Lab6: Copy-on-Write Fork for xv6

原文地址：YSBLOG
参考资料：MIT 6.s081 xv6-lab6-cow - 知乎 (zhihu.com)

实验背景：

​ 在原本的xv6中，当Shell处理指令时，会通过fork创建一个子进程，该子进程包含一个完整的Shell拷贝，在该子进程中调用exec执行对应的指令程序，而在exec中第一件事就是丢去fork拷贝的Shell地址空间，取而代之的是对应指令的地址空间。在这个过程中，Shell拷贝后就被丢弃，降低了程序执行的效率。

实验目的：

​ 结合上述背景，在本次实验中需要实现cow（copy-on-write），当创建子进程时，并不实际对父进程进行拷贝，而是将页表项改为只读，在父/子进程第一次对页面进行写操作时才进行内存的拷贝，从而节约实际使用内存空间。

​ 根据提示，首先我们将PTE标志位的第八位设置为PTE_COW用于标识该页表项对应的页面是否是cow页面。

// riscv.h
#define PTE_COW (1L << 8) // cow page

​ 我们引入cow后，当父进程退出后，我们并不能直接释放父进程的内存，因为这时子进程可能也指向了该内存页面（该页面还没有触发page fault，并没有实际进行拷贝），若释放后子进程就无法访问该页面内存了。所以我们需要对每个页面增加一个引用计数，当进程退出时，若该页面的引用计数为0才释放内存。

// kalloc.c

// 用于访问物理页引用计数数组
#define PA2PGREF_ID(p) (((p)-KERNBASE)/PGSIZE)
#define PGREF_MAX_ENTRIES PA2PGREF_ID(PHYSTOP)

// 定义单个页面结构
struct page_ref{
  struct spinlock lock; // 每个页面一个锁
  int cnt; // 引用计数
};
struct page_ref page_ref_list[PGREF_MAX_ENTRIES]; // 引用计数数组


void
kinit()
{
  // 初始化每个页面引用计数的锁
  for (int i = 0; i < PGREF_MAX_ENTRIES; ++i) {
    initlock(&(page_ref_list[i].lock), "kpage_ref");
    page_ref_list[i].cnt = 1; // 页面引用计数初始值为1
  }
  initlock(&kmem.lock, "kmem");
  freerange(end, (void*)PHYSTOP);
}

// 当页面引用计数为0时才释放内存
void
kfree(void *pa)
{
  struct run *r;

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

  // 获取页面锁
  acquire(&((page_ref_list[PA2PGREF_ID((uint64)pa)].lock)));
  // 该页面引用计数减一
  page_ref_list[PA2PGREF_ID((uint64)pa)].cnt--;
  if (page_ref_list[PA2PGREF_ID((uint64)pa)].cnt > 0) {
    // 还有进程在引用该页面，不释放内存，直接返回
    // 释放锁
    release(&((page_ref_list[PA2PGREF_ID((uint64)pa)].lock)));
    return;
  }
  release(&((page_ref_list[PA2PGREF_ID((uint64)pa)].lock)));
    
  // 下面是实际释放该页面内存
  // 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);
}

// 分配物理内存时初始化引用计数为1
void *
kalloc(void)
{
  struct run *r;

  acquire(&kmem.lock);
  r = kmem.freelist; // 获取空闲页面
  if(r)
    kmem.freelist = r->next; // 将空闲页面指向下一个页面
  release(&kmem.lock);

  if(r){
    memset((char*)r, 5, PGSIZE); // fill with junk
    // 获取页面锁
    acquire(&((page_ref_list[PA2PGREF_ID((uint64)r)].lock)));
    page_ref_list[PA2PGREF_ID((uint64)r)].cnt = 1; // 新页面的引用计数为1
    // 释放锁
    release(&((page_ref_list[PA2PGREF_ID((uint64)r)].lock)));
  }
  return (void*)r;
}

// 引用页面，为 pa 的引用计数增加 1
int krefpage(uint64 pa) {
  if(pa % PGSIZE != 0 // pa位于guard page上 
  || (char*)pa < end // pa位于内核代码区域
  || pa >= PHYSTOP) // pa超过最大内存区域
  { 
    return -1;
  }
  acquire(&((page_ref_list[PA2PGREF_ID(pa)].lock)));
  page_ref_list[PA2PGREF_ID(pa)].cnt++; // 引用计数加一
  release(&((page_ref_list[PA2PGREF_ID(pa)].lock)));
  return 1;
}

// defs.h
int             krefpaga(uint64 pa);

与lab5相同，引入cow页面后，系统触发的缺页中断的情况需要特殊处理，当检测到是由于cow机制触发的缺页中断后，我们需要对cow页面进行实际的物理内存分配和映射，所以添加cow_check用于检测是否是cow页面，cow_copy用于执行对cow页面的实际物理内存分配以及映射。

// kalloc.c
// 发生缺页中断时，用于检测该页面地址是否是cow页面
int cow_check(pagetable_t pagetable, uint64 va) {
  if (va > MAXVA) {
    return 0;
  }
  pte_t *pte = walk(pagetable, va, 0);
  if (pte == 0) {
    return 0;
  }
  if (( (*pte) & PTE_V) == 0) {
    return 0;
  }
  return ((*pte) & (PTE_COW));
}


