genesis的空间站
0%

Lab Copy on Write Fork

发表于
本文字数： 6.1k 阅读时长 ≈ 6 分钟

Lab Copy on Write Fork

前置知识

一、原理

  1. 在xv6原始的eager fork中，执行fork会立刻将parent的所有页拷贝一份给child，但有时child会执行exec，然后丢到所有的拷贝，加载exec中的内容。这种重复的拷贝会浪费时空，因此可以进行copy on write fork。
  2. 在cow中，执行fork只会拷贝parent的页表，这些页表不分配空间，而是指向parent的页。parent的页此时不能有PTE_W位(只读)，当出现修改请求时，会出现一个page fault(13, 15)，此时再copy一个新页并分配给请求修改的地址就可以了(此时分配的page可读可写)
  3. 因为每一个parent可能会有多个child，因此每一个页在这些child都分配出去之前是不能被释放的，也就是说，一个页只有引用次数为1的时候才可以被释放。关于引用的计数，可以通过开一个大数组来记录所有页的引用次数(但总感觉10^6的int数组有点大)

task: Implement copy-on write

  1. 首先，我们需要拿出一位flag来记录当前page是否是一个cow page，根据录播课，可拿出第八位

    1
    2
    3
    4
    5
    6
    7
    //riscv.h
    ...
    #define PTE_W (1L << 2)
    #define PTE_X (1L << 3)
    #define PTE_U (1L << 4) // 1 -> user can access
    #define PTE_F (1L << 8) // copy-on-write fork
    ...

  2. 然后，我们需要一个数组来记录所有page的引用次数。这里有几个特殊地方需要注意：

因为整个cow fork与IO模拟设备无关，因此完全可以不用记录KERNBASE(0x80000000L)之下的page，这样可以节省一些空间消耗。

这个数组的每一个元素都要加自旋锁。如果不加，则可能会出现两个core同时申请一个parent的free 和 fork,两者同时拿到了parent的引用次数2，此时假设先执行fork，则引用加一为3，后执行free，引用减一为1，而后执行的结果会覆盖先执行的结果，从而导致race condition。对于到底是给每个元素加lock还是给整个数组加lock，我觉得应该是前者。因为如果给整个数组加lock，则这个数组只能在同一时间被一个core所使用，这显然会在并发中导致阻塞。

