附录 A · CSAPP 核心概念与命令速查表

目录 · ← l25

附录 A · CSAPP 核心概念与命令速查表

本附录是全书 24 讲的压缩索引：按主题列成表格，供随时查阅。 表中每条都可以在正文对应章节找到展开讲解。

A.1 数据表示速查

A.1.1 C 类型 → 字节数 → 汇编后缀（x86-64）

记忆钩子：b=1、w=2、l=4、q=8；浮点后缀 ss/sd = scalar single / scalar double。 AT&T 语法下 8 位寄存器称 %al 一类（b 后缀），16 位为 %ax（w），32 位为 %eax（l），64 位为 %rax（q）。

A.1.2 取值范围表（补码与无符号）

常用速记：INT_MAX = 0x7FFFFFFF，INT_MIN = 0x80000000，UINT_MAX = 0xFFFFFFFF， LONG_MAX = 0x7FFFFFFFFFFFFFFF，ULONG_MAX = 0xFFFFFFFFFFFFFFFF。 在 C 里更稳妥的写法是 #include <limits.h> 后用 INT_MAX / INT_MIN / UINT_MAX，或用 stdint.h 的 INT32_MAX、INT64_MIN、UINT64_MAX。

A.1.3 补码 ↔ 无符号：四个转换函数

• 核心恒等式：$T2U_w(x) = x + 2^w$（当 $x<0$）；$U2T_w(u) = u - 2^w$（当 $u \ge 2^{w-1}$）。二者都只改解释、不改位。
• 溢出环：$T2U$ 把 $TMin \to 2^{w-1}$、$-1 \to UMax$；$U2T$ 把 $UMax \to -1$、$2^{w-1} \to TMin$。
• C 语言中的触发点：显式强制转换 (unsigned)ty、赋值 ux = tx、以及函数调用传参（原型为 unsigned 而实参为 int）都会做 $T2U$。
• 排序反转：$x<0 \Rightarrow T2U(x) > TMax$，所以 -1 > 0U 为真。混合有/无符号比较时，有符号操作数被隐式转成无符号。

A.1.4 溢出检测规则

• 正溢出（positive overflow）：$x>0, y>0, s<0$，真值 $= x+y-2^w$（结果为 $TMin$ 附近）。
• 负溢出（negative overflow）：$x<0, y<0, s \ge 0$，真值 $= x+y+2^w$（结果为 $TMax$ 附近）。
• 补码构成阿贝尔群：加法满足交换律、结合律，0 是单位元，每个数有加法逆元（$TMin$ 的逆元是它自己）；由此推出”平凡”恒等式 -x == ~x + 1、x - y == x + (-y) 恒成立。
• 乘法：$w$ 位乘积只保留低 $w$ 位，$x \cdot y$ 的无符号值与补码值位模式相同（乘法的低 $w$ 位不区分有/无符号）。溢出判定用 imulq 的 OF（判断 128 位乘积是否等于符号扩展后的低 64 位）。
• 取反：-x 即 ~x + 1；对 $TMin$ 取反得 $TMin$（溢出）。
• C 语言注意：有符号溢出是未定义行为（UB），编译器可据此优化；无符号溢出是有定义的模运算。检测有符号溢出的可移植写法是先转成无符号算，再检查。

A.1.5 移位规则

• 负数右移在 C 中是实现定义行为（implementation-defined）：标准未规定补 0 还是补符号位。x86-64 的 sar 族补符号位，GCC/Clang 一贯如此，但不可移植。
• 移位量非法：C 标准规定 $k < 0$ 或 $k \ge w$ 是 UB（x86 硬件实际只取 $k \bmod w$，例如 1 << 32 在硬件上等价于 1 << 0）。
• 右移 ≠ 除法：负数算术右移向 $-\infty$ 取整，/ 向 0 取整。例：-7 >> 1 == -4，-7 / 2 == -3。 向 0 取整的补偿写法：(x < 0 ? x + (1<<k) - 1 : x) >> k。
• >> vs >>>：C 语言只有 >>，没有 >>>；要逻辑右移就先转 unsigned（(unsigned)x >> k）。>>> 是 Java 的逻辑右移运算符（Java 的 >> 恒为算术右移），>>> 也存在于 JavaScript。阅读语言特性时勿混淆。
• 指令对应：shl/sal 等价（左移）、shr 逻辑右移、sar 算术右移；移位量放在 %cl 或立即数（salq $2, %rax）。

A.1.6 IEEE 754 位域与数值分类

double —— 64 位                               float —— 32 位
 63  62        52 51                    0      31  30     23 22           0
+---+-----------+-----------------------+     +---+-------+--------------+
| s |    exp    |         frac          |     | s |  exp  |     frac     |
| 1 |    11     |          52           |     | 1 |   8   |      23      |
+---+-----------+-----------------------+     +---+-------+--------------+

