虚拟地址转换

早年(8位和16位CPU时代),计算机系统是实地址模式.那个时候,程序是直接使用物理地址.操作系统和应用程序是运行在相同的地址空间的. 一个系统中的进程与其他进程共享CPU和主存资源, 然而共享使用物理内存会带来一些特殊的挑战, 例如如果太多的进程需要太多的内存, 那么它们中有一些就根本无法运行; 如果某个进程不小心写入了另一个进程使用的内存, 就可能导致另一个进程以某种完全和程序逻辑无关的方式失败

因此为了更加有效的管理内存并且减少出错情况, 现代操作系统提供了一种对主存的抽象概念: 虚拟内存(Virtual Memory)

物理地址和虚拟地址

前文物理布局探测中提到, 计算机上电之后就会读取插入在主板上的内存条, 此时物理的内存颗粒会被操作系统组织成一个有 M 个连续的字节大小的单元组成的数组, 每一个字节都有唯一的物理地址

CPU访问内存的最自然的方式就是使用物理地址, 这种方式被称为 物理寻址. 下图表示 CPU 读取从物理地址 4 开始的连续 4 个字节, 当 CPU 执行这条加载指令的时候会生成一个有效的物理地址, 和取址长度, 通过内存总线传递给主存; 主存根据地址找到物理地址为 4 的单元, 取出连续的 4 个字节, 并将其返回给 CPU, CPU 将其存放在一个寄存器之中

在早期 PC 上使用的是物理地址, 现代 CPU 使用的虚拟地址的寻址方式. CPU 通过生成一个虚拟地址(VA)来访问主存, 这个虚拟地址在被送到内存总线之前先传递到 CPU 芯片上的 MMU (Memoryy Management Unit)单元, 将一个虚拟地址转换成物理地址, 在传输给内存. 这一步需要 CPU 硬件和操作系统紧密结合, 如下图所示

系统中实际存在的内存空间是物理地址空间, 一共有 M 字节, 其中 M = 2^m, 物理地址空间范围是 {0, 1, ..., M - 1}

CPU 从一个 n 位地址空间中构建虚拟地址空间, 一共 N 字节, 其中 N = 2^n, 虚拟地址空间的范围是 {0, 1, ..., N-1}

值得注意的是, 虚拟地址空间和物理地址的空间没有什么关系, 物理内存实际上就是电脑上的内存,一般是 8GB 16GB(2^34)那样; 虚拟地址空间则可以很大, 如果是 64 位的虚拟地址空间, 则可以表示大约 2^64 = 16384P 大小的虚拟地址空间

另外并不是 64 位机器所用的是 64 位的虚拟地址空间, 这对于虚拟内存来说实在是太大了, linux目前使用的是48位的虚拟地址空间, 即256TB. windows 使用的是47位, 即128TB. 这个空间大小对于物理内存容量已经足够了

虚拟内存可以被看作一个存放在磁盘上的数组, 大小为 N, 每字节都有一个唯一的虚拟地址, 作为到数组的索引. VM 系统通过将虚拟内存分割称为虚拟页(Virtual Page, VP)的大小固定块, 每个虚拟页的大小是 P = 2^p 字节, 类似的物理内存也被分割为物理页(Physical Page, PP), 物理页大小和虚拟页一样都是P字节 , 物理页也可以称为页帧

Linux 与 Windows 都是采用 4kb作为物理页和虚拟页大小

通常来说由于物理内存有限, 虚拟地址空间要远远大于物理地址空间, 也就是说虚拟页的数量要远远大于物理页的数量, 因此必然不可能将全部的虚拟页面映射到物理页面中, 所以在任意时刻, 虚拟页面的集合都可以分为三个不相交的子集

未分配的(unallocated): 没有任何数据和该虚拟页面相关联, 不占用任何磁盘空间

缓存的(cached): 当前虚拟页面已被分配数据, 并且缓存在物理内存中

未缓存的(uncached): 当前虚拟页面已被分配数据, 但未被缓存在物理内存中

上图中 VP0 VP4 是未分配的页面, VP2 5 7 是已分配并且缓存的, 剩下的是已分配未缓存的

这里有几个小问题需要解释一下, 上文说虚拟内存可以被看作一个存放在磁盘上的数组, 大小为 N, 也就是按理来说我们希望 N 刚好为磁盘大小, 但实际上计算机组成的磁盘空间是不确定的, 而操作系统 linux 48位, windows 47位, 也就是说实际上虚拟内存已经在操作系统初始化完成之后确定下来了, 256/128TB, 正常来说这个空间对于我的磁盘是足够大的, 假设我有 1TB 的磁盘, 那么多出来的 255/127TB, 也就是最高位并没有用到, 1TB的磁盘根据虚拟页划分, 映射到虚拟内存, 这没有问题

但是当磁盘空间大于256TB时, 48位的虚拟地址空间就不足了, Linux中如果需要访问大于256TB的磁盘空间,可以使用LVM(逻辑卷管理器)等技术来扩展磁盘空间, 这种特殊情况并不在本文讨论范围之内

也并不是说磁盘空间大于 256TB 就一定要一次性全部映射到虚拟地址空间, 分段映射也是合理的

