Lock-free stack: visibility issue when checking hazard pointers during pop()?

Question

I'm reading Anthony William's C++ Concurrency in Action. Chapter 7 describes the process of developing a lock-free stack and illustrates common issues that make lock-free programming difficult. Specifically, section 7.2.3 (Detecting nodes that can't be reclaimed using hazard pointers) describes how hazard pointers can be used to avoid a data race and make sure other threads don't delete a node still referenced by another thread.

This code is one of the iterations of pop() illustrated in that chapter:

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:

    if(outstanding_hazard_pointers_for(old_head))
    {
      reclaim_later(old_head);
    }
    else
    {
      delete old_head;
    }

The purpose of the hazard pointers is making sure old_head is deleted when no other threads may still be using it. The suggested implementation of outstanding_hazard_pointers_for is the following:

unsigned const max_hazard_pointers=100;
struct hazard_pointer
{
  std::atomic<std::thread::id> id;
  std::atomic<void*> pointer;
};
hazard_pointer hazard_pointers[max_hazard_pointers];

bool outstanding_hazard_pointers_for(void* p)
{
  for(unsigned i=0; i < max_hazard_pointers; ++i)
  {
    if(hazard_pointers[i].pointer.load() == p)
    {
      return true;
    }
  }

  return false;
}

Basically, the array of hazard pointers is scanned to check whether the pointer to the node looked for is present. I'm wondering why this operation is indeed safe. An atomic load() is performed and even if sequentially consistent ordering is used, load() may load a stale value. As a consequence, p may not be found, and pop() would be deleting a node that is still in use.

Imagine the following happens:

• Thread A starts to execute pop() and is preempted just before executing:

  while(old_head &&
    !head.compare_exchange_strong(old_head,old_head->next));
  

  Thread A thus sees the current head as old_head, which is saved into its hazard pointer. old_head will be dereferenced when the thread wakes up and tries to pop the head invoking head.compare_exchange_strong(old_head, old_head->next).

• Thread B starts invoking pop() down to

  if(outstanding_hazard_pointers_for(old_head))
  

  old_head will be the current head of the stack, that is the same node that thread A is referencing as old_head. Thread B will not delete old_head iff a load() on Thread A's hazard pointer returns the latest value stored by Thread A.

Basically: I'm wondering whether Thread B can load() a stale value instead of the latest one. Said another way, I'm not sure why it has to return the value set by Thread A's (old_node).

Where's the flaw in this reasoning? I cannot find a justification as to why hp.store(old_head) on another thread will happen-before hazard_pointers[i].pointer.load().

Answer 1

I'm answering my own question for two reasons: I think the answer I accepted is not very clear, and JJ15k's comment confirms that impression.

Basically the key is observing that for another thread to make it through if(outstanding_hazard_pointers_for(old_head)) and seeing the same old_head seen by another thread that was preempted before executing while(old_head && !head.compare_exchange_strong(old_head, old_head->next)), it has to have executed head.compare_exchange_strong(old_head, old_head->next) with the same old_head. But then (assuming < indicates a happens-before relationship):

thread A: hp.store(old_head)     < 
thread A: old_head = head.load() < 
thread B: head.compare_exchange_strong(old_head, old_head->next)

Remember that thread B is seeing the same old_head we loaded in the first instruction and it's swapping it's value to old_head->next. We still see the same value in head.load(), that's why it Thread A hp.store(old_head) happens-before the Thread B compare_exchange_strong.

So the thread that is about to check whether the head contained in the hazard pointer can be deleted has to see old_head. Also notice the fundamental role played by old_head = head.load() (and the loop that contains those statements that may seem redundant at first sight). Without that load operation, there would be no happens-before relationship between the store of old_head into hp and the compare_exchange_strong.

I hope this answers your question.

Answer 2

My understanding of the code is the following.

If hp.store(old_head) in another thread NOT happen-before the call hazard_pointers[i].pointer.load() in this thread, it means that this thread successfully performed head.compare_exchange_strong(old_head,old_head->next) call. It means that for another thread old_head != temp, so it will perform another attempt to store a proper old_head as a thread's hp.

And it means that the original old_head pointer in the current thread can be safely deleted, since it's not actually used by another thread.