Lab6 写时复制 fork

虚拟内存提供了一个间接层：内核可以通过将页表项（PTE）标记为无效或只读来拦截内存访问（这会导致页错误），并且可以通过修改页表项来改变地址的含义。计算机系统中流传着一句话：任何系统问题都可以通过增加一个间接层来解决。懒加载分配实验提供了一个例子，本实验将探讨另一个例子：写时复制（Copy-on-Write） Fork

要开始本实验，请切换到 cow 分支：

git fetch
git checkout cow
make clean

问题所在

在 xv6 中，fork() 系统调用会将父进程的所有用户空间内存完整地复制一份给子进程。如果父进程占用的内存很大，这个复制过程会非常耗时。更糟糕的是，这种复制工作常常是白费力气；例如，在一个 fork() 之后，子进程如果立即调用 exec()，那么子进程会丢弃掉刚刚复制过来的内存，而其中大部分内存可能根本就没被使用过。另一方面，如果父子进程都使用某个页面，并且其中一个或两个进程需要写入该页面，那么复制一份副本就是确实有必要的

解决方案

写时复制（COW）fork() 的目标是推迟为子进程分配和复制物理内存页面的时机，直到真正需要这些副本时（如果真的需要的话）

写时复制 fork() 只为子进程创建一个页表，其中用户内存的页表项（PTE）指向父进程的物理页面。同时，COW fork() 会将父子进程中的所有用户内存页表项都标记为不可写。当任何一个进程尝试写入这些被标记为 COW 的页面时，CPU 会强制触发一个页错误（page fault）。

内核的页错误处理程序会检测到这种情况，然后为出错的进程分配一个新的物理内存页面，将原始页面的内容复制到新页面中，并修改出错进程中对应的页表项，使其指向这个新页面，同时将该页表项标记为可写。当页错误处理程序返回后，用户进程就可以顺利地写入它自己的那份页面副本了。

COW fork() 使得用户内存物理页的释放过程变得稍微复杂一些。一个给定的物理页面可能会被多个进程的页表所引用，只有当最后一个引用消失时，这个物理页面才能被释放。

实现写时复制

hard

你的任务是在 xv6 内核中实现写时复制 fork。如果修改后的内核能够成功运行 cowtest 和 usertests 这两个程序，那么你就完成了任务。

为了帮助你测试，我们提供了一个名为 cowtest 的 xv6 程序（源代码在 user/cowtest.c）。cowtest 会运行多种测试，但在未修改的 xv6 上，即便是第一个测试也会失败。因此，一开始你会看到：

cowtest
simple: fork() failed

“simple” 测试会分配超过一半的可用物理内存，然后调用 fork()。这个 fork 会失败，因为没有足够的空闲物理内存来为子进程创建父进程内存的完整副本。

当你完成后，你的内核应该能通过 cowtest 和 usertests 中的所有测试。也就是说：

$ cowtest
simple: ok
simple: ok
three: zombie!
ok
three: zombie!
ok
three: zombie!
ok
file: ok
ALL COW TESTS PASSED
$ usertests
...
ALL TESTS PASSED
$

下面是一个合理的实施方案：

修改 uvmcopy() 函数，使其将父进程的物理页面映射到子进程，而不是分配新页面。同时，清除父子进程页表项中的 PTE_W（可写）标志位。
修改 usertrap() 函数来识别页错误。当一个写时复制（COW）页面发生页错误时，使用 kalloc() 分配一个新页面，将旧页面的内容复制到新页面，然后将这个新页面安装到页表项（PTE）中，并设置 PTE_W 标志位。
确保每个物理页面在最后一个指向它的页表项消失时才被释放——但不能提前释放。一个好的方法是为每个物理页面维护一个**“引用计数”**，记录有多少个用户页表引用了该页面。当 kalloc() 分配页面时，将其引用计数设为 1。当 fork 导致子进程共享页面时，增加该页面的引用计数。每当有进程从其页表中移除对该页面的映射时，就减少其引用计数。kfree() 函数应该只在页面引用计数为零时才将其放回空闲列表。你可以使用一个固定大小的整型数组来保存这些计数。你需要设计一个方案来索引这个数组并确定其大小。例如，你可以用页面的物理地址除以 4096 来作为数组索引，并将数组的大小设置为 kinit() 函数（在 kalloc.c 中）放入空闲列表的最高物理地址所对应的页面数量。
修改 copyout() 函数，当它遇到一个写时复制（COW）页面时，采用与处理页错误相同的机制

