Wie man nebenläufige Datenstrukturen richtig testet

 (matklad.github.io)
2 Punkte von GN⁺ 2024-07-07 | 1 Kommentare | Auf WhatsApp teilen
  • Zeigt anhand eines defekten nebenläufigen Counters in Rust, wie sich Probleme, die normale Thread-Lasttests übersehen, durch reproduzierbare und minimierbare Steuerung der Ausführungsreihenfolge sichtbar machen lassen
  • Ein Test-Wrapper für AtomicU32 fügt pause() ein, und managed threads halten vor und nach atomaren Operationen an und laufen anschließend in der vom Test gewählten Reihenfolge weiter
  • Ein einfacher Test kann 100 Threads jeweils 100 Inkremente ausführen lassen und statt des erwarteten Werts 10000 einen Fehler wie 9598 erzeugen, ist aber timingabhängig und daher schwer zu reproduzieren, zu debuggen und zu verkleinern
  • Property-based Testing auf Basis von arbtest reproduziert mit demselben Seed dasselbe Interleaving und minimiert den Fehlerfall bis auf 0: increment, 1: increment, 0: unpause, 1: unpause
  • Erweitert man dieselbe Struktur mit exhaustigen, lassen sich bis zu 5 Inkremente alle Interleavings aufzählen; nach der Korrektur mit fetch_add bestehen 81133 Interleavings

Nicht-atomarer nebenläufiger Counter

  • Das Beispiel verwendet Rusts AtomicU32, aber increment() führt nach einem load ein store(value + 1) aus, sodass die Inkrement-Operation selbst nicht atomar ist
  • Die Struktur Counter ist einfach
    • value: AtomicU32
    • increment() liest den Wert mit SeqCst, addiert 1 auf den gelesenen Wert und speichert ihn wieder
    • get() liest den aktuellen Wert mit SeqCst
  • Zwei Threads können denselben Wert lesen und anschließend dasselbe Inkrement-Ergebnis speichern, wodurch ein Update verloren geht

Warum normale Thread-Tests nicht ausreichen

  • Die einfachste Prüfung lässt mehrere Threads denselben Counter wiederholt inkrementieren und prüft am Ende den Wert
    • thread_count = 100
    • increment_count = 100
    • Erwarteter Wert ist 10000
  • Ein Beispiellauf schlägt mit left: 9598, right: 10000 fehl
  • Diese Methode hängt stark vom Scheduling-Timing ab
    • Es ist schwierig, denselben Fehler deterministisch zu reproduzieren
    • Sie ist schwer zu debuggen
    • Reduziert man die Anzahl der Threads oder Inkremente, kann der Test mit Glück bestehen, wodurch sich der Fehlerfall nur schwer minimieren lässt

Interleavings mit Property-based Testing behandeln

  • Property-based Testing (PBT) passt gut zu State-Machine-Tests
    • Zufällige Eingaben lassen sich leicht erzeugen
    • Man kann die Eigenschaft formulieren, dass das Ergebnis der nebenläufigen Ausführung dem sequentiellen Ausführungsmodell entsprechen muss
    • Das passt auch zum Bedarf, fehlschlagende Eingaben zu minimieren
  • Die Schwierigkeit besteht darin, echte OS-Threads zu gewünschten Zeitpunkten Schritt für Schritt weiterlaufen zu lassen
  • Die Lösung ist eine Struktur, die in jeder Iteration einen zufälligen Thread auswählt und ihn einen Schritt ausführen lässt
    • Es muss möglich sein, zwischen load und store eines Threads einen anderen Thread einzuschieben
    • Dafür wird eine managed thread-API aufgebaut, die Threads direkt steuert

