MIT 6.S081 Lab 5: Copy-on-Write Fork for xv6

3 Sep 2022

Rudeness is the weak man’s imitation of strength.

6.S081课程的第五个Lab，为 xv6 添加 Copy-on-Write 的 fork 机制。

The problem

虚拟内存提供了一个间接级别：内核可以通过标记 pte 无效或只读来拦截内存引用，从而导致页错误，并可以通过修改 pte 来改变地址的含义（虚拟地址指向的真实物理内容）。在计算机系统中有这样一种说法：任何系统问题都可以用间接层次来解决。

xv6中的fork()系统调用将父进程的所有用户空间内存复制到子进程中。如果父进程用户空间很大，复制可能需要很长时间。更糟糕的是，这些工作大部分都被浪费了；例如，在子进程中使用fork()后跟exec()将导致子进程丢弃复制的内存，可能根本没有读写其中的大部分内存。另一方面，如果父和子都使用一个页，并且其中一个或双方都写它，那么确实需要一个物理页副本。

The solution

copy-on-write (COW) fork()的目标是延迟为子进程分配和复制物理内存页，直到实际需要拷贝(如果需要的话)。

COW fork()只为子进程创建一个页表，其中的pte指向父进程的物理页面。COW fork()将父和子中的所有用户pte标记为不可写。当任何一个进程试图写入其中一个COW页时，CPU将强制产生一个页错误。内核页故障处理程序检测这种情况，为故障进程分配一页物理内存，将原始页内容复制到新页中，并修改故障进程中的相关PTE以引用新页，这次PTE标记为可写。当页错误处理程序返回时，用户进程将能够写这个页的副本。

COW fork()使释放实现用户内存的物理页面变得有点棘手。一个给定的物理页可能被多个进程的页表引用，只有当最后一个引用消失时才应该被释放。

Implement copy-on write

修改的核心在于标记 PTE 是否为 COW 页与之前是否可写，并且为物理页的引用次数做记录。这里仅展示部分代码。

reference count

我们需要确保在对每个物理页的最后一个 PTE 引用结束时释放它。实现这一点的一个好方法是为每个物理页面保留一个“引用计数”，代表该物理页的被不同用户页表引用的次数。当 kalloc() 分配一个页面时，将它的引用计数设置为 1。当 fork 导致子进程共享该页时，增加该页的引用计数；当任何进程将该页从其页表中删除时，减少该页的引用计数。只有当某个物理页引用计数为零时，kfree() 才会真正地将页面放回 free list 空闲列表。我们可以将这些计数保存在固定大小的整数数组中。关键在于如何索引数组以及如何选择它的大小。例如，可以用页面的物理地址除以 4096 （页大小）对数组进行索引，引用计数数组大小等于空闲列表中任何页面的最高物理地址对应的索引数目。

struct {
  struct spinlock lock;
  struct run *freelist;
  int ref_count[PHYSTOP / PGSIZE];
} kmem;

结构体 kmem 的 ref_count 字段即为引用计数数组，可以看到大小为最高物理地址 PHYSTOP 整除页大小 PGSIZE。其余 kalloc 、kfree 与一些新增辅助函数（读写相关物理地址的引用计数）这里就不赘述了。

COW fork

增加 COW 机制只用修改 fork 时的 uvmcopy 函数，完成 PTE 与引用计数的修改。

// Given a parent process's page table, copy
// its memory into a child's page table.
// Copies both the page table and the
// physical memory.
// returns 0 on success, -1 on failure.
// frees any allocated pages on failure.
int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
  pte_t *pte;
  uint64 pa, i;
  uint flags;

  for(i = 0; i < sz; i += PGSIZE){
    if((pte = walk(old, i, 0)) == 0)
      panic("uvmcopy: pte should exist");
    if((*pte & PTE_V) == 0)
      panic("uvmcopy: page not present");
    // clear PTE_W and record PTE_COW
    if((*pte) & PTE_W)
      *pte = (((*pte) ^ PTE_W) | PTE_PRW | PTE_COW);
    else
      *pte = ((*pte) | PTE_COW);
    pa = PTE2PA(*pte);
    flags = PTE_FLAGS(*pte);

    increRefCount(pa);
    
    if(mappages(new, i, PGSIZE, pa, flags) != 0) {
      goto err;
    }
  }
  return 0;

 err:
  uvmunmap(new, 0, i / PGSIZE, 1);
  return -1;
}

我这里用到了 PTE Flag 的 8、9 位（保留位），PTE_COW 标记当前页为 COW 页，PTE_PRW 标记这个页原本是否 Writable (不是所有页都可写，即使用了 COW 机制，若该页原来不可写，任何写尝试也应当被阻止)。

handle COW page

若一个页 PTE 标记为 COW 页，任何写尝试的处理逻辑是统一的，这里封装为函数 handleCOWpage 。大致代码逻辑为，根据 PTE_PRW 的不同，还原当初的 Flag ；根据 COW 页引用计数不同选择不同处理，

计数大于 1 ，通过 kalloc 分配一个新物理页，复制原物理页内容，修改页表中的映射（调用 uvmunmap 去掉原映射，调用 mappages 增加新映射）。
计数等于 1 ，仅还原 PTE Flag ，因为这是最后一个引用的物理页，没必要分配新的页副本。
计数等于 0 ，报告错误。