1
2
3
4
5
// kalloc.c
struct Pagecount{ // count for physical memory reference
  struct spinlock lock;
  int cnt; // 猜测是给元素加lock,因为如果整个加lock大概会影响并发
}ref[(PHYSTOP - KERNBASE) / PGSIZE];

  1. 初始化自旋锁和元素值。关于为何要把每一个cnt设置为1，因为每次启动kernel的时候，都会kfree一遍所有的page，在kfree中，会把cnt-1，因此要先+1。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    // kalloc.c
    void
    kinit()
    {
      for (int i = 0; i < (PHYSTOP - KERNBASE) / PGSIZE; i++)
        initlock(&ref[i].lock, "cow");
      initlock(&kmem.lock, "kmem");
      freerange(end, (void*)PHYSTOP);
    }

    void
    freerange(void *pa_start, void *pa_end)
    {
      char *p;
      p = (char*)PGROUNDUP((uint64)pa_start);
      for(; p + PGSIZE <= (char*)pa_end; p += PGSIZE)
      {
        ref[((uint64)p - KERNBASE) / PGSIZE].cnt = 1; //因为kfree会-1
        kfree(p);    
      }

    }

  2. 正如原理所说，在kfree中，只有引用次数为1的page才可以被释放，否则就只是给它的引用次数减一。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    void
    kfree(void *pa)
    {
      struct run *r;

      if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
        panic("kfree");
      uint64 rpa = ((uint64)pa - KERNBASE) / PGSIZE;
      acquire(&ref[rpa].lock);
      if ((--ref[rpa].cnt) <= 0){
      // 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);
      }
      release(&ref[rpa].lock);
    }

  3. 同时，在kalloc中，也需要把每一个初始分配的page引用计数设为1

    1
    2
    3
    4
    5
    6
    7
    8
    9
    if(r) {
      memset((char*)r, 5, PGSIZE); // fill with junk    
      uint64 rpa = ((uint64)r - KERNBASE) / PGSIZE;
      acquire(&ref[rpa].lock);
      if (ref[rpa].cnt)
        panic("kalloc: not a free page");
      ref[rpa].cnt = 1;
      release(&ref[rpa].lock);    
    }

  4. 把判断一个page是否是cow page，改变一个page的引用计数封装成函数(其实也可以直接写)

    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
    // kalloc.c
    // 修改cow计数
    void changeref(uint64 pa, uint64 num)
    {
      if (pa >= PHYSTOP)
        panic("chgref: pa too big");
      if (pa % PGSIZE != 0)
        panic("chgref: not a complete page");
      uint64 rpa = (pa - KERNBASE) / PGSIZE;
      acquire(&ref[rpa].lock);
      ref[rpa].cnt += num;
      release(&ref[rpa].lock); 
    }

    // 该page是否是cow page
    int iscow(pagetable_t pagetable, uint64 va)
    {
      if (va >= MAXVA)
        return -1;
      pte_t* pte = walk(pagetable, va, 0);
      if (!pte)
        return -1;
      if((*pte & PTE_V) == 0)
        return -1;
      return ((*pte) & PTE_F ? 0 : -1);
    }

  5. 此时，如果申请修改，那么会有page fault，此时如果该page只有一个引用，那么把flag还原一下就好，如果有多个引用，那么就分配一个可修改的page，然后把引用数减一。因为它冗杂且多用，因此封装为函数。注意，所有新添加的函数都需要在defs.h中声明一下。同时在这个函数中我们使用了walkaddr来取物理地址，因此也需要把它声明到defs.h中。

    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
    // kalloc.c
    uint64 cowalloc(pagetable_t pagetable, uint64 va)
    {
      if (va % PGSIZE != 0) {
        printf("cowalloc: va exceeds MAXVA\n");
        return -1;
      }

      
      uint64 pa = walkaddr(pagetable, va);
      if (pa == 0)
        return -1;
        //panic("cowalloc: pte not exists"); // 这里不能panic，而是返回错误并kill process，否则你的stacktest就会panic
      pte_t* pte = walk(pagetable, va, 0);  

      if (pte == 0)
        panic("cowalloc: pte not exists");
      if ((*pte & PTE_V) == 0 || (*pte & PTE_U) == 0) {
        panic("cowalloc: pte permission err");
      }


      if (refcnt((void*)pa) == 1) { // 只有一个引用
        *pte |= PTE_W;
        *pte &= ~PTE_F; // 还原标记
        return (uint64)pa;
      } else { // 多个引用
        uint64 mem = (uint64)kalloc();
        if (mem == 0) {
          printf("cowalloc: kalloc fails\n");
          return -1;      
        }

        memmove((void*)mem, (void*)pa, PGSIZE);

        *pte &= ~PTE_V; // 防止被mappage判定为remap

        if (mappages(pagetable, va, PGSIZE, mem, (PTE_FLAGS(*pte) | PTE_W) & ~PTE_F) != 0) {
          kfree((void*)mem);
          *pte |= PTE_V;
          return -1;
        }
        kfree((void*)PGROUNDDOWN(pa)); // 引用减一
        return mem;
      }
    }

  6. 我们知道，fork会跳转到uvmcopy来拷贝page，因此在里面我们需要作出修改。每次fork的时候，不需要分配物理page，只需要把parent的flag设好，引用数加一，并添加child的映射就好。

    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
    //vm.c
    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);
        *pte &= ~PTE_W;
        *pte |= PTE_F;
        flags = PTE_FLAGS(*pte);
        //if((mem = kalloc()) == 0)
        //  goto err;
        //memmove(mem, (char*)pa, PGSIZE);
        if(mappages(new, i, PGSIZE, pa, flags) != 0){
          //kfree(mem);
          goto err;
        }
        changeref(pa, 1);
      }
      return 0;

     err:
      uvmunmap(new, 0, i / PGSIZE, 1);
      return -1;
    }

  7. 因为page fault会跳转到usertrap，因此我们也需要修改usertrap，方法和lazy如出一辙。注意，在实现cowalloc时，映射错误，请求越界，内存耗尽等错误都会返回-1，这些情况需要立刻kill进程。(但后来仔细想了一下，请求越界是否也可以直接panic呢？)

    1
    2
    3
    4
    5
    } else if (r_scause() == 15) {
      uint64 fault_va = r_stval();
      if (fault_va >= p->sz || iscow(p->pagetable, fault_va) != 0 || cowalloc(p->pagetable, PGROUNDDOWN(fault_va)) == -1)
        p->killed = 1;
    } else {

  8. 还有一个小问题，当执行copyout时是在kernel中，并不能触发usertrap，因此需要另外处理。这里同样也需要拷贝页面，并需要拿到新分配页面的地址，这也就是为什么我们的cowalloc返回的是一个地址了。而且如果cowalloc出错，返回的是-1，需要与下面的出错判断统一(当然你也可以让它出错返回0，但我懒得改了)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    while(len > 0){
      va0 = PGROUNDDOWN(dstva);
      pa0 = walkaddr(pagetable, va0);
      if (iscow(pagetable, va0) == 0){
        pa0 = (uint64)cowalloc(pagetable, va0);
        if (pa0 == -1)
          pa0 = 0;     
      }
      if(pa0 == 0)
        return -1;

后记

在观摩前人代码时，发现了一个有意思的问题。请回看uvmcopy函数和cowalloc函数，在uvmcopy中，我们并没有判断该page在fork之前是否已经是只读的。如果它是只读的，那经过fork后，它和其他可写page一起被设为了只读的cow page，而在cowalloc中，引用数为1的page会直接标记可写，那么会不会出现不可写的page经过这种操作错误转化成可写page呢？如果要解决的话，我觉得需要用上第二个RSW位特殊记录，但在lab中并没有进行实现，但可以通过所有test，有兴趣者可自行尝试。

review:

在复习中，我在xv6 cow中查找了所有关于PTE_V的修改，发现只有在实现cow相关功能时，会出现只读不写的flag，因此在这个单独的修改中直接判断是可行的。基于这个特性，我们在这个lab中甚至可以优化掉PTE_F位，但是一旦加入其他的优化，比如lazy allocation，就需要额外判断。课程中morris老师讲到，在现代操作系统中，不是实现的简单page table，而是模仿page table的数据结构，或许这样就可以避免冲突了。