Hazard Pointers: Lock-Free Memory Reclamation Without GC
The Hook
Your lock-free stack works great — until you need to free popped nodes. Who frees the memory? Reference counting adds overhead. Epoch-based reclamation is coarse. Hazard pointers let each thread publish “I’m accessing this pointer” — the reclaimer waits until no hazards exist. Lock-free, wait-free, no GC needed.
The Thesis
Memory reclamation is the hard part of lock-free programming. You can’t free a node while another thread might still be reading it. Hazard pointers solve this with a simple protocol: threads publish “hazard pointers” to nodes they’re accessing; the reclaimer scans all hazards before freeing. Wait-free for readers, bounded for reclaimers.
The Science
The Problem
// Lock-free stack pop
Node* pop() {
Node* head = head_.load();
while (head && !head_.compare_exchange_weak(head, head->next)) {
// retry
}
// DANGER: Can we delete head here?
// Another thread might still be reading head->next!
return head;
}The problem: Thread A reads head, gets preempted. Thread B pops, frees head. Thread A resumes, dereferences freed memory → crash.
Hazard Pointers (Michael, 2004)
Core idea: Each thread publishes “I’m accessing this pointer” in a global hazard pointer array. Reclaimer checks all hazards before freeing.
// Global hazard pointer array
constexpr int MAX_THREADS = 128;
constexpr int HAZARDS_PER_THREAD = 2;
struct HazardPointers {
std::atomic<Node*> hazards[MAX_THREADS][HAZARDS_PER_THREAD];
std::atomic<int> active_threads;
// Thread registers a hazard
void protect(int thread_id, int hazard_slot, Node* ptr) {
hazards[thread_id][hazard_slot].store(ptr, std::memory_order_release);
}
// Thread clears hazard
void clear(int thread_id, int hazard_slot) {
hazards[thread_id][hazard_slot].store(nullptr, std::memory_order_release);
}
// Check if any thread protects ptr
bool is_protected(Node* ptr) {
for (int t = 0; t < MAX_THREADS; ++t) {
for (int h = 0; h < HAZARDS_PER_THREAD; ++h) {
if (hazards[t][h].load(std::memory_order_acquire) == ptr)
return true;
}
}
return false;
}
};Usage in Lock-Free Stack
class LockFreeStack {
std::atomic<Node*> head_;
HazardPointers hp_;
std::vector<Node*> retired_; // Per-thread retired list
void push(int value) {
Node* node = new Node(value);
node->next = head_.load();
while (!head_.compare_exchange_weak(node->next, node));
}
int pop() {
int thread_id = get_thread_id(); // Thread-local
while (true) {
Node* head = head_.load();
if (!head) return -1; // Empty
// Publish hazard
hp_.protect(thread_id, 0, head);
// Re-check (head might have changed)
if (head != head_.load()) {
hp_.clear(thread_id, 0);
continue;
}
// Try to pop
if (head_.compare_exchange_weak(head, head->next)) {
int value = head->value;
hp_.clear(thread_id, 0);
// Retire node
retired_.push_back(head);
if (retired_.size() >= 100) scan_and_delete();
return value;
}
hp_.clear(thread_id, 0);
}
}
void scan_and_delete() {
for (Node* node : retired_) {
if (!hp_.is_protected(node)) {
delete node;
} else {
// Keep for next scan
}
}
// Rebuild retired list with unprotected nodes
}
};Optimizations
1. Thread-Local Retired Lists + Global Scan
thread_local std::vector<Node*> thread_retired;
void retire(Node* node) {
thread_retired.push_back(node);
if (thread_retired.size() >= BATCH_SIZE) {
global_retired_list.push_back(thread_retired);
thread_retired.clear();
}
}
void global_scan() {
// Collect all retired lists
// Check each against all hazard pointers
// Delete unprotected
}2. Epoch-Based Alternative (Simpler, Coarser)
class EpochReclamation {
std::atomic<uint64_t> global_epoch{0};
thread_local uint64_t thread_epoch = 0;
thread_local std::vector<Node*> retired;
void enter() { thread_epoch = global_epoch.load(); }
void exit() { thread_epoch = 0; }
void retire(Node* n) { retired.push_back(n); }
void try_advance() {
if (global_epoch.compare_exchange_weak(epoch, epoch + 1)) {
// Scan all retired lists from epochs < epoch - 1
}
}
};Comparison
| Method | Reclamation Latency | Memory Overhead | Complexity | Throughput Impact |
|---|---|---|---|---|
| Hazard Pointers | Bounded (scan interval) | O(threads × hazards) | Medium | Low |
| Epoch-Based | Up to 2 epochs | O(threads) | Low | Very low |
| Reference Counting | Immediate | O(1) per node | Low | High (atomic inc/dec) |
| RCU | Grace period | O(CPUs) | High | Very low (readers) |
The Protocol: Implement Hazard Pointers
Step 1: Global Hazard Array
// Fixed-size array, cache-line aligned
struct alignas(64) HazardSlot {
std::atomic<Node*> ptr;
};
HazardSlot hazards[MAX_THREADS][HAZARDS_PER_THREAD];Step 2: Thread Registration
thread_local int my_thread_id = []() {
static std::atomic<int> next_id{0};
return next_id.fetch_add(1);
}();Step 3: Protect/Clear in Critical Sections
void access(Node* ptr) {
hp.protect(my_thread_id, 0, ptr);
// ... use ptr ...
hp.clear(my_thread_id, 0);
}Step 4: Retire and Scan
void retire(Node* n) {
thread_retired.push_back(n);
if (thread_retired.size() >= 64) {
scan_retired();
}
}
void scan_retired() {
for (auto it = thread_retired.begin(); it != thread_retired.end();) {
if (!hp.is_protected(*it)) {
delete *it;
it = thread_retired.erase(it);
} else {
++it;
}
}
}The Counterpoint
- Scan overhead: O(hazards × retired) per scan
- Memory bloat: Retired nodes accumulate until scan
- Not wait-free for reclaimers: Scanning can take time
- ABA problem: Hazard pointers don’t solve ABA (need tagged pointers)
Practical Takeaway
Use hazard pointers when: Lock-free data structures, manual memory management, no GC. Use epoch-based when: Simpler, can tolerate longer reclamation latency. Use reference counting when: Simplicity > performance, low contention.
Libraries: libcds (C++), concurrent (Rust), liblfds (C), folly (Facebook).
Sources: Michael (2004) “Hazard Pointers”; Maged Michael “Hazard Pointers: Safe Memory Reclamation”; Dmitry Vyukov “Memory Reclamation”; Facebook Folly Hazptr; Rust crossbeam::epoch; Linux kernel RCU.