Lecture 19: Virtual Memory

目录 · ← l18 · l20 →

Lecture 19: Virtual Memory

1. 章节标题与概述

Lecture 19: Virtual Memory（虚拟内存：地址翻译这条”隐藏的访存流水线”）

• 本讲核心问题：程序里的一次 load 只用了一个地址，但这个地址不是内存真正的地址——从虚拟地址（VA, Virtual Address）到物理地址（PA, Physical Address）的翻译发生在每一次访存上，而它必须和”取数据”这件事本身竞争延迟、带宽和缓存容量。本讲要回答三件事：(1) 虚拟内存这套抽象为什么值得（讲义 slide 7 给出两条理由：efficient memory usage 与 programmability）；(2) 硬件如何在没有软件介入的情况下完成翻译（TLB、page walk、TLB 与 cache 的相互作用），以及当翻译成为瓶颈时，用什么技术把延迟压回去（多级 TLB、页走缓存 PWC、把翻译放进数据 cache、大页）；(3) 当页表本身被修改时，如何让 N 个核上私有的 TLB 保持一致——这就是 TLB shootdown，也是并行程序里最容易被忽略的一种”隐式同步”。最后讲义把虚拟内存抽象再叠一层，讲到 虚拟机（Virtual Machine） 与嵌套页表。

• 涉及的主要硬件/软件机制：
  • 翻译层：MMU（Memory Management Unit，内存管理单元）；页（page）与页框；页表（page table）与页表项（PTE, Page Table Entry）；present bit 为 0 → page fault（缺页），由 OS 处理（讲义区分 major page fault：页不在内存，需要从存储取；minor page fault：页已在内存但尚未映射进该进程地址空间，两者都由 OS 处理）。
  • 硬件缓存翻译：TLB（Translation Lookaside Buffer，翻译后备缓冲）、TLB 命中/缺失、page walk（页走）、x86-64 的四级基数页表（multi-level radix page table）（CR3 → PGD → PUD → PMD → PTE，9/9/9/9/12 位切分），以及页走的”指针追逐”本质。
  • 缓解延迟的四种技术（讲义 slide 25/34 反复列出的清单）：multi-level TLBs、Page Walk Cache（PWC，也叫 MMU cache）、caching translations in data caches、larger translations（huge pages，大页）。
  • 翻译一致性（translation coherence）：硬件负责页走、TLB 填充/替换、出错抛异常；OS 负责创建/更新 PTE 并维护跨核一致性——因为硬件不保证 TLB 与 cache/页表之间的一致性（讲义 slide 41 原话：no cache coherence between TLBs and Caches）。跨核传播靠 TLB shootdown：锁 PTE → 计算受害者核集合 → 发 IPI（Inter-Processor Interrupt，处理器间中断） → 本地失效 → 其它核在中断处理里失效并回 ack → 收齐 ack 后解锁。
  • 虚拟化扩展：SVM（System Virtual Machine，系统虚拟机）、VMM/hypervisor、guest VM、real memory 这层新增的地址空间、shadow page table（影子页表） vs nested page tables（嵌套页表，Intel EPT / AMD NPT，寄存器 EPTP）、虚拟化扩展的目标（避免 flush TLB、设备 DMA、guest 处理设备中断等）。

• 在并行计算知识体系中的角色：前几讲（缓存一致性、目录协议、内存一致性模型、同步）讨论的是数据在多个核之间怎么保持一致；本讲讨论的是地址在多个核之间怎么保持一致——两者是同一类问题在不同抽象层的复现：cache 有 per-core 副本所以需要 coherence 协议，TLB 也有 per-core 副本，但它没有硬件协议，只有 OS 的 shootdown，代价随核数超线性增长。同时，本讲是”内存墙”这条主线里最容易被忽视的一层：程序写得再并行，如果访问模式是”每页只碰几个字节”（图遍历、稀疏矩阵、哈希探测、随机指针追逐），那么每次访存都要额外付一次地址翻译，32 核的带宽优势会被翻译延迟吃掉。它也解释了并行程序里两个常见的实测怪象：为什么随机访问的带宽远低于流式带宽（不只是 cache miss，还有 TLB miss + 页走），以及为什么”多线程 + 频繁 mprotect/munmap/fork”（用户态页表管理、GC 写屏障、COW）会突然变得极慢。

• 配套材料：
  • Fall 2026 日程表（https://www.cs.cmu.edu/~418/schedule.html）把 Oct 9 排为第 19 讲 “Virtual Memory”。该行的 slides/video 链接目前仍被 HTML 注释包住，注释文字为 “slides/video from a previous offering; uncomment when posted for Fall 2026:”，其中给出的链接是 lectures/13_virtualmemory.pdf 与一个 YouTube 视频。也就是说：Fall 2026 尚未把本讲的幻灯片/录像正式挂到页面上（页面当前不显示这些链接）。
  • 但该 PDF 本身在公开网络可直接下载：https://www.cs.cmu.edu/~418/lectures/13_virtualmemory.pdf（实测 HTTP 200，1,927,441 字节，Last-Modified 2025-09-30）。本笔记的事实基础就是它——本地副本 lectures/13_virtualmemory.pdf 与逐页抽取文本 extracted/13_virtualmemory.txt（共 59 页，文件内标记 ===== [slide i/59] =====）。因此本讲材料状态为：讲义已公开（归入”上一学期沿用”的 PDF），但 Fall 2026 版尚未在日程表上正式发布；录像未发布。
  • 讲义首页写的是 “CMU 15-418/15-618, Fall 2025 — Lecture 13: Virtual Memory”：讲义沿用历史学期的版本是正常现象（同一份 PDF 在 Fall 2026 的日程表注释里被引用，文件名编号 13 与 Fall 2026 的第 19 讲不对应也是同一原因），不是错误。本笔记正文中标注的 slide 编号，均指这份 59 页 PDF 的页码（i/59）。
  • 未公开部分：历史学期讲义位于 /afs/cs/academic/class/15418-*/public/ 之下，需要 CMU 登录；Ed 讨论区、Autolab、Canvas 均需要登录；本讲录像（Panopto/YouTube）在 Fall 2026 日程表中被注释隐藏，属未发布。
  • Fall 2026 授课教师为 Brian Railing 与 Dimitrios Skarlatos；课程由 Kayvon Fatahalian 创建。
  • 讲义第 3、4 页的”address translation wall”配图注明出自 Zhao et al., “Contiguitas: The Pursuit of Physical Memory Contiguity in Datacenters,” ISCA ‘23（本文只复述该页要传达的定性结论，不复述图中的具体数值）；第 53 页 TLB shootdown 性能图注明出自 Baumann et al., “The Multikernel: a New OS Architecture for Scalable Multicore Systems,” SOSP ‘09；第 54 页 “Further reading” 只给了一个 ASPLOS II (1987) 的 ACM DL 链接，未给标题。
  • 本文档中所有标为”本机实测”的数据都不是讲义内容，而是本文作者为一篇学习笔记所做的公开实验：机器为 2 × AMD EPYC 7V13（64 核/颗，共 128 个硬件线程、无 SMT）、2 个 NUMA 节点、L3 共 512 MiB（16 个 32 MiB 实例）、503 GiB DRAM，Linux + g++ 12.2.0，THP（透明大页）策略为 enabled=always / defrag=madvise；该机为共享节点（实测期间 load average 约 5–7），因此绝对数值会随负载波动，请把它当作数量级与相对趋势的证据。所有代码示例都标注了完整的编译命令。

2. 核心概念与硬件/软件架构图解

2.1 从一个 int array[10] 说起：物理寻址 vs 虚拟寻址

• 定义与目的：讲义 slide 5 用一个最小例子开场：int array[10]——一个值到底住在内存的哪里？处理器怎么找到它？ 这个问题有两个答案。答案一是物理寻址（physical addressing）：CPU 发出的地址就是 DRAM 的地址（讲义 slide 6 的嵌入式微控制器：Core 直接输出 PA）。答案二是虚拟寻址（virtual addressing）：CPU 发出 VA，经过 MMU 翻译成 PA 再访问内存（slide 7）。所有现代系统（服务器、笔记本、手机、平板）都用后者，讲义称之为 “one of the great ideas in computer science”。
• 直观解释（”它是什么？”）：物理寻址像直接报出门牌号：你说”第 16 号楼”，邮差就送到第 16 号楼——简单，但整栋楼只有你能用，别人要住进来就得知道你还空着哪些房间。虚拟寻址像酒店前台 + 房号映射：每位客人拿到的房间号永远是”我的 301 房”（线性、连续、从 0 开始，programmability），而 301 到底对应大楼里哪个物理房间由前台（OS 的页表）决定；前台还可以把长期不用的客人行李寄存到仓库（DRAM 只缓存 VA 空间的一部分 → efficient memory usage），需要时再取回来。客人永远不需要知道真实房间号，也不能去动别人的房间（isolation / protection）。
• 两条收益（讲义 slide 7 明确给出）：
  1. Efficient memory usage（高效利用内存）：物理 DRAM 只装得下虚拟地址空间的一部分，多出来的部分放到更慢更大的存储上（paging），进程的”地址空间”可以远大于物理内存。
  2. Programmability（可编程性）：每个进程拿到一个从 0 开始的线性地址空间，链接器/分配器不用关心物理布局；同时天然获得隔离与保护（每个进程有自己的页表）。
• 架构图解 D1：两种寻址模式的数据通路

  (a) 物理寻址 (简单嵌入式微控制器, 讲义 slide 6)
      ┌────────┐   PA=16 (物理地址直接就是内存地址)
      │  Core  │───────────────┬──────────────────────────┐
      └────────┘               │                          │
                          ┌────▼────┐                ┌────▼────┐
        Main Memory:      │ PA 0    │  1  ...  M-1   │ PA 16   │
                          └─────────┘                └─────────┘
      优点: 无翻译延迟、无页表、硬件极简
      缺点: 没有隔离/保护, 程序必须自己做内存管理, 无法"地址空间 > 物理内存"

  (b) 虚拟寻址 (所有现代系统, 讲义 slide 7)
      ┌────────┐  VA=1300   ┌─────┐  PA=16   ┌──────────────────────┐
      │  Core  │───────────►│ MMU │─────────►│     Main Memory      │
      └────────┘            └──┬──┘          │  0  1 ... PA16 ...   │
      "Issue LD VA 1"          │             └──────────────────────┘
                          ┌────▼─────────────────┐
                          │ Page Tables (在内存里)│  ← OS 维护
                          │  VA 1 ──► PA 4        │
                          │  VA 8 ──► PA 1        │
                          └──────────────────────┘
      关键代价: 每次访存都要"先翻译, 再访问" → 翻译延迟落在关键路径上

• 性能特征：物理寻址下 load 的延迟 = cache/DRAM 延迟。虚拟寻址下理想情况延迟 = TLB 命中延迟 + cache/DRAM 延迟（TLB 命中可与 cache 索引并行，见 2.5）；最坏情况还要加上一次页走（可能 4 次串行访存）。这多出来的一层，就是本讲后半段所有优化技术的靶子。

2.2 页、页表、页表项与缺页

• 定义与目的：虚拟内存抽象的三个动作（讲义 slide 11–14 的动画序列）：
  1. 把物理地址空间切成页（pages）——固定大小，x86-64 的基础页是 4 KB；
  2. 用页表在页粒度上建立 VA→PA 映射；
  3. present bit 为 0 时触发缺页（page fault），OS 把页取进内存并更新页表项。
