Likely erroneous dangling reference error in `scope-lock` library

[zetanumbers]

I could not easily shrink faulty code, so I am gonna explain how this library works. scope-lock uses parking_lot::RwLock to facilitate safe lifetime extension of closures and futures under a similar to std::thread::scope mechanism. That is we take a read lock for each closure/future with extended lifetime and at the return from the look_scope's scope we take a write lock, blocking until every object with extended lifetime is dropped. However in the example utilizing threads named boxed.rs MIRI assumes basically that the read guards on other threads are unlocked after lock's deallocation. This doesn't seem reasonable to me and happens only if Box was used, so I assume simulation of acquire-release atomic order for some reason no longer respects allocation information.

After a git bisection I have managed to reduce the scope of the issue to 26d3a02 suspect commit.
UPDATE: This error reproduces even on the old versions with -Zmiri-many-seeds enabled.

Steps to reproduce:

git clone https://github.com/zetanumbers/scope-lock.git
cd scope-lock
cargo miri run --example boxed

Error log

hello from the first scoped thread
[examples/boxed.rs:12:17] &a = [
    1hello from the main thread
,
    2,
    3hello from the second scoped thread
,
]
error: Undefined Behavior: constructing invalid value at .<captured-var(0)>: encountered a dangling reference (use-after-free)
   --> /home/zetanumbers/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/parking_lot_core-0.9.10/src/parking_lot.rs:791:5
    |
791 |     callback(result);
    |     ^^^^^^^^ constructing invalid value at .<captured-var(0)>: encountered a dangling reference (use-after-free)
    |
    = 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 on thread `unnamed-1`:
    = note: inside `parking_lot_core::parking_lot::unpark_one::<{closure@parking_lot::raw_rwlock::RawRwLock::unlock_shared_slow::{closure#0}}>` at /home/zetanumbers/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/parking_lot_core-0.9.10/src/parking_lot.rs:791:5: 791:13
    = note: inside `parking_lot::raw_rwlock::RawRwLock::unlock_shared_slow` at /home/zetanumbers/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/parking_lot-0.12.3/src/raw_rwlock.rs:742:13: 742:57
    = note: inside `<parking_lot::raw_rwlock::RawRwLock as lock_api::rwlock::RawRwLock>::unlock_shared` at /home/zetanumbers/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/parking_lot-0.12.3/src/raw_rwlock.rs:137:13: 137:38
    = note: inside `<lock_api::rwlock::RwLockReadGuard<'_, parking_lot::raw_rwlock::RawRwLock, ()> as std::ops::Drop>::drop` at /home/zetanumbers/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/lock_api-0.4.12/src/rwlock.rs:1375:13: 1375:44
    = note: inside `std::ptr::drop_in_place::<lock_api::rwlock::RwLockReadGuard<'_, parking_lot::raw_rwlock::RawRwLock, ()>> - shim(Some(lock_api::rwlock::RwLockReadGuard<'_, parking_lot::raw_rwlock::RawRwLock, ()>))` at /home/zetanumbers/.rustup/toolchains/miri/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:524:1: 524:56
    = note: inside `std::ptr::drop_in_place::<scope_lock::extended::AssociateReference<scope_lock::extended::UnsafeAssertSync<scope_lock::extended::UnsafeAssertSend<{closure@scope_lock::extend_fn_unchecked<'_, std::boxed::Box<{closure@examples/boxed.rs:9:36: 9:40}>, (), ()>::{closure#0}}>>>> - shim(Some(scope_lock::extended::AssociateReference<scope_lock::extended::UnsafeAssertSync<scope_lock::extended::UnsafeAssertSend<{closure@scope_lock::extend_fn_unchecked<'_, std::boxed::Box<{closure@examples/boxed.rs:9:36: 9:40}>, (), ()>::{closure#0}}>>>))` at /home/zetanumbers/.rustup/toolchains/miri/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:524:1: 524:56
    = note: inside `std::ptr::drop_in_place::<{closure@scope_lock::extended::func::<impl scope_lock::Extender<'_, '_>>::fn_<'_, std::boxed::Box<{closure@examples/boxed.rs:9:36: 9:40}>, (), ()>::{closure#0}}> - shim(Some({closure@scope_lock::extended::func::<impl scope_lock::Extender<'_, '_>>::fn_<'_, std::boxed::Box<{closure@examples/boxed.rs:9:36: 9:40}>, (), ()>::{closure#0}}))` at /home/zetanumbers/.rustup/toolchains/miri/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:524:1: 524:56
    = note: inside `std::ptr::drop_in_place::<{closure@examples/boxed.rs:14:13: 14:20}> - shim(Some({closure@examples/boxed.rs:14:13: 14:20}))` at /home/zetanumbers/.rustup/toolchains/miri/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:524:1: 524:56
