The code is on Github. In general, if the COW mechanism is understood, the completion of this experiment is not very complicated.

This experiment is to complete COW (copy on write) fork. In the original XV6, the fork function was implemented by making a complete copy of the process’s address space directly. However, copying the entire address space can be time-consuming, and in many cases, the program immediately calls the exec function to replace the address space, resulting in a lot of wasted effort to fork. Even if the exec function is not called, read-only segments such as code segments of the parent and child processes can be shared to save memory space. COW also disperses address space copy latency to improve operating system efficiency.

The first is to change the fork function so that it does not copy the address space. Fork calls uvmCopy, so you just need to modify the uVMCopy function: Delete the kalloc function in uVMCopy, set the page table entries of the parent and child processes as unwritable, and set the COW flag bit (2 bits in the page table are reserved for the operating system, here uses the 8th bit #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;
}
Copy the code

We then set an array to hold the reference count of the page in memory. Since parallelism is involved, we also need to set a lock, and define some auxiliary functions:

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

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

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

inline
void
release_refcnt(a){
  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);
}
Copy the code

Modify the kfree function so that it releases the page only when the reference count is 1, and otherwise reduces the reference count only:

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);
}
Copy the code

Modify the kalloc function to set the reference count to 1 when allocating pages: note that the kalloc implementation does not return 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;
}
Copy the code

Add a judgment statement to the usertrap, and you only need to handle scause==15, because 13 is a page read error and COW does not cause a read error.

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){
  ...
}
Copy the code

In the cowcopy function, the COW flag bit is determined first. When the page is a COW page, it can be processed according to the reference count. If the count is greater than 1, you need to apply for a new page through kalloc, copy the content, and map the page. During the mapping, clear COW flag bit and set PTE_W flag bit. If the reference count is equal to 1, there is no need to apply for a new page, just change the flag bit of the page:


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;
}
Copy the code

Pay attention to lock Settings when reading or writing reference counts. In the Mappages function, a panic for remap is triggered, just comment it out, because COW is remapping the page.