Lab 6

Lab 6 ： Copy-on-Write Fork for xv6

问题：

xv6中的fork()系统调用将父进程的所有用户空间内存复制到子进程中。

如果父进程较大，则复制可能需要很长时间。更糟糕的是，这项工作经常造成大量浪费；

例如，子进程中的fork()后跟exec()将导致子进程丢弃复制的内存，而其中的大部分可能都从未使用过。

另一方面，如果父子进程都使用一个页面，并且其中一个或两个对该页面有写操作，则确实需要复制。

copy-on-write (COW) fork()的目标是推迟到子进程实际需要物理内存拷贝时再进行分配和复制物理内存页面,也就是说当你子进程想修改自己的页面时才给它分配，否则就一直跟父进程处于一个映射。

Hint1：

// riscv.h: 
// 可以使用RISC-V PTE中的RSW（reserved for software，即为软件保留的）位来实现判断一个页面是否是cow页面。
#define PTE_COW (1L << 5)

// vm.c
int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
  pte_t *pte;
  uint64 pa, i;
  uint flags;
  // char *mem;

  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);
    // 如果页面可写，那么cow页面就需要首先置为只读
    flags = PTE_FLAGS(*pte);
    if (flags & PTE_W) {
      flags = (flags | PTE_COW) & ~PTE_W;
      *pte = (*pte | PTE_COW) & ~PTE_W;
    }
    // if((mem = kalloc()) == 0)
    //   goto err;
    // memmove(mem, (char*)pa, PGSIZE);
    if(mappages(new, i, PGSIZE, pa, flags) != 0){
      goto err;
    }
    // 增加页面引用，具体看下面
    cowaddrefc((char*)pa);
  }
  return 0;

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

Hint3

确保每个物理页在最后一个PTE对它的引用撤销时被释放——而不是在此之前。 --- 修改kfree()

这样做的一个好方法是为每个物理页保留引用该页面的用户页表数的“引用计数”。--- 添加结构

当kalloc()分配页时，将页的引用计数设置为1。--- 修改kalloc()

当fork导致子进程共享页面时，增加页的引用计数；每当任何进程从其页表中删除页面时，减少页的引用计数。

kfree()只应在引用计数为零时将页面放回空闲列表。

可以将这些计数保存在一个固定大小的整型数组中。

你必须制定一个如何索引数组以及如何选择数组大小的方案。

例如，您可以用页的物理地址除以4096对数组进行索引，并为数组提供等同于*kalloc.c*中kinit()在空闲列表中放置的所有页面的最高物理地址的元素数。

在kalloc.c中定义计数的结构：

struct ref_count
{
  // count 在加减时非并发安全
  struct spinlock lock;
  int count[PHYSTOP/PGSIZE];
}ref;

初始化锁：

void
kinit()
{
  initlock(&kmem.lock, "kmem");
  initlock(&ref.lock,"ref");
  freerange(end, (void*)PHYSTOP);
}

修改kfree实现：只有在最后一个引用时才释放此物理页以及计数减一的功能：

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

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

  acquire(&ref.lock);
  // 如果 ref.count == 1，说明这是最后一个引用了，那么就正常释放
  if(--ref.count[(uint64)pa/PGSIZE] == 0){
    release(&ref.lock);

    r = (struct run*)pa;
     // Fill with junk to catch dangling refs.
    memset(pa, 1, PGSIZE);

    acquire(&kmem.lock);
    r->next = kmem.freelist;
    kmem.freelist = r;
    release(&kmem.lock);
  } else {
    // 否则就只释放锁，（因为在if中已经减掉一个计数了）
    release(&ref.lock);
  }
}

修改kalloc()初始化页的引用计数为1：

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


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

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

因为freerange会调用kfree，将count-1，所以为了保证初始时count的值都是0，需要先在freerange中初始化：

