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