Fallback implementation may not provide sequential consistency with Ordering::SeqCst

[taylordotfish]

The fallback implementation ignores the provided Ordering and always locks and unlocks the lock with Acquire and Release operations. However, this may not be sufficient to provide sequential consistency when requested by the user.

For example, this code:

fn main() {
    let a = Atomic::<u128>::new(0);
    let b = Atomic::<u128>::new(0);
    let c = Atomic::<u8>::new(0);
    std::thread::scope(|s| {
        s.spawn(|| { a.store(1, Ordering::SeqCst); });
        s.spawn(|| { b.store(1, Ordering::SeqCst); });
        s.spawn(|| {
            if a.load(Ordering::SeqCst) > b.load(Ordering::SeqCst) {
                c.fetch_add(1, Ordering::Relaxed);
            }
        });
        s.spawn(|| {
            if b.load(Ordering::SeqCst) > a.load(Ordering::SeqCst) {
                c.fetch_add(1, Ordering::Relaxed);
            }
        });
    });
    println!("{}", c.load(Ordering::Relaxed));
}

should never print 2, because there should be a single total modification order of all SeqCst atomic writes that prevents one thread from seeing the write to a before the write to b, while the other sees the write to b before the write to a.

However, if Atomic<u128> uses the fallback implementation, each SeqCst operation will be replaced by an Acquire followed by a Release, as part of the spinlock code. I could be wrong, but I don't believe this is sufficient to prevent the program from printing 2. There is no happens-before relationship between the two stores, and I believe nothing else to enforce a globally consistent view across all threads. This wouldn't happen on x86 but it could potentially occur on certain weakly-ordered architectures like IBM Power.

Although it's unlikely many practical issues could come of this, I think it would be a good idea to use SeqCst orderings for the spinlocks whenever the ordering of the requested atomic operation is SeqCst. In such cases, I think it would be sufficient to use SeqCst only for the unlock operation; the lock operation could remain Acquire.

[Amanieu]

I believe that for the case of your example, acquire/release order is sufficient to guarantee that c is never 2. See https://stackoverflow.com/questions/41847511/is-stdmutex-sequentially-consistent.

However I believe you are correct: when the ordering is SeqCst then we need to insert a SeqCst fence before and after the atomic operation. Would you be willing to author a PR for this?

[taylordotfish]

Sure, I'll work on a PR.