• PTE 里有什么：至少包括 Present（有效）位、Dirty 位、权限位（读/写/执行、user/supervisor）、以及 Physical Page Number（PPN，物理页号）。讲义 slide 22 的画法很关键：TLB 项里存的是 Valid \| Dirty \| Tag(VPN) \| PPN，其中页内偏移（offset）根本不参与翻译，原封不动地从 VA 的低位复制到 PA 的低位——这也是后面 VIPT 能成立、大页能成立的根本原因。
• 直观解释（”它是什么？”）：页表像搬家时的”旧地址→新地址”对照表，但表太大不能整本带着，于是切成”每个目录 512 条”的多级目录（见 2.4）；页内偏移像门牌号：无论整栋楼叫什么名字，你住的那间房在楼层里的第几号是不变的。缺页（major）像”行李还在仓库里，前台得派人去取”；缺页（minor，讲义 slide 11 的脚注）像”行李其实就在大堂，只是还没登记到你名下”。
• 架构图解 D2：一次访存的完整翻译路径（页表项在内存里）

   应用层            OS 层                     硬件层
 ┌─────────┐    ┌──────────────┐    ┌────────────────────────────────────────┐
 │int a[10]│    │ 创建/更新 PTE│    │  Core                                  │
 │ a[i]    │───►│ 处理 page    │    │   LD  VA ──►[MMU: 查 TLB]              │
 │  VA     │    │ fault        │    │              │命中: 得 PPN            │
 └─────────┘    └──────┬───────┘    │              │缺失: 触发 page walk    │
                       │            │              ▼                        │
                       │            │   PA = PPN:PageOffset ──► [L1/L2/L3]   │
                       │            │                            │miss       │
                       │            │                            ▼           │
                       ▼            │                      ┌───────────────┐  │
              ┌──────────────────┐  └─────────────────────►│ Main Memory   │  │
              │ Page Tables      │  (页走: 读 4 级页表)     │ DRAM          │  │
              │ PGD→PUD→PMD→PTE  │─────────────────────────►└───────────────┘  │
              └──────────────────┘                                             │
                              Present=0 ──► page fault ──► OS 介入(换页/分配)  │

• 性能特征：翻译的粒度是页（4 KB），而数据移动的粒度是 cache line（64 B）——一次 4 KB 的翻译够用 64 条 64 B 的 cache line（讲义 slide 17–20 反复强调的观察）。这带来页粒度的空间局部性 + 时间局部性：顺序扫描时每 512 次（4 KB / 8 B）访存只需要一次新翻译。反之，“每页只碰一个元素”的访问模式（页步长、随机换页）会把翻译成本摊到每一次访存上——这是本讲最重要的一条性能直觉。

2.3 TLB 与页走：把翻译缓存起来

• 定义与目的：TLB（Translation Lookaside Buffer）是一个小型的、通常全相联或高度相联的硬件表，缓存最近的 VA→PA 翻译（项里含 VPN、PPN、权限位、ASID/PCID 等）。每次访存都从内存取翻译太贵（讲义 slide 17 原话 “Fetching each translation on a load would be expensive!”），TLB 让绝大多数访存在 1 个周期内拿到 PPN。TLB 缺失（TLB miss）时，硬件（x86/ARM 的硬件页走器）或软件（部分 MIPS/RISC-V 实现）去页表里取翻译，这一步叫 page walk（页走）：”Fetch entry from page table”（slide 19）。
• 直观解释（”它是什么？”）：TLB 像你手机里的常用联系人：绝大多数电话（访存）直接拨号（命中），偶尔要翻通讯录（页走）。也像前台桌边贴着的一张便签，只记下最近来访客人对应的真实房间号；便签写满了就得擦掉一行（替换），查不到的客人就得去翻档案柜（页表）。注意两个细节：便签是前台自己的（per-core 私有），档案柜是全楼共用的（页表在共享内存里，由 OS 维护）。
• “TLB 覆盖率”是判断性能的第一把尺子：TLB reach（覆盖范围） = 项数 × 页大小。讲义 slide 17–20 的算例：4 KB 的翻译”enough for 64 cache lines of 64 bytes”。同一个 TLB，页大小翻 512 倍，reach 就翻 512 倍——这就是大页的杠杆（2.6 节）。
• 架构图解 D3：TLB 命中 / TLB 缺失 + 页走（讲义 slide 17–20 的动画）

   Core                        ┌──────────────────── 私有 (per-core) ────────┐
   ┌──────┐   LD VA=1          │  ┌─────────── TLB ───────────┐               │
   │ Load │──────────────────► │  │ V D Tag(VPN) │ PPN         │               │
   │ Unit │                    │  │ 1 0   1      │ 4   ◄── 命中 │               │
   └──┬───┘                    │  │ 1 1   8      │ 1            │               │
      │ PA=4                   │  └───────────┬───────────────┘               │
      ▼                        └──────────────┼───────────────────────────────┘
   [L1]──miss──►[L2]──miss──►[L3]──miss──► DRAM      │ 缺失时:
                                              ┌──────▼────────────────────┐
   共享 (per-process):                        │ Page Walk: 逐级读页表项   │
   ┌────────────────────────────────────┐     │ PGD → PUD → PMD → PTE     │
   │ Page Tables (CR3 给出根节点 PA)     │◄────┤ 每一级都是一次"依赖访存"  │
   └────────────────────────────────────┘     └───────────────────────────┘
      页走结束后: 把新翻译填入 TLB (可能替换掉一个旧项), 再重发这次访存

• 性能特征：
  • TLB 命中：几乎不增加关键路径（在 VIPT L1 里可与 cache 索引并行，见 2.5），延迟≈1–2 周期。
  • TLB 缺失：多出一次页走。页走的串行性（每级地址依赖上一级结果）使它成为关键路径上的 4 次访存；但同时，多个访存各自的页走是彼此独立的，乱序执行可以把它们的延迟重叠起来（页走级并行，TLB-MLP），这正是实测中”单线程随机访问仍有 24 ns/hop、而不是 400 ns/hop”的原因（见第 3、4 节）。

2.4 x86-64 的四级基数页表：稀疏性与指针追逐

• 定义与目的：现代处理器用多级基数页表（multi-level radix page table）（讲义 slide 26–33）。x86-64 把 48 位虚拟地址切为 9 / 9 / 9 / 9 / 12：[47:39] → PGD、[38:30] → PUD、[29:21] → PMD、[20:12] → PTE、[11:0] → 页内偏移。每张页表恰好 4 KB，每个表项 8 字节 → 512 项 → 正好需要 9 位索引（slide 28 的推导）。CR3 寄存器保存 PGD 的物理基址（进程切换时换 CR3）。
• 为什么分级？ 讲义 slide 29 把它和覆盖范围列在一起：一级页表覆盖 512 GB / 1 GB / 2 MB / 4 KB。根因是稀疏性（sparsity）：VA 空间（48 位 = 256 TB）远大于物理内存，绝大多数 VA 区间根本没有映射；单级页表要为整个 VA 空间准备表项（48 位 VA、4 KB 页 → 2^36 项 × 8 B = 512 GB 页表，不可能），而多级树只要按需分配路径上的那几张表（缺的整棵子树用”present=0”表示）。
• 代价：页走变成了指针追逐（pointer chasing）——讲义 slide 30–33 用连续四张动画演示了这个过程：每读一个表项才知道下一个表在哪（它的 PPN 就在表项里），四级 = 四次串行访存。这是最坏情形；真实系统里绝大多数中间层被 PWC/数据 cache 兜住（见 2.6）。
• 大页如何嵌进这棵树（讲义 slide 39）：PMD 项可以直接指向一个 2 MB 页（跳过 PTE 级），PUD 项可以直接指向一个 1 GB 页（跳过 PMD、PTE 级）——注意 slide 39 把 4 KB / 2 MB / 1 GB / 512 GB 的覆盖范围标在树上，说明大页并没有改变树的结构，只是让更上层的项直接终结。
• 架构图解 D4：四级页走（最坏情况，4 次依赖访存）

   VA 47..39   38..30   29..21   20..12   11..0
   ┌────────┬────────┬────────┬────────┬────────┐
   │  9bit  │  9bit  │  9bit  │  9bit  │  12bit │   虚拟地址 A
   └───┬────┴───┬────┴───┬────┴───┬────┴────────┘
       │        │        │        │
  CR3  │        │        │        │
   │   │        │        │        │
   ▼   ▼        │        │        │         每个方块 = 4KB 页 = 512 项 × 8B
 ┌──────────┐   │        │        │
 │   PGD    │   │        │        │    ①读 PGD[47:39] ─► 得到 PUD 的物理基址
 └────┬─────┘   │        │        │
      └────────►▼        │        │    ②读 PUD[38:30] ─► 得到 PMD 的物理基址
             ┌────────┐  │        │
             │  PUD   │  │        │       (若此项标记为 1GB 页 → 页走到此结束)
             └───┬────┘  │        │
                 └──────►▼        │    ③读 PMD[29:21] ─► 得到 PTE 页的物理基址
                      ┌────────┐  │
                      │  PMD   │  │       (若此项标记为 2MB 页 → 页走到此结束)
                      └───┬────┘  │
                          └──────►▼    ④读 PTE[20:12] ─► 得到数据页的 PPN
                               ┌────────┐
                               │  PTE   │
                               └───┬────┘
                                   ▼
                 PA = PPN : PageOffset(11..0)   ──► 现在才真正去访问数据
   最终访存次数(最坏) = 4 (页走) + 1 (数据) = 5 ; 依赖链长度 = 4 次串行访存

• 性能特征：一次全冷页走 = 4 次 DRAM 访问 ≈ 4 × 80 ns ≈ 320 ns（假设 DRAM 延迟 80 ns），而且这 4 次是严格串行的（Span = 4 × 延迟，工作量为 4 次访存，并行度 ≈ 1）。若这 4 次正好都在 cache 里（PWC/数据 cache 命中），页走可以缩到十几纳秒甚至更少——这正是 2.6 节四种技术要争取的效果。

2.5 TLB 与 cache 的交互：PIPT / VIPT / VIVT

• 定义与目的：翻译出来的 PA 要拿去查 cache，那么 cache 用虚拟地址还是物理地址来索引/打标签？（讲义 slide 21–23）。这不是实现细节，而是延迟的关键：如果 cache 必须等翻译完成才能开始查，那么每次访存的 L1 延迟都会变成”TLB 延迟 + cache 延迟”。
• 三种方案（讲义 slide 23 的三行结论，本文补全其后果）：
  • PIPT（Physically Indexed, Physically Tagged）：索引和标签都用物理地址。语义最干净（没有别名/同义词问题），但必须等翻译完成才能访问 cache（slide 23 原话 “Cannot access cache before TLB!”）。
  • VIPT（Virtually Indexed, Physically Tagged）：索引只用页内偏移的位（因为偏移在翻译前后不变），标签用物理地址。于是 cache 索引可以和 TLB 查找并行进行（slide 23：”No need to wait for translation”），翻译结果只用于最后的标签比较。限制：可用的索引位数被页内偏移位数（4 KB 页 → 12 位）卡死 → cache 容量有上限（这也是为什么 L1 通常是 32–48 KB、8–12 路，见第 7 节思考题 1）。
  • VIVT（Virtually Indexed, Virtually Tagged）：完全不碰物理地址，但同义词（synonym/alias）问题：两个不同 VA 映射到同一个 PA 时，cache 里会有两份副本，一致性与刷新变得麻烦（slide 23：”Synonyms!”）；此外还有”同形异义（homonym）”——不同进程的相同 VA 指向不同 PA，必须在进程切换时刷新或用 ASID 区分。
• 架构图解 D5：VIPT 的关键路径（翻译与索引并行）

  虚拟地址 A:  [ 47 ................ 12 | 11 ......... 0 ]
                └──── VPN ─────────────┘└─ Page Offset ─┘
                          │                    │
              ┌───────────▼──────────┐         │  (偏移位在翻译前后不变!)
              │        TLB           │         │
              │ VPN A ──► PPN X      │         │
              └───────────┬──────────┘         │
                          │ PPN                │
                          ▼                    ▼
   ┌───────────────────────────────────────────────────────────┐
   │ L1 Cache (VIPT)                                           │
   │   Index  ← 来自 Page Offset (可立即开始, 不必等 TLB!)     │
   │   Tag    ← 来自 PPN (等 TLB 结果)   ──► 比较 ──► 命中/缺失 │
   └───────────────────────────────────────────────────────────┘
   时间轴:   |── TLB 查找 ──|── 标签比较 ──|          (两条路并行)
             |── cache 索引 ──|── 读数据 ──|
   对比 PIPT: |── TLB 查找 ──|── cache 索引 ──|── 标签比较 ──|   (串行, 更慢)
   对比 VIVT: |── cache 索引+虚拟标签比较 ──|  (最快, 但同义词/同形异义要额外处理)

