代码在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就是要对页面进行重新映射的。