MIT 6.S081 (BOOK-RISCV-REV1)教材第四章内容 -- Trap -- 下

MIT 6.S081 教材第四章内容 -- Trap -- 下

引言

MIT 6.S081 2020 操作系统

本文为MIT 6.S081课程第四章教材内容翻译加整理。

本课程前置知识主要涉及:

• C语言(建议阅读C程序语言设计—第二版)
• RISC-V汇编
• 推荐阅读: 程序员的自我修养-装载，链接与库

从内核空间陷入

xv6根据执行的是用户代码还是内核代码，对CPU陷阱寄存器的配置有所不同。当在CPU上执行内核时，内核将stvec指向kernelvec(kernel/kernelvec.S:10)的汇编代码。

stvec指向kernelvec的设置有如下两处,分别是trap模块初始化和用户态切换到内核的中的时候:

由于xv6已经在内核中，kernelvec可以依赖于设置为内核页表的satp，以及指向有效内核栈的栈指针。kernelvec保存所有寄存器，以便被中断的代码最终可以不受干扰地恢复。

kernelvec将寄存器保存在被中断的内核线程的栈上，这是有意义的，因为寄存器值属于该线程。如果陷阱导致切换到不同的线程，那这一点就显得尤为重要——在这种情况下，陷阱将实际返回到新线程的栈上，将被中断线程保存的寄存器安全地保存在其栈上。

为什么内核发生的trap可以将寄存器环境保存在内核栈上，而不是像用户态一样，保存在属于内核的trapframe中呢？

• 用户态需要这样做是因为要将内核态与用户态隔离，因此内核态要避免访问用户栈，因为用户栈由用户程序维护，内核未必了解用户栈的布局结构，因此内核态为了保存用户态寄存器环境，采用了trapframe实现
• 内核栈由内核态负责维护，所以可以完全信任，也就无需再单独开启trapframe存放内核态寄存器环境了

Kernelvec在保存寄存器后跳转到kerneltrap(kernel/trap.c:134)。

kerneltrap为两种类型的陷阱做好了准备：

• 设备中断和异常。
• 它调用devintr(kernel/trap.c:177)来检查和处理前者。
• 如果陷阱不是设备中断，则必定是一个异常，内核中的异常将是一个致命的错误；
• 内核调用panic并停止执行。

如果由于计时器中断而调用了kerneltrap，并且一个进程的内核线程正在运行（而不是调度程序线程），kerneltrap会调用yield，给其他线程一个运行的机会。在某个时刻，其中一个线程会让步，让我们的线程和它的kerneltrap再次恢复。第7章解释了yield中发生的事情。

xv6中是一个用户态线程绑定到一个内核态线程，在这种情况下，可以简单看做是一个线程具有两种不同的执行状态，因为其不涉及多个用户线程绑定一个内核线程，或者多对多绑定等更复杂的场景。

当kerneltrap的工作完成后，它需要返回到任何被陷阱中断的代码。因为一个yield可能已经破坏了保存的sepc和在sstatus中保存的前一个状态模式，因此kerneltrap在启动时保存它们。

从yield返回继续执行会等到当前线程让出CPU使用权，下一次被调度执行时。

它现在恢复这些控制寄存器并返回到kernelvec(kernel/kernelvec.S:48)。kernelvec从栈中弹出保存的寄存器并执行sret，将sepc复制到pc并恢复中断的内核代码。

值得思考的是，如果内核陷阱由于计时器中断而调用yield，陷阱返回是如何发生的。

当CPU从用户空间进入内核时，xv6将CPU的stvec设置为kernelvec；您可以在usertrap(kernel/trap.c:29)中看到这一点。

内核执行时有一个时间窗口(usertrapret)，将stvec设置为uservec，在该窗口中禁用设备中断至关重要。幸运的是，RISC-V总是在开始设置陷阱时禁用中断，xv6在设置stvec之前不会再次启用中断。

页面错误异常

Xv6对异常的响应相当无趣: 如果用户空间中发生异常，内核将终止故障进程。如果内核中发生异常，则内核会崩溃。真正的操作系统通常以更有趣的方式做出反应。

例如，许多内核使用页面错误来实现写时拷贝版本的fork——copy on write (COW) fork。要解释COW fork，请回忆第3章内容：

• xv6的fork通过调用uvmcopy(kernel/vm.c:309) 为子级分配物理内存，并将父级的内存复制到其中，使子级具有与父级相同的内存内容。
• 如果父子进程可以共享父级的物理内存，则效率会更高。
• 然而武断地实现这种方法是行不通的，因为它会导致父级和子级通过对共享栈和堆的写入来中断彼此的执行。

由页面错误驱动的COW fork可以使父级和子级安全地共享物理内存。当CPU无法将虚拟地址转换为物理地址时，CPU会生成页面错误异常。Risc-v有三种不同的页面错误:

• 加载页面错误 (当加载指令无法转换其虚拟地址时)
• 存储页面错误 (当存储指令无法转换其虚拟地址时)
• 指令页面错误 (当指令的地址无法转换时)

scause寄存器中的值指示页面错误的类型，stval寄存器包含无法翻译的地址。

• COW fork中的基本计划是让父子最初共享所有物理页面，但将它们映射为只读。
• 因此，当子级或父级执行存储指令时，risc-v CPU引发页面错误异常。
• 为了响应此异常，内核复制了包含错误地址的页面。
• 它在子级的地址空间中映射一个权限为读/写的副本，在父级的地址空间中映射另一个权限为读/写的副本。
• 更新页表后，内核会在导致故障的指令处恢复故障进程的执行。
• 由于内核已经更新了相关的PTE以允许写入，所以错误指令现在将正确执行。

