在前几个lab中提到过COW（写时复制），比如fork一个进程后，子进程与父进程使用同样的指令和数据。如果每次都复制一份父进程的数据，在一些情况下子进程创建后调用exec，原本被复制的数据根本没有被使用过就被直接覆盖，在这种情况下就白白浪费了这次复制，并且复制也会有很大的开销，会拖慢系统执行的速度。

为了提高系统执行效率，避免资源浪费，引入了COW（写时复制）机制，需要依赖缺页中断机制。当进行用户虚拟内存复制（uvmcopy）时，对相同的物理地址进行pte映射，使多个进程的pte指向同一片物理内存，并且这部分内容是只读的，如果有任何一个指向共享物理内存的进程需要对这部分内存进行写操作时，触发缺页中断，此时将需要进行写操作的页面进行真正的复制。

Lab5 Implement copy-on write (hard)实现

要实现一个稳健的COW，必须串联起内核的四个核心模块：

1. 引用计数

物理内存是共享的，我们不能在kfree时直接回收。因此在kernel/kalloc.c中引入了全局计数数组：

• ref_count结构体：保存一个全局数组，配备自旋锁（以后章节中会提到）。
• 修改kinit,freerange,kfree,kalloc函数：kalloc分配物理页后初始化引用计数为1；kfree不再直接释放内存，添加检测引用计数机制；另外两个函数涉及初始化物理内存，也需要做一定修改来应用全局计数数组。
• kincref,kget_ref函数：为虚拟内存处理提供物理内存引用计数的信息。

struct {
  struct spinlock lock;
  int count[PHYSTOP / PGSIZE];
} ref_count;

这里使用了一个小trick：通过将ref_count.count数组全部设为1，在freerange中对每个物理页进行kfree，将所有页的引用计数初始化为0。

void
kinit()
{
  initlock(&kmem.lock, "kmem");
  initlock(&ref_count.lock, "ref_count");
  for (int i = 0; i < PHYSTOP / PGSIZE; i++)
    ref_count.count[i] = 1;
  freerange(end, (void*)PHYSTOP);
}

void
freerange(void *pa_start, void *pa_end)
{
  char *p;
  p = (char*)PGROUNDUP((uint64)pa_start);
  for(; p + PGSIZE <= (char*)pa_end; p += PGSIZE)
    kfree(p);
}

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

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

  uint64 i = (uint64)pa / PGSIZE;

  acquire(&ref_count.lock);
  if (ref_count.count[i] < 1)
    panic("kfree: count < 1");

  ref_count.count[i]--;
  int c = ref_count.count[i];
  release(&ref_count.lock);

  if (c == 0) {
    // Fill with junk to catch dangling refs.
    memset(pa, 1, PGSIZE);

    r = (struct run*)pa;

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

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

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

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

    uint64 i = (uint64)r / PGSIZE;

    acquire(&ref_count.lock);
    ref_count.count[i] = 1;
    release(&ref_count.lock);
  }
  return (void*)r;
}

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

  uint64 i = (uint64)pa / PGSIZE;

  acquire(&ref_count.lock);
  ref_count.count[i]++;
  release(&ref_count.lock);
}

int
kget_ref(void *pa)
{
  if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
    panic("kget_ref");
  int c;
  acquire(&ref_count.lock);
  c = ref_count.count[(uint64)pa / PGSIZE];
  release(&ref_count.lock);
  return c;
}

2. 页表管理（uvmcopy）

修改uvmcopy，不再调用kalloc。

• 清除PTE_W写权限。
• 设置自定义的PTE_COW标志位，表示当前pte指向一个COW物理页。
• 将父进程的物理页直接映射给子进程。

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");
    *pte &= (~PTE_W);
    *pte |= (PTE_COW);
    pa = PTE2PA(*pte);
    flags = PTE_FLAGS(*pte);

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

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

3. 中断处理（usertrap）

当进程尝试写入只读页时，RISC-V硬件抛出scause 15。

• 逻辑：检查stval中保存的中断产生地址是否合法(< MAXVA and < p->sz)。
• 处理：调用store_page_fault进行物理页的复制。

