操作系统基础-内存虚拟化

原文发布于微信公众号 - 云服务与SRE架构师社区（ai-cloud-ops），作者李勇。

前言

在CPU虚拟化中我们采用的是分时复用的机制——在不同的时刻运行不同的进程；而在内存虚拟化中需要用到另一种复用技术——空间复用，即把物理内存的不同部分划分给不同的进程。但是如果每个进程在运行时需要先知道自己的物理内存地址，比如说某个指针的物理地址是什么，这对编译器和开发者来说都是非常不友好的， 从易用性的角度出发，我们希望所有进程的地址空间都是类似的。因此操作系统引入了一层转换，隐式地把进程看到的地址（逻辑地址）转换成实际的物理内存地址（物理地址）。

进程地址空间

在研究逻辑地址到物理地址的转换前，先来看看一个进程的地址空间(Space Address)需要包含什么内容，我们先以一个非常小的地址空间为起点，它总共只有16K，也就是说这个进程只能使用16K的内存。

只需要14位的无符号数就能完整地表示这16K的地址，类似地32位地址可以表示4GiB的地址空间，而目前的64位系统通常只使用48位，地址空间大小为256TiB。

图1-进程地址空间

大体来说，这个地址空间可以分成3个段（Segment)：

1. 代码段（图中0-1KB的部分），程序的二进制指令保存在这里
2. 用来存放动态数据的堆（Heap，图中1-2KB的部分）， malloc的内存就从这里申请，当现有堆大小不够的时候往高地址扩展
3. 用来追踪函数调用的栈（Stack，途中16-15KB的部分），里面保存了每个函数调用中的局部变量，参数等信息，每层函数调用都会导致堆往低地址扩展

这个地址空间忽略了很多东西，比如代码段和堆之前还有全局变量，BSS段等。但是我们可以看到，这个地址空间是相当稀疏的，堆和栈之间有一大片地址没有利用起来。

假设我们有很多个进程，怎么把每个进程的逻辑地址空间映射到物理地址呢？

Base and Bounds

最简单的机制叫做Base and Bounds，因为每个进程的地址空间大小都是固定，只需要把物理内存按照同样的大小分割，按需分配给不同的进程即可。比如下图中，物理地址的32-48K被分配给了一个进程。

图2 - Base and Bounds

具体实现上，CPU上有两个寄存器用来记录这些信息：

• Base 寄存器用来记录当前进程在物理内存的起始位置(32K)
• Bounds 寄存器用来记录该进程地址空间的边界（16K）

毫无疑问，这两个寄存器的值在上下切换的时候需要保存到PCB中。

操作系统进行逻辑地址到物理地址的转换时非常容易，只要给逻辑地址加上Base寄存器的值即可。然而这种模式有很严重的问题:

1. 这个地址空间太小，虽然我们可以放大这个地址空间（比如说640K……），但无论如何不能超过物理内存的大小
2. 更严重的是，堆和栈之间有一大片分配了却没有使用的地址，地址空间越大，这里的浪费越明显

段式寻址

为了解决Base and Bounds的问题，人们引入了段式寻址(Segmentation)，CPU上不是一组Base 和 Bounds寄存器，地址空间的每一个段（Segment）都有各自单独的一组Base 和 Bounds寄存器。因此进程的代码段，堆和栈可以分配到物理内存的不同位置，而不需要占据连续的空间：

图3 - Segmentation

这里有一个问题，当进程引用一个逻辑地址的时候，怎么知道它是那个段呢？VAX/VMS里面采用了地址的前两位来区分：

段式寻址带来的另一个好处是，如果运行同一个程序的多个副本时，因为代码段是只读的，这些进程的代码段可以映射到同一个物理内存区域。

但是段式寻址没有解决根本问题，假如一个进程申请了一个巨大的堆，比如说1GB，然后释放了这1GB里面大部分的空间，只留下开头和结尾各1KB的空间，这同样导致的浪费。我们需要更精细的内存分配手段。

Pagetable

解决这个问题的思路是每次只分配一小片内存，按需分配，这一小片内存的大小通常为4KB，称之为一页（page）。按照同样的大小切割逻辑地址空间和物理地址空间，比如前面16K的地址空间可以划分成4个逻辑页（Virtual Page），编号为0-3；我们再假设物理内存大小为32K，因此可以划分成8个物理页（page Frame），编号为0-7。

这时需要一个数据结构来记录逻辑地址到物理地址的映射关系，最简单的形式就是数组，这个数组称为页表(pagetable)，数组的每一个元素称为页表项目(Page Table Entry，或PTE)，其内容就是这个逻辑页对应的物理页编号（Page Frame Number）。对于16K的逻辑地址空间，每个进程只需要一个大小为4的页表就足够记录其逻辑地址和虚拟地址的对应关系，例如：

图4-页表

图5-物理内存

上图可以看到，进程的逻辑页0、1、3分别映射到物理页3、7、2，而逻辑页2没有使用，因此处于没有分配的状态。这里需要一个叫做valid bit的标记位来确定该页是否已经映射到物理内存。

地址翻译

操作系统在创建进程的时候需要把这个进程的页表放置到物理内存的某个位置（为简单起见，我们假设它存在内核中），然后把这个页表的内存地址写入到CPU中的页表基址寄存器（Page Table Base Register，或PTBR)中。在x86中，这个寄存器叫做CR3。