在早期的系统比如 DEC PDP-11上, 虚拟地址空间甚至比物理地址空间还要小, 但使用虚拟地址空间仍然是一个非常有用的机制, 可以大大简化内存管理, 通常来说在现代操作系统上 物理内存空间 M << 虚拟内存空间 N

页表

与缓存类似, 虚拟内存系统需要有办法可以判断一个虚拟页是否缓存在 DRAM 中, 并且确定存放在哪一个物理页中. 如果缓存不命中, 那么还需要判断虚拟页应该对应磁盘的哪个位置, 并且需要从物理内存中选择一个牺牲页, 将虚拟页从磁盘复制到 DRAM 替换掉牺牲页

虚拟内存系统的功能是由软硬件联合提供的, 包括操作系统, MMU(内存管理单元) 中的地址翻译硬件和一个存放在物理内存中的页表(page table)的数据结构, 页表负责保存虚拟内存到物理内存的映射关系, 操作系统负责维护页表的内容, 当地址翻译硬件试图将一个虚拟地址转换到物理地址的时候会读取页表, 然后根据页表中的信息找到对应的物理地址

下图是一个页表的基本结构, 页表是常驻内存的, 它是一个页表条目(PTE, Page Table Entry)的数组, 每一个页表条目有一个有效位(valid bit)和 m 位的磁盘地址组成

这里的 m 是上文提到过的物理地址空间的大小, M = 2^m

上图中左侧是页表, 我们可以根据其中的索引找到对应的 PTE.

如果有效位为1则说明该 PTE 构建了一个从 VP 到 PP 的映射, PTE 中的 m 位地址是主存中的物理页号

如果有效位为0
- 如果 m 位地址不空, 则该 PTE 没有使用, 但已经与一个 VP 绑定了, 即未缓存虚拟页
- 如果 m 位地址为空, 则该 PTE 还没有被分配

这里注意要与之前的虚拟页和物理页区分开, 虚拟页是在磁盘中的, 物理页是在 DRAM 中, 页表也是在 DRAM 中, 下图中的映射关系没有改变, 只是借助页表这一数据结构实现了一种映射关系

页命中与缺页

当 CPU 想要读 VP2 虚拟页面中的一个字的时候, CPU 将虚拟地址发送给 MMU, MMU 查找页表进行地址转换, 通过某种技术(下面会提到)通过虚拟地址定位到索引, 找到页表中的 PTE2, 发现其有效位为 1, 说明该 PTE 有效, 则取出其中保存的物理内存地址, 找到物理内存中的数据, 如下图所示

注意页表并不是一个 Hashmap<int, int>, 而是一个数组, 由虚拟页面的页号作为索引 index 对应查找

但如果 CPU 发出一条指令希望读取 VP3, 此时发现有效位为0, 说明 VP3 并未被缓存, 操作系统触发一个缺页异常, 调用内核的缺页异常处理程序, 选择 DRAM 中的一个物理页作为牺牲页, 假设选中的是位于 PP3 的 VP4, 则内核从磁盘复制 VP3 到内存 PP3, 更新 PTE3, 如下图所示

当异常处理程序返回的时候, CPU会重新启动导致缺页的指令, 把之前导致缺页的虚拟地址重新发送到 MMU, 此时VP3 已经缓存在 DRAM 中了, 所以正常处理执行

关于虚拟内存有如下的一些相关名词, 磁盘和内存之间传送页被叫做交换或者 页面调度, 当有不命中发生的时候才换入页面的调度策略叫做 按需页面调度, 这也是现代所有系统都使用的页面调度策略

实际上操作系统为每一个进程都提供了独立的页表, 也就是每一个进程都会对应以一个独立的地址空间, 上图中只展示了 VP 和 PP的部分, 地址翻译的过程对应页表, 我们注意到进程i的 VP2 和进程j的 VP1对应的都是 PP7 的物理页面, 说明多个虚拟页面可以映射到同一个物理页面当中

简化链接
独立的虚拟地址空间允许每个进程的内存映像使用相同的基本格式, 比如 64 位地址空间中所有代码段都是从 0x400000 开始的, 数据段在代码段之后, 栈段从用户进程的最高地址空间向下生长
这样的一致性的地址空间大大简化了链接器的设计和实现, 不再需要去关系实际物理内存中的地址映射关系, 而是在一个统一的地址视图中执行程序

简化加载
当我们运行一个可执行文件的时候, 我们希望将其加载到内存中, Linux 加载器只需要简单的为代码段和数据段分配虚拟页, 然后将其标志位置 0, 加载器实际上并不从磁盘复制任何数据到内存, 只是创建一个未缓存的虚拟页, 该进程分配到时间片开始执行之后再通过缺页中断完成加载
将一组连续的虚拟页映射到任意一个文件的任意位置称为 内存映射, Linux 提供了一个 mmap 的系统调用, 允许应用程序自己做内存映射

简化共享
每个进程有自己的代码, 数据, 堆, 栈, 不与其他进程共享. 但通常来说我们会需要进程共享代码和数据, 比如每个进程都可能需要调用系统调用以及一些 C 标准库的程序, 比如 printf; 操作系统只需要将这部分经常使用的程序加载到内存一次, 让其他所有进程在使用的时候映射到相同的物理页面即可, 而不是为每个进程都创建一份副本

