lundi 10 octobre 2022

Is the implementation of the hazard pointer in C++ Concurrency in Action flawed?

I am reading the second edition of C++ Concurrency in Action. The code below is from Listing 7.6. It implements pop() for the stack using hazard pointers.

std::shared_ptr<T> pop() {
  std::atomic<void*>& hp = get_hazard_pointer_for_current_thread();
  node* old_head = head.load();  // #1
  do {
    node* temp;
    do {
      temp = old_head;
      hp.store(old_head);        // #2
      old_head = head.load();    // #3
    } while (old_head != temp);  // #4
  } while (old_head &&
           !head.compare_exchange_strong(old_head, old_head->next));
  hp.store(nullptr);
  // ...
}

The book explains the role of the inner loop:

You have to do this in a while loop to ensure that the node hasn't been deleted between the reading of the old head pointer #1 and the setting of the hazard pointer #2. During this window no other thread knows you're accessing this particular node. Fortunately, if the old head node is going to be deleted, head itself must have changed, so you can check this and keep looping until you know that the head pointer still has the same value you set your hazard pointer to #4.

According to the implementation of pop, if another thread deletes the head node by pop between #1 and #2, then head will be modified to the new node.

What confuses me is, can the modification of head by other threads be seen by the current thread in time? For example, if the new value of head has not been propagated to the current thread, then #1 and #3 will still read the same value (the old value), causing the inner while loop to exit and in turn the outer while loop accessing old_head->next, resulting in undefined behavior.

I've searched stackoverflow for some answers. For example, this answer says

The default memory ordering of std::memory_order_seq_cst provides a single global total order for all std::memory_order_seq_cst operations across all variables. This doesn't mean that you can't get stale values, but it does mean that the value you do get determines and is determined by where in this total order your operation lies.

This comment says

Every atomic variable has its own modification order that all threads can agree on, but that only serializes modifications, not reads. The coherency requirements involving reads just guarantee that if you've seen one value in the modification order, you can't see an earlier one.

But cppreference says

Each memory_order_seq_cst operation B that loads from atomic variable M, observes one of the following:

  • the result of the last operation A that modified M, which appears before B in the single total order

...

So what exactly should the answer to my question be?

Also, if a weaker ordering (like release-acquire or relaxed) is used here, would the above problem arise?

Aucun commentaire:

Enregistrer un commentaire