Implement copy-on write实验

实验目的

本节实验不是最难的一个，但是逻辑细节比较多（所以坑也多），也让我花了不少时间去打印和调试。本节和上一节页懒分配类似，都是利用Page Fault特性向xv6增加一些扩展。主要目的是，每次系统启动父进程会通过fork函数创建子进程，系统为子进程分配与父进程大小相当的空间，例如shell进程占4个页帧（4*4096字节），子进程也会分配新的4个字节；然而子进程很快就会被exec占据并且去运行其他进程，大部分情况下这新分配的空间没有被使用就被丢弃了，既浪费了内存也消耗了启动性能。

因此本节核心思想是在调用fork复制父进程时，不要直接为子进程分配物理内存，而是通过页表将子进程的虚拟地址也指向父进程的物理内存（暂且称其为COW内存）；为了保证这个物理内存的安全，在共享后必须将物理内存的写权限取消成为只读内存，当子进程确实需要空间时，对该物理内存进行写操作就会造成Page Fault；而又为了区分进程是对这种COW内存操作，还是真的误读了其他只读的页帧，我们需要引入新的标志位PTE_COW来区分两种只读页面。

为了处理这个page fault，在usertrap遇到COW内存时，就为其分配新的物理内存；另一个问题是这个COW内存的释放问题；现在一个物理内存可以被多个亲属进程共享，因此需要引入计数，只有引用进程数量为0，才将该物理内存释放；计数的实现是自由的，但在每个进程维护一个字段并且退出时更新到其他进程貌似是困难的，这里我参考了一位字节大佬的在内存的数据结构封装以及PV操作，较好地实现计数操作。

