30-SV39-multilevel-page-table

本节导读

在上一小节中我们已经简单介绍了分页的内存管理策略，现在我们尝试在 RISC-V 64 架构提供的 SV39 分页硬件机制的基础上完成内核中的软件对应实现。由于内容过多，我们将分成两个小节进行讲解。

本节主要讲解在

RISC-V 64 架构下的虚拟地址与物理地址的访问属性（可读，可写，可执行等），
组成结构（页号，帧号，偏移量等），
访问的空间范围，
硬件实现地址转换的多级页表访问过程等；
以及如何用 Rust 语言来设计有类型的页表项。

虚拟地址和物理地址

内存控制相关的 CSR 寄存器

默认情况下 MMU 未被使能（启用），此时无论 CPU 位于哪个特权级，访存的地址都会作为一个物理地址交给对应的内存控制单元来直接访问物理内存。我们可以通过修改 S 特权级的一个名为 satp 的 CSR 来启用分页模式，在这之后 S 和 U 特权级的访存地址会被视为一个虚拟地址，它需要经过 MMU 的地址转换变为一个物理地址，再通过它来访问物理内存；而 M 特权级的访存地址，我们可设定是内存的物理地址。

[! note] 暂不深入探讨 M 特权级的地址转换 M 特权级的访存地址被视为一个物理地址还是一个需要经历和 S/U 特权级相同的地址转换的虚拟地址取决于硬件配置，在这里我们不会进一步探讨。

上图是 RISC-V 64 架构下 satp 的字段分布，含义如下：

MODE 控制 CPU 使用哪种页表实现；
- 当 MODE 设置为 0 的时候，代表所有访存都被视为物理地址；
- 而设置为 8 的时候，SV39 分页机制被启用，所有 S/U 特权级的访存被视为一个 39 位的虚拟地址，它们需要先经过 MMU 的地址转换流程，如果顺利的话，则会变成一个 56 位的物理地址来访问物理内存；否则则会触发异常，这体现了分页机制的内存保护能力。
- 39 位的虚拟地址可以用来访问理论上最大 512GB 的地址空间，而 56 位的物理地址在理论上甚至可以访问一块大小比这个地址空间的还高出几个数量级的物理内存。
- 但是实际上无论是虚拟地址还是物理地址，真正有意义、能够通过 MMU 的地址转换或是 CPU 内存控制单元检查的地址仅占其中的很小一部分，因此它们的理论容量上限在目前都没有实际意义。
ASID 表示地址空间标识符，这里还没有涉及到进程的概念，我们不需要管这个地方；
PPN 存的是根页表所在的物理页号。这样，给定一个虚拟页号，CPU 就可以从三级页表的根页表开始一步步的将其映射到一个物理页号。

地址格式与组成

我们采用分页管理，单个页面的大小设置为 4KiB，每个虚拟页面和物理页帧都对齐到这个页面大小，

也就是说虚拟 / 物理地址区间 $[0, 4 K i B)$ 为第 0 个虚拟页面 / 物理页帧，而 $[4 K i B, 8 K i B)$ 为第 2 个，以此类推。
4KiB 需要用 12 个比特位来表示 (4KiB=2^12b)，因此虚拟地址和物理地址都被分成两部分：
- 它们的低 12 位，即 [11:0] 被称为 页内偏移 (Page Offset) ，它描述一个地址指向的字节在它所在页面中的相对位置。
- 而虚拟地址的高 27 位，即 [38:12] 为它的虚拟页号 VPN，
- 同理物理地址的高 44 位，即 [55:12] 为它的物理页号 PPN，页号可以用来定位一个虚拟 / 物理地址属于哪一个虚拟页面 / 物理页帧。

地址转换是以页为单位进行的，在地址转换的前后地址的页内偏移部分不变。可以认为 MMU 只是从虚拟地址中取出 27 位虚拟页号，在页表中查到其对应的物理页号（如果存在的话），最后将得到的 44 位的物理页号与虚拟地址的 12 位页内偏移依序拼接到一起就变成了 56 位的物理地址。

