Korrektes Testen nebenläufiger Datenstrukturen
Eins, zwei, drei, zwei
- Mit
loom, einer Rust-Bibliothek, lassen sich Lock-Free-Datenstrukturen gründlich testen
- Es wird ein einfacher Beispielcode für einen nebenläufigen Zähler gezeigt
- Der Bug im Code besteht darin, dass die Inkrement-Operation nicht atomar ist
use std::sync::atomic::{AtomicU32, Ordering::SeqCst};
#[derive(Default)]
pub struct Counter {
value: AtomicU32,
}
impl Counter {
pub fn increment(&self) {
let value = self.value.load(SeqCst);
self.value.store(value + 1, SeqCst);
}
pub fn get(&self) -> u32 {
self.value.load(SeqCst)
}
}
Ein einfacher Test
- Ein Test, der denselben Zähler in mehreren Threads wiederholt erhöht und das Ergebnis prüft
- Der Test schlägt zwar wie erwartet fehl, ist aber zeitabhängig und daher schwer reproduzierbar
#[test]
fn threaded_test() {
let counter = Counter::default();
let thread_count = 100;
let increment_count = 100;
std::thread::scope(|scope| {
for _ in 0..thread_count {
scope.spawn(|| {
for _ in 0..increment_count {
counter.increment()
}
});
}
});
assert_eq!(counter.get(), thread_count * increment_count);
}
Property-based Testing (PBT)
- Versuch, Property-based Testing anzuwenden, das sich gut zum Testen von Zustandsmaschinen eignet
- Wenn sich Threads manuell Schritt für Schritt ausführen lassen, kann man leicht zwischen
load und store eines anderen Threads hineingrätschen
#[test]
fn state_machine_test() {
arbtest::arbtest(|rng| {
let mut state: i32 = 0;
let step_count: usize = rng.int_in_range(0..=100)?;
for _ in 0..step_count {
match *rng.choose(&["inc", "dec"])? {
"inc" => state += 1,
"dec" => state -= 1,
_ => unreachable!(),
}
}
Ok(())
});
}
Einfache Instrumentierung
- Eine Methode, mit der ein Thread zwischen atomaren Operationen „pausieren“ kann
pub fn increment(&self) {
pause();
let value = self.value.load(SeqCst);
pause();
self.value.store(value + 1, SeqCst);
pause();
}
fn pause() {
// ¯\\_(ツ)_/¯
}
API für verwaltete Threads
- Eine Regel beim API-Design ist, mit einem einzelnen Nutzer zu beginnen, zuerst ein Gefühl für die API zu bekommen und erst dann die eigentliche Implementierung anzugehen
- Schreiben von Property-based Tests mit verwalteten Threads
let counter = Counter::default();
let t1 = managed_thread::spawn(&counter);
let t2 = managed_thread::spawn(&counter);
while !rng.is_empty() {
let coin_flip: bool = rng.arbitrary()?;
if t1.is_paused() {
if coin_flip {
t1.unpause();
}
} else if t2.is_paused() {
if coin_flip {
t2.unpause();
}
}
}
Implementierung verwalteter Threads
- Es wird Kommunikation zwischen dem steuernden Thread und den verwalteten Threads benötigt
- Implementiert mit einem Mutex und einer Condition Variable zum Schutz des Zustands
struct SharedContext {
state: Mutex<State>,
cv: Condvar,
}
#[derive(PartialEq, Eq, Default)]
enum State {
#[default]
Running,
Paused,
}
impl SharedContext {
fn pause(&self) {
let mut guard = self.state.lock().unwrap();
assert_eq!(*guard, State::Running);
*guard = State::Paused;
self.cv.notify_all();
guard = self.cv.wait_while(guard, |state| *state == State::Paused).unwrap();
assert_eq!(*guard, State::Running);
}
}
Gesamten Code integrieren
- Integration von verwalteten Threads und Testcode
#[test]
fn test_counter() {
arbtest::arbtest(|rng| {
eprintln!("begin trace");
let counter = Counter::default();
let mut counter_model: u32 = 0;
std::thread::scope(|scope| {
let t1 = managed_thread::spawn(scope, &counter);
let t2 = managed_thread::spawn(scope, &counter);
let mut threads = [t1, t2];
while !rng.is_empty() {
for (tid, t) in threads.iter_mut().enumerate() {
if rng.arbitrary()? {
if t.is_paused() {
eprintln!("{tid}: unpause");
t.unpause()
} else {
eprintln!("{tid}: increment");
t.submit(|c| c.increment());
counter_model += 1;
}
}
}
}
for t in threads {
t.join();
}
assert_eq!(counter_model, counter.get());
Ok(())
})
});
}
Zusammenfassung von GN⁺
- Der Artikel erklärt, wie man nebenläufige Datenstrukturen testet
- Er untersucht, wie sich mit der Rust-Bibliothek
loom nicht atomare Operationen testen lassen
- Mit verwalteten Threads werden Nebenläufigkeitsprobleme auf reproduzierbare und debuggable Weise getestet
- Der Artikel dürfte für Entwickler nützlich sein, die sich für nebenläufige Programmierung interessieren
- Ein ähnliches Projekt mit vergleichbarer Funktionalität ist
JCStress in Java
1 Kommentare
Hacker-News-Kommentare
Ich entwickle eine Bibliothek namens Temper in Rust, und es ist viel Aufwand nötig, um die komplexeren Teile des Rust-Speichermodells zu handhaben
Ich habe in Rust einen atomaren Snapshot für gemeinsam genutzten Speicher implementiert und halte automatisierte Tests für äußerst wichtig
Ein Nachteil dieses Ansatzes ist, dass man den Code selbst an den Testcode anpassen muss
Lincheck von JetBrains ist eine gute Bibliothek in der Kotlin/Java-Welt
Ich frage mich, ob es eine Bibliothek wie "Loom" für C++ gibt
Dieser Ansatz könnte Grenzen bei Soft-Progress-Garantien haben
Man braucht praktisches Know-how und muss echte Threads erzeugen
Mit ptrace kann man Threads im Single-Step ausführen und so auf Instruktionsebene andere Interleavings erzeugen
Um Loom zu verwenden, muss man bedingte Kompilierung einsetzen, was etwas invasiv ist
Ich würde gern wissen, wie man dasselbe in Python machen kann