ABA problem

In multithreaded computing, the ABA problem occurs during synchronization, when a location is read twice, has the same value for both reads, and "value is the same" is used to indicate "nothing has changed". However, another thread can execute between the two reads and change the value, do other work, then change the value back, thus fooling the first thread in to thinking "nothing has changed" even though the second thread did work that violates that assumption.

The ABA problem occurs when multiple threads (or processes) accessing shared memory interleave. Below is the sequence of events that will result in the ABA problem:
* Process $P\_1$ reads value A from shared memory,
* $P\_1$ is preempted, allowing process $P\_2$,
* $P\_2$ modifies the shared memory value A to value B and back to A before preemption,
* $P\_1$ begins execution again, sees that the shared memory value has not changed and continues.

Although $P\_1$ can continue executing, it is possible that the behavior will not be correct due to the "hidden" modification in shared memory.

A common case of the ABA problem is encountered when implemening a lock-free data structure. If an item is removed from the list, deleted, and then a new item is allocated and added to the list, it is common for the allocated object to be at the same location as the deleted object thanks to optimizations in the memory manager. A pointer to the new item is thus sometimes equal to a pointer to the old item which is an ABA problem.

Example

Consider this lock-free stack:

/* Naive lock-free stack which suffers from ABA problem.*/ class Stack { volatile Obj* top_ptr; // // Pops the top object and returns a pointer to it. // Obj* Pop() { while(1) { Obj* ret_ptr = top_ptr; if (!ret_ptr) return NULL; Obj* next_ptr = ret_ptr->next; // If the top node is still ret, then assume no one has changed the stack. // (That statement is not always true because of the ABA problem) // Atomically replace top with next. if (CompareAndExchange(top_ptr, ret_ptr, next_ptr)) { return ret_ptr; } // The stack has changed, start over. } } // // Pushes the object specified by obj_ptr to stack. // void Push(Obj* obj_ptr) { while(1) { Obj* next_ptr = top_ptr; obj->next = next_ptr; // If the top node is still next, then assume no one has changed the stack. // (That statement is not always true because of the ABA problem) // Atomically replace top with obj. if (CompareAndExchange(top_ptr, next_ptr, obj_ptr)) { return; } // The stack has changed, start over. } }

This code can normally prevent problems from concurrent access, but suffers from ABA problems. Consider the following sequence:

Stack initially contains top -> A -> B -> C

Thread 1 starts running pop: ret = A; next = B;Thread 1 gets interrupted just before the CompareExchange...

{ // Thread 2 runs pop: ret = A; next = B; CompareExchange(A, A, B) // Success, top = B return A; } // Now the stack is top -> B -> C { // Thread 2 runs pop again: ret = B; next = C; CompareExchange(B, B, C) // Success, top = C return B; } // Now the stack is top -> C delete B; { // Thread 2 now pushes A back onto the stack: A->next = C; CompareExchange(C, C, A) // Success, top = A }

Now the stack is top -> A -> C

When Thread 1 resumes: CompareExchange(A, A, B)

This instruction succeeds because it finds top = ret (both are A), so it sets top to next (which is B). But B was deleted! Bad things will result...

Workarounds

A common workaround is to add extra "tag" bits to the quantity being considered. For example, an algorithm using compare and swap on a pointer might use the low bits of the address to indicate how many times the pointer has been successfully modified. Because of this, the next compare-and-swap will fail, even if the addresses are the same, because the tag bits will not match. This does not completely solve the problem, as the tag bits will eventually wrap around, but helps to avoid it. Some architectures provide a double-word compare and swap, which allows for a larger tag. This is sometimes called ABA' since the second A is made slightly different from the first.

A correct but expensive approach is to use intermediate nodes that are not data elements and thus assure invariants as elements are inserted and removed [Valois] .

Another approach is to use one or more hazard pointers, which are pointers to locations that otherwise cannot appear in the list. Each hazard pointer represents an intermediate state of an in-progress change; the presence of the pointer assures further synchronization [Doug Lea] .

Some architectures provide "larger" atomic operations such that, as example, both forward and backward links in a doubly-linked list can be updated atomically.

Some architectures provide a load linked, store conditional instruction in which the store is performed only when there are no other stores of the indicated location. This effectively separates the notion of "storage contains value" from "storage has been changed". Examples include DEC Alpha and PowerPC.

References

# Damian Dechev, Peter Pirkelbauer, and Bjarne Stroustrup. [http://www.research.att.com/~bs/lock-free-vector.pdf Lock-free Dynamically Resizable Arrays]