Skip to main content

shrink/
shrink.rs

1//! Searching across schedules, then shrinking the failing one.
2//!
3//! Two kernels, because they shrink to very different answers.
4//!
5//! The first is an ordinary missing-barrier race. Riri finds it structurally,
6//! from the happens-before relation rather than from catching the accesses in
7//! a bad order, so it does not need a peculiar interleaving at all. Shrinking
8//! says so: the schedule collapses to nothing, meaning threads running in
9//! plain order already hit it.
10//!
11//! The second only goes wrong when one thread is late. Shrinking has to keep
12//! the decisions that hold it back, and what comes out is a short list of
13//! thread indices that is the whole reproducer.
14//!
15//! cargo run --example shrink
16
17use riri::{replay, Explore, GlobalBuf, LaunchConfig, Ordering, ThreadCtx};
18
19fn main() {
20    structural();
21    println!();
22    order_dependent();
23}
24
25/// A missing barrier. Any schedule finds it.
26fn structural() {
27    const THREADS: u32 = 64;
28    let config = LaunchConfig::new(1, THREADS);
29
30    let found = Explore::new(&config).seeds(64).run_with(|| {
31        let out = GlobalBuf::new("out", vec![0u32; THREADS as usize]);
32        move |t: &ThreadCtx<'_>| {
33            let tile = t.shared::<u32>("tile", THREADS as usize);
34            let i = t.thread_linear();
35            tile.write(t, i, i as u32);
36            // BUG: no t.sync_threads() before reading a neighbour's slot.
37            out.write(t, i, tile.read(t, (i + 1) % THREADS as usize));
38        }
39    });
40
41    println!("== missing barrier");
42    print!("{found}");
43
44    if let Some(f) = &found.failure {
45        if let Some(s) = f.shrink.schedule() {
46            println!(
47                "   {} decisions shrunk to {}: {:?}",
48                f.decisions,
49                s.len(),
50                s.plan()
51            );
52            if s.is_empty() {
53                println!("   an empty schedule means threads in order already hit it");
54            }
55        }
56    }
57}
58
59/// A race that only happens when thread 0 is slow to publish its flag. The
60/// atomics are how the flag is read without racing on the flag itself, so the
61/// only finding is the one worth looking at.
62fn order_dependent() {
63    const THREADS: u32 = 4;
64    let config = LaunchConfig::new(1, THREADS);
65
66    let build = || {
67        let flag = GlobalBuf::new("flag", vec![0u32; 1]);
68        let out = GlobalBuf::new("out", vec![0u32; 1]);
69        move |t: &ThreadCtx<'_>| {
70            let i = t.thread_linear();
71            if i == 0 {
72                flag.atomic_add(t, 0, 1, Ordering::Relaxed);
73            } else if flag.atomic_add(t, 0, 0, Ordering::Relaxed) == 0 {
74                // Racy, but only for the threads that ran before thread 0.
75                out.write(t, 0, i as u32);
76            }
77        }
78    };
79
80    let found = Explore::new(&config).seeds(64).run_with(build);
81
82    println!("== flag published too late");
83    print!("{found}");
84
85    let Some(failure) = &found.failure else {
86        println!("   no schedule reached the racy branch");
87        return;
88    };
89    let Some(schedule) = failure.shrink.schedule() else {
90        return;
91    };
92
93    println!(
94        "   {} decisions shrunk to {}: {:?}",
95        failure.decisions,
96        schedule.len(),
97        schedule.plan()
98    );
99
100    // That schedule is the entire reproducer. No seed involved.
101    let report = replay(&config, schedule, build());
102    println!("   replaying it alone:");
103    print!("   {report}");
104}