Track permissions on the byte-level

Co-authored-by: Ralf Jung <post@ralfj.de>
Co-authored-by: Johannes Hostert <jhostert@ethz.ch>

9 files changed, 329 insertions, 116 deletions

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 f3e32e75f2f..e1e35b43af7 100644
--- a/src/tools/miri/src/borrow_tracker/tree_borrows/mod.rs
+++ b/src/tools/miri/src/borrow_tracker/tree_borrows/mod.rs
@@ -3,6 +3,8 @@ use rustc_middle::mir::{Mutability, RetagKind};
 use rustc_middle::ty::layout::HasTypingEnv;
 use rustc_middle::ty::{self, Ty};
 
+use self::foreign_access_skipping::IdempotentForeignAccess;
+use self::tree::LocationState;
 use crate::borrow_tracker::{GlobalState, GlobalStateInner, ProtectorKind};
 use crate::concurrency::data_race::NaReadType;
 use crate::*;
@@ -113,16 +115,19 @@ impl<'tcx> Tree {
 
 /// Policy for a new borrow.
 #[derive(Debug, Clone, Copy)]
-struct NewPermission {
-    /// Which permission should the pointer start with.
-    initial_state: Permission,
+pub struct NewPermission {
+    /// Permission for the frozen part of the range.
+    freeze_perm: Permission,
+    /// Whether a read access should be performed on the frozen part on a retag.
+    freeze_access: bool,
+    /// Permission for the non-frozen part of the range.
+    nonfreeze_perm: Permission,
+    /// Whether a read access should be performed on the non-frozen
+    /// part on a retag.
+    nonfreeze_access: bool,
     /// Whether this pointer is part of the arguments of a function call.
     /// `protector` is `Some(_)` for all pointers marked `noalias`.
     protector: Option<ProtectorKind>,
-    /// Whether a read should be performed on a retag.  This should be `false`
-    /// for `Cell` because this could cause data races when using thread-safe
-    /// data types like `Mutex<T>`.
-    initial_read: bool,
 }
 
 impl<'tcx> NewPermission {
@@ -133,27 +138,42 @@ impl<'tcx> NewPermission {
         kind: RetagKind,
         cx: &crate::MiriInterpCx<'tcx>,
     ) -> Option<Self> {
-        let ty_is_freeze = pointee.is_freeze(*cx.tcx, cx.typing_env());
         let ty_is_unpin = pointee.is_unpin(*cx.tcx, cx.typing_env());
         let is_protected = kind == RetagKind::FnEntry;
-        // As demonstrated by `tests/fail/tree_borrows/reservedim_spurious_write.rs`,
-        // interior mutability and protectors interact poorly.
-        // To eliminate the case of Protected Reserved IM we override interior mutability
-        // in the case of a protected reference: protected references are always considered
-        // "freeze" in their reservation phase.
-        let (initial_state, initial_read) = match mutability {
+        let protector = is_protected.then_some(ProtectorKind::StrongProtector);
+
+        Some(match mutability {
             Mutability::Mut if ty_is_unpin =>
-                (Permission::new_reserved(ty_is_freeze, is_protected), true),
-            Mutability::Not if ty_is_freeze => (Permission::new_frozen(), true),
-            Mutability::Not if !ty_is_freeze => (Permission::new_cell(), false),
-            // Raw pointers never enter this function so they are not handled.
-            // However raw pointers are not the only pointers that take the parent
-            // tag, this also happens for `!Unpin` `&mut`s, which are excluded above.
+                NewPermission {
+                    freeze_perm: Permission::new_reserved(
+                        /* ty_is_freeze */ true,
+                        is_protected,
+                    ),
+                    freeze_access: true,
+                    nonfreeze_perm: Permission::new_reserved(
+                        /* ty_is_freeze */ false,
+                        is_protected,
+                    ),
+                    // If we have a mutable reference, then the non-frozen part will
+                    // have state `ReservedIM` or `Reserved`, which can have an initial read access
+                    // performed on it because you cannot have multiple mutable borrows.
+                    nonfreeze_access: true,
+                    protector,
+                },
+            Mutability::Not =>
+                NewPermission {
+                    freeze_perm: Permission::new_frozen(),
+                    freeze_access: true,
+                    nonfreeze_perm: Permission::new_cell(),
+                    // If it is a shared reference, then the non-frozen
+                    // part will have state `Cell`, which should not have an initial access,
+                    // as this can cause data races when using thread-safe data types like
+                    // `Mutex<T>`.
+                    nonfreeze_access: false,
+                    protector,
+                },
             _ => return None,
-        };
-
-        let protector = is_protected.then_some(ProtectorKind::StrongProtector);
-        Some(Self { initial_state, protector, initial_read })
+        })
     }
 
     /// Compute permission for `Box`-like type (`Box` always, and also `Unique` if enabled).
