无锁堆栈：在 pop() 期间检查危险指针时出现可见性问题？

Question

我正在阅读 Anthony William 的 C++ Concurrency in Action。第 7 章描述了开发无锁堆栈的过程，并说明了使无锁编程变得困难的常见问题。具体来说，第 7.2.3 节（使用危险指针检测无法回收的节点）描述了如何使用危险指针来避免数据竞争并确保其他线程不会 delete 一个节点仍然被另一个线程引用。

此代码是该章中说明的 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;
}

我对这个片段有疑问：

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

危险指针的目的是确保在没有其他线程可能仍在使用它时删除 old_head。 outstanding_hazard_pointers_for 的建议实施如下：

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

基本上，扫描风险指针数组以检查是否存在指向要查找的节点的指针。我想知道为什么这个操作确实是安全的。执行原子 load()，即使使用顺序一致的顺序，load() 也可能加载过时值。因此，可能找不到 p，并且 pop() 将删除仍在使用的节点。

假设发生以下情况：

线程A开始执行pop()被抢占刚执行前:
```
while(old_head &&
  !head.compare_exchange_strong(old_head,old_head->next));
```
线程A因此将当前头视为old_head，它被保存到它的风险指针中。 old_head 将在线程唤醒并尝试弹出头部调用 head.compare_exchange_strong(old_head, old_head->next) 时取消引用。
线程 B 开始调用 pop() 直至
```
if(outstanding_hazard_pointers_for(old_head))
```
old_head 将是堆栈的当前头部，即线程 A 引用为 old_head 的同一节点。线程 B 将不是 delete old_head 当且仅当线程 A 的危险指针 return 上的 load() 是线程 A 存储的最新值。

基本上：我想知道线程 B 是否可以 load() 一个陈旧的值而不是最新的值。换句话说，我不确定为什么线程 A (old_node).

设置的值具有到 return

这个推理的漏洞在哪里？我找不到关于为什么另一个线程上的 hp.store(old_head) 会发生在 hazard_pointers[i].pointer.load().

之前的理由

Answer 1

我对代码的理解如下。

如果另一个线程中的 hp.store(old_head) 未在本线程中调用 hazard_pointers[i].pointer.load() 之前发生，则表示该线程成功执行了 head.compare_exchange_strong(old_head,old_head->next) 调用。这意味着对于另一个线程old_head != temp，它将执行另一次尝试将适当的old_head存储为线程的hp。

这意味着可以安全地删除当前线程中的原始 old_head 指针，因为它实际上并没有被另一个线程使用。

Answer 2

我回答我自己的问题有两个原因：我认为我接受的答案不是很清楚，证实了这个印象。

基本上关键是观察另一个线程通过 if(outstanding_hazard_pointers_for(old_head)) 和看到另一个线程看到的相同 old_head 之前被抢占执行while(old_head && !head.compare_exchange_strong(old_head, old_head->next))，它必须用相同的old_head执行head.compare_exchange_strong(old_head, old_head->next)。但是然后（假设 < 表示先发生关系）：

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

请记住，线程 B 正在看到我们在第一条指令中加载的 same old_head，并将它的值交换为 old_head->next。我们仍然在 head.load() 中看到相同的值，这就是线程 A hp.store(old_head) 发生在线程 B compare_exchange_strong.

之前的原因

所以即将检查危险指针中包含的头部是否可以删除的线程有要看old_head。还要注意 old_head = head.load() 所起的基本作用（以及包含那些乍一看似乎多余的语句的循环）。如果没有那个 load 操作，old_head 的 store 到 hp 和 compare_exchange_strong.

之间就不会有 happens-before 关系

我希望这能回答你的问题。

无锁堆栈：在 pop() 期间检查危险指针时出现可见性问题？

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

c++

multithreading

c++11

lock-free

memory-barriers