We touched on hazard pointers as a method for safe memory reclamation in the previous chapter. We'll now examine the concept in-depth and in the context of a more or less ready-to-use implementation via the Redox project (https://crates.io/crates/conc). We'll be inspecting conc as a part of its parent project, tfs (https://github.com/redox-os/tfs), at SHA 3e7dcdb0c586d0d8bb3f25bfd948d2f418a4ab10. Incidentally, if you're unfamiliar with this, Redox is a Rust microkernel-based operating system. The allocator, coreutils, and netutils are all encouraged reading.

Hazard pointers were introduced by Maged Michael—of Michael and Scott Queue fame—in his 2004 book, Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects. A hazard, in this context, is any pointer that is subject to races or ABA issues in the rendezvous of multiple treads participating in some shared data structure. In the previous section's Treiber stack, the hazard is the head pointer inside of the Stack struct, and in the Michael and Scott queue, it is the head and tail pointers. A hazard pointer associates these hazards with single-writer multireader shared pointers, owned by a single writer thread and read by any other threads participating in the data structure.

Every participating thread maintains a reference to its own hazard pointers and all other participating threads in addition to private, thread-local lists for the coordination of deallocation. The algorithm description in section 3 of Michael's paper is done at a high level and is difficult to follow with an eye towards producing a concrete implementation. Rather than repeat that here, we will instead examine a specific implementation, conc. The reader is encouraged to read Michael's paper ahead of the discussion of conc, but this is not mandatory.