[−][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.
Compare-and-Swap
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.
Re-exports
pub use reclaim; |
pub use reclaim::typenum; |
Structs
HP | Hazard Pointer based reclamation scheme. |
Type Definitions
Atomic | |
Guard | A guarded pointer that can be used to acquire hazard pointers. |
Owned | |
Shared | |
Unlinked | |
Unprotected | A specialization of |