本文记录了 Lab: Copy-on-Write Fork for xv6 的实验过程

Lab: Copy-on-Write Fork for xv6

为 xv6 实现 Copy-on-Write Fork 功能

git fetch
checkout cow
make clean

根据实验的提示

• 在 kernel/kalloc.c 文件中用一个数组跟踪每个空闲页的引用计数。在 kalloc() 函数中设置分配页面的引用计数为 1，然后在 fork() -> uvmcopy() 中，当子进程引用了某个页面，这个页面的引用计数加 1；在 kfree 函数中，先对这页的引用计数减 1，当减为 0 时，说明这页应该被释放。

• 在 kernel/vm.c 中，将 uvmcopy 函数中分配内存相关代码放到我们定义的函数 copyonwrite 中，实现当进程想对一个 COW 页进行写操作时，会触发 page fault，然后在 usertrap 中调用 copyonwrite 函数来分配一个新的物理页。copyonwrite 函数会检查虚拟地址 va 是否大于 MAXVA、它所在的页的 PTE_U 是否为 1（因为不允许访问内核的物理页面）、这个页面是否是 COW 页。然后才分配内存

• 在 copyout 函数中，对于虚拟地址 va0，我们需要像处理 COW page fault 来处理 va0，然后再继续下面的代码。

• 去掉 mappages 函数中的 panic("remap");

需要更新的文件

1. kernel/defs.h
2. kernel/riscv.h
3. kernel/kalloc.c
4. kernel/trap.c
5. kernel/vm.c

Diff

diff --git a/kernel/defs.h b/kernel/defs.h
index 4b9bbc0..76060bb 100644
--- a/kernel/defs.h
+++ b/kernel/defs.h
@@ -63,6 +63,7 @@ void            ramdiskrw(struct buf*);
 void*           kalloc(void);
 void            kfree(void *);
 void            kinit(void);
+void            increfcount(uint64);
 
 // log.c
 void            initlog(int, struct superblock*);
@@ -171,6 +172,7 @@ uint64          walkaddr(pagetable_t, uint64);
 int             copyout(pagetable_t, uint64, char *, uint64);
 int             copyin(pagetable_t, char *, uint64, uint64);
 int             copyinstr(pagetable_t, char *, uint64, uint64);
+int             copyonwrite(pagetable_t, uint64);
 
 // plic.c
 void            plicinit(void);
diff --git a/kernel/kalloc.c b/kernel/kalloc.c
index fa6a0ac..39c84eb 100644
--- a/kernel/kalloc.c
+++ b/kernel/kalloc.c
@@ -13,6 +13,7 @@ void freerange(void *pa_start, void *pa_end);
 
 extern char end[]; // first address after kernel.
                    // defined by kernel.ld.
+int refcount[(PHYSTOP - KERNBASE) / PGSIZE]; // reference count
 
 struct run {
   struct run *next;
@@ -50,7 +51,11 @@ kfree(void *pa)
 
   if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
     panic("kfree");
-
+  // minus reference count, if it equal 0, then we should free this page
+  if(--refcount[((uint64)pa - KERNBASE) / PGSIZE] > 0){ 
+    return;
+  }
+  refcount[((uint64)pa - KERNBASE) / PGSIZE] = 0;
   // Fill with junk to catch dangling refs.
   memset(pa, 1, PGSIZE);
 
@@ -78,5 +83,11 @@ kalloc(void)
 
   if(r)
     memset((char*)r, 5, PGSIZE); // fill with junk
+  if(r)
+    refcount[((uint64)r - KERNBASE) / PGSIZE] = 1;
   return (void*)r;
 }
+void increfcount(uint64 pa)
+{
+  refcount[(pa - KERNBASE) / PGSIZE]++;
+}
\ No newline at end of file
diff --git a/kernel/riscv.h b/kernel/riscv.h
index 0aec003..25e253d 100644
--- a/kernel/riscv.h
+++ b/kernel/riscv.h
@@ -331,6 +331,7 @@ sfence_vma()
 #define PTE_W (1L << 2)
 #define PTE_X (1L << 3)
 #define PTE_U (1L << 4) // 1 -> user can access
