LC

Fix ABA Problem Using Stamped Reference or Hazard Pointers

hard3/8

Implement Lock-Free Stack Using Compare-And-Swap Implement Lock-Free Queue (Michael-Scott Queue)

Language

Compiler

2.0s Limit 256MB

Implementation

Demonstrate and fix ABA problem using stamped references.

Requirements:

Implement stack WITHOUT stamped references (buggy)
Show ABA problem with 2 threads
Implement StampedPtr structure with version number
Fix stack using stamped references
Demonstrate fix prevents ABA
Use atomic operations with CAS
Show encode/decode for stamped pointer
Test with high thread count
Print before/after comparison
Explain why version numbers fix ABA

Why This Matters

The ABA problem is a real memory-safety bug class, not a theoretical curiosity — it's exactly why the Windows kernel's SLIST and .NET's ConcurrentStack use double-width CAS with a tagged version counter instead of a bare pointer. Facebook's folly library and Linux's RCU-based structures use hazard pointers or epoch-based schemes for the same reason: a freed-and-reallocated node fooling a CAS is a use-after-free in production, not just a benchmark curiosity.

Hints

0 / 3 revealed

Validation Suite

main.c

Workspace 1.0