简化内存分配
当程序调用 malloc 希望分配在堆空间分配一块内存的时候, 操作系统只需要分配 k 个连续的虚拟内存页面, 然后将其映射到物理内存中的任意k 个物理页面即可, 虚拟内存页面需要连续, 但是物理内存的页面没有必要连续, 可以由操作系统的内存分配器寻找最合适的位置

flag

一个现代操作系统应该可以做到对内存系统的完全控制, 包括不允许一个用户进程修改它的只读代码段, 不允许读写其他进程的私有内存, 不允许修改与其他进程共享的虚拟页面(除非共享者都显示的允许)

就像我们上文提到过的, 操作系统通过虚拟内存提供了独立的地址空间, 而虚拟内存地址到物理内存地址的映射由操作系统和 MMU 控制, 我们可以在 PTE 页表项中添加一些标志位, 可以在地址翻译阶段更加容易的判断权限和合法性

上图中添加了三个权限标志位

SUP: 进程是否必须运行在内核态的进程才可以访问, 用户态进程只允许访问 SUP=0 的页面

READ: 读权限

WRITE: 写权限

如果进程执行的过程中发出了一条指令, 希望读取一个页面, 但是操作系统发现该进程没有这个页面的写权限(比如修改 const 变量) 或者不是内核态进程, 则 CPU 触发异常, 并将控制传递给内核中的异常处理程序, 也就是我们编程过程中很常见的, Linux shell 一般将这种异常报告称为 "段错误(segmentation fault)"

当然,上图中原先的有效位被隐藏了, 页表中依然保留了这一位用于判断 PTE 是否有效

地址翻译

开始本节内容之前我们先列举一下所需的所有符号简写, 希望读者预览一下有一个大致的印象, 如果后文出现了对应的符号可以到这里对照

符号	描述
N=2^n	虚拟地址空间中的地址数量
M=2^m	物理地址空间中的地址数量
P=2^p	页的大小
PTBR	Page Table Base Register, CPU中的一个控制寄存器, 指向当前页表
VPO	虚拟页面偏移量 offset
VPN	虚拟页号 number
TLB	Translation Lookaside Buffer 快表
TLBI	快表索引 index
TLBT	块表标记 tag
PPO	物理页面偏移量
PPN	物理页号
CO	缓冲块内字节偏移量 cache offset
CI	高速缓冲索引
CT	高速缓冲标记

上图展示了 MMU 是如何利用页表实现这种映射的

首先每个进程中保留着页表的基地址, 需要访存的时候传送给 PTBR, 指向页表的起始地址

整个虚拟地址跟据页内偏移量(p, 通常4kb, 12位)被分割为 VPN VPO 两部分

VPN 对应该页表的索引值, VPN = 13, 则对应页表的索引值也是13, 找到与虚拟页面对应的 PTE

MMU 判断有效位是否为 1
- 如果为 1 则说明该 PTE 已经和物理地址完成映射, 直接取其中地址
- 如果为 0 则说明该 PTE 无效, 产生缺页中断, 从磁盘中将 VP 读入 DRAM, 并完成 PTE, 再将有效位置 1, 重新执行该指令

将 PTE 中的 PPN 取出, 与 VPO 结合得到实际的物理地址.

由于虚拟页和物理页都是 P 字节的, 所以实际上 PPO 就是 VPO, 只是完成了 VPN -> PPN 的替换

当页面命中时, 上图中的12345流程分别对应

处理器生成一个虚拟地址, 并将其传给 MMU

MMU 根据 VPN 找到 PTEA 地址, 从高速缓存/主存中请求该 PTE

高速缓存/主存向 MMU 返回 PTE

MMU 构造物理地址, 将其传送给高速缓存/主存已请求数据所在的物理地址 PA

高速缓存/主存返回所请求的数据字 Data 交给处理器

这个过程完全是由硬件来处理的
上图中的 PTEA 是 PTE address的缩写, 也可以简写为 PA

当页面不命中的时候, 即有效位为 0, 情况稍微复杂一点

处理器生成一个虚拟地址, 并将其传给 MMU

MMU 根据 VPN 找到 PTEA 地址, 从高速缓存/主存中请求该 PTE

高速缓存/主存向 MMU 返回 PTE

PTE 有效位为 0, MMU 触发异常, 传递给 CPU, 由操作系统内核的缺页异常处理程序

缺页处理程序通过算法确定出物理内存的牺牲页, 如果这个页面已经被修改了则将其换出到磁盘

缺页处理程序将该虚拟页面调入到物理内存, 替换牺牲页, 并更新 PTE

缺页处理程序返回到原来的进程, 再次实行导致缺页的指令

此时 CPU 再次将之前引起缺页异常的虚拟地址发送给 MMU, 由于对应的 PTE 已经被更新了, 所以就可以正常执行了

实际上在既使用高速缓存, 也是用虚拟内存的系统中, 还有一步关于高速缓存是否命中的情况的讨论, 如下图所示

多级页表

