[6.s081]Lab Copy-on-Write Fork for xv6

Overview

This lab aims to tell us how to optimize the memory allocation between process.

Copy-on-Write

The fork() function originally calls uvmcopy() to copy the whole page table of the parent process. It allocates a new page for each entry in the parent process and copy the content. As it's written in the book, in most cases we only read the content of the memory so it gives us the possibility to ask parent and child to share the memory at fisrt, and only to allocate new pages when writes happen.

1. We need a counter for memorizing the reference count of the pages, we only free the pages when the reference count is 0.
2. We need to implement a handler for page fault, which can allocate new pages when copy-on-write page fault happens. There are three kinds of page fault:
   1. Read Page Fault
   2. Write Page Fault - this is the one we need to take care of, which is 15 is scause.
   3. Instruction Page Fault
3. We need to add an extra flag in the page entry to distinguish real write page fault and page fault caused by our mechanism. There are two flags(bit 8 & 9) for customization. I used 8 here.

I tried to bind reference count utilities together with uvmunmap() and mappages(), but the latter will also be used in the kernel, which will results in all the pages will marked at least once since they are mapped to the kernel page table. Finally, I decoupled it and only to call the increase_ref() and decrease_ref() when the it's related to COW.

// vm.c
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);
        if(*pte & PTE_L || *pte & PTE_W) {
            flags = (flags & (~PTE_W)) | PTE_L;
            *pte = (*pte & (~PTE_W)) | PTE_L;
            increase_ref((void*)pa);
        }
    if(mappages(new, i, PGSIZE, pa, flags) != 0){
//      kfree(mem);
      goto err;
    }
  }
  return 0;

 err:
    // TODO: clean the parent page table?
  uvmunmap(new, 0, i / PGSIZE, 1);
  return -1;
}

// trap.c
int
cow_handler(pagetable_t pagetable, uint64 va)
{
    if(pagetable == 0) {
        panic("page table is null\n");
    }

    if(myproc()->sz <= va) {
        printf("cow_handler receives a out of range address\n");
        myproc()->killed = 1;
        return -1;
    }

    uint64 vabase = PGROUNDDOWN(va);
    pte_t *pte;
    if((pte = walk(pagetable, vabase, 0)) == 0) {
        return -1;
    }

    uint flags = PTE_FLAGS(*pte);
    if(!((*pte & PTE_L) && !(*pte & PTE_W))) {
        return -1;
    }

    void* mem = kalloc();
    if(mem == 0) {
        return -1;
    }

    memmove(mem, (void*)PTE2PA(*pte), PGSIZE);
    uvmunmap(pagetable, vabase, 1, 1);
    flags = (flags & (~PTE_L)) | PTE_W; 
    if(mappages(pagetable, vabase, PGSIZE, (uint64)mem, flags)) {
    return -1;
    }

  return 0;
}

// kalloc.c
void
increase_ref(void* pa)
{
    acquire(&kmem.lock);
    int idx = pageindex(pa);
    if(idx < 0 || idx >= 1 << 15) {
        release(&kmem.lock);
        return;
    }
    kmem.refcount[idx]++;
    if(kmem.refcount[idx] == 1) {
        kmem.refcount[idx]++;
    }
    release(&kmem.lock);
}

int 
decrease_ref(void* pa)
{
    acquire(&kmem.lock);
    int idx = pageindex(pa);
    if(idx < 0 || idx >= 1 << 15) {
        release(&kmem.lock);
        return 0;
    }
    --kmem.refcount[idx];
    int count = kmem.refcount[idx];
    release(&kmem.lock);
    return count;
}