ABA Problem - Examples

Examples

The first example of the ABA problem is a real-life scenario:

Charlie is sitting in an airport terminal with a briefcase containing a large sum of money on the floor next to his feet. He is transporting it for his boss, so he does not know the suitcase's combination. An attractive and provocatively-dressed woman (Sharon) approaches him and strikes up a conversation. While Sharon is distracting Charlie, her partner-in-crime (Albert) decides to seize the opportunity to grab the money. He realizes that if Charlie turns his head and sees that his briefcase has disappeared, he will sound an alarm; after that, it is not likely that he and Sharon will make it out of the airport without being stopped by security.

Instead, Albert quickly takes Charlie's briefcase and replaces it with an identical briefcase filled with sand to match the weight of the money. Sharon finishes up her conversation with Charlie, he gets up, gets on the plane, and leaves. He is completely unaware that the briefcase now contains only sand. When Charlie's boss finally opens the briefcase, it is likely Charlie will be in a lot of trouble.

In this scenario, the 'A' state is when there is a briefcase next to Charlie, and the 'B' state is when there is nothing next to him. Originally, his briefcase starts in 'A' state. If Charlie had turned around in between the time Albert took his real briefcase and replaced it with the fake, he would've seen his briefcase gone ('B' state) and sounded the alarm. Unfortunately, when he finished talking to Sharon he observed 'A' state and had no choice but to assume that 'B' state never happened.

See the workaround section to find out how Charlie could have prevented this misfortune.

Next, consider a software example of ABA using a 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 0; 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 (CompareAndSwap(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_ptr->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 (CompareAndSwap(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 CompareAndSwap...

{ // Thread 2 runs pop: ret = A; next = B; CompareAndSwap(A, A, B) // Success, top = B return A; } // Now the stack is top → B → C { // Thread 2 runs pop again: ret = B; next = C; CompareAndSwap(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; CompareAndSwap(C, C, A) // Success, top = A }

Now the stack is top → A → C

When Thread 1 resumes:

CompareAndSwap(A, A, B)

This instruction succeeds because it finds top == ret (both are A), so it sets top to next (which is B). As B has been deleted the program will access freed memory when it tries to look the first element on the stack. Accessing freed memory is undefined, so the program will soon crash. ABA bugs, such as this, can be difficult to debug.