对于一个 32 位的地址空间来说, 4KB 的页大小意味着 p = 12, 所以 VPO 是12位, VPN是20位. 页表也要保存在虚拟页中, 即使每一个 PTE 表项只保存物理地址也需要 4B(即不考虑有效位, SUB READ WRITE), 所以一页中最多可以保存的 PTE 数量是 4KB/4B = 1K = 2^10

所以为了保存所有的虚拟页面, 就需要保存所有的 20 位 VPN, 至少需要 2^20 / 2^10 = 2^10 个虚拟页. 这些虚拟页只是用来保存页表. 这些虚拟页一共是 1K x 4KB = 4MB, 所以 4MB 的内存空间没有用来保存任何程序相关的数据, 只是用来保存页表. 对于每一个进程来说都需要一个 4MB 内存空间来存储其需要的页表, 这未免有些太占空间了

而对于一个 64 位的系统来说(地址8B), 即使每个进程页表只使用 48 位的虚拟地址空间, 也需要保存 36 位的 VPN 索引, 共需要 512 GB 内存只是用来保存一个进程的页表, 这显然是无法接受的

但事实上, 对于一个 64 位程序来说, 虽然虚拟地址空间很大(2^48), 但实际上我们编写的程序并不需要那么多内存, 也就是说没有必要都把这么多虚拟页同时存在内存中, 最理想的情况是我们只把用到的虚拟页保存在 DRAM 中, 剩下的都不存, 即使突然又要访问另一个虚拟页中的数据, 那么使用缺页中断再将这个页面调入内存即可

那么现代操作系统的解决方式就是使用多级页表

如上图所示, 假设对于一个 48 位的虚拟地址空间, 我们对于高 32 位每隔 p(9位) 做一个划分, 原先的 VPN 被划分为四段, 对应四级页表

完整的多级页表访存流程为:

通过进程的页表基地址 CR3(x86) 找到一级页表起始地址

通过 VPN1 作为索引找到 L1 PTE, 作为二级页表起始地址

通过 VPN2 作为索引找到 L2 PTE, 作为三级页表起始地址

通过 VPN3 作为索引找到 L3 PTE, 作为四级页表起始地址

通过 VPN4 作为索引找到 L4 PTE, 得到最终转换的物理地址高位 PPN, 由 MMU 拼接得到实际物理地址 PA

上述的 L1-L4 PTE 还有一个更为标准的术语

PGD (Page Global Directory)

PUD (Page Upper Directory)

PMD (Page Middle Directory)

PTE (Page Table Entry)

当 TLB 未命中时,硬件页表遍历器遍历页表以查找 VA 到 PA 的映射.在页表遍历期间,48 位 VA 的前 9 位用作 PGD 的索引,以提取 PUD 的物理地址. VA 中的接下来的 9 位索引到 PUD 以提取 PMD 的物理地址,类似地,接下来的 9 位索引到 PMD 以提取 PTE 的物理地址.最后,VA中的最后9位用于索引PTE以提取数据页的物理地址. VA 中剩余的 12 位用作大小为 4 KB 的数据页中的偏移量.在页表遍历期间,硬件在页表树的所有级别(从 PGD 到 PTE)设置 ACCESSED 位

由于虚拟地址的使用是接近连续的, 低地址会连续使用到但是高位几乎不会连续使用, 所以一级页表的 PTE 被使用的极少, 基本上一两个 PTE. 这是一种巨大的潜在节约, 这意味着我们只需要存有限的必要的一些页表即可

进程多级页表完整来说是一颗深度为 4 的树, 越接近根节点使用的条目越少, 绝大部分的路径没有使用到, 内存中只需要保存有效的页表即可.

这种稀疏的页表分布非常适合使用 Radix tree 来表示

理论上来说多级页表并不一定是 4 级页表, 页表的级数主要取决于虚拟页的大小, 页表项的大小. 为什么64位系统的页表每级占9位呢? 主要是为了和硬件配合,基于i386编写的linux也采用4KB的页大小作为内存管理的基本单位.处理器进入64位时代后,其实可以不再使用4KB作为一个页帧的大小,但可能为了提供硬件的向前兼容性以及和操作系统的兼容性,大部分64位处理器依然使用4KB作为默认的页大小(ARMv8-A还支持16KB和64KB的页大小). 其实多级页表可理解位一种时间换空间的技术,所以设计每级页表具体占多大,就是一种时间和空间的平衡

所以对于现代操作系统和 MMU 硬件来说 4KB + 四级页表可以认为是标配, ~~虽然 intel 有五级页表的硬件但是暂时不考虑~~

下文中多级页表特指四级页表

TLB

前文讨论的访存流程中, CPU 得到虚拟地址, 需要先由 MMU 根据 PTBR 和 VPN 索引访问一次内存找到对应的 PTE, 在根据 PTE 中的地址找到对应的物理地址访存一次得到数据, 这个过程经历了两次访问内存

在多级页表的这种情况访存次数会进一步增加, 每一级页表都需要访问一次内存, 一共需要 5 次访存! 这显然是一个不理想的性能开销, 许多系统都希望可以消除这种开销, 所以在 MMU 中包含了一个关于 PTE 的小型缓存 TLB(translation lookaside buffer) 快表.

TLB其实就是一块高速缓存. 数据cache缓存地址(虚拟地址或者物理地址)和数据, 而 TLB 缓存虚拟地址和其映射的物理地址.

