Lab: Copy-on-Write Fork for xv6

Implement copy-on write

这个Lab的任务只有一个——将写入时复制这一功能实现。Lab对此给出了十分值得参考的步骤，翻译如下：

[ ] 修改 uvmcopy() ，使父进程不再为子进程分配新的页面，而是将父进程的页面映射至子进程的页表中。当父进程的页面的 PTE_W 权限为真时，将两个进程对该页面的写权限都取消。
[ ] 修改 usertrap() ，当写入时复制页面抛出缺页异常时，使函数通过 kalloc() 分配一个新的页面，并将旧的页面中的内容复制到这个新页面，将新的页面装载至进程的页表中并赋予进程对该页面写入的权限。
[ ] 保证当且仅当没有进程使用某个物理页面时才将该页面释放。要做到这一点，可以为每个物理页面添加一个引用计数器。当 kalloc() 将其分配时，使计数器的值初始化为 1；当一个进程将这个页面与其子进程共享时，增加计数器的值；当一个进程不再使用这个页面时，减少计数器的值。只有当一个页面的计数器的值为 0 时， kfree() 才可以将这个页面释放并放回至自由表中。可以考虑在一个定长数组中维护这些计数。要这样做，需要确定该数组的大小并需要决定物理页面应如何映射到数组的下标中。例如，可以将一个页面的下标定义为其物理地址除以 4096 的结果并将数组的长度设置为自由表中可以分配的页面的最大物理地址的值除以 4096 的结果（不一定要这样做）。
[ ] 修改 copyout() ，使其以应对缺页异常的方式处理写入时复制页面。

有了上面的步骤之后，我们基本上可以按照这个顺序来解决这个Lab。

修改uvmcopy

首先是修改 uvmcopy() ，我们将程序为子进程分配页面这一步及之后的指令注释掉，添加我们的代码。

在这里，我们的任务是将不需要立刻复制的页面从父进程处以只读的方式映射至子进程的页表中，复制后父进程同样不允许写入该页面。

那么，对于父进程的一个页面，一般有三种情况：

首先是父进程对这个页面有写入权限，此时我们需要将父进程对这个页面的写入权限取消，而后将这个页面以只读的方式映射至子进程的页表中。对于这样被多个进程所共享的页面，我们最好将其打上标记，这样进程之后要写入这个页面，内核在分配权限时可以将其从进程原本就不具有写入权限的页面中区分出来。我们在页表一章中已经得知PTE的第8位-第9位是保留位，因此我们可以利用保留位来标记该PTE指向的物理页面是否与其他进程共享的公用页面。
而后是父进程的这个页面同样来自于祖先进程（PTE_C为真），父进程对这个页面同样没有写入权限。对这样的页面，我们不需要变更父进程的权限，直接以同样的权限将这个页面映射至子进程的页表中即可。
最后是父进程既不与其他进程共享该物理页面，本身也不对该页面具有写入权限。对于这样的页面，由于其永远不会被更改，我们同样可以直接像第二种情况那样处理这个页面。

综上，我们对 uvmcopy() 作如下更改：

int 
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
  pte_t *pte;
  uint64 pa, i;
  uint flags, new_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);
    flags = PTE_FLAGS(*pte);

    // if PTE initially doesn't have permission to write
    // then don't mark it as COW page
    if (flags & PTE_W) {
      new_flags = (flags & ~PTE_W) | PTE_C;
      *pte = (*pte & ~PTE_W) | PTE_C;
    }
    else {
      new_flags = flags;
    }

    if (mappages(new, i, PGSIZE, pa, new_flags) < 0) {
      goto err;
    }

    acquire(&ref.lock);
    ++ref_count[PAGE_INDEX(pa)];
    release(&ref.lock);
  }
  return 0;

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

修改 `usertrap`

完成对 uvmcopy() 的修改后，我们需要让操作系统在遇到写入时复制页面时可以正确地处理。

进程在尝试对写入时复制页面进行写入时，由于没有对该页面写入的权限，会使CPU向操作系统抛出一个缺页错误。抛出错误时，系统处于用户态，因此，我们需要在 usertrap() 中对相应的错误进行识别，最后进行处理。

由RISC-V手册我们已经知道CPU在尝试写入时遇到错误的话，我们调用 r_scause() 将得到 15 的错误码。因此，我们在 usertrap() 中捕捉到错误码为 15 的异常后便直接调用错误处理函数并根据函数的返回值，决定进程是否遇到了合法的缺页异常，如果不是，则将进程杀死。对应的代码片段如下：

// kernel/user.trap.c
void
usertrap(void)
{
  // ...
  if(r_scause() == 8){
    // ...
  } else if((which_dev = devintr()) != 0){
    // ok
  } else if(r_scause() == 15) {
    uint64 va = r_stval();
    if (va >= p->sz)
      p->killed = 1;
    if (copy_on_write_page_fault_handler(p->pagetable, va) < 0) {
      p->killed = 1;
    }
  } else {
    // ...
  }
	// ...
}

在这里，我们提前加上了对进程访问的地址是否超出进程已分配的内存的判断，usertests中会针对这一项进行测试。

Lab: Copy-on-Write Fork for xv6

Implement copy-on write

修改uvmcopy

修改 usertrap

修改 `usertrap`