Lock-Free Stack with AtomicPtr

Treiber Stack With compare_exchange

Lock-free structures avoid mutexes by retrying atomic compare-and-swap (CAS) loops. crossbeam and tokio queues build on the same primitives you practice on a Treiber stack.

rustCopy
Loading…

• AtomicPtr: thread-safe pointer reads/writes
• Ordering::Acquire/Release: publish/consume pairs between threads
• Push: swing head to a new node whose next was the old head
• Pop: read head, read next, CAS head forward; retry on contention

ABA Is the Gotcha

A popped node can be reallocated at the same address, fooling a naive CAS. Production code uses tagged pointers, hazard pointers, or epoch reclamation (crossbeam-epoch).

For this exercise, you will implement push/pop on a lock-free stack with AtomicPtr. This task asks you to retry failed CAS loops correctly, because a broken stack manifests as rare lost nodes under load, the worst concurrency failure mode.

Keep the relevant man page, ABI doc, or Rust reference chapter open while you work. When your output disagrees with the reference implementation on the same machine, the mismatch is usually an alignment rule, an off-by-one terminator, or a register slot you misread in GDB. Skim the official documentation for the tool or ABI named in the exercise; the prose changes, but register roles, syscall numbers, and ownership rules stay stable across releases.