Test-AtomicU32 und Einfügen von pause

  • In Test-Builds wird statt std::sync::atomic::AtomicU32 ein eigenes managed_thread::AtomicU32 verwendet
    • #[cfg(test)] use managed_thread::AtomicU32
    • #[cfg(not(test))] use std::sync::atomic::AtomicU32
  • Der Wrapper AtomicU32 ruft vor und nach load() und store() jeweils pause() auf
    • load: pause() → tatsächliches load → pause()
    • store: pause() → tatsächliches store → pause()
  • Dank dieser Einfügepunkte kann der Test Threads rund um atomare Operationen anhalten, wieder fortsetzen und so die Ausführungsreihenfolge steuern

Form der managed-thread-API

  • Der Test erzeugt innerhalb von std::thread::scope zwei managed threads
    • Da scoped threads verwendet werden, können stack-lokale Daten ausgeliehen werden
    • Wie bei spawn(scope, &counter) wird eine Counter-Referenz als Zustand übergeben
  • Ein managed thread führt nicht von Anfang an eine bestimmte main-Funktion aus, sondern die Closures, die der Steuer-Thread per submit() sendet
    • t.submit(|c| c.increment())
    • Der Thread führt die Closure auf seinem Zustand T aus
  • Die Testschleife verhält sich für jeden Thread zufällig, solange noch Entropie vorhanden ist
    • Wenn der Thread angehalten ist, unpause()
    • Wenn er nicht angehalten ist, per submit() increment() ausführen
    • Auch das sequentielle Modell counter_model wird um dieselbe Anzahl erhöht
  • Am Ende werden alle Threads mit join() verbunden, und counter_model wird mit dem tatsächlichen counter.get() verglichen

Implementierung von pause und unpause

  • pause() findet den Kontext des aktuellen managed threads über thread_local!, damit die API des zu testenden Counter nicht geändert werden muss
    • Der Kontext wird als Arc<SharedContext> geteilt
    • SharedContext besitzt Mutex<State> und Condvar
  • Der Zustand ist in Ready, Running und Paused unterteilt
    • Ready: wartet auf die nächste Closure
    • Running: der managed thread läuft
    • Paused: am pause()-Punkt angehalten
  • Wenn ein managed thread pause() erreicht, ändert er den Zustand von Running zu Paused und benachrichtigt den Steuer-Thread über die Condition Variable
  • unpause() ändert den Zustand von Paused zu Running, weckt den managed thread und wartet anschließend, bis der Zustand nicht mehr Running ist
    • So wird verhindert, dass Steuer-Thread und managed thread gleichzeitig weiterlaufen
    • Zu jedem Zeitpunkt läuft nur einer von beiden, was die Nichtdeterministik reduziert

Fehler reproduzieren und minimieren

  • Ein arbtest-Lauf findet im defekten Counter einen Fehler
    • Der Beispielfehler hat Modellwert 4, tatsächlichen Wert 3
    • Der Fehler-Seed ist 0x4fd7ddff00000020
  • Gibt man denselben Seed an, erhält man dasselbe Interleaving erneut, wodurch sich der Fehler leicht reproduzieren lässt
  • Mit .minimize() wird der Fehlerfall auf eine kürzere Ausführung reduziert
    • Der finale minimale Seed ist 0x9c2a13a600000001
    • Der minimale Trace besteht aus vier Schritten
      • 0: increment
      • 1: increment
      • 0: unpause
      • 1: unpause
  • In diesem Minimalfall ist der erwartete Wert 2, der tatsächliche Wert aber 1, wodurch der Defekt des load/store-basierten Inkrements sichtbar wird

Erweiterung auf das Aufzählen aller Interleavings

  • Dieselbe Struktur lässt sich von zufälligen Interleavings auf eine aufzählungsbasierte Variante umstellen
  • Mit exhaustigen wird ein Test geschrieben, der bis zu 5 Inkremente alle Interleavings durchsucht
    • Der Test vermeidet Dummy-Iterationen und ist so aufgebaut, dass er Threads immer per unpause fortsetzt oder ein increment einreicht
  • Die defekte Implementierung findet denselben Bug
    • Der Beispielfehler ist left: 2, right: 1
  • Korrigiert man Counter::increment() zu fetch_add(1, SeqCst), besteht der Test
    • Auch dem AtomicU32-Wrapper wird vor und nach fetch_add() ein pause() hinzugefügt
    • Das Ergebnis lautet all 81133 interleavings are fine!
    • Die Laufzeit beträgt real 8.65s, CPU 8.16s, RSS 63.91mb