void
freerange(void *pa_start, void *pa_end)
{
  char *p;
  p = (char*)PGROUNDUP((uint64)pa_start);
  for(; p + PGSIZE <= (char*)pa_end; p += PGSIZE){
    ref.count[(uint64)p/PGSIZE] = 1;
    kfree(p);
  }
}

Hint2

修改usertrap()以识别页面错误。当COW页面出现页面错误时，使用kalloc()分配一个新页面，并将旧页面复制到新页面，然后将新页面添加到PTE中并设置PTE_W。

trap.c : usertrap()

else if(r_scause() == 13 || r_scause() == 15){
    // uint64 fault_va = r_stval();
    // pte_t *pte = walk(p->pagetable, fault_va, 0);
    // todo hint 2
    uint64 fault_va = r_stval();
    if(fault_va >= p->sz) 
        p->killed = 1;
    // 如果不是cow页面，那就不管了
    if(cowpage(p->pagetable,fault_va) != 0)
        p->killed = 1;
    // 如果分配空间失败，那就错误了
    if((uint64)cowalloc(p->pagetable,PGROUNDDOWN(fault_va)) == 0) {
        p->killed = 1;
    }
}

Hint4

修改copyout()在遇到COW页面时使用与页面错误相同的方案。

int
copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len)
{
  uint64 n, va0, pa0;

  while(len > 0){
    va0 = PGROUNDDOWN(dstva);
    pa0 = walkaddr(pagetable, va0);

    // 如果是cow页，就分配新的物理空间用于write
    if(cowpage(pagetable,va0) == 0) {
      pa0 = (uint64)cowalloc(pagetable,va0);
    }

    if(pa0 == 0)
      return -1;
    n = PGSIZE - (dstva - va0);
    if(n > len)
      n = len;
    // 已经知道这里会对 pa0 的内容进行修改，如果是cow页，就需要提前分配
    memmove((void *)(pa0 + (dstva - va0)), src, n);

    len -= n;
    src += n;
    dstva = va0 + PGSIZE;
  }
  return 0;
}

封装的函数

// 判断一个页面是否为cow页 (-1 : fail) (0 : succeed)
int cowpage(pagetable_t pgtbl,uint64 va) {
  if(va >= MAXVA || va < 0) 
    return -1;
  pte_t* pte = walk(pgtbl,va,0);
  if(!pte)
    return -1;
  if((*pte & PTE_V) == 0)
    return -1;
  return (*pte & PTE_COW ? 0 : -1);
}

// 获取引用计数 (-1 : fail) (>0 : succeed)
int cowrefc(void* pa) {
  return ref.count[(uint64)pa/PGSIZE];
}

// 增加引用计数 (-1 : fail) (0 : succeed)
int cowaddrefc(void* pa) {
  if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
    return -1;
  
  acquire(&ref.lock);
  ref.count[(uint64)pa/PGSIZE]++;
  release(&ref.lock);
  return 0;
}

// 为cow页分配新pa
void* cowalloc(pagetable_t pgtbl,uint64 va) {
  if(va % PGSIZE != 0) {
    return 0;
  }

  uint64 pa = walkaddr(pgtbl, va);
  if(!pa)
    return 0;
  
  pte_t* pte = walk(pgtbl,va,0);
  if(!pte) 
    return 0;

  if(cowrefc((char *)pa) == 1) {
    *pte |= PTE_W;
    *pte &= ~PTE_COW;
    return (void*)pa;
  } else {
    char *mem = kalloc();
    if(!mem) 
      return 0;
    
    memmove(mem,(char *)pa,PGSIZE);

    *pte &= ~PTE_V;
    if(mappages(pgtbl,va,PGSIZE,(uint64)mem,(PTE_FLAGS(*pte) | PTE_W) & ~PTE_COW) != 0) {
      kfree(mem);
      *pte |= PTE_V;
      return 0;
    }

    kfree((char *)PGROUNDDOWN(pa));
    return mem;
  }
}