Atomic load makes threads not explore at all

[ZobyTwo]

Loom uses a per-thread state to remember the status of threads at branching points.
When a newly spawned thread immediately does an atomic load, the code in Execution::schedule ends up setting that to Thread::Skip, disabling any exploration, which is clearly wrong.

This reproduces the case:

#[test]
fn thread_skipped() {
    let solutions = std::sync::Arc::new(std::sync::Mutex::new(HashSet::new()));
    let solutions1 = std::sync::Arc::clone(&solutions);

    loom::model(move || {
        let a1 = Arc::new(AtomicBool::new(false));
        let a2: Arc<AtomicBool> = a1.clone();

        let th = thread::spawn(move || {
            // Some irrelevant load, which causes loom to not explore properly.
            let _irrelevant = a1.load(Relaxed);
            a1.store(true, Relaxed);
        });

        let update_done = a2.load(Relaxed); // Could be either true or false

        th.join().unwrap();

        solutions1.lock().unwrap().insert(update_done);
    });

    let solutions = solutions.lock().unwrap();
    
    assert!(solutions.contains(&false));
    assert!(solutions.contains(&true));

    assert_eq!(solutions.len(), 2);
}

Branch number 0 then finds no alternative paths and exploration ends after one iteration.
Remove the let _irrelevant = a1.load(Relaxed); and exploration happens as expected.

The code in Execution is a bit suspect:

        let next = self.path.branch_thread(self.id, {
            self.threads.iter().map(|(i, th)| {
                if initial.is_none() && th.is_runnable() {
                    initial = Some(i);
                }

                if initial == Some(i) {
                    Thread::Active
                } else if th.is_yield() {
                    Thread::Yield
                } else if !th.is_runnable() {
                    Thread::Disabled
                } else {
                    Thread::Skip // <--- here
                }
            })
        });

This sets the thread to Skip even though it is runnable. However, changing this to Pending makes this case work, but breaks some other tests as some schedulings (e.g. thread creations?) count as preemptions, making loom eventually hit the assert in path.rs:

            debug_assert!(
                self.preemption_bound.is_none() || Some(preemptions) <= self.preemption_bound,
                "[loom internal bug] max = {:?}; curr = {}",
                self.preemption_bound,
                preemptions,
            );

I can't follow the code well enough yet to prepare a fix. Any pointers as to what should actually happen would be highly appreciated.

I guess a workaround is to start each spawned thread with some otherwise useless store?

Edit: Tried that, but the same issue occurs in some other circumstances as well.

[ZobyTwo]

After trying to understand the code a bit more, I think the idea of the Skip is that it is set to Pending when adding a backtracking point, but that only happens if there is a dependent access in the path, which there isn't. It didn't produce a dependent access because that extra load immediately switches back to branch zero, which just performed a load, and after that, a store.

After that initial execution, Path::step is supposed to select the next one, but it won't change the scheduling, because there is only one runnable thread, the other one is still Skipped, and it thinks we are done.

I suspect that, due to the way loom is implemented, loads cannot read from future stores (in execution order), so I think dependent accesses cannot be reliably used to decide whether to un-skip a thread. Thus, I think Skip should maybe be removed and some other way should be found to prevent preempting more often than the bound specifies.