COW策略对fork很有效，因为通常子进程会在fork之后立即调用exec，用新的地址空间替换其地址空间。在这种常见情况下，子级只会触发很少的页面错误，内核可以避免拷贝父进程内存完整的副本。此外，COW fork是透明的: 无需对应用程序进行任何修改即可使其受益。

除COW fork以外，页表和页面错误的结合还开发出了广泛有趣的可能性。另一个广泛使用的特性叫做惰性分配——*lazy allocation。*它包括两部分内容：

• 首先，当应用程序调用sbrk时，内核增加地址空间，但在页表中将新地址标记为无效。
• 其次，对于包含于其中的地址的页面错误，内核分配物理内存并将其映射到页表中。
• 由于应用程序通常要求比他们需要的更多的内存，惰性分配可以称得上一次胜利
• 内核仅在应用程序实际使用它时才分配内存。
• 像COW fork一样，内核可以对应用程序透明地实现此功能。

利用页面故障的另一个广泛使用的功能是从磁盘分页。如果应用程序需要比可用物理RAM更多的内存，内核可以换出一些页面:

• 将它们写入存储设备 (如磁盘)，并将它们的PTE标记为无效。
• 如果应用程序读取或写入被换出的页面，则CPU将触发页面错误。
• 然后内核可以检查故障地址。
• 如果该地址属于磁盘上的页面，则内核分配物理内存页面，将该页面从磁盘读取到该内存，将PTE更新为有效并引用该内存，然后恢复应用程序。
• 为了给页面腾出空间，内核可能需要换出另一个页面。
• 此功能不需要对应用程序进行更改，并且如果应用程序具有引用的地址 (即，它们在任何给定时间仅使用其内存的子集)，则该功能可以很好地工作。

结合分页和页面错误异常的其他功能包括自动扩展栈空间和内存映射文件。

本节，我们简单页面错误是如何处理的，以及它的用处，下面补充视频内容并辅以代码进行讲解。

Page Fault Basics

通过page fault可以实现的一系列虚拟内存功能：

• lazy allocation
• copy-on-write fork
• demand paging
• memory mapped files

Linux就实现了所有的这些功能。然而在XV6中，一旦用户空间进程触发了page fault，会导致进程被杀掉。这是非常保守的处理方式。

在这节中，我们将会探讨在发生page fault时可以做的一些有趣的事情。这节对于代码的讲解会比较少，相应的在设计层面会有更多的内容，毕竟我们也没有代码可以讲解（因为XV6中没有实现）。

在继续接下来的内容之前，我们先来回顾一下虚拟内存有的两个主要优点：

• 第一个是Isolation，隔离性。虚拟内存使得操作系统可以为每个应用程序提供属于它们自己的地址空间。所以一个应用程序不可能有意或者无意的修改另一个应用程序的内存数据。虚拟内存同时也提供了用户空间和内核空间的隔离性。
• 另一个好处是level of indirection，提供了一层抽象。处理器和所有的指令都可以使用虚拟地址，而内核会定义从虚拟地址到物理地址的映射关系。这一层抽象是我们这节要讨论的许多有趣功能的基础。不过到目前为止，在XV6中内存地址的映射都比较无聊，实际上在内核中基本上是直接映射（注，也就是虚拟地址等于物理地址）。当然也有几个比较有意思的地方：
  • trampoline page，它使得内核可以将一个物理内存page映射到多个用户地址空间中。
  • guard page，它同时在内核空间和用户空间用来保护Stack。

到目前为止，我们介绍的内存地址映射相对来说比较静态。不管是user page table还是kernel page table，都是在最开始的时候设置好，之后就不会再做任何变动。

page fault可以让这里的地址映射关系变得动态起来。通过page fault，内核可以更新page table，这是一个非常强大的功能。因为现在可以动态的更新虚拟地址这一层抽象，结合page table和page fault，内核将会有巨大的灵活性。我们接下来会看到各种各样利用动态变更page table实现的有趣的功能。

但是在那之前，首先，我们需要思考的是，什么样的信息对于page fault是必须的。或者说，当发生page fault时，内核需要什么样的信息才能够响应page fault：

• 很明显的，我们需要出错的虚拟地址，或者是触发page fault的源。
  • 可以假设的是，你们在page table lab中已经看过一些相关的panic，所以你们可能已经知道，当出现page fault的时候，XV6内核会打印出错的虚拟地址，并且这个地址会被保存在STVAL寄存器中。

  

  • 所以，当一个用户应用程序触发了page fault，page fault会使用与上节课介绍的相同的trap机制，将程序运行切换到内核，同时也会将出错的地址存放在STVAL寄存器中。这是我们需要知道的第一个信息。
• 我们需要知道的第二个信息是出错的原因，我们或许想要对不同场景的page fault有不同的响应。
  • 不同的场景是指，比如因为load指令触发的page fault、因为store指令触发的page fault又或者是因为jump指令触发的page fault
  • 所以实际上如果你查看RISC-V的文档，在SCAUSE（注，Supervisor cause寄存器，保存了trap机制中进入到supervisor mode的原因）寄存器的介绍中，有多个与page fault相关的原因。
  • 比如，13表示是因为load引起的page fault；
  • 15表示是因为store引起的page fault；
  • 12表示是因为指令执行引起的page fault。
  • 所以第二个信息存在SCAUSE寄存器中，其中总共有3个类型的原因与page fault相关，分别是读、写和指令。
  • ECALL进入到supervisor mode对应的是8，这是我们在上节课中应该看到的SCAUSE值。基本上来说，page fault和其他的异常使用与系统调用相同的trap机制来从用户空间切换到内核空间。
  • 如果是因为page fault触发的trap机制并且进入到内核空间，STVAL寄存器和SCAUSE寄存器都会有相应的值。

• 我们或许想要知道的第三个信息是触发page fault的指令的地址。从上节课可以知道，作为trap处理代码的一部分，这个地址存放在SEPC（Supervisor Exception Program Counter）寄存器中，并同时会保存在trapframe->epc中。

