Treiber Stack and ABA problem

Treiber Stack is a classical example of incorrect scalable lock-free stack. When a value is read twice, has the same value for both reads, and “value is the same” is used to indicate “nothing has changed”. It then use a compare-and-swap (CAS) atomic instruction to update the stack. It suffers from the ABA problem. The value can be changed twice between the two reads.

Sample implementation of Treiber Stack in Java using AtomicReference:

import java.util.concurrent.atomic.*;

import net.jcip.annotations.*;

/**
* ConcurrentStack
*
* Nonblocking stack using Treiber's algorithm
*
* @author Brian Goetz and Tim Peierls
*/
@ThreadSafe
public class ConcurrentStack <E> {
  AtomicReference<Node<E>> top = new AtomicReference<Node<E>>();

  public void push(E item) {
    Node<E> newHead = new Node<E>(item);
    Node<E> oldHead;
    do {
      oldHead = top.get();
      newHead.next = oldHead;
    } while (!top.compareAndSet(oldHead, newHead));
  }

  public E pop() {
    Node<E> oldHead;
    Node<E> newHead;
    do {
      oldHead = top.get();
      if (oldHead == null)
      return null;
      newHead = oldHead.next;
    } while (!top.compareAndSet(oldHead, newHead));
    return oldHead.item;
  }

  private static class Node <E> {
    public final E item;
    public Node<E> next;

    public Node(E item) {
      this.item = item;
    }
  }
}