forwarding 与 Cheney：搬一次，更新每一条边

找到可达对象以后，collector 要把它们搬到 to-space。这里马上出现两个问题：

1. 同一个对象可能被多个 root 或字段引用，不能复制成多份；
2. 对象可能组成环，不能沿边递归到永远。

forwarding 为每个已经搬过的旧对象留下“新家地址”，同时解决这两个问题。

共享对象只能复制一次

gc_record_identity.lang 让两个变量共享同一个 record：

1
2
3
4
5
6
7
8
9

(let item (record 40 2)
  (let alias item
    (letrec loop n
      (if (eq? n 0)
          (eq? item alias)
          (begin
            (record n n n n n n n n)
            (loop (sub1 n))))
      (loop 100))))

解释执行：

1

./mini run examples/gc_record_identity.lang

输出是 1。item 和 alias 不是两个字段相同的 record，而是同一个对象的两个引用。

由于所有词法绑定都装进 cell，这段程序中 item cell 和 alias cell 是两个不同节点，但它们的 current Value 指向同一个旧 record。更一般地说，同一个对象可以同时被 root slot、record 字段、closure capture 或 cell value 引用。若 collector 每遇到一条入边就复制一次，会得到：

1
2

item cell.value  ----> new copy A
alias cell.value ----> new copy B

对象身份被拆成两份，GC 后的 eq? 就会错误变成 0。正确结果必须是：

1
2
3

item cell.value  --+
                   +----> one new copy
alias cell.value --+

一个 word 就能保存 forwarding 地址

所有对象起点都按 8 字节对齐，所以 raw address 的低三位一定是 000。第一次复制对象以后，runtime 把旧对象的 header 改写为：

1

forwarding word = new_raw_address | 7

7 的低三位是 111。普通 header 的 kind 只有 1、2、3，所以 collector 可以先看旧 header 的低三位来区分：

1
2

header & 7 != 7    还没有搬过
header & 7 == 7    已经搬过，header 本身就是 forwarding word

第一次搬运结束时，C++ runtime 会先复制对象、推进 to_free，再改写旧 header：

1
2
3
4
5
6
7

Byte* destination = to_free;
std::memcpy(destination, object, bytes);
to_free += bytes;

object[0] = address(destination) | kForwardingTag;
return address(destination) |
       static_cast<Word>(mini::kHeapObjectTag);

这里 object 指向旧 raw address，destination 是新 raw address。写回旧 offset 0 的是 new_raw | 7，返回给程序的则是正常 heap Value new_raw | 4。

第二次遇到同一个旧对象时，不再复制，只需：

1
2

new_raw = forwarding_word & -8
return new_raw | 4

marker 7 只是 collector 写在旧半区的内部状态。半区交换后，这些旧内容不再属于任何可达对象，并会在下一轮复制时被覆盖。它不是第四种源语言 tag，不是 HeapKind，也不会作为普通 Value 交给程序。

为什么不能把新地址写在 offset 8

一种看似直观的方案是：旧 offset 0 写“已转发”，旧 offset 8 保存新地址。它对非空对象似乎可行，却会破坏第六章已经支持的空 record：

1
2
3
4

(record)

offset 0    header
total       8 bytes

空 record 根本没有 offset 8。往那里写会覆盖紧邻对象的 header。

单 word 的 new_raw | 7 只覆盖对象本来就有的 header，因此 payload count 为 0 时也成立。gc_empty_record.lang 专门让空 record 跨越多轮 collection：

1
2
3
4

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

在 Apple Silicon Mac 上使用 c++ -arch x86_64 out.s gc_runtime.o -o out。链接运行后的退出状态仍是 42，说明 header-only 对象既能复制，也能从 forwarding word 找回同一新地址。

forward 的完整职责

forward 是 gc.cpp 内部的普通 C++ 函数：它接收 tagged Word，返回更新后的 tagged Word。逻辑可以写成：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

forward(value):
    if value 的 tag 不是 4:
        return value

    old_raw = value & -8
    if old_raw 不在当前 from-space 已分配范围内:
        return value

    word = old_raw[0]
    if (word & 7) == 7:
        return (word & -8) | 4

    从 header 算出对象大小并检查 kind、边界
    new_raw = to_free
    把整个对象复制到 new_raw
    to_free += object_size
    old_raw[0] = new_raw | 7
    return new_raw | 4

