Assigning Some instead of calling replace triggers Miri under some unsafe conditions

[angelorendina]

This is hopefully a small enough repro snippet:

#[test]
fn family() {
    struct Parent {
        value: u8,
        child: Option<Box<Self>>,
    }

    impl Parent {
        fn declare_child(&mut self, value: u8) {
            self.child.replace(Box::new(Self { value, child: None }));
        }

        fn declare_child_too(&mut self, value: u8) {
            self.child = Some(Box::new(Self { value, child: None }));
        }
    }

    // create the first ancestor
    let mut progenitor = Parent {
        value: 0,
        child: None,
    };

    // we record the lineage as a stack of raw pointers to each generation
    // we cannot have &mut as there would be aliasing/memory overlap
    // (e.g. both `x` and its child `y` could write into `x.child.value` <-> `y.value`)
    let mut past_parents = vec![];
    // to make this safe to use, we keep around one exclusive &mut reference
    // through which we perform all read and writes
    let mut parent_today = &mut progenitor;

    for i in 1..4 {
        // today's parent is becoming tomorrow's grandparent, so:
        // record it in the lineage (as a pointer)
        past_parents.push(parent_today as *mut Parent);
        // generate the new child
        parent_today.child = Some(Box::new(Parent { value: i, child: None }));
        // and make that the new parent for tomorrow
        parent_today = parent_today.child.as_mut().unwrap();
    }

    // now we can use the stack to navigate up the lineage
    while let Some(ptr) = past_parents.pop() {
        // SAFETY:
        // - ptr is valid (obtained directly from a valid &mut)
        // - aliasing is respected (there are no other references to the data, just this one &mut)
        parent_today = unsafe { ptr.as_mut().unwrap() };
    }

    // we should have reached the ancestor
    assert_eq!(parent_today.value, 0);
}

I am experimenting with unsafe, so apologies if the code/comments above are wrong or misleading.

Running cargo miri test, possible UB is detected because

help: <192863> was created by a SharedReadWrite retag at offsets [0x0..0x10]
   past_parents.push(parent_today as *mut Parent);
                     ^^^^^^^^^^^^
help: <192863> was later invalidated at offsets [0x0..0x8] by a write access
   parent_today.child = Some(Box::new(Parent { val...
   ^^^^^^^^^^^^^^^^^^

1. I am not really sure I understand the problem here. If I rewrite that assignment as parent_today.child.replace(Box::new(Self { value, child: None })); then Miri is happy and reports no issue. Could I get some insight on this?
2. If I declare helper methods

impl Parent {
    fn declare_child(&mut self, value: u8) {
        self.child.replace(Box::new(Self { value, child: None }));
    }

    fn declare_child_too(&mut self, value: u8) {
        self.child = Some(Box::new(Self { value, child: None }));
    }
}

which just wrap the two different behaviours of the previous point, then Miri reports no issue when using either (in place of the incriminated assignment). In particular, I would expect declare_child_too to trigger the same error reported originally.

[RalfJung]

If I rewrite that assignment as parent_today.child.replace(Box::new(Self { value, child: None })); then Miri is happy and reports no issue. Could I get some insight on this?

By writing it that way, you are creating a two-phase borrow (that's how Rust handles implicit mutable references for function calls). Sadly two-phase borrows are incompatible with Stacked Borrows so Miri treats them like raw pointers, which in this case then happens to allow the code.

That is a Stacked Borrows/Miri limitation, and we are actively working on a better aliasing model that can properly track two-phase borrows. If you write (&mut parent_today.child).replace, you should see the error come back, since that explicit &mut will be a regular (not-2-phase) borrow.

That also explains why these wrapping functions help -- they, too, will be called using two-phase borrows. This is all not great, and Miri should error (or not error) consistently here, but turns out that is actually quite hard to achieve and we are not there yet.

---

The problem with this code is that you are doing parent_today as *mut Parent, which creates a raw pointer that may be used until the next time parent_today is used again, and then you immediately use parent_today again, which invalidates the raw pointer. For code with rampant aliasing like this, you need to make sure to use raw pointers throughout. parent_today should be a raw pointer, not a reference.

aliasing is respected (there are no other references to the data, just this one &mut)

This seems to indicate a fundamental misunderstanding: for aliasing to be respected, there must be no other pointers or references to this data that are being used. An &mut and *mut that alias will lead to UB when both are being used. The uniqueness guarantees of &mut would be worth absolutely nothing if we would allow aliasing raw pointers.

So, the safety comment also needs to explain that none of the aliasing pointers are going to be used for the lifetime of this mutable reference.

[angelorendina]

Thanks for your answer, that was extremely helpful!
What should I do about this issue? Is there an already open tracking issue for two-phase borrows I can link to, so I can close this? Or feel free to just close as answered.

[saethlin]

I don't know that there is one tracking issue, but you can start from here and follow links: rust-lang/rust#96268 (your opening this issue is basically the problem I was concerned about)

This is a classic problem with sanitizers: When you expect them to complain but they don't, it's nearly impossible to figure out why. We do have some special functions (they are documented in the README) which you can use to print out borrow stacks at runtime. Though I wonder if miri_print_borrow_stacks will be all that enlightening because when the program is UB, the problematic tag is 189400. Perhaps a Miri debugger could do better, but that doesn't on its own solve the data volume issue.

[RalfJung]

The tracking issue is at rust-lang/unsafe-code-guidelines#85. It's a model issue, not a Miri implementation issue, which is why it is in another repo.