src/stacked_borrows.rs

   1 use std::cell::RefCell;
   2 use std::collections::HashSet;
   3 use std::rc::Rc;
   4
   5 use rustc::ty::{self, layout::Size};
   6 use rustc::hir::{Mutability, MutMutable, MutImmutable};
   7 use rustc::mir::RetagKind;
   8
   9 use crate::{
  10     EvalResult, EvalErrorKind, MiriEvalContext, HelpersEvalContextExt, Evaluator, MutValueVisitor,
  11     MemoryKind, MiriMemoryKind, RangeMap, AllocId, Allocation, AllocationExtra,
  12     Pointer, Immediate, ImmTy, PlaceTy, MPlaceTy,
  13 };
  14
  15 pub type Timestamp = u64;
  16 pub type CallId = u64;
  17
  18 /// Information about which kind of borrow was used to create the reference this is tagged
  19 /// with.
  20 #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
  21 pub enum Borrow {
  22     /// A unique (mutable) reference.
  23     Uniq(Timestamp),
  24     /// An aliasing reference.  This is also used by raw pointers, which do not track details
  25     /// of how or when they were created, hence the timestamp is optional.
  26     /// Shr(Some(_)) does NOT mean that the destination of this reference is frozen;
  27     /// that depends on the type!  Only those parts outside of an `UnsafeCell` are actually
  28     /// frozen.
  29     Alias(Option<Timestamp>),
  30 }
  31
  32 impl Borrow {
  33     #[inline(always)]
  34     pub fn is_aliasing(self) -> bool {
  35         match self {
  36             Borrow::Alias(_) => true,
  37             _ => false,
  38         }
  39     }
  40
  41     #[inline(always)]
  42     pub fn is_unique(self) -> bool {
  43         match self {
  44             Borrow::Uniq(_) => true,
  45             _ => false,
  46         }
  47     }
  48 }
  49
  50 impl Default for Borrow {
  51     fn default() -> Self {
  52         Borrow::Alias(None)
  53     }
  54 }
  55
  56 /// An item in the per-location borrow stack
  57 #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
  58 pub enum BorStackItem {
  59     /// Indicates the unique reference that may mutate.
  60     Uniq(Timestamp),
  61     /// Indicates that the location has been mutably shared.  Used for raw pointers as
  62     /// well as for unfrozen shared references.
  63     Raw,
  64     /// A barrier, tracking the function it belongs to by its index on the call stack
  65     FnBarrier(CallId)
  66 }
  67
  68 /// Extra per-location state
  69 #[derive(Clone, Debug, PartialEq, Eq)]
  70 pub struct Stack {
  71     borrows: Vec<BorStackItem>, // used as a stack; never empty
  72     frozen_since: Option<Timestamp>, // virtual frozen "item" on top of the stack
  73 }
  74
  75 impl Stack {
  76     #[inline(always)]
  77     pub fn is_frozen(&self) -> bool {
  78         self.frozen_since.is_some()
  79     }
  80 }
  81
  82 /// What kind of reference is being used?
  83 #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
  84 pub enum RefKind {
  85     /// &mut
  86     Unique,
  87     /// & without interior mutability
  88     Frozen,
  89     /// * (raw pointer) or & to `UnsafeCell`
  90     Raw,
  91 }
  92
  93 /// What kind of access is being performed?
  94 #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
  95 pub enum AccessKind {
  96     Read,
  97     Write,
  98     Dealloc,
  99 }
 100
 101 /// Extra global state in the memory, available to the memory access hooks
 102 #[derive(Debug)]
 103 pub struct BarrierTracking {
 104     next_id: CallId,
 105     active_calls: HashSet<CallId>,
 106 }
 107 pub type MemoryState = Rc<RefCell<BarrierTracking>>;
 108
 109 impl Default for BarrierTracking {
 110     fn default() -> Self {
 111         BarrierTracking {
 112             next_id: 0,
 113             active_calls: HashSet::default(),
 114         }
 115     }
 116 }
 117
 118 impl BarrierTracking {
 119     pub fn new_call(&mut self) -> CallId {
 120         let id = self.next_id;
 121         trace!("new_call: Assigning ID {}", id);
 122         self.active_calls.insert(id);
 123         self.next_id += 1;
 124         id
 125     }
 126
 127     pub fn end_call(&mut self, id: CallId) {
 128         assert!(self.active_calls.remove(&id));
 129     }
 130
 131     fn is_active(&self, id: CallId) -> bool {
 132         self.active_calls.contains(&id)
 133     }
 134 }
 135
 136 /// Extra global machine state
 137 #[derive(Clone, Debug)]
 138 pub struct State {
 139     clock: Timestamp
 140 }
 141
 142 impl Default for State {
 143     fn default() -> Self {
 144         State { clock: 0 }
 145     }
 146 }
 147
 148 impl State {
 149     fn increment_clock(&mut self) -> Timestamp {
 150         let val = self.clock;
 151         self.clock = val + 1;
 152         val
 153     }
 154 }
 155
 156 /// Extra per-allocation state
 157 #[derive(Clone, Debug)]
 158 pub struct Stacks {
 159     // Even reading memory can have effects on the stack, so we need a `RefCell` here.
 160     stacks: RefCell<RangeMap<Stack>>,
 161     barrier_tracking: MemoryState,
 162 }
 163
 164 /// Core per-location operations: deref, access, create.
 165 /// We need to make at least the following things true:
 166 ///
 167 /// U1: After creating a Uniq, it is at the top (+unfrozen).
 168 /// U2: If the top is Uniq (+unfrozen), accesses must be through that Uniq or pop it.
 169 /// U3: If an access (deref sufficient?) happens with a Uniq, it requires the Uniq to be in the stack.
 170 ///
 171 /// F1: After creating a &, the parts outside `UnsafeCell` are frozen.
 172 /// F2: If a write access happens, it unfreezes.
 173 /// F3: If an access (well, a deref) happens with an & outside `UnsafeCell`, it requires the location to still be frozen.
 174 impl<'tcx> Stack {
 175     /// Deref `bor`: Check if the location is frozen and the tag in the stack.
 176     /// This dos *not* constitute an access!  "Deref" refers to the `*` operator
 177     /// in Rust, and includs cases like `&*x` or `(*x).foo` where no or only part
 178     /// of the memory actually gets accessed.  Also we cannot know if we are
 179     /// going to read or write.
 180     /// Returns the index of the item we matched, `None` if it was the frozen one.
 181     /// `kind` indicates which kind of reference is being dereferenced.
 182     fn deref(
 183         &self,
 184         bor: Borrow,
 185         kind: RefKind,
 186     ) -> Result<Option<usize>, String> {
 187         // Exclude unique ref with frozen tag.
 188         if let (RefKind::Unique, Borrow::Alias(Some(_))) = (kind, bor) {
 189             return Err(format!("Encountered mutable reference with frozen tag ({:?})", bor));
 190         }
 191         // Checks related to freezing
 192         match bor {
 193             Borrow::Alias(Some(bor_t)) if kind == RefKind::Frozen => {
 194                 // We need the location to be frozen. This ensures F3.
 195                 let frozen = self.frozen_since.map_or(false, |itm_t| itm_t <= bor_t);
 196                 return if frozen { Ok(None) } else {
 197                     Err(format!("Location is not frozen long enough"))
 198                 }
 199             }
 200             Borrow::Alias(_) if self.frozen_since.is_some() => {
 201                 return Ok(None) // Shared deref to frozen location, looking good
 202             }
 203             _ => {} // Not sufficient, go on looking.
 204         }
 205         // If we got here, we have to look for our item in the stack.
 206         for (idx, &itm) in self.borrows.iter().enumerate().rev() {
 207             match (itm, bor) {
 208                 (BorStackItem::Uniq(itm_t), Borrow::Uniq(bor_t)) if itm_t == bor_t => {
 209                     // Found matching unique item.  This satisfies U3.
 210                     return Ok(Some(idx))
 211                 }
 212                 (BorStackItem::Raw, Borrow::Alias(_)) => {
 213                     // Found matching aliasing/raw item.
 214                     return Ok(Some(idx))
 215                 }
 216                 // Go on looking.  We ignore barriers!  When an `&mut` and an `&` alias,
 217                 // dereferencing the `&` is still possible (to reborrow), but doing
 218                 // an access is not.
 219                 _ => {}
 220             }
 221         }
 222         // If we got here, we did not find our item.  We have to error to satisfy U3.
 223         Err(format!("Borrow being dereferenced ({:?}) does not exist on the borrow stack", bor))
 224     }
 225
 226     /// Perform an actual memory access using `bor`.  We do not know any types here
 227     /// or whether things should be frozen, but we *do* know if this is reading
 228     /// or writing.
 229     fn access(
 230         &mut self,
 231         bor: Borrow,
 232         kind: AccessKind,
 233         barrier_tracking: &BarrierTracking,
 234     ) -> EvalResult<'tcx> {
 235         // Check if we can match the frozen "item".
 236         // Not possible on writes!
 237         if self.is_frozen() {
 238             if kind == AccessKind::Read {
 239                 // When we are frozen, we just accept all reads.  No harm in this.
 240                 // The deref already checked that `Uniq` items are in the stack, and that
 241                 // the location is frozen if it should be.
 242                 return Ok(());
 243             }
 244             trace!("access: Unfreezing");
 245         }
 246         // Unfreeze on writes.  This ensures F2.
 247         self.frozen_since = None;
 248         // Pop the stack until we have something matching.
 249         while let Some(&itm) = self.borrows.last() {
 250             match (itm, bor) {
 251                 (BorStackItem::FnBarrier(call), _) if barrier_tracking.is_active(call) => {
 252                     return err!(MachineError(format!(
 253                         "Stopping looking for borrow being accessed ({:?}) because of barrier ({})",
 254                         bor, call
 255                     )))
 256                 }
 257                 (BorStackItem::Uniq(itm_t), Borrow::Uniq(bor_t)) if itm_t == bor_t => {
 258                     // Found matching unique item.  Continue after the match.
 259                 }
 260                 (BorStackItem::Raw, _) if kind == AccessKind::Read => {
 261                     // When reading, everything can use a raw item!
 262                     // We do not want to do this when writing: Writing to an `&mut`
 263                     // should reaffirm its exclusivity (i.e., make sure it is
 264                     // on top of the stack).
 265                     // Continue after the match.
 266                 }
 267                 (BorStackItem::Raw, Borrow::Alias(_)) => {
 268                     // Found matching raw item.  Continue after the match.
 269                 }
 270                 _ => {
 271                     // Pop this, go on.  This ensures U2.
 272                     let itm = self.borrows.pop().unwrap();
 273                     trace!("access: Popping {:?}", itm);
 274                     continue
 275                 }
 276             }
 277             // If we got here, we found a matching item.  Congratulations!
 278             // However, we are not done yet: If this access is deallocating, we must make sure
 279             // there are no active barriers remaining on the stack.
 280             if kind == AccessKind::Dealloc {
 281                 for &itm in self.borrows.iter().rev() {
 282                     match itm {
 283                         BorStackItem::FnBarrier(call) if barrier_tracking.is_active(call) => {
 284                             return err!(MachineError(format!(
 285                                 "Deallocating with active barrier ({})", call
 286                             )))
 287                         }
 288                         _ => {},
 289                     }
 290                 }
 291             }
 292             // NOW we are done.
 293             return Ok(())
 294         }
 295         // If we got here, we did not find our item.
 296         err!(MachineError(format!(
 297             "Borrow being accessed ({:?}) does not exist on the borrow stack",
 298             bor
 299         )))
 300     }
 301
 302     /// Initiate `bor`; mostly this means pushing.
 303     /// This operation cannot fail; it is up to the caller to ensure that the precondition
 304     /// is met: We cannot push `Uniq` onto frozen stacks.
 305     /// `kind` indicates which kind of reference is being created.
 306     fn create(&mut self, bor: Borrow, kind: RefKind) {
 307         // When creating a frozen reference, freeze.  This ensures F1.
 308         // We also do *not* push anything else to the stack, making sure that no nother kind
 309         // of access (like writing through raw pointers) is permitted.
 310         if kind == RefKind::Frozen {
 311             let bor_t = match bor {
 312                 Borrow::Alias(Some(t)) => t,
 313                 _ => bug!("Creating illegal borrow {:?} for frozen ref", bor),
 314             };
 315             // It is possible that we already are frozen (e.g. if we just pushed a barrier,
 316             // the redundancy check would not have kicked in).
 317             match self.frozen_since {
 318                 Some(loc_t) => assert!(loc_t <= bor_t, "Trying to freeze location for longer than it was already frozen"),
 319                 None => {
 320                     trace!("create: Freezing");
 321                     self.frozen_since = Some(bor_t);
 322                 }
 323             }
 324             return;
 325         }
 326         assert!(self.frozen_since.is_none(), "Trying to create non-frozen reference to frozen location");
 327
 328         // Push new item to the stack.
 329         let itm = match bor {
 330             Borrow::Uniq(t) => BorStackItem::Uniq(t),
 331             Borrow::Alias(_) => BorStackItem::Raw,
 332         };
 333         if *self.borrows.last().unwrap() == itm {
 334             // This is just an optimization, no functional change: Avoid stacking
 335             // multiple `Shr` on top of each other.
 336             assert!(bor.is_aliasing());
 337             trace!("create: Sharing a shared location is a NOP");
 338         } else {
 339             // This ensures U1.
 340             trace!("create: Pushing {:?}", itm);
 341             self.borrows.push(itm);
 342         }
 343     }
 344
 345     /// Add a barrier
 346     fn barrier(&mut self, call: CallId) {
 347         let itm = BorStackItem::FnBarrier(call);
 348         if *self.borrows.last().unwrap() == itm {
 349             // This is just an optimization, no functional change: Avoid stacking
 350             // multiple identical barriers on top of each other.
 351             // This can happen when a function receives several shared references
 352             // that overlap.
 353             trace!("barrier: Avoiding redundant extra barrier");
 354         } else {
 355             trace!("barrier: Pushing barrier for call {}", call);
 356             self.borrows.push(itm);
 357         }
 358     }
 359 }
 360
 361 /// Higher-level per-location operations: deref, access, reborrow.
 362 impl<'tcx> Stacks {
 363     /// Check that this stack is fine with being dereferenced
 364     fn deref(
 365         &self,
 366         ptr: Pointer<Borrow>,
 367         size: Size,
 368         kind: RefKind,
 369     ) -> EvalResult<'tcx> {
 370         trace!("deref for tag {:?} as {:?}: {:?}, size {}",
 371             ptr.tag, kind, ptr, size.bytes());
 372         let stacks = self.stacks.borrow();
 373         for stack in stacks.iter(ptr.offset, size) {
 374             stack.deref(ptr.tag, kind).map_err(EvalErrorKind::MachineError)?;
 375         }
 376         Ok(())
 377     }
 378
 379     /// `ptr` got used, reflect that in the stack.
 380     fn access(
 381         &self,
 382         ptr: Pointer<Borrow>,
 383         size: Size,
 384         kind: AccessKind,
 385     ) -> EvalResult<'tcx> {
 386         trace!("{:?} access of tag {:?}: {:?}, size {}", kind, ptr.tag, ptr, size.bytes());
 387         // Even reads can have a side-effect, by invalidating other references.
 388         // This is fundamentally necessary since `&mut` asserts that there
 389         // are no accesses through other references, not even reads.
 390         let barrier_tracking = self.barrier_tracking.borrow();
 391         let mut stacks = self.stacks.borrow_mut();
 392         for stack in stacks.iter_mut(ptr.offset, size) {
 393             stack.access(ptr.tag, kind, &*barrier_tracking)?;
 394         }
 395         Ok(())
 396     }
 397
 398     /// Reborrow the given pointer to the new tag for the given kind of reference.
 399     /// This works on `&self` because we might encounter references to constant memory.
 400     fn reborrow(
 401         &self,
 402         ptr: Pointer<Borrow>,
 403         size: Size,
 404         mut barrier: Option<CallId>,
 405         new_bor: Borrow,
 406         new_kind: RefKind,
 407     ) -> EvalResult<'tcx> {
 408         assert_eq!(new_bor.is_unique(), new_kind == RefKind::Unique);
 409         trace!("reborrow for tag {:?} to {:?} as {:?}: {:?}, size {}",
 410             ptr.tag, new_bor, new_kind, ptr, size.bytes());
 411         if new_kind == RefKind::Raw {
 412             // No barrier for raw, including `&UnsafeCell`.  They can rightfully
 413             // alias with `&mut`.
 414             // FIXME: This means that the `dereferencable` attribute on non-frozen shared
 415             // references is incorrect!  They are dereferencable when the function is
 416             // called, but might become non-dereferencable during the course of execution.
 417             // Also see [1], [2].
 418             //
 419             // [1]: <https://internals.rust-lang.org/t/
 420             //       is-it-possible-to-be-memory-safe-with-deallocated-self/8457/8>,
 421             // [2]: <https://lists.llvm.org/pipermail/llvm-dev/2018-July/124555.html>
 422             barrier = None;
 423         }
 424         let barrier_tracking = self.barrier_tracking.borrow();
 425         let mut stacks = self.stacks.borrow_mut();
 426         for stack in stacks.iter_mut(ptr.offset, size) {
 427             // Access source `ptr`, create new ref.
 428             let ptr_idx = stack.deref(ptr.tag, new_kind).map_err(EvalErrorKind::MachineError)?;
 429             // If we can deref the new tag already, and if that tag lives higher on
 430             // the stack than the one we come from, just use that.
 431             // IOW, we check if `new_bor` *already* is "derived from" `ptr.tag`.
 432             // This also checks frozenness, if required.
 433             let bor_redundant = barrier.is_none() &&
 434                 match (ptr_idx, stack.deref(new_bor, new_kind)) {
 435                     // If the new borrow works with the frozen item, or else if it lives
 436                     // above the old one in the stack, our job here is done.
 437                     (_, Ok(None)) => true,
 438                     (Some(ptr_idx), Ok(Some(new_idx))) if new_idx >= ptr_idx => true,
 439                     // Otherwise we need to create a new borrow.
 440                     _ => false,
 441                 };
 442             if bor_redundant {
 443                 assert!(new_bor.is_aliasing(), "A unique reborrow can never be redundant");
 444                 trace!("reborrow is redundant");
 445                 continue;
 446             }
 447             // We need to do some actual work.
 448             let access_kind = if new_kind == RefKind::Unique {
 449                 AccessKind::Write
 450             } else {
 451                 AccessKind::Read
 452             };
 453             stack.access(ptr.tag, access_kind, &*barrier_tracking)?;
 454             if let Some(call) = barrier {
 455                 stack.barrier(call);
 456             }
 457             stack.create(new_bor, new_kind);
 458         }
 459         Ok(())
 460     }
 461 }
 462
 463 /// Hooks and glue
 464 impl AllocationExtra<Borrow, MemoryState> for Stacks {
 465     #[inline(always)]
 466     fn memory_allocated<'tcx>(size: Size, extra: &MemoryState) -> Self {
 467         let stack = Stack {
 468             borrows: vec![BorStackItem::Raw],
 469             frozen_since: None,
 470         };
 471         Stacks {
 472             stacks: RefCell::new(RangeMap::new(size, stack)),
 473             barrier_tracking: Rc::clone(extra),
 474         }
 475     }
 476
 477     #[inline(always)]
 478     fn memory_read<'tcx>(
 479         alloc: &Allocation<Borrow, Stacks>,
 480         ptr: Pointer<Borrow>,
 481         size: Size,
 482     ) -> EvalResult<'tcx> {
 483         alloc.extra.access(ptr, size, AccessKind::Read)
 484     }
 485
 486     #[inline(always)]
 487     fn memory_written<'tcx>(
 488         alloc: &mut Allocation<Borrow, Stacks>,
 489         ptr: Pointer<Borrow>,
 490         size: Size,
 491     ) -> EvalResult<'tcx> {
 492         alloc.extra.access(ptr, size, AccessKind::Write)
 493     }
 494
 495     #[inline(always)]
 496     fn memory_deallocated<'tcx>(
 497         alloc: &mut Allocation<Borrow, Stacks>,
 498         ptr: Pointer<Borrow>,
 499         size: Size,
 500     ) -> EvalResult<'tcx> {
 501         alloc.extra.access(ptr, size, AccessKind::Dealloc)
 502     }
 503 }
 504
 505 impl<'tcx> Stacks {
 506     /// Pushes the first item to the stacks.
 507     pub(crate) fn first_item(
 508         &mut self,
 509         itm: BorStackItem,
 510         size: Size
 511     ) {
 512         for stack in self.stacks.get_mut().iter_mut(Size::ZERO, size) {
 513             assert!(stack.borrows.len() == 1);
 514             assert_eq!(stack.borrows.pop().unwrap(), BorStackItem::Raw);
 515             stack.borrows.push(itm);
 516         }
 517     }
 518 }
 519
 520 impl<'a, 'mir, 'tcx> EvalContextPrivExt<'a, 'mir, 'tcx> for crate::MiriEvalContext<'a, 'mir, 'tcx> {}
 521 trait EvalContextPrivExt<'a, 'mir, 'tcx: 'a+'mir>: crate::MiriEvalContextExt<'a, 'mir, 'tcx> {
 522     fn reborrow(
 523         &mut self,
 524         place: MPlaceTy<'tcx, Borrow>,
 525         size: Size,
 526         fn_barrier: bool,
 527         new_bor: Borrow
 528     ) -> EvalResult<'tcx> {
 529         let this = self.eval_context_mut();
 530         let ptr = place.ptr.to_ptr()?;
 531         let barrier = if fn_barrier { Some(this.frame().extra) } else { None };
 532         trace!("reborrow: Creating new reference for {:?} (pointee {}): {:?}",
 533             ptr, place.layout.ty, new_bor);
 534
 535         // Get the allocation.  It might not be mutable, so we cannot use `get_mut`.
 536         let alloc = this.memory().get(ptr.alloc_id)?;
 537         alloc.check_bounds(this, ptr, size)?;
 538         // Update the stacks.
 539         if let Borrow::Alias(Some(_)) = new_bor {
 540             // Reference that cares about freezing. We need a frozen-sensitive reborrow.
 541             this.visit_freeze_sensitive(place, size, |cur_ptr, size, frozen| {
 542                 let kind = if frozen { RefKind::Frozen } else { RefKind::Raw };
 543                 alloc.extra.reborrow(cur_ptr, size, barrier, new_bor, kind)
 544             })?;
 545         } else {
 546             // Just treat this as one big chunk.
 547             let kind = if new_bor.is_unique() { RefKind::Unique } else { RefKind::Raw };
 548             alloc.extra.reborrow(ptr, size, barrier, new_bor, kind)?;
 549         }
 550         Ok(())
 551     }
 552
 553     /// Retag an indidual pointer, returning the retagged version.
 554     /// `mutbl` can be `None` to make this a raw pointer.
 555     fn retag_reference(
 556         &mut self,
 557         val: ImmTy<'tcx, Borrow>,
 558         mutbl: Option<Mutability>,
 559         fn_barrier: bool,
 560         two_phase: bool,
 561     ) -> EvalResult<'tcx, Immediate<Borrow>> {
 562         let this = self.eval_context_mut();
 563         // We want a place for where the ptr *points to*, so we get one.
 564         let place = this.ref_to_mplace(val)?;
 565         let size = this.size_and_align_of_mplace(place)?
 566             .map(|(size, _)| size)
 567             .unwrap_or_else(|| place.layout.size);
 568         if size == Size::ZERO {
 569             // Nothing to do for ZSTs.
 570             return Ok(*val);
 571         }
 572
 573         // Compute new borrow.
 574         let time = this.machine.stacked_borrows.increment_clock();
 575         let new_bor = match mutbl {
 576             Some(MutMutable) => Borrow::Uniq(time),
 577             Some(MutImmutable) => Borrow::Alias(Some(time)),
 578             None => Borrow::default(),
 579         };
 580
 581         // Reborrow.
 582         this.reborrow(place, size, fn_barrier, new_bor)?;
 583         let new_place = place.with_tag(new_bor);
 584         // Handle two-phase borrows.
 585         if two_phase {
 586             assert!(mutbl == Some(MutMutable), "two-phase shared borrows make no sense");
 587             // We immediately share it, to allow read accesses
 588             let two_phase_time = this.machine.stacked_borrows.increment_clock();
 589             let two_phase_bor = Borrow::Alias(Some(two_phase_time));
 590             this.reborrow(new_place, size, /*fn_barrier*/false, two_phase_bor)?;
 591         }
 592
 593         // Return new ptr.
 594         Ok(new_place.to_ref())
 595     }
 596 }
 597
 598 impl<'a, 'mir, 'tcx> EvalContextExt<'a, 'mir, 'tcx> for crate::MiriEvalContext<'a, 'mir, 'tcx> {}
 599 pub trait EvalContextExt<'a, 'mir, 'tcx: 'a+'mir>: crate::MiriEvalContextExt<'a, 'mir, 'tcx> {
 600     fn tag_new_allocation(
 601         &mut self,
 602         id: AllocId,
 603         kind: MemoryKind<MiriMemoryKind>,
 604     ) -> Borrow {
 605         let this = self.eval_context_mut();
 606         let time = match kind {
 607             MemoryKind::Stack => {
 608                 // New unique borrow. This `Uniq` is not accessible by the program,
 609                 // so it will only ever be used when using the local directly (i.e.,
 610                 // not through a pointer).  IOW, whenever we directly use a local this will pop
 611                 // everything else off the stack, invalidating all previous pointers
 612                 // and, in particular, *all* raw pointers.  This subsumes the explicit
 613                 // `reset` which the blog post [1] says to perform when accessing a local.
 614                 //
 615                 // [1] https://www.ralfj.de/blog/2018/08/07/stacked-borrows.html
 616                 this.machine.stacked_borrows.increment_clock()
 617             }
 618             _ => {
 619                 // Nothing to do for everything else
 620                 return Borrow::default()
 621             }
 622         };
 623         // Make this the active borrow for this allocation
 624         let alloc = this.memory_mut().get_mut(id).expect("This is a new allocation, it must still exist");
 625         let size = Size::from_bytes(alloc.bytes.len() as u64);
 626         alloc.extra.first_item(BorStackItem::Uniq(time), size);
 627         Borrow::Uniq(time)
 628     }
 629
 630     /// Called for value-to-place conversion.  `mutability` is `None` for raw pointers.
 631     ///
 632     /// Note that this does NOT mean that all this memory will actually get accessed/referenced!
 633     /// We could be in the middle of `&(*var).1`.
 634     fn ptr_dereference(
 635         &self,
 636         place: MPlaceTy<'tcx, Borrow>,
 637         size: Size,
 638         mutability: Option<Mutability>,
 639     ) -> EvalResult<'tcx> {
 640         let this = self.eval_context_ref();
 641         trace!("ptr_dereference: Accessing {} reference for {:?} (pointee {})",
 642             if let Some(mutability) = mutability { format!("{:?}", mutability) } else { format!("raw") },
 643             place.ptr, place.layout.ty);
 644         let ptr = place.ptr.to_ptr()?;
 645         if mutability.is_none() {
 646             // No further checks on raw derefs -- only the access itself will be checked.
 647             return Ok(());
 648         }
 649
 650         // Get the allocation
 651         let alloc = this.memory().get(ptr.alloc_id)?;
 652         alloc.check_bounds(this, ptr, size)?;
 653         // If we got here, we do some checking, *but* we leave the tag unchanged.
 654         if let Borrow::Alias(Some(_)) = ptr.tag {
 655             assert_eq!(mutability, Some(MutImmutable));
 656             // We need a frozen-sensitive check
 657             this.visit_freeze_sensitive(place, size, |cur_ptr, size, frozen| {
 658                 let kind = if frozen { RefKind::Frozen } else { RefKind::Raw };
 659                 alloc.extra.deref(cur_ptr, size, kind)
 660             })?;
 661         } else {
 662             // Just treat this as one big chunk
 663             let kind = if mutability == Some(MutMutable) { RefKind::Unique } else { RefKind::Raw };
 664             alloc.extra.deref(ptr, size, kind)?;
 665         }
 666
 667         // All is good
 668         Ok(())
 669     }
 670
 671     fn retag(
 672         &mut self,
 673         kind: RetagKind,
 674         place: PlaceTy<'tcx, Borrow>
 675     ) -> EvalResult<'tcx> {
 676         let this = self.eval_context_mut();
 677         // Determine mutability and whether to add a barrier.
 678         // Cannot use `builtin_deref` because that reports *immutable* for `Box`,
 679         // making it useless.
 680         fn qualify(ty: ty::Ty<'_>, kind: RetagKind) -> Option<(Option<Mutability>, bool)> {
 681             match ty.sty {
 682                 // References are simple
 683                 ty::Ref(_, _, mutbl) => Some((Some(mutbl), kind == RetagKind::FnEntry)),
 684                 // Raw pointers need to be enabled
 685                 ty::RawPtr(..) if kind == RetagKind::Raw => Some((None, false)),
 686                 // Boxes do not get a barrier: Barriers reflect that references outlive the call
 687                 // they were passed in to; that's just not the case for boxes.
 688                 ty::Adt(..) if ty.is_box() => Some((Some(MutMutable), false)),
 689                 _ => None,
 690             }
 691         }
 692
 693         // We need a visitor to visit all references.  However, that requires
 694         // a `MemPlace`, so we have a fast path for reference types that
 695         // avoids allocating.
 696         if let Some((mutbl, barrier)) = qualify(place.layout.ty, kind) {
 697             // fast path
 698             let val = this.read_immediate(this.place_to_op(place)?)?;
 699             let val = this.retag_reference(val, mutbl, barrier, kind == RetagKind::TwoPhase)?;
 700             this.write_immediate(val, place)?;
 701             return Ok(());
 702         }
 703         let place = this.force_allocation(place)?;
 704
 705         let mut visitor = RetagVisitor { ecx: this, kind };
 706         visitor.visit_value(place)?;
 707
 708         // The actual visitor
 709         struct RetagVisitor<'ecx, 'a, 'mir, 'tcx> {
 710             ecx: &'ecx mut MiriEvalContext<'a, 'mir, 'tcx>,
 711             kind: RetagKind,
 712         }
 713         impl<'ecx, 'a, 'mir, 'tcx>
 714             MutValueVisitor<'a, 'mir, 'tcx, Evaluator<'tcx>>
 715         for
 716             RetagVisitor<'ecx, 'a, 'mir, 'tcx>
 717         {
 718             type V = MPlaceTy<'tcx, Borrow>;
 719
 720             #[inline(always)]
 721             fn ecx(&mut self) -> &mut MiriEvalContext<'a, 'mir, 'tcx> {
 722                 &mut self.ecx
 723             }
 724
 725             // Primitives of reference type, that is the one thing we are interested in.
 726             fn visit_primitive(&mut self, place: MPlaceTy<'tcx, Borrow>) -> EvalResult<'tcx>
 727             {
 728                 // Cannot use `builtin_deref` because that reports *immutable* for `Box`,
 729                 // making it useless.
 730                 if let Some((mutbl, barrier)) = qualify(place.layout.ty, self.kind) {
 731                     let val = self.ecx.read_immediate(place.into())?;
 732                     let val = self.ecx.retag_reference(
 733                         val,
 734                         mutbl,
 735                         barrier,
 736                         self.kind == RetagKind::TwoPhase
 737                     )?;
 738                     self.ecx.write_immediate(val, place.into())?;
 739                 }
 740                 Ok(())
 741             }
 742         }
 743
 744         Ok(())
 745     }
 746 }