ABA – A is not the same as A

A common problem in concurrency is the so-called ABA problem. That means you read a value twice and each time it returns the same value A. Therefore you conclude that nothing changed in between. But you forgot the B.

Let me first use a simple scenario to introduce the problem.

An analogy

The scenario consists of you sitting in a car and waiting that the traffic light becomes green. Green stands in our case for B, and red for A. What’s happening?

You look at the traffic light and it is red (A).
Because you are bored, you begin to check the news on your smartphone and forget the time.
You look once more at the traffic light. Damn, is still red (A).

Of course, the traffic light became green (B) between your two checks. Therefore, what seems to be one red phase was two.

What does this mean for threads (processes)? Now once more formal.

$Thread 1 reads a variable var with value A.$
Thread 1 is preempted, and thread 2 runs.
Thread 2 changes the variable var from A to B to A.
Thread 1 starts to execute and checks the value of variable var; because the value of variable var is the same, thread 1 continues with its work,

Often, that is a no-brainer. You can simply ignore it.

No-brainer

Have a look at it here. The function fetch_mult (1) multiplies a std::atomic<T>& shared by mult.

// fetch_mult.cpp

#include <atomic>
#include <iostream>

template <typename T>
T fetch_mult(std::atomic<T>& shared, T mult){                          // 1
  T oldValue = shared.load();                                          // 2
  while (!shared.compare_exchange_strong(oldValue, oldValue * mult));  // 3
  return oldValue;
}

int main(){
  std::atomic<int> myInt{5};
  std::cout << myInt << std::endl;          
  fetch_mult(myInt,5);
  std::cout << myInt << std::endl;         
}

The key observation is that there is a small time window between the reading of the old value T oldValue = shared.load (2) and the comparison with the new value (3). Therefore, another thread can kick in and change the oldValue from oldValue to anotherValue to oldValue back. The anotherValue is the B in ABA.

Modernes C++ Mentoring

"Fundamentals for C++ Professionals" (open)

"Design Patterns and Architectural Patterns with C++" (open)

"C++20: Get the Details" (open)

"Concurrency with Modern C++" (open)

"Generic Programming (Templates) with C++": October 2024

"Embedded Programming with Modern C++": October 2024

"Clean Code: Best Practices for Modern C++": March 2025

Do you want to stay informed: Subscribe.

Often it makes no difference if the first read value is in the second read operation the original value. But in a lock-free concurrent data structure, ABA may have a great impact.

A lock-free data structure

I will not present here in detail a lock-free data structure. I will use a lock-free stack implemented as a singly linked list. The stack supports only two operations.

Pops the top object and returns a pointer to it.
Pushes the object specified to stack.

Let me describe in pseudo-code the pop operation to get an idea of the ABA problem. The pop operation performs, in essence, the following steps in a loop until the operation was successful.

Get the head node: head
Get the subsequent node: headNext
Make headNext to the new head if head is still the head of the stack

Here are the first two nodes of the stack:

Stack: TOP -> head -> headNext -> ...

Let’s construct the ABA problem.

ABA in action

Let’s start with the following stack:

Stack: TOP -> A -> B -> C

Thread 1 is active and wants to pop the head of stack.

Thread 1 stores
- head = A
- headNext = B

Before thread 1 finishes the pop algorithm, thread 2 kicks in.

Thread 2 pops A

    Stack: TOP -> B -> C

Thread 2 pops B and deletes B

    Stack: TOP -> C

Thread 2 pushes A back

    Stack: TOP -> A -> C

Thread 1 is rescheduled, and check if A == head. Because A == head, headNext which is B becomes the new head. But B was already deleted. Therefore, the program has undefined behavior.

There are a few remedies for the ABA problem.

Remedy for ABA

The conceptual problem of ABA is relatively easy to get. A node such as B == headNext was deleted, although another node A == head was referring to it. The solution to our problem is to eliminate the premature deletion of the node. Here are a few remedies.

Tagged state reference

You can add a tag indicating how often the node has been successfully modified. The result is that compare and swap method will eventually fail, although the check returns true.

The next three techniques are based on the idea of deferred reclamation.

Garbage collection

Garbage collection guarantees that the variables will only be deleted if it is not needed anymore. That sounds promising but has a big drawback. Most garbage collectors are not lock-free. Therefore, you have a lock-free data structure, but the overall system is not lock-free.

Hazard pointers

From Wikipedia: Hazard Pointers:

In a hazard-pointer system, each thread keeps a list of hazard pointers indicating which nodes the thread is accessing. (This “list” may be limited to only one or two elements in many systems.) Nodes on the hazard pointer list must not be modified or deallocated by any other thread. … When a thread wishes to remove a node, it places it on a list of nodes “to be freed later” but does not deallocate the node’s memory until no other thread’s hazard list contains the pointer. A dedicated garbage-collection thread can do this manual garbage collection (if the list “to be freed later” is shared by all the threads); alternatively, cleaning up the “to be freed” list can be done by each worker thread as part of an operation such as “pop”.

RCU

RCU stands for Read Copy Update and is a synchronization technique for almost read-only data structures. RCU was created by Paul McKenney and is used in the Linux Kernel since 2002.

The idea is quite simple and follows the acronym. To modify data, you make a copy of the data and modify that copy. On the contrary, all readers work with the original data. You can safely replace the data structure with the copy if there is no reader.

For more details about RCU, read the article What is RCU, Fundamentally? by Paul McKenney.

As part of a concurrency toolkit, two proposals for upcoming C++ standards exist. The proposal P0233r0 for hazard pointers and the proposal P0461R0 for RCU.

What’s next?

I’m not so sure. I have to go for the next big topic with the potential for at least 20 exciting posts. Let yourself be surprised.

Post Views: 7,779

Thanks a lot to my Patreon Supporters: Matt Braun, Roman Postanciuc, Tobias Zindl, G Prvulovic, Reinhold Dröge, Abernitzke, Frank Grimm, Sakib, Broeserl, António Pina, Sergey Agafyin, Андрей Бурмистров, Jake, GS, Lawton Shoemake, Jozo Leko, John Breland, Venkat Nandam, Jose Francisco, Douglas Tinkham, Kuchlong Kuchlong, Robert Blanch, Truels Wissneth, Mario Luoni, Friedrich Huber, lennonli, Pramod Tikare Muralidhara, Peter Ware, Daniel Hufschläger, Alessandro Pezzato, Bob Perry, Satish Vangipuram, Andi Ireland, Richard Ohnemus, Michael Dunsky, Leo Goodstadt, John Wiederhirn, Yacob Cohen-Arazi, Florian Tischler, Robin Furness, Michael Young, Holger Detering, Bernd Mühlhaus, Stephen Kelley, Kyle Dean, Tusar Palauri, Juan Dent, George Liao, Daniel Ceperley, Jon T Hess, Stephen Totten, Wolfgang Fütterer, Matthias Grün, Phillip Diekmann, Ben Atakora, Ann Shatoff, Rob North, Bhavith C Achar, Marco Parri Empoli, Philipp Lenk, Charles-Jianye Chen, Keith Jeffery,and Matt Godbolt.

Thanks, in particular, to Jon Hess, Lakshman, Christian Wittenhorst, Sherhy Pyton, Dendi Suhubdy, Sudhakar Belagurusamy, Richard Sargeant, Rusty Fleming, John Nebel, Mipko, Alicja Kaminska, Slavko Radman, and David Poole.

My special thanks to Embarcadero
My special thanks to PVS-Studio
My special thanks to Tipi.build
My special thanks to Take Up Code
My special thanks to SHAVEDYAKS