C++Concurrency in action:Can the Listing7.6(An implementation of pop() using hazard pointers) really detect nodes that can't be reclaimed?

user_8259974 0
Viewed 114

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:

  • 4 elements in the stack.(a->b->c->d)
  • head is the pointer to the top of the stack.(head->a)
  • 3 theads is invoking pop()( Thread 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?

lock-free c++
1 Answers

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.

user_127478330
Related