MIT 6.s081 Lab copy-on-write fork

---

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

Problem and Solution

xv6中的fork系统调用将父进程的用户空间内存全部复制到子进程，而如果需要拷贝的内存数量比较大，拷贝过程会引起严重的开销问题。并且在子进程中，fork系统调用后通常紧跟着exec系统调用以修改进程影响，导致fork复制的内存被丢弃。如果父进程和子进程使用同一个页面，只有当其中一个进程对内存进行写操作时，才真正需要进行拷贝。

为fork实现copy-on-write机制，将为子进程分配和拷贝物理页的操作推迟到子进程或父进程发生了写操作时来完成。COW fork在创建子进程时，仅为子进程创建页表，使子进程的用户页表项指向父进程的物理页，并且将父进程和子进程的所有用户PTE标记为不可写。当进程尝试进行写操作时，触发一个缺页中断，然后内核为产生中断的进程分配一个新的物理页，将旧页的内容复制到新页，并为PTE添加写权限。当进程从缺页中断返回后，可以继续进行之前的写操作。

COW fork()中，多个进程的页表可能会映射到同一个物理页，而这个物理页只有当引用计数为0时才能被释放。

Implementation

首先修改uvmcopy函数的实现，在为子进程构建页表时，不分配物理页，而是将子进程的页表项映射到父进程的物理页，并将父进程和子进程的PTE_W标志位置0，同时使用保留位（第8位）作为PTE_COW位表示这是一个COW页。对于具有COW标志位的页，在发生写操作时创建一个新的物理页然后添加为其添加写权限，因此如果父进程中与该物理页对应的页表项本身不具有写权限，则不应该设置COW标志位，而是仅将子进程的页表映射到该物理页。

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);
    if (*pte & PTE_W) {
      *pte = (*pte & (~PTE_W)) | PTE_COW;
    }
    flags = PTE_FLAGS(*pte);
    if(mappages(new, i, PGSIZE, pa, flags) != 0){
      goto err;
    }
    kincref((void *)pa);
  }
  return 0;

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

然后修改usertrap函数的缺页中断处理逻辑，只有当发生缺页写中断时，检查发生缺页中断的虚拟地址对应的PTE是否具有PTE_COW标志位。对于具有COW标志位的页，进行拷贝操作，通过kalloc分配一个新的物理页，添加页表映射并为PTE添加写权限。此时如果有两个或多个进程同时映射到这个旧页，其他进程对于该页的权限保持不变，即当这些进程需要写时，依然会再次触发一个缺页中断，进行拷贝操作。代码如下：

void usertrap(void)
{
  int which_dev = 0;
  pte_t *pte;
  char *mem;
  uint flags;

  if ((r_sstatus() & SSTATUS_SPP) != 0)
    panic("usertrap: not from user mode");

  // send interrupts and exceptions to kerneltrap(),
  // since we're now in the kernel.
  w_stvec((uint64)kernelvec);

  struct proc *p = myproc();

  // save user program counter.
  p->trapframe->epc = r_sepc();

  if (r_scause() == 8)
  {
    // system call
    // ......
  }
  else if (r_scause() == 15)
  {
    uint64 va = r_stval();
    pte = walk(p->pagetable, va, 0);
    if (va < p->sz && pte != 0 && (*pte & PTE_V) && (*pte & PTE_COW))
    {
      uint64 pa = walkaddr(p->pagetable, va);
      
      if ((mem = kcopy_page((void *)pa)) == 0) {
        printf("Out of memory\n");
        p->killed = 1;
      } else {
        flags = (PTE_FLAGS(*pte) & (~PTE_COW)) | PTE_W;
        uvmunmap(p->pagetable, PGROUNDDOWN(va), 1, 0);
        if (mappages(p->pagetable, PGROUNDDOWN(va), PGSIZE, (uint64)mem, flags) != 0)
        {
          kfree(mem);
          p->killed = 1;
        }
      }
    } else {
      printf("PTE_COW is disabled\n");
      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;
    }
  }
  else if ((which_dev = devintr()) != 0)
  {
    // ok
  }
  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;
  }

  if (p->killed)
    exit(-1);

  // give up the CPU if this is a timer interrupt.
  if (which_dev == 2)
    yield();

  usertrapret();
}

上面的代码存在内存泄露问题。考虑如下情况：某一时刻只有一个进程映射到该物理页，并且对应的PTE其COW位为1，PTE_W位为0（其他原本映射到同一物理页的进程，此前对该物理页尝试写操作触发了缺页中断，从而使PTE映射到新的物理页），此时如果为该进程分配一个新的物理页，并解除对旧的物理页的映射，则当前系统中不再存在到旧页的映射，这部分空间将永远不会被回收，随着进程的增多，整个系统的内存将会被占满。

为每个物理页建立引用计数可以解决该问题。物理页面的引用计数表示当前映射到该页面的进程PTE的数量，当引用计数<=0时，表示当前已经没有进程使用这个页面，可以直接释放。当引用计数为1时，如果对这个物理页的写操作触发了page-fault，则直接为PTE添加写权限而不是分配一个新的物理页。在每次fork使子进程的页表映射到物理页时，对该物理页的引用计数+1。由于可能存在多个进程并发访问同一个页的引用计数，因此使用自旋锁加以保护。引用计数机制代码如下：

struct {
  int reference_cnt[(PHYSTOP - KERNBASE) / PGSIZE];
  struct spinlock lock;
} mem_ref;

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

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

  acquire(&mem_ref.lock);

  if (--mem_ref.reference_cnt[((uint64)pa-KERNBASE) / PGSIZE] <= 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);
  }
  release(&mem_ref.lock);
}

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

  acquire(&kmem.lock);
  r = kmem.freelist;
  if(r) {
    kmem.freelist = r->next;
    mem_ref.reference_cnt[(PGROUNDDOWN((uint64)r) - KERNBASE) / PGSIZE] = 1;
  }
  release(&kmem.lock);

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

void
kincref(void *pa)
{
  acquire(&mem_ref.lock);
  ++mem_ref.reference_cnt[((uint64)pa-KERNBASE) / PGSIZE];
  release(&mem_ref.lock);
}

void *
kcopy_page(void *pa) 
{
  char *mem;
  acquire(&mem_ref.lock);
  if (mem_ref.reference_cnt[((uint64)pa-KERNBASE) / PGSIZE] <= 1) {
    release(&mem_ref.lock);
    return pa;
  } else {
    if ((mem = kalloc()) == 0) {
      release(&mem_ref.lock);
      return 0;
    }
    --mem_ref.reference_cnt[((uint64)pa-KERNBASE) / PGSIZE];
    memmove(mem, (char *)pa, PGSIZE);
  }
  release(&mem_ref.lock);
  return (void *)mem;
}