虚拟地址首先发往TLB确认是否命中

如果 TLB hit直接可以得到物理地址.

否则,一级一级查找页表获取物理地址.并将虚拟地址和物理地址的映射关系缓存到TLB中.

TLB 的组织结构如下图所示:

由于虚拟地址 VPO 和物理地址 PPO 部分的 12 位是相同的, 所以只需要存储虚拟地址的 VPN 到 PPN 的映射就可以了. 如果命中 TLB, 也会一次性从cache中拿出全部的数据.所以虚拟地址不需要offset域.

index域是否需要呢? 这取决于cache的组织形式.如果是全相连高速缓存.那么就不需要index.如果使用多路组相连高速缓存,依然需要index.

上图就是一个四路组相连TLB的例子, 可以采用 tag + index 的方式, 当然也可以直接映射, 取决于 TLB 的硬件设计

一次完整的访存流程如下: 先查询 TLB, 如果命中直接得到 PPN, 否则依次查询四级页表得到 PPN. 拼接 PPO 得到 PA; 再查询 cache, 如果 cache hit 则直接返回, 否则查询主存后返回

多级页表项缓存

在多级页表系统中, TLB 其实只是最后一级PTE的缓存. 多级页表的查找是一个串行的,链式的过程.试想一下,访问在虚拟地址空间里连续的两个pages(比如起始地址分别为"0x123456789000"和"0x12345678A000"),而这两个页面只有最后一级的 PTE 不一样, 难道在通过n次内存访问(n等于页表级数)查找到第一个page的物理页面号后,在访问相邻的(虚拟地址层面)第二个page时还需要再老老实实,一步一步的往下找?这对于在追求性能方面可谓无所不用其极的现代处理器来说是不可接受的

既然最后一级的 PTE 都可以被缓存, 那前面几级的 PTE 能否被缓存呢? 可以的,以intel的x86-64架构为例, 它支持其余的三级 PTE 的 cache. 除了最后一级页表PTE的entry是直接指向page 之外,其他级的页表的entry都是指向下一级页表首地址的,因此这些级的页表被称为paging structure,所以这些 PTE 的 cache被统称为paging structure caches.在ARM中,这些caches被称为table walk caches(名字应该是来自MMU里的table walk unit)

因此即使发生TLB miss, 相当于最后一级 PTE cache 中没找到, 也会依次的去查找前面一级的 PTE cache, 减少了访存次数

TLB 的别名和歧义

既然TLB是虚拟高速缓存(VIVT),是否存在别名和歧义问题呢?如果存在,软件和硬件是如何配合解决这些问题呢?

由于共享内存的存在, 多个虚拟地址可能映射到同一个物理地址, 在 cache 的地址访问中讨论了关于 VIVT/PIPT/VIPT 三种情况的设计. 但是 TLB 不存在修改的情况, 所以不存在别名和歧义, 只是会多冗余了一些数据而已, 因此虽然存在别名的情况但是不存在别名带来的问题

TLB flush

TLB作为一种cache,也需要维护(和页表PTE的)一致性,区别在于普通cache对应的是属于物理硬件的内存,CPU可以维护cache和内存的一致性.而TLB对应的是page table(一种软件的数据结构),因此需要软件(操作系统)去维护TLB和page table的一致性.

在页表PTE的内容出现变化时,比如page fault时页面被换出,munmap()时映射被解除,就需要invalidate对应的TLB entry,有时这个操作也被称为flush

但这个flush和普通cache的flush是不一样的,它相当于是将某TLB entry清除,而不是刷到外部页表去同步,因为也不会有TLB里的数据比页表更新的情况,这是TLB和普通cache的又一区别.早期的处理器,比如intel的80386只支持TLB的全部flush,80486之后的x86处理器开始支持对TLB某个entry的单独刷新(selective flushing)

我们知道不同的进程之间看到的虚拟地址范围是一样的,所以多个进程下,不同进程的相同的虚拟地址可以映射不同的物理地址.这就会造成歧义问题.例如,进程A将地址0x2000映射物理地址0x4000.进程B将地址0x2000映射物理地址0x5000.当进程A执行的时候将0x2000对应0x4000的映射关系缓存到TLB中.当切换B进程的时候,B进程访问0x2000的数据,会由于命中TLB从物理地址0x4000取数据.这就造成了歧义.

进程切换时 flush TLB 固然可以, 但是显然可能会影响性能. 试想一下,在发生 A进程切换到 B 的时候,如果对TLB全部flush,则意味着新换入的进程(设为B)开始执行的时候,TLB对于B进程来说是空的,B的执行性能会受到影响.如果B进程只执行了很短一段时间,就又切回了A进程,那整个性能表现就更差了. 我们当然不希望刚刚热起来的 TLB 由于一次进程切换就全部冷掉了, 那么如何解决这个问题呢?

如果能够区分不同的进程的TLB表项, 就可以避免flush TLB. 每个进程拥有一个独一无二的进程ID.如果TLB在判断是否命中的时候,除了比较tag以外, 还可以额外比较进程ID, 这样就可以区分不同进程的TLB表项.进程A和B虽然虚拟地址一样,但是进程ID不一样,自然就不会发生进程B命中进程A的TLB表项.

