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

Question

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

c++multithreadingconcurrencyatomicstdatomic

5

我正在阅读《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);
  // ...
}

这本书解释了内部循环的作用：

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

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

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

我在stackoverflow上搜索了一些答案。例如，this answer说：

默认的内存顺序std::memory_order_seq_cst为所有变量提供了一个单一的全局总序。这并不意味着您不能获得过期的值，但它确实意味着您获得的值取决于您的操作在该总序中的位置。

这篇评论说：

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

但是cppreference说：

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

M 的最后一个操作 A 的结果，在单个完全顺序中出现在 B 之前

...

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

另外，如果使用较弱的顺序（如释放-获取或松散顺序），上述问题会出现吗？

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

- Pluto

1

当考虑无锁原子编程时，我发现忘记关于“时间”和与之相关的一切是有帮助的。内存模型的整个重点在于它是以原则上与墙上的钟无关的顺序来定义的（尽管在现实生活中可能与之相关）。我假设第一个引用答案中的“过时”意味着“您可能无法加载相对于实时更早存储的值”，但这应该是无关紧要的，因为除非您正在进行实时编程，否则您的程序不应关心实时时间如何流逝。 - Nate Eldredge

2

线程安全是一种关系属性；两个或多个代码片段相对于彼此是线程安全的。询问单个线程是否线程安全是无意义的：最好假定其他线程族群存在。您共享了一个代码片段。您需要修改head的代码以及可能使用hp的代码，以确定相对线程安全性。这种无法进行单独分析的能力是并发基本上很难的原因。 - Yakk - Adam Nevraumont

1

“hp必须保证与它的值相同。”但是何时呢？我们实际上只能观察到某些hp的加载和某些head的加载是否返回相同的值。这两个负载不能同时进行，因此了解它们相对于彼此的排序方式至关重要。 - Nate Eldredge

@NateEldredge 是的。据我所知，当我们尝试取消引用 old_head 时，我们必须确保 hp 的值与它相同，而不是 head 而是 old_head，因为 old_head 是当前线程要删除的节点。但在我看来，这似乎偏离了我的问题。 - Pluto

嗯，你的问题是“代码有缺陷吗”，但没有看到两边的代码就无法回答。但我想我知道你在问什么。如果另一个线程在实时方面在＃1和＃3“之间”（称存储为W）存储了head，则可能会出现＃1和＃3都返回相同值的情况。但如果是这样，则W必须在按顺序一致的总排序中后于＃3，并因此也在＃2之后。这将使我们能够推断出另一个线程不会释放我们在＃1和＃3处加载的指针。 - Nate Eldredge

显示剩余11条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Nate Eldredge · Accepted Answer

不，我认为它没有缺陷。

为了验证算法的正确性，让我在这里注释几行代码。我重新编写了第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想要删除它。

很可能，例如在线程B的第6行（B6）中的compare_exchange_strong发生在相对于实时的A1和A3之间进行加载，但直到稍后才可见于线程A。

但是，我们具有顺序一致性。每个线程必须按照那个顺序观察操作B6和B8。因此，如果B6直到A3之后才变得可见，则B8也不能在稍后变得可见，而且到那时，存储A2将已经生效。换句话说，load B8必须观察前面所有的存储，包括特别是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，因此它们之间存在全序关系，并且一致性规则确保它们以所有通常的方式相互观察。

我们将在此处编写A1、B1等，表示由线程A或B执行的操作＃1。同时，让hpA，hpB分别为相应线程所属的危险指针。让H0为进入此代码的head的值，两个线程最初都将其作为它们的old_head加载，并且H1，H2是下一个节点的地址。

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

同样地，如果B6将要删除H0，那么它必须从head加载H0并将H1存储。因此，如果这两个条件都成立，则A3在总序列中领先于B6（或简写为A3 < B6）；否则，A3将加载H1。通过传递性和seq_cst全序关系与排序（程序顺序）一致的事实，我们得到A2 < A3 < B6 < B8。

现在，由于它是一个全序关系，要么A7 < B8，要么A7 > B8。

如果 A7 < B8，则 B8 观察到由 A7 存储的 nullptr。由于 A7 是一个 release store（由 seq_cst 隐含），而 B8 是一个 acquire load，它观察到了 A7 存储的值，我们有 A7 发生在 B8 之前。通过排序 A5 发生在 A7 之前，B8 发生在 B9 之前，因此 A5 发生在 B9 之前。因此 B9 将删除 H0，但是 A5 已经完成对其的解引用，没有数据竞争或使用-after-free。

如果 A7 > B8，则我们有 A3 < B8 < A7。所以 B8必须观察存储 A3（存储了 hpA 中的H0），并且不能观察到存储 nullptr 的 A7。因此，在这种情况下，B8加载值 H0，它等于线程 B 的 old_head，并且删除 H0 延迟到线程 B。因此，在 A5 处的解引用是安全的，因为 H0 根本没有被删除。

仅使用 acquire-release 排序不足以支持此算法。非正式地说，acquire-release 禁止 LoadLoad、StoreStore 和 LoadStore 重排序，但仍允许 StoreLoad 重排序。因此，A2 可以在 A3 之后变得可见，这将是灾难性的。编辑：对于您下面的评论，是的，B6S 也可以在 B8 和 B9 之后变得可见（而 B7 更晚才变得可见）。

松弛排序甚至更糟；例如，A7 可以在 A5 完成之前变得可见。