ThinkLab

The problem 问题

xv6 中的 fork()系统调用会将父进程的用户空间内存全部复制到子进程。如果父进程较大，复制过程可能需要很长时间。更糟糕的是，这项工作往往大部分是浪费的：fork()后子进程通常会立即执行 exec()，这会丢弃复制的内存，而且通常并未使用大部分复制的内容。另一方面，如果父进程和子进程都使用同一复制页面，并且一个或两个进程对其进行写入，那么复制就是真正必要的。

Solution 方案

实现写时复制（COW）fork()的目标是，如果可能的话，推迟分配和复制物理内存页面，直到实际需要时才进行。

写时复制分叉()仅为主进程创建一个页表，其中用户内存的 PTE 指向父进程的物理页。写时复制分叉()将父进程和子进程中的所有用户 PTE 标记为只读。当任一进程尝试写入这些写时复制页时，CPU 将强制触发页错误。内核页错误处理程序检测到此情况，为出错进程分配一页物理内存，将原始页复制到新页中，并修改出错进程中的相关 PTE 以指向新页，这次将 PTE 标记为可写。当页错误处理程序返回时，用户进程将能够写入其页的副本。

COW 的 fork()使得释放实现用户内存的物理页变得稍微复杂一些。一个给定的物理页可能被多个进程的页表引用，并且只有在最后一个引用消失时才应该被释放。在一个简单的内核如 xv6 中，这种记录工作相对直接，但在生产内核中要正确处理这可能很困难；例如，参见 Patching until the COWs come home。

实现 copy-on-write fork

你的任务是实现在 xv6 内核中的 copy-on-write fork。如果你的修改后的内核能成功执行 cowtest 和'usertests -q'程序，那么你就完成了。

为了帮助你测试你的实现，我们提供了一个名为 cowtest 的 xv6 程序（源代码在 user/cowtest.c）。cowtest 运行各种测试，但即使是第一个测试在未修改的 xv6 上也会失败。因此，最初你会看到：
$ cowtest
simple: fork() failed
$ 
"简单"测试会分配超过可用物理内存一半的资源，然后执行 fork()。fork()失败是因为没有足够的空闲物理内存来为子进程提供父进程内存的完整副本。

当你完成时，你的内核应该通过 cowtest 和 usertests -q 中的所有测试。具体如下：
$ cowtest
simple: ok
simple: ok
three: ok
three: ok
three: ok
file: ok
forkfork: ok
ALL COW TESTS PASSED
$ usertests -q
...
ALL TESTS PASSED
$
这是一个合理的计划。

修改 uvmcopy() 以将父进程的物理页映射到子进程，而不是分配新页。清除子进程和父进程的 PTE 中的 PTE_W ，对于设置了 PTE_W 的页。

修改 vmfault() 以识别页错误。当在原本可写的 COW 页上发生写页错误时，使用 kalloc() 分配一个新页，将旧页复制到新页，并在 PTE 中安装新页，设置 PTE_W 。原本是只读的页（未映射 PTE_W ，如文本段的页）应保持只读并共享于父进程和子进程之间；尝试写入这种页面的进程应被终止。

确保当最后一个 PTE 引用某个物理页时才释放该页——但在此之前不能释放。一种好的做法是为每个物理页维护一个"引用计数"，记录有多少用户页表引用该页。当 kalloc() 分配一个页时，将其引用计数设为 1。当 fork 导致子进程共享一个页时，增加该页的引用计数，每当任何进程将其从页表中移除时，减少该页的计数。 kfree() 只有在页的引用计数为 0 时才将其放回空闲列表。可以将这些计数保存在一个固定大小的整数数组中。你需要设计一个方案来索引这个数组并确定其大小。例如，可以用页的物理地址除以 4096 来索引数组，并将数组元素数量设为 kalloc.c 中 kinit() 在空闲列表中放置的最高物理地址。你可以自由修改 kalloc.c（例如 kalloc() 和 kfree() ）来维护引用计数。

修改 copyout()，使其在遇到写时复制页时使用与页错误相同的方案。

一些提示：

对于每个 PTE，记录它是否是 COW 映射的方式可能很有用。你可以使用 RISC-V PTE 中的 RSW（保留用于软件）位来实现这一点。

usertests -q 探索了 cowtest 未测试的场景，所以别忘了检查两个场景的所有测试都通过。

kernel/riscv.h 的末尾有一些有助于页面表标志的宏和定义。

如果发生 COW 页面错误且没有空闲内存，进程应该被终止。

我的解决方案一共会更改四个文件：

kalloc.c
- 在kmem中定义int refcnt[]。这是用来记录每一个page有几个页表正在引用。最大的大小应该是PHYSTOP/PGSIZE。
- kfree()时检查当前的页面有无引用，如果还有引用则只减refcnt，不真正free（记得松锁）。
- kalloc()中将refcnt初始值设置为1。
- 定义increfork()，增加一个pa的refcnt。
defs.h
- 增加increfork()的定义。
riscv.h
- 增加宏PTE_COW，使用页表项中software-defined bit，定义为1L <<8。
- 增加宏PA2PREFIX，将pa转为refcnt的index。转换方式为pa / PGSIZE，即4096，则定义为pa >> 12。
vm.c
- 修改uvmcopy，如果当前pte可写（即不是text或者其他区域），则去除当前pte的写权限，并定义为COW。在新页表中增加entry，map到物理地址，并增加当前物理地址的refcnt。
- 修改vmfault，判断当前pte是否为COW，即!read && pte && (*pte & PTE_V) && (*pte & PTE_COW)。如果为COW，则创建新页面，将原pa中内容memmove过去，并去除新perm中的COW标识，新增PTE_W标识。free一次pa。
- 修改copyout()，如果当前pte不可写并且为COW，调用vmfault()尝试处理，处理失败则报错。

结果

== Test running cowtest == 
$ make qemu-gdb
(39.8s) 
== Test   simple == 
  simple: OK 
== Test   three == 
  three: OK 
== Test   file == 
  file: OK 
== Test   forkfork == 
  forkfork: OK 
== Test usertests == 
$ make qemu-gdb
(109.7s) 
== Test   usertests: copyin == 
  usertests: copyin: OK 
== Test   usertests: copyout == 
  usertests: copyout: OK 
== Test   usertests: all tests == 
  usertests: all tests: OK 
== Test time == 
time: OK 
Score: 130/130

xv6内核扩展5：写时复制fork()

The problem 问题

Solution 方案

实现 copy-on-write fork

结果

探索主题