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?

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

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

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

1. Thread 1 reads a variable var with value A.
   
2. Thread 1 is preempted and thread 2 runs.
3. Thread 2 changes the variable var from A to B to A.
4. 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 a 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.

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 that is implemented as a singly linked list. The stack supports only two operations. 

1. Pops the top object and returns a pointer to it.
2. 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.

1. Get the head node: head
2. Get the subsequent node: headNext
3. 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 want 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 behaviour.

There are a few remedies for the ABA problem.

Remedy for ABA

The conceptional problem of ABA is quite 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 get rid of the premature deletion of the node. Here are a few remedies.

Tagged state reference

You can add a tag to each node 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 any more. That sounds promising but has a big drawback. Most garbage collectors is 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 currently accessing. (In many systems this "list" may be provably limited to only one or two elements.) 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 actually deallocate the node's memory until no other thread's hazard list contains the pointer. This manual garbage collection can be done by a dedicated garbage-collection thread (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 synchronisation 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. In order to modify data, you make a copy of the data and modify that copy. On contrary all readers work with the original data. If there is no reader, you can safely replace the data structure with the copy.

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

As part of a concurrency toolkit, there are two proposals for upcoming C++ standards. 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 that has the potential for at least 20 exciting posts. Let yourself be surprised.