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 . 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.
The API of this library follows the abstract interface defined by the
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
It provides all operations that are also supported by
AtomicPtr, such as
All load operations on an
Atomic return (optional)
Shared is a non-nullable pointer type that is protected by a hazard
pointer and has similar semantics to
Read-Modify-Write operations (
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
compare_exchange method of
Atomic type is highly versatile and uses generics and (internal)
traits in order to achieve some degree of argument overloading.
new arguments accept a wide variety of pointer types,
current accepts values of either types
The same range of types and wrappers is also accepted for
A compare-and-swap can only succeed if the
current value is equal to
the value that is actually stored in the
Consequently, the return type of this method adapts to the input type:
current is either a
Shared or an
Unprotected, the return
Unlinked, since all of these types are non-nullable.
current is an
Option, the return type is
new argument accepts types like
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
is returned that contains both the actual value and the value that was
attempted to be inserted.
This ensures that move-only types like
Unlinked can be
retrieved again in the case of a failed compare-and-swap.
The actually loaded value is returned in the form a
The other methods of
Atomic are similarly versatile in terms of
accepted argument types.
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
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.
Hazard Pointer based reclamation scheme.
A guarded pointer that can be used to acquire hazard pointers.