代码在github上。总体来说如果理解了COW机制的话,这个实验的完成也没有很复杂。
这一个实验是要完成COW(copy on write)fork。在原始的XV6中,fork函数是通过直接对进程的地址空间完整地复制一份来实现的。但是,拷贝整个地址空间是十分耗时的,并且在很多情况下,程序立即调用exec函数来替换掉地址空间,导致fork做了很多无用功。即使不调用exec函数,父进程和子进程的代码段等只读段也是可以共享的,从而达到节省内存空间的目的。同时COW也可以将地址空间拷贝的耗时进行延迟分散,提高操作系统的效率。
首先就是要对fork函数进行修改,使其不对地址空间进行拷贝。fork函数会调用uvmcopy进行拷贝,因此只需要修改uvmcopy函数就可以了:删去uvmcopy中的kalloc函数,将父子进程页面的页表项都设置为不可写,并设置COW标志位(在页表项中保留了2位给操作系统,这里用的是第8位#define PTE_COW (1L << 8))
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); flags = PTE_FLAGS(*pte); *pte = ((*pte) & (~PTE_W)) | PTE_COW; // set parent's page unwritable // printf("c: %p %p %p\n", i, ((flags & (~PTE_W)) | PTE_COW), *pte); // map child's page with page unwritable if(mappages(new, i, PGSIZE, (uint64)pa, (flags & (~PTE_W)) | PTE_COW) != 0){ goto err; } refcnt_incr(pa, 1); } return 0; err: uvmunmap(new, 0, i / PGSIZE, 1); return -1; }之后设置一个数组用于保存内存页面的引用计数,由于会涉及到并行的问题,因此也需要设置一个锁,同时定义了一些辅助函数:
struct { struct spinlock lock; uint counter[(PHYSTOP - KERNBASE) / PGSIZE]; } refcnt; inline uint64 pgindex(uint64 pa){ return (pa - KERNBASE) / PGSIZE; } inline void acquire_refcnt(){ acquire(&refcnt.lock); } inline void release_refcnt(){ release(&refcnt.lock); } void refcnt_setter(uint64 pa, int n){ refcnt.counter[pgindex((uint64)pa)] = n; } inline uint refcnt_getter(uint64 pa){ return refcnt.counter[pgindex(pa)]; } void refcnt_incr(uint64 pa, int n){ acquire(&refcnt.lock); refcnt.counter[pgindex(pa)] += n; release(&refcnt.lock); }修改kfree函数,使其只有在引用计数为1的时候释放页面,其他时候就只减少引用计数:
void kfree(void *pa) { struct run *r; // page with refcnt > 1 should not be freed acquire_refcnt(); if(refcnt.counter[pgindex((uint64)pa)] > 1){ refcnt.counter[pgindex((uint64)pa)] -= 1; release_refcnt(); return; } if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP) panic("kfree"); // Fill with junk to catch dangling refs. memset(pa, 1, PGSIZE); refcnt.counter[pgindex((uint64)pa)] = 0; release_refcnt(); r = (struct run*)pa; acquire(&kmem.lock); r->next = kmem.freelist; kmem.freelist = r; release(&kmem.lock); }修改kalloc函数,使其在分配页面时将引用计数也设置为1:这里注意要判断r是否为0,kalloc实现时没有当r==0时就返回。
void * kalloc(void) { ... if(r) memset((char*)r, 5, PGSIZE); // fill with junk if(r) refcnt_incr((uint64)r, 1); // set refcnt to 1 return (void*)r; }在usertrap中加入判断语句,这里只需要处理scause==15的情况,因为13是页面读错误,而COW是不会引起读错误的。
void usertrap(void) { ... } else if(r_scause() == 15){ // page write fault uint64 va = r_stval(); if(cowcopy(va) == -1){ p->killed = 1; } } else if((which_dev = devintr()) != 0){ ... }在cowcopy函数中先判断COW标志位,当该页面是COW页面时,就可以根据引用计数来进行处理。如果计数大于1,那么就需要通过kalloc申请一个新页面,然后拷贝内容,之后对该页面进行映射,映射的时候清除COW标志位,设置PTE_W标志位;而如果引用计数等于1,那么就不需要申请新页面,只需要对这个页面的标志位进行修改就可以了:
int cowcopy(uint64 va){ va = PGROUNDDOWN(va); pagetable_t p = myproc()->pagetable; pte_t* pte = walk(p, va, 0); uint64 pa = PTE2PA(*pte); uint flags = PTE_FLAGS(*pte); if(!(flags & PTE_COW)){ printf("not cow\n"); return -2; // not cow page } acquire_refcnt(); uint ref = refcnt_getter(pa); if(ref > 1){ // ref > 1, alloc a new page char* mem = kalloc_nolock(); if(mem == 0) goto bad; memmove(mem, (char*)pa, PGSIZE); if(mappages(p, va, PGSIZE, (uint64)mem, (flags & (~PTE_COW)) | PTE_W) != 0){ kfree(mem); goto bad; } refcnt_setter(pa, ref - 1); }else{ // ref = 1, use this page directly *pte = ((*pte) & (~PTE_COW)) | PTE_W; } release_refcnt(); return 0; bad: release_refcnt(); return -1; }在对引用计数进行读写时注意锁的设置。在mappages函数中会触发一个remap的panic,这里只要注释掉就行了,因为COW就是要对页面进行重新映射的。