所以，从硬件和XV6的角度来说，当出现了page fault，现在有了3个对我们来说极其有价值的信息，分别是：

• 引起page fault的内存地址
• 引起page fault的原因类型
• 引起page fault时的程序计数器值，这表明了page fault在用户空间发生的位置

我们之所以关心触发page fault时的程序计数器值，是因为在page fault handler中我们或许想要修复page table，并重新执行对应的指令。理想情况下，修复完page table之后，指令就可以无错误的运行了。所以，能够恢复因为page fault中断的指令运行是很重要的。

接下来我们将查看不同虚拟内存功能的实现机制，来帮助我们理解如何利用page fault handler修复page table并做一些有趣的事情。

Lazy page allocation

我们首先来看一下内存allocation，或者更具体的说sbrk。sbrk是XV6提供的系统调用，它使得用户应用程序能扩大自己的heap。当一个应用程序启动的时候，sbrk指向的是heap的最底端，同时也是stack的最顶端。这个位置通过代表进程的数据结构中的sz字段表示，这里以p->sz表示。

当调用sbrk时，它的参数是整数，代表了你想要申请的page数量（注，原视频说的是page，但是根据Linux man page，实际中sbrk的参数是字节数）。sbrk会扩展heap的上边界（也就是会扩大heap）。

//sysproc.c
uint64
sys_sbrk(void)
{
  int addr;
  int n;

  if(argint(0, &n) < 0)
    return -1;
  addr = myproc()->sz;
  // 从a0参数寄存器取出sbrk函数的参数---参数单位是字节
  if(growproc(n) < 0)
    return -1;
  return addr;
}

相关函数之前页表节已经讲解过,这里不多展开

//proc.c

// Grow or shrink user memory by n bytes.
// Return 0 on success, -1 on failure.
int
growproc(int n)
{
  uint sz;
  struct proc *p = myproc();

  sz = p->sz;
  if(n > 0){
    //参数: 当前进程用户态根页表,oldsize,newsize
    if((sz = uvmalloc(p->pagetable, sz, sz + n)) == 0) {
      return -1;
    }
  } else if(n < 0){
    sz = uvmdealloc(p->pagetable, sz, sz + n);
  }
  p->sz = sz;
  return 0;
}

// Allocate PTEs and physical memory to grow process from oldsz to
// newsz, which need not be page aligned.  Returns new size or 0 on error.
uint64
uvmalloc(pagetable_t pagetable, uint64 oldsz, uint64 newsz)
{
  char *mem;
  uint64 a;

  if(newsz < oldsz)
    return oldsz;
  // 向上对齐--可以确保最终分配的得到的大小一定大于等于newsz
  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);
    //参数: 页表,虚拟地址,要映射的虚拟地址范围,对应物理地址,pte权限
    if(mappages(pagetable, a, PGSIZE, (uint64)mem, PTE_W|PTE_X|PTE_R|PTE_U) != 0){
      kfree(mem);
      uvmdealloc(pagetable, a, oldsz);
      return 0;
    }
  }
  return newsz;
}

这意味着，当sbrk实际发生或者被调用的时候，内核会分配一些物理内存，并将这些内存映射到用户应用程序的地址空间，然后将内存内容初始化为0，再返回sbrk系统调用。这样，应用程序可以通过多次sbrk系统调用来增加它所需要的内存。类似的，应用程序还可 以通过给sbrk传入负数作为参数，来减少或者压缩它的地址空间。不过在这节课我们只关注增加内存的场景。

在XV6中，sbrk的实现默认是eager allocation。这表示了，一旦调用了sbrk，内核会立即分配应用程序所需要的物理内存。但是实际上，对于应用程序来说很难预测自己需要多少内存，所以通常来说，应用程序倾向于申请多于自己所需要的内存。这意味着，进程的内存消耗会增加许多，但是有部分内存永远也不会被应用程序所使用到。

你或许会认为这里很蠢，怎么可以这样呢？

• 你可以设想自己写了一个应用程序，读取了一些输入然后通过一个矩阵进行一些运算。
• 你需要为最坏的情况做准备，比如说为最大可能的矩阵分配内存，但是应用程序可能永远也用不上这些内存
• 通常情况下，应用程序会在一个小得多的矩阵上进行运算。
• 所以，程序员过多的申请内存但是过少的使用内存，这种情况还挺常见的。

原则上来说，这不是一个大问题。但是使用虚拟内存和page fault handler，我们完全可以用某种更聪明的方法来解决这里的问题，这里就是利用lazy allocation:

• 核心思想非常简单，sbrk系统调基本上不做任何事情，唯一需要做的事情就是提升p->sz，将p->sz增加n,其中n是需要新分配的内存page数量(视频里面说的是page数量，但是代码中是字节数，当然其实都可以)。
• 但是内核在这个时间点并不会分配任何物理内存。之后在某个时间点，应用程序使用到了新申请的那部分内存，这时会触发page fault，因为我们还没有将新的内存映射到page table。
• 所以，如果我们解析一个大于旧的p->sz，但是又小于新的p->sz（注，也就是旧的p->sz + n）的虚拟地址，我们希望内核能够分配一个内存page，并且重新执行指令。

所以，当我们看到了一个page fault，相应的虚拟地址小于当前p->sz，同时大于stack，那么我们就知道这是一个来自于heap的地址，但是内核还没有分配任何物理内存。

所以对于这个page fault的响应也理所当然的直接明了：

• 在page fault handler中，通过kalloc函数分配一个内存page；
• 初始化这个page内容为0；
• 将这个内存page映射到user page table中；
• 最后重新执行指令。

比方说，如果是load指令，或者store指令要访问属于当前进程但是还未被分配的内存，在我们映射完新申请的物理内存page之后，重新执行指令应该就能通过了。

