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.
Pinning
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.
Garbage
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.
APIs
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.
Examples
The following is a completely synthetic example.
use hyaline_smr as hyaline;
use std::{
ptr::NonNull,
sync::atomic::{AtomicUsize, Ordering},
thread,
};
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);
}
}
});
handle_array.push(handle);
}
while DROP_COUNT.load(Ordering::Relaxed) < MAX_THREADS * 50 {}
assert_eq!(DROP_COUNT.load(Ordering::Relaxed), MAX_THREADS * 50);
}Structs
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
Traits
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
Functions
Returns the default global collector.
Pins the current thread.