Refuse

一个易于使用、增量式、多线程的Rust垃圾回收器。

//! A basic usage example demonstrating the garbage collector.
use refuse::{CollectionGuard, Ref, Root};

let guard = CollectionGuard::acquire();
// Allocate a vec![Ref(1), Ref(2), Ref(3)].
let values: Vec<Ref<u32>> = (1..=3).map(|value| Ref::new(value, &guard)).collect();
let values = Root::new(values, &guard);
drop(guard);

// Manually execute the garbage collector. Our data will not be freed,
// since `values` is a "root" reference.
refuse::collect();

// Root references allow direct access to their data, even when a
// `CollectionGuard` isn't held.
let (one, two, three) = (values[0], values[1], values[2]);

// Accessing the data contained in a `Ref` requires a guard, however.
let mut guard = CollectionGuard::acquire();
assert_eq!(one.load(&guard), Some(&1));
assert_eq!(two.load(&guard), Some(&2));
assert_eq!(three.load(&guard), Some(&3));

// Dropping our root will allow the collector to free our `Ref`s.
drop(values);
guard.collect();
assert_eq!(one.load(&guard), None);

正如版本号所示，这个crate处于早期开发阶段。直到 0.1.0 不会提供semver兼容性。

动机

在开发 Muse 时，@Ecton 认识到 垃圾回收的必要性 以防止不受信任的脚本无控制地泄露内存。在调查了市场后，他没有找到任何可以轻松融入他语言愿景的解决方案。据他所知，这个回收器的设计选择与Rust中现有的任何回收器都不同。

设计

这个crate在Rust中公开了一个增量式、多线程、追踪式垃圾回收器的完全安全的API。

追踪式垃圾回收器可以通过各种方式实现，以识别已知内存的“根”，从而可以从根开始通过所有必要的引用来跟踪，以确定哪些内存分配可以被释放。

这个crate公开了一个 Root<T> 类型，其行为类似于一个 Arc<T>，但会自动成为回收器的根。 Root<T> 实现 Deref<Target = T>，允许在回收器运行时访问底层数据。

Ref<T> 类型实现 Copy 并不提供对底层数据的直接访问。要获取底层数据的引用，必须使用 CollectionGuard 将弱引用升级。返回的引用与守卫绑定，防止在持有任何守卫时运行回收。

需要 CollectionGuard 做以下事情：

• 分配一个新的 Root<T> 或 Ref<T>
• 从一个 Ref<T> 加载一个 &T

安全性

该包在每个使用 unsafe 的地方旁边都有安全注释，并且在提供标志的情况下通过了 Miri 测试

MIRIFLAGS="-Zmiri-permissive-provenance -Zmiri-ignore-leaks" cargo +nightly miri test

• -Zmiri-permissive-provenance: parking_lot 内部将 usize 转换为指针，这违反了指针来源规则。指针来源目前只是一个实验性模型，而这个收集器从 parking_lot 中使用的一切都不能以尊重指针来源的方式实现。因此，这个库的作者认为这是一个可以忽略的实现细节。

• -Zmiri-ignore-leaks: 这个包启动了一个全局收集器线程，该线程永远不会关闭。Miri 检测到主线程没有等待启动的线程关闭，并警告这种潜在的内存泄漏。当一个线程关闭并且其所有数据都不可访问时，线程存储将被清理。然而，收集器永远不会关闭，并假设在任何给定时间都可能启动新的线程。

  此外，在某些平台上，当主线程退出时，主线程的线程局部存储可能不会根据 LocalKey 的文档 清理

该包公开了一个安全的 API，该 API 保证在错误使用 API 或错误实现 Collectable 特性时不会触发未定义的行为。 错误使用此包可能导致死锁和内存泄漏。 特别是

• Root<T> 之间的引用循环会导致泄漏，就像 Arc<T> 一样。
• 如果 Root<T> 使用锁定来实现内部可变性，则在没有收集器守护者的情况下保持锁定会导致垃圾收集器阻塞，直到锁定被释放。如果无法在没有获取收集器守护者的情况下释放锁定，则这将从暂停升级到死锁。 所有锁定应在获取 CollectorGuard 时获取和释放。

还有什么

• 终结器：目前执行了 Drop，但没有方法可以将行为附加到在对象被丢弃之前运行。
• 更高级的算法：当前使用的算法是简单的标记-清除。它对较小的集合表现良好，但随着内存集的增长，它会变得较慢。可能还会考虑其他算法，但当前的简单算法可能适合其应用（《Muse》[链接]）。

基准测试

基准测试很难。这些基准测试并不充分。这些数字来自执行benches/timings.rs的结果，该测试比较了分配100,000个32字节值所需的时间，包括分配每个Arc<[u8; 32]>、Root<[u8;32]>和Ref<[u8; 32]>所需的时间。这些测量值表示单个分配所需的时间。这些结果是在Ryzen 3700X上运行的。

1个线程

4个线程

8个线程

16个线程

32个线程

作者基准测试总结

在这些基准测试中，100个分配被收集到一个预分配的Vec中。清除Vec后，整个过程重复1000次，总共产生100,000个分配。

在Root和Ref基准测试中，在清除Vec之后放置了对CollectorGuard::yield_to_collector()的显式调用。测量值包括在这些让步点等待增量垃圾收集器运行所需的时间。

执行上述基准测试的CPU有16个核心。正如基准测试中的数字所示，CPU越接近完全饱和，垃圾收集对性能的影响就越大。

有很多机会可以提高性能，但增量垃圾收集需要在所有线程上暂停以执行收集。当活动线程较少时，这些暂停通常很短暂，但当许多线程活跃时，暂停可能会很长。