[! note] RISC-V 64 架构中虚拟地址为何只有 39 位？ 在 64 位架构上虚拟地址长度确实应该和位宽一致为 64 位，但是在启用 SV39 分页模式下，只有低 39 位是真正有意义的。SV39 分页模式规定 64 位虚拟地址的 [63:39] 这 25 位必须和第 38 位相同，否则 MMU 会直接认定它是一个不合法的虚拟地址。通过这个检查之后 MMU 再取出低 39 位尝试将其转化为一个 56 位的物理地址。

也就是说，所有 2^64 个虚拟地址中，只有最低的 256GiB（当第 38 位为 0 时）以及最高的 256GiB（当第 38 位为 1 时）是可能通过 MMU 检查的。当我们写软件代码的时候，一个地址的位宽毋庸置疑就是 64 位，我们要清楚可用的只有最高和最低这两部分，尽管它们已经巨大的超乎想象了；而本节中我们专注于介绍 MMU 的机制，强调 MMU 看到的真正用来地址转换的虚拟地址只有 39 位。

地址相关的数据结构抽象与类型定义

正如本章第一小节所说，在分页内存管理中，地址转换的核心任务在于如何维护虚拟页号到物理页号的映射——也就是页表。不过在具体实现它之前，我们先将地址和页号的概念抽象为 Rust 中的类型，借助 Rust 的类型安全特性来确保它们被正确实现。

首先是这些类型的定义：

// os/src/mm/address.rs

#[derive(Copy, Clone, Ord, PartialOrd, Eq, PartialEq)]
pub struct PhysAddr(pub usize);

#[derive(Copy, Clone, Ord, PartialOrd, Eq, PartialEq)]
pub struct VirtAddr(pub usize);

#[derive(Copy, Clone, Ord, PartialOrd, Eq, PartialEq)]
pub struct PhysPageNum(pub usize);

#[derive(Copy, Clone, Ord, PartialOrd, Eq, PartialEq)]
pub struct VirtPageNum(pub usize);

上面分别给出了物理地址、虚拟地址、物理页号、虚拟页号的 Rust 类型声明，它们都是 Rust 的元组式结构体，可以看成 usize 的一种简单包装。我们刻意将它们各自抽象出不同的类型而不是都使用与 RISC-V 64 硬件直接对应的 usize 基本类型，就是为了在 Rust 编译器的帮助下，通过多种方便且安全的 类型转换 (Type Conversion) 来构建页表。

首先，这些类型本身可以和 usize 之间互相转换，以物理地址 PhysAddr 为例，我们需要：

// os/src/mm/address.rs

const PA_WIDTH_SV39: usize = 56;
const PPN_WIDTH_SV39: usize = PA_WIDTH_SV39 - PAGE_SIZE_BITS;

impl From<usize> for PhysAddr {
    fn from(v: usize) -> Self { Self(v & ( (1 << PA_WIDTH_SV39) - 1 )) }
}
impl From<usize> for PhysPageNum {
    fn from(v: usize) -> Self { Self(v & ( (1 << PPN_WIDTH_SV39) - 1 )) }
}

impl From<PhysAddr> for usize {
    fn from(v: PhysAddr) -> Self { v.0 }
}
impl From<PhysPageNum> for usize {
    fn from(v: PhysPageNum) -> Self { v.0 }
}

前者允许我们从一个 usize 来生成 PhysAddr ，即 PhysAddr::from(_: usize) 将得到一个 PhysAddr 。注意 SV39 支持的物理地址位宽为 56 位，因此在生成 PhysAddr 的时候我们仅使用 usize 较低的 56 位。

同理在生成虚拟地址 VirtAddr 的时候仅使用 usize 较低的 39 位。反过来，从 PhysAddr 等类型也很容易得到对应的 usize 。==其实由于我们在声明结构体的时候将字段公开了出来，从物理地址变量 pa 得到它的 usize 表示的更简便方法是直接 pa.0== 。

[! note] Rust Tips：类型转换之 From 和 Into

一般而言，当我们为类型 U 实现了 From<T> Trait 之后，可以使用 U::from(_: T) 来从一个 T 类型的实例来构造一个 U 类型的实例；

而当我们为类型 U 实现了 Into<T> Trait 之后，对于一个 U 类型的实例 u ，可以使用 u.into() 来将其转化为一个类型为 T 的实例。

