# 地址与页表

## 物理地址与虚拟地址

RV64支持多种分页方案，但我们只介绍最受欢迎的一种， `Sv39`。每个页的大小是4KB，也就是4096个字节。页表就是那个“字典”，里面有程序使用的虚拟页号到实际内存的物理页号的对应关系，但并不是所有的虚拟页都有对应的物理页。虚拟页可能的数目远大于物理页的数目，而且一个程序在运行时，一般不会拥有所有物理页的使用权，而只是将部分物理页在它的页表里进行映射。

在 Sv39 中，定义**物理地址(Physical Address)**有 56位，而**虚拟地址(Virtual Address)** 有 39位。实际使用的时候，一个虚拟地址要占用 64位，只有低 39位有效，规定 63−39 位的值必须等于第 38 位的值（类似有符号整数），否则会认为该虚拟地址不合法，在访问时会产生异常。

{% hint style="success" %}
**未被使用的地址位**

由于Sv39的虚拟地址比RISC-v64整数寄存器要短，可能你想知道剩下的35位是什么。 Sv39要求地址位 63-39是第 38位的副本。因此有效的虚拟地址是0x0000 0000 0000 0000 -0x0000 003f ffff ffff和 0xffff ffc0 0000 0000-0xffff ffff ffff ffff。这两个区间之间间隔的大 小是两个区间长度大小的225倍，看上去似乎浪费了64位寄存器可以表达范围的99.999997%。为什么不充分地利用这额外的 25位空间呢？答案是，随着程序的增长，它们可能会需要大于 512 GiB的虚址空间。而架构师希望再不破坏向后兼容性的前提下增加地 址空间。如果我们允许程序在高 25位中存储额外的数据，那么以后就不可能把这些位回收 从而存储更大的地址。像这样允许在未使用的地址位中存储数据的严重错误，在计算机的历 史中已经重复出现了多次。
{% endhint %}

不论是物理地址还是虚拟地址，我们都可以认为，最后12位表示的是页内偏移，也就是这个地址在它所在页帧的什么位置（同一个位置的物理地址和虚拟地址的页内偏移相同）。除了最后12位，前面的部分表示的是物理页号或者虚拟页号。

## 页表项

很容易理解，我们需要给词典的每个词条约定一个固定的格式（包括每个词条的大小，含义），查起来才方便。

我们的”词典“（页表）存储在内存里，由若干个格式固定的”词条“也就是**页表项（PTE, Page Table Entry）**组成。

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

Sv39的一个页表项占据8字节，结构是这样的：

| 63-54      | 53-28   | 27-19   | 18-10   | 9-8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| ---------- | ------- | ------- | ------- | --- | - | - | - | - | - | - | - | - |
| *Reserved* | PPN\[2] | PPN\[1] | PPN\[0] | RSW | D | A | G | U | X | W | R | V |
| 10         | 26      | 9       | 9       | 2   | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |

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

* RSW两位留给 S Mode 的应用程序，我们可以用来进行拓展。
* D，即 Dirty ，如果 D=1表示自从上次 D被清零后，有虚拟地址通过这个页表项进行写入。
* A，即 Accessed，如果 A=1表示自从上次 A 被清零后，有虚拟地址通过这个页表项进行读、或者写、或者取指。
* G，即Global，如果G=1表示这个页表项是”全局"的，也就是所有的地址空间（所有的页表）都包含这一项
* U(user)为 111 表示用户态 (U Mode)的程序 可以通过该页表项进行映射。在用户态运行时也只能够通过 U=1的页表项进行虚实地址映射。

  注意，S Mode 不一定可以通过 U=1的页表项进行映射。我们需要将 S Mode 的状态寄存器 `sstatus` 上的 **SUM** 位手动设置为 111 才可以做到这一点（通常情况不会把它置1）。否则通过 U=1的页表项进行映射也会报出异常。另外，不论`sstatus`的**SUM**位如何取值，S Mode都不允许执行 U=1的页面里包含的指令，这是出于安全的考虑。
* R,W,X为许可位，分别表示是否可读 (Readable)，可写 (Writable)，可执行 (Executable)。
* V表示这个页表项是否合法。如果为 000 表示不合法，此时页表项其他位的值都会被忽略。

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

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

| X | W | R | Meaning                       |
| - | - | - | ----------------------------- |
| 0 | 0 | 0 | 指向下一级页表的指针                    |
| 0 | 0 | 1 | 这一页只读                         |
| 0 | 1 | 0 | *保留(reserved for future use)* |
| 0 | 1 | 1 | 这一页可读可写（不可执行）                 |
| 1 | 0 | 0 | 这一页可读可执行（不可写）                 |
| 1 | 0 | 1 | 这一页可读可执行                      |
| 1 | 1 | 0 | *保留(reserved for future use)* |
| 1 | 1 | 1 | 这一页可读可写可执行                    |

”指向下一级页表的指针 “ 暗示我们有多级页表。下面就来看看多级页表是怎么回事。

## 多级页表