Erweiterung auf schwache Speichermodelle und Model Checking

  • Die aktuelle Spielzeugimplementierung von AtomicU32 delegiert an echte Atomics
  • Eine Erweiterungsidee besteht darin, für jedes Atomic die Menge der geschriebenen Werte zu pflegen und beim Lesen einen beliebigen Wert zurückzugeben, der mit einem schwachen Speichermodell konsistent ist
  • Auch die Interleaving-Suche lässt sich intelligenter gestalten als rein zufällig
    • Mit einem Model-Checking-Ansatz kann geprüft werden, ob alle sinnvoll verschiedenen Interleavings berücksichtigt wurden
    • Wie im Ansatz von Generate All The Things lassen sich in kleinen Bereichen alle Interleavings aufzählen

Warum Minimierung ohne Shrinking möglich ist

  • Das verwendete arbtest sieht wie eine vertraute PRNG-Schnittstelle aus, verwendet aber einen endlichen PRNG
    • Fordert man weiter Zufallswerte an, gibt er irgendwann Err(OutOfEntropy) zurück
    • Deshalb erscheinen im Testcode ? und while !rng.is_empty()
  • Wenn der Test die Entropie aufgebraucht hat, endet er kurz; reduziert man also die verfügbare Entropie, wird auch die Testausführung kürzer
  • Die interne Implementierung ist konzeptionell nahe an &mut &[u8]
    • Bei jeder Anforderung einer Zufallszahl wird der Byte-Slice kleiner
    • Je kürzer der anfängliche Slice ist, desto einfacherer Test entsteht
  • Dadurch können Fehlerfälle kürzer werden, ohne dass man eine separate Shrinking-Logik selbst implementieren muss
  • Der Beispielquellcode befindet sich unter properly-concurrent

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-07-07
Hacker-News-Kommentare

  • In Rust entsteht mit einem ähnlichen Ansatz eine Bibliothek namens Temper: https://github.com/reitzensteinm/temper/tree/main
    Allerdings muss man deutlich weiter gehen, um die merkwürdigen Implikationen des gesamten Rust-Speichermodells zu modellieren; dafür braucht es eine Art Buchführung, die nachverfolgt, welche Schreibvorgänge jeder Thread wahrgenommen hat. Je nach atomarer Speicherordnung, Read-/Write-Fences usw. können Garantien entstehen, etwa dass man, wenn man Schreibvorgang X wahrnimmt, zwingend auch Schreibvorgang Y wahrnehmen muss.
    Ich denke, dass dies eine der umfangreichsten Sammlungen von Testfällen für das C++-/Rust-Speichermodell ist; ich habe fast alles zusammengetragen, was sich in Büchern, dem C++-Standard, auf Stack Overflow, in Blogs usw. finden lässt. Die Datei zu Mara Bos’ Rust Atomics and Locks ist zum Beispiel hier: https://github.com/reitzensteinm/temper/blob/main/memlog/tes...
    Das im Artikel erwähnte Loom ist eine ähnliche, aber deutlich ausgereiftere Bibliothek, mit der sich höherstufige Komponenten wie Mutexes oder Queues gründlich testen lassen: https://github.com/tokio-rs/loom Allerdings modelliert sie das Speichermodell selbst nicht so engmaschig wie Temper; ich hatte darüber nachgedacht, die Testfälle nach Loom zu portieren.
    Inspiriert wurde das Ganze von Will Wilsons Vortrag über Tests bei FoundationDB; er baut jetzt bei Antithesis eine hypervisorbasierte Lösung, die diese Art von Tests auf beliebige Docker-Container anwendet: https://www.youtube.com/watch?v=4fFDFbi3toc, https://antithesis.com/
    Ich bin fest davon überzeugt, dass dieser Bereich in den nächsten zehn Jahren deutlich wachsen wird. WebAssembly liegt an einem idealen Punkt: vollständig genug, um beliebige Software dafür zu kompilieren, aber einfach genug, damit der Bau von etwas wie Antithesis nicht zu einem Fünfjahresprojekt für ein Eliteteam wird, das bereits eine Datenbank auf den Markt gebracht hat.

  • Ich habe in Rust atomare Snapshots für Shared Memory implementiert und automatisierte Tests so ernsthaft wie möglich behandelt: https://github.com/kaymanb/todc/tree/main/todc-mem
    Anfangs habe ich das im Artikel erwähnte Loom verwendet, später aber zu shuttle gewechselt: https://github.com/tokio-rs/loom, https://github.com/awslabs/shuttle
    shuttle verwendet im Gegensatz zu Loom keine vollständige Erschöpfungssuche, sondern einen randomisierten Ansatz; der Scheduler liefert aber dennoch probabilistische Garantien für das Finden von Bugs. In der Praxis war shuttle schneller und skalierte auch auf komplexere Testszenarien.
    Ähnlich wie beim Ansatz im Artikel lässt sich der Zufalls-Seed speichern, wenn ein bestimmter Schedule einen Testfehler auslöst. Die Fähigkeit, fehlgeschlagene Tests schnell zu reproduzieren, ist sehr wichtig und ermöglicht es, explizite Testfälle für zuvor gefundene und behobene Bugs zu schreiben: https://github.com/kaymanb/todc/blob/0e2874a70ec8beed8fae773...

  • Für Kotlin/Java ist JetBrains’ Lincheck eine gute Bibliothek für solche Aufgaben: https://github.com/JetBrains/lincheck
    Besonders gefällt mir, dass sie deklarativ ist und wie sie Ergebnisse zur Linearisierbarkeit ausgibt.

  • Ich frage mich, ob es auch für C++ eine Bibliothek wie Loom gibt. Ich habe einige lock-free Datenstrukturen, die ich testen möchte.

  • Wenn ich es richtig verstanden habe, hat dieser Ansatz im Hinblick auf schwache Fortschrittsgarantien Grenzen.
    Die Berechnung im Text ist zwar nicht ganz trivial, aber man kann sich eine cmpxchg-Schleife vorstellen, bei der es auf realer Hardware und mit einem realen Scheduler extrem unwahrscheinlich ist, dass sie auf einer bestimmten CPU unterbrochen wird. Wenn die Zahl der CPUs n beträgt, liegt die Fortschrittswahrscheinlichkeit im Worst Case bei 1/n; bei dieser Testmethode wird sie jedoch zu 1/t^p. Dabei ist t die Zahl der Tasks, die viel größer sein kann als die Zahl der CPUs, und p ist die Zahl der Pausen innerhalb dieses Schleifenrumpfs, die leicht 3 oder mehr erreichen kann. Das reicht aus, um einen Algorithmus, der in der Praxis funktioniert, als kaputt erscheinen zu lassen.
    Umgekehrt scheint diese Methode auch dann kein nützliches Werkzeug zu bieten, wenn man schwachen Fortschritt als Bug erfassen möchte und deshalb starken Fortschritt verlangt.
    Für viele Nebenläufigkeitsprobleme ist sie aber eindeutig nützlich.

    • 1/t^p scheint mir nicht zu stimmen; ich würde eher einfach 1/t ansetzen. Nach Ablauf von t Zeit muss schließlich irgendein Task Fortschritt gemacht haben, und wenn es t Tasks gibt, beträgt die Wahrscheinlichkeit, dass es der Task war, den ich ausgeführt habe, 1/t.
      Die zentrale Verwechslung scheint darin zu liegen, dass eine Unterbrechung nicht zwangsläufig bedeutet, bei CAS zu verlieren.

  • Zu der Stelle „Ehrlich gesagt steckt hier ein wenig Vorwissen drin. Solange man nicht mit Inline-Assembly extrem verfluchte Dinge tut, scheint es nicht möglich zu sein, die Erzeugung echter Threads zu vermeiden. Wenn etwas die Funktion pause() aufruft und wir es bis zu einer späteren Anweisung angehalten lassen wollen, muss das in einem Thread passieren, der einen separaten Stack vom Stack des Tests verwaltet“ frage ich mich, ob man nicht irgendeine Art von asynchroner Runtime verwenden könnte.
    Es sieht so aus, als würde durch Instrumentierung atomarer Operationen kooperatives Multitasking erreicht. Vielleicht brauche ich mehr Kaffee, aber ohne Threads wirkt es einfacher.

    • Async wäre bequem, aber eine weitere Anforderung ist, dass man die von außen beobachtbare API der zu testenden Software nicht ändern möchte. Async ist „ansteckend“, daher braucht eine synchrone API auch eine synchrone Implementierung.

  • Ein Nachteil dieses Ansatzes ist, dass der zu testende Code selbst für den Testcode angepasst werden muss.
    Man könnte vermutlich dasselbe erreichen, indem man zwei Threads startet und sie mit ptrace im Single-Step-Modus ausführt, während man die Ausführung von Instruktionen „zufällig“ ineinander verschachtelt. Also ähnlich wie der Chaos-Modus von rr.
    Allerdings sind manche Instruktionen möglicherweise nicht atomar; daher bräuchte man wohl, sofern es ohne Emulation überhaupt möglich ist, eine Möglichkeit, im Single-Step-Modus auf Ebene „atomarer Mikrocode“-Einheiten auszuführen.

    • Klingt wie der Hypervisor von Antithesis.

  • Um Loom zu verwenden, scheint bedingte Kompilierung nötig zu sein; beim Testen einer einzelnen Bibliothek ist das in Ordnung, aber es ist ziemlich invasiv.
    #[cfg(loom)]
    pub(crate) use loom::sync::atomic::AtomicUsize;
    #[cfg(not(loom))]
    pub(crate) use std::sync::atomic::AtomicUsize;
    Ich frage mich, ob es Sprachen gibt, mit denen sich ein eigener Scheduler besser nutzen lässt.

  • Wenn man es wirklich gründlich machen wollte, könnte man den Test mit ptrace ausführen und die Threads per Single-Step voranschreiten lassen, um auf Instruktionsebene unterschiedliche Interleavings zu erzeugen. Ich frage mich, ob jemand so etwas tatsächlich schon gesehen hat.
    Wenn man den Code wie hier nicht instrumentieren kann: Gibt es Alternativen für Black-Box-Tests?

    • Für Tests asynchroner Signal-Handler habe ich so etwas schon verwendet, aber dort ist die Zahl der Kombinationen deutlich günstiger. Wenn der Hauptthread n Instruktionen ausführt, braucht man nur n Läufe, bei denen vor dem Einschieben des Signals 0 bis n Instruktionen ausgeführt werden; danach läuft der Signal-Handler bis zum Ende und anschließend auch der Hauptthread bis zum Ende. Die Gesamtzeit ist O(n^2).
      Wenn es aber t Threads gibt, die jeweils n Instruktionen ausführen, und sie einander an jeder Grenze unterbrechen können, wird der Ansatz bei realistischen Werten für n unzugänglich. Man müsste ihn wohl reduzieren, indem man nur Operationen auswählt und simuliert, die interessantes Verhalten zeigen.

  • Sieht ziemlich cool aus, ich sollte es einmal ausprobieren. Allerdings wird es nicht alle Arten von Fehlern finden. Entsteht nicht bei jedem pause()-Aufruf eine Synchronisierung zwischen den Threads, sodass manche Data-Race-Probleme verdeckt werden? In Rust ist das vielleicht kein Problem.