一些提示：

懒加载页面分配实验可能已经让你熟悉了 xv6 内核中与写时复制相关的大部分代码。但是，你不应该基于你的懒加载实验方案来做这个实验；请按照上面的指示，从一个全新的 xv6 副本开始。
为每个页表项（PTE）记录它是否是一个 COW 映射可能会很有用。你可以使用 RISC-V 页表项中的 RSW（软件预留）位来实现这一点。
usertests 会测试一些 cowtest 没有覆盖到的场景，所以别忘了检查两个测试程序是否都能全部通过。
在 kernel/riscv.h 文件的末尾有一些关于页表标志位的宏和定义，它们可能会很有帮助。
如果发生 COW 页错误时没有空闲内存，该进程应该被终止（killed）。

提交实验

实验到此结束。请确保你通过了 make grade 的所有测试。如果实验中有问题需要回答，别忘了在 answers-lab-name.txt 文件中写下你的答案。提交你的代码变更（包括添加 answers-lab-name.txt 文件），然后在实验目录下输入 make handin 来提交你的实验。

花费时间

创建一个新文件 time.txt，在里面只写入一个整数，代表你花在这个实验上的小时数。别忘了 git add 和 git commit 这个文件。

提交

你将通过提交网站来上交你的作业。在提交任何作业或实验之前，你需要从提交网站申请一个 API 密钥。在提交你实验的最终代码变更后，输入 make handin 来提交实验。

git commit -am "ready to submit my lab"
[util c2e3c8b] ready to submit my lab
 2 files changed, 18 insertions(+), 2 deletions(-)
 
make handin
tar: Removing leading `/' from member names
Get an API key for yourself by visiting https://6828.scripts.mit.edu/2020/handin.py/
Please enter your API key: XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
  % Total    % Received % Xferd  Average Speed   Time    Time     Time  Current
                                 Dload  Upload   Total   Spent    Left  Speed
100 79258  100   239  100 79019    853   275k --:--:-- --:--:-- --:--:--  276k
$

make handin 会将你的 API 密钥保存在 myapi.key 文件中。如果你需要更改 API 密钥，只需删除这个文件，然后让 make handin 重新生成它（myapi.key 文件中不能包含换行符）。

如果你运行 make handin 时有未提交的更改或未跟踪的文件，你会看到类似下面的输出：

 M hello.c
?? bar.c
?? foo.pyc
Untracked files will not be handed in.  Continue? [y/N]

请检查以上几行，确保你的实验解决方案需要的所有文件都已被跟踪，即没有列在以 ?? 开头的行中。你可以使用 git add filename 命令来让 git 跟踪你创建的新文件。

如果 make handin 无法正常工作，请尝试使用 curl 或 Git 命令修复问题。或者你也可以运行 make tarball。这会为你创建一个 tar 压缩包，然后你可以通过我们的网站界面上传它。

请运行 make grade 来确保你的代码通过了所有测试。
在运行 make handin 之前，请提交所有修改过的源代码。
你可以在 https://6828.scripts.mit.edu/2020/handin.py/ 查看你的提交状态并下载已提交的代码。

可选的挑战练习

修改 xv6，使其同时支持懒加载页面分配和写时复制（COW）
测量你的 COW 实现减少了 xv6 复制的字节数和分配的物理页面数量。寻找并利用机会来进一步减少这些数字

Outaink's Blog

探索