loom does not respect modification order

[ibraheemdev]

trafficstars

#[test]
fn test() {
    use loom::sync::atomic::AtomicU32;
    use loom::sync::atomic::Ordering::*;
    use loom::sync::Mutex;

    loom::model(|| {
        loom::lazy_static! {
            static ref LOCK: AtomicU32 = AtomicU32::new(0);
            static ref DATA: AtomicU32 = AtomicU32::new(0);
            static ref OBSERVED: Mutex<u32> = Mutex::new(21);
        }

        fn t1() {
            DATA.store(42, Relaxed);
            LOCK.store(1, Release);
        }

        fn t2() {
            LOCK.swap(2, AcqRel);
            *OBSERVED.lock().unwrap() = DATA.load(Relaxed);
        }

        fn t3() {
            match [(); 2].map(|()| LOCK.load(Relaxed)) {
                [1, 2] => {
                    while *OBSERVED.lock().unwrap() == 21 {
                        loom::thread::yield_now();
                    }
                    let x = *OBSERVED.lock().unwrap();
                    assert_eq!(x, 42, "x is {:?}", x);
                }
                _ => (),
            }
        }

        let t1 = loom::thread::spawn(t1);
        let t2 = loom::thread::spawn(t2);
        let t3 = loom::thread::spawn(t3);
        t1.join().unwrap();
        t2.join().unwrap();
        t3.join().unwrap();
    });
}

The above test case fails under loom with the following execution:

// loom::rt: spawn thread=Id(1)
// loom::rt: spawn thread=Id(2)
// loom::rt: spawn thread=Id(3)
// loom::rt::execution: ~~~~~~~~ THREAD 2 ~~~~~~~~
// loom::rt::atomic: Atomic::rmw state=Ref<loom::rt::atomic::State>(4) success=AcqRel failure=AcqRel
// loom::rt::atomic: Atomic::load state=Ref<loom::rt::atomic::State>(4) ordering=Acquire
// loom::rt::atomic: Atomic::load state=Ref<loom::rt::atomic::State>(3) ordering=Relaxed
// loom::rt::mutex: Mutex::new state=Ref<loom::rt::mutex::State>(5) seq_cst=true
// loom::rt::mutex: Mutex::is_locked state=Ref<loom::rt::mutex::State>(5) is_locked=false
// loom::rt::execution: ~~~~~~~~ THREAD 1 ~~~~~~~~
// loom::rt::atomic: Atomic::store state=Ref<loom::rt::atomic::State>(3) ordering=Relaxed
// loom::rt::atomic: Atomic::store state=Ref<loom::rt::atomic::State>(4) ordering=Release
// loom::rt::execution: ~~~~~~~~ THREAD 3 ~~~~~~~~
// loom::rt::atomic: Atomic::load state=Ref<loom::rt::atomic::State>(4) ordering=Relaxed
// loom::rt::atomic: Atomic::load state=Ref<loom::rt::atomic::State>(4) ordering=Relaxed
// loom::rt::mutex: Mutex::is_locked state=Ref<loom::rt::mutex::State>(5) is_locked=false
// loom::rt::mutex: Mutex::is_locked state=Ref<loom::rt::mutex::State>(5) is_locked=false

If t3 observes LOCK=1, LOCK=2, then t2's RMW operation must see t1's store of 1 and thus DATA=42. In the failing execution t2 in fact runs first, yet t3 observes t2's store after t1s, which is incoherent with the modification order of LOCK.

[Darksonn]

Here's another trace of the execution: (gist)

t2 SWAP LOCK 0 to 2 (acqrel)
t2 LOAD DATA = 0 (relaxed)
t2 STORE OBSERVED = 0 (mutex)
t1 STORE DATA = 42 (relaxed)
t1 STORE LOCK = 1 (release)
t3 LOAD LOCK = 1 (relaxed)
t3 LOAD LOCK = 2 (relaxed)
t3 LOAD OBSERVED = 0 (mutex)
t3 LOAD OBSERVED = 0 (mutex)

So it seems like two consecutive relaxed loads on the same thread can return the values out of order.

Changing STORE LOCK in thread one to a swap makes the issue go away.

[sbarral]

I simplified somewhat the test to make sure this was not Mutex-related:

loom::lazy_static! {
    static ref LOCK: AtomicU32 = AtomicU32::new(0);
    static ref DATA: AtomicU32 = AtomicU32::new(0);
    static ref OBSERVED: AtomicU32 = AtomicU32::new(21);
}

let t1 = loom::thread::spawn(|| {
    DATA.store(42, Relaxed);
    LOCK.store(1, Release);
});

let t2 = loom::thread::spawn(|| {
    LOCK.swap(2, AcqRel);
    OBSERVED.store(DATA.load(Relaxed), Release);
});

let t3 = loom::thread::spawn(|| {
    let lock1 = LOCK.load(Relaxed);
    let lock2 = LOCK.load(Relaxed);
    let observed = OBSERVED.load(Acquire);

    if lock1 == 1 && lock2 == 2 && observed != 21 {
        assert_eq!(observed, 42);
    }
});

t1.join().unwrap();
t2.join().unwrap();
t3.join().unwrap();

It fails and can be cured in the same way as the original test. As @Darksonn wrote, it looks like this fails for good reasons: some sequential consistency would be required to make sure all 3 threads observe the same modification order.