Reusing allocation addresses should imply a happens-before relationship

[joboet]

The following code fails under miri:

#![feature(reentrant_lock)]

use std::thread;
use std::sync::ReentrantLock;

fn main() {
    let lock = ReentrantLock::new(());
    let acquire = || drop(lock.lock());

    thread::scope(|s| {
        s.spawn(acquire);
        s.spawn(acquire);
    });
}

Commit: e38a828bb8c1faa95be23d1fa902913d218de848
Command: ./miri run -Zmiri-seed=706 -Zmiri-track-weak-memory-loads -Zmiri-preemption-rate=0 race.rs
Result:

note: tracking was triggered
   --> /Users/Jonas/.rustup/toolchains/miri/lib/rustlib/src/rust/library/std/src/sync/reentrant_lock.rs:187:16
    |
187 |             if self.owner.load(Relaxed) == this_thread {
    |                ^^^^^^^^^^^^^^^^^^^^^^^^ weak memory emulation: outdated value returned from load
    |
    = note: BACKTRACE on thread `unnamed-2`:
    = note: inside `std::sync::ReentrantLock::<()>::lock` at /Users/Jonas/.rustup/toolchains/miri/lib/rustlib/src/rust/library/std/src/sync/reentrant_lock.rs:187:16: 187:40
note: inside closure
   --> race.rs:8:27
    |
8   |     let acquire = || drop(lock.lock());
    |                           ^^^^^^^^^^^

error: Undefined Behavior: Data race detected between (1) non-atomic write on thread `unnamed-1` and (2) non-atomic read on thread `unnamed-2` at alloc1432+0x10. (2) just happened here
   --> /Users/Jonas/.rustup/toolchains/miri/lib/rustlib/src/rust/library/std/src/sync/reentrant_lock.rs:244:34
    |
244 |         *self.lock_count.get() = (*self.lock_count.get()).checked_add(1)?;
    |                                  ^^^^^^^^^^^^^^^^^^^^^^^^ Data race detected between (1) non-atomic write on thread `unnamed-1` and (2) non-atomic read on thread `unnamed-2` at alloc1432+0x10. (2) just happened here
    |
help: and (1) occurred earlier here
   --> race.rs:8:22
    |
8   |     let acquire = || drop(lock.lock());
    |                      ^^^^^^^^^^^^^^^^^
    = help: this indicates a bug in the program: it performed an invalid operation, and caused Undefined Behavior
    = help: see https://doc.rust-lang.org/nightly/reference/behavior-considered-undefined.html for further information
    = note: BACKTRACE (of the first span) on thread `unnamed-2`:
    = note: inside `std::sync::ReentrantLock::<()>::increment_lock_count` at /Users/Jonas/.rustup/toolchains/miri/lib/rustlib/src/rust/library/std/src/sync/reentrant_lock.rs:244:34: 244:58
    = note: inside `std::sync::ReentrantLock::<()>::lock` at /Users/Jonas/.rustup/toolchains/miri/lib/rustlib/src/rust/library/std/src/sync/reentrant_lock.rs:188:17: 188:44
note: inside closure
   --> race.rs:8:27
    |
8   |     let acquire = || drop(lock.lock());
    |                           ^^^^^^^^^^^

note: some details are omitted, run with `MIRIFLAGS=-Zmiri-backtrace=full` for a verbose backtrace

error: aborting due to 1 previous error

Error: command exited with non-zero code `cargo +miri --quiet run --manifest-path /Users/Jonas/src/miri/Cargo.toml -- -Zmiri-seed=706 -Zmiri-track-weak-memory-loads -Zmiri-preemption-rate=0 race.rs --edition=2021`: 1

ReentrantLock uses the address of a TLS variable to check whether the current thread already owns the lock. As -Zmiri-track-weak-memory-loads shows, the second thread reads an outdated owner value and as with this specific seed the TLS allocation happens to be on the same address, it thinks it already owns the lock; thus triggering UB inside miri.

However, I do not believe this to be an issue with ReentrantLock. In any allocator, reallocating the same address requires observing that the address has been deallocated. Thus, there must be a happens-before relationship between deallocation and allocation. miri currently does not form such a relationship, leading to the issue above. With happens-before, the outdated read cannot happen because the second thread will observe that the owner has been reset and released after allocating the TLS variable.

[RalfJung]

Hm, I've never heard that the allocator would be required to establish happens-before relationships when doing address reuse.

The compiler already can't move things that access this memory down below the free or up across the malloc, so it may be sufficient for the allocator to use Relaxed access to check that the address has been freed, and not actually incur happens-before? Not sure.

Would it help to make these owned accesses in the ReentrantLock check be release/acquire?

@Amanieu @m-ou-se I'd be curious what your take on this is.

[joboet]

Would it help to make these owned accesses in the ReentrantLock check be release/acquire?

No, because those could still load an old value.

The compiler already can't move things that access this memory down below the free or up across the malloc, so it may be sufficient for the allocator to use Relaxed access to check that the address has been freed, and not actually incur happens-before? Not sure.

If there is no happens-before, then writes from before the free could be ordered after the malloc and cause data races.

[RalfJung]

As -Zmiri-track-weak-memory-loads shows, the second thread reads an outdated owner value and as with this specific seed the TLS allocation happens to be on the same address, it thinks it already owns the lock; thus triggering UB inside miri.

I am not sure I fully understand what happens. So we're reading an outdated owner which happens to have the right value but is actually a different thread? And the proper, latest value of owner would be 0? So if the owner == this_thread arm had a debug_assert to ensure that the lock count is currently non-zero, that would catch this particular execution (though likely it would not fix the issue)?

[joboet]

I am not sure I fully understand what happens. So we're reading an outdated owner which happens to have the right value but is actually a different thread?

Yes, exactly.

So if the owner == this_thread arm had a debug_assert to ensure that the lock count is currently non-zero, that would catch this particular execution (though likely it would not fix the issue)?

No, because that read would still race with the write of the count in the other thread (or at least miri would think so).

[RalfJung]

Is it possible to reproduce this without involving ReentrantLock? I thought something like this would do it but there doesn't seem to be a race here.

use std::thread;

// Just a type with a rare size to make it more likely that we will
// reuse the right allocation.
type T = [u8; 7];

fn thread() {
    for _ in 0..100 {
        let b = Box::new(T::default());
        drop(b);
        thread::yield_now();
    }
}

fn main() {
    let j1 = thread::spawn(thread);
    let j2 = thread::spawn(thread);
    j1.join().unwrap();
    j2.join().unwrap();
}

[RalfJung]

Ah I guess it's not enough to just reuse the memory, as the data race detector will consider the old and new allocation to have nothing to do with each other. It's about using (abusing?) the address as a signal for synchronization on another shared location.

I am honestly not convinced that your reasoning is sound here, it sounds extremely sketchy to me.

[RalfJung]

Cc @rust-lang/opsem any opinions on this?

I feel like if we're changing Miri to accommodate this we at least need to also document this as a requirement for our allocator traits. I don't know enough about allocators to judge whether there's a a risk of a real-world allocator violating this property.

[RalfJung]

In this case it's a thread-local, that wouldn't even go through a regular allocator right? I have no idea how the memory backing thread-locals is managed, some sort of page table magic as part of thread creation/destruction or so? Where would the happens-before come from there?

[bjorn3]

musl libc either puts TLS on the (mmapped) stack or uses malloc to allocate it.

[bjorn3]

The kernel would have a happens before between the munmap and mmap, right? It will only reuse a mmap region after it is certain all threads have flushed the TLB entries for the old mapping (which requires synchronization) Same with a memory allocator which won't reuse a memory location until after it has synchronized with the free call.

[joboet]

Yes, this is invariant over all correct memory allocators. In terms of hardware, if the free call and its internal writes do not present a barrier, they may get ordered before reads to the allocation, which therefore could read data written after the malloc.

[tmiasko]

Separately, doesn't address reuse mean that ReentrantLock ownership is transferred to a different thread when a thread exits without releasing the lock? That doesn't seem right either.

[joboet]

It's the same thing: as long as there is a happens-before relationship between the deallocation and allocation, that is totally sound.

[tmiasko]

Sure, it might be sound but is it safe? It seems wrong that you can have multiple threads locking the same lock without unlocking it first (EDIT: i.e., it is inconsistent with guarantees documented in ReentrantLock::lock).