+#define PTE_COW (1L << 8) // the page is COW
 
 // shift a physical address to the right place for a PTE.
 #define PA2PTE(pa) ((((uint64)pa) >> 12) << 10)
diff --git a/kernel/trap.c b/kernel/trap.c
index a63249e..5d06c78 100644
--- a/kernel/trap.c
+++ b/kernel/trap.c
@@ -67,6 +67,12 @@ usertrap(void)
     syscall();
   } else if((which_dev = devintr()) != 0){
     // ok
+  } else if (r_scause() == 13 || r_scause() == 15){
+    // page faults, then call Copy-on-Write handler it.
+    uint64 va = r_stval();
+    if(copyonwrite(myproc()->pagetable, va) == -1){
+      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());
diff --git a/kernel/vm.c b/kernel/vm.c
index bccb405..07e3412 100644
--- a/kernel/vm.c
+++ b/kernel/vm.c
@@ -157,7 +157,7 @@ mappages(pagetable_t pagetable, uint64 va, uint64 size, uint64 pa, int perm)
     if((pte = walk(pagetable, a, 1)) == 0)
       return -1;
     if(*pte & PTE_V)
-      panic("remap");
+      ;
     *pte = PA2PTE(pa) | perm | PTE_V;
     if(a == last)
       break;
@@ -311,7 +311,7 @@ uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
   pte_t *pte;
   uint64 pa, i;
   uint flags;
-  char *mem;
 
   for(i = 0; i < sz; i += PGSIZE){
     if((pte = walk(old, i, 0)) == 0)
@@ -319,14 +319,14 @@ uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
     if((*pte & PTE_V) == 0)
       panic("uvmcopy: page not present");
     pa = PTE2PA(*pte);
+    *pte = (*pte & (~PTE_W)) | PTE_COW; // clear PTE_W and set COW
     flags = PTE_FLAGS(*pte);
-    if((mem = kalloc()) == 0)
-      goto err;
-    memmove(mem, (char*)pa, PGSIZE);
-    if(mappages(new, i, PGSIZE, (uint64)mem, flags) != 0){
-      kfree(mem);
+    // map the parent's physical pages into the child, instead of allocating new pages
+    if(mappages(new, i, PGSIZE, pa, flags) != 0){
       goto err;
     }
+    increfcount(pa); // the physical page reference count plus 1
   }
   return 0;
 
@@ -358,6 +358,11 @@ copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len)
 
   while(len > 0){
     va0 = PGROUNDDOWN(dstva);
+    // weather va0 is a COW VA? If not, then we do nothing
+    // otherwish, we execute COW, then map va0 to a new physical page.
+    if(copyonwrite(pagetable, va0) == -1){
+      return -1;
+    }
     pa0 = walkaddr(pagetable, va0);
     if(pa0 == 0)
       return -1;
@@ -440,3 +445,30 @@ copyinstr(pagetable_t pagetable, char *dst, uint64 srcva, uint64 max)
     return -1;
   }
 }
+int
+copyonwrite(pagetable_t pagetable, uint64 va)
+{
+  if(va >= MAXVA)
+    return -1;
+  va = PGROUNDDOWN(va);
+  pte_t *pte = walk(pagetable, va, 0);
+  if(pte == 0 || (*pte & PTE_V) == 0 || (*pte & PTE_U) == 0)
+    return -1;
+  if((*pte & PTE_COW) == 0) // not a COW page
+    return 0;
+
+  uint64 pa = PTE2PA(*pte);
+
+  char *mem = kalloc();
+  if(mem == 0){ // no free physical memory, kill the process
+    return -1;
+  }
+  memmove(mem, (char*)pa, PGSIZE);
+  kfree((void*)pa); // reference count minus 1
+  uint64 flags = PTE_FLAGS(*pte) & (~PTE_COW);
+  if(mappages(pagetable, va, PGSIZE, (uint64)mem, flags | PTE_W) != 0){
+    kfree(mem);
+    return 0;
+  }
+  return (uint64)mem;
+}

测试

make qemu
cowtest
usertests

make grade