note: inside closure
   --> examples/boxed.rs:14:25
    |
14  |             move || f(())
    |                         ^

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

error: aborting due to 1 previous error

Example's code

use std::thread;

fn main() {
    let mut a = vec![1, 2, 3];
    let mut x = 0;

    scope_lock::lock_scope(|e| {
        thread::spawn({
            let f = e.fn_(Box::new(|()| {
                println!("hello from the first scoped thread");
                // We can borrow `a` here.
                dbg!(&a);
            }));
            move || f(())
        });
        thread::spawn({
            let mut f = e.fn_mut(Box::new(|()| {
                println!("hello from the second scoped thread");
                // We can even mutably borrow `x` here,
                // because no other threads are using it.
                x += a[0] + a[2];
            }));
            move || f(())
        });
        println!("hello from the main thread");
    });

    // After the scope, we can modify and access our variables again:
    a.push(4);
    assert_eq!(x, a.len());
}

[zetanumbers]

Flag -Zmiri-fixed-schedule makes the issue go away.

[saethlin]

From everything that you've described, I suspect that this is not a regression but just UB that was not detected before because the way that threads used to be scheduled just happened to never hit the UB case.

Have you run the failing code on old Miri using many-seeds? https://github.com/rust-lang/miri?tab=readme-ov-file#testing-multiple-different-executions

[RalfJung]

In particular, that commit landed some advanced scheduler randomization, where we will now explore non-round-robin schedules that were never explored before. So if your code only has UB for non-round-robin schedules, then older versions of Miri would have missed that bug.

I assume simulation of acquire-release atomic order for some reason no longer respects allocation information.

Nothing about that logic changed in the regression commit, so this seems unlikely.

[zetanumbers]

Have you run the failing code on old Miri using many-seeds? https://github.com/rust-lang/miri?tab=readme-ov-file#testing-multiple-different-executions

I've tried it and this error reproduces even on the old versions. Alas 26d3a02 is not the issue here.

