Lock-Free Stack, in depth: linearization points, ABA under garbage collection, tagged indices, elimination backoff and jcstress

What correct means for a concurrent stack

Two properties define a correct lock-free stack. Linearizability says every operation appears to take effect at a single instant between its call and its return, and the resulting order is a legal sequential stack history: each pop returns the most recent push not yet popped, or empty if there is none. Lock-freedom says that whenever threads are taking steps, some operation completes in a finite number of steps. It does not promise that every thread finishes; one unlucky thread can fail its CAS forever while others succeed. The stronger guarantee, wait-freedom, is rarely worth its cost for a stack.

The bugs in this area are plausible-looking histories: an element returned twice, an element lost, a pop reporting empty while the stack held an item. Naming the linearization point of every path lets you argue each of these away.

The base algorithm and its linearization points

import java.util.concurrent.atomic.AtomicReference;

public final class TreiberStack<T> {
  private static final class Node<T> {
    final T value;
    Node<T> next;                 // written before the publishing CAS, never after
    Node(T value) { this.value = value; }
  }

  private final AtomicReference<Node<T>> top = new AtomicReference<>();

  public void push(T x) {
    Node<T> n = new Node<>(x);    // allocated once, reused across retries
    while (true) {
      Node<T> t = top.get();
      n.next = t;
      if (top.compareAndSet(t, n)) return;               // LP: successful CAS
    }
  }

  public T pop() {
    while (true) {
      Node<T> t = top.get();                             // LP if t == null: empty
      if (t == null) return null;
      if (top.compareAndSet(t, t.next)) return t.value;  // LP: successful CAS
    }
  }
}

The comments mark the linearization points (LP). A push takes effect at its successful CAS. A non-empty pop takes effect at its successful CAS. An empty pop takes effect at the read that returned null: at that instant the stack really was empty, so reporting empty is legal even if a push lands a nanosecond later. Every failed CAS has no effect on the shared state, so it can be ignored in the history.

Memory visibility rides on the CAS. In Java, AtomicReference.get and compareAndSet have volatile semantics, so the plain write to n.next and the final value happen before the CAS that publishes the node, and a popper that reads top sees both. In C++ you would use a release CAS in push and an acquire load in pop. Atomic classes and their memory modes are covered in Java atomic classes.

ABA: when a garbage collector saves you, and when it does not

The ABA problem is the classic hazard. Thread P1 starts a pop, reads top = A and A.next = B, then is descheduled. Meanwhile P2 pops A, pops B, and pushes A back. The top is A again, so P1's CAS from A to B succeeds, and B, which is no longer in the stack, becomes the top. The stack is now corrupt.

In the Java code above this cannot happen, and the reason is precise. P2 can only push A back if it still has the node A; but push always allocates a fresh node, so the second push creates A-prime, a different object. P1's CAS compares references, sees A-prime, not A, and fails. The garbage collector guarantees that A's memory is not reused for A-prime while P1 still holds a reference to A. That is the whole trick: in a garbage-collected language, ABA on node identity is impossible as long as nodes are never reused.

The protection disappears in three common situations. You pool nodes to cut allocation, so a popped node really is pushed again. You store indices into an array instead of references, so index 7 can leave and come back. Or you work in C or C++, where freed memory is handed out again by the allocator and a stale pointer can also be a use-after-free. The usual fixes are a version tag next to the pointer, which the next section builds, or a safe memory reclamation scheme such as hazard pointers or epochs, which delay reuse until no thread can hold the old pointer.

A bounded stack with tagged indices

A bounded stack over preallocated arrays avoids allocation entirely, which matters in latency-sensitive code and is the natural shape for a free list of buffer slots. It keeps two index stacks in the same arrays: live for occupied slots and free for empty ones. Each head is a 64-bit word holding a 32-bit tag and a 32-bit index, and every successful CAS increments the tag.

import java.util.concurrent.atomic.AtomicIntegerArray;
import java.util.concurrent.atomic.AtomicLong;
import java.util.concurrent.atomic.AtomicReferenceArray;

