MIT 6.1810(6.828/6.S081) 操作系统工程 Lab5 Copy-on-Write Fork

前言

虚拟内存提供某种间接引用：内核可以通过将PTE标记为无效或只读来截获内存引用，从而导致页面错误，也可以通过修改PTE来更改地址含义。计算机系统中有一个说法：任何系统问题都能通过某种间接引用来解决。本实验探讨了一个示例：copy-on-write(COW)fork

问题

xv6中的fork()syscall复制父进程所有用户空间的内存到子进程中。如果父进程很大，这个拷贝过程就会花很长时间。更糟糕的是，这个拷贝经常被浪费：fork()函数后子进程通常跟随一个exec()，这会丢弃复制的内存、通常不使用大部分内存。另一方面，若父子进程其中一个或都写入了这个复制的页面，则这个拷贝过程是需要的。

解决方案

你在实现COW fork()过程中的目标是，推迟开辟空间和拷贝物理内存页直到真正需要这些拷贝时。
COW fork()仅为子进程创建一个页表，其中用于用户内存的PTE指向父进程物理页。COW fork()将父子进程所有用户PTE都标记为只读。当任一进程尝试写入这些 COW 页之一时，CPU 将强制出现页错误。内核页面错误处理程序检测到这种情况，为错误进程分配一页物理内存，将原始页面复制到新页面中，并在错误进程中修改相关 PTE 以引用新页面，这次 PTE 标记为可写。当页面错误处理程序返回时，用户进程将能够写入其页面副本。

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

要求

在xv6内核中实现copy-on-write fork。

为帮助你的实现，我们已经提供了一个程序指令cowtest（源码在user/cowtest.c）。cowtest运行各种测试，但如果过没有更改xv6即便第一个测试也会失败。
这个“简单的”测试开辟超过一半的可用物理内存，然后fork()s。一般情况下，fork会因为没有足够的空闲物理内存给子进程一个完整的拷贝而失败。
当你完成后，应当通过cowtest usertests -q的所有测试。

合理的attack计划

1. 修改 uvmcopy() 以将父级的物理页面映射到子级，而不是分配新页面。清除子级和父级的 PTE 中已被置位PTE_W的PTE_W位。
2. 修改 usertrap() 以识别页面错误。当最初可写的 COW 页面上发生写入页面错误时，使用 kalloc() 分配一个新页面，将旧页面复制到新页面，并在被置位为PTE_W的 PTE 中安装新页面。最初为只读的页面（未映射PTE_W，如文本段中的页面）应保持只读并在父进程和子进程之间共享; 尝试编写此类页面的进程应该被kill()。
3. 确保每个物理页在最后一个 PTE 引用消失时被释放–但不是之前。执行此操作的一个好方法是为每个物理页面保留引用该页面的用户页表数量的“引用计数”。将页面的引用计数设置为 1 当 kalloc() 分配它时。当 fork 导致子级共享页面时，递增页面的引用计数，并在每次任何进程从其页表中删除页面时递减页面的计数。kfree()应该只在引用计数为零时将页面放回自由列表。可以将这些计数保存在固定大小的整数数组中。您必须制定一个如何索引数组以及如何选择其大小的方案。例如，你可以用页面的物理地址除以 4096 来索引数组，并为数组提供一个数字，这个数等于 kalloc.c 中的kinit()放置在空闲列表中的任何页面的最高位物理地址。可以随意修改kalloc.c（例如kalloc(), kfree()）来维护引用计数。
4. 修改 copyout() 以在遇到 COW 页面时使用与页面错误相同的方案。

提示

• 记录每个PTE是否是COW映射会很有用。为此，你可以使用RISC-V PTE的RSW（软件预留）置位。
• 有关页表flags的一些有用的宏和定义位于kernel/riscv.h末尾。
• 若发生一个COW页面错误且内存不够，则该进程应当被kill

实现