After revisiting the parking_lot::RwLock implementation I've found I've been assuming release ordering on read unlock all along. But use of relaxed ordering does seem to be a bug (Amanieu/parking_lot#463), so if it is then it can be added to the list of bug discovered with MIRI.
UPDATE: I was wrong and it's not a bug, release ordering is used there.

However this error report potential scenario with relaxed orderings could still be considered to be sort of a MIRI bug. To be a dangling reference to this memory region it must be first deallocated. But why its deallocation wouldn't be synchronized with a relaxed atomic operation? Do we consider internal state of an allocator when determining it? Well, this kind of memory management simply serves a purpose to restrict overlap of operations on memory associated with unrelated structures in case of memory region's reuse. But the order of operations on an atomic variable is guaranteed to be consistent (https://en.cppreference.com/w/cpp/atomic/memory_order#Relaxed_ordering), thus deallocation if sequenced-after its last atomic operation, then it also should be consistent with this order and no acquire nor release order is required.

[zetanumbers]

I'm not sure how should I rename this issue to be short and concise. And I wonder if there is a good fix for it. Anyway this issue should stay open in case it's relevant to someone IMO.

Issue is yet to be solved.

[zetanumbers]

After reexamining parking_lot code I've come to the conclusion that it assumes user would not deallocate the RawRwLock based on its state (being locked either this or that way), thus doing a bit of a cleanup after actually unlocking via atomic op.

I will rewrite scope_lock and then will report on it.

[RalfJung]

could still be considered to be sort of a MIRI bug. To be a dangling reference to this memory region it must be first deallocated. But why its deallocation wouldn't be synchronized with a relaxed atomic operation? Do we consider internal state of an allocator when determining it? Well, this kind of memory management simply serves a purpose to restrict overlap of operations on memory associated with unrelated structures in case of memory region's reuse. But the order of operations on an atomic variable is guaranteed to be consistent (https://en.cppreference.com/w/cpp/atomic/memory_order#Relaxed_ordering), thus deallocation if sequenced-after its last atomic operation, then it also should be consistent with this order and no acquire nor release order is required.

I don't understand what you mean here. The allocator acts entirely on thread-local state, so it doesn't by itself synchronize anything. Deallocation acts like a non-atomic write in the memory model; if there are concurrent reads or writes that are not happens-before ordered, that is UB.

Can you express this situation in the form of a short program that Miri complains about, but that you think should be permitted?

[zetanumbers]

After reexamining parking_lot code I've come to the conclusion that it assumes user would not deallocate the RawRwLock based on its state (being locked either this or that way), thus doing a bit of a cleanup after actually unlocking via atomic op.

I will rewrite scope_lock and then will report on it.

I have fixed my original issue with in commit, so now MIRI tests pass there as intended:
zetanumbers/scope-lock@edbae7a

I don't understand what you mean here. The allocator acts entirely on thread-local state, so it doesn't by itself synchronize anything. Deallocation acts like a non-atomic write in the memory model; if there are concurrent reads or writes that are not happens-before ordered, that is UB.

Can you express this situation in the form of a short program that Miri complains about, but that you think should be permitted?

This is not the actual problem, but it once was my hypothesis. Alas this failing example could be considered safe
(see playground):

use std::{
    alloc::{Layout, alloc, dealloc},
    sync::atomic::{self, AtomicUsize},
};

const THREADS: usize = 2;
const DECREMENTS: usize = 10;
const ATOMIC_LAYOUT: Layout = Layout::new::<AtomicUsize>();

fn main() {
    unsafe {
        let x = AssertSendSafe(alloc(ATOMIC_LAYOUT).cast::<AtomicUsize>());
        x.0.write(AtomicUsize::new(THREADS * DECREMENTS));
        std::thread::scope(|s| {
            for _ in 0..THREADS {
                s.spawn(move || {
                    let x = x;
                    let AssertSendSafe(x) = x;
                    for _ in 0..DECREMENTS {
                        let old_count = (*x).fetch_sub(1, atomic::Ordering::Relaxed);
                        if old_count == 1 {
                            dealloc(x.cast::<u8>(), ATOMIC_LAYOUT);
                            eprintln!("Dropped the box");
                        }
                    }
                });
            }
        });
    }
}

#[derive(Clone, Copy)]
struct AssertSendSafe<T>(T);

unsafe impl<T> Send for AssertSendSafe<T> {}
unsafe impl<T> Sync for AssertSendSafe<T> {}

Error log

error: Undefined Behavior: Data race detected between (1) atomic store on thread `unnamed-1` and (2) deallocation on thread `unnamed-2` at alloc824. (2) just happened here
  --> src/main.rs:22:29
   |
22 | ...                   dealloc(x.cast::<u8>(), ATOMIC_LAYOUT);
   |                       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Data race detected between (1) atomic store on thread `unnamed-1` and (2) deallocation on thread `unnamed-2` at alloc824. (2) just happened here
   |
help: and (1) occurred earlier here
  --> src/main.rs:20:41
   |
20 |                         let old_count = (*x).fetch_sub(1, atomic::Ordering::Relaxed);
   |                                         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   = 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 closure at src/main.rs:22:29: 22:67

[zetanumbers]

Maybe I should move this example into another issue or rename this one?

[RalfJung]

Alas this failing example could be considered safe

This is not safe, since you do a deallocate that races with concurrent accesses.

Seems like the regression has been explained then and there's no Miri bug here so I'll close the issue.

[zetanumbers]

This is not safe, since you do a deallocate that races with concurrent accesses.

Why would it be unsafe tho?

1. Allocation always happens before deallocation;
2. Modification order is consistent while deallocation is sequenced after the last modification;
3. New allocation reusing this memory region and its further modifications may only happen after deallocation;

Thus modification order of that atomic variable remains bound from new allocation's (even non-atomic) memory accesses. I get if it's hard to formalize it like this, but I don't see any way how it could lead to UB in practice.

[RalfJung]

You agree that the following program has UB, I assume? This is a plain data race:

use std::{
    alloc::{Layout, alloc, dealloc},
    sync::atomic::{self, AtomicUsize},
};

const THREADS: usize = 2;
const DECREMENTS: usize = 10;
const ATOMIC_LAYOUT: Layout = Layout::new::<AtomicUsize>();

fn main() {
    unsafe {
        let x = AssertSendSafe(alloc(ATOMIC_LAYOUT).cast::<AtomicUsize>());
        x.0.write(AtomicUsize::new(THREADS * DECREMENTS));
        std::thread::scope(|s| {
            for _ in 0..THREADS {
                s.spawn(move || {
                    let x = x;
                    let AssertSendSafe(x) = x;
                    for _ in 0..DECREMENTS {
                        let old_count = (*x).fetch_sub(1, atomic::Ordering::Relaxed);
                        if old_count == 1 {
                            x.cast::<u8>().write(0); // <--- write instead of dealloc
                        }
                    }
                });
            }
        });
    }
}

#[derive(Clone, Copy)]
struct AssertSendSafe<T>(T);

unsafe impl<T> Send for AssertSendSafe<T> {}
unsafe impl<T> Sync for AssertSendSafe<T> {}

Deallocation is like a very destructive form of a non-atomic write. So it follows that your program must also have UB.

It is your responsibility that deallocation happens after all accesses to the allocation (in the "happens-before" sense of the concurrency memory model). A relaxed fetch_sub does not establish a happens-before edge.