lab2: 物理内存和页表

在接下来两个lab里，我们将：

进行物理内存和虚拟内存的管理
使用页表机制
处理缺页中断
实现页面置换算法。

lab2里，我们将完成物理内存管理，并建立一个最简单的页表映射。

如果我们只有物理内存空间，那么我们也可以写程序，但是所有的程序，包括内核，包括用户程序，都在同一个地址空间里，用户程序访问的0x80200000和内核访问的0x80200000是同一个地址。这样好不好？如果只有一个程序在运行，那也无所谓。但很多程序使用同一个内存空间，就会有问题：怎样防止程序之间互相干扰，甚至互相搞破坏？比较粗暴的方式就是，我让用户程序访问的0x80200000和内核访问的0x80200000不是一个地址。但是我们只有一块内存，为了创造两个不同的地址空间，我们可以引入一个”翻译“机制：程序使用的地址需要经过一步”翻译“才能变成真正的内存的物理地址。这个”翻译“过程，我们用一个”词典“实现---给出翻译之前的地址，可以在词典里查找翻译后的地址。每个程序都有唯一的一本”词典“，而它能使用的内存也就只有他的”词典“所包含的。

”词典“是否对能使用的每个字节都进行翻译？我们可以想象，存储每个字节翻译的结果至少需要一个字节，那么使用1MB的内存将至少需要构造1MB的”词典“，这效率太低了。观察到，一个程序使用内存的数量级通常远大于字节，至少以KB为单位（所以上古时代的人说的是”640K对每个人都够了“而不是”640B对每个人都够了"）。那么我们可以考虑，把连续的很多字节合在一起翻译，让他们翻译前后的数值之差相同，这就是“页”。

物理地址和虚拟地址

我们使用RISCV的sv39页表机制，每个页的大小是4KB，也就是4096个字节。页表就是那个“字典”，里面有程序使用的虚拟页号到实际内存的物理页号的对应关系，但并不是所有的虚拟页都有对应的物理页。虚拟页可能的数目远大于物理页的数目，而且一个程序在运行时，一般不会拥有所有物理页的使用权，而只是将部分物理页在它的页表里进行映射。

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

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

页表项

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

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

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

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

63-54

53-28

27-19

18-10

9-8

Reserved

PPN[2]

PPN[1]

PPN[0]

RSW

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

$\text{RSW}$ 两位留给 S Mode 的应用程序，我们可以用来进行拓展。
$\text{D}$ ，即 Dirty ，如果 $\text{D}=1$ 表示自从上次 $\text{D}$ 被清零后，有虚拟地址通过这个页表项进行写入。
$\text{A}$ ，即 Accessed，如果 $\text{A}=1$ 表示自从上次 $\text{A}$ 被清零后，有虚拟地址通过这个页表项进行读、或者写、或者取指。
$\text{G}$ ，即Global，如果 $\text{G=1}$ 表示这个页表项是”全局"的，也就是所有的地址空间（所有的页表）都包含这一项
$\text{U(user)}$ 为 $1$ 表示用户态 (U Mode)的程序可以通过该页表项进行映射。在用户态运行时也只能够通过 $\text{U}=1$ 的页表项进行虚实地址映射。
注意，S Mode 不一定可以通过 $\text{U}=1$ 的页表项进行映射。我们需要将 S Mode 的状态寄存器 sstatus 上的 SUM 位手动设置为 $1$ 才可以做到这一点（通常情况不会把它置1）。否则通过 $\text{U}=1$ 的页表项进行映射也会报出异常。另外，不论sstatus的SUM位如何取值，S Mode都不允许执行 $\text{U}=1$ 的页面里包含的指令，这是出于安全的考虑。
$\text{R,W,X}$ 为许可位，分别表示是否可读 (Readable)，可写 (Writable)，可执行 (Executable)。
$\text{V}$ 表示这个页表项是否合法。如果为 $0$ 表示不合法，此时页表项其他位的值都会被忽略。

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

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

Meaning

指向下一级页表的指针

这一页只读

保留(reserved for future use)

这一页可读可写（不可执行）

这一页可读可执行（不可写）

这一页可读可执行

保留(reserved for future use)