• 规格化数隐含前导 1（$M = 1.\texttt{frac}$）：这一位不存储，白赚一个有效位，代价是 0 无法表示——于是 exp=0 专用于非规格化数。
• 非规格化数：$M = 0.\texttt{frac}$，阶码固定为 $1-\text{bias}$（不是 $0-\text{bias}$），使 $0$ 与最小规格化数之间的间距均匀，称为渐进下溢（gradual underflow）。
• 最大规格化数：float 约 $3.4\times10^{38}$（exp=0xFE，frac 全 1）；最小正规格化数：$2^{-126}\approx1.18\times10^{-38}$。
• 舍入：默认向偶数舍入（round-to-nearest-even）；另可设向零、向下、向上。
• 浮点特殊事实：
  • float 有 24 位有效位（隐含 1 + 23），$\log_{10}2^{24}\approx 7.22$，故约 7 位十进制有效数字；double 有 53 位，$\log_{10}2^{53}\approx 15.95$，故约 15–16 位。
  • 0.1 + 0.2 != 0.3：0.1、0.2、0.3 都不能被二进制有限表示，相加后的舍入结果与 0.3 的最近可表示数不同（0.1+0.2 打印约 0.30000000000000004441）。浮点比较必须用容差：fabs(a-b) < 1e-9 * fmax(1.0, fmax(fabs(a), fabs(b)))。
  • 浮点不满足结合律：(x+y)+z != x+(y+z)（大数吞小数）；只有 -ffast-math 才允许编译器重排。
  • float → int → float 不是恒等（(int)3.14f == 3，精度与截断都丢）。
  • int → float 对 $>2^{24}$ 的整数会丢低位；int → double 对所有 32 位整数精确。

A.2 x86-64 寄存器与调用约定速查

A.2.1 16 个通用寄存器：64/32/16/8 位名称对照

• %r8–%r15 的 8 位形式是 %r8b–%r15b（不是 %r8l），且需要 REX 前缀编码。
• %sil、%dil、%bpl、%spl 也是 REX 时代新增的低字节名（历史上 %esi/%edi/%ebp/%esp 的低字节不可寻址）。
• 写 32 位寄存器会清零高 32 位：movl $1, %eax 之后 %rax == 1；而 movw/movb 只改写低 16/8 位，高位保留。这是 x86-64 特有的优化点（movl 省一条 movz）。
• %rip 不是通用寄存器：程序计数器（instruction pointer），只能用于 RIP 相对寻址（如 0x2fda(%rip)）和 leaq，不能作为算术目标。

A.2.2 参数传递与返回值

• 整型与浮点参数混排时各自计数：void f(int a, double b, int c, double d) → a→%rdi，b→%xmm0，c→%rsi，d→%xmm1。
• 调用者不需要为栈传参预留”影子空间”——这与 Windows x64 的 32 字节 shadow space 不同。

A.2.3 caller-saved vs callee-saved

• 规律：所有参数寄存器 + 返回值寄存器 + %r10/%r11 都是 caller-saved；%rbx/%rbp/%r12–%r15 是 callee-saved。
• 被调用者保存 callee-saved 寄存器的两种典型做法：pushq %rbx … popq %rbx，或先 subq $N, %rsp 再 movq %rbx, k(%rsp)。
• 递归能正常工作，正是因为”只在 callee-saved 寄存器与自己的栈帧里保存值”这条纪律。

A.2.4 栈帧布局与 16 字节对齐

        高地址
        +---------------------------+
        |   调用者的栈帧 (caller)     |
        +---------------------------+
        |  第 7+ 个参数 (argument build) |
        +---------------------------+
        |   返回地址 (return address)  |  <-- call 压入；%rsp 在 callee 入口指向它
        +---------------------------+
 %rbp ->|   保存的 %rbp (old %rbp)    |  <-- 可选：被调用者压入
        +---------------------------+
        |   被保存的 callee-saved 寄存器 |
        +---------------------------+
        |   局部变量 / 数组 / 临时量     |
        +---------------------------+  <-- %rsp（函数体内随 push/sub 移动）
        低地址（栈向低地址增长）

A.2.5 浮点/向量寄存器 %xmm0–%xmm15

• 每个 %xmm 是 128 位；标量 float 用低 32 位，double 用低 64 位，写入时高位置零。
• %xmm 寄存器没有 callee-saved 的：调用者若在 %xmm 里存了跨调用要用的值，必须自己溢出到栈上。
• %ymm0–%ymm15（AVX，256 位）与 %zmm0–%zmm31（AVX-512，512 位）复用同一编号的寄存器组，低 128 位即 %xmm。

A.3 x86-64 指令速查（AT&T 语法）

AT&T 语法三条铁律：① 操作数顺序是 源, 目的（movq src, dst）；② 寄存器加 %（%rax）；③ 立即数加 $（$15213）。 内存寻址写作 D(Rb, Ri, S) $= \text{Mem}[R_b + R_i \cdot S + D]$，$S \in \{1,2,4,8\}$，Ri 不能是 %rsp。

A.3.1 数据传送

• movl 的清零副作用：movl $0, %eax 使整个 %rax 为 0；而 movw/movb 保留高位。
• leaq 的经典用法：leaq (%rdi,%rdi,2), %rax 得 $3x$；leaq 4(%rdi,%rdx), %rcx 得 $x + y + 4$；配合 salq 实现任意常数乘法（如 x*12 = leaq (%rdi,%rdi,2),%rax + salq $2,%rax）。
• 传送指令只有 movabsq 例外：movq $0x123456789, %rax 汇编器会报错或截断，必须 movabsq。

A.3.2 算术与逻辑

• 移位量：k 为立即数，或放在 %cl 中（salq %cl, %rax）。
• 乘法常被编译器强度削减为 leaq + sal（如 x*48 → leaq (%rsi,%rsi,2),%rdx + salq $4,%rdx）——看汇编时不要以为一定有 imul。

A.3.3 比较与测试

A.3.4 条件码表

• leaq 不设置任何条件码——这是它在编译器中被当作”纯算术”使用的关键原因。
• 四种组合判定有符号比较：cmp 后看 SF 与 OF 是否相等（SF == OF 表示”确实不小于”）。

A.3.5 set 指令：按条件写单字节

• set 类指令的目的操作数必须是单字节位置（%al、%r10b 等，或内存），写成 setg %rax 会报错。
• 常与 movzbl 配合得到 32 位 0/1 结果：cmpq %rsi,%rdi; setg %al; movzbl %al,%eax。

