action:Can Listing7.6 中的 C++Concurrency（An implementation of pop() using hazard pointers）真的能检测到不能回收的节点吗？

Question

我正在阅读 C++ 并发实战 一书。有一个使用冒险指针实现无锁栈数据结构的例子。我真的很疑惑，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 theads 正在调用 pop()( Thread A,Thread B,Thread C)

首先线程A在head和old_head做compare/exchange

之前被抢占

....
<================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 执行 compare/exchange

之后被抢占

...
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 和 old_head 之后的 while 循环中被抢占 compare/exchange 仅执行一次 .现在线程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() returns，元素 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 已通过其 compare_exchange 将 head 更新为 b，因此当线程 A 尝试弹出 a 时，compare_exchange 失败并更新 old_head指向 b、，然后线程 A 开始 outer 循环 的另一次迭代。所以它再次执行内部循环：

    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），因此必须重试。

action:Can Listing7.6 中的 C++Concurrency（An implementation of pop() using hazard pointers）真的能检测到不能回收的节点吗？

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

c++

lock-free