Lock-freier Stack: Details zu Implementierung von Hazard Pointers, Teil 2

In meinem letzten Artikel habe ich mit der Erläuterung einer Implementierung von Hazard Pointers begonnen, die ich in diesem Beitrag fortsetze.

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++.

Die Retire-Liste

Die RetireList verfügt über die öffentlichen Member-Funktionen isInUse, addNode und deleteUnusedNodes. Darüber hinaus verfügt sie über die innere Klasse RetireNode, ein atomares Mitglied davon, und die private Member-Funktion addToRetiredNodes:

template <typename T, Node MyNode = MyNode<T>>
class RetireList {

  struct RetiredNode {
    MyNode* node;
    RetiredNode* next;
    RetiredNode(MyNode* p) : node(p), next(nullptr) { }
    ~RetiredNode() {
      delete node;
    }
  };

  std::atomic<RetiredNode*> RetiredNodes;
  void addToRetiredNodes(RetiredNode* retiredNode) {
    retiredNode->next = RetiredNodes.load();
    while (!RetiredNodes.compare_exchange_strong(retiredNode->next, retiredNode));
  }

  public:

  bool isInUse(MyNode* node) {
    for (std::size_t i = 0; i < MaxHazardPointers; ++i) {
      if (HazardPointers<T>[i].pointer.load() == node) return true;
    }
    return false;
  }

  void addNode(MyNode* node) {
    addToRetiredNodes(new RetiredNode(node));
  }

  void deleteUnusedNodes() {
    RetiredNode* current = RetiredNodes.exchange(nullptr);
    while (current) {
      RetiredNode* const next = current->next;
      if (!isInUse(current->node)) delete current;
      else addToRetiredNodes(current);
      current = next;
    }
  }
};

Beginnen wir mit der Schnittstelle des Datentyps RetireList. Die Member-Funktion isInUse prüft, ob node in Gebrauch ist. Sie durchläuft dazu das variable Template HazardPointers, das auf den Datentyp des Knotens parametrisiert ist. HazardPointers ist ein C-Array von HazardPointer der Länge 50. Ein HazardPointer besteht aus einer atomaren Thread-ID und einem atomaren Zeiger auf einen Knoten:

constexpr std::size_t MaxHazardPointers = 50;

template <typename T, Node MyNode = MyNode<T>>
struct HazardPointer {
  std::atomic<std::thread::id> id;
  std::atomic<MyNode*> pointer;
};

template <typename T>
HazardPointer<T> HazardPointers[MaxHazardPointers];

Die Verwendung eines STL-Containers wie std::set als HazardPointers ist viel praktischer. std::set ist bereits geordnet und garantiert im Durchschnitt eine konstante Zugriffszeit, hat aber ein großes Problem: Es ist nicht Thread-sicher.

Die Member-Funktion addNode nimmt einen Knoten, ruft die private Member-Funktion addToRetiredNodes auf und fügt den Knoten in einen RetiredNode ein. RetiredNode ist ein RAII-Objekt und garantiert, dass der umschlossene Knoten zerstört wird, wodurch sein Speicher freigegeben wird. Alle ausgemusterten Knoten bilden eine einfach verknüpfte Liste.

Die Member-Funktion deleteUnusedNodes durchläuft die einfach verknüpfte Liste der ausgemusterten Knoten nach folgendem Muster:

void deleteUnusedNodes() {
  RetiredNode* current = RetiredNodes.exchange(nullptr);
  while (current) {
    RetiredNode* const next = current->next;
    if (!isInUse(current->node)) delete current;
    else addToRetiredNodes(current);
    current = next;
  }
}

Es überprüft den aktuellen Knoten, verweist den nächsten Knoten auf current->next und aktualisiert den aktuellen Knoten mit dem nächsten Knoten. Schließlich wird der aktuelle Knoten zerstört, wenn er nicht mehr verwendet oder zu den ausgemusterten Knoten hinzugefügt wird. Die private Member-Funktion addToRetireNodes fügt die ausgemusterten Knoten zur einfach verknüpften Liste hinzu. Um ihre Aufgabe zu erfüllen, lädt sie die ausgemusterten Knoten und macht den neuen Knoten retiredNode zum neuen Kopf der einfach verknüpften Liste.

Bevor retiredNode zum neuen Kopf der einfach verknüpften Liste wird, muss ich sicherstellen, dass es immer noch der Kopf der einfach verknüpften Liste ist, da ein anderer Thread dazwischenkommen und den Kopf der einfach verknüpften Liste ändern könnte. Dank der While-Schleife wird retiredNode nur dann zum neuen Kopf, wenn retiredNode->next = RetiredNodes.load() gilt. Wenn nicht, wird retiredNode->next auf RetiredNodes.load() aktualisiert.

Es fehlt nur noch ein Teil des Puzzles: Der Besitzer des Hazard Pointer:

template <typename T, Node MyNode = MyNode<T>>
class HazardPointerOwner {

  HazardPointer<T>* hazardPointer;

public:
  HazardPointerOwner(HazardPointerOwner const &) = delete;
  HazardPointerOwner operator=(HazardPointerOwner const &) = delete;

  HazardPointerOwner() : hazardPointer(nullptr) {
    for (std::size_t i = 0; i < MaxHazardPointers; ++i) {
      std::thread::id old_id;
      if (HazardPointers<T>[i].id.compare_exchange_strong(
          old_id, std::this_thread::get_id())) {
        hazardPointer = &HazardPointers<T>[i];
        break;
      }
    }
    if (!hazardPointer) {
      throw std::out_of_range(„No hazard pointers available!“);
    }
  }

  std::atomic<MyNode*>& getPointer() {
    return hazardPointer->pointer;
  }

  ~HazardPointerOwner() {
    hazardPointer->pointer.store(nullptr);
    hazardPointer->id.store(std::thread::id());
  }
};

HazardPointerOwner hält einen HazardPointer. Dieser wird im Konstruktor durch Durchlaufen aller HazardPointer gesetzt. Der Aufruf compare_exchange_strong prüft in einem atomaren Schritt, ob der aktuell durchlaufene HazardPointer nicht gesetzt ist, und setzt seine ID auf die ID des jetzt ausgeführten Threads (std::this_thread::get_id()). Im Erfolgsfall wird HazardPointer zum neuen HazardPointer, der an den Client zurückgegeben wird, der die Member-Funktion getPointer aufruft. Wenn alle Hazard Pointer von HazardPointers verwendet werden, löst der Konstruktor eine std::out_of_range Exception aus. Schließlich setzt der Destruktor von HazardPointerOwner den hazardPointer auf seinen Standardzustand zurück.

Wie geht es weiter?

In C++26 werden wir Hazard Pointer erhalten. Darüber werde ich in meinem nächsten Artikel schreiben.

(rme)