copy-on-write

​ COW 在我看 深入理解计算机系统 这本书的时候就已经接触过了，可惜那时后理解不深，现在做完 VM 相关的 3 个 lab 后，算是彻彻底底明白了。其实理解后感觉很自然很简单。

​ Fork 可以创建出一个子进程，并与父进程有一致的内存映像。在之前的实现中，xv6 是通过 uvmcopy 为子进程分配物理内存并作映射，然后将对应的父进程中的内存映像 memmove 到子进程对应内存中。

​ 所以这里每次 Fork 的时候都是实实在在分配了物理内存的！所以这就引出了一个问题了？有必要实实在在得给子进程分配物理内存吗？

​ 我觉得，没必要！

​ 因为很多 Fork 后面接着是调用 exec 系统调用来装载新的可执行文件的 Section 进入内存中，那么在装载前，我们就需要先释放用户进程空间映射到的物理内存，这样一来，之前 fork 时分配的动作相当于做了无用功；

​ 除此之外，由于 text section 是存放代码的节，在 fork 后，父子进程是可以共享同的，这样还能节省物理内存。data section 也可以被用来共享，在发生写操作时才有必要为写的那个进程去分配物理页。

​ 由于我们不做物理内存的实际分配以及 memmove 而是仅仅建立了映射，整个的 Fork 的执行速度将会大大提升。

​ 在真正需要某一物理页的时候（写某一页物理页时）再分配也不迟呀！

COW 很好地利用了异常机制，在 Fork 中将父子进程对应用户空间的 PTEs 中的写权限位（PTE_W）置 0，这样任意进程在写 PTE 对应的物理页时都会发生一个页异常，紧接着我们只要在 usertrap 中添加一个由 写权限为0 导致的页异常处理逻辑即可！

由于现在一个物理页可能由多个进程进行共享，因此在进程结束释放资源的时候，需要查看它所释放的物理页是否有别的进程在引用。我们的实现方法是增加一个为每一个物理页设置一个 reference count 来表明有多少进程引用了这个物理页。

现在整理一下实现 lab 的思路：

  • 定义一个全局数组来记录物理页引用计数：
1
int rc[128*1024*1024 / PGSIZE]; // 由于 virtio 板子可用的最大物理内存是 128M，所以最多 128M / 4K 页

当一个物理页的 reference count = 0 时才进行真正的释放。

  • 在 kalloc中，被分配空闲页面的引用计数设为1。在 kfree 中，物理页的引用计数先减一，如果减一后 <= 0（为什么是 <= 而不是 = ？这是为初始化内存的时候准备的， freerange 会最新调用 kfree 一次），才会被加入空闲链表，减1和判<=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
    // 这一段代码 加锁和解锁 是比较难理解的地方。
    kernel/kalloc.c:
      
    void
    kfree(void *pa)
    {
      struct run *r;
      
      if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
        panic("kfree");
      
      acquire(&kmem.lock); // 加锁
      uint64 idx = ((uint64)pa - (uint64)PGROUNDUP((uint64)end)) / PGSIZE;
      rc[idx]--;
      if (rc[idx] > 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);
    }

  • uvmcopy 中不再实际分配内存而仅仅做映射，并对父进程的各个物理页的引用计数加一，同时父子两者的 PTEs 都要清除 Write 位。

    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
    kernel/vm.c:

    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);
        flags = PTE_FLAGS(*pte) & (~PTE_W);
        if(mappages(new, i, PGSIZE, (uint64)pa, flags) != 0)
            goto err;
        // set PTE_W to 0
        *pte &= ~PTE_W;
        // increament rc
        uint64 idx = ((uint64)pa - (uint64)PGROUNDUP((uint64)end)) / PGSIZE;
        acquire(&kmem.lock); // 这里一定要在修改共享资源之前加锁
        rc[idx]++;
        release(&kmem.lock);
      }
      return 0;
      
    err:
      uvmunmap(new, 0, i / PGSIZE, 1);
      return -1;
    }
    //////////////////////////////////////////////////////////////////

  • 改动 usertrap ，在一个 va 发生缺页异常时，尝试对它进行分配新的物理页并作映射和内容 copy，打开 PTE_W ，对原来所引用的物理页的引用计数 -1，如果失败了就走原来把它 kill 掉的逻辑。

    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
     kernel/trap.c:

     void
     usertrap(void)
     {
        ···
    	syscall();
       } else if((which_dev = devintr()) != 0){
         // ok
       } else {
         uint64 cause = r_scause();
         if (cause == 13 || cause == 15) { // 13 和 15 表示页异常，具体见 riscv 特权指令手册
             uint64 va = r_stval(); // 读取导致异常的那个虚拟地址
             pte_t *pte = walk(p->pagetable, va, 0);
             if (pte == 0 || (*pte & PTE_U) == 0) // 如果是因为访问 stack guard page 导致的异常，就把进程 killed 掉
                 p->killed = 1;
             else if ((*pte & PTE_V) == 0) { // 如果是缺页异常；这个 lab 不会发生
                 // lazy allocation, for now just kill it
                 p->killed = 1;
             }
             else if ((*pte & PTE_W) == 0) { // 如果是写物理页导致的页异常
                 char *pa = (char *)PTE2PA(*pte);
                 uint64 idx = ((uint64)pa - (uint64)PGROUNDUP((uint64)end)) / PGSIZE;
                 *pte |= PTE_W;
                 if (rc[idx] > 1) {
                     // cow
                     char *mem = kalloc();
                     if (mem) {
                         memmove(mem, pa, PGSIZE);
                         int flags = PTE_FLAGS(*pte);
                         *pte = PA2PTE(mem)|flags;
                         // decreament rc
                         kfree((void*)pa);
                     }
                     else
                         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());
             p->killed = 1;
         }
       }
    	···
    }

  • copyout 同 usetrap。

    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
    kernel/vm.c:

    int
    copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len)
    {
      uint64 n, va0, pa0;
      
      struct proc *p = myproc();
      while(len > 0){
        va0 = PGROUNDDOWN(dstva);
        pa0 = walkaddr(pagetable, va0);
        if(pa0 == 0)
          return -1;
      
        uint64 idx = ((uint64)pa0 - (uint64)PGROUNDUP((uint64)end)) / PGSIZE;
        if (rc[idx] > 1) {
            // 这一页是共享的，要重新分配一页进行修改
            char *mem = kalloc();
            if (mem) {
                pte_t *pte = walk(pagetable, va0, 0);
                *pte |= PTE_W;
                memmove(mem, (void*)pa0, PGSIZE);
                int flags = PTE_FLAGS(*pte);
                *pte = PA2PTE(mem)|flags;
                // decreament rc
                kfree((void*)pa0);
            }
            else {
                p->killed = 1;
                goto err;
            }
        }
        else {
            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;
      
    err:
      uvmunmap(pagetable, 0, (uint64)PGROUNDUP(p->sz) / PGSIZE, 1);
      return -1;
    }