CIRC: 并发即时引用计数

一个高效的线程安全引用计数指针，支持原子共享可变性和弱指针。

该库基于以下研究论文。

Jaehwang Jung, Jeonghyeon Kim, Matthew J. Parkinson, 和 Jeehoon Kang. 2024. 并发即时引用计数. Proc. ACM Program. Lang. 8, PLDI, 文章 153 (2024年6月)，24 页. https://doi.org/10.1145/3656383

使用 Rc<T> 和 AtomicRc<T> 的并发引用计数

circ::Rc<T> 是一个指向类型为 T 的对象的线程安全引用计数指针，类似于 std::sync::Arc<T>。与 std::sync::Arc<T> 不同，circ::Rc<T> 的接口非常适合实现非阻塞并发数据结构。具体来说，它

• 允许标记指针；
• 可以是 null（因此不实现 Deref 特性）；
• 最重要的是，它可以存储在 circ::AtomicRc<T>，一个支持原子 load、store 和 compare_exchange 的共享可变位置。

通过 Snapshot<'g, T> 实现高效的访问

当访问大量对象时，如遍历链表，引用计数可能导致显著的性能开销。为了解决这个问题，CIRC 提供了 Snapshot<T> 指针类型，用于未计数的临时局部引用。从 AtomicRc 加载 Snapshot 不会增加被引用对象的计数，从而避免性能开销。相反，Snapshot 的引用通过基于周期的回收（EBR）进行保护，使用 crossbeam-epoch 的修改版本来实现。

事实上，CIRC 在底层依赖于 EBR 安全回收零计数对象。因此，所有对 AtomicRc 的访问都必须在 EBR-protected 的临界区中进行。线程可以使用 circ::cs() 激活临界区，该操作返回一个 RAII 风格的 Guard。AtomicRc 的方法接收一个 Guard 引用以确保它在临界区中运行。当释放保护器时，临界区被关闭。

Snapshot<'g, T> 仅在其创建的临界区内部有效（因此称为“临时”和“局部”）。这是通过 'g 生命周期参数强制执行的，该参数来自传递给 AtomicRc 方法的保护器引用。要将加载的 Snapshot 存储到 AtomicRc 或发送给其他人，首先使用 .counted() 将其提升为 Rc。

使用弱引用管理循环结构

由于回收的循环依赖性，使用 Rc 和 AtomicRc 引用形成的循环不能自动回收。在某些情况下，可以使用 CIRC 对 std::sync::Weak 的对应物 circ::Weak 来打破这种依赖关系。一个 Weak 不会阻止被引用对象的销毁（允许回收循环结构），因此不能直接解引用。然而，它可以防止释放引用的内存块，如果对象尚未销毁，则可以将其升级为 Rc。Weak 可以存储在 AtomicWeak 中，并且可以从 AtomicWeak 加载 WeakSnapshot。

类型关系

       ┌──────────┐                       ┌────────────┐
       │          │                       │            │
       │ AtomicRc │                       │ AtomicWeak │
┌──────┤          │                       │            ├─────┐
│      └──────────┘                       └────────────┘     │
│             ▲                                ▲             │
│             │ store                    store │             │
│             │                                │             │
│          ┌──┴─┐         downgrade        ┌───┴──┐          │
│ load     │    ├─────────────────────────►│      │     load │
│          │ Rc │                          │ Weak │          │
│          │    │◄─────────────────────────┤      │          │          has count
│          └┬───┘         upgrade          └─────┬┘          │              ▲
│           │  ▲                             ▲   │           │              │
│  snapshot │  │ counted             counted │   │ snapshot  │            ──┼──
│           ▼  │                             │   ▼           │              │
│      ┌───────┴──┐       downgrade       ┌──┴───────────┐   │              ▼
└─────►│          ├──────────────────────►│              │◄──┘       doesn't have count
       │ Snapshot │                       │ WeakSnapshot │
       │          │◄──────────────────────┤              │
       └──────────┘       upgrade         └──────────────┘

                              │
    prevents destruction   ◄──┼──►    prevents deallocation
      (deref-able)            │

与其他并发引用计数算法的比较

CIRC 相比其他最近出现的引用计数算法的关键优势是它能够快速回收长链结构。配备未计数局部引用的引用计数算法使用延迟递减或延迟处理零计数对象。这引入了回收两个链对象之间的延迟。由于这种延迟，回收可能无法跟上应用程序创建垃圾的速度。CIRC 采用类似的方法，但通过一个基于 EBR 的新型算法来快速识别可以立即递归回收的对象。有关深入讨论，请参阅上述研究论文。

示例

use circ::{cs, AtomicRc, RcObject, Rc, Snapshot};
use std::sync::atomic::Ordering::Relaxed;

// A simple singly linked list node.
struct Node {
    item: usize,
    next: AtomicRc<Self>,
}

// The `RcObject` trait must be implemented for all reference-counted objects.
// This trait enables *immediate recursive destruction*.
// Implementation is straightforward: simply add outgoing `Rc` pointers to `out`.
unsafe impl RcObject for Node {
    fn pop_edges(&mut self, out: &mut Vec<Rc<Self>>) {
        out.push(self.next.take());
    }
}


// Let's create a root node with an item `1`.
let root = AtomicRc::new(Node {
    item: 1,
    next: AtomicRc::null(),
});

// Before accessing the shared objects, the thread must activate EBR critical section.
// This enables us to efficiently access the objects without updating the reference counters.
let guard = cs();
// Load the first node as a `Snapshot` pointer.
let first = root.load(Relaxed, &guard);
assert_eq!(first.as_ref().map(|node| &node.item), Some(&1));

// Let's install a new node after the first node.
let new_second = Rc::new(Node {
    item: 2,
    next: AtomicRc::null(),
});
let result = first.as_ref().unwrap().next.compare_exchange(
    Snapshot::null(),
    new_second,
    Relaxed,
    Relaxed,
    &guard,
);
assert!(result.is_ok());

// Let's check the secondary node is properly installed.
let second = first
    .as_ref()
    .map(|node| node.next.load(Relaxed, &guard))
    .unwrap();
assert_eq!(second.as_ref().map(|node| &node.item), Some(&2));

// Those `Snapshot` pointers we have created so far (`first` and `second`) are able to be accessed
// only within the scope of `Guard`. After the `Guard` is dropped, further accesses to the `Snapshot`
// pointers are forbidden by the Rust type system.
//
// If we want to keep pointers alive, we need to promote them to `Rc`s with `counted()`.
// `Rc` is independent to the EBR backend, and owns the reference count by itself.
let first_rc = first.counted();
drop(guard);

// Even after the `Guard` is dropped, `first_rc` is still accessible.
assert_eq!(first_rc.as_ref().map(|node| &node.item), Some(&1));

请参阅 ./tests 以获取更多带有实际数据结构的示例。

限制

• 由于它使用 EBR，如果线程没有关闭其临界区，则回收无法进行。
• 仅适用于 Sized 类型。
• 立即递归销毁只沿相同类型的边缘工作。

许可证

在以下任一许可证下发布：

• Apache许可证，版本2.0 (LICENSE-APACHE 或 https://apache.ac.cn/licenses/LICENSE-2.0)
• MIT许可证 (LICENSE-MIT 或 http://opensource.org/licenses/MIT)

由您选择。

贡献

除非您明确说明，否则任何您有意提交并纳入工作的贡献，如Apache-2.0许可证中定义的，应双重许可如上，不附加任何额外条款或条件。