http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p1121r3.pdf https://github.com/facebook/folly/tree/0e92d3c2705a45ba7850708fd7fe0c709d6a0e5f

License

Licensed under Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0).

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be licensed as above, without any additional terms or conditions.

lib.rs:

Dynamic memory management for lock-free data structures.

This library implements the hazard pointer memory reclamation mechanism, specifically as proposed for the C++ Concurrency Technical Specification. It is adapted from the implementation found in Facebook's Folly library. The initial phases of implementation were all live streamed.

At a high level, hazard pointers provide a mechanism that allows readers of shared pointers to prevent concurrent reclamation of the pointed-to objects by concurrent writers for as long as the read operation is ongoing. When a writer removes an object from a data structure, it instructs the hazard pointer library that said object is no longer reachable (that it is retired), and that the library should eventually drop said object (reclaim it) once it is safe to do so. Readers, meanwhile, inform the library any time they wish to read through a pointer shared with writers. Internally, the library notes down the address that was read in such a way that it can ensure that if the pointed-to object is retired while the reader still has access to it, it is not reclaimed. Only once the reader no longer has access to the read pointer does the library allow the object to be reclaimed.

TODO: Can also help with the ABA problem (ensure object isn't reused until there are no pointers to it, so cannot "see" A again until there are no As left).

For an overview of concurrent garbage collection with hazard pointers, see "Fearless concurrency with hazard pointers". Aaron Turon post on "Lock-freedom without garbage collection" which discusses the alternate approach of using epoch-based reclamation (see below) is also a good reference.

High-level API structure

TODO: Ref section 3 of the proposal and folly's docs.

Hazard pointers vs. other deferred reclamation mechanisms

TODO: Ref sections 3.4 and 4 of the proposal and section from folly's docs.

Note esp. memory usage.

Examples

TODO: Ref section 5 of the proposal and example from folly's docs.

use haphazard::{AtomicPtr, Domain, HazardPointer};

// First, create something that's intended to be concurrently accessed.
let x = AtomicPtr::from(Box::new(42));

// All reads must happen through a hazard pointer, so make one of those:
let mut h = HazardPointer::new();

// We can now use the hazard pointer to read from the pointer without
// worrying about it being deallocated while we read.
let my_x = x.safe_load(&mut h).expect("not null");
assert_eq!(*my_x, 42);

// We can willingly give up the guard to allow writers to reclaim the Box.
h.reset_protection();
// Doing so invalidates the reference we got from .load:
// let _ = *my_x; // won't compile

// Hazard pointers can be re-used across multiple reads.
let my_x = x.safe_load(&mut h).expect("not null");
assert_eq!(*my_x, 42);

// Dropping the hazard pointer releases our guard on the Box.
drop(h);
// And it also invalidates the reference we got from .load:
// let _ = *my_x; // won't compile

// Multiple readers can access a value at once:

let mut h = HazardPointer::new();
let my_x = x.safe_load(&mut h).expect("not null");

let mut h_tmp = HazardPointer::new();
let _ = x.safe_load(&mut h_tmp).expect("not null");
drop(h_tmp);

// Writers can replace the value, but doing so won't reclaim the old Box.
let old = x.swap(Box::new(9001)).expect("not null");

// New readers will see the new value:
let mut h2 = HazardPointer::new();
let my_x2 = x.safe_load(&mut h2).expect("not null");
assert_eq!(*my_x2, 9001);

// And old readers can still access the old value:
assert_eq!(*my_x, 42);

// The writer can retire the value old readers are seeing.
//
// Safety: this value has not been retired before.
unsafe { old.retire() };

// Reads will continue to work fine, as they're guarded by the hazard.
assert_eq!(*my_x, 42);

// Even if the writer actively tries to reclaim retired objects, the hazard makes readers safe.
let n = Domain::global().eager_reclaim();
assert_eq!(n, 0);
assert_eq!(*my_x, 42);

// Only once the last hazard guarding the old value goes away will the value be reclaimed.
drop(h);
let n = Domain::global().eager_reclaim();
assert_eq!(n, 1);

// Remember to also retire the item stored in the AtomicPtr when it's dropped
// (assuming of course that the pointer is not shared elsewhere):
unsafe { x.retire(); }

Differences from the specification

Differences from the folly

TODO: Note differences from spec and from folly. Among other things, see this note from folly.