6.S081/6.828: 5 Lab Copy-on-Write Fork for xv6

原创

冰寒火

修改于 2022-11-26 05:01:02

4260

修改于 2022-11-26 05:01:02

文章被收录于专栏：软件设计软件设计

没有什么问题是增加一个中间层解决不了的。

一、page fault

page fault主要三种情况引起的:

load page faults：当load instruction无法翻译虚拟地址时发生
store page faults：当store instruction无法翻译虚拟地址时发生
instruction page faults：当一个instruction的地址无法翻译时发生

处理page fault时需要的信息有以下：

读、写的虚拟地址或者执行指令的地址，放在STVAL中。
错误原因，13表示是因为load引起的page fault；15表示是因为store引起的page fault；12表示是因为指令执行引起的page fault；8表示ecall引起的。
引起page fault的指令地址，前面是读写数据的地址，这里是读写指令的地址（PC），用于加载数据后执行指令。

预留的几个bit是给软件层面扩展的，CPU是感知不出来的。

二、背景

fork系统调用会复制proc给子进程，除了pid，几乎其他的都一样，其中开销最大的就是用户页表。更重要的是，fork之后一般会用exec替换掉用户页表，导入新的可执行文件，所以拷贝用户页表显得有点浪费。因此诞生了写时复制，延迟空间的分配，用户页表浅拷贝，最底层页表项延迟拷贝，另外一种延迟分配的场景就是sbrk，后面可以考虑实现。

COW拷贝时需要对父子进程的页表项清除写权限，一旦发生写cpu就触发page fault，然kernel page fault handler捕获这case，拷贝这一页，然后将父子进程的页表设置为可写。

修改uvmcopy，拷贝父进程页表，clear PTE_W，设置PTE_COW，PTE_COW是用于软件层面的，硬件不会检测，需要我们自己处理。
修改usertrap识别cow page fault，此时分配new page，并设置父子进程PTE_W。
但最后一个PTE 引用释放，物理页应该被释放，可以采用一个数组去跟踪物理页引用计数，但是这个数组的大小是一个问题。
修改copyout，copyout是向用户态写入返回结果，也可能遇到page fault。

三、实现

1 物理页引用计数

考虑并发和共享问题，需要加锁解决竞态问题。引用计数发生变化的场景主要是：

kalloc时，设置为1即可。
kfree时，如果计数减1后还大于0，就return，否则释放掉。
fork时copy页表，此时需要引用+1。
cow page fault时拷贝一页，对原页引用减1。

//物理地址转页号
#define PA2PANUM(pa) (((pa)-KERNBASE)>>PGSHIFT)
#define PA2REF(pa) kcounter.refcount[PA2PANUM((uint64)(pa))]
struct {
  struct spinlock lock;
  //物理页的引用计数
  int refcount[(PHYSTOP-KERNBASE)>>PGSHIFT];
}kcounter;

void freerange(void *pa_start, void *pa_end);

extern char end[]; // first address after kernel.
                   // defined by kernel.ld.

struct run {
  struct run *next;
};

struct {
  struct spinlock lock;
  struct run *freelist;
} kmem;

//对引用+1并返回值
int paref(uint64 pa){
  if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
    panic("paref");
  acquire(&kcounter.lock);
  int count=++PA2REF(pa);
  release(&kcounter.lock);
  return count;
}

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

  initlock(&kcounter.lock, "kcounter");
  for(int i=0;i< (PHYSTOP-KERNBASE)>>PGSHIFT;i++){
    kcounter.refcount[i]=0;
  } 
}

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);
}

// Free the page of physical memory pointed at by v,
// which normally should have been returned by a
// call to kalloc().  (The exception is when
// initializing the allocator; see kinit above.)
void
kfree(void *pa)
{
  struct run *r;

  if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
    panic("kfree"); 
  //还有其他引用，不能释放
  acquire(&kcounter.lock);
  if(--PA2REF((uint64)pa)>0){
    release(&kcounter.lock);
    return;
  }
  //避免小于0
  PA2REF((uint64)pa)=0;
  release(&kcounter.lock);
  // 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);
}

