# CIRC: Concurrent Immediate Reference Counting [![crates.io](https://img.shields.io/crates/v/circ.svg)](https://crates.io/crates/circ) [![docs.rs](https://img.shields.io/docsrs/circ/latest)](https://docs.rs/circ) 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. ## Concurrent reference counting with `Rc` and `AtomicRc` `circ::Rc` is a thread-safe reference-counted pointer to an object of type `T`, similar to `std::sync::Arc`. Unlike `std::sync::Arc`, the interface of `circ::Rc` 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`, 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` 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](https://docs.rs/crossbeam-epoch/latest/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 ```text ┌──────────┐ ┌────────────┐ │ │ │ │ │ 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 ```rust 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, } // 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>) { 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](LICENSE-APACHE) or ) * MIT license ([LICENSE-MIT](LICENSE-MIT) or ) 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.