[][src]Crate hazptr

Hazard pointer based concurrent memory reclamation.

A difficult problem that has to be considered when implementing lock-free collections or data structures is deciding, when a removed entry can be safely deallocated. It is usually not correct to deallocate removed entries right away, because different threads might still hold references to such entries and could consequently access already freed memory.

Concurrent memory reclamation schemes solve that problem by extending the lifetime of removed entries for a certain grace period. After this period it must be impossible for other threads to have any references to these entries anymore and they can be finally deallocated. This is similar to the concept of Garbage Collection in languages like Go and Java, but with a much more limited scope.

The Hazard-pointer reclamation scheme was described by Maged M. Michael in 2004 [1]. It requires every read of an entry from shared memory to be accompanied by a global announcement marking the read entry as protected. Threads must store removed (retired) entries in a local cache and regularly attempt to reclaim all cached records in bulk. A record is safe to be reclaimed, once there is no hazard pointer protecting it anymore.

Reclamation Interface and Pointer Types

The API of this library follows the abstract interface defined by the reclaim crate. Hence, it uses the following types for atomically reading and writing from and to shared memory:

The primary type exposed by this API is Atomic, which is a shared atomic pointer with similar semantics to Option<Box<T>>. It provides all operations that are also supported by AtomicPtr, such as store, load or compare_exchange. All load operations on an Atomic return (optional) Shared references. Shared is a non-nullable pointer type that is protected by a hazard pointer and has similar semantics to &T. Read-Modify-Write operations (swap, compare_exchange, compare_exchange_weak) return Unlinked values if they succeed. Only values that are successfully unlinked in this manner can be retired, which means they will be automatically reclaimed at some some point when it is safe to do so. Unprotected is useful for comparing and storing values, which do not need to be de-referenced and hence don't need to be protected by hazard pointers.


The atomic compare_exchange method of the Atomic type is highly versatile and uses generics and (internal) traits in order to achieve some degree of argument overloading. The current and new arguments accept a wide variety of pointer types, interchangeably.

For instance, current accepts values of either types Shared, Option<Shared>, or Marked<Shared>. The same range of types and wrappers is also accepted for Unprotected values. A compare-and-swap can only succeed if the current value is equal to the value that is actually stored in the Atomic. Consequently, the return type of this method adapts to the input type: When current is either a Shared or an Unprotected, the return type is Unlinked, since all of these types are non-nullable. However, when current is an Option, the return type is Option<Unlinked>.

The new argument accepts types like Owned, Shared, Unlinked, Unprotected or Option thereof. Care has to be taken when inserting a Shared in this way, as it is possible to insert the value twice at different positions of the same collection, which violates the primary reclamation invariant (which is also the reason why retire is unsafe): It must be impossible for a thread to read a reference to a value that has previously been retired.

When a compare-and-swap fails, a struct is returned that contains both the actual value and the value that was attempted to be inserted. This ensures that move-only types like Owned and Unlinked can be retrieved again in the case of a failed compare-and-swap. The actually loaded value is returned in the form a MarkedPtr.

The other methods of Atomic are similarly versatile in terms of accepted argument types.

Pointer Tagging

Many concurrent algorithms require the use of atomic pointers with additional information stored in one or more of a pointer's lower bits. For this purpose the reclaim crate provides a type-based generic solution for making pointer types markable. The number of usable lower bits is part of the type signature of types like Atomic or Owned. If the pointed-to type is not able to provide the required number of mark bits (which depends on its alignment) this will lead to a compilation error. Since the number of mark bits is part of the types themselves, using zero mark bits also has zero runtime overhead.


pub use reclaim;
pub use reclaim::typenum;



Hazard Pointer based reclamation scheme.

Type Definitions


A specialization of Atomic for the HP reclamation scheme.


A guarded pointer that can be used to acquire hazard pointers.


A specialization of Owned for the HP reclamation scheme.


A specialization of Shared for the HP reclamation scheme.


A specialization of Unlinked for the HP reclamation scheme.


A specialization of Unprotected for the HP reclamation scheme.