零 unsafe 代码！Rust 垃圾回收库 safe - gc 实现无安全隐患回收
无需不安全代码的垃圾回收
2024 年 2 月 6 日，包括作者在内的很多人都为 Rust 实现了垃圾回收（Garbage Collection，GC）库。几年前，Manish Goregaokar 撰写了一篇精彩的综述，介绍了这一领域。这些库旨在为用户提供安全的 API，即一个无 `unsafe` 的接口，能妥善封装并隐藏库内部的 `unsafe` 代码。不过，枚举用户定义的 GC 类型的外向 GC 边的机制是个例外。因为若未能枚举所有边，可能导致悬空指针（use - after - free）错误。通常，这个功能会以 `unsafe` 特性（trait）的形式暴露给用户实现，毕竟维护这一关键安全不变性是用户的责任，而非库的责任。
然而，尽管这些库提供了安全的接口，但它们在内部实现中都大量使用了 `unsafe` 代码。作者一直认为可以编写一个完全不使用 `unsafe` 代码的垃圾回收库，而且和别人这么说时也没人反对，但一直没有实际的实现来证明。
最终，作者创建了 `safe - gc` 库：一个零 `unsafe` 代码的 Rust 垃圾回收库。不仅 API 中没有 `unsafe`，实现中也没有，甚至在代码顶部还有 `forbid(unsafe_code)` 编译指示。不过，`safe - gc` 并不是一个高性能的垃圾回收器。
使用 `safe - gc`
要使用 `safe - gc`，首先要定义由 GC 管理的类型，使用 `Gc` 来定义对其他 GC 管理对象的引用，并实现 `Trace` 特性，将这些 GC 边报告给收集器。这看起来和其他 Rust 的 GC 库很相似，不过如果能为 `Option` 实现 `Trace` 特性，再加上一个 `derive(Trace)` 宏就更好了。与现有 GC 库的最大区别在于，`Trace` 实现起来是安全的。
接下来，创建一个或多个 `Heap` 来分配对象。每个堆都会独立进行垃圾回收。有了 `Heap` 后，就可以分配对象了。堆会在必要时自动触发垃圾回收，也可以手动强制进行回收。
不能直接解引用 `Gc` 指针，而必须通过索引 `Heap` 来访问引用的 `T` 对象。这与其他 GC 库不同，也是 `safe - gc` 无需 `unsafe` 代码的关键，这样的实现能遵循 Rust 的所有权和借用规则。
实际上，有两种类型可以用来索引 `Heap` 以访问 GC 对象：一是 `Gc`，它是可复制（`Copy`）的，当在 GC 管理对象的类型定义中引用其他 GC 管理对象，或者能证明不会发生垃圾回收（即对其堆有共享借用）时使用，但它不会将其引用的 `T` 固定（root），无法保证对象在垃圾回收中存活，因此在可能触发垃圾回收的操作中，不应使用 `Gc` 来持有 GC 引用；二是 `Root`，它会固定其关联的 `T` 对象，防止对象在垃圾回收中被回收，适合在可能触发垃圾回收的操作中持有对 GC 管理对象的引用，且不可复制，因为丢弃它时必须从堆的根集（root set）中移除其条目，分配操作返回的是固定引用。
深入探究
`safe_gc::Heap` 更像是基于 `Vec` 的竞技场新类型（arena newtype），而不是像 Immix 那样具有区域层次结构的工程化堆。它的主要存储是一个从 `std::any::TypeId` 到关联类型的统一竞技场（arena）的哈希映射。这让我们最终可以使用 `Vec` 作为堆分配对象的存储，无需进行任何不安全的指针运算，也不用担心在空闲列表中分割大块内存。实际上，空闲列表只管理索引，而非原始内存块。
要在堆中分配一个新的 `T`，首先从堆的哈希映射中获取 `T` 对象的竞技场，如果不存在则创建。然后，检查竞技场是否有足够的容量来分配新的 `T`。如果有，将对象添加到竞技场并返回一个固定引用；如果没有，则采用较慢的路径，触发垃圾回收以确保有空间分配新对象，然后再次尝试。
`Arena` 的分配最终依赖于 `FreeList` 的分配，它会尽可能使用内部的空闲条目列表来利用现有容量，否则会保留额外的容量。
访问堆中的对象很简单：查找 `T` 的竞技场并进行索引。
在了解 `safe - gc` 如何进行垃圾回收之前，需要先看看它如何实现根集。根集是那些肯定存活的对象集合，即应用程序当前正在使用或计划在未来使用的对象。收集器的目标是识别所有从这些根对象可传递引用的对象，而回收其他所有对象。
每个 `Arena` 都有自己的 `RootSet`。为简单起见，`RootSet` 是 `FreeList>` 的包装器。添加新的根对象时，将其插入 `FreeList`；丢弃根对象时，将其从 `FreeList` 中移除。这意味着根集可能包含重复项，因此不是一个真正的集合。根集的 `FreeList` 还被包装在 `Rc>` 中，这样就可以为 `Root` 实现 `Clone`，在根集中添加另一个条目，并且无需显式传递 `Heap` 来持有对固定对象的额外引用。
最后，作者精心设计了 `Root` 和 `RootSet`，使 `Root` 不直接持有 `Gc`。这样可以在回收后更新固定的 GC 指针，这对于像分代 GC 和内存整理（compaction）这样的移动 GC 算法是必要的。实际上，作者最初打算为 `safe - gc` 实现一个复制收集器（copying collector），这是一种移动 GC 算法，但遇到了一些问题。目前，保留了在未来引入移动 GC 的可能性。
了解了这些之后，就可以看看核心的垃圾回收算法了。`safe - gc` 实现了简单的标记 - 清除（mark - and - sweep）垃圾回收算法。首先，重置每个竞技场的标记位，并确保有足够的位来标记所有已分配的对象，因为将标记位存储在一个独立的紧凑位集中，而不是每个对象的头部字中。
接下来进入标记阶段。从遍历每个根对象开始，设置其标记位，并通过调用 `collector.edge(root)` 将其加入标记栈。标记阶段会在一个定点循环中继续标记从这些根对象可传递到达的所有对象。如果发现一个未标记的对象，就标记它并将其加入追踪队列；如果遇到已经标记的对象，则忽略它。
不同寻常的是，没有一个统一的标记栈。`Heap` 没有 `T` 类型参数，包含多种不同类型的对象，所以堆本身不知道如何追踪任何特定的对象。然而，堆中的每个 `Arena` 只包含一种类型的对象，并且竞技场知道如何追踪其对象。因此，为每个 `T`（即每个竞技场）都有一个标记栈。这意味着定点循环有两层：外层循环在任何标记栈有工作时继续执行，内层循环用于清空特定的标记栈。
虽然标记的驱动循环在 `Heap::gc` 方法中，但实际的边追踪和标记位设置发生在 `Collector` 和竞技场中，因为竞技场有 `T` 类型参数，可以为每个对象调用正确的 `Trace` 实现。那么，`safe - gc` 在实际应用中的表现究竟如何呢？