Questions about atomic ordering

help
1

I'm trying to get a better understanding of atomic ordering guarantees, but this issue threw me off a bit.

In it, RalfJung and jeehoonkang are discussing this code (I changed AtomicCell to AtomicBool, hopefully that's not significant):

let x = AtomicBool::new(false);
let y = AtomicBool::new(false);

scope(|s| {
    // Thread A
    s.spawn(|| x.store(true, <ordering>));
    // Thread B
    s.spawn(|| y.store(true, <ordering>));

    // Thread C
    s.spawn(|| {
        while !x.load(<ordering>) {}
        if y.load(<ordering>) { println!("y then x"); }
    });

    // Thread D
    s.spawn(|| {
        while !y.load(<ordering>) {}
        if x.load(<ordering>) { println!("x then y"); }
    });
}).unwrap();

I understand that if <ordering> is replaced with Release for stores and Acquire for loads, then it is not guaranteed that this code will print anything, since thread A/B don't establish an ordering of the stores.

I have a few questions related to this code:

  1. If we instead use SeqCst for all loads and stores, is the code guaranteed to print something?
  2. If AtomicBool is replaced with Mutex<bool>, is it guaranteed to print? This one confused me, since in the linked issue Ralf and jeehoonkang seem to believe the answer is no. However I thought the answer was yes, since a Mutex load translates into lock(Acq); read; unlock(Rel) and I believe the Acq/Rels on every access are enough to guarantee that something prints. I'm mostly basing this intuition on this C++ SO post.
  3. In general, if we have code that uses multiple AtomicBool variables and uses SeqCst for every access to those variables, and then we replace AtomicBool with Mutex<bool>, will the new code and old code have exactly the same semantics? (I'm aware that mixing SeqCst and Acq/Rel complicates things - I'm just focusing on completely SeqCst vs completely Acq/Rel for now)
2

(Just my understanding, can't comment how well Rust conforms.)
This is for AtomicBool, can't comment on AtomicCell.

To guarantee a print you can have either;
while !_.load(Acquire with anything for other orderings.
if _.load(SeqCst with anything for other orderings.
Either ensures the order the conditions are performed don't get juggled.

~~Above alone is not enough. Atomic adds another guarantee; Read-read coherence. https://en.cppreference.com/w/cpp/atomic/memory_order~~

With a bit more reading I see more crazy unintuitive behaviour is allowed. Which just gets me querying more basic acquire/release and simple counters as risky rather than giving better understanding to apply where useful.

3

Yes, it'll at least print one of the string literals.

No, because synchronization happens between threads and both stores need to happen on the same thread for there to be a guarantee to print at least one string literal (with acquire/release).

Please, don't do that. Analyzing relationships between several atomic objects is complex and it's very easy to miss an invariant, that has to be held up. The team behind RustBelt (project to formally verify the Rust standard library) discovered several soundness issues in Arc and other synchronizing data structures, that use atomics, that were caused by wrong analysis or assumptions regarding memory ordering.

4

Don't worry, these questions are purely academic :slight_smile:. I'm just trying to understand the relationship between the guarantees that atomics make and the guarantees that mutexes make (the Rust mutex documentation doesn't seem to say anything about this?). If the answer is "there's no clear relationship and you just have to take it on a case by case basis", that's also fine.

Would you mind taking a look at this SO answer? The logic that they use makes sense to me, so I'm wondering if there's a mistake that I'm not seeing, or maybe it's C++-specific logic that doesn't apply to Rust mutexes. I can also translate the answer to this specific Rust example if that helps.

5

I'll withdraw my quoted answer, for now and revisit this thread, after having gotten some sleep. I just realized, that mutexes make the situation slightly more complex.

6 
fn main() {
    let x = &*Box::leak(Box::new(std::sync::Mutex::new(false)));
    let y = &*Box::leak(Box::new(std::sync::Mutex::new(false)));

    vec![
        std::thread::spawn(move || *x.lock().unwrap() = true),
        std::thread::spawn(move || *y.lock().unwrap() = true),
        std::thread::spawn(move || {
            while !*x.lock().unwrap() {}

            if *y.lock().unwrap() {
                println!("y then x");
            }
        }),
        std::thread::spawn(move || {
            while !*y.lock().unwrap() {}

            if *x.lock().unwrap() {
                println!("x then y");
            }
        }),
    ]
    .into_iter()
    .for_each(|handle| {
        std::thread::JoinHandle::join(handle).unwrap();
    });
}

(Playground)

Possible outputs:

x then y

y then x

x then y
y then x

y then x
x then y

The following, too?

<nothing>

Simplified desugared code:

*x.lock().unwrap() = true;

becomes

// lock
{
    // compare_exchange_weak:
    // Stores a value into the bool if the current value is the same as the `current` value.
    while x.flag«AtomicBool».compare_exchange_weak(
            false«current: bool»,
            true«new: bool»,
            AcqRel«success: Ordering»,
            Acquire«failure: Ordering»
        ).is_err() {
            // Signals the processor that it is inside a busy-wait spin-loop ("spin lock").
            std::sync::atomic::spin_loop_hint();
    }
}

*x.value«bool» = true;

// unlock
{
    // store:
    // Stores a value into the bool.
    x.flag.store(
            false«val: bool»,
            Release«order: Ordering»
        );
}

The standard library Mutex doesn't use a spin loop, of course, but it is the simplest version of a mutex, which helps in understanding the concept.

53350

The interesting operation is compare_exchange(_weak). Read-modify-write atomic operations behave different from separate reads (loads) and writes (stores). In particular:

Atomic read-modify-write operations shall always read the last value (in the modification order) written before the write associated with the read-modify-write operation.

Assuming the boolean is initialized with false, if thread A stores true with relaxed ordering, a load operation on thread B with any ordering, happening afterwards, can fail to see true, because relaxed operation do not synchronize with other operations. A compare-exchange operation, on the other hand, will always see true, in this case. Any subsequent loads on the same thread will also see true, but a load on a thread C can still see false, even if a compare-exchange was executed before on thread B. Different threads see different things except in the case of sequential consistency.

In addition, executing the compare-exchange operation with acquire-release semantics prevents any reordering around it, i.e. it's impossible for the if to be reordered before the while when using mutexes.

In conclusion, it is guaranteed to print something.