// 当触发缺cow页触发缺页中断时进行实际物理内存分配和映射
uint64
cow_copy(pagetable_t pagetable, uint64 va) {
  va = PGROUNDDOWN(va); // 获得当前页面起始位置
  pte_t *pte = walk(pagetable, va, 0);
  uint64 pa = PTE2PA(*pte);
  // 获取当前页面锁
  acquire(&((page_ref_list[PA2PGREF_ID(pa)].lock)));
  if (page_ref_list[PA2PGREF_ID(pa)].cnt == 1) {
    // 当前页面只有一个进程在使用时，直接返回该页面
    // 恢复该页面权限
    *pte = (*pte) & (~PTE_COW);
    *pte = (*pte) | (PTE_W);
    // 释放锁
    release(&((page_ref_list[PA2PGREF_ID(pa)].lock)));
    return pa;
  }
  // 一定要释放锁，在kalloc中会申请锁，会导致死锁
  release(&((page_ref_list[PA2PGREF_ID(pa)].lock)));

  // 分配新的内存页面
  uint64 newpa = (uint64)kalloc();
  if (newpa == 0) {
    // 内存分配失败 
    return 0;
  }

  // 复制旧页面内容到新页面
  memmove((void*)newpa, (void*)pa, PGSIZE);
  *pte = (*pte) & (~PTE_V); // 清楚页面PTE_V标志，防止remap 
  uint64 flag = PTE_FLAGS(*pte);
  flag = flag | PTE_W;
  flag = flag & (~PTE_COW);

  // 将申请的物理地址隐射到对应的虚拟地址上
  if(mappages(pagetable, va, PGSIZE, (uint64)newpa, flag) != 0) {
    kfree((void*)newpa);
    return 0;
  }

  // 尝试清除原始的cow副本，此时引用计数可能为0
  kfree((void*)PGROUNDDOWN(pa));
  
  return (uint64)newpa;
}

// defs.h
uint64 cow_copy(pagetable_t pagetable, uint64 va);
int cow_check(pagetable_t pagetable, uint64 va);

​ 与lab5同样的方式，修改陷入中断的处理。

// trap.c
void
usertrap(void)
{
  ... ...
  } else if((which_dev = devintr()) != 0){
    // ok
  } else if (r_scause() == 13 || r_scause() == 15) {
    // 出现缺页异常
    uint64 va = r_stval();
    if (cow_check(p->pagetable, va)) {
      // 异常为cow页面
      if (cow_copy(p->pagetable, va) == 0) {
        p->killed = 1;
      }
    } else {
      p->killed = 1;
    }
  } 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;
  }
  ... ...
}

​ 最后需要修改copyout，当拷贝页面为cow页面时，调用cow_copy。

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

  while(len > 0){
    va0 = PGROUNDDOWN(dstva);
    pa0 = walkaddr(pagetable, va0);
    if (cow_check(pagetable, va0) != 0) {
      // 若拷贝页面为cow页面，执行cow拷贝
      pa0 = cow_copy(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;
}

​ 最后使用cowtest和usertests完成测试。

init: starting sh
$ usertests
usertests starting
test execout: OK
test copyin: OK
test copyout: OK
test copyinstr1: OK
test copyinstr2: OK
test copyinstr3: OK
test rwsbrk: OK
test truncate1: OK
test truncate2: OK
test truncate3: OK
test reparent2: OK
test pgbug: OK
test sbrkbugs: usertrap(): unexpected scause 0x000000000000000c pid=3235
            sepc=0x000000000000555e stval=0x000000000000555e
usertrap(): unexpected scause 0x000000000000000c pid=3236
            sepc=0x000000000000555e stval=0x000000000000555e
OK
test badarg: OK
test reparent: OK
test twochildren: OK
test forkfork: OK
test forkforkfork: OK
test argptest: OK
test createdelete: OK
test linkunlink: OK
test linktest: OK
test unlinkread: OK
test concreate: OK
test subdir: OK
test fourfiles: OK
test sharedfd: OK
test dirtest: OK
test exectest: OK
test bigargtest: OK
test bigwrite: OK
test bsstest: OK
test sbrkbasic: OK
test sbrkmuch: OK
test kernmem: OK
test sbrkfail: OK
test sbrkarg: OK
test validatetest: OK
test stacktest: OK
test opentest: OK
test writetest: OK
test writebig: OK
test createtest: OK
test openiput: OK
test exitiput: OK
test iput: OK
test mem: OK
test pipe1: OK
test preempt: kill... wait... OK
test exitwait: OK
test rmdot: OK
test fourteen: OK
test bigfile: OK
test dirfile: OK
test iref: OK
test forktest: OK
test bigdir: OK
ALL TESTS PASSED
$ cowtest 
simple: ok
simple: ok
three: ok
three: ok
three: ok
file: ok
ALL COW TESTS PASSED