Pfthb

I've been toying around with a simple implementation of a lock-free Stack in Java.

edit: See fixed/working version below

Do you see any issues with this implementation?

Similar implementations in native languages seem to suffer from the ABA problem, but I'm not sure if this is a problem here; obviously no pointer handling done directly in Java, and given all I care for is the end of the stack both for pop and push, I don't see how "missing" any changes in any non-tail element of the stack would cause issues.

public class LockFreeStack<T extends LockFreeStack.StackItem<T>>

 public abstract static class StackItem<SELF extends StackItem<SELF>>
 
 volatile SELF next;
 // .. data ..
 

 final AtomicReference<T> top = new AtomicReference<T>(null);

 public void push(T item)
 
 T localTop;

 do 
 localTop = top.get();
 item.next = localTop;
 while(!top.compareAndSet(localTop, item));
 

 public T pop()
 
 T localTop;

 do 
 localTop = top.get();
 while(localTop != null && !top.compareAndSet(localTop, localTop.next));

 return localTop;
 

But, here's what I don't get. I've written a simple test that launches a few threads; each one pops items from a pre-existing LockFreeStack and (later, from the same thread that popped it) pushes them back.
After its popped, I increment an atomic counter, and before pushing it back, I decrement it. So I'd always expect the counter to be 0 (right after decrementing / right before pushing back onto the stack) or 1 (right after popping & incrementing).

But, that's not what happens...

public class QueueTest 
 static class TestStackItem extends LockFreeStack.StackItem<TestStackItem>
 
 final AtomicInteger usageCount = new AtomicInteger(0);

 public void inc() throws Exception
 
 int c = usageCount.incrementAndGet();

 if(c != 1)
 throw new Exception(String.format("Usage count is %d; expected %d", c, 1));
 

 public void dec() throws Exception
 
 int c = usageCount.decrementAndGet();

 if(c != 0)
 throw new Exception(String.format("Usage count is %d; expected %d", c, 0));
 
 

 public final LockFreeStack<TestStackItem> testStack = new LockFreeStack<TestStackItem>();

 public void test()
 
 final int NUM_THREADS = 4;

 for(int i = 0; i < 10; i++)
 
 TestStackItem item = new TestStackItem();
 testStack.push(item);
 

 Thread threads = new Thread[NUM_THREADS];
 for(int i = 0; i < NUM_THREADS; i++)
 
 threads[i] = new Thread(new TestRunner());
 threads[i].setDaemon(true);
 threads[i].setName("Thread"+i);
 threads[i].start();
 

 while(true)
 
 Thread.yield();
 

 

 class TestRunner implements Runnable
 
 @Override
 public void run() 
 try 
 boolean pop = false;
 TestStackItem lastItem = null;
 while (true) 
 pop = !pop;

 if (pop) 
 TestStackItem item = testStack.pop();
 item.inc();
 lastItem = item;
 else 
 lastItem.dec();
 testStack.push(lastItem);
 lastItem = null;
 
 
 catch (Exception ex)
 
 System.out.println("exception: " + ex.toString());
 
 
 

throws non-deterministic exceptions, e.g.

exception: java.lang.Exception: Usage count is 1; expected 0
exception: java.lang.Exception: Usage count is 2; expected 1

or from another run

exception: java.lang.Exception: Usage count is 2; expected 0
exception: java.lang.Exception: Usage count is 3; expected 1
exception: java.lang.Exception: Usage count is 3; expected 1
exception: java.lang.Exception: Usage count is 2; expected 1

So some race-condition like issue must be going on here.

What's wrong here - is this indeed ABA-related (and if so, how exactly?) or am I missing anything else?

Thanks!

NOTE: This works, but it doesn't seem to be a great solution. It's neithe garbage-free (StampedAtomicReference creates objects internally), nor does the benefit of being lock free really seem to pay off; in my benchmarks, this wasn't really faster in a single threaded environment, and when testing with 6 threads concurrently, it fell significantly behind just putting locks around the push/pop functions

based on the solution suggested below, this was indeed an ABA problem, and this small change will circumvent that:

public class LockFreeStack<T extends LockFreeStack.StackItem<T>>

 public abstract static class StackItem<SELF extends StackItem<SELF>>
 
 volatile SELF next;
 // .. data ..
 

 private final AtomicStampedReference<T> top = new AtomicStampedReference<T>(null, 0);

 public void push(T item)
 
 int stampHolder = new int[1];

 T localTop;

 do 
 localTop = top.get(stampHolder);
 item.next = localTop;
 while(!top.compareAndSet(localTop, item, stampHolder[0], stampHolder[0]+1));
 

 public T pop()
 
 T localTop;
 int stampHolder = new int[1];

 do 
 localTop = top.get(stampHolder);
 while(localTop != null && !top.compareAndSet(localTop, localTop.next, stampHolder[0], stampHolder[0]+1));

 return localTop;
 

You don't really need this weird cycle with "if condition" and "lastItem" in your test, you can reproduce the bug by simply pop and push same node.

To fix mentioned above issue, you can create new TestStackItem when pushing it into the stack (and passing existing counter into the new creared node) or you can use AtomicStampedReference to see if node has been modified.

Yes, your stack has an ABA problem.

• Thread A pop does localTop = top.get() and reads localTop.next




• Other threads pop a bunch of stuff and put it back in a different order, but Thread A's localTop is still the last one pushed.




• Thread A's CAS succeeds, but it corrupts the stack, because the value it read from localTop.next is no longer accurate.

Lock free data structures are a lot easier to implement in garbage-collected languages like Java than they are in other languages, though. Your ABA problem goes away if push() allocates a new stack item every time. Then StackItem.next can be final and the whole thing becomes a lot easier to reason about.