A generic trait based interface for abstracting over various schemes for concurrent memory reclamation.
Unlike garbage collected languages such as Go or Java, memory
management in Rust is primarily scope or ownership based and more akin to
Rust's ownership model in combination with the standard library's smart
Arc make memory management as painless as
possible and are able to handle the vast majority of use-cases, while at the
same time preventing the classic memory bugs such as use-after-free,
double-free or memory leaks.
Consequently, there is usually little need for the relatively small
additional comfort provided by a fully automated Garbage Collector (GC).
In the domain of concurrent lock-free data structures, however, the aforementioned memory management schemes are insufficient for determining, when a removed entry can be actually dropped and de-allocated: Just because an entry has been removed (unlinked) from some shared data structure does not guarantee, that no other thread could still be in the process of reading that same entry at the same time. This is due to the possible existence of stale references that were created by other threads before the unlinking occurred. The only fact that can be ascertained, due to nature of atomic swap and compare-and-swap operations, is that other threads can not acquire new references after an entry has been unlinked.
Concurrent memory reclamation schemes work by granting every value (record) earmarked for deletion (retired) a certain grace period before being actually dropped and de-allocated. During this period the value will be cached and can still be safely read by other threads with live references to it, but no new references must be possible. Determining the exact length of this grace period is up to each individual reclamation scheme. It is usually either not possible or not practical to determine the exact moment at which it becomes safe to reclaim a retired. Hence, reclamation schemes commonly tend to only guarantee grace periods that are at least as long as to ensure no references can possibly exist afterwards.
Lock-free data structures are usually required to work on atomic pointers to heap allocated memory. This is due to the restrictions of atomic CPU instructions to machine-word sized values, such as pointers. Working with raw pointers is inherently unsafe in the Rust sense. Consequently, this crate avoids and discourages the use of raw pointers as much as possible in favor of safer abstractions with stricter constraints for their usage. In effect, the vast majority of this crate's public API is safe to use under any circumstances. This, however, is achieved by shifting and concentrating the burden of manually maintaining safety invariants into one specific key aspect: The retiring (and eventual reclamation) of records.
reclaim crate primarily exposes four different traits, which are
relevant for users of generic code and implementors of reclamation schemes
The first trait is
Reclaim, which provides generic functionality for
Note, that this trait does not presume the presence of an operating system
and functionality like thread local storage.
Hence, this trait can even be used in
However, in order to use this trait's associated methods, an explicit
reference to the current thread's (local) state is required.
For environments with implicit access to thread local storage, the
GlobalReclaim trait exists as an extension to
This trait additionally requires an associated type
Guard, which must implement both the
Types implementing the
Protect trait can be used to safely read values
from shared memory that are subsequently safe from concurrent reclamation
and can hence be safely de-referenced.
Note that a single guard can only protect one value at a time.
This follows the design of many reclamation schemes, such as hazard
This is represented by the requirement to pass a mutable reference to a
guard in order to safely load a shared value.
Some reclamation schemes (e.g. epoch based ones) do not require individual
protection of values, but instead protect arbitrary numbers of shared at
The guard types for these schemes can additionally implement the
Such guards do not have to carry any state and protect values simply by
Consequently, it is also possible to call eg
Atomic::load with a shared
reference to a guard implementing that trait.
Atomic markable concurrent pointer type is the main point of
interaction with this crate.
It can only be safely created as a
null pointer or with valid heap
allocation backing it up.
It supports all common atomic operations like
The key aspect of this type is that together with a guard, shared values
can be safely loaded and de-referenced while other threads can concurrently
reclaim removed values.
In addition to the
Shared type, which represents a shared reference that
is protected from reclamation, other atomic operations can yield
The former are explicitly not protected from reclamation and can be loaded
without any guards.
They are not safe to de-reference, but can be used to e.g. swing a pointer
from one linked list node to another.
Unlinked values are the result of swap or compare-and-swap
operations and represent values/references to which no new references can be
acquired any more by other threads.
They are like owned values that are also borrowed, since other threads may
still reference them.
All of these three different types are guaranteed to never be null at the
It is a ubiquitous technique in lock-free programming to use the lower bits of a pointer address to store additional information alongside an address. Common use-cases are ABA problem mitigation or to mark a node of a linked list for removal.
Accordingly, this crate allows all pointer and reference types
Shared, etc.) to be marked.
The number of usable mark bits is encoded in the type itself as a generic
However, the number of available mark bits has a physical upper bound, which
is dictated by the alignment of the pointed-to type.
For instance, a
bool has an alignment of 1, hence pointers to boolean
values can not, in fact, be marked.
On a 64-bit system, an
usize has an alignment of 8, which means a pointer
to one can use up to 3 mark bits.
Since the number
N is encoded in the pointer types themselves, attempting
to declare types with more available mark bits than what the pointed-to
type's alignment will lead to a (currently fairly cryptic) compile time
Note, that tags are allowed to overflow. This can lead to surprising results
when attempting to e.g. mark a pointer that is declared to support zero mark
N = 0), as the tag will be silently truncated.
Throughout this crate's API and its documentation a certain terminology is consistently used, which is summarized below:
A heap allocated value which is managed by some reclamation scheme.
The act removing the pointer to a record from shared memory through an atomic operation such as compare-and-swap.
The act of marking an unlinked record as no longer in use and handing off the responsibility for de-allocation to the reclamation scheme.
The act of dropping and de-allocating a retired record. The reclamation scheme is responsible for guaranteeing that retired records are kept alive (cached) at least until their respective grace periods have expired.
Thin wrapper types for adjusting a type's alignment to increase the number of markable lower bits.
A no-op memory reclamation scheme that leaks memory, mainly for exemplary and testing purposes.
Useful and/or required types, discriminants and traits for the
An atomic markable pointer type to an owned heap allocated value similar to
A raw pointer type which can be safely shared between threads, which can store additional information in its lower (unused) bits.
A guard type fused with a protected value.
An error type for representing failed conversions from nullable to non-nullable pointer types.
A non-nullable marked raw pointer type like
A raw, unsafe pointer type like
A zero-size marker type that represents the failure state of an
A pointer type for heap allocated values similar to
A record type that is associated with a specific reclamation scheme.
A type-erased fat pointer to a retired record.
A shared reference to a value that is actively protected from reclamation by other threads.
A reference to a value that has been removed from its previous location in memory and is hence no longer reachable by other threads.
A reference to a value loaded from an
A value that represents the possible states of a nullable marked pointer.
A trait for retiring and reclaiming entries removed from concurrent collections and data structures.
Trait for nullable and non-nullable markable pointer types.
An sealed (internal) marker trait for non-nullable pointer types.
A trait for guard types that protect a specific value from reclamation during the lifetime of the protecting guard.
A trait for guard types that protect any values loaded during their existence and lifetime.
A trait, which constitutes the foundation for the
Result type for [