Trying to clarify futex wait/wake behavior.

[Imberflur]

The content that the question is about

https://marabos.nl/atomics/os-primitives.html#futex

fn main() {
    let a = AtomicU32::new(0);

    thread::scope(|s| {
        s.spawn(|| {
            thread::sleep(Duration::from_secs(3));
            a.store(1, Relaxed);
            wake_one(&a);
        });

        println!("Waiting...");
        while a.load(Relaxed) == 0 {
            wait(&a, 0);
        }
        println!("Done!");
    });
}

The question

(This is somewhat similar to the question in https://github.com/m-ou-se/rust-atomics-and-locks/issues/10)

I'm trying to understand what guarantees that the wait will always see the relaxed store of 1 if wake_one has already been called.

The chapter notes:

The wait operation behaves atomically with respect to the wake operation, meaning that no wake signal can get lost between the check of the expected value and the moment it actually goes to sleep.

If we make sure that the value of the atomic variable is changed right before a wake operation, we can be sure that a thread that’s about to start waiting will not go to sleep, such that potentially missing the futex wake operation no longer matters.

However, I'm having trouble connecting the atomic-ness of the wait operation to the implication that it will observe the store that occurs right before the wake.

The linux futex docs note:

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.

Does the "totally ordered" play a role in this somehow? From the memory ordering chapter, I do know that a particular atomic variable will have a total modification order, but for me it isn't clear how this is connected to the order of futex operations (which aren't writes to that atomic).

I guess the next paragraph in the futex docs pretty much guarantees that the changed value will be observed, but it doesn't really provide any additional explanation:

The purpose of the comparison with the expected value is to prevent lost wake-ups. If another thread changed the value of the futex word after the calling thread decided to block based on the prior value, and if the other thread executed a FUTEX_WAKE operation (or similar wake-up) after the value change and before this FUTEX_WAIT operation, then the calling thread will observe the value change and will not start to sleep.

[m-ou-se]

Quoting from the futex man page:

When executing a futex operation that requests to block a thread, the kernel will block only if the futex word has the value that the calling thread supplied (as one of the arguments of the futex() call) as the expected value of the futex word. The loading of the futex word's value, the comparison of that value with the expected value, and the actual blocking will happen atomically and will be totally ordered with respect to concurrent operations performed by other threads on the same futex word. Thus, the futex word is used to connect the synchronization in user space with the implementation of blocking by the kernel. Analogously to an atomic compare-and-exchange operation that potentially changes shared memory, blocking via a futex is an atomic compare-and-block operation.

(Emphasis mine.)

It's indeed the 'totally ordered' note here that is important.

I do know that a particular atomic variable will have a total modification order, but for me it isn't clear how this is connected to the order of futex operations (which aren't writes to that atomic).

The easiest way to think about it, is basically that the futex wait and wake operations take part in the 'total modification order'.

What makes it tricky to specify precisely, is that the Linux kernel uses its own memory model with its own definitions. The Linux kernel was doing advanced memory ordering related things far before the memory model that is now used by (modern) C, C++ and Rust even existed. That's why it can be tricky to connect the 'happens before' and 'total modification order' style of rules to the kind of wording and guarantees from the Linux kernel.

Regardless, the one main thing that the kernel guarantees about the ordering of futex operations, is that the standard pattern of

• a waker modifying a value and then using FUTEX_WAKE, and
• a waiter checking a value and then using FUTEX_WAIT,

should always work fine. That is, either the waiter will see the updated value, or the waiter will wait and will be awoken by the waker. See this comment in the Linux source code: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/kernel/futex/waitwake.c?h=v6.3-rc5#n12

[Imberflur]

totally ordered with respect to concurrent operations performed by other threads on the same futex word.

Ah, that is helpful (as well as the rest of this answer)! The section I was looking at only mentioned futex operations. Maybe I should have read the whole page :sweat_smile:.

Thank you for the additional explanation and context.