Hazard Pointers und Epochen-Freigabe

Ein sperrfreier Stack blockiert nie, kann aber einen entnommenen Knoten nicht einfach freigeben: Ein anderer Thread kann den Kopf einen Moment zuvor gelesen haben und gleich das next dieses Knotens lesen. Freigegebener Speicher kann wiederverwendet oder entzogen werden, dieses Lesen ist also ein Use-after-free. Es gibt zwei klassische Heilmittel. Hazard Pointers lassen einen Thread den Knoten ankündigen, den er benutzt. Epochen lassen ihn ankündigen, wann er eingetreten ist. In beiden wird ein abgekoppelter Knoten erst freigegeben, wenn ihn niemand mehr halten kann.

Das Modell ist der Stack des ABA-Themas. Ein Thread liest den Kopf, liest den Knoten und tauscht dann den Kopf in einem Compare-and-swap. Das unsichere Pop gibt den Knoten in dem Zug frei, in dem der Tausch gelingt. Ein freigegebener Knoten darf von niemandem berührt werden, und read_node vermerkt einen Use-after-free, sobald ein Thread einen liest. Zwei Threads, die je einmal poppen, ergeben nur 20 Schedules, und der Explorer findet die schlechten sofort: die, in denen ein Thread den Kopf las, der andere diesen Knoten poppte und freigab und der erste ihn danach liest.

def pop_unsafe(shared, tid):    while True:        yield        idx = shared["head"]        if idx == -1:            return None        yield        nxt, value = read_node(shared, idx)        yield        if compare_and_swap(shared, "head", idx, nxt):            shared["popped"] = shared["popped"] + (value,)            free_node(shared, idx)            return valuedef two_pops(shared):    return [pop_unsafe(shared, 0), pop_unsafe(shared, 1)]outcomes = explore_all(two_pops, make_heap([9369, 9305]))hits = sum(n for key, n in outcomes.items() if dict(key)["uaf"])print(sum(outcomes.values()), "schedules,", hits, "of them read a freed node")

20 schedules, 6 of them read a freed node

Ein Hazard Pointer macht aus der Freigabe ein Gespräch. Vor dem Lesen eines Knotens schreibt der Thread seine Nummer in seinen Platz. Das allein genügt nicht, denn der Knoten kann zwischen dem Lesen des Kopfs und dem Schreiben des Platzes gepoppt und freigegeben worden sein, also validiert der Thread: Er liest den Kopf erneut und beginnt von vorn, wenn er sich bewegt hat. Nach einem erfolgreichen Pop gibt der Thread den Knoten nicht frei, sondern legt ihn in seine eigene Retired-Liste und scannt: Er liest einmal den Platz jedes Threads und gibt nur die Retired-Knoten frei, die kein Platz nennt. Die übrigen warten auf einen späteren Scan.

def pop_hazard(shared, tid):    while True:        yield        idx = shared["head"]        if idx == -1:            shared["hp%d" % tid] = -1            return None        yield        shared["hp%d" % tid] = idx        yield        if shared["head"] != idx:            continue        yield        nxt, value = read_node(shared, idx)        yield        if compare_and_swap(shared, "head", idx, nxt):            shared["popped"] = shared["popped"] + (value,)            shared["hp%d" % tid] = -1            shared["retired%d" % tid] = shared["retired%d" % tid] + (idx,)            break    yield    hazards = tuple(shared["hp%d" % t] for t in range(shared["threads"]))    yield    keep = []    for node in shared["retired%d" % tid]:        if node in hazards:            keep.append(node)        else:            free_node(shared, node)    shared["retired%d" % tid] = tuple(keep)    return valuedef two_pops(shared):    return [pop_hazard(shared, 0), pop_hazard(shared, 1)]outcomes = explore_all(two_pops, make_heap([9369, 9305]))hits = sum(n for key, n in outcomes.items() if dict(key)["uaf"])waiting = max(sum(len(dict(key)["retired%d" % t]) for t in (0, 1)) for key in outcomes)print(sum(outcomes.values()), "schedules,", hits, "read a freed node, up to", waiting, "node waiting at the end")

