Lab6: Copy-on-Write Fork for xv6

原文地址：YSBLOG
参考资料：MIT 6.s081 xv6-lab6-cow - 知乎 (zhihu.com)

实验背景：

​ 在原本的xv6中，当Shell处理指令时，会通过fork创建一个子进程，该子进程包含一个完整的Shell拷贝，在该子进程中调用exec执行对应的指令程序，而在exec中第一件事就是丢去fork拷贝的Shell地址空间，取而代之的是对应指令的地址空间。在这个过程中，Shell拷贝后就被丢弃，降低了程序执行的效率。

实验目的：

​ 结合上述背景，在本次实验中需要实现cow（copy-on-write），当创建子进程时，并不实际对父进程进行拷贝，而是将页表项改为只读，在父/子进程第一次对页面进行写操作时才进行内存的拷贝，从而节约实际使用内存空间。

​ 根据提示，首先我们将PTE标志位的第八位设置为PTE_COW用于标识该页表项对应的页面是否是cow页面。

// riscv.h
#define PTE_COW (1L << 8) // cow page

​ 我们引入cow后，当父进程退出后，我们并不能直接释放父进程的内存，因为这时子进程可能也指向了该内存页面（该页面还没有触发page fault，并没有实际进行拷贝），若释放后子进程就无法访问该页面内存了。所以我们需要对每个页面增加一个引用计数，当进程退出时，若该页面的引用计数为0才释放内存。

// kalloc.c// 用于访问物理页引用计数数组
#define PA2PGREF_ID(p) (((p)-KERNBASE)/PGSIZE)
#define PGREF_MAX_ENTRIES PA2PGREF_ID(PHYSTOP)// 定义单个页面结构
struct page_ref{struct spinlock lock; // 每个页面一个锁int cnt; // 引用计数
};
struct page_ref page_ref_list[PGREF_MAX_ENTRIES]; // 引用计数数组void
kinit()
{// 初始化每个页面引用计数的锁for (int i = 0; i < PGREF_MAX_ENTRIES; ++i) {initlock(&(page_ref_list[i].lock), "kpage_ref");page_ref_list[i].cnt = 1; // 页面引用计数初始值为1}initlock(&kmem.lock, "kmem");freerange(end, (void*)PHYSTOP);
}// 当页面引用计数为0时才释放内存
void
kfree(void *pa)
{struct run *r;if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)panic("kfree");// 获取页面锁acquire(&((page_ref_list[PA2PGREF_ID((uint64)pa)].lock)));// 该页面引用计数减一page_ref_list[PA2PGREF_ID((uint64)pa)].cnt--;if (page_ref_list[PA2PGREF_ID((uint64)pa)].cnt > 0) {// 还有进程在引用该页面，不释放内存，直接返回// 释放锁release(&((page_ref_list[PA2PGREF_ID((uint64)pa)].lock)));return;}release(&((page_ref_list[PA2PGREF_ID((uint64)pa)].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);
}// 分配物理内存时初始化引用计数为1
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// 获取页面锁acquire(&((page_ref_list[PA2PGREF_ID((uint64)r)].lock)));page_ref_list[PA2PGREF_ID((uint64)r)].cnt = 1; // 新页面的引用计数为1// 释放锁release(&((page_ref_list[PA2PGREF_ID((uint64)r)].lock)));}return (void*)r;
}// 引用页面，为 pa 的引用计数增加 1
int krefpage(uint64 pa) {if(pa % PGSIZE != 0 // pa位于guard page上 || (char*)pa < end // pa位于内核代码区域|| pa >= PHYSTOP) // pa超过最大内存区域{ return -1;}acquire(&((page_ref_list[PA2PGREF_ID(pa)].lock)));page_ref_list[PA2PGREF_ID(pa)].cnt++; // 引用计数加一release(&((page_ref_list[PA2PGREF_ID(pa)].lock)));return 1;
}

// defs.h
int             krefpaga(uint64 pa);

与lab5相同，引入cow页面后，系统触发的缺页中断的情况需要特殊处理，当检测到是由于cow机制触发的缺页中断后，我们需要对cow页面进行实际的物理内存分配和映射，所以添加cow_check用于检测是否是cow页面，cow_copy用于执行对cow页面的实际物理内存分配以及映射。

// kalloc.c
// 发生缺页中断时，用于检测该页面地址是否是cow页面
int cow_check(pagetable_t pagetable, uint64 va) {if (va > MAXVA) {return 0;}pte_t *pte = walk(pagetable, va, 0);if (pte == 0) {return 0;}if (( (*pte) & PTE_V) == 0) {return 0;}return ((*pte) & (PTE_COW));
}// 当触发缺cow页触发缺页中断时进行实际物理内存分配和映射
uint64
cow_copy(pagetable_t pagetable, uint64 va) {va = PGROUNDDOWN(va); // 获得当前页面起始位置pte_t *pte = walk(pagetable, va, 0);uint64 pa = PTE2PA(*pte);// 获取当前页面锁acquire(&((page_ref_list[PA2PGREF_ID(pa)].lock)));if (page_ref_list[PA2PGREF_ID(pa)].cnt == 1) {// 当前页面只有一个进程在使用时，直接返回该页面// 恢复该页面权限*pte = (*pte) & (~PTE_COW);*pte = (*pte) | (PTE_W);// 释放锁release(&((page_ref_list[PA2PGREF_ID(pa)].lock)));return pa;}// 一定要释放锁，在kalloc中会申请锁，会导致死锁release(&((page_ref_list[PA2PGREF_ID(pa)].lock)));// 分配新的内存页面uint64 newpa = (uint64)kalloc();if (newpa == 0) {// 内存分配失败 return 0;}// 复制旧页面内容到新页面memmove((void*)newpa, (void*)pa, PGSIZE);*pte = (*pte) & (~PTE_V); // 清楚页面PTE_V标志，防止remap uint64 flag = PTE_FLAGS(*pte);flag = flag | PTE_W;flag = flag & (~PTE_COW);// 将申请的物理地址隐射到对应的虚拟地址上if(mappages(pagetable, va, PGSIZE, (uint64)newpa, flag) != 0) {kfree((void*)newpa);return 0;}// 尝试清除原始的cow副本，此时引用计数可能为0kfree((void*)PGROUNDDOWN(pa));return (uint64)newpa;
}

// defs.h
uint64 cow_copy(pagetable_t pagetable, uint64 va);
int cow_check(pagetable_t pagetable, uint64 va);

​ 与lab5同样的方式，修改陷入中断的处理。

// trap.c
void
usertrap(void)
{... ...} else if((which_dev = devintr()) != 0){// ok} else if (r_scause() == 13 || r_scause() == 15) {// 出现缺页异常uint64 va = r_stval();if (cow_check(p->pagetable, va)) {// 异常为cow页面if (cow_copy(p->pagetable, va) == 0) {p->killed = 1;}} else {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;}... ...
}

​ 最后需要修改copyout，当拷贝页面为cow页面时，调用cow_copy。

// vm.c
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);if (cow_check(pagetable, va0) != 0) {// 若拷贝页面为cow页面，执行cow拷贝pa0 = cow_copy(pagetable, va0);} 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;
}

