常见错误与练习

GC 的难点通常不在“复制几段内存”，而在编译器和运行时是否遵守同一份对象、root 与 safepoint 协议。很多错误只在堆恰好装满时出现，所以一个小程序运行正确，还不能证明 collector 正确。

先整理最常见的错误，再用一组可以实际执行的练习逐步验证本章实现。

常见错误

把机器栈和 shadow root stack 混为一谈

本章的 %rsp/%rbp 管理普通调用帧，%r15 管理只保存 tagged Value 的 shadow root stack。collector 扫描后者，不会猜测机器栈里的任意 word 是否恰好像指针。

如果只把对象地址压到机器栈，却没有写进 root home，GC 不会更新它。

让堆指针只存在于 scratch register 中跨过 safepoint

mini_alloc 会直接触发 GC；普通源语言 call 也可能进入一个会分配的函数。调用前仍然需要的对象必须有 root home。

分配返回以后还要从 home 重新读取。调用前放在 %rax 或 %rcx 中的旧地址不会由 collector 自动修正。

分支只按文本顺序清 root

“IR 文件里最后一次出现”不等于“这条运行路径上的最后一次使用”。一个值若只在 else 中使用，程序走 then 时就不会执行 else 里的清根指令；它可能被错误保活到后续 collection。

正确做法是在 CFG 上反向计算 liveness，并把 branch 的两个后继取并集。程序进入某条具体路径后，下一次 safepoint 会按那一程序点的 live_in 清理死 roots；不需要为了 GC 在每个 label 都插入清根指令。

把 call operands 保留到被调函数返回以后

若 callee 或 argument 在 call 之后已无用途，让它们跨整个被调函数继续作为 roots，可能保留一大块本应可回收的对象图。

后端可以先把 callee、argument 和 raw code address 装入 %rdi、%rsi、scratch register，再清除不属于 call live_out 的 caller roots，最后执行间接调用。被调函数会在第一次分配前建立自己的参数与 capture roots。

忘记清理完全未使用的参数或 capture

一个参数可能在函数体中从未读取，一个 closure capture 也可能经过保守构造后不再有实际用途。若只等“最后一次使用”，这些没有 use 的 roots 永远不会被清除。

CFG liveness 会让它们不出现在下一个 allocation 的 live_in 或 call 的 live_out 中，于是下一个 safepoint 会清除相应 metadata roots。

把 closure 的 code pointer 当成 Value 扫描

closure offset 8 保存 raw machine address。它计入 payload_count 和对象大小，却没有 source-language tag。scanner 必须从 offset 16 才开始 forward captures。

用第二个 word 保存 forwarding address

空 record 只有一个 header word。把 forwarding marker 写在 offset 0、新地址写在 offset 8，会覆盖下一个对象。

本章用 new_raw_address | 7 覆盖旧 header，单个 word 就能表示 forwarding。

同一对象复制多次

若第二个别名没有识别 forwarding word，collector 会复制第二份对象。这样 (eq? first second) 会从 1 变成 0，共享 cell 也可能分裂成两份状态。

对环做递归复制却不先安装 forwarding

letrec 会形成：

1

self cell -> closure -> self cell

若复制 closure 的字段以后才记录 forwarding，沿着环会无限重复。应该先复制并在旧对象写好 forwarding，再等待 Cheney scan 处理字段。

把总分配量和最大活跃集混为一谈

程序一生可以累计分配远大于 4096 字节，只要任一 collection 时仍然可达的对象能放进一个半区。

反过来，即使总分配量不算大，只要某一时刻的活跃集超过 4096 字节，copying collector 仍然无法完成。这不是“垃圾太多”，而是“活对象太多”。

把 abort 当作语言错误状态 70

错误 call、closure eq?、非法 size/get 进入 exit(70)。半区 OOM、root stack OOM 或 runtime 内部协议错误进入 abort()。后者通常由信号结束，不承诺固定的 shell 状态。

练习 1：先跑通两条路径

构建本章：

1
2

cd code/09_gc
make

解释执行压力示例：

1

./mini run examples/gc_stress.lang

输出应为：

1

42

再查看结构化 IR：

1

./mini ir examples/gc_stress.lang

在输出中找出：

1
2
3
4
5

self cell 的创建
closure 捕获 self cell
八字段 record
check-closure
递归 call

最后生成并运行汇编：

1
2
3
4

