Fix ABA Problem Using Stamped Reference or Hazard Pointers

When CAS Sees a Ghost Head

ABA bites when a CAS compares only the pointer value, not the generation. Thread A reads head H, stalls, other threads pop H and push a new node that reuses the same address H. A's CAS succeeds even though the stack changed underneath.

Mitigations

Tagged pointers (version in high bits), hazard pointers, epoch reclamation, or never freeing nodes until quiescence. Windows uses a per-stack sequence counter in SLIST_HEADER.

cCopy
Loading…

• Memory pools make address reuse common, worsening ABA
• 32-bit tags wrap; size tag field for expected concurrency depth
• Michael-Scott queue needs careful ABA handling on both head and tail
• Test with deliberate node recycling to expose the bug

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

• Trace first: walk one failing input step by step
• Read the manual: skim the official doc for the mechanism named in this task
• Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will demonstrate ABA on a naive lock-free stack and fix it with tagged pointers or a hazard-pointer scheme. This exercise asks you to show a failing scenario and a corrected one.