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?

  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, 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.

  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 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:

 

Rainer D 6 P2 500x500Modernes 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)
  • "Embedded Programming with Modern C++": January 2025
  • "Generic Programming (Templates) with C++": February 2025
  • "Clean Code: Best Practices for Modern C++": May 2025
  • Do you want to stay informed: Subscribe.

     

    • If the comparison returns false, expected is set to shared
    • If the atomic comparison of shared with expected returns true, shared is set in the same atomic operation to expected

    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. 

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

    Do you want to stay informed about my mentoring programs? Subscribe Here

    Rainer Grimm
    Yalovastraße 20
    72108 Rottenburg

    Mobil: +49 176 5506 5086
    Mail: schulung@ModernesCpp.de
    Mentoring: www.ModernesCpp.org