在eager allocation的场景，一个进程可能消耗了太多的内存进而耗尽了物理内存资源。如果我们不使用eager allocation，而是使用lazy allocation，应用程序怎么才能知道当前已经没有物理内存可用了？

• 从应用程序的角度来看，会有一个错觉：存在无限多可用的物理内存。但是在某个时间点，应用程序可能会用光了物理内存，之后如果应用程序再访问一个未被分配的page，但这时又没有物理内存，这时内核可以有两个选择，稍后会介绍更复杂的那个。你们在lazy lab中要做的是，返回一个错误并杀掉进程。因为现在已经OOM（Out Of Memory）了，内核也无能为力，所以在这个时间点可以杀掉进程。

如何判断一个地址是新分配的内存还是一个无效的地址？

• 在地址空间中，我们有stack，data和text。通常来说我们将p->sz设置成一个更大的数，新分配的内存位于旧的p->sz和新的p->sz之间，但是这部分内存还没有实际在物理内存上进行分配。如果使用的地址低于p->sz，那么这是一个用户空间的有效地址。如果大于p->sz，对应的就是一个程序错误，这意味着用户应用程序在尝试解析一个自己不拥有的内存地址。

为什么我们需要杀掉进程？操作系统不能只是返回一个错误说现在已经OOM了，尝试做一些别的操作吧。

• 在XV6的page fault中，我们默认会直接杀掉进程，但是这里的处理可以更加聪明。实际的操作系统的处理都会更加聪明，尽管如此，如果最终还是找不到可用内存，实际的操作系统还是可能会杀掉进程。

为了进一步理解lazy allocation，我们大概来看一下它的代码会是怎么样？

1. 我们首先要修改的是sys_sbrk函数，sys_sbrk会完成实际增加应用程序的地址空间，分配内存等等一系列相关的操作,这里我们要修改这个函数，让它只对p->sz加n，并不执行增加内存的操作。

//sysproc.c

uint64
sys_sbrk(void)
{
  int addr;
  int n;

  if(argint(0, &n) < 0)
    return -1;
  addr = myproc()->sz;
  myproc()->sz=addr+n;
  //if(growproc(n) < 0)
  //  return -1;
  return addr;
}

1. 修改完之后启动XV6，并且执行“echo hi”，我们会得到一个page fault。

之所以会得到一个page fault是因为，在Shell中执行程序，Shell会先fork一个子进程，子进程会通过exec执行echo。在这个过程中，Shell会申请一些内存，所以Shell会调用sys_sbrk，然后就出错了（注，因为前面修改了代码，调用sys_sbrk不会实际分配所需要的内存）。

这里输出的内容包含了一些有趣的信息：

• 这里输出了SCAUSE寄存器内容，我们可以看到它的值是15，表明这是一个store page fault（详见8.1）。
• 我们可以看到进程的pid是3，这极可能是Shell的pid。
• 我们还可以看到SEPC寄存器的值，是0x12a6。
• 最后还可以看到出错的虚拟内存地址，也就是STVAL寄存器的内容，是0x4008。

我们可以查看Shell的汇编代码，这是由Makefile创建的。我们搜索SEPC对应的地址，可以看到这的确是一个store指令。这看起来就是我们出现page fault的位置:

如果我们向前看汇编代码，我们可以看到page fault是出现在malloc的实现代码中。这也非常合理，在malloc的实现中，我们使用sbrk系统调用来获得一些内存，之后会初始化我们刚刚获取到的内存，在0x12a4位置，刚刚获取的内存中写入数据，但是实际上我们在向未被分配的内存写入数据。

我们接下来看看如何能够聪明的处理这里的page fault：

• 首先查看trap.c中的usertrap函数，在usertrap中根据不同的SCAUSE完成不同的操作

在trap一节中，我们是因为SCAUSE == 8进入的trap，这是我们处理普通系统调用的代码。如果SCAUSE不等于8，接下来会检查是否有任何的设备中断，如果有的话处理相关的设备中断。如果两个条件都不满足，这里会打印一些信息，并且杀掉进程。

现在我们需要增加一个检查，判断SCAUSE == 15，如果符合条件，我们需要一些定制化的处理。我们这里想要做什么样的定制化处理呢？

• 在上面增加的代码中，首先打印一些调试信息。之后分配一个物理内存page，如果ka等于0，表明没有物理内存我们现在OOM了，我们会杀掉进程。
• 如果有物理内存，首先会将内存内容设置为0，之后将物理内存page指向用户地址空间中合适的虚拟内存地址。
• 具体来说，我们首先将虚拟地址向下取整，这里引起page fault的虚拟地址是0x4008，向下取整之后是0x4000。
• 之后我们将物理内存地址跟取整之后的虚拟内存地址的关系加到page table中。
• 对应的PTE需要设置常用的权限标志位，在这里是u，w，r bit位。

接下来运行一些这部分代码。先重新编译XV6，再执行“echo hi”，我们或许可以乐观的认为现在可以正常工作了：

但是实际上并没有正常工作。我们这里有两个page fault，第一个对应的虚拟内存地址是0x4008，但是很明显在处理这个page fault时，我们又有了另一个page fault 0x13f48。现在唯一的问题是，uvmunmap在报错，一些它尝试unmap的page并不存在。这里unmap的内存是什么？

• 这里unmap的是之前lazy allocated，但是又还没有用到的地址。所以对于这个内存，并没有对应的物理内存。所以在uvmunmap函数中，当PTE的v标志位为0并且没有对应的mapping，这并不是一个实际的panic，这是我们预期的行为。

实际上，对于这个page我们并不用做任何事情，我们可以直接continue跳到下一个page:

接下来，我们再重新编译XV6，并执行“echo hi”:

现在我们可以看到2个page fault，但是echo hi正常工作了。

