每个程序员都应该了解的“虚拟内存”知识
英文原文：Memory part 3: Virtual Memory
编辑注：本文是 Ulrich Drepper 的“每个程序员应该了解的内存方面的知识”文章的第三部分；这一部分谈论了虚拟内存，特别是 TLB 性能。没有阅读第 1 部分和第 2 部分的人可能现在就想读一读了。和往常一样，请将排字错误报告之类发送到 lwn@lwn.net，而不要发送到这里的评论。
4 虚拟内存
处理器的虚拟内存子系统为每个进程实现了虚拟地址空间。这让每个进程认为它在系统中是独立的。虚拟内存的优点列表别的地方描述的非常详细，所以这里就不重复了。本节集中在虚拟内存的实际的实现细节，和相关的成本。
虚拟地址空间是由 CPU 的内存管理单元(MMU)实现的。OS 必须填充页表数据结构，但大多数 CPU 自己做了剩下的工作。这事实上是一个相当复杂的机制；最好的理解它的方法是引入数据结构来描述虚拟地址空间。
由 MMU 进行地址翻译的输入地址是虚拟地址。通常对它的值很少有限制 — 假设还有一点的话。 虚拟地址在 32 位系统中是 32 位的数值，在 64 位系统中是 64 位的数值。在一些系统，例如 x86 和 x86-64，使用的地址实际上包含了另一个层次的间接寻址：这些结构使用分段，这些分段只是简单的给每个逻辑地址加上位移。我们可以忽略这一部分的地址 产生，它不重要，不是程序员非常关心的内存处理性能方面的东西。{x86 的分段限制是与性能相关的，但那是另一回事了}
4. 1 最简单的地址转换
有趣的地方在于由虚拟地址到物理地址的转换。MMU 可以在逐页的基础上重新映射地址。就像地址缓存排列的时候，虚拟地址被分割为不同的部分。这些部分被用来做多个表的索引，而这些表是被用来创建最终物理地址用的。最简单的模型是只有一级表。
Figure 4.1: 1-Level Address Translation
图 4.1 显示了虚拟地址的不同部分是如何使用的。高字节部分是用来选择一个页目录的条目；那个目录中的每个地址可以被 OS 分别设置。页目录条目决定了物理内存页的地址；页面中可以有不止一个条目指向同样的物理地址。完整的内存物理地址是由页目录获得的页地址和虚拟地址低字节 部分合并起来决定的。页目录条目还包含一些附加的页面信息，如访问权限。
页目录的数据结构存储在内存中。OS 必须分配连续的物理内存，并将这个地址范围的基地址存入一个特殊的寄存器。然后虚拟地址的适当的位被用来作为页目录的索引，这个页目录事实上是目录条目的列表。
作为一个具体的例子，这是 x86 机器 4MB 分页设计。虚拟地址的位移部分是 22 位大小，足以定位一个 4M 页内的每一个字节。虚拟地址中剩下的 10 位指定页目录中 1024 个条目的一个。每个条目包括一个 10 位的 4M 页内的基地址，它与位移结合起来形成了一个完整的 32 位地址。
4. 2 多级页表
4MB 的页不是规范，它们会浪费很多内存，因为 OS 需要执行的许多操作需要内存页的队列。对于 4kB 的页（32 位机器的规范，甚至通常是 64 位机器的规范），虚拟地址的位移部分只有 12 位大小。这留下了 20 位作为页目录的指针。具有220个条目的表是不实际的。即使每个条目只要 4 比特，这个表也要 4MB 大小。由于每个进程可能具有其唯一的页目录，因为这些页目录许多系统中物理内存被绑定起来。
解决办法是用多级页表。然后这些就能表示一个稀疏的大的页目录，目录中一些实际不用的区域不需要分配内存。因此这种表示更紧凑，使它可能为内存中的很多进程使用页表而并不太影响性能。.
今天最复杂的页表结构由四级构成。图 4.2 显示了这样一个实现的原理图。
Figure 4.2: 4-Level Address Translation
在这个例子中，虚拟地址被至少分为五个部分。其中四个部分是不同的目录的索引。被引用的第 4 级目录使用 CPU 中一个特殊目的的寄存器。第 4 级到第 2 级目录的内容是对次低一级目录的引用。如果一个目录条目标识为空，显然就是不需要指向任何低一级的目录。这样页表树就能稀疏和紧凑。正如图 4.1，第 1 级目录的条目是一部分物理地址，加上像访问权限的辅助数据。
为了决定相对于虚拟地址的物理地址，处理器先决定最高级目录的地址。这个地址一般保存在一个寄存器。然后 CPU 取出虚拟地址中相对于这个目录的索引部分，并用那个索引选择合适的条目。这个条目是下一级目录的地址，它由虚拟地址的下一部分索引。处理器继续直到它到达 第 1 级目录，那里那个目录条目的值就是物理地址的高字节部分。物理地址在加上虚拟地址中的页面位移之后就完整了。这个过程称为页面树遍历。一些处理器（像 x86 和 x86-64）在硬件中执行这个操作，其他的需要 OS 的协助。
系统中运行的每个进程可能需要自己的页表树。有部分共享树的可能，但是这相当例外。因此如果页表树需要的内存尽可能小的话将对性能与可扩展性有 利。理想的情况是将使用的内存紧靠着放在虚拟地址空间；但实际使用的物理地址不影响。一个小程序可能只需要第2，3，4 级的一个目录和少许第 1 级目录就能应付过去。在一个采用 4kB 页面和每个目录 512 条目的 x86-64 机器上，这允许用 4 级目录对 2MB 定位（每一级一个）。1GB 连续的内存可以被第 2 到第 4 级的一个目录和第 1 级的 512 个目录定位。
但是，假设所有内存可以被连续分配是太简单了。由于复杂的原因，大多数情况下，一个进程的栈与堆的区域是被分配在地址空间中非常相反的两端。这样使得任一个区域可以根据需要尽可能的增长。这意味着最有可能需要两个第 2 级目录和相应的更多的低一级的目录。
但即使这也不常常匹配现在的实际。由于安全的原因，一个可运行的（代码，数据，堆，栈，动态共享对象，aka 共享库）不同的部分被映射到随机的地址[未选中的]。随机化延伸到不同部分的相对位置；那意味着一个进程使用的不同的内存范围，遍布于虚拟地址空间。通过 对随机的地址位数采用一些限定，范围可以被限制，但在大多数情况下，这当然不会让一个进程只用一到两个第 2 和第 3 级目录运行。
如果性能真的远比安全重要，随机化可以被关闭。OS 然后通常是在虚拟内存中至少连续的装载所有的动态共享对象(DSO)。
4. 3 优化页表访问
页表的所有数据结构都保存在主存中；在那里 OS 建造和更新这些表。当一个进程创建或者一个页表变化，CPU 将被通知。页表被用来解决每个虚拟地址到物理地址的转换，用上面描述的页表遍历方式。更多有关于此：至少每一级有一个目录被用于处理虚拟地址的过程。这需 要至多四次内存访问（对一个运行中的进程的单次访问来说），这很慢。有可能像普通数据一样处理这些目录表条目，并将他们缓存在 L1d,L2 等等，但这仍然非常慢。
从虚拟内存的早期阶段开始，CPU 的设计者采用了一种不同的优化。简单的计算显示，只有将目录表条目保存在 L1d 和更高级的缓存，才会导致可怕的性能问题。每个绝对地址的计算，都需要相对于页表深度的大量的 L1d 访问。这些访问不能并行，因为它们依赖于前面查询的结果。在一个四级页表的机器上，这种单线性将至少至少需要 12 次循环。再加上 L1d 的非命中的可能性，结果是指令流水线没有什么能隐藏的。额外的 L1d 访问也消耗了珍贵的缓存带宽。
所以，替代于只是缓存目录表条目，物理页地址的完整的计算结果被缓存了。因为同样的原因，代码和数据缓存也工作起来，这样的地址计算结果的缓存 是高效的。由于虚拟地址的页面位移部分在物理页地址的计算中不起任何作用，只有虚拟地址的剩余部分被用作缓存的标签。根据页面大小这意味着成百上千的指令 或数据对象共享同一个标签，因此也共享同一个物理地址前缀。
保存计算数值的缓存叫做旁路转换缓存(TLB)。因为它必须非常的快，通常这是一个小的缓存。现代 CPU 像其它缓存一样，提供了多级 TLB 缓存；越高级的缓存越大越慢。小号的 L1 级 TLB 通常被用来做全相联映像缓存，采用 LRU 回收策略。最近这种缓存大小变大了，而且在处理器中变得集相联。其结果之一就是，当一个新的条目必须被添加的时候，可能不是最久的条目被回收于替换了。
正如上面提到的，用来访问 TLB 的标签是虚拟地址的一个部分。如果标签在缓存中有匹配，最终的物理地址将被计算出来，通过将来自虚拟地址的页面位移地址加到缓存值的方式。这是一个非常快 的过程；也必须这样，因为每条使用绝对地址的指令都需要物理地址，还有在一些情况下，因为使用物理地址作为关键字的 L2 查找。如果 TLB 查询未命中，处理器就必须执行一次页表遍历；这可能代价非常大。
通过软件或硬件预取代码或数据，会在地址位于另一页面时，暗中预取 TLB 的条目。硬件预取不可能允许这样，因为硬件会初始化非法的页面表遍历。因此程序员不能依赖硬件预取机制来预取 TLB 条目。它必须使用预取指令明确的完成。就像数据和指令缓存，TLB 可以表现为多个等级。正如数据缓存，TLB 通常表现为两种形式：指令 TLB (ITLB)和数据 TLB (DTLB)。高级的 TLB 像 L2TLB 通常是统一的，就像其他的缓存情形一样。
4. 3.1 使用 TLB 的注意事项
TLB 是以处理器为核心的全局资源。所有运行于处理器的线程与进程使用同一个 TLB。由于虚拟到物理地址的转换依赖于安装的是哪一种页表树，如果页表变化了，CPU 不能盲目的重复使用缓存的条目。每个进程有一个不同的页表树（不算在同一个进程中的线程），内核与内存管理器 VMM (管理程序)也一样，如果存在的话。也有可能一个进程的地址空间布局发生变化。有两种解决这个问题的办法：
- 当页表树变化时 TLB 刷新。
- TLB 条目的标签附加扩展并唯一标识其涉及的页表树
第一种情况，只要执行一个上下文切换 TLB 就被刷新。因为大多数 OS 中，从一个线程/进程到另一个的切换需要执行一些核心代码，TLB 刷新被限制进入或离开核心地址空间。在虚拟化的系统中，当内核必须调用内存管理器 VMM 和返回的时候，这也会发生。如果内核和/或内存管理器没有使用虚拟地址，或者当进程或内核调用系统/内存管理器时，能重复使用同一个虚拟地址，TLB 必须被刷新。当离开内核或内存管理器时，处理器继续执行一个不同的进程或内核。
刷新 TLB 高效但昂贵。例如，当执行一个系统调用，触及的内核代码可能仅限于几千条指令，或许少许新页面（或一个大的页面，像某些结构的 Linux 的就是这样）。这个工作将替换触及页面的所有 TLB 条目。对 Intel 带 128ITLB 和 256DTLB 条目的 Core2 架构，完全的刷新意味着多于 100 和 200 条目（分别的）将被不必要的刷新。当系统调用返回同一个进程，所有那些被刷新的 TLB 条目可能被再次用到，但它们没有了。内核或内存管理器常用的代码也一样。每条进入内核的条目上，TLB 必须擦去再装，即使内核与内存管理器的页表通常不会改变。因此理论上说，TLB 条目可以被保持一个很长时间。这也解释了为什么现在处理器中的 TLB 缓存都不大：程序很有可能不会执行时间长到装满所有这些条目。
当然事实逃脱不了 CPU 的结构。对缓存刷新优化的一个可能的方法是单独的使 TLB 条目失效。例如，如果内核代码与数据落于一个特定的地址范围，只有落入这个地址范围的页面必须被清除出 TLB。这只需要比较标签，因此不是很昂贵。在部分地址空间改变的场合，例如对去除内存页的一次调用，这个方法也是有用的，
更好的解决方法是为 TLB 访问扩展标签。如果除了虚拟地址的一部分之外，一个唯一的对应每个页表树的标识（如一个进程的地址空间）被添加，TLB 将根本不需要完全刷新。内核，内存管理程序，和独立的进程都可以有唯一的标识。这种场景唯一的问题在于，TLB 标签可以获得的位数异常有限，但是地址空间的位数却不是。这意味着一些标识的再利用是有必要的。这种情况发生时 TLB 必须部分刷新（如果可能的话）。所有带有再利用标识的条目必须被刷新，但是希望这是一个非常小的集合。
当多个进程运行在系统中时，这种扩展的 TLB 标签具有一般优势。如果每个可运行进程对内存的使用（因此 TLB 条目的使用）做限制，进程最近使用的 TLB 条目，当其再次列入计划时，有很大机会仍然在 TLB。但还有两个额外的优势：
- 特殊的地址空间，像内核和内存管理器使用的那些，经常仅仅进入一小段时间；之后控制经常返回初始化此次调用的地址空间。没有标签，就有两次 TLB 刷新操作。有标签，调用地址空间缓存的转换地址将被保存，而且由于内核与内存管理器地址空间根本不会经常改变 TLB 条目，系统调用之前的地址转换等等可以仍然使用。
- 当同一个进程的两个线程之间切换时，TLB 刷新根本就不需要。虽然没有扩展 TLB 标签时，进入内核的条目会破坏第一个线程的 TLB 的条目。
有些处理器在一些时候实现了这些扩展标签。AMD 给帕西菲卡（Pacifica）虚拟化扩展引入了一个 1 位的扩展标签。在虚拟化的上下文中，这个 1 位的地址空间 ID（ASID）被用来从客户域区别出内存管理程序的地址空间。这使得 OS 能够避免在每次进入内存管理程序的时候（例如为了处理一个页面错误）刷新客户的 TLB 条目，或者当控制回到客户时刷新内存管理程序的 TLB 条目。这个架构未来会允许使用更多的位。其它主流处理器很可能会随之适应并支持这个功能。
4. 3.2 影响 TLB 性能
有一些因素会影响 TLB 性能。第一个是页面的大小。显然页面越大，装进去的指令或数据对象就越多。所以较大的页面大小减少了所需的地址转换总次数，即需要更少的 TLB 缓存条目。大多数架构允许使用多个不同的页面尺寸；一些尺寸可以并存使用。例如，x86/x86-64 处理器有一个普通的 4kB 的页面尺寸，但它们也可以分别用 4MB 和 2MB 页面。IA-64 和 PowerPC 允许如 64kB 的尺寸作为基本的页面尺寸。
然而，大页面尺寸的使用也随之带来了一些问题。用作大页面的内存范围必须是在物理内存中连续的。如果物理内存管理的单元大小升至虚拟内存页面的 大小，浪费的内存数量将会增长。各种内存操作（如加载可执行文件）需要页面边界对齐。这意味着平均每次映射浪费了物理内存中页面大小的一半。这种浪费很容 易累加；因此它给物理内存分配的合理单元大小划定了一个上限。
在 x86-64 结构中增加单元大小到 2MB 来适应大页面当然是不实际的。这是一个太大的尺寸。但这转而意味着每个大页面必须由许多小一些的页面组成。这些小页面必须在物理内存中连续。以 4kB 单元页面大小分配 2MB 连续的物理内存具有挑战性。它需要找到有 512 个连续页面的空闲区域。在系统运行一段时间并且物理内存开始碎片化以后，这可能极为困难（或者不可能）
因此在 Linux 中有必要在系统启动的时候，用特别的 Huge TLBfs 文件系统，预分配这些大页面。一个固定数目的物理页面被保留，以单独用作大的虚拟页面。这使可能不会经常用到的资源捆绑留下来。它也是一个有限的池；增大 它一般意味着要重启系统。尽管如此，大页面是进入某些局面的方法，在这些局面中性能具有保险性，资源丰富，而且麻烦的安装不会成为大的妨碍。数据库服务器 就是一个例子。
增大最小的虚拟页面大小（正如选择大页面的相反面）也有它的问题。内存映射操作（例如加载应用）必须确认这些页面大小。不可能有更小的映射。对 大多数架构来说，一个可执行程序的各个部分位置有一个固定的关系。如果页面大小增加到超过了可执行程序或 DSO (Dynamic Shared Object)创建时考虑的大小，加载操作将无法执行。脑海里记得这个限制很重要。图 4.3 显示了一个 ELF 二进制的对齐需求是如何决定的。它编码在 ELF 程序头部。
$ eu-readelf -l /bin/ls Program Headers: Type Offset VirtAddr PhysAddr FileSiz MemSiz Flg Align ... LOAD 0x000000 0x0000000000400000 0x0000000000400000 0x0132ac 0x0132ac R E 0x200000 LOAD 0x0132b0 0x00000000006132b0 0x00000000006132b0 0x001a71 0x001a71 RW 0x200000 ...Figure 4.3: ELF 程序头表明了对齐需求
在这个例子中，一个 x86-64 二进制，它的值为0×200000 = 2,097,152 = 2MB，符合处理器支持的最大页面尺寸。
使用较大内存尺寸有第二个影响：页表树的级数减少了。由于虚拟地址相对于页面位移的部分增加了，需要用来在页目录中使用的位，就没有剩下许多了。这意味着当一个 TLB 未命中时，需要做的工作数量减少了。
超出使用大页面大小，它有可能减少移动数据时需要同时使用的 TLB 条目数目，减少到数页。这与一些上面我们谈论的缓存使用的优化机制类似。只有现在对齐需求是巨大的。考虑到 TLB 条目数目如此小，这可能是一个重要的优化。
4. 4 虚拟化的影响
OS 映像的虚拟化将变得越来越流行；这意味着另一个层次的内存处理被加入了想象。进程（基本的隔间）或者 OS 容器的虚拟化，因为只涉及一个 OS 而没有落入此分类。类似 Xen 或 KVM 的技术使 OS 映像能够独立运行 — 有或者没有处理器的协助。这些情形下，有一个单独的软件直接控制物理内存的访问。
图 4.4: Xen 虚拟化模型
对 Xen 来说（见图 4.4），Xen VMM (Xen 内存管理程序)就是那个软件。但是，VMM 没有自己实现许多硬件的控制，不像其他早先的系统（包括 Xen VMM 的第一个版本）的 VMM，内存以外的硬件和处理器由享有特权的 Dom0 域控制。现在，这基本上与没有特权的 DomU 内核一样，就内存处理方面而言，它们没有什么不同。这里重要的是，VMM 自己分发物理内存给 Dom0 和 DomU 内核，然后就像他们是直接运行在一个处理器上一样，实现通常的内存处理
为了实现完成虚拟化所需的各个域之间的分隔，Dom0 和 DomU 内核中的内存处理不具有无限制的物理内存访问权限。VMM 不是通过分发独立的物理页并让客户 OS 处理地址的方式来分发内存；这不能提供对错误或欺诈客户域的防范。替代的，VMM 为每一个客户域创建它自己的页表树，并且用这些数据结构分发内存。好处是对页表树管理信息的访问能得到控制。如果代码没有合适的特权，它不能做任何事。 在虚拟化的 Xen 支持中，这种访问控制已被开发，不管使用的是参数的或硬件的（又名全）虚拟化。客户域以意图上与参数的和硬件的虚拟化极为相似的方法，给每个进程创建它们 的页表树。每当客户 OS 修改了 VMM 调用的页表，VMM 就会用客户域中更新的信息去更新自己的影子页表。这些是实际由硬件使用的页表。显然这个过程非常昂贵：每次对页表树的修改都需要 VMM 的一次调用。而没有虚拟化时内存映射的改变也不便宜，它们现在变得甚至更昂贵。 考虑到从客户 OS 的变化到 VMM 以及返回，其本身已经相当昂贵，额外的代价可能真的很大。这就是为什么处理器开始具有避免创建影子页表的额外功能。这样很好不仅是因为速度的问题，而且它 减少了 VMM 消耗的内存。Intel 有扩展页表(EPTs)，AMD 称之为嵌套页表(NPTs)。基本上两种技术都具有客户 OS 的页表，来产生虚拟的物理地址。然后通过每个域一个 EPT/NPT 树的方式，这些地址会被进一步转换为真实的物理地址。这使得可以用几乎非虚拟化情境的速度进行内存处理，因为大多数用来内存处理的 VMM 条目被移走了。它也减少了 VMM 使用的内存，因为现在一个域（相对于进程）只有一个页表树需要维护。 额外的地址转换步骤的结果也存储于 TLB。那意味着 TLB 不存储虚拟物理地址，而替代以完整的查询结果。已经解释过 AMD 的帕西菲卡扩展为了避免 TLB 刷新而给每个条目引入 ASID。ASID 的位数在最初版本的处理器扩展中是一位；这正好足够区分 VMM 和客户 OS。Intel 有服务同一个目的的虚拟处理器 ID (VPIDs)，它们只有更多位。但对每个客户域 VPID 是固定的，因此它不能标记单独的进程，也不能避免 TLB 在那个级别刷新。
对虚拟 OS，每个地址空间的修改需要的工作量是一个问题。但是还有另一个内在的基于 VMM 虚拟化的问题：没有什么办法处理两层的内存。但内存处理很难（特别是考虑到像 NUMA 一样的复杂性，见第 5 部分）。Xen 方法使用一个单独的 VMM，这使最佳的（或最好的）处理变得困难，因为所有内存管理实现的复杂性，包括像发现内存范围之类“琐碎的”事情，必须被复制于 VMM。OS 有完全成熟的与最佳的实现；人们确实想避免复制它们。
图 4.5: KVM 虚拟化模型
这就是为什么对 VMM/Dom0 模型的分析是这么有吸引力的一个选择。图 4.5 显示了 KVM 的 Linux 内核扩展如何尝试解决这个问题的。并没有直接运行在硬件之上且管理所有客户的单独的 VMM，替代的，一个普通的 Linux 内核接管了这个功能。这意味着 Linux 内核中完整且复杂的内存管理功能，被用来管理系统的内存。客户域运行于普通的用户级进程，创建者称其为“客户模式”。虚拟化的功能，参数的或全虚拟化的， 被另一个用户级进程 KVM VMM 控制。这也就是另一个进程用特别的内核实现的 KVM 设备，去恰巧控制一个客户域。
这个模型相较 Xen 独立的 VMM 模型好处在于，即使客户 OS 使用时，仍然有两个内存处理程序在工作，只需要在 Linux 内核里有一个实现。不需要像 Xen VMM 那样从另一段代码复制同样的功能。这带来更少的工作，更少的 bug，或许还有更少的两个内存处理程序接触产生的摩擦，因为一个 Linux 客户的内存处理程序与运行于裸硬件之上的 Linux 内核的外部内存处理程序，做出了相同的假设。
总的来说，程序员必须清醒认识到，采用虚拟化时，内存操作的代价比没有虚拟化要高很多。任何减少这个工作的优化，将在虚拟化环境付出更多。随着时间的过去，处理器的设计者将通过像 EPT 和 NPT 技术越来越减少这个差距，但它永远都不会完全消失。