src/stacked_borrows.rs

   1 use std::cell::RefCell;
   2 use std::collections::HashSet;
   3 use std::rc::Rc;
   4 use std::fmt;
   5 use std::num::NonZeroU64;
   6
   7 use rustc::ty::{self, layout::Size};
   8 use rustc::hir::{MutMutable, MutImmutable};
   9 use rustc::mir::RetagKind;
  10
  11 use crate::{
  12     EvalResult, InterpError, MiriEvalContext, HelpersEvalContextExt, Evaluator, MutValueVisitor,
  13     MemoryKind, MiriMemoryKind, RangeMap, Allocation, AllocationExtra,
  14     Pointer, Immediate, ImmTy, PlaceTy, MPlaceTy,
  15 };
  16
  17 pub type PtrId = NonZeroU64;
  18 pub type CallId = u64;
  19
  20 /// Tracking pointer provenance
  21 #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
  22 pub enum Tag {
  23     Tagged(PtrId),
  24     Untagged,
  25 }
  26
  27 impl fmt::Display for Tag {
  28     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  29         match self {
  30             Tag::Tagged(id) => write!(f, "{}", id),
  31             Tag::Untagged => write!(f, "<untagged>"),
  32         }
  33     }
  34 }
  35
  36 /// Indicates which permission is granted (by this item to some pointers)
  37 #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
  38 pub enum Permission {
  39     /// Grants unique mutable access.
  40     Unique,
  41     /// Grants shared mutable access.
  42     SharedReadWrite,
  43     /// Greants shared read-only access.
  44     SharedReadOnly,
  45 }
  46
  47 /// An item in the per-location borrow stack.
  48 #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
  49 pub enum Item {
  50     /// Grants the given permission for pointers with this tag.
  51     Permission(Permission, Tag),
  52     /// A barrier, tracking the function it belongs to by its index on the call stack.
  53     FnBarrier(CallId),
  54 }
  55
  56 impl fmt::Display for Item {
  57     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  58         match self {
  59             Item::Permission(perm, tag) => write!(f, "[{:?} for {}]", perm, tag),
  60             Item::FnBarrier(call) => write!(f, "[barrier {}]", call),
  61         }
  62     }
  63 }
  64
  65 /// Extra per-location state.
  66 #[derive(Clone, Debug, PartialEq, Eq)]
  67 pub struct Stack {
  68     /// Used *mostly* as a stack; never empty.
  69     /// We sometimes push into the middle but never remove from the middle.
  70     /// The same tag may occur multiple times, e.g. from a two-phase borrow.
  71     /// Invariants:
  72     /// * Above a `SharedReadOnly` there can only be barriers and more `SharedReadOnly`.
  73     borrows: Vec<Item>,
  74 }
  75
  76
  77 /// Extra per-allocation state.
  78 #[derive(Clone, Debug)]
  79 pub struct Stacks {
  80     // Even reading memory can have effects on the stack, so we need a `RefCell` here.
  81     stacks: RefCell<RangeMap<Stack>>,
  82     // Pointer to global state
  83     global: MemoryState,
  84 }
  85
  86 /// Extra global state, available to the memory access hooks.
  87 #[derive(Debug)]
  88 pub struct GlobalState {
  89     next_ptr_id: PtrId,
  90     next_call_id: CallId,
  91     active_calls: HashSet<CallId>,
  92 }
  93 pub type MemoryState = Rc<RefCell<GlobalState>>;
  94
  95 /// Indicates which kind of access is being performed.
  96 #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
  97 pub enum AccessKind {
  98     Read,
  99     Write,
 100 }
 101
 102 impl fmt::Display for AccessKind {
 103     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 104         match self {
 105             AccessKind::Read => write!(f, "read"),
 106             AccessKind::Write => write!(f, "write"),
 107         }
 108     }
 109 }
 110
 111 /// Indicates which kind of reference is being created.
 112 /// Used by high-level `reborrow` to compute which permissions to grant to the
 113 /// new pointer.
 114 #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
 115 pub enum RefKind {
 116     /// `&mut` and `Box`.
 117     Unique,
 118     /// `&` with or without interior mutability.
 119     Shared,
 120     /// `*mut`/`*const` (raw pointers).
 121     Raw { mutable: bool },
 122 }
 123
 124 impl fmt::Display for RefKind {
 125     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 126         match self {
 127             RefKind::Unique => write!(f, "unique"),
 128             RefKind::Shared => write!(f, "shared"),
 129             RefKind::Raw { mutable: true } => write!(f, "raw (mutable)"),
 130             RefKind::Raw { mutable: false } => write!(f, "raw (constant)"),
 131         }
 132     }
 133 }
 134
 135 /// Utilities for initialization and ID generation
 136 impl Default for GlobalState {
 137     fn default() -> Self {
 138         GlobalState {
 139             next_ptr_id: NonZeroU64::new(1).unwrap(),
 140             next_call_id: 0,
 141             active_calls: HashSet::default(),
 142         }
 143     }
 144 }
 145
 146 impl GlobalState {
 147     pub fn new_ptr(&mut self) -> PtrId {
 148         let id = self.next_ptr_id;
 149         self.next_ptr_id = NonZeroU64::new(id.get() + 1).unwrap();
 150         id
 151     }
 152
 153     pub fn new_call(&mut self) -> CallId {
 154         let id = self.next_call_id;
 155         trace!("new_call: Assigning ID {}", id);
 156         self.active_calls.insert(id);
 157         self.next_call_id = id+1;
 158         id
 159     }
 160
 161     pub fn end_call(&mut self, id: CallId) {
 162         assert!(self.active_calls.remove(&id));
 163     }
 164
 165     fn is_active(&self, id: CallId) -> bool {
 166         self.active_calls.contains(&id)
 167     }
 168 }
 169
 170 // # Stacked Borrows Core Begin
 171
 172 /// We need to make at least the following things true:
 173 ///
 174 /// U1: After creating a `Uniq`, it is at the top.
 175 /// U2: If the top is `Uniq`, accesses must be through that `Uniq` or remove it it.
 176 /// U3: If an access happens with a `Uniq`, it requires the `Uniq` to be in the stack.
 177 ///
 178 /// F1: After creating a `&`, the parts outside `UnsafeCell` have our `SharedReadOnly` on top.
 179 /// F2: If a write access happens, it pops the `SharedReadOnly`.  This has three pieces:
 180 ///     F2a: If a write happens granted by an item below our `SharedReadOnly`, the `SharedReadOnly`
 181 ///          gets popped.
 182 ///     F2b: No `SharedReadWrite` or `Unique` will ever be added on top of our `SharedReadOnly`.
 183 /// F3: If an access happens with an `&` outside `UnsafeCell`,
 184 ///     it requires the `SharedReadOnly` to still be in the stack.
 185
 186 impl Default for Tag {
 187     #[inline(always)]
 188     fn default() -> Tag {
 189         Tag::Untagged
 190     }
 191 }
 192
 193 /// Core relations on `Permission` define which accesses are allowed:
 194 /// On every access, we try to find a *granting* item, and then we remove all
 195 /// *incompatible* items above it.
 196 impl Permission {
 197     /// This defines for a given permission, whether it permits the given kind of access.
 198     fn grants(self, access: AccessKind) -> bool {
 199         match (self, access) {
 200             // Unique and SharedReadWrite allow any kind of access.
 201             (Permission::Unique, _) |
 202             (Permission::SharedReadWrite, _) =>
 203                 true,
 204             // SharedReadOnly only permits read access.
 205             (Permission::SharedReadOnly, AccessKind::Read) =>
 206                 true,
 207             (Permission::SharedReadOnly, AccessKind::Write) =>
 208                 false,
 209         }
 210     }
 211
 212     /// This defines for a given permission, which other permissions it can tolerate "above" itself
 213     /// for which kinds of accesses.
 214     /// If true, then `other` is allowed to remain on top of `self` when `access` happens.
 215     fn compatible_with(self, access: AccessKind, other: Permission) -> bool {
 216         use self::Permission::*;
 217
 218         match (self, access, other) {
 219             // Some cases are impossible.
 220             (SharedReadOnly, _, SharedReadWrite) |
 221             (SharedReadOnly, _, Unique) =>
 222                 bug!("There can never be a SharedReadWrite or a Unique on top of a SharedReadOnly"),
 223             // When `other` is `SharedReadOnly`, that is NEVER compatible with
 224             // write accesses.
 225             // This makes sure read-only pointers become invalid on write accesses (ensures F2a).
 226             (_, AccessKind::Write, SharedReadOnly) =>
 227                 false,
 228             // When `other` is `Unique`, that is compatible with nothing.
 229             // This makes sure unique pointers become invalid on incompatible accesses (ensures U2).
 230             (_, _, Unique) =>
 231                 false,
 232             // When we are unique and this is a write/dealloc, we tolerate nothing.
 233             // This makes sure we re-assert uniqueness ("being on top") on write accesses.
 234             // (This is particularily important such that when a new mutable ref gets created, it gets
 235             // pushed into the right item -- this behaves like a write and we assert uniqueness of the
 236             // pointer from which this comes, *if* it was a unique pointer.)
 237             (Unique, AccessKind::Write, _) =>
 238                 false,
 239             // `SharedReadWrite` items can tolerate any other akin items for any kind of access.
 240             (SharedReadWrite, _, SharedReadWrite) =>
 241                 true,
 242             // Any item can tolerate read accesses for shared items.
 243             // This includes unique items!  Reads from unique pointers do not invalidate
 244             // other pointers.
 245             (_, AccessKind::Read, SharedReadWrite) |
 246             (_, AccessKind::Read, SharedReadOnly) =>
 247                 true,
 248             // That's it.
 249         }
 250     }
 251 }
 252
 253 /// Core per-location operations: access, dealloc, reborrow.
 254 impl<'tcx> Stack {
 255     /// Find the item granting the given kind of access to the given tag, and where that item is in the stack.
 256     fn find_granting(&self, access: AccessKind, tag: Tag) -> Option<(usize, Permission)> {
 257         self.borrows.iter()
 258             .enumerate() // we also need to know *where* in the stack
 259             .rev() // search top-to-bottom
 260             // Return permission of first item that grants access.
 261             // We require a permission with the right tag, ensuring U3 and F3.
 262             .filter_map(|(idx, item)| match item {
 263                 &Item::Permission(perm, item_tag) if perm.grants(access) && tag == item_tag =>
 264                     Some((idx, perm)),
 265                 _ => None,
 266             })
 267             .next()
 268     }
 269
 270     /// Test if a memory `access` using pointer tagged `tag` is granted.
 271     /// If yes, return the index of the item that granted it.
 272     fn access(
 273         &mut self,
 274         access: AccessKind,
 275         tag: Tag,
 276         global: &GlobalState,
 277     ) -> EvalResult<'tcx, usize> {
 278         // Two main steps: Find granting item, remove all incompatible items above.
 279         // The second step is where barriers get implemented: they "protect" the items
 280         // below them, meaning that if we remove an item and then further up encounter a barrier,
 281         // we raise an error.
 282
 283         // Step 1: Find granting item.
 284         let (granting_idx, granting_perm) = self.find_granting(access, tag)
 285             .ok_or_else(|| InterpError::MachineError(format!(
 286                     "no item granting {} access to tag {} found in borrow stack",
 287                     access, tag,
 288             )))?;
 289
 290         // Step 2: Remove everything incompatible above them.
 291         // Items below an active barrier however may not be removed, so we check that as well.
 292         // We do *not* maintain a stack discipline here.  We could, in principle, decide to only
 293         // keep the items immediately above `granting_idx` that are compatible, and then pop the rest.
 294         // However, that kills off entire "branches" of pointer derivation too easily:
 295         // in `let raw = &mut *x as *mut _; let _val = *x;`, the second statement would pop the `Unique`
 296         // from the reborrow of the first statement, and subequently also pop the `SharedReadWrite` for `raw`.
 297         {
 298             // Implemented with indices because there does not seem to be a nice iterator and range-based
 299             // API for this.
 300             let mut cur = granting_idx + 1;
 301             let mut removed_item = None;
 302             while let Some(item) = self.borrows.get(cur) {
 303                 match *item {
 304                     Item::Permission(perm, _) => {
 305                         if granting_perm.compatible_with(access, perm) {
 306                             // Keep this, check next.
 307                             cur += 1;
 308                         } else {
 309                             // Aha! This is a bad one, remove it.
 310                             let item = self.borrows.remove(cur);
 311                             trace!("access: removing item {}", item);
 312                             removed_item = Some(item);
 313                         }
 314                     }
 315                     Item::FnBarrier(call) if !global.is_active(call) => {
 316                         // An inactive barrier, just get rid of it. (Housekeeping.)
 317                         self.borrows.remove(cur);
 318                     }
 319                     Item::FnBarrier(call) => {
 320                         // We hit an active barrier!  If we have already removed an item,
 321                         // we got a problem!  The barrier was supposed to protect this item.
 322                         if let Some(removed_item) = removed_item {
 323                             return err!(MachineError(format!(
 324                                     "not granting {} access to tag {} because barrier ({}) protects incompatible item {}",
 325                                     access, tag, call, removed_item
 326                                 )));
 327                         }
 328                         // Keep this, check next.
 329                         cur += 1;
 330                     }
 331                 }
 332             }
 333         }
 334
 335         // Done.
 336         return Ok(granting_idx);
 337     }
 338
 339     /// Deallocate a location: Like a write access, but also there must be no
 340     /// barriers at all.
 341     fn dealloc(
 342         &mut self,
 343         tag: Tag,
 344         global: &GlobalState,
 345     ) -> EvalResult<'tcx> {
 346         // Step 1: Find granting item.
 347         self.find_granting(AccessKind::Write, tag)
 348             .ok_or_else(|| InterpError::MachineError(format!(
 349                     "no item granting write access for deallocation to tag {} found in borrow stack",
 350                     tag,
 351             )))?;
 352
 353         // We must make sure there are no active barriers remaining on the stack.
 354         // Also clear the stack, no more accesses are possible.
 355         while let Some(itm) = self.borrows.pop() {
 356             match itm {
 357                 Item::FnBarrier(call) if global.is_active(call) => {
 358                     return err!(MachineError(format!(
 359                         "deallocating with active barrier ({})", call
 360                     )))
 361                 }
 362                 _ => {},
 363             }
 364         }
 365
 366         Ok(())
 367     }
 368
 369     /// `reborrow` helper function.
 370     /// Grant `permisson` to new pointer tagged `tag`, added at `position` in the stack.
 371     fn grant(&mut self, perm: Permission, tag: Tag, position: usize) {
 372         // Simply add it to the "stack" -- this might add in the middle.
 373         // As an optimization, do nothing if the new item is identical to one of its neighbors.
 374         let item = Item::Permission(perm, tag);
 375         if self.borrows[position-1] == item || self.borrows.get(position) == Some(&item) {
 376             // Optimization applies, done.
 377             trace!("reborrow: avoiding redundant item {}", item);
 378             return;
 379         }
 380         trace!("reborrow: adding item {}", item);
 381         self.borrows.insert(position, item);
 382     }
 383
 384     /// `reborrow` helper function.
 385     /// Adds a barrier.
 386     fn barrier(&mut self, call: CallId) {
 387         let itm = Item::FnBarrier(call);
 388         if *self.borrows.last().unwrap() == itm {
 389             // This is just an optimization, no functional change: Avoid stacking
 390             // multiple identical barriers on top of each other.
 391             // This can happen when a function receives several shared references
 392             // that overlap.
 393             trace!("reborrow: avoiding redundant extra barrier");
 394         } else {
 395             trace!("reborrow: adding barrier for call {}", call);
 396             self.borrows.push(itm);
 397         }
 398     }
 399
 400     /// `reborrow` helper function: test that the stack invariants are still maintained.
 401     fn test_invariants(&self) {
 402         let mut saw_shared_read_only = false;
 403         for item in self.borrows.iter() {
 404             match item {
 405                 Item::Permission(Permission::SharedReadOnly, _) => {
 406                     saw_shared_read_only = true;
 407                 }
 408                 Item::Permission(perm, _) if saw_shared_read_only => {
 409                     panic!("Found {:?} on top of a SharedReadOnly!", perm);
 410                 }
 411                 _ => {}
 412             }
 413         }
 414     }
 415
 416     /// Derived a new pointer from one with the given tag.
 417     fn reborrow(
 418         &mut self,
 419         derived_from: Tag,
 420         barrier: Option<CallId>,
 421         new_perm: Permission,
 422         new_tag: Tag,
 423         global: &GlobalState,
 424     ) -> EvalResult<'tcx> {
 425         // Figure out which access `perm` corresponds to.
 426         let access = if new_perm.grants(AccessKind::Write) {
 427                 AccessKind::Write
 428             } else {
 429                 AccessKind::Read
 430             };
 431         // Now we figure out which item grants our parent (`derived_from`) this kind of access.
 432         // We use that to determine where to put the new item.
 433         let (derived_from_idx, _) = self.find_granting(access, derived_from)
 434             .ok_or_else(|| InterpError::MachineError(format!(
 435                     "no item to reborrow for {:?} from tag {} found in borrow stack", new_perm, derived_from,
 436             )))?;
 437
 438         // We behave very differently for the "unsafe" case of a shared-read-write pointer
 439         // ("unsafe" because this also applies to shared references with interior mutability).
 440         // This is because such pointers may be reborrowed to unique pointers that actually
 441         // remain valid when their "parents" get further reborrows!
 442         // However, either way, we ensure that we insert the new item in a way that between
 443         // `derived_from` and the new one, there are only items *compatible with* `derived_from`.
 444         if new_perm == Permission::SharedReadWrite {
 445             // A very liberal reborrow because the new pointer does not expect any kind of aliasing guarantee.
 446             // Just insert new permission as child of old permission, and maintain everything else.
 447             // This inserts "as far down as possible", which is good because it makes this pointer as
 448             // long-lived as possible *and* we want all the items that are incompatible with this
 449             // to actually get removed from the stack.  If we pushed a `SharedReadWrite` on top of
 450             // a `SharedReadOnly`, we'd violate the invariant that `SaredReadOnly` are at the top
 451             // and we'd allow write access without invalidating frozen shared references!
 452             // This ensures F2b for `SharedReadWrite` by adding the new item below any
 453             // potentially existing `SharedReadOnly`.
 454             self.grant(new_perm, new_tag, derived_from_idx+1);
 455
 456             // No barrier. They can rightfully alias with `&mut`.
 457             // FIXME: This means that the `dereferencable` attribute on non-frozen shared references
 458             // is incorrect! They are dereferencable when the function is called, but might become
 459             // non-dereferencable during the course of execution.
 460             // Also see [1], [2].
 461             //
 462             // [1]: <https://internals.rust-lang.org/t/
 463             //       is-it-possible-to-be-memory-safe-with-deallocated-self/8457/8>,
 464             // [2]: <https://lists.llvm.org/pipermail/llvm-dev/2018-July/124555.html>
 465         } else {
 466             // A "safe" reborrow for a pointer that actually expects some aliasing guarantees.
 467             // Here, creating a reference actually counts as an access, and pops incompatible
 468             // stuff off the stack.
 469             // This ensures F2b for `Unique`, by removing offending `SharedReadOnly`.
 470             let check_idx = self.access(access, derived_from, global)?;
 471             assert_eq!(check_idx, derived_from_idx, "somehow we saw different items??");
 472
 473             // We insert "as far up as possible": We know only compatible items are remaining
 474             // on top of `derived_from`, and we want the new item at the top so that we
 475             // get the strongest possible guarantees.
 476             // This ensures U1 and F1.
 477             self.grant(new_perm, new_tag, self.borrows.len());
 478
 479             // Now is a good time to add the barrier, protecting the item we just added.
 480             if let Some(call) = barrier {
 481                 self.barrier(call);
 482             }
 483         }
 484
 485         // Make sure that after all this, the stack's invariant is still maintained.
 486         if cfg!(debug_assertions) {
 487             self.test_invariants();
 488         }
 489
 490         Ok(())
 491     }
 492 }
 493 // # Stacked Borrows Core End
 494
 495 /// Map per-stack operations to higher-level per-location-range operations.
 496 impl<'tcx> Stacks {
 497     /// Creates new stack with initial tag.
 498     pub(crate) fn new(
 499         size: Size,
 500         tag: Tag,
 501         extra: MemoryState,
 502     ) -> Self {
 503         let item = Item::Permission(Permission::Unique, tag);
 504         let stack = Stack {
 505             borrows: vec![item],
 506         };
 507         Stacks {
 508             stacks: RefCell::new(RangeMap::new(size, stack)),
 509             global: extra,
 510         }
 511     }
 512
 513     /// Call `f` on every stack in the range.
 514     fn for_each(
 515         &self,
 516         ptr: Pointer<Tag>,
 517         size: Size,
 518         f: impl Fn(&mut Stack, Tag, &GlobalState) -> EvalResult<'tcx>,
 519     ) -> EvalResult<'tcx> {
 520         let global = self.global.borrow();
 521         let mut stacks = self.stacks.borrow_mut();
 522         for stack in stacks.iter_mut(ptr.offset, size) {
 523             f(stack, ptr.tag, &*global)?;
 524         }
 525         Ok(())
 526     }
 527 }
 528
 529 /// Glue code to connect with Miri Machine Hooks
 530 impl Stacks {
 531     pub fn new_allocation(
 532         size: Size,
 533         extra: &MemoryState,
 534         kind: MemoryKind<MiriMemoryKind>,
 535     ) -> (Self, Tag) {
 536         let tag = match kind {
 537             MemoryKind::Stack => {
 538                 // New unique borrow. This `Uniq` is not accessible by the program,
 539                 // so it will only ever be used when using the local directly (i.e.,
 540                 // not through a pointer). That is, whenever we directly use a local, this will pop
 541                 // everything else off the stack, invalidating all previous pointers,
 542                 // and in particular, *all* raw pointers. This subsumes the explicit
 543                 // `reset` which the blog post [1] says to perform when accessing a local.
 544                 //
 545                 // [1]: <https://www.ralfj.de/blog/2018/08/07/stacked-borrows.html>
 546                 Tag::Tagged(extra.borrow_mut().new_ptr())
 547             }
 548             _ => {
 549                 Tag::Untagged
 550             }
 551         };
 552         let stack = Stacks::new(size, tag, Rc::clone(extra));
 553         (stack, tag)
 554     }
 555 }
 556
 557 impl AllocationExtra<Tag> for Stacks {
 558     #[inline(always)]
 559     fn memory_read<'tcx>(
 560         alloc: &Allocation<Tag, Stacks>,
 561         ptr: Pointer<Tag>,
 562         size: Size,
 563     ) -> EvalResult<'tcx> {
 564         trace!("read access with tag {}: {:?}, size {}", ptr.tag, ptr, size.bytes());
 565         alloc.extra.for_each(ptr, size, |stack, tag, global| {
 566             stack.access(AccessKind::Read, tag, global)?;
 567             Ok(())
 568         })
 569     }
 570
 571     #[inline(always)]
 572     fn memory_written<'tcx>(
 573         alloc: &mut Allocation<Tag, Stacks>,
 574         ptr: Pointer<Tag>,
 575         size: Size,
 576     ) -> EvalResult<'tcx> {
 577         trace!("write access with tag {}: {:?}, size {}", ptr.tag, ptr, size.bytes());
 578         alloc.extra.for_each(ptr, size, |stack, tag, global| {
 579             stack.access(AccessKind::Write, tag, global)?;
 580             Ok(())
 581         })
 582     }
 583
 584     #[inline(always)]
 585     fn memory_deallocated<'tcx>(
 586         alloc: &mut Allocation<Tag, Stacks>,
 587         ptr: Pointer<Tag>,
 588         size: Size,
 589     ) -> EvalResult<'tcx> {
 590         trace!("deallocation with tag {}: {:?}, size {}", ptr.tag, ptr, size.bytes());
 591         alloc.extra.for_each(ptr, size, |stack, tag, global| {
 592             stack.dealloc(tag, global)
 593         })
 594     }
 595 }
 596
 597 impl<'a, 'mir, 'tcx> EvalContextPrivExt<'a, 'mir, 'tcx> for crate::MiriEvalContext<'a, 'mir, 'tcx> {}
 598 trait EvalContextPrivExt<'a, 'mir, 'tcx: 'a+'mir>: crate::MiriEvalContextExt<'a, 'mir, 'tcx> {
 599     /// High-level `reborrow` operation.  This decides which reference gets which kind
 600     /// of permission!
 601     fn reborrow(
 602         &mut self,
 603         place: MPlaceTy<'tcx, Tag>,
 604         size: Size,
 605         kind: RefKind,
 606         new_tag: Tag,
 607         fn_barrier: bool,
 608     ) -> EvalResult<'tcx> {
 609         let this = self.eval_context_mut();
 610         let barrier = if fn_barrier { Some(this.frame().extra) } else { None };
 611         let ptr = place.ptr.to_ptr()?;
 612         trace!("reborrow: {:?} reference {} derived from {} (pointee {}): {:?}, size {}",
 613             kind, new_tag, ptr.tag, place.layout.ty, ptr, size.bytes());
 614
 615         // Get the allocation. It might not be mutable, so we cannot use `get_mut`.
 616         let alloc = this.memory().get(ptr.alloc_id)?;
 617         alloc.check_bounds(this, ptr, size)?;
 618         // Update the stacks.
 619         let perm = match kind {
 620             RefKind::Unique => Permission::Unique,
 621             RefKind::Raw { mutable: true } => Permission::SharedReadWrite,
 622             RefKind::Shared | RefKind::Raw { mutable: false } => {
 623                 // Shared references and *const are a whole different kind of game, the
 624                 // permission is not uniform across the entire range!
 625                 // We need a frozen-sensitive reborrow.
 626                 return this.visit_freeze_sensitive(place, size, |cur_ptr, size, frozen| {
 627                     // We are only ever `SharedReadOnly` inside the frozen bits.
 628                     let perm = if frozen { Permission::SharedReadOnly } else { Permission::SharedReadWrite };
 629                     alloc.extra.for_each(cur_ptr, size, |stack, tag, global| {
 630                         stack.reborrow(tag, barrier, perm, new_tag, global)
 631                     })
 632                 });
 633             }
 634         };
 635         debug_assert_ne!(perm, Permission::SharedReadOnly, "SharedReadOnly must be used frozen-sensitive");
 636         alloc.extra.for_each(ptr, size, |stack, tag, global| {
 637             stack.reborrow(tag, barrier, perm, new_tag, global)
 638         })
 639     }
 640
 641     /// Retags an indidual pointer, returning the retagged version.
 642     /// `mutbl` can be `None` to make this a raw pointer.
 643     fn retag_reference(
 644         &mut self,
 645         val: ImmTy<'tcx, Tag>,
 646         kind: RefKind,
 647         fn_barrier: bool,
 648         two_phase: bool,
 649     ) -> EvalResult<'tcx, Immediate<Tag>> {
 650         let this = self.eval_context_mut();
 651         // We want a place for where the ptr *points to*, so we get one.
 652         let place = this.ref_to_mplace(val)?;
 653         let size = this.size_and_align_of_mplace(place)?
 654             .map(|(size, _)| size)
 655             .unwrap_or_else(|| place.layout.size);
 656         if size == Size::ZERO {
 657             // Nothing to do for ZSTs.
 658             return Ok(*val);
 659         }
 660
 661         // Compute new borrow.
 662         let new_tag = match kind {
 663             RefKind::Raw { .. } => Tag::Untagged,
 664             _ => Tag::Tagged(this.memory().extra.borrow_mut().new_ptr()),
 665         };
 666
 667         // Reborrow.
 668         this.reborrow(place, size, kind, new_tag, fn_barrier)?;
 669         let new_place = place.replace_tag(new_tag);
 670         // Handle two-phase borrows.
 671         if two_phase {
 672             assert!(kind == RefKind::Unique, "two-phase shared borrows make no sense");
 673             // Grant read access *to the parent pointer* with the old tag.  This means the same pointer
 674             // has multiple items in the stack now!
 675             // FIXME: Think about this some more, in particular about the interaction with cast-to-raw.
 676             // Maybe find a better way to express 2-phase, now that we have a "more expressive language"
 677             // in the stack.
 678             let old_tag = place.ptr.to_ptr().unwrap().tag;
 679             this.reborrow(new_place, size, RefKind::Shared, old_tag, /* fn_barrier: */ false)?;
 680         }
 681
 682         // Return new pointer.
 683         Ok(new_place.to_ref())
 684     }
 685 }
 686
 687 impl<'a, 'mir, 'tcx> EvalContextExt<'a, 'mir, 'tcx> for crate::MiriEvalContext<'a, 'mir, 'tcx> {}
 688 pub trait EvalContextExt<'a, 'mir, 'tcx: 'a+'mir>: crate::MiriEvalContextExt<'a, 'mir, 'tcx> {
 689     fn retag(
 690         &mut self,
 691         kind: RetagKind,
 692         place: PlaceTy<'tcx, Tag>
 693     ) -> EvalResult<'tcx> {
 694         let this = self.eval_context_mut();
 695         // Determine mutability and whether to add a barrier.
 696         // Cannot use `builtin_deref` because that reports *immutable* for `Box`,
 697         // making it useless.
 698         fn qualify(ty: ty::Ty<'_>, kind: RetagKind) -> Option<(RefKind, bool)> {
 699             match ty.sty {
 700                 // References are simple.
 701                 ty::Ref(_, _, MutMutable) =>
 702                     Some((RefKind::Unique, kind == RetagKind::FnEntry)),
 703                 ty::Ref(_, _, MutImmutable) =>
 704                     Some((RefKind::Shared, kind == RetagKind::FnEntry)),
 705                 // Raw pointers need to be enabled.
 706                 ty::RawPtr(tym) if kind == RetagKind::Raw =>
 707                     Some((RefKind::Raw { mutable: tym.mutbl == MutMutable }, false)),
 708                 // Boxes do not get a barrier: barriers reflect that references outlive the call
 709                 // they were passed in to; that's just not the case for boxes.
 710                 ty::Adt(..) if ty.is_box() => Some((RefKind::Unique, false)),
 711                 _ => None,
 712             }
 713         }
 714
 715         // We need a visitor to visit all references. However, that requires
 716         // a `MemPlace`, so we have a fast path for reference types that
 717         // avoids allocating.
 718         if let Some((mutbl, barrier)) = qualify(place.layout.ty, kind) {
 719             // Fast path.
 720             let val = this.read_immediate(this.place_to_op(place)?)?;
 721             let val = this.retag_reference(val, mutbl, barrier, kind == RetagKind::TwoPhase)?;
 722             this.write_immediate(val, place)?;
 723             return Ok(());
 724         }
 725         let place = this.force_allocation(place)?;
 726
 727         let mut visitor = RetagVisitor { ecx: this, kind };
 728         visitor.visit_value(place)?;
 729
 730         // The actual visitor.
 731         struct RetagVisitor<'ecx, 'a, 'mir, 'tcx> {
 732             ecx: &'ecx mut MiriEvalContext<'a, 'mir, 'tcx>,
 733             kind: RetagKind,
 734         }
 735         impl<'ecx, 'a, 'mir, 'tcx>
 736             MutValueVisitor<'a, 'mir, 'tcx, Evaluator<'tcx>>
 737         for
 738             RetagVisitor<'ecx, 'a, 'mir, 'tcx>
 739         {
 740             type V = MPlaceTy<'tcx, Tag>;
 741
 742             #[inline(always)]
 743             fn ecx(&mut self) -> &mut MiriEvalContext<'a, 'mir, 'tcx> {
 744                 &mut self.ecx
 745             }
 746
 747             // Primitives of reference type, that is the one thing we are interested in.
 748             fn visit_primitive(&mut self, place: MPlaceTy<'tcx, Tag>) -> EvalResult<'tcx>
 749             {
 750                 // Cannot use `builtin_deref` because that reports *immutable* for `Box`,
 751                 // making it useless.
 752                 if let Some((mutbl, barrier)) = qualify(place.layout.ty, self.kind) {
 753                     let val = self.ecx.read_immediate(place.into())?;
 754                     let val = self.ecx.retag_reference(
 755                         val,
 756                         mutbl,
 757                         barrier,
 758                         self.kind == RetagKind::TwoPhase
 759                     )?;
 760                     self.ecx.write_immediate(val, place.into())?;
 761                 }
 762                 Ok(())
 763             }
 764         }
 765
 766         Ok(())
 767     }
 768 }