本篇博客主要是复习 MIT6.s081/6.828 lectrue07：Page faults 以及记录 Lab5 ：COW fork 的心得

值得一提的是，2020 年之前的版本第 5 个 lab 是 lazy alloction，但是到了 2020 年之后就换成了难度稍高一点的 COW fork，有兴趣的小伙伴可以把 lazy alloction也一起做一做~毕竟这些 lab 都是精心设计的，不做蛮可惜的。

前面 6 节课程，Frans 教授的授课风格都是一边讲解，一边实际操作 xv6 来演示，但这节课有所不同，以理论讲解为主，主要是因为对应的代码在 xv6 中都没有实现，而是作为 lab 要求学生来实现，所以教授无法演示，但今天的理论也很好理解，而且十分“涨见识”，我在没学之前完全没有意识到 Page faults 竟然有如此多的作用。（以下有时对 Page faults 简称 pf）

借用权游中的著名台词：混乱是阶梯。

这句台词完美描述了 Page fault 的设计哲学！

Page fault 概述

Page fault（页错误）是 OS 中的一种异常情况，当程序访问一个虚拟内存中的 page 时，发现该地址无效（可能是在页表中找不到，或者是找到之后 PTE_V 标志位为 0）。

xv6 对于 Page fault 的处理十分简单粗暴，就是直接杀死进程，但实际上没有任何真实世界的 OS 会这么干，因为 “Page fault 是阶梯”，可以利用它做很多有益的事情。

当程序发生 page fault 时，OS 应该考虑如何处理，而不是简单粗暴的杀死进程，正如我们遇到问题，要先了解问题才能解决之一样，OS 要处理 page fault，需要了解 page fault 的以下信息：

• 出错的虚拟地址，当出现 page fault 的时候，是由于页表中找不到这个地址对应的 PTE 或者 PTE 无效，这里的出错的虚拟地址值得就是这条"找不到的地址"，XV6 内核会打印出错的虚拟地址，并且这个地址会被保存在 STVAL 寄存器中。
• 出错的原因，查看 RISC-V 文档可知有三种引起 page fault 的原因：load 引起的 page fault；store 引起的 page fault；指令执行引起的 page fault。这个信息存在 SCAUSE 寄存器中，总共有3个类型的原因与page fault 相关，分别是读、写和指令
• 触发 page fault 的指令的地址，即 page fault 在用户空间发生的位置。从上节课可以知道，作为trap处理代码的一部分，这个地址存放在 SEPC 寄存器中，并同时会保存在trapframe->epc 中。

处理 page fault

有了以上三条信息，OS 就有能力处理 page fault 了，xv6 对于 pf 采取了非常保守的处理方式，即直接杀死进程，但是在稍微正式一点的操作系统中都不会这么简单粗暴，因为借助 pf 可以实现很多功能，比如：

• lazy page allocation
• copy-on-write fork（会作为 lab 出现）
• demand paging
• memory mapped files（会作为 lab 出现）

比如Linux就实现了所有的这些功能。

为什么借助 pf 可以实现这些功能，归根到底还是 pf 会导致 trap 到 kernel mode，在 kernel mode 中，就可以做很多“魔法”。下面会依次介绍这些 pf 的处理方式。

Page fault 作用

page fault 是阶梯，触发 page fault 后，我们可以在 page fault handler 中做很多事情，其中最重要的就是“懒加载”，下面的 lazy allocation、Zero Fill On Demand、COW fork 、Demand paging 、Memory mapped 的核心思想都是“懒加载”。

XV6提供了一个系统调用叫 sbrk，这个系统调用的核心实现如下：

uint64
uvmalloc(pagetable_t pagetable, uint64 oldsz, uint64 newsz, int xperm)
{
  char *mem;
  uint64 a;

  if(newsz < oldsz)
    return oldsz;

  oldsz = PGROUNDUP(oldsz);
  for(a = oldsz; a < newsz; a += PGSIZE){
    mem = kalloc();
    if(mem == 0){
      uvmdealloc(pagetable, a, oldsz);
      return 0;
    }
    memset(mem, 0, PGSIZE);
    if(mappages(pagetable, a, PGSIZE, (uint64)mem, PTE_R|PTE_U|xperm) != 0){
      kfree(mem);
      uvmdealloc(pagetable, a, oldsz);
      return 0;
    }
  }
  return newsz;
}

很容易就看明白其中使用 kalloc() 和 mappages() 函数分配物理内存并且在页表中添加新的 PTE（如果看不明白说明 lectrue04：page table 没有学好哦，快来这里复习），所以 sbrk 的作用就是应用程序用来申请新的内存空间

