FULL PRODUCT VERSION :
java version "1.7.0_60-ea"
Java(TM) SE Runtime Environment (build 1.7.0_60-ea-b04)
Java HotSpot(TM) 64-Bit Server VM (build 24.60-b07, mixed mode)

ADDITIONAL OS VERSION INFORMATION :
Microsoft Windows [Version 6.1.7601]


A DESCRIPTION OF THE PROBLEM :
If multiple threads call AtomicReference.compareAndSet with the SAME pair of values, then multiple threads may succeed. The documentation should make this clear, as most developers and tutorials seem to assume that the compareAndSet methods of the Atomic classes guarantee that only one thread will succeed.

STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
Execute attached code.

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
There should be no output from the code. Specifically, there should be no way for two threads to retrieve and claim ownership of the same StackEntry.
ACTUAL -
Many threads obtain the same StackEntry and claim ownership. This can only happen if multiple threads are calling AtomicReference.compareAndSet with the SAME pair of values and are all succeeding.

REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
public class AtomicReferenceTest {
private static final class StackEntry {
volatile Thread owner;

volatile StackEntry next;
}

private static final AtomicReference<StackEntry> stack = new AtomicReference<StackEntry>();

private static class MyThread extends Thread {
@Override
public void run() {
while (true) {

/*
* Pop an entry off the top of the stack. The only way to exit
* this loop is to have found an empty stack, or to have
* ATOMICALLY replaced the head of the stack with the next item
* on the stack. In theory, no two threads should be able to
* exit this loop with the SAME entry...
*/
StackEntry entry;
while (true) {
entry = stack.get();
if (entry == null)
break;

// Atomic, right? Only one thread can succeed...
if (stack.compareAndSet(entry, entry.next))
break;
}

/*
* If there was nothing on the stack, make a new entry.
* Otherwise, just set the 'next' to null. This isn't required
* but is good practice.
*/
if (entry == null)
entry = new StackEntry();
else
entry.next = null;

/*
* Check if the entry really was exclusively claimed. In theory,
* no two threads should ever have a reference to the same
* entry...
*/
Thread owner = entry.owner;
if (owner != null)
System.err.println("ALREADY CLAIMED BY " + owner);
entry.owner = Thread.currentThread();

/* Push the entry back on to the queue. */
entry.owner = null;
while (true) {
entry.next = stack.get();

// Atomic, right? Only one thread can succeed...
if (stack.compareAndSet(entry.next, entry))
break;
}
}
}
};

public static void main(String[] args) {
Thread[] threads = new Thread[8];
for (int i = 0; i < threads.length; i++)
threads[i] = new MyThread();
for (int i = 0; i < threads.length; i++)
threads[i].start();
}
}
---------- END SOURCE ----------