MIT6.S081 Lab-6: Copy on Write

本次实验只有一个难度为$\text{hard}$的任务，实现fork的写时复制。这一次以及上一次实验我们都是在利用页表机制和trap的结合，也就是$\text{Page Fault}$，来完成赶ddl物理内存的按需分配。

虽然任务只有一个，但是做得极为艰难。。。最后也是看了教授讲解发现自己有个地方出bug了才改对。按照我自己的做法是没怎么考虑多个CPU的，所以有的测试会时而通过时而不通过，这已经是目前的极限了。。。更完善的话还是得继续往后学。

之前在做$\text{Page Table}$的时候就觉得fork首先复制父进程页表，然后在exec里面会清空旧页改换成新页表。但是有可能父进程占用内存非常大，我们把父进程内存先复制给子进程，在子进程里可能没怎么使用就全清了，实在非常浪费时间和空间，肯定可以优化。这次$\text{Lab}$就来解决这个问题。写时复制就很有点像可持久化数据结构，我们只会给被修改的部分复制一份副本，然后对新的副本进行修改，没有改变的部分就共用，其实前面的$\text{Page Table}$中我们也是用类似的方法实现了每个进程的内核页表。

按照指南，首先从修改uvmcopy开始，这个比较容易，我们只要知道，$\text{Copy-on-Write}$机制会将$\text{PTE}$的写入位设为$0$，以在下一次对该页进行写入时触发$\text{Page Fault}$

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");
    pa = PTE2PA(*pte);
    *pte &= (~PTE_W);
    *pte |= PTE_COW;
    flags = PTE_FLAGS(*pte);
    ref[PXIDX(pa)]++;
    if(mappages(new, i, PGSIZE, pa, flags) != 0)
      goto err;
  }
  return 0;

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

我们做的事情就是清除掉被复制页的$\text{PTE}$项的写入位，并且设置其为需要使用$\text{Copy-on-Write}$。指南里提到可以通过设置一个扩展的标志位用来表示该页面是否需要进行$\text{Copy-on-Write}$。这些相当于是$\text{Copy-on-Write}$的准备工作。然后增加被复制页的引用计数。

接下来修改usertrap，对应的错误代码是$15$

if((r_scause() != 15)|| !copy_on_write(p->pagetable, r_stval()))
    p->killed = 1;
if(p->killed)
{
    printf("usertrap(): unexpected scause %p pid=%d, name is %s\n", r_scause(), p->pid, p->name);
    printf("            sepc=%p stval=%p\n", r_sepc(), r_stval());
}

然后是实现copy_on_write函数，虽然思路很好懂，但是实现起来颇有点细节

int copy_on_write(pagetable_t pagetable, uint64 va)
{
  uint64 a = PGROUNDDOWN(va);
  pte_t *pte = walk(pagetable, a, 0);
  uint64 old_pa = PTE2PA(*pte);
  if(ref[PXIDX(old_pa)] == 1) // this is the last reference to old_pa, so there is no need to make a copy of it
  {
    *pte &= (~PTE_COW);
    *pte |= PTE_W;
    return 1;
  }
  uint64 flags = PTE_FLAGS(*pte);
  if(!(flags & PTE_COW))
  {
    printf("copy_on_write: not a copy-on-write page\n");
    return 0;
  }
  uint64 pa = (uint64)kalloc();
  if(pa == 0)
  {
    printf("copy_on_write: no free page\n");
    return 0;
  } 
  uint64 perm = (flags | PTE_W) & (~PTE_COW);
  memmove((void *)pa, (void *)old_pa, PGSIZE);
  uvmunmap(pagetable, a, 1, 1);// unmap old mappings and map it to a new one
  if(mappages(pagetable, a, PGSIZE, pa, perm) != 0)
  {
    kfree((void*)pa);
    printf("copy_on_write: mappages failed\n");
    return 0;
  }
  ref[PXIDX(pa)]++;
  return 1;
}

