页表：从虚拟内存到物理内存

回顾第二章，我们曾提到使用了一种“魔法”之后，内核就可以像一个普通的程序一样运行了，它按照我们设定的内存布局决定代码和数据存放的位置，跳转到入口点开始运行...当然，别忘了，在 $64$ 位寻址空间下，你需要一块大小为 $2^{64}$ 字节即 $2^{24}\text{TiB}$ 的内存！

现实中一块这么大的内存当然不存在，因此我们称它为虚拟内存。我们知道，实际上内核的代码和数据都存放在物理内存上，而 CPU 只能通过物理地址来访问它。

因此，当我们在程序中通过虚拟地址假想着自己在访问一块虚拟内存的时候，需要有一种机制，将虚拟地址转化为物理地址，交给 CPU 来根据它到物理内存上进行实打实的访问。而这种将虚拟地址转化为物理地址的机制，在 riscv64 中是通过页表来实现的。

[info]地址的简单解释

物理地址：物理地址就是内存单元的绝对地址，比如一个 128MB 的 DRAM 内存条插在计算机上，物理地址 0x0000 就表示内存条的第 1 个存储单元，0x0010 就表示内存条的第 17 个存储单元，不管 CPU 内部怎么处理内存地址，最终访问的都是内存单元的物理地址。

虚拟地址：虚拟地址是操作系统给运行在用户态的应用程序看到的假地址，每一个虚拟地址，如果有一个对应的物理地址，那么就是一个合法的虚拟地址，应用程序实际访问的是其对应的物理地址；否则就是一个非法的虚拟地址。一旦应用程序访问非法的虚拟地址，CPU 当然就会产生异常了。一旦出现这样的异常，操作系统就会及时进行处理，甚至是杀死掉这个应用程序。虚拟地址与物理地址的对应关系，一般是通过页表来实现。

rCore 中整体的虚拟地址空间到物理地址空间映射如下图：

虚拟地址和物理地址

在本教程中，我们选用 Sv39 作为页表的实现。

在 Sv39 中，定义物理地址(Physical Address)有 $56$ 位，而虚拟地址(Virtual Address) 有 $64$ 位。虽然虚拟地址有 $64$ 位，只有低 $39$ 位有效。不过这不是说高 $25$ 位可以随意取值，规定 $63-39$ 位的值必须等于第 $38$ 位的值，否则会认为该虚拟地址不合法，在访问时会产生异常。

Sv39 同样是基于页的，在物理内存那一节曾经提到物理页帧(Frame) 与物理页号(PPN, Physical Page Number) 。在这里物理页号为 $44$ 位，每个物理页帧大小 $2^{12}=4096$ 字节，即 $4\text{KiB}$ 。同理，我们对于虚拟内存定义虚拟页(Page) 以及虚拟页号(VPN, Virtual Page Number) 。在这里虚拟页号为 $27$ 位，每个虚拟页大小也为 $2^{12}=4096$ 字节。物理地址和虚拟地址的最后 $12$ 位都表示页内偏移，即表示该地址在所在物理页帧(虚拟页)上的什么位置。

虚拟地址到物理地址的映射以页为单位，也就是说把虚拟地址所在的虚拟页映射到一个物理页帧，然后再在这个物理页帧上根据页内偏移找到物理地址，从而完成映射。我们要实现虚拟页到物理页帧的映射，由于虚拟页与虚拟页号一一对应，物理页帧与物理页号一一对应，本质上我们要实现虚拟页号到物理页号的映射，而这就是页表所做的事情。

页表项

一个页表项 (PTE, Page Table Entry)是用来描述一个虚拟页号如何映射到物理页号的。如果一个虚拟页号通过某种手段找到了一个页表项，并通过读取上面的物理页号完成映射，我们称这个虚拟页号通过该页表项完成映射。

我们可以看到 Sv39 里面的一个页表项大小为 $64$ 位 $8$ 字节。其中第 $53-10$ 共 $44$ 位为一个物理页号，表示这个虚拟页号映射到的物理页号。后面的第 $9-0$ 位则描述映射的状态信息。

$\text{V}$ 表示这个页表项是否合法。如果为 $0$ 表示不合法，此时页表项其他位的值都会被忽略。
$\text{R,W,X}$ 为许可位，分别表示是否可读 (Readable)，可写 (Writable)，可执行 (Executable)。

以 $\text{W}$ 这一位为例，如果 $\text{W}=0$ 表示不可写，那么如果一条 store 的指令，它通过这个页表项完成了虚拟页号到物理页号的映射，找到了物理地址。但是仍然会报出异常，是因为这个页表项规定如果物理地址是通过它映射得到的，那么不准写入！ $\text{R,X}$ 也是同样的道理。

