src/librustc_mir/interpret/memory.rs

   1 //! The memory subsystem.
   2 //!
   3 //! Generally, we use `Pointer` to denote memory addresses. However, some operations
   4 //! have a "size"-like parameter, and they take `Scalar` for the address because
   5 //! if the size is 0, then the pointer can also be a (properly aligned, non-NULL)
   6 //! integer. It is crucial that these operations call `check_align` *before*
   7 //! short-circuiting the empty case!
   8
   9 use std::collections::VecDeque;
  10 use std::ptr;
  11 use std::borrow::Cow;
  12
  13 use rustc::ty::{self, Instance, ParamEnv, query::TyCtxtAt};
  14 use rustc::ty::layout::{Align, TargetDataLayout, Size, HasDataLayout};
  15 use rustc_data_structures::fx::{FxHashSet, FxHashMap};
  16
  17 use syntax::ast::Mutability;
  18
  19 use super::{
  20     Pointer, AllocId, Allocation, GlobalId, AllocationExtra,
  21     InterpResult, Scalar, InterpError, GlobalAlloc, PointerArithmetic,
  22     Machine, AllocMap, MayLeak, ErrorHandled, CheckInAllocMsg,
  23 };
  24
  25 #[derive(Debug, PartialEq, Eq, Copy, Clone, Hash)]
  26 pub enum MemoryKind<T> {
  27     /// Error if deallocated except during a stack pop
  28     Stack,
  29     /// Error if ever deallocated
  30     Vtable,
  31     /// Additional memory kinds a machine wishes to distinguish from the builtin ones
  32     Machine(T),
  33 }
  34
  35 impl<T: MayLeak> MayLeak for MemoryKind<T> {
  36     #[inline]
  37     fn may_leak(self) -> bool {
  38         match self {
  39             MemoryKind::Stack => false,
  40             MemoryKind::Vtable => true,
  41             MemoryKind::Machine(k) => k.may_leak()
  42         }
  43     }
  44 }
  45
  46 /// Used by `get_size_and_align` to indicate whether the allocation needs to be live.
  47 #[derive(Debug, Copy, Clone)]
  48 pub enum AllocCheck {
  49     /// Allocation must be live and not a function pointer.
  50     Dereferencable,
  51     /// Allocations needs to be live, but may be a function pointer.
  52     Live,
  53     /// Allocation may be dead.
  54     MaybeDead,
  55 }
  56
  57 // `Memory` has to depend on the `Machine` because some of its operations
  58 // (e.g., `get`) call a `Machine` hook.
  59 pub struct Memory<'mir, 'tcx, M: Machine<'mir, 'tcx>> {
  60     /// Allocations local to this instance of the miri engine. The kind
  61     /// helps ensure that the same mechanism is used for allocation and
  62     /// deallocation. When an allocation is not found here, it is a
  63     /// static and looked up in the `tcx` for read access. Some machines may
  64     /// have to mutate this map even on a read-only access to a static (because
  65     /// they do pointer provenance tracking and the allocations in `tcx` have
  66     /// the wrong type), so we let the machine override this type.
  67     /// Either way, if the machine allows writing to a static, doing so will
  68     /// create a copy of the static allocation here.
  69     // FIXME: this should not be public, but interning currently needs access to it
  70     pub(super) alloc_map: M::MemoryMap,
  71
  72     /// To be able to compare pointers with NULL, and to check alignment for accesses
  73     /// to ZSTs (where pointers may dangle), we keep track of the size even for allocations
  74     /// that do not exist any more.
  75     pub(super) dead_alloc_map: FxHashMap<AllocId, (Size, Align)>,
  76
  77     /// Extra data added by the machine.
  78     pub extra: M::MemoryExtra,
  79
  80     /// Lets us implement `HasDataLayout`, which is awfully convenient.
  81     pub(super) tcx: TyCtxtAt<'tcx>,
  82 }
  83
  84 impl<'mir, 'tcx, M: Machine<'mir, 'tcx>> HasDataLayout for Memory<'mir, 'tcx, M> {
  85     #[inline]
  86     fn data_layout(&self) -> &TargetDataLayout {
  87         &self.tcx.data_layout
  88     }
  89 }
  90
  91 // FIXME: Really we shouldn't clone memory, ever. Snapshot machinery should instead
  92 // carefully copy only the reachable parts.
  93 impl<'mir, 'tcx, M> Clone for Memory<'mir, 'tcx, M>
  94 where
  95     M: Machine<'mir, 'tcx, PointerTag = (), AllocExtra = (), MemoryExtra = ()>,
  96     M::MemoryMap: AllocMap<AllocId, (MemoryKind<M::MemoryKinds>, Allocation)>,
  97 {
  98     fn clone(&self) -> Self {
  99         Memory {
 100             alloc_map: self.alloc_map.clone(),
 101             dead_alloc_map: self.dead_alloc_map.clone(),
 102             extra: (),
 103             tcx: self.tcx,
 104         }
 105     }
 106 }
 107
 108 impl<'mir, 'tcx, M: Machine<'mir, 'tcx>> Memory<'mir, 'tcx, M> {
 109     pub fn new(tcx: TyCtxtAt<'tcx>) -> Self {
 110         Memory {
 111             alloc_map: M::MemoryMap::default(),
 112             dead_alloc_map: FxHashMap::default(),
 113             extra: M::MemoryExtra::default(),
 114             tcx,
 115         }
 116     }
 117
 118     #[inline]
 119     pub fn tag_static_base_pointer(&self, ptr: Pointer) -> Pointer<M::PointerTag> {
 120         ptr.with_tag(M::tag_static_base_pointer(ptr.alloc_id, &self))
 121     }
 122
 123     pub fn create_fn_alloc(&mut self, instance: Instance<'tcx>) -> Pointer<M::PointerTag> {
 124         let id = self.tcx.alloc_map.lock().create_fn_alloc(instance);
 125         self.tag_static_base_pointer(Pointer::from(id))
 126     }
 127
 128     pub fn allocate(
 129         &mut self,
 130         size: Size,
 131         align: Align,
 132         kind: MemoryKind<M::MemoryKinds>,
 133     ) -> Pointer<M::PointerTag> {
 134         let alloc = Allocation::undef(size, align);
 135         self.allocate_with(alloc, kind)
 136     }
 137
 138     pub fn allocate_static_bytes(
 139         &mut self,
 140         bytes: &[u8],
 141         kind: MemoryKind<M::MemoryKinds>,
 142     ) -> Pointer<M::PointerTag> {
 143         let alloc = Allocation::from_byte_aligned_bytes(bytes);
 144         self.allocate_with(alloc, kind)
 145     }
 146
 147     pub fn allocate_with(
 148         &mut self,
 149         alloc: Allocation,
 150         kind: MemoryKind<M::MemoryKinds>,
 151     ) -> Pointer<M::PointerTag> {
 152         let id = self.tcx.alloc_map.lock().reserve();
 153         let (alloc, tag) = M::tag_allocation(id, Cow::Owned(alloc), Some(kind), &self);
 154         self.alloc_map.insert(id, (kind, alloc.into_owned()));
 155         Pointer::from(id).with_tag(tag)
 156     }
 157
 158     pub fn reallocate(
 159         &mut self,
 160         ptr: Pointer<M::PointerTag>,
 161         old_size_and_align: Option<(Size, Align)>,
 162         new_size: Size,
 163         new_align: Align,
 164         kind: MemoryKind<M::MemoryKinds>,
 165     ) -> InterpResult<'tcx, Pointer<M::PointerTag>> {
 166         if ptr.offset.bytes() != 0 {
 167             return err!(ReallocateNonBasePtr);
 168         }
 169
 170         // For simplicities' sake, we implement reallocate as "alloc, copy, dealloc".
 171         // This happens so rarely, the perf advantage is outweighed by the maintenance cost.
 172         let new_ptr = self.allocate(new_size, new_align, kind);
 173         let old_size = match old_size_and_align {
 174             Some((size, _align)) => size,
 175             None => Size::from_bytes(self.get(ptr.alloc_id)?.bytes.len() as u64),
 176         };
 177         self.copy(
 178             ptr.into(),
 179             Align::from_bytes(1).unwrap(), // old_align anyway gets checked below by `deallocate`
 180             new_ptr.into(),
 181             new_align,
 182             old_size.min(new_size),
 183             /*nonoverlapping*/ true,
 184         )?;
 185         self.deallocate(ptr, old_size_and_align, kind)?;
 186
 187         Ok(new_ptr)
 188     }
 189
 190     /// Deallocate a local, or do nothing if that local has been made into a static
 191     pub fn deallocate_local(&mut self, ptr: Pointer<M::PointerTag>) -> InterpResult<'tcx> {
 192         // The allocation might be already removed by static interning.
 193         // This can only really happen in the CTFE instance, not in miri.
 194         if self.alloc_map.contains_key(&ptr.alloc_id) {
 195             self.deallocate(ptr, None, MemoryKind::Stack)
 196         } else {
 197             Ok(())
 198         }
 199     }
 200
 201     pub fn deallocate(
 202         &mut self,
 203         ptr: Pointer<M::PointerTag>,
 204         old_size_and_align: Option<(Size, Align)>,
 205         kind: MemoryKind<M::MemoryKinds>,
 206     ) -> InterpResult<'tcx> {
 207         trace!("deallocating: {}", ptr.alloc_id);
 208
 209         if ptr.offset.bytes() != 0 {
 210             return err!(DeallocateNonBasePtr);
 211         }
 212
 213         let (alloc_kind, mut alloc) = match self.alloc_map.remove(&ptr.alloc_id) {
 214             Some(alloc) => alloc,
 215             None => {
 216                 // Deallocating static memory -- always an error
 217                 return match self.tcx.alloc_map.lock().get(ptr.alloc_id) {
 218                     Some(GlobalAlloc::Function(..)) => err!(DeallocatedWrongMemoryKind(
 219                         "function".to_string(),
 220                         format!("{:?}", kind),
 221                     )),
 222                     Some(GlobalAlloc::Static(..)) |
 223                     Some(GlobalAlloc::Memory(..)) => err!(DeallocatedWrongMemoryKind(
 224                         "static".to_string(),
 225                         format!("{:?}", kind),
 226                     )),
 227                     None => err!(DoubleFree)
 228                 }
 229             }
 230         };
 231
 232         if alloc_kind != kind {
 233             return err!(DeallocatedWrongMemoryKind(
 234                 format!("{:?}", alloc_kind),
 235                 format!("{:?}", kind),
 236             ));
 237         }
 238         if let Some((size, align)) = old_size_and_align {
 239             if size.bytes() != alloc.bytes.len() as u64 || align != alloc.align {
 240                 let bytes = Size::from_bytes(alloc.bytes.len() as u64);
 241                 return err!(IncorrectAllocationInformation(size,
 242                                                            bytes,
 243                                                            align,
 244                                                            alloc.align));
 245             }
 246         }
 247
 248         // Let the machine take some extra action
 249         let size = Size::from_bytes(alloc.bytes.len() as u64);
 250         AllocationExtra::memory_deallocated(&mut alloc, ptr, size)?;
 251
 252         // Don't forget to remember size and align of this now-dead allocation
 253         let old = self.dead_alloc_map.insert(
 254             ptr.alloc_id,
 255             (Size::from_bytes(alloc.bytes.len() as u64), alloc.align)
 256         );
 257         if old.is_some() {
 258             bug!("Nothing can be deallocated twice");
 259         }
 260
 261         Ok(())
 262     }
 263
 264     /// Check if the given scalar is allowed to do a memory access of given `size`
 265     /// and `align`. On success, returns `None` for zero-sized accesses (where
 266     /// nothing else is left to do) and a `Pointer` to use for the actual access otherwise.
 267     /// Crucially, if the input is a `Pointer`, we will test it for liveness
 268     /// *even of* the size is 0.
 269     ///
 270     /// Everyone accessing memory based on a `Scalar` should use this method to get the
 271     /// `Pointer` they need. And even if you already have a `Pointer`, call this method
 272     /// to make sure it is sufficiently aligned and not dangling.  Not doing that may
 273     /// cause ICEs.
 274     pub fn check_ptr_access(
 275         &self,
 276         sptr: Scalar<M::PointerTag>,
 277         size: Size,
 278         align: Align,
 279     ) -> InterpResult<'tcx, Option<Pointer<M::PointerTag>>> {
 280         fn check_offset_align(offset: u64, align: Align) -> InterpResult<'static> {
 281             if offset % align.bytes() == 0 {
 282                 Ok(())
 283             } else {
 284                 // The biggest power of two through which `offset` is divisible.
 285                 let offset_pow2 = 1 << offset.trailing_zeros();
 286                 err!(AlignmentCheckFailed {
 287                     has: Align::from_bytes(offset_pow2).unwrap(),
 288                     required: align,
 289                 })
 290             }
 291         }
 292
 293         // Normalize to a `Pointer` if we definitely need one.
 294         let normalized = if size.bytes() == 0 {
 295             // Can be an integer, just take what we got.  We do NOT `force_bits` here;
 296             // if this is already a `Pointer` we want to do the bounds checks!
 297             sptr
 298         } else {
 299             // A "real" access, we must get a pointer.
 300             Scalar::Ptr(self.force_ptr(sptr)?)
 301         };
 302         Ok(match normalized.to_bits_or_ptr(self.pointer_size(), self) {
 303             Ok(bits) => {
 304                 let bits = bits as u64; // it's ptr-sized
 305                 assert!(size.bytes() == 0);
 306                 // Must be non-NULL and aligned.
 307                 if bits == 0 {
 308                     return err!(InvalidNullPointerUsage);
 309                 }
 310                 check_offset_align(bits, align)?;
 311                 None
 312             }
 313             Err(ptr) => {
 314                 let (allocation_size, alloc_align) =
 315                     self.get_size_and_align(ptr.alloc_id, AllocCheck::Dereferencable)?;
 316                 // Test bounds. This also ensures non-NULL.
 317                 // It is sufficient to check this for the end pointer. The addition
 318                 // checks for overflow.
 319                 let end_ptr = ptr.offset(size, self)?;
 320                 end_ptr.check_in_alloc(allocation_size, CheckInAllocMsg::MemoryAccessTest)?;
 321                 // Test align. Check this last; if both bounds and alignment are violated
 322                 // we want the error to be about the bounds.
 323                 if alloc_align.bytes() < align.bytes() {
 324                     // The allocation itself is not aligned enough.
 325                     // FIXME: Alignment check is too strict, depending on the base address that
 326                     // got picked we might be aligned even if this check fails.
 327                     // We instead have to fall back to converting to an integer and checking
 328                     // the "real" alignment.
 329                     return err!(AlignmentCheckFailed {
 330                         has: alloc_align,
 331                         required: align,
 332                     });
 333                 }
 334                 check_offset_align(ptr.offset.bytes(), align)?;
 335
 336                 // We can still be zero-sized in this branch, in which case we have to
 337                 // return `None`.
 338                 if size.bytes() == 0 { None } else { Some(ptr) }
 339             }
 340         })
 341     }
 342
 343     /// Test if the pointer might be NULL.
 344     pub fn ptr_may_be_null(
 345         &self,
 346         ptr: Pointer<M::PointerTag>,
 347     ) -> bool {
 348         let (size, _align) = self.get_size_and_align(ptr.alloc_id, AllocCheck::MaybeDead)
 349             .expect("alloc info with MaybeDead cannot fail");
 350         ptr.check_in_alloc(size, CheckInAllocMsg::NullPointerTest).is_err()
 351     }
 352 }
 353
 354 /// Allocation accessors
 355 impl<'mir, 'tcx, M: Machine<'mir, 'tcx>> Memory<'mir, 'tcx, M> {
 356     /// Helper function to obtain the global (tcx) allocation for a static.
 357     /// This attempts to return a reference to an existing allocation if
 358     /// one can be found in `tcx`. That, however, is only possible if `tcx` and
 359     /// this machine use the same pointer tag, so it is indirected through
 360     /// `M::tag_allocation`.
 361     ///
 362     /// Notice that every static has two `AllocId` that will resolve to the same
 363     /// thing here: one maps to `GlobalAlloc::Static`, this is the "lazy" ID,
 364     /// and the other one is maps to `GlobalAlloc::Memory`, this is returned by
 365     /// `const_eval_raw` and it is the "resolved" ID.
 366     /// The resolved ID is never used by the interpreted progrma, it is hidden.
 367     /// The `GlobalAlloc::Memory` branch here is still reachable though; when a static
 368     /// contains a reference to memory that was created during its evaluation (i.e., not to
 369     /// another static), those inner references only exist in "resolved" form.
 370     fn get_static_alloc(
 371         id: AllocId,
 372         tcx: TyCtxtAt<'tcx>,
 373         memory: &Memory<'mir, 'tcx, M>,
 374     ) -> InterpResult<'tcx, Cow<'tcx, Allocation<M::PointerTag, M::AllocExtra>>> {
 375         let alloc = tcx.alloc_map.lock().get(id);
 376         let alloc = match alloc {
 377             Some(GlobalAlloc::Memory(mem)) =>
 378                 Cow::Borrowed(mem),
 379             Some(GlobalAlloc::Function(..)) =>
 380                 return err!(DerefFunctionPointer),
 381             None =>
 382                 return err!(DanglingPointerDeref),
 383             Some(GlobalAlloc::Static(def_id)) => {
 384                 // We got a "lazy" static that has not been computed yet.
 385                 if tcx.is_foreign_item(def_id) {
 386                     trace!("static_alloc: foreign item {:?}", def_id);
 387                     M::find_foreign_static(def_id, tcx)?
 388                 } else {
 389                     trace!("static_alloc: Need to compute {:?}", def_id);
 390                     let instance = Instance::mono(tcx.tcx, def_id);
 391                     let gid = GlobalId {
 392                         instance,
 393                         promoted: None,
 394                     };
 395                     // use the raw query here to break validation cycles. Later uses of the static
 396                     // will call the full query anyway
 397                     let raw_const = tcx.const_eval_raw(ty::ParamEnv::reveal_all().and(gid))
 398                         .map_err(|err| {
 399                             // no need to report anything, the const_eval call takes care of that
 400                             // for statics
 401                             assert!(tcx.is_static(def_id));
 402                             match err {
 403                                 ErrorHandled::Reported => InterpError::ReferencedConstant,
 404                                 ErrorHandled::TooGeneric => InterpError::TooGeneric,
 405                             }
 406                         })?;
 407                     // Make sure we use the ID of the resolved memory, not the lazy one!
 408                     let id = raw_const.alloc_id;
 409                     let allocation = tcx.alloc_map.lock().unwrap_memory(id);
 410                     Cow::Borrowed(allocation)
 411                 }
 412             }
 413         };
 414         // We got tcx memory. Let the machine figure out whether and how to
 415         // turn that into memory with the right pointer tag.
 416         Ok(M::tag_allocation(
 417             id, // always use the ID we got as input, not the "hidden" one.
 418             alloc,
 419             M::STATIC_KIND.map(MemoryKind::Machine),
 420             memory
 421         ).0)
 422     }
 423
 424     pub fn get(
 425         &self,
 426         id: AllocId,
 427     ) -> InterpResult<'tcx, &Allocation<M::PointerTag, M::AllocExtra>> {
 428         // The error type of the inner closure here is somewhat funny.  We have two
 429         // ways of "erroring": An actual error, or because we got a reference from
 430         // `get_static_alloc` that we can actually use directly without inserting anything anywhere.
 431         // So the error type is `InterpResult<'tcx, &Allocation<M::PointerTag>>`.
 432         let a = self.alloc_map.get_or(id, || {
 433             let alloc = Self::get_static_alloc(id, self.tcx, &self).map_err(Err)?;
 434             match alloc {
 435                 Cow::Borrowed(alloc) => {
 436                     // We got a ref, cheaply return that as an "error" so that the
 437                     // map does not get mutated.
 438                     Err(Ok(alloc))
 439                 }
 440                 Cow::Owned(alloc) => {
 441                     // Need to put it into the map and return a ref to that
 442                     let kind = M::STATIC_KIND.expect(
 443                         "I got an owned allocation that I have to copy but the machine does \
 444                             not expect that to happen"
 445                     );
 446                     Ok((MemoryKind::Machine(kind), alloc))
 447                 }
 448             }
 449         });
 450         // Now unpack that funny error type
 451         match a {
 452             Ok(a) => Ok(&a.1),
 453             Err(a) => a
 454         }
 455     }
 456
 457     pub fn get_mut(
 458         &mut self,
 459         id: AllocId,
 460     ) -> InterpResult<'tcx, &mut Allocation<M::PointerTag, M::AllocExtra>> {
 461         let tcx = self.tcx;
 462         let alloc = Self::get_static_alloc(id, tcx, &self);
 463         let a = self.alloc_map.get_mut_or(id, || {
 464             // Need to make a copy, even if `get_static_alloc` is able
 465             // to give us a cheap reference.
 466             let alloc = alloc?;
 467             if alloc.mutability == Mutability::Immutable {
 468                 return err!(ModifiedConstantMemory);
 469             }
 470             match M::STATIC_KIND {
 471                 Some(kind) => Ok((MemoryKind::Machine(kind), alloc.into_owned())),
 472                 None => err!(ModifiedStatic),
 473             }
 474         });
 475         // Unpack the error type manually because type inference doesn't
 476         // work otherwise (and we cannot help it because `impl Trait`)
 477         match a {
 478             Err(e) => Err(e),
 479             Ok(a) => {
 480                 let a = &mut a.1;
 481                 if a.mutability == Mutability::Immutable {
 482                     return err!(ModifiedConstantMemory);
 483                 }
 484                 Ok(a)
 485             }
 486         }
 487     }
 488
 489     /// Obtain the size and alignment of an allocation, even if that allocation has
 490     /// been deallocated.
 491     ///
 492     /// If `liveness` is `AllocCheck::MaybeDead`, this function always returns `Ok`.
 493     pub fn get_size_and_align(
 494         &self,
 495         id: AllocId,
 496         liveness: AllocCheck,
 497     ) -> InterpResult<'static, (Size, Align)> {
 498         if let Ok(alloc) = self.get(id) {
 499             return Ok((Size::from_bytes(alloc.bytes.len() as u64), alloc.align));
 500         }
 501         // can't do this in the match argument, we may get cycle errors since the lock would get
 502         // dropped after the match.
 503         let alloc = self.tcx.alloc_map.lock().get(id);
 504         // Could also be a fn ptr or extern static
 505         match alloc {
 506             Some(GlobalAlloc::Function(..)) => {
 507                 if let AllocCheck::Dereferencable = liveness {
 508                     // The caller requested no function pointers.
 509                     err!(DerefFunctionPointer)
 510                 } else {
 511                     Ok((Size::ZERO, Align::from_bytes(1).unwrap()))
 512                 }
 513             }
 514             // `self.get` would also work, but can cause cycles if a static refers to itself
 515             Some(GlobalAlloc::Static(did)) => {
 516                 // The only way `get` couldn't have worked here is if this is an extern static
 517                 assert!(self.tcx.is_foreign_item(did));
 518                 // Use size and align of the type
 519                 let ty = self.tcx.type_of(did);
 520                 let layout = self.tcx.layout_of(ParamEnv::empty().and(ty)).unwrap();
 521                 Ok((layout.size, layout.align.abi))
 522             }
 523             _ => {
 524                 if let Ok(alloc) = self.get(id) {
 525                     Ok((Size::from_bytes(alloc.bytes.len() as u64), alloc.align))
 526                 }
 527                 else if let AllocCheck::MaybeDead = liveness {
 528                     // Deallocated pointers are allowed, we should be able to find
 529                     // them in the map.
 530                     Ok(*self.dead_alloc_map.get(&id)
 531                         .expect("deallocated pointers should all be recorded in `dead_alloc_map`"))
 532                 } else {
 533                     err!(DanglingPointerDeref)
 534                 }
 535             },
 536         }
 537     }
 538
 539     pub fn get_fn(&self, ptr: Pointer<M::PointerTag>) -> InterpResult<'tcx, Instance<'tcx>> {
 540         if ptr.offset.bytes() != 0 {
 541             return err!(InvalidFunctionPointer);
 542         }
 543         trace!("reading fn ptr: {}", ptr.alloc_id);
 544         match self.tcx.alloc_map.lock().get(ptr.alloc_id) {
 545             Some(GlobalAlloc::Function(instance)) => Ok(instance),
 546             _ => Err(InterpError::ExecuteMemory.into()),
 547         }
 548     }
 549
 550     pub fn mark_immutable(&mut self, id: AllocId) -> InterpResult<'tcx> {
 551         self.get_mut(id)?.mutability = Mutability::Immutable;
 552         Ok(())
 553     }
 554
 555     /// For debugging, print an allocation and all allocations it points to, recursively.
 556     pub fn dump_alloc(&self, id: AllocId) {
 557         self.dump_allocs(vec![id]);
 558     }
 559
 560     fn dump_alloc_helper<Tag, Extra>(
 561         &self,
 562         allocs_seen: &mut FxHashSet<AllocId>,
 563         allocs_to_print: &mut VecDeque<AllocId>,
 564         mut msg: String,
 565         alloc: &Allocation<Tag, Extra>,
 566         extra: String,
 567     ) {
 568         use std::fmt::Write;
 569
 570         let prefix_len = msg.len();
 571         let mut relocations = vec![];
 572
 573         for i in 0..(alloc.bytes.len() as u64) {
 574             let i = Size::from_bytes(i);
 575             if let Some(&(_, target_id)) = alloc.relocations.get(&i) {
 576                 if allocs_seen.insert(target_id) {
 577                     allocs_to_print.push_back(target_id);
 578                 }
 579                 relocations.push((i, target_id));
 580             }
 581             if alloc.undef_mask.is_range_defined(i, i + Size::from_bytes(1)).is_ok() {
 582                 // this `as usize` is fine, since `i` came from a `usize`
 583                 write!(msg, "{:02x} ", alloc.bytes[i.bytes() as usize]).unwrap();
 584             } else {
 585                 msg.push_str("__ ");
 586             }
 587         }
 588
 589         trace!(
 590             "{}({} bytes, alignment {}){}",
 591             msg,
 592             alloc.bytes.len(),
 593             alloc.align.bytes(),
 594             extra
 595         );
 596
 597         if !relocations.is_empty() {
 598             msg.clear();
 599             write!(msg, "{:1$}", "", prefix_len).unwrap(); // Print spaces.
 600             let mut pos = Size::ZERO;
 601             let relocation_width = (self.pointer_size().bytes() - 1) * 3;
 602             for (i, target_id) in relocations {
 603                 // this `as usize` is fine, since we can't print more chars than `usize::MAX`
 604                 write!(msg, "{:1$}", "", ((i - pos) * 3).bytes() as usize).unwrap();
 605                 let target = format!("({})", target_id);
 606                 // this `as usize` is fine, since we can't print more chars than `usize::MAX`
 607                 write!(msg, "└{0:─^1$}┘ ", target, relocation_width as usize).unwrap();
 608                 pos = i + self.pointer_size();
 609             }
 610             trace!("{}", msg);
 611         }
 612     }
 613
 614     /// For debugging, print a list of allocations and all allocations they point to, recursively.
 615     pub fn dump_allocs(&self, mut allocs: Vec<AllocId>) {
 616         if !log_enabled!(::log::Level::Trace) {
 617             return;
 618         }
 619         allocs.sort();
 620         allocs.dedup();
 621         let mut allocs_to_print = VecDeque::from(allocs);
 622         let mut allocs_seen = FxHashSet::default();
 623
 624         while let Some(id) = allocs_to_print.pop_front() {
 625             let msg = format!("Alloc {:<5} ", format!("{}:", id));
 626
 627             // normal alloc?
 628             match self.alloc_map.get_or(id, || Err(())) {
 629                 Ok((kind, alloc)) => {
 630                     let extra = match kind {
 631                         MemoryKind::Stack => " (stack)".to_owned(),
 632                         MemoryKind::Vtable => " (vtable)".to_owned(),
 633                         MemoryKind::Machine(m) => format!(" ({:?})", m),
 634                     };
 635                     self.dump_alloc_helper(
 636                         &mut allocs_seen, &mut allocs_to_print,
 637                         msg, alloc, extra
 638                     );
 639                 },
 640                 Err(()) => {
 641                     // static alloc?
 642                     match self.tcx.alloc_map.lock().get(id) {
 643                         Some(GlobalAlloc::Memory(alloc)) => {
 644                             self.dump_alloc_helper(
 645                                 &mut allocs_seen, &mut allocs_to_print,
 646                                 msg, alloc, " (immutable)".to_owned()
 647                             );
 648                         }
 649                         Some(GlobalAlloc::Function(func)) => {
 650                             trace!("{} {}", msg, func);
 651                         }
 652                         Some(GlobalAlloc::Static(did)) => {
 653                             trace!("{} {:?}", msg, did);
 654                         }
 655                         None => {
 656                             trace!("{} (deallocated)", msg);
 657                         }
 658                     }
 659                 },
 660             };
 661
 662         }
 663     }
 664
 665     pub fn leak_report(&self) -> usize {
 666         trace!("### LEAK REPORT ###");
 667         let leaks: Vec<_> = self.alloc_map.filter_map_collect(|&id, &(kind, _)| {
 668             if kind.may_leak() { None } else { Some(id) }
 669         });
 670         let n = leaks.len();
 671         self.dump_allocs(leaks);
 672         n
 673     }
 674
 675     /// This is used by [priroda](https://github.com/oli-obk/priroda)
 676     pub fn alloc_map(&self) -> &M::MemoryMap {
 677         &self.alloc_map
 678     }
 679 }
 680
 681 /// Reading and writing.
 682 impl<'mir, 'tcx, M: Machine<'mir, 'tcx>> Memory<'mir, 'tcx, M> {
 683     /// Performs appropriate bounds checks.
 684     pub fn read_bytes(
 685         &self,
 686         ptr: Scalar<M::PointerTag>,
 687         size: Size,
 688     ) -> InterpResult<'tcx, &[u8]> {
 689         let ptr = match self.check_ptr_access(ptr, size, Align::from_bytes(1).unwrap())? {
 690             Some(ptr) => ptr,
 691             None => return Ok(&[]), // zero-sized access
 692         };
 693         self.get(ptr.alloc_id)?.get_bytes(self, ptr, size)
 694     }
 695
 696     /// Performs appropriate bounds checks.
 697     pub fn copy(
 698         &mut self,
 699         src: Scalar<M::PointerTag>,
 700         src_align: Align,
 701         dest: Scalar<M::PointerTag>,
 702         dest_align: Align,
 703         size: Size,
 704         nonoverlapping: bool,
 705     ) -> InterpResult<'tcx> {
 706         self.copy_repeatedly(src, src_align, dest, dest_align, size, 1, nonoverlapping)
 707     }
 708
 709     /// Performs appropriate bounds checks.
 710     pub fn copy_repeatedly(
 711         &mut self,
 712         src: Scalar<M::PointerTag>,
 713         src_align: Align,
 714         dest: Scalar<M::PointerTag>,
 715         dest_align: Align,
 716         size: Size,
 717         length: u64,
 718         nonoverlapping: bool,
 719     ) -> InterpResult<'tcx> {
 720         // We need to check *both* before early-aborting due to the size being 0.
 721         let (src, dest) = match (self.check_ptr_access(src, size, src_align)?,
 722                 self.check_ptr_access(dest, size * length, dest_align)?)
 723         {
 724             (Some(src), Some(dest)) => (src, dest),
 725             // One of the two sizes is 0.
 726             _ => return Ok(()),
 727         };
 728
 729         // first copy the relocations to a temporary buffer, because
 730         // `get_bytes_mut` will clear the relocations, which is correct,
 731         // since we don't want to keep any relocations at the target.
 732         // (`get_bytes_with_undef_and_ptr` below checks that there are no
 733         // relocations overlapping the edges; those would not be handled correctly).
 734         let relocations = {
 735             let relocations = self.get(src.alloc_id)?.relocations(self, src, size);
 736             if relocations.is_empty() {
 737                 // nothing to copy, ignore even the `length` loop
 738                 Vec::new()
 739             } else {
 740                 let mut new_relocations = Vec::with_capacity(relocations.len() * (length as usize));
 741                 for i in 0..length {
 742                     new_relocations.extend(
 743                         relocations
 744                         .iter()
 745                         .map(|&(offset, reloc)| {
 746                             // compute offset for current repetition
 747                             let dest_offset = dest.offset + (i * size);
 748                             (
 749                                 // shift offsets from source allocation to destination allocation
 750                                 offset + dest_offset - src.offset,
 751                                 reloc,
 752                             )
 753                         })
 754                     );
 755                 }
 756
 757                 new_relocations
 758             }
 759         };
 760
 761         let tcx = self.tcx.tcx;
 762
 763         // This checks relocation edges on the src.
 764         let src_bytes = self.get(src.alloc_id)?
 765             .get_bytes_with_undef_and_ptr(&tcx, src, size)?
 766             .as_ptr();
 767         let dest_bytes = self.get_mut(dest.alloc_id)?
 768             .get_bytes_mut(&tcx, dest, size * length)?
 769             .as_mut_ptr();
 770
 771         // SAFE: The above indexing would have panicked if there weren't at least `size` bytes
 772         // behind `src` and `dest`. Also, we use the overlapping-safe `ptr::copy` if `src` and
 773         // `dest` could possibly overlap.
 774         // The pointers above remain valid even if the `HashMap` table is moved around because they
 775         // point into the `Vec` storing the bytes.
 776         unsafe {
 777             assert_eq!(size.bytes() as usize as u64, size.bytes());
 778             if src.alloc_id == dest.alloc_id {
 779                 if nonoverlapping {
 780                     if (src.offset <= dest.offset && src.offset + size > dest.offset) ||
 781                         (dest.offset <= src.offset && dest.offset + size > src.offset)
 782                     {
 783                         return err!(Intrinsic(
 784                             "copy_nonoverlapping called on overlapping ranges".to_string(),
 785                         ));
 786                     }
 787                 }
 788
 789                 for i in 0..length {
 790                     ptr::copy(src_bytes,
 791                               dest_bytes.offset((size.bytes() * i) as isize),
 792                               size.bytes() as usize);
 793                 }
 794             } else {
 795                 for i in 0..length {
 796                     ptr::copy_nonoverlapping(src_bytes,
 797                                              dest_bytes.offset((size.bytes() * i) as isize),
 798                                              size.bytes() as usize);
 799                 }
 800             }
 801         }
 802
 803         // copy definedness to the destination
 804         self.copy_undef_mask(src, dest, size, length)?;
 805         // copy the relocations to the destination
 806         self.get_mut(dest.alloc_id)?.relocations.insert_presorted(relocations);
 807
 808         Ok(())
 809     }
 810 }
 811
 812 /// Undefined bytes
 813 impl<'mir, 'tcx, M: Machine<'mir, 'tcx>> Memory<'mir, 'tcx, M> {
 814     // FIXME: Add a fast version for the common, nonoverlapping case
 815     fn copy_undef_mask(
 816         &mut self,
 817         src: Pointer<M::PointerTag>,
 818         dest: Pointer<M::PointerTag>,
 819         size: Size,
 820         repeat: u64,
 821     ) -> InterpResult<'tcx> {
 822         // The bits have to be saved locally before writing to dest in case src and dest overlap.
 823         assert_eq!(size.bytes() as usize as u64, size.bytes());
 824
 825         let undef_mask = &self.get(src.alloc_id)?.undef_mask;
 826
 827         // Since we are copying `size` bytes from `src` to `dest + i * size` (`for i in 0..repeat`),
 828         // a naive undef mask copying algorithm would repeatedly have to read the undef mask from
 829         // the source and write it to the destination. Even if we optimized the memory accesses,
 830         // we'd be doing all of this `repeat` times.
 831         // Therefor we precompute a compressed version of the undef mask of the source value and
 832         // then write it back `repeat` times without computing any more information from the source.
 833
 834         // a precomputed cache for ranges of defined/undefined bits
 835         // 0000010010001110 will become
 836         // [5, 1, 2, 1, 3, 3, 1]
 837         // where each element toggles the state
 838         let mut ranges = smallvec::SmallVec::<[u64; 1]>::new();
 839         let first = undef_mask.get(src.offset);
 840         let mut cur_len = 1;
 841         let mut cur = first;
 842         for i in 1..size.bytes() {
 843             // FIXME: optimize to bitshift the current undef block's bits and read the top bit
 844             if undef_mask.get(src.offset + Size::from_bytes(i)) == cur {
 845                 cur_len += 1;
 846             } else {
 847                 ranges.push(cur_len);
 848                 cur_len = 1;
 849                 cur = !cur;
 850             }
 851         }
 852
 853         // now fill in all the data
 854         let dest_allocation = self.get_mut(dest.alloc_id)?;
 855         // an optimization where we can just overwrite an entire range of definedness bits if
 856         // they are going to be uniformly `1` or `0`.
 857         if ranges.is_empty() {
 858             dest_allocation.undef_mask.set_range_inbounds(
 859                 dest.offset,
 860                 dest.offset + size * repeat,
 861                 first,
 862             );
 863             return Ok(())
 864         }
 865
 866         // remember to fill in the trailing bits
 867         ranges.push(cur_len);
 868
 869         for mut j in 0..repeat {
 870             j *= size.bytes();
 871             j += dest.offset.bytes();
 872             let mut cur = first;
 873             for range in &ranges {
 874                 let old_j = j;
 875                 j += range;
 876                 dest_allocation.undef_mask.set_range_inbounds(
 877                     Size::from_bytes(old_j),
 878                     Size::from_bytes(j),
 879                     cur,
 880                 );
 881                 cur = !cur;
 882             }
 883         }
 884         Ok(())
 885     }
 886
 887     pub fn force_ptr(
 888         &self,
 889         scalar: Scalar<M::PointerTag>,
 890     ) -> InterpResult<'tcx, Pointer<M::PointerTag>> {
 891         match scalar {
 892             Scalar::Ptr(ptr) => Ok(ptr),
 893             _ => M::int_to_ptr(scalar.to_usize(self)?, self)
 894         }
 895     }
 896
 897     pub fn force_bits(
 898         &self,
 899         scalar: Scalar<M::PointerTag>,
 900         size: Size
 901     ) -> InterpResult<'tcx, u128> {
 902         match scalar.to_bits_or_ptr(size, self) {
 903             Ok(bits) => Ok(bits),
 904             Err(ptr) => Ok(M::ptr_to_int(ptr, self)? as u128)
 905         }
 906     }
 907 }