15

I'm looking for some nice real-world examples of the ABA-problem causing trouble in multithreaded code.

The ABA-problem occurs in concurrent code when executing an atomic compare-and-swap instruction. If a thread is interrupted immediately before executing the compare-and-swap, a second thread may change change the target of the compare-and-swap from its initial value A to a different value B. If it then changes the value back to A before the first thread resumes, the compare-and-swap will succeed despite the changes to the target value.

In many cases ABA is not an issue. Take a shared reference count for example: Even if the refcount is changed concurrently we do not have a problem, as long as we never increase from a refcount that has already dropped to 0. So we are clearly only interested in whether the target matches the expected value at the time of the swap and not whether it has changed in the past.

The wikipedia page has an example of a lock-free stack implementation that suffers from ABA, but I personally have not run into the problem in production code so far. I was just curious whether anyone has some nice war stories to share about ABA.

ComicSansMS
  • 51,484
  • 14
  • 155
  • 166

1 Answers1

12

Suppose you want to implement an ordered list using a traditional linked list. Suppose you want to add a new value V to the list. First, you have to find the right position to insert the new element using an auxiliary pointer AUX and locate it in the last node with a value smaller than V, and also save AUX->next to make the comparison in the CAS operation. Once you have the reference you make NEW->next points to AUX->next and then using a CAS you switch AUX->next to NEW if AUX->next is still the same reference you saved. It should be something like this:

AUX = list.HEAD;
WHILE( AUX->next.value < V)
    AUX = AUX->next;
OLD = AUX->next; //line 4
NEW->next = AUX->next; //line 5
IF( CAS(AUX->next, NEW, OLD)) //line 6
    Success!!!
ELSE
    Try again or whatever

This is the simplest way to do it. The problem is that between lines 4 and 5, another thread might have removed "OLD" and then have inserted another element X smaller than V but still greater than AUX.value. If this happens, and the memory assigned to the node with value X is in the same address that used to have OLD, the CAS will succeed, but the list will not be ordered. If the actions of the second thread occur between lines 5 and 6, you will lose the node with the value X. All of these is because of the ABA problem.

ees_cu
  • 800
  • 1
  • 9
  • 20
  • Shouldn't `CAS(AUX->next, NEW, OLD)` be `CAS(AUX->next, OLD, NEW)`? – Jason Law Jan 22 '20 at 13:07
  • 1
    This is a great-sounding example, the only problem is that ABA isn't the cause of these problems. Having concurrent insertion and removal from this singly-linked list is already unsafe. ABA indeed happens when the second thread removes `OLD` and inserts a new value `X` which is given the same node address `OLD`. But ABA is unnecessary -- removing `AUX` on the second thread is sufficient to cause corruption. – Ben Voigt Jan 10 '22 at 21:02