[FIXED] Ist die Implementierung des Gefahrenzeigers in C++ Concurrency in Action fehlerhaft?

Ausgabe

Ich lese gerade die zweite Ausgabe von C++ Concurrency in Action. Der folgende Code stammt aus Listing 7.6. Es implementiert pop()für den Stack unter Verwendung von Gefahrenzeigern.

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);
  // ...
}

Das Buch erklärt die Rolle der inneren Schleife:

Das müssen Sie in einer whileSchleife machen, um sicherzustellen, dass nodezwischen dem Lesen des alten headZeigers #1und dem Setzen des Gefahrenzeigers#2 der nicht gelöscht wurde . Während dieses Fensters weiß kein anderer Thread, dass Sie auf diesen bestimmten Knoten zugreifen. Wenn der alte headKnoten gelöscht werden soll, headmuss er sich glücklicherweise selbst geändert haben, sodass Sie dies überprüfen und die Schleife fortsetzen können, bis Sie wissen, dass der headZeiger immer noch denselben Wert hat, auf den Sie Ihren Gefahrenzeiger gesetzt haben#4 .

popWenn ein anderer Thread den Kopfknoten popzwischen #1und löscht #2, wird er gemäß der Implementierung von headin den neuen Knoten geändert.

Was mich verwirrt ist, kann die Änderung headdurch andere Threads rechtzeitig vom aktuellen Thread gesehen werden? Wenn beispielsweise der neue Wert von headnicht an den aktuellen Thread weitergegeben wurde, liest #1und #3immer noch denselben Wert (den alten Wert), wodurch die innere whileSchleife beendet wird und die äußere whileSchleife wiederum auf old_head->next, was zu einem undefinierten Verhalten führt.

Ich habe Stackoverflow nach einigen Antworten durchsucht. Diese Antwort sagt zum Beispiel

Die standardmäßige Speicherreihenfolge von std::memory_order_seq_cststellt eine einzige globale Gesamtreihenfolge für alle std::memory_order_seq_cstOperationen über alle Variablen hinweg bereit. Dies bedeutet nicht, dass Sie keine veralteten Werte erhalten können , aber es bedeutet, dass der Wert, den Sie erhalten, bestimmt und dadurch bestimmt wird, wo in dieser Gesamtreihenfolge Ihre Operation liegt.

Dieser Kommentar sagt

Jede atomare Variable hat ihre eigene Modifikationsreihenfolge, auf die sich alle Threads einigen können, die aber nur Modifikationen serialisiert, nicht liest. Die Kohärenzanforderungen, die Lesevorgänge betreffen , garantieren lediglich, dass Sie, wenn Sie einen Wert in der Änderungsreihenfolge gesehen haben, keinen früheren sehen können .

Aber cpreference sagt

Jede memory_order_seq_cstOperation B, die von der atomaren Variablen geladen wird M, beobachtet eine der folgenden Bedingungen:

• das Ergebnis der letzten Operation A, die geändert Mhat, die vor B in der einzelnen Gesamtreihenfolge erscheint

…

Wie genau soll denn die Antwort auf meine Frage lauten?

Auch wenn hier eine schwächere Reihenfolge (wie Release-Acquire oder Relaxed) verwendet wird, würde das obige Problem auftreten?

Hier ist der Code von 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()öffnet den Knoten, auf den gezeigt wird, headund gibt ihn frei, wenn kein Gefahrenzeiger darauf zeigt. Das Ändern von headwird erreicht durch compare_exchange_strong.

Lösung

Nein, ich glaube nicht, dass es defekt ist.

Um zu überprüfen, ob der Algorithmus korrekt ist, lassen Sie mich hier noch ein paar Codezeilen kommentieren. Ich habe Zeile 8 umgeschrieben, um deutlich zu machen, dass sie vom Gefahrenzeiger des anderen Threads lädt.

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

Formlose Begründung

Angenommen, Thread A versucht sicher zu dereferenzieren, old_headwährend Thread B ihn löschen möchte.

Es ist durchaus möglich, dass beispielsweise die compare_exchange_strongLinie 6 in Thread B (kurz B6) echtzeitmäßig zwischen den Lasten A1 und A3 auftritt, für Thread A aber erst später sichtbar wird.