A.3.6 j 指令：按条件跳转

• 选择口诀：g/l（greater/less）用于有符号；a/b（above/below）用于无符号。写错类别是汇编题最常见错误——int 用 jg，unsigned 用 ja。
• C 的 <、> 编译成 cmp + jl/jg；unsigned 的比较编译成 cmp + jb/ja。

A.3.7 cmov 指令：条件传送（无分支）

• 源操作数不能是立即数：必须先 movq $c, %reg 再 cmovXX %reg, %dst。
• 内存源无论如何都会被读取：即使条件不成立，CPU 也会发起该访存（可能触发缺页/段错误）。因此编译器只在”两个分支都安全可算”时才用 cmov——这也是 CS:APP 讲的”分支不可预测时 cmov 更快，但语义不等价”的原因。
• 浮点比较用 ucomisd/comisd，它设置的是 ZF/PF/CF（不设 SF/OF），也无序（NaN）时置 ZF=PF=CF=1；因此浮点的条件传送/跳转要用 无符号 形式（cmova/cmovae/cmovb/cmovbe），不能用 cmovg/cmovl。

A.3.8 过程调用

A.3.9 浮点/SSE 指令

• 浮点参数 %xmm0–%xmm7，返回值 %xmm0；%xmm 全为 caller-saved。
• %xmm 与 %rdi 等整型寄存器的计数互相独立（见 A.2.2）。

A.3.10 易混淆指令对照表

A.4 GDB 速查

启动前用 gcc -g -O0 -Wall 编译，调试信息才完整。-Og 兼顾优化与可调试性。

A.4.1 启动

A.4.2 断点

A.4.3 执行

• 卡在 input 里怎么办：finish 可能因程序等待输入而挂住；先 kill 再重启。
• Bomb Lab 惯用组合：b explode_bomb → run → bt 找到调用点 → frame N → info locals。

A.4.4 查看数据

A.4.5 x/nfu addr 格式详解

语法 x/[n][f][u] addr：n 重复次数（十进制，默认 1）、f 显示格式、u 单元大小。

• 省略 f/u 时沿用上一次的设置（所以 x/8xb 之后再 x/4 仍是字节）；默认单元是 w、默认格式是 x。
• 常用组合速记：nfu = “多少 / 怎么显示 / 多大一块”。

A.4.6 栈与帧

• 读栈帧的经典套路：bt 找到帧号 → f N → info frame 看到 saved rip 的位置 → x/8gx $rbp 核对局部变量与返回地址。
• 编译加 -fno-omit-frame-pointer（或 -O0）时 %rbp 链才完整，bt 才可靠。

A.4.7 反汇编与源码

A.4.8 TUI 与布局

• Bomb Lab 推荐姿势：gdb -tui ./bomb → layout regs → b explode_bomb / 单步 si，一边看 %rax、%rdi 一边看反汇编。
• TUI 花屏或按键失灵时退出重进通常最快；Ctrl-x a 可临时回到普通模式。

A.4.9 信号与线程

• 多线程下断点会在所有线程命中；配合 scheduler-locking 可让调试结果可复现。
• 死锁排查顺序：thread apply all bt → 找到卡在 pthread_mutex_lock/sem_wait/read 的线程 → thread N + bt full 看谁持锁。

A.5 二进制工具速查

A.5.1 gcc 常用开关

• 典型组合：调试 gcc -g -O0 -Wall -Wextra -std=c11 prog.c -o prog；优化对比 gcc -O0/-O1/-O2/-O3 -S。
• -O2 及以上会让 %rbp 消失、变量被提升进寄存器、循环被重排——看汇编时先确认编译级别。

A.5.2 objdump：反汇编目标文件

• -d 反汇编 .text 中所有函数，但依赖节头里的符号信息；被剥离符号的二进制要靠地址区间或 nm。
• -M intel 输出的地址格式与 GDB set disassembly-flavor intel 一致，两者可交叉核对。
• 链接前的 .o 里，未解析引用的目标字段是 0，必须看 -r 的重定位条目才能知道它要填什么。

A.5.3 readelf：ELF 结构

• 记忆钩子：小写 -h/-S/-l/-s/-r/-d 分别对应 header / Sections / segments(program headers) / symbols / relocations / dynamic。
• 对比：readelf 面向 ELF 结构，objdump 面向机器码与反汇编；两者都要会。

A.5.4 其它二进制工具

A.5.5 链接关键机制（一句话版）

A.6 调试与动态分析工具速查

A.6.1 valgrind 工具族

memcheck 关键选项

memcheck 报告分类速查

• Valgrind 不是万能的：它跟踪的是真实执行的路径；-O3 下越界可能被优化掉从而”查不出错”——务必用 -O0 -g 编译后再跑 valgrind。
• Valgrind 通过动态二进制插桩运行，程序会慢 10–50 倍，不适合作性能测量（用 perf）。

A.6.2 Sanitizer 编译开关

A.6.3 strace 与 ltrace

• 典型用法：Shell Lab 调试 fork/execve/waitpid 用 strace -f -e trace=process ./tsh；Proxy Lab 看 socket 用 strace -e trace=network；”文件打不开”用 strace -e trace=file -y。

A.6.4 perf：硬件性能计数器

• perf 需要内核权限：sudo perf ... 或把 perf_event_paranoid 调低。
• 性能优化流程：perf stat 定位瓶颈类别（IPC 低？缓存未命中高？）→ perf record -g 找热点函数 → perf annotate 找热点指令。

A.6.5 gprof、time、ulimit

• gprof 只统计用户态且需要 -pg 重编译，对库调用与内联函数不敏感；现代更推荐 perf。
• -pg 与 -O2 可同用，但内联会让调用图失真。

