这个风险指针示例因ABA问题存在缺陷吗？

Question

在书籍C++ Concurrency in Action中，作者给出了使用危险指针实现无锁栈数据结构的示例。代码的一部分如下所示：

std::shared_ptr<T> pop()
{
    std::atomic<void*>& hp=get_hazard_pointer_for_current_thread();
    node* old_head=head.load();
    node* temp;
    do
    {
        temp=old_head;
        hp.store(old_head);
        old_head=head.load();
    } while(old_head!=temp);
    // ...
}

描述说：

你必须在一个 while 循环中执行此操作，以确保节点在读取旧 head 指针和设置危险指针之间未被删除。在此窗口期间，没有其他线程知道您正在访问此特定节点。幸运的是，如果旧的 head 节点将被删除，则 head 本身必须已更改，因此您可以检查这一点并继续循环，直到您知道 head 指针仍具有与您设置危险指针相同的值。

我认为代码存在缺陷，因为 head 节点受到 ABA 问题的影响。即使 head 的值保持不变，它最初指向的节点可能已被删除。分配了一个新的 head 节点，它恰好具有与先前节点相同的地址值。

- Lingxi

---

我同意你的观点，但除了运行数小时的单元测试直到出现ABA问题外，我无法证明你是正确的。为了避免这里的ABA问题，我会比较节点的“值”，而不是“地址”。 - YSC

如果我没理解错的话，你展示给我们的代码仅涉及到危险指针(hazard pointer)，它只包含线程当前正在读取的某个地址，其他线程不应该乱改。我真的不明白为什么只有这样的代码会出现ABA问题，因为你从来没有实际查看head指向的内容。 - Caninonos

换句话说，那段代码似乎从来没有假设 head == old_head 意味着 *head 没有变化，而这恰恰是导致 ABA 问题的错误假设，除非我搞错了。 - Caninonos

@Caninonos 再想一想，你说得很对。 - Lingxi

Answer 1

load()操作的默认memory_order是std::memory_order_seq_cst，它确保所有操作的顺序一致（全局总序）：

每个从原子变量M加载的memory_order_seq_cst操作B都会观察到以下情况之一：

• 最后一个修改M的操作A的结果，在单个总序中出现在B之前
• 或者，如果存在这样的A，则B可能会观察到对M进行的某些不是memory_order_seq_cst且不发生在A之前的修改的结果
• 或者，如果不存在这样的A，B可能会观察到对M的某些不相关修改的结果，这些修改不是memory_order_seq_cst。

所以，如果节点被修改（删除），并且这发生在总全局顺序的第二次读取之前，您保证会看到该更改，因此循环将继续执行。如果此修改是有序的，则没有任何伤害，因为已经设置了风险指针。

您拥有此保证，因为对危险指针的存储也使用了std::memory_order_seq_cst。这个内存顺序为加载操作提供了acquire操作，为存储操作提供了release操作，防止在同一线程内重新排序。因此，“成功”的读取（old_head == temp）保证保存了正确的数据。

将这两个加载操作视为同步点-因为它们执行acquire操作，它们与修改这些值的相应release操作进行同步，导致所有写入变得可见。

---

你所描述的问题并不影响示例代码。 pop() 函数用于删除顶部元素，它会执行此操作。如果在此期间添加/删除元素，则它将弹出它，无论其地址是什么（甚至可能与先前获取的地址相同）。这是一个完全不同的问题。请考虑：

concurrent_stack<int> p;
if (!p.empty() && (p.top() == 5))
{
  auto t = p.pop();
  assert( t ); // May fail
  assert( *t == 5 ); // May fail
}

两个断言可能会失败，如果许多线程非常密集地使用堆栈，则很可能经常失败。但这不是由于pop()的实现不正确，而是因为您需要更强的访问限制来确保最后检查的元素确实从堆栈中删除。

- Mateusz Grzejek