Confusion about the happens-before relation on relaxed atomics

I'm reading the book "Rust Atomic and Locks" and encounters the following code:

use std::sync::atomic::AtomicBool;
use std::sync::atomic::Ordering::Relaxed;

fn main() {
    static STOP: AtomicBool = AtomicBool::new(false);

    // Spawn a thread to do the work.
    let background_thread = thread::spawn(|| {
        while !STOP.load(Relaxed) {
            some_work();
        }
    });

    // Use the main thread to listen for user input.
    for line in std::io::stdin().lines() {
        match line.unwrap().as_str() {
            "help" => println!("commands: help, stop"),
            "stop" => break,
            cmd => println!("unknown command: {cmd:?}"),
        }
    }

    // Inform the background thread it needs to stop.
    STOP.store(true, Relaxed);

    // Wait until the background thread finishes.
    background_thread.join().unwrap();
}

The happens-befores relation rule says that in a single thread, everything just happens as the code order. Therefore I assume user input "stop" before storing true to STOP;

However, since the STOP atomic uses relaxed ordering, I assume that there's no happen-before relation between storing true to STOP and the point where the background thread reads true. Therefore I think there's no way I can ensure that the user input "stop" before the background thread received true in STOP, which means the background thread may break before the user input "stop".

I think I must be wrong but I dont know why. Any help?

If back_thread sees false, main_thread may stored true or may not.

If back_thread sees true, main_thread must finished storing, so stdio reading loop must be broekn.


In main_thread's perspective, if main_thread stored true, back_thread may see new true or old false. if main_stored did not store true, back_thread can only see false.

1 Like

"happens" relation causing reordering only applies to unobservable. (Not sure if there is a list of everything that counts as observable.) The code before and after store() come under the observable category.

Talking about events getting reordered is misleading. Events don't really get reordered per se. What actually happens is that in some cases you may see old values, even though a newer value has been written.

So for example if the main thread does this:

  1. Write A to atomic location 1.
  2. Reads "stop" from stdin.
  3. Write B to atomic location 2.

And background thread does this:

  1. Loop until atomic location 2 contains B.
  2. Read from atomic location 1.

(all atomic ops are relaxed)

Does the background thread see an A from location 1? Not necessarily. But this is not because things got reordered. That's the wrong way to think about it. It's because the background thread saw an old value when reading from location 1.

6 Likes

Thanks. But when talking about the happens-before rule, can we ensure that step 2 in main thread must happens-before step 1 in background thread?

If back_thread sees true , main_thread must finished storing, so stdio reading loop must be broekn.

This is my question! Can you ensure that in background thread's perspective, main_thread must finished storing after user input "stop" with the happens-before rule?

Yes, you can. You know that in main_thread, it cannot call STOP.store(true, Relaxed), until after the input loop is over, since that's the rule for the ordering within a single thread.

Thus, since you cannot get STOP.load(Relaxed) returning true until main_thread has stored it, you know that main_thread has done everything up until the store.

The thing that sometimes catches people out is that non-atomic stores and loads can be buffered and cached indefinitely inside a single thread; thus, while the background thread may be sure that the main thread has exited the loop, without a stronger ordering, it's possible for the background thread to be reading a stale cache, or the main thread to have buffered the store so that the background thread can't read it.

2 Likes

But in the happens-before rule, relaxed ordering ensures no relation between threads, which means there's no happens-before relation between STOP.load(Relaxed) returning true and main_thread has stored it.

happens-before is not about the atomic variable itself, it always hold the happens-before relation ship --- you can never read a variable to be true before someone set it true and it not possible to read out a false after it being set true -- that what the atomic means.

the happens-before is about another variable involved, for example:

initial:
let mut n = 0;

at cpu 1:
n = 1;
atomic.store(true, relax);

at cpu 2:
if atomic.load(relax) {
assert!(n == 1);
}

with relax, the assert may fail
But it is sure the atomic.store(true, relax); happens before atomic.load(relax) == true.

Notice the failing does not necessarily means n = 1 happens after atomic.load(relax), although it is possible in this example, it is also possible the n's new value does not broadcast to cpu2 or the value updating has not been processed by cpu2 yet.

3 Likes

Assuming these steps are referring to my example, no. There is no happens-before relationship established. If there was, then it would be guaranteed that the background thread sees the write of A to location 1. But like I said, it's not guaranteed in this case and the background thread could see the old value.

It sounds like you're assuming that happens-before means more than it does. What bad behavior are you worried about?

You're not going to have a situation where STOP becomes true even though the user is not going to write "stop".

3 Likes

I think I had a misunderstanding of the happens-before definition. Thank you very much!

1 Like

Let me explain step by step.

Why atomic

Atomic means cannot be divided.
i += 1, which read i, add 1, write back. Needs three steps. If two threads add at the same time, they may both read i=1, and both write 2, which is not what we want.
So atomic operations came out.

Why Ordering

Let's see this classical example.

initial state: x = 0, y = 1

THREAD 1        THREAD 2
y = 3;          if x == 1 {
x = 1;              y *= 2;
                }

Easily, we can guess there are two output:

  • thread2 sees x==1, then it sees y==3, so the output is y==6.
  • or, thread 2 doesn’t see x==1, so y*=2 doesn’t run, the output must be y==3.

However, due to cache, CPU disordering, compiler or something advanced else, here’s a annoying situation:

  • thread2 sees x==1, but it also sees y==1, so the output is y==2.

In this architecture,

Thread1 | Thread2
CPU1    | CPU2
Cache1 <-> Cache2

Thread1 did things on CPU1 and accessed Cache1, but Cache1 and Cache2 didn't fully synchronized, so CPU2 probably saw out-dated data.

  • Ordering::Release and Ordering::Acquire then become friends. If operations in different threads on the same atomic type with strong Ordering, the caches will perform synchronization to some extend.
  • Ordering::Relaxed simply influence nothing.

Back to the original question

main_thread: loop reading stdin, break then write true.
back_thread: loop checking until true.

Therefore, back_thread may see the wrong data, why it's wrong? Lack of synchronization. More concrete, it's out-dated.

In this case, if true has been set, false was the out-dated data.

In another example,

x.store(1, Ordering::Relaxed); // line 1
x.store(2, Ordering::Relaxed); // line 2

You may think, as the observer-thread can see x==1 or x==2, so line2 can run before line1. If so, everything will be in a mess. Line1 and line2 will just follow the program order within a single thread, it just seems to be in a mess in observers' eyes due to crazy cache synchronization or compiler optimization and so on.

For more details about other Ordering, you may see my arcticle.

2 Likes

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.