Lab: Copy-on-Write Fork for xv6

实现xv6中的写时复制

Virtual memory provides a level of indirection: the kernel can intercept memory references by marking PTEs invalid or read-only, leading to page faults, and can change what addresses mean by modifying PTEs. There is a saying in computer systems that any systems problem can be solved with a level of indirection. The lazy allocation lab provided one example. This lab explores another example: copy-on write fork.

modify uvmcopy()

修改uvmcopy()函数，不分配新的物理页，而是直接在父子进程间共享
清空PTE_W不允许写，同时添加PTE_COW标记为COW(copy-on-write)页

(*pte) &= ~PTE_W;
(*pte) |= PTE_COW;
pa = PTE2PA(*pte);
flags = PTE_FLAGS(*pte);
if(mappages(new, i, PGSIZE, pa, flags) != 0){
    goto err;
}

modify trap handler

通过r_scause()的值判断缺页中断
调用is_cow()判断是否是COW页
如果是，则调用cow_alloc()分配新内存

else if(r_scause()==13||r_scause()==15){
    uint64 va=r_stval();
    if(is_cow(p->pagetable,va)){
        if(cow_alloc(p->pagetable,va)==0)
            p->killed=1;
}

is_cow()

pte中有两位为Reserved for supervisor software 分别是第九位和第十位

把第九位拿来标记COW

#define PTE_COW (1L << 8)

检查pte中有没有设置PTE_COW判断是否是COW页

int
is_cow(pagetable_t pagetable, uint64 va)
{
  pte_t *pte;

  if(va >= MAXVA)
    return 0;

  pte = walk(pagetable, va, 0);
  if(pte == 0)
    return 0;
  if((*pte & PTE_V) == 0)
    return 0;
  if((*pte & PTE_U) == 0)
    return 0;
  if((*pte&PTE_COW)==0)
    return 0;
  return 1;
}

cow_alloc()

分配新的内存，复制旧页内容到新页
打上PTE_W标记，去除PTE_COW标记
分了防止mappages()panic，调用walk()获取pte然后映射就行

uint64
cow_alloc(pagetable_t pagetable,uint64 va)
{
  uint64 pa=walkaddr(pagetable,va);
  char* mem=kalloc();
  if(mem==0)
  {
    return 0;
  }
  memmove(mem,(char*)pa,PGSIZE);
  va=PGROUNDDOWN(va);
  pte_t* pte=walk(pagetable,va,0);
  uint flag=PTE_FLAGS(*pte);
  (*pte)=PA2PTE((uint64)mem)| flag | PTE_W;
  (*pte)&=~PTE_COW;
  kfree((void*)pa);
  return (uint64)mem;
}

如果内存不够了，则返回里，在trap handler里杀死进程

if(cow_alloc(p->pagetable,va)==0)
    p->killed=1;

page's reference count

因为现在可能有多个进程共享一页，所以为每个进程维护一个引用计数
我这里比较懒，没有算的很仔细，就开了一个比较大的数组

#define NPA PHYSTOP/PGSIZE

int ref[NPA];

void
kinit()
{
    initlock(&kmem.lock, "kmem");
    for(int i=0;i<NPA;i++)
        ref[i]=0;
    freerange(end, (void*)PHYSTOP);
}

因为每个物理地址都是页对齐的，所以pa/PGSIZE就可以得出对应的下标

在kfree()中，先减少计数，只有物理页的引用计数到零后，才真正free

if(ref[((uint64)pa)/PGSIZE]!=0)
{
    kdecre(pa);
    if(ref[((uint64)pa)/PGSIZE]!=0)
        return;
}

kincre()和kdecre()就单纯的增加和减少计数

void kincre(void* pa)
{
  ref[((uint64)pa)/PGSIZE]++;
}

void kdecre(void* pa)
{
  ref[((uint64)pa)/PGSIZE]--;
}

kalloc()中，分配页时将计数置为1

if(r)
{
    memset((char*)r, 5, PGSIZE); // fill with junk
    ref[((uint64)r)/PGSIZE]=1;
}

uvmcopy()共享页时要增加对应的计数

if(mappages(new, i, PGSIZE, pa, flags) != 0){
      goto err;
}
kincre((void*)pa);

cow_alloc()分配新页时要减少对应的计数

kfree((void*)pa);
return (uint64)mem;

modify copyout()

内核可能会写用户地址空间，要处理COW页的情况
和处理缺页中断类似

if(is_cow(pagetable,va0))
{
    pa0=cow_alloc(pagetable,va0);
    if(pa0==0)
    return -1;
}

test