课程地址：https://pdos.csail.mit.edu/6.S081/2020/schedule.html
Lab 地址：https://pdos.csail.mit.edu/6.S081/2020/labs/cow.html
我的代码地址：https://github.com/Amroning/MIT6.S081/tree/cow
xv6手册：https://pdos.csail.mit.edu/6.S081/2020/xv6/book-riscv-rev1.pdf
相关翻译：http://xv6.dgs.zone/labs/requirements/lab6.html
参考博客：https://blog.miigon.net/posts/s081-lab6-copy-on-write-fork/

学习的笔记记录，如有错误恳请各位大佬指正

Lab6: Copy-on-Write Fork for xv6

​ 本次实验还是利用缺页故障实现一个有趣的机制：写时复制（Copy-on-Write，COW）。

​ 在原始的XV6中，fork函数是通过直接对进程的地址空间完整地复制一份来实现的。但是，拷贝整个地址空间是十分耗时的，并且在很多情况下，程序立即调用exec函数来替换掉地址空间，导致fork做了很多无用功

​ 该实验的改进：COW fork()只为子进程创建一个页表，用户内存的PTE指向父进程的物理页。COW fork()将父进程和子进程中的所有用户PTE标记为不可写。当任一进程试图写入其中一个COW页时，CPU将强制产生页面错误。内核页面错误处理程序检测到这种情况，将为出错进程分配一页物理内存，将原始页复制到新页中，并修改出错进程中的相关PTE指向新的页面，将PTE标记为可写。当页面错误处理程序返回时，用户进程将能够写入其页面副本。

​ COW fork()将使得释放用户内存的物理页面变得更加棘手。给定的物理页可能会被多个进程的页表引用，并且只有在最后一个引用消失时才应该被释放，所以针对这个问题需要有引用计数机制

Lab

​ 仅复制题目部分内容，完整要求请去该帖子顶部链接查看

Implement copy-on write (hard)

您的任务是在xv6内核中实现copy-on-write fork。如果修改后的内核同时成功执行cowtest和usertests程序就完成了。

​ 首先给页表添加一个新的标志位，代表这个页是否是写时复制页。其他的标志位就是PTE_W、PTE_R这些，这里新的标志位就叫PTE_COW，以下就把写时复制页称为COW页：

// kernel/riscv.h
#define PTE_V (1L << 0) // valid
#define PTE_R (1L << 1)
#define PTE_W (1L << 2)
#define PTE_X (1L << 3)
#define PTE_U (1L << 4) // 1 -> user can access
#define PTE_COW (1L << 8) 
//是否为COW页，使用页表项 flags 中保留的第 8 位表示（页表项 flags 中，第 8、9、10 位均为保留给操作系统使用的位，可以用作任意自定义用途）

​ 父进程使用fork创建子进程时，会调用uvmcopy，把父进程映射的物理页全都复制一份新的给子进程。写时复制是写的时候才复制，所以这里去掉复制的功能，只给对应的页添加上PTE_COW标志位。这里原本父进程中只读的页，不做修改，也就是说，只读的页在父进程和子进程中一直都会是共享的。只有原本是可写的页做修改：

// 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);

    // 清除父进程中所有PTE的PTE_W位，并且设置PTE_COW位，表示所在页是一个写时复制页（多个进程引用同个物理页）
    // 如果该页本身就是不可写（只读），则不会添加这个标志位
    if (*pte & PTE_W)
        *pte = (*pte & ~PTE_W) | PTE_COW;

    flags = PTE_FLAGS(*pte);        //获取当前父进程pte的标志位

    //将父进程映射的物理页直接map到子进程中，权限保持和父进程一致（注意现在都是不可写，而且原本是可写的页会有新增的PTE_COW写时复制标志）
    if (mappages(new, i, PGSIZE, (uint64)pa, flags) != 0)
        goto err;

    krefpage((void*)pa);         //映射的物理页的引用数+1

    // 去掉以下复制内存的代码
    // if((mem = kalloc()) == 0)
    //   goto err;
    // memmove(mem, (char*)pa, PGSIZE);
    // if(mappages(new, i, PGSIZE, (uint64)mem, flags) != 0){
    //   kfree(mem);
    //   goto err;
    // }
  }
  return 0;

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

​ krefpage函数是使物理页引用数+1。为了避免内存泄漏，多个进程映射同一个物理页的时候，记录一下这个物理页的引用数，调用kfree释放物理页的时候，只对引用数-1，当引用数为0的时候，才释放物理页。这里先有个概念，krefpage函数下面实现。

