xv6 labs Copy-On-Write fork

虚拟内存提供了一个中间层：内核可以通过将PTE标记为invalid或者read-only来拦截内存引用，这会导致page fault，此时，你可以通过修改PTE来改变地址的含义。在计算机系统中有一种说法，任何系统问题都可以通过中间层解决。lazy allocation实验提供了一个例子，本次实验将探索另一个例子：copy-on-write fork。

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

$ git fetch
$ git checkout cow
$ make clean

问题

xv6中的fork()系统调用复制父进程的所有用户空间内存到子进程中，如果父进程很大，复制可能会占用很长一段时间。更坏的情况是，大部分情况下，我们所做的努力都会浪费掉。举个例子：一个fork()，在子进程的后面跟了一个exec()，这种调用将导致子进程丢弃复制的内存，可能其中的大部分都从没使用过。另一方面，如果父进程和子进程使用一个页，那么如果其中一个或者它们都写入该页，此时确实需要复制。

解决办法

copy-on-write（COW）fork的目标是将子进程的物理内存页的分配和复制推迟到实际需要时。

COW fork()只为子进程创建一个页表，该页表中包含指向父进程物理页的用户内存的PTE。COW fork()将父进程和子进程中的所有PTE标记为不可写，当任一进程尝试写入这些COW页面，CPU将产生一个page fault，内核page fault处理器会检测到这个情况，为出错进程分配一个物理页，复制原始页到新页面，修改出错进程的对应PTE指向新页面，这次，PTE将被标记为可写。当page fault处理器返回，用户进程将可以写入它的拷贝页。

COW fork()使得用户内存的物理页释放稍微复杂，一个给定的物理页可能被多个进程的页表引用，只有当最后一个引用消失时，才能被释放。

实现copy-on-write(hard)

你的任务是在xv6内核中实现copy-on-write fork。如果你修改的内核可以成功执行cowtest以及usertests程序，你的任务就完成了。

为了帮助你测试你的实现，我们提供了一个xv6程序，它叫cowtest（user/cowtest.c）。cowtest运行多个测试，但即使是第一个测试，在未经修改的xv6上也无法通过。所以，最开始，你会看到：

$ cowtest
simple: fork() failed
$ 

测试"simple"分配超过一半的可用物理内存，然后调用fork()。因为已经没有足够的空闲物理内存给子进程来完成父进程内存的拷贝了，所以fork将会失败。

当你完成任务，你的内核将会通过cowtest和usertests中的所有测试：

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

一些合理的计划：

1. 修改uvmcopy()以将父物理页映射到子，而不是分配新页。在父和子的PTE中都要清除PTE_W
2. 修改usertrap()以识别page fault，当一个page-fault在COW页上发生时，使用kalloc()分配一个新页，复制旧页到新页，将新页安装到PTE上，并设置PTE_W标记
3. 对于每一个物理页，当它的最后一个引用消失时，确定它被释放——但不能提前释放。一个好方法是为每一个物理页保存一个“引用计数”，代表有多少个用户页表引用了这个页。当调用kalloc()分配页面时，将它的引用计数设置为1，当fork导致一个子进程共享该页时，增加该页的引用计数，当每次一个进程从它的页表中销毁该页时，递减该页的引用计数。kfree()将只在一个页的引用计数为0时将它放回free list中。可以在一个固定大小的整型数组中保存这些计数，你需要制定如何索引数组以及如何选择数组大小的方案，举个例子，你可能通过页的物理地址除以4096来索引数组，并将所有被kinit()放置在freelist中的页里面物理地址最高的那一个作为数组的元素数
4. 修改copyout()以在遇到COW页时使用与页错误相同的方案

一些提示：

• lazy page allocation实验已经让你熟悉了与copy-on-write相关的大部分xv6内核代码，然而，你不应该在你的lazy allocation之上进行本次实验，请从按照上面的指示从一个新的xv6副本开始
• 有一个方法来记录每个PTE是否是一个COW映射可能很有用，你可以使用RISC-V PTE中的RSW（reserved for software）位来实现
• usertest中有一些cowtest没有测试到的情况，别忘了通过所有测试
• 一些有用的页表位相关的宏以及定义在kernel/riscv.h的末尾处
• 如果一个COW page fault发生了，并且没有空闲内存，进程应该被杀死