@@ -168,13 +188,17 @@ impl<'tcx> NewPermission {
         pointee.is_unpin(*cx.tcx, cx.typing_env()).then_some(()).map(|()| {
             // Regular `Unpin` box, give it `noalias` but only a weak protector
             // because it is valid to deallocate it within the function.
-            let ty_is_freeze = pointee.is_freeze(*cx.tcx, cx.typing_env());
-            let protected = kind == RetagKind::FnEntry;
-            let initial_state = Permission::new_reserved(ty_is_freeze, protected);
-            Self {
-                initial_state,
-                protector: protected.then_some(ProtectorKind::WeakProtector),
-                initial_read: true,
+            let is_protected = kind == RetagKind::FnEntry;
+            let protector = is_protected.then_some(ProtectorKind::WeakProtector);
+            NewPermission {
+                freeze_perm: Permission::new_reserved(/* ty_is_freeze */ true, is_protected),
+                freeze_access: true,
+                nonfreeze_perm: Permission::new_reserved(
+                    /* ty_is_freeze */ false,
+                    is_protected,
+                ),
+                nonfreeze_access: true,
+                protector,
             }
         })
     }
@@ -194,8 +218,6 @@ trait EvalContextPrivExt<'tcx>: crate::MiriInterpCxExt<'tcx> {
         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(place.ptr(), ptr_size, CheckInAllocMsg::Dereferenceable)?;
 
@@ -206,7 +228,13 @@ trait EvalContextPrivExt<'tcx>: crate::MiriInterpCxExt<'tcx> {
             let global = this.machine.borrow_tracker.as_ref().unwrap().borrow();
             let ty = place.layout.ty;
             if global.tracked_pointer_tags.contains(&new_tag) {
-                let kind_str = format!("initial state {} (pointee type {ty})", new_perm.initial_state);
+                 let ty_is_freeze = ty.is_freeze(*this.tcx, this.typing_env());
+                 let kind_str =
+                     if ty_is_freeze {
+                         format!("initial state {} (pointee type {ty})", new_perm.freeze_perm)
+                     } else {
+                         format!("initial state {}/{} outside/inside UnsafeCell (pointee type {ty})", new_perm.freeze_perm, new_perm.nonfreeze_perm)
+                     };
                 this.emit_diagnostic(NonHaltingDiagnostic::CreatedPointerTag(
                     new_tag.inner(),
                     Some(kind_str),
@@ -285,43 +313,103 @@ trait EvalContextPrivExt<'tcx>: crate::MiriInterpCxExt<'tcx> {
 
         let span = this.machine.current_span();
         let alloc_extra = this.get_alloc_extra(alloc_id)?;
-        let range = alloc_range(base_offset, ptr_size);
         let mut tree_borrows = alloc_extra.borrow_tracker_tb().borrow_mut();
 
-        // All reborrows incur a (possibly zero-sized) read access to the parent
-        if new_perm.initial_read {
-            tree_borrows.perform_access(
-                orig_tag,
-                Some((range, AccessKind::Read, diagnostics::AccessCause::Reborrow)),
-                this.machine.borrow_tracker.as_ref().unwrap(),
-                alloc_id,
-                this.machine.current_span(),
-            )?;
-        }
+        // Store initial permissions and their corresponding range.
+        let mut perms_map: RangeMap<LocationState> = RangeMap::new(
+            ptr_size,
+            LocationState::new_init(Permission::new_disabled(), IdempotentForeignAccess::None), // this will be overwritten
+        );
+        // Keep track of whether the node has any part that allows for interior mutability.
+        // FIXME: This misses `PhantomData<UnsafeCell<T>>` which could be considered a marker
+        // for requesting interior mutability.
+        let mut has_unsafe_cell = false;
+
+        // When adding a new node, the SIFA of its parents needs to be updated, potentially across
+        // the entire memory range. For the parts that are being accessed below, the access itself
+        // trivially takes care of that. However, we have to do some more work to also deal with
+        // the parts that are not being accessed. Specifically what we do is that we
+        // call `update_last_accessed_after_retag` on the SIFA of the permission set for the part of
+        // memory outside `perm_map` -- so that part is definitely taken care of. The remaining concern
+        // is the part of memory that is in the range of `perms_map`, but not accessed below.
+        // There we have two cases:
+        // * If we do have an `UnsafeCell` (`has_unsafe_cell` becomes true), then the non-accessed part
+        //   uses `nonfreeze_perm`, so the `nonfreeze_perm` initialized parts are also fine. We enforce
+        //   the `freeze_perm` parts to be accessed, and thus everything is taken care of.
+        // * If there is no `UnsafeCell`, then `freeze_perm` is used everywhere (both inside and outside the initial range),
+        //   and we update everything to have the `freeze_perm`'s SIFA, so there are no issues. (And this assert below is not
+        //   actually needed in this case).
+        assert!(new_perm.freeze_access);
+
+        let protected = new_perm.protector.is_some();
+        this.visit_freeze_sensitive(place, ptr_size, |range, frozen| {
+            has_unsafe_cell = has_unsafe_cell || !frozen;
+
+            // We are only ever `Frozen` inside the frozen bits.
+            let (perm, access) = if frozen {
+                (new_perm.freeze_perm, new_perm.freeze_access)
+            } else {
+                (new_perm.nonfreeze_perm, new_perm.nonfreeze_access)
+            };
+
+            // Store initial permissions.
+            for (_loc_range, loc) in perms_map.iter_mut(range.start, range.size) {
+                let sifa = perm.strongest_idempotent_foreign_access(protected);
+                // NOTE: Currently, `access` is false if and only if `perm` is Cell, so this `if`
+                // doesn't not change whether any code is UB or not. We could just always use
+                // `new_init` and everything would stay the same. But that seems conceptually
+                // odd, so we keep the initial "accessed" bit of the `LocationState` in sync with whether
+                // a read access is performed below.
+                if access {
+                    *loc = LocationState::new_init(perm, sifa);
+                } else {
+                    *loc = LocationState::new_uninit(perm, sifa);
+                }
+            }
+
+            // Some reborrows incur a read access to the parent.
+            if access {
+                // Adjust range to be relative to allocation start (rather than to `place`).
+                let mut range_in_alloc = range;
+                range_in_alloc.start += base_offset;
+
+                tree_borrows.perform_access(
+                    orig_tag,
+                    Some((range_in_alloc, AccessKind::Read, diagnostics::AccessCause::Reborrow)),
+                    this.machine.borrow_tracker.as_ref().unwrap(),
+                    alloc_id,
+                    this.machine.current_span(),
+                )?;
+
+                // Also inform the data race model (but only if any bytes are actually affected).
+                if range.size.bytes() > 0 {
+                    if let Some(data_race) = alloc_extra.data_race.as_vclocks_ref() {
+                        data_race.read(
+                            alloc_id,
+                            range_in_alloc,
+                            NaReadType::Retag,
+                            Some(place.layout.ty),
+                            &this.machine,
+                        )?
+                    }
+                }
+            }
+            interp_ok(())
+        })?;
+
         // Record the parent-child pair in the tree.
         tree_borrows.new_child(
+            base_offset,
             orig_tag,
             new_tag,
-            new_perm.initial_state,
-            range,
+            perms_map,
+            // Allow lazily writing to surrounding data if we found an `UnsafeCell`.
+            if has_unsafe_cell { new_perm.nonfreeze_perm } else { new_perm.freeze_perm },
+            protected,
             span,
-            new_perm.protector.is_some(),
         )?;
         drop(tree_borrows);
 
-        // Also inform the data race model (but only if any bytes are actually affected).
-        if range.size.bytes() > 0 && new_perm.initial_read {
-            if let Some(data_race) = alloc_extra.data_race.as_vclocks_ref() {
-                data_race.read(
-                    alloc_id,
-                    range,
-                    NaReadType::Retag,
-                    Some(place.layout.ty),
-                    &this.machine,
-                )?;
-            }
-        }
-
         interp_ok(Some(Provenance::Concrete { alloc_id, tag: new_tag }))
     }
 
@@ -508,15 +596,21 @@ pub trait EvalContextExt<'tcx>: crate::MiriInterpCxExt<'tcx> {
     fn tb_protect_place(&mut self, place: &MPlaceTy<'tcx>) -> InterpResult<'tcx, MPlaceTy<'tcx>> {
         let this = self.eval_context_mut();
 
-        // Note: if we were to inline `new_reserved` below we would find out that
-        // `ty_is_freeze` is eventually unused because it appears in a `ty_is_freeze || true`.
-        // We are nevertheless including it here for clarity.
-        let ty_is_freeze = place.layout.ty.is_freeze(*this.tcx, this.typing_env());
         // Retag it. With protection! That is the entire point.
         let new_perm = NewPermission {
-            initial_state: Permission::new_reserved(ty_is_freeze, /* protected */ true),
+            // Note: If we are creating a protected Reserved, which can
+            // never be ReservedIM, the value of the `ty_is_freeze`
+            // argument doesn't matter
+            // (`ty_is_freeze || true` in `new_reserved` will always be `true`).
+            freeze_perm: Permission::new_reserved(
+                /* ty_is_freeze */ true, /* protected */ true,
+            ),
+            freeze_access: true,
+            nonfreeze_perm: Permission::new_reserved(
+                /* ty_is_freeze */ false, /* protected */ true,
+            ),
+            nonfreeze_access: true,
             protector: Some(ProtectorKind::StrongProtector),
-            initial_read: true,
         };
         this.tb_retag_place(place, new_perm)
     }
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 087f6fc3f24..38863ca0734 100644
--- a/src/tools/miri/src/borrow_tracker/tree_borrows/perms.rs
+++ b/src/tools/miri/src/borrow_tracker/tree_borrows/perms.rs
@@ -94,6 +94,7 @@ impl PermissionPriv {
     }
 
     /// Reject `ReservedIM` that cannot exist in the presence of a protector.
+    #[cfg(test)]
     fn compatible_with_protector(&self) -> bool {
         // FIXME(TB-Cell): It is unclear what to do here.
         // `Cell` will occur with a protector but won't provide the guarantees
@@ -253,10 +254,6 @@ impl Permission {
     pub fn is_disabled(&self) -> bool {
         self.inner == Disabled
     }
-    /// Check if `self` is the post-child-write state of a pointer (is `Active`).
-    pub fn is_active(&self) -> bool {
-        self.inner == Active
-    }
     /// Check if `self` is the never-allow-writes-again state of a pointer (is `Frozen`).
     pub fn is_frozen(&self) -> bool {
         self.inner == Frozen
@@ -289,6 +286,11 @@ impl Permission {
     /// is a protector is relevant because being protected takes priority over being
     /// interior mutable)
     pub fn new_reserved(ty_is_freeze: bool, protected: bool) -> Self {
+        // As demonstrated by `tests/fail/tree_borrows/reservedim_spurious_write.rs`,
+        // interior mutability and protectors interact poorly.
+        // To eliminate the case of Protected Reserved IM we override interior mutability
+        // in the case of a protected reference: protected references are always considered
+        // "freeze" in their reservation phase.
         if ty_is_freeze || protected { Self::new_reserved_frz() } else { Self::new_reserved_im() }
     }
 
@@ -309,6 +311,7 @@ impl Permission {
     }
 
     /// Reject `ReservedIM` that cannot exist in the presence of a protector.
+    #[cfg(test)]
     pub fn compatible_with_protector(&self) -> bool {
         self.inner.compatible_with_protector()
     }
@@ -393,11 +396,6 @@ impl PermTransition {
         self.from <= self.to
     }
 
-    pub fn from(from: Permission, to: Permission) -> Option<Self> {
-        let t = Self { from: from.inner, to: to.inner };
-        t.is_possible().then_some(t)
-    }
-
     pub fn is_noop(self) -> bool {
         self.from == self.to
     }
@@ -407,11 +405,6 @@ impl PermTransition {
         (starting_point.inner == self.from).then_some(Permission { inner: self.to })
     }
 
-    /// Extract starting point of a transition
-    pub fn started(self) -> Permission {
-        Permission { inner: self.from }
-    }
-
     /// Determines if this transition would disable the permission.
     pub fn produces_disabled(self) -> bool {
         self.to == Disabled
diff --git a/src/tools/miri/src/borrow_tracker/tree_borrows/tree.rs b/src/tools/miri/src/borrow_tracker/tree_borrows/tree.rs
index 47ccaadbb9e..0a35a70c2e3 100644
--- a/src/tools/miri/src/borrow_tracker/tree_borrows/tree.rs
+++ b/src/tools/miri/src/borrow_tracker/tree_borrows/tree.rs
@@ -10,6 +10,7 @@
 //!   and the relative position of the access;
 //! - idempotency properties asserted in `perms.rs` (for optimizations)
 
+use std::ops::Range;
 use std::{fmt, mem};
 
 use rustc_abi::Size;
@@ -58,7 +59,7 @@ impl LocationState {
     /// to any foreign access yet.
     /// The permission is not allowed to be `Active`.
     /// `sifa` is the (strongest) idempotent foreign access, see `foreign_access_skipping.rs`
-    fn new_uninit(permission: Permission, sifa: IdempotentForeignAccess) -> Self {
+    pub fn new_uninit(permission: Permission, sifa: IdempotentForeignAccess) -> Self {
         assert!(permission.is_initial() || permission.is_disabled());
         Self { permission, initialized: false, idempotent_foreign_access: sifa }
     }
@@ -66,7 +67,7 @@ impl LocationState {
     /// Constructs a new initial state. It has not yet been subjected
     /// to any foreign access. However, it is already marked as having been accessed.
     /// `sifa` is the (strongest) idempotent foreign access, see `foreign_access_skipping.rs`
-    fn new_init(permission: Permission, sifa: IdempotentForeignAccess) -> Self {
+    pub fn new_init(permission: Permission, sifa: IdempotentForeignAccess) -> Self {
         Self { permission, initialized: true, idempotent_foreign_access: sifa }
     }
 
@@ -612,20 +613,32 @@ impl Tree {
 }
 
 impl<'tcx> Tree {
-    /// Insert a new tag in the tree
-    pub fn new_child(
+    /// Insert a new tag in the tree.
+    ///
+    /// `initial_perms` defines the initial permissions for the part of memory
+    /// that is already considered "initialized" immediately. The ranges in this
+    /// map are relative to `base_offset`.
+    /// `default_perm` defines the initial permission for the rest of the allocation.
+    ///
+    /// For all non-accessed locations in the RangeMap (those that haven't had an
+    /// implicit read), their SIFA must be weaker than or as weak as the SIFA of
+    /// `default_perm`.
+    pub(super) fn new_child(
         &mut self,
+        base_offset: Size,
         parent_tag: BorTag,
         new_tag: BorTag,
-        default_initial_perm: Permission,
-        reborrow_range: AllocRange,
+        initial_perms: RangeMap<LocationState>,
+        default_perm: Permission,
+        protected: bool,
         span: Span,
-        prot: bool,
     ) -> InterpResult<'tcx> {
-        assert!(!self.tag_mapping.contains_key(&new_tag));
         let idx = self.tag_mapping.insert(new_tag);
         let parent_idx = self.tag_mapping.get(&parent_tag).unwrap();
-        let strongest_idempotent = default_initial_perm.strongest_idempotent_foreign_access(prot);
+        assert!(default_perm.is_initial());
+
+        let default_strongest_idempotent =
+            default_perm.strongest_idempotent_foreign_access(protected);
         // Create the node
         self.nodes.insert(
             idx,
@@ -633,25 +646,36 @@ impl<'tcx> Tree {
                 tag: new_tag,
                 parent: Some(parent_idx),
                 children: SmallVec::default(),
-                default_initial_perm,
-                default_initial_idempotent_foreign_access: strongest_idempotent,
-                debug_info: NodeDebugInfo::new(new_tag, default_initial_perm, span),
+                default_initial_perm: default_perm,
+                default_initial_idempotent_foreign_access: default_strongest_idempotent,
+                debug_info: NodeDebugInfo::new(new_tag, default_perm, span),
             },
         );
         // Register new_tag as a child of parent_tag
         self.nodes.get_mut(parent_idx).unwrap().children.push(idx);
-        // Initialize perms
-        let perm = LocationState::new_init(default_initial_perm, strongest_idempotent);
-        for (_perms_range, perms) in self.rperms.iter_mut(reborrow_range.start, reborrow_range.size)
+
+        for (Range { start, end }, &perm) in
+            initial_perms.iter(Size::from_bytes(0), initial_perms.size())
         {
-            perms.insert(idx, perm);
+            assert!(perm.is_initial());
+            for (_perms_range, perms) in self
+                .rperms
+                .iter_mut(Size::from_bytes(start) + base_offset, Size::from_bytes(end - start))
+            {
+                assert!(
+                    default_strongest_idempotent
+                        >= perm.permission.strongest_idempotent_foreign_access(protected)
+                );
+                perms.insert(idx, perm);
+            }
         }
 
         // Inserting the new perms might have broken the SIFA invariant (see `foreign_access_skipping.rs`).
         // We now weaken the recorded SIFA for our parents, until the invariant is restored.
         // We could weaken them all to `LocalAccess`, but it is more efficient to compute the SIFA
         // for the new permission statically, and use that.
-        self.update_last_accessed_after_retag(parent_idx, strongest_idempotent);
+        // See the comment in `tb_reborrow` for why it is correct to use the SIFA of `default_uninit_perm`.
+        self.update_last_accessed_after_retag(parent_idx, default_strongest_idempotent);
 
         interp_ok(())
     }
@@ -1073,15 +1097,4 @@ impl AccessRelatedness {
     pub fn is_foreign(self) -> bool {
         matches!(self, AccessRelatedness::AncestorAccess | AccessRelatedness::CousinAccess)
     }
-
-    /// Given the AccessRelatedness for the parent node, compute the AccessRelatedness
-    /// for the child node. This function assumes that we propagate away from the initial
-    /// access.
-    pub fn for_child(self) -> Self {
-        use AccessRelatedness::*;
-        match self {
-            AncestorAccess | This => AncestorAccess,
-            StrictChildAccess | CousinAccess => CousinAccess,
-        }
-    }
 }
diff --git a/src/tools/miri/src/range_map.rs b/src/tools/miri/src/range_map.rs
index 2c2484cd0bc..29a5a8537a4 100644
--- a/src/tools/miri/src/range_map.rs
+++ b/src/tools/miri/src/range_map.rs
@@ -31,6 +31,11 @@ impl<T> RangeMap<T> {
         RangeMap { v }
     }
 
+    pub fn size(&self) -> Size {
+        let size = self.v.last().map(|x| x.range.end).unwrap_or(0);
+        Size::from_bytes(size)
+    }
+
     /// Finds the index containing the given offset.
     fn find_offset(&self, offset: u64) -> usize {
         self.v
@@ -71,10 +76,7 @@ impl<T> RangeMap<T> {
         };
         // The first offset that is not included any more.
         let end = offset + len;
-        assert!(
-            end <= self.v.last().unwrap().range.end,
-            "iterating beyond the bounds of this RangeMap"
-        );
+        assert!(end <= self.size().bytes(), "iterating beyond the bounds of this RangeMap");
         slice
             .iter()
             .take_while(move |elem| elem.range.start < end)
@@ -327,4 +329,16 @@ mod tests {
         let map = RangeMap::<i32>::new(Size::from_bytes(20), -1);
         let _ = map.iter(Size::from_bytes(11), Size::from_bytes(11));
     }
+
+    #[test]
+    fn empty_map_iter() {
+        let map = RangeMap::<i32>::new(Size::from_bytes(0), -1);
+        let _ = map.iter(Size::from_bytes(0), Size::from_bytes(0));
+    }
+
+    #[test]
+    fn empty_map_iter_mut() {
+        let mut map = RangeMap::<i32>::new(Size::from_bytes(0), -1);
+        let _ = map.iter_mut(Size::from_bytes(0), Size::from_bytes(0));
+    }
 }
diff --git a/src/tools/miri/tests/fail/tree_borrows/cell-inside-struct.rs b/src/tools/miri/tests/fail/tree_borrows/cell-inside-struct.rs
new file mode 100644
index 00000000000..ff797877682
--- /dev/null
+++ b/src/tools/miri/tests/fail/tree_borrows/cell-inside-struct.rs
@@ -0,0 +1,33 @@
+//! A version of `cell_inside_struct` that dumps the tree so that we can see what is happening.
+//@compile-flags: -Zmiri-tree-borrows
+#[path = "../../utils/mod.rs"]
+#[macro_use]
+mod utils;
+
+use std::cell::Cell;
+
+struct Foo {
+    field1: u32,
+    field2: Cell<u32>,
+}
+
+pub fn main() {
+    let root = Foo { field1: 42, field2: Cell::new(88) };
+    unsafe {
+        let a = &root;
+
+        name!(a as *const Foo, "a");
+
+        let a: *const Foo = a as *const Foo;
+        let a: *mut Foo = a as *mut Foo;
+
+        let alloc_id = alloc_id!(a);
+        print_state!(alloc_id);
+
+        // Writing to `field2`, which is interior mutable, should be allowed.
+        (*a).field2.set(10);
+
+        // Writing to `field1`, which is frozen, should not be allowed.
+        (*a).field1 = 88; //~ ERROR: /write access through .* is forbidden/
+    }
+}
diff --git a/src/tools/miri/tests/fail/tree_borrows/cell-inside-struct.stderr b/src/tools/miri/tests/fail/tree_borrows/cell-inside-struct.stderr
new file mode 100644
index 00000000000..717f1419452
--- /dev/null
+++ b/src/tools/miri/tests/fail/tree_borrows/cell-inside-struct.stderr
@@ -0,0 +1,26 @@
+──────────────────────────────────────────────────
+Warning: this tree is indicative only. Some tags may have been hidden.
+0..   4..   8
+| Act | Act |    └─┬──<TAG=root of the allocation>
+| Frz |?Cel |      └────<TAG=a>
+──────────────────────────────────────────────────
+error: Undefined Behavior: write access through <TAG> (a) at ALLOC[0x0] is forbidden
+  --> tests/fail/tree_borrows/cell-inside-struct.rs:LL:CC
+   |
+LL |         (*a).field1 = 88;
+   |         ^^^^^^^^^^^^^^^^ write access through <TAG> (a) at ALLOC[0x0] is forbidden
+   |
+   = help: this indicates a potential bug in the program: it performed an invalid operation, but the Tree Borrows rules it violated are still experimental
+   = help: the accessed tag <TAG> (a) has state Frozen which forbids this child write access
+help: the accessed tag <TAG> was created here, in the initial state Cell
+  --> tests/fail/tree_borrows/cell-inside-struct.rs:LL:CC
+   |
+LL |         let a = &root;
+   |                 ^^^^^
+   = note: BACKTRACE (of the first span):
+   = note: inside `main` at tests/fail/tree_borrows/cell-inside-struct.rs:LL:CC
+
+note: some details are omitted, run with `MIRIFLAGS=-Zmiri-backtrace=full` for a verbose backtrace
+
+error: aborting due to 1 previous error
+
diff --git a/src/tools/miri/tests/pass/both_borrows/basic_aliasing_model.rs b/src/tools/miri/tests/pass/both_borrows/basic_aliasing_model.rs
index c2b6a7e68be..c06dba6252e 100644
--- a/src/tools/miri/tests/pass/both_borrows/basic_aliasing_model.rs
+++ b/src/tools/miri/tests/pass/both_borrows/basic_aliasing_model.rs
@@ -1,6 +1,7 @@
 //@revisions: stack tree
 //@[tree]compile-flags: -Zmiri-tree-borrows
 #![feature(allocator_api)]
+use std::cell::Cell;
 use std::ptr;
 
 // Test various aliasing-model-related things.
@@ -23,6 +24,7 @@ fn main() {
     not_unpin_not_protected();
     write_does_not_invalidate_all_aliases();
     box_into_raw_allows_interior_mutable_alias();
+    cell_inside_struct()
 }
 
 // Make sure that reading from an `&mut` does, like reborrowing to `&`,
@@ -260,7 +262,7 @@ fn write_does_not_invalidate_all_aliases() {
 
 fn box_into_raw_allows_interior_mutable_alias() {
     unsafe {
-        let b = Box::new(std::cell::Cell::new(42));
+        let b = Box::new(Cell::new(42));
         let raw = Box::into_raw(b);
         let c = &*raw;
         let d = raw.cast::<i32>(); // bypassing `Cell` -- only okay in Miri tests
@@ -270,3 +272,19 @@ fn box_into_raw_allows_interior_mutable_alias() {
         drop(Box::from_raw(raw));
     }
 }
+
+fn cell_inside_struct() {
+    struct Foo {
+        field1: u32,
+        field2: Cell<u32>,
+    }
+
+    let mut root = Foo { field1: 42, field2: Cell::new(88) };
+    let a = &mut root;
+
+    // Writing to `field2`, which is interior mutable, should be allowed.
+    (*a).field2.set(10);
+
+    // Writing to `field1`, which is reserved, should also be allowed.
+    (*a).field1 = 88;
+}
diff --git a/src/tools/miri/tests/pass/tree_borrows/cell-alternate-writes.stderr b/src/tools/miri/tests/pass/tree_borrows/cell-alternate-writes.stderr
index 75a30c9a083..e09aed2cf5d 100644
--- a/src/tools/miri/tests/pass/tree_borrows/cell-alternate-writes.stderr
+++ b/src/tools/miri/tests/pass/tree_borrows/cell-alternate-writes.stderr
@@ -3,8 +3,8 @@ Warning: this tree is indicative only. Some tags may have been hidden.
 0..   1
 | Act |    └─┬──<TAG=root of the allocation>
 | ReIM|      └─┬──<TAG=data>
-| Cel |        ├────<TAG=x>
-| Cel |        └────<TAG=y>
+|?Cel |        ├────<TAG=x>
+|?Cel |        └────<TAG=y>
 ──────────────────────────────────────────────────
 ──────────────────────────────────────────────────
 Warning: this tree is indicative only. Some tags may have been hidden.
diff --git a/src/tools/miri/tests/pass/tree_borrows/cell-lazy-write-to-surrounding.rs b/src/tools/miri/tests/pass/tree_borrows/cell-lazy-write-to-surrounding.rs
new file mode 100644
index 00000000000..abe08f2cd22
--- /dev/null
+++ b/src/tools/miri/tests/pass/tree_borrows/cell-lazy-write-to-surrounding.rs
@@ -0,0 +1,22 @@
+//@compile-flags: -Zmiri-tree-borrows
+
+use std::cell::Cell;
+
+fn foo(x: &Cell<i32>) {
+    unsafe {
+        let ptr = x as *const Cell<i32> as *mut Cell<i32> as *mut i32;
+        ptr.offset(1).write(0);
+    }
+}
+
+fn main() {
+    let arr = [Cell::new(1), Cell::new(1)];
+    foo(&arr[0]);
+
+    let pair = (Cell::new(1), 1);
+    // TODO: Ideally, this would result in UB since the second element
+    // in `pair` is Frozen.  We would need some way to express a
+    // "shared reference with permission to access surrounding
+    // interior mutable data".
+    foo(&pair.0);
+}