./mini compile examples/gc_stress.lang -o out.s
c++ out.s gc_runtime.o -o out
./out
echo $?

状态也应为 42。Apple Silicon Mac 的链接命令改为：

1

c++ -arch x86_64 out.s gc_runtime.o -o out

这个正常程序的解释器结果与原生状态相同，说明两条路径仍给出相同结果；只有后者实际使用本章的 copying collector。

后面的练习也遵守这个区分：mini run 用来确认语言语义，mini ir 用来观察 lowering；只有 mini compile 生成汇编、再用 c++ 与 gc_runtime.o 链接运行，才能验证本章的 root stack 和 collector。为了避免把“解释器算对了”误写成“GC 已验证”，涉及搬移行为的练习都会保留原生运行步骤。

练习 2：计算压力示例为什么一定触发 GC

gc_stress.lang 每轮创建一个八字段 record，一共递归 120 轮。

先使用公式：

1
2

header = (payload_count << 8) | kind
size = 8 * (1 + payload_count)

填写八字段 record：

检查点：kind 是 1，payload_count 是 8，header 是 2049，大小是 72 字节。

然后计算整个程序的堆分配：

总计：

1

16 + 24 + 1936 + 8640 = 10616 bytes

它明显大于一个 4096 字节半区，也大于两个半区容量之和。原生程序仍能返回 42，说明不可达的八字段临时 record 没有被全部假保活，并且执行过程中确实复用了半区。

单凭这个结果还不能证明每个已死参数 cell 都在最早的 safepoint 被清掉：121 个参数 cell 总共只有 1936 字节，即使错误地多保留一部分，也未必立刻撑满半区。call operand 的及时清理要由练习 9 中专门构造的 300 字段大对象来验收。

问题：为什么这里只能由“累计分配超过半区”推出发生过 collection，却不能说某一时刻有 10616 字节对象同时存活？

练习 3：追踪一个活 record

阅读并运行：

1
2
3
4
5
6

./mini run examples/gc_live_record.lang
./mini ir examples/gc_live_record.lang
./mini compile examples/gc_live_record.lang -o out.s
c++ out.s gc_runtime.o -o out
./out
echo $?

解释器输出和原生状态都应为 42。画出程序开始递归以后最重要的可达路径：

1
2
3
4
5
6

root home
  -> loop self cell
       -> loop closure
            -> loop self cell  (self capture，形成环)
            -> keep cell
                 -> record(40, 2)

每轮创建的八字段 record 会变成垃圾，但 keep 指向的二字段 record 必须沿这条路径跨越所有 collections。某些程序点也可能有 root home 直接指向 keep cell；它一旦不在当前 live_in 中，就可以被清掉，因为递归 closure 仍然间接保活同一个 cell。

生成汇编后，不要要求 keep capture 的 home 在每个 mini_alloc 前都非零。应检查的是：每次可能触发 collection 时，二字段 record 都能从某个活动 root 沿对象边到达；allocation 返回后，后续字段访问又从已更新的 home 或对象字段重新加载地址，而不是继续使用调用前 %rax 中的旧地址。

练习 4：空 record 怎样 forwarding

运行：

1
2
3
4
5

./mini run examples/gc_empty_record.lang
./mini compile examples/gc_empty_record.lang -o out.s
c++ out.s gc_runtime.o -o out
./out
echo $?

解释器输出和原生状态都应为 42。源码在递归结束时计算：

1

(+ (size keep) 42)

解释器结果先确认这段源码的语义；原生状态才进一步说明空 record 在 copying collector 下仍然存活，并且搬移后字段数仍是 0。

填写布局：

检查点依次是 1、0、1、8。

在纸上分别画出普通 header 和 forwarding 后的旧 header：

1
2

collection 前  [ header = 1 ]
collection 后  [ new raw address | 7 ]

解释为什么不需要、也不能写 offset 8。

练习 5：共享身份不能被复制成两份

运行：

1
2
3
4
5

./mini run examples/gc_record_identity.lang
./mini compile examples/gc_record_identity.lang -o out.s
c++ out.s gc_runtime.o -o out
./out
echo $?

解释器输出和原生状态都应为：

1

1

这个程序让 item 和 alias 两个不同的 binding cell 保存同一个 record pointer，再进行足以触发多次 GC 的分配，最后比较两者。

选择一次发生在递归 else 路径中、临时 record 分配前的 collection。此时 item 和 alias 的 capture homes 可以已经清零，因为 loop closure 仍然间接保活它们。只追踪与 identity 相关的对象，画出一条可能的 Cheney 顺序：

