Test whether self-referential futures are compatible with stacked borrows

[RalfJung]

I have no idea if an async function that borrows across a yield point is compatible with Stacked Borrows. We should find out! I just am not sure how.

@cramertj @withoutboats I could use your help. :) What is a minimal example for code that creates a self-referential future and then runs it? Ideally with no dependencies beyond libstd but that might not be possible.^^ Also, if there are different cases/"kinds" of self-referential fields in futures, we should make sure we cover all of them.

rustc must test these things somehow, right? Might be worth looking into that, too.

[Nemo157]

I'm actually working on trying to create a step-by-step example of how an async fn is first transformed into a self-referential generator then into a state machine. I should have a nice small self-contained example that uses both references into upvars and local variables ready in the next couple of days. (I already have this playground that I intended to use, but I just realised I made a mistake in expanding await! that means this doesn't actually require self-references into local variables, just upvars).

if there are different cases/"kinds" of self-referential fields in futures, we should make sure we cover all of them

There are only two different kinds that I know of, and fundamentally they should be the same. You can have references to upvars that have been moved into the generator and references to locals created while the generator is running. Once the generator transform has run these both just become references into the generator state variable, and I don't think they're distinguishable in the MIR.

[Nemo157]

Actually I might as well throw something together now, here should be a small example showing all kinds of references in an async fn. y is an upvar of the generator created in foo and z is a local of it; a reference to each are moved into the async block on line 14, inside await! the result implementation of this block is stored into a local variable (so that variable is referencing both y and z in the outer generator) and polled to completion over a yield point. a is a local of the generator which has a reference taken but is dereferenced and dropped without hitting a yield point. Finally x is kept as reference out of the generator environment, as an example of non-self-referential references.

There's also the minimal framework for running an async fn inside main, this may be changing a little bit in the near future in a couple of ways, but I'll be creating an up-to-date version of this example as it does.

[withoutboats]

@RalfJung might it be easier to focus on generators before async fn, since they have direct access to yield?

[cramertj]

Here's a self-referential generator example:

#![feature(generators, generator_trait)]

use std::ops::Generator;

fn main() {
    let mut generator = || {
        let mut x = Box::new(5);
        let y = &mut *x;
        *y = 5;
        yield ();
        *y = 10;
        *x
    };
    
    unsafe { generator.resume() };
}

[RalfJung]

@cramertj Thanks! I thought there had to be async and a Future. I clearly know nothing about how async functions work.^^

[RalfJung]

To my big surprise, this actually passes in miri :D

EDIT: Even more interestingly though, it no longer passes locally...

[RalfJung]

Oh. The generator MIR transform happens after we added the retag statements, leading to... strange results.

However, the generator MIR stuff happens extremely late -- it happens after inlining! That seems really strange to me, shouldn't we first get the MIR "complete" before doing interesting transformations?

[RalfJung]

See rust-lang/rust#56100

[RalfJung]

@withoutboats That makes sense, I wasn't aware of the layering here. This seems covered by #536 though, and it's actually working (with a small rustc fix), which is great!

However, something like @Nemo157's example also seems like a nice addition. Thanks for that @Nemo157! It also seems to pass, to my ever greater surprise.^^

[RalfJung]

With barriers entering the picture, I now see a violation of Stacked Borrows in async functions. The error happens with the following stacktrace:

error[E0080]: constant evaluation error: Stopping looking for borrow being accessed (Shr(None)) because of barrier (765)
    --> /home/r/src/rust/rustc/src/libcore/ptr.rs:2928:9
     |
2928 |         &mut *self.as_ptr()
     |         ^^^^^^^^^^^^^^^^^^^ Stopping looking for borrow being accessed (Shr(None)) because of barrier (765)
     |
     = note: inside call to `<std::ptr::NonNull<T>><std::task::LocalWaker>::as_mut` at /home/r/src/rust/rustc/src/libstd/future.rs:101:16
     = note: inside call to `std::future::get_task_waker::<[closure@DefId(1/1:1773 ~ std[de45]::future[0]::poll_with_tls_waker[0]::{{closure}}[0]) 0:std::pin::Pin<&mut std::future::GenFuture<[static generator@tests/run-pass-fullmir/async-fn.rs:15:26: 15:37 y:&&u32, z:&&u32 {}]>>], std::task::Poll<u32>>` at /home/r/src/rust/rustc/src/libstd/future.rs:110:5
