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