void
usertrap(void)
{
  int which_dev = 0;

  if((r_sstatus() & SSTATUS_SPP) != 0)
    panic("usertrap: not from user mode");

  // send interrupts and exceptions to kerneltrap(),
  // since we're now in the kernel.
  w_stvec((uint64)kernelvec);

  struct proc *p = myproc();

  // save user program counter.
  p->trapframe->epc = r_sepc();

  if(r_scause() == 8){
    // system call

    if(p->killed)
      exit(-1);

    // sepc points to the ecall instruction,
    // but we want to return to the next instruction.
    p->trapframe->epc += 4;

    // an interrupt will change sstatus &c registers,
    // so don't enable until done with those registers.
    intr_on();

    syscall();
  } else if (r_scause() == 15) {
    // store page fault
    uint64 va = r_stval();
    if (va >= MAXVA || va >= p->sz)
      p->killed = 1;
    else {
      if (store_page_fault(p->pagetable, va) != 0) {
        p->killed = 1;
      }
    }

  } else if((which_dev = devintr()) != 0){
    // ok
  } else {
    printf("usertrap(): unexpected scause %p pid=%d\n", r_scause(), p->pid);
    printf("            sepc=%p stval=%p\n", r_sepc(), r_stval());
    p->killed = 1;
  }

  if(p->killed)
    exit(-1);

  // give up the CPU if this is a timer interrupt.
  if(which_dev == 2)
    yield();

  usertrapret();
}

store_page_fault中还有一点特殊的处理：当count为1时，不需要额外复制一个页，只需要设置这个页的PTE_W，并且清除PTE_COW，这样可以避免一次不必要的页面复制以及页面清除的资源消耗。

int
store_page_fault(pagetable_t pagetable, uint64 va)
{
  char *mem;
  pte_t *pte;
  uint64 pa;
  uint flags;

  if (va >= MAXVA)
    return -1;

  if((pte = (pte_t*)walk(pagetable, va, 0)) == 0)
    panic("store_page_fault: pte should exist");

  if ((*pte & PTE_V) && (*pte & PTE_U) && (*pte & PTE_COW)) {
    pa = PTE2PA(*pte);

    int count = kget_ref((void*)pa);

    if (count > 1) {
      if((mem = kalloc()) == 0)
        return -1;

      memmove(mem, (char*)pa, PGSIZE);

      flags = (PTE_FLAGS(*pte) | PTE_W) & ~PTE_COW;

      *pte = PA2PTE(mem) | flags;
      kfree((void*)pa);
    } else if (count == 1) {
      *pte |= PTE_W;
      *pte &= ~PTE_COW;
    }

    return 0;
  }

  return -1;
}

4. 内核边界（copyout）

这也是这个lab需要处理的一个问题，内核在执行系统调用时（如read）写回用户内存时，通过软件（即walk函数）手动模拟了硬件查表的过程，不会触发硬件中断，因此必须在copyout中手动拦截并处理PTE_COW。详细流程如下图：

图 5-1 ：Copyout COW Flow

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

  while(len > 0){
    va0 = PGROUNDDOWN(dstva);
    if (va0 >= MAXVA)
      return -1;

    if ((pte = walk(pagetable, va0, 0)) == 0 || (*pte & PTE_V) == 0)
      return -1;

    if (*pte & PTE_COW) {
      if (store_page_fault(pagetable, va0) < 0)
        return -1;

      if ((pte = walk(pagetable, va0, 0)) == 0 || (*pte & PTE_V) == 0)
        return -1;
    }

    if ((*pte & PTE_W) == 0)
      return -1;

    pa0 = PTE2PA(*pte);
    if(pa0 == 0)
      return -1;
    n = PGSIZE - (dstva - va0);
    if(n > len)
      n = len;
    memmove((void *)(pa0 + (dstva - va0)), src, n);

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

本实验到此结束，一个hard的lab写了一天多，现在已经比较深入了解了如何添加一个内核处理函数，并且熟悉虚拟内存的处理机制（如RISC-V中的一些宏调用和pte设置方法等），收获较大。