​ 现在使用fork函数不会复制内存了，父进程和子进程都映射到同一片物理内存，且所有的页都是不可写的状态。这个时候某一个进程尝试执行写操作，就会出现页面错误被usertrap捕获。接下来修改usertrap函数，实现在修改页的时候，才创建和映射新的物理页

​ 和上一个实验惰性分配类似，在usertrap中添加对页面错误的检测，如果当前访问的地址符合COW页的条件时，就进程复制内存操作：

// kernel/trap.c
void
usertrap(void)
{
  ......
    
  } else if((which_dev = devintr()) != 0){
    // ok
  }else if ((r_scause() == 13 || r_scause() == 15) && uvmcheckcowpage(r_stval())) {
      // 发生页面错误，并且检测出错误是写时复制机制导致的页面不可写，则执行写时复制
      if (uvmcowcopy(r_stval()) == -1)
          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;
  }

  ......
}

​ 调用r_scause判断是否是页面错误，实现一个uvmcheckcowpage函数判断是否是COW机制导致的页面错误，符合这些条件，再实现一个uvmcowcopy函数执行写时复制操作。

​ 实现uvmcheckcowpage函数，检查这个地址是否在COW页：

// kernel/vm.c
//检查虚拟地址所在页是否是COW页
int uvmcheckcowpage(uint64 va) {
    pte_t* pte;
    struct proc* p = myproc();

    return va < p->sz
        && ((pte = walk(p->pagetable, va, 0)) != 0)
        && (*pte & PTE_V)
        && (*pte & PTE_COW);
    //地址在进程内存范围内  &&  地址有映射  && 地址有效且是COW页
}

​ 实现uvmcowcopy函数，复制一个新的物理页，创建新的映射。上面说到原本是只读的页不会添加PTE_COW标志位，所以恢复可写权限时，要检查一下pte是否有PTE_COW标志位，也就是说，原本是只读的页不会有PTE_COW标志位，不用修改写权限；原本是可写的页会带有PTE_COW标志位（此时是不可写的状态），要恢复写权限，并清除掉PTE_COW标志位：

// kernel/vm.c
// 实现写时复制
int uvmcowcopy(uint64 va) {
    pte_t* pte;
    struct proc* p = myproc();

    if ((pte = walk(p->pagetable, va, 0)) == 0)     //获取虚拟地址的页表项
        panic("uvmcowcopy: walk");

    uint64 pa = PTE2PA(*pte);                     //获取映射的物理地址
    uint64 new = (uint64)kcopy_n_deref((void*)pa);  //获取新分配的物理页（如果原本的物理页引用数为1，则获取到的还是原本的物理页）
    if (new == 0)       //内存不足的情况
        return -1;

    //修改新的映射，若当前页有COW标识，权限修改为可写，清除COW标识
    uint64 flags = PTE_FLAGS(*pte);
    if (*pte & PTE_COW)
        flags = (PTE_FLAGS(*pte) | PTE_W) & ~PTE_COW;
    uvmunmap(p->pagetable, PGROUNDDOWN(va), 1, 0);              //清除旧的映射
    if (mappages(p->pagetable, va, 1, new, flags) == -1)        //新的映射
        panic("uvmcowcopy: mappages");

    return 0;
}

​ kcopy_n_deref函数的思路是，当有进程通过COW复制新的物理页时，把原本物理页的引用数-1，返回新创建的物理页地址。如果原本的物理页引用数就是1了，那可以直接使用这个物理页了，因为也没有其他进程会使用这个物理页了。kcopy_n_deref函数下面实现。

​ copyout函数是软件访问页表，不会触发缺页异常，这里添加上检测代码，检测复制的页是否是一个COW页，是的话就执行复制操作：