==当我们为 U 实现了 From<T> 之后，Rust 会自动为 T 实现 Into<U> Trait==，因为它们两个本来就是在做相同的事情。因此我们只需相互实现 From 就可以相互 From/Into 了。

需要注意的是，当我们使用 From Trait 的 from 方法来构造一个转换后类型的实例的时候，from 的参数已经指明了转换前的类型，因而 Rust 编译器知道该使用哪个实现；而==使用 Into Trait 的 into 方法来将当前类型转化为另一种类型的时候，它并没有参数，因而函数签名中并没有指出要转化为哪一个类型，则我们必须在其它地方显式指出目标类型==。比如，当我们要将 u.into() 绑定到一个新变量 t 的时候，必须通过 let t: T 显式声明 t 的类型；又或是将 u.into() 的结果作为参数传给某一个函数，那么由于这个函数的函数签名中指出了传入位置的参数的类型，所以 Rust 编译器也就明确知道转换的类型。

请注意，==解引用 Deref Trait 是 Rust 编译器唯一允许的一种隐式类型转换，而对于其他的类型转换，我们必须手动调用类型转化方法或者是显式给出转换前后的类型==。这体现了 Rust 的类型安全特性，在 C/C++ 中并不是如此，比如两个不同的整数 / 浮点数类型进行二元运算的时候，编译器经常要先进行隐式类型转换使两个操作数类型相同，而后再进行运算，导致了很多数值溢出或精度损失问题。Rust 不会进行这种隐式类型转换，它会在编译期直接报错，提示两个操作数类型不匹配。(Rust 必须实现显式类型转换)

其次，地址和页号之间可以相互转换。我们这里仍以物理地址和物理页号之间的转换为例：

// os/src/mm/address.rs

impl PhysAddr {
    pub fn page_offset(&self) -> usize { self.0 & (PAGE_SIZE - 1) }
}

impl From<PhysAddr> for PhysPageNum {
    fn from(v: PhysAddr) -> Self {
        assert_eq!(v.page_offset(), 0);
        v.floor()
    }
}

impl From<PhysPageNum> for PhysAddr {
    fn from(v: PhysPageNum) -> Self { Self(v.0 << PAGE_SIZE_BITS) }
}

其中 PAGE_SIZE 为 4096 ， PAGE_SIZE_BITS 为 12 ，它们均定义在 config 子模块中，分别表示每个页面的大小和页内偏移的位宽。

从物理页号到物理地址的转换只需左移 12 位即可，
但是物理地址需要保证它与页面大小对齐才能通过右移转换为物理页号。

对于不对齐的情况，物理地址不能通过 From/Into 转换为物理页号，而是需要通过它自己的 floor 或 ceil 方法来进行下取整或上取整的转换。

// os/src/mm/address.rs

impl PhysAddr {
    pub fn floor(&self) -> PhysPageNum { PhysPageNum(self.0 / PAGE_SIZE) }
    pub fn ceil(&self) -> PhysPageNum { PhysPageNum((self.0 + PAGE_SIZE - 1) / PAGE_SIZE) }
}

我们暂时先介绍这两种最简单的类型转换。

页表项的数据结构抽象与类型定义

第一小节中我们提到，在页表中以虚拟页号作为索引不仅能够查到物理页号，还能查到一组保护位，它控制了应用对地址空间每个虚拟页面的访问权限。但实际上还有更多的标志位，==物理页号和全部的标志位以某种固定的格式保存在一个结构体中，它被称为 页表项 (PTE, Page Table Entry)== ，是利用虚拟页号在页表中查到的结果。

上图为 SV39 分页模式下的页表项，其中 [53:10] 这 44 位是物理页号，最低的 8 位 [7:0] 则是标志位，它们的含义如下（请注意，为方便说明，==下文我们用 页表项的对应虚拟页面 来表示索引到一个页表项的虚拟页号对应的虚拟页面==）：

V (Valid)：仅当位 V 为 1 时，页表项才是合法的；
R (Read)/W (Write)/X (eXecute)：分别控制索引到这个页表项的对应虚拟页面是否允许读 / 写 / 执行；
U (User)：控制索引到这个页表项的对应虚拟页面是否在 CPU 处于 U 特权级的情况下是否被允许访问；
G：暂且不理会；
A (Accessed)：处理器记录自从页表项上的这一位被清零之后，页表项的对应虚拟页面是否被访问过；
D (Dirty)：处理器记录自从页表项上的这一位被清零之后，页表项的对应虚拟页面是否被修改过。