因此可以为硬件TLB添加一项单独区分进程, 在x86里这叫 PCID(Process Context Identifiers), 在ARM里这叫 ASID(Address Space Identifiers) 的匹配. PCID/ASID就类似进程ID一样,用来区分不同进程的TLB表项.这样在进程切换的时候就不需要flush TLB.但是仍然需要软件管理和分配

AMD ASID

如下图所示, TLB 的结构中多加了 ASID 的单元, 这样就可以根据进程对应的 ASID 来区分 TLB 表项了

注意到进程调度有两种

一种是某进程(设为A)通过system call(或其他中断方式)进入了kernel mode,内核处理完后再返回user mode
对于这种情况,无论是A进程的页表对应的TLB entries,还是内核的页表对应的TLB entries,都是不需要被flush的.试想一下,如果进入kernel mode的时候flush了整个TLB,那kernel将面对一个空的TLB,需要过一段时间,让kernel的常用PTE进入TLB后,才能让TLB再次展现它的优势.
那如果保持kernel的TLB entries不变,只flush进程A的TLB entries呢?这样在返回user mode的时候,TLB虽然不是整个空的,但对进程A来说确是空的.这种用户空间和内核空间的切换在现实应用中是非常频繁的,如果采用TLB flush的策略将会严重性能.

另一种是进程切换(其实也是user mode->kernel mode->user mode)
这种情况下由于TLB是采用虚拟地址的位域子集作为tag的,而不同的进程可能会有相同的虚拟地址,所有共用TLB的时候会发生冲突

但是在发生进程切换的时候,kernel的页表是不会有大的变化的,那kernel对应的TLB entries可以不被flush么?

在linux的内存模型中,用户空间和内核空间所用的虚拟地址是不会重叠的,因此理论上可以通过比对虚拟地址所在的内存范围(比如在32位系统中大于3GB的地址部分)来识别哪些TLB entries是属于kernel的, 但是这种判断方法实现起来比较困难.

难办? 那就再加一个标记位. 针对内核空间这种全局共享的映射关系称之为global映射.针对每个进程的映射称之为non-global映射. 对于 global 映射的内核程序来说始终保持 TLB hot, 所以可以在最后一级页表中引入一个bit(non-global (nG) bit)代表是不是global映射.

比如kernel和虚拟化里的hypervisor.以x86为例,当CR3寄存器中的内容被更新(因为CR3是指向进程页表的首地址的,这意味是发生了进程切换),默认会flush整个TLB. 如果在CR4寄存器里置位了PGE(page global enable),则TLB里的G标志位就生效了,含有G的TLB entries就不会被flush了,成了钉子户了

最后的 TLB 设计如下所示

如何管理ASID

相信细心的读者已经注意到了, 进程 pid 的取值范围很大, 而留给区分进程的 PCID/ASID 这些位数远远不够计数所有 pid, 因此不可能将进程ID和ASID一一对应

当ASID分配完后, 就需要 flush 所有的TLB,重新分配ASID. 所以,如果想完全避免flush TLB的话,理想情况下,运行的进程数目必须小于等于 ASID 的位数表示范围

CR3中的PCID只占12个bits,也就是说,它最多能表达4096个process
当ASID分配完的时候,需要flush全部TLB.ASID的管理可以使用bitmap管理,flush TLB后clear整个bitmap

然而软件层面还可以做一些优化. 前面我们提到每个进程会通过页表基地址寄存器(CR3)来找到一级页表, 这个寄存器的高 [48-63] 位为空闲位. 因此 Linux kernel为了管理每个进程会有个 task_struct 结构体,我们可以把分配给当前进程的ASID存储在这里

当进程切换时,可以将页表基地址和ASID(可以从 task_struct 获得)共同存储在页表基地址寄存器中.当查找TLB时,硬件可以对比tag以及ASID是否相等(对比页表基地址寄存器存储的ASID和TLB表项存储的ASID).如果都相等,代表TLB hit.否则TLB miss.当TLB miss时,需要多级遍历页表,查找物理地址.然后缓存到TLB中,同时缓存当前的ASID

TLB shootdown

什么是 TLB shootdown(TLB 击落)? TLB shootdown 是一种在多处理器系统中用于确保所有处理器的 Translation Lookaside Buffer(TLB)保持一致性的机制.TLB 是一种特殊的缓存,用于加速虚拟地址到物理地址的转换过程.当系统中的一个处理器修改了页表条目(Page Table Entry, PTE)时,为了确保其他处理器不会使用过时的 TLB 条目,需要执行 TLB shootdown 操作.

那么为什么需要 TLB shootdown 呢? 由于 TLB 位于 CPU 内部, 由每个 CPU 核心单独缓存, 即每个 CPU 核心都有自己的 TLB, 因此每当页表条目被任何内核修改时,该特定 TLB 条目在所有内核中都会失效

在虚拟化环境中,多个虚拟机(Guest)共享宿主机(Host)的物理硬件资源.当一个虚拟机修改了内存映射(例如,通过 madvise 系统调用指定某个内存区域为 MADV_DONTNEED,释放内存映射),这可能会导致 TLB 中的条目变得无效.为了防止其他虚拟机访问这些已经释放的内存区域,需要通知所有处理器清空它们 TLB 中的相应条目.