为什么在uvmunmap中可以直接改成continue？

• 之前的panic表明，我们尝试在释放一个并没有map的page。
• 怎么会发生这种情况呢？
  • 唯一的原因是sbrk增加了p->sz，但是应用程序还没有使用那部分内存。
  • 因为对应的物理内存还没有分配，所以这部分新增加的内存的确没有映射关系。
  • 我们现在是lazy allocation，我们只会为需要的内存分配物理内存page。
  • 如果我们不需要这部分内存，那么就不会存在map关系，这非常的合理。
  • 相应的，我们对于这部分内存也不能释放，因为没有实际的物理内存可以释放，所以这里最好的处理方式就是continue，跳过并处理下一个page。

这部分内容对于下一个实验有很大的帮助，实际上这是下一个实验3个部分中的一个，但是很明显这部分不足以完成下一个lazy lab。我们这里做了一些修改，但是很多地方还是有可能出错。就像有人提到的，我这里并没有检查触发page fault的虚拟地址是否小于p->sz。还有其他的可能出错的地方吗？

• 通过sbrk增加的用户进程的内存数是一个整型数而不是一个无符号整型数，可能会传入负数。
• 使用负数，这意味着缩小用户内存。当我们在缩小用户内存时，我们也需要小心一些。实际上，在一个操作系统中，我们可能会在各种各样的用户场景中使用这里的PTE，对于不同的用户场景我们或许需要稍微修改XV6，这就是接下来的lazy lab的内容。你们需要完成足够多的修改，才能通过所有的测试用例。

Zero Fill On Demand

当你查看一个用户程序的地址空间时，存在text区域，data区域，同时还有一个BSS区域（注，BSS区域包含了未被初始化或者初始化为0的全局或者静态变量）。当编译器在生成二进制文件时，编译器会填入这三个区域。text区域是程序的指令，data区域存放的是初始化了的全局变量，BSS包含了未被初始化或者初始化为0的全局变量。

之所以这些变量要单独列出来，是因为例如你在C语言中定义了一个大的矩阵作为全局变量，它的元素初始值都是0，为什么要为这个矩阵分配内存呢？

• 其实只需要记住这个矩阵的内容是0就行。

在一个正常的操作系统中，如果执行exec，exec会申请地址空间，里面会存放text和data。因为BSS里面保存了未被初始化的全局变量，这里或许有许多许多个page，但是所有的page内容都为0。

通常可以调优的地方是，我有如此多的内容全是0的page，在物理内存中，我只需要分配一个page，这个page的内容全是0。然后将所有虚拟地址空间的全0的page都map到这一个物理page上。这样至少在程序启动的时候能节省大量的物理内存分配。

当然这里的mapping需要非常的小心，我们不能允许对于这个page执行写操作，因为所有的虚拟地址空间page都期望page的内容是全0，所以这里的PTE都是只读的。之后在某个时间点，应用程序尝试写BSS中的一个page时，比如说需要更改一两个变量的值，我们会得到page fault。那么，对于这个特定场景中的page fault我们该做什么呢？

• 假设store指令发生在BSS最顶端的page中。
• 我们想要做的是，在物理内存中申请一个新的内存page，将其内容设置为0，因为我们预期这个内存的内容为0。
• 之后我们需要更新这个page的mapping关系，首先PTE要设置成可读可写，然后将其指向新的物理page。这里相当于更新了PTE，之后我们可以重新执行指令。

为什么这是一个好的优化？或者说为什么操作系统要这么做？

• 这里类似于lazy allocation。假设程序申请了一个大的数组，来保存可能的最大的输入，并且这个数组是全局变量且初始为0。但是最后或许只有一小部分内容会被使用。
• 第二个好处是在exec中需要做的工作变少了。程序可以启动的更快，这样你可以获得更好的交互体验，因为你只需要分配一个内容全是0的物理page。所有的虚拟page都可以映射到这一个物理page上。

但是因为每次都会触发一个page fault，update和write会变得更慢吧？

• 这是个很好的观点，所以这里实际上我们将一些操作推迟到了page fault再去执行。并且我们期望并不是所有的page都被使用了。如果一个page是4096字节，我们只需要对每4096个字节消耗一次page fault即可。但是这里是个好的观点，我们的确增加了一些由page fault带来的代价。

page fault的代价是多少呢？我们该如何看待它？这是一个与store指令相当的代价，还是说代价要高的多？

• 在页表节中我们已经看到了，仅仅是在trap处理代码中，就有至少有100个store指令用来存储当前的寄存器。除此之外，还有从用户空间转到内核空间的额外开销。所以，page fault并不是没有代价的。

Copy On Write Fork

当Shell处理指令时，它会通过fork创建一个子进程。fork会创建一个Shell进程的拷贝，所以这时我们有一个父进程（原来的Shell）和一个子进程。Shell的子进程执行的第一件事情就是调用exec运行一些其他程序，比如运行echo。现在的情况是，fork创建了Shell地址空间的一个完整的拷贝，而exec做的第一件事情就是丢弃这个地址空间，取而代之的是一个包含了echo的地址空间。这里看起来有点浪费。

• fork调用

