Hazard Pointers for Memory Reclamation
What you'll learn: How hazard pointers let threads safely reclaim memory in lock-free data structures by announcing which nodes they're currently accessing.
The Core Problem
In lock-free data structures, you can't just free memory when you remove a node—another thread might still be reading it! The memory reclamation problem (from the previous lesson) asks: when is it safe to actually delete memory?
How Hazard Pointers Work
Think of hazard pointers like "Do Not Disturb" signs on hotel rooms. Before a thread accesses a node, it places a hazard pointer on it—announcing to all other threads: "I'm using this, don't delete it!"
Here's the process:
- Before reading: Thread announces the pointer it's about to access by storing it in a hazard pointer (a shared location)
- Access safely: The thread can now read the node knowing no one will free it
- After reading: Thread clears its hazard pointer
- Deferred deletion: When removing a node, threads don't immediately free it—they add it to a "retire list"
- Safe reclamation: Periodically, threads scan all active hazard pointers. Any retired node not in the hazard pointer list is safe to free
The Safety Guarantee
A node can only be reclaimed when zero threads have hazard pointers pointing to it. This creates a happens-before relationship: all accesses complete before reclamation.
Key Takeaway: Hazard pointers solve the memory reclamation problem by letting threads explicitly mark which memory they're using, deferring deletion until no thread has announced interest in that memory.