However, we have sequential consistency. Every thread must observe the operations B6 and B8 in that order. So if B6 didn’t become visible to A until after A3, then B8 cannot become visible to A until later still, and by that time, store A2 will have taken effect. In other words, load B8 must observe all stores that preceded A3, including in particular A2. So either B8 will return the non-null hazard pointer from A, in which case the delete is not done; or else it returns nullptr, which can only happen if store A7 has become visible, and by that time the dereference A5 has already completed.

Thus, if there can be a delay between when B6 is executed and when it becomes globally visible, then the implementation must arrange that all subsequent operations in thread B, including in particular B8, are stalled until after B6 does become visible. On present-day hardware, the typical reason for such a delay is that the store at B6 went into a store buffer. So to ensure sequential consistency, the compiler has to insert a barrier instruction between B6 and B8, which will wait for the store buffer to drain and commit to coherent L1 cache before continuing on.

Edit: To your question in comments about delaying non-atomic operations: Things are complicated a bit because B6 is a read-modify-write, but for memory ordering purposes, you can think of it as consisting of a load (B6L) and a store (B6S), both of which are seq_cst. For purposes of ordering with respect to non-seq_cst operations, including all non-atomic operations, a seq_cst store is simply a release store, and a seq_cst load is merely an acquire load. So indeed, non-atomic operations that follow B6S do not have to “stall” and, unless otherwise restricted, may become visible before B6S does. (They cannot become visible before B6L however, because it is acquire.)

But by the same token, B8 is acquire. This does require later operations, including non-atomic operations such as B9, to stall until after B8 has become visible. (Here B9 is on one side of a conditional branch which depends on the value loaded by B8, but without the acquire barrier, it could still start doing loads speculatively.) So indeed, the net result is that B9 must become visible only after B6S, because B9 must wait for B8 which must wait for B6S.

Formal proof of correctness

Remember that the C++ memory model has no concept of “in time” or “stale”; everything is defined in terms of abstract orderings. Here all the atomic operations are seq_cst by default, so there is a total order on all of them, with coherency rules ensuring that they observe each other in all the usual ways.

We’ll write A1, B1, etc, for operation #1 as executed by Threads A or B respectively. Also, let hpA, hpB be the hazard pointers belonging to the corresponding threads. Let H0 be the value of head going into the code here, which both threads initially load as their old_head, and H1, H2 the addresses of the following nodes.

We want to make sure that A5 happens before B9. If A5 is going to dereference pointer H0, it must be that loads A1, A3 both returned H0, which means that A2 stored H0 to hpA. (Or if A1 didn’t, then both the second-to-last and last iterations of A3 must have loaded H0; either way the conclusion is that A2 stored H0.)

Likewise, if B6 is going to delete H0, it must be that B6 loaded H0 from head and stored H1. So if both these conditions hold, then A3 precedes B6 in the total order (or A3 < B6 for short); otherwise A3 would have loaded H1 instead. By transitivity, and the fact that the seq_cst total order is consistent with sequencing (program order), we have A2 < A3 < B6 < B8.

Now since it is a total order, either A7 < B8 or A7 > B8.

• If A7 < B8, then B8 observes nullptr stored by A7. Since A7 was a release store (implied by seq_cst), and B8 was an acquire load that observed the value stored by A7, we have that A7 happens before B8. By sequencing A5 happens before A7, and B8 happens before B9, so A5 happens before B9. Thus B9 will delete H0, but A5 has already finished dereferencing it and there is no data race or use-after-free.

• If A7 > B8, then we have A3 < B8 < A7. So B8 must observe the store A3 (which stored H0 to hpA), and it must not observe store A7 which stored nullptr. So in this case B8 loads the value H0, which equals thread B’s old_head, and
  the deletion of H0 is deferred by thread B. Thus the dereference at A5 was safe, because H0 is not being deleted at all.

Die Reihenfolge Acquire-Release wäre für diesen Algorithmus nicht gut genug. Informell verbietet das Erfassen-Freigeben das Neuordnen von LoadLoad, StoreStore und LoadStore, lässt aber dennoch das Neuordnen von StoreLoad zu. Als solches könnte A2 nach A3 sichtbar werden, was katastrophal wäre. Bearbeiten : Und zu Ihrem Kommentar unten, ja, B6S könnte auch nach B8 und B9 sichtbar werden (wobei B7 noch später sichtbar wird).

Entspanntes Bestellen wäre noch schlimmer; Beispielsweise könnte A7 sichtbar werden, bevor A5 abgeschlossen ist.

Beantwortet von – Nate Eldredge

Antwort geprüft von – Mary Flores (FixError Volunteer)