// Create a new process, copying the parent.
// Sets up child kernel stack to return as if from fork() system call.
int
fork(void)
{
  int i, pid;
  struct proc *np;
  struct proc *p = myproc();

  // Allocate process.
  if((np = allocproc()) == 0){
    return -1;
  }

  // Copy user memory from parent to child.
  // copy父进程叶子页表的所有pte到子进程页表,同时copy物理页-->此时未实现COW
  if(uvmcopy(p->pagetable, np->pagetable, p->sz) < 0){
    freeproc(np);
    release(&np->lock);
    return -1;
  }
  // copy brk指针
  np->sz = p->sz;
  // 建立进程树关系
  np->parent = p;

  // copy saved user registers.
  // 拷贝trapframe中保存的用户态寄存器
  *(np->trapframe) = *(p->trapframe);

  // Cause fork to return 0 in the child.
  // 让fork调用返回给子进程0
  np->trapframe->a0 = 0;

  // increment reference counts on open file descriptors.
  // copy父进程打开的文件列表,同时增加文件引用计数 
  for(i = 0; i < NOFILE; i++)
    if(p->ofile[i])
      np->ofile[i] = filedup(p->ofile[i]);
  // copy父进程当前工作目录    
  np->cwd = idup(p->cwd);
  // copy父进程程序名
  safestrcpy(np->name, p->name, sizeof(p->name));
  
  pid = np->pid;
  // 设置子进程为待调度状态
  np->state = RUNNABLE;

  release(&np->lock);
  // fork调用返回给父进程的结果为子进程pid
  return pid;
}

• uvmcopy完成父进程页表copy

// Given a parent process's page table, copy
// its memory into a child's page table.
// Copies both the page table and the
// physical memory.
// returns 0 on success, -1 on failure.
// frees any allocated pages on failure.
// 给出父进程页表,copy父进程页表内容和页表中pte映射的物理页内容到子进程页表中
int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
  pte_t *pte;
  uint64 pa, i;
  uint flags;
  char *mem;
  // 拷贝父进程虚拟地址空间范围: 0~sz
  for(i = 0; i < sz; i += PGSIZE){
    // 存在未映射虚拟地址,抛出异常
    if((pte = walk(old, i, 0)) == 0)
      panic("uvmcopy: pte should exist");
    // pte无效  
    if((*pte & PTE_V) == 0)
      panic("uvmcopy: page not present");
    // 得到pte指向的物理页地址
    pa = PTE2PA(*pte);
    // 拿到pte权限位
    flags = PTE_FLAGS(*pte);
    // 为子进程分配物理页
    if((mem = kalloc()) == 0)
      goto err;
    // copy 父进程pte指向的物理页内容   
    memmove(mem, (char*)pa, PGSIZE);
    // copy 父进程页表pte内容-->在子进程中页表中将虚拟地址映射到指向新分配的物理页
    if(mappages(new, i, PGSIZE, (uint64)mem, flags) != 0){
      kfree(mem);
      goto err;
    }
  }
  return 0;

 err:
  // 解除已经在子进程页表中建立的映射关系
  uvmunmap(new, 0, i / PGSIZE, 1);
  return -1;
}

所以，我们最开始有了一个父进程的虚拟地址空间，然后我们有了子进程的虚拟地址空间。在物理内存中，XV6中的Shell通常会有4个page，当调用fork时，基本上就是创建了4个新的page，并将父进程page的内容拷贝到4个新的子进程的page中。

copy的是父进程0~sbrk指针范围的虚地址范围。

但是之后，一旦调用了exec，我们又会释放这些page，并分配新的page来包含echo相关的内容。所以对于这个特定场景有一个非常有效的优化：

• 当我们创建子进程时，与其创建，分配并拷贝内容到新的物理内存，其实我们可以直接共享父进程的物理内存page。
• 所以这里，我们可以设置子进程的PTE指向父进程对应的物理内存page。

当然，再次要提及的是，我们这里需要非常小心。因为一旦子进程想要修改这些内存的内容，相应的更新应该对父进程不可见，因为我们希望在父进程和子进程之间有强隔离性，所以这里我们需要更加小心一些。为了确保进程间的隔离性，我们可以将这里的父进程和子进程的PTE的标志位都设置成只读的。

在某个时间点，当我们需要更改内存的内容时，我们会得到page fault。因为父进程和子进程都会继续运行，而父进程或者子进程都可能会执行store指令来更新一些全局变量，这时就会触发page fault，因为现在在向一个只读的PTE写数据。

在得到page fault之后，我们需要拷贝相应的物理page：

• 假设现在是子进程在执行store指令，那么我们会分配一个新的物理内存page，然后将page fault相关的物理内存page拷贝到新分配的物理内存page中，并将新分配的物理内存page映射到子进程。
• 这时，新分配的物理内存page只对子进程的地址空间可见，所以我们可以将相应的PTE设置成可读写，并且我们可以重新执行store指令。
• 实际上，对于触发刚刚page fault的物理page，因为现在只对父进程可见，相应的PTE对于父进程也变成可读写的了。

所以现在，我们拷贝了一个page，将新的page映射到相应的用户地址空间，并重新执行用户指令。重新执行用户指令是指调用userret函数，也即是trap节中介绍的返回到用户空间的方法。

对于一些没有父进程的进程，比如系统启动的第一个进程，它会对于自己的PTE设置成只读的吗？还是设置成可读写的，然后在fork的时候再修改成只读的？

• 这取决于你。实际上在lazy lab之后，会有一个copy-on-write lab。在这个lab中，你自己可以选择实现方式。当然最简单的方式就是将PTE设置成只读的，当你要写这些page时，你会得到一个page fault，之后你可以再按照上面的流程进行处理。

因为我们经常会拷贝用户进程对应的page，内存硬件有没有实现特定的指令来完成拷贝，因为通常来说内存会有一些读写指令，但是因为我们现在有了从page a拷贝到page b的需求，会有相应的拷贝指令吗？

• x86有硬件指令可以用来拷贝一段内存。但是RISC-V并没有这样的指令。当然在一个高性能的实现中，所有这些读写操作都会流水线化，并且按照内存的带宽速度来运行。
• 在我们这个例子中，我们只需要拷贝1个page，对于一个未修改的XV6系统，我们需要拷贝4个page。所以这里的方法明显更好，因为内存消耗的更少，并且性能会更高，fork会执行的更快。

