Bien tester les structures de données concurrentes
Un, deux, trois, deux
- La bibliothèque Rust
loom permet de tester en profondeur des structures de données lock-free
- Exemple de code d’un compteur concurrent simple
- Le bug du code est que l’opération d’incrémentation n’est pas atomique
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)
}
}
Test simple
- Test consistant à incrémenter de façon répétée le même compteur depuis plusieurs threads puis à vérifier le résultat
- Le test échoue bien, mais sa reproduction est difficile car elle dépend du timing
#[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);
}
Tests basés sur les propriétés (PBT)
- Tentative d’appliquer des tests basés sur les propriétés, adaptés pour tester des machines à états
- Si l’on pouvait exécuter les threads manuellement étape par étape, il serait facile d’intercaler une exécution entre le
load et le store d’un autre thread
#[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(())
});
}
Instrumentation simple
- Méthode permettant à un thread de se « mettre en pause » entre des opérations atomiques
pub fn increment(&self) {
pause();
let value = self.value.load(SeqCst);
pause();
self.value.store(value + 1, SeqCst);
pause();
}
fn pause() {
// ¯\_(ツ)_/¯
}
API de threads gérés
- Une règle de conception d’API consiste à commencer par un usage simple afin de comprendre le ressenti de l’API, puis à passer à l’implémentation réelle
- Écriture de tests basés sur les propriétés à l’aide de threads gérés
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();
}
}
}
Implémentation des threads gérés
- Besoin d’une communication entre le thread de contrôle et les threads gérés
- Implémentation à l’aide d’un mutex protégeant l’état et d’une variable de condition
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);
}
}
Intégration complète du code
- Intégration des threads gérés et du code de test
#[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(())
})
});
}
Le résumé de GN⁺
- Cet article explique comment tester des structures de données concurrentes
- Il explore comment utiliser la bibliothèque Rust
loom pour tester des opérations non atomiques
- Il utilise des threads gérés pour tester des problèmes de concurrence de manière reproductible et débogable
- Cet article sera utile aux développeurs intéressés par la programmation concurrente
- Un projet similaire offrant des fonctionnalités proches est JCStress en Java
1 commentaires
Commentaires Hacker News
Je développe une bibliothèque appelée Temper en Rust, et cela demande beaucoup d’efforts pour gérer les aspects complexes du modèle mémoire de Rust
J’ai implémenté des snapshots atomiques en mémoire partagée en Rust, et j’accorde une grande importance aux tests automatisés
L’inconvénient de cette approche est qu’il faut modifier le code lui-même pour l’adapter au code de test
Lincheck de JetBrains est une bonne bibliothèque dans l’écosystème Kotlin/Java
Je me demande s’il existe une bibliothèque comparable à « Loom » pour C++
Cette approche peut avoir des limites concernant les garanties de progression souple
Il faut des connaissances pratiques, et il est nécessaire de créer de vrais threads
En utilisant ptrace, on peut exécuter les threads en pas à pas pour créer différents entrelacements au niveau des instructions
Pour utiliser Loom, il faut recourir à la compilation conditionnelle, ce qui est assez intrusif
J’aimerais savoir comment faire la même chose en Python