tag 检查让整数直接原样返回；from-space 范围检查则让已经指向 to-space 的新 Value 原样返回。实现还会验证 header kind、payload count、旧对象边界和 to-space 容量，发现损坏的不变量就 abort，而不是继续越界复制。

注意顺序：对象复制完便立即安装 forwarding word，之后才会扫描新副本里的字段。这个“先登记新家，再沿边继续走”的顺序正是处理环的关键。

closure 与 self cell 的环怎样停下来

回到 letrec 的对象图：

1
2
3

closure ------> self cell
   ^                |
   +----------------+

假设 root 首先指向旧 closure：

1. forward(old closure) 在 to-space 复制 closure，并在旧 closure header 安装 forwarding word；
2. 稍后扫描新 closure 的 capture，遇到旧 self cell；
3. forward(old cell) 复制 cell，并在旧 cell header 安装 forwarding word；
4. 扫描新 cell 的 current Value，再次遇到旧 closure；
5. 旧 closure 已有 forwarding word，直接返回步骤 1 的新地址。

没有第三份对象，也没有无限递归。若外部没有 root 指向这个环，步骤 1 根本不会开始，closure 和 cell 都留在旧半区，交换后一起成为垃圾。

roots 只找到第一层，还要继续扫描新对象

把每个 root 执行一次 forward，只能保证 root 直接指向的对象被复制。假设：

1

root -> record -> closure -> cell -> record

后面几层仍藏在刚复制的对象字段里。collector 需要一个待处理队列。

Cheney 算法不额外申请队列，而是直接把 to-space 的已复制区当作队列，用两个地址管理：

1
2
3
4
5
6

to_start             scan                     to_free              to_end
   |                   |                          |                    |
   v                   v                          v                    v
   +-------------------+--------------------------+--------------------+
   | 已扫描对象        | 已复制、尚未扫描对象     | 未使用             |
   +-------------------+--------------------------+--------------------+

• free，也就是 C++ runtime 中的 to_free，指向下一个新副本要写入的位置；
• scan 从 to_start 开始，指向下一个需要检查内部边的对象。

Cheney collection 的两个阶段

第一阶段先转发全部 roots，并原地更新 shadow root slots：

1
2
3
4

to_free = to_start

for slot in [root_start, root_top):
    slot = forward(slot)

当前 C++ runtime 的循环正是：

1
2
3

for (Word* root = root_start; root != root_top; ++root) {
    *root = forward(*root);
}

第二阶段扫描 to-space：

1
2
3
4
5
6
7
8

scan = to_start

while scan < to_free:
    读取 scan[0] 的 header
    按 kind 找到需要扫描的 Value slots
    for each slot:
        slot = forward(slot)
    scan += object_size

forward 一个字段时可能在 free 处追加新对象，所以循环过程中 to_free 会继续向右增长。只要 scan < to_free，就还有已经发现但尚未检查的对象；当二者相等，整张可达对象图才扫描完。

runtime 按 kind 选择边：

1
2
3

record    offset 8 起，扫描 payload_count 个字段
closure   跳过 offset 8 code pointer，扫描 payload_count - 1 个 captures
cell      只扫描 offset 8 的一个 Value

closure 的 code pointer 仍会随整个对象逐字复制，但绝不会传给 forward。它是对象内容，不是对象图的边。

扫描结束后交换角色

当 scan == to_free，to-space 已经包含所有且仅包含可达对象，而且 roots 与对象内部的边都已改成新地址。运行时交换两块区域的角色：

1
2

old to-space    -> new from-space，继续从 live objects 末尾分配
old from-space  -> new to-space，下一轮 collection 时覆盖

旧 from-space 不需要逐对象 free，也不需要把每个垃圾对象清零。没有复制的对象自然留在即将重用的整个半区里；这正是 copying collector 能把回收动作保持简单的原因。

最后可以一起检查共享、环和跨对象边：

1
2
3

./mini run examples/gc_record_identity.lang
./mini run examples/gc_closure_cell.lang
./mini run examples/gc_record_closure.lang

输出依次是 1、42、42。解释器给出预期语义；把同样的文件编译、链接后，进程退出状态应得到相同整数。压力分配迫使编译路径多次搬家，而 forwarding 与 Cheney 扫描保证对象身份、共享状态和 closure code address 都没有被破坏。