C++ Core Guidelines: The Resolution of the Riddle


Today, I solve the riddle from my last post. Thanks to my readers, the analysis of the ABA problem is quite accurate.


park 748339 1280

Only to remind you. The rule CP.100 from the C++ core guidelines is the starting point of the riddle.


Rainer D 6 P2 540x540Modernes C++ Mentoring

Stay informed about my mentoring programs.



Subscribe via E-Mail.

CP.100: Don’t use lock-free programming unless you absolutely have to.

The challenge in the rule states that the following code snippet has a bug. The bug should be due to the ABA problem. The post ABA - A is not the same as A gives a concise introduction to the ABA problem.

extern atomic<Link*> head;        // the shared head of a linked list

Link* nh = new Link(data, nullptr);    // make a link ready for insertion
Link* h = head.load();                 // read the shared head of the list   

do {
    if (h->data <= data) break;        // if so, insert elsewhere           
    nh->next = h;                      // next element is the previous head  
} while (!head.compare_exchange_weak(h, nh));    // write nh to head or to h 


Thanks a lot in particular to anonymous readers of my German blog, here is a runnable piece of code and a deep analysis of the issue.

#include <atomic>

class Link {
    Link(int d, Link* p) : data(d), next(p) {}
    int     data;
    Link*   next;

void foo (int data) {
    extern std::atomic<Link*> head;

    Link* nh = new Link(data, nullptr);            // (1)
    Link* h  = head.load();                        // (2)

    do {
        if (h->data <= data) break;                // (3)
        nh->next = h;                              // (4)
    } while (!head.compare_exchange_weak(h, nh));  // (5)


First of all, what should this piece of code do? It creates a singly linked list of nodes (Link). Each node has a pointer and a data field. The pointer points to the next element (node->next), and the data field stores the value: node->data. Each new node is inserted into the singly linked list in such a way that data is ordered in ascending order.

To insert a new node into the correct position in the singly linked list, the following steps are performed.

  • Line 1: A new node is created. This is fine because the node is locally created in each thread.
  • Line 2: The pointer to the head is read. The read operation is atomic; therefore,  considered in isolation the operation is also fine. What does in isolation mean? Line 2 creates with line 5 a kind of transaction. Line 2 stores the initial state of the transaction and line 5 publish the transaction if nothing had changed in between.
  • Line 3: Correspondingly to the previous lines, this line 3 has no issue. Only a value comparison takes place which may end the function if the data of head is smaller than the new data.
  • Line 4: nh is local data; therefore, the assignment of nh->next is fine. It may happen head h was changed in the meantime and, consequently, nh->next does not refer to the head afterwards. This is only an issue if the change is committed in the next line 5.
  • Line 5: The instruction head.compare_exchange_weak(h, nh) compares head with the stored h in line 2 and exchanges h and nh in an atomic step as soon as they are the same. If head is not equal to h, h is set to head. Line 5 is the end of the atomic transaction and publishes the updated singly linked list.

What is the issue with these few lines of code? The entire transaction is based on the pointer comparison in line 5. If the pointer comparison can be fooled, the singly linked list can be broken.

There is a time window between the loading of the head (line 2) and then check if the current head is the old head (line 5). The means another thread may kick in and change in the meantime head but the first thread is not aware of it.

Let me present a buggy sequence of events.

Breaking of the Invariant

The invariant of the following singly linked list is that data is ordered in ascending order. The blue node is the head of the list.

This is the initial structure of the list. The head has the address 0x0815.



Thread 1


  • Wants to add the new node with data 42.
  • 42 < 47, therefore the new node should become the new head.
  • Right before line (5), Thread 2 kicks in.

Thread 2

  • Removes the current head 47.
  • Makes the node with data 60 to the new head.

ABAThread2 60head

  • Wants to add the new node with data 30.


  • Makes 30 the new head with address 0x0815; this was the former address of 47 and will often happen because of memory reuse.

ABAThread2 30


 Thread 1

  • Makes the node with the data 42 to the new head; this is fine because the comparison in line 5 just compares the old with the new node and they have the same address: 0x0815.

ABAThread1 42

 Now, the singly linked list is broken because the values of the nodes are not ordered in ascending order.

What's next?

I'm nearly done with the rules to concurrency and lock-free programming in particular. The remaining rules are about wrong assumptions to hardware/compiler combinations and the infamous double-checked locking pattern. Read about it in the next post.



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, Animus24, Jozo Leko, John Breland, Venkat Nandam, Jose Francisco, Douglas Tinkham, Kuchlong Kuchlong, Robert Blanch, Truels Wissneth, Kris Kafka, 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, Matthieu Bolt, Stephen Kelley, Kyle Dean, Tusar Palauri, Dmitry Farberov, Juan Dent, George Liao, Daniel Ceperley, Jon T Hess, Stephen Totten, Wolfgang Fütterer, Matthias Grün, Phillip Diekmann, Ben Atakora, Ann Shatoff, Dominik Vošček, and Rob North.


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



My special thanks to Embarcadero CBUIDER STUDIO FINAL ICONS 1024 Small


My special thanks to PVS-Studio PVC Logo


My special thanks to Tipi.build tipi.build logo


I'm happy to give online seminars or face-to-face seminars worldwide. Please call me if you have any questions.

Bookable (Online)


Standard Seminars (English/German)

Here is a compilation of my standard seminars. These seminars are only meant to give you a first orientation.

  • C++ - The Core Language
  • C++ - The Standard Library
  • C++ - Compact
  • C++11 and C++14
  • Concurrency with Modern C++
  • Design Pattern and Architectural Pattern with C++
  • Embedded Programming with Modern C++
  • Generic Programming (Templates) with C++


  • Clean Code with Modern C++
  • C++20

Contact Me

Modernes C++,


Tags: lock-free


Stay Informed about my Mentoring


English Books

Course: Modern C++ Concurrency in Practice

Course: C++ Standard Library including C++14 & C++17

Course: Embedded Programming with Modern C++

Course: Generic Programming (Templates)

Course: C++ Fundamentals for Professionals

Interactive Course: The All-in-One Guide to C++20

Subscribe to the newsletter (+ pdf bundle)

All tags

Blog archive

Source Code


Today 1707

Yesterday 4791

Week 1707

Month 191783

All 11672937

Currently are 279 guests and no members online

Kubik-Rubik Joomla! Extensions

Latest comments