• 性能特征（把三种方案放在一张表里）：

补充说明：VIPT 若索引位超出了页内偏移，就会退化成有同义词问题的方案——所以 VIPT 的”无别名”性质只在 index_bits + block_offset_bits ≤ page_offset_bits 时成立（4 KB 页时右边是 12）。第 7 节思考题 1 会用具体数字算这个上限。

2.6 把翻译延迟压回去：四种技术的共同逻辑

• 定义与目的：讲义 slide 25 / 34 两次列出同一份清单，因为在多级页表时代，页走本身可能就是”4 次串行内存访问”，必须用缓存 + 覆盖范围两把武器去压缩它：
  1. 多级 TLB（multi-level TLB）：L1 TLB 分 I/D（指令/数据各一个，条目少、延迟低），L2 TLB（STLB）混合 I+D、条目多、延迟高（讲义 slide 35 提到 “Intel i7 TLB structures”）。收益：利用翻译的局部性，让 L1 缺失时还有一层兜底；代价：额外硬件面积，及 L2 命中带来的额外几个周期。
  2. 页走缓存 PWC（Page Walk Cache，也叫 MMU cache）：缓存页表的中间层项（PGD/PUD/PMD 项）。讲义 slide 36 的关键观察是：上层项覆盖的地址范围巨大且局部性极好——一个 PGD 项覆盖 512 GB、一个 PUD 项覆盖 1 GB、一个 PMD 项覆盖 2 MB，所以进程哪怕用了几百 GB，上层可能只有几十个不同的项。收益：把 4 级页走缩短成 1 级；代价：额外硬件，且只在”上层复用率高”时有收益。
  3. 把翻译放进数据 cache（caching translations in data caches）：让页表项走正常的 cache 层次，而不是每次都去 DRAM。收益：页走中的某一级若在 L2/L3 命中，就省掉一次 DRAM 往返（讲义 slide 37：”Leverage cache locality for translations … avoids DRAM access”）；代价：与数据争抢 cache 容量（页表项会污染 cache）。
  4. 大页（huge pages / larger translations）：让一条 TLB 项覆盖更大的地址范围（4 KB → 2 MB → 1 GB）。收益：同样大小的 TLB，reach 提高 512× / 262144×，TLB 命中率大幅提升（讲义 slide 38：”Fewer TLB entries & higher hit rate … Same TLB space but larger coverage per entry”）。代价：见 2.6 末尾与第 6 节。
• 架构图解 D6：翻译的四层”缓存阶梯”

                    覆盖范围大  ◄─────────────────────────►  覆盖范围小
                    延迟高                                  延迟低
   ┌──────────────┐   ┌──────────────┐   ┌──────────────┐   ┌──────────────┐
   │  内存中的     │   │ L2 TLB (STLB)│   │   PWC / MMU   │   │  L1 I/D TLB  │
   │  页表 +       │   │ 上千项, I+D   │   │  cache: 缓存  │   │ 数十项, 分 I/D│
   │  数据 cache   │   │  混合         │   │  页表中间层项 │   │  1~2 周期     │
   └──────┬───────┘   └──────┬───────┘   └──────┬───────┘   └──────┬───────┘
          │                  │                  │                  │
          │  miss            │  miss            │  页走查下一级     │  hit
          ▼                  ▼                  ▼                  ▼
   ┌───────────────────────────────────────────────────────────────────────┐
   │  一次访存的翻译查找顺序: L1 TLB → L2 TLB → PWC(逐级) → 页表(逐级)     │
   │  命中位置越靠左, 关键路径上多出来的访存次数越少:                      │
   │      L1 命中 : +0        L2 命中 : +1 (较慢的 TLB 访问)               │
   │      PWC 命中: +1~2     全冷页走: +4 次串行 DRAM 访问 (最坏 ≈ 320 ns) │
   └───────────────────────────────────────────────────────────────────────┘
   注意: 这四级"阶梯"里, 只有 L1/L2 TLB 与 PWC 是**为翻译专设**的硬件;
        "页表项落在数据 cache 里" 是复用已有 cache 的顺带结果 (slide 37)。

• 四种技术的对比（收益 / 代价 / 何时有用）：

• 实测补充（本机，非讲义内容）：讲义 slide 3–4 用 Contiguitas（ISCA ‘23）的图说明”地址翻译墙”——随着数据中心负载的地址空间膨胀、物理内存连续性下降，页走与 TLB 缺失的成本在系统性上升。这类”物理内存碎片化”的问题在这台共享机器上就能观察到：我们请求 1 GiB 的透明大页（madvise(MADV_HUGEPAGE)）时，/proc/self/smaps 显示只有 72 MiB（7%） 真正落成了 2 MB 大页；把区域缩到 32 MiB 才拿到 32 MiB 全覆盖。这说明”用大页”不是一个可以假设的前提，而是一个需要用 smaps 验证的运行期事实（第 3 节示例 1、2 都打印了这个验证值）。

2.7 翻译一致性（translation coherence）与 TLB Shootdown

• 定义与目的：页表在共享内存里，任何核（严格说是 OS 在任何核上）都能改它；而 TLB 是每个核私有的。问题是：改了 PTE，怎么让别的核知道？（讲义 slide 40–42）
  • 硬件的职责（slide 41）：执行页走并找到翻译；出错时抛异常（例如 page fault）；填充 TLB 并在冲突时替换 TLB 项；但硬件不提供 TLB 与 cache（以及页表）之间的一致性（原话：”But no cache coherence between TLBs and Caches”）。讲义的追问非常锋利：“如果页的权限变了会怎样？”
  • OS 的职责（slide 42）：创建 PTE（把内存映射进地址空间）；更新 PTE（权限变化、页迁移、换页等）；以及维护跨 TLB 的翻译一致性——这一条硬件不管。
• 直观解释（”它是什么？”）：把 TLB 想成每个人手机里缓存的”联系人旧号码”；页表是公司通讯录。HR 在通讯录上把一个号码改成新号（改 PTE）之后，已经存了旧号的人不会自动更新——必须挨个打电话通知（IPI），并且等每个人都回复”已更新”（ack）才能认为通讯录生效。为什么非要等所有人？因为旧号码可能把信息送错人：这正是讲义 slide 43 的场景——“Change permissions to read-only”：如果某个核还在用”可写”的旧翻译，它就能绕过刚刚设置的只读保护（安全性问题），或者写进一个已经回收给别人（或已经换出到磁盘）的物理页（静默数据损坏）。
• 流程（讲义 slide 45 的六步，逐字对应）：
  1. 发起核上的 OS 锁定该页表项（lock PTE）；
  2. OS 生成可能正在使用该 PTE 的核列表；
  3. 发起核向其它核发送 IPI（Inter-Processor Interrupt），要求它们使对应的 TLB 项失效；
  4. 发起核先使本核的 TLB 项失效，然后等待 ack；
  5. 其它核收到中断 → 执行中断处理程序：使自己的 TLB 项失效，回送 ack；
  6. 发起核收齐所有 ack 后解锁 PTE。
• 表 2-4：硬件 vs OS 的职责划分（对照讲义 slide 41–42）

• 表 2-5：TLB shootdown 六步的角色分工

• 架构图解 D7：shootdown 的状态机（含失败/阻塞路径）

                        改权限/换页/取消映射的请求
                                 │
                                 ▼
                    ┌────────────────────────────┐
                    │ S0: 获得 PTE 锁 (lock PTE) │
                    └──────────────┬─────────────┘
                                   │
                                   ▼
                    ┌────────────────────────────┐
                    │ S1: 计算受害者核集合        │
                    │     (谁可能缓存了该翻译?)   │
                    └──────────────┬─────────────┘
                                   │
                    ┌──────────────▼─────────────┐
                    │ S2: 发送 IPI 给受害者核     │
                    └──────────────┬─────────────┘
                                   │
                    ┌──────────────▼─────────────┐        ┌──────────────────┐
                    │ S3: 本地 TLB 失效 + WAIT   │───────►│ 目标核:          │
                    │     (等待是所有核的交汇点) │        │ 收到 IPI         │
                    └──────────────┬─────────────┘        │  → 失效 TLB 项   │
                                   │                      │  → 回 ack        │
                                   │  ◄──── ack ──────────┤                  │
                                   │                      └──────────────────┘
                    ┌──────────────▼─────────────┐
                    │ S4: 全部 ack 到齐?          │
                    │   否 → 继续等 (可能被目标核 │
                    │        关中断/长临界区拖延)│
                    │   是 → 更新 PTE 并解锁      │
                    └──────────────┬─────────────┘
                                   ▼
                                完成 (映射变更对所有核生效)

• 架构图解 D8：shootdown 在今天的时间线（讲义 slide 52 的甘特图）

   时间 ──────────────────────────────────────────────────────────────────────►
   Core 0 (发起核, 属于进程 A):
     [Flush Pipeline][Save Context][Calc Victim Set][Send IPIs]──┐
                                                                │
                             TLB Invalidate (本地)              │
                                                                ▼
     [WAIT ... 等 ack]───────────────────────────────[Restore Context][Flush]
                                                                ▲
   Core 1 (进程 A 的线程 B):                                    │
     [Flush Pipeline][Save Context][TLB Invalidate][Restore Context][Flush]
                                     └──── ack ─────────────────┘
   Core 2 (进程 A 的线程 C):
     [Flush Pipeline][Save Context][TLB Invalidate][Restore Context][Flush]
                                     └──── ack ─────────────────┘
                                     ▲
                                     └─ 只是在做普通计算的 B/C, 被硬生生打断:
                                        流水线冲刷 + 上下文保存/恢复 = 纯开销
   ┌────────────────────────────────────────────────────────────────────────┐
   │ 结论(讲义 slide 52 原话): "Substantial performance impact on           │
   │ multithreaded applications" —— 并行度越高, 被牵连的核越多              │
   └────────────────────────────────────────────────────────────────────────┘

• 性能特征与实测（讲义 + 本机）：
  • 讲义 slide 53（引自 SOSP ‘09 的 Multikernel 论文）：TLB shootdown 是昂贵操作，8 个或更多核时超过 10,000 周期，而且核越多越贵。
  • 本机实测（非讲义内容）：用 mprotect 单页触发 shootdown，工作线程数 = 被牵连的核数（shootdown.cpp，见第 3 节示例 3）：0 个活跃核时 2.79 µs/次；8 核 15.53 µs（5.6×）；16 核 47.24 µs（16.9×）；32 核 159.99 µs（57.4×）。增长明显是超线性的（每多牵连一个核的边际成本从约 1.7 µs 涨到约 7 µs），与讲义的定性结论一致。这 160 µs ≈ 48 万周期（按 3 GHz 折算），比讲义引用的 10,000 周期还高一个数量级——原因是本实验里目标核正在紧密自旋（最坏的中断打断场景），且这是”一页 + 32 个目标核”的组合。
  • 与讲义 slide 59 呼应的一点（公开知识补充）：正因为 flush/shootdown 这么贵，现代 ISA 引入了 PCID/ASID（地址空间标识）与 INVPCID 之类的按地址空间/按项失效指令，避免进程切换或小改动导致”整表 flush”，虚拟化扩展也把”Avoid flushing TLB”列为目标（讲义 slide 59 明确列出）。

2.8 从虚拟内存到虚拟机：再来一层翻译

