[MIT6.S081]Lab5: Copy-on-Write Fork for xv6

Lab: Copy-on-Write Fork for xv6 (mit.edu) (opens new window)

1、Implement copy-on write

这个 lab 中我们要实现写时复制。

我们知道当一个进程 fork 出一个子进程后，子进程会复制父进程的所有内容，那么此时如果子进程执行了 exec，则会将刚刚复制完的内容又全部重置。我们知道拷贝是非常耗时的，如果每次像这样复制必然会产生许多的浪费。

于是便有了写时复制，在 fork 出一个子进程后，我们不进行拷贝，而是将父子进程的页表映射到同一块物理内存，并将 PTE_W 都置为 0，当父子进程需要写这个地址时，便会产生 page fault，在遇到这种情况后我们才进行实际的拷贝操作。

接下来我们开始写代码 💻

因为此时同一块物理可能被多个进程所共享，那么我们就不能随意释放内存，而是要引入一个新的变量，作为引用计数，类似于 C++ 里的智能指针，只要当一块内存的引用计数为 0 了，才会释放该内存。

在 kalloc.c 中添加引用计数变量

int ref_cnt[(PHYSTOP - KERNBASE) / PGSIZE];

我们对应的在新分配一块内存时也要将引用计数初始化为 1

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

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

  if(r) {
    ref_cnt[pageid(r)] = 1; // 初始化引用计数为 1 
    memset((char*)r, 5, PGSIZE); // fill with junk
  }
  return (void*)r;
}

在释放内存的时候，如果引用计数 > 1 时，就将其减 1，否则再释放

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

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

  if (ref_cnt[pageid(pa)] > 1) { // 引用计数减 1
    ref_cnt[pageid(pa)]--;
    return;
  }

  // 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);
}

之后我们要对 uvmcopy 函数进行修改，当 fork 出一个子进程后，我们要让父子进程共享同一块物理内存，并将 PTE_W 设置为 0。同时为了标记一个页面是写时复制页面，我们要给 PTE 打一个新的标记 PTE_COW，这里可以用到 RSW 位。

在 riscv.h 中添加

#define PTE_COW (1L << 8)

回到 uvmcopy，我们遍历父进程的页表，对每个 PTE 设置其标记位和获取对应的物理地址 pa，接着我们给新进程的页表的每一个同样位置的 PTE，与 pa 也进行映射，并且引用计数 + 1

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");
    *pte &= ~PTE_W; // 将 PTE_W 位 置为 0
    *pte |= PTE_COW; // 设置 PTE_COW 位
    pa = PTE2PA(*pte);
    flags = PTE_FLAGS(*pte);
    if(mappages(new, i, PGSIZE, (uint64)pa, flags) != 0){
      panic("uvmcopy: mappages");
      goto err;
    }
    ref_cnt[pageid(pa)]++;
  }

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

然后我们进入 trap.c 来对这种 page fault 进行处理。

根据文档，我们知道此时对应的异常码是 15

另外我们还要检查虚拟地址是否合法，指向的 PTE 是否是一个 cow 页面...，如果都符合我们就根据实验文档所说的 copy the old page to the new page, and install the new page in the PTE with PTE_W set.

void usertrap(void) {
//......
else if ((r_scause() == 15) && checkcow(r_stval())) { 
    if (cow_fault(r_stval()) != 0) {
      panic("usertrap: cow_fault");
      p->killed = 1;
    }
//......
}

下面是检查虚拟地址的代码 checkcow：「具体看注释」

int checkcow(uint64 va) {
  pte_t *pte;
  struct proc *p = myproc();
  if (va >= MAXVA) return 0; // 虚拟地址是否在合法范围内
  if ((pte = walk(p->pagetable, va, 0)) == 0) return 0; // 是否能找到对应的 PTE
  if (!(*pte & PTE_V) || !(*pte & PTE_COW)) return 0; // PTE_V 有效位是否被设置，PTE_COW 是否被设置
  return 1;
}

下面是实际拷贝的代码 cow_fault： 「具体看注释」

int cow_fault(uint64 va) {
  va = PGROUNDDOWN(va); // 要 page-aligned
  pte_t *pte;
  struct proc *p = myproc();
  if ((pte = walk(p->pagetable, va, 0)) == 0) { // 获取 PTE
    panic("cow_fault: walk");
  }
  uint64 old = PTE2PA(*pte); // 获取 PTE 对应的物理地址
  uint64 new;
  uint64 flags = (PTE_FLAGS(*pte) | PTE_W) & ~PTE_COW; // 取消 PTE_COW 位，设置 PTE_W 位
  if ((new = (uint64)kalloc()) == 0) { // 分配新的物理内存
    panic("cow_fault: kalloc panic");
  }
  memmove((void *)new, (void *)old, PGSIZE); // 实际拷贝操作
  uvmunmap(p->pagetable, va, 1, 1); // 取消 PTE 与原来的物理内存的映射
  if (mappages(p->pagetable, va, PGSIZE, new, flags) != 0) { // 与 new 建立新的映射，并设置了新的标志位
    panic("cow_fault: mappages");
    kfree((void *)new);
    return -1;
  }
  return 0;
}

这样一来，copy-on-write 就基本完成了，另外根据实验文档，我们还要在 copyout 函数中运用写时复制。

先对虚拟地址 va0 进行检查，如果符合则进行写时复制。

int copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len) {
  uint64 n, va0, pa0;
  while(len > 0){
    va0 = PGROUNDDOWN(dstva);
    if (checkcow(va0)) { // copy-on-write
      if (cow_fault(va0) != 0) {
        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;
}

实验结果

TODO

给页面上把读写锁，保证进程安全（不过好像测试用例没有这部分要求？）