Crate reclaim

An abstract & generalized interface supporting various schemes for concurrent memory reclamation.

Memory Management in Rust

Unlike garbage collected languages such as Go or Java, memory management in Rust is ultimately manual and more akin to C++. Rust's ownership model in combination with the standard library's smart pointer types Box, Rc and 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 access to dangling pointers/references. Consequently, there is usually little need for the small additional comfort provided by a fully automated Garbage Collector (GC).

The Need for Automatic Memory Reclamation

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 be in the process of reading that same entry at the same time. This is due to the possibility of stale references that were created before the unlinking occurred. The only thing 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.

Extending the Grace Period

Concurrent memory reclamation schemes work by granting every value (record) earmarked for deletion (retired) a certain grace period before being actually dropped and deallocated, during which it is cached and can still be safely read by other threads with live references to it. How to determine the length of this grace period is up to each individual reclamation scheme.

The Reclaim Interface

Due to the restrictions of atomic instructions to machine-word sized chunks of memory, lock-free data structures are necessarily required to work with pointers as well, which is inherently unsafe. Nonetheless, this crate attempts to provide abstractions and an API that encapsulates this unsafety behind safe interface as much as possible. Consequently, the majority of functions and methods exposed are safe to call and can not lead to memory-unsafety.

This is primarily achieved by shifting the burden of explicitly maintaining safety invariants to the process of actually reclaiming allocated records. Also construction and insertion into shared variables (Atomic) is only safely allowed with valid (heap allocated) values. All values that are read from shared variables have reference semantics and are non-nullable, although not all types can be safely de-referenced. The Option and Marked wrapper types are used to ensure null pointer safety. Under these circumstances, memory-unsafety (e.g. use-after-free errors) can only be introduced by incorrectly retiring (and hence reclaiming) memory, which is consequently unsafe.

Marked Pointer & Reference Types

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 (MarkedPtr, Shared, etc.) to be marked. The number of usable mark bits is encoded in the type itself as a generic parameter N. 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 error. 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 bits (N = 0), as the tag will be silently truncated.

Terminology

Throughout this crate's API and its documentation a certain terminology is consistently used, which is summarized below:

• record

  A heap allocated value which is managed by some reclamation scheme.

• unlink

  The act removing the pointer to a record from shared memory through an atomic operation such as compare-and-swap.

• retire

  The act of marking an unlinked record as no longer in use and handing off the responsibility for de-allocation to the reclamation scheme.

• reclaim

  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.

Re-exports

pub use typenum;

Modules

align	Thin wrapper types for adjusting a type's alignment to increase the number of markable lower bits.
leak	A no-op memory reclamation scheme that leaks memory, mainly for exemplary and testing purposes.
prelude	Useful and/or required types, discriminants and traits for the reclaim crate.

Structs

Atomic	An atomic markable pointer type to an owned heap allocated value similar to AtomicPtr.
AtomicMarkedPtr	A raw pointer type which can be safely shared between threads, which can store additional information in its lower (unused) bits.
CompareExchangeFailure	The returned error type for a failed compare_exchange or compare_exchange_weak operation.
InvalidNullError	An error type for representing failed conversions from nullable to non-nullable pointer types.
MarkedNonNull	A non-nullable marked raw pointer type like NonNull.
MarkedPtr	A raw, unsafe pointer type like *mut T in which up to N of the pointer's lower bits can be used to store additional information (the tag).
NotEqualError	A zero-size marker type that represents the failure state of an acquire_if_equal operation.
Owned	A pointer type for heap allocated values similar to Box.
Record	A record type that is associated with a specific reclamation scheme.
Retired	A type-erased fat pointer to a retired record.
Shared	A shared reference to a value that is actively protected from reclamation by other threads.
Unlinked	A reference to a value that has been removed from its previous location in memory and is hence no longer reachable by other threads.
Unprotected	A reference to a value loaded from an Atomic that is not actively protected from reclamation.

Enums

Marked

A value that represents the possible states of a nullable marked pointer.

Traits

LocalReclaim	A trait, which constitutes the foundation for the Reclaim trait.
MarkedPointer	Trait for nullable and non-nullable markable pointer types.
NonNullable	An sealed (internal) marker trait for non-nullable pointer types.
Protect	A trait applicable for pointer types that protect their pointed-to value from reclamation during the lifetime of the protecting guard.
Reclaim	A trait for retiring and reclaiming entries removed from concurrent collections and data structures.

Type Definitions

AcquireResult

Result type for acquire_if_equal operations.