元垃圾回收：使用OCaml的垃圾回收器来回收Rust的内存

# 元垃圾回收：利用 OCaml 的垃圾回收来回收 Rust - Soteria 来源：https://soteria-tools.com/blog/meta-garbage-collection 返回博客 (https://soteria-tools.com/blog) --- ## 追踪 Rust 的别名模型如果没有优化，成本可能呈二次方增长。了解我们如何通过元垃圾回收在 Soteria Rust 中解决这个问题。 Soteria Rust 是一个用于验证 Rust 程序的符号执行工具；它探索每条执行路径 (https://soteria-tools.com/blog/introducing-soteria#meet-soteria)，捕获未定义行为、别名错误等。我们最近注意到一个奇怪的现象：一个简单的循环，递增变量 `N` 次，消耗的时间竟然是 `N` 的二次方！罪魁祸首是我们的 *Tree Borrows* (https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/tree-borrows.md) 实现，这是 Rust 最新、最先进的别名模型。最终的修复意外地简单：因为 Soteria 是用 OCaml 编写的，我们可以将 Tree Borrows 状态的垃圾回收委托给 OCaml 的垃圾回收器。在大约 40 行代码中，我们从 **二次方时间变为线性时间**，**最高可提速 10 倍**！让我们看看我们是如何发现这个问题并修复它的。 让我们看看让我们注意到这个问题的例子：一个简单的基准测试，我们获取一个可变引用 `r`，读取它一次（到 `_old` 中），将其重置为零，然后在循环中递增它 `N` 次，断言结果确实是 `N`。 ``` fn loop_incr(r: &mut u32) { let _old = *r; *r = 0; for _ in 0..N { *r += 1; } assert_eq!(*r, N); } ``` 让我们用几个不同的 `N` 来运行它并测量时间： 0s 2s 4s 6s 8s 10s 12s - 0 500 1000 1500 2000 N 执行时间 (s) 二次方增长，对于一个线性递增……嗯。 看看 `N=1000` 时的执行时间，在 3.02 秒中，有 2.62 秒（87%）花费在我们的 Tree Borrows 实现中。 Tree Borrows 是我在 Soteria Rust 早期（2025 年 4 月）实现的第一批东西之一。它被设计用来在不安全 Rust 中给出别名规则，因为在这种情况下借用检查器无法帮助你，它提供了在操作原始指针时必须遵循的规则。这反过来允许编译器进行更多优化，但代价是更多触发未定义行为 (https://doc.rust-lang.org/reference/behavior-considered-undefined.html) (UB) 的方式。 这里关于 Tree Borrows 需要了解的重要事情是：它用一棵树追踪对某个内存位置的所有引用（和指针）之间的关系。每次 *重借用*（从一个引用派生出另一个引用，例如通过字段访问）都会在树中产生一个新节点，每次内存访问（每次读取或写入）都需要更新树中所有节点的状态。这个状态是模型的核心：每个引用处于五种状态之一，每次访问都会沿着一个状态机移动它。状态机自原始论文以来已经发生了很大变化，但为了演示，让我们看看原始的状态机： 例如，`&mut T` 从 `Reserved` 状态开始，`&T` 从 `Frozen` 状态开始。状态之间的箭头是在内存访问时发生的转换；如果某个引用的状态到达右侧的 `↯`，意味着程序有 UB，并且违反了 Rust 的别名规则。箭头旁边的符号告诉我们可以在什么条件下从一个状态转换到另一个状态。R 代表读取，W 代表写入，↓ 代表 *本地* 访问，而 ↑ 代表 *外来* 访问。因为我们在树中追踪引用，如果访问发生在这个引用上，或者发生在从这个引用重借用的引用（子节点）上，那么它就是本地访问。否则就是外来访问。查看状态机，只有通过本地访问（↓）才能到达 UB（`↯`）；请记住这一点以备后用。 在 Tree Borrows 的访问函数中添加一些调试信息，我们可以看到到循环结束时，有一棵包含 **9,010** 个节点的树，并且被访问了 **10,012** 次。然而，循环每次迭代只访问 `r: &mut u32` 常量次数，那么发生了什么？ 进行代码分析时一个重要的考虑因素是：我们 **不能** 启用优化，因为优化可能依赖于没有 UB，并且可能会擦除它。我们的工具希望能够检测 UB，所以这是不可行的。函数内联？隐藏 UB。未使用变量消除？隐藏 UB。语句重排序？隐藏 UB。我们必须使用未优化的代码，这通常比优化后的代码效率低得多，而且更长。为了说明这一点，这是 Rust 编译器 (https://godbolt.org/z/YWvG9hW5c) 为此程序生成的代码，优化级别设置为 1： ``` fn loop_incr(r: &mut u32) { let _old = *r; *r = 0; for _ in 0..N { *r += 1; } assert_eq!(*r, N); } pub fn main() { loop_incr::<1000>(&mut 0); } ``` ``` example::main::h98dd2dc58b240508: ret ``` 编译器足够聪明，能看出这个函数是空操作（断言永远不会失败），并完全擦除了它！然而，这只有在 Rust 类型系统保证了可变引用是非空、正确对齐、指向已初始化且可写内存的情况下才成立。所以优化是不可能的。 让我们看看没有优化 (https://godbolt.org/z/casY97YG9) 的 MIR，即 Soteria Rust 运行的 Rust 中间语言。我们可以看到 `for` 循环脱糖而成的 `` (https://doc.rust-lang.org/std/ops/struct.Range.html#impl-Iterator-for-Range%3CA%3E) 调用（下面第 6 行和第 11 行）。这些调用按理说总是会被内联（这是 Rust 的零成本抽象承诺！），但在没有优化的情况下它们会保留下来。 ``` 1 fn loop_incr(_1: &mut u32) -> () { 2 bb0: { 3 _2 = copy (*_1); 4 (*_1) = const 0_u32; 5 _4 = std::ops::Range<u32> { start: const 0_u32, end: const N }; 6 _3 = <std::ops::Range<u32> as IntoIterator>::into_iter(move _4) -> [return: bb2, unwind continue]; 7 } 8 9 bb2: { 10 _7 = &mut _3; 11 _6 = <std::ops::Range<u32> as Iterator>::next(copy _7) -> [return: bb3, unwind continue]; 12 } 13 14 ... 15 } ``` 这给我们一个提示，实际发生了什么：这棵过度生长的树并非由 `r` 引起，而是由正在被迭代的 `Range` 对象引起。每次迭代，树都会增加 `A` 个节点，并且被访问 `B` 次。这意味着总共大约有 `A * B * N²` 次节点访问，这在 `N` 上是二次方的！如果你想要精确的数字，展开下面的细节；事实证明，我们之前测量的 9,010 个节点和 10,012 次访问，正是我们预期会看到的。 ### 乏味的细节和数学计算 新节点在重借用时创建，这隐含发生在 1. 函数调用、2. 在方法调用之前对接收者进行（这是自动引用 (https://doc.rust-lang.org/reference/expressions/method-call-expr.html#r-expr.method.autoref-deref)）、以及 3. 字段访问中。 如果我们深入挖掘，我们会发现在栈中有以下重借用： - 在调用 `Iterator::next` 之前（参见上面的 MIR）——这是 1 - 那个方法调用（上面列表中的情况 2）——2 - 同一个函数调用（情况 1）——3 - 在 `Iterator::next` 内部调用方法 `spec_next` (https://doc.rust-lang.org/src/core/iter/range.rs.html#1396-1398)（情况 2）——4 - 同一个函数调用（情况 1）——5 - `spec_next` 本身然后重借用 `self.start` 和 `self.end` (https://doc.rust-lang.org/src/core/iter/range.rs.html#899-908)（情况 3）——7 - ……然后调用 `::lt`，这再次重借用两者（情况 1）——**9**！ 每次对 `::next` 的函数调用因此在范围的位置添加 **9** 个节点，该函数被调用 `N + 1` 次。加上根节点，到函数结束时，我们有 `9 * (N + 1) + 1 = 9N + 10` 个节点，这匹配我们看到的 `N=1000` 时的 9,010 个节点。 查看代码，我们还看到： - 对 `Range` 的初始借用访问了树两次，因为它有两个字段——所以总共 2 次树访问 - 每次调用 `next` 在返回 `Some(_)` 时进行 10 次树访问，否则进行 8 次——`2 + 10N + 8`，对应于 N 次迭代和最后的 `None` 返回 - 当 `Range` 离开作用域时，树最后被访问两次——`2 + 10N + 8 + 2 = 10N + 12` 对于 `N=1000`，这给出了 10,012 次树访问，这也与我们之前看到的匹配。 这解释了二次方增长。每次迭代，树增长 `A=9` 个节点，并且被访问 `B=10` 次。所以对于 `N` 次迭代，我们有 `1/2 * 9 * 10 * N² = 45N²` 次节点访问，这在 `N` 上是二次方的（`1/2` 是因为树线性增长，所以平均是半大）。 所以，我们*应该*追踪这 9,010 个节点，但这似乎工作量很大。我们能避免吗？幸运的是，答案是肯定的！可以说是的。在最好的情况下。而且理由又回到了 Tree Borrows 的状态机。如果我们更仔细地观察我们代码示例中树的结构，我们有类似这样的东西，它匹配我们之前做的计算： Tree Borrows 树的结构 需要注意的重要事情是，每次迭代创建的每个分支都是*独立的*；这些引用是从根节点（存储 `Range` 对象的变量）创建的。正如我们之前看到的，节点达到 UB 的唯一方式是通过*本地访问*。但是一旦一次迭代完成，它的分支就无法到达：没有活跃的引用指向它，所以没有任何东西可以对它执行本地访问。因此这些节点永远不能导致 UB，一旦我们知道它们不可达，我们就可以安全地将它们从树中删除！ ### 额外的健全性理由 对于熟悉 Tree Borrows 的人来说，我在这里略过了一些细节。所以这里是最后几个理由，以表明这是正确的！ - 当引用是 *protected* 时，实际上可以通过外来访问达到 UB，这在函数入口处发生（它在函数出口处不受保护）。垃圾回收一个受保护的节点可能导致我们错过 UB！幸运的是，我们的解释器在整个函数作用域内将这些引用保留在一个变量中，以便能够释放保护器。这意味着我们持有对它们的强引用，它们不能被 GC 回收。 - 如果某个中间节点被 GC 回收，但其子节点仍然可达呢？那么本地访问也是可能的，我们会错过 UB！幸运的是，由于状态机的结构和重借用的工作方式，我们知道子节点总是至少与其父节点一样接近 UB。父节点引起的任何 UB，子节点也会引起。因此去除父节点是安全的，因为它不会比子节点引起 *更多的 UB*。我们组织数据结构以允许中间节点被 GC 回收的方式是：树被表示为一个从节点到一组弱节点的弱映射，这些弱节点是*所有*该节点的祖先，而不仅仅是其父节点。如果一个中间节点被 GC 回收，其所有后代都会失去它作为一个祖先，但它们仍然直接持有所有其他祖先，所以本地/外来关系保持完整。 - 那符号执行呢？这个 GC 机制难道不会擦除在一条执行分支中不可达但在另一条分支中可达的引用吗？这个系统对跨并行执行分支共享的状态引入了可变性！再次，这自然地被我们解释器的工作方式避免了。我们总是在分支点之前持有状态的引用，所以如果 Tree Borrows 节点在另一条执行分支中可达，那么指向该状态的引用将阻止它在它不可达的分支中被 GC 回收。这在技术上是次优的，因为这意味着某些分支可能需要追踪它们不需要的引用，但这是正确的，在实践中我们还没有看到任何问题。一种解决方案是在我们的解释器中实现一个垃圾回收器，它遍历我们正在追踪的堆，查找哪些树节点仍然可达，并清除所有不可达的节点。然而这成本高昂，因为堆可能变得非常大。完全遍历它，记录遇到的节点，然后清除这些节点是很大工作量。 幸运的是，Soteria Rust 是用 OCaml 编写的，它自带垃圾回收器。如果我们直接重用它呢？这样做出乎意料地简单！我们需要确保两件事： 1. 节点的 OCaml 对象在其 Rust 引用仍在使用的任何地方都被*强*持有，这样引用活跃的节点永远不会被回收。这已经是事实。 2. 我们的 Tree Borrows 实现*弱*持有其节点：GC 不应将树中的节点视为阻碍垃圾回收，因为我们希望它们被回收并移除。为此，我们使用 `Weak` 集合 (https://ocaml.org/manual/5.5/api/Weak.html) 和 `Ephemeron` (https://ocaml.org/manual/5.5/api/Ephemeron.html) 的组合，这是 OCaml 提供的两种数据结构，它们持有所含元素的弱引用。 就这样！让我们再次运行它。 0s 2s 4s 6s 8s 10s 12s - 0 500 1000 1500 2000 N 执行时间 (s) 现在执行时间……更慢了？而且折线图超出了图表范围。 发生的情况是OCaml 垃圾回收器 (https://ocaml.org/docs/garbage-collector) 只是定期运行，而不是持续运行。在我们的例子中，Soteria Rust 并没有分配太多内存，所以垃圾回收器运行得不频繁。在这个例子中，垃圾回收器似乎从未运行，我们反而要支付弱引用的成本，弱引用的访问比强引用稍微昂贵一些。 让我们自己掌握主动权。我们不能持续运行 GC，那样成本太高。我们还想确保在它不太可能值得的时候不调用它；当树很小时重借用引用不是问题。此外，OCaml GC 分两个阶段进行：次要回收，速度快，只回收“年轻”值；主要回收，速度较慢，回收所有值。次要回收对我们来说不够，因为它不会回收树中不再可达的节点，所以我们必须强行进行主要回收，使用 `Gc.major ()` (https://ocaml.org/manual/5.5/api/Gc.html#VALmajor)。我们将在树超过大小 `T` 时运行 GC，`T` 是我们用来实验的单独参数。我们还需要小心树增长超过大小 `T` 但 GC 没有释放任何节点（因为所有引用都被持有）的情况：我们不希望后续的所有访问因为一次 GC 运行而变慢。相反，我们将实现一个“回退”机制，如果 GC 未能释放任何节点，下一次 `T` 将设置为 `2T`。 让我们再次运行它；首先使用 `T=10`，对于这个例子来说是理论上的最优值，因为任何时候最多有 10 个节点可达。我们还尝试了 `T=32, 64, 128, 256, 512`，以观察它在 GC 运行频率较低时的表现。 0s 2s 4s 6s 8s 10s 12s - 0 500 1000 1500 2000 N 执行时间 (s) 太棒了！GC 现在运行了，我们又有了线性执行时间。不出所料，`T=10` 实际上远非最优，因为每 10 个节点运行一次 GC 成本太高。似乎最好的值是 `T=256`，它在保持树相对较小和不太频繁运行 GC 之间取得了良好的平衡。对于 `N=1000`，执行时间现在是 0.54 秒，比原来的 3.02 秒**提速 5.6 倍**。在 `N=2000` 时，提速达到 **10.6 倍**！最重要的是，**我们的执行时间现在相对于 `N` 是线性的**，而不是二次方的。 我们还可以直接观察改进，方法是测量在 10,012 次访问后 `Range` 树的大小。没有收集时，树只会增长，最终达到我们之前预测的 9,010 个节点。使用 `T=256`，我们得到一个锯齿形图案，增长直到达到阈值 `T`，此时 GC 运行并收集大部分节点。 0 2000 4000 6000 8000 10000 - 0 2500 5000 7500 10000 树访问次数 树大小 (节点) 在其他基准测试中运行此更改，我们得到了大部分正面结果；一些基准测试变慢了，原因是使用弱引用而不是直接实现。