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 the read value being the same twice is used to conclude that nothing has happened in the interim; 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 into 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 data interleave. Below is a sequence of events that illustrates the ABA problem: # Process P_1 reads value A from some shared memory location, # P_1 is preempted, allowing process P_2 to run, # P_2 writes value B to the shared memory location # P_2 writes value A to the shared memory location # P_2 is preempted, allowing process P_1 to run, # P_1 reads value A from the shared memory location, # P_1 determines 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 implementing a lock-free data structure.…

In multithreaded computing, the ABA problem occurs during synchronization, when a location is read twice, has the same value for both reads, and the read value being the same twice is used to conclude that nothing has happened in the interim; 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 into 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 data interleave. Below is a sequence of events that illustrates the ABA problem: Process P_1 reads value A from some shared memory location, P_1 is preempted, allowing process P_2 to run, P_2 writes value B to the shared memory location P_2 writes value A to the shared memory location P_2 is preempted, allowing process P_1 to run, P_1 reads value A from the shared memory location, P_1 determines 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 implementing 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 due to MRU memory allocation. A pointer to the new item is thus often equal to a pointer to the old item, causing an ABA problem. /* Naive lock-free stack which suffers from ABA problem.*/ class Stack { std::atomic top_ptr; // // Pops the top object and returns a pointer to it. // Obj* Pop() { while (1) { Obj* ret_ptr = top_ptr; if (ret_ptr == nullptr) return nullptr; // For simplicity, suppose that we can ensure that this dereference is safe // (i.e., that no other thread has popped the stack in the meantime). 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 (top_ptr.compare_exchange_weak(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 (top_ptr.compare_exchange_weak(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_ptr = A; next_ptr = B; Thread 1 gets interrupted just before the compare_exchange_weak ... { // Thread 2 runs pop: ret_ptr = A; next_ptr = B; top_ptr.compare_exchange_weak(A, B) // Success, top = B return A; } // Now the stack is top → B → C { // Thread 2 runs pop again: ret_ptr = B; next_ptr = C; top_ptr.compare_exchange_weak(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_ptr = C; top_ptr.compare_exchange_weak(C, A) // Success, top = A } Now the stack is top → A → C When Thread 1 resumes: compare_exchange_weak(A, B) This instruction succeeds because it finds top == ret_ptr (both are A), so it sets top to next_ptr (which is B). As B has been deleted the program will access freed memory when it tries to look at the first element on the stack. In C++, as shown here, accessing freed memory is undefined behavior: this may result in crashes, data corruption or even just silently appear to work correctly. ABA bugs such as this can be difficult to debug.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1375335505 under CC BY-SA 4.0; modifications have been made.