解决过程

先执行一下cowtest，肯定不通过

修改uvmcopy使父子共用物理内存页

然后观察一下fork()创建子进程时都做了啥，这里只关注和用户虚拟内存有关的代码：

int
fork(void)
{
  int i, pid;
  struct proc *np;
  struct proc *p = myproc();
  // ...省略...

  // 从父进程复制用户内存到子进程
  if(uvmcopy(p->pagetable, np->pagetable, p->sz) < 0){
    // 失败情况
    freeproc(np);
    release(&np->lock);
    return -1;
  }
  // 子进程的内存大小=父进程的内存大小
  np->sz = p->sz;

  // ...省略...

  return pid;
}

uvmcopy()只有在proc.c中fork子进程时被用到，所以我们按照实验中的提示在这里进行修改不会对系统中的其它部分产生什么其它影响。

uvmcopy原始代码很好理解，就是将old页表中的所有页复制到new页表，物理内存页也被复制了：

// 给定一个父进程的页表，将它的内存复制到一个子进程页表中
// 复制页表以及物理内存，返回0成功，-1失败
// 失败是释放任何已分配的页
int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
  pte_t *pte;
  uint64 pa, i;
  uint flags;
  char *mem;

  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");
    pa = PTE2PA(*pte);
    flags = PTE_FLAGS(*pte);
    if((mem = kalloc()) == 0)
      goto err;
    memmove(mem, (char*)pa, PGSIZE);
    if(mappages(new, i, PGSIZE, (uint64)mem, flags) != 0){
      kfree(mem);
      goto err;
    }
  }
  return 0;

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

现在，我们把它改成只建立页表，共用一份物理内存，并将old和new中的PTE都设置为不可写：

int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{

  for(i = 0; i < sz; i += PGSIZE){
    // ...

    // 新flag=旧flag并去掉PTE_W位
    flags = PTE_FLAGS(*pte);
    flags &= ~PTE_W;

    // old和new共用一个物理页，并重新映射双方的flag为不可写
    if(mappages(new, i, PGSIZE, pa, flags) != 0){
      goto err;
    }
    *pte = PA2PTE(pa) | flags;

  }
  return 0;
  // ...
}

运行cowtest，现在usertrap里出了一些问题，这应该是因为我们无法识别scause，我们需要编写对应的陷阱处理程序

通过查阅scause的表格，在pid3进程中，我们得到了一个Store/AMO page fault，在pid2中得到了一个保留的陷阱原因，在pid1中得到了一个Instruction page fault。

修改usertrap处理COW页写入

在usertrap中，我们只需要添加一个尝试向页面写入失败的陷阱处理程序，它对应的异常代码是15：

if(r_scause() == 8){
    // system call...
} else if((which_dev = devintr()) != 0){
    // interrupt...
} else if(r_scause() == 15) {
    // [+] 尝试对页面进行写入，失败!
} else {
    // unexpected...
}

但是，嘶，我们无法确定这是一次正常的，预期之中的写入失败，还是由于COW产生的写入失败，所以，我们还得回退到之前的代码，为COW相关的页面加一个标记。

在PTE中，前10位是标记位，前8位被占用，后两位我们可以随意使用，我们使用其中的一位标记页是COW页

kernel/riscv.h

#define PTE_V (1L << 0) // valid
#define PTE_R (1L << 1)
#define PTE_W (1L << 2)
#define PTE_X (1L << 3)
#define PTE_U (1L << 4) // 1 -> user can access
+#define PTE_COW (1L << 8) // 1 -> page is a COW page

kernel/vm.c

// 新flag=旧flag并去掉PTE_W位
flags = PTE_FLAGS(*pte);
flags &= ~PTE_W;
+flags |= PTE_COW;

