Pengujian yang Tepat untuk Struktur Data Konkuren

Pengujian yang tepat untuk struktur data konkurensi

Satu, dua, tiga, dua

• Dengan menggunakan loom, pustaka Rust, struktur data lock-free dapat diuji secara menyeluruh
• Disediakan contoh kode penghitung konkurensi yang sederhana
• Bug pada kode tersebut adalah operasi penambahan tidak bersifat atomik

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

Pengujian sederhana

• Pengujian yang berulang kali menambah nilai penghitung yang sama dari beberapa thread lalu memeriksa hasilnya
• Pengujian gagal dengan benar, tetapi sulit direproduksi karena bergantung pada 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);
}

Pengujian berbasis properti (PBT)

• Mencoba menerapkan pengujian berbasis properti yang cocok untuk menguji state machine
• Jika thread dapat dijalankan langkah demi langkah secara manual, mudah untuk menyisipkan eksekusi di antara load dan store milik thread lain

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

Instrumentasi sederhana

• Cara agar thread bisa "dijeda" di antara operasi atomik

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

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

API thread terkelola

• Salah satu aturan dalam desain API adalah memulai dari satu pengguna untuk memahami nuansa API, lalu melanjutkan ke implementasi sebenarnya
• Menulis pengujian berbasis properti dengan menggunakan thread terkelola

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

Implementasi thread terkelola

• Diperlukan komunikasi antara thread pengendali dan thread terkelola
• Diimplementasikan dengan mutex dan condition variable untuk melindungi state

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

Mengintegrasikan seluruh kode

• Mengintegrasikan thread terkelola dan kode pengujian

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

Ringkasan GN⁺

• Artikel ini menjelaskan cara menguji struktur data konkurensi
• Mengeksplorasi cara menggunakan pustaka loom di Rust untuk menguji operasi yang tidak atomik
• Menggunakan thread terkelola untuk menguji masalah konkurensi dengan cara yang dapat direproduksi dan mudah di-debug
• Artikel ini akan bermanfaat bagi developer yang tertarik pada pemrograman konkurensi
• Proyek serupa dengan fungsi sejenis adalah JCStress dari Java

[GN⁺]

Komentar Hacker News

• Sedang mengembangkan library bernama Temper dengan Rust, dan membutuhkan banyak upaya untuk menangani bagian-bagian rumit dari model memori Rust

  • Mencakup kumpulan kasus uji terbesar untuk model memori C++/Rust
  • Loom adalah library yang lebih lengkap, yang memungkinkan pengujian menyeluruh terhadap struktur tingkat tinggi seperti mutex dan queue
  • Terinspirasi oleh ceramah pengujian Foundation DB, dan percaya bahwa WebAssembly akan memainkan peran penting di bidang ini

• Telah mengimplementasikan snapshot atomik shared memory di Rust, dan menganggap pengujian otomatis sangat penting

  • Awalnya menggunakan Loom, tetapi kemudian beralih ke Shuttle
  • Shuttle menggunakan pendekatan yang diacak, dan memberikan jaminan probabilistik untuk menemukan bug
  • Shuttle lebih cepat dan dapat diskalakan dengan baik untuk skenario pengujian yang lebih kompleks
  • Fitur untuk mereproduksi pengujian yang gagal sangat penting

• Kekurangan dari pendekatan ini adalah bahwa kode itu sendiri harus dimodifikasi agar sesuai dengan kode pengujian

  • Mungkin juga bisa dilakukan dengan menjalankan dua thread dan mengacak eksekusi instruksi melalui single-step dengan ptrace

• Lincheck dari JetBrains adalah library yang bagus di dunia Kotlin/Java

  • Suka karena bersifat deklaratif dan menampilkan hasil linearisasi

• Penasaran apakah ada library seperti "Loom" untuk C++

  • Ingin menguji struktur data lock-free

• Pendekatan ini mungkin memiliki keterbatasan untuk jaminan soft progress

  • Dalam loop cmpxchg, kemungkinan terhenti pada hardware dan scheduler nyata sangat rendah
  • Namun, dalam pendekatan pengujian ini, probabilitas progress berubah tergantung pada jumlah pekerjaan dan frekuensi jeda

• Dibutuhkan pengetahuan praktis, dan harus membuat thread nyata

  • Penasaran apakah runtime asinkron bisa digunakan

• Dengan menggunakan ptrace, thread dapat dijalankan single-step untuk membuat interleaving lain pada tingkat instruksi

  • Penasaran apakah ada alternatif pengujian black-box

• Untuk menggunakan Loom, perlu memakai conditional compilation, dan ini cukup invasif

  • Penasaran apakah bahasa lain lebih baik karena menggunakan scheduler sendiri

• Ingin tahu cara melakukan hal yang sama di Python

  • Penasaran apakah bisa membuat kelas thread yang memungkinkan pengujian seperti ini