Quartz 4

05-cow

8 min read

实验：写时复制

虚拟内存提供了一层间接性：内核可以通过将PTE标记为无效或只读来拦截内存引用，从而导致页面错误，并且可以通过修改PTE来更改地址的含义。计算机系统中有一句话，即任何系统问题都可以通过一层间接性来解决。本实验探讨一个例子：写时复制分支。

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

git fetch
git checkout cow
make clean

问题

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

解决方案

在实现写时复制（COW）fork()时，您的目标是在实际需要时（如果需要）推迟分配和复制物理内存页面。

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

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

实现写时复制fork（困难）

您的任务是在xv6内核中实现写时复制fork。如果您修改后的内核能够成功执行cowtest和usertests -q程序，则表示您已完成。

为了帮助您测试实现，我们提供了一个名为cowtest的xv6程序（源代码位于user/cowtest.c中）。cowtest运行各种测试，但即使是第一个测试在未修改的xv6上也会失败。因此，最初您会看到：

$ cowtest
simple: fork() failed
$

“simple”测试分配了超过一半的可用物理内存，然后进行了fork()。由于没有足够的空闲物理内存来给子进程提供完整的父进程内存副本，fork失败了。

完成后，您的内核应通过cowtest和usertests -q中的所有测试。也就是说：

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

以下是一个合理的攻击计划。

  1. 修改uvmcopy()将父进程的物理页面映射到子进程中，而不是分配新页面。对于已设置了PTE_W的页面，清除子进程和父进程的PTE中的PTE_W。
  2. 修改usertrap()以识别页面错误。当发生写入页面错误，并且原始页面是可写的COW页面时，使用kalloc()分配一个新页面，将旧页面复制到新页面，并使用设置了PTE_W的PTE将新页面安装到PTE中。原始只读页面（未映射PTE_W，例如文本段中的页面）应保持只读并在父进程和子进程之间共享；试图写入此类页面的进程应该被终止。
  3. 确保每个物理页面在最后一个PTE引用消失时释放，但不能在此之前释放。一种很好的方法是为每个物理页面保留一个“引用计数”，用于引用该页面的用户页表的数量。当kalloc()分配页面时，将页面的引用计数设置为1。当fork导致子进程共享页面时，增加页面的引用计数，并在任何进程从其页表中删除页面时递减页面的计数。如果页面的引用计数为零，则kfree()只需将页面放回空闲列表。在固定大小的整数数组中保持这些计数是可以的。您需要设计一种方案，用于对数组进行索引并选择其大小。例如，您可以使用页面的物理地址除以4096来索引数组，并且给数组分配的元素数量等于kalloc.c中由kinit()放置在空闲列表上的任何页面的最高物理地址。请随意修改kalloc.c（例如kalloc()和kfree）以维护引用计数。
  4. 修改copyout()以在遇到COW页面时使用与页面错误相同的方案。

一些建议：

  • 为记录每个PTE是否为COW映射，有一个记录的方式可能会很有用。您可以使用RISC-V PTE中的RSW（保留给软件使用）位来实现此目的。
  • usertests -q探索了cowtest未测试的场景，因此不要忘记检查所有测试是否都通过。
  • 在kernel/riscv.h的末尾有一些有用的宏和页面表标志的定义。
  • 如果发生COW页面错误并且没有可用的内存，则应终止该进程。

可选挑战练习

  • 测量您的COW实现减少了xv6复制的字节数和分配的物理页面数。找到并利用进一步减少这些数字的机会。

Graph View