MIT6.S081 lab6 Copy-on-Write Fork

There is a saying in computer systems that any systems problem can be solved with a level of indirection.

任何计算机系统的问题都可以通过增加一个中间层解决。

COW的思想就是fork时child的PTE指向parent的Physical Page，这样一个PP两个进程共同使用。等到真正要使用时，再拷贝一份出来，避免冲突。需要注意，fork可能在fork，于是一份物理页面可能不止两个进程共享，于是我们需要为每个物理页面额外维护一个引用计数。

S1 引用计数的设计

直接用一个大数组，将物理页的页号当作索引，计算使用次数。

struct memcnt{
    struct spinlock lock;
    int cnt;
};
struct memcnt p_cnt[PHYSTOP/PGSIZE];
void increase_cnt(uint64 pa){
    int pn = PA2PN(pa);
    acquire(&p_cnt[pn].lock);
    p_cnt[pn].cnt += 1;
    release(&p_cnt[pn].lock);
}
void set_cnt(uint64 pa){
    int pn = PA2PN(pa);
    acquire(&p_cnt[pn].lock);
    p_cnt[pn].cnt = 1;
    release(&p_cnt[pn].lock);
}

这里为什么要加锁？我也是看了其他人的博客才知道，应该是有冲突的场景。

然后第一次分配页面时，引用计数初始化为1，归还页面时只减少引用计数，只有引用计数为0时才真正归还页面。

void kinit(){
  for(int i=0; i<PHYSTOP/4096;++i){
      initlock(&p_cnt[i].lock, "memref");
      p_cnt[i].cnt=0;
  }
  initlock(&kmem.lock, "kmem");
  freerange(end, (void*)PHYSTOP);
}
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
      set_cnt((uint64)r);
  }
  return (void*)r;
}
void kfree(void *pa){
  struct run *r;

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

  int pn = PA2PN((uint64)pa);
  // attentino here
  acquire(&p_cnt[pn].lock); 
  p_cnt[pn].cnt -= 1;
  if(p_cnt[pn].cnt>0){
      release(&p_cnt[pn].lock);
      return;
  }
  release(&p_cnt[pn].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);

}

S2 修改fork时的行为

fork不再单独拿出一个新物理页，而是指向parent的pa。注意要修改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");
    pa = PTE2PA(*pte);
    *pte = (*pte & ~PTE_W) | PTE_COW;
    flags = PTE_FLAGS(*pte);
    if(mappages(new, i, PGSIZE, pa, flags) != 0){
      goto err;
    }
    increase_cnt(pa);
  }
  return 0;

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

S3 应对PageFault

首先要检查出错的va的合法性，然后要检查cow标识位，再就是分配新物理页，复制内容，然后替换原来的pte。这里有一点需要注意，减少引用计数时用的是kfree函数。

void usertrap(void){
  	...
  	else if (r_scause()==13 || r_scause() ==15){
      uint64 va = r_stval();
      pte_t *pte;
      uint64 pa;
      do{
          if (va >= MAXVA || va >p->sz){
              p->killed = 1;
              break;
          }
          if((pte = walk(p->pagetable, va, 0))==0){
              p->killed = 1;
              break;
          }
          // only cope with cow page fault
          if((*pte & PTE_COW) == 0){
              p->killed = 1;
              break;
          }
          pa = PTE2PA(*pte);
          // alloc a new physical page
          char* pg;
          if((pg = kalloc()) == 0){
              p->killed = 1;
              break;
          }
          // copy content from old page to new page
          memmove(pg, (char*)pa, PGSIZE);
          // change flags
          uint flags = PTE_FLAGS(*pte);
          flags = (flags & ~PTE_COW) | PTE_W;
          // replace PTE with new pa
          *pte = PA2PTE(pg) | flags;
          // decrease cnt
          kfree((void*)pa);
      } while (0);
  	}
   ....
}

其实这么设计还是有一个缺陷：当最后一个cow页的page fault时，它可以不用复制原来的物理页，而是直接复用这个页面，因为没有其他进程与它共享了。

S4 应对copyout

copyout的行为和中断处理几乎一样。

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

  while(len > 0){
    va0 = PGROUNDDOWN(dstva);
    if(va0 >= MAXVA)
        return -1;
    pte_t *pte;
    if((pte = walk(pagetable, va0, 0))==0){
        return -1;
    }
    if((*pte & PTE_V) == 0){
        return -1;
    }
    if((*pte & PTE_U) == 0){
        return -1;
    }
    // cow页则分配新页
    if((*pte & PTE_COW)){
        uint64 pa = PTE2PA(*pte);
        // alloc a new physical page
        char* pg;
        if((pg = kalloc()) == 0){
            return -1;
        }
        // copy content from old page to new page
        memmove(pg, (char*)pa, PGSIZE);
        // change flags
        uint flags = PTE_FLAGS(*pte);
        flags = (flags & ~PTE_COW) | PTE_W;
        // replace PTE with new pa
        *pte = PA2PTE(pg) | flags;
        // decrease cnt
        kfree((void*)pa);
    }
    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;
}

细节

cow标志位与计算页号的宏定义

#define PTE_COW (1L << 8) // copy on write

#define PA2PN(pa) (((uint64)pa) >> 12)