处理 TLB shootdown 主要分为三步

检测到页表修改:当一个处理器需要修改页表时,它会检测到这个修改可能会影响到其他处理器的 TLB.

发送 IPI:修改页表的处理器会使用 Inter-Processor Interrupt (IPI) 来通知其他处理器.

清空 TLB:收到 IPI 的处理器会响应并清空它们的 TLB,确保它们不会使用过时的页表信息.

因为涉及到处理器间的通信(IPI), 所以 TLB shootdown 可能会导致性能问题. 在高负载或频繁内存操作的场景下,TLB shootdown 的频率可能会增加,从而影响系统性能.

为了减少 TLB shootdown 的影响,研究人员和工程师们提出了多种优化策略:

批处理:将多个 TLB shootdown 操作合并为一个,减少 IPI 的使用.

自失效 TLB 条目:设计 TLB 条目,使其在检测到页表修改时自动失效,避免需要显式的 shootdown 操作.

上下文相关的清空:仅在必要时清空用户空间的 TLB 条目,减少不必要的 shootdown.

共享 TLB 目录:使用共享数据结构来同步 TLB 状态,减少每个处理器单独清空 TLB 的需要.

一篇很有意思的参考论文: Don't shoot down TLB shootdowns!

hugepage

除了 TLB 的各种优化(page structure cache), 操作系统还可以使用大页(hugepage)来优化对多级页表的访问时间. huagepage 的思想非常简单, 如下图所示:

原先需要四级页表的遍历, 那么如果扩大虚拟页大小到 2MB(4KB * 2^9), 那么就不需要最后一级 PTE 了, 直接通过 PDE 找到虚拟页得到物理地址. 同理如果虚拟页为 1GB(4KB * 2^9 * 2^9) 那么两级页表就可以完成映射.

关于处理器硬件层面是如何实现 huge page 的原理见下文页表格式中的 page size flag

hugepage的使用可以减少页表的级数,也就减少了查找页表的内存访问次数,而且对于同样entries数目的TLB,可以扩大TLB对内存地址的覆盖范围,减小TLB miss的概率

在使用 hugepage 的系统中,可能存在4KB,2MB,1GB等不同大小的page共存的情况,这就需要不同的TLB支持.

当然,使用large page也会带来一些问题,比如:

由于各种内存操作基本都要求按照page对齐,比如一个可执行文件映射到进程地址空间,根据文件大小的不同,平均算下来会浪费掉半个page size的物理内存,使用large page的话这个消耗就显得比较大了.

系统运行一段时间后,会很难再也大块的连续物理内存,这时分配large page将会变的很困难,所以通常需要在系统初始化的时候就划分出一段物理内存给large page用(类似于DMA的内存分配),这样就减少了一些灵活性.

动态large page(THP)在换出到外部的flash/disk和从flash/disk换入物理内存的过程会比normal size的page带来更大的开销

页表格式

其中虚拟地址低 12 位为页内偏移, 四级页表每个表索引号占据 9 个比特, 高位的 [48-63] 为符号扩展. 尽管48-63位毫无用处,但依然不被允许随意赋值,而是必须将其设置为与47位相同的值以保证地址唯一性,由此留出未来对此进行扩展的可能性,如实现5级页表.该技术被称为符号扩展,理由是它与二进制补码机制真的太相似了.当地址不符合该机制定义的规则时,CPU会抛出异常

值得注意的是,英特尔最近发布了一款代号是冰湖的CPU,它的新功能之一就是可选支持能够将虚拟地址从48位扩展到57位的 5级页表.但是针对一款特定的CPU做优化在现阶段并没有多少意义,所以本文仅会涉及标准的4级页表.

虚拟地址的最大宽度是48位

内核虚拟地址在64位地址空间的顶部,高16位是全1,范围是 [0xFFFF 0000 0000 0000 - 0xFFFF FFFF FFFF FFFF];

用户虚拟地址在64位地址空间的底部,高16位是全0,范围是 [0x0000 0000 0000 0000 - 0x0000 FFFF FFFF FFFF];

高16位是全1或全0的地址称为规范的地址,两者之间是不规范的地址,不允许使用

而对于物理地址来说, 当 64 位硬件变得可用之后,处理更大地址空间(大于 2^32 字节)的需求变得显而易见.现如今一些公司已经提供 64TiB 或更大内存的服务器,x86_64 架构和 arm64 架构现在允许寻址的地址空间大于 2^48 字节(可以使用默认的 48 位地址支持).

arm64 架构通过引入两个新的体系结构 ARMv8.2 LVA(更大的虚拟寻址) 和 ARMv8.2 LPA(更大的物理地址寻址) 拓展来实现相同的功能.这允许使用 4PiB 的虚拟地址空间和 4PiB 的物理地址空间(即分别为 2^52 位). 因此如今物理地址的范围为 52 位

其中 [0-51] 为物理地址, [52-62] 为可以被操作系统自由使用, [63] 位为禁用位. 前文提到过在多级页表中,每一级页表的entry除了存放下一级页表(对于PTE来说是页)的首地址,还留下了不少bit空间可供使用. 通常虚拟页的大小为4KB,所以PTE中指向的page首地址是4KB对齐的,也就是说page首地址的最后12个bit都为0.而一个PTE的大小为8字节,所以这后面的12个bit可以被用来表达page的属性.

