XV6學習（9）Lab cow: Copy-on-write fork
代碼在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就是要對頁面進行重新映射的。
