YangYuchen
xv6学习，Lab5-Copy-on-Write Fork for xv6

xv6学习，Lab5-Copy-on-Write Fork for xv6

2024年07月29日 2.6k 字 大概 12 分钟

五、Lab5: Copy-on-Write Fork for xv6

虚拟内存提供了一种间接性：内核可以通过将页表项标记为无效或只读来拦截内存引用，从而导致页面错误，并且可以通过修改页表项来改变地址的含义。在 xv6 中，fork() 系统调用会将父进程的所有用户空间内存复制到子进程中。如果父进程很大，复制过程可能会花费很长时间。更糟糕的是，这项工作往往在很大程度上是浪费的：在子进程中，fork() 之后通常会跟着 exec()，它会丢弃复制的内存，而且通常大部分都不会被使用。另一方面，如果父进程和子进程都使用一个复制的页面，并且其中一个或两个进程对其进行写入操作，那么这个复制确实是有必要的。

您在实现写时复制（COW）的 fork() 函数时的目标是，将物理内存页面的分配和复制推迟到实际需要这些副本时（如果需要的话）。 写时复制的 fork() 函数只为子进程创建一个页表，子进程的用户内存页表项（PTE）指向父进程的物理页面。写时复制的 fork() 函数将父进程和子进程中的所有用户 PTE 标记为只读。当任一进程试图写入这些写时复制页面中的一个时，CPU 将强制产生一个页面错误。内核的页面错误处理程序会检测到这种情况，为出错的进程分配一个物理内存页面，将原始页面的内容复制到新页面中，并修改出错进程中相关的 PTE，使其指向新页面，这次将 PTE 标记为可写。当页面错误处理程序返回时，用户进程将能够写入其页面副本。 写时复制的 fork() 函数使得释放实现用户内存的物理页面变得稍微复杂一些。一个给定的物理页面可能会被多个进程的页表引用，并且只有当最后一个引用消失时才应该被释放。

1.Implement copy-on-write fork()

