网页：https://pdos.csail.mit.edu/6.S081/2023/labs/cow.html

---

任务1：Implement copy-on-write fork(hard) (完成)

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

解决方案：
实现写时复制（COW）fork()的目标是将物理内存页的分配和复制推迟到真正需要这些副本的时候，如果有的话。 COW fork()只为子进程创建一个页表，用户内存的PTE指向父进程的物理页面。COW fork()将父子进程中所有的用户PTE标记为只读。当任一进程尝试写入这些COW页面时，CPU将强制产生一个页错误。内核的页错误处理程序检测到这种情况，为出错进程分配一页物理内存，将原始页面复制到新页面，并修改出错进程中的相关PTE，使其指向新页面，这次将PTE标记为可写。当页错误处理程序返回时，用户进程将能够写入其页面的副本。

COW fork()使得释放实现用户内存的物理页面变得更加复杂。一个给定的物理页面可能被多个进程的页表引用，并且只有在最后一个引用消失时才应该被释放。在像xv6这样的简单内核中，这种簿记工作相对直接，但在生产内核中，这可能会很难做对；例如，参见《Patching until the COWs come home》（修补直到COW回家）。

根据讲义，这次的测试程序是 cowtest，在调用 fork 之前，用户程序会使用多余一半的内存。因此如果没有实现 COW fork，那么 cowtest 会失败

让我们看看 cowtest 源码：

int
main(int argc, char *argv[])
{
  simpletest();

  // check that the first simpletest() freed the physical memory.
  simpletest();

  threetest();
  threetest();
  threetest();

  filetest();

  printf("ALL COW TESTS PASSED\n");

  exit(0);
}

如上是 main 函数，大概过了一遍 simpletest, threetest, filetest 的源码。

测试内容是：
simpletest 检测 COW 是否节约了内存、是否能够释放内存
threetest 检测 COW 是否能够在子进程写入内存时分配新的页
filetest 检测读取这些内存时是否会出错，尤其是内核的 copyout 是否能和 COW 配合完美

我们直接跟着讲义和提示写代码吧：
1.Modify uvmcopy() to map the parent’s physical pages into the child, instead of allocating new pages. Clear PTE_W in the PTEs of both child and parent for pages that have PTE_W set. (设置为只读的目的是为了以后写入的时候能够触发 page fault；父子进程都要设置为 Read-only 是因为都需要触发 page-fault，当父进程对某块内存写入时，需要分配一个相应的内存页给子进程，否则子进程会访问到父进程写入的数据)
2. Modify usertrap() to recognize page faults. When a write page-fault occurs on a COW page that was originally writeable, allocate a new page with kalloc(), copy the old page to the new page, and install the new page in the PTE with PTE_W set. Pages that were originally read-only (not mapped PTE_W, like pages in the text segment) should remain read-only and shared between parent and child; a process that tries to write such a page should be killed. (COW 不能让本来只读的页面变成可写)
3. Ensure that each physical page is freed when the last PTE reference to it goes away – but not before. A good way to do this is to keep, for each physical page, a “reference count” of the number of user page tables that refer to that page. Set a page’s reference count to one when kalloc() allocates it. Increment a page’s reference count when fork causes a child to share the page, and decrement a page’s count each time any process drops the page from its page table. kfree() should only place a page back on the free list if its reference count is zero. It’s OK to to keep these counts in a fixed-size array of integers. You’ll have to work out a scheme for how to index the array and how to choose its size. For example, you could index the array with the page’s physical address divided by 4096, and give the array a number of elements equal to highest physical address of any page placed on the free list by kinit() in kalloc.c. Feel free to modify kalloc.c (e.g., kalloc() and kfree()) to maintain the reference counts.（当对于一个页面的所有引用都消失时，再释放这一页的内存）
4. Modify copyout() to use the same scheme as page faults when it encounters a COW page. (需要对 copyout 做一些修改)
5. It may be useful to have a way to record, for each PTE, whether it is a COW mapping. You can use the RSW (reserved for software) bits in the RISC-V PTE for this. (可以用 RSW bits 来记录一个 PTE 是否是一个 COW mapping)
6. Some helpful macros and definitions for page table flags are at the end of kernel/riscv.h. （kernel/riscv.h 里的内容可能有用）
7. If a COW page fault occurs and there’s no free memory, the process should be killed. (当发生 COW page fault 但没有足够内存时，进程应该被杀掉)

