当我们谈论垃圾回收器的实现时，Baby's First Garbage Collector 往往被视为入门起点。这个实现足够简单，能够正确回收垃圾，但它存在一个致命缺陷：无法正确处理那些「逃离」 Lisp 栈的对象。在动态语言的运行时中，当对象从 Lisp 栈逃逸到本机栈时，精确式 GC 会错误地将其判定为垃圾并回收，这直接导致程序崩溃。本文将深入探讨如何将一个精确式 GC 演进为保守式 GC，实现对本机栈和寄存器的根扫描，从而彻底解决对象误回收问题。

从精确到保守：演进的核心动机

精确式垃圾回收器的核心优势在于它完全掌握对象的分布位置。它维护着一个对象列表，能够实时监控每一个对象的生命周期。当对象从栈上弹出时，精确式 GC 能够在瞬间感知并将其标记为可回收。然而，这种「全知全能」的能力恰恰也是它的阿喀琉斯之踵 —— 它只能追踪自己「管辖」范围内的对象，一旦对象跨越到它的视野之外，比如进入本机栈或寄存器，这些对象就会被错误地判定为不可达。

问题的本质在于动态语言运行时与底层系统之间的边界。在 Lisp 解释器执行过程中，本机代码与 Lisp 代码会交替运行。当 Lisp 值被传递给本机函数时，它们实际上已经从 Lisp 栈迁移到了本机栈。对于精确式 GC 而言，这些对象就像凭空消失了一样。下次垃圾回收时，它会慷慨地「帮助」这些对象提前结束生命，结果就是程序在后续使用这些已回收对象时发生难以调试的崩溃。

保守式 GC 的设计哲学截然不同。它不假设自己知道所有对象的准确位置，而是采取一种更为「保守」的态度：只要某个内存位置可能指向堆中的对象，就将其视为根。这种策略虽然可能造成一些「假阳性」—— 将已死亡的对象误标记为存活 —— 但它永远不会漏掉存活的对象，从而保证了程序的安全性。

本机栈扫描：找到逃逸的对象

实现保守式 GC 的第一步是能够扫描本机栈。关键在于我们需要在垃圾回收发生时，获取当前的本机栈指针范围，然后遍历这个范围内的所有内存位置，检查它们是否指向堆中的对象。

在 C 语言中，我们可以使用 __builtin_frame_address(0) 获取当前函数的帧地址。这个内置函数返回一个指向当前栈帧的指针，配合栈顶指针就可以确定整个栈的范围。代码实现如下：

long lone(int argc, char **argv, char **envp, struct lone_auxiliary_vector *auxv)
{
    void *stack = __builtin_frame_address(0);
    /* interpreter runs... */
    return 0;
}

获取栈指针后，我们需要遍历栈上的每个机器字，检查它是否是指向堆的指针。这里有一个重要的优化：对象在堆中是连续排列的，我们不需要逐个比较每个指针，而是检查它是否落在某个堆块的地址范围内。

static void lone_lisp_mark_native_stack_roots_in_range(struct lone_lisp *lone, void *bottom, void *top)
{
    void *tmp, **pointer;
    if (top < bottom) {
        tmp = bottom;
        bottom = top;
        top = tmp;
    }
    for (pointer = bottom; pointer < top; ++pointer) {
        if (lone_lisp_points_to_heap(lone, *pointer)) {
            lone_lisp_mark_heap_value(lone, *pointer);
        }
    }
}

这个实现中有一个细节值得注意：我们需要处理栈可能向下增长的情况，因此要先比较 bottom 和 top，确保循环方向的正确性。扫描过程中，对于每个可能指向堆的指针，我们调用标记函数将其标记为可达。

为了高效地判断某个指针是否指向堆，我们维护了一个堆链表。每个堆结构包含一组连续排列的值对象。判断操作只需要遍历这个链表，检查指针是否落在某个堆的值数组范围内：

static bool lone_lisp_points_to_heap(struct lone_lisp *lone, void *pointer)
{
    struct lone_lisp_heap *heap;
    for (heap = lone->heaps; heap; heap = heap->next) {
        if (lone_points_within_range(pointer, heap->values, 
            heap->values + LONE_LISP_HEAP_VALUE_COUNT)) {
            return true;
        }
    }
    return false;
}

这种保守式扫描策略不可避免地会带来一些性能开销，因为栈上可能存在一些看起来像指针的数值，但实际上它们只是普通的整数数据。不过，只要我们足够保守，就不会漏掉任何真正的存活对象，这比偶尔误回收一个对象要好得多。

寄存器溢出：处理 CPU 状态的隐藏对象

如果说本机栈扫描已经解决了大部分问题，那么寄存器就是最后一个盲区。当垃圾回收被触发时，CPU 寄存器中可能仍然保存着对堆对象的引用。这些引用在栈上根本找不到，因为它们从未被写入内存。传统的手工扫描寄存器是不现实的 —— 寄存器的数量和布局因架构而异，而且我们很难在任意时刻获取完整的寄存器快照。

