经典实验手册：把机制变成可验证的实现

本手册把六个经典实验拆成可以独立推进的里程碑。每个实验都有两层材料：官方自学 handout 用来遵守原接口与评分规则；本仓库原创练习用来观察机制。两者必须分别记录结果，不能将教学测试通过写成官方 lab 完成。

开工前：固定目标与环境

在 CS:APP3e 官方实验目录 下载对应 Self-Study Handout。压缩包由官网托管，本仓库不镜像第三方二进制或教师解答。下载后在独立目录解包，保存 URL、下载日期、SHA-256、README，以及 uname -m、cc --version 和 file 对关键可执行文件的输出。

# 对你实际下载的文件执行；不预设尚未下载的包名存在。
shasum -a 256 datalab-handout.tar
file bomb
uname -m
cc --version

原始 Bomb/Attack 目标为 Linux x86-64，官方 Cache Lab 也要求合适的 x86-64 环境。macOS arm64 上本仓库的六个 C 程序能运行，不意味着原 handout 可原生执行。优先使用你管理的 Linux x86-64 虚拟机或机器；老实验包可能还需要兼容工具和库，按 README 处理，不要为了匹配网上文章盲目修改系统。

统一记录表：输入/trace → 预期机制 → 实际输出 → 判断 → 修复。先写预期再运行，能避免只接受自己程序给出的答案。

1. Data Lab：先推导位，再满足限制

目标是构造位级函数并满足每题操作规则。官方说明

任务拆解。 先给每题列真值或分类表：零、全一、符号位单独置位、正负边界。对选择函数，从布尔量构造全零/全一掩码，再用两份互补掩码选择输入。对大小比较，先区分符号不同与相同，避免用可能溢出的差直接判断。浮点字段题先分出 NaN/无穷、非正规、正规三类，再考虑指数和尾数的变换。

关键实现。 整数题受限于特定运算符和控制流，不能直接移植本仓库循环写法。把每一步解释成位模式变换，检查常量宽度和中间表达式。对 float 位题，输入是整数编码，不能偷偷用浮点计算再转回。

运行与判据。 在下载包的目录执行 make，然后 ./btest -f bitXor 聚焦一个函数；./dlc -e bits.c 查看规则与计数；最后 ./driver.pl。以实际 handout 函数名为准。通过功能测试但 dlc 报错，仍未完成官方要求。

常见错误。 右移负数的环境假设与通用 C 混用；移位 32 位；漏掉最小补码；NaN 被错误转换成普通数；非正规转正规时忘记指数边界。将触发错误的具体位模式写成十六进制保存，逐步检查符号、指数和小数字段。

完成产物。 每题一段推导、一组边界用例、合法性检查结果。本站 位表示 的 bits.c 提供另一种可读参考与边界测试方式。

2. Bomb Lab：输出控制流证据

目标是理解当前二进制每一阶段的接受条件，而不是寻找可套用的答案。官方说明

任务拆解。 先找主流程与阶段入口；再找输入解析；然后将每个失败分支反向转换成必须成立的条件。字符串阶段检查比较函数参数；整数阶段检查输入数量与递推；switch 阶段画跳转表；递归阶段写出递归关系；链表阶段分别跟踪输入索引、节点数值和 next 指针。

关键数据结构。 对疑似节点，先确认字段宽度及偏移，例如值是否 32 位，next 是否 64 位，padding 占多少。使用 x/… 按正确宽度查看，避免把相邻两个 int 拼成一个 long 后误判。用一张节点地址到字段内容的表还原结构。

调试流程。 objdump -d bomb 获取全图；在 GDB 设置阶段入口和失败函数断点；disassemble phase_1 看局部；info registers、x/s、x/8gx $rsp 查看实时状态；ni 跨过不需要深入的调用，si 逐指令验证关键处。先确认寄存器含义，再解释读出的字节。

测试预期。 你推导的输入能逐一满足所有比较，并到达下一阶段。已完成阶段保存在本地输入文件中，便于重放。失败时回到第一个偏离预期的比较，修改约束模型，避免随机试数。

常见错误。 将字符串地址当成内容；忽略 sscanf 成功解析个数；混淆 signed/unsigned 分支；把数组索引当节点数值；从不同版本复制答案。

完成产物。 每阶段的控制流草图、约束和调试证据；自己的本地输入。具体阅读方法见 机器代码。

3. Attack Lab：验证栈布局与控制转移

在官方提供的本地实验目标内，观察无边界输入怎样影响保存状态，并理解对应防护。使用 handout 的 ctarget/rtarget 与指定目标函数，不涉及外部系统。官方说明

任务拆解。 先找到 getbuf 的栈分配与返回位置；测量缓冲区到保存返回地址的实际距离；确认当前阶段目标函数的参数；按照目标字节序组织本地测试输入；最后在调试器验证每一步栈变化。后续返回导向阶段，先为可用 gadget 建立“消耗几个栈槽、改变哪些寄存器、下一步从哪里取地址”的表。

关键思考。 保持控制转移所需的 ABI 条件。进入目标函数并不代表完成：参数值、字符串生命周期、栈对齐和后续调用覆盖都可能导致失败。把填充长度、目标地址、参数数据分别标注，避免无法解释的十六进制长串。

运行与预期。 使用 ./ctarget -q 或 ./rtarget -q 的本地模式；按 handout 使用 hex2raw 将自己生成的十六进制文件转为输入。逐阶段检查目标中的验证结果，不修改验证逻辑。输入中的特殊终止字节也要按手册约定处理。

常见错误。 从数组声明猜偏移；地址未按小端排列；把其他目标的 cookie/地址搬来；临时字符串在后续栈使用中被覆盖；把 NX、ASLR、canary 当作同一种保护。

