Need help understanding atomic ordering

help
1

Hello,

I do have a question regarding atomics. I am reading the book by marabos and I am looking at the following example of Mutex.

pub struct Mutex<T> {
    /// 0: unlocked
    /// 1: locked
    state: AtomicU32,
    value: UnsafeCell<T>,
}

impl<T> Mutex<T> {
    pub const fn new(value: T) -> Self {
        Self {
            state: AtomicU32::new(0), // unlocked state
            value: UnsafeCell::new(value),
        }
    }

    pub fn lock(&self) -> MutexGuard<T> {
        // Set the state to 1: locked.
        while self.state.swap(1, Acquire) == 1 {
            // If it was already locked..
            // .. wait, unless the state is no longer 1.
            wait(&self.state, 1);
        }
        MutexGuard { mutex: self }
    }
}

My issue is with the following Drop impl.

impl<T> Drop for MutexGuard<'_, T> {
    fn drop(&mut self) {
        // Set the state back to 0: unlocked.
        self.mutex.state.store(0, Release);
        // Wake up one of the waiting threads, if any.
        wake_one(&self.mutex.state);
    }
}

I do not understand what prevents the wake_one to be re-ordered before the self.mutex.state.store(0, Release);, since the Release ordering prevents things that happens "before" to be re-ordered "after", but not the opposite.

Then, the thread waiting with wait would view the wake_one, would actually not wake up since the value has not changed yet.

Could somebody help me to understand what I am missing ?

Thank you very much.

2

The compiler can't just reorder whatever it wants. It can only reorder stuff when that doesn't change the behaviour. Here wake_one would see a different value if it was reordered to run before the store.

So even if the Ordering was Relaxed or it wasn't a atomic at all the compiler couldn't reorder this.

1 Like
3

Thank you for your answer !
I think that is where my misunderstanding lies. I don't know the internals of wake_one, but after reading the book and the man page, it felt like the wake_one function only used the address of the pointer to the atomic value to know which threads are concerned by the wake, but not the actual value.

In which case I don't understand why the wake_one would see a different value, since, in my understanding, it does not see a value at all, since it does not read to read from the address.

1 Like
4

Hmm. You are right this would allow the compiler to reorder this call. The (unsatisfying) reason that the compiler doesn't so this (and won't be able to do this in the future) is that the compiler doesn't know that the function won't read it.

Even if wake_one was inlined it would still pass the pointer into the kernel which the compiler can't look into. So it has to assume the value will be read.

Speculation:
This is probably the reason that wake_one takes a pointer instead of just the address as a usize. Then it wouldn't be allowed to read and the compiler could reorder.

5

I assume that the kernel is internally using atomic operations (or similar) to synchronize threads, presumably with a release ordering (or stronger) for wake-related functions and acquire (or stronger) for wait-related functions.

If the kernel can't be assumed to do that, then several of std's condvar methods could theoretically deadlock AFAICT from reading the source code.

It seems that this is indeed explicitly documented on Linux:

The load of the value of the futex word is an atomic memory access
(i.e., using atomic machine instructions of the respective
architecture). This load, the comparison with the expected value,
and starting to sleep are performed atomically and totally ordered
with respect to other futex operations on the same futex word.

from FUTEX_WAIT(2const) - Linux manual page, and

The FUTEX_WAKE_OP operation is equivalent to executing the
following code atomically and totally ordered with respect to
other futex operations on any of the two supplied futex words:

from FUTEX_WAKE_OP(2const) - Linux manual page. I assume that "totally ordered" is equivalent to SeqCst or at least AcqRel. Some of the man pages don't elaborate that far, but it presumably applies to all of them.

1 Like
6

Reasoning about the compiler isn't enough. A maximally pathological CPU could also reorder instructions. Thus it's important for the kernel to use atomic operations with the correct orderings.

Edit: as pointed out below, context switches affect a lot of CPU state, so it'd be crazy to try to reorder operations across a context switch into/from kernel-mode code.

1 Like
7

Ok, so the kernel either loads the value or does a atomic fence otherwise it couldn't give these ordering guarantees.

Yes, although a CPU that reorders instructions over a context switch into the kernel sounds like a security vulnerability waiting to happen :wink:

1 Like
8

lmao, right, for some reason I forgot about the context switch being ever so slightly impactful.