Understanding the stacked borrow check in miri+potential unsoundness in genawaiter crate?

rlee287 · August 21, 2021, 4:27am

While testing code using genawaiter under Miri, I encountered a stacked borrows violation, which I was able to reproduce with this code sample:

use genawaiter::rc::Gen; // also triggers with genawaiter::sync::Gen

pub fn simple_range_iter(upper_bound: usize) -> impl IntoIterator<Item = usize> {
    let mut counter = 0;
    Gen::new(|state| async move {
        while counter < upper_bound {
            state.yield_(counter).await;
            counter += 1;
        }
    })
}

/*
 * All tests pass under `cargo test` and `cargo +nightly test`
 * Errors described below occur with `cargo +nightly miri test`
 */
mod test {
    use super::*;
    #[test]
    fn range_iter_empty() {
        // This test works correctly
        let mut counter_empty_iter = simple_range_iter(0).into_iter();
        assert_eq!(counter_empty_iter.next(), None);
    }
    #[test]
    fn range_iter_to_five() {
        // This test triggers a miri stacked borrows violation
        /*
        error: Undefined Behavior: trying to reborrow for SharedReadOnly at alloc85070+0x10, but parent tag <212711> does not have an appropriate item in the borrow stack
            --> /home/ryan/.cargo/registry/src/github.com-1ecc6299db9ec823/genawaiter-0.99.1/src/core.rs:164:15
                |
            164 |         match self.airlock.peek() {
                |               ^^^^^^^^^^^^ trying to reborrow for SharedReadOnly at alloc85070+0x10, but parent tag <212711> does not have an appropriate item in the borrow stack
         */
        let mut counter_ref = 0;
        for number in simple_range_iter(5) {
            assert_eq!(counter_ref, number);
            counter_ref += 1;
        }
    }
}

Running this with cargo +nightly miri test (1.56.0-nightly (a0035916e 2021-0
8-20)) results in the following printout:

running 2 tests
test test::range_iter_empty ... ok
test test::range_iter_to_five ... error: Undefined Behavior: trying to reborrow for SharedReadOnly at alloc75845+0x10, but parent tag <189131> does not have an appropriate item in the borrow stack
   --> /home/ryan/.cargo/registry/src/github.com-1ecc6299db9ec823/genawaiter-0.99.1/src/core.rs:164:15
    |
