Page faults
# 1. Page fault 基础
今天介绍 page fault,以及通过 page fault 可以实现的一系列虚拟内存的功能:
- lazy allocation
- copy-on-write fork
- demand paging
- memory mapped files
几乎所有正经的 OS 都实现了这些功能,比如 Linux。但在 xv6 中,这些功能一个都没实现。一旦用户进程触发 page fault,那就会导致进程被杀掉,这是一个非常保守的处理方式。
这节课将探讨发生 page fault 时可以做的一些有趣的事情,这些功能也是后续的 lab 内容,我们将会花一些时间来研究他们。
在这之前,我们先回顾一下虚拟内存,它的两个主要优点是:
- Isolation。提供了多个用户程序、内核空间与用户空间的隔离性。
- level of indirection。处理器和所有指令都可以使用虚拟地址,而内核会定义从虚拟地址到物理地址的映射关系。这一层抽象是我们这节课要讨论的许多有趣功能的基础。
在之前,xv6 中的内存地址映射很无聊,基本上都是直接映射(也就是 VA = PA)。
之前我们介绍的内存地址映射相对来说比较静态,也就是 user page table 和 kernel page table 都在最开始就设置后,后面基本不做变动了。而 page fault 就让地址映射关系变得动态起来。通过 page fault,内核可以更新 page table,这是一个非常强大的功能。
我们需要思考一下,当发生 page fault 时,内核需要什么样的信息才能够处理 page fault?
- 触发 page fault 的出错的虚拟地址。当一个用户程序触发了 page fault 时,page fault 会使用 trap 机制将程序运行切换到内核,同时将出错的地址放到 STVAL 寄存器中。
- 出错的原因。我们或许会想要对不同场景的 page fault 有不同的处理方式,比如 load 指令、store 指令、jump 指令等不同触发 page fault 的原因。RISC-V 文档介绍了,SCAUSE 寄存器用来记录 trap 机制进入 supervisor mode 的原因,其中有 3 类原因是与 page fault 相关的,分别是执行、读、写指令导致的:12 表示因指令执行而引起的 page fault,13 表示因 load 指令而引起的 page fault,15 表示因 store 指令而引起的 page fault。
- 触发 page fault 的指令的地址。因为我们可能希望在修复 page fault 后能重新执行对应的指令。从上节课我们知道,作为 trap 处理代码的一部分,这个地址存放在 SEPC 寄存器中,并同时保存在
trapframe->epc
中。
在通过 ECALL 指令进入 supervisor mode 时,SCAUSE 寄存器中记录的值是 8
所以,当出现 page fault 时,有 3 个对我们很重要的信息,分别是:
- 引起 page fault 的内存地址
- 引起 page fault 的原因类型
- 引起 page fault 时的程序计数器的值,这表明了 page fault 在用户空间发生的位置
接下来我们看一下这些利用 page fault 而实现的不同机制,来帮助我们理解如何利用 page fault handler 修复 page table 并做一些有趣的事情。
# 2. Lazy page allocation
# 2.1 sbrk
先来看一下内存的分配,也就是 sbrk 系统调用,它使得用户程序可以扩大自己的 heap。当一个应用程序启动的时候,sbrk 指向的是 heap 的最底端,同时也是 stack 的最顶端。当调用 sbrk 时,传入一个整数参数,表示你想要申请的 heap 字节数,sbrk 会扩展 heap 的上边界。
在代码中,代表进程的数据结构中的 sz 字段就表示 sbrk 所指向的位置,即
p->sz
。
这意味着,当 sbrk 被调用时,内核会分配一些物理内存,并将这些内存映射到用户应用程序的地址空间里面,然后将内存内容初始化为 0,再返回给 sbrk 系统调用。类似的,应用程序也可以给 sbrk 传入负数来减少它的地址空间。不过在这节课我们只关注增加内存的场景。
# 2.2 eager allocation
在 xv6 中,sbrk 的默认实现是 eager allocation。也就是一旦调用 sbrk,内核会立刻分配应用程序所需要的物理内存。但实际上,应用程序很难预测自己需要多少内存,通常他会申请多于自己需要的内存,但在之后并不会使用这些内存。
比如一些矩阵运算,程序员会最大可能为矩阵分配内存,但实际的运算只在一个很小的矩阵上完成。所以,程序员过多申请内存的情况还挺常见的。
# 2.3 lazy allocation
eager allocation 并不是什么大问题,但是用虚拟内存和 page fault handler,我们完全可以实现 lazy allocation。核心思想就是,sbrk 系统调用基本不做什么事情,只需要将 p-sz
增大所需分配的内存空间,但内核并不会实际分配物理内存。在之后的某个时间点,当应用程序用到了新申请的那部分内存,由于 page table 中没有记录这块内存而会触发 page fault。所以,如果我们解析一个大于旧的 p->sz
但又小于新的 p->sz
的虚拟地址时,我们希望内核能够分配一个 page,并重新执行指令。
所以,实现思路就是:当我们看到一个 page fault,相应的 VA 小于当前 p->sz
但又大于 stack,那我们就知道这是一个来自于 heap 的地址,但内核还没有分配任何物理内存,所以这个 page fault 的处理方式很直接明了:在 page fault handler 中,通过 kalloc 函数分配一个内存 page,然后初始化这个 page 的内容为 0,将这个内存 page 映射到 user page table 中,最后重新执行指令。在我们映射完新申请的物理内存 page 后,重新执行指令就应该可以通过了。
下面看一下为了实现 lazy allocation,代码应该会是什么样的。这也是今天唯一与编程相关的内容。
我们首先要修改的是 sys_sbrk 函数,sys_sbrk 原本会完成实际增加应用程序的地址空间,分配内存等等一系列相关的操作。但我们需要修改这个函数,让它只对 p->sz
加 n,并不执行实际的增加内存的操作:
uint64
sys_sbrk(void)
{
int addr;
int n;
if(argint(0, &n) < 0)
return -1;
addr = myproc()->sz;
// if(growproc(n) < 0)
// return -1;
return addr;
}
2
3
4
5
6
7
8
9
10
11
12
13
修改完之后启动 xv6 并执行 echo hi
,那我们就会得到一个 page fault:
这里会出现 page fault 的原因是,shell 需要 fork 出一个子进程,并通过 exec 执行 echo,而这个过程需要 shell 来申请一些内存,所以 shell 会调用 sys_sbrk,然后就出错了。
上图的输出中包含了一些有趣的信息:
- 输出的 SCAUSE 寄存器内容是 15,表明这是一个 store page fault
- 这个 pid 是 3,这很可能是 shell 的 pid
- 可以看到出错的虚拟内存地址,也就是 STVAL 寄存器的值 0x4008
以上就是 page fault 的信息,我们接下来看看如何能够聪明地处理这里的 page fault。
首先看一下 trap.c 中的 usertrap 函数中的这段代码:
if(r_scause() == 8){
// system call
if(p->killed)
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 sstatus &c registers,
// so don't enable until done with those registers.
intr_on();
syscall();
} else if((which_dev = devintr()) != 0){
// ok
} 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;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
- 这段代码检查 SCAUSE 寄存器的值,如果是 8 的话,就代表这次 trap 是一次 system call,如果不等于 8,就会接着检查是否有任何的设备中断,如果有的话处理相关的设备中断。如果两个条件都不满足,这里会打印一些信息,并且杀掉进程。
我们在这里增加一个检查,判断 SCAUSE == 15
,如果符合条件,我们需要一些定制化的处理来完成物理内存的分配。
这里以演示为目的展示一种处理方式:
在上面的代码中,首先打印了一些调试信息,之后分配了一个物理内存 page,如果 ka 等于 0,表明没有物理内存,于是直接 OOM 了,我们就会直接杀掉进程。如果还有物理内存,先会将内存内容设置为 0,之后将物理内存 page 指向用户地址空间中合适的虚拟内存地址。具体来说,我们首先将虚拟地址向下取整,这里引起 page fault 的虚拟地址是 0x4008,向下取整之后是 0x4000。之后我们将物理内存地址跟取整之后的虚拟内存地址的关系加到 page table 中。对应的PTE需要设置常用的权限标志位,在这里是 u,w,r bit 位。
接下来运行这一部分代码,重新编译后执行 echo hi
:
不幸的是,这里并没有正常工作,这里出现了两个 page fault,第一个对应的虚拟内存地址是0x4008,但是很明显在处理这个page fault时,我们又有了另一个page fault 0x13f48。现在唯一的问题是,uvmunmap在报错,一些它尝试unmap的page并不存在。这里unmap的内存是什么?答案是,之前 lazy allocation 没有实际分配的内存在被 ummap 时会报错。所以对于这个内存,并没有对应的物理内存。所以在 uvmunmap 函数中,当PTE的 v 标志位为 0 并且没有对应的 mapping,这并不是一个实际的 panic,这是我们预期的行为。原先的 uvmunmap 函数如下:
// Remove npages of mappings starting from va. va must be
// page-aligned. The mappings must exist.
// Optionally free the physical memory.
void
uvmunmap(pagetable_t pagetable, uint64 va, uint64 npages, int do_free)
{
uint64 a;
pte_t *pte;
if((va % PGSIZE) != 0)
panic("uvmunmap: not aligned");
for(a = va; a < va + npages*PGSIZE; a += PGSIZE){
if((pte = walk(pagetable, a, 0)) == 0)
panic("uvmunmap: walk");
if((*pte & PTE_V) == 0)
panic("uvmunmap: not mapped");
if(PTE_FLAGS(*pte) == PTE_V)
panic("uvmunmap: not a leaf");
if(do_free){
uint64 pa = PTE2PA(*pte);
kfree((void*)pa);
}
*pte = 0;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
所以实际上,对于这个 page 我们其实并不用做任何事情,我们可以直接 continue 跳到下一个 page:
接下来再重新编译并执行:
可以看到,这次有两个 page fault,但 echo hi
正常工作了。现在,我们一定程度上有了最基本最简单的 lazy allocation。
# 3. Zero Fill On Demand
另一个简单但使用很频繁的功能是 zero fill on demand。
在一个用户程序的地址空间中,存在 text 区域、data 区域、BSS 区域,BSS 区域包含了未被初始化或者初始化为 0 的全局或静态变量,这些变量的内存中都是 0。
在一个正常的 OS 中,如果执行 exec,exec 会申请地址空间,里面会存放 text、data、BSS 等,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 handler 中为其创建一个新的 page,并将其内容写为全 0,更新 mapping 后然后重新执行指令。
这种优化思想就类似于 lazy allocation。假如程序申请了一个大的数组,来保存可能的最大的输入,并且这个数组是全局变量且初始为 0。但是最后或许只有一小部分内容会被使用,那么这种优化会减少很多开销。
第二个好处是在 exec 中需要做的工作变少了。程序可以启动的更快,这样你可以获得更好的交互体验,因为你只需要分配一个内容全是 0 的物理 page。所有的虚拟 page 都可以映射到这一个物理 page 上。
但注意,page fault 也是具有开销的,一次由 page fault 而导致的 trap 就会涉及大量指令的运行。这些类似 lazy allocation 的方法会将很多开销推迟到了 page fault 发生时。
# 4. Copy On Write Fork
这也是一个常见的优化:copy-on-write fork,也被称为 COW fork。
当 shell 处理命令时,它会 fork 一个子进程,这个子进程是 shell 进程的拷贝,子进程接着调用 exec 运行其他程序(比如 echo)。现在的情况是,fork 创建的地址空间的完整拷贝,会被 exec 立刻丢弃,取而代之的是一个包含了 echo 的地址空间。这看起来就很浪费。
在物理内存中,xv6 的 shell 通常有 4 个 page,当调用 fork 后,会新创建 4 个 page,并将父进程 page 的内容拷贝到新创建的子进程的 page 中。但是,一旦调用了 exec,我们又会释放掉这些 page,并分配新的 page 来包含 echo 的内容。所以,对于这个特定场景有一个非常有效的优化:COW fork:当我们创建子进程时,与其创建,分配并拷贝内容到新的物理内存,其实我们可以直接共享父进程的物理内存 page。所以这里,我们可以设置子进程的 PTE 指向父进程对应的物理内存 page。当子进程需要写 page 时,再为其创建新的物理内存 page 并修改 page table 的 mapping。
实现的做法就是:当 fork 时,将子进程的 PTE 都指向父进程对应的物理内存 page,同时父进程和子进程的 PTE 均设置为只读,当有一方想要写入 page 时,会触发 page fault,内核就分配一个新的物理内存 page,并将原 page 的内容拷贝到新 page 中,然后更新 page table 的 mapping 关系,这样父进程和子进程的 PTE 都变成可读可写的了。之后再重新执行用户的指令就好了。
重新执行用户指令就是指调用 userret 函数,这也是之前介绍的返回到用户空间的方法。
注意,内核为了识别是一个 copy-on-write 场景触发的 page fault,需要在 PTE 上增加一个 bit 来标识这是一个 copy-on-write page,否则内核无法识别这个 page fault 是一次错误的“向只读地址写入数据”还是 copy-on-write。几乎所有的 page table 硬件都支持这一点,这个多出来的 bit 标志位可以放在 PTE 的预留位中。
在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中,你们需要引入一些额外的数据结构或者元数据信息来完成引用计数。
# 5. Demand Paging
Demand Paging 也是一个很流行的功能,许多操作系统都实现了它。
在 exec 中,xv6 的默认行为是 OS 会加载程序内存的 text、data 区域,并且以 eager 的方式将这些区域加载进 page table。但是根据我们在 lazy allocation 和 zero-filled on demand 的经验,为什么我们要以 eager 的方式将程序加载到内存中呢?为什么不再等等,直到应用程序实际需要这些指令的时候再加载内存?程序的二进制文件可能非常的巨大,将它全部从磁盘加载到内存中将会是一个代价很高的操作。又或者data区域的大小远大于常见的场景所需要的大小,我们并不一定需要将整个二进制都加载到内存中。
所以对于 exec,在虚拟地址空间中,我们为 text 和 data 分配好地址段,但是相应的 PTE 并不对应任何物理内存 page。对于这些 PTE,我们只需要将 valid bit 位设置为 0。
按照这样修改 xv6 后,由于应用程序是从 0 地址开始运行,text 区域从地址 0 开始向上增长,所以位于地址 0 的指令是会触发第一个 page fault 的指令。
如何处理这里的 page fault 呢?首先我们可以发现这个 page 是一个 on-demand page,我们需要在某个地方记录了这些 page 对应的程序文件,我们在 page fault handler 中需要从程序文件中读取 page 数据,加载到内存中,之后将内存 page 映射到 page table,最后再重新执行指令,程序就可以正常运行了。
前面的流程还有点问题,对于 demand paging 来说,当发生 page fault 时,如果内存已经耗尽或者 OOM 了该怎么办?
如果内存耗尽了,一种选择是撤回 page(evict page)。比如说将这部分内存 page 中的内容写回到文件系统再撤回 page。一旦你撤回并释放了 page,那你就有了一个新的空闲 page,你就可以使用这个刚刚空闲出来的 page,分配给刚刚的 page fault handler,再重新执行指令。
以上就是常见 OS 的行为。这里的关键问题是,什么样的 page 可以被撤回?并且该使用什么样的策略来撤回 page?
最常见的策略就是 LRU(Least recently Used),但除此之外还有一个小优化,如果你要撤回一个 page,你需要在 dirty page 和 non-dirty page 中做出一个选择。如果你选择 dirty page,那么之后如果这个 page 再被修改,现在你或许需要对它写两次了(注,一次内存,一次文件),所以现实中往往选择 non-dirty page。对于选中需要 evict 的 page,将其的内容写到文件中,再将相应的 PTE 标记为 non-valid,这就完成了所有的工作。之后你可以在另一个 page table 重复使用这个 page,所以通常来说会优先选择 non-dirty page 来 evict。
在 PTE 的标志位中,专门有一个 dirty bit,当硬件向一个 page 写入数据的时候,会设置 dirty bit,之后操作系统就可以发现这个 page 曾经被写入过了。另外还有一个 access bit,任何一个 page 被读或者写了,这个 access bit 就会被置 1。在想实现 LRU 时,我们想知道在一定时间内没有被访问过的 page,就是靠的这个 access bit,当然,OS 也需要定期将一些 page 的 access bit 恢复为 0,表示可以 evict。
这里可以参考 CMU 15445 实验中的 replacer 的实现方式。
# 6. Memory Mapped Files
这也是后续的一个 lab,就是 memory mapped files。它的核心思想是:将完整或部分文件加载到内存中,这样就可以通过内存地址相关的 load 或者 store 指令来操纵文件。现代 OS 的 mmap 系统调用就是这个功能的实现。
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。
Question: 有没有可能多个进程将同一个文件映射到内存,然后会有同步的问题?
Answer: 这个问题其实等价于,多个进程同时通过read/write系统调用读写一个文件会怎么样?这里的行为是不可预知的。write系统调用会以某种顺序出现,如果两个进程向一个文件的block写数据,要么第一个进程的write能生效,要么第二个进程的write能生效,只能是两者之一生效。在这里其实也是一样的,所以我们并不需要考虑冲突的问题。一个更加成熟的Unix操作系统支持锁定文件,你可以先锁定文件,这样就能保证数据同步。但是默认情况下,并没有同步保证。
# 7. 总结
总结一下最近几节课的内容。我们首先看了 page table 是如何工作的,之后又详细看了一下 trap 是如何工作的,而 page fault 结合了这两部分内容,可以用来实现非常强大且优雅的虚拟内存功能。
这节课介绍的内容只是 OS 基于 page fault 功能的子集,一个典型的 OS 实现了今天讨论的所有内容,如果你查看 Linux,它就包含了所有的内容,以及许多其他有趣的功能。今天的内容是希望你理解,一个你可以在 page fault handler 中动态更新 page table,虚拟内存将会变得有多强大。