Auto merge of #3106 - RalfJung:tree-borrows-initial, r=RalfJung

Tree Borrows: do not create new tags as 'Active'

Cc `@Vanille-N`

9 files changed, 106 insertions, 61 deletions

diff --git a/src/tools/miri/src/borrow_tracker/mod.rs b/src/tools/miri/src/borrow_tracker/mod.rs
index b6dfd9944ee..1951cf87f2f 100644
--- a/src/tools/miri/src/borrow_tracker/mod.rs
+++ b/src/tools/miri/src/borrow_tracker/mod.rs
@@ -305,7 +305,10 @@ pub trait EvalContextExt<'mir, 'tcx: 'mir>: crate::MiriInterpCxExt<'mir, 'tcx> {
         }
     }
 
-    fn protect_place(&mut self, place: &MPlaceTy<'tcx, Provenance>) -> InterpResult<'tcx> {
+    fn protect_place(
+        &mut self,
+        place: &MPlaceTy<'tcx, Provenance>,
+    ) -> InterpResult<'tcx, MPlaceTy<'tcx, Provenance>> {
         let this = self.eval_context_mut();
         let method = this.machine.borrow_tracker.as_ref().unwrap().borrow().borrow_tracker_method;
         match method {
diff --git a/src/tools/miri/src/borrow_tracker/stacked_borrows/mod.rs b/src/tools/miri/src/borrow_tracker/stacked_borrows/mod.rs
index e670dcef330..a440ee720c7 100644
--- a/src/tools/miri/src/borrow_tracker/stacked_borrows/mod.rs
+++ b/src/tools/miri/src/borrow_tracker/stacked_borrows/mod.rs
@@ -810,36 +810,43 @@ trait EvalContextPrivExt<'mir: 'ecx, 'tcx: 'mir, 'ecx>: crate::MiriInterpCxExt<'
         Ok(Some(Provenance::Concrete { alloc_id, tag: new_tag }))
     }
 
-    /// Retags an individual pointer, returning the retagged version.
-    /// `kind` indicates what kind of reference is being created.
-    fn sb_retag_reference(
+    fn sb_retag_place(
         &mut self,
-        val: &ImmTy<'tcx, Provenance>,
+        place: &MPlaceTy<'tcx, Provenance>,
         new_perm: NewPermission,
         info: RetagInfo, // diagnostics info about this retag
-    ) -> InterpResult<'tcx, ImmTy<'tcx, Provenance>> {
+    ) -> InterpResult<'tcx, MPlaceTy<'tcx, Provenance>> {
         let this = self.eval_context_mut();
-        // We want a place for where the ptr *points to*, so we get one.
-        let place = this.ref_to_mplace(val)?;
-        let size = this.size_and_align_of_mplace(&place)?.map(|(size, _)| size);
+        let size = this.size_and_align_of_mplace(place)?.map(|(size, _)| size);
         // FIXME: If we cannot determine the size (because the unsized tail is an `extern type`),
         // bail out -- we cannot reasonably figure out which memory range to reborrow.
         // See https://github.com/rust-lang/unsafe-code-guidelines/issues/276.
         let size = match size {
             Some(size) => size,
-            None => return Ok(val.clone()),
+            None => return Ok(place.clone()),
         };
 
         // Compute new borrow.
         let new_tag = this.machine.borrow_tracker.as_mut().unwrap().get_mut().new_ptr();
 
         // Reborrow.
-        let new_prov = this.sb_reborrow(&place, size, new_perm, new_tag, info)?;
+        let new_prov = this.sb_reborrow(place, size, new_perm, new_tag, info)?;
 
-        // Adjust pointer.
-        let new_place = place.map_provenance(|_| new_prov);
+        // Adjust place.
+        Ok(place.clone().map_provenance(|_| new_prov))
+    }
 
-        // Return new pointer.
+    /// Retags an individual pointer, returning the retagged version.
+    /// `kind` indicates what kind of reference is being created.
+    fn sb_retag_reference(
+        &mut self,
+        val: &ImmTy<'tcx, Provenance>,
+        new_perm: NewPermission,
+        info: RetagInfo, // diagnostics info about this retag
+    ) -> InterpResult<'tcx, ImmTy<'tcx, Provenance>> {
+        let this = self.eval_context_mut();
+        let place = this.ref_to_mplace(val)?;
+        let new_place = this.sb_retag_place(&place, new_perm, info)?;
         Ok(ImmTy::from_immediate(new_place.to_ref(this), val.layout))
     }
 }
@@ -972,26 +979,23 @@ pub trait EvalContextExt<'mir, 'tcx: 'mir>: crate::MiriInterpCxExt<'mir, 'tcx> {
     /// call.
     ///
     /// This is used to ensure soundness of in-place function argument/return passing.
-    fn sb_protect_place(&mut self, place: &MPlaceTy<'tcx, Provenance>) -> InterpResult<'tcx> {
+    fn sb_protect_place(
+        &mut self,
+        place: &MPlaceTy<'tcx, Provenance>,
+    ) -> InterpResult<'tcx, MPlaceTy<'tcx, Provenance>> {
         let this = self.eval_context_mut();
 
-        // We have to turn the place into a pointer to use the usual retagging logic.
-        // (The pointer type does not matter, so we use a raw pointer.)
-        let ptr = this.mplace_to_ref(place)?;
-        // Reborrow it. With protection! That is the entire point.
+        // Retag it. With protection! That is the entire point.
         let new_perm = NewPermission::Uniform {
             perm: Permission::Unique,
             access: Some(AccessKind::Write),
             protector: Some(ProtectorKind::StrongProtector),
         };
-        let _new_ptr = this.sb_retag_reference(
-            &ptr,
+        this.sb_retag_place(
+            place,
             new_perm,
             RetagInfo { cause: RetagCause::InPlaceFnPassing, in_field: false },
-        )?;
-        // We just throw away `new_ptr`, so nobody can access this memory while it is protected.
-
-        Ok(())
+        )
     }
 
     /// Mark the given tag as exposed. It was found on a pointer with the given AllocId.
diff --git a/src/tools/miri/src/borrow_tracker/tree_borrows/mod.rs b/src/tools/miri/src/borrow_tracker/tree_borrows/mod.rs
index 924e0de38c9..68bc4a415c6 100644
--- a/src/tools/miri/src/borrow_tracker/tree_borrows/mod.rs
+++ b/src/tools/miri/src/borrow_tracker/tree_borrows/mod.rs
@@ -5,7 +5,11 @@ use rustc_target::abi::{Abi, Align, Size};
 use crate::borrow_tracker::{AccessKind, GlobalStateInner, ProtectorKind, RetagFields};
 use rustc_middle::{
     mir::{Mutability, RetagKind},
-    ty::{self, layout::HasParamEnv, Ty},
+    ty::{
+        self,
+        layout::{HasParamEnv, HasTyCtxt},
+        Ty,
+    },
 };
 use rustc_span::def_id::DefId;
 
@@ -174,6 +178,8 @@ trait EvalContextPrivExt<'mir: 'ecx, 'tcx: 'mir, 'ecx>: crate::MiriInterpCxExt<'
         new_tag: BorTag,
     ) -> InterpResult<'tcx, Option<Provenance>> {
         let this = self.eval_context_mut();
+        // Make sure the new permission makes sense as the initial permission of a fresh tag.
+        assert!(new_perm.initial_state.is_initial());
         // Ensure we bail out if the pointer goes out-of-bounds (see miri#1050).
         this.check_ptr_access_align(
             place.ptr(),
@@ -275,10 +281,6 @@ trait EvalContextPrivExt<'mir: 'ecx, 'tcx: 'mir, 'ecx>: crate::MiriInterpCxExt<'
             diagnostics::AccessCause::Reborrow,
         )?;
         // Record the parent-child pair in the tree.
-        // FIXME: We should eventually ensure that the following `assert` holds, because
-        // some "exhaustive" tests consider only the initial configurations that satisfy it.
-        // The culprit is `Permission::new_active` in `tb_protect_place`.
-        //assert!(new_perm.initial_state.is_initial());
         tree_borrows.new_child(orig_tag, new_tag, new_perm.initial_state, range, span)?;
         drop(tree_borrows);
 
@@ -306,15 +308,12 @@ trait EvalContextPrivExt<'mir: 'ecx, 'tcx: 'mir, 'ecx>: crate::MiriInterpCxExt<'
         Ok(Some(Provenance::Concrete { alloc_id, tag: new_tag }))
     }
 
-    /// Retags an individual pointer, returning the retagged version.
-    fn tb_retag_reference(
+    fn tb_retag_place(
         &mut self,
-        val: &ImmTy<'tcx, Provenance>,
+        place: &MPlaceTy<'tcx, Provenance>,
         new_perm: NewPermission,
-    ) -> InterpResult<'tcx, ImmTy<'tcx, Provenance>> {
+    ) -> InterpResult<'tcx, MPlaceTy<'tcx, Provenance>> {
         let this = self.eval_context_mut();
-        // We want a place for where the ptr *points to*, so we get one.
-        let place = this.ref_to_mplace(val)?;
 
         // Determine the size of the reborrow.
         // For most types this is the entire size of the place, however
@@ -323,7 +322,7 @@ trait EvalContextPrivExt<'mir: 'ecx, 'tcx: 'mir, 'ecx>: crate::MiriInterpCxExt<'
         // then we override the size to do a zero-length reborrow.
         let reborrow_size = match new_perm {
             NewPermission { zero_size: false, .. } =>
-                this.size_and_align_of_mplace(&place)?
+                this.size_and_align_of_mplace(place)?
                     .map(|(size, _)| size)
                     .unwrap_or(place.layout.size),
             _ => Size::from_bytes(0),
@@ -339,12 +338,21 @@ trait EvalContextPrivExt<'mir: 'ecx, 'tcx: 'mir, 'ecx>: crate::MiriInterpCxExt<'
         let new_tag = this.machine.borrow_tracker.as_mut().unwrap().get_mut().new_ptr();
 
         // Compute the actual reborrow.
-        let new_prov = this.tb_reborrow(&place, reborrow_size, new_perm, new_tag)?;
+        let new_prov = this.tb_reborrow(place, reborrow_size, new_perm, new_tag)?;
 
-        // Adjust pointer.
-        let new_place = place.map_provenance(|_| new_prov);
+        // Adjust place.
+        Ok(place.clone().map_provenance(|_| new_prov))
+    }
 
-        // Return new pointer.
+    /// Retags an individual pointer, returning the retagged version.
+    fn tb_retag_reference(
+        &mut self,
+        val: &ImmTy<'tcx, Provenance>,
+        new_perm: NewPermission,
+    ) -> InterpResult<'tcx, ImmTy<'tcx, Provenance>> {
+        let this = self.eval_context_mut();
+        let place = this.ref_to_mplace(val)?;
+        let new_place = this.tb_retag_place(&place, new_perm)?;
         Ok(ImmTy::from_immediate(new_place.to_ref(this), val.layout))
     }
 }
@@ -493,22 +501,21 @@ pub trait EvalContextExt<'mir, 'tcx: 'mir>: crate::MiriInterpCxExt<'mir, 'tcx> {
     /// call.
     ///
     /// This is used to ensure soundness of in-place function argument/return passing.
-    fn tb_protect_place(&mut self, place: &MPlaceTy<'tcx, Provenance>) -> InterpResult<'tcx> {
+    fn tb_protect_place(
+        &mut self,
+        place: &MPlaceTy<'tcx, Provenance>,
+    ) -> InterpResult<'tcx, MPlaceTy<'tcx, Provenance>> {
         let this = self.eval_context_mut();
 
-        // We have to turn the place into a pointer to use the usual retagging logic.
-        // (The pointer type does not matter, so we use a raw pointer.)
-        let ptr = this.mplace_to_ref(place)?;
-        // Reborrow it. With protection! That is the entire point.
+        // Retag it. With protection! That is the entire point.
         let new_perm = NewPermission {
-            initial_state: Permission::new_active(),
+            initial_state: Permission::new_reserved(
+                place.layout.ty.is_freeze(this.tcx(), this.param_env()),
+            ),
             zero_size: false,
             protector: Some(ProtectorKind::StrongProtector),
         };
-        let _new_ptr = this.tb_retag_reference(&ptr, new_perm)?;
-        // We just throw away `new_ptr`, so nobody can access this memory while it is protected.
-
-        Ok(())
+        this.tb_retag_place(place, new_perm)
     }
 
     /// Mark the given tag as exposed. It was found on a pointer with the given AllocId.
diff --git a/src/tools/miri/src/borrow_tracker/tree_borrows/perms.rs b/src/tools/miri/src/borrow_tracker/tree_borrows/perms.rs
index 16bad13e28f..3e019356ca7 100644
--- a/src/tools/miri/src/borrow_tracker/tree_borrows/perms.rs
+++ b/src/tools/miri/src/borrow_tracker/tree_borrows/perms.rs
@@ -159,6 +159,7 @@ impl Permission {
     }
 
     /// Default initial permission of the root of a new tree.
+    /// Must *only* be used for the root, this is not in general an "initial" permission!
     pub fn new_active() -> Self {
         Self { inner: Active }
     }
diff --git a/src/tools/miri/src/machine.rs b/src/tools/miri/src/machine.rs
index f1c50794ca8..fb56e0135b4 100644
--- a/src/tools/miri/src/machine.rs
+++ b/src/tools/miri/src/machine.rs
@@ -1275,19 +1275,25 @@ impl<'mir, 'tcx> Machine<'mir, 'tcx> for MiriMachine<'mir, 'tcx> {
         ecx: &mut InterpCx<'mir, 'tcx, Self>,
         place: &PlaceTy<'tcx, Provenance>,
     ) -> InterpResult<'tcx> {
-        // We do need to write `uninit` so that even after the call ends, the former contents of
-        // this place cannot be observed any more.
-        ecx.write_uninit(place)?;
         // If we have a borrow tracker, we also have it set up protection so that all reads *and
         // writes* during this call are insta-UB.
-        if ecx.machine.borrow_tracker.is_some() {
+        let protected_place = if ecx.machine.borrow_tracker.is_some() {
             // Have to do `to_op` first because a `Place::Local` doesn't imply the local doesn't have an address.
             if let Either::Left(place) = ecx.place_to_op(place)?.as_mplace_or_imm() {
-                ecx.protect_place(&place)?;
+                ecx.protect_place(&place)?.into()
             } else {
                 // Locals that don't have their address taken are as protected as they can ever be.
+                place.clone()
             }
-        }
+        } else {
+            // No borrow tracker.
+            place.clone()
+        };
+        // We do need to write `uninit` so that even after the call ends, the former contents of
+        // this place cannot be observed any more. We do the write after retagging so that for
+        // Tree Borrows, this is considered to activate the new tag.
+        ecx.write_uninit(&protected_place)?;
+        // Now we throw away the protected place, ensuring its tag is never used again.
         Ok(())
     }
 
diff --git a/src/tools/miri/tests/fail/function_calls/arg_inplace_mutate.tree.stderr b/src/tools/miri/tests/fail/function_calls/arg_inplace_mutate.tree.stderr
index 544cd575ada..3d8ba68547b 100644
--- a/src/tools/miri/tests/fail/function_calls/arg_inplace_mutate.tree.stderr
+++ b/src/tools/miri/tests/fail/function_calls/arg_inplace_mutate.tree.stderr
@@ -19,11 +19,17 @@ LL | |             let non_copy = S(42);
 LL | |
 LL | |     }
    | |_____^
-help: the protected tag <TAG> was created here, in the initial state Active
+help: the protected tag <TAG> was created here, in the initial state Reserved
   --> $DIR/arg_inplace_mutate.rs:LL:CC
    |
 LL |     unsafe { ptr.write(S(0)) };
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^
+help: the protected tag <TAG> later transitioned to Active due to a child write access at offsets [0x0..0x4]
+  --> $DIR/arg_inplace_mutate.rs:LL:CC
+   |
+LL |     unsafe { ptr.write(S(0)) };
+   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^
+   = help: this transition corresponds to the first write to a 2-phase borrowed mutable reference
    = note: BACKTRACE (of the first span):
    = note: inside `callee` at $DIR/arg_inplace_mutate.rs:LL:CC
 note: inside `main`
diff --git a/src/tools/miri/tests/fail/function_calls/arg_inplace_observe_during.tree.stderr b/src/tools/miri/tests/fail/function_calls/arg_inplace_observe_during.tree.stderr
index c33645bdd28..7b1846a32db 100644
--- a/src/tools/miri/tests/fail/function_calls/arg_inplace_observe_during.tree.stderr
+++ b/src/tools/miri/tests/fail/function_calls/arg_inplace_observe_during.tree.stderr
@@ -19,11 +19,17 @@ LL | |             let non_copy = S(42);
 LL | |
 LL | |     }
    | |_____^
-help: the protected tag <TAG> was created here, in the initial state Active
+help: the protected tag <TAG> was created here, in the initial state Reserved
   --> $DIR/arg_inplace_observe_during.rs:LL:CC
    |
 LL |     x.0 = 0;
    |     ^^^^^^^
+help: the protected tag <TAG> later transitioned to Active due to a child write access at offsets [0x0..0x4]
+  --> $DIR/arg_inplace_observe_during.rs:LL:CC
+   |
+LL |     x.0 = 0;
+   |     ^^^^^^^
+   = help: this transition corresponds to the first write to a 2-phase borrowed mutable reference
    = note: BACKTRACE (of the first span):
    = note: inside `change_arg` at $DIR/arg_inplace_observe_during.rs:LL:CC
 note: inside `main`
diff --git a/src/tools/miri/tests/fail/function_calls/return_pointer_aliasing.tree.stderr b/src/tools/miri/tests/fail/function_calls/return_pointer_aliasing.tree.stderr
index 66c2fb8db19..deafbf02077 100644
--- a/src/tools/miri/tests/fail/function_calls/return_pointer_aliasing.tree.stderr
+++ b/src/tools/miri/tests/fail/function_calls/return_pointer_aliasing.tree.stderr
@@ -19,11 +19,17 @@ LL | |             let ptr = &raw mut x;
 LL | |         }
 LL | |     }
    | |_____^
-help: the protected tag <TAG> was created here, in the initial state Active
+help: the protected tag <TAG> was created here, in the initial state Reserved
   --> $DIR/return_pointer_aliasing.rs:LL:CC
    |
 LL |     unsafe { ptr.read() };
    |     ^^^^^^^^^^^^^^^^^^^^^
+help: the protected tag <TAG> later transitioned to Active due to a child write access at offsets [0x0..0x4]
+  --> $DIR/return_pointer_aliasing.rs:LL:CC
+   |
+LL |     unsafe { ptr.read() };
+   |     ^^^^^^^^^^^^^^^^^^^^^
+   = help: this transition corresponds to the first write to a 2-phase borrowed mutable reference
    = note: BACKTRACE (of the first span):
    = note: inside `myfun` at $DIR/return_pointer_aliasing.rs:LL:CC
 note: inside `main`
diff --git a/src/tools/miri/tests/fail/function_calls/return_pointer_aliasing2.stderr b/src/tools/miri/tests/fail/function_calls/return_pointer_aliasing2.stderr
index 443ee8643fc..e1b40a6bc18 100644
--- a/src/tools/miri/tests/fail/function_calls/return_pointer_aliasing2.stderr
+++ b/src/tools/miri/tests/fail/function_calls/return_pointer_aliasing2.stderr
@@ -19,11 +19,17 @@ LL | |             let ptr = &raw mut _x;
 LL | |         }
 LL | |     }
    | |_____^
-help: the protected tag <TAG> was created here, in the initial state Active
+help: the protected tag <TAG> was created here, in the initial state Reserved
   --> $DIR/return_pointer_aliasing2.rs:LL:CC
    |
 LL |     unsafe { ptr.write(0) };
    |     ^^^^^^^^^^^^^^^^^^^^^^^
+help: the protected tag <TAG> later transitioned to Active due to a child write access at offsets [0x0..0x4]
+  --> $DIR/return_pointer_aliasing2.rs:LL:CC
+   |
+LL |     unsafe { ptr.write(0) };
+   |     ^^^^^^^^^^^^^^^^^^^^^^^
+   = help: this transition corresponds to the first write to a 2-phase borrowed mutable reference
    = note: BACKTRACE (of the first span):
    = note: inside `myfun` at $DIR/return_pointer_aliasing2.rs:LL:CC
 note: inside `main`