这 12 位有很重要的用途, 下面从低位到高位分别介绍一下:

P(present): 为1表明该page存在于当前物理内存中,为0则PTE的其他部分都失去意义了,不用看了,直接触发page fault.P位为0的PTE也不会有对应的TLB entry,因为早在P位由1变为0的时候,对应的TLB就已经被flush掉了

R/W(read/write): 置为1表示该page是writable的,置为0则是read only,对只读的page进行写操作会触发page fault
比如,父进程通过 fork 系统调用创建子进程之后,父子进程的虚拟内存空间完全是一模一样的,包括父子进程的页表内容都是一样的,父子进程页表中的 PTE 均指向同一物理内存页面,此时内核会将父子进程页表中的 PTE 的 R/W 位均改为只读(0),并将父子进程共同映射的这个物理页面引用计数 + 1.
当父进程或者子进程对该页面发生写操作的时候,我们现在假设子进程先对页面发生写操作,随后子进程发现自己页表中的 PTE 是只读的,于是产生写保护中断,子进程进入内核态,在内核的缺页中断处理程序中发现,访问的这个物理页面引用计数大于 1,说明此时该物理内存页面存在多进程共享的情况,于是发生写时复制(Copy On Write, COW),内核为子进程重新分配一个新的物理页面,然后将原来物理页中的内容拷贝到新的页面中,最后子进程页表中的 PTE 指向新的物理页面并将 PTE 的 R/W 位设置为 1,原来物理页面的引用计数 - 1
后面父进程在对页面进行写操作的时候,同样也会发现父进程的页表中 PTE 是只读的,也会产生写保护中断,但是在内核的缺页中断处理程序中,发现访问的这个物理页面引用计数为 1 了,那么就只需要将父进程页表中的 PTE 的 R/W 位设置为 1 就可以了

U/S(User/Supervisor): 置为0表示只有supervisor(比如操作系统中的kernel)才可访问该page,置为1表示user也可以访问

PTW(Page Write Through): 置为1表示该page对应的cache部分采用write through的方式,否则采用write back

PCD(Page Cache Disabled): 置为1表示disable,即该page中的内容是不可以被cache的.如果置为0(enable),还要看CR0寄存器中的CD位这个总控开关是否也是0
页表既然是放在普通内存中的,自然也可以被缓存到普通cache中,MMU在不得不去查找页表之前,也会先去普通cache里看看,实在没有再极不情愿的去访问内存.该位控制下级页表是否需要被缓存到普通cache中
该位大部分情况下为 1, 即默认启用 cache. 但是对于 DMA 以及 VIVT 解决别名问题中会关闭该位使得数据不经过 cache.

A(access): 当该页正在被访问时,CPU设置该比特的值
当这个page被访问(读/写)过后,硬件将该位置1,TLB只会缓存access的值为1的page对应的映射关系.软件可将该位置0,然后对应的TLB将会被flush掉.这样,软件可以统计出每个page被访问的次数,作为内存不足时,判断该page是否应该被回收的参考

D(dirty): 当该页正在被写入时,CPU设置该比特的值
这个标志位只对file backed的page有意义,对anonymous的page是没有意义的.当page被写入后,硬件将该位置1,表明该page的内容比外部disk/flash对应部分要新,当系统内存不足,要将该page回收的时候,需首先将其内容flush到外部存储.之后软件将该标志位清0

PS(page size): 是否是 hugepage; 1级页表项(PML4E)和4级页表项(PTE)中该位一定为 0, 如果4级页表项(PDE)中为 1 则说明该页是一个 2MB 的大页, 如果2级页表项(PDPE)中为 1 则说明是一个 1GB 的大页
huge page 标志位允许2级页表或3级页表直接指向页帧来分配一块更大的内存空间, 操作系统检测到2/3级页表项该位被置 1, 则说明改虚拟页是一个大页, 跳过剩余的页表遍历直接得到大页

G(global): 用于context switch的时候不用flush掉kernel对应的TLB, 这个标志位在TLB entry中也是存在的, 在前文 TLB flush 中提到

AVL: 剩余高 3 位可以由操作系统自定义

P 位为 0 就说明页面不存在, 触发 page fault, 这是多级页表节约内存空间的一个好手段
对 R/W 和 U/S 位的判断是操作系统控制权限实现方式
除了和I/O紧密相关的(比如MMIO),大部分情况下都是 cache enable, write back, 即 PTW=PCD=1
A/D 位的设计是硬件到软件的一个经典的沟通方式, 硬件访问页面置标记位然后由软件统计数据, 用于后续的页面迁移, 回收等操作
G 位只有 kernel page 才会置 1

前面我们提到 Intel 的 CPU TLB 会保留每个进程的 PCID 用于减缓进程页表切换, 64位CR3中加入了对PCID的支持,因为CR3存放的是当前进程的页表首地址,所以CR3是最适合放PCID的了,但是高16位通常保留,所以只能塞到低12位和PCD,PWT共用bit位了, 如下图所示