164 |         match self.airlock.peek() {
    |               ^^^^^^^^^^^^ trying to reborrow for SharedReadOnly at alloc75845+0x10, but parent tag <189131> does not have an appropriate item in the borrow stack
    |
    = help: this indicates a potential bug in the program: it performed an invalid operation, but the rules it violated are still experimental
    = help: see https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md for further information
            
    = note: inside `<genawaiter::core::Barrier<genawaiter::rc::engine::Airlock<usize, ()>> as std::future::Future>::poll` at /home/ryan/.cargo/registry/src/github.com-1ecc6299db9ec823/genawaiter-0.99.1/src/core.rs:164:15
note: inside closure at src/lib.rs:7:13
   --> src/lib.rs:7:13
    |
7   |             state.yield_(counter).await;
    |             ^^^^^^^^^^^^^^^^^^^^^^^^^^^
    = note: inside `<std::future::from_generator::GenFuture<[static generator@src/lib.rs:5:33: 10:6]> as std::future::Future>::poll` at /home/ryan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/future/mod.rs:80:19
    = note: inside `genawaiter::core::advance::<usize, (), std::future::from_generator::GenFuture<[static generator@src/lib.rs:5:33: 10:6]>, genawaiter::rc::engine::Airlock<usize, ()>>` at /home/ryan/.cargo/registry/src/github.com-1ecc6299db9ec823/genawaiter-0.99.1/src/core.rs:34:11
    = note: inside `genawaiter::rc::Gen::<usize, (), std::future::from_generator::GenFuture<[static generator@src/lib.rs:5:33: 10:6]>>::resume_with` at /home/ryan/.cargo/registry/src/github.com-1ecc6299db9ec823/genawaiter-0.99.1/src/rc/generator.rs:47:9
    = note: inside `genawaiter::rc::Gen::<usize, (), std::future::from_generator::GenFuture<[static generator@src/lib.rs:5:33: 10:6]>>::resume` at /home/ryan/.cargo/registry/src/github.com-1ecc6299db9ec823/genawaiter-0.99.1/src/rc/generator.rs:59:9
    = note: inside `<genawaiter::rc::iterator::IntoIter<usize, std::future::from_generator::GenFuture<[static generator@src/lib.rs:5:33: 10:6]>> as std::iter::Iterator>::next` at /home/ryan/.cargo/registry/src/github.com-1ecc6299db9ec823/genawaiter-0.99.1/src/rc/iterator.rs:22:15
note: inside `test::range_iter_to_five` at src/lib.rs:36:23
   --> src/lib.rs:36:23
    |
36  |         for number in simple_range_iter(5) {
    |                       ^^^^^^^^^^^^^^^^^^^^
note: inside closure at src/lib.rs:26:5
   --> src/lib.rs:26:5
    |
25  |       #[test]
    |       ------- in this procedural macro expansion
26  | /     fn range_iter_to_five() {
27  | |         // This test triggers a miri stacked borrows violation
28  | |         /*
29  | |         error: Undefined Behavior: trying to reborrow for SharedReadO...
...   |
39  | |         }
40  | |     }
    | |_____^
    = note: inside `<[closure@src/lib.rs:26:5: 40:6] as std::ops::FnOnce<()>>::call_once - shim` at /home/ryan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:227:5
    = note: inside `<fn() as std::ops::FnOnce<()>>::call_once - shim(fn())` at /home/ryan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:227:5
    = note: inside `test::test::__rust_begin_short_backtrace::<fn()>` at /home/ryan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:578:5
    = note: inside closure at /home/ryan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:569:30
    = note: inside `<[closure@test::test::run_test::{closure#2}] as std::ops::FnOnce<()>>::call_once - shim(vtable)` at /home/ryan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:227:5
    = note: inside `<std::boxed::Box<dyn std::ops::FnOnce() + std::marker::Send> as std::ops::FnOnce<()>>::call_once` at /home/ryan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/boxed.rs:1636:9
    = note: inside `<std::panic::AssertUnwindSafe<std::boxed::Box<dyn std::ops::FnOnce() + std::marker::Send>> as std::ops::FnOnce<()>>::call_once` at /home/ryan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/panic/unwind_safe.rs:271:9
    = note: inside `std::panicking::r#try::do_call::<std::panic::AssertUnwindSafe<std::boxed::Box<dyn std::ops::FnOnce() + std::marker::Send>>, ()>` at /home/ryan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:403:40
    = note: inside `std::panicking::r#try::<(), std::panic::AssertUnwindSafe<std::boxed::Box<dyn std::ops::FnOnce() + std::marker::Send>>>` at /home/ryan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:367:19
    = note: inside `std::panic::catch_unwind::<std::panic::AssertUnwindSafe<std::boxed::Box<dyn std::ops::FnOnce() + std::marker::Send>>, ()>` at /home/ryan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panic.rs:129:14
    = note: inside `test::test::run_test_in_process` at /home/ryan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:601:18
    = note: inside closure at /home/ryan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:493:39
    = note: inside `test::test::run_test::run_test_inner` at /home/ryan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:531:13
    = note: inside `test::test::run_test` at /home/ryan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:565:28
    = note: inside `test::test::run_tests::<[closure@test::test::run_tests_console::{closure#2}]>` at /home/ryan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:306:17
    = note: inside `test::test::run_tests_console` at /home/ryan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/console.rs:290:5
    = note: inside `test::test::test_main` at /home/ryan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:123:15
    = note: inside `test::test::test_main_static` at /home/ryan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:142:5
    = note: inside `main`
    = note: inside `<fn() as std::ops::FnOnce<()>>::call_once - shim(fn())` at /home/ryan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:227:5
    = note: inside `std::sys_common::backtrace::__rust_begin_short_backtrace::<fn(), ()>` at /home/ryan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/sys_common/backtrace.rs:125:18
    = note: inside closure at /home/ryan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:63:18
    = note: inside `std::ops::function::impls::<impl std::ops::FnOnce<()> for &dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe>::call_once` at /home/ryan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:259:13
    = note: inside `std::panicking::r#try::do_call::<&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe, i32>` at /home/ryan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:403:40
    = note: inside `std::panicking::r#try::<i32, &dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe>` at /home/ryan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:367:19
    = note: inside `std::panic::catch_unwind::<&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe, i32>` at /home/ryan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panic.rs:129:14
    = note: inside closure at /home/ryan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:45:48
    = note: inside `std::panicking::r#try::do_call::<[closure@std::rt::lang_start_internal::{closure#2}], isize>` at /home/ryan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:403:40
    = note: inside `std::panicking::r#try::<isize, [closure@std::rt::lang_start_internal::{closure#2}]>` at /home/ryan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:367:19
    = note: inside `std::panic::catch_unwind::<[closure@std::rt::lang_start_internal::{closure#2}], isize>` at /home/ryan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panic.rs:129:14
    = note: inside `std::rt::lang_start_internal` at /home/ryan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:45:20
    = note: inside `std::rt::lang_start::<()>` at /home/ryan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:62:5
    = note: this error originates in the attribute macro `test` (in Nightly builds, run with -Z macro-backtrace for more info)

error: aborting due to previous error

The message seems to suggest that the issue arises from self.airlock being provided through a mutable reference, while being passed as an immutable reference to .peek(). However, the following example code does not trigger a stacked borrows error from Miri:

fn vector_func(arr: &mut Vec<String>) {
    match arr.len() {
        2 => arr.clear(),
        _ => () // Do nothing
    }
}

fn main() {
    // Something that is runtime-determined that cannot be constant-folded away
    let mut arg_arr: Vec<String> = std::env::args().collect();
    vector_func(&mut arg_arr);
    println!("{:?}", arg_arr);
}

Is the error message arising from a current limitation of two-phase borrowing, or is it an actual indication of unsoundness?

Cerber-Ursi · August 21, 2021, 5:02am

I'm curious if this is the same issue as Suspicious "undefined behavior" report by miri when using `tokio::task::yield_now`?

alice · August 21, 2021, 9:55am

Yes it's the same as mentioned there.

H2CO3 · August 21, 2021, 5:01pm

@alice you wrote in your answer to that thread:

I'm curious what this means policy-wise?

Is it a legitimate bug in MIRI?
Does the "MIRI has no false positives when it comes to UB" assertion not hold anymore?

alice · August 21, 2021, 8:28pm

It's less of a bug in miri and more of a bug in the Rust soundness model. Stacked borrows simply does not allow self-referential objects like the futures generated by async/await.

system · November 19, 2021, 8:29pm

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.