Data race detected by Miri between `Sender::take_waker()` and `Receiver::drop()`

[sandersaares]

Miri detects a data race in oneshot.

error: Undefined Behavior: Data race detected between (1) non-atomic read on thread `unnamed-3` and (2) retag write of type `oneshot::Channel<()>` on thread `unnamed-2` at alloc724351
    -->
C:\Users\sasaares\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\alloc\src\boxed.rs:1260:9


     |

1260 |         Box(unsafe { Unique::new_unchecked(raw) }, alloc)

|         ok^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ (2) just happened here
     |
help: and (1) occurred earlier here

    --> C:\Source\oss\oneshot\src\lib.rs:1225:13
     |
1225 |             ptr::read(self.waker.get()).assume_init()
     |             ^^^^^^^^^^^^^^^^^^^^^^^^^^^
     = help: retags occur on all (re)borrows and as well as when references are copied or moved
     =
help: retags permit optimizations that insert speculative reads or writes
     = helpok: therefore from the perspective of data races, a retag has the same implications as a read or write
     = help: this indicates a bug in the program: it performed an invalid operation, and caused Undefined Behavior

That the race is between:

• The ptr::read() in take_waker() called from Sender::send()
• Receiver::drop() that drops the channel.

Precondition:

• receiver observes UNPARKING state at least once

Because the UNPARKING state is exited via a Relaxed load, Miri considers that the Receiver::drop() that follows is racing with Sender::take_waker() - even though the latter was followed by an AcqRel state update, there was no Acquire that "closed the loop" on the receiver side.

The fix appears to be to add an Acquire fence when exiting the UNPARKING loop:

UNPARKING => loop {
    hint::spin_loop();
    // ORDERING: The load above has already synchronized with the write of the message.
    match channel.state.load(Relaxed) {
        MESSAGE => {
            // ORDERING: the sender has been dropped, so this update only
            // needs to be visible to us
            channel.state.store(DISCONNECTED, Relaxed);

            // synchronize with the take_waker() that resulted in us exiting the loop.
            fence(Acquire);

            // SAFETY: We observed the MESSAGE state
            break Poll::Ready(Ok(unsafe { channel.take_message() }));
        }
        DISCONNECTED => break Poll::Ready(Err(RecvError)),
        UNPARKING => (),
        _ => unreachable!(),
    }
},

Test that reproduces the issue:

#![cfg(feature = "std")]
#![cfg(feature = "async")]

use std::{
    future::Future,
    hint::spin_loop,
    pin::pin,
    task::{self, Poll, Waker},
};

#[test]
fn data_race() {
    // Depending on the random seed used by Miri, this will result in a data race being detected.
    // Use MIRIFLAGS="-Zmiri-many-seeds=0..512" to test with many different seeds.
    let (tx, rx) = oneshot::channel::<()>();

    let rx_thread = std::thread::spawn(move || {
        let mut rx = pin!(rx);

        let mut cx = task::Context::from_waker(Waker::noop());

        while let Poll::Pending = rx.as_mut().poll(&mut cx) {
            spin_loop();
        }
    });

    // It is important that we enter RECEIVING state first.
    // We start this thread later to increase the probability of that.
    let tx_thread = std::thread::spawn(move || {
        tx.send(()).unwrap();
    });

    tx_thread.join().unwrap();
    rx_thread.join().unwrap();
}

Steps to reproduce:

• Set MIRIFLAGS="-Zmiri-many-seeds" to try with 64 different randomness seeds (result depends on Miri random choices). Use MIRIFLAGS="-Zmiri-many-seeds=0..512" to try with even more seeds if the time of day is not favorable for repro.
• cargo +nightly miri test data_race

[faern]

Thanks for reporting this issue! I'm trying to wrap my head around why this happens. Your suggested fence(Acquire) makes your test work indeed. But if you replace tx.send(()).unwrap(); with drop(tx) in your test, then it still fails. So it fixes the synchronization in one specific code path, but not all it seems.

Changing the Sender::drop impl to use channel.state.fetch_xor(0b001, Release) makes that modified test pass, but I have not yet fully understood why exactly.

[faern]

I'm able to write a lot of different tests that make miri report issues like the above for different atomic loads and stores. I have managed to fix all of these by replacing a lot of atomic orderings with AcqRel... But I'm not yet sure if this is actually needed, or if miri is just overly strict/has bugs 🤔

I'll try to write some minimal example and see if I can reason about that easier, and report this to miri/ask them about it.

[faern]

I have a better grasp of this now. But atomics are complicated, and I might still have some errors in my understanding. If there are errors in my explanation below, please correct me, so I can learn and make this library better.

Consider the following code:

while data.state.load(Relaxed) == 0 {}
write_to(data);

I have assumed that in code like this, the code in write_to must execute strictly after this thread has observed state becoming non-zero. Meaning the other thread that has a reference to state must have finished executing its atomic write operation to state. This is not true. The compiler/CPU is allowed to optimize the execution so that parts of write_to is carried out before the while loop. And if those parts ending up before the while loop does (or could hypothetically) write to data, then we suddenly have a race with any other thread that is performing the store (write) operation to data.state.

In our miri error reported above, and the others I found, the code it is upset about is not really strictly writing to data. It just performs an operation on it that is a "retag", which in turn is classified as both read and write under the stacked borrowing model. Both ptr::read and Box::from_raw are such "retag" operations, that although they look like they only read, miri treats them as operations that could lead to memory writes in those objects.

As a result, we must ensure that we enforce strict happens-before relationships in all places where we wait for our channel state to reach a certain value and then perform a write (or "retag") operation.

Here is the most minimal example I could produce with just std that show the same race. Here miri becomes angry, because the Box::from_raw operation is a retag, but it does not have a strict happens-after relationship to the other thread's state.store write.

use std::sync::atomic::{AtomicU8, Ordering};

struct StateHandle {
    state_ptr: *mut AtomicU8,
}
unsafe impl Send for StateHandle {}

#[test]
fn retag_drop() {
    let (handle1, handle2) = {
        let state_ptr: *mut AtomicU8 = Box::into_raw(Box::new(AtomicU8::new(0)));
        (StateHandle { state_ptr }, StateHandle { state_ptr })
    };

    let t1 = std::thread::spawn(move || {
        let handle = handle1;
        let state: &AtomicU8 = unsafe { &*(handle.state_ptr) };

        while state.load(Ordering::Relaxed) == 0 {
            std::thread::yield_now();
        }
        // std::sync::atomic::fence(Ordering::Acquire);

        // The "retag" happens here. So we must have synchronization to ensure this
        // strictly happens after the store in the other thread.
        let state = unsafe { Box::from_raw(handle.state_ptr) };
        // The drop (the actual memory freeing) is not the main problem here. The `Box::from_raw`
        // in what miri detects as a "write" and is the source of the UB.
        drop(state);
    });

    let t2 = std::thread::spawn(move || {
        let handle = handle2;
        let state: &AtomicU8 = unsafe { &*(handle.state_ptr) };
        // This store must have `Release` ordering in order to let the other thread
        // issue an `Acquire` fence before accessing the `state` in a mutable (retag) way.
        state.store(1, Ordering::Relaxed);
    });

    t1.join().unwrap();
    t2.join().unwrap();
}

[faern]

The test code in this PR (data_race) is equivalent to the test tx_send_rx_poll_to_completion added in #71. This, along with a bunch of other races found by miri was fixed in #72