| 本篇位置 | 专门解决第 12 篇留下的账二：页表太大 |
| 运行环境 | 容器里的 Linux，Python 3 |
一、账二：512 GB 的页表
第 12 篇算过：48 位地址空间、4 KB 页、每项 8 字节，朴素做法要 512 GB，每个进程一份。
这个数字荒谬到你应该当场停下来。 你这台机器上此刻跑着几百个进程，要是每个都需要 512 GB 的页表，光页表就要几十 TB——而你的内存只有几十 GB，机器却跑得好好的。
回头看第 12 篇那个实测：VmPTE（页表占的内存）只有 196 kB。
差了六个数量级。 这一篇讲这六个数量级是怎么省下来的。
二、省在哪：地址空间几乎全是空的
回头看第 8 篇那张 maps 表。一个进程用到的地址长这样：
0x00400000 代码、数据 几 MB
0x24000000 堆 几 MB
...
← 中间隔着几十 TB 什么都没有 →
...
0xffffdb1ad000 栈 132 KB
中间那几十 TB 是空的。 不是"没数据"，是根本没有任何一个合法地址落在那里。
朴素页表的荒谬之处就在于：它给那几十 TB 也准备了页表项，每一项都老老实实写着"无效"。
⭐ 所以问题变成了：怎么让"一大片连续的无效项"不占地方？
打个比方
酒店的对照表，现在改一下做法。
朴素做法是一本按房号从 1 号排到一千万号的大账本——哪怕 200 号到 900 万号之间一间都没开，这几百万行也印在那儿。
多级做法是：先做一本目录册，一页对应一个楼层。要查 307 房，先翻目录册找到"3 楼"，目录册告诉你"3 楼的详表在第 12 号抽屉"，再去那个抽屉里查。
关键在这句话：如果整个 47 楼一间房都没开，目录册里"47 楼"那一格就直接写"没有"——那一层的详表压根不用做。
⭐ 省下来的不是某几行，是整本子册。 这就是多级页表的全部想法。
三、机制：把页表本身也分页
把虚拟页号再切成几段，每段索引一级：
虚拟地址（48 位）
┌────────┬────────┬────────┬────────┬──────────────┐
│ 一级 9 │ 二级 9 │ 三级 9 │ 四级 9 │ 页内偏移 12 │
└────────┴────────┴────────┴────────┴──────────────┘
│ │ │ │
▼ ▼ ▼ ▼
顶级表 → 二级表 → 三级表 → 末级表 → 物理帧号
每一级 9 位 = 512 项，每项 8 字节 = 4096 字节，正好一页。这不是巧合——每一级的表本身就是一个页，可以用管理普通页的那套机制来管它（甚至可以被换出去）。
四级 × 9 位 + 12 位偏移 = 48 位。这就是 x86-64 和 arm64 的标准布局。
省在哪： 如果顶级表里某一项是空的，它下面那整棵子树的表全都不用存在。一个顶级项覆盖 2⁹×2⁹×2⁹×4096 = 512 GB 的地址空间——一格写"没有"，512 GB 的页表就省掉了。
⭐ 所以 VmPTE 只有 196 kB：一个真实进程用到的地址空间，只落在极少数几棵子树上。
四、⭐ 跑一遍看看：这个机制的边界在哪
多级页表省的是整块的空。那如果你的数据不是"挤在几处"，而是"稀稀拉拉散得到处都是"呢？
这个问题可以直接量。下面两次实验，碰的页数完全一样（1000 页），数据量完全一样（4 MB），唯一的区别是这 1000 页离得多远：
# sparse.py
import mmap, os
PAGE = os.sysconf("SC_PAGESIZE")
def vm(key):
for line in open("/proc/self/status"):
if line.startswith(key + ":"):
return int(line.split()[1])
def trial(tag, span_bytes, n_pages):
m = mmap.mmap(-1, span_bytes)
stride = span_bytes // n_pages
r0, p0 = vm("VmRSS"), vm("VmPTE")
for i in range(n_pages):
m[i * stride] = 1
r1, p1 = vm("VmRSS"), vm("VmPTE")
print(f" {tag:<34} 摸了 {n_pages} 页 RSS +{r1-r0:>6} kB 页表 VmPTE +{p1-p0:>6} kB")
m.close()
print(f"两次都只碰 1000 个页面，总共就 4 MB 数据。区别只是这 1000 页离得多远：\n")
trial("挨着摸（跨度 4 MB）", 4 << 20, 1000)
trial("散着摸（跨度 2 GB，每 2 MB 一页）", 2 << 30, 1000)
两次都只碰 1000 个页面，总共就 4 MB 数据。区别只是这 1000 页离得多远：
挨着摸（跨度 4 MB） 摸了 1000 页 RSS + 4248 kB 页表 VmPTE + 8 kB
散着摸（跨度 2 GB，每 2 MB 一页） 摸了 1000 页 RSS + 4000 kB 页表 VmPTE + 4008 kB
同样 4 MB 数据。页表一个涨了 8 KB，一个涨了 4008 KB——五百倍。
而且注意第二行那个数字：页表本身（4008 KB）比数据本身（4000 KB）还大。
为什么？因为末级页表一张覆盖 512 个连续页 = 2 MB。
- 挨着摸：1000 个连续页只跨了 2 张末级表，8 KB。
- 散着摸：每 2 MB 摸一页，每一页都落在一张不同的末级表上——1000 页就要 1000 张表，每张 4 KB，正好 4000 KB。每张表里只有一项是有用的，另外 511 项全是空的。
⭐ 多级页表省的是"整块的空"，省不了"稀稀拉拉的空"。 稀疏到一定程度，它就退化回朴素方案还要更糟——因为多了几级中间表。
回到那本目录册：它省事的前提是"整层楼都没开房"。 而"散着摸"相当于每一层各开了一间房——目录册上每一格都得写"有"，每一层的详表都得做出来，而每张详表上只有一行是有内容的，另外 511 行全空着。册子比住的人还厚。
这条结论有很实际的用处：“内存用得少"和"地址空间用得紧凑"是两件事。 一个到处 mmap 小块、把数据撒在整个地址空间里的程序，页表开销会大得离谱，而 top 里的 RES 看不出这一点（VmPTE 才看得出）。
五、还有两个代价
代价一：查表变成四次
朴素页表未命中时查一次内存，四级页表要查四次。加上最后取数据，一共五次内存访问。
这就是第 13 篇 TLB 那个台阶为什么那么陡——TLB 未命中的代价不是一次内存访问，是四次。
补救办法是给中间几级也加缓存（page walk cache），CPU 里真的有。
代价二：一个巧妙的攻击面
页表结构本身会泄露信息。一次 TLB 未命中要查几级、每级落在哪个缓存行上，这些都能被旁边的进程通过时间间接观察到。第 30 篇讲。
六、别的路子（以及它们为什么没赢）
多级页表不是唯一解。历史上还有两条：
倒排页表（inverted page table）：不给每个虚拟页一项，而是给每个物理帧一项，记录"这一帧现在属于谁的哪个虚拟页”。
好处是大小只和物理内存有关，和地址空间大小无关——4 GB 内存就是 100 万项，不管有多少个进程。
坏处是查找方向反了。你手上有虚拟页号，要找物理帧，得搜索整张表。得配哈希表，而哈希冲突让最坏情况不可控。PowerPC 和 Itanium 用过，没有推广开。
多级 + 大页混合：这是今天真正在用的补充手段。x86-64 允许在第二级或第三级就"停下来"，直接指向一个 2 MB 或 1 GB 的大页。
⭐ 这一下同时省了两笔：末级页表整张不用建（省内存），一条 TLB 项覆盖 512 倍的范围（省第 13 篇那笔）。代价是内部碎片和对连续物理内存的要求——第 11 篇那个碎片问题第三次回来了。
七、小结
- 朴素页表要 512 GB，实测
VmPTE只有 196 kB。差距来自真实地址空间几乎全是空的。 - 多级页表把页表本身也分页。每级 9 位 = 512 项 = 正好一页。顶级表里一格写"没有"，下面 512 GB 的页表就整棵省掉。
- ⭐ 实测：同样碰 1000 页、同样 4 MB 数据，挨着碰页表涨 8 KB，散着碰涨 4008 KB——五百倍，而且页表比数据还大。因为末级表一张覆盖 2 MB，散着碰时每张表里只有一项有用。
- ⭐ 它省的是"整块的空"，省不了"稀稀拉拉的空"。“内存用得少"和"地址空间用得紧凑"是两件事，后者只有
VmPTE看得出来。 - 代价一：TLB 未命中要查四次内存，这是第 13 篇那个台阶陡的原因。
- 别的路：倒排页表大小只和物理内存有关，但查找方向反了、要哈希，没推广开；大页同时省页表和 TLB，代价是内部碎片和连续物理内存的要求——第 11 篇的碎片问题第三次回来。
思考题
- 第四节"散着摸"的例子里，如果把跨度从 2 MB 改成 1 GB，
VmPTE会怎么变？（提示：算一下要跨几张三级表。） - 每一级页表本身就是一个页。那么，页表能不能被换出到磁盘？如果能，会有什么麻烦？
- 倒排页表的大小只和物理内存有关。这听起来对"很多进程"的场景特别友好。那为什么它还是输了？（提示：想想第 13 篇讲的 TLB 未命中频率。）
- 目录册那个比方里，“大页"对应什么操作？（提示：目录册翻到某一层时，直接就给出了答案，不用再去抽屉里翻。）