Hazptr

Hazard pointer based concurrent lock-free memory reclamation.

Whenever a thread reads a value from shared memory it also protects the loaded value with a globally visible hazard pointer. All threads can retire shared values that are no longer needed and accessible and cache them locally. Retired records are reclaimed (dropped and de-allocated) in bulk, but only when they are not or no longer protected by any hazard pointers.

Usage

Add this to your Cargo.toml

[dependencies]
hazptr = "0.2.0"

Minimum Supported Rust Version (MSRV)

The minimum supported Rust version for this crate is 1.36.0.

Comparison with crossbeam-epoch

The hazard pointer reclamation scheme is generally less efficient then epoch-based reclamation schemes (or any other type of reclamation scheme for that matter). This is mainly because acquisition of hazard pointers requires an expensive memory fence to be issued after every load from shared memory. It is, however, usually the best scheme in terms of reclamation reliability. Retired records are generally reclaimed in a timely manner and reclamation is not affected by contention. These properties can lead to a better memory footprint of applications using hazard pointers instead of other reclamation schemes. Also, since hazard pointers only protect individual pointers from reclamation, they can be better suited for protecting individual records for long periods of time. Epoch-based schemes, on the other hand, completely prevent reclamation by all threads whenever records need to be protected.

Examples

See examples/treiber/stack.rs for an implementation of Treiber's stack with hazard pointers or examples/hash_set/ordered.rs for an implementation of a concurrent hash set.

Crate Features & Runtime Configuration

The following features are defined for this crate:

• std (default)
• count-release

By default, a thread initiates a GC scan and attempts to flush its cache of retired records, once it has retired a certain threshold count of records. By compiling the crate with the count-release feature, this can be changed to count the instances of successfully acquired hazard pointers Guards going out of scope (i.e. being released) instead. This can be beneficial, e.g. when there are only few records overall and their retirement is rare.

Scan Threshold

The scan threshold value is used internally for determining the frequency of GC scans. These scans traverse the thread local list of retired records and reclaim all records which are no longer protected by any hazard pointers. This threshold variable can be any positive non-zero 32-bit integer value and is set to 100 by default. It can be set to a different value exactly once during the runtime of the program. Note that only threads that are spawned after setting this variable will be able to use the adjusted value. The following code gives an example for how to adjust this value:

use hazptr::{ConfigBuilder, CONFIG};

fn main() {
    // preferably this should be called before spawning any threads
    CONFIG.init_once(|| ConfigBuilder::new().scan_threshold(512).build());
}

A scan threshold of 1 means, for example, that a GC scan is initiated after every operation counting towards the threshold, meaning either operations for retiring records or releases of Guards, in case the count-release feature is enabled. The env var can be specified e.g. by invoking cargo with:

env HAZPTR_SCAN_THRESHOLD=1 cargo build

Alternatively, this variable could also be set as part of a build script:

// build.rs

fn main() {
    // alternative: std::env::set_var("HAZPTR_SCAN_THRESHOLD", "1")
    println!("cargo:rustc-env=HAZPTR_SCAN_THRESHOLD=1");
}

It is necessary to call cargo clean, before attempting to change this variable once set, in order to force a rebuild with the new value.

As a general rule, a higher scan threshold is better performance-wise, since threads have to attempt to reclaim records less frequently, but could lead to the accumulation of large amounts of garbage and also degrade performance.

Usage in #[no_std] environments

When building the crate without the (default) std feature, it becomes possible to use its functionality in an #[no_std] + alloc environment, albeit with arguably worse ergonomics. In this configuration, the crate's public API additionally exposes the Local type. Also, instead of exporting the Guard type, a different LocalGuard type is exported, which contains an explicit reference to the thread local state.

In order to use hazptr in such an environment, one has to manually to do the following steps:

• for every thread, create a separate Local instance
• hazard pointers can only be created by explicitly passing a reference to the current thread's Local instance

License

Hazptr is distributed under the terms of both the MIT license and the Apache License (Version 2.0).

See LICENSE-APACHE and LICENSE-MIT for details.