I'm reading the book C++ Concurrency in Action. There is an example of using hazard pointer to implement a lock-free stack data structure. I am really puzzled, can the implementation of pop() really detect nodes that can't be reclaimed? The code is as follows:
std::shared_ptr<T> pop()
{
std::atomic<void*>& hp = get_hazard_pointer_for_current_thread();
node* old_head = head.load();
do
{
node* temp;
do
{
temp = old_head;
hp.store(old_head);
old_head = head.load();
} while(old_head != temp);
}
while(old_head &&
!head.compare_exchange_strong(old_head,old_head->next));
hp.store(nullptr);
std::shared_ptr<T> res;
if(old_head)
{
res.swap(old_head->data);
if(outstanding_hazard_pointers_for(old_head))
{
reclaim_later(old_head);
}
else
{
delete old_head;
}
delete_nodes_with_no_hazards();
}
return res;
}
I have a doubt about this fragment:
do
{
node* temp;
do
{
temp = old_head;
hp.store(old_head);
old_head = head.load();
} while(old_head != temp);
}
while(old_head &&
!head.compare_exchange_strong(old_head,old_head->next));
hp.store(nullptr);
The purpose of the hazard pointers (hp) is making sure the object that old_head point to is not deleted when other threads may still be using it. It really work when old_head == hp.load(). But there is a state here that old_head != ph.load(). In this state, the dereference of old_head is not safe.
For Example:
a->b->c->d)head is the pointer to the top of the stack.(head->a)A,Thread B,Thread C)First, thread A is preempted before head and old_head do compare/exchange
....
<================A is preempted here==================>
while(old_head &&
!head.compare_exchange_strong(old_head,old_head->next));
....
the state of Thread A and stack:
stack:a->b->c->d (head->a)
Thread A:hp->a old_head->a
then, thread B calls the pop() and is preempted after head and old_head do compare/exchange
...
while(old_head &&
!head.compare_exchange_strong(old_head,old_head->next))
<================B is preempted here==================>
hp.store(nullptr);
...
the state of Thread A,Thread B and stack:
stack:a->b->c->d (head->b)
Thread A: hp->a old_head->a
Thread B: hp->a old_head->a
then, thread A run and is preempted in while loop after head and old_head do compare/exchange only once. Now, hp of thread A have not changed, but old_head points to b.
...
while(old_head &&
<================A is preempted here==================>
!head.compare_exchange_strong(old_head,old_head->next));
...
the state of Thread A,Thread B and stack:
stack:a->b->c->d (head->b)
Thread A: hp->a old_head->b
Thread B: hp->a old_head->a
then,the thread C calls the pop() and runs very fast until pop() returns, the element b of stack is deleted.
the state of Thread A,Thread B and stack:
stack:a->b[deleted] c->d (head->c)
Thread A: hp->a old_head->b[deleted]
Thread B: hp->a old_head->a
Now, thread A continue to run.
head.compare_exchange_strong(old_head,old_head->next)
program is crashed because of the dereference of old_head (Dangling pointer)
If the implementation is right, where did the above example go wrong?
Now, hp of thread A have not changed, but old_head points to b.
Yes, but only temporarily after the compare_exchange attempt. Thread B has updated head via its compare_exchange to b, so when thread A attempts to pop a, the compare_exchange fails and updates old_head to point to b, but then thread A starts another iteration of the outer loop. So it again performs the inner loop:
do
{
temp = old_head;
hp.store(old_head);
old_head = head.load();
} while(old_head != temp);
So when a thread reaches the while of the outer loop
while(old_head &&
!head.compare_exchange_strong(old_head,old_head->next));
it is guaranteed that old_head == hp.load() (you could add an according assertion before these lines).
That way it is guaranteed that each thread has a safe reference in old_head before it attempts to remove it from the stack.
See Memory ordering for hazard-pointers for more details about how hazard pointers provide the guarantee that either an object is protected via a hazard pointer (i.e., the thread has acquired a safe reference), or the thread that tries to acquire a safe reference to some object sees the updated value (in this case of head) and therefore has to perform a retry.