xv6 cow

发布时间 2023-12-03 18:26:59作者: trashwin

虚拟内存提供了一定程度的间接性:内核可以通过将PTE标记为无效或只读来拦截内存引用,从而导致页面错误,并可以通过修改PTE来更改地址的含义。

xv6中的fork系统调用将父进程的所有用户空间内存复制到子进程中。如果父对象很大,则复制可能需要很长时间。更糟糕的是,这项工作经常被大量浪费:fork通常在子进程后跟exec,这会丢弃复制的内存,其中大部分复制内存都不使用。但如果父级和子级都使用复制的页面,而且都写入,则确实需要复制。

COW fork只为子进程创建一个页表,并且复制父进程的页表。但为了支持父子进程对同一页面的读写,COW fork将页表所有PTE标记为只读。当任一进程试图写入其中一个COW页面时,CPU将强制执行页面故障,从而进入usertrap。usertrap缺页处理程序检测到这种情况(r_scause() = 15,Store page fault),为出错进程分配一页物理内存,将原始页面内容复制到新页面中,并修改出错进程中的对应PTE以引用新页面,标记为可写。当页面错误处理程序返回时,用户进程将能够写入页面的副本,并且重新执行导致缺页的程序。

对于设计COW面临的问题,以下是解决方法:

  1. 如何判断一个页面是不是采用了COW?
    在PTE的RSW保留位中设置新的PTE_COW标志,表示该页面采用了COW。
  2. 多个进程共享同一页面时,如何保证正确保留和释放页面?
    为每个物理页面维护一个引用计数,计数为0时,释放页面。
  3. 如何维护引用计数?
    使用数组存储计数,以pa/PGSIZE作为索引。fork创建子进程共享页面时,计数加1,进程调用kfree时,计数减1。由于共享页面的进程会争用引用计数,因此需要使用锁来保护。

需要修改哪些函数代码?
为了方便操作,重新定义了一些全局变量、辅助函数和宏。锁的使用之前的lab已经有了,这里不再赘述。

// riscv.h
#define PTE_COW (1L << 8) // copy on write
#define PGINDEX(a)     (((a)) >> PGSHIFT)

// kalloc.c
uint pgref[PHYSTOP>>PGSHIFT]; // page reference count
struct spinlock reflock; // lock for pgref
void incref(uint64 pa){
  uint idx = PGINDEX(pa);
  acquire(&reflock);
  pgref[idx]++;
  release(&reflock);
}

void setref(uint64 pa, uint cnt){
  uint idx = PGINDEX(pa);
  acquire(&reflock);
  pgref[idx] = cnt;
  release(&reflock);
}

void decref(uint64 pa){
  uint idx = PGINDEX(pa);
  acquire(&reflock);
  pgref[idx]--;
  release(&reflock);
}

usertrap()

处理Store page fault时,检测COW,分配新的物理页面,将原始页面内容复制到新页面中,并修改出错进程中的对应PTE以引用新页面,标记为可写。
由于类似的行为在copyout中也可能会用到,因此将其封装为一个函数CowHandler。decref设计原本是为了在分配新页面后,递减原页面引用计数,这个任务直接交给kfree,来确保计数为0的页面能被立即释放,而使用decref可能导致页面无法正常释放的问题(three中分配了很多页面,第三次中kalloc会出错,没有剩余空间)。

// trap.c
else if(r_scause() == 15){
    int err = CowHandler(r_stval());
    if(err < 0){
      printf("usertrap(): unexpected CowHandler err %p pid=%d\n", err, p->pid);
      printf("            sepc=%p stval=%p\n", r_sepc(), r_stval());
      setkilled(p);
    }
}

int CowHandler(uint64 va){
  pte_t *pte = walk(myproc()->pagetable, va, 0);
  if(pte == 0 || (*pte & PTE_V) == 0 || (*pte & PTE_U) == 0 || (*pte & PTE_COW) == 0)
    return -1;
  acquire(&reflock);
  uint cnt = pgref[PGINDEX(*pte)];
  if(cnt == 1){
    *pte &= ~PTE_COW;
    *pte |= PTE_W;
    release(&reflock);
    return 0;
  }
  release(&reflock);
  char* mem = kalloc();
  if(mem == 0)
    return -2;
  uint64 pa = PTE2PA(*pte);
  memmove(mem, (void*)pa, PGSIZE);

  // !!!!!!!!!!!!!! dont use decref, or may cause kalloc return 0
  // if A finds ref = 2, it will kalloc, before A decref, B find ref = 2, which also kalloc
  //then ref get decreased twice and becomes 0, so it is dead.
  kfree((void*)pa);

  *pte = PA2PTE(mem) | PTE_W | PTE_FLAGS(*pte);
  *pte &= ~PTE_COW;
  return 0;
}
  • uvmcopy():未使用COW时,fork函数调用uvmcopy,对父进程页表中所有有效的页表项,为子进程分配空间并复制;而使用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);
    if(((*pte) & PTE_W)||((*pte) & PTE_COW)){
      *pte &= (~PTE_W);
      *pte |= PTE_COW;
    }
    flags = PTE_FLAGS(*pte);

    if(mappages(new, i, PGSIZE, pa, flags)!=0){
      goto err;
    }
    incref(pa);
  }
  return 0;
 err:
  uvmunmap(new, 0, i / PGSIZE, 1);
  return -1;
}
  • copyout 该函数将内核数据复制到用户空间,所以也可能出现缺页中断,需要处理COW
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;
    pte = walk(pagetable, va0, 0);
    if(pte == 0 || (*pte & PTE_V) == 0 || (*pte & PTE_U) == 0)
      return -1;
    if((*pte & PTE_W) == 0){
      if(CowHandler(va0) < 0)
        return -1;
    }
    pa0 = PTE2PA(*pte);
    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;
}