• 定义与目的：讲义最后把虚拟内存的思想又叠了一层（slide 55–59）。SVM（System Virtual Machine，系统虚拟机）让多个互不相关的用户共享硬件，并提供隔离与安全；它甚至允许把不同的 ISA 和 OS 呈现给用户程序；实现它的软件叫 VMM（Virtual Machine Monitor）/ hypervisor，运行其下的每个虚拟机叫 guest VM。讲义指出这条路能成立的一个现实前提是处理器足够快，使得额外开销可以接受。
• VMM 的要求（slide 56）：guest 软件应当表现得像跑在原生硬件上，且不能改变真实系统资源的分配；VMM 要能在 guest 之间做上下文切换；因此硬件必须提供系统态/用户态与一组特权指令用于分配系统资源。
• 虚拟内存受到的影响（slide 57–58）：
  • 每个 guest OS 维护自己的一套页表；
  • VMM 在”虚拟地址”与”物理地址”之间加了一层，叫 real memory；
  • 传统方案：VMM 维护 shadow page table（影子页表），把 guest 虚拟地址直接映射到真实物理地址，代价是 VMM 必须侦测 guest 对自己页表的每一次修改（讲义指出：如果”访问页表指针”本身是特权操作，这种侦测就自然发生——即 guest 写 CR3 会陷入 VMM）；
  • 现代方案：nested page tables（嵌套页表），即硬件两段翻译（Intel EPT / AMD NPT，根寄存器 EPTP），guest 页表负责 gVA → gPA，另一套由 VMM 维护的嵌套页表负责 gPA → sPA。
• 架构图解 D9：嵌套页表的页走爆炸（讲义 slide 58 的编号 1…24）

   guest 视角:  gVA ──(guest 页表, 4 级)──► gPA ──(VMM 嵌套页表, 4 级)──► sPA
                                          ▲                ▲
                                     guest 眼里的     真实硬件地址
                                     "物理地址"

   展开一次 gVA→sPA 的访问(讲义 slide 58 的 24 步编号):
   ┌──────────────────────────────────────────────────────────────────────────┐
   │ 读 guest L4 项:  需要在 gPA 上访存 → 该 gPA 又要 4 级嵌套翻译            │
   │   ①nL4 ②nL3 ③nL2 ④nL1 ⑤gL4                                              │
   │ 读 guest L3 项:  ⑥nL4 ⑦nL3 ⑧nL2 ⑨nL1 ⑩gL3                              │
   │ 读 guest L2 项:  ⑪nL4 ⑫nL3 ⑬nL2 ⑭nL1 ⑮gL2                              │
   │ 读 guest L1 项:  ⑯nL4 ⑰nL3 ⑱nL2 ⑲nL1 ⑳gL1                              │
   │ 最后取数据:      ㉑nL4 ㉒nL3 ㉓nL2 ㉔nL1 → 得到 sPA → 访问数据           │
   └──────────────────────────────────────────────────────────────────────────┘
   最坏 = 4 + 5×4 = 24 次访存 (原生只需 4 次页走 + 1 次数据)
   讲义在这一页标注了 "NTLB Caching" 与 "PWC Caching":
     → 嵌套翻译同样靠 TLB/PWC 缓存中间层结果, 否则虚拟化没法用

• 虚拟化扩展的目标（讲义 slide 59 逐条）：避免 flush TLB（用地址空间标识区分 guest，而不是切换时整表刷新）、用嵌套页表替代影子页表、允许设备用 DMA 搬数据、允许 guest OS 处理设备中断、以及安全方向的”允许程序管理加密的代码/数据区域”。
• 性能特征：原生最坏 5 次访存 → 嵌套最坏 24 次（4.8 倍）；即使只算”每次 guest 页走要额外做一次 4 级嵌套翻译”，也是 4 级 → 4+16 = 20 量级。这就是虚拟化环境对 TLB reach 极其敏感、并率先激进使用 2 MB/1 GB 大页的原因：大页不仅省 TLB 项，还能一次性砍掉嵌套树里的好几级。

2.9 软件执行模型：多线程程序里”谁拥有哪份翻译状态”

• 定义与目的：把上面所有结构放进一个并行程序的执行视图里，才能看清什么时候付出翻译代价。要点是所有权划分：
  • 页表：每个进程一份（进程内所有线程共享同一套页表、同一个 CR3）——所以线程之间不需要 shootdown，只有跨核/跨 CPU 的 TLB 副本需要；但同一进程的线程分布在多个核上，shootdown 就要打所有那些核。
  • TLB：每个核私有（更准确地说，每个硬件线程/核有自己的 L1 TLB，每核有自己的 L2 TLB 或共享给 SMT 兄弟）——一个线程预热过的 TLB，对另一个核上的线程毫无帮助。
  • Page fault 的处理是串行的、且可能持锁：多个线程同时首次触碰新页会争抢内核的 mm 锁（这是并行程序”启动开销”的主要来源之一）。
• 架构图解 D10：fork-join 程序中的翻译状态与代价点

                进程地址空间 (1 套页表, 共享)          每核私有 TLB
   ┌──────────────────────────────────────────────┐
   │  VA [0 .. 4GB)   已映射, 页表在内存(L2/L3 缓存)│
   └──────────────────────────────────────────────┘
        ▲                ▲                ▲
        │                │                │
  ┌─────┴─────┐    ┌─────┴─────┐    ┌─────┴─────┐
  │  Core 0   │    │  Core 1   │    │  Core 2   │   ... P 个核
  │ TLB0      │    │ TLB1      │    │ TLB2      │
  └─────┬─────┘    └─────┬─────┘    └─────┬─────┘
        │                │                │
   ┌────▼────────────────▼────────────────▼────┐
   │ 并行区 A: 各线程访问自己的那一块数据       │  ← 首次触碰 ⇒ minor page fault
   │  · 页表被并发"首次填充" ⇒ 内核 mm 锁争用   │     代价: 每页几微秒级
   │  · 每个核各自填充自己的 TLB (无共享, 无通信)│     TLB 命中率随局部性上升
   └────┬────────────────┬────────────────┬────┘
        │                │                │
   ┌────▼────────────────▼────────────────▼────┐
   │ ★ 全程序唯一的"翻译一致性事件"             │
   │   例如: mprotect / munmap / fork(COW) /    │
   │         mmap 新区域 / 用户态页表管理        │
   │   ⇒ 必须 shootdown: IPI 打到所有活跃核      │  ← 串行的 rendezvous,
   │      + 等 ack ⇒ 整个程序一起停一下          │     代价随核数超线性增长
   └───────────────────────────────────────────┘
   ┌───────────────────────────────────────────┐
   │ 并行区 B: 数据落到合法地址上, TLB 已稳定    │  ← 翻译几乎免费(命中)
   └───────────────────────────────────────────┘
   fork-join 视角: T_总 = T_串行(页故障 + shootdown) + T_并行/W
   ⇒ 并行度越高, "改映射"这类串行事件的占比越致命 (见第 4 节算例)

• 性能特征：在纯计算/纯访存的稳态阶段，翻译是”免费的”（TLB 命中）；代价集中在三类事件上：(1) 首次触碰（page fault，每页几微秒级）；(2) 改映射（shootdown，随核数超线性）；(3) 工作集超出 TLB reach 的访问模式（每次访存多一次页走）。第 3 节的三个代码示例分别把这三种代价单独放大出来测量。

3. 代码示例与性能分析

本节三个示例都给出了完整的编译命令与实测数据。实测数据不是讲义内容，是在本文档所用机器（2 × AMD EPYC 7V13，128 硬件线程，L3 512 MiB，共享节点）上跑出来的，仅用于说明数量级与相对趋势。三个示例共享同一条主线：把地址翻译的代价从其它效应里单独拉出来看。

3.1 示例 1：依赖指针追逐（pointer chasing）——把”翻译延迟”放到关键路径上

• 动机：普通循环里的多次访存是彼此独立的，乱序执行可以让多个 cache miss / 页走重叠，于是”页走很慢”这件事会被隐藏（这正是 3.2 节示例 2 里我们观察到的情况）。要单独测量翻译延迟，就得让每一次访存都依赖上一次的结果（依赖链上没有并行度，也没有 MLP 可用）。
• 设计（2 × 2 控制变量）：同一块 32 MiB 区域，同样的”随机跳转”序列，只改页大小：
  • same-page：512 个节点挤在 1 个 4 KB 页内（TLB 必命中、数据在 L1）→ 基线；
  • dense-32MiB：400 万个节点紧密排列（4 KB 布局下跨 8192 个页）；
  • spread-32MiB：8192 个节点、每个占一个 4 KB 页（4 KB 布局下每跳都换页）；
  • 每个布局都跑 THP off（4 KB 页） 与 THP on（2 MB 页） 两组，并用 /proc/self/smaps 验证大页是否真的生效。

// ============================================================================
// tlb_chase.cpp -- 依赖指针追逐 (pointer chasing): 隔离"地址翻译"在关键路径上的代价
//
//   三种布局 × 页大小(4KB / 2MB THP)，测每次跳转的延迟 (ns/hop)。
//   依赖链上每一跳都必须等上一跳回来, 所以内存延迟 + 页走延迟都暴露在关键路径上。
//
//   编译: g++ -O3 -march=native -o tlb_chase tlb_chase.cpp
//   运行: ./tlb_chase <thp:0|1> <每模式跳数(百万)>
//         例: ./tlb_chase 0 20    # 4KB 页, 每模式 2000 万跳
//
//   布局: same-page  : 512 个节点挤在 1 个 4KB 页内        (TLB 必命中, 数据在 L1)
//         dense-32M  : 400 万个节点紧密排列在 32 MiB 内     (4KB 布局下 8192 个页)
//         spread-32M : 8192 个节点每 4KB 放一个, 占 32 MiB  (4KB 布局下每跳换一页)
// ============================================================================
#include <cstdio>
#include <cstdlib>
#include <cstdint>
#include <cstring>
#include <vector>
#include <random>
#include <algorithm>
#include <chrono>
#include <sys/mman.h>

static double now_s() {
  using namespace std::chrono;
  return duration<double>(steady_clock::now().time_since_epoch()).count();
}

// 只统计"目标映射"里的大页, 避免把 malloc 的堆区算进来
static double anon_huge_mb_for(void* addr) {
  FILE* f = fopen("/proc/self/smaps", "r");
  if (!f) return -1.0;
  char line[512];
  bool inside = false; double kb = 0.0;
  while (fgets(line, sizeof(line), f)) {
    unsigned long lo, hi;
    if (sscanf(line, "%lx-%lx", &lo, &hi) == 2) {
      inside = ((unsigned long)addr >= lo && (unsigned long)addr < hi);
      continue;
    }
    if (inside && strncmp(line, "AnonHugePages:", 14) == 0) { kb += atof(line + 14); inside = false; }
  }
  fclose(f);
  return kb / 1024.0;
}

// 在 [0,n) 上建一个随机哈密顿环, 返回 next[]: next[perm[k]] = perm[k+1]
static void build_cycle(std::vector<uint32_t>& next, size_t n, unsigned seed) {
  std::vector<uint32_t> p(n);
  for (size_t i = 0; i < n; i++) p[i] = (uint32_t)i;
  std::mt19937 rng(seed);
  std::shuffle(p.begin(), p.end(), rng);
  next.assign(n, 0);
  for (size_t k = 0; k < n; k++) next[p[k]] = p[(k + 1) % n];
}

// 依赖追逐: 返回 ns/hop
static double chase(uint8_t* base, size_t stride, const std::vector<uint32_t>& next,
                    size_t hops) {
  uint64_t idx = 0;
  const size_t n = next.size();
  // 把 next[] 拷到各自的布局上
  for (size_t i = 0; i < n; i++)
    *reinterpret_cast<uint64_t*>(base + (size_t)i * stride) = next[i];
  __asm__ __volatile__("" ::: "memory");
  double t0 = now_s();
  // next[] 构成 [0,n) 上的单个环, 所以 idx 永远落在 [0,n) 内, 不需要取模
  for (size_t k = 0; k < hops; k++)
    idx = *reinterpret_cast<uint64_t*>(base + idx * stride);   // 依赖链, 不可乱序
  double dt = now_s() - t0;
  __asm__ __volatile__("" :: "r"(idx) : "memory");             // 防止被优化掉
  return dt * 1e9 / (double)hops;
}