A.6.6 /proc/<pid>/ 常用文件

• 排查”内存涨了但不知道是谁”：对比 /proc/<pid>/smaps 里各 VMA 的 Rss；排查”到底是哪个文件”：ls -l /proc/<pid>/fd/。

A.7 存储与缓存速查

A.7.1 缓存组织的基本公式

地址切分（从高位到低位）

 m-1            m-s-b   m-s-b-1        b   0
+----------------+-------+---------------+
|   tag (t 位)    | 组索引 |  块偏移 (b 位)  |
|                | (s 位) |               |
+----------------+-------+---------------+

• 为什么组索引取中间位：若用高位做索引，连续地址会全部落在同一组，造成严重冲突；用低位做索引则大步长访问（跨块）会全撞一组。中间位同时打散这两类模式。
• 一条缓存行（line）的元数据：有效位（valid bit）、标记（tag）、脏位（dirty bit，仅写回策略需要），外加 $B$ 字节的数据块。
• 组相联查找：组索引选中一组 → 组内 $E$ 行并行比较标记与有效位 → 命中则按块偏移取字节，未命中则从下一级取块并替换组内某行。

A.7.2 命中 / 未命中 / 替换 / 有效位 / 脏位

A.7.3 写策略四格表

• 记忆：真实的 L1/L2/L3 = 写回 + 写分配；简单的写直达缓存常配非写分配。
• 写回策略下，丢弃脏行是数据丢失；msync/fsync 就是把”缓存里的脏数据”强制推到下一级。

A.7.4 3C 未命中分类与削减手段

• 判定顺序：先看是不是第一次访问（冷）→ 再看”若缓存无限大是否还会未命中”（容量）→ 否则是冲突。
• 冲突未命中是唯一可以不改硬件、只改代码就消除的一类（用 padding 或重排访问顺序）。
• 3C 之外常补充第四类：一致性未命中（coherence miss）——其他核写入了共享块导致本核的副本作废。

A.7.5 AMAT：平均访存时间

多级缓存的 AMAT 递推（把下一级整体看成”上一级的未命中惩罚”）：

• 算例（讲义原例）：命中 1 周期、未命中惩罚 100 周期。 97% 命中 → $1 + 0.03\times100 = 4$ 周期；99% 命中 → $1 + 0.01\times100 = 2$ 周期。 即”99% 命中率是 97% 的两倍好”——命中率的微小提升在 AMAT 上被放大。
• 优化方向只有两条：降低未命中率（局部性、分块）或降低未命中惩罚（多级缓存、预取、更宽的带宽）。

A.7.6 Intel Core i7 缓存层次参数

• 块大小对所有层级统一为 64 字节（$b=6$）。
• L1 d-cache 的地址位域（47 位物理地址，Core i7）：$C = 64 \times 8 \times 64 = 32768$ B ； $S = C/(E \times B) = 32768/(8\times64) = 64 \Rightarrow s = 6$ ；$b = 6$ ；$t = 47 - 6 - 6 = 35$ 位。

物理地址 47 位 → L1 d-cache 划分
 46            12 11        6 5          0
+----------------+-----------+------------+
|  tag: 35 位     | set: 6 位 | off: 6 位   |
+----------------+-----------+------------+
例：地址 0x00007f7262a1e010
    tag  = 0x7f7262a1e
    set  = 0x0        (位 11..6)
    off  = 0x10       (位 5..0，落在块内第 16 字节)

• 术语对照：L1/L2/L3 = 缓存层级；i-cache = 指令缓存、d-cache = 数据缓存、unified = 二者合一；块偏移/组索引/标记三段切分对每一层都成立，只是 $s$、$t$ 不同。
• 页大小 4 KB = 64 块/页，因此同页内的相邻块组索引不同、标记相同——这是”TLB 与 L1 可并行查找”的硬件基础（决定组索引的位在 VA 与 PA 中相同）。

A.7.7 局部性速查

• 验算口诀：“每 $B/\text{sizeof(elem)}$ 个连续元素共享一次未命中”。double 数组、64 B 块 → 每 8 个元素一次未命中。
• 矩阵 sumA += a[i][j] 按行 vs 按列，实测可差 10 倍以上（Core i7 上讲义实测从约 20 GB/s 掉到不足 2 GB/s）。

A.7.8 分块（Blocking）速查

原则：把大矩阵切成 $B \times B$ 的小块，让一个块在被换出之前被尽可能多次复用——把”对全矩阵的时间局部性”压缩到”对一个小块的时间局部性”，使工作集装得进缓存。

64×64 转置的 4×4 子块 + 8 局部变量技巧（Cache Lab 经典）

• 测什么：Cache Lab 用 csim 模拟器统计 hits/misses/evictions，再对真实 trans 用 valgrind --tool=cachegrind 看 D1 miss rate。
• 判断是否有效的实操：先 perf stat -e L1-dcache-load-misses,LLC-load-misses ./prog 看基线，再改分块后对比。

A.7.9 存储器山（Memory Mountain）读法

定义：以读取吞吐率（read throughput，MB/s）为高度，横轴为工作集大小（size，从 32 KB 到 128 MB，对数刻度），另一轴为步长（stride，1–11 个 long，即 8–88 字节）的三维地形图。它把内存系统的空间/时间局部性一次性画成一张图。

