The question this answers
How does a CAS on a single head pointer implement a whole stack operation, and what does the simplified version leave out?
Several producer threads pushing work items onto a shared stack, and several consumers popping them, with no mutex anywhere.
One head pointer, and the chain of nodes reachable from it.
Every successfully pushed node is reachable from head exactly once until it is popped, and no two pops ever return the same node.
Synchronization exists to preserve this sentence. If a schedule can make it false, the code is wrong no matter which primitive it uses.
Push: build the node privately, then swing the head
The structure is a singly linked list with the head as the only shared mutable location — see Singly Linked List for the shape and Stack for the semantics. Push works because everything expensive is private: you allocate the node and set its payload while no other thread can see it, so the only shared step is one pointer write. Making that one write conditional is what makes the whole operation safe.
The order inside the loop is the entire trick. Read the current head. Point your new node's next at it. CAS the head from that value to your node. If the CAS fails, another thread pushed or popped in between, so your next is stale — re-read and re-link before trying again. Writing next once outside the loop is the classic beginner bug and produces a stack that silently loses nodes.
Pop is the harder half, and the code below shows why in a comment rather than pretending otherwise: to pop you must read head->next, which means dereferencing a node another thread may be about to pop and free. Everything hard about lock-free data structures is contained in that sentence.
1template <class T>2struct Node { T value; Node* next; };3 4template <class T>5class TeachingStack {6 std::atomic<Node<T>*> head{nullptr};7public:8 void push(T v) {9 Node<T>* n = new Node<T>{std::move(v), nullptr}; // private: nobody can see n yet10 n->next = head.load(std::memory_order_relaxed);11 // release: everything written to *n above must be visible to a thread12 // that acquires this head. See safe-publication.13 while (!head.compare_exchange_weak(n->next, n,14 std::memory_order_release,15 std::memory_order_relaxed)) {16 // CAS wrote the CURRENT head into n->next for us, so n is already17 // re-linked correctly and the next attempt is against fresh state.18 }19 }20 21 bool pop(T& out) {22 Node<T>* old = head.load(std::memory_order_acquire);23 while (old) {24 // DANGER: another thread may pop and free 'old' between this load25 // and the dereference below. This line is the whole reclamation26 // problem, and this class does not solve it.27 Node<T>* next = old->next;28 if (head.compare_exchange_weak(old, next,29 std::memory_order_acquire,30 std::memory_order_relaxed)) {31 out = std::move(old->value);32 // ...and we still must not 'delete old' here. See section three.33 return true;34 }35 }36 return false;37 }38};Two pushes racing, with and without the retry
The schedule below is the case the CAS exists for. Both threads read the same head. One wins. The loser's node still points at the old head, which is now buried one level down — so if the loser simply stored its node, the winner's node would be unreachable and its work would be lost with no error anywhere.
With the retry, the failed CAS hands the loser the head that actually exists, the loser re-links, and both nodes end up on the stack in some order. Note what "some order" means: the stack's ordering between concurrent pushes is not the wall-clock order in which the threads called push. That is not a bug, but it is a property callers assume without noticing. See Ordering Guarantees: Four Levels, Four Prices.
Notice that the winner and loser are not decided by who called push first — they are decided by who reached the CAS first. Any code that depends on push order between concurrent threads is depending on the scheduler, which is Nondeterminism: Same Input, Different Output by another name.
| # | Producer 1 (node A) | Producer 2 (node B) | State |
|---|---|---|---|
| 1 | load head -> X; A.next = X | · | head=X A.next=X |
| 2 | · | load head -> X; B.next = X | head=X A.next=X B.next=X |
| 3 | CAS(head, expected=X, desired=A) -> success | · | head=A A.next=X |
| 4 | · | CAS(head, expected=X, desired=B) -> FAILS; expected now A | head=A B.next=X |
| 5 | · | re-link B.next = A; CAS(head, expected=A, desired=B) -> success | head=B B.next=A A.next=X |
| 6 | · | [no-retry version] store head = B directly | head=B B.next=X ✕ A is no longer reachable from head. A successful push vanished, the caller was told it succeeded, and the node leaks. |
Everything the teaching version leaves out
The code above will pass a casual test suite and lose data in production. Not because the CAS logic is wrong — it is correct — but because a lock-free container has obligations a locked one does not, and every one of them is invisible until it fails.
The largest is memory reclamation. After a successful pop you hold a node that some other thread may be reading ->next from right now, because it loaded the head before your CAS and has not yet dereferenced. Freeing it is a use-after-free. Never freeing it is a leak. The real answers are hazard pointers (each thread publishes what it is currently reading, and reclamation skips those), epoch-based reclamation (free only what no thread could have been reading in a previous epoch), or a garbage collector doing it for you — which is why lock-free structures are meaningfully easier in Java, C# and JavaScript.
The second is ABA, which pop is exposed to and which is a whole lesson: The ABA Problem: The Value Came Back. The remainder — memory ordering, allocation inside the loop, cache-line contention on the head, exception safety when T's move constructor throws — are each capable of producing a bug that survives months of testing. The engineering conclusion is unglamorous and correct: use a reviewed library implementation, or use a mutex.
| Omitted concern | How it fails | What production implementations use |
|---|---|---|
| Memory reclamation | A popped node is freed while another thread is reading its next — use-after-free, often a crash far from the cause | Hazard pointers, epoch/quiescent-state reclamation, RCU, or a tracing GC |
| ABA on pop | CAS succeeds because the head pointer returned to the same address; head is set to an already-popped node | Version-tagged pointers with double-width CAS, or reclamation schemes that prevent address reuse |
| Memory ordering | A consumer sees the node before its payload is visible — a fully constructed object read as garbage | Explicit release on publish, acquire on read — see Safe Publication: Handing Over a Finished Object |
| Allocation in the loop | Every retry may allocate, and the allocator itself takes a lock, defeating the progress guarantee | Preallocated node pools, freelists that are themselves lock-free |
| Head-line contention | Every push and pop needs exclusive ownership of the same cache line; throughput collapses with core count | Elimination arrays, backoff, or a different structure entirely |
| Exception safety | A throwing move constructor after a successful CAS leaves the item removed and lost | Move the value out before committing, or require a non-throwing move |
| Size and emptiness | size() and empty() are stale the instant they return | Do not offer them, or document them as hints only |
Key points
- Push is safe because all the work is private and the only shared step is one conditional pointer write.
- The retry must re-link
nextfrom the head the failed CAS handed back; linking once outside the loop silently loses nodes. - Between concurrent pushes, stack order reflects who reached the CAS first, not who called push first.
- Pop must dereference a node another thread may free, which is the memory-reclamation problem the teaching version does not solve.
- The correct engineering conclusion from this lesson is to use a reviewed library or a mutex — the value here is understanding, not a recipe.
The loop, answered
Every field is required, which is why no lesson here can recommend concurrency without naming the interleaving that breaks it, the complexity it adds, and the simpler thing to consider first.
- • Allocate and fully initialise the node while it is still private to the pushing thread.
- • Load the current head and set the new node's
nextto it. - • CAS the head from that loaded value to the new node, with release ordering so the node's contents are visible to whoever acquires the head.
- • On failure, the CAS has already written the current head into your expected variable — re-link
nextto it and retry. - • Pop reverses it: load head, read its
next, CAS head tonextwith acquire ordering, and then face the question of when the removed node may be freed.
- • P1 loads head=X, links A.next=X; P2 loads head=X, links B.next=X; P1 CAS succeeds (head=A); P2 CAS fails, re-links B.next=A, CAS succeeds (head=B). Both nodes present exactly once.
- • Without the retry: P2 stores head=B with B.next=X — node A is unreachable, its push reported success, and the item is gone with no error.
- • C1 loads head=A and reads A.next=X; C2 pops A and frees it; C1 dereferences freed memory. The CAS logic is correct; the reclamation is not.
- • C1 loads head=A, next=B; C2 pops A, pops B, pushes A back (head=A, A.next=C); C1 CAS(head, A -> B) succeeds and head now points at the already-popped B. This is The ABA Problem: The Value Came Back.
- • Producer pushes a node whose payload write is not release-ordered; a consumer acquires the head, pops the node, and reads a field that has not become visible yet. See Safe Publication: Handing Over a Finished Object.
- • Promises: push and pop are lock-free — a thread suspended anywhere in either operation blocks nobody.
- • Promises: each successful push makes its node reachable exactly once, and each successful pop removes exactly one node.
- • Promises: linearizability of push and pop, given correct memory ordering — each appears to take effect at one instant.
- • Does NOT promise: FIFO or wall-clock ordering between concurrent operations. It is a stack, and concurrent pushes order by CAS arrival.
- • Does NOT promise: that the node may be freed after a successful pop. That is a separate protocol you must supply.
- • Does NOT promise: freedom from ABA. Pop is exposed to it by construction.
- • Does NOT promise: a meaningful
size(). Any count is stale before the caller can act on it. - • Does NOT promise: better throughput than a mutex-protected stack. See Lock-Free Is a Progress Guarantee.
- • Every push and every pop needs exclusive ownership of the single head cache line. That is one line for the entire structure, which is the tightest possible contention point.
- • Under N threads all pushing, one succeeds per round and N-1 retry, so useful work per CAS attempt falls as N grows while CPU utilisation stays high.
- • Push and pop contend with each other as well as within themselves — there is no read path that avoids the head.
- • The standard mitigations (backoff, elimination arrays that pair a push with a concurrent pop directly) are real techniques with real complexity, not tuning flags.
- • Lost push — the no-retry bug: a node silently unreachable, reported as success.
- • Use-after-free — reclaiming a popped node another thread is still dereferencing. Usually manifests as a crash in unrelated code, hours later.
- • ABA corruption — head pointing at an already-popped node, producing duplicate pops of the same item.
- • Torn publication — a consumer reading a node's payload before the producer's writes to it are visible. See Safe Publication: Handing Over a Finished Object.
- • Unbounded memory growth if the chosen answer to reclamation is "never free".
- • Progress-guarantee violation via the allocator —
newinside the retry loop may take a lock, so the structure is not lock-free in the way the code claims. - • Starvation of the slowest thread, which loses every CAS round. See Wait-Free vs Lock-Free: Whose Progress Is Guaranteed.
- • A free-list or node pool where the items are interchangeable, order does not matter, and the structure must be usable from a context that cannot block.
- • Shared-memory regions between processes where one process may crash while holding what would have been a lock.
- • Signal handlers and real-time callbacks that may not block, where a stack of preallocated buffers is the standard idiom.
- • As a teaching object: it is the shortest complete example of the whole family of problems in this module.
- • Whenever a mutex-protected
std::stackordequewould do, which covers nearly all application code. - • When ordering between producers matters, because concurrent pushes do not preserve call order.
- • In a language without a garbage collector, unless someone owns the reclamation scheme as a real piece of the design.
- • Under high contention on the head, where a queue with separate head and tail — or sharding — removes the bottleneck instead of managing it.
- • Count pushes and pops and compare against items observed by consumers. A deficit is a lost push or a duplicated pop, and it is the only symptom you will get.
- • Run under AddressSanitizer and a thread sanitizer; use-after-free from reclamation is exactly what ASan is for, and it will fire long before a customer sees it.
- • Track CAS attempts per successful operation. A ratio above about two under normal load means the head is the bottleneck.
- • Stress with more threads than cores and with deliberate delays inserted between the load and the CAS, which widens every window in the schedules above. See Stress Testing: A Test That Passed Once Proves Nothing.
- • Watch RSS if the reclamation answer is deferred — an epoch scheme that never advances looks exactly like a leak. See Memory Leaks: Growth That Does Not Come Back.
- • Reclamation is a second data structure with its own correctness argument, its own tuning, and its own failure mode (leak versus crash).
- • Memory ordering becomes part of the public contract: callers cannot reason about the payload without knowing the publish/acquire pair.
- • The structure cannot offer the API people expect — no reliable size, no iteration, no bulk operations — so it constrains its callers.
- • Review requires someone who can hold every interleaving in their head, and that person becomes a bottleneck for every change to it.
- • A mutex around
std::stackor adeque. Fewer lines, no reclamation problem, no ABA, and usually competitive. See Mutexes: What They Protect and What They Do Not. - • A reviewed concurrent container from a library —
boost::lockfree::stack,java.util.concurrent.ConcurrentLinkedDeque, a Go channel — where the reclamation and ordering problems are already solved. - • A bounded ring buffer over preallocated slots, which avoids allocation and reclamation entirely and gives backpressure for free. See Bounded vs Unbounded Queues.
- • Per-thread stacks with work stealing, which removes the single hot head and is what real task schedulers do. See Work Stealing.
- • A queue rather than a stack when order matters, and a channel rather than either when you can move data instead of sharing it. See Channels.
A lock-free stack, one head pointer
push(node): pop():
do { do {
t = head; t = head; if (t == null) return null;
node.next = t; n = t.next;
} while (!CAS(&head, t, node)); } while (!CAS(&head, t, n));| # | Pusher 1 — push(X) | Pusher 2 — push(Y) | Popper — pop() | State |
|---|---|---|---|---|
| 1 | t ← head (= A) | · | · | head=A stack=A→∅ |
| 2 | · | t ← head (= A) | · | head=A stack=A→∅ |
| 3 | X.next ← t (= A) | · | · | head=A stack=A→∅ |
| 4 | · | Y.next ← t (= A) | · | head=A stack=A→∅ |
compare_exchange in a loop — retries, and the pointer that lied
do {
old = counter.load(); # 1 read
next = old + 1; # compute off to the side
} while (!counter.compare_exchange(old, next)); # swap only if unchanged| # | T1 — pop() via CAS | T2 — another thread | State |
|---|---|---|---|
| 1 | old ← head (= A) | · | head=A stack=A→B→C |
| 2 | · | pop() → A | head=B stack=B→C |
| 3 | · | pop() → B | head=C stack=C |
| 4 | · | push(A) | head=A stack=A→C |
| 5 | CAS(head, A, B) → SUCCESS | · | head=B stack=B→ freed ✕ head now points at B, which was popped and freed. Node C has vanished from the stack and T1 returned a node it never observed being on top. |
| 6 | return A to the caller | · | head=B stack=corrupt |
The lost update, step by step
| # | Task A — counter++ | Task B — counter++ | State |
|---|---|---|---|
| 1 | rA ← counter | · | counter=0 rA=0 rB=— |
| 2 | · | rB ← counter | counter=0 rA=0 rB=0 |
| 3 | rA ← rA + 1 | · | counter=0 rA=1 rB=0 |
| 4 | counter ← rA | · | counter=1 rA=1 rB=0 |
| 5 | · | rB ← rB + 1 | counter=1 rA=1 rB=1 |
| 6 | · | counter ← rB | counter=1 rA=1 rB=1 ✕ 2 increments completed, counter = 1 |
What people believe, and what is true
The CAS is the hard part.
The CAS is the easy part. Knowing when it is safe to free a popped node is the hard part, and it is not visible in the code at all.
It compiles and my test passes, so it works.
Reclamation and ABA bugs need a specific interleaving plus address reuse. Tests reproduce them rarely enough that passing is close to no evidence.
A lock-free stack is faster than a locked one.
Both serialise on one location. The lock-free version buys the progress guarantee; whether it also buys throughput is a measurement, and often it does not.
Go deeper
Overview
A stack whose only shared state is the head pointer. Push builds a node privately and swings the head with one conditional write.
Practical
If you write one, write the retry so it re-links from the value the failed CAS returned. Then stop, and decide how popped nodes are reclaimed, before writing anything else.
Advanced
Hazard pointers give per-thread published references and bounded memory at the cost of a store and a fence on every read. Epoch-based reclamation is cheaper per operation and unbounded if any thread stalls inside a critical region. The choice is a latency-versus-memory trade, and it is the real design decision in this structure.
Internals
This is Treiber's stack (1986). The elimination-array variant pairs a blocked push with a concurrent pop directly, letting them cancel without touching the head at all — which is how the contention bottleneck is actually removed rather than tuned.