根据 $\text{R,W,X}$ 取值的不同，我们可以分成下面几种类型：

如果 $\text{R,W,X}$ 均为 $0$ ，文档上说这表示这个页表项指向下一级页表，我们先暂时记住就好。
$\text{U}$ 为 $1$ 表示用户态 (U Mode) 可以通过该页表项进行映射。事实上用户态也只能够通过 $\text{U}=1$ 的页表项进行虚实地址映射。

然而，我们所处在的 S Mode 也并不是理所当然的可以通过这些 $\text{U}=1$ 的页表项进行映射。我们需要将 S Mode 的状态寄存器 sstatus 上的 $\text{SUM}$ 位手动设置为 $1$ 才可以做到这一点。否则通过 $\text{U}=1$ 的页表项进行映射也会报出异常。
$\text{A}$ ，即 Accessed，如果 $\text{A}=1$ 表示自从上次 $\text{A}$ 被清零后，有虚拟地址通过这个页表项进行读、或者写、或者取指。

$\text{D}$ ，即 Dirty ，如果 $\text{D}=1$ 表示自从上次 $\text{D}$ 被清零后，有虚拟地址通过这个页表项进行写入。
$\text{RSW}$ 两位留给 S Mode 的应用程序，我们可以用来进行拓展。

多级页表

一个虚拟页号要通过某种手段找到页表项...那么要怎么才能找到呢？

想一种最为简单粗暴的方法，在物理内存中开一个大数组作为页表，把所有虚拟页号对应的页表项都存下来。在找的时候根据虚拟页号来索引页表项。即，加上大数组开头的物理地址为 $a$ ，虚拟页号为 $\text{VPN}$ ，则该虚拟页号对应的页表项的物理地址为 $a+\text{VPN}\times 8$ (我们知道每个页表项 $8$ 字节)。

但是这样会花掉我们 $2^{27}\times 8=2^{30}$ 字节即 $1\text{GiB}$ 的内存！不说我们目前只有可怜的 $128\text{MiB}$ 内存，即使我们有足够的内存也不应该这样去浪费。这是由于有很多虚拟地址我们根本没有用到，因此他们对应的虚拟页号不需要映射，我们开了很多无用的内存。

事实上，在 Sv39 中我们采用三级页表，即将 $27$ 位的虚拟页号分为三个等长的部分，第 $26-18$ 位为三级索引 $\text{VPN}[2]$ ，第 $17-9$ 位为二级索引 $\text{VPN}[1]$ ，第 $8-0$ 位为一级索引 $\text{VPN}[0]$ 。

我们也将页表分为三级页表，二级页表，一级页表。每个页表都是 $9$ 位索引的，因此有 $2^{9}=512$ 个页表项，而每个页表项都是 $8$ 字节，因此每个页表大小都为 $512\times 8=4\text{KiB}$ 。正好是一个物理页帧的大小。我们可以把一个页表放到一个物理页帧中，并用一个物理页号来描述它。事实上，三级页表的每个页表项中的物理页号描述一个二级页表；二级页表的每个页表项中的物理页号描述一个一级页表；一级页表中的页表项则和我们刚才提到的页表项一样，物理页号描述一个要映射到的物理页帧。

具体来说，假设我们有虚拟页号 $(\text{VPN}[2],\text{VPN}[1],\text{VPN}[0])$ ，设三级页表的物理页号为 $\text{PPN}_3$ ，那么将其映射到物理页号的流程如下：

索引控制虚拟页号范围在 $(\text{VPN}[2],\text{Any},\text{Any})$ 的三级页表项，其地址为 $\text{PPN}_3 \times 2^{12}+ \text{VPN}[2] \times 8$ 。从这个页表项里读出二级页表的物理页号 $\text{PPN}_2$ 。
索引控制虚拟页号范围在 $(\text{VPN}[2],\text{VPN}[1],\text{Any})$ 的二级页表项，其地址为 $\text{PPN}_2\times 2^{12}+\text{VPN}[1]\times 8$ 。从这个页表项里读出一级页表的物理页号 $\text{PPN}_1$ 。
索引控制虚拟页号范围在 $(\text{VPN}[2],\text{VPN}[1],\text{VPN}[0])$ 的一级页表项，其地址为 $\text{PPN}_1\times 2^{12}+\text{VPN}[0]\times 8$ 。可以看出一级页表项只控制一个虚拟页号，因此从这个页表项中读出来的物理页号，就是虚拟页号 $(\text{VPN}[2],\text{VPN}[1],\text{VPN}[0])$ 所要映射到的物理页号。