幸运的是，Unix 系统提供了一个现成的解决方案：setjmp/longjmp。这对函数原本用于非本地跳转，但它们的实现机制恰好可以为我们所用。setjmp 会将当前的寄存器状态（包括栈指针、程序计数器和其他关键寄存器）保存到一个 jmp_buf 结构中。我们可以利用这个特性来获取完整的寄存器快照。

Boehm GC（最著名的保守式 GC 实现之一）就采用了这种技术。它的实现方式是先清空 jmp_buf，然后调用 setjmp，这样就能确保我们获得一个干净的寄存器状态。随后，我们只需要扫描这个 jmp_buf 中的内容，找出所有指向堆的指针即可。

具体到汇编层面，我们需要为不同的 CPU 架构编写寄存器保存函数。以 x86_64 为例，需要保存 16 个通用寄存器的值：

typedef long lone_registers[16];
extern void lone_save_registers(lone_registers);

__asm__
(
    ".global lone_save_registers"            "\n"
    ".type lone_save_registers,@function"    "\n"
    "lone_save_registers:"                   "\n" // rdi = &lone_registers
    "mov %rax,   0(%rdi)"                    "\n"
    "mov %rbx,   8(%rdi)"                    "\n"
    "mov %rcx,  16(%rdi)"                    "\n"
    /* ... */
    "mov %r13, 104(%rdi)"                    "\n"
    "mov %r14, 112(%rdi)"                    "\n"
    "mov %r15, 120(%rdi)"                    "\n"
    "ret"                                    "\n"
);

对于 aarch64 架构，情况稍有不同。这个 64 位架构提供了近两倍于 x86_64 的通用寄存器（31 个），因此我们需要保存更多的状态：

typedef long lone_registers[31];
extern void lone_save_registers(lone_registers);

__asm__
(
    ".global lone_save_registers"            "\n"
    ".type lone_save_registers,@function"    "\n"
    "lone_save_registers:"                   "\n" // x0 = &lone_registers
    "stp x0,  x1,  [x0, #0  ]"               "\n"
    "stp x2,  x3,  [x0, #16 ]"               "\n"
    /* ... */
    "stp x28, x29, [x0, #224]"               "\n"
    "str x30,      [x0, #240]"               "\n"
    "ret"                                    "\n"
);

在垃圾回收的标记阶段，我们只需要调用这个寄存器保存函数，然后像扫描栈一样扫描返回的寄存器数组：

static void lone_lisp_mark_all_reachable_values(struct lone_lisp *lone, 
    struct lone_lisp_machine *machine)
{
    lone_registers registers;
    lone_save_registers(registers);
    /* precise roots */
    lone_lisp_mark_known_roots(lone);
    lone_lisp_mark_lisp_stack_roots(lone, machine);
    /* conservative roots */
    lone_lisp_mark_native_stack_roots(lone);
}

这种实现既保留了精确式 GC 对已知根的高效处理能力，又通过保守式扫描弥补了对本机栈和寄存器的盲区。测试结果表明，经过这番改造后，解释器的测试套件能够完全通过，再也没有出现对象被错误回收导致的崩溃。

工程实践中的权衡与优化

将精确式 GC 演进为保守式 GC 并非没有代价。最主要的开销来自于对本机栈和寄存器的全面扫描。在极端情况下，这种扫描可能导致 GC 暂停时间显著增加，尤其是当栈深度很大时。然而，相比于程序崩溃的风险，这种开销是完全可接受的。

另一个值得关注的点是假阳性问题。由于我们无法区分栈上的数值是真正的指针还是碰巧看起来像地址的整数，保守式 GC 可能会保留一些实际上已经死亡的对象。这会导致堆内存使用率略有下降，但换来的是程序正确性的保证。在实际应用中，这种权衡通常是值得的。

对于追求更低暂停时间的场景，可以考虑进一步引入增量式或并发式 GC 技术。增量式 GC 将完整的标记过程分解为多个小步骤，每次只暂停一小段时间；并发式 GC 则利用多核 CPU 在后台线程中执行标记工作。这些技术都可以与保守式根扫描相结合，构建一个既安全又高效的垃圾回收系统。

总结

从精确式 GC 到保守式 GC 的演进，本质上是对运行时边界认知的扩展。通过实现本机栈扫描和寄存器溢出处理，我们不仅解决了对象误回收的技术难题，也为后续进一步的 GC 优化奠定了基础。保守式根扫描虽然引入了一定的性能开销，但它提供的是程序正确性的根本保障。在实际的动态语言实现中，这种演进往往是必经之路 —— 唯有如此，才能构建一个稳定可靠的运行时环境。

资料来源：Matheus Moreira 的博客文章《Baby's Second Garbage Collector》（https://www.matheusmoreira.com/articles/babys-second-garbage-collector）