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

GC 面对的第一个问题不是“怎样释放”，而是“哪些对象已经不能释放”。

考虑 gc_live_record.lang 的外层结构：

1
2
3
4
5
6
7
8

(let keep (record 40 2)
  (letrec loop n
    (if (eq? n 0)
        (+ (get keep 0) (get keep 1))
        (begin
          (record n n n n n n n n)
          (loop (sub1 n))))
    (loop 100)))

keep 指向的 record 在许多次分配以后还要读取，所以它必须保留。循环中创建的八字段 record 没有保存到任何地方，下一步递归开始后就再也拿不到，可以回收。

“以后还会不会读”很难直接从机器代码猜出来。GC 使用一个更机械的定义：

如果从 root 出发，沿着堆对象里的引用能够到达某个对象，这个对象就是可达的，也就是本次 collection 必须保留的对象。

root 是堆外由程序直接持有的起点。本章会把它们放进独立的 shadow root stack；这一节先把 root 画成一个方框：

1
2
3
4
5
6
7

root slot
   |
   v
 keep cell ------> record
                     |
                     +--> integer 40
                     +--> integer 2

整数不是堆对象，扫描到这里就停止。若另一个 record 字段保存 closure，或者 closure 捕获 cell，图就会继续向后延伸。

节点和边来自已有的三类对象

第九章没有增加新的源语言 Value。堆上的节点仍然只有第六至第八章逐步加入的三类对象：

• record：每个字段都可能保存另一个堆对象；
• closure：每个 capture 都可能保存另一个堆对象；
• cell：当前值可能是整数、record 或 closure。

它们组成对象图时，真正需要跟随的边是：

cell 仍是编译器表示“位置”的内部对象，不是源语言新增的可构造 Value。GC 能识别 cell，是因为编译器在堆上创建了它；读者不能在源程序里写 (cell ...)。

解释器不运行这套机器 collector，但它提供同一幅语义图：Env 中的名字指向 Store 的 Location，closure 保存自由变量的 Location，record 字段保存 Value。编译路径只是把 Location 落成真实 cell，并把对象之间的关系变成内存里的 tagged pointer。

所有堆指针继续共用 tag 4

第八章已经确定统一的机器表示，本章不会为了 GC 改回三套 pointer tag：

1
2

integer       low tag = 1
heap object   low tag = 4

因此一个堆 Value 的形式始终是：

1

tagged heap Value = aligned raw object address | 4

低三位只回答“这是不是堆对象”。要判断它是 record、closure 还是 cell，collector 会清除 pointer tag，再读取 offset 0 的 header。

runtime/value.h 中的种类保持：

1
2
3
4
5

enum class HeapKind : long {
    record = 1,
    closure = 2,
    cell = 3,
};

header 的公式也没有变化：

1

header = (payload_count << 8) | kind

低 8 位是 kind，其余高位是 payload word 数。collector 既用 kind 决定“哪些槽是边”，也用 payload count 算出对象占多少字节：

1

object size = 8 * (1 + payload_count)

统一 tag 很重要。record? 不能只看低三位，否则 closure 和 cell 也会被误认成 record；它与 GC 一样，要继续检查 header kind。

record：所有 payload 都是 Value

一个 N 字段 record 的布局是：

1
2
3
4
5

offset 0       header: kind=1, payload_count=N
offset 8       field 0
offset 16      field 1
...
offset 8*N     field N-1

每个字段都是完整的 tagged Value，所以 collector 从 offset 8 开始扫描 N 个 word。

空 record (record) 也是真实对象：

1
2

offset 0       header: kind=1, payload_count=0
total          8 bytes

它是对象图中的一个节点，只是没有向外的边。这个只有一个 word 的布局会直接约束后面的 forwarding 设计：GC 不能假设旧对象一定有 offset 8 可以借用。

gc_empty_record.lang 的编译版本会让一个空 record 活着跨过多轮 collection，最后用 size 验证它仍然完好。先用解释器确认预期结果：

1

./mini run examples/gc_empty_record.lang

输出是 42。

closure：code pointer 不是对象图的边

一个捕获 C 个值的 closure 使用：

1
2
3
4
5

offset 0       header: kind=2, payload_count=1+C
offset 8       raw code pointer
offset 16      capture 0
offset 24      capture 1
...

header 的 payload count 包含 code pointer，因为它决定整个对象的大小。但是 offset 8 保存的是 .Llambda0 之类的机器代码地址，不是源语言 tagged Value，也不指向托管堆。

所以 closure 的扫描规则必须分成两部分：

1
2

对象大小     1 个 code word + C 个 capture words
GC 边        只扫描 offset 16 起的 C 个 captures

code pointer 不属于托管堆，collector 不能把它当作对象图中的 Value 边；若错误改写，closure 下次调用时就会跳到错误地址。gc_record_closure.lang 从另一方向验证对象图：一个 record 保存 closure，编译版本经历大量分配后再取出并调用它。

1

./mini run examples/gc_record_closure.lang

输出是 42。

cell：唯一 payload 是一条边

cell 的布局仍是第八章确定的 16 字节：

1
2

offset 0       header: kind=3, payload_count=1
offset 8       current tagged Value

collector 必须扫描 offset 8。否则 closure 捕获的共享状态可能还在，cell 当前保存的 record 或 closure 却会被错误丢弃。

gc_closure_cell.lang 中，返回的 counter closure 捕获并修改 start 的 cell；程序先制造大量垃圾，最后调用 counter。结果仍为 42，说明 closure 到 cell 的边以及 cell 中的 Value 都被正确更新。

letrec 天然形成 closure 和 cell 的环

查看压力程序 IR 的前三行：

1
2
3

loop0.cell = cell 0
f.0 = closure lambda0 [loop0.cell]
store loop0.cell f.0

第二行让 closure 捕获 self cell，第三行又让 self cell 保存 closure：

1
2
3
4
5

          capture 0
closure ------------> self cell
   ^                      |
   |______________________|
          current Value

这不是错误，而是可变递归绑定的真实表示。

引用计数看到这个环时，即使外部 root 已经消失，两个对象的计数也可能都不为零。copying collector 不靠局部计数判断生死：

• 若某个 root 仍能到达环，就复制整张可达子图；
• 若没有 root 能到达环，就一个对象也不复制，旧半区稍后整体丢弃。

因此“有没有环”不是问题，“能不能从 root 到达”才是本章统一的生死标准。后面的 forwarding 会保证遍历这个环时不会无限循环，也不会把同一对象复制多份。