roots：用独立栈保存 GC 的起点

对象搬家以后，旧地址立刻失效。collector 不仅要复制对象，还必须找到程序手中每一份仍会使用的指针，把它们原地改成新地址。

这些位于托管堆外、需要由 GC 检查和更新的 Value，就是 roots。

为什么不扫描机器调用栈

x86-64 的机器栈混合保存很多东西：

1
2
3
4
5

源语言 Value
返回地址
旧的 %rbp
对齐 padding
编译器和 runtime 的临时机器值

只看一个 64 位 word 的比特，有时很难证明它究竟是 tagged Value，还是碰巧长得相似的机器地址。moving collector 若误把普通数据当成指针，不但会错误保留对象，还可能改写本来不该改的 word。

本章选择一条更清楚的边界：机器调用栈继续负责 call、ret 和栈帧；另开一块只保存 tagged Value 的 shadow root stack。

1
2
3
4
5
6

machine stack                 shadow root stack

return address                tagged integer
saved %rbp                    tagged record pointer
saved %r15                    tagged closure pointer
                              tagged cell pointer

collector 只扫描右边，不猜左边。

启动时申请 1 MiB root area

mini_gc_init 除了分配两个半区，还会在 C++ runtime 中申请一块 1 MiB 的 root area：

1
2
3
4
5

root_start = reinterpret_cast<Word*>(
    allocate_bytes(kRootStackBytes));
mini_gc_root_end =
    root_start + kRootStackBytes / mini::kWordSize;
return root_start;

root_start 只由 collector 内部扫描；mini_gc_root_end 则通过 C ABI 导出，让生成代码能在写 root frame 以前检查边界。初始化函数返回 root area 的起始地址。Linux 目标的 main 调用后会从 %rax 把它放进 %r15：

1
2

call mini_gc_init
movq %rax, %r15

macOS 的外部符号写作 _mini_gc_init。两种目标调用的仍是同一个 C++ 函数，不是两份 collector。

从这以后，在生成的用户函数中，%r15 始终表示 shadow root stack 的第一个空地址，也就是 root_top：

1
2
3
4
5
6

root_start                                      root_top = %r15
    |                                                  |
    v                                                  v
    +--------------------------------------------------+--------------+
    | 当前所有生成函数仍在使用的 fixed root homes     | 尚未使用     |
    +--------------------------------------------------+--------------+

System V ABI 把 %r15 归为 callee-saved register。每个生成函数仍会主动保存旧 %r15，进入时为自己的 root frame 向上扩展，返回时再恢复；这样嵌套函数调用的 root frames 会像机器栈帧一样成对进入和退出，却不会与返回地址混在一起。

每个 IR local 都有固定 root home

本章还没有进行类型证明。一个 IR local 今天保存整数，换一段源程序就可能保存 record、closure 或 cell。为了保持规则统一，emitter 给这些位置都安排 8 字节 root home：

• 函数参数；
• letrec 的 self cell；
• 普通 captures；
• 所有有结果的 IR op。

这些 home 在本函数内固定，不复用，也不搬进普通寄存器。第十章才会用表示分析、冲突图和寄存器分配减少这种保守做法。

gc_stress.lang 的递归函数需要 152 字节 root frame。函数入口的实际汇编开头是：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

pushq %rbp
movq %rsp, %rbp
subq $16, %rsp
movq %r15, -8(%rbp)
leaq 152(%r15), %rax
cmpq mini_gc_root_end(%rip), %rax
ja .Lmini_gc_abort
movq %rax, %r15
movq $1, -8(%r15)
movq $1, -16(%r15)
# 其余 root slots 同样初始化

旧 root top 暂存在机器栈的 -8(%rbp)。新 top 不能越过 C ABI 变量 mini_gc_root_end。越界时跳到生成汇编内部的 .Lmini_gc_abort 小入口；它只负责调用 C++ runtime 导出的 mini_gc_abort()。返回时：

1
2
3

movq -8(%rbp), %r15
leave
retq

恢复旧 top 就等于一次性弹掉整个 root frame，不必逐槽清理已经离开的函数。

第一次 safepoint 前必须写入 tagged 0

root frame 刚扩展时，里面是未初始化的宿主内存。collector 不能扫描任意比特，所以 emitter 在第一次可能触发 GC 以前，把每个 slot 初始化成源语言整数 0：

1

tagged 0 = 0 * 8 + 1 = 1

这就是入口处反复出现 movq $1, ...(%r15) 的原因。它不是把 root 设成 raw null pointer，而是放入一个合法、确定不是堆指针的 tagged Value。

随后函数把入口值写进自己的 home。压力程序的递归函数会先保存 %rsi 中的 tagged argument，再从 %rdi 的 tagged closure 中取出 self cell：

1
2
3
4
5

movq %rsi, -16(%r15)
movq %rdi, %rax
andq $-8, %rax
movq 16(%rax), %rcx
movq %rcx, -8(%r15)

这几行都不分配，所以可以短暂使用 %rax、%rcx 中的 raw address。参数和需要的 captures 进入 root homes 以后，函数才调用 mini_alloc 为参数创建 cell。

safepoint 是“地址可能变化”的位置

本章有两类 safepoint：

1. 直接调用 mini_alloc；
2. 调用源语言 closure，因为被调函数可能继续分配。

safepoint 前后最重要的不变量是：

任何之后仍会使用、而且可能是堆引用的 Value，都必须存在于 [root_start, root_top) 的 root home 中。

mini_alloc 的 %rsi 参数正是当前 %r15。慢路径触发 collection 时，C++ runtime 从内部保存的 root_start 扫到这个 top，对每个 slot 执行 forward，并把返回的新 Value 写回原 slot。