除了 G 外的上述位可以被操作系统设置，只有 A 位和 D 位会被处理器动态地直接设置为 1 ，表示对应的页被访问过或修过（注：A 位和 D 位能否被处理器硬件直接修改，取决于处理器的具体实现）。

让我们先来实现页表项中的标志位 PTEFlags ：

// os/src/main.rs

#[macro_use]
extern crate bitflags;

// os/src/mm/page_table.rs

use bitflags::*;

bitflags! {
    pub struct PTEFlags: u8 {
        const V = 1 << 0;
        const R = 1 << 1;
        const W = 1 << 2;
        const X = 1 << 3;
        const U = 1 << 4;
        const G = 1 << 5;
        const A = 1 << 6;
        const D = 1 << 7;
    }
}

bitflags 是一个 Rust 中常用来比特标志位的 crate 。它提供了一个 bitflags! 宏，如上面的代码段所展示的那样，==可以将一个 u8 封装成一个标志位的集合类型，支持一些常见的集合运算==。它的一些使用细节这里不展开，请同学自行参考它的官方文档。注意，在使用之前我们需要引入该 crate 的依赖：

# os/Cargo.toml

[dependencies]
bitflags = "1.2.1"

接下来我们实现页表项 PageTableEntry ：

// os/src/mm/page_table.rs

#[derive(Copy, Clone)]
#[repr(C)]
pub struct PageTableEntry {
    pub bits: usize,
}

impl PageTableEntry {
    pub fn new(ppn: PhysPageNum, flags: PTEFlags) -> Self {
        PageTableEntry {
            bits: ppn.0 << 10 | flags.bits as usize,
        }
    }
    pub fn empty() -> Self {
        PageTableEntry {
            bits: 0,
        }
    }
    pub fn ppn(&self) -> PhysPageNum {
        (self.bits >> 10 & ((1usize << 44) - 1)).into()
    }
    pub fn flags(&self) -> PTEFlags {
        PTEFlags::from_bits(self.bits as u8).unwrap()
    }
}

第 3 行我们让编译器自动为 PageTableEntry 实现 Copy/Clone Trait，来让这个类型以值语义赋值 / 传参的时候不会发生所有权转移，而是拷贝一份新的副本。从这一点来说 PageTableEntry 就和 usize 一样，因为它也只是后者的一层简单包装，并解释了 usize 各个比特段的含义。
第 10 行使得我们可以==从一个物理页号 PhysPageNum 和一个页表项标志位 PTEFlags 生成一个页表项 PageTableEntry 实例==；
而第 20 行和第 23 行则实现了分别可以从一个页表项将它们两个取出的方法。
第 15 行中，我们也可以通过 empty 方法生成一个全零的页表项，注意这隐含着该页表项的 V 标志位为 0 ，因此它是不合法的。

后面我们还为 PageTableEntry 实现了一些辅助函数 (Helper Function)，可以快速判断一个页表项的 V/R/W/X 标志位是否为 1 以 V 标志位的判断为例：

// os/src/mm/page_table.rs

impl PageTableEntry {
    pub fn is_valid(&self) -> bool {
        (self.flags() & PTEFlags::V) != PTEFlags::empty()
    }
}

这里相当于判断两个集合的交集是否为空集，部分说明了 bitflags crate 的使用方法。

多级页表

页表的一种最简单的实现是线性表，也就是按照地址从低到高、输入的虚拟页号从 0 开始递增的顺序依次在内存中（我们之前提到过页表的容量过大无法保存在 CPU 中）放置每个虚拟页号对应的页表项。

由于每个页表项的大小是 8 字节，我们只要知道第一个页表项（对应虚拟页号）被放在的物理地址 base_addr，就能直接计算出每个输入的虚拟页号对应的页表项所在的位置。如下图所示：

事实上，对于虚拟页号 i ，如果页表（每个应用都有一个页表，这里指其中某一个）的起始地址为 base_addr，则这个虚拟页号对应的页表项可以在物理地址 base_add + 8i 处找到。这使得 MMU 的实现和内核的软件控制都变得非常简单。

