XV6学习（9）Lab cow: Copy-on-write fork

代码在 github 上。总体来说如果理解了COW机制的话，这个实验的完成也没有很复杂。

这一个实验是要完成COW（copy on write）fork。在原始的XV6中，fork函数是通过直接对进程的地址空间完整地复制一份来实现的。但是，拷贝整个地址空间是十分耗时的，并且在很多情况下，程序立即调用 exec 函数来替换掉地址空间，导致 fork 做了很多无用功。即使不调用 exec 函数，父进程和子进程的代码段等只读段也是可以共享的，从而达到节省内存空间的目的。同时COW也可以将地址空间拷贝的耗时进行延迟分散，提高操作系统的效率。

首先就是要对 fork 函数进行修改，使其不对地址空间进行拷贝。 fork 函数会调用 uvmcopy 进行拷贝，因此只需要修改 uvmcopy 函数就可以了：删去 uvmcopy 中的 kalloc 函数，将父子进程页面的页表项都设置为不可写，并设置COW标志位（在页表项中保留了2位给操作系统，这里用的是第8位 #define PTE_COW (1L << 8) ）

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);
    flags = PTE_FLAGS(*pte);

    *pte = ((*pte) & (~PTE_W)) | PTE_COW; // set parent's page unwritable
    // printf("c: %p %p %p\n", i, ((flags & (~PTE_W)) | PTE_COW), *pte);
    // map child's page with page unwritable
    if(mappages(new, i, PGSIZE, (uint64)pa, (flags & (~PTE_W)) | PTE_COW) != 0){
      goto err;
    }
    refcnt_incr(pa, 1);
  }
  return 0;

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

之后设置一个数组用于保存内存页面的引用计数，由于会涉及到并行的问题，因此也需要设置一个锁，同时定义了一些辅助函数：

struct {
  struct spinlock lock;
  uint counter[(PHYSTOP - KERNBASE) / PGSIZE];
} refcnt;

inline
uint64
pgindex(uint64 pa){
  return (pa - KERNBASE) / PGSIZE;
}

inline
void
acquire_refcnt(){
  acquire(&refcnt.lock);
}

inline
void
release_refcnt(){
  release(&refcnt.lock);
}

void
refcnt_setter(uint64 pa, int n){
  refcnt.counter[pgindex((uint64)pa)] = n;
}

inline
uint
refcnt_getter(uint64 pa){
  return refcnt.counter[pgindex(pa)];
}

void
refcnt_incr(uint64 pa, int n){
  acquire(&refcnt.lock);
  refcnt.counter[pgindex(pa)] += n;
  release(&refcnt.lock);
}

修改 kfree 函数，使其只有在引用计数为1的时候释放页面，其他时候就只减少引用计数：

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

  // page with refcnt > 1 should not be freed
  acquire_refcnt();
  if(refcnt.counter[pgindex((uint64)pa)] > 1){
    refcnt.counter[pgindex((uint64)pa)] -= 1;
    release_refcnt();
    return;
  }

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

  // Fill with junk to catch dangling refs.
  memset(pa, 1, PGSIZE);
  refcnt.counter[pgindex((uint64)pa)] = 0;
  release_refcnt();

  r = (struct run*)pa;

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

修改 kalloc 函数，使其在分配页面时将引用计数也设置为1：这里注意要判断 r 是否为0， kalloc 实现时没有当 r==0 时就返回。

void *
kalloc(void)
{
  ...
  if(r)
    memset((char*)r, 5, PGSIZE); // fill with junk

  if(r)
    refcnt_incr((uint64)r, 1); // set refcnt to 1
  return (void*)r;
}

在 usertrap 中加入判断语句，这里只需要处理 scause==15 的情况，因为13是页面读错误，而COW是不会引起读错误的。

void
usertrap(void)
{
  ...
  } else if(r_scause() == 15){
    // page write fault
    uint64 va = r_stval();
    if(cowcopy(va) == -1){
      p->killed = 1;
    }
  } else if((which_dev = devintr()) != 0){
  ...
}

在 cowcopy 函数中先判断COW标志位，当该页面是COW页面时，就可以根据引用计数来进行处理。如果计数大于1，那么就需要通过 kalloc 申请一个新页面，然后拷贝内容，之后对该页面进行映射，映射的时候清除COW标志位，设置 PTE_W 标志位；而如果引用计数等于1，那么就不需要申请新页面，只需要对这个页面的标志位进行修改就可以了：

int
cowcopy(uint64 va){
  va = PGROUNDDOWN(va);
  pagetable_t p = myproc()->pagetable;
  pte_t* pte = walk(p, va, 0);
  uint64 pa = PTE2PA(*pte);
  uint flags = PTE_FLAGS(*pte);

  if(!(flags & PTE_COW)){
    printf("not cow\n");
    return -2; // not cow page
  }

  acquire_refcnt();
  uint ref = refcnt_getter(pa);
  if(ref > 1){
    // ref > 1, alloc a new page
    char* mem = kalloc_nolock();
    if(mem == 0)
      goto bad;
    memmove(mem, (char*)pa, PGSIZE);
    if(mappages(p, va, PGSIZE, (uint64)mem, (flags & (~PTE_COW)) | PTE_W) != 0){
      kfree(mem);
      goto bad;
    }
    refcnt_setter(pa, ref - 1);
  }else{
    // ref = 1, use this page directly
    *pte = ((*pte) & (~PTE_COW)) | PTE_W;
  }
  release_refcnt();
  return 0;

  bad:
  release_refcnt();
  return -1;
}

在对引用计数进行读写时注意锁的设置。在 mappages 函数中会触发一个remap的panic，这里只要注释掉就行了，因为COW就是要对页面进行重新映射的。