在usertrap中，如果有人尝试写COW页，那么我们得将这个物理内存页的内容复制到一个新物理页上，并更新该进程的PTE，让它指向新页。

  else if(r_scause() == 15) {

    uint64 va = PGROUNDDOWN(r_stval());
    pte_t *pte = walk(p->pagetable, va, 0);
    uint64 pa = PTE2PA(*pte);
    uint flags = PTE_FLAGS(*pte);

    char *mem;

    if (flags & PTE_COW) {
      flags |= PTE_W; // 我们需要某种手段来记录pte之前是不是可写的
      flags &= ~PTE_COW; // 清除PTE_COW

      if ((mem = kalloc()) == 0) {
        p->killed = 1;
      } else {
        memmove(mem, (char*)pa, PGSIZE);
        *pte = PA2PTE((uint64)mem) | flags;
      }
    } else {
      printf("usertrap(): unexpected scause %p pid=%d\n", r_scause(), p->pid);
      printf("            sepc=%p stval=%p\n", r_sepc(), r_stval());
      p->killed = 1;
    }
  }

嘶，好像又出了一个问题啊，在上面的代码里，我们将分配新的物理页，拷贝原来的数据，并重新映射到PTE上，但是...我们现在要清除PTE_COW标记，重新设置PTE_W标记，可是万一PTE_W之前就不可写呢？我们这段代码很危险，貌似我们可以通过fork一个子进程，修改原本不可写的trampoline代码...不过考虑到我只是做个实验，我先放着这种情况不管，实在不行我们再用PTE中的另一个保留位记录原来带PTE_W。

添加引用计数器

现在运行cowtest，有了一个新问题：

2是一个保留异常号，应该没什么实际含义，它是由0x1004这个位置的指令产生的，这是一个unimp指令，貌似是一个未实现的命令，c则是指令page fault，说明需要读取的指令是不可写的。

通过查看cowtest的代码，估计是子进程退出了，父进程在wait期间会扫描所有ZOMBIE子进程，并调用proc_freepagetable清理它的页表。父进程和子进程用的是一个页表，所以相当于父进程亲手终结了自己的页表......相关代码如下：

// cowtest中的父进程会让子进程`exit`，并让父进程`wait`一个已经退出的子进程
// 如下是wait函数，精简了很多内容，只保留核心逻辑，当伪代码看即可
int
wait(uint64 addr)
{

  for(;;){
    // 扫描所有进程，若找到一个自己的子进程，并且处于ZOMBIE状态
    for(np = proc; np < &proc[NPROC]; np++){
      if(np->parent == p){
        if(np->state == ZOMBIE){
          // 清理子进程
          freeproc(np);
          return pid;
        }
      }
    }
  }
}
// freeproc执行子进程清理工作，实际上会清理子进程的trapframe以及页表
// trapframe在内核栈中，我们不关心。下面的代码仍然当作精简后的伪代码处理
static void
freeproc(struct proc *p)
{
  // 清理进程页表
  if(p->pagetable)
    proc_freepagetable(p->pagetable, p->sz);
}

// 下面是proc_freepagetable的代码
void
proc_freepagetable(pagetable_t pagetable, uint64 sz)
{
  // 解映射TRAMPOLINE和TRAPFRAME
  uvmunmap(pagetable, TRAMPOLINE, 1, 0);
  uvmunmap(pagetable, TRAPFRAME, 1, 0);
  // 释放页表
  uvmfree(pagetable, sz);
}

在对TRAMPOLINE和TRAPFRAME的解映射中，最后一个参数do_free都是0，这代表不会进行实际的物理页清理工作，我们先不看它，来看uvmfree中做了什么。

void
uvmfree(pagetable_t pagetable, uint64 sz)
{
  if(sz > 0)
    uvmunmap(pagetable, 0, PGROUNDUP(sz)/PGSIZE, 1);
  freewalk(pagetable);
}

