Scalable Delayed Dealloc
A scalable lock-free delayed memory reclaimer that emulates garbage collection by keeping track of memory reachability.
Its delayed deallocation algorithm is based on a variant of epoch-based reclamation where retired memory chunks are stored in thread-local storage until certain criteria are met. The crossbeam_epoch crate offers similar functionality, however users will find sdd
easier to use as the lifetime of a memory chunk is safely managed. For instance, sdd::AtomicOwned
and sdd::Owned
retire the contained instance when they are dropped, and sdd::AtomicShared
and sdd::Shared
retire the instance when the last strong reference is dropped.
Features
- Lock-free epoch-based reclamation.
Loom
support:features = ["loom"]
.
Examples
This crate can be used without an unsafe
block.
use ;
use Relaxed;
// `atomic_shared` holds a strong reference to `17`.
let atomic_shared: = new;
// `atomic_owned` owns `19`.
let atomic_owned: = new;
// `guard` prevents the garbage collector from dropping reachable instances.
let guard = new;
// `ptr` cannot outlive `guard`.
let mut ptr: = atomic_shared.load;
assert_eq!;
// `atomic_shared` can be tagged.
atomic_shared.update_tag_if;
// `ptr` is not tagged, so CAS fails.
assert!;
// `ptr` can be tagged.
ptr.set_tag;
// The ownership of the contained instance is transferred to the return value of CAS.
let prev: = atomic_shared.compare_exchange.unwrap.0.unwrap;
assert_eq!;
// `17` will be garbage-collected later.
drop;
// `sdd::AtomicShared` can be converted into `sdd::Shared`.
let shared: = atomic_shared.into_shared.unwrap;
assert_eq!;
// `18` and `19` will be garbage-collected later.
drop;
drop;
// `17` is still valid as `guard` keeps the garbage collector from dropping it.
assert_eq!;
// Execution of a closure can be deferred until all the current readers are gone.
guard.defer_execute;
drop;
// `sdd::Owned` and `sdd::Shared` can be nested.
let shared_nested: = new;
assert_eq!;
// If the thread is expected to lie dormant for a while, call `suspend()` to allow
// others to reclaim the memory.
suspend;
Memory Overhead
Retired instances are stored in intrusive queues in thread-local storage, and therefore additional space for Option<NonNull<dyn Collectible>>
is allocated per instance.
Performance
The average time taken to enter and exit a protected region: 2.4 nanoseconds on Apple M2 Max.