Programmiersprache C++: Hazard Pointers in C++26

C++26 führt Hazard Pointer ein. Das Proposal P2530R3 gibt eine gute Erklärung, worum es sich dabei handelt:

Modernes C++ – Rainer Grimm

Rainer Grimm ist seit vielen Jahren als Softwarearchitekt, Team- und Schulungsleiter tätig. Er schreibt gerne Artikel zu den Programmiersprachen C++, Python und Haskell, spricht aber auch gerne und häufig auf Fachkonferenzen. Auf seinem Blog Modernes C++ beschäftigt er sich intensiv mit seiner Leidenschaft C++.

A hazard pointer is a single-writer multi-reader pointer that can be owned by at most one thread at any time. Only the owner of the hazard pointer can set its value, while any number of threads may read its value. A thread that is about to access dynamic objects acquires ownership of hazard pointer(s) to protect such objects from being reclaimed. The owner thread sets the value of a hazard pointer to point to an object in order to indicate to concurrent threads — that may remove such object — that the object is not yet safe to reclaim.

Hazard pointers are owned and written by threads that act as accessors/protectors (i.e., protect removable objects from unsafe reclamation in order to access such objects) and are read by threads that act as removers/reclaimers (i.e., may remove and try to reclaim objects). Removers retire removed objects to the hazard pointer library (i.e., pass the responsibility for reclaiming the objects to the library code rather than normally by user code). The set of protector and remover threads may overlap.

Schutz und Rückgewinnung

Kurz gesagt garantieren Hazard Pointers, dass die referenzierten Objekte gelöscht werden, wenn sie nicht mehr erforderlich sind. Hazard Pointers führen Schutz- und verzögerte Rückgewinnungsfunktionen aus und interagieren miteinander.

• Schutz: Sie garantieren, dass Objekte nur dann zerstört werden, wenn sie nicht mehr benötigt werden.
• Aufgeschobene Rückgewinnung: Sammelt die zurückgezogenen Objekte und extrahiert deren Werte in einen Set. Liest die Werte aller Hazard Pointers und vergleicht sie mit den Adressen der extrahierten Werte im Set. Wenn ein Wert aus dem Set nicht in den Werten der Hazard Pointers gefunden wird, kann er zerstört werden. Wenn er gefunden wird, wird er wieder in das Set der zurückgezogenen Objekte aufgenommen.

Korrektheit und Performance

Was sind die Vorteile von Hazard Pointers? Meine Antwort besteht aus zwei Punkten: Korrektheit und Performance. Die Korrektheit lässt sich anhand eines einfachen Beispiels veranschaulichen:

Node* currentNode = this->head;
Node* nextNode = currentNode->next;

Die entscheidende Frage zu diesem kleinen Codeausschnitt lautet: Wie können wir sicherstellen, dass currentNode noch gültig ist? Während ein Thread diesen Code ausführt, greift möglicherweise bereits ein anderer Thread auf currentNode zu.

Atomare Compare-and-Swap-(CAS)-Operationen verschärfen dieses Problem. In C++ wird für diesen Zweck typischerweise die Operation compare_exchange_strong verwendet. CAS-Operationen leiden jedoch unter dem ABA-Problem. Ich diskutiere das ABA-Problem ausführlicher in meinem Artikel Deferred Reclamation in C++26: Read-Copy Update und Hazard Pointers. Die Lösung des Problems liegt auf der Hand: automatische Garbage Collection. Genau das bieten Hazard Pointers.

Mit C++14 wurden Reader-Writer-Locks eingeführt. Mit diesen speziellen Locks werden Lese-Threads anders behandelt als Schreib-Threads. Das bedeutet, dass beliebig viele Lese-Threads gleichzeitig ausgeführt werden können, aber nur ein Schreib-Thread. Dadurch versprechen Reader-Writer-Locks eine Performanceverbesserung gegenüber exklusiven Locks.

Das Proposal P2530R3 liefert ein schönes Beispiel für eine Datenstruktur, die überwiegend gelesen wird. Dabei kommen ein klassischer Reader-Writer-Lock und ein Hazard Pointer zum Einsatz.

Die typische Latenz beim Erstellen beziehungsweise Löschen von hazard_pointer in der Folly-Implementierung auf einem aktuellen Standardserver beträgt etwa 4 ns. Einen vorab erstellten hazard_pointer zu verwenden, erfordert in der Regel eine Unterbrechung von weniger als einer Nanosekunde, um den Schutz zu aktivieren.

Die offene Bibliothek Folly von Facebook bietet die Referenzimplementierung von Hazard Pointers.

Klassen und Funktionen

Hazard Pointers bestehen aus den beiden Klassen hazard_pointer_obj_base und hazard_pointer sowie den beiden Funktionen make_hazard_pointer und swap.

• hazard_pointer_obj_base ist die Basisklasse der zu schützenden Klasse und stellt die Funktion retire bereit.
• hazard_pointer stellt die Funktionen empty, protect, try_protect, reset_protection und swap zur Verfügung
• make_hazard_pointer erstellt einen Hazard Pointer.

Wie geht es weiter?

RCU steht für Read Copy Update und ist eine Synchronisationstechnik für Datenstrukturen, die fast ausschließlich lesbar sind. Paul McKenney hat die Technik entwickelt, die seit 2002 im Linux-Kernel verwendet wird. RCU wird gerne im Zusammenhang mit Hazard Pointers erwähnt und sind Thema meines nächsten Beitrags.

(rme)