这一页可读可写可执行

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

多级页表

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

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

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

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

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

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

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

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

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

三级和二级页表项不一定要指向下一级页表。我们知道每个一级页表项控制一个虚拟页号，即控制 $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}$ 的大页 (Mega Page) 。同理，也可以将三级页表项看作一个叶子，来映射一个 $1\text{GiB}$ 的大大页(Giga Page)。

须知
这么看来，建立一个虚拟页到物理页的映射，我们需要在三个层级（页，大页，大大页）各自给它分配一个物理页帧，是不是还没把所有物理内存都建立映射，就把所有物理页帧都耗尽了？
事实上这个问题是不存在的。关键点在于，我们要映射的是一段连续的虚拟内存区间，因此，每连续建立 $512$ 页的映射才会新建一个一级页表，每连续建立 $512^{2}$ 页的映射才会新建一个二级页表，而三级页表最多只新建一个。因此这样进行映射花费的总物理页帧数,约占物理内存中物理页帧总数的约 $\frac{1}{512}\approx 0.2\%$ 。

页表基址

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

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

63-60

59-44

43-0

MODE(WARL)

ASID(WARL)

PPN(WARL)

MODE表示当前页表的模式

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

ASID（address space identifier）我们目前用不到~~我目前不知道是啥东西~~

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

扩展
啥是 WARL?
Write Any Values, Reads Legal Values
Some read/write CSR fields are only defined for a subset of bit encodings, but allow any value to be written while guaranteeing to return a legal value whenever read. Assuming that writing the CSR has no other side effects, the range of supported values can be determined by attempting to write a desired setting then reading to see if the value was retained. These fields are labeled WARL in the register descriptions. Implementations will not raise an exception on writes of unsupported values to a WARL field. Implementations can return any legal value on the read of a WARL field when the last write was of an illegal value, but the legal value returned should deterministically depend on the illegal written value and the value of the field prior to the write.
总而言之就是Garbage in, Something Useful Out

快表(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 只会刷新这个虚拟地址的映射。

小结

这一节我们回顾了页表的前世今生。接下来两个lab，我们将在ucore里进行物理内存管理，并利用页表知识，来重新实现内核已有的功能，只不过从物理地址空间抽象为虚拟地址空间，这让内核更加符合它“自身也是一个程序”的属性。lab2里只实现一个最简单的，把三级页表项看作叶子的页表。lab3使用多级页表机制并实现页面置换算法。

项目组成

lab2
├── Makefile
├── kern
│   ├── debug
│   │   ├── assert.h
│   │   ├── kdebug.c
│   │   ├── kdebug.h
│   │   ├── kmonitor.c
│   │   ├── kmonitor.h
│   │   ├── panic.c
│   │   └── stab.h
│   ├── driver
│   │   ├── clock.c
│   │   ├── clock.h
│   │   ├── console.c
│   │   ├── console.h
│   │   ├── intr.c
│   │   └── intr.h
│   ├── init
│   │   ├── entry.S
│   │   └── init.c
│   ├── libs
│   │   └── stdio.c
│   ├── mm
│   │   ├── best_fit_pmm.c
│   │   ├── best_fit_pmm.h
│   │   ├── default_pmm.c
│   │   ├── default_pmm.h
│   │   ├── memlayout.h
│   │   ├── mmu.h
│   │   ├── pmm.c
│   │   └── pmm.h
│   ├── sync
│   │   └── sync.h
│   └── trap
│       ├── trap.c
│       ├── trap.h
│       └── trapentry.S
├── lab2.md
├── libs
│   ├── atomic.h
│   ├── defs.h
│   ├── error.h
│   ├── list.h
│   ├── printfmt.c
│   ├── readline.c
│   ├── riscv.h
│   ├── sbi.c
│   ├── sbi.h
│   ├── stdarg.h
│   ├── stdio.h
│   ├── string.c
│   └── string.h
└── tools
    ├── boot.ld
    ├── function.mk
    ├── gdbinit
    ├── grade.sh
    ├── kernel.ld
    ├── kernel_nopage.ld
    ├── sign.c
    └── vector.c

10 directories, 51 files

最后更新于4年前