int main(int argc, char** argv) {
  const int    use_thp = (argc > 1) ? atoi(argv[1]) : 0;
  const size_t mhops   = (argc > 2) ? strtoull(argv[2], nullptr, 10) : 20;

  const size_t SMALL_N  = 512;              // 4KB 页内能放 512 个 8B 节点
  const size_t DENSE_N  = (32u << 20) / 8;  // 32 MiB / 8B = 4M 节点
  const size_t SPREAD_N = (32u << 20) / 4096;// 32 MiB / 4KB = 8192 节点
  const size_t REGION   = 32u << 20;

  void* raw = mmap(nullptr, REGION, PROT_READ | PROT_WRITE,
                   MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
  if (raw == MAP_FAILED) { perror("mmap"); return 1; }
  if (madvise(raw, REGION, use_thp ? MADV_HUGEPAGE : MADV_NOHUGEPAGE) != 0) perror("madvise");
  uint8_t* base = static_cast<uint8_t*>(raw);

  printf("== THP=%s | 区域 32 MiB | AnonHugePages(初始)=%.0f MiB ==\n",
         use_thp ? "on" : "off", anon_huge_mb_for(raw));

  const char* name[3] = {"same-page  (512 节点/1 页, L1 命中)",
                         "dense-32MiB (4M 节点, 8 节点/line) ",
                         "spread-32MiB(8192 节点/8192 页)  "};
  const size_t ns[3]  = {SMALL_N, DENSE_N, SPREAD_N};
  const size_t st[3]  = {8, 8, 4096};

  for (int m = 0; m < 3; m++) {
    std::vector<uint32_t> next;
    build_cycle(next, ns[m], 2024 + m);
    double best = 1e30;
    for (int rep = 0; rep < 3; rep++) {
      double v = chase(base, st[m], next, mhops * 1000000ULL);
      if (v < best) best = v;
    }
    printf("  %s : %8.2f ns/hop  (页数 %zu, 该映射 AnonHugePages=%.0f MiB)\n",
           name[m], best, (ns[m] * st[m] + 4095) / 4096, anon_huge_mb_for(raw));
  }
  munmap(raw, REGION);
  return 0;
}

• 【代码做什么？】
  1. build_cycle() 在 [0, n) 上构造一个随机哈密顿环：把下标随机打乱成 p[0..n-1]，令 next[p[k]] = p[k+1]（末尾指回开头）。这样从任意节点出发，沿着 next 走恰好 n 步会遍历所有节点并回到起点——这个结构保证了 idx 永远落在 [0, n)，于是追逐循环里不需要取模（idx % n 是一次 20–40 周期的整数除法，会淹没我们要测的信号；这是写这类微基准时最常踩的坑）。
  2. 按 stride 把 next[] 铺到目标布局上：stride = 8 就是紧密排列（8 字节一个节点），stride = 4096 就是”每页一个节点”。
  3. chase() 里 idx = *(uint64_t*)(base + idx * stride) 是纯依赖链：下一次的地址来自这一次的数据，CPU 无法提前发射（不存在 MLP），也无法用预取器猜。整个循环的时间除以跳数就是 ns/hop。
  4. 用 __asm__ volatile 屏障阻止编译器把循环优化掉，并取 3 次测量中的最小值（最小值最接近”无干扰”的真实能力）。
  5. anon_huge_mb_for() 只统计目标映射里的大页（不统计 malloc 的堆），用来确认 madvise(MADV_HUGEPAGE) 是否成功。
• 【并行机制与性能解说】
  • 这段代码本身是单线程的，这正是它的目的：依赖链的 Span = 跳数 × 单跳延迟，Work = 跳数 × O(1)，因此并行度 = Work/Span ≈ 1。任何”加线程”的做法都不能降低单跳延迟，只能通过多条互相独立的追逐链（interleaved pointer chasing）把页走的重叠度提上来：P 条独立链给出 Work = P·H，Span = H·t_hop（不变！），并行度 = P，加速比上限 = P（受核数限制），单跳延迟不改善——这就是”依赖链只能靠 TLP（线程级并行），不能靠 ILP”的教科书式例子。
  • 页走在这条链上为什么完全无法隐藏：一次 load 需要 PA，PA 需要翻译，翻译需要页走，页走本身的每一级又要访存——这些全是串行依赖。所以 4 KB 页下的每条新翻译都在关键路径上加了”1 次（PWC 命中时）到 4 次（全冷时）”的访存。
  • 实测（本机，./tlb_chase 0 10 / ./tlb_chase 1 10，单位 ns/hop）：

• 读数：把 32 MiB 的足迹从 4 KB 页换成 2 MB 页（数据访问序列完全相同，只有页大小变化），随机追逐的每次跳转就少了 5.1–15.0 ns（按 3 GHz 折算约 15–45 周期）。这就是”纯翻译开销”的实测上界：8192 个页远超 L2 TLB 的覆盖范围（公开测量值：AMD Zen 3/4 约 3072 项、同期 Intel 约 1536 项，均为公开资料补充，非讲义数据），在 4 KB 页下几乎每一跳都要走一次页走；换成 2 MB 页后 32 MiB 只需 16 条 TLB 项，页走消失。
• 为什么 dense 的翻译税（15.0 ns）比 spread（5.1 ns）更大：两者页数与跳数相同，但 dense 的数据足迹是 32 MiB 的全部 cache line（每跳都是一次冷 line），页表中间层项更容易被数据流从 L2/L3 里挤出去，页走中更多的级落到更慢的层次；spread 只反复碰 8192 条 line（约 512 KB），页表项更容易常驻。这也说明”翻译税”不是一个常数，而是与数据流争夺缓存的结果。
• 瓶颈归类：延迟受限（latency-bound），且瓶颈在串行依赖链（按 Little 定律，吞吐 = 并行度/延迟，这里并行度 ≈ 1）。要提升这类代码，只有两条路：减少页走（大页） 或 增加并发的独立链（多线程/TLP）。

3.2 示例 2：页步长 / 随机换页的并行带宽测试——”翻译墙”的带宽视角

• 动机：示例 1 测的是延迟；但并行程序员更常看到的是带宽。这个示例在同一个数组上做三种访问模式，比较有用带宽（只算真正取到的 8 字节）随线程数的变化：
  • seq：顺序遍历全部元素（每 4 KB 页用满 512 个元素 → 翻译成本被摊薄 512 次）；
  • page-stride：每 4 KB 只碰 1 个元素（顺序换页）→ 每次访问都是新页；
  • random-page：乱序换页（访问顺序被随机打乱）→ 每次访问都是新页，而且硬件预取器也失效。

// ============================================================================
// tlb_pressure.cpp -- 地址翻译(TLB)压力测试
//
//   三种访问模式 × 两种页大小(4KB / 2MB THP)，测量 每次访问延迟 与 有用带宽。
//
//   编译: g++ -O3 -march=native -fopenmp tlb_pressure.cpp -o tlb_pressure
//   运行: ./tlb_pressure <数组MiB> <thp:0|1> <线程数>
//         例: ./tlb_pressure 1024 0 32      # 1 GiB, 4KB 页, 32 线程
//             ./tlb_pressure 1024 1 32      # 1 GiB, 2MB 大页, 32 线程
//
//   说明: thp=1 时用 madvise(MADV_HUGEPAGE) 请求透明大页，
//         thp=0 时用 madvise(MADV_NOHUGEPAGE) 强制 4KB 页。
//         注意 madvise 必须在"第一次触碰"之前调用。
// ============================================================================
#include <cstdio>
#include <cstdlib>
#include <cstdint>
#include <cstring>
#include <vector>
#include <random>
#include <algorithm>
#include <chrono>
#include <sys/mman.h>
#include <omp.h>

static double now_s() {
  using namespace std::chrono;
  return duration<double>(steady_clock::now().time_since_epoch()).count();
}

// 从 /proc/self/smaps_rollup 读 AnonHugePages，验证大页是否真的生效
static double anon_huge_mb() {
  FILE* f = fopen("/proc/self/smaps_rollup", "r");
  if (!f) return -1.0;
  char line[256];
  double kb = -1.0;
  while (fgets(line, sizeof(line), f)) {
    if (strncmp(line, "AnonHugePages:", 14) == 0) { kb = atof(line + 14); break; }
  }
  fclose(f);
  return kb / 1024.0;   // MiB
}

int main(int argc, char** argv) {
  const size_t mb       = (argc > 1) ? strtoull(argv[1], nullptr, 10) : 1024;
  const int    use_thp  = (argc > 2) ? atoi(argv[2]) : 0;
  const int    nthreads = (argc > 3) ? atoi(argv[3]) : 1;

  const size_t bytes  = mb << 20;
  const size_t nelem  = bytes / sizeof(uint64_t);      // 8B 元素
  const size_t epage  = 4096 / sizeof(uint64_t);       // 每 4KB 页 512 个元素
  const size_t npages = nelem / epage;                 // 4KB 页数

  void* raw = mmap(nullptr, bytes, PROT_READ | PROT_WRITE,
                   MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
  if (raw == MAP_FAILED) { perror("mmap"); return 1; }
  if (madvise(raw, bytes, use_thp ? MADV_HUGEPAGE : MADV_NOHUGEPAGE) != 0)
    perror("madvise");
  uint64_t* a = static_cast<uint64_t*>(raw);

  // 初始化: 并行顺序写, 触发物理页分配 (first touch) 与可能的 khugepaged 合并
  #pragma omp parallel for num_threads(nthreads) schedule(static)
  for (size_t i = 0; i < nelem; i++) a[i] = i;

  // 随机页序: 每次访问落在随机的一个 4KB 页上
  std::vector<uint32_t> perm(npages);
  for (size_t i = 0; i < npages; i++) perm[i] = (uint32_t)i;
  std::mt19937 rng(12345);
  std::shuffle(perm.begin(), perm.end(), rng);

  printf("== 数组 %zu MiB | %zu 个 4KB 页 | THP=%s | 线程=%d | AnonHugePages=%.0f MiB ==\n",
         mb, npages, use_thp ? "on" : "off", nthreads, anon_huge_mb());

  const int    REP    = 3;
  const int    PASSES = 16;   // seq 模式跑 1 遍, 另外两种模式跑 16 遍 (时间太短测不准)
  const char*  names[3] = {"seq         (步长 8B) ",
                           "page-stride (步长 4KB)",
                           "random-page (乱序换页)"};
  uint64_t     acc = 0;

  for (int mode = 0; mode < 3; mode++) {
    double best = 1e30;
    for (int rep = 0; rep < REP; rep++) {
      double t0 = now_s();
      uint64_t local = 0;
      if (mode == 0) {                       // 顺序遍历全部元素
        #pragma omp parallel for num_threads(nthreads) schedule(static) reduction(+:local)
        for (size_t i = 0; i < nelem; i++) local += a[i];
      } else if (mode == 1) {                // 每页只碰一个元素(顺序换页)
        for (int pass = 0; pass < PASSES; pass++) {
          #pragma omp parallel for num_threads(nthreads) schedule(static) reduction(+:local)
          for (size_t p = 0; p < npages; p++) local += a[p * epage];
        }
      } else {                               // 每页只碰一个元素(乱序换页)
        for (int pass = 0; pass < PASSES; pass++) {
          #pragma omp parallel for num_threads(nthreads) schedule(static) reduction(+:local)
          for (size_t i = 0; i < npages; i++) local += a[(size_t)perm[i] * epage];
        }
      }
      double dt = now_s() - t0;
      acc = local;
      if (dt < best) best = dt;
    }
    size_t nacc = (mode == 0) ? nelem : npages * (size_t)PASSES;
    double per_acc_ns = best * 1e9 / (double)nacc;
    double useful_GBs = (double)nacc * 8.0 / best / 1e9;   // 只算"有用"的 8B
    printf("  %s : %8.2f ms | %7.2f ns/访问 | 有用带宽 %7.3f GB/s (acc=%llu)\n",
           names[mode], best * 1e3, per_acc_ns, useful_GBs, (unsigned long long)acc);
  }
  munmap(raw, bytes);
  return 0;
}

• 【代码做什么？】
  1. mmap 一块匿名区域，用 madvise(MADV_HUGEPAGE/MADV_NOHUGEPAGE) 在同一份代码里切换 4 KB / 2 MB 页（注意：madvise 必须在第一次触碰之前调用，否则 THP 不会生效——这是最常见的”大页没生效”原因）。
  2. 用 OpenMP 并行初始化（a[i] = i），这一步同时完成物理页分配（Linux 的 first-touch 策略：谁先写，页就分配在谁的 NUMA 节点上），并可能触发 khugepaged 的合并。
  3. 构造随机页序 perm[]，保证 random-page 模式每次访问都落在不同的 4 KB 页上。
  4. 依次跑三种模式，每种取 3 次中的最好成绩，输出 ms、ns/访问、有用带宽 GB/s。短时间模式（page-stride / random-page）跑 16 遍（PASSES）以保证计时精度。
  5. 打印 AnonHugePages（来自 smaps_rollup）——让”大页到底有没有生效”变成可见的事实。
• 【并行机制与性能解说】
  • 并行机制：三种模式都是数据并行（data parallelism）的 for 循环，OpenMP parallel for ... schedule(static) 把索引区间均分给 P 个线程；每个线程只需要一个私有累加器，最后由 reduction(+:local) 汇总。没有锁、没有线程间通信、没有数据共享写（只读 a[] 与 perm[]）——除了归约那一下。
  • Work / Span / 并行度：
    • seq：Work = N（N = 数组元素数），Span = N/P + O(log P)（归约树或原子操作），并行度 = Work/Span ≈ P；
    • page-stride / random-page：Work = npages × PASSES，Span = Work/P + O(log P)，并行度 ≈ P。
    • 三者都是”完美并行”的循环，加速比上限 = 核数；但实测远达不到，因为瓶颈从”并行度不足”变成了内存系统（延迟 × 未完成请求数 × 带宽）。这就是 work-span 模型必须与内存模型一起用的原因：work-span 只告诉你”够不够并行”，不告诉你”内存喂不喂得饱”。
  • 实测（本机，1 GiB 数组，THP off，g++ 12.2.0）：

• 三条读数：
  1. 顺序访问对翻译几乎免疫：1 线程下 0.32 ns/访问就够了（一次翻译覆盖 512 次访问），8/32 线程时彻底变成带宽受限（8 线程 170 GB/s → 32 线程 196.6 GB/s，几乎不再增长）。这说明”地址翻译”不是所有负载的瓶颈，只对”每页利用率低”的访问模式是瓶颈。
  2. 每页只碰一个元素 = 灾难：1 线程 1 GiB 随机换页 15.07 ns/访问，是顺序访问（0.32 ns）的 47 倍；32 线程有用带宽只剩 23.4 GB/s，是流式带宽（196.6 GB/s）的 1/8。请注意：这里的 8 字节”有用数据”实际要拉一条 64 B 的 cache line（8× 放大），再加上页走的额外访存——带宽放大是”有用带宽崩塌”的直接原因。
  3. 线程数 8 → 32 只有 3.4×：这些访问每个线程已经是”一次独立的冷 line + 一次页走”，32 个核产生的访存并发（MSHR/页走器数量）逼近系统上限，于是子线性。
• 大页在这一组里为什么”没帮上忙”（诚实记录一个反例）：在 1 GiB 数组上请求 THP 时，smaps 只显示 72 MiB（7%） 真正落成大页（机器长期运行、物理内存碎片化），所以 page-stride/random-page 的耗时不降反微升；把数组缩到 32 MiB 才拿到 100% 覆盖。结论：MADV_HUGEPAGE 只是”请求”，必须验证；这同时印证了讲义第 3–4 页那张图所指向的问题——物理内存连续性（contiguity）正在成为翻译性能的实际瓶颈。

3.3 示例 3：TLB shootdown 随活跃核数的扩展性（翻译一致性的代价）

• 动机：讲义花了 8 页（slide 44–53）讲 shootdown，并给出”8 核以上超过 10,000 周期”的结论。这个示例用最朴素的系统调用把这条曲线在本机复现出来：对一个小页面反复改保护属性，同时让 T 个线程在 T 个不同的核上持续读这一页。

// ============================================================================
// shootdown.cpp -- 测量 TLB Shootdown 随"活跃核数"的增长
//
//   主线程反复对一个 4KB 页做 mprotect(只读) / mprotect(读写)，
//   每次调用内核都必须把该页的翻译从"其他正在跑本进程的核"的 TLB 里打掉
//   => 发送 IPI(处理器间中断) 并等待所有 ACK (讲义里的 6 步流程)。
//   T 个工作线程各自跑在一个不同的核上并持续读这一页, 因此 T 越大,
//   需要被中断、被打掉 TLB 项的核越多, 每次 mprotect 的延迟就越高。
//
//   编译: g++ -O3 -march=native -pthread shootdown.cpp -o shootdown
//   运行: taskset -c 0-63 ./shootdown          (建议先绑定到同一颗 socket)
// ============================================================================
#include <cstdio>
#include <cstdlib>
#include <cstdint>
#include <cstring>
#include <atomic>
#include <chrono>
#include <thread>
#include <vector>
#include <pthread.h>
#include <sched.h>
#include <sys/mman.h>
#include <unistd.h>

static double now_s() {
  using namespace std::chrono;
  return duration<double>(steady_clock::now().time_since_epoch()).count();
}

static volatile int g_stop = 0;
static volatile uint64_t g_sink = 0;
static volatile char* g_page = nullptr;   // 所有工作线程一起读这一页

static void pin_to(int cpu) {
  cpu_set_t set; CPU_ZERO(&set); CPU_SET(cpu, &set);
  pthread_setaffinity_np(pthread_self(), sizeof(set), &set);
}

static void* worker(void* arg) {
  pin_to((int)(intptr_t)arg);
  uint64_t s = 0;
  while (!g_stop) s += g_page[0] + g_page[2048];   // 持续读同一页 => 一直持有翻译
  g_sink += s;
  return nullptr;
}

int main() {
  // 1) 分配并触碰区域: 用 4KB 页(禁用 THP), 这样 PTE 数量最多
  const size_t region = 2u << 20;                       // 2 MiB
  char* p = static_cast<char*>(mmap(nullptr, region, PROT_READ | PROT_WRITE,
                                    MAP_PRIVATE | MAP_ANONYMOUS, -1, 0));
  if (p == MAP_FAILED) { perror("mmap"); return 1; }
  madvise(p, region, MADV_NOHUGEPAGE);
  for (size_t i = 0; i < region; i += 4096) p[i] = 1;   // 每个 4KB 页都真实分配
  g_page = p;

  const int MAXT = 32, K = 20000;
  printf("== mprotect(4KB 页) 触发的 TLB shootdown 延迟 vs 活跃核数 (每点 %d 次) ==\n", K);
  printf("   活跃线程数 |  每次 mprotect 延迟 |  相对 0 线程\n");
  printf("   ----------+---------------------+-------------\n");

  double base = 0;
  for (int T = 0; T <= MAXT; T = (T == 0) ? 1 : T * 2) {
    std::vector<std::thread> th;
    g_stop = 0;
    for (int i = 0; i < T; i++) th.emplace_back(worker, (void*)(intptr_t)(i + 1));
    std::this_thread::sleep_for(std::chrono::milliseconds(200));   // 等线程就位

    pin_to(0);
    // 预热
    for (int k = 0; k < 100; k++) {
      mprotect(p, 4096, PROT_READ);
      mprotect(p, 4096, PROT_READ | PROT_WRITE);
    }
    double best = 1e30;
    for (int rep = 0; rep < 3; rep++) {
      double t0 = now_s();
      for (int k = 0; k < K; k++) {
        mprotect(p, 4096, PROT_READ);                  // 触发 shootdown
        mprotect(p, 4096, PROT_READ | PROT_WRITE);     // 再触发一次
      }
      double dt = (now_s() - t0) / (2.0 * K);          // 每次 mprotect
      if (dt < best) best = dt;
    }
    g_stop = 1;
    for (auto& t : th) t.join();
    if (T == 0) base = best;
    printf("   %8d  |  %8.2f us/次  |  %6.2fx\n", T, best * 1e6, best / base);
  }
  munmap(p, region);
  printf("(sink=%llu)\n", (unsigned long long)g_sink);
  return 0;
}

• 【代码做什么？】
  1. mmap 一块 2 MiB 匿名区域，madvise(MADV_NOHUGEPAGE) 强制 4 KB 页并逐页写一个字节把它们真正分配出来（避免测到缺页，而只测 shootdown）。
  2. 启动 T 个 worker 线程，每个线程 pthread_setaffinity_np 绑定到 CPU i+1（主线程绑 CPU 0），然后死循环读同一页的两个字节——这样每个目标核都稳定持有一个该页的翻译。
  3. 主线程对该页反复执行 mprotect(PROT_READ) → mprotect(PROT_READ\|PROT_WRITE)：每次调用内核都要把这一页的翻译从其它核的 TLB 里打掉，也就是发 IPI + 等 ack（讲义 slide 45 的六步）。
  4. 对 T = 0, 1, 2, 4, 8, 16, 32 各测 3 轮取最优，输出每次 mprotect 的平均延迟与相对 T = 0 的倍数。
  5. 为什么只改读权限而不设 PROT_NONE：工作线程一直在读这一页，如果中间出现”不可读”的窗口就会段错误——微基准必须保证被测操作对并发的观察者是安全的。
• 【并行机制与性能解说】
  • 并行机制：这里的并行是被观察的对象而不是加速手段。T 个线程是”无辜的旁观者”：它们在读数据，不参与任何同步，却会被 IPI 硬生生打断（flush pipeline、保存/恢复上下文，讲义 slide 52 的甘特图）。这说明”页表变更”是一种全局的隐式同步原语——即使程序里一个锁都没用。
  • Work / Span / 并行度：每次 mprotect 的 Work = O(1)（更新 1 个 PTE）+ O(T)（发送 IPI、等待并汇总 T 个 ack）；Span 与 Work 同阶——因为发起核必须等所有 ack 才能返回，整个操作是串行 rendezvous，并行度 = 1。所以 shootdown 是”Amdahl 定律意义上的串行段“，而且这个串行段的长度 L(T) 本身随核数超线性增长。
  • 实测（本机，shootdown.cpp，每点 2 × 20000 次 mprotect）：

• 读数：T = 0 的 2.79 µs 是系统调用 + 页表更新 + 本地 TLB 刷新的底价；从 4 → 8 → 16 → 32 核，延迟翻了 2.6× → 3.0× → 3.4×，边际成本随核数上升（每多牵连一个核：8 核附近约 2.4 µs，32 核附近约 7.1 µs）。这与讲义 slide 53 的结论完全一致：“Gets more expensive with increasing number of cores.”
• 瓶颈归类：同步/串行 rendezvous 开销（不是带宽、不是负载不均）。实战含义：任何”每 N 次迭代就改一次映射”的并行代码（GC 写屏障、用户态页表、频繁 fork 的 COW、JIT 改代码页权限、mpi 的大页池重映射）都会随核数变差，而且这类代码在 1–4 核上测试时完全看不出问题。

4. 性能模型与复杂度分析

4.1 翻译的平均访问延迟模型（AMAT 形式）

把一次访存的延迟写成分层命中公式（AMAT = average memory access time）：

  t_eff  =  t_TLB_hit  +  P(miss | L1 TLB) · t_L2TLB
                        +  P(walk) · t_walk
                        +  t_data

  其中  t_walk = Σ_{i=1..L} t_level(i),   L = 页走级数（x86-64 基础页为 4）
        t_level(i) ∈ { L1 命中, L2 命中, L3 命中, DRAM }  取决于第 i 级页表项在哪
        P(walk) = (1 - p_L1) · (1 - p_L2 | L1 miss)

数值算例（与 3.1 节实测对照）：32 MiB 随机追逐，4 KB 页，8192 个页；取 L1 dTLB 64 项、L2 TLB（STLB）3072 项（AMD Zen 3/4 公开测量量级）：

同一模型给出两个极端，说明”翻译成本”取决于页表项在缓存层次里的位置：

结论：P(walk) 由 TLB reach 与工作集页数之比决定，t_walk 由页表项的缓存局部性决定。这两项正是 2.6 节四种技术分别攻击的目标（大页打 P(walk)，PWC / 翻译进 cache 打 t_walk）。

4.2 TLB reach（覆盖率）与工作集：第一个必须算的数字

TLB reach = 项数 × 页大小。它是判断”翻译会不会成为瓶颈”的第一把尺子：

• 命中率估算（均匀随机访问）：hit ≈ min(1, reach / 工作集大小)。
  • 工作集 1 GiB：4 KB 页 → 12 MiB / 1 GiB = 1.2%（几乎每次访存都要走页）；2 MB 页 → 512 个页，100% 命中。
  • 工作集 32 MiB（8192 页）：4 KB 页 → 3072/8192 = 37.5%（与 4.1 节模型一致）；2 MB 页 → 16 个页，100% 命中。
• 算一笔”每页只取 8 字节”的账（与 3.2 节实测对得上）：遍历 1 GiB 数组、每 4 KB 只取 1 个 8 字节元素 = 262144 次访问。
  • 单线程实测：13.35 ns/访问（page-stride）、15.07 ns/访问（random-page）→ 一遍耗时 3.5–3.95 ms（实测 63.19 ms / 16 遍 = 3.95 ms，吻合）；
  • 若只看”有用数据量”：262144 × 8 B = 2 MiB；同样 3.95 ms 里顺序流式（24.67 GB/s 单线程）能搬 97 MiB——同一个核，同一段时间，随机换页模式只产生了流式模式 2% 的有效数据。
  • 真实流量：262144 × 64 B（每访问一条 cache line）= 16.8 MB；若页走中的 PTE 级也落空，再加 262144 × 64 B = 16.8 MB → 放大 8×–16×。
• 讲义 slide 17–20 的算例（页粒度局部性的正面案例）：4 KB 的翻译 “enough for 64 cache lines of 64 bytes”——顺序访问时每 512 次 8 字节访问才需要一次新翻译，摊薄后翻译成本 < 0.1%。这正是实测里 seq 模式（0.32 ns/访问）与 32 线程下 196.6 GB/s 的原因。

4.3 页走的 Work / Span 与”每次翻译的流量”

• 单次页走：Work = L 次访存（L = 4），Span = 4 次串行访存（地址依赖），并行度 = Work/Span = 1。
• N 个相互独立的访存：Work = 4N，Span 仍是 4 次访存（每条链自己串行），并行度 = N —— 但这个并行度受硬件能同时容纳多少个未完成页走限制（页走器/MSHR 数量，通常每核十几到几十个）。设并发页走数为 M，页走延迟 t_walk，则：

   单核页走吞吐  =  M / t_walk            (walks/s)
   有用数据吞吐  =  (M / t_walk) × 8 B    (每页只取 8 字节时)

数值算例（解释实测的 0.6 GB/s）：若 t_walk ≈ 80 ns（PWC 命中上层，只有 PTE 级去 DRAM），要得到实测的 0.599 GB/s（1 线程 page-stride），需要：

   M = 0.599e9 B/s × 80e-9 s / 8 B = 5.99  ⇒  M ≈ 6 个并发的页走在飞

即：在这台机器上，单核大约能同时保持 6 个左右未完成的页走；若页走是全冷的 4 级（320 ns），同样的有用吞吐需要 M ≈ 24，而硬件给不了——这也是”PTE 被挤出缓存后性能断崖”的另一种说法。

• 带宽放大（bandwidth amplification）：每页只取 8 字节时，每次翻译平均要读 1 条 64 B 的页表项缓存行（PWC 未覆盖时甚至 4 条 = 256 B），而有用数据只有 8 B。定义”翻译流量放大比”：

   放大比 = (每访问的有用字节 + 页表流量) / 有用字节
          = (8 + 64) / 8 = 9×      (PWC 覆盖上层, 只有 PTE 级去内存)
          = (8 + 256) / 8 = 33×    (全冷页走, 4 级都去 DRAM)

4.4 Shootdown 的 Amdahl 分析：串行段长度本身随核数增长

模型：设每个 epoch（例如一次 GC 周期、一次 JIT 编译、一次 fork）有 W 的可并行工作量，并触发 1 次映射变更：

   T(P) = L(P) + W / P
        L(P) = 实测的每次 mprotect 延迟 (随被牵连核数 P 增长, 见 3.3 节表)
   加速比 S(P) = T(1) / T(P),  T(1) = L(1) + W

数值算例（用 3.3 节本机实测的 L(P)，取 W = 1 ms 的可并行工作）：

这张表是本节最重要的结论：把核数从 8 加到 32，程序反而慢了 36%（191 µs vs 141 µs），加速比从 7.14× 掉到 5.24×。原因不是负载不均、不是带宽，而是 Amdahl 定律里那个”串行段”的长度本身随 P 增长（L(P) 从 2.79 µs 涨到 160 µs）——经典 Amdahl 公式假设串行段是常数，而 shootdown 打破了这个假设：

   经典 Amdahl:  S(P) = 1 / (f + (1-f)/P)          f 为常数
   这里:         S(P) = T(1) / (L(P) + W/P)        L(P) 超线性增长
   ⇒ 存在最优核数 P*, 超过它之后"加核"是负收益:
        (本例中 P* 在 16 附近; W 越小, P* 越靠左)

工程含义：减少映射变更的”次数”比优化每次变更更有效（批量合并 flush 请求、在启动阶段一次性映射好大页、避免在计算热路径上 mprotect/munmap/fork）。这也是讲义 slide 59 把 “Avoid flushing TLB” 列为虚拟化扩展目标的原因。

4.5 Roofline / 算术强度视角：翻译到底改变了哪个上限

把”每访问有用字节”与”每访问真实流量”算成 算术强度（arithmetic intensity, 有用字节/字节传输），再对照实测的流式带宽上限（32 线程 196.6 GB/s）：

三条定量结论：

1. 顺序访问下翻译不是瓶颈：AI = 1.0，实测贴着带宽上限（196.6 GB/s ≈ 24.6 GB/s/线程 × 8 线程就饱和了）。
2. “每页少用字节”的模式下，瓶颈首先是 line 放大（8×），其次才是页表流量：32 线程实测 23.4 GB/s 与”只算 64 B line”的模型上限 24.6 GB/s 吻合到 5% 以内——说明在这个规模下，页走的额外流量主要被 PWC/L2 吸收了，真正的浪费是”拉了一条 64 B 的线只用了 8 B”。
3. 小线程数下是延迟受限，大线程数下是带宽受限：1 线程 0.6 GB/s（延迟/MLP 上限），8 线程 7.9 GB/s（4.5×，MLP 随核数增加），32 线程 26.5 GB/s（≈ 带宽上限）。这解释了为什么”翻译优化”（大页）在单线程/少核时收益巨大（延迟路径上的 5–15 ns/hop），而在多核带宽饱和后收益变小——因为此时真正的瓶颈已经转移。

5. 关键要点

1. 地址翻译本身就是一层访存层次，不是一个常数开销。 每次访存的翻译都要经过 “L1 TLB → L2 TLB → PWC/MMU cache → 页表（逐级）” 这条阶梯，命中位置决定关键路径上要多走几次访存：L1 命中 ≈ +0；STLB 命中 ≈ +1 次更慢的 TLB 访问；页走 = +1~4 次串行访存（全冷 4 级 ≈ 320 ns）。讲义 slide 25/34 列出的四种技术（多级 TLB、PWC、翻译进数据 cache、大页）恰好沿”提高覆盖范围（reach）”与”提高复用（把中间层留在 cache 里）”两条轴展开——理解这两条轴，就不会把四项技术当成互不相干的技巧。

2. 判断翻译会不会成为瓶颈，第一把尺子是 reach = 项数 × 页大小 与工作集页数之比。 4 KB 页时 STLB 的 reach 只有十几 MiB 量级（3072 × 4 KB = 12 MiB），所以任何超过十几 MiB 的随机访问工作集都几乎每次访存都要走页；而顺序访问时一次翻译覆盖 512 次 8 字节访问，翻译成本被摊薄到 0.1% 以下（实测：seq 0.32 ns/访问 vs random-page 15.07 ns/访问，相差 47 倍）。页粒度（4 KB）与 line 粒度（64 B）的错配，是”每页只取几个字节”的模式性能崩塌的根因。

3. TLB 是每核私有、且硬件不保证它与页表/cache 一致（讲义 slide 41）。因此“改映射”在并行程序里是一种全局的隐式同步：OS 必须 lock PTE → 计算受害者核 → 发 IPI → 等所有核 ack（讲义 slide 45 六步）。它不是常数开销：本机实测从 0 个活跃核的 2.79 µs 涨到 32 核的 159.99 µs（57×，超线性），导致”每毫秒触发一次映射变更”的程序在 32 核上比 8 核还慢 36%（4.4 节）。减少改映射的次数，比优化单次改映射更有效。

4. 大页是最大的杠杆，也是最大的风险。 一条 2 MB 页表项把 reach 提高 512 倍（4 KB → 2 MB），并且让页走在 PMD 级就终止（少一级页走；在虚拟化下省掉一整套嵌套翻译）。但它的代价是内部碎片、COW 放大、首次触碰更贵（要清零 2 MB）、分配需要连续物理内存；更关键的是它可能根本拿不到——本机实测请求 1 GiB 透明大页只成功 72 MiB（7%），32 MiB 区域才 100% 成功。结论：madvise(MADV_HUGEPAGE) 是请求而不是保证，必须用 /proc/self/smaps 验证。

5. 虚拟化把”一层翻译”变成”两层翻译”（gVA→gPA→sPA），最坏 4 次访存变 24 次（讲义 slide 58 的编号 1…24）。所以现代 ISA 的虚拟化扩展把”避免 flush TLB、用嵌套页表代替影子页表、支持设备 DMA 与 guest 处理中断”列为目标（slide 59），而嵌套页表能实用，靠的仍然是 TLB/PWC 缓存中间层结果 + 大页——本讲的每一件技术，在虚拟机里都要再用一遍。

6. 常见陷阱与注意事项

• 把 TLB 当成”会自动和页表保持一致的缓存”。 硬件只提供”页走 + 填充/替换 TLB”，没有任何机制在 PTE 被修改后自动失效别的核的 TLB 项（讲义 slide 41 明确写了 “no cache coherence between TLBs and Caches”）。任何”我改了页表，别的线程应该马上看到”的假设都是错的；同一进程内的其它核（不是线程）同样需要 shootdown。
• 把所有”随机访问慢”都归因于 cache miss 或伪共享。 诊断顺序应该是：先算 工作集页数 vs TLB reach（第 4.2 节），再看 cache 冲突。一个实用的判别实验：保持访问序列不变、只改变页大小或数据布局的”每页元素数”——如果时间显著变化，瓶颈里有翻译的份（3.1 节的两组数据差 5–15 ns/hop）。反之，如果只是把数组 padding 一下就好了，那才是 cache set 冲突。
• 以为”顺序访问就没有 TLB 问题”。 顺序访问只是把翻译摊薄（4 KB 页覆盖 64 条 line），并不是消除它；一旦访问模式变成”每页只碰一个元素”（页步长遍历、稀疏矩阵按列扫、图 BFS 的随机顶点、哈希表随机探测、跨页采样的 profiler），翻译立刻回到关键路径上。“每页利用率”是一个应该主动检查的性能指标。
• 假设大页一定生效、且只有好处。 三个具体错误：(1) 在第一次触碰之后才调用 madvise(MADV_HUGEPAGE)，于是 THP 根本没机会生效；(2) 不检查 /proc/self/smaps（本机实测 1 GiB 只拿到 7% 大页）；(3) 忽视代价——大页让写时复制（COW）放大 512 倍（改 1 个字节可能复制 2 MB）、首次触碰要清零 2 MB（按 20–50 GB/s 的清零带宽约 40–100 µs/页）、内存回收与统计粒度变粗、swap/超分行为变差。
• 在并行热路径上改地址映射。 mprotect / munmap / mmap / mremap / fork（COW）/ 用户态页表管理（如 DPDK、GC 写屏障做法、JIT 改代码页权限）都会触发 TLB shootdown，而它的代价随活跃核数超线性增长（实测 8 核 15.5 µs → 32 核 160 µs）。这类代码在 1–4 核上测试完全正常，一上大机器就崩——必须按核数做扩展性测试，并尽量把映射变更批量化、放在启动阶段。
• 微基准的方法学错误会让结论完全反过来。 常见的有：(a) 用独立访存的循环去测”翻译延迟”，结果测到的是带宽/MLP（3.2 节里 THP 开关在 1 GiB 数组上几乎看不出差异，正是因为瓶颈不在翻译）；(b) 指针追逐里插入 idx % n 取模（一次整数除法 20–40 周期，淹没有用信号）；(c) 不用 volatile/屏障保护结果，循环被编译器删掉；(d) 用依赖链测带宽（测到的是延迟）；(e) 忘记 NUMA first-touch —— 多线程初始化会让页按线程所在节点分布，跨节点访问带宽可能只有本地的一半，从而把翻译效应掩盖掉。

7. 思考题（带答案）

题 1：VIPT L1 的容量上限与真实 L1 尺寸

某处理器使用 4 KB 基础页、64 B cache line，L1 数据 cache 采用 VIPT（虚拟索引、物理标签）以保证”索引与 TLB 查找并行”。请推导：在不引入同义词（synonym）问题的前提下，L1 最大能做成多大（8 路相联）？为什么真实产品的 L1 是 32 KB 8 路 / 48 KB 12 路这样的尺寸？如果非要更大的 L1，有哪些办法？

【答案】 VIPT 无别名的充要条件是：cache 索引位必须全部落在页内偏移里（因为只有偏移位在翻译前后不变）。4 KB 页 → 页内偏移 12 位；64 B line → 块内偏移 6 位。因此索引位 ≤ 12 − 6 = 6 位，即 set 数 ≤ 64。

   容量上限(8 路) = sets × line × ways = 64 × 64 B × 8 = 32 KB
   超了会怎样: 索引位进入 VPN 部分 → 同一个物理页的两个不同 VA 可能映射到
              不同 set → 同一份数据在 cache 里出现两份 (同义词/别名)
              → 需要反别名或刷新, VIPT 的最大优点(索引不等翻译)就没了

• 为什么真实尺寸是这些值：32 KB/8 路 → 64 set（6 位索引，6+6 = 12 ✅）；48 KB/12 路 → 48K/(64×12) = 64 set（同样 6 位 ✅）；而 64 KB/8 路 → 128 set（需要 7 位索引，7+6 = 13 > 12 ❌，会出现别名）；若改成 64 KB/16 路 → 64 set（6 位 ✅，合法）。这就是为什么 Intel 长期用 32 KB 8 路、后来用 48 KB 12 路 L1，而不是直接堆到 64 KB 8 路——容量不是被面积卡住，而是被”4 KB 页的 12 位偏移”卡住（保持关联度、降低 set 数，就能在 12 位里塞下索引）。
• 要更大 L1 的办法：(1) 提高关联度（同容量下 set 数变少，索引位变少；但关联度本身有延迟/面积/功耗代价）；(2) 改用 PIPT（索引也要等翻译 → 每次访存都多一次 TLB 延迟，这也是为什么大容量 L2/L3 用 PIPT 而无所谓：它们的延迟本来就高，且不必与 TLB 并行）；(3) VIVT（索引标签都用虚拟地址，最快，但同义词 + 进程切换的”同形异义”必须靠 ASID 或整表刷新解决）；(4) 让硬件利用大页的更大偏移来扩展索引位——但实际硬件通常按最小页（4 KB）设计索引（因为访问时可能用 4 KB 页），所以不能依赖大页来放宽 L1 的 VIPT 约束；大页主要解决的是 TLB reach 问题。

题 2：为什么 TLB shootdown 必须”等所有 ack”？漏掉一个核会发生什么？

【答案】 因为翻译是缓存在每个核上的、硬件不保证一致的状态。页表更新（改权限、换页、取消映射）不会自动让其它核的 TLB 项失效（讲义 slide 41）。如果发起核在没等到某个核的 ack 之前就”认为变更已生效”，那个核会继续用一个陈旧的翻译去访问，具体后果分三类：

1. 权限绕过（安全漏洞）：典型场景是把页收紧为只读（例如 fork 之后父子共享的 COW 页、GC 的写屏障保护、W^X 的代码页、JIT 后加只读/可执行的代码段）。若某核仍持有”可写”的旧翻译，它就能写入本应只读的页，破坏只读不变量——这类漏洞历史上真实存在（例如”写时复制的页被越权写入”导致的隔离失效）。
2. 静默数据损坏（更常见、更难查）：页被换出（swap）或被 OS 回收后，同一个物理页框可能已经分配给别的进程。旧翻译会把这个核的写操作送到属于别人的物理页上：数据静默丢失 + 信息泄漏，而且往往只在负载高、内存紧张时偶发。
3. 语义错乱：munmap 之后的 use-after-unmap、mremap 之后越界访问到已经被用作其它对象的内存，表现为随机崩溃或”不可能复现”的 bug。

所以 shootdown 的 “等所有 ack”不是性能优化，而是正确性要求。它要维持的不变式可以写成：

   当 PTE 锁被释放(即变更宣告完成)时,
   系统中不存在任何一个核, 其 TLB 里持有与该 PTE 当前值不一致的翻译。
   ── 实现它需要: 在临界区内完成 (a) 页表更新, (b) 对所有可能缓存该翻译的核
      发送失效请求, (c) 收齐 ack 才能解锁。

补充两点：(1) ack 的语义是”该核的 TLB 项已失效”，而不是”该核永远不会再装填”——所以”失效”与”页表更新”的顺序和内存屏障必须保证不会有核在”失效之后、新值可见之前”重新装填旧翻译；(2) 代价上，这个 rendezvous 让所有被牵连的核一起停下来等，因此如果目标核长时间关中断或处于长临界区，发起核（乃至整个系统）会被拖住——这正是讲义 slide 52 甘特图与 slide 53（Multikernel 论文数据：8 核以上 >10,000 周期）要强调的扩展性问题。

题 3：大页的收益、代价，以及为什么”数据中心里越来越难拿到大页”

请从 TLB reach、页走级数、缺页次数、内存碎片、COW 语义五个角度分析大页（2 MB）相对 4 KB 页的收益与代价，并说明在长时间运行的共享机器上”请求大页却拿不到”会发生什么。

【答案】 收益（四项，都可定量）：

1. TLB reach ×512：4 KB 页下 3072 项 STLB 只覆盖 12 MiB；2 MB 页下覆盖 6 GiB，1 GB 页下覆盖 3 TiB。对 1 GiB 随机访问负载，STLB 命中率从 ≈1% 变成 ≈100%。
2. 页走级数减少：PMD 项直接指向 2 MB 页 → 页走少一级（少一次依赖访存）；在虚拟化下，guest 每少一级页走就少一整套 4 级嵌套翻译（讲义 slide 58），收益被放大数倍。
3. 缺页/页表开销降低：1 GiB 区域从 262144 个 PTE 变成 512 个 PMD 项，页表内存从 2 MB 级别降到几十 KB 级别，缺页处理次数也随之下降（在首次触碰阶段尤其明显）。
4. 翻译税消失的实测证据：3.1 节里同一访问序列、只把页大小从 4 KB 换成 2 MB，随机指针追逐从 24.24 ns/hop 降到 19.16 ns/hop（32 MiB 足迹，8192 个 4 KB 页 → 16 个 2 MB 页）。

代价（五项）：

1. 内部碎片：分配粒度 2 MB，需要 8 KB 却拿到 2 MB → 内存利用率下降；多进程/多容器场景下更容易触发 OOM。
2. COW / 写时复制放大：fork 后只改 1 个字节，内核可能要复制整个 2 MB（而不是 4 KB），fork 密集型服务（如 Redis、prefork 模型）性能显著变差。
3. 首次触碰更贵：新大页必须清零（安全要求）——2 MB 按 20–50 GB/s 的清零带宽约 40–100 µs，比 4 KB 页高出两个数量级；这也让”按需增长”的负载出现延迟尖刺。
4. 回收/换页/超分粒度变粗：内核回收整页，2 MB 的粒度让内存压力下的行为更粗暴，且难以做精细的 swap/压缩；内存统计（RSS、cgroup）也失真。
5. 分配需要连续物理内存：必须有 2 MB 物理连续块，需要内存压缩（compaction）配合，可能失败且延迟不可控。

“拿不到大页”会发生什么（本机实测）：在这台长期运行（已连续运行 118 天）、内存已被大量占用的共享机器上，对 1 GiB 匿名区域调用 madvise(MADV_HUGEPAGE) 后，/proc/self/smaps 只报告 72 MiB 的 AnonHugePages（7%）；把区域缩小到 32 MiB 时才拿到 100%。后果是：“优化”静默失效——代码里写了 MADV_HUGEPAGE，但翻译税照付；更糟的是”部分生效”会让性能在不同运行之间抖动（大页落在哪里取决于当时的物理内存状态）。这正是讲义第 3–4 页那张 Contiguitas（ISCA ‘23）配图指向的问题：数据中心里物理内存连续性在下降，翻译成本在系统性上升。工程做法：(1) 用 smaps 的 AnonHugePages 或 perf stat -e dTLB-load-misses 之类的 PMU 事件验证而不是假设；(2) 对延迟敏感的服务用显式 hugetlbfs 预留（启动时保留，保证可用，代价是不能弹性扩展）；(3) 用页迁移/compaction在低负载时整理内存；(4) 至少保证”要么全用大页、要么全不用”，避免混合状态造成的性能抖动。

Lecture 20: Guest Lecture

日期：Oct 19　|　材料状态：未公开 官方日程表该行仅写作 “Guest Lecture”，未提供 slides 或录像链接；Fall 2026 的 guest lecture 讲者与题目在抓取时（2026-09）尚未公布。

概述

本讲由工业界或学术界客座讲者主讲，主题每年不同，通常与当年热点（AI 基础设施、新型加速器、大规模分布式训练、编译器/运行时工程等）相关。由于课程未公开其材料，本笔记无法提供基于官方讲义的逐页笔记。

可从课程其他讲次获得的对应背景

课程日程中保留的归档客座讲座行提供了往届类似主题，可作为知识补充：

考试相关

官方明确说明：Exam 2 覆盖 Lecture 14–24，但排除 guest lecture，因此本讲不进入考核范围。

学习建议

1. 若你是选课学生，务必现场听讲并自行记录（客座讲座的内容通常不会出现在任何公开讲义里）。
2. 若你是在自学，可用以下三条线索自行补足”工业界视角”：
   • 专用加速器：见 Lecture 18（硬件专用化的能效谱系）。
   • 大规模训练系统：见 Lecture 22–23（数据并行、张量并行、流水线并行的通信记账）。
   • 性能工程实践：见 Lecture 14（测量方法论与高水位实验）。