1
2
3
4
5

forward(root self cell)      -> 复制 loop self cell
scan self cell.value         -> 复制 loop closure
scan closure captures        -> 复用 self cell，复制 item cell 与 alias cell
scan item cell.value         -> 复制共享 record，安装 forwarding
scan alias cell.value        -> 读取 forwarding，复用同一个新地址

回答：如果最后一步又复制一次 record，最终结果会变成什么？更一般地说，若重复复制的是一个被多个 closure 共享的可变 cell，又会造成什么更严重的问题？

练习 6：closure 与 cell 跨 GC 保持共享状态

运行：

1
2
3
4
5
6

./mini run examples/gc_closure_cell.lang
./mini ir examples/gc_closure_cell.lang
./mini compile examples/gc_closure_cell.lang -o out.s
c++ out.s gc_runtime.o -o out
./out
echo $?

解释器输出和原生状态都应为 42。这个程序先创建一个初值为 40 的 counter，再分配大量临时 record，最后调用 counter 加 2。

在 IR 中找出：

1
2
3
4
5

start 参数的 cell
内层 closure 捕获的 start cell
loop closure 捕获的 counter cell
counter 调用中的 check-closure
修改 start cell 的 store

再画对象图：

1

loop closure -> counter binding cell -> counter closure -> start cell -> 40

指出 collector 扫描这条长期存活路径时使用哪两种对象 kind，并解释每轮创建的临时 record 为什么不属于这条路径。

练习 7：record 字段也能把 closure 保活

运行：

1
2
3
4
5
6

./mini run examples/gc_record_closure.lang
./mini ir examples/gc_record_closure.lang
./mini compile examples/gc_record_closure.lang -o out.s
c++ out.s gc_runtime.o -o out
./out
echo $?

解释器输出和原生状态都应为 42。box 是一个一字段 record，字段中保存 closure。临时分配结束以后，程序执行：

1

((get box 0) 40)

按顺序说明：

1. root stack 怎样找到 box 对应的 cell；
2. cell scanner 怎样找到 record；
3. record scanner 怎样找到 closure；
4. closure scanner 为什么跳过 code pointer；
5. get 和 call 最终怎样得到 42。

练习 8：letrec 的环为什么不会困住 collector

几个使用 letrec 的 GC 压力例会包含一个对象环：

1

self cell -> closure -> self cell

选择 gc_stress.lang，画出两种时刻：

1
2

仍有 root 指向 self cell
没有 root 指向这组对象

回答：

1. 第一种情况下，哪一个对象先被转发并不重要，为什么两者最后都会复制？
2. forwarding 在扫描字段前就安装，怎样阻止沿环无限复制？
3. 第二种情况下，为什么纯引用计数可能处理不了这种所有权环，而 tracing GC 仍能整组回收？注意这只是两种回收策略的对比，不是在描述本章 C++ 解释器的 Store 实现。

再运行状态章节留下的验证：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

./mini run examples/recursive_binding_set.lang
./mini run examples/self_param_shadow.lang
./mini compile examples/recursive_binding_set.lang -o recursive.s
c++ recursive.s gc_runtime.o -o recursive
./recursive
echo $?
./mini compile examples/self_param_shadow.lang -o shadow.s
c++ shadow.s gc_runtime.o -o shadow
./shadow
echo $?

两个解释器结果和两个原生状态都应为 42。前者确认语言语义，后者确认换成第九章后端与统一对象协议后，可变 self 和同名参数遮蔽没有回退；这两个小程序本身不保证填满半区，因此不能单独证明发生过 collection。

练习 9：观察 CFG root liveness

先运行三个专门的回归例：

1
2
3

./mini run examples/gc_caller_live.lang
./mini run examples/gc_branch_liveness.lang
./mini run examples/gc_call_liveness.lang

第一个输出 42，后两个输出 300。它们分别检查 call 两侧相反的要求：

• caller-live 示例把二字段 record 留在调用者的 keep 中；churn 不捕获它，却在被调函数里触发多轮 collection，返回后仍要读取 keep；
• branch 示例创建一个 300 字段 record，只在未执行的 then 分支引用它；走 else 后，它在第二次 allocation 前已经死亡；
• call-liveness 示例把一个 300 字段 record 作为未使用的 argument；callee 分配第二个 record 时，caller 不应继续把旧 argument 当作 root。