然而遗憾的是，这远远超出了我们的物理内存限制。由于虚拟页号有 2^27 种，每个虚拟页号对应一个 8 字节的页表项，则每个页表都需要消耗掉 1GiB 内存！应用的数据还需要保存在内存的其他位置，这就使得每个应用要吃掉至少 1GiB 以上的内存。作为对比，我们的 K210 开发板目前只有 8MiB 的内存，因此从空间占用角度来说，这种线性表实现是完全不可行的。

线性表的问题在于：它保存了所有虚拟页号对应的页表项，但是高达 512GiB 的地址空间中真正会被应用使用到的只是其中极小的一个子集（本教程中的应用内存使用量约在数十 ~ 数百 KiB 量级），也就导致有意义并能在页表中查到实际的物理页号的虚拟页号在 2^27 中也只是很小的一部分。由此线性表的绝大部分空间其实都是被浪费掉的。

那么如何进行优化呢？核心思想就在于 按需分配 ，也就是说：有多少合法的虚拟页号，我们就维护一个多大的映射，并为此使用多大的内存用来保存映射。这是因为，每个应用的地址空间最开始都是空的，或者说所有的虚拟页号均不合法，那么这样的页表自然不需要占用任何内存， MMU 在地址转换的时候无需关心页表的内容而是将所有的虚拟页号均判为不合法即可。

而在后面，内核已经决定好了一个应用的各逻辑段存放位置之后，它就需要负责从零开始以虚拟页面为单位来让该应用的地址空间的某些部分变得合法，反映在该应用的页表上也就是一对对映射顺次被插入进来，自然页表所占据的内存大小也就逐渐增加。

这种 按需分配 思想在计算机科学中得到了广泛应用：为了方便接下来的说明，我们可以举一道数据结构的题目作为例子。设想我们要维护一个字符串的多重集，集合中所有的字符串的字符集均为 α={a, b, c}，长度均为一个给定的常数 n 。该字符串集合一开始为空集。我们要支持两种操作，第一种是将一个字符串插入集合，第二种是查询一个字符串在当前的集合中出现了多少次。

简单起见，假设 n=3 。那么我们可能会建立这样一颗 字典树 (Trie) ：

字典树由若干个节点（图中用椭圆形来表示）组成，

从逻辑上而言每个节点代表一个可能的字符串前缀。
每个节点的存储内容都只有三个指针，对于蓝色的非叶节点来说，它的三个指针各自指向一个子节点；
而对于绿色的叶子节点来说，它的三个指针不再指向任何节点，而是具体保存一种可能的长度为 n 的字符串的计数。

这样，对于题目要求的两种操作，我们只需根据输入的字符串中的每个字符在字典树上自上而下对应走出一步，最终就能够找到字典树中维护的它的计数。之后我们可以将其直接返回或者加一。

注意到如果某些字符串自始至终没有被插入，那么一些节点没有存在的必要。反过来说一些节点是由于我们插入了一个以它对应的字符串为前缀的字符串才被分配出来的。如下图所示：

一开始仅存在一个根节点。在我们插入字符串 acb 的过程中，我们只需要分配 a 和 ac 两个节点。
注意 ac 是一个叶节点，它的 b 指针不再指向另外一个节点而是保存字符串 acb 的计数。
此时我们无法访问到其他未分配的节点，如根节点的 b/c 或是 a 节点的 a/b 均为空指针。如果后续再插入一个字符串，那么 至多分配两个新节点 ，因为如果走的路径上有节点已经存在，就无需重复分配了。
这可以说明，字典树中节点的数目（或者说字典树消耗的内存）是随着插入字符串的数目逐渐线性增加的。

同学可能很好奇，为何在这里要用相当一部分篇幅来介绍字典树呢？事实上 SV39 分页机制等价于一颗字典树。

