无 Unsafe 代码的垃圾回收

# 无需 Unsafe 代码的垃圾回收 原文：https://fitzgen.com/2024/02/06/safe-gc.html 包括我在内的很多人都为 Rust 实现过垃圾回收（GC）库。Manish Goregaokar 几年前写过一篇精彩的综述（https://manishearth.github.io/blog/2021/04/05/a-tour-of-safe-tracing-gc-designs-in-rust/），盘点过这一领域。这些库都力求为使用者提供**安全**的 API：对外暴露的接口完全无 `unsafe`，把库内部不可避免的 `unsafe` 封装得滴水不漏。 唯一的例外是“扫描用户自定义 GC 类型的所有出边”这一机制：一旦漏掉某条边， collector 就会误判对象已死而回收，但用户仍持有引用，导致 use-after-free。¹ 因此这一功能通常以 `unsafe` trait 的形式暴露——由用户而非库来承担维护这条关键不变量的责任。 然而，尽管 API 安全，这些库内部依旧大量使用 `unsafe`。我一直坚信**可以**写出完全不依赖 `unsafe` 的 GC 库，而所有听我断言的人都没反对过，却始终没有“构造性证明”。于是，我干脆自己撸了一个：`safe-gc`（https://github.com/fitzgen/safe-gc）——**零 `unsafe`**：API 没有，实现也没有，文件顶部直接 `forbid(unsafe_code)`。 当然，`safe-gc` 并不是高性能回收器。 --- ### 使用 `safe-gc` 先定义 GC 托管类型，用 `Gc<T>` 表示对象间的引用，并实现 `Trace` 向 collector 报告所有出边： ```rust use safe_gc::{Collector, Gc, Trace}; // GC 托管对象 struct List { value: u32, prev: Option<Gc<List>>, next: Option<Gc<List>>, } // 向 collector 报告引用边 impl Trace for List { fn trace(&self, collector: &mut Collector) { if let Some(prev) = self.prev { collector.edge(prev); } if let Some(next) = self.next { collector.edge(next); } } } ``` 看起来和其它 Rust GC 库差不多，只是 `Trace` 是**安全 trait**——后面会解释为什么能这么干。 接着创建一个或多个 `Heap`，每个堆独立回收： ```rust use safe_gc::Heap; let mut heap = Heap::new(); ``` 然后就可以分配对象： ```rust let a = heap.alloc(List { value: 42, prev: None, next: None }); let b = heap.alloc(List { value: 36, prev: Some(a.into()), next: None }); // 随便制造垃圾，反正最终会被清理 for i in 0..100 { let _ = heap.alloc(List { value: i, prev: None, next: None }); } ``` 堆会在必要时自动触发 GC，也可手动强制： ```rust heap.gc(); // 强制回收 ``` 访问对象时，**不能**直接对 `Gc<T>` 解引用，而要通过 `Heap` 索引——这正是 `safe-gc` 能彻底避开 `unsafe` 的关键：² ```rust // 读 let b_value = heap[&b].value; assert_eq!(b_value, 36); // 写 heap[&b].value += 1; assert_eq!(heap[&b].value, 37); ``` 索引操作返回两种句柄： 1. `Gc<T>` —— `Copy`，仅用于**对象内部**相互引用，或能证明“此时不会 GC”（例如持有堆的共享引用）。它**不会**阻止对象被回收，因此**不能**跨越可能触发 GC 的操作。 2. `Root<T>` —— 会**钉住**对象，使其在 GC 中存活。适合跨 GC 操作持有引用。`Root` 不是 `Copy`，因为 drop 时要把自己从 root set 移除。 `heap.alloc(...)` 返回的正是 `Root<T>`。 --- ### 窥视内部 `safe_gc::Heap` 更像一个“带 ID 的 arena newtype”套 `Vec`，而非 Immix 那种层级区域堆。核心存储是按 `std::any::TypeId` 分组的统一 arena，最终落到 `Vec` 上，无需裸指针算术，也不用切分内存块——空闲列表只管理**下标**。 ```rust pub struct Heap { arenas: HashMap<TypeId, Box<dyn ArenaObject>>, ... } struct Arena<T> { elements: FreeList<T>, ... } enum FreeListEntry<T> { Occupied(T), Free(Option<u32>), // 指向下一空闲槽的链表 } struct FreeList<T> { entries: Vec<FreeListEntry<T>>, free: Option<u32>, // 首空闲槽 ... } ``` 分配流程：先拿到或创建 `T` 对应的 `Arena`，有容量就直接塞；否则走慢路径——先 GC 再重试。 ```rust impl Heap { #[inline] pub fn alloc<T: Trace>(&mut self, value: T) -> Root<T> { let arena = self.ensure_arena::<T>(); match arena.try_alloc(self.id, value) { Ok(root) => root, Err(value) => self.alloc_slow(value), } } #[inline(never)] fn alloc_slow<T: Trace>(&mut self, value: T) -> Root<T> { self.gc(); self.ensure_arena::<T>().alloc_slow(self.id, value) } } ``` `FreeList` 层面：优先复用空闲槽，否则扩容。 ```rust impl<T> FreeList<T> { fn try_alloc(&mut self, value: T) -> Result<u32, T> { ... } fn alloc(&mut self, value: T) -> u32 { self.try_alloc(value) .unwrap_or_else(|v| { self.double_capacity(); self.try_alloc(v).ok().unwrap() }) } } ``` 访问对象更简单：按 `TypeId` 找 arena，再按索引拿引用。 ```rust impl Heap { pub fn get<T: Trace>(&self, gc: impl Into<Gc<T>>) -> &T { ... } pub fn get_mut<T: Trace>(&mut self, gc: impl Into<Gc<T>>) -> &mut T { ... } } ``` --- ### Root Set 与 Moving GC 预留 Root set 即“必定活着”的集合。每个 `Arena` 自带一个 `RootSet`，内部是 `FreeList<Gc<T>>`，外面再包 `Rc<RefCell<...>>` 以便 `Root` 克隆时加项，drop 时删项。 特意让 `Root` **不直接**存 `Gc<T>`，而是存索引——这样以后若做搬移式 GC（如复制算法），可以在回收后统一修正 root 里的指针，而无需改动用户代码。虽然最初想直接上复制回收，后来遇到一些阻碍，但架构已预留好扩展点。 --- ### Mark-Sweep 算法 1. **准备阶段**：给每个 arena 重置/预分配 mark bit（用紧凑位图，不占对象头）。 2. **标记阶段**： - 先扫描 root set，把每个 root 压入对应 `T` 的 mark stack 并置位。 - 外层循环：只要任一 mark stack 非空； 内层循环：弹出一个索引，让所属 arena 调用该对象的 `Trace` 继续标记。 由于 `Heap` 本身无泛型参数，无法统一遍历，因此按 `TypeId` 分堆栈。 3. **清扫阶段**：遍历各 arena，若 mark bit 未置则 drop 对象并把槽回收到空闲链表。清扫后若 arena 仍接近满，则提前扩容，避免“每次分配都 GC 只腾一个槽”的抖动。 ```rust impl Collector { pub fn edge(&mut self, to: Gc<T>) { ... if mark_bits.set(to.index) { return; } // 已标记过 mark_stack.push(to.index); // 首次访问，入栈 } } ``` --- ### 小结 `safe-gc` 用纯 safe Rust 实现了完整的 mark-sweep GC： - 通过“索引访问”取代裸指针解引用，彻底遵守 Rust 借用规则； - `Trace` trait 无需 `unsafe`，因为漏报边只会导致“过早回收”，而回收后访问会 panic（而非 UB），从而把内存安全转化为逻辑错误； - 架构已预留 moving GC 的扩展能力。 虽然速度不算顶尖，但它给出了**零 unsafe 垃圾回收器**的鲜活样本——“可以写”不再只是口号。