• 读法三步：① 沿某根”脊”（固定 stride）走，定位三级台阶 → 读出 L1/L2/L3 容量；② 沿某个”坡”（固定 size）走，看 stride 从 1 增到 11 的跌幅 → 读出块大小的影响；③ 比较不同机器的山形，即可判断其缓存层次与预取策略的强弱。
• 测量方法（讲义 mountain.c）：test(elems, stride) 用 4×4 循环展开累加，先跑一次预热缓存，再跑一次计时；对多种 elems/stride 组合重复，绘制成图。
• 实践意义：“为什么我的程序忽快忽慢”——把访问模式（size × stride）落在这张图上，就知道它在吃哪一级缓存。

A.8 虚拟内存速查

A.8.1 术语表

A.8.2 关键恒等式与翻译流程

地址翻译数据通路

 CPU 发 VA
   │
   ├─ VPO (12 位) ────────────────────────────────┐
   │                                              │
   └─ VPN (36 位) → [ TLB 查找 ]                  │
                     │命中                        │
                     │   PPN ──────────┐          │
                     │未命中           │          │
                     ↓                 ↓          ↓
              查页表（最多 4 级访存）→ PPN ──► 拼接 PA = PPN|VPO
                                                 │
                                                 ↓
                                         查 L1/L2/L3 → 取数据

• TLB 命中省掉一次内存访问；TLB 未命中只是”多一次访存”，与缺页（可能含磁盘 I/O）量级完全不同。
• 无论页表有多少级，TLB 缓存的始终是完整的 VPN → PPN 映射。

A.8.3 x86-64 四级页表位划分

 47        39 38       30 29       21 20       12 11          0
+------------+-----------+-----------+-----------+-------------+
|  PGD (9)   |  PUD (9)  |  PMD (9)  |  PTE (9)  |  offset(12) |
+------------+-----------+-----------+-----------+-------------+
     │            │            │            │
   CR3 ──►L4表──►L3表────────►L2表────────►L1表────────► PPN | offset = PA

A.8.4 缺页处理流程

• 关键洞察：”合法的地址 + 无效的 PTE” 是正常流程（按需分页），不是错误；只有”地址不在任何 VMA”或”权限不符”才是真正的段错误。
• error code 读法（dmesg 里 segfault at 0 error 4）：bit 0 = 保护违规（1）还是页不存在（0）；bit 1 = 写（1）还是读（0）；bit 2 = 用户态（1）还是内核态（0）。
• 观察命令：perf stat -e page-faults,minor-faults,major-faults ./prog；/usr/bin/time -v ./prog 看缺页总数。

A.8.5 TLB 参数（Intel Core i7）

• 位域计算（L1 d-TLB）：VPN 共 36 位，组数 $= 64/4 = 16 \Rightarrow$ TLBI = 4 位；TLBT = 36 − 4 = 32 位。
• 性能含义：工作集（活跃页数）≤ TLB 项数时命中率接近 100%；一旦超出，每轮都要换入换出，命中率崩盘——“工作集小于 TLB 容量则快”。
• 大页（2 MB）把”每页 4 KB 一个 TLB 项”变成”每页 2 MB 一个 TLB 项”，同样项数覆盖 512 倍的内存，是数据库/大内存程序的常用优化。
• 观察命令：perf stat -e dTLB-loads,dTLB-load-misses,page-faults ./prog。
• TLB 与缓存的协同：VPO = PPO，且决定 L1 组索引的位在 VA 与 PA 中相同，因此 TLB 查找与 L1 组索引可以并行；页命中时两者同时完成，进一步掩盖翻译延迟。

A.8.6 Linux VMA 标志

• /proc/<pid>/maps 每行的权限串 rwxp 就是 VM_READ\|VM_WRITE\|VM_EXEC 加 VM_SHARED（s 而非 p）的组合；---p 表示保留但不可访问（如 guard page）。
• 权限位在 PTE 里（硬件实际执行），VMA 标志是内核记账；mprotect 同时改两者中受影响页的 PTE。

A.8.7 mmap 用法与三大用途

#include <sys/mman.h>
void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);
int munmap(void *addr, size_t length);
int mprotect(void *addr, size_t len, int prot);
int msync(void *addr, size_t len, int flags);

• 惯用法：char *p = mmap(NULL, len, PROT_READ\|PROT_WRITE, MAP_PRIVATE\|MAP_ANONYMOUS, -1, 0);
• mmap 之后并不分配物理页（实测缺页增量为 0）——这正是按需分页：只有第一次触碰某页才产生次缺页。
• munmap 归还整个区间；madvise(MADV_DONTNEED) 归还物理页但保留 VMA（适合”释放但留着以后再分配”）。

A.8.8 fork 写时复制（COW）与 execve

• 核心结论：execve 之后所有页都是按需换入的（PTE 无效），所以”启动新程序”并不需要先把整个程序读进内存。
• 观察：cat /proc/<pid>/maps 能看到 r-xp 的 .text 文件映射、rw-p 的匿名堆栈、r--p 的只读共享库段。

A.8.9 malloc 的 brk / mmap 双路径

• 容易混淆：brk 推的是进程级的堆顶；mmap 建的是独立 VMA。两者都只申请虚拟空间，物理页仍按需分配（因此”malloc 了 1 GB 却没爆内存”是正常的，直到你逐页触碰）。

A.8.10 常用命令（VM 相关）

A.9 动态内存分配器速查

对应讲次：Lecture 13（F25-13-malloc-basic.txt）、Lecture 14（F25-14-malloc-advanced.txt）； 教材 CS:APP3e 第 9.9–9.11 节；关联 L5a/L5b Malloc Lab。 表中未出现在 F25 讲义里的实现细节（glibc 调参、错误信息文本）已标注「补充说明」。

A.9.1 malloc 家族接口语义

realloc 的三个边界情形（讲义只给了”改变大小”一句，下表为补充说明，按 C 标准与 glibc 实际行为）：

