2020 MIT6.s081 Lab: Copy-on-Write Fork for xv6

---

实验链接

https://pdos.csail.mit.edu/6.S081/2020/labs/cow.html

---

实验

Implement copy-on-write

需要注意的点：

1. fork子进程时，并不实际分配物理内存，只是将对应的虚拟内存map至父进程对应的物理内存，只有子进程需要修改物理内存时，才真正进行物理页的分配。
2. 用变量记录每个物理页实际的引用计数，只有在引用计数为0时，才能将该物理页彻底释放。

具体代码如下：

1. 在文件kernel/defs.h文件中，增加如下内容

   void            decrease_cnt(uint64);
   void            increase_cnt(uint64);
   long            get_ref_cnt(uint64);
   
   pte_t *         walk(pagetable_t, uint64, int);
   int             cownewpage(pagetable_t, uint64);
   
   1
   2
   3
   4
   5
   6
   7

2. 在文件kernel/memlayout.h文件中，增加如下内容：

       
       // 用数组记录每个物理页对应的引用计数，以下为该数组的大小
       #define ARR_MAX ((PHYSTOP - KERNBASE) >> 12)
       // 物理内存对应的数组下标
       #define ARR_INDEX(pa) ((((uint64)pa) - KERNBASE) >> 12)
       
   1
   2
   3
   4
   5
   6

3. 文件kernel/kalloc.c，修改如下内容：

   
   long pa_ref_cnt[ARR_MAX];    
   
   void
   kinit()
   {
     initlock(&kmem.lock, "kmem");
     for (int i = 0; i < ARR_MAX; i++) {
       // 主要为freerange做准备  
       pa_ref_cnt[i] = 1;
     }
     freerange(end, (void*)PHYSTOP);
   //  printf("total physical page: %d\n", ARR_MAX);
   //  printf("begin: %p\n", end);
   //  for (int i = 0; i < ARR_MAX; i++) {
   //    if (pa_ref_cnt[i] != 0) {
   //      printf("%d: %d\n", i, pa_ref_cnt[i]);
   //    }
   //  }
   } 
   
   
   
   void
   kfree(void *pa)
   {
     struct run *r;
   
     if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
       panic("kfree");
   
     acquire(&kmem.lock);
     pa_ref_cnt[ARR_INDEX((uint64)pa)]--;
     if (pa_ref_cnt[ARR_INDEX((uint64)pa)] > 0) {
       release(&kmem.lock);
       return;
     }
     release(&kmem.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);
   }
   void *
   kalloc(void)
   {
     struct run *r;
   
     acquire(&kmem.lock);
     r = kmem.freelist;
     if(r) {
       kmem.freelist = r->next;
       pa_ref_cnt[ARR_INDEX((uint64)r)] = 1;
     }
     release(&kmem.lock);
   
     if(r)
       memset((char*)r, 5, PGSIZE); // fill with junk
     return (void*)r;
   }
   
   void
   decrease_cnt(uint64 pa)
   {
     acquire(&kmem.lock);
     pa_ref_cnt[ARR_INDEX(pa)]--;
     release(&kmem.lock);
   }
   
   void
   increase_cnt(uint64 pa)
   {
     acquire(&kmem.lock);
     pa_ref_cnt[ARR_INDEX(pa)]++;
     release(&kmem.lock);
   }
   
   long
   get_ref_cnt(uint64 pa)
   {
     return pa_ref_cnt[ARR_INDEX(pa)];
   }
   
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21
   22
   23
   24
   25
   26
   27
   28
   29
   30
   31
   32
   33
   34
   35
   36
   37
   38
   39
   40
   41
   42
   43
   44
   45
   46
   47
   48
   49
   50
   51
   52
   53
   54
   55
   56
   57
   58
   59
   60
   61
   62
   63
   64
   65
   66
   67
   68
   69
   70
   71
   72
   73
   74
   75
   76
   77
   78
   79
   80
   81
   82
   83
   84
   85
   86
   87
   88

4. 在文件kernel/riscv.h文件中，增加如下内容：

   //flag的第8位为保留位，我们可以根据需要设置不同的标志
   // 这里通过设置第8位为1表示该物理页是一个cow页，为0表示为正常的页
   #define PTE_RSW (1L << 8)
   1
   2
   3