主要矛盾在于：相比于可用的物理内存空间，我们的虚拟地址空间太大，不可能为每个虚拟内存页都分配一个页表项。在Sv39中，虚拟地址有39位，后12位是页内偏移，还有27位可以编码不同的虚拟页号。如果开个大数组Pagetable\[], 给2^27个虚拟页号都分配8字节的页表项，pagetable\[vpn]是虚拟页号为vpn的虚拟页的页表项，那就是整整1 GiB的内存。这里面很多虚拟地址我们没有用到，会有大片大片的页表项的V 标志位为0（不合法）。我们不想为那么多非法页表项浪费宝贵的内存空间。

因此，我们可以对页表进行“分级”，变成一个树状结构。也就是把很多页表项组合成一个”大页“，如果这些页表项都非法（没有对应的物理页），那么只需要用一个非法的页表项来覆盖这个大页，而不需要分别建立一大堆非法页表项。很多个大页(megapage)还可以组合起来变成大大页(gigapage!)，继而可以有大大大页(terapage!).....但肯定不是分层越多越好，层数越多开销越大。

Sv39权衡各方面效率，使用三级页表。有4KiB=40964字节的页，大小为2MiB=2^21字节的大页，和大小为1 GiB的大大页。

原先的一个39位虚拟地址，被我们看成27位的页号和12位的页内偏移。

现在我们把它看成9位的“大大页页号”，9位的“大页页号”（也是大大页内的页内偏移），9位的“页号”（大页的页内偏移），还有12位的页内偏移。这是一个递归的过程，中间的每一级页表映射是类似的。

也就是说，整个Sv39的虚拟内存空间里，有512（2的9次方）个大大页，每个大大页里有512个大页，每个大页里有512个页，每个页里有4096个字节，整个虚拟内存空间里就有512∗512∗512∗4096512 *512* 512 \* 4096512∗512∗512∗4096个字节，是512GiB的地址空间。

那么为啥是512呢？注意，4096/8 = 512，我们恰好可以在一页里放下512个页表项！

我们可以认为，Sv39的多级页表在逻辑上是一棵树，它的每个叶子节点（直接映射4KB的页的页表项）都对应内存的一页，它的每个内部节点都对应512个更低一层的节点，而每个内部节点向更低一层的节点的链接都使用内存里的一页进行存储。

或者说，Sv39页表的根节点占据一页4KiB的内存，存储512个页表项，分别对应512个1 GiB的大大页，其中有些页表项（大大页）是非法的，另一些合法的页表项（大大页）是根节点的儿子，可以通过合法的页表项跳转到一个物理页号，这个物理页对应树中一个“大大页”的节点，里面有512个页表项，每个页表项对应一个2MiB的大页。同样，这些大页可能合法，也可能非法，非法的页表项不对应内存里的页，合法的页表项会跳转到一个物理页号，这个物理页对应树中一个“大页”的节点，里面有512个页表项，每个页表项对应一个4KiB的页，在这里最终完成虚拟页到物理页的映射。

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

{% hint style="info" %}
这么看来，建立一个虚拟页到物理页的映射，我们需要在三个层级（页，大页，大大页）各自给它分配一个物理页帧，是不是还没把所有物理内存都建立映射，就把所有物理页帧都耗尽了？

事实上这个问题是不存在的。关键点在于，我们要映射的是一段**连续**的虚拟内存**区间**，因此，每连续建立 512 页的映射才会新建一个一级页表，每连续建立 512^2页的映射才会新建一个二级页表，而三级页表最多只新建一个。因此这样进行映射花费的总物理页帧数,约占物理内存中物理页帧总数的约1/512≈0.2%。
{% endhint %}

## 页表基址

在翻译的过程中，我们首先需要知道树状页表的根节点的物理地址（思考：为啥不是“根节点的虚拟地址”？）。

这一般保存在一个特殊寄存器里。对于RISCV架构，是一个叫做`satp`（Supervisor Address Translation and Protection Register）的CSR。实际上，`satp`里面存的不是最高级页表的起始物理地址，而是它所在的物理页号。除了物理页号，`satp`还包含其他信息

| 63-60 | 59-44 | 43-0 |
| ----- | ----- | ---- |
| MODE  | ASID  | PPN  |
| 4     | 16    | 44   |

MODE表示当前页表的模式

* 0000表示不使用页表，直接使用物理地址，在简单的嵌入式系统里用着很方便。
* 0100表示Sv39页表，也就是我们使用的，虚拟内存空间高达512GiB。
* 0101表示Sv48页表，它和Sv39兼容，可以猜猜它有几层。虚拟内存空间高达256TiB。
* 其他编码保留备用。

ASID （Address Space Identifier 地址空间标识符）域是可选的，它可以用来降低上下文切换的开销。

PPN字段保存了根页表的物理地址，它以 4 KiB的页面大小为单位。通常 M模式的程序在第一次进入 S模式之前会把零写入 satp以禁用分页，然后 S模式的程序在初始化页表以后会再次进行satp寄存器的写操作。

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

## 快表

物理内存的访问速度要比 CPU 的运行速度慢很多, 去访问一次物理内存可能需要几百个时钟周期（带来所谓的“冯诺依曼瓶颈”）。如果我们按照页表机制一步步走，将一个虚拟地址转化为物理地址需要访问 333 次物理内存，得到物理地址之后还要再访问一次物理内存，才能读到我们想要的数据。这很大程度上降低了效率。

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

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

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

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

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