​ 最后使用cowtest和usertests完成测试。

init: starting sh
$ usertests
usertests starting
test execout: OK
test copyin: OK
test copyout: OK
test copyinstr1: OK
test copyinstr2: OK
test copyinstr3: OK
test rwsbrk: OK
test truncate1: OK
test truncate2: OK
test truncate3: OK
test reparent2: OK
test pgbug: OK
test sbrkbugs: usertrap(): unexpected scause 0x000000000000000c pid=3235sepc=0x000000000000555e stval=0x000000000000555e
usertrap(): unexpected scause 0x000000000000000c pid=3236sepc=0x000000000000555e stval=0x000000000000555e
OK
test badarg: OK
test reparent: OK
test twochildren: OK
test forkfork: OK
test forkforkfork: OK
test argptest: OK
test createdelete: OK
test linkunlink: OK
test linktest: OK
test unlinkread: OK
test concreate: OK
test subdir: OK
test fourfiles: OK
test sharedfd: OK
test dirtest: OK
test exectest: OK
test bigargtest: OK
test bigwrite: OK
test bsstest: OK
test sbrkbasic: OK
test sbrkmuch: OK
test kernmem: OK
test sbrkfail: OK
test sbrkarg: OK
test validatetest: OK
test stacktest: OK
test opentest: OK
test writetest: OK
test writebig: OK
test createtest: OK
test openiput: OK
test exitiput: OK
test iput: OK
test mem: OK
test pipe1: OK
test preempt: kill... wait... OK
test exitwait: OK
test rmdot: OK
test fourteen: OK
test bigfile: OK
test dirfile: OK
test iref: OK
test forktest: OK
test bigdir: OK
ALL TESTS PASSED
$ cowtest 
simple: ok
simple: ok
three: ok
three: ok
three: ok
file: ok
ALL COW TESTS PASSED