C++ Concurrency in Action 中危险指针的实现是否存在缺陷？

Question

我正在阅读《C++ Concurrency in Action》第二版。下面的代码来自清单 7.6。它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循环中执行此操作，以确保node在读取旧head指针#1和设置危险指针#2之间没有删除。在此窗口期间，没有其他线程知道您正在访问该特定节点。幸运的是，如果旧head节点要被删除，head那么它本身一定已经发生了变化，因此您可以检查这一点并继续循环，直到您知道该head指针仍然具有与您设置危险指针相同的值#4。

根据 的实现，如果另一个线程在和之间pop删除了头节点，则将被修改为新节点。pop#1#2head

令我困惑的是，其他线程的修改能否head及时被当前线程看到？例如，如果 的新值head尚未传播到当前线程，则#1和#3仍会读取相同的值（旧值），导致内while循环退出，进而外while循环访问old_head->next，从而导致未定义的行为。

我在 stackoverflow 上搜索了一些答案。例如，这个答案说

默认的内存排序std::memory_order_seq_cst为所有变量上的所有操作提供了一个全局总顺序std::memory_order_seq_cst。这并不意味着您无法获得过时的值，但它确实意味着您获得的值决定了您的操作在整个顺序中的位置。

这条评论说

每个原子变量都有自己的修改顺序，所有线程都可以同意该顺序，但这仅序列化修改，而不序列化读取。涉及读取的一致性要求只是保证，如果您在修改顺序中看到了一个值，则无法看到更早的值。

但cppreference说

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

• 修改 的最后一个操作的结果，在单个全序中出现在 B 之前AM

...

那么我的问题的答案到底应该是什么？

另外，如果这里使用较弱的排序（如release-acquire或relaxed），是否会出现上述问题？

---

这是代码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当没有危险指针指向它时，弹出 指向的节点并释放它。修改head是通过 实现的compare_exchange_strong。

Answer 1

不，我不认为它有缺陷。

为了验证算法是否正确，我这里再注释几行代码。我重写了第 8 行，以明确它从另一个线程的危险指针进行加载。

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));
                                 // #5 deref of old_head
                                 // #6 the compare_exchange
  hp.store(nullptr);             // #7 
  std::shared_ptr<T> res;
  if (old_head) {
    res.swap(old_head->data);
    if (other_thread_hp.load() == old_head)
                                 // #8
      reclaim_later(old_head);
    else
      delete old_head;           // #9
    delete_nodes_with_no_hazards();
  }
  return res;
}

非正式的理由

假设线程 A 尝试安全地取消引用old_head，而线程 B 想要删除它。

例如，compare_exchange_strong线程 B 中的第 6 行（简称 B6）完全有可能实时发生在负载 A1 和 A3 之间，但直到稍后才对线程 A 可见。

然而，我们有顺序一致性。每个线程必须按顺序观察操作 B6 和 B8。因此，如果 B6 直到 A3 之后才对 A 可见，那么 B8 直到更晚才对 A 可见，到那时，存储 A2 将生效。换句话说，加载 B8 必须观察 A3 之前的所有存储，尤其包括 A2。因此，要么 B8 将返回来自 A 的非空危险指针，在这种情况下，删除不会完成；否则它返回nullptr，这只有在存储 A7 变得可见时才会发生，并且此时取消引用 A5 已经完成。

因此，如果 B6 执行和它变得全局可见之间可能存在延迟，则实现必须安排线程 B 中的所有后续操作（特别是 B8）停止，直到 B6 变得可见之后。在当今的硬件上，这种延迟的典型原因是 B6 处的存储进入存储缓冲区。因此，为了确保顺序一致性，编译器必须在 B6 和 B8 之间插入一条屏障指令，该指令将等待存储缓冲区耗尽并提交到一致的 L1 缓存，然后再继续。

编辑：对于关于延迟非原子操作的评论中的问题：事情有点复杂，因为 B6 是读取-修改-写入，但出于内存排序的目的，您可以将其视为由加载（B6L）和商店（B6S），两者都是seq_cst. 出于对非seq_cst操作（包括所有非原子操作）进行排序的目的，seq_cst存储只是释放存储，并且seq_cst加载仅仅是获取加载。因此，事实上，B6S 之后的非原子操作不必“停止”，并且除非另有限制，否则可能会在 B6S 之前变得可见。（然而，它们在 B6L 之前无法可见，因为它是获取的。）

但出于同样的原因，B8 是获取的。这确实需要稍后的操作（包括 B9 等非原子操作）停止，直到 B8 变得可见之后。（这里 B9 位于条件分支的一侧，该分支取决于 B8 加载的值，但如果没有获取屏障，它仍然可以开始进行推测性加载。）因此，实际上，最终结果是 B9 必须仅在 B6S 之后才可见，因为B9必须等待B8，而B8必须等待B6S。

正确性的正式证明

请记住，C++ 内存模型没有“及时”或“过时”的概念；一切都是根据抽象顺序来定义的。这里所有的原子操作都是seq_cst默认的，因此所有这些操作都有一个总的顺序，并且一致性规则确保它们以所有通常的方式相互观察。

我们将分别为线程 A 或 B 执行的操作 #1 编写 A1、B1 等。另外，让hpA, hpB为属于相应线程的危险指针。让为进入此处代码H0的值，两个线程最初加载为它们的、 和，以下节点的地址。headold_headH1H2

我们要确保 A5 在 B9 之前发生。如果 A5 要取消引用指针H0，则必须加载 A1、A3 都返回H0，这意味着 A2 存储H0到hpA。（或者如果 A1 没有，那么 A3 的倒数第二个和最后一个迭代都必须已加载H0；无论哪种方式，结论都是 A2 存储了H0。）

同样，如果 B6 要删除H0，则 B6 必须H0从加载head并存储H1。因此，如果这两个条件都成立，则 A3 在总顺序上先于 B6（或简称 A3 < B6）；否则 A3 将会被加载H1。根据传递性，以及 seq_cst 总顺序与排序（程序顺序）一致的事实，我们有 A2 < A3 < B6 < B8。

现在既然是全序，要么A7<B8，要么A7>B8。

• 如果 A7 < B8，则 B8 观察nullptrA7 存储的值。由于 A7 是释放存储（由 表示seq_cst），而 B8 是观察 A7 存储的值的获取负载，因此我们认为 A7 发生在 B8 之前。通过排序，A5 发生在 A7 之前，B8 发生在 B9 之前，因此 A5 发生在 B9 之前。因此 B9 将删除H0，但 A5 已经完成对它的取消引用，并且不存在数据竞争或释放后使用。

• 如果 A7 > B8，则 A3 < B8 < A7。因此，B8 必须观察存储 A3（存储了H0）hpA，并且不能观察存储 A7（存储了 ）nullptr。因此，在本例中，B8 加载值H0，该值等于线程 B 的，并且线程 B 推迟了 的old_head删除。因此 A5 处的取消引用是安全的，因为根本没有被删除。H0H0

获取-释放顺序对于该算法来说还不够好。非正式地，获取-释放禁止 LoadLoad、StoreStore 和 LoadStore 重新排序，但仍然允许 StoreLoad 重新排序。因此，A2 可能会在 A3 之后变得可见，这将是灾难性的。 编辑：对于您下面的评论，是的，B6S 也可能在 B8 和 B9 之后变得可见（B7 稍后也会变得可见）。

宽松的订购会更糟糕；例如，A7 可能会在 A5 完成之前变得可见。