27 位的虚拟页号可以看成一个长度 n=3 的字符串，字符集为 α={0,1,2,…, 511} ，因为每一位字符都由 9 个比特组成。而我们也不再维护所谓字符串的计数，而是要找到字符串（虚拟页号）对应的页表项。因此，每个叶节点都需要保存 512 个 8 字节的页表项，一共正好 4KiB ，可以直接放在一个物理页帧内。
而对于非叶节点来说，从功能上它只需要保存 512 个指向下级节点的指针即可，不过我们就像叶节点那样也保存 512 个页表项，这样每个节点都可以被放在一个物理页帧内，节点的位置可以用它所在物理页帧的物理页号来代替。当想从一个非叶节点向下走时，只需找到当前字符对应的页表项的物理页号字段，它就指向了下一级节点的位置，这样非叶节点中转的功能也就实现了。
每个节点的内部是一个线性表，也就是将这个节点起始物理地址加上字符对应的偏移量就找到了指向下一级节点的页表项（对于非叶节点）或是能够直接用来地址转换的页表项（对于叶节点）。

这种页表实现被称为 多级页表 (Multi-Level Page-Table) 。由于 SV39 中虚拟页号被分为三级 页索引 (Page Index) ，因此这是一种三级页表。在这种三级页表的树结构中，自上而下分为三种不同的节点：一级 / 二级 / 三级页表节点。树的根节点被称为一级页表节点；一级页表节点可以通过一级页索引找到二级页表节点；二级页表节点可以通过二级页索引找到三级页表节点；三级页表节点是树的叶节点，通过三级页索引可以找到一个页表项。

[! question] 不同习惯的命名注意本书将多级页表的根节点称为一级页表，在其他地方则可能以相反的顺序将根节点称为三级页表，这只是表述的习惯不同。

非叶节点（页目录表，非末级页表）的表项标志位含义和叶节点（页表，末级页表）相比有一些不同：

当 V 为 0 的时候，代表当前指针是一个空指针，无法走向下一级节点，即该页表项对应的虚拟地址范围是无效的；
只有当 V 为 1 且 R/W/X 均为 0 时，表示是一个合法的页目录表项，其包含的指针会指向下一级的页表；
注意: 当 V 为 1 且 R/W/X 不全为 0 时，表示是一个合法的页表项，其包含了虚地址对应的物理页号。

在这里我们给出 SV39 中的 R/W/X 组合的含义：

[! note] 大页 (Huge Page) 所谓大页就是某些页的大小（如 2MiB , 1GiB ）大于常规缺省的页大小（如 4KiB ）。本教程中并没有用到大页的知识，这里只是作为拓展，不感兴趣的同学可以跳过。

RISC-V 64 处理器在地址转换过程中，只要表项中的 V 为 1 且 R/W/X 不全为 0 就会直接从当前的页表项中取出物理页号，再接上页内偏移，就完成最终的地址转换。注意这个过程可以发生在多级页表的任意一级。如果这一过程并没有发生在多级页表的最深层，那么在地址转换的时候，物理页号对应的物理页帧的起始物理地址的位数与页内偏移的位数都和按缺省页处理时的情况不同了。我们需要按大页的地址转换方式来处理。

这里需要进一步理解将物理页号和页内偏移 “接起来” 这一行为，它的本质是将物理页号对应的物理页帧的起始物理地址和页内偏移进行求和，物理页帧的起始物理地址是将物理页号左移上页内偏移的位数得到，因此看上去恰好就是将物理页号和页内偏移接在一起。==如果在从多级页表往下走的中途停止，未用到的页索引会和虚拟地址的 12 位缺省页内偏移一起形成一个位数更多的大页页内偏移==。即对应于一个大页，在转换物理地址的时候，其算法仍是上述二者求和，只是物理页帧的起始物理地址和页内偏移的位数不同了。

在 SV39 中，

如果使用了一级页索引就停下来，则它可以涵盖虚拟页号的高 9 位为某一固定值的所有虚拟地址，对应于一个 1GiB 的大页；

如果使用了二级页索引就停下来，则它可以涵盖虚拟页号的高 18 位为某一固定值的所有虚拟地址，对应于一个 2MiB 的大页。

以同样的视角，如果使用了所有三级页索引才停下来，它可以涵盖虚拟页号的高 27 位为某一个固定值的所有虚拟地址，自然也就对应于一个大小为 4KiB 的虚拟页面。