note: inside call to `std::future::poll_with_tls_waker::<std::future::GenFuture<[static generator@tests/run-pass-fullmir/async-fn.rs:15:26: 15:37 y:&&u32, z:&&u32 {}]>>` at <::std::macros::await macros>:4:49
    --> tests/run-pass-fullmir/async-fn.rs:15:13
     |
15   |     let y = await!(async { *y + *z });
     |             ^^^^^^^^^^^^^^^^^^^^^^^^^
     = note: inside call to closure at /home/r/src/rust/rustc/src/libstd/future.rs:46:46
     = note: inside call to closure at /home/r/src/rust/rustc/src/libstd/future.rs:77:5
     = note: inside call to `std::future::set_task_waker::<[closure@DefId(1/1:1762 ~ std[de45]::future[0]::{{impl}}[1]::poll[0]::{{closure}}[0]) 0:std::pin::Pin<&mut std::future::GenFuture<[static generator@tests/run-pass-fullmir/async-fn.rs:11:42: 19:2 y:u32, x:&u32 for<'r, 's, 't0, 't1, 't2, 't3> {u32, &'r u32, &'s u32, impl std::future::Future, ()}]>>], std::task::Poll<u32>>` at /home/r/src/rust/rustc/src/libstd/future.rs:46:9
note: inside call to `<std::future::GenFuture<T> as std::future::Future><[static generator@tests/run-pass-fullmir/async-fn.rs:11:42: 19:2 y:u32, x:&u32 for<'r, 's, 't0, 't1, 't2, 't3> {u32, &'r u32, &'s u32, impl std::future::Future, ()}]>::poll` at tests/run-pass-fullmir/async-fn.rs:34:16
    --> tests/run-pass-fullmir/async-fn.rs:34:16
     |
34   |     assert_eq!(unsafe { Pin::new_unchecked(&mut fut) }.poll(&lw), Poll::Ready(31));
     |                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
     = note: inside call to `main` at /home/r/src/rust/rustc/src/libstd/rt.rs:74:34

The relevant parts are: There is a call to set_task_waker, which does

/// Sets the thread-local task context used by async/await futures.
pub fn set_task_waker<F, R>(lw: &LocalWaker, f: F) -> R
where
    F: FnOnce() -> R
{
    let old_waker = TLS_WAKER.with(|tls_waker| {
        tls_waker.replace(Some(NonNull::from(lw)))
    });
    let _reset_waker = SetOnDrop(old_waker);
    f()
}

Notice that lw is a shared reference. This gets called with some f that calls get_task_waker:

pub fn get_task_waker<F, R>(f: F) -> R
where
    F: FnOnce(&LocalWaker) -> R
{
    let waker_ptr = TLS_WAKER.with(|tls_waker| {
        // Clear the entry so that nested `get_task_waker` calls
        // will fail or set their own value.
        tls_waker.replace(None)
    });
    let _reset_waker = SetOnDrop(waker_ptr);

    let mut waker_ptr = waker_ptr.expect(
        "TLS LocalWaker not set. This is a rustc bug. \
        Please file an issue on https://github.com/rust-lang/rust.");
    unsafe { f(waker_ptr.as_mut()) }
}

Notice the as_mut: This creates a mutable reference, while there still is an aliasing shared reference live in set_task_waker! That seems a clear violation of mutable references being unique to me.

It also likely is just a typo, as_ref() should work as well because f just needs a shared reference.

[RalfJung]

I confirmed that rust-lang/rust#56319 fixes this.

[withoutboats]

This bug would have also been eliminated when the desugaring uses some sort of resume argument instead of TLS (that is, the entire context in which the mistake occurred is incidental complexity to the implementation)

[RalfJung]

Turns out I was very right to be suspicious, but didn't come up with the right test case. But the issue with Stacked Borrows and self-referential generators is a spec one, not a Miri one, so it is being tracked at rust-lang/unsafe-code-guidelines#148.