Stacked borrows: Mutable reference pops stack when created in some cases

[eivindbergem]

I'm working on a statically allocated MPSC queue for embedded systems, and I've run into a miri issue. From my understanding of stacked borrows, reading from a mutable reference shouldn't pop from the stack. However, in my case the stack is popped when creating the reference, but only in some cases.

I've created a minimal example shown below.

Shared code:

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

struct Queue {
    field: AtomicBool,
}

impl Queue {
    fn new() -> Self {
        Self {
            field: AtomicBool::new(false),
        }
    }

    unsafe fn get_sender(&self) -> Sender {
        let this = &*(self as *const Self);

        Sender::new(&this.field)
    }

    fn recv(&mut self) {
        self.field.store(true, Ordering::Relaxed);
    }

    fn ref_mut(&mut self) -> &mut Self {
        self
    }
}

struct Sender {
    field: &'static AtomicBool,
}

impl Sender {
    fn new(field: &'static AtomicBool) -> Self {
        Self { field }
    }

    fn send(&self) {
        self.field.store(true, Ordering::Relaxed);
    }
}

This is fine:

fn main() {
    let mut queue = Queue::new();

    let sender = unsafe { queue.get_sender() };

    queue.recv();
    sender.send();
}

And this is also fine:

fn main() {
    let mut queue = Queue::new();

    let sender = unsafe { queue.get_sender() };
    let queue = queue.ref_mut();

    queue.recv();
    sender.send();
}

But this is not:

fn main() {
    let mut queue = Queue::new();

    let sender = unsafe { queue.get_sender() };
    let queue = &mut queue;

    queue.recv();
    sender.send();
}

Error (with tag tracking):

note: tracking was triggered
  --> src/main.rs:35:16
   |
35 |         Self { field }
   |                ^^^^^ created tag 2411
   |
   = note: inside `Sender::new` at src/main.rs:35:16
note: inside `Queue::get_sender` at src/main.rs:17:9
  --> src/main.rs:17:9
   |
17 |         Sender::new(&this.field)
   |         ^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `main` at src/main.rs:46:27
  --> src/main.rs:46:27
   |
46 |     let sender = unsafe { queue.get_sender() };
   |                           ^^^^^^^^^^^^^^^^^^

note: tracking was triggered
  --> src/main.rs:48:17
   |
48 |     let queue = &mut queue;
   |                 ^^^^^^^^^^ popped tracked tag for item [SharedReadWrite for <2411>] due to Write access for <2392>
   |
   = note: inside `main` at src/main.rs:48:17

error: Undefined Behavior: trying to reborrow <2411> for SharedReadWrite permission at alloc1283[0x0], but that tag does not exist in the borrow stack for this location
  --> src/main.rs:39:9
   |
39 |         self.field.store(true, Ordering::Relaxed);
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |         |
   |         trying to reborrow <2411> for SharedReadWrite permission at alloc1283[0x0], but that tag does not exist in the borrow stack for this location
   |         this error occurs as part of a reborrow at alloc1283[0x0..0x1]
   |
   = 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 `Sender::send` at src/main.rs:39:9
note: inside `main` at src/main.rs:52:5
  --> src/main.rs:52:5
   |
52 |     sender.send();
   |     ^^^^^^^^^^^^^

[saethlin]

This code: &mut queue is a reborrow of the base tag of queue. Reborrowing to a &mut pops everything above the parent tag. In this case, because the parent tag is the base tag, all pointers to queue are popped. If this instead reborrowed an existing pointer, that pointer and anything below it would still be in the stack.

I suspect you're saying "sometimes" because sometimes you're reborrowing other pointers.

[y86-dev]

What i find confusing and astonishing, is that

fn main() {
    let mut queue = Queue::new();

    let sender = unsafe { queue.get_sender() };
    let queue = queue.ref_mut();

    queue.recv();
    sender.send();
}

does not produce an error. I thought that it would desugar to this:

fn main() {
    let mut queue = Queue::new();

    let sender = unsafe { Queue::get_sender(&queue) };
    let queue = Queue::ref_mut(&mut queue);

    Queue::recv(queue);
    Sender::send(&sender);
}

But in fact this code also gives the miri error that the code with &mut queue produces.
So then i looked at the MIR to see that in the second case the temporary reference created by &mut queue is dereferenced. In the first case MIR creates such a reference manually, but does not dereference it.
Is this expected behavior? Because I actually expected both examples to produce a miri error...