使用大页的优点在于，当地址空间的大块连续区域的访问权限均相同的时候，可以直接映射一个大页，从时间上避免了大量页表项的读写开销，从空间上降低了所需节点的数目。但是，从内存分配算法的角度，这需要内核支持从物理内存上分配三种不同大小的连续区域（ 4KiB 或是另外两种大页），便不能使用更为简单的插槽式管理。权衡利弊之后，本书全程只会以 4KiB 为单位进行页表映射而不会使用大页特性。

那么 SV39 多级页表相比线性表到底能节省多少内存呢？这里直接给出结论：设某个应用地址空间实际用到的区域总大小为 S 字节，则地址空间对应的多级页表消耗内存为 $\frac{S}{512}$ 左右。下面给出了详细分析，对此不感兴趣的同学可以直接跳过。

[! note] 分析 SV39 多级页表的内存占用 我们知道，多级页表的总内存消耗取决于节点的数目，每个节点需要存放在一个大小为 4KiB 物理页帧中。考虑一个地址空间，除了根节点（即一级页表）占用的一个物理页帧之外，在映射地址空间中的一个实际用到的大小为 T 字节的连续区间的时候，最多需要额外分配 $⌈ \frac{T}{1 G i B} ⌉$ 个二级页表节点和 $⌈ \frac{T}{2 M i B} ⌉$ 个三级页表节点。

这是因为，每个三级页表节点管理地址空间中一块大小为 4KiB * 512 = 2MiB 的区域，每个二级页表节点管理地址空间中一块大小为 4KiB * 512^2 = 1GiB 的区域。因此，每连续映射 1GiB 需要在多级页表中分配一个二级页表节点；每连续映射 2MiB 需要在多级页表中分配一个三级页表节点。无论二级 / 三级页表都需要占用一个 4KiB 的物理页帧，因此映射 T 字节的连续区间需要的额外内存为 4KiB * ( $⌈ \frac{T}{1 G i B} ⌉ + ⌈ \frac{T}{2 M i B} ⌉$ )。相比三级页表，我们可以将二级页表的内存消耗忽略，即省略掉括号中的第二项，最后得到的结果接近于 $\frac{T}{512}$ 。而一般情况下我们对于地址空间的使用方法都是在其中放置少数几个连续的逻辑段，因此当一个地址空间实际使用的区域大小总和为 S 字节的时候，我们可以认为多级页表消耗的内存在 $\frac{S}{512}$ 左右。相比线性表固定消耗 1GiB 的内存，这已经相当可以接受了。

然而，从理论上来说，不妨设某个应用地址空间中的实际用到的总空间大小为 S 字节，则对于这个应用的 SV39 多级页表所需的内存量，有两个更加严格的上限：

假设目前多级页表中已经分配了一个一级页表节点。接下来，每映射一个 4KiB 的虚拟页面，至多沿着路径额外分配一个二级页表和一个三级页表。之所以是 “最多”，是因为路径上经过的二级页表和三级页表可能已经被分配了从而无需重复分配。因此，当总共映射 S 字节时，多级页表的总节点数不超过 $1 + 2 \frac{S}{4 K i B}$ ，故总消耗内存不超过 $4 K i B \times (1 + 2 \frac{S}{4 K i B}) = 4 K i B + 2 S$ ；

考虑已经映射了很多虚拟页面，使得根节点（一级页表节点）指向的 512 个二级页表节点都已经被分配的情况（事实上它们不一定都被分配），此时最坏的情况是每次映射都需要分配一个不同的三级页表节点。与上面同理可得：此时消耗内存不超过 $4 K i B \times (1 + 512 + \frac{S}{4 K i B}) = 4 K i B + 2 M i B + S$ 。

虽然这两个上限值都可以通过刻意构造一种地址空间的使用来达到，但是它们看起来很不合理，因为它们均大于 S ，也就是元数据比数据还大。其实，真实环境中一般不会有如此极端的使用方式，一般情况下我们知道多级页表消耗内存为 $\frac{S}{512}$ 左右就行了。

SV39 地址转换过程

接下来，我们给出 SV39 地址转换的全过程图示（来源于 MIT 6.828 课程）来结束多级页表原理的介绍：

在 SV39 模式中我们采用三级页表，即将 27 位的虚拟页号分为三个等长的部分，第 26-18 位为一级页索引 $V P N_{0}$ ，第 17-9 位为二级页索引 $V P N_{1}$ ，第 8-0 位为三级页索引 $V P N_{2}$ 。