在XV6中，sbrk的实现默认是 eager allocation。即一旦调用了sbrk，内核会立即分配应用程序所需要的物理内存。但是实际上，对于应用程序来说很难预测自己需要多少内存，所以通常来说，应用程序倾向于申请多于自己所需要的内存。以矩阵计算程序为例，程序员需要为最坏的情况做准备，比如说为最大可能的矩阵分配内存，但是应用程序可能永远也用不上这些内存。所以，程序员过多的申请内存但是过少的使用内存，这种情况还挺常见的。

所以就引出了lazy allocation 的概念。核心思想非常简单，摒弃 eager allocation，sbrk 被调用时不会立即分配内存，只是记录一下"假如真的分配了内存，那么现在应用程序可用的内存是多少"（在实际的 xv6 中，这个值是由 p->sz 记录的，他表示堆顶指针）

当应用程序真的用到了新申请的这部分内存，由于没有分配、页表中没有映射，自然找不到相应PTE，这时会触发page fault，但是 kernel 会识别到：要访问 va 小于新的 p->sz，并且大于旧的 p->sz，就知道这是一个当初假装分配的地址，所以这时才会真正分配物理地址并且在用户程序的页表中添加 PTE，所以在 page fault handler 中就会：

• 在page fault handler中，通过kalloc函数分配一个内存page；并初始化这个 page 内容为0；
• 将这个内存 page 映射到 user page table 中；
• 最后重新执行指令（SEPC 寄存器记录了发生 pf 时的地址，所以可以回到“事发地”重新执行指令）

总之，lazy allocation 的核心概念就是“将分配物理内存 page 推迟到了真正访问这个内存 page 时做”。

再次搬出这张图：一个用户程序的内存分布图

但是这张图省略了一点布局，就是除了 text 区域，data 区域，同时还有一个BSS区域，BSS 区域位于 data 区域之后。text 区域存放是程序的指令，data 区域存放的是初始化了的全局变量，BSS 包含了未被初始化或者初始化为0的全局变量。

之所以要创建这个 BSS 区域，是因为作为全局变量，元素初始值都是 0 的情况还是蛮多的，比如在 C 语言中定义了一个大的矩阵作为全局变量，那么它的元素初始值都是 0。由于 BSS 里面保存了未被初始化的全局变量，这里可能有很多 page，但是所有的page内容都为0。每个 page 都需要分配实际的物理内存空间：

但如果采用 Zero Fill On Demand ，那么 BSS 区域的 page 就不需要全部到不同的物理内存上，而是都映射到同一个物理 page 上，之所以能这么做，是因为所有的 page 内容都是 0，所以就可以用一个 page 代替其他 page，但是由于共享了 page，便不能随意写这个 page 了，所以这个 page 的 flag 标志位设置为只读：

如果需要写这个BSS 区域的某个 page（va），由于设置了只读，所以会触发 page fault，这时在 page fault handler 中就会：

• 分配一个新的物理 page，将 va 映射到新的 page 上
• 在新的 page 上执行写指令，而 BSS 区域其他page 依旧映射到原 page 上

fork 机制在第一节已经讲过了，fork会拷贝当前进程的内存，并创建一个新的进程，这里的内存包含了进程的指令和数据。之后，我们就有了两个拥有完全一样内存的进程。

fork 最典型的用法就是和 exec 系统调用一起使用，先调用fork，再在子进程中调用 exec，通过这种方式来运行程序，最典型的就是 shell，我们在 shell 中执行的任何命令，都是 shell 这个进程 fork 出一个子进程，然后在子进程中调用 exec 来运行这个命令。

再来重复一遍这个浪费的过程：fork 创建了 Shell 地址空间的一个完整的拷贝，而 exec 做的第一件事情就是丢弃这个地址空间，取而代之的是一个包含了 echo 的地址空间。

由于fork首先拷贝了整个父进程的内存，但是之后exec整个将这个拷贝丢弃了，所以这里的拷贝，显得有些浪费（双押23333）：

而 Copy On Write Fork 就是解决这个浪费问题的，他的核心思想依旧很简单：当我们创建子进程时，直接共享父进程的物理内存page，而不是分配新的内存 page。即直接设置子进程的 PTE 指向父进程对应的物理内存 page，和 zero fill on demand 一样，由于共享了物理 page，父进程和子进程的 PTE 的标志位都应该设置成只读的，这样写这个 page 时才会触发 page fault

当父进程或者子进程写这些共享的地址时，就会触发 page fault，page fault handler 就会

1. 复制出错的 page 并重新映射

2. 在新 page 上写

3. 将复制的 page 和原 page 的标志位修改为可写（原来是只读）

关于 COW fork 还有两个重要的细节：