• malloc(0) 的两套口径：讲义规定返回 NULL；glibc 实际返回一个唯一的最小可 free 块（非 NULL）。写代码时应把 NULL 当”分配失败或零长度”处理，不要依赖 glibc 行为。
• 成功/失败判定：malloc 失败时返回 NULL 并设置 errno，所以 perror("malloc") 有意义；但 size == 0 也返回 NULL 且不设置 errno——这是 malloc 返回值语义最容易踩的歧义。

A.9.2 分配器硬性约束与两个目标

• 附加要求：对齐。必须满足所有对齐约束：讲义口径是 x86-64 上 16 字节；Malloc Lab 放宽到 8 字节（与 libc malloc 一致），mdriver 会强制检查。
• 两个目标（常互相冲突）：

A.9.3 碎片与利用率

利用率与开销（讲义定义）：设第 $k$ 次请求后

• $U_k$ 越接近 1 越好；$O_k$ 是”堆里没被程序数据用掉的比例”，完美分配器趋近于 0。
• 讲义 benchmark syn-array-short（10 个块的分配/释放序列）峰值载荷为 90036 字节，用于画出 $P_k$ 与 $\max_{i\le k}P_i$ 的曲线。

• 内部碎片的三个来源：① 维护堆数据结构（header/footer）的开销；② 对齐 padding；③ 显式策略（例如”小请求也给一个大块”）。
• 讲义 benchmark 数值：完美适配内部碎片开销 1.6%；外部碎片叠加后最佳适配 8.3%、首次适配 11.9%、下次适配 21.6%。

A.9.4 块格式与边界标记（boundary tag）

块布局（asize = 块总大小，含 header 与 footer）：

   low addr                                                      high addr
   +---------------------+--------------------------+---------------------+
   | header: size | a    | payload (app data)       | footer: size | a    |
   | 1 word = 8 bytes    | asize - 16 bytes         | 1 word = 8 bytes    |
   +---------------------+--------------------------+---------------------+
   ^                     ^                          ^
  hdr                 bp = hdr + 8                hdr + asize - 8

size 字的位域：

   63                        3   2   1   0
   +--------------------------+---+---+---+
   |       block size         | 0 | P | A |
   +--------------------------+---+---+---+
                                  A = 本块已分配（cur allocated）
                                  P = 前一块已分配（prev allocated）

为什么低 3–4 位可以复用为标志位：

• 块大小必然是 8 的倍数（因为所有块至少 8 字节对齐、且大小按 word 向上取整），所以 size 的低 3 位恒为 0；当块按 16 字节对齐时低 4 位也恒为 0。
• 既然这些位永远是 0，就不必”存一个恒为 0 的位”，直接借用来当标志。读取大小前 & ~0x7 即可。
• 讲义在”合并四情况”里实际用低 2 位：P<<1 \| A（bit1 = 前块是否已分配，bit0 = 本块是否已分配）——有了 bit1，判断前块状态不用再去读前块 header，合并变成真正的 O(1)。
• Malloc Lab 用 16 字节对齐时可用低 4 位，多出的位可放”块是否来自 mmap“等标记。

边界标记为何给出 O(1) 合并：

   prev_hdr          hdr (= cur_hdr)                next_hdr = hdr + asize
   +--------+--------+--------+-------------------+--------+--------+
   |  ...   | footer | header |   payload ...     | header |  ...   |
   +--------+--------+--------+-------------------+--------+--------+
            ^                                   ^
      prev_footer = hdr - 8                读 next_hdr 的 size 得下一块大小
      -> 读出 prev_size -> prev_hdr = hdr - prev_size

1. 找后块：next_hdr = hdr + asize（当前块大小从自己的 header 读）。
2. 找前块：prev_size = *(word_t *)(hdr - 8)（前块的 footer 就是当前块 header 前 8 字节），于是 prev_hdr = hdr - prev_size。
3. 前后块的大小、分配状态全部O(1) 拿到，不需遍历链表——这是”边界标记 + 立即合并”能做到常数时间释放的全部秘密。
4. 讲义另加两个哨兵：堆起始处的 dummy footer（标记为已分配，防止释放首块时误合并）与堆结束前的 dummy header（防止释放末块时越界合并）。

堆布局示例（隐式空闲链表，标注”大小/分配位”，单位 = word）：

  heap_start                                                   heap_end
  +--------+--------+--------+--------+--------+--------+-------------+
  | 16/0   | 32/1   | 32/1   | 64/0   |  ...   |  8/1   | dummy hdr   |
  | free   | alloc  | alloc  | free   |        | epilog | (allocated) |
  +--------+--------+--------+--------+--------+--------+-------------+
    16     32      32      64      ...      8       8  (bytes)

• header 落在非对齐位置，payload 才是对齐的——这正是”低 3 位可当标志”的物理来源。

A.9.5 四种分配器对比

• 显式链表的插入策略：LIFO（插到表头）与 FIFO（插到表尾）都简单且常数时间，但研究显示碎片比地址序更差；地址序（保持 addr(prev) < addr(curr) < addr(next)）碎片更低，代价是插入需搜索。
• 分离适配的分配流程：① 在合适类中做首次适配，找到就分割并把余料放入合适类；② 该类找不到就试下一个更大的类，直到找到；③ 全都找不到才向 OS 申请新堆内存（sbrk），从新内存切出 n 字节，余料作为一个空闲块放进合适类。

A.9.6 合并的四种情况（立即合并，含边界标记）

设被释放块大小为 $n$，前块大小 $m_1$、后块大小 $m_2$：

