Deferred Reclamation in C++26: Read-Copy Update and Hazard Pointers
Before I dive into lock-free programming, there’s a little bit of theory necessary.

A common problem in concurrency is the so-called ABA problem. That means you read a variable twice, which returns the same value each time, 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 involves you sitting in a car and waiting for the traffic light to turn green. In our case, green stands 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 ignore it.
Atomic Multiplication
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 << '\n'; fetch_mult(myInt,5); std::cout << myInt << '\n'; }
shared.compare_exchange_strong(expected, desired)
(3) has the following behavior:
Modernes C++ Mentoring
Do you want to stay informed: Subscribe.
- If the comparison returns
false
,expected
is set toshared
- If the atomic comparison of
shared
withexpected
returnstrue
,shared
is set in the same atomic operation toexpected
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.
Let me exemplify ABA in a lock-free data structure.
A lock-free Stack
I will use a lock-free stack implemented as a single 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 the pop operation in pseudo-code to give you an idea of the ABA problem. The pop operation performs the following steps in a loop until it is 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 to 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 understand. 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. However, the 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 they are 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, a synchronization technique for almost read-only data structures created by Paul McKenney and 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.
What’s Next?
In my next post, I will implement a lock-free stack with deferred reclamation.
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, Matt Godbolt, Honey Sukesan, and bruce_lee_wayne.
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 | ![]() |
Modernes C++ GmbH
Modernes C++ Mentoring (English)
Rainer Grimm
Yalovastraße 20
72108 Rottenburg
Mail: schulung@ModernesCpp.de
Mentoring: www.ModernesCpp.org