第九章：垃圾回收

本节阅读量:

第六章把 record 放到堆上，第七章加入 closure，第八章又用 cell 表示可变位置。到上一章为止，编译后的程序每次创建这些对象都调用 malloc，却从不主动释放。

短程序看不出问题。程序运行得足够久以后，即使某个对象已经再也找不到，它占用的内存也不会回来。

第九章不增加源语言语法，也不改变已有表达式的结果。我们只替换编译后程序的内存管理方式：

1
2


第八章   每个对象单独 malloc，不回收
第九章   从托管堆分配，只保留仍然可达的对象

本章会实现一个小型的 Cheney copying collector。名字暂时不必记，先看它需要解决的实际问题。

一个确定会触发 GC 的程序

examples/gc_stress.lang 是本章的第一条完整测试：

1
2
3
4
5
6
7


(letrec loop n
  (if (eq? n 0)
      42
      (begin
        (record n n n n n n n n)
        (loop (sub1 n))))
  (loop 120))

每次递归都会创建一个八字段 record，然后立即把它丢掉。这个 record 占：

1

1 个 header + 8 个字段 = 9 words = 72 bytes

函数的参数仍按第八章的统一装箱策略放在 16 字节 cell 中。整个程序累计分配大约是：

1
2
3
4


self cell 和递归 closure       40 bytes
121 个参数 cell              1936 bytes
120 个临时 record            8640 bytes
合计                         10616 bytes

本章正在使用的一个半区只有 4096 字节，因此这段程序不可能靠“一直向后分配”运行到底。另一方面，临时 record 在下一次递归前已经无用；真正同时活着的对象仍能放进一个半区。程序若最终得到 42，中途就一定回收并复用了空间。

这里刻意没有简单地把递归次数改得极大。第五章没有实现尾调用优化，递归越深，机器调用栈仍会不断增长；本章的 CFG root-liveness 虽会在递归 call 前清掉 caller 中已经无用的参数 cell，但没有把机器调用本身变成跳转。压力测试只需让“累计分配量超过半区很多”，同时让“某一刻仍然活着的对象量有界”，不必顺手把机器栈深度也变成测试变量。

先走解释器路径

构建并解释执行：

1
2
3


cd code/09_gc
make
./mini run examples/gc_stress.lang

输出：

1

42

这一步只是在确认语言语义。run 使用 C++ 解释器中的 Env、Store 和宿主对象，它不会运行本章的 copying collector。解释器告诉我们“程序应该算出什么”，随后编译路径再验证“自己管理内存时仍能算对”。

两条路径的分工是：

1
2
3
4
5


source -> AST -> interpreter ------------------------------> 42
          |
          +-> structured IR -> out.s -----------+
                                                  +-> native program -> exit 42
C++ GC runtime source -> gc_runtime.o -----------+

看看没有变化的 IR

GC 不需要新 AST 节点，也不需要新源语言表达式。cell、closure 和 record 仍然使用第八章已经建立的结构化 IR：

1

./mini ir examples/gc_stress.lang

开头的实际输出是：

1
2
3
4
5
6
7


loop0.cell = cell 0
f.0 = closure lambda0 [loop0.cell]
store loop0.cell f.0
t.16 = load loop0.cell
check-closure t.16
t.17 = call t.16 120
return t.17

函数体中仍能看到八字段 record：

1

t.11 = record t.3 t.4 t.5 t.6 t.7 t.8 t.9 t.10

变化发生在 IR 之后：汇编 emitter 不再为 cell、closure 和 record 生成 call malloc，而是生成对 C ABI 函数 mini_alloc 的调用。真正的分配器和 collector 位于 src/runtime/gc.cpp，由 C++ 编译成 gc_runtime.o。

编译并运行托管堆版本

刚才的 make 同时生成了语言工具 mini 和目标程序需要的 gc_runtime.o。在 Linux、WSL 或 Intel Mac 上：

1
2
3
4


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

Apple Silicon Mac 需要让系统编译器链接 x86-64 程序：

1
2
3
4


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

编译后的程序不会打印计算结果，所以 ./out 本身不会显示 42；最后的 echo $? 才会显示进程退出状态：

1

42

compile 仍然只输出 x86-64 System V ABI 的 AT&T 汇编，也不会替读者链接。与前八章不同，out.s 从这一章开始不是单文件程序：它声明并调用 mini_gc_init、mini_alloc 等外部符号，链接时必须带上同一章构建出的 gc_runtime.o。这里使用 c++ 驱动链接，是因为这个 object 来自 C++ 源文件。

这一章要回答什么

我们会沿着一条连续路线前进：

先把 record、closure 和 cell 画成对象图，定义“可达”；
再把 malloc 换成两个固定半区中的快速顺序分配；
建立独立的 shadow root stack，让 GC 知道从哪里开始找；
用 forwarding 处理共享引用、对象身份和环；
用 scan、free 两个指针完成 Cheney copying collection；
最后通过一组很小的 C ABI，把生成汇编与 C++ runtime 链接起来。

核心问题可以压缩成三句话：

1
2
3


从 roots 出发，哪些对象还能走到？
对象搬家以后，所有旧指针怎样改成新指针？
已经走不到的对象，怎样整批丢弃？

这不是工业级 GC。本章只做单线程、固定大小、stop-the-world 的双半区 collector，不做堆增长、分代、并发、增量回收、finalizer 或 weak reference。小实现的价值在于：所有关键步骤都能在一章内看清楚，并且能真实运行闭包、record、共享可变状态和递归对象环。

8.7 常见错误与练习

9.1 对象图：从“还拿得到”定义活对象

本节目录