• 讲义记法：Case 2 为 n+m2，Case 3 为 m1+n，Case 4 为 m1+m2+n；四种情况都只需常数时间。
• 讲义给出的位变化记法：?0（前块状态未知/空闲）、n 01（本块空闲且前块已分配）、m2 10（后块空闲且前块已分配）等，本质就是维护 P<<1 \| A。
• 合并策略：立即合并（每次 free 就合并，简单、碎片少）vs 延迟合并（攒着直到 malloc 找不到合适块时才合并，提升 free 吞吐率）。

A.9.7 适配策略对比

• 记忆口诀：首次快、下次更差、最佳更省。分离适配的”类内首次适配”可以同时拿到接近最佳适配的利用率与常数级吞吐率，这是它成为工业实现主流的原因。
• 三类策略选择之外还有两个正交策略：分割策略（何时把空闲块切开——直接决定能容忍多少内部碎片）与合并策略（立即/延迟）。

A.9.8 分离适配的大小类划分

2 的幂划分示例（类 $k$ 覆盖 $[2^{k-2}+1,\ 2^{k-1}]$，类内统一按上界取整）：

• 讲义的两条常见选择：① 小尺寸一档一块（16、32、48、64…，类内无内部碎片）；② 到某个点后切换到 2 的幂 $[2^{i}+1,\ 2^{i+1}]$。
• 最大块那一类必须没有上界，否则超大请求无处安放。
• 大小类如何划分”对利用率和吞吐率都有重大影响”，是设计决策而非定式。

A.9.9 realloc 的实现路径

• Malloc Lab 的关键提分点：先能用 mm_malloc+mm_free 搭出 realloc（保证正确性），再改写成独立的 realloc（原地扩展 + 原地缩小），因为最后 2 个 trace 全是 realloc，吞吐率差距明显。
• 语义红线：realloc 失败时必须返回 NULL 且不动原块；返回的新块同样要满足8 字节对齐。

A.9.10 glibc malloc 要点

以下均为补充说明（F25 讲义未涉及 glibc 实现细节），用于对照 Malloc Lab 与真实调试。

• arena 与竞争：多线程下 glibc 会为每个线程分配独立 arena，减少锁竞争；这也是为什么”多线程 malloc”看起来并没有一个全局锁那么慢。
• tcache：glibc 2.26+ 每个线程有一组 tcache（每类最多 7 个块）的快速缓存，malloc/free 的绝大多数操作在此完成、几乎无锁——这解释了下面那些错误信息里的 in tcache 2。

A.9.11 glibc 常见错误信息含义

补充说明（讲义未涉及；文本随 glibc 版本略有差异）。这些都是堆元数据被破坏的信号，不是”分配器不可靠”。

• 最实用的一招：编译时不要”绕过”分配器检查——MALLOC_CHECK_=3 ./prog、MALLOC_PERTURB_=165 ./prog（每次分配填垃圾值，暴露”读了未初始化内存”）、以及 valgrind。Malloc Lab 里则完全靠自己写的 mm_check 堆一致性检查器。

A.9.12 Malloc Lab 提分点清单与 mdriver 用法

评分公式（官方 writeup：Correctness 20 + Performance 35 + Style 10）：

评分规则红线：

• 不得修改 mm.c 里的四个接口签名（mm_init/mm_malloc/mm_free/mm_realloc）。
• 不得调用任何内存管理相关库函数/系统调用：禁止 malloc、calloc、free、realloc、sbrk、brk 及其变体。
• 不得定义任何全局或静态复合数据结构（数组、结构体、树、链表）；只允许全局标量（整数、浮点、指针）。空闲链表必须构造在堆内存里。
• mm_init 出错返回 -1，否则 0；mm_malloc 必须返回 8 字节对齐的指针（mdriver 强制检查）。

提分路线（按投入产出排序）：

mdriver 命令行（-h 可查全部）：

• 官方 hint 摘要：先用 -f 跑小 trace 建立正确性；前 9 个 trace 只含 malloc/free，最后 2 个含 realloc——先把前者做对再做 realloc；用宏封装指针运算（分配器里的指针算术充满强制类型转换，是 bug 温床）；先完全读懂教材的隐式链表例子再动手；用 gcc -g + 调试器定位越界引用。

A.10 进程与信号速查

对应讲次：Lecture 16（F25-16-processes.txt）、Lecture 17（F25-17-ecf.txt）； 教材 CS:APP3e 第 8 章（8.1–8.8）；关联 L6 Shell Lab。

A.10.1 异常四分类

• 机械记忆：中断异步并跳过、陷阱同步并跳过、故障同步并重来、终止同步并结束。
• 异常号（讲义 Figure 8.9 口径）：0 = 除法错误，13 = 一般保护故障，14 = 缺页，18 = 机器检查；32–255 由操作系统定义（Linux 用 128 = 0x80 作系统调用入口）。
• 故障两种结局的典范：缺页 → 内核调页 → 重新执行同一条 movl；非法地址 → 无法恢复 → 内核向进程发 SIGSEGV → “segmentation fault” 退出。同一机制，两种归宿。
• 异常表 / 中断向量：内核启动时把每个异常号对应的处理程序地址填进异常表（exception table，又称中断向量 interrupt vector），硬件按异常号查表跳转。

A.10.2 进程控制接口

• fork 的经典坑：fork 后父子共享终端输出，若在 fork 之前有未 fflush 的 stdio 缓冲，父子各会输出一份 → 同一行打印两遍。修复：fork 前 fflush(stdout)，或改用 write。
• 僵尸进程（zombie）：子进程已终止但父进程尚未 wait，内核保留其退出状态 → 父进程必须回收。父进程先死则子进程被 init/pid 1 收养。

A.10.3 waitpid 选项与 status 宏完整表

#include <sys/wait.h>
pid_t waitpid(pid_t pid, int *statusp, int options);