它会对整个页表中所有内存进行uvmunmap，并设置do_free为1，这相当于对所有用户内存的物理页进行一次释放，然后，它会调用freewalk来释放页表页占用的物理内存。到了这里，我们应该已经知道问题出在这个uvmunmap调用上了，它把子进程的物理页释放，相当于把自己的物理页也释放了。下面是uvmunmap的代码：

// 有所省略
void
uvmunmap(pagetable_t pagetable, uint64 va, uint64 npages, int do_free)
{
  uint64 a;
  pte_t *pte;

  for(a = va; a < va + npages*PGSIZE; a += PGSIZE){
    if((pte = walk(pagetable, a, 0)) == 0)
      panic("uvmunmap: walk");
    if((*pte & PTE_V) == 0)
      panic("uvmunmap: not mapped");
    if(PTE_FLAGS(*pte) == PTE_V)
      panic("uvmunmap: not a leaf");
    if(do_free){ // 调用kfree释放物理页
      uint64 pa = PTE2PA(*pte);
      kfree((void*)pa);
    }
    *pte = 0;
  }
}

uvmunmap中实际上是对于每一个物理页，调用kfree进行释放，根据实验的提示，我们需要为每个物理页维护一个引用计数，在kalloc中递增它，在kfree中递减它，一旦引用计数为0，该物理页才可以真正的被释放。

修改kalloc.c，新增一个结构体用于对物理页进行引用计数：

// 这个宏将物理地址转换成页引用计数器的物理页索引
#define PA2PID(pa) (((uint64)(pa) - KERNBASE) / PGSIZE)

// 页引用计数器
struct {
  struct spinlock lock;
  int rcs[PA2PID(PHYSTOP) + 1];
} pagerc;

由于需要在其它地方操作这个引用计数器，所以暴露两个接口：

// 递增引用计数器，返回递增后的值
int REF_I(uint64 pa) {
  acquire(&pagerc.lock);
  int r = ++pagerc.rcs[PA2PID(pa)];
  release(&pagerc.lock);
  return r;
}
// 递减引用计数器，返回递减后的值
int REF_D(uint64 pa) {
  acquire(&pagerc.lock);
  int r = --pagerc.rcs[PA2PID(pa)];
  release(&pagerc.lock);
  return r;
}

修改所有需要改变引用计数的位置

修改kfree，只有当一个物理页的引用计数为0时才真正释放物理页：

void
kfree(void *pa)
{
  struct run *r;

  if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
    panic("kfree");

  // 递减引用计数器
  int rc = REF_D((uint64)pa);
  
  // 如果已经没有其它引用了
  if (rc == 0) {
    // Fill with junk to catch dangling refs.
    memset(pa, 1, PGSIZE);

    r = (struct run*)pa;

    acquire(&kmem.lock);
    r->next = kmem.freelist;
    kmem.freelist = r;
    release(&kmem.lock);
  }
}

修改kalloc，将新分配页的引用计数设置为1：

void *
kalloc(void)
{
  struct run *r;

  acquire(&kmem.lock);
  r = kmem.freelist;
  if(r) {
    kmem.freelist = r->next;
    // 设置引用计数器
    pagerc.rcs[PA2PID(r)] = 1;
  }
  release(&kmem.lock);

  if(r) {
    memset((char*)r, 5, PGSIZE); // fill with junk
  }
  return (void*)r;
}

由于xv6启动时kinit会调用freerange将所有物理内存页放到freelist中，每一个物理内存页都会被调用一次kfree，这时我们不能让引用计数器的值变成-1。可以采取很多种办法，比如向kfree添加一个标记参数，标记是否改动引用计数器；比如在初始时给引用计数器都设置为1，这里采用后者：

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

  for(; p + PGSIZE <= (char*)pa_end; p += PGSIZE) {
    // 先把引用计数器设置成1，然后调用kfree减1，页面的引用计数就成了0
    pagerc.rcs[PA2PID(p)] = 1;
    kfree(p);
  }
}

执行uvmcopy时，物理页的引用计数需要递增：