您的任务是在 xv6 内核中实现上述写时复制的 fork 功能。为了帮助测试，提供了 user/cowtest.c ，cowtest 会运行各种测试。

  • 根据提示，为每个PTE有记录其是否为COW映射，可以使用 RISC-V PTE 中的 RSW位来实现此目的。根据下图，RSW位为第8和第9位，我们只需要使用第8位，去riscv.h中进行定义。

    image.png 
    1
    2
    // kernel/riscv.h
    #define PTE_RSW (1L << 8)

  • 修改 uvmcopy() 函数，将父进程的物理页映射到子进程中，而不是分配新的页面。对于设置了 PTE_W 的页面，清除子进程和父进程的页表项（PTE）中的 PTE_W 标志，这样这些页面就变成了一个“只读”页面，当触发写操作时就会进入中断。基本上有关页表的操作都在kernel/vm.c中， 现在对uvmcopy()进行修改，如下：

    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
    // kernel/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");
        // lab5-1,对PTE_W置位进行清除
        flags = PTE_FLAGS(*pte);
        pa = PTE2PA(*pte);
        // PTE_RSW置位
        if(*pte & PTE_W){
          flags = (flags & (~PTE_W)) | PTE_RSW;
          *pte = (*pte & (~PTE_W)) | PTE_RSW;
        }
        // 这里原先直接分配了物理页面，我们把这一部分删除
        // 由于引用数组位于kalloc.c，我们在kalloc.c中编写一个额外的方法
        // 最后把页表映射给子进程
        if(mappages(new, i, PGSIZE, (uint64)pa, flags) != 0){
          goto err;
        }
        // 这里要把引用数组对应的值加一
        refarrayadd((uint64)pa);
      }
      return 0;

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

  • 确保当最后一个指向某个物理页面的页表项引用消失时（且仅在此时），该物理页面才会被释放。一个好的方法是为每个物理页面维护一个“引用计数”，表示有多少个用户页表引用了该页面。当 kalloc() 分配一个页面时，将其引用计数设置为 1。当 fork 操作导致子进程共享该页面时，增加该页面的引用计数，当任何进程从其页表中删除该页面时，减少该页面的计数。只有当页面的引用计数为 0 时，kfree() 才应将该页面放回空闲列表。将这些计数保存在一个固定大小的整数数组中，为此定义了一个ref结构体和refarray数组。可以自由修改 kalloc.c（例如，kalloc() 和 kfree()）来维护引用计数。 

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

    // 定义引用数组
    // 数组大小是页面的个数，对应第三章页表中学习过的PHYSTOP - KERNBASE这部分地址
    // 再除以页面大小就是数组的上限
    // 除此之外还得定义这个数组的自旋锁
    // 防止同一个页面被申请两次

    struct {
      struct spinlock lock;
      struct run *freelist;
    } kmem;

    // lab5-1
    // 类似kmem，定义一个ref结构体
    // 定义锁和引用数组
    struct {
      struct spinlock reflock;
      int refarray[(PHYSTOP -KERNBASE) / PGSIZE];
    } ref;

    void
    kinit()
    {
      // 初始化刚才定义的
      initlock(&kmem.lock, "kmem");
      initlock(&ref.reflock, "ref");
      freerange(end, (void*)PHYSTOP);
    }
      
    void
    kfree(void *pa)
    {
        struct run *r;
        if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
            panic("kfree");
         // 如果引用数组大于1，我们不需要真正的释放这片内存，只需要把对应数组减一即可
        if(ref.refarray[((uint64)pa -KERNBASE) / PGSIZE] > 1){
            acquire(&ref.reflock);
            ref.refarray[((uint64)pa -KERNBASE) / PGSIZE]--;
            release(&ref.reflock);
        }else{
            memset(pa, 1, PGSIZE);
            r = (struct run*)pa;
            acquire(&kmem.lock);
            r->next = kmem.freelist;
            kmem.freelist = r;
            release(&kmem.lock);
        }
    }

    // 物理地址pa的引用数组对应值加1
    void
    refarrayadd(uint64 pa){
        acquire(&ref.reflock);
        ref.refarray[(pa - KERNBASE) / PGSIZE]+=1;  
        release(&ref.reflock);
    }

    // 获取物理地址pa对应引用数组的值
    int
    getrefnum(uint64 pa){
        int num;
        acquire(&ref.reflock);
        num = ref.refarray[(pa -KERNBASE) / PGSIZE];  
        release(&ref.reflock);
        return num;
    }

    void *
    kalloc(void)
    {
        struct run *r;
        acquire(&kmem.lock);
        r = kmem.freelist;
        if(r){
            kmem.freelist = r->next;
             // lab5-1
             // 引用数组对应值初始化为1
            acquire(&ref.reflock);
            ref.refarray[((uint64)r -KERNBASE) / PGSIZE] = 1;  
            release(&ref.reflock);
        }
        release(&kmem.lock);
        if(r)
            memset((char*)r, 5, PGSIZE);
        return (void*)r;
    }

  • 修改 usertrap() 函数，使其能够识别页面错误。当对原本可写的COW页面发生写页面错误时，使用 kalloc() 分配一个新页面，将旧页面的内容复制到新页面，并将新页面安装到设置了 PTE_W 的 PTE 中。原本只读的页面（未映射 PTE_W，如文本段中的页面）应保持只读状态，并在父进程和子进程之间共享；试图写入这样页面的进程应被终止。在官方文档第49页中有如下说明:

    RISC-V 区分三种页面错误：加载页面错误（当加载指令无法转换其虚拟地址时）、存储页面错误（当存储指令无法转换其虚拟地址时）和指令页面错误（当程序计数器中的地址无法转换时）。scause 寄存器指示页面错误的类型，stval 寄存器包含无法转换的地址。

    也就是说，应该先判断SCAUSE寄存器的值，如下图所示，其存储发生中断的原因，是写页面时发生的错误，SCAUSE应为15。之后再从STVAL寄存器中取出无法转换的地址进行处理。

    image.png

    实现这一部分是这个实验的难点，kernel/vm.c中是涉及虚拟地址相关的操作，我们在trap中获取了写页面失败时的地址，但不能直接对其进行操作，应该在vm.c中定义一个新的函数对这个地址进行处理，使用walk函数获取地址对应PTE，并判断其合法性以及是否为COW页，若为COW页就为其分配物理内存并更改引用数组。

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

    // 这个函数用于处理传入的异常地址
    // 返回-1说明出错，返回0说明正常                                                                                   
    int tacklecowaddr(pagetable_t pagetable,uint64 addr)
    {
        // 一定要确保页面对齐
        uint64 va = PGROUNDDOWN(addr);
        if(va>=MAXVA)
            return -1;
        // 使用walk找到异常虚拟地址对应的PTE
        pte_t *pte = walk(pagetable, va, 0);
        if(pte==0)
            return -1;
        uint64 flags = PTE_FLAGS(*pte);
        //转换物理地址
        uint64 pa = PTE2PA(*pte);
        if(pa==0)
            return -1;
        //如果是COW页面（PTE_RSW置位)
        if(flags&PTE_RSW)
        {
             // 用kalloc分配空间
            uint64 mem = (uint64)kalloc();
            if(mem==0){
                printf("tacklecowaddr : kalloc error!");
                return -1;
             }
             // 用memmove将pa处的页面复制道新申请的地址处
            memmove((char *)mem, (char *)pa, PGSIZE);
             // 解除原先的页面映射
            uvmunmap(pagetable, va, 1, 1);
            flags = (flags | PTE_W) & ~PTE_RSW;
             // 为新的映射创建PTE
            if(mappages(pagetable,va,PGSIZE,mem,flags)!=0)
            {
                 printf("tacklecowaddr : mappage error!");
                kfree((void *)mem);
                return -1;
            }
        }
        return 0;
    }

    // kernel/trap.c

    void
    usertrap(void)
    {
      int which_dev = 0;
      if((r_sstatus() & SSTATUS_SPP) != 0)
        panic("usertrap: not from user mode");
      w_stvec((uint64)kernelvec);
      struct proc *p = myproc();
      p->trapframe->epc = r_sepc();
      if(r_scause() == 8){
        if(killed(p))
          exit(-1);
        p->trapframe->epc += 4;
        intr_on();
        syscall();
      } else if((which_dev = devintr()) != 0){
        // ok
      } else if(r_scause() == 15){
          // lab5-1
          // COW页面发生写页面错误,先获取其错误的页面地址
          uint64 faultaddr = r_stval();
          // 调用我们在vm.c中编写的tacklecowaddr函数处理地址
          if(tacklecowaddr(p->pagetable,faultaddr) < 0 ){
          setkilled(p);
          }
      }else {
        printf("usertrap(): unexpected scause %d pid=%d\n", r_scause(), p->pid);
        printf("            sepc=%p stval=%p\n", r_sepc(), r_stval());
        setkilled(p);
      }
      if(killed(p))
        exit(-1);
      if(which_dev == 2)
        yield();
      usertrapret();
    }

  • 修改 copyout() 函数，使其在遇到写时复制页面时使用与页面错误处理相同的方案。除此之外要把新定义的几个函数写进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
    int
    copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len)
    {
      uint64 n, va0, pa0;
      pte_t *pte;

      while(len > 0){
        va0 = PGROUNDDOWN(dstva);
        if(va0 >= MAXVA)
          return -1;
        // lab5-1
        if(tacklecowaddr(pagetable,va0)<0){
            printf("copyout : tacklecowaddr error!");
            return -1;
        }
        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;
    }

  • 解决各种编译报错后运行qemu，发现仍有各种报错，解决各种指针问题后无报错信息。但运行 cowtest 测试后仍然报错，发现了kfree 和 tacklecowaddr 中出现了错误。

  • 上方代码已修改。

    image.png
本文作者：YangYuchen
本文链接：https://www.littlewhite.site/xv6学习，Lab5-240729/
版权声明：本文采用 CC BY-NC-SA 3.0 CN 协议进行许可