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 thenode
hasn't been deleted between the reading of the oldhead
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 oldhead
node is going to be deleted,head
itself must have changed, so you can check this and keep looping until you know that thehead
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 allstd::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
operationB
that loads from atomic variableM
, observes one of the following:
- the result of the last operation
A
that modifiedM
, 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