零 unsafe 代码！Rust 垃圾回收库 safe - gc 实现无安全隐患回收

无需不安全代码的垃圾回收2024 年 2 月 6 日包括作者在内的很多人都为 Rust 实现了垃圾回收Garbage CollectionGC库。几年前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 在实际应用中的表现究竟如何呢