实现写时复制 (Copy-On-Write)

系统实验 (基于 xv6)

截止时间：2024年12月22日 23:59

提交内容：

  1. 代码源文件 学号.zip: 请注意代码中应有必要的注释；
  2. 实验报告 学号.pdf：简要描述实验中遇到的关键问题及解决方案、印象最深的 bugs、或者额外实现的功能等即可 (1～2 页)。

提交方式：TBD

在执行 fork() 系统调用时，操作系统需要将父进程地址空间复制一份副本给子进程。此时，如果父进程所使用的内存空间很大，复制会需要很长时间，并且这个复制开销很可能是无意义的 (例如，子进程在 fork() 返回后立即执行 execve())。为了降低 fork() 的执行开销并提高内存资源的利用率，现代操作系统会使用写时复制 (Copy-On-Write, COW)这一机制。 在本实验中，我们需要为 xv6 增加这一机制，以此来熟悉操作系统内存管理的一些相关概念和实现细节。

运行如下命令下载实验框架代码，并切换到 lab-cow 分支：

git clone https://git.nju.edu.cn/oslab/os-lab-2024fall.git
cd os-lab-2024fall
git checkout lab-cow

如果你在 Lab 2 的基础上进行实验，直接切换分支即可：

git checkout -b lab-cow origin/lab-cow

🗒️ 实验内容

在本次实验中，我们需要为 xv6 实现基于写时复制的 fork() (COW Fork)，从而将物理页的分配和复制推迟到实际需要的时候：即当父进程调用 fork() 时，子进程直接设置其 PTE 指向父进程的物理页 (父子进程共享物理页)，并设置 PTE 为只读；随后，当其中一个进程需要对某个页进行写操作时，就会发生异常中断，此时在内核相应的 Interrupt Handler 中就可实际分配并复制相应物理页的内容，并将 PTE 更新为可写；最终，在异常中断返回后，进程就可以按正常方式写这个页。

在上述流程中，一个关键问题是在发生异常中断时，如何判断造成异常的原因是触发 COW 机制、还是访问了一个非法的虚拟地址？ 为了解决这个问题，我们可以在 xv6 的 PTE 中添加一个标志位，用于标记该页面是否与 COW Fork 相关。另外，COW Fork 会导致同一个物理页被多个进程的页表引用，此时还需要记录每个物理页被引用的次数，以此来判断在进程结束时是否能释放对应的物理内存。

你可以参考以下流程来实现本次实验：

  1. 修改 kernel/vm.c 中的 uvmcopy() 函数，使其在 fork() 时不复制父进程的整个内存空间，而是让子进程共享。在这一过程中，需要修改父进程和子进程的 PTE，包括将页标记为只读 (擦除可写标志位 PTE_W)，并设置 COW 标志位 (需要在合适的位置定义 PTE 的内容)。

  2. 修改 kernel/trap.c 中的 usertrap() 函数，使其在处理中断时，判断是否是 COW Fork 产生的中断异常。如果是，则分配和复制对应的物理页，并更新 PTE 为可写 (注意，如果该页面本来就是只读页面，则属于进程访问了非法地址，此时应杀死该进程)。

  3. 在合适的时机释放物理内存。为此，需要维护一个新的数据结构来记录各物理页的引用数，在此基础上，在第一次分配物理页时设置引用计数初始值 (kalloc())、在共享物理页时增加引用数、在进程从页表删除物理页时减少引用数 (kfree()、或者触发 COW 异常中断而导致页面复制时)、并最终当物理页引用数为 0 时释放物理内存。

  4. 修改 kernel/vm.c 中的 copyout() 函数，从内核复制页面到用户空间时，使用同样的方案处理 COW 页面。

在 COW Fork 实现正确的情况下，你应该可以通过 cowtest 测试：

$ cowtest
simple: ok
simple: ok
three: ok
three: ok
three: ok
file: ok
ALL COW TESTS PASSED

在 xv6 上，添加 COW 标志位、引用计数等是相对简单的。然而，在实际的操作系统中，这些操作可能会变得复杂，例如：Patching until the COWs come home。

其它需求说明

你可以采用不同的实现方式来完成本实验，但对 xv6 代码的修改应局限于以下文件：

  • kernel/defs.h
  • kernel/riscv.h
  • kernel/kalloc.c
  • kernel/trap.c
  • kernel/vm.c

💭 Tips

  • kernel/riscv.h 中包含了一些有用的宏定义；
  • COW 标志位的设置可以参考 PTE 中已有的 PET_W 等标志位的定义和修改方式；
  • 可以利用 xv6 中的一些已有函数来实现你需要的功能，阅读这些代码并在需要的时候使用：
    • kernel/vm.c/walk()：获取虚拟地址对应的页表的页表项；
    • kernel/vm.c/mappages()：映射虚拟地址到物理地址，创建页表项；
    • kernel/vm.c/uvmunmap()：移除虚拟地址的映射；
    • kernel/string.c/memmove()：复制一块内存；
  • 物理页引用数可以通过类似如下的 refcnt 结构来实现，其中通过物理地址除以 PGSIZE 来索引对应的物理页：
    struct {
  struct spinlock lock;
  int count[(PGROUNDUP(PHYSTOP) - KERNBASE)/PGSIZE];
} refcnt;

    注意这里可能存在多个进程同时尝试修改 refcnt 的数据竞争情况，因此还需要使用 spinlock 来实现互斥，即在修改数据前需要使用 acquire() 来获取锁，并在修改结束后使用 release() 释放锁。

  • 如果一个 COW 页面需要被复制，但没有足够的空间，应该杀死该进程；
  • 产生中断异常时需要对地址的合法性进行检查，例如：是否超过虚拟地址的范围、是否请求了 Guard Page 内的地址等，如果地址不合法，应该杀死进程；
  • 根据 RISC-V 手册，页错误的 Supervisor Trap Cause (scause) 编号为 15。

📊 结果评估

你可以使用以下测试用例在本地测试：

1) cowtest：包含不同难度的针对 COW Fork 的测试用例。

$ cowtest
simple: ok
simple: ok
three: ok
three: ok
three: ok
file: ok
ALL COW TESTS PASSED

2) usertests：该测试包含了一些 cowtest 不涉及的情况。你对 xv6 的修改应当不影响这些测试用例的正常执行，如果这里的一些测试用例执行失败 (即使 cowtest 执行通过)，你的实现很有可能在已有功能上引入了新的 Bugs。

$ usertests -q
usertests starting
# ...
OK
# ...
OK
ALL TESTS PASSED