// if pte is a pre_va mapping entry of COW page 
// in page table pt, handle it before writing.
// return physical addr of the writable page
// or 0 if failed.
uint64
handleCOWpage(pagetable_t pt, pte_t *pte, uint64 pre_va) {
  uint64 flags = PTE_FLAGS(*pte);
  uint64 pa = PTE2PA(*pte);
  int refcnt = getRefCount(pa);

  if (flags & (PTE_PRW))
    flags = ((flags & (~PTE_COW) & (~PTE_PRW)) | PTE_W);
  else
    flags = (flags & (~PTE_COW));

  if (refcnt > 1) {
    /* allocate new Page, copy and map*/
    void* newPage;
    if((newPage = kalloc()) == 0)
      exit(-1);

    memmove(newPage, (char*)pa, PGSIZE);
    // unmap and 'free' the old COW page
    // kfree only place a page back on the free 
    // list if its reference count is zero. 
    uvmunmap(pt, PGROUNDDOWN(pre_va), 1, 1);
    if(mappages(pt, PGROUNDDOWN(pre_va), PGSIZE, (uint64)newPage, flags) != 0) {
      kfree(newPage);
      exit(-1);
    }

    return walkaddr(pt, PGROUNDDOWN(pre_va));   
  } else if (refcnt == 1) {
    // the last page, just restore flags
    *pte = ((((*pte) >> 10) << 10) | flags);
    return pa;
  } else {
    printf("Reference count is zero: virtual addr=%p physical addr=%p\n", pre_va, pa);
    return 0;
  }
}

encounter a COW page

用户态遭遇 COW 页，一般是尝试写 COW 页，由于页 PTE_W 为 0 , 引发页错误，陷入内核。RISC-V 的 scause 记录的异常码为 15 ，我们在 usertrap 函数中增加新的异常处理逻辑：从 stval 读取页错误的虚拟地址，并完成地址检查与 PTE_COW 检查后，调用 handleCOWpage 函数处理错误页。

// in kernel/trap.c usertrap function
else if(which_cause == 15) {
    // Store/AMO page fault

    if(p->killed)
      exit(-1);

    //get faulting virtual address
    uint64 fault_va = r_stval();
    if (fault_va >= MAXVA)
      exit(-1);
    pte_t *pte = walk(p->pagetable, fault_va, 0);
  
    if (0 == ((*pte) & PTE_COW)) {
      printf("Non-COW page cause fault 15: virtual addr=%p physical addr=%p\n", fault_va, PTE2PA(*pte));
      exit(-1);
    }

    if (0 == handleCOWpage(p->pagetable, pte, fault_va)) 
      p->killed = 1;
  }

内核态遭遇 COW 页，为函数 copyout 在内核态将数据复制到用户态的某页，可能用户态页是 COW 页。这相当于在内核态写 COW 页。如果不修改 kerneltrap，我们可以仅简单检查 COW 页并调用 handleCOWpage 处理，这里也不赘述了。

debug

在跑测试与调试过程中，使用 gdb 也有一点小问题，这里简单记录。

由于课程贴心的使用了 .gdbinit 文件以期与 Makefile 中的 qemu-gdb 目标配置相同，每次调试 qemu-gdb 只用直接启动 gdb 自动导入配置即可。但我遇到，

warning: File “/home/ezio/xv6-labs-2021/.gdbinit” auto-loading has been declined by your `auto-load safe-path’ set to “$debugdir:$datadir/auto-load”.

这个问题在zhihu文章: 在QEMU的XV6上使用GDB也有记录。简单说，就是 gdb loading safe path 机制为了确保安全，并不总是自动加载任何文件，而是提供了一组自动加载安全路径设置来列出可信任的目录。

我简单配置了文件 ~/.gdbinit 即可解决这个问题。

add-auto-load-safe-path /home/ezio/xv6-labs-2021/.gdbinit

后来又遭遇同developerload: ‘Running gdb on xv6-riscv-fall19 相同的 issue

.gdbinit:2: Error in sourced command file: Undefined item: “riscv:rv64”.

排查 GDB 版本也没有错误，重装 tool chain 也没有任何新增，猜测是 WSL Ubuntu 下的问题。所幸使用 gdb-multiarch 可以解决。以后 6.S081 的调试都使用 gdb-multiarch 代替。

Conclusion

完成 COW 机制，我们需要善用 PTE 的 Flag 位记录与引用计数维护物理页信息。然后只用考虑 fork 如何增加 COW 页，以及用户态与内核态下尝试写 COW 页的不同：

用户态写 COW 页。通过页错误在 usertrap 中处理异常。
内核态写 COW 页。仅在 copyout 中遭遇并处理。

相同的 COW 页处理逻辑就可以封装：根据 PTE_PRW 的不同，各自还原当初的 Flag ；根据 COW 页引用计数不同选择不同处理，

计数大于 1 ，通过 kalloc 分配一个新物理页，复制原物理页内容，修改页表中的映射（调用 uvmunmap 去掉原映射，调用 mappages 增加新映射）。
计数等于 1 ，仅还原 PTE Flag ，因为这是最后一个引用的物理页，没必要分配新的页副本。
计数等于 0 ，报告错误。

当然现实的 COW 机制可能与 xv6 不同，但总体的流程和思想可以从这个lab 中学习不少。

Reference

system-programming