a hazard pointer
Imagine a shared library where, before you pick up a book to read it, you write your name on a public sign-out sheet next to that book's title. Anyone who wants to throw the book away first checks the sheet; if your name is there, they leave the book alone and come back later. Hazard pointers, invented by Maged Michael, are exactly this protocol for safe memory reclamation in lock-free code. Each thread publicly announces the pointers it is currently using, and no one frees a node that someone has announced.
Concretely, each thread owns a small fixed number of single-writer, multi-reader slots called its hazard pointers. The reader-side protocol is: before you dereference a node you loaded from the shared structure, you store that node's address into one of your hazard slots, and then you re-validate that the structure still points to it (because it might have changed between your load and your publish). Once published and re-validated, you may safely use the node — anyone scanning will see your reservation. When you remove a node, you do not free it; you add it to a per-thread retired list. Periodically you run a scan: collect every hazard pointer published by every thread into a set, then free only those retired nodes whose address is NOT in that set. Anything still hazarded stays on the list and is tried again next scan.
The honest trade-offs: hazard pointers make reclamation safe with bounded, predictable memory usage (only a small number of nodes can be in limbo per thread), and they tolerate a thread stalling. But they cost something on the read side — every protected access needs a store to publish the hazard plus a memory fence and a re-check — which is heavier than RCU's nearly-free reads. They are the go-to choice when you need bounded memory and robustness, for example in a long-running server that cannot afford the unbounded deferral some epoch schemes allow.
/* Reader: publish a hazard, then re-validate before using the node. */ for (;;) { Node *p = atomic_load(&head); hazard[my_id] = p; /* announce: I am using p */ if (atomic_load(&head) == p) break;/* re-check: still the same? then safe */ } use(p->data); hazard[my_id] = NULL; /* done: release the reservation */ /* Reclaimer: free a retired node only if no thread has it hazarded. */
Publish-then-revalidate guards against the node being freed between the load and the announcement; the scan refuses to free anything still hazarded.
Hazard pointers bound the memory in limbo and tolerate stalled threads, but add a store, a fence, and a re-check to every protected read — heavier than RCU's reads, lighter on memory than naive epoch schemes.