/** Fixed-capacity lock-free stack. Slots are recycled, so ABA is real here. */
public final class BoundedLockFreeStack<T> {
  private static final int NIL = -1;
  private final AtomicReferenceArray<T> values;
  private final AtomicIntegerArray next;
  private final AtomicLong live = new AtomicLong(pack(0, NIL));
  private final AtomicLong free;

  public BoundedLockFreeStack(int capacity) {
    values = new AtomicReferenceArray<>(capacity);
    next = new AtomicIntegerArray(capacity);
    for (int i = 0; i < capacity; i++) next.set(i, i + 1 < capacity ? i + 1 : NIL);
    free = new AtomicLong(pack(0, capacity > 0 ? 0 : NIL));
  }

  private static long pack(int tag, int index) { return ((long) tag << 32) | (index & 0xFFFFFFFFL); }
  private static int index(long w) { return (int) w; }
  private static int tag(long w) { return (int) (w >>> 32); }

  private int popIndex(AtomicLong head) {
    while (true) {
      long h = head.get();
      int i = index(h);
      if (i == NIL) return NIL;
      int n = next.get(i);                          // stale if slot i was recycled...
      if (head.compareAndSet(h, pack(tag(h) + 1, n))) return i;  // ...but then the tag moved
    }
  }

  private void pushIndex(AtomicLong head, int i) {
    while (true) {
      long h = head.get();
      next.set(i, index(h));                        // slot i is owned by this thread here
      if (head.compareAndSet(h, pack(tag(h) + 1, i))) return;
    }
  }

  public boolean push(T x) {
    if (x == null) throw new NullPointerException("null means empty");
    int i = popIndex(free);
    if (i == NIL) return false;                     // full
    values.set(i, x);
    pushIndex(live, i);
    return true;
  }

  public T pop() {
    int i = popIndex(live);
    if (i == NIL) return null;                      // empty
    T x = values.getAndSet(i, null);
    pushIndex(free, i);
    return x;
  }
}

Replay the ABA history against this code. P1 reads live as tag 5, index 3, and reads next[3] = 7. P2 pops 3 and 7 and pushes 3 back, so the head is now tag 8, index 3. P1's CAS expects tag 5 and fails, rereads, and proceeds correctly. Without the tag the CAS would succeed and install index 7, a slot that is now on the free list.

The tag is a counter, so it can wrap. P1 would have to stay descheduled across exactly a multiple of 2³² successful operations on that head and then find the same index on top. That is astronomically unlikely in practice, but it is a probability argument, not a proof; a 64-bit platform with a 128-bit CAS can widen the tag if you need more margin, which Java's standard atomics do not expose. Java's AtomicStampedReference offers the same idea for references, at the cost of allocating a pair object on every update.

Contention and elimination backoff

Every operation on a Treiber stack hits one memory word. Under heavy contention the cache line holding top bounces between cores, most CAS attempts fail, and adding threads adds retries rather than throughput. Exponential backoff helps a little. Hendler, Shavit and Yerushalmi's elimination backoff stack (SPAA 2004) helps more by noticing that a push followed immediately by a pop leaves the stack unchanged, so a colliding pair can complete each other without touching top at all. The version below is simplified, in the style of the elimination array in Herlihy and Shavit's The Art of Multiprocessor Programming.

// Inside a Treiber stack: fields top (as before), slots, width, SPINS.
private static final class Box<T> { final T v; Box(T v) { this.v = v; } }
private final AtomicReferenceArray<Box<T>> slots = new AtomicReferenceArray<>(width);

public void push(T x) {
  Node<T> n = new Node<>(x);
  while (true) {
    Node<T> t = top.get();
    n.next = t;
    if (top.compareAndSet(t, n)) return;   // uncontended path is unchanged
    if (tryHandOff(x)) return;             // lost the race: try to meet a pop
  }
}