所以分配后不能继续相信 safepoint 前的 heap pointer 寄存器副本。正确顺序是：

1
2
3

把仍活跃的 Value 放在 root home
call mini_alloc
从 root home 重新读取可能已经更新的 Value

创建八字段 record 时，八个字段已经分别在 root homes 中。若分配触发 GC，emitter 会在返回后从这些 homes 读取最新地址，再填入新对象。

普通函数 call 也必须保住 callee 和 argument

间接调用前，callee 和 argument 本来就有固定 root homes。emitter 先把它们复制到调用约定使用的寄存器。压力程序递归调用 loop 时，当前生成结果的关键部分是：

1
2
3
4
5
6
7
8
9

movq -128(%r15), %rdi
movq %rdi, %rcx
andq $-8, %rcx
movq 8(%rcx), %r11
movq -144(%r15), %rsi
movq $1, -8(%r15)
movq $1, -16(%r15)
# 其余不在 live_out 中的 caller root slots 同样清零
call *%r11

%rcx 中清 tag 后的是 closure 的 raw address，offset 8 处取出的 raw code pointer 放在 %r11。二者都只活到紧随其后的 call，中间没有分配。

寄存器装载完成后，emitter 会按 call 的 live_out 收紧整个 caller root frame：调用返回后不再需要的 homes 都清成 tagged 0，需要跨越 call 的 homes 则继续保留。callee 或 argument 若不在 live_out 中，它们自己的 caller homes 也可以清掉，因为这段清理与 call 之间没有另一个 safepoint，寄存器中的实参仍然有效。

被调函数进入后，会先扩展自己的 root frame，把 %rsi 的 argument 和 %rdi closure 中需要的 self/captures 存进去，然后才允许第一次分配。这样即使参数 cell 的分配立即触发 collection，调用所需的对象也已经进入可扫描区域。

这条约束允许 heap pointer 暂时进入 %rax、%rcx 等 scratch register，但不允许未被 root home 保护的指针跨越 allocation 或普通函数 call。第十章只会把确定为整数的值交给寄存器分配；可能是堆指针的值仍保守地放在 root slot。若还想让 heap pointer 跨 safepoint 长期待在普通寄存器，就需要额外的精确 register root map，本书不做。

固定 home 不等于永远活着

给一个 IR local 分配 root home，只说明它可能在函数的某段路径上有用，不代表 collector 应该在整个函数期间一直保留它。

压力程序中的临时 record 正好说明区别：record op 把结果写入一个固定 home，但 begin 会丢弃这个结果。若 slot 一直保留旧指针，120 个本应成为垃圾的 record 反而都会被 root 强行留住，最终造成假 OOM。

控制流让这个问题不能只靠 Markdown 中从上到下的“最后一次出现”判断。then 分支里的清理指令在 else 路径上根本不会执行；反过来也一样。因此 emitter 对结构化 IR 做一轮轻量 CFG root-liveness。

这里 uses 是一条 op 读取的 locals，defs 是它写入的目标，successors 是执行完以后可能到达的下一条 op。live_in 表示执行该 op 以前仍需要的 locals，live_out 表示执行以后仍需要的 locals：

1
2

live_out(op) = 所有后继 live_in 的并集
live_in(op)  = uses(op) ∪ (live_out(op) - defs(op))

普通 op 的后继是下一条；jump 的后继是目标 label；branch 的两个后继分别是 then 和 else，必须取并集。分析从后向前迭代，直到各点的集合不再变化。

这轮分析会沿 CFG 区分不同后继，并在控制流汇合处保守地取并集；但不必在每条普通 op 或每个 label 旁都插入清理。对象只会在 safepoint 搬家，所以 emitter 只在两类 safepoint 前收紧 roots：

• allocation 类 op 调用 mini_alloc 前，只保留该 op 的 live_in，其余 fixed homes 清成 tagged 0；
• source call 先把 closure、argument 和 raw code address 装进寄存器，再只保留 call 的 live_out，然后执行间接调用。

第一条保住了构造对象所需的 fields、captures 或初始值，同时清掉即将被目标覆盖的旧指针。第二条保住所有需要跨越 callee 的 caller 值，却不会让已经装进调用寄存器、返回后无用的 operand 在 callee 执行期间继续误保活。

两个 safepoint 之间，即使一个 dead home 暂时还留着旧 tagged pointer，也不会触发 collection，因此不影响正确性；到下一处可能扫描 root stack 以前，它一定会按对应的 live set 清理。这比在每条普通指令后写清零代码更小，也把规则集中在真正会改变地址的位置。

清 root 的机器动作很小：

1

movq $1, dead_home

这轮分析只回答“到这个 safepoint 时，哪个 fixed home 必须算 root”。它不让两个 local 共用 slot，不构建冲突图，也不分配寄存器；因此它仍属于 GC 的 root 生命周期管理，而不是提前讲第十章。

先用三个例子确认解释器语义：

1
2
3

./mini run examples/gc_live_record.lang
./mini run examples/gc_closure_cell.lang
./mini run examples/gc_caller_live.lang

三个程序都输出 42。再按本章前面的流程逐一执行 mini compile，用 c++ 把汇编和 gc_runtime.o 链接起来并运行，三个进程状态也都应为 42；只有这条编译路径实际运行本章的 root stack 与 collector。

第一个程序让递归 closure 捕获活 record，第二个让 closure 与共享 cell 跨越大量 safepoints，第三个则把活 record 只留在调用者 frame 中，被调函数不捕获它，却会触发多轮 collection。三份原生结果分别检查不同的可达路径；与此同时，大批临时 record 会在离开 live set 后停止充当 roots。