Understanding compare_exchange_weak

The code below is the example for compare_exchange_weak from https://www.cplusplus.com/reference/atomic/atomic/compare_exchange_weak/

I don't understand what kinds of operations are acceptable inside the compare_exchange_weak while loop.

In the example, they are setting the newNode->next value to the oldHead pointer as long as the compare_exchange returns false. I don't understand how this is always valid.

What happens if another thread is in the same loop, and it succeeds to change the oldHead pointer between the time we set it, and the time the compare_exchange succeeds on our thread? Then we would have the wrong head pointer in our newNode. I can't see why this is not possible.

For example, if I put a sleep(5), or do some long calculation in the loop after I set the ->next value, would this work?

The loop marked "WHAT IS SAFE TO DO HERE" is the part I don't get.

// atomic::compare_exchange_weak example:
#include <iostream>       // std::cout
#include <atomic>         // std::atomic
#include <thread>         // std::thread
#include <vector>         // std::vector

// a simple global linked list:
struct Node { int value; Node* next; };
std::atomic<Node*> list_head (nullptr);

void append (int val) {     // append an element to the list
  Node* oldHead = list_head;
  Node* newNode = new Node {val,oldHead};

  // what follows is equivalent to: list_head = newNode, but in a thread-safe way:
  while (!list_head.compare_exchange_weak(oldHead,newNode))

    newNode->next = oldHead;                 // <-- WHAT IS SAFE TO DO HERE?

    // WHAT IF I DO SOMETHING STUPID LIKE THIS?
    //sleep(5);

    // OR LIKE THIS:
    //some_long_calculation();    

  }

int main ()
{
  // spawn 10 threads to fill the linked list:
  std::vector<std::thread> threads;
  for (int i=0; i<10; ++i) threads.push_back(std::thread(append,i));
  for (auto& th : threads) th.join();

  // print contents:
  for (Node* it = list_head; it!=nullptr; it=it->next)
    std::cout << ' ' << it->value;
  std::cout << '\n';

  // cleanup:
  Node* it; while (it=list_head) {list_head=it->next; delete it;}

  return 0;
}

Solution

Basically you can do whatever you like inside the loop. compare_exchange (both, weak and strong) only ever succeed if and only if the value of the variable to be updated equals the first provided argument. In your example, list_head.compare_exchange_weak(oldHead,newNode) can only ever succeed iff list_head == oldHead. So if inside the loop you have a sleep or some long calculation, then there is a good chance that some other thread is faster and updates list_head, so your compare_exchange operation is likely to fail. It is important to note that the first parameter is passed by reference. If the compare fails, the given parameter is updated with the new value.

Storing oldHead in newNode->next is perfectly safe, because if subsequent the compare_exchange fails, oldHead is updated, the new value is again stored in newNode->next and we try again (and again, and again, ...) until the compare_exchange eventually succeeds. When that is the case, it is guaranteed that the value stored in newNode->next matches the one we just replaced in list_head - voilà, we have successfully inserted the node in the list.

  // what follows is equivalent to:
  //   newNode->next = list_head;
  //   list_head = newNode;
  // but in a thread-safe way:
  while (!list_head.compare_exchange_weak(oldHead,newNode)) {
    // if we are here, the compare_exchange_weak has failed, but
    // oldHead has been updated with the current value from list_head
    newNode->next = oldHead;
  }
  // if we are here, the compare_exchange_weak was successful, i.e., the value
  // in list_head (oldHead) did not change between our assignment to newNode->next
  // and the subsequent (successful) compare_exchange.

The difference the weak and strong version is that compare_exchange_weak may fail spuriously. That is, it may even fail in cases where the comparison yields true. The reason why there why there is weak version is that on architectures that implement compare-exchange using LL/SC, a compare_exchange_weak is cheaper than the strong version. In general, if you have a retry loop like in your example, you should prefer compare_exchange_weak, because if you really have a (rare) spurious failure, we simply perform another retry.