我们也将页表分为一级页表（多级页表的根节点），二级页表，三级页表（多级页表的叶节点）。每个页表都用 9 位索引，因此有 2^9 个页表项，而每个页表项都是 8 字节，因此每个页表大小都为 512 * 8 = 4KiB 。正好是一个物理页的大小。我们可以把一个页表放到一个物理页中，并用一个物理页号来描述它。

事实上，一级页表的每个页表项中的物理页号可描述一个二级页表；二级页表的每个页表项中的物理页号可描述一个三级页表；三级页表中的页表项内容则和我们刚才提到的页表项一样，其内容包含物理页号，即描述一个要映射到的物理页。

具体来说，假设我们有虚拟地址 ( $V P N_{0}, V P N_{1}, V P N_{2}, o ff se t$ ) ：

我们首先会记录装载「当前所用的一级页表的物理页」的页号到 satp 寄存器中；
把 $V P N_{0}$ 作为偏移在一级页表的物理页中找到二级页表的物理页号；
把 $V P N_{1}$ 作为偏移在二级页表的物理页中找到三级页表的物理页号；
把 $V P N_{2}$ 作为偏移在三级页表的物理页中找到要访问位置的物理页号；
物理页号对应的物理页基址（即物理页号左移 12 位）加上 offset 就是虚拟地址对应的物理地址。

这样处理器通过这种多次转换，终于从虚拟页号找到了一级页表项，从而得出了物理页号和虚拟地址所对应的物理地址。刚才我们提到若页表项满足 R, W, X 都为 0，表明这个页表项指向下一级页表。在这里三级和二级页表项的 R, W, X 为 0 应该成立，因为它们指向了下一级页表。

快表（TLB）

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

实践表明绝大部分应用程序的虚拟地址访问过程具有时间局部性和空间局部性的特点。因此，在 CPU 内部，我们使用 MMU 中的 快表（TLB, Translation Lookaside Buffer） 来作为虚拟页号到物理页号的映射的页表缓存。这部分知识在计算机组成原理课程中有所体现，当我们要进行一个地址转换时，会有很大可能对应的地址映射在近期已被完成过，所以我们可以先到 TLB 缓存里面去查一下，如果有的话我们就可以直接完成映射，而不用访问那么多次内存了。

上面主要是对单个应用的多级页表进行了介绍。在一个多任务系统中，可能同时存在多个任务处于运行 / 就绪状态，它们各自的多级页表在内存中共存，那么 MMU 应该如何知道当前做地址转换的时候要查哪一个页表呢？回到 stap CSR的布局，其中的 PPN 字段指的就是多级页表根节点所在的物理页号。因此，每个应用的地址空间就可以用包含了它多级页表根节点所在物理页号的 satp CSR 代表。在我们切换任务的时候， satp 也必须被同时切换。

但==如果修改了 satp 寄存器，说明内核切换到了一个与先前映射方式完全不同的页表。此时快表里面存储的映射已经失效了，这种情况下内核要在修改 satp 的指令后面马上使用 sfence.vma 指令刷新清空整个 TLB==。

同样，我们手动修改一个页表项之后，也修改了映射，但 TLB 并不会自动刷新清空，我们也需要使用 sfence.vma 指令刷新整个 TLB。

注：可以在 sfence.vma 指令后面加上一个虚拟地址，这样 sfence.vma 只会刷新 TLB 中关于这个虚拟地址的单个映射项。

评论区的讨论

RISC-V 64 架构中虚拟地址为何只有 39 位？

《RISC-V 手册》第十章 RV32/64 特权架构里面把”RISC-V 64 架构中虚拟地址为何只有 39 位？“的问题讲得更清楚。本质上是为了兼容性。全0前导的地址，是要有一块低地址空间。全1前导的地址，是要有一块高地址空间。如果未来升级的话，可以一点一点地把中间未用空间分给低地址空间和高地址的空间，并且同时保证这三块空间都是连续的。（从而在未来还可以“故技重施”）

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

🌰Senjl's Digital Garden🐉

Recent writing

Welcome to Senj's Digital Garden

6-文件系统

7-进程间通信与IO重定向

探索