Prompt and context
You have a high-contention lock-free stack whose nodes are linked by an atomic pointer. A thread reads and CAS-removes the head while another thread may free it. Design safe reclamation using the C++26 hazard_pointer model, allowing concurrent readers without a global lock around the stack.
What the interviewer is testing
Hazard pointers protect an address currently being read; they do not keep a node alive forever. A reader publishes a hazard, rechecks that the atomic head still names that node, and only then dereferences it. A removed node enters a retired list and is reclaimed only after scanning every hazard. Cover acquire/release, registration and exit, scan cost, and the fact that ABA needs separate protection.
Clarifying questions to ask first
Data structure and progress guarantee
Confirm whether this is a Treiber stack, linked list, or hash bucket, whether lock-free or wait-free progress is required, and whether thread-local retired lists are acceptable.
Thread lifetime
Ask how threads obtain hazard slots and how exit clears protection and transfers retired nodes. A crashed thread must not leave a permanent unreclaimable record.
ABA and tagging policy
Determine whether addresses can be reused and whether a version counter or tagged pointer is available. Hazard pointers prevent freeing a protected node but do not by themselves prevent ABA from making a CAS succeed incorrectly.
30-second answer framework
“The reader atomically loads head, publishes that address in its hazard slot, and loads head again; only an unchanged value may be dereferenced. After a successful CAS, the old node goes to a retired list instead of being deleted. A scan collects all hazard addresses and reclaims only retired nodes absent from that set. Use matching acquire/release semantics, clear the slot before thread exit, and handle ABA with a version or tag separately.”
Step-by-step deep answer
Step 1: Define hazard slots and retired lists
Each thread that may dereference shared nodes owns a hazard slot. A retired list holds nodes removed from the data structure but not yet safe to reclaim. Registration and slot ownership must be explicit so a temporary raw pointer cannot bypass protection.
Step 2: Establish the publish-and-validate window
Load head, publish it to the hazard slot with release or an equivalent ordering, then reload head with acquire. Dereference fields only when both values match; otherwise clear the slot and retry. This closes the gap in which another thread could remove and reclaim the node.
Step 3: CAS and defer reclamation
Read next and compare-exchange head. On CAS failure, clear the hazard and retry. On success, append the old node to the retired list and clear the slot only after the reader no longer needs the node. No path may directly delete a shared node.
Step 4: Scan and reclaim
Scan every thread’s hazard slot into a protected-address set. Traverse the retired list and reclaim only nodes absent from that set. Tune scan thresholds from slot count and retired-list length. A compliant reader’s publish-and-validate protocol ensures a node cannot become unprotected before the scan sees its hazard.
Step 5: Handle ABA and memory ordering
Deferred reclamation reduces address reuse but does not eliminate ABA. If a node can be removed and reinserted quickly, use a version counter, tagged pointer, or another ABA defense. Define the happens-before relationships for atomic head, hazard slots, and node fields; relaxed operations must not be used merely for speed without proof.
Step 6: Handle thread exit and exceptions
Clear the hazard before stopping reads, then transfer retired nodes to a live reclaimer or shared domain. The registry needs an owner state that can detect exit and avoid abandoned slots. Destruction runs only after no reader can reach the node; ordinary object-lifetime assumptions are insufficient.
Step 7: Test safety and performance
Use ThreadSanitizer, randomized scheduling, and stress tests for CAS failure, concurrent scans, thread exit, reuse, and exceptions. Add delayed-free sentinels to detect use-after-free. Measure scan time, retired-list peak, throughput, and tail latency, then tune batch thresholds instead of adding a global lock.
High-quality sample answer
I would give each reader a hazard slot. pop loads head, publishes the hazard, reloads head, and only then reads next and attempts CAS; a changed value clears the slot and retries. A successful removal enters a retired list, and a scan of all hazard addresses reclaims only unprotected nodes. Thread exit clears and transfers its slot. ABA uses a version or tagged pointer separately. Tests cover contention, CAS failures, reuse, exit, and exceptions while checking use-after-free and scan cost.
Common mistakes
- Mistake: Dereferencing head immediately after the first load. → Why it fails: The node may be reclaimed before protection is published. → Fix: Publish the hazard and validate head again.
- Mistake: Deleting after a successful CAS. → Why it fails: Another reader may still be in its protection window. → Fix: Retire first, scan, then reclaim.
- Mistake: Assuming hazard pointers solve ABA. → Why it fails: Delayed free does not guarantee logical version stability. → Fix: Add a version counter or tagged pointer.
- Mistake: Using only relaxed atomics. → Why it fails: Publication and validation may not be visible in the required order. → Fix: Prove acquire/release and happens-before relationships.
Follow-up questions and answers
Follow-up 1: Why reload head after publishing?
There is a window between the first load and publishing the hazard in which another thread may remove and reclaim the node. The reload proves the node is still the current head under protection; otherwise retry.
Follow-up 2: Can a scan miss a hazard published during the scan?
The protocol requires a reader to publish before validating and to retry when validation fails. With that protocol, only retired nodes absent from the protected set are reclaimed; an unprotected raw-pointer reader is outside the guarantee.
Follow-up 3: Can the retired list grow without bound?
It can grow when readers hold hazards for a long time, a thread stops, or scans are too infrequent. Set thresholds, monitor the peak, clean up on exit, and let a reclaimer scan proactively when needed.
Follow-up 4: When choose hazard pointers over epoch-based reclamation?
Hazard pointers precisely protect a small number of addresses and fit dynamic read paths, but scanning slots costs CPU. Epoch reclamation batches efficiently but can be held back by a stalled thread. Choose from reader count, stall tolerance, and memory limits.