Correct use of AtomicReference.compareAndSet for a stack implementation

Question

I was experimenting with java.util.concurrent and trying to work out how to use AtomicReference.compareAndSet correctly to manage concurrent access to a single unit of shared state.

In particular: is the following usage of compareAndSet correct and safe? Any pitfalls?

My test class is a simple stack based on a linked list of nodes.

public class LinkedStack<T> {

  AtomicReference<Node<T>> topOfStack=new AtomicReference<Node<T>>();

  public T push(T e) {
    while(true) {
      Node<T> oldTop=topOfStack.get();
      Node<T> newTop=new Node<T>(e,oldTop);
      if (topOfStack.compareAndSet(oldTop, newTop)) break;
    } 
    return e;
  }

  public T pop() {
    while(true) {
      Node<T> oldTop=topOfStack.get();
      if (oldTop==null) throw new EmptyStackException();
      Node<T> newTop=oldTop.next;
      if (topOfStack.compareAndSet(oldTop, newTop)) return oldTop.object;
    } 
  }

  private static final class Node<T> {
    final T object;
    final Node<T> next;

    private Node (T object, Node<T> next) {
      this.object=object;
      this.next=next;
    }
  } 
  ...................
}

Answer 1

Yes, that's exactly how it should be used.

Perhaps the following syntax would be more elegant:

Node<T> oldTop = null;
Node<T> newTop = null;
do {
    oldTop=topOfStack.get();
    newTop=new Node<T>(e,oldTop);
} while (!topOfStack.compareAndSet(oldTop, newTop));

Answer 2

It is correct in its current form.

Your structure is known as Treiber's Stack. It is a simple thread-safe lock-free structure that suffers from having a single point of contention (topOfStack) and therefore tends to scale badly (under contention it will thrash, and that doesn't play nicely with the MMU). It is a good option for if the contention is likely to be low but thread-safety is still required.

For further reading on scaling stack algorithms see "A Scalable Lock-free Stack Algorithm (pdf)" by Danny Hendler, Nir Shavit and Lena Yerushalmi.