Lock-Free Stack with AtomicPtr

Topic Overview

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.

Your Task

A lock-free Treiber stack is a single AtomicPtr<Node> updated with compare-and-swap. It is famous for the ABA problem. A thread reads head = A and A.next = B. Meanwhile A and B are popped and freed, and A's memory is reused for a new push, so the CAS "head is still A" succeeds and installs the dangling B. Real thread timing is not reproducible, so this task makes the interleaving explicit: you run each thread's atomic steps in the order given by a schedule, in two modes. plain compares only the pointer. tagged compares a pointer plus a version counter, the classic fix.

Input

cCopy
Loading…

Nodes are numbered #1, #2, … as they are first allocated, and there are at most 32. Freed nodes are reused in the order they were freed (FIFO), before any new number. Values are in -1000000..1000000.

Atomic steps

push V

1. load: on the first attempt, allocate its node. Set old = head and node.next = old.
2. CAS: if head still equals old, set head = node and the op is done. Otherwise go back to step 1 (keeping the node).

pop

1. load: old = head. If it is null, the op returns None immediately.
2. read: next = old.next (this reads a freed node if old was freed meanwhile).
3. CAS: if head still equals old, set head = next, return old.value, and free old. Otherwise go back to step 1.

In tagged mode, head also carries a tag. Every successful CAS increments it, and a CAS succeeds only if the pointer and the tag match. init does not change the tag (it starts at 0).

Output

One line per step, prefixed with NAME OP: (e.g. T1 pop: or T2 push 9: ):

cCopy
Loading…

In tagged mode, head values print as #3/t2: the load shows the current tag, and a CAS shows old/tag -> new/tag+1. .next pointers never show a tag. A step for a thread with no ops left prints NAME: finished.

The stack prints as stack: 3(#3) 2(#2) 1(#1) from the top, or stack: empty. If the walk reaches a free node, it prints #N FREED (corrupted) and stops.

Errors: error: mode is plain or tagged, error: bad value V, error: out of nodes, error: bad thread (missing, too long (over 15 characters), duplicate or too many), error: bad script for NAME (the thread is not created), error: no thread NAME, error: unknown command CMD. A push that cannot allocate prints out of nodes, skipped.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Model memory reuse exactly (FIFO free list). ABA only happens because the address comes back.
2. Keep each thread's local state (old, tag, next, its node) between steps, as a real thread keeps registers between its atomic instructions.

Hidden tests cover the same ABA schedule in tagged mode (the CAS fails and retries), contention between two pushers, pops on an empty stack, and malformed commands.