// Allocate one 4096-byte page of physical memory.
// Returns a pointer that the kernel can use.
// Returns 0 if the memory cannot be allocated.
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
    //重置
    PA2REF((uint64)r)=1;
  }
 
  return (void*)r;
}
//复制pa物理页，并返回新页地址
//如果pa的引用为1，则直接返回pa，
//用于copy on write
void *kcopy_and_unref(uint64 pa){
  if((pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
    panic("kcopy_and_unref");

  uint64 newpa=0;
  acquire(&kcounter.lock);
  //如果引用为1了，那就不用拷贝了，直接用这页即可
  if(PA2REF(pa)<=1){
      release(&kcounter.lock);
      return (void*)pa;
  }
  if((newpa=(uint64)kalloc())==0){
    release(&kcounter.lock);
    return 0;
  }
  memmove((void*)newpa,(void*)pa,PGSIZE);
  //将原pa引用减1
  PA2REF(pa)--;
  release(&kcounter.lock);
  return (void*)newpa;
}

针对上述情况，改变引用计数只能通过kalloc、kfree、paref、kcopy_and_unref这四种方式，不能直接操纵kcounter。

2 拷贝页表

fork时会拷贝页表，其实页表是独立的，只是最底层页表项指向的数据页是共享的。

int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
  // printf("uvmcopy...\n");
  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");
      continue; //lazy allocate
    if((*pte & PTE_V) == 0)
      // panic("uvmcopy: page not present");
      continue; //lazy allocate
    pa = PTE2PA(*pte);
    //清除写标志、设置cow
    *pte=(*pte&~PTE_W) | PTE_COW; 
    flags = PTE_FLAGS(*pte);
    //增加引用
    paref(pa);
    // printf("uvmcopy va: %p pa: %p perm: %d\n",i,pa,flags);
    if(mappages(new, i, PGSIZE, (uint64)pa, flags) != 0){
      goto err;
    }
    
  }
  // printf("uvmcopy success, newpg: %p, sz: %d\n",new,sz);
  return 0;

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

3 cow page fault

void
usertrap(void)
{
  int which_dev = 0;
  //...
  int scause;
  if((scause=r_scause()) == 8){
    //...
  } else if((which_dev = devintr()) != 0){
    // ok
  } else if(scause==13 || scause==15){
    uint64 va=r_stval();
    // printf("page fault, scause: %d, pid: %d, va: %p\n",scause,p->pid,va);
    if (va>=MAXVA || (va<=PGROUNDDOWN(p->trapframe->sp)&&va>=PGROUNDDOWN(p->trapframe->sp)-PGSIZE) ){
      p->killed=-1;
    }else if(uvmtrapcopy(p->pagetable,va,p->sz)<0){
      p->killed=1;
    }
  }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();
}


int uvmtrapcopy(pagetable_t pagetable,uint64 va,uint64 sz){
    va=PGROUNDDOWN(va);
    pte_t *pte=walk(pagetable,va,0);
    // printf("uvmtrapcopy va: %p, pte: %p, flag: %d\n",va,*pte,PTE_FLAGS(*pte));
    if(pte!=0 &&(*pte &PTE_V) &&(*pte&PTE_COW)){
      return uvmcowcopy(pagetable,pte,va);
    }
    // }else if(pte!=0 && va<sz && (*pte&PTE_V)==0){
    //   return uvmsbrkalloc(pagetable,pte,va);
    // }
    return -1;
}


int uvmcowcopy(pagetable_t pagetable,pte_t * pte,uint64 va){
    uint64 oldpa=PTE2PA(*pte);
    if(oldpa==0){
      return -1;
    }
    uint64 newpa;
    if((newpa=(uint64)kcopy_and_unref(oldpa))==0){
      // vmprint(pagetable);
      return -1;
    }
    // printf("kcopy_and_unref newpa: %p\n",newpa);
    //去除页表项，并减少物理页的引用
    *pte=*pte|PTE_W;
    *pte=*pte&~PTE_COW;
    uint64 flag=PTE_FLAGS(*pte);
    *pte=PA2PTE((uint64)newpa) | flag;
    return 0;
}

4 copyout

从内核空间将数据写入到用户空间地址，copyout是直接操作物理地址进行的，没有经过用户页表，这一步也要考虑copy on write问题。

int
copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len)
{
  uint64 n, va0, pa0;
  uint64 mem;
  while(len > 0){
    va0 = PGROUNDDOWN(dstva);
    pa0 = walkaddr(pagetable, va0);
    if(pa0 == 0)
      return -1;
    pte_t *pte=walk(pagetable,va0,0);
    if(pte==0){
      return -1;
    }
    //复制一个新页，然后进行写入操作
    if(*pte&PTE_COW){
      mem=(uint64)kcopy_and_unref(pa0);
        *pte=*pte|PTE_W | PTE_R | PTE_U;
        *pte=*pte&~PTE_COW;
        uint64 flag=PTE_FLAGS(*pte);
        *pte=PA2PTE((uint64)mem) | flag;
        pa0=(uint64)mem;
    }
    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;
}