int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
  for(i = 0; i < sz; i += PGSIZE){
    // ... 省略一些代码 ...
    REF_I(pa);
  }
  return 0;
}

当进行COW复制时，需要释放一次原始物理页，因为原始物理页的引用以及少了一个：

// ...
memmove(mem, (char*)pa, PGSIZE);
*pte = PA2PTE((uint64)mem) | flags;
kfree((void*) pa);
// ...

修改copyout

当执行某些系统调用需要从内核复制数据给用户时，copyout需要以软件形式遍历页表并写入对应物理页，这时是不会有page fault的，即使遇到和父进程共享的页（PTE_W已经被清除）。所以，copyout函数需要手动识别这种情况，并在适当的时候执行cow。

为了方便，在trap.c中将cow过程提取成一个函数：

// usertrap()部分代码：
} else if((which_dev = devintr()) != 0){
  // 中断处理
} else if(r_scause() == 15) {
  if (cow(r_stval(), p->pagetable) == -1) {
    p->killed = 1;
  }
}

// 提取出的cow函数：成功0，-1失败
int cow(uint64 va, pagetable_t pgtable) {
    pte_t *pte = walk(pgtable, va, 0);
    uint64 pa = PTE2PA(*pte);
    uint flags = PTE_FLAGS(*pte);

    char *mem;

    if (flags & PTE_W) return 0;

    if (!(flags & PTE_COW)) return -1;
    
    flags |= PTE_W; // 我们需要某种手段来记录pte之前是不是可写的
    flags &= ~PTE_COW; // 清除PTE_COW
    if ((mem = kalloc()) == 0) return -1;
    memmove(mem, (char*)pa, PGSIZE);
    *pte = PA2PTE((uint64)mem) | flags;
    kfree((void*) pa);
    return 0;
}

修改copyout，调用cow函数：

int
copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len)
{
  uint64 n, va0, pa0;

  while(len > 0){
    va0 = PGROUNDDOWN(dstva);
    // 如果cow失败 返回失败
    if (cow(dstva, pagetable) == -1) return -1;
    pa0 = 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;
}

初始化引用计数器锁

不能忘了初始化锁：

void
kinit()
{
  initlock(&kmem.lock, "kmem");
  initlock(&pagerc.lock, "pagerc");
  freerange(end, (void*)PHYSTOP);
}

defs.h中也别忘了添加新编写的函数。

通过cowtest

向cow函数中添加边界条件检查

在执行usertest时失败了：

失败原因是一个load page fault（0x0d，13），是在kerneltrap中读0x0时发生的？？？命令是0x80002796。一点头绪没有，看看kernel.asm里2796是什么命令吧。是我们编写的cow函数里的这一行：

应该是pte为空吧，学着网上的代码加了两个边界条件检查：

int cow(uint64 va, pagetable_t pgtable) {
    if (va >= MAXVA) return -1;
    pte_t *pte = walk(pgtable, va, 0);
    if(pte == 0 || (*pte & (PTE_V)) == 0 || (*pte & PTE_U) == 0) return -1;  
    // ...
}

通过usertests测试：

实验代码

YHaoNan/xv6-2020-labs - cow

参考

• MIT6.S081 lab6 Copy On Write Fork - 林夕丶

本栏目推荐文章
• upload-labs
• "nginx.conf" E514 : write error (file system full?)
• Prometheus监控remote_write参数（远程写入）调用
• fork 后的代码仓如何同步被fork仓的代码
• 11-K8 Service：轻松搞定服务发现和负载均衡 (copy)
• rCore_Lab3
• MIT6.828 Lab1-1(分析boot.S文件)
• docker cp -> 从container当初copy文件出来
• java深copy
• 可笑！在网页上复制点东西 还需要掏钱？教你copy事件的禁用

Copy-On-Write Write labs Copy forkcopy-on-write write fork copy copy-on-write write lab6 copy copy-on-write write labs copy copy-on-write copy-on-write write copy on copy-on-write project笔记15445 copy_process do_fork process copy iceberg write merge copy fork forked