// kernel/vm.c
int
copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len)
{
    uint64 n, va0, pa0;

    while (len > 0) {

        if (uvmcheckcowpage(dstva))     //检查每一个页是否为COW页
            uvmcowcopy(dstva);

        va0 = PGROUNDDOWN(dstva);
        pa0 = walkaddr(pagetable, va0);
        ......
}

​ 到此，已实现了大致的逻辑：调用fork的时候不复制内存，只是把子进程的映射和父进程保持一致，并把可写的页变为不可写，添加PTE_COW标志位。某一进程进行写操作时产生页面错误，此时才调用相关函数实现复制内存，并把新的页面恢复写权限。

​ 接下来需要对页的生命周期进行管理，确保页没有被任何进程使用的时候才释放

​ 原本的xv6中，一个物理页只会在一个进程中有映射，kalloc用来分配物理页，kfree用来回收物理页。在COW机制中，一个物理页会在多个进程中有映射，所以要在最后一个映射释放的时候，才真正释放回收该物理页，结合这些，需要实现以下操作：

• kalloc: 分配物理页，将其引用数置为 1
• krefpage: 创建物理页的一个新映射的时候，引用数+1
• kcopy_n_deref: 将原物理页的数据复制到一个新物理页上（引用数为 1），返回得到的新物理页；并将原物理页的引用数-1
• kfree: 释放物理页的一个映射，引用数减 1；如果引用数变为 0，则释放回收物理页

​ 一个物理页首先会被父进程使用 kalloc创建，fork 的时候，新创建的子进程的时候会调用krefpage 声明对应物理页的引用数+1。当尝试修改父进程或子进程中的页时，kcopy_n_deref 负责将想要修改的页复制到独立的副本，并记录解除旧的物理页的映射（引用数-1）。最后 kfree 保证只有在所有的引用者都释放该物理页的映射时，才释放回收该物理页

​ 在kallo.c定义一些相关的宏：

#define PA2PGREF_ID(p) (((p)-KERNBASE)/PGSIZE)      // 由物理地址获取物理页id
#define PGREF_MAX_ENTRIES PA2PGREF_ID(PHYSTOP)      // 物理页数上限

int pageref[PGREF_MAX_ENTRIES];         //每个物理页的引用数 数组（pageref[i]表示第i个物理页的引用数）
struct spinlock pgreflock;              //用于pageref数组的锁，防止竞态条件引起内存泄漏

#define PA2PGREF(p) pageref[PA2PGREF_ID((uint64)(p))]       //获取地址对应物理页引用数

​ 初始化锁：

void
kinit()
{
    initlock(&kmem.lock, "kmem");
    initlock(&pgreflock, "pgref");      //初始化锁
    freerange(end, (void*)PHYSTOP);
}

​ 修改kfree：

void
kfree(void *pa)
{
  struct run *r;

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

  //当页面的引用数<=0的时候释放页面
  acquire(&pgreflock);
  if (--PA2PGREF(pa) <= 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(&pgreflock);
}

​ 修改kalloc：

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
    PA2PGREF(r) = 1;        //将新分配的物理页的引用数设置为1（刚分配的页还没映射，不会有进程来使用，不用加锁）
  }
  return (void*)r;
}

​ 实现krefpage：

//物理页引用数+1
void krefpage(void* pa) {
    acquire(&pgreflock);
    PA2PGREF(pa)++;
    release(&pgreflock);
}

​ 实现kcopy_n_deref：

// 写时复制一个新的物理地址返回
// 如果该物理页的引用数>1，则将引用数-1，并分配一个新的物理页返回
// 如果引用数 <=1，则无需操作直接返回该物理页
void* kcopy_n_deref(void* pa) {
    acquire(&pgreflock);

    //当前物理页的引用数为1，无需分配新的物理页
    if (PA2PGREF(pa) <= 1) {
        release(&pgreflock);
        return pa;
    }

    //分配新的物理页，并把旧页中的数据复制到新页
    uint64 newpa = (uint64)kalloc();
    if (newpa == 0) {           //内存不够了
        release(&pgreflock);
        return 0;
    }
    memmove((void*)newpa, (void*)pa, PGSIZE);

    //旧页引用数-1
    PA2PGREF(pa)--;

    release(&pgreflock);
    return (void*)newpa;
}

​ 这里定义了一个自旋锁pgreflock，通过acquire(&pgreflock)和release(&pgreflock)获取锁和释放锁来保护操作的代码，锁的作用是防止竞态条件下导致的内存泄漏

比如，父进程的一个物理页p，此时引用数是1。

父进程执行fork创建子进程，此时p的引用数是2。

父进程执行写操作，触发页面异常。因为p的引用数大于1，开始执行复制p的操作（p的引用数还是2）。

进程调度，切换到子进程（父进程复制操作中断）。子进程马上执行exec，释放所有旧的物理页，物理页引用数-1（p的引用数为1）。

进程调度，切换到父进程。父进程继续复制p的数据到新的物理页。复制完毕，p的引用数-1。之后回到uvmcowcopy函数中，通过uvmunmap解除了对p的映射。物理页p并没有被释放回收，所有进程都丢失了对p的映射（页表中均没有指向 p 的页表项），造成内存泄漏

​ 加上锁之后，可以防止这个现象发生。在使用kalloc分配内存时可以不用加锁，因为这个地址还没返回，没有哪个进程可以操作这个新分配的地址。

​ 此时可以执行make grade验证实验是否完成。

PS：有一个 Cannot read time.txt 的检查项目，应该是原课程要求学生上传一个time.txt文件说明完成实验花了多长时间。在项目主目录xv6-labs-2020/创建这个文件，随便写一个数字就能通过这个检查项