假设要把逻辑地址16383翻译成物理地址，过程如下：

1. 把16383的二进表示（11111111111111,一共14个1）拆成两部分，后面12位（对应4K页大小）作为页内偏移量（offset），前2位为作为页表索引（Virtual Page Number，或VPN），转换成10进制标的话：
   1. offset = 4095
   2. VPN = 3
2. CPU从PTBR中读取出进程的页表
3. 从页表中读出第3项（即VPN指向的PTE），从图4中可以看到，它的内容是2，表示这个逻辑页对应第2个物理页。
4. 最后可以计算出逻辑地址16383对应的物理地址 2(逻辑页编号) × 4K（页大小） + 4095 (offset) = 12287

Swapping

有些时候，物理内存实在放不下所有进程需要的页，这时候可以在硬盘中划分一个swap分区，把不常用的页换出(Swap out) 到swap分区中，这样物理内存能空出一部分放置别的内容。当需要访问swap分区中的内容时，再用类似的方式淘汰其他不常用的内容，在把swap分区的内容换入（Swap in)到物理内存中。

因此，PTE中其实需要一个叫做present bit的标记位，用来标记这个页对应的内容是否在物理内存中。如果preset bit为1，说明对应的页在物理内存中，PTE的内容表示对应的物理页（PFN）；如果为0,说明这个页不在内存中，操作系统可以使用PTE来保存这个页在swap分区中的位置。

Page Table Entry

读者们会注意到，PTE不像图4中展示的那么简单，它至少应该包含两个标记位：

• Valid bit: 标记该页是否已经映射到物理内存
• Present bit：标记该页是否在物理内存中。一个页可以是Valid，但是not present的，因为它被换出去了。

PTE上通常还会有些别的标记为，来看看X86的PTE：

图6 - x86 PTE

• present bit(P)：表示页是否在内存中
• read/write bit(P)：页是否可写
• user/supervisor(P)：用户是否可访问这些页
• PTW/PCD/PAT/G：跟硬件缓存相关
• access bit（A)：该页最近是否访问过，操作系统可以依赖这个位来制定swap的策略
• dirty bit(D)：是否有脏数据需要写回到硬盘的。为什么会有这个位？因为物理页还可以用来缓存文件或者块设备的内容，设置了direct bit的内容需要定期写回到硬盘中。
• Page Frame Number(PFN)：该页对应的物理页号。

我们可以发现：

1. 这里缺少了一个valid bit，linux用别的方式实现了valid bit，如果整个PTE的内容全为0，那么这个页是未映射的。
2. 跟文件系统相比，这里缺少了一个可执行权限的判断，攻击者这可以通过缓冲区溢出攻击漏洞在栈中注入可恶意代码，参考《CS:APP Attack Lab: 缓冲区溢出攻击》（https://cloud.tencent.com/developer/article/1590156）。后来x86_64中添加了禁止执行位（No-Execute bit，或NX）来解决这个问题。

有些硬件采用了讨厌的段页式的混合寻址，现代操作系统已经不用这种模式了。

Translation Lookaside Buffer

Pagetable 目前看起来很美好，但是它太慢了，每一次访问内存（包括读取代码段的指令）都额外的计算以及多一次的内存操作：

1. 根据地址计算出这个地址所在页以及offset
2. 根据PTBR，从物理内存中读取PTE
3. 根据PTE和offset计算出物理地址
4. 从物理地址读取实际内容

一个简单的movl 21, %eax (把逻辑地址21指向的值移动到寄存器%eax)需要4次内存操作，读取这条指令本身需要2次，读取逻辑地址21的内容同样需要2次。

解决方案是在CPU上设置一个页表的缓存，这就是（Translation Lookaside Buffer）TLB，每次做地址转换的时候首先检查对应的页地址是否在TLB中，如果在的话（TLB命中）就省下了一次额外的内存访问。由于局部性原理，这个模式工作得很好。

多级页表

pagetable的另一个问题是，它太大了，以x86为例，我们知道PTE的大小是4字节，每一个PTE指向一个4K的页，要完整的表示32位地址空间（4G）需要4G / 4K * 4 = 4MB。假设系统中运行了100个进程，那么这些进程什么都不做的情况下，光是所有进程的页表就占用了400MiB的内存。读者朋友不妨计算一下64位系统会是什么情况？

这个问题的解决方案是使用多级页表，以一个二级页表为例，一级页表的每一项不再指向一个PTE，而是一个叫Page Directory的页；Page Directory包含多个PTE，如下图右边所示：

图7 - 线性页表（左边）和多级页表（右边）

那么多级页表是如何节省空间的呢？如果某个Page Directory中所有的PTE都没有映射，那么直接不分配这个Page Directory，并且在父页表对应的项中把present bit设置为0。

来看一个现实的例子，x86_64中采用了4级页表，每级页表包含512个PTE，每个PTE的大小是8字节，512*8正好是4K，即一个页的大小：

图8 - x86_64 四级页表

关于作者

不怎么务正业的程序员，BUG制造者、CPU0杀手。从事过开发、运维、SRE、技术支持等多个岗位。原Oracle系统架构和性能服务团队成员，目前在腾讯从事运营系统开发。