Page faults

---

Page Fault Basics

这节课的主要内容是page fault以及通过它实现的一系列虚拟内存功能，包括lazy allocation、copy-on-write fork、demand paging、memory mapped files。但在xv6中这些都没实现，采用的是直接杀掉进程的非常保守的处理方式。

我们认为虚拟内存有两个主要的优点：

• 一个是Isolation，隔离性。虚拟内存既提供了应用程序之间的隔离，也提供了用户空间和内核空间的隔离。

• 另一个是Level of indirection，提供了一层抽象，处理器和所有指令都可以使用虚拟地址，而内核会定义从虚拟地址到物理地址的映射关系。

目前的地址映射基本是静态的，即开始的时候设置好，之后基本不会再做变动。而page fault可以让地址映射关系变得动态起来，通过page fault，内核可以更新page table，这可以提供很多有趣的功能。

当发生page fault时，内核需要哪些信息才能响应它呢？

• 首先是出错的虚拟地址，即触发page fault的源。当出现page fault时，xv6内核会使用trap机制，打印出错的虚拟地址，这个地址会被保存在STVAL寄存器中。

• 然后是出错的原因类型。这个被存储在SCAUSE中，由RISC-V的文档定义。

• 还有触发page fault指令的程序计数器的值，这表明page fault在用户空间发生的位置。它存放在SEPC中，并且也在trapframe->epc中。

关注程序计数器值是因为在page fault handler中我们希望修复page table并重新执行对应指令。

---

Lazy page allocation

sbrk系统调用是xv6提供给用户应用程序扩大自己的heap用的。当一个应用程序启动时，sbrk指向的是heap的最底端，同时也是stack的最顶端。这个位置通过代表进程的数据结构中的sz字段表示，在proc.h中。后面我们记作p->sz。

xv6中栈是一个PAGESIZE大小，而堆在栈之上，可以增长。

// Per-process state
struct proc {
  struct spinlock lock;

  // p->lock must be held when using these:
  enum procstate state;        // Process state
  void *chan;                  // If non-zero, sleeping on chan
  int killed;                  // If non-zero, have been killed
  int xstate;                  // Exit status to be returned to parent's wait
  int pid;                     // Process ID

  // wait_lock must be held when using this:
  struct proc *parent;         // Parent process

  // these are private to the process, so p->lock need not be held.
  uint64 kstack;               // Virtual address of kernel stack
  uint64 sz;                   // Size of process memory (bytes)
  pagetable_t pagetable;       // User page table
  struct trapframe *trapframe; // data page for trampoline.S
  struct usyscall *usyscall; // in memlayout.h
  struct context context;      // swtch() here to run process
  struct file *ofile[NOFILE];  // Open files
  struct inode *cwd;           // Current directory
  char name[16];               // Process name (debugging)
};

当调用sbrk时，它的参数是n，代表你想申请的page数量，sbrk会扩展heap的上边界，内核会分配一些物理内存，并将其映射到用户应用程序的地址空间，然后将内存内容初始化为0，再返回。

Linux manual page中sbrk的参数是字节数。

xv6中，sbrk的实现方式是eager allocation，即一旦调用sbrk，内核会立即分配应用程序需要的物理内存。这种实现方式的坏处在于应用程序基本都倾向于申请多于需要的内存，这会导致一定程度的资源浪费。

特性	预先分配（Eager）	惰性分配（Lazy）
分配时机	申请时立即分配物理内存	首次访问内存时分配物理内存（触发缺页中断）
内存利用率	可能浪费内存（分配后未使用的页）	按需分配，利用率较高
性能开销	启动时开销大（需立即分配）	运行时延迟（处理缺页中断）
确定性	内存访问无额外延迟，适合实时系统	延迟不确定，可能影响实时性

不过基于虚拟内存和page fault handler，我们可以利用lazy allocation来解决。sbrk系统调用提升p->sz，将它增加n，但是内核在这个时间点并不分配任何物理内存；当应用程序使用到了新申请的那部分内存时，触发page fault。

这个page fault中，触发的虚拟地址小于当前的p->sz，同时大于stack，因此这是一个来自heap的地址，但内核还没有分配任何物理内存。这样的话page fault handler只需要通过kalloc函数分配一个内存page，初始化内容为0，然后将它映射到user page table中，最后重新执行指令即可。

这种方法下，从应用程序的角度看，会有一个错觉，即存在无限多可用的物理内存，内核需要解决这个问题。

修改sys_sbrk函数，让它只对p->sz加n，并不执行增加内存的操作。

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

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

然后启动xv6，执行echo hi，可以得到一个page fault：

xv6 kernel is booting

hart 1 starting
hart 2 starting
init: starting sh
$ echo hi
usertrap(): unexpected scause 0xf pid=3
            sepc=0x11ae stval=0x5008
va=20480 pte=0
panic: uvmunmap: not mapped

在Shell中执行程序时，它会先fork一个子进程，然后子进程通过exec执行echo。在这个过程中，它会申请一些内存，调用sys_sbrk，然后导致这个错误。