上述流程如下图所示。

我们通过这种复杂的手段，终于从虚拟页号找到了一级页表项，从而得出了物理页号。刚才我们提到若页表项满足 $\text{R,W,X}=0$ ，表明这个页表项指向下一级页表。在这里三级和二级页表项的 $\text{R,W,X}=0$ 应该成立，因为它们指向了下一级页表。

然而三级和二级页表项不一定要指向下一级页表。我们知道每个一级页表项控制一个虚拟页号，即控制 $4\text{KiB}$ 虚拟内存；每个二级页表项则控制 $9$ 位虚拟页号，总计控制 $4\text{KiB}\times 2^9=2\text{MiB}$ 虚拟内存；每个三级页表项控制 $18$ 位虚拟页号，总计控制 $2\text{MiB}\times 2^9=1\text{GiB}$ 虚拟内存。我们可以将二级页表项的 $\text{R,W,X}$ 设置为不是全 $0$ 的许可要求，那么它将与一级页表项类似，只不过可以映射一个 $2\text{MiB}$ 的大页 (Huge Page) 。同理，也可以将三级页表项看作一个叶子，来映射一个 $1\text{GiB}$ 的超大页。

如果不考虑大页的情况，对于每个要映射的虚拟页号，我们最多只需要分配三级页表，二级页表，一级页表三个物理页帧来完成映射，可以做到需要多少就花费多少。

页表基址

页表的基址（起始地址）一般会保存在一个特殊的寄存器中。在 RISC-V 中，这个特殊的寄存器就是页表寄存器 satp。

我们使用寄存器 satp 来控制 CPU 进行页表映射。

$\text{MODE}$ 控制 CPU 使用哪种页表实现，我们只需将 $\text{MODE}$ 设置为 $8$ 即表示 CPU 使用 Sv39 。
$\text{ASID}$ 我们先不用管。
$\text{PPN}$ 存的是三级页表所在的物理页号。这样，给定一个虚拟页号，CPU 就可以从三级页表开始一步步的将其映射到一个物理页号。

于是，OS 可以在内存中为不同的应用分别建立不同虚实映射的页表，并通过修改寄存器 satp 的值指向不同的页表，从而可以修改 CPU 虚实地址映射关系及内存保护的行为。然而，仅仅这样做是不够的。

快表(TLB)

我们知道，物理内存的访问速度要比 CPU 的运行速度慢很多。如果我们按照页表机制循规蹈矩的一步步走，将一个虚拟地址转化为物理地址需要访问 $3$ 次物理内存，然后得到物理地址还需要再访问一次物理内存，才能完成访存。这无疑很大程度上降低了效率。

事实上，实践表明虚拟地址的访问具有时间局部性和空间局部性。

时间局部性是指，被访问过一次的地址很有可能不远的将来再次被访问；
空间局部性是指，如果一个地址被访问，则这个地址附近的地址很有可能在不远的将来被访问。

因此，在 CPU 内部，我们使用快表 (TLB, Translation Lookaside Buffer) 来记录近期已完成的虚拟页号到物理页号的映射。不懂 CPU 的内部构造？那先回头学习一下计算机组成原理这门课吧。由于局部性，当我们要做一个映射时，会有很大可能这个映射在近期被完成过，所以我们可以先到 TLB 里面去查一下，如果有的话我们就可以直接完成映射，而不用访问那么多次内存了。

但是，我们如果修改了 satp 寄存器，比如将上面的 $\text{PPN}$ 字段进行了修改，说明我们切换到了一个与先前映射方式完全不同的页表。此时快表里面存储的映射结果就跟不上时代了，很可能是错误的。这种情况下我们要使用 sfence.vma 指令刷新整个 TLB 。

同样，我们手动修改一个页表项之后，也修改了映射，但 TLB 并不会自动刷新，我们也需要使用 sfence.vma 指令刷新 TLB 。如果不加参数的， sfence.vma 会刷新整个 TLB 。你可以在后面加上一个虚拟地址，这样 sfence.vma 只会刷新这个虚拟地址的映射。

小结

这一节我们终于大概讲清楚了页表的前因后果。接下来，我们将利用页表知识，来重新实现内核已有的功能，只不过从物理地址空间抽象为虚拟地址空间，这让内核更加符合它自身“程序”的属性。

页表：从虚拟内存到物理内存