Pruebas adecuadas de estructuras de datos concurrentes

Pruebas adecuadas de estructuras de datos concurrentes

Uno, dos, tres, dos

• Se puede probar a fondo una estructura de datos lock-free usando loom, una biblioteca de Rust
• Se proporciona un ejemplo de código simple de un contador concurrente
• El bug del código es que la operación de incremento no es atómica

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)
    }
}

Prueba simple

• Una prueba que incrementa repetidamente el mismo contador desde varios hilos y verifica el resultado
• La prueba falla correctamente, pero como depende del timing es difícil de reproducir

#[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);
}

Pruebas basadas en propiedades (PBT)

• Se intenta aplicar pruebas basadas en propiedades, adecuadas para probar máquinas de estado
• Si se pudiera ejecutar manualmente cada hilo paso a paso, sería fácil intercalarlo entre el load y el store de otro hilo

#[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(())
    });
}

Instrumentación simple

• Un método para permitir que los hilos se “pausen” entre operaciones atómicas

pub fn increment(&self) {
    pause();
    let value = self.value.load(SeqCst);
    pause();
    self.value.store(value + 1, SeqCst);
    pause();
}

fn pause() {
    // ¯\\_(ツ)_/¯
}

API de hilos administrados

• Una regla del diseño de APIs es empezar con un solo usuario, entender cómo se siente la API y luego avanzar a la implementación real
• Escritura de pruebas basadas en propiedades usando hilos administrados

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();
        }
    }
}

Implementación de hilos administrados

• Se necesita comunicación entre el hilo de control y los hilos administrados
• Se implementa usando un mutex y una variable de condición para proteger el estado

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);
    }
}

Integración del código completo

• Integración de los hilos administrados con el código de prueba

#[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(())
        })
    });
}

Resumen de GN⁺

• Este artículo explica cómo probar estructuras de datos concurrentes
• Explora cómo usar la biblioteca loom de Rust para probar operaciones no atómicas
• Usa hilos administrados para probar problemas de concurrencia de una forma reproducible y depurable
• Será útil para desarrolladores interesados en programación concurrente
• Un proyecto con funcionalidades similares es JCStress de Java

[GN⁺]

Opiniones de Hacker News

• Está desarrollando una biblioteca llamada Temper en Rust, y se requiere mucho esfuerzo para manejar las partes complejas del modelo de memoria de Rust

  • Incluye una de las mayores colecciones de casos de prueba del modelo de memoria de C++/Rust
  • Loom es una biblioteca más completa, que permite probar a fondo estructuras de alto nivel como mutexes y colas
  • Se inspiró en una charla sobre pruebas de Foundation DB, y cree que WebAssembly jugará un papel importante en esta área

• Implementó snapshots atómicos de memoria compartida en Rust y considera que las pruebas automatizadas son muy importantes

  • Al principio usó Loom, pero después cambió a Shuttle
  • Shuttle usa un enfoque aleatorizado y ofrece garantías probabilísticas de encontrar errores
  • Shuttle es más rápido y escala bien para escenarios de prueba más complejos
  • La capacidad de reproducir pruebas fallidas es muy importante

• La desventaja de este enfoque es que hay que modificar el propio código para adaptarlo al código de prueba

  • También sería posible ejecutar dos hilos y mezclar aleatoriamente la ejecución de instrucciones usando ptrace con single-step

• Lincheck de JetBrains es una buena biblioteca en el mundo de Kotlin/Java

  • Le gusta que sea declarativa y la forma en que muestra los resultados de linealización

• Se pregunta si existe una biblioteca tipo "Loom" para C++

  • Quiere probar estructuras de datos lock-free

• Este enfoque puede tener limitaciones con las garantías de progreso débil

  • En un bucle cmpxchg, en hardware real y con el scheduler es muy poco probable que se interrumpa
  • Sin embargo, en este enfoque de pruebas, la probabilidad de progreso cambia según la cantidad de tareas y el número de pausas

• Se necesita conocimiento práctico y hay que crear hilos reales

  • Se pregunta si se puede usar un runtime asíncrono

• Se puede usar ptrace para ejecutar hilos en single-step y crear distintos interleavings a nivel de instrucción

  • Se pregunta si existe una alternativa de pruebas de caja negra

• Para usar Loom hay que recurrir a compilación condicional, y eso es algo invasivo

  • Se pregunta si otros lenguajes son mejores al usar su propio scheduler

• Quiere saber cómo hacer lo mismo en Python

  • Se pregunta si se puede crear una clase de hilos que permita este tipo de pruebas