Fast, efficient, and robust memory reclamation for concurrent data structures.

Concurrent data structures are faced with the problem of deciding when it is safe to free memory. Although an object might have been logically removed, other threads that previously loaded it may still be accessing it, and thus it is not safe to free immediately. Over the years, many algorithms have been devised to solve this problem. However, most traditional memory reclamation schemes make the tradeoff between performance, efficiency, and robustness. For example, epoch based reclamation is fast and lightweight but lacks robustness in that a stalled thread can prevent the reclamation of all retired objects. Hazard pointers, another popular scheme, tracks individual pointers, making it efficient and robust but generally much slower.

Another problem that is often not considered is workload balancing. In most reclamation schemes, the thread that retires an object is the one that reclaims it. This leads to unbalanced reclamation in read-dominated workloads; parallelism is degraded when only a fraction of threads are writing. This is especially prevalent with the use of M:N threading models as provided by asynchronous runtimes like Tokio.

Seize is based on the Crystalline-L reclamation scheme, which uses reference counting to determine when it is safe to free memory. However, reference counters are only used for objects that have been retired, avoiding the high overhead incurred by traditional reference counting schemes where every memory access requires modifying shared memory. Performance is competitive with that of epoch based schemes, while memory efficiency is similar to hazard pointers. Reclamation is naturally balanced as the thread with the last reference to an object is the one that frees it. Era tracking protects against stalled threads, making reclamation truly lock-free.

Seize uses hidden headers placed before user data, eliminating the need for wrapper types and enabling support for dynamically sized types.

Seize is compatible with all modern hardware that supports single-word atomic operations such as FAA and CAS.

Seize tries to stay out of your way as much as possible. It works with raw pointers directly instead of creating safe wrapper types that end up being a hassle to work with in practice. Below is a step-by-step guide on how to get started.

Seize avoids the use of global state and encourages creating a designated collector per data structure. Collectors allow you to allocate, protect, and retire objects:

use seize::Collector;

struct Stack<T> {
    collector: Collector,
    // ...
}

impl<T> Stack<T> {
    pub fn new() -> Self {
        Self {
            collector: Collector::new(),
        }
    }
}

Objects in a concurrent data structure that may be reclaimed are allocated through the collector's handle. Seize uses hidden headers placed before user data, so your types don't need any special wrapper:

use seize::Collector;
use std::mem::ManuallyDrop;
use std::sync::atomic::AtomicPtr;

pub struct Stack<T> {
    head: AtomicPtr<Node<T>>,
    collector: Collector,
}

struct Node<T> {
    next: *mut Node<T>,
    value: ManuallyDrop<T>,
}

impl<T> Stack<T> {
    pub fn push(&self, value: T) {
        let handle = self.collector.handle();
        let node = handle.allocate(Node {
            next: std::ptr::null_mut(),
            value: ManuallyDrop::new(value),
        }).into_raw();

        // ...
    }
}

Before loading atomic pointers, you must pin a guard to mark the thread as active. Each thread has multiple reservation slots (configurable via MAX_IDX), allowing multiple concurrent guards:

impl<T> Stack<T> {
    pub fn push(&self, value: T) {
        // ...

        let handle = self.collector.handle();
        let guard = handle.pin(0); // Pin reservation slot 0

        // ...
    }
}

Guards allow you to safely load atomic pointers. Any valid pointer loaded through a guard is guaranteed to stay valid until the guard is dropped, or is retired by the current thread. Importantly, if another thread retires an object that you protected, the collector knows not to reclaim the object until your guard is dropped.

impl<T> Stack<T> {
    pub fn push(&self, value: T) {
        // ...

        let handle = self.collector.handle();
        let guard = handle.pin(0);

        loop {
            let head = guard.protect(&self.head);
            unsafe { (*node).next = head; }

            if self
                .head
                .compare_exchange(head, node, Ordering::Release, Ordering::Relaxed)
                .is_ok()
            {
                break;
            }
        }

        // drop(guard);
    }
}

Note that the lifetime of a guarded pointer is logically tied to that of the guard -- when the guard is dropped the pointer is invalidated -- but a raw pointer is returned for convenience. Datastructures that return shared references to values should ensure that the lifetime of the reference is tied to the lifetime of a guard.

Objects that have been removed from a data structure can be safely retired through the handle. They will be reclaimed when no threads hold a reference to them:

impl<T> Stack<T> {
    pub fn pop(&self) -> Option<T> {
        let handle = self.collector.handle();
        let guard = handle.pin(0); // mark the thread as active

        loop {
            let head = guard.protect(&self.head); // safely load the head

            if head.is_null() {
                return None;
            }

            let next = unsafe { (*head).next };

            if self
                .head
                .compare_exchange(head, next, Ordering::Release, Ordering::Relaxed)
                .is_ok()
            {
                unsafe {
                    let data = ptr::read(&(*head).value);
                    drop(guard);
                    handle.retire(head); // retire the removed node
                    return Some(ManuallyDrop::into_inner(data));
                }
            }
        }
    }
}

There are a couple important things to note about retiring an object:

An object can only be retired if it is no longer accessible to any thread that comes after. In the above code example this was ensured by swapping out the node before retiring it. Threads that loaded a value before it was retired are safe, but threads that come after are not.

Unlike in schemes like EBR, a guard does not protect objects retired by the current thread. If no other thread holds a reference to an object it may be reclaimed immediately. This makes the following code unsound:

let ptr = guard.protect(&node);
handle.retire(ptr);
println!("{}", (*ptr).value); // <===== unsound!

Drop the guard before retiring to avoid this issue:

let ptr = guard.protect(&node);
drop(guard);
handle.retire(ptr);
// ptr is no longer protected, but you've safely transferred ownership

One of the key features of the Crystalline-L algorithm is support for multiple reservation slots per thread. This allows holding multiple guards simultaneously with different indices:

let handle = collector.handle();

let guard0 = handle.pin(0);
let guard1 = handle.pin(1);

let ptr0 = guard0.protect(&atomic0);
let ptr1 = guard1.protect(&atomic1);

// Both pointers are protected simultaneously

The number of slots is configurable via const generics:

// Collector with 4 reservation slots per thread
let collector = Collector::<4>::new();

For simple use cases, you can also use CrystallineBox<T> directly without a collector for one-off allocations with hidden headers:

use seize::CrystallineBox;

let boxed = CrystallineBox::new(42u64, 0);
assert_eq!(*boxed, 42);

// Convert to raw pointer
let ptr = boxed.into_raw();

// Later, reconstruct and drop
unsafe { drop(CrystallineBox::from_raw(ptr)); }