1. 复制页表但推迟复制页表内容：根据提示，我从fork()中调用的uvmcopy()入手。uvmcopy()原本的作用是：把父进程页表中每个PTE所指内容都拷贝到新开辟的空间内并在子进程的页表上形成映射。现在需要把开辟空间这一步去掉，直接在子页表形成映射，但是要改变flags。为了让代码好看点、保持逻辑清晰，我创建一个新函数cow_uvmcopy()并在uvmcopy()中调用它。新函数基本与老函数保持一致，不过去掉开辟空间、加上改变flags：

   int cow_uvmcopy(pagetable_t old, pagetable_t new, uint64 sz) {
       pte_t *pte;
       uint64 pa, i;
   
       for(i = 0; i 

   有关flags的设置：首先要把父子进程的PTE_W给去掉，这样才能在将来触发page fault。然后就是加上关于cow的标记，需要在riscv.h中自定义，可以定义在预留位上（详见Lab3 page tables）#define PTE_C (1L 。将来可通过该bit位判断是原本就不可读的还是cow机制强加的不可读。

2. 更改trap以碰到page fault时开辟空间拷贝内容：根据题目给的方案第2点，需要在usertrap()中识别需要cow的page fault情况，开辟空间并拷贝，然后改变只读的权限置位进而使程序能够写入指定内存。

   • usertrap()本身就算一个选择结构，比如当发生系统调用时，通过r_scause() == 8进入syscall分支调用syscall()。因此此处只需要添加一个else if分支来处理page fault
   • 关于识别需要cow的page fault情况：其实在2020年的课程中，本实验前边还有一个实验[Lab: xv6 lazy page allocation

   ](https://pdos.csail.mit.edu/6.828/2020/labs/lazy.html)，其中给出了关于识别page fault的提示r_scause() == 13 || r_scause() == 15（也可以只判断15时，13代表读，15代表写）。

   • 具体实现。由于copyout也需要处理此情况，因此把业务逻辑代码放入函数封装

     if (...) { // 其他情况
         ...
     } else if (r_scause() == 13 || r_scause() == 15) { // page fault情况
         // 页面错误, 分配空间并拷贝
         // 在walkaddr函数完成情况判断和分配空间并拷贝的业务
         if (cow_walkaddr(p->pagetable, r_stval()) == 0) { 
             goto error;  //处理失败或遇到并非cow的page fault
     } else {
     error: 
         // 该分支通过打印信息然后kill掉进程来处理未知中断情况，
         //对于不需要cow的page fault情况可设置标签将其跳转到此处
         printf("usertrap(): unexpected scause %p pid=%dn", r_scause(), p->pid);
         printf("            sepc=%p stval=%pn", r_sepc(), r_stval());
         setkilled(p);
     }

   • 完成情况判断和分配空间并拷贝业务的cow_walkaddr()。参考walkaddr()函数（通过给定page table和虚拟地址返回物理地址，失败返回0）。cow_walkaddr()逻辑是：通过给定page table和虚拟地址，若非cow情况则象walkaddr()一样返回物理地址；若是cow情况，则开辟新空间、拷贝内存、接触旧的只读映射、建立新的可写映射。

     uint64 cow_walkaddr(pagetable_t pagetable, uint64 va) {
         pte_t *pte;
         uint64 pa;
         int flags;
     
         if(va >= MAXVA)
             return 0;
     
         pte = walk(pagetable, va, 0); // 虚拟地址对应PTE
         if (pte == 0) return 0;
         else if ((*pte & PTE_V) == 0) return 0;
         else if ((*pte & PTE_U) == 0) return 0;
     
         pa = PTE2PA(*pte);
     
         flags = PTE_FLAGS(*pte);
         if (flags & PTE_W) return pa; // 若有PTE_W说明不是cow
         else if ((flags & PTE_C) == 0) return 0;  // 判断是否带PTE_C
     
         void* new_mem = kalloc();  // 新页面空间    
         if (new_mem == 0) 
         return 0;
     
         memmove(new_mem, (const void*)pa, PGSIZE);  // 拷贝页面空间
         uvmunmap(pagetable, PGROUNDDOWN(va), 1, 1);  // 解除map并释放空间
         flags = (flags | PTE_W) ^ PTE_C;  // 新flags
         // 建立新map
         if (mappages(pagetable, PGROUNDDOWN(va), PGSIZE, (uint64)new_mem, flags) != 0) {
             kfree(new_mem);
             return 0;
         }  
         return (uint64)new_mem;
     }

3. 内存空间引用计数：根据提示可知基本思路是：对每个物理内存都标记一个数字表示该内存被引用次数，当kalloc()的时候置1，每次fork和copyout的时候+1；而kfree()的时候先将该数字-1，然后判断只有当该数字为0的时候才真正释放该内存。

   • 由此，在新文件ref_cnt.c中完成引用次数保存、引用次数增加减少功能。

     // ref_cnt.c
     #include "types.h"
     #include "memlayout.h"
     #include "riscv.h"
     #include "defs.h"
     #include "spinlock.h"
     
     static int ref_cnts[PHYSTOP / 4096];  // 根据提示设置数组大小
     // 由于涉及并发的共享内存问题，因此需要🔒
     // 可以使用一个锁。
     // 但实际上每个引用计数之间并没有冲突，因此也可以分开使用锁
     static struct spinlock locks[PHYSTOP / 4096];
     
     void increaseReference(uint64 pa) {
         uint64 idx = (pa) / 4096;
         acquire(locks + idx);
         ++ref_cnts[idx];
         release(locks + idx);
     }
     
     int decreaseReference(uint64 pa) {
         int ret;
         uint64 idx = (pa) / 4096;
         acquire(locks + idx);
         ret = --ref_cnts[idx];
         release(locks + idx);
         if (ret 

     别忘了在defs.h中声明函数

   • 引用计数初始化：kalloc()需要将引用计数置1。由于没使用的内存引用计数为0，因此这里直接采用增加的方式初始化。
   • 引用计数增加：在刚fork()后父子进程共享内存时，内存实际上被引用2次。具体应当在fork()复制父页表到子页表（直接与父进程物理地址建立映射）时增加引用计数。即在cow_uvmcopy()中，映射建立成功后调用increaseReference()。(前边已有标记)

   • 引用计数减少：根据提示，在kfree()中先减少引用次数、再判断是否需要真的释放——即在kfree()开头加入系列命令：

     void kfree(void *pa) {
         // 将引用计数-1并判断当前引用计数是否为0
         // 若大于0则直接返回函数
         if (decreaseReference((uint64)pa) > 0) return;
         ...
     }

   • 其他：实际上xv6在初始化时会先kfree()一波，这时候所有引用计数都还是0，kfree的时候会发生引用计数为-1的错误情况，因此可将所有引用计数初始化为1或初始调用kfree()前先将引用计数+1：在kalloc.c的kinit()中初始化内存，调用freerange()来kfree内存，因此在freerange()中的kfree()之前加increaseReference():

     void freerange(void *pa_start, void *pa_end) {
         char *p;
         p = (char*)PGROUNDUP((uint64)pa_start);
         for(; p + PGSIZE 

4. 在copyout()中添加同样的处理：

   int copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len) {
       uint64 n, va0, pa0;
   
       while(len > 0){
           va0 = PGROUNDDOWN(dstva);
           // pa0 = walkaddr(pagetable, va0);
           // 之前已经封装好函数，这里只需要把walkaddr换成cow_walkaddr
           pa0 = cow_walkaddr(pagetable, va0);
           if(pa0 == 0) return -1;
           n = PGSIZE - (dstva - va0);
           if(n > len) n = len;
           memmove((void *)(pa0 + (dstva - va0)), src, n);
   
           len -= n;
           src += n;
           dstva = va0 + PGSIZE;
       }
       return 0;
   }

遇到的问题

1. panic: reference count = -1（引用计数为-1）
   
   最开始跑的时候连第一个都过不去，就报这个引用计数-1（自己设置的）的panic。想了半天反应过来：由于我按照提示顺序，先写了cow_uvmcopy()完成页表复制，再写引用计数，以至于再复制页表的时候忘加引用计数递增了。因此在cow_uvmcopy()中加上引用计数递增就解决了。

2. textwrite failed
   
   这个错误不是很明显。在过了所有cowtest的同时，还过了大部分usertests。只有到这个textwrite的时候才出现错误，对应了调试理论中bug-error-failure过程中也许会差很多个状态转移。又试了又想了半天，才搞明白bug，其实在提示2中也有提示：将原本可写的PTE设为不可写，然后触发错误；但是对于原本就不可写的，就要一致保持父子进程共享，不能cow。
   我最初写cow_uvmcopy()的时候没有考虑这一点，直接用*pte = (*pte & (~PTE_W)) | PTE_C;一刀切地把PTE的PTE_W去掉（因为觉得没有PTE_W的PTE这一步也没影响）然后加上PTE_C位（但是这一步就产生很大影响）。加入cow机制后，在试图写入不可写内存时有两种情况：（1）触发cow机制，需要开辟新内存拷贝…（2）这个内存原本就不可写，这时候是真的page fault。而我一刀切的方法，将原本不可写的内存也加上了PTE_C位，就无法判断出第（2）种情况了，结果全是第（1）种。因此，通过加入判断原本的PTE是否可写再去改变置位就能避免这种情况：

   if (*pte & PTE_W) {
       // 把父进程PTE的PTE_W位置0，再加上PTE_C位
       *pte = (*pte & (~PTE_W)) | PTE_C;
   }

结果

• 运行结果
  
• 测试结果
  

总结

• 通过该实验对COW机制的基本原理有了认识和理解，也感叹计算机前辈们能够思考出并实现该机制的厉害！
• C++智能指针引用计数用法也可直接在内存上使用！
• 对创建进程有了更深入的理解！

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net