《C++ Concurrency in Action》中hazard pointer的pop实现是否存在缺陷？

我正在阅读《C++ Concurrency in Action》第二版，以下是清单7.6中用hazard pointer实现栈的pop()函数核心代码：

std::shared_ptr<T> pop() {
  std::atomic<void*>& hp = get_hazard_pointer_for_current_thread();
  node* old_head = head.load();  // #1
  do {
    node* temp;
    do {
      temp = old_head;
      hp.store(old_head);        // #2
      old_head = head.load();    // #3
    } while (old_head != temp);  // #4
  } while (old_head &&
           !head.compare_exchange_strong(old_head, old_head->next));
  hp.store(nullptr);
  // ...
}

书中对内层循环的作用解释如下：

必须使用while循环来确保在读取旧head指针（#1）和设置hazard pointer（#2）之间，node未被删除。在此期间没有其他线程知道你正在访问该特定节点。幸运的是，如果旧head节点即将被删除，head本身必须已更改，因此你可以检查这一点并持续循环，直到确定head指针的值与你设置hazard pointer的值相同（#4）。

根据pop()的实现，如果其他线程在#1和#2之间通过pop删除了head节点，head会被修改为新节点。我困惑的是：其他线程对head的修改能否被当前线程及时感知？比如，如果head的新值尚未传播到当前线程，#1和#3仍会读取相同的旧值，导致内层while循环退出，进而外层while循环访问old_head->next，引发未定义行为。

我查找了相关资料，整理出几个关键信息：

• 默认的std::memory_order_seq_cst内存序会为所有原子操作提供单一全局总序，但这不代表不会读到过期值，只是读到的值在这个总序里有确定的位置。
• 每个原子变量有自己的修改顺序，所有线程都认可这个顺序，但它仅序列化修改操作，而非读取操作；读取的一致性仅保证：如果已经看到修改顺序中的某个值，就不会再看到更早的值。
• cppreference指出：每个对原子变量M的seq_cst加载操作B，会观察到在全局总序中出现在B之前的最后一次修改M的操作A的结果。

核心问题的准确答案 #

当使用默认的std::memory_order_seq_cst时，不会出现你担心的未定义行为，原因如下：

1. 内层循环的核心逻辑是：确保我们设置危险指针（#2）后，读取到的head值（#3）和设置危险指针时的head值（temp）完全一致。如果其他线程在#2到#3之间修改了head，#3会读到新值，循环会重新执行——直到再次设置危险指针后，head的值不再变化。
2. 从内存序角度，seq_cst的全局总序保证：其他线程通过compare_exchange_strong（同样是seq_cst操作）修改head的动作，在全局总序中拥有确定位置。当前线程执行#3的load操作时，要么读到这个最新修改的值，要么读到在它之前的最后一个有效修改值。而内层循环的重试机制会不断重复“设危险指针→读head→校验一致性”的流程，直到我们确认：危险指针指向的节点就是当前有效的head节点，此时其他线程会因为看到这个危险指针，不会删除该节点。

简言之：内层循环的重试逻辑+seq_cst的内存序保证，共同确保了退出内层循环时，old_head是有效的、未被删除的节点，后续访问old_head->next是安全的。

弱内存序的影响 #

如果替换为更弱的内存序，情况会有所不同：

1. release-acquire内存序 #

如果将head.load()改为memory_order_acquire，compare_exchange_strong的成功操作使用memory_order_release（失败操作使用memory_order_acquire），同时保证危险指针的存储操作使用memory_order_release：

• 这种情况下，release-acquire的同步关系可以保证：其他线程成功修改head的release操作，会被当前线程的acquire load同步，确保当前线程能看到head的新值。内层循环的重试逻辑依然有效，不会出现未定义行为。
• 需要注意危险指针的内存序设置，必须确保其他线程在检查危险指针时，能看到当前线程注册的危险指针，否则仍有节点被误删的风险。

2. relaxed内存序 #

如果使用memory_order_relaxed，原子操作之间没有任何同步关系和顺序保证：

• 当前线程可能持续读取到head的旧值，即使其他线程已经修改了它。这会导致内层循环错误退出，进而访问已被删除节点的next指针，直接引发未定义行为。
• 因此，绝对不能用relaxed内存序实现这个逻辑，它无法保证线程间的修改可见性，会彻底破坏hazard pointer的安全机制。

以下是完整的pop()代码：

std::shared_ptr<T> pop() {
  std::atomic<void*>& hp = get_hazard_pointer_for_current_thread();
  node* old_head = head.load();  // #1
  do {
    node* temp;
    do {
      temp = old_head;
      hp.store(old_head);        // #2
      old_head = head.load();    // #3
    } while (old_head != temp);  // #4
  } while (old_head &&
           !head.compare_exchange_strong(old_head, old_head->next));
  hp.store(nullptr);  // Clear hazard pointer once you're finished
  std::shared_ptr<T> res;
  if (old_head) {
    res.swap(old_head->data);
    if (outstanding_hazard_pointers_for(old_head)) // Check for hazard pointers referencing a node before you delete it.
      reclaim_later(old_head);
    else
      delete old_head;
    delete_nodes_with_no_hazards();
  }
  return res;
}

pop()弹出head指向的节点，并在没有hazard pointer指向它时释放该节点，修改head通过compare_exchange_strong实现。

内容的提问来源于stack exchange，提问作者Pluto