当发生page fault时，我们其实是在向一个只读的地址执行写操作。内核如何能分辨现在是一个copy-on-write fork的场景，而不是应用程序在向一个正常的只读地址写数据。是不是说默认情况下，用户程序的PTE都是可读写的，除非在copy-on-write fork的场景下才可能出现只读的PTE？

• 内核必须要能够识别这是一个copy-on-write场景。几乎所有的page table硬件都支持了这一点。我们之前并没有提到相关的内容，下图是一个常见的多级page table。对于PTE的标志位，之前介绍过第0bit到第7bit，但是没有介绍最后两位RSW。
• 这两位保留给supervisor software使用，supervisor softeware指的就是内核。内核可以随意使用这两个bit位。所以可以做的一件事情就是，将bit8标识为当前是一个copy-on-write page。

• 当内核在管理这些page table时，对于copy-on-write相关的page，内核可以设置相应的bit位，这样当发生page fault时，我们可以发现如果copy-on-write bit位设置了，我们就可以执行相应的操作了。否则的话，比如说lazy allocation，我们就做一些其他的处理操作。
• 在copy-on-write lab中，你们会使用RSW在PTE中设置一个copy-on-write标志位。

在copy-on-write lab中，还有个细节需要注意：

• 目前在XV6中，除了trampoline page外，一个物理内存page只属于一个用户进程。
• trampoline page永远也不会释放，所以也不是什么大问题。
• 但是对于这里的物理内存page，现在有多个用户进程或者说多个地址空间都指向了相同的物理内存page
• 举个例子:
  • 当父进程退出时我们需要更加的小心，因为我们要判断是否能立即释放相应的物理page。
  • 如果有子进程还在使用这些物理page，而内核又释放了这些物理page，我们将会出问题。
• 那么现在释放内存page的依据是什么呢？
  • 我们需要对于每一个物理内存page的引用进行计数，当我们释放虚拟page时，我们将物理内存page的引用数减1，如果引用数等于0，那么我们就能释放物理内存page。所以在copy-on-write lab中，你们需要引入一些额外的数据结构或者元数据信息来完成引用计数。

真的有必要额外增加一位来表示当前的page是copy-on-write吗？因为内核可以维护有关进程的一些信息…

• 是的，你可以在管理用户地址空间时维护一些其他的元数据信息，这样你就知道这部分虚拟内存地址如果发生了page fault，那么必然是copy-on-write场景。实际上，在后面的一个实验中，你们需要出于相同的原因扩展XV6管理的元数据。在你们完成这些实验时，具体的实现是很自由的。

Demand Paging

我们回到exec，在未修改的XV6中，操作系统会加载程序内存的text，data区域，并且以eager的方式将这些区域加载进page table。

这里的eager指的是分lazy aollcation的实现方式

但是根据我们在lazy allocation和zero-filled on demand的经验，为什么我们要以eager的方式将程序加载到内存中？为什么不再等等，直到应用程序实际需要这些指令的时候再加载内存？

• 程序的二进制文件可能非常的巨大，将它全部从磁盘加载到内存中将会是一个代价很高的操作。
• 又或者data区域的大小远大于常见的场景所需要的大小，我们并不一定需要将整个二进制都加载到内存中。

所以对于exec，在虚拟地址空间中，我们为text和data分配好地址段，但是相应的PTE并不对应任何物理内存page。对于这些PTE，我们只需要将valid bit位设置为0即可。

如果我们修改XV6使其按照上面的方式工作，我们什么时候会得到第一个page fault呢？或者说，用户应用程序运行的第一条指令是什么？用户应用程序在哪里启动的？

应用程序是从地址0开始运行。text区域从地址0开始向上增长。位于地址0的指令是会触发第一个page fault的指令，因为我们还没有真正的加载内存。

那么该如何处理这里的page fault呢？

• 首先我们可以发现，这些page是on-demand page。
• 我们需要在某个地方记录了这些page对应的程序文件，我们在page fault handler中需要从程序文件中读取page数据，加载到内存中；
• 之后将内存page映射到page table；
• 最后再重新执行指令。

之后程序就可以运行了。在最坏的情况下，用户程序使用了text和data中的所有内容，那么我们将会在应用程序的每个page都收到一个page fault。但是如果我们幸运的话，用户程序并没有使用所有的text区域或者data区域，那么我们一方面可以节省一些物理内存，另一方面我们可以让exec运行的更快（注，因为不需要为整个程序分配内存）。

前面描述的流程其实是有点问题的。我们将要读取的文件，它的text和data区域可能大于物理内存的容量。又或者多个应用程序按照demand paging的方式启动，它们二进制文件的和大于实际物理内存的容量。对于demand paging来说，假设内存已经耗尽了或者说OOM了，这个时候如果得到了一个page fault，需要从文件系统拷贝中拷贝一些内容到内存中，但这时你又没有任何可用的物理内存page，这其实回到了之前的一个问题：

• 在lazy allocation中，如果内存耗尽了该如何办？

如果内存耗尽了，一个选择是撤回page（evict page）:

• 比如说将部分内存page中的内容写回到文件系统再撤回page。
• 一旦你撤回并释放了page，那么你就有了一个新的空闲的page，你可以使用这个刚刚空闲出来的page，分配给刚刚的page fault handler，再重新执行指令。

重新运行指令稍微有些复杂，这包含了整个userret函数背后的机制以及将程序运行切换回用户空间等等。

以上就是常见操作系统的行为。这里的关键问题是，什么样的page可以被撤回？并且该使用什么样的策略来撤回page？

• Least Recently Used

Least Recently Used，或者叫LRU。除了这个策略之外，还有一些其他的小优化。如果你要撤回一个page，你需要在dirty page和non-dirty page中做选择。dirty page是曾经被写过的page，而non-dirty page是只被读过，但是没有被写过的page。你们会选择哪个来撤回？