pid 参数取值：

options 参数（可用 \| 组合）：

statusp 判定宏（必须先判类别、再取具体值，顺序不可颠倒）：

• 返回值：成功返回被回收子进程的 PID；WNOHANG 且无子进程可回收时返回 0；出错返回 $-1$（常见 errno = ECHILD，表示没有可等待的子进程——SIGCHLD 处理程序里用 while ((pid = waitpid(-1, &st, WNOHANG\|WUNTRACED)) > 0)，靠返回 -1/0 退出循环）。
• Shell Lab 的官方推荐用法：waitfg 里用围绕 sleep 的忙循环，sigchld 处理程序里恰好调用一次 waitpid；不要在 waitfg 里也调 waitpid（”虽然可行，但极易混乱”）。

A.10.4 execve 家族表

• execvp 如何搜索 PATH：若 file 不含 /，则按 PATH 环境变量（以 : 分隔的目录列表）依次在每个目录下查找可执行文件；找到即执行，全都找不到才返回 $-1$（errno = ENOENT）。若 file 含 /，则当作路径直接使用，不搜索 PATH（这正是 Shell Lab 里 ./myspin 与 myspin 行为不同的原因）。
• execve 与 argv 约定：argv[0] 按惯例是可执行文件名（可任意，程序无法强制校验），argv 必须以 NULL 结尾。
• execve 之后的代码只在失败时执行——Shell 中的标准写法是 execve(...); fprintf(stderr, "%s: Command not found.\n", argv[0]); exit(0);。

A.10.5 进程组与作业控制

kill(pid, sig) 的 pid 取值含义：

Shell Lab 的作业控制要点：

• 子进程在 fork 之后、execve 之前必须调用 setpgid(0, 0)，否则子进程默认留在 Shell 的进程组里——于是 Ctrl-C 会同时打到 Shell 自己和它创建的所有进程，这显然是错的。
• Shell 捕获 SIGINT/SIGTSTP 后，必须用 kill(-pid, SIGINT)（负的 pid）转发给整个前台进程组；sdriver.pl 会专门测试你有没有用 -pid。
• 必须在 fork 前用 sigprocmask 屏蔽 SIGCHLD，在 addjob 之后解除屏蔽，否则会出现”子进程已被 sigchld 处理程序回收并从作业表删除，父进程却还没 addjob“的竞态。由于子进程继承父进程的屏蔽字，子进程在 execve 前必须解除 SIGCHLD 屏蔽。

A.10.6 常用信号表（编号 / 默认动作 / 可否捕获或阻塞）

* 带 * 的信号只能被”其他进程发来的”实例阻塞；由当前指令直接触发的同步异常（如自己产生 SIGSEGV/SIGILL）无法靠屏蔽躲开。

• 信号类型用小整数 ID（1–30）标识；信号里唯一的载体就是 ID 和”它到了”这个事实，不携带数据。
• SIGKILL(9) 与 SIGSTOP(19) 是唯二不可捕获、不可忽略、不可阻塞的信号。

A.10.7 sigaction 结构与 sa_flags

#include <signal.h>
int sigaction(int signum, struct sigaction *act, struct sigaction *oldact);
/* 结构字段：sa_handler / sa_sigaction、sa_mask、sa_flags */

• signal() 的教训：老接口 signal() 语义在不同系统上不一致（是否重启系统调用、是否重置），Posix 标准推荐一律用 sigaction。
• 隐式屏蔽：内核在进入处理程序前，自动把”正在处理的信号类型”加入屏蔽集——所以 SIGINT 处理程序不会被另一个 SIGINT 打断（这正是”同种信号不会嵌套”的机制来源）。

A.10.8 阻塞与待处理信号

暂时阻塞信号的惯用法（保护不可被打断的代码区）：

sigset_t mask, prev_mask;
sigemptyset(&mask);
sigaddset(&mask, SIGINT);
sigprocmask(SIG_BLOCK, &mask, &prev_mask);   /* 阻塞 SIGINT，并保存原掩码 */
    /* 这段区域不会被 SIGINT 打断 */
sigprocmask(SIG_SETMASK, &prev_mask, NULL);  /* 恢复原掩码 = 解除阻塞 */

• 恢复必须用 SIG_SETMASK + 保存的旧掩码，而不是 SIG_UNBLOCK——否则会把调用者原本就屏蔽的信号误解除。

A.10.9 异步信号安全（async-signal-safe）函数

定义：函数是异步信号安全的，当且仅当它要么可重入（所有变量都在栈帧上），要么不可被信号打断。POSIX 保证 117 个函数满足该性质（man 7 signal-safety）。

• write 是唯一的异步信号安全输出函数——所以信号处理程序里要打印信息，只能用 write(STDOUT_FILENO, buf, n) 或 CS:APP 提供的 SIO 库（sio_puts、sio_putl、sio_error、支持 %c %s %d %u %x %% 的 sio_printf，内部只用 write）。
• longjmp 的限定：自 POSIX.1-2008 TC2 起列入安全清单，但若处理程序打断的正是某个非异步信号安全函数，从处理程序中 longjmp 出去行为未定义。

A.10.10 信号处理五条准则

G1–G3 代码骨架：

volatile sig_atomic_t flag = 0;              /* G4 + G5 */

void handler(int sig)                        /* G0：尽量简单 */
{
    int olderrno = errno;                    /* G2：进场保存 errno */
    flag = 1;                                /* G5：只做赋值，无需加锁 */
    write(STDOUT_FILENO, "caught\n", 7);     /* G1：只用异步信号安全的 write */
    errno = olderrno;                        /* G2：退场恢复 errno */
}