自己的提示：
在做 LAB3 : pagetable 的时候遇到过这么一张图，在这里也很有用

RSW bits 是 8~9

开始写代码：
1.在 vm.c : uvmcopy 添加 printf 打印 PTEs，发现 RSW bits 一直都是 0，说明平时不用都是置为 0
2.在 vm.c : uvmcopy 去掉分配内存和拷贝内存内容的部分，仅仅保留拷贝映射的部分。同时，设置老新页表的 RSW bits = original WR bits。此外，错误处理中去掉释放内存的部分，仅保留删除映射的部分。
3.在 trap.c : usertrap 中新添一个分支 “if scause == 0xf”。(0xd 是 load page fault，0xf 是 store page fault)使用 stval 寄存器的值作为触发 page fault 的页面起始地址va。使用 RSW bits 判断是否属于 COW pages，同时判断原来的权限。如果不属于 COW pages，直接 kill 掉；如果属于且本来可写，那么使用 kalloc 分配页面并设置为可写；如果属于 COW pages 但本来不可写，那么直接 kill 掉。如果使用 kalloc 由于内存不足失败，那么直接 kill 掉。这里注意使用 kalloc 分配页面成功时，修改 PTE 映射时要 clear RSW bits，否则以后该页被用户程序设置为只读时，发生 page-fault 会使用残留的 RSW bits 设置为可写。
4.在 kalloc.c 中维护一个全局的 reference_count 数组，大小为 [(PHYSTOP - KERNBASE) / PGSIZE]。在 kalloc 中，根据分配的页面的起始物理地址，把 reference_count 数组中对应元素设置为 1。把 mappages 包装出一个新的函数 uvmmap，替换掉原来调用 mappages 的地方。在 uvmcopy 中增加 reference_count 数组元素 (一个进程结束后，由于这个进程分配的页就应该回到 freelist，所以只考虑用户进程计算引用数，不考虑内核引用)。在 kfree 中减少 reference_count 数组元素，到 0 时真正释放内存（原因是，fork 后，多个程序会调用多次 kfree，所以在 kfree 中计数）。第一次调用 kfree (kinit) 的时候还没有调用过 kalloc，因此拷贝一个 kfree_initialize 来替换 kinit 中的 kfree
5.由于 copyout 会在内核态发生对 COW page 写入的操作，所以这里也要进行 page fault 的处理。如果发现是 COW page，为了不影响其它进程访问到的内存内容，我们调用 kalloc 申请一个新的页，然后拷贝原始内容，修改页表 … （跟 page fault 很相似）

出现内存泄漏的时候，可以使用 gdb watch 去观察 reference_count 数组的某些元素，找到修改这些元素的代码，这样能帮助我们快速调试。

出现内存泄漏的时候，调试思路为搞清楚几个问题：1.哪些内存地址没有被释放？ 2.这些没被释放的内存地址是什么时候被分配的？3.它们为什么没有被释放？

一个很容易出错的地方：使用 fork 后，父子进程的 PTE 的 PTE_W 都要 clear，这是为了防止父进程对内存进行修改后，子进程访问到父进程修改的内容。那么此时有一个问题，父子进程都发生 store page fault 并且申请了新的 kalloc() 后，那么此时申请了两个新页，一开始的那个页就悬空泄露了，会造成内存泄漏。

个人感觉这次 LAB 最容易出 bug 的地方就是内存泄漏。

处理完后，运行 cowtest 很顺利如下：

再运行 usertests，发现报错，经过观察，发现只是对代码的修改导致代码在遇到错误情况时（比如内存不足或写入一个超高地址时应该返回 -1,或者直接把用户进程杀掉）没有返回正确的错误码，稍作调整即可。再次测试，顺利，如下：

所有 usertests 顺利通过

运行 make grade，所有测试顺利通过

---