• 如果选择dirty page,那么需要考虑其之后再被修改，现在你或许需要对它写两次了（注，一次内存，一次文件），现实中会选择non-dirty page。
• 如果non-dirty page出现在page table中，你可以将内存page中的内容写到文件中，之后将相应的PTE标记为non-valid，这就完成了所有的工作。之后你可以在另一个page table重复使用这个page。所以通常来说这里优先会选择non-dirty page来撤回。

如果你们再看PTE，我们有RSW位，你们可以发现在bit7，对应的就是Dirty bit。当硬件向一个page写入数据，会设置dirty bit，之后操作系统就可以发现这个page曾经被写入了。类似的，还有一个Access bit，任何时候一个page被读或者被写了，这个Access bit会被设置。

没有被Access过的page可以直接撤回，是吗？

• 如果你想实现LRU，你需要找到一个在一定时间内没有被访问过的page，那么这个page可以被用来撤回。而被访问过的page不能被撤回。所以Access bit通常被用来实现这里的LRU策略。

那是不是要定时的将Access bit恢复成0？

• 是的，这是一个典型操作系统的行为。操作系统会扫描整个内存，这里有一些著名的算法例如clock algorithm，就是一种实现方式。

为什么需要恢复这个bit？

• 如果你想知道page最近是否被使用过，你需要定时比如每100毫秒或者每秒清除Access bit，如果在下一个100毫秒这个page被访问过，那你就知道这个page在上一个100毫秒中被使用了。
• 而Access bit为0的page在上100毫秒未被使用。这样你就可以统计每个内存page使用的频度，这是一个成熟的LRU实现的基础。（注，可以通过Access bit来决定内存page 在LRU中的排名）

Memory Mapped Files

最后要讨论的内容，也是后面的一个实验，就是memory mapped files。这里的核心思想是，将完整或者部分文件加载到内存中，这样就可以通过内存地址相关的load或者store指令来操纵文件。

• 为了支持这个功能，一个现代的操作系统会提供一个叫做mmap的系统调用。这个系统调用会接收一个虚拟内存地址（VA），长度（len），protection，一些标志位，一个打开文件的文件描述符，和偏移量（offset）。

• 这里的语义就是，从文件描述符对应的文件的偏移量的位置开始，映射长度为len的内容到虚拟内存地址VA，同时我们需要加上一些保护，比如只读或者读写。
• 假设文件内容是读写并且内核实现mmap的方式是eager方式（不过大部分系统都不会这么做），内核会从文件的offset位置开始，将数据拷贝到内存，设置好PTE指向物理内存的位置。之后应用程序就可以使用load或者store指令来修改内存中对应的文件内容。
• 当完成操作之后，会有一个对应的unmap系统调用，参数是虚拟地址（VA），长度（len）。来表明应用程序已经完成了对文件的操作，在unmap时间点，我们需要将dirty block写回到文件中。我们可以很容易的找到哪些block是dirty的，因为它们在PTE中的dirty bit为1。

当然，在任何聪明的内存管理机制中，所有的这些都是以lazy的方式实现。你不会立即将文件内容拷贝到内存中，而是先记录一下这个PTE属于这个文件描述符。相应的信息通常在VMA结构体中保存，VMA全称是Virtual Memory Area。

• 例如对于这里的文件f，会有一个VMA，在VMA中我们会记录文件描述符，偏移量等等，这些信息用来表示对应的内存虚拟地址的实际内容在哪，这样当我们得到一个位于VMA地址范围的page fault时，内核可以从磁盘中读数据，并加载到内存中。
• 所以这里回答之前一个问题，dirty bit是很重要的，因为在unmap中，你需要向文件回写dirty block。

有没有可能多个进程将同一个文件映射到内存，然后会有同步的问题？

• 这个问题其实等价于，多个进程同时通过read/write系统调用读写一个文件会怎么样？
• 这里的行为是不可预知的。write系统调用会以某种顺序出现，如果两个进程向一个文件的block写数据，要么第一个进程的write能生效，要么第二个进程的write能生效，只能是两者之一生效。在这里其实也是一样的，所以我们并不需要考虑冲突的问题。
• 一个更加成熟的Unix操作系统支持锁定文件，你可以先锁定文件，这样就能保证数据同步。但是默认情况下，并没有同步保证。

mmap的参数中，len和flag是什么意思？

• len是文件中你想映射到内存中的字节数。prot是read/write。flags会在mmap lab中出现，我认为它表示了这个区域是私有的还是共享的。如果是共享的，那么这个区域可以在多个进程之间共享。

如果其他进程直接修改了文件的内容，那么是不是意味着修改的内容不会体现在这里的内存中？

• 是的。但是如果文件是共享的，那么你应该同步这些变更。

真实世界

如果内核内存被映射到每个进程的用户页表中（带有适当的PTE权限标志），就可以消除对特殊蹦床页面的需求。这也将消除在从用户空间捕获到内核时对页表切换的需求。

这反过来也将允许内核中的系统调用实现利用当前进程正在映射的用户内存，允许内核代码直接解引用用户指针。许多操作系统已经使用这些想法来提高效率。Xv6避免了这些漏洞，以减少由于无意中使用用户指针而导致内核中出现安全漏洞的可能性，并降低了确保用户和内核虚拟地址不重叠所需的一些复杂性。

最后来总结一下最近几节课的内容，我们首先详细看了一下page table是如何工作的，之后我们详细看了一下trap是如何工作的。而page fault结合了这两部分的内容，可以用来实现非常强大且优雅的虚拟内存功能。一个典型的操作系统实现了今天讨论的所有内容，如果你查看Linux，它包含了所有的内容，以及许多其他有趣的功能。今天的内容希望能给让你们理解，一旦你可以在page fault handler中动态的更新page table，虚拟内存将会变得有多强大。