错误信息里，可以看到scause寄存器的值是15，表明它是一个store page fault；进程的pid是3，这大概是Shell的pid；sepc寄存器的值是0x11ae；最后出错的虚拟地址是stval的内容0x5008。

查看sh.asm汇编代码：

hp->s.size = nu;
    11ae:	01652423          	sw	s6,8(a0)

可以看到这确实是一个store指令，另外还能注意到这个page fault出现在malloc的汇编代码中。在malloc中会用sbrk系统调用来获得一些内存，然后初始化刚刚获取的内存，在0x11ae位置刚刚获取的内存中写入数据，但实际上是在向未分配的内存写入数据。

然后在usertrap需要增加一个scause==15的检查并做一些特殊处理，这里只做了一个示例处理。

void
usertrap(void)
{
  int which_dev = 0;

  if((r_sstatus() & SSTATUS_SPP) != 0)
    panic("usertrap: not from user mode");

  // send interrupts and exceptions to kerneltrap(),
  // since we're now in the kernel.
  w_stvec((uint64)kernelvec);

  struct proc *p = myproc();
  
  // save user program counter.
  p->trapframe->epc = r_sepc();
  
  if(r_scause() == 8){
    // system call

    if(killed(p))
      exit(-1);

    // sepc points to the ecall instruction,
    // but we want to return to the next instruction.
    p->trapframe->epc += 4;

    // an interrupt will change sepc, scause, and sstatus,
    // so enable only now that we're done with those registers.
    intr_on();

    syscall();
  } else if((which_dev = devintr()) != 0){
    // ok
  } else if (r_scause() == 15){
    uint64 va = r_stval();
    printf("usertrap(): page fault va %p\n", (void *)va);
    uint64 ka = (uint64) kalloc();
    if (ka == 0){
      p->killed = 1;
    } else {
      memset((char*)ka, 0, PGSIZE);
      if (mappages(p->pagetable, va, PGSIZE, ka, PTE_R | PTE_W | PTE_X) != 0){
        kfree((void*)ka);
        p->killed = 1;
      }
    }
  } else {
    printf("usertrap(): unexpected scause 0x%lx pid=%d\n", r_scause(), p->pid);
    printf("            sepc=0x%lx stval=0x%lx\n", r_sepc(), r_stval());
    setkilled(p);
  }

  if(killed(p))
    exit(-1);

  // give up the CPU if this is a timer interrupt.
  if(which_dev == 2)
    yield();

  usertrapret();
}

首先打印一些调试信息，然后分配一个物理内存page。如果ka等于0，则表明没有物理内存即现在OOM（Out Of Memory）了，那我们会杀掉进程；而如果有物理内存，则首先把内存内容设置为0，然后将物理内存page指向用户地址空间中合适的虚拟内存地址并设置权限标志位。现在重新尝试一下：

xv6 kernel is booting

hart 2 starting
hart 1 starting
init: starting sh
$ echo hi
page fault 0x0000000000005008
page fault 0x0000000000014f48
panic: uvmunmap: not mapped

但是还是有问题，第一个page fault对应的虚拟地址是0x5008，但是在处理这个page fault的时候，出现了第二个page fault位于0x14f48。uvmunmap报错说明它尝试unmap的page不存在。

这里unmap的是之前lazy allocation但还没有用到的地址，因此这个内存并没有对应的物理地址，在uvmunmap中触发了：

if((*pte & PTE_V) == 0)
      panic("uvmunmap: not mapped");

但实际上对这个page我们可以不管它，直接跳到下一个即可。

if((*pte & PTE_V) == 0)
      continue;

然后再运行，可以发现两个page fault后输出hi正常工作了。

xv6 kernel is booting

hart 2 starting
hart 1 starting
init: starting sh
$ echo hi
page fault 0x0000000000005008
page fault 0x0000000000014f48
hi

这就是一个最简单的lazy allocation了。

uvmunmap函数在进程退出、执行新程序时都会别调用来释放空间。

但是这个实现仍然有很多可能出错，比如没有检查触发page fault的虚拟地址是否小于p->sz；另外sys_sbrk中的n是int型，有可能是负数，意味着缩小用户内存。这些都还需要完善。

---

Zero Fill On Demand

下一个功能是zero-fill-on-demand。

一个用户程序的地址空间，有text区域，data区域，和BBS区域。当编译器生成二进制文件时，编译器会填入这三个区域，text区域存放程序的指令，data区域存放初始化的全局变量，BBS区域则包含未被初始化或初始化为0的全局和静态变量。

这些变量单独列出来是因为这样不用为它们分配内存

在操作系统中，如果执行exec，它会申请地址空间，里面存放text和data，而BBS里面保存了未被初始化的全局变量，这里面可能会有很多内容为0的page。

因此我们可以进行优化，在物理内存中只需要分配一个page，这个page的内容全是0，然后将所有虚拟地址空间中全0的page都映射到这一个物理页上，这样至少在程序启动时可以节省大量的物理内存分配。