12122 schedules, 0 read a freed node, up to 1 node waiting at the end

Die Epochen-Freigabe kündigt viel weniger an. Es gibt einen globalen Epochen-Zähler. Ein Thread schreibt beim Eintritt in eine Operation die aktuelle Epoche in seinen Platz und beim Verlassen -1 und kündigt nie einzelne Knoten an. Ein in Epoche e retired-ter Knoten kann nur von einem Thread gehalten werden, der in Epoche e oder früher eintrat, er ist also freigebbar, wenn jeder Thread in einer Operation eine Epoche größer als e angekündigt hat. Der Preis: Ein Thread, der lange drinbleibt, hält alle seit seinem Eintritt retired-ten Knoten zurück, während ein Hazard Pointer nur den einen Knoten zurückhält, den er nennt.

def pop_epoch(shared, tid):    yield    shared["ep%d" % tid] = shared["epoch"]    while True:        yield        idx = shared["head"]        if idx == -1:            shared["ep%d" % tid] = -1            return None        yield        nxt, value = read_node(shared, idx)        yield        if compare_and_swap(shared, "head", idx, nxt):            shared["popped"] = shared["popped"] + (value,)            shared["ep%d" % tid] = -1            shared["retired%d" % tid] = shared["retired%d" % tid] + ((idx, shared["epoch"]),)            shared["epoch"] = shared["epoch"] + 1            break    announced = []    for t in range(shared["threads"]):        yield        if shared["ep%d" % t] != -1:            announced.append(shared["ep%d" % t])    yield    keep = []    for node, epoch in shared["retired%d" % tid]:        if announced and epoch >= min(announced):            keep.append((node, epoch))        else:            free_node(shared, node)    shared["retired%d" % tid] = tuple(keep)    return valuedef two_pops(shared):    return [pop_epoch(shared, 0), pop_epoch(shared, 1)]outcomes = explore_all(two_pops, make_heap([9369, 9305]))hits = sum(n for key, n in outcomes.items() if dict(key)["uaf"])waiting = max(sum(len(dict(key)["retired%d" % t]) for t in (0, 1)) for key in outcomes)print(sum(outcomes.values()), "schedules,", hits, "read a freed node, up to", waiting, "node waiting at the end")

9012 schedules, 0 read a freed node, up to 1 node waiting at the end

Sicherheit kostet Schedules, denn jede Ankündigung, Validierung und jeder Scan ist ein weiterer Schritt, in den der andere Thread schlüpfen kann: Aus 20 wurden 12.122 und 9.012. Genau deshalb ist der Explorer hier nützlich. Er muss nicht wissen, warum das Verfahren stimmt, er prüft jeden dieser Schedules.

Das Labor folgt der Lektion: der gemeinsame Zustand mit einem Satz Plätze pro Thread, das unsichere Pop, das Hazard-Pointer-Pop, das Epochen-Pop, die Prüfung der beiden Invarianten (kein Use-after-free, nichts verloren), der Verifizierer, der alle Schedules eines Verfahrens erkundet, und die Studie aller drei Verfahren an SPY-Schlusskursen.

• Funktion · FrageBaut auf
• make_heap(values, threads)Was ist geteilt?Einfache Arithmetik
• pop_unsafe(shared, tid)Poppen und sofort freigebenEinfache Arithmetik
• pop_hazard(shared, tid)Ankündigen, validieren, retiren, scannenEinfache Arithmetik
• pop_epoch(shared, tid)Eintreten, mit Epoche retiren, freigebenEinfache Arithmetik
• violations(final)Welche Invarianten brachen?Einfache Arithmetik
• verify(scheme, values, pops)Ist ein Verfahren unter allen Schedules sicher?explore_allviolations
• study(bars)Welches Verfahren überlebt den SPY-Stack?verify

Nächstes Thema: Das war ein Stack, und ein Spielzeug. Das Abschlussprojekt ein sperrfreier Marktdaten-Fan-out setzt die ganze Fertigkeit ein: SPY-Ticks fließen von einem Producer zu mehreren Consumern durch eine sperrfreie Struktur, und der Explorer beweist ihre Invarianten unter allen Schedules.