完成产物。 每阶段一张栈图、控制转移轨迹、当前目标的本地验证记录，以及“哪一种边界检查或防护阻断哪一步”的解释。没有相应 Linux 环境时保留纸面分析，记录未运行，不伪造通过信息。

4. Cache Lab：模拟器先对，再研究转置

官方任务包括缓存模拟和矩阵转置优化。官方说明

任务拆解。 第一阶段实现地址拆分、set 内查找、valid/tag、替换策略和统计；第二阶段处理 trace 的 I/L/S/M 语义；第三阶段与参考程序逐条比较；最后开展转置优化。不要同时调试模拟器与优化算法，否则 miss 差异难以定位。

数据结构。 每行至少保存有效位、tag 和用于 LRU 的状态。相联度 E 个元素构成一组。命中更新时间，miss 有空行先用空行，满组才 eviction。本站 cache_sim.c 的扩展支持跨块访问，官方提交实现需严格遵从 handout 的输入约定与命令行接口。

调试与判据。 本站 make -C labs/csapp test 有 direct、LRU、cross 三条 trace，以及非法配置、地址范围检查。在官方目录用 ./test-csim 检查模拟部分，./test-trans -M 32 -N 32 检查相应转置尺寸，再用该包的 driver 完整验证。工具与尺寸以实际 README 为准。

优化步骤。 首先建立正确的朴素转置；再添加块循环；随后观察对角元素与 A/B 组冲突；必要时用局部临时变量降低交错驱逐。每次只改变一个策略，同时保存正确性与 miss 数。

常见错误。 M 只记一次；I 计入数据 cache；每次 miss 都加 eviction；命中不更新 LRU；把十六进制 10 读成十进制 10；为了降低 miss 写出了错误的矩阵。

完成产物。 可重放的最短反例、模拟器结果、每个目标尺寸的转置验证与优化前后统计。详见 缓存。

5. Shell Lab：把并发事件放进状态机

官方 handout 的核心是带作业控制的 tsh。官方说明

任务拆解。 先运行单前台命令；增加后台作业表；实现退出回收；加入停止/继续；实现 jobs、bg、fg；最后正确转发前台作业组信号。每步只增加一种状态变化，对应运行较短 trace。

状态与同步。 作业状态可抽象为 FG、BG、ST、已删除。退出到删除，停止到 ST，bg 转为 BG，fg 转为 FG 并等待。fork 前屏蔽 SIGCHLD，父进程加入作业表后恢复，孩子执行新程序前恢复。所有访问作业表的上下文都要遵守同一屏蔽协议。

调试与预期。 make test01 与 make rtest01 比较自己的 tsh 与参考程序；也可按 README 用 sdriver.pl -t trace01.txt -s ./tsh -a '-p'。PID 每次不同，应比较行为而不是硬编码 PID。逐条推进 trace，特别检查立即退出、多孩子合并通知、后代进程也收到信号。

常见错误。 handler 删除作业发生在 addjob 之前；只 wait 一次漏回收；把退出 status 当退出码；kill 正 PID 只影响一个进程；用 sleep 掩盖竞态；主流程与 handler 同时回收同一孩子。

完成产物。 状态转移表、信号屏蔽时间线、全部所用 trace 的结果。本站 tiny_shell.c 只展示前台运行，process_demo.c 专门展示不丢唤醒，两者均未实现完整 Shell Lab。见 异常控制流。

6. Malloc Lab：每次修改都守住堆不变量

官方实验的接口、模拟堆工具和性能指标以 handout 为准。官方说明

任务拆解。 初始布局 → 请求对齐 → 找块与分裂 → 释放 → 合并 → realloc → 性能优化。初期先用隐式链表，稳定后再引入显式链表或分离适配，避免一次引入所有指针关系。

数据结构。 每个块需要大小和分配状态，常见设计用 header/footer 支持邻块发现；空闲块还可以存链表指针。不要把块的总大小、payload 容量和用户请求大小当同一字段使用。最小块必须能容纳所有必要元数据并满足对齐。

验证。 mm_checkheap 类检查器要遍历物理堆与空闲表，核验边界、对齐、header/footer 一致性、链表对称和空闲块唯一性。在官方目录使用 ./mdriver -V 获得详细结果。本站 allocator 验证固定 arena 的分裂合并与数据保持，不包含官方接口、realloc 或堆扩展。

调试步骤。 找到首个失败 trace，缩短到仍能失败的请求序列；每步打印块偏移、容量和状态；在损坏字段上设置 watchpoint。地址记录可转成相对堆起点的偏移，便于不同运行间比较。

常见错误。 分裂后未更新后继 prev；合并少算 header；释放后继续使用旧的空闲表节点；realloc 先释放旧块导致失败时丢失数据；未检查大小运算溢出；为了吞吐量删除正确性检查却失去定位线索。

完成产物。 堆布局图、不变量清单、短反例、正确性与性能记录。详见 动态分配。

Proxy Lab：只学习请求生命周期

按本课程范围，不要求实现完整代理。把一次请求画成：客户端连接 → 解析请求目标与头 → 缓存查找 → 未命中时连接上游 → 转发响应 → 满足条件时缓存 → 释放资源。每个箭头明确谁拥有 fd、缓冲区和缓存对象。

讨论三个问题即可达到本专题目标：短读/短写怎样影响转发循环；并发缓存如何避免释放仍被使用的数据；只用 URL 做缓存键可能遗漏哪些响应变化因素。HTTP 缓存完整语义超出本章，不把教学代理等同于生产代理。官方 Proxy Lab 说明

自测：实验完成报告中最不能省略的是什么？

版本与环境、实际执行的命令、可重放输入、预期与实际结果，以及未运行部分。只说“理解了”或“测试通过”无法让另一个学习者重复你的判断。

下一章：调试与验证。