不过这里映射时，我们不能允许对这个页进行写操作。当后面应用程序尝试写BBS中的一个page时，就会触发page fault。

对于这个page fault，我们需要在物理内存中申请一个新的内存页，将其内容设置为0，然后要更新这个page的映射关系，设置成可读可写，并将它指向新申请的物理页，最后重新执行指令。

这个优化一方面可以节省一部分内存，另一方面exec的工作变少了，程序可以更快启动。但相应的，write或其他相关的会变得更慢，因为它们都要触发page fault，这比store慢的多，store可能需要消耗实际访问RAM，但page fault需要进入内核。

---

Copy On Write Fork

这个优化也被称为COW fork。

当Shell处理指令时，会通过fork创建一个子进程，fork会创建一个Shell进程的拷贝；这个子进程执行的第一件事就是调用exec运行一些其他程序，如echo。但现在fork创建了Shell地址空间的一个完整的拷贝，而exec做的第一件事就是丢弃这个地址空间，而用一个包含echo的地址空间取代它，这有些浪费。

具体来说，xv6的Shell 通常有4个page，调用fork会创建4个新的page，并复制父进程的到子进程中。但是调用exec时，我们又会释放这些page，并分配新的page来包含echo相关的内容。

对于这个场景一个有效的优化是：在创建子进程时共享父进程的物理内存page，即将子进程的PTE指向父进程对应的物理内存页。当然了，我们仍然需要保证两个进程之间的强隔离性，可以把两个进程的PTE标志位都设置成只读。

当我们需要修改内存的内容时，我们会得到page fault。这时需要拷贝相应的物理page。代码会先分配一个新的物理内存page，然后将page fault的相关物理内存页拷贝到这个里，并将它映射到子进程，设置标志位为可读写。这时父进程的标志位也可以设置为可读写了。这时再重新执行用户指令即可。

重新执行用户指令是调用userret函数。

PTE的标志位中有两位RSW，这两位保留给supervisor software使用，可以将它标识为当前是一个copy-on-write page，以给page fault分辨。

另外值得注意的是，这里的物理内存页可能是多对一的情况，多个用户进程指向相同的物理内存页。这时需要判断在一个进程退出时是否能立即释放相应的物理页，我们对每一个物理内存页的引用进行计数，为0时才可释放。

---

Demand Paging

exec中，操作系统会加载程序内存的text、data区域，并以eager的方式将它们加载进page table。但这里我们同样可以考虑lazy的方式。

我们可以在虚拟地址空间中为text和data分配好地址段，但相应的PTE并不对应任何物理内存页，只需将它们的PTE_V设置为0即可。

应用程序会从地址0开始，这里的指令会触发第一个page fault。对这个情况，我们需要先从程序文件中读取数据，然后加载到物理内存中，将内存页映射到页表，再重新执行指令。

当出现OOM的情况，一个选择是撤回并释放page，这里最常用的策略是Least Recently Used。对于dirty page（被写过）和non-dirty page（只被读过），我们会选择non-dirty page撤回。这是因为dirty page必须写回磁盘，而non-dirty page直接修改标志位即可。PTE中有dirty bit和access bit标志位。

操作系统会定时扫描整个内存，将access bit恢复成0，这里有一些如clock algorithm之类的算法实现。

---

Memory Mapped Files

这部分的思想是，将文件的一部分或者全部映射到进程的虚拟地址空间，这样就可以通过内存地址相关的load或者store指令来直接操纵文件，而无需传统的read、write系统调用。

现代操作系统会提供一个mmap系统调用，它接受一个虚拟内存地址VA、长度len、内存保护权限prot、一些标志位flags、一个打开文件的文件描述符fd和偏移量offset。它从文件描述符对应文件的偏移量的位置开始，映射一定长度的内容到虚拟内存地址，并加上一些保护，然后设置好PTE指向物理内存的位置。完成后有一个对应的unmap系统调用，这时需要将dirty block写回到文件中，通过PTE中的dirty bit识别即可。

以lazy方式实现的话，不会立即将文件内容拷贝到内存中，首先会记录一下PTE属于这个文件描述符，然后有一个VMA（Virtual Memory Area）结构体，这里面记录文件描述符、偏移量等信息，用来表示对应的内存虚拟地址的实际内容在哪。这样当我们得到一个位于VMA地址范围的page fault时，内核可以从磁盘中读取数据，并加载到内存中。

---

总结

这里应该内存部分的课程内容就全部结束了吧，后面还有几个Lab。虚拟内存这部分是我这门课遇到的第一个坎，这三节花了很长很长时间。

这节课中Frans说了好几次，当我们理解page fault handler中可以动态更新page table，才能理解虚拟内存有多强大。确实上到这里才意识到page fault handler才是整个虚拟内存系统的核心枢纽，通过它可以实现非常多高级的内存管理功能，这些功能主要在于它赋予了虚拟内存系统非常高的灵活性，可以随时按照需求调整，同时还能保存安全与隔离。