CIRC: Concurrent Immediate Reference Counting

An efficient thread-safe reference-counted pointer, with the support for atomic shared mutability and weak pointers.

This library is based on the following research paper.

Jaehwang Jung, Jeonghyeon Kim, Matthew J. Parkinson, and Jeehoon Kang. 2024. Concurrent Immediate Reference Counting. Proc. ACM Program. Lang. 8, PLDI, Article 153 (June 2024), 24 pages. https://doi.org/10.1145/3656383

Concurrent reference counting with Rc<T> and AtomicRc<T>

circ::Rc<T> is a thread-safe reference-counted pointer to an object of type T, similar to std::sync::Arc<T>. Unlike std::sync::Arc<T>, the interface of circ::Rc<T> is well suited for implementing non-blocking concurrent data structures. Specifically, it

• allows tagged pointers;
• can be null (thus does not implement the Deref trait); and
• most importantly, can be stored in a circ::AtomicRc<T>, a shared mutable location supporting atomic load, store, and compare_exchange.

Efficient access with Snapshot<'g, T>

Reference counting can incur significant overhead when accessing many objects, e.g., traversing linked lists. To address this, CIRC offers the Snapshot<T> pointer type for uncounted temporary local references. Loading a Snapshot from AtomicRc does not increment the count of the referent, avoiding the overhead. Instead, the referent of Snapshot is protected with epoch-based reclamation (EBR), using a modified version of crossbeam-epoch.

In fact, CIRC relies on EBR to safely reclaim zero-count objects under the hood. Therefore, all accesses to AtomicRc must be inside an EBR-protected critical section. A thread can activate a critical section with circ::cs(), which returns an RAII-style Guard. AtomicRc's methods take a reference to Guard to ensure that it is run in a critical section. The critical section is deactivated when the guard is dropped.

A Snapshot<'g, T> is valid only inside the critical section it was created in (thus "temporary" and "local"). This is enforced by the 'g lifetime parameter, which is derived from the reference to the guard passed to AtomicRc's methods. To store a loaded Snapshot to AtomicRc or send it to someone else, first promote it to an Rc with .counted().

Managing cyclic structures with weak references

Cycles formed with Rc and AtomicRc references cannot be reclaimed automatically due to cyclic dependency of reclamation. In some cases, the dependency can be broken with circ::Weak, CIRC's counterpart for std::sync::Weak. A Weak does not prevent destruction of the referent (allowing reclamation of cyclic structure), and thus is not directly dereferenceable. However, it prevents deallocation of the referenced memory block, and can be upgraded to Rc if the object has not been destructed yet. Weak can be stored in AtomicWeak, and a WeakSnapshot can be loaded from an AtomicWeak.

Type relation

       ┌──────────┐                       ┌────────────┐
       │          │                       │            │
       │ 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)            │

Comparison with other concurrent reference counting algorithms

The key advantage of CIRC over other recent reference counting algorithms is that it can quickly reclaim long linked structures. Reference counting algorithms equipped with uncounted local reference employ deferred decrement or deferred handling of zero-count objects. This introduces delay between reclaiming two linked objects. Because of this delay, the reclamation may not be able to keep up with the application's rate of creating garbage. CIRC follows a similar approach, but solves this problem with a novel EBR-based algorithm to quickly identify objects that can be immediately recursively reclaimed. For in-depth discussion, see the aforementioned research paper.

Example

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));

See ./tests for more examples with actual data structures.

Limitations

• Since it uses EBR, the reclamation cannot proceed if a thread does not deactivate its critical section.
• Works only for Sized types.
• Immediate recursive destruction works only along the edges of the same type.

License

Licensed under either of

• Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
• MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.