Crate reclaim

A generic trait based interface for abstracting over various schemes for concurrent memory reclamation.

Memory Management in Rust

Unlike garbage collected languages such as Go or Java, memory management in Rust is primarily scope or ownership based 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 memory leaks. Consequently, there is usually little need for the relatively 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 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.

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 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.

The Reclaim Interface

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.

Traits and Types

The reclaim crate primarily exposes four different traits, which are relevant for users of generic code and implementors of reclamation schemes alike. The first trait is Reclaim, which provides generic functionality for retiring records. 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 #[no_std] environments. 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 Reclaim. This trait additionally requires an associated type Guard, which must implement both the Default and the Protect trait.

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 pointers. 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 once. The guard types for these schemes can additionally implement the ProtectRegion trait. Such guards do not have to carry any state and protect values simply by their existence. Consequently, it is also possible to call eg Atomic::load with a shared reference to a guard implementing that trait.

The Atomic Type

The 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 load, store, compare_exchange, etc. 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 Unprotected or Unlinked values. 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 type level.

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.
• Guarded
  A guard type fused with a protected value.
• 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][Protect::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

• GlobalReclaim
  A trait for retiring and reclaiming entries removed from concurrent collections and data structures.
• MarkedPointer
  Trait for nullable and non-nullable markable pointer types.
• NonNullable
  An sealed (internal) marker trait for non-nullable pointer types.
• Protect
  A trait for guard types that protect a specific value from reclamation during the lifetime of the protecting guard.
• ProtectRegion
  A trait for guard types that protect any values loaded during their existence and lifetime.
• Reclaim
  A trait, which constitutes the foundation for the GlobalReclaim trait.

Type Aliases

• AcquireResult
  Result type for [acquire_if_equal][Protect::acquire_if_equal] operations.