先不管这里的ref，一个很容易错的地方就是全程用*pte来算原来的地址和原来的标志位。。。但是我们使用uvmunmap以后会导致*pte的值发生改变，因此在后续计算中如果继续用*pte就会出错，所以需要提前计算好地址和标志位。

uvmunmap相应也要修改

void
uvmunmap(pagetable_t pagetable, uint64 va, uint64 npages, int do_free)
{
  uint64 a;
  pte_t *pte;

  if((va % PGSIZE) != 0)
    panic("uvmunmap: not aligned");

  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");
    uint64 pa = PTE2PA(*pte);
    // no matter we free the physical page or not, it is a must to decrement the reference count
    ref[PXIDX(pa)]--;
    if(do_free && !ref[PXIDX(pa)])
      kfree((void*)pa);
    *pte = 0;
  }
}

和原来的区别是，现在的uvmunmap即使设置了do_free=1也不一定释放物理页。我们使用ref数组对所有物理页进行引用计数，uvmunmap一定会做的事情是将ref数组减一（因为映射已经被清空了），只有在ref为$0$的情况下才会去释放物理页。这样是为了保证当有多个进程的页表指向同一物理页（因为$\text{Copy-on-Write}$机制这是常有的事情）时，释放其中某个进程不会释放被共用的物理页。如果我们不这么小心地控制物理页的释放，结果很可能是某个进程被释放以后顺便释放了它指向的所有物理页，和它共用物理页的其他进程就全都出错了。

那么回到copy_on_write，一个坑点就是uvmunmap的do_free究竟应该设置为什么。看起来我们即使设置为$1$也不会发生物理页的释放，因为当$\text{Copy-on-Write}$发生时，一定是多个进程共用这个物理页，ref肯定不会为$0$。单$\text{CPU}$情况下这么想确实没问题，但是很难想到的一个事情是多$\text{CPU}$情况下这就不一定对了，如果同时在发生多个进程对这个页面的$\text{Copy-on-Write}$，那就可能有物理页要被释放了。这也是看了教授的讲解以后才想到的事情。

下一个问题是copyout的处理，在内核态我们可能需要向用户页写入些东西，这也要考虑copy_on_write。对此我的一贯做法是修改walkaddr

uint64
walkaddr(pagetable_t pagetable, uint64 va, int w)
{
  pte_t *pte;
  uint64 pa;

  if(va >= MAXVA)
    return 0;

  pte = walk(pagetable, va, 0);
  if(pte == 0)
    return 0;
  if((*pte & PTE_V) == 0)
    return 0;
  if((*pte & PTE_U) == 0)
    return 0;
  if(w && (*pte & PTE_COW))
  {
    if(!copy_on_write(pagetable, va)) return 0;
    else pte = walk(pagetable, va, 0);
  }
  pa = PTE2PA(*pte);
  return pa;
}

注意我修改了函数的原型，多加了一个参数用来表示是否写入，以更方便地配合copy_on_write。

最后的问题是ref的维护，其实做法有很多，教授的做法是把ref的修改都放在kalloc和kfree里，这样做确实是OK的，而且对于多个$\text{CPU}$也同样适用。但是实际上我们只需要对用户页维护ref，也就是说很多kalloc分配的页其实不需要我们维护ref，所以我没有把ref的修改放在这两个函数里，而是根据需要自己操作，如果修改的页面是用户页，那么就修改ref，否则不动。但是这样单$\text{CPU}$没问题，多$\text{CPU}$就有可能出问题（当然也有可能不出问题）。这样做确实省了一点点不必要的计算，但是拓展起来很麻烦，而且要非常小心地选择修改ref的时机（尤其是在有错误处理的时候）。具体改动可以见我的$\text{github}$。

据说当年$\text{Linus}$在写$\text{Linux}$的时候最难的部分也是$\text{Copy-on-Write}$，只能说这个思路并不难，但是细节很多，对得起教授专门为它开一节习题课（