把三者都走一遍编译路径：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

./mini compile examples/gc_caller_live.lang -o caller.s
c++ caller.s gc_runtime.o -o caller
./caller
echo $?

./mini compile examples/gc_branch_liveness.lang -o branch.s
c++ branch.s gc_runtime.o -o branch
./branch
echo $?

./mini compile examples/gc_call_liveness.lang -o call.s
c++ call.s gc_runtime.o -o call
./call
echo $?

分别生成、链接并运行时，caller-live 的进程状态仍是 42，后两个是 44，也就是 300 mod 256。若 call 前无条件清空 caller roots，keep home 会变回 tagged 0，返回后的 load 将解引用无效值；若按文本最后一次使用清根，或把已消费的 call operands 保留到返回以后，后两个程序会因为假活跃集超过 4 KiB 而错误 abort。

生成压力示例汇编：

1

./mini compile examples/gc_stress.lang -o out.s --target linux

在 out.s 中寻找写入 tagged 0 的指令：

1

movq $1, -offset(%r15)

区分三类用途：

• 进入 root frame 时初始化槽；
• allocation 前清理不属于该操作 live_in 的 root；
• source call 装好寄存器后、真正调用前清理不属于 live_out 的 caller root。

普通操作或 label 附近不一定出现清根，因为这些位置不会自行触发 GC。然后查看递归 call：后端应先把 callee、argument 和 code address 装入寄存器，再在真正的 call 前收紧 roots。

思考下面的控制流：

1
2
3

(if condition
    usex
    usey)

为什么 branch 的 live_out 必须合并两个分支，而不能只看源文件中紧随其后的 then？进入其中一条路径以后，为什么该路径下一次 safepoint 的 live_in 又可以排除另一条路径独有的值？

练习 10：区分语言错误与 GC abort

先验证受控语言错误：

1
2
3
4

./mini compile examples/call_integer_error.lang -o out.s
c++ out.s gc_runtime.o -o out
./out
echo $?

状态应为 70。

再把下面程序保存为 oom.lang：

1
2
3
4
5

(letrec build n
  (if (eq? n 0)
      (record)
      (record n (build (sub1 n))))
  (build 300))

它返回一条仍然可达的 record 链。生成并运行编译结果：

1
2
3

./mini compile oom.lang -o oom.s
c++ oom.s gc_runtime.o -o oom
./oom

随着递归返回，越来越多 record 同时存活；当活跃集无法放入 4096 字节半区时，运行时调用 abort()。终端可能显示 Aborted，不要要求它返回 70。

先计算这条最终存活链的大小：递归基例创建一个 8 字节空 record，其余每层创建一个 24 字节二字段 record，因此 n 层需要：

1

8 + 24 * n

在当前 liveness 协议下，递归所用的 self cell 与 closure 在返回构造 record 链时已经不再属于 caller 的活动 roots，不计入最终链。由 8 + 24 * n <= 4096 可预测最大成功值是 170；把源码分别改成 170 和 171，验证前者成功、后者 abort。直接计算 floor(4096 / 24) 在这里碰巧也得到 170，但它漏掉了基例的 8 字节，不能作为精确推导；collector 真正判断的是“当前 live bytes 加本次请求”能否一起放入半区。

这个练习是 OOM 行为验证，不要求修改 collector 让程序成功。

练习 11：手推一次 Cheney 扫描

给定对象图：

1
2
3
4
5

root A -> record R
root B -> cell C
R.field0 -> C
C.value  -> closure F
F.capture0 -> R

假设 roots 按 A、B 顺序扫描。为每一步记录：

检查点：R、C、F 各复制一次；再次遇到 R 或 C 时读取 forwarding；最终 scan == to_free，环中的所有指针都指向 to-space。

练习 12：给 collector 增加统计计数（选做）

在 src/runtime/gc.cpp 的匿名名字空间加入一个 collection counter，并在 C++ 函数 collect 入口递增。重新运行 make 生成新的 gc_runtime.o，然后在调试器中于程序退出前查看计数；也可以暂时在 collect 中用宿主调试输出打印它。比较：

• record.lang 不应因为对象很小而触发 collection；
• gc_stress.lang 应触发多次 collection；
• gc_live_record.lang 中长期存活的 record 不会让计数停止增长。

这个练习只用于观察，不要改变源语言语法，也不要为它增加正式的 I/O primitive。完成后恢复正常的程序结果协议。