5. 在文件kernel/vm.c中，修改如下：

   // 新增函数walkpte
   pte_t*
   walkpte(pagetable_t pagetable, uint64 va)
   {
     pte_t *pte;
   
     if(va >= MAXVA)
       return 0;
   
     pte = walk(pagetable, va, 0);
     if(pte == 0)
       return 0;
     if((*pte & PTE_V) == 0)
       return 0;
     if((*pte & PTE_U) == 0)
       return 0;
     return pte;
   }
   
   // 修改函数uvmunmap
   void
   uvmunmap(pagetable_t pagetable, uint64 va, uint64 npages, int do_free)
   {
     uint64 a;
     pte_t *pte;
   
     if((va % PGSIZE) != 0)
       panic("uvmunmap: not aligned");
   
     for(a = va; a < va + npages*PGSIZE; a += PGSIZE){
       if((pte = walk(pagetable, a, 0)) == 0)
         panic("uvmunmap: walk");
       if((*pte & PTE_V) == 0)
         panic("uvmunmap: not mapped");
       if(PTE_FLAGS(*pte) == PTE_V)
         panic("uvmunmap: not a leaf");
       //++++begin++++  
       if(do_free) {
         uint64 pa = PTE2PA(*pte);
         kfree((void *) pa);
       }
       else {
         decrease_cnt(PTE2PA(*pte));
       }
       //+++++end++++++
       *pte = 0;
     }
   }
   // 修改uvmcopy函数为如下内容：
   // 子进程不申请物理页，而是与父进程共享物理页
   int
   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)
         panic("uvmcopy: pte should exist");
       if((*pte & PTE_V) == 0)
         panic("uvmcopy: page not present");
       pa = PTE2PA(*pte);
       // 将写标志位设置为0
       *pte = (*pte) & (~PTE_W);
       *pte = (*pte) | PTE_RSW;
       flags = PTE_FLAGS(*pte);
   //    if((mem = kalloc()) == 0)
   //      goto err;
   //    memmove(mem, (char*)pa, PGSIZE);
       if(mappages(new, i, PGSIZE, (uint64)pa, flags) != 0){
   //      kfree(mem);
         goto err;
       }
       increase_cnt(pa);
     }
     return 0;
   
    err:
     uvmunmap(new, 0, i / PGSIZE, 1); // TODO
     return -1;
   }
   
   // 新增如下函数
   // 该函数的主要作用是，在父进程或者子进程向cow页写东西时，
   // 为进程新分配物理页，即物理页的申请是在此时才真正执行，而不是
   // fork时申请的
   int
   cownewpage(pagetable_t pagetable, uint64 va)
   {
   //  printf("loop\n");
     va = PGROUNDDOWN(va);
     pte_t* pte = walk(pagetable, va, 0);
     if (0 == pte) {
   //    printf("pte should exist\n");
       return -1;
     }
   
     if ((*pte & PTE_RSW) == 0) {
       return -1;
     }
   
     if ((*pte & PTE_V) == 0) {
   //    printf("pte should valid\n");
       return -1;
     }
   
     uint64 pa = PTE2PA(*pte);
     if (get_ref_cnt(pa) == 1) { // only children or only parent
       *pte = *pte | PTE_W;
       *pte = *pte & (~PTE_RSW);
       return 0;
     }
   
     char* mem = kalloc();
     if (0 == mem) {
   //    printf("out of memory\n");
       return -1;
     }
   
   //  decrease_cnt((uint64)pa);
     memmove(mem, (void*)pa, PGSIZE);
     kfree((void*)pa);
     uint64 flag = (PTE_FLAGS(*pte) | (PTE_W)) & (~PTE_RSW);
     *pte = PA2PTE((uint64)mem) | flag;
     return 0;
   }
   
   // 修改copyout函数，在发现cow时新申请物理页
   // 这个函数是由内核调用的，内核不会调用usertrap函数，因此这里需要单独处理。
   // 为什么只需要修改copyout而不需要修改copyin呢?
   // 因为copyout是内核向用户空间写数据，会涉及cow
   // 而copyin是内核向用户空间读数据，因此不会涉及cow
   int
   copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len)
   {
     uint64 n, va0, pa0;
     pte_t* pte;
   
     while(len > 0){
       va0 = PGROUNDDOWN(dstva);
       pte = walkpte(pagetable, va0);
       if (0 == pte) {
         return -1;
       }
       if ((*pte & PTE_RSW)) {
         if (cownewpage(pagetable, va0) < 0) {
           printf("copyout: cow failed\n");
           return -1;
         } else {
           pte = walkpte(pagetable, va0);
         }
       }
       pa0 = PTE2PA(*pte);
       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;
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21
   22
   23
   24
   25
   26
   27
   28
   29
   30
   31
   32
   33
   34
   35
   36
   37
   38
   39
   40
   41
   42
   43
   44
   45
   46
   47
   48
   49
   50
   51
   52
   53
   54
   55
   56
   57
   58
   59
   60
   61
   62
   63
   64
   65
   66
   67
   68
   69
   70
   71
   72
   73
   74
   75
   76
   77
   78
   79
   80
   81
   82
   83
   84
   85
   86
   87
   88
   89
   90
   91
   92
   93
   94
   95
   96
   97
   98
   99
   100
   101
   102
   103
   104
   105
   106
   107
   108
   109
   110
   111
   112
   113
   114
   115
   116
   117
   118
   119
   120
   121
   122
   123
   124
   125
   126
   127
   128
   129
   130
   131
   132
   133
   134
   135
   136
   137
   138
   139
   140
   141
   142
   143
   144
   145
   146
   147
   148
   149
   150
   151
   152
   153
   154
   155
   156
   157
   158
   159
   160
   161
   162
   163
   164
   165
   166

6. 修改kernel/trap.c为如下内容：

   // 在函数usertrap中，增加如下中断处理分支
   // 即遇到cow页时，重新申请新的物理页
   } else if (r_scause() == 13 || r_scause() == 15) { // page fault
       uint64 va = r_stval();
   
       if (cownewpage(p->pagetable, va) < 0) {
         p->killed = 1;
   //      printf("usertrap(): cow failed\n");
       }
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10

7. 测试结果：

   

   
   

   

8. 执行make grade

   

---

提交结果

$ git commit -m "lab copy on write"
$ make handin
1
2

---

查看结果

登录网站https://6828.scripts.mit.edu/2020/handin.py/student，可以看到提交的结果。

---

常用命令

1. ctrl + a c，进入qemu的console页面；
   1. 在console页面，输入info mem，可以打印当前的page table。

---

Github

https://github.com/aerfalwl/mit-xv6-labs-2020.git