具体实现

  1. fork调用kernel/vm.c的uvmcopy函数实现进程的拷贝和内存分配，这里取消物理内存申请并且映射到父进程同一块空间。将COW内存标记为PTE_COW，第8位为预留位可以使用，详见基础理论页表一节的地址转换。 

    1
    #define PTE_COW (1L<<8)
    将内存设置成非可写，这样子进程进行内存交互就会触发pagefault，这里遇到就是第一个坑，报错见Q&A的1；标志位置位时必须将通过*pte置位，使得父子进程页表项的COW位生效；如果是写法1，则只有子进程页表被定义COW有效。V函数将在后面解析。 
    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
    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);
        //if((mem = kalloc()) == 0)
        //  goto err;
        //memmove(mem, (char*)pa, PGSIZE);
        //uint flags= PTE_FLAGS(*pte); //this is a fault!!!You didn't change the original pagetable!!!!!
      //flags=(flags&~PTE_W)|PTE_COW;  //写法1：错误写法
        *pte&=~PTE_W;  //写法2
      *pte|=PTE_COW;  //设置PTE_COW为1 PTE_W为0
      flags=PTE_FLAGS(*pte);
      if(mappages(new, i, PGSIZE, (uint64)pa,flags) != 0){
          //kfree(mem);
          goto err;
        }
        V(pa);  //物理内存占用标记，计数+1
      }
      return 0;
      err:
      uvmunmap(new, 0, i / PGSIZE, 1);
      return -1;
    }

  2. 在kernel/trap.c的usertrap函数处理page fault：从stval寄存器读取虚拟内存位置，这就是子进程想要写入却没有写入成功的内存位置，判断页面错误且PTE_COW标志位有效，就分配内存。这里主要存在两个问题：

    其一这里的uvmunmap是经过修改的，后续会介绍，这里最后的参数1，不是真正意义上的释放物理内存，它只会减小内存的引用数量，数量如果为0才会释放；

    其二是这里的标志位设置和上面步骤1的不同，是通过局部变量flags而不是pte设置的了，因为uvmunmap会将旧页表（也就是子进程到父进程内存）页表项清空，因此使用解析的pte设置没有意义。

    不知道为什么，kernel/defs.h原本竟然没有walk函数声明，加上： 

    1
    pte_t *         walk(pagetable_t, uint64 , int);
    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
    uint64 va=r_stval();
    pte_t *pte =walk(p->pagetable,va,0);
    if(pte == 0)           
      exit(-1);
    //panic("pte error");
    uint64 pa = PTE2PA(*pte);
    if(pa==0)
      exit(-1);
    //uint flags=PTE_FLAGS(*pte);
    uint flags;
    ......
    else if((r_scause()==15||r_scause()==13)&&(*pte&PTE_COW)){//页面错误，而且为COW共享的内存就分配内存
      uint64 cow_pa=(uint64)kalloc();
      if(cow_pa==0)
      //panic("usertrap cow_pa");
        exit(-1);
      memmove((char*)cow_pa,(char*)pa,PGSIZE);
      flags=PTE_FLAGS(*pte);
      uvmunmap(p->pagetable,PGROUNDDOWN(va),1,1); //remember to cancel the parent process map
        //*pte&=~PTE_COW;  //无需
      //*pte|=PTE_W;
      if(mappages(p->pagetable,PGROUNDDOWN(va),PGSIZE,cow_pa,(flags&~PTE_COW)|PTE_W)!=0){
        kfree((void*)cow_pa);
          panic("usertrap mappage error");
      }
    }

  3. 实现物理内存的引用计数,首先要定义一个宏，这个宏用于获取每个物理地址的数组编号：这里的理解可以参考基础理论的内核地址空间一节，虚拟内存的KERNBASE~PHYSTOP被直接映射整块物理内存RAM中，基本分配单位为1个页帧PGSIZE大小。如KERNBASE+PGSIZE就是编号为1的空间（PA2CNT(KERNBASE+PGSIZE)=1）。 

    1
    #define PA2CNT(pa) (((uint64)pa-KERNBASE)/PGSIZE)

    在kernel/kalloc.c仿照kmem定义一个结构体，这个变量被多个进程共享，为了安全需要加锁。 

    1
    2
    3
    4
    struct {
      int cow_num[PA2CNT(PHYSTOP)+1]; //长度为编号+1     
      struct spinlock cow_lock;  //锁
    }cow_count;
    锁在kinit()进行初始化； 
    1
    initlock(&cow_count.cow_lock,"cow_count");
    对这个变量的加减值可以看成是一种PV操作，在分配新内存、拷贝父进程都会使得内存引用数量增加，为V操作；在进程释放内存，会使得内存引用数量减少，为P操作；当然不使用PV操作也可以将结构体定义在头文件直接对数组进行读写；封装的形式： 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    int P(uint64 pa){
      acquire(&cow_count.cow_lock); //锁
      if(pa<KERNBASE||pa>=PHYSTOP)//物理内存合法性（直接映射，因此和内核空间范围对应）
        panic("P pa error\n");
      int use_num=--cow_count.cow_num[PA2CNT(pa)]; //P操作，注意先+再赋值
      release(&cow_count.cow_lock);
      return use_num;
    }
    int V(uint64 pa){
      acquire(&cow_count.cow_lock); //锁
      if(pa<KERNBASE||pa>=PHYSTOP)  //物理内存合法性（直接映射，因此和内核空间范围对应）
        panic("V pa error\n");
      int use_num=++cow_count.cow_num[PA2CNT(pa)]; //V操作，注意先+再赋值
      release(&cow_count.cow_lock);
      return use_num;
    }

    有了这个操作，就可以对刚刚描述三种情况进行PV操作了，依次是kalloc分配新内存、uvmcopy拷贝父进程内存、kfree释放内存;对新分配内存必然只有申请内存的进程使用，因此无需V操作，直接写数组即可。 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    //kernel/kalloc.c
    void *
    kalloc(void)
    {
      struct run *r;
      acquire(&kmem.lock);
      r = kmem.freelist;
      if(r)
        kmem.freelist = r->next;
      release(&kmem.lock);

      if(r){
        memset((char*)r, 5, PGSIZE); // fill with junk
      //printf("%p\n",r);
        cow_count.cow_num[PA2CNT(r)]=1; //new
      //printf("%x\n",PA2CNT(r));
      }
      return (void*)r;
    }
    uvmcopy我们在第一步就实现了，不再赘述；

    释放内存kfree主要是三种场景，一种是页表映射失败调用kfree回收，第二种是解映射uvmunmap函数调用kfree进行释放，都可以进行P操作即可。第三种往下看，只有严格为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
    //kernel/kalloc.c
    void
    kfree(void *pa)
    {
      struct run *r;

      if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
        panic("kfree");


      int num=P((uint64)pa);  //P操作，然后查看引用值，不要把函数写入比较，否则就是两次P操作了
      if(num<0)
      panic("kfree P<0");
      if(num>0)
      return;

      // Fill with junk to catch dangling refs.
      memset(pa, 1, PGSIZE);  //num==0才会执行以下代码

      r = (struct run*)pa;
      acquire(&kmem.lock);
      r->next = kmem.freelist;
      kmem.freelist = r;
      release(&kmem.lock);
    }

    第三种情况，就是一开始系统启动，会调用kinit进行初始化，kinit会调用freerange调用kfree清空垃圾内存，相当于内存启动时就进行了一次P操作，因此这些进程的计数值会是-1；为了避免这个问题，需要在freerange之前给所有进程的计数值置1，抵消掉P操作，使其初始化完成时、最后没有进程时计数值为0，sizeof(cow_count.cow_num)/sizeof(int)获取进程的数量，逐个进程置1； 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    void
    freerange(void *pa_start, void *pa_end)
    {
      char *p;
      p = (char*)PGROUNDUP((uint64)pa_start);
      for(int i = 0; i < sizeof(cow_count.cow_num)/ sizeof(int); ++ i) //新增
        cow_count.cow_num[i]=1;
      for(; p + PGSIZE <= (char*)pa_end; p += PGSIZE)
        kfree(p);
    }
    如果不想需要这一步，也可以修改kfree，使其<0时也可以释放而不会报panic。

  4. 修改copyout函数：数据从内核传输到用户空间，会改变用户进程的内容，这是写操作，从名称Copy on Write就知道这会触发复制操作，因为用户进程此时可能和其他进程共享某个内存，用于节省资源，内核向用户进程写数据（这些数据只有监管者模式能够获取），而写操作发生就必须分配新的物理内存给该用户进程；相反，copyin基本不会影响COW机制，因为copyin的作用是从用户空间读取数据到内核，这些数据一般是用户告知内核的自己的需求、参数等，从共享内存读数据是安全的，也不会写入内核，因此无需修改copyin。

    因此，调用walk函数获取页表项，通过标志位判断用户空间dstva是否指向一个COW内存（共享内存），如果是则需要分配物理内存，分配过程和usertrap类似。但注意：这里如果判断不是COW内存，也即PTE_COW标志位为0，不能直接返回-1，因为copyout也负责了其他页面的跨态传输，如果直接返回会导致系统无法运行，见Q&A 2。 

    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
    int
    copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len)
    {
      uint64 n, va0, pa0;
      uint flags;

      while(len > 0){
        va0 = PGROUNDDOWN(dstva);
      if(va0>MAXVA)  //新增---------------------------------------
        return -1;
      pte_t *pte=walk(pagetable,dstva,0);  //获取页表项
        if(pte == 0)
          //panic("pte error");
          return -1;
      uint64 pa=PTE2PA(*pte);
      if(pa==0)
          return -1;
        //panic("copyout pa error");
      flags=PTE_FLAGS(*pte);
      //printf("  1:%p\n",flags);
      //printf("  2:%p\n",flags&PTE_COW);
      //printf("  3:%p\n",PTE_COW);
      if(*pte&PTE_COW){  //如果用户进程为共享页，就分配物理内存
        uint64 cow_pa=(uint64)kalloc();                                                        
        if(cow_pa==0)
          return -1;
        memmove((char*)cow_pa,(char*)pa,PGSIZE);
        uvmunmap(pagetable,va0,1,1);
        if(mappages(pagetable,va0,PGSIZE,cow_pa,(flags&~PTE_COW)|PTE_W)!=0){
          kfree((void*)cow_pa);
        return -1;
        }
      }     //--------------------------------------新增
      pa0 = walkaddr(pagetable, va0); //其他非COW进程正常执行即可
      if(pa0 == 0)
        return -1;
      n = PGSIZE - (dstva - va0);
      if(n > len)
        n = len;
      memmove((void *)(pa0 + (dstva - va0)), src, n);

      len -= n;
      src += n;
      return -1;
      }
    }
    至此，要点基本陈述完了，做这一节多少需要一点祝福buf,测试cowtest和usertests后提交： COW Fork Done

