tracing-rc

tracing-rc是用于Rust的具有安全、简单API的循环收集引用计数指针。

该crate实现的Gc类型提供了一种类似于std::rc::Rc的循环感知智能指针，主要区别是你不能对Gc有弱引用。如果你有一些相互链接的数据结构（例如GraphNode、LuaTable等）且没有明确的生命周期或所有者，这将很有用。

Gc可能不适合许多用例

• 如果你有一个具有明确父子关系的数据结构（如双向链表或树），你可能只需使用std::rc::Rc和Weak。
• 如果你的数据只用于特定范围并全部丢弃，你可能从类似typed-arena或bumpalo的crate中受益。
• 如果你只有一个类型并且想要添加/删除值，类似generational-arena的crate可能最好。

不安全代码的使用

库在两个地方使用了不安全代码，它丢弃了Gc和Agc类型的内部数据。对于Gc，这种不安全代码通过调用borrow_mut到一个故意泄漏在数据丢弃后的RefCell来保护，使得内部（已丢弃）数据不可访问。Agc类似地在其内部数据丢弃后泄漏一个WriteMutexGuard。

并发收集支持

此库在sync标志后面有实验性的并发收集支持。启用sync标志将为原子Agc类型以及并发的collect实现提供访问权限。

安全性 & Rc收集器设计考虑

由于任何对由垃圾回收指针拥有的对象的Trace特性和自定义Drop实现的实现都可能运行任意代码，它们可能会在收集过程中尝试创建新的副本或丢弃现有的已跟踪对象（即使是已经跟踪的对象）。此外，由于客户端代码中的错误，Trace可能会报告比它实际拥有的更多项作为子项（报告较少是 trivially 安全的，因为它将简单地泄漏）。

为了使这个crate具有正确性和提供安全的Trace特性，收集器必须不会在概述的任何场景中导致未定义的行为。为了实现这一点，收集器执行以下操作

1. 等待收集或已在跟踪过程中访问的项目被赋予一个额外的强引用或弱引用，以确保内存保持分配状态，即使在遍历过程中强引用被丢弃，包含的数据仍然有效。
2. 在遍历期间，收集器不会减少跟踪项的引用计数（这与最初启发了这个crate的Bacon-Rajan不同）。相反，收集器会记录通过跟踪到达每个指针的次数，然后将其与它跟踪的每个指针的强计数进行比较，以决定该项目是否死亡。
3. 在丢弃任何值之前，收集器会标记对象为已死亡。在这个过程中，Trace实现中的错误可能导致收集器相信一个已死亡值仍然存活（导致泄漏）或一个活动值已死亡（使其不可访问，但留下gc指针有效）。安全代码无法访问已死亡值（它将引发恐慌或返回Option::None），并且无法恢复已死亡对象的活状态。值永远不会临时死亡，收集器只在完全确定它是有效的收集候选者（所有强引用都来自其循环的成员）之后才会将其标记为死亡。
4. 在标记完所有跟踪对象之后，收集器开始丢弃它认为已死亡的对象的内部数据，在检查是否有任何未解决的借用（不可变或可变）之前。这次丢弃 不会 也不会 不能 释放gc指针的内存，也不会使引用计数或活跃状态不可访问。借用检查确保数据不会被从活动借用中丢弃。
5. 在完成丢弃已死亡值的内部数据之后，收集器释放其强/弱引用。如果循环被打破，该引用将是Gc值的最后一个剩余引用，其内存将被清理。如果有剩余引用，其内存将在未解决引用超出范围时被清理。

包括设计来锻炼每个这些场景的大量测试，并且所有这些测试都通过miri（除了故意行为错误的代码的泄漏）。

示例

use tracing_rc::{
    rc::{
        collect_full,
        Gc,
    },
    Trace,
};

#[derive(Trace)]
struct GraphNode<T: 'static> {
    #[trace(ignore)]
    data: T,

    edge: Option<Gc<GraphNode<T>>>,
}

fn main() {
    {
        let node_a = Gc::new(GraphNode {
            data: 10,
            edge: None,
        });
        let node_b = Gc::new(GraphNode {
            data: 11,
            edge: None,
        });
        let node_c = Gc::new(GraphNode {
            data: 12,
            edge: Some(node_a.clone()),
        });

        node_a.borrow_mut().edge = Some(node_b.clone());
        node_b.borrow_mut().edge = Some(node_c);

        let a = node_a.borrow();
        let b = a.edge.as_ref().unwrap().borrow();
        let c = b.edge.as_ref().unwrap().borrow();

        assert_eq!(a.data, c.edge.as_ref().unwrap().borrow().data);
        // all of the nodes go out of scope at this point and would normally be leaked.
    }

    // In this simple example, we always have cycles and our program is complete after this,
    // so we can't take advantage of the young generation picking up acyclic pointers without
    // tracing.
    collect_full();

    // All leaked nodes have been cleaned up!
}

其他GC实现

Rust中有许多垃圾回收的优秀实现，其中一些启发了这个crate。

• bacon_rajan_cc
  • 与这个crate类似，它基于Bacon-Rajan算法，并提供了一个用于循环跟踪的Trace特性。它在理解原始论文的工作方式方面非常有帮助，尽管这个crate采用了非常不同的方法。
• gc-arena
  • 一个非常整洁的基于生命周期和区域而非循环跟踪的垃圾回收实现。
• cactusref
  • 对循环收集的另一种新颖的方法。
• rust-gc
• shredder
• shifgrethor