@eivindbergem you are not allowed to simultaneously have an &mut and & to the same memory. You are extending the lifetime of your AtomicBool to be 'static, this is unsafe, because you need to then ensure that that AtomicBool is never (for the duration of the lifetime, but here it is static, so forever) borrowed mutably. By later using queue mutably you violated this contract.
When using AtomicBool you also only need &, or are you storing additional data in your Queue? If so, then why not use a Mutex instead of AtomicBool (but maybe because you are working in embedded you cannot?).

[oli-obk]

I don't think that can be it just on its own. Consider that queue.ref_mut() should desugar to Queue::ref_mut(&mut queue), which also doesn't compile.

EDIT: @y86-dev beat me to it

More info: I think it must be two phase borrows, because the MIR for the method call looks like

        _5 = &mut _1;                   
        Retag([2phase] _5);             
        _4 = Queue::ref_mut(move _5) -> bb3;

instead of for the mutable borrow:

        _6 = &mut _1;                   
        Retag(_6);                      
        _5 = &mut (*_6);               
        Retag([2phase] _5);            
        _4 = Queue::ref_mut(move _5) -> bb3;

[eivindbergem]

@eivindbergem you are not allowed to simultaneously have an &mut and & to the same memory. You are extending the lifetime of your AtomicBool to be 'static, this is unsafe, because you need to then ensure that that AtomicBool is never (for the duration of the lifetime, but here it is static, so forever) borrowed mutably. By later using queue mutably you violated this contract. When using AtomicBool you also only need &, or are you storing additional data in your Queue? If so, then why not use a Mutex instead of AtomicBool (but maybe because you are working in embedded you cannot?).

I'm still trying to wrap my head around stacked borrows, so I thought I could get away with this, but I guess not. I don't actually need the queue to be mutable, but I want the queue to be member of another struct that is mutable. Because of static allocation, I can't wrap it in an Arc. I'd rather not have to do two static allocations, but be able to keep everything neatly in one statically allocated struct. Since this didn't work, I'm not sure how to do this and keep miri happy.

[y86-dev]

I am guessing that you are using some kind of synchronization wrapper, so you could just do it like this:

pub struct QueueAndData {
    data: SyncWrapper<Data>,
    queue: Queue,
}

impl QueueAndData {
    pub fn do_foo(&self) {
        self.data.lock().do_foo();
    }

    pub fn do_foobar(&self) {
        self.data.lock().do_foo();
        self.queue.do_bar();
    }
}

pub static QUEUE_AND_DATA: QueueAndData = ...;

You just need to be careful, that queue is now no longer synced with the SyncWrapper, but i guess that queue is doing some syncing of its own. But as you mentioned, you could also declare two statics which might be simpler at the definition site.

Another solution would be to make Queue: !Unpin. That is the current way of allowing aliasing. However you still are not allowed to simultaneously hold &'static and &'_ mut to the same location (you would then need to use raw pointers). But i would suggest to try to solve it another way as this !Unpin hack is implementation detail.

[eivindbergem]

Thanks for the help! I'll close this as the issue is on my end.

[y86-dev]

@oli-obk (and anyone else) do you think that the rules for two phase borrows should be adjusted? Because in this case just taking &mut on the queue is UB (if two-phase borrows allows for this, then it is a different story, as i am not too familiar with two phase borrows).
The two phase borrow is also not needed in this case, so why is it emitted (my guess is simplicity of implementation)?

We could also add a lint in miri, when a two phase borrow is reserved (i have no idea, if this information is available in MIR), but there are conflicting shared borrows similar to how the borrow checker does it.

[oli-obk]

I am not sure what the issue is here exactly, but we should make sure we know why two phase borrows allow this code and whether that is sound. If it is sound (because the borrow is delayed to the actual use site), then I'm wondering why we can't do something similar for the plain mutable borrow.

[RalfJung]

Two-phase borrows are basically treated like (tagged) raw pointers by Miri. They allow all sorts of funky aliasing so Stacked Borrows can't really do any better. Maybe future aliasing models can...

Cc rust-lang/rust#96268 rust-lang/rust#59159

[RalfJung]

Miri implements Stacked Borrows as intended here. So closing in favor of rust-lang/unsafe-code-guidelines#85.