Qifan Wang
The Jungle Book
A blog for programming

MIT 6.S081 Lecture 7: Page faults

What is an ocean but a multitude od drops.

6.S081第七课，讲述以页错误为代表的异常，并教授OS以页表和页错误实现的许多虚拟内存的优化机制。阅读RISC-V Calling Convention第四章第六节部分，观看课程视频。

Page faluts in risc-v exceptions

Xv6对于异常的处理十分简单，来自用户态的异常导致内核kill用户进程，来自内核态的异常导致内核 panic 。而 RISC-V 原生支持 16 种异常（这十六种其实也包括了系统调用，这也是我上一节提到的，所谓不同 Trap 之间的”用语混淆”），控制状态寄存器 scause 记录不同类型。其中有 12 ， 13 与 15 号与分页有关，均为页错误。

Exception Code Description
0 Instruction address misaligned
1 Instruction access fault
2 Illegal instruction
3 Breakpoint
4 Reserved
5 Load access fault
6 AMO address misaligned
7 Store/AMO access fault
8 Environment call
9-11 Reserved
12 Instruction page fault
13 Load page fault
14 Reserved
15 Store/AMO page fault
>16 Reserved

而 CSR stval 记录异常特定的信息。有些异常类型不会用到，将 stval 置零；页错误会将其置为页错误的地址。

发生页错误，OS需要获取信息，

  1. 引发页错误的虚拟地址记录于 stval 中。
  2. 引发页错误的类型记录在 scause 中。12 -> 取指令；13 -> 读数据；15 -> 写数据。
  3. 错误发生的IP与CPU优先级分别记录在 trapframe 的 epc 字段与 CSR sstatus 的 SPP 位中。

Optimizations

通过页错误与页表可以实现很多OS 虚拟内存的特性。课程介绍了几种，我小小记录一下。

lazy/on-demand page allocation

系统调用 sbrk 分配堆上内存，但应用可能申请的堆内存没有使用，比如输入缓冲区在应用运行时只用到部分。如果申请太多内存，调用 sbrk 可能过于昂贵，比如物理内存已经大部分使用或用完，再申请大量内存需要等待换页。

现代OS一般是 lazily 分配内存。具体就是当用户进程使用内存时再分配。比如实现系统调用 sbrk ，可以先调整进程的堆大小，当进程使用这块新内存时，OS发生页错误再分配物理内存，并重新执行错误的治理那个。如此可以使用更少内存，如果不用就没有页错误，也没有分配。本质上，这将一次性内存申请分摊到未来多次的页错误上。

注意，以上优化也是针对堆分配的特点。如果是栈分配，肯定不能如此实现。因为栈空间较小，而且是立刻使用，会引起过多密集的页错误。

one zero-filled page

用户进程常常使用大量内容为 0 的内存，例如，C的全局变量，全局数组初始化。在 CSAPP 这一段内存是 bss (block starting symbol 或称为 better saved space) 段。因此，内核将这块内存的页内容初始化为 0 。

现代OS一个技巧是，专门分配一个内容为 0 的页。当内核需要 zeor-filled 页时，将虚拟地址映射到这个特殊页，并设为 copy-on-write ；当需要写这块内存时，再真实分配一页用于写，并替换原来的映射，设为 r/w 权限。

copy-on-write fork

系统调用 fork 往往紧接着 exec 调用。如果内核为子进程真实分配物理页，之后也会被 exec 替换整个页表，造成无用功。

现代OS一般在实现 fork 时，让父进程和子进程共享所有物理页，但每个PTE都将它们映射为只读(清除PTE W标志)。父子进程可以从共享物理内存中读取数据。如果其中任何一个写入给定的页面，CPU将引发一个页面错误异常，由内核分配一个物理页用于写，并修改原来父子进程页表中的映射。

demand paging

简单看，系统调用 exec 将整个程序文件映像从磁盘载入内存。这个过程代价很高，花费时间（如果文件存在低速磁盘上就更慢了），而且不是所有文件内容都立刻使用。

OS优化可以将载入文件实现为按需载入页面，在页表中映射，但不真实分配物理页；发生页错误后，再从文件读入页，分配物理页并更新页表。实现这类优化需要物理页的磁盘定位元信息，这种信息一般在结构 virtual memory area （VMA）中。

用户进程可能需要超过物理内存的内存空间。OS一般将地址空间不常用的页置于磁盘，通过地址空间频繁换页实现。换页可能策略常用的有 LRU (Least recently used)。PTE 的 PTE_A 位可以帮助实现LRU。

memory-mapped files

OS通常使用系统调用 read ，write 与 lseek 读写文件。其实也可以将文件载入内存，读写内存来读写文件。如此不用如调用 lseek 每次改变 offset。Unix 提供 mmap 系统调用实现文件映射到内存。读写时，内核按需 page-in 文件映射页；当物理内存满了，page-out 不最近使用的文件映射页。

shared virtual memory

一般共享内存是一台机器上进程间通信的方式。而课程提及的共享虚拟内存是指不同机器的进程共享内存，通过网络分享 Distributed Memory。这属于分布式内容。

TLB management

CPU通过TLB缓存使用的物理页。Xv6在切换user/kernel时需要刷新整个TLB，因为内核页表与用户空间页表隔离，之前的缓存肯定用不上。

RISC-V提供许多精细化控制TLB的机制。

  1. PTE_G为global TLB bits不需要被刷新。例如，Xv6的trampoline由于被进程与内核共享，且用于陷入/离开内核，就可以设置为 PTE_G 存放于TLB中不被刷新。
  2. ASID (Address space identifier) 用于区分不同的地址空间。TLB entries 有 ASID 标记，内核的部分页可以选择性刷新。CSR satp 也保存 ASID 信息，指令 sfence.vma 也可以使用 ASID 选择性刷新TLB。

Conclusion

由于异常处理流程在上一节课基本覆盖，这节课讲页错误以及页表实现的各种OS优化技巧。虚拟内存的机制仍在不断演化，比较早的如支持 large page，支持 eXecute 标记位，最近的如支持五级页表，支持 ASID等。

有意思的是，Linux为了缓和Meltdown漏洞影响，开始支持KPTI以隔离内核与进程地址空间。Xv6通过内核独立页表基本上也实现了KPTI。维基的记录表明，为了安全需要 KPTI ，但又一定程度上牺牲了陷入内核的效率。从中我们也可以学习内核设计的取舍。

Reference

  1. MIT 6.S081 2021
  2. RISC-V Calling Convention
  3. Videos
  4. [Meltdown(security vulnerability)](https://en.wikipedia.org/wiki/Meltdown_(security_vulnerability)
  5. Kernel page table isolation

Table of Contents