public T pop() {
  while (true) {
    Node<T> t = top.get();
    if (t == null) return null;
    if (top.compareAndSet(t, t.next)) return t.value;
    T x = tryTake();
    if (x != null) return x;
  }
}

private boolean tryHandOff(T x) {
  int i = ThreadLocalRandom.current().nextInt(width);
  Box<T> b = new Box<>(x);                 // fresh box: no ABA on slots
  if (!slots.compareAndSet(i, null, b)) return false;
  for (int k = 0; k < SPINS; k++) {
    if (slots.get(i) != b) return true;    // a pop took it
    Thread.onSpinWait();
  }
  return !slots.compareAndSet(i, b, null); // withdraw; failure means it was taken
}

private T tryTake() {
  int i = ThreadLocalRandom.current().nextInt(width);
  Box<T> b = slots.get(i);
  if (b != null && slots.compareAndSet(i, b, null)) return b.v;
  return null;
}

The linearization argument: when a pop's CAS removes a box, the pushing thread is still inside its push call and the pop is inside its pop call, so we may place the push and then the pop at that instant. The stack state is the same before and after the pair, so no other thread can tell. A pop that finds top null returns empty without looking at the array, which is legal because a push parked in a slot has not linearized yet. Two tuning knobs matter: width, which should grow with the number of contending threads, and SPINS, which trades latency at low contention for hit rate at high contention. The original paper adapts both at run time. At low contention elimination never triggers and costs nothing.

Testing with jcstress

Concurrency bugs hide from ordinary unit tests because the bad interleaving is rare. jcstress, the OpenJDK concurrency stress harness, runs small actor methods against shared state millions of times and tallies the observed outcomes against the ones you declare acceptable.

import org.openjdk.jcstress.annotations.*;
import org.openjdk.jcstress.infra.results.II_Result;

@JCStressTest
@Outcome(id = "1, 0", expect = Expect.ACCEPTABLE, desc = "push, then pop")
@Outcome(id = "0, 1", expect = Expect.ACCEPTABLE, desc = "pop saw empty, item remains")
@Outcome(expect = Expect.FORBIDDEN, desc = "lost or duplicated element")
@State
public class PushPopRace {
  final TreiberStack<Integer> s = new TreiberStack<>();

  @Actor public void pusher() { s.push(1); }

  @Actor public void popper(II_Result r) { Integer v = s.pop(); r.r1 = v == null ? 0 : v; }

  @Arbiter public void after(II_Result r) { Integer v = s.pop(); r.r2 = v == null ? 0 : v; }
}

Write one such test per pair of operations and run each against every variant. For larger histories, record every call and return with timestamps in a randomized test and feed the log to a linearizability checker, which searches for a legal sequential order consistent with the real-time order. Run the tests on an ARM machine as well as x86: x86's strong ordering hides missing barriers that ARM exposes, a point developed in atomics and memory ordering.

Failure modes

• Pooling nodes without tags: the Java stack becomes vulnerable to ABA the moment popped nodes are recycled.
• Reading a field of a popped node after the CAS in C++: another thread may have freed it. Read what you need before the CAS, and reclaim with hazard pointers or epochs.
• Null as a value: if null also means empty, a pushed null is indistinguishable from an empty pop. Reject it, as the bounded stack does.
• Livelock under contention: lock-free does not mean fast. Many threads hammering one CAS can deliver less throughput than a mutex; measure before switching.

Trade-offs

What to do next

1. Implement the Treiber stack above and annotate each linearization point in your own words.
2. Write the jcstress push and pop race, then add push-push and pop-pop races, and run them on x86 and ARM.
3. Add node pooling to a copy without tags and watch the tests fail; then switch to the tagged bounded version.
4. Benchmark a mutex stack, the Treiber stack and the elimination variant at 1, 4, 16 and 64 threads with JMH on your hardware.
5. If you work in C++, add hazard pointers or epoch-based reclamation before shipping, never after.
6. Choose the simplest design that meets your measured contention, and document why.