VM 的 return 无论函数返不返回值,都会在 ARG 指向的位置留一个返回槽;编译器对 void 的 do 调用跳过 pop,于是每次调用漏 1 字,Tetris 玩久了栈顶会顶穿堆区。修完后 ROM 溢出,又靠官方三字 pop 惯用法省回 674 字。最终 7 个检查点屏幕哈希全不变、门级 7/7 零分歧、demo 重发布。
这个 bug 最难受的地方,是它一直看起来不像 bug。
Tetris 跑完一亿七千多万个周期,7 个检查点的屏幕哈希全对,门级模拟器和行为级解释器逐周期一致,测试全绿。然后我翻开编译器生成的 VM 代码,发现每一个 do 调用后面,都少了一条 pop。
也就是说:这个程序一直在漏栈。只是它漏得很安静。
先交代一下战场
这是 Nand2Tetris 的 Hack 计算机,16 位、32768 字的 ROM、512×256 的屏幕。我没有用官方工具,而是把软件栈整个重写了一遍:
- 汇编器:两遍扫描、符号表、全错误报告;
hackrun:行为级 ISA 解释器,1 指令 = 1 周期,作为整条工具链的 oracle;- VM 翻译器:全部段、算逻、流控、调用帧;
- Jack 编译器:词法、递归下降语法分析、AST 到 VM 的代码生成;
- Jack OS 子集:Memory 分配器、Array、Math、String、Output、Screen、Keyboard、Sys;
- Tetris:用自己写的语言、自己的编译器、自己的 OS 跑起来。
为了证明“我写的编译器没有把 ROM 编错”,我准备了两把尺子:一把是行为级解释器,一把是硬件轨的门级模拟器。同一份 ROM 喂给两边,逐周期比对 pc、a、d、addressM、writeM、outM,再在 7 个检查点分别对屏幕取 SHA-256。两边一致,才算过关。
这套东西看起来已经挺像回事了。所以第一轮审计修完 10 项之后,我以为剩下的只是收尾。
调用约定里的那一个字
Jack 里的 do 语句用来调用一个函数并丢弃返回值:
do Screen.drawRectangle(0, y1, 511, y2);
do Output.printInt(score);编译器要为它生成 VM 代码。VM 的调用约定是这样的:
call f n:
依次压入 返回地址、LCL、ARG、THIS、THAT
ARG = SP - (n + 5)
LCL = SP
goto f
return:
*ARG = pop()
SP = ARG + 1注意最后两行。return 根本不看函数签名,它只认栈:从栈顶弹出一个字,写回 *ARG,然后把 SP 设成 ARG + 1。
假设参数已经压好、call 即将执行时 SP = S,n 个参数占着 S-n 到 S-1。call 压入 5 个字后 SP = S+5,ARG = S-n。函数返回时 SP = ARG+1 = S-n+1。参数被消费掉了,调用方本该回到参数入栈前的 S-n;但 return 留下了一个返回槽,SP 停在 S-n+1。想让栈恢复调用前的形状,就必须再弹一次。
对非 void 函数,这个字是返回值。对 void 函数,它弹出来的可能是局部变量、临时值,甚至是被保存的寄存器之一——反正调用方不会读它。但垃圾也要弹。 这是 ABI 的一部分,不是语言层面的“有没有值”。
我之前的编译器不是这么想的:
case "do": {
compileExpr(st.call, ctx);
// 旧注释:void callees leave no value on the stack
if (ctx.subroutineRets.get(calleeFullName(ctx, st.call)) !== "void") {
out.push("pop temp 0");
}
return;
}注释写得很自信:void 函数不在栈上留值,所以不用弹。可 VM 的 return 不认这句话。它每次都会留下返回槽,不管你是不是 void。
于是每次 do SomeVoid(),SP 净增 1。修复只需要删掉那个条件:
case "do": {
compileExpr(st.call, ctx);
// VM return 恒留一个返回槽,void 也一样
out.push("pop temp 0");
return;
}生成的 VM 代码只多了一行,但这一行决定了栈会不会慢慢爬进堆里。
它到底能漏多大
单个字听起来没什么。问题是调用次数。
审计脚本里在一个循环里用 do Memory.dealloc 释放 3222 个块,SP 从约 270 涨到约 3490——每释放一个块,就多留一个字。Hack 的栈区是 256 到 2047,堆从 2048 开始。SP 一旦越过 2048,函数调用的帧和分配器的空闲链表就会重叠,接下来发生的事取决于谁先写谁:可能是 String.new 返回一个指向栈帧的指针,可能是屏幕重绘把堆里的元数据覆盖掉,也可能只是画面某个角落花掉。
Tetris 里每次逻辑帧会触发 1 到 3 次这样的 void 调用。短时间玩没事,玩久了就不是“性能差一点”,而是内存分配器被踩烂。一个看起来正常的游戏,正在以每帧一到三个字的速率走向崩溃。
更值得说的是:为什么这么多测试都没抓到?
- 编译器测试断言的是最终输出:屏幕内容、RAM 里的值、函数返回值。没有一条断言
SP。 - VM 那 400 例差分测试很棒,但它喂给翻译器的是程序生成的 VM 表达式,不是编译器生成的 VM 程序。编译器根本不在这条测试链路上。
- 门级 vs 行为级的对拍更强,但两边跑的是同一份 ROM。编译器的错误已经烤进 ROM 了,门级模拟器和行为级解释器当然会一起错。它们能证明“我的 CPU 和我的解释器一致”,不能证明“我的编译器生成的代码符合调用约定”。
- 黄金脚本只跑到第 5 个方块。在泄漏把栈顶推到堆区之前,7 个检查点的屏幕哈希可以完美通过。
这是一个很典型的测试盲区:每个层都在假设下面那层是对的。汇编器相信 VM 翻译器的输出,VM 翻译器相信编译器生成的东西,集成测试相信 ROM 里的代码。只要错误在进入 ROM 之前就已经发生,后面的所有对拍都会忠实地复现它。
我补的回归测试很朴素:连续做 100 次 do Main.v()、100 次 do Main.f(),然后停在死循环里读 SP。修复后是 268;泄漏版会是 468——200 次调用,正好多 200 个字。
想省两个字,被语义教育
修复加上去,ROM 从 32540 字涨到 32706。再加上 Screen、String、Tetris 的三处修复,变成了 32958 字。
上限是 32768。
汇编器直接把构建拦了下来。这一点值得单独夸一句:ROM 溢出报错本身也是第一轮审计修出来的。在那之前,超过 32768 字的程序不会报错,你会拿到一份看起来正常、实际上 CPU 根本寻址不到的 ROM。
回到溢出。第一反应是做窥孔优化:call f n; pop temp 0 能不能合成一条特殊调用,调用完直接把 SP 减一,不真的写 temp 0?这样每个 do 调用能省两个字。
想法很合理,测试不同意。
已有的 VM 测试里有这么一段:
call Test.f 0
pop temp 0然后它去读 RAM[5],期望值是 11。pop temp 0 的语义就是“把栈顶写进 RAM[5]”,这是一个可观察的副作用。编译器当然知道这个值马上会被丢弃,但 VM 翻译器不能知道,也不该知道——它面对的是任意合法 VM 代码,不是只面对自家编译器。
优化必须在语义边界内做。既然不能省掉写入,那就把 pop 本身写短一点。旧写法是四字:
@SP
M=M-1
A=M
D=M换成官方 VM 翻译器的三字惯用法:
@SP
AM=M-1
D=M关键在 Hack 的 old-A 语义:M= 的写入地址是这条指令开始前的 A,而 A= 同时把 A 改成新值。AM=M-1 一条指令做了两件事:把 SP-1 写回 RAM[0],并把 A 指向新的栈顶。第三字 D=M 把栈顶读进 D。
这个惯用法被铺到了所有 pop 位置:通用 pop、二元运算、比较、if-goto、return、数组写入。每处省一个字,累计把 32958 字压回了 32094 字,还多出 674 字的余量。
有意思的是,修完 bug 的 ROM 比修之前更小:审计前 32540 字,审计后 32094 字。正确性和紧凑性这次没有打架,前提是你愿意去读官方翻译器怎么写。
另外三颗地雷
栈泄漏是第二轮审计里最严重的一个,但不是唯一一个。另外三处都符合“平时没事,特定输入才炸”的特征。
Screen.drawRectangle 忘了裁剪 y
drawRectangle 会先处理坐标交换,再算屏幕基址:
let base = 16384 + (y1 * 32);x 方向有裁剪,y 方向没有。如果调用者传进来负数 y,base 就会落到 16384 以下——那是堆区。画一个矩形,等于往堆里写数据。
修复是在交换之后把 y 夹到屏幕范围:
if (y1 < 0) {
let y1 = 0;
}
if (y2 > 255) {
let y2 = 255;
}回归测试直接画 y = -5、y = -200、y = 250..300,然后断言 ram[16384 - 160] 和 ram[16384 - 32] 仍然是 0,同时第 250、255 行确实被点亮。既证明没有越界写,也证明可见部分没被裁没。
String.setInt 不尊重 maxLength
String.new(maxLength) 按容量分配,setInt 却默认“符号位加数字一定放得下”。对一个容量只有 2 的字符串调用 setInt(-32768),它会写 6 个字符,把相邻的堆块踩坏。
修复是在每次写符号和数字之前检查 len < maxLength。测试用 String.new(2) 存 -32768,期望得到 "-3"(长度 2,字符 45 和 51);再用 String.new(0),期望长度保持 0。不是“尽量写”,而是“容量不够就截断”。
Tetris 的长按只动三次
按住方向键时,Tetris 用一个 repeatCnt 做自动重复:计数没超过 3 就继续处理方向。但计数只增不减,超过 3 之后就再也不会回到可触发区间——按住右键,方块横移三次,然后永远停住。
修复是让计数回绕:
// wrap the counter so a held key keeps auto-repeating
if (repeatCnt > 3) {
let repeatCnt = 0;
}测试从第一个检查点开始按住右键 4000 万周期,每 10 万周期采样一次方块横坐标,直到方块落地;断言移动次数大于 3。修复前这个数字会卡在 3。
第一轮的十项,大多是“错误不够响”
第一轮审计集中在工具链外围,修的东西没有栈泄漏这么戏剧性,但共同点是:它们让错误变得可见。
| 位置 | 问题 |
|---|---|
| VM 翻译器 | label/goto/if-goto 用模块作用域,同名 label 跨函数串地址;改为函数作用域 |
| VM 翻译器 | 数组读窥孔覆盖了 THAT 的副作用,let a[i] = a[j] 可能写错地址 |
| hackrun | 检查点 dump 共享同一块 RAM,所有检查点看到的都是最终状态;改为逐检查点快照 |
| hackrun | run() 的 maxCycles 差一 |
| 汇编器 | 用原型链判断预定义符号,@toString 被误判;改用 Object.hasOwn |
| 汇编器 | ROM 超过 32768 字不报错;改为显式失败 |
| VM 解析器 | 无参指令带了参数也不报错 |
| disasm | 标签类型判断错误 |
| CLI | 不剥 UTF-8 BOM |
| jackc | 多类共享静态区没有警告 |
这些 bug 单独看都不致命,但它们的共同效果是“让错误安静地通过”。审计的价值有时候不是修一个惊天大 bug,而是把系统里所有“静默”改成“吵闹”。
改完怎么证明没改坏
这是我最喜欢的部分:修了编译器、VM 翻译器、OS 和游戏逻辑,怎么证明 Tetris 的行为没变?
答案是黄金检查点。重录之后:
- 7 个检查点的屏幕 SHA-256 全部不变,从开局
376f24bd…到终局eb9348b8…; - 最终局面不变:
LINES 1 · SCORE 100; - ROM 从 32540 字变成 32094 字,
romSha256=aaa3b68c…40de; - 总周期从 175,296,393 变成 166,446,228。
最后一条一开始让我愣了一下:哈希全一样,周期怎么少了 885 万?
因为指令变少了。三字 pop 让每个 pop 位置少一条指令,整份 ROM 小了一截;do 修复虽然增加了 pop,但总体上还是净减少。屏幕哈希不变、周期数下降,这正好是“语义没变、执行路径变短”的签名。如果哈希变了,才说明我们把行为改坏了;如果周期没变,才说明优化没生效。
接着是更重的一关:门级模拟器。把同一份 ROM 和 25 条输入事件交给硬件轨的门级计算机,跑满 166,446,228 个周期:
oracleDiff.ok = true,firstDivergence = null;- 7/7 检查点的门级屏幕哈希 = 行为级 oracle = 黄金记录;
- 全程十几分钟,门级模拟大约 20 万周期/秒。
以及浏览器里的行为级 demo:重新部署到 Cloudflare Pages,线上 tetris.hack、input.txt、meta.json、engine.js、ui.js、index.html 的哈希全部与本地构建一致;Chromium 里开机渲染、方向键移动、黄金脚本回放到 LINES 1 · SCORE 100,画布哈希 1723327576,控制台零错误。
测试数从审计前的 58 条变成 71 条。新增的不是“多跑几个用例”,而是四类以前没有的断言:栈平衡、屏幕边界、字符串容量、长按重复。
审计之后留下的
这次两轮审计一共 16 项发现,修了 14 项。剩下两项我没有硬修,而是明确写进了文档:
- VM 的
gt/lt采用 nand2tetris 参考翻译器的 16 位环绕差值判定,异号且差值绝对值大于等于 32768 时和数学比较不一致。防溢出的内联展开每处约多 14 字,Tetris 有 76 处比较,ROM 余量不够,所以保留紧凑实现并加固定用例。 - 未定义标签的链接检查还没实现:
@Missing会被当成新变量分配,而不是报错。这是 Hack 汇编器的传统行为,但对一个自称全错误报告的工具链来说,是个缺口。
我不觉得这是什么光彩的收尾,但审计报告如果只写修好的部分,那它就是公关稿,不是报告。
如果让我只留一条结论,大概是这个:差分测试证明的是一致性,不是正确性。 当两个实现共享同一个错误时,它们会相处得非常融洽。真正能抓住这类 bug 的,是断言不变量——SP 应该回到哪里、堆边界有没有被越过、ROM 有没有超限——以及偶尔真的去读一眼生成的代码。
现在再跑一次 Tetris,最后一行还是 LINES 1 · SCORE 100。画面和修复前一模一样,但栈底那些多出来的字终于不再往上爬了。
Demo 还在这里:nand-computer-demo.pages.dev
继续阅读 · 相关文章
根据文章内容的语义相似度自动推荐