1. 当发生page fault时，我们其实是在向一个只读的地址执行写操作。内核如何能分辨现在是一个 copy-on-write fork 的场景，而不是应用程序在向一个正常的只读地址写数据？

   这其实是个共性的问题

   在 lazy allocation 中，我们如何知道是向 PTE 找不到是因为本该分配的 lazy 了，还是确实没找到？答案是根据访问地址判断：如果要访问的 va < 新的 p->sz 且 > 旧的 p->sz，说明是 lazy 的情况。

   在 zero fill on demand 中，如何能分辨现在是一个 zero fill on demand 的场景，而不是应用程序在向一个正常的只读地址写数据？答案也是根据 va 判断，va 是否是 BSS 段的 page，如果是则说明是一个 zero fill on demand 的场景

   那么在 COW fork 中也一样，还记得 RISC-V 中一条 PTE 有10 bit 的辅助位把，其中 8、9bit 是保留位，我们可以使用其中的任意一个 bit 作为“这是 COW page ”的标记：

2. 第二个细节是 page 释放时要小心翼翼，因为共享物理 page 的存在，每次释放 page 时都要确保没有进程引用这些 page，所以需要有一个引用计数器来统计当前有多少个进程在使用这个 page，只有引用计数器为 0，才可以释放 page

这里老师讲的十分模糊，核心依旧是 lazy 的思想，我认为关键在于细节，但教授没有给出更多细节，这里推荐一篇博客：

这个后面会有 mmap lab （也是本课程最后一个 lab）来实现相应的功能，所以我打算干脆放在那里一起复习。

Lab5 ：COW fork 心得

这个 lab 要求实现 COW fork，xv6 已经实现了一个 eager allocation 的 fork，而本次要求将这种实现修改为 COW fork，推迟实际的物理内存的分配，直到真正使用要使用的时候，才会复制物理内存页。

以下是一些需要注意的细节：

1. 每个 page 的引用计数存在哪里？我第一反应是 map，key 是 page 的地址，value 是引用计数，但 lab 提示可以使用一个数组来存储，每个 page 的引用计数索引可以使用 页的物理地址/4096 来索引数组。

2. COW fork 要求实际使用 page 时，复制原 page，而且要将原来的 page 和新 page 的标志位改为可写，但是值得注意的是，对于那些本来就使只读的（例如代码段），不论在旧页还是新页中，应该依旧保持它的只读性，那些试图对这样一个只读页进行写入的进程应该被杀死。

   实际这里的处理更加巧妙，让我们仔细梳理一下这个正常的流程：

   1. 装模作样 fork 的时候（只创建页表，并且在页表中添加 pte），pte 需要打 cow 标志位，并且清除 W 标志位，使其只读

   2. 这样写这个 page 时会触发 pf（写入了只读 page ），并且由 cow bit 得知这是 cow 页，不能直接杀死进程，需要懒复制

   3. 但有一种情况就是，这个 cow page 本身就是只读的，而不是清除了 W 标志位之后才只读，所以这时即使是 cow page 也需要杀死进程

   正常的想法是利用 PTE 中一个保留 bit 记录一下这个 page 本身就是只读的，这样在 pf 之后，如果是 cow page，只需要再判断一下这个保留位，本身只读就直接杀死，否则正常进行 cow 的实际复制过程

   但实际写代码时并不需要这个保留位来记录，采用另一种更巧妙的写法：在 fork 时，如果判断这个 page 是只读的，干脆就不给他打 cow 标志（这样就能保证所有的 cow page 原来都是可写的），所以触发 pf 后就可以直接杀死进程，这样和触发 pf 后、判断 cow、判断原来就是只读的效果是一样的，都是直接杀死。

3. cow page 的处理一定要小心翼翼，lab 提示要在 copyout() 函数中，如遇到 cow page，也要采取相应的策略，这里的关键问题就是想清楚为什么会影响到 copyout() 函数，因为 copyout 函数是用来将内核地址空间的 page 复制到用户地址空间，如果目的地的用户地址是一个 cow page，说明这个 page 不能被写入，但是这时没有任何 page fault 发生来触发 cow_handler，所以就需要我们在copyout() 函数中主动检查这一点

查看 fork 函数的源码，会发现复制内存的核心函数是：uvmcopy(p->pagetable, np->pagetable, p->sz)，所以我们知道要修改这个函数，让这个函数不再真正分配 page，而是只在子进程的页表中映射父进程的 page。

int uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
  pte_t *pte;
  uint64 pa, i;
  uint flags;
  // char *mem;
    // 从这里也能看出来 fork 时父进程是从地址 0 开始一直到 p-sz，复制到子进程
  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);
    // if((mem = kalloc()) == 0)
    //   goto err;
    // memmove(mem, (char*)pa, PGSIZE);
    // if(mappages(new, i, PGSIZE, (uint64)mem, flags) != 0){
    //   kfree(mem);
    //   goto err;
    // }
    // 父进程 page 可写， 绝妙之处！
    if((*pte) & PTE_W) {
      // 添加 COW 标志位、清除可写标志位
      flags = (flags | PTE_COW)  & (~PTE_W);
      *pte = (*pte & ~PTE_W) | PTE_COW;
    }
    // 子进程页表添加映射
    if(mappages(new, i, PGSIZE, pa, flags) != 0){
      //kfree((void *)pa);
      goto err;
    }
    krefincr((void *)pa);

  }
  return 0;

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

以上连续注释掉的代码就是原代码，即真正分配物理 page 的代码，而紧接着下面的代码就是实现只添加 PTE 、而不分配 page 的代码

由于我们在父进程和子进程的页表中都设置了只读标志位，所以触发 pf 需要有进程对这个 page 进行写。出错的原因信息存在 SCAUSE 寄存器中，在 [trap 的流程](MIT6.s081/6.828 lectrue5/6：System call entry/exit 以及 Lab4 心得 - byFMH - 博客园 (cnblogs.com))中我们已经知道，一旦 trap，就会进入 trampoline.S 代码，trampoline.S 又会跳到 usertrap()，所以我们需要在 usertrap()代码中判断 SCAUSE 寄存器 的值：

可以看出当写 page 时触发 pf 时，scause 寄存器的值是 15：

if(r_scause() == 15) {
    uint64 va = r_stval();
    // ** If virtual address is over maximum va size or within guard page, kill the process
    if (va >= MAXVA || (va < p->trapframe->sp && va >= (p->trapframe->sp - PGSIZE)))
      p->killed = 1;
    if (cow_handler(p->pagetable, PGROUNDDOWN(va)) == -1)
      p->killed = 1;
 }

在cow_handler就要进行实际的 page 分配，但这里也要注意判断 page 的引用，如果引用只有 1，那么也无需复制了，直接将 page 修改为可写即可

int cow_handler(pagetable_t pagetable, uint64 va) {
  pte_t *pte;
  void *new_pa;
  uint flags;

    // ** va must be PGSIZE aligned
  if ((va % PGSIZE) != 0) return -1;

  // ** safety check
  if (va >= MAXVA) return -1;

  pte = walk(pagetable, va, 0);
  if (pte == 0) return -1;

  uint64 pa = PTE2PA(*pte);
  if (pa == 0) return -1;

  if(*pte & PTE_COW) {// cow page，uvmcopy 已经初始化，有 cow bit 一定没有 w bit
    int cnt = krefget((void *)pa);

    if(cnt == 1) {// 唯一引用，直接修改标志位让其顺利写，我认为这里是我多虑了，应该不会有这种情况，如果是 cow page ，引用至少为 2
      *pte = (*pte | PTE_W) & (~PTE_COW);
    } else if(cnt > 1) {// 多个引用，不能随意写，需要复制新页，这里的代码属于原 uvmcopy
        new_pa = kalloc();
        memmove(new_pa, (char*)pa, PGSIZE);

        flags = PTE_FLAGS(*pte);
        flags = (flags | PTE_W) & (~PTE_COW);

        uvmunmap(pagetable, PGROUNDDOWN(va), 1, 0);
        mappages(pagetable, va, PGSIZE, (uint64)new_pa, flags);

        krefdecr((void *)pa);// va 已经映射到 new_pa了，所以原 pa 引用计数减 1

    } else {//
      printf("cnt < 0\n");
      return -1;
    }

  } else if(!(*pte & PTE_COW) && (*pte & PTE_W)){// 没有 cow bit 、有 w bit，但依旧触发 pf，不是此函数的职责
      return 0;
  } else if(!(*pte & PTE_COW) && !(*pte & PTE_W)){// 没有 cow bit 且没有 w bit，直接杀死
      printf("cnt < 0\n");
      return -1;
  }
  return 0;
}

最后在 copyout()函数中也要有相应的处理，至于为什么已经在前面分析过了：

// in copyout
if(uvmcheckcowpage(va0)) {
  cow_handler(pagetable, va0);
}

另外还有一些 引用计数 方面的修改细节，入 kallock 时 page 的计数初始化为 1，mappage 后引用计数++，kfree 后引用计数--等

OK，以上就是 MIT6.s081/6.828 lectrue07：Page faults 的所有内容了，这节课程的确很涨见识，page fault 是阶梯，借助它可以实现灵活的 page table 映射，或者说得掉书袋一些就是：实现虚拟内存的动态分配~

获得更好的阅读体验，这里是我的博客，欢迎访问：byFMH - 博客园

所有代码见：我的GitHub实现（记得切换到相应分支）