完整Commit请参考：COW Fork Done

Q&A

注意，造成系统报错的原因是多方面的，这里仅陈述我的程序调试过程，不能保证唯一性。

  1. cowtest的file test报错 
    1
    2
    3
    4
    file: ereerorr:r rroorrre:a dr efaadi lfeadi
    led
    : re$ad fa iled
    error: read the wrong value
  • 读取时读取到错误数据，虽然系统没有崩溃，但是COW的流程可能是有问题的，简单的可能是虚拟地址dstva相关错误，复杂点的就是COW没有正确运行，例如上述步骤1标志位导致父进程的COW位无效，判断逻辑出错，应该先确保标志位、标志位判断正确；
  1. 系统启动时显示panic: init exiting
  • 这里我的错误定位就在copyout函数，写成了if(*pte&PTE_COW==0) return -1,系统启动时会从内核copyout各种页帧到用户空间，其中包含着非COW内存，如果直接return -1，自然无法正常copy，导致系统无法启动。

总结

调试可能是这个lab的难关之一，尤其是第一个错误，几个小时都没能看出来，gdb也调不出一个所以然，看了博客也没有人提到这个问题，因为没人像我这样来写的。。。而遇到的错误也不止这两个，包括一些平时程序很理所应当，但是放操作系统很离谱的事情。例如进程退出的三巨头：panic、return、exit，从我的代码可以看出，panic定位错误的确很好用，但是对于xv6，panic出错是经常的事，因此一些命令本身就是放在进程中被循环调用的，使用exit就好，如果使用panic，usertests能全部通过才真是见鬼。最后，返回值逻辑也是一个坑，如果满足就执行、以及如果不满足就返回，这是两码的事情，因此比较好的习惯是每获取一个值，就给它判断一下合法性，以免这个不合法的值导致其他奇奇怪怪的错误，如果出错，就要看看判断合法性是不是矫枉过正了。