Crate hyaline_smr[][src]

Expand description

Safe Memory Reclaimation using Hyaline algorithm
Snapshot-Free, Transparent, and Robust Memory Reclamation for Lock-Free Data Structures

An interesting problem concurrent collections deal with comes from the remove operation. Suppose that a thread removes an element from a lock-free map, while another thread is reading that same element at the same time. The first thread must wait until the second thread stops reading the element. Only then it is safe to destruct it.

Programming languages that come with garbage collectors solve this problem trivially. The garbage collector will destruct the removed element when no thread can hold a reference to it anymore.

This crate implements the Scalable Multiple-List without support for stalled threads version of Hyaline. When an element gets removed from a concurrent collection, it is inserted into a global list of garbage and every time a thread accesses a collection, it registers itself to the colletor. When the thread de-registers from the collector it destructs some garbage that became so old that no thread can be referencing it anymore.

That is the general mechanism behind Hyaline memory reclamation, but the details are a bit more complicated. Anyhow, memory reclamation is designed such that the users of concurrent collections don’t have to worry much about.

Please Refer Snapshot-Free, Transparent, and Robust Memory Reclamation for Lock-Free Data Structures for futher information.


Before a concurrent collection can be accessed, a participant must be pinned. By pinning a participant we declare that any object that gets removed from now on must not be destructed just yet.


Objects that get removed from concurrent collections must be stashed away until all currently pinned participants get unpinned. Such objects can be stored into a thread-local or global storage, where they are kept until the right time for their destruction comes.

There is a global shared instance of garbage queue. You can retire the garbage values after which the garbage collector will take care of the deallocation of the value at the correct time.


For majority of use cases, just use the default garbage collector by invoking pin and retire. If you want to create your own garbage collector, use the Collector API.


The following is a completely synthetic example.

use hyaline_smr as hyaline;
use std::{
    sync::atomic::{AtomicUsize, Ordering},

const MAX_THREADS: usize = 8;
static DROP_COUNT: AtomicUsize = AtomicUsize::new(0);

struct TestNode {
   foo: usize

impl Drop for TestNode {
    fn drop(&mut self) {
        DROP_COUNT.fetch_add(1, Ordering::Relaxed);

fn count_drop() {
    let mut handle_array = Vec::new();

    for _i in 0..MAX_THREADS {
        let handle = thread::spawn(move || {
            let guard = hyaline::pin();
            for j in 0..50 {
                unsafe {
                    let x = Box::new(TestNode { foo: j });
                    let garb = NonNull::new(Box::into_raw(x));
                    hyaline::retire(garb, &guard);
    while DROP_COUNT.load(Ordering::Relaxed) < MAX_THREADS * 50 {}
    assert_eq!(DROP_COUNT.load(Ordering::Relaxed), MAX_THREADS * 50);


Garbage collector that implements Hyaline algorithm Number of slots is fixed at present with 32 slots

A RAII guard which keeps the thread active in garbage collection. The thread will be unpinned automatically upon guard’s destruction


Safe Memory Reclaimation(SMR) trait defines the methods that a collector must implement and expose to the end user. The methods defined here are standard APIs in the concurrent garbage collector world. These APIs are also used in other SMR schemes like epoch based garbage collector


Returns the default global collector.

Pins the current thread.

Collects the garbage values form the user. The local_guard argument is just here for ensuring that retire() is called after a pin().