C++Concurrency in action :Can the Listing7. 6(使用危险指针的 pop() 实现)真的检测到无法回收的节点吗？

Question

我正在阅读 C++ Concurrency in Action 一书。有一个使用危险指针实现无锁栈数据结构的例子。真的很纳闷，pop()的实现真的能检测到不能回收的节点吗？代码如下:

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;
}

我对这个片段有疑问:

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);

危险指针 (hp) 的目的是确保 old_head 指向的对象在其他线程可能仍在使用时不会被删除。当 old_head == hp.load()时它真的有效.但是这里有一个状态 old_head != ph.load() .在这种状态下，取消引用 old_head不安全。
例如:

堆栈中有 4 个元素。( a -> b -> c -> d )

head是指向栈顶的指针。(head->a)

3 个主题正在调用 pop()( 线程 A ,线程 B ,线程 C )

首先，线程A在 head之前被抢占和 old_head做比较/交换

....
<================A is preempted here==================>
while(old_head &&
      !head.compare_exchange_strong(old_head,old_head->next));
....

线程A和堆栈的状态:

stack:a->b->c->d (head->a)
Thread A:hp->a old_head->a

然后，线程 B 调用 pop()并且在 head 之后被抢占和 old_head做比较/交换

...
while(old_head &&
    !head.compare_exchange_strong(old_head,old_head->next))
<================B is preempted here==================>
hp.store(nullptr);
...

线程A、线程B和栈的状态:

stack:a->b->c->d (head->b)
Thread A: hp->a old_head->a 
Thread B: hp->a old_head->a

然后，线程 A 运行并在 head 之后在 while 循环中被抢占和 old_head做比较/交换 只有一次 .现在，线程 A 的 hp 没有改变，但 old_head 指向 b。

...
while(old_head &&
<================A is preempted here==================>
    !head.compare_exchange_strong(old_head,old_head->next));
...

线程A、线程B和栈的状态:

stack:a->b->c->d (head->b)
Thread A: hp->a old_head->b 
Thread B: hp->a old_head->a

然后，线程 C 调用 pop()并且运行非常快，直到 pop()返回，元素 b 堆栈被删除。

线程A、线程B和栈的状态:

stack:a->b[deleted] c->d (head->c)
Thread A: hp->a old_head->b[deleted]
Thread B: hp->a old_head->a

现在，线程 A 继续运行。
head.compare_exchange_strong(old_head,old_head->next)
由于old_head(悬空指针)的取消引用，程序崩溃

如果实现是正确的，上面的例子是哪里出错了？

Answer 1

Now, hp of thread A have not changed, but old_head points to b.

是的，但只是暂时在 compare_exchange 之后试图。话题 B 已更新 head通过其 compare_exchange至 b ，所以当线程 A 试图弹出 a , compare_exchange失败并更新 old_head指向 b ，但随后线程 A 开始了 的另一次迭代外 环形。所以它再次执行内部循环:

    do
    {
      temp = old_head;
      hp.store(old_head);
      old_head = head.load();
    } while(old_head != temp);

所以当一个线程到达 while外环的

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

保证 old_head == hp.load() (您可以在这些行之前添加相应的断言)。

这样可以保证每个线程在 old_head 中都有一个安全的引用。在它尝试从堆栈中删除它之前。

见 Memory ordering for hazard-pointers有关危险指针如何提供通过危险指针保护对象(即，线程已获取安全引用)或尝试获取对某个对象的安全引用的线程看到更新值的保证的更多详细信息(在这种情况下 head )，因此必须执行重试。