src/librustc_mir/interpret/memory.rs

   1 // Copyright 2018 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! The memory subsystem.
  12 //!
  13 //! Generally, we use `Pointer` to denote memory addresses. However, some operations
  14 //! have a "size"-like parameter, and they take `Scalar` for the address because
  15 //! if the size is 0, then the pointer can also be a (properly aligned, non-NULL)
  16 //! integer.  It is crucial that these operations call `check_align` *before*
  17 //! short-circuiting the empty case!
  18
  19 use std::collections::VecDeque;
  20 use std::ptr;
  21
  22 use rustc::ty::{self, Instance, query::TyCtxtAt};
  23 use rustc::ty::layout::{self, Align, TargetDataLayout, Size, HasDataLayout};
  24 use rustc::mir::interpret::{Pointer, AllocId, Allocation, ConstValue, ScalarMaybeUndef, GlobalId,
  25                             EvalResult, Scalar, EvalErrorKind, AllocType, PointerArithmetic,
  26                             truncate};
  27 pub use rustc::mir::interpret::{write_target_uint, read_target_uint};
  28 use rustc_data_structures::fx::{FxHashSet, FxHashMap};
  29
  30 use syntax::ast::Mutability;
  31
  32 use super::Machine;
  33
  34 #[derive(Debug, PartialEq, Eq, Copy, Clone, Hash)]
  35 pub enum MemoryKind<T> {
  36     /// Error if deallocated except during a stack pop
  37     Stack,
  38     /// Additional memory kinds a machine wishes to distinguish from the builtin ones
  39     Machine(T),
  40 }
  41
  42 #[derive(Clone)]
  43 pub struct Memory<'a, 'mir, 'tcx: 'a + 'mir, M: Machine<'mir, 'tcx>> {
  44     /// Additional data required by the Machine
  45     pub data: M::MemoryData,
  46
  47     /// Allocations local to this instance of the miri engine.  The kind
  48     /// helps ensure that the same mechanism is used for allocation and
  49     /// deallocation.  When an allocation is not found here, it is a
  50     /// static and looked up in the `tcx` for read access.  Writing to
  51     /// a static creates a copy here, in the machine.
  52     alloc_map: FxHashMap<AllocId, (MemoryKind<M::MemoryKinds>, Allocation)>,
  53
  54     /// To be able to compare pointers with NULL, and to check alignment for accesses
  55     /// to ZSTs (where pointers may dangle), we keep track of the size even for allocations
  56     /// that do not exist any more.
  57     dead_alloc_map: FxHashMap<AllocId, (Size, Align)>,
  58
  59     pub tcx: TyCtxtAt<'a, 'tcx, 'tcx>,
  60 }
  61
  62 impl<'a, 'mir, 'tcx, M: Machine<'mir, 'tcx>> HasDataLayout for &'a Memory<'a, 'mir, 'tcx, M> {
  63     #[inline]
  64     fn data_layout(&self) -> &TargetDataLayout {
  65         &self.tcx.data_layout
  66     }
  67 }
  68 impl<'a, 'b, 'c, 'mir, 'tcx, M: Machine<'mir, 'tcx>> HasDataLayout
  69     for &'b &'c mut Memory<'a, 'mir, 'tcx, M>
  70 {
  71     #[inline]
  72     fn data_layout(&self) -> &TargetDataLayout {
  73         &self.tcx.data_layout
  74     }
  75 }
  76
  77 impl<'a, 'mir, 'tcx, M: Machine<'mir, 'tcx>> Memory<'a, 'mir, 'tcx, M> {
  78     pub fn new(tcx: TyCtxtAt<'a, 'tcx, 'tcx>, data: M::MemoryData) -> Self {
  79         Memory {
  80             data,
  81             alloc_map: FxHashMap::default(),
  82             dead_alloc_map: FxHashMap::default(),
  83             tcx,
  84         }
  85     }
  86
  87     pub fn create_fn_alloc(&mut self, instance: Instance<'tcx>) -> Pointer {
  88         self.tcx.alloc_map.lock().create_fn_alloc(instance).into()
  89     }
  90
  91     pub fn allocate_static_bytes(&mut self, bytes: &[u8]) -> Pointer {
  92         self.tcx.allocate_bytes(bytes).into()
  93     }
  94
  95     pub fn allocate_with(
  96         &mut self,
  97         alloc: Allocation,
  98         kind: MemoryKind<M::MemoryKinds>,
  99     ) -> EvalResult<'tcx, AllocId> {
 100         let id = self.tcx.alloc_map.lock().reserve();
 101         self.alloc_map.insert(id, (kind, alloc));
 102         Ok(id)
 103     }
 104
 105     pub fn allocate(
 106         &mut self,
 107         size: Size,
 108         align: Align,
 109         kind: MemoryKind<M::MemoryKinds>,
 110     ) -> EvalResult<'tcx, Pointer> {
 111         self.allocate_with(Allocation::undef(size, align), kind).map(Pointer::from)
 112     }
 113
 114     pub fn reallocate(
 115         &mut self,
 116         ptr: Pointer,
 117         old_size: Size,
 118         old_align: Align,
 119         new_size: Size,
 120         new_align: Align,
 121         kind: MemoryKind<M::MemoryKinds>,
 122     ) -> EvalResult<'tcx, Pointer> {
 123         if ptr.offset.bytes() != 0 {
 124             return err!(ReallocateNonBasePtr);
 125         }
 126
 127         // For simplicities' sake, we implement reallocate as "alloc, copy, dealloc"
 128         let new_ptr = self.allocate(new_size, new_align, kind)?;
 129         self.copy(
 130             ptr.into(),
 131             old_align,
 132             new_ptr.into(),
 133             new_align,
 134             old_size.min(new_size),
 135             /*nonoverlapping*/ true,
 136         )?;
 137         self.deallocate(ptr, Some((old_size, old_align)), kind)?;
 138
 139         Ok(new_ptr)
 140     }
 141
 142     /// Deallocate a local, or do nothing if that local has been made into a static
 143     pub fn deallocate_local(&mut self, ptr: Pointer) -> EvalResult<'tcx> {
 144         // The allocation might be already removed by static interning.
 145         // This can only really happen in the CTFE instance, not in miri.
 146         if self.alloc_map.contains_key(&ptr.alloc_id) {
 147             self.deallocate(ptr, None, MemoryKind::Stack)
 148         } else {
 149             Ok(())
 150         }
 151     }
 152
 153     pub fn deallocate(
 154         &mut self,
 155         ptr: Pointer,
 156         size_and_align: Option<(Size, Align)>,
 157         kind: MemoryKind<M::MemoryKinds>,
 158     ) -> EvalResult<'tcx> {
 159         debug!("deallocating: {}", ptr.alloc_id);
 160
 161         if ptr.offset.bytes() != 0 {
 162             return err!(DeallocateNonBasePtr);
 163         }
 164
 165         let (alloc_kind, alloc) = match self.alloc_map.remove(&ptr.alloc_id) {
 166             Some(alloc) => alloc,
 167             None => {
 168                 // Deallocating static memory -- always an error
 169                 return match self.tcx.alloc_map.lock().get(ptr.alloc_id) {
 170                     Some(AllocType::Function(..)) => err!(DeallocatedWrongMemoryKind(
 171                         "function".to_string(),
 172                         format!("{:?}", kind),
 173                     )),
 174                     Some(AllocType::Static(..)) |
 175                     Some(AllocType::Memory(..)) => err!(DeallocatedWrongMemoryKind(
 176                         "static".to_string(),
 177                         format!("{:?}", kind),
 178                     )),
 179                     None => err!(DoubleFree)
 180                 }
 181             }
 182         };
 183
 184         if alloc_kind != kind {
 185             return err!(DeallocatedWrongMemoryKind(
 186                 format!("{:?}", alloc_kind),
 187                 format!("{:?}", kind),
 188             ));
 189         }
 190         if let Some((size, align)) = size_and_align {
 191             if size.bytes() != alloc.bytes.len() as u64 || align != alloc.align {
 192                 let bytes = Size::from_bytes(alloc.bytes.len() as u64);
 193                 return err!(IncorrectAllocationInformation(size,
 194                                                            bytes,
 195                                                            align,
 196                                                            alloc.align));
 197             }
 198         }
 199
 200         // Don't forget to remember size and align of this now-dead allocation
 201         let old = self.dead_alloc_map.insert(
 202             ptr.alloc_id,
 203             (Size::from_bytes(alloc.bytes.len() as u64), alloc.align)
 204         );
 205         if old.is_some() {
 206             bug!("Nothing can be deallocated twice");
 207         }
 208
 209         Ok(())
 210     }
 211
 212     /// Check that the pointer is aligned AND non-NULL. This supports ZSTs in two ways:
 213     /// You can pass a scalar, and a `Pointer` does not have to actually still be allocated.
 214     pub fn check_align(&self, ptr: Scalar, required_align: Align) -> EvalResult<'tcx> {
 215         // Check non-NULL/Undef, extract offset
 216         let (offset, alloc_align) = match ptr {
 217             Scalar::Ptr(ptr) => {
 218                 let (size, align) = self.get_size_and_align(ptr.alloc_id)?;
 219                 // check this is not NULL -- which we can ensure only if this is in-bounds
 220                 // of some (potentially dead) allocation.
 221                 if ptr.offset > size {
 222                     return err!(PointerOutOfBounds {
 223                         ptr,
 224                         access: true,
 225                         allocation_size: size,
 226                     });
 227                 };
 228                 // keep data for alignment check
 229                 (ptr.offset.bytes(), align)
 230             }
 231             Scalar::Bits { bits, size } => {
 232                 assert_eq!(size as u64, self.pointer_size().bytes());
 233                 assert!(bits < (1u128 << self.pointer_size().bits()));
 234                 // check this is not NULL
 235                 if bits == 0 {
 236                     return err!(InvalidNullPointerUsage);
 237                 }
 238                 // the "base address" is 0 and hence always aligned
 239                 (bits as u64, required_align)
 240             }
 241         };
 242         // Check alignment
 243         if alloc_align.abi() < required_align.abi() {
 244             return err!(AlignmentCheckFailed {
 245                 has: alloc_align,
 246                 required: required_align,
 247             });
 248         }
 249         if offset % required_align.abi() == 0 {
 250             Ok(())
 251         } else {
 252             let has = offset % required_align.abi();
 253             err!(AlignmentCheckFailed {
 254                 has: Align::from_bytes(has, has).unwrap(),
 255                 required: required_align,
 256             })
 257         }
 258     }
 259
 260     /// Check if the pointer is "in-bounds". Notice that a pointer pointing at the end
 261     /// of an allocation (i.e., at the first *inaccessible* location) *is* considered
 262     /// in-bounds!  This follows C's/LLVM's rules.  The `access` boolean is just used
 263     /// for the error message.
 264     /// If you want to check bounds before doing a memory access, be sure to
 265     /// check the pointer one past the end of your access, then everything will
 266     /// work out exactly.
 267     pub fn check_bounds(&self, ptr: Pointer, access: bool) -> EvalResult<'tcx> {
 268         let alloc = self.get(ptr.alloc_id)?;
 269         let allocation_size = alloc.bytes.len() as u64;
 270         if ptr.offset.bytes() > allocation_size {
 271             return err!(PointerOutOfBounds {
 272                 ptr,
 273                 access,
 274                 allocation_size: Size::from_bytes(allocation_size),
 275             });
 276         }
 277         Ok(())
 278     }
 279 }
 280
 281 /// Allocation accessors
 282 impl<'a, 'mir, 'tcx, M: Machine<'mir, 'tcx>> Memory<'a, 'mir, 'tcx, M> {
 283     /// Helper function to obtain the global (tcx) allocation for a static
 284     fn get_static_alloc(
 285         tcx: TyCtxtAt<'a, 'tcx, 'tcx>,
 286         id: AllocId,
 287     ) -> EvalResult<'tcx, &'tcx Allocation> {
 288         let alloc = tcx.alloc_map.lock().get(id);
 289         let def_id = match alloc {
 290             Some(AllocType::Memory(mem)) => {
 291                 return Ok(mem)
 292             }
 293             Some(AllocType::Function(..)) => {
 294                 return err!(DerefFunctionPointer)
 295             }
 296             Some(AllocType::Static(did)) => {
 297                 did
 298             }
 299             None =>
 300                 return err!(DanglingPointerDeref),
 301         };
 302         // We got a "lazy" static that has not been computed yet, do some work
 303         trace!("static_alloc: Need to compute {:?}", def_id);
 304         if tcx.is_foreign_item(def_id) {
 305             return M::find_foreign_static(tcx, def_id);
 306         }
 307         let instance = Instance::mono(tcx.tcx, def_id);
 308         let gid = GlobalId {
 309             instance,
 310             promoted: None,
 311         };
 312         tcx.const_eval(ty::ParamEnv::reveal_all().and(gid)).map_err(|err| {
 313             // no need to report anything, the const_eval call takes care of that for statics
 314             assert!(tcx.is_static(def_id).is_some());
 315             EvalErrorKind::ReferencedConstant(err).into()
 316         }).map(|const_val| {
 317             if let ConstValue::ByRef(_, allocation, _) = const_val.val {
 318                 allocation
 319             } else {
 320                 bug!("Matching on non-ByRef static")
 321             }
 322         })
 323     }
 324
 325     pub fn get(&self, id: AllocId) -> EvalResult<'tcx, &Allocation> {
 326         match self.alloc_map.get(&id) {
 327             // Normal alloc?
 328             Some(alloc) => Ok(&alloc.1),
 329             // Static. No need to make any copies, just provide read access to the global static
 330             // memory in tcx.
 331             None => Self::get_static_alloc(self.tcx, id),
 332         }
 333     }
 334
 335     pub fn get_size_and_align(&self, id: AllocId) -> EvalResult<'tcx, (Size, Align)> {
 336         Ok(match self.get(id) {
 337             Ok(alloc) => (Size::from_bytes(alloc.bytes.len() as u64), alloc.align),
 338             Err(err) => match err.kind {
 339                 EvalErrorKind::DanglingPointerDeref =>
 340                     // This should be in the dead allocation map
 341                     *self.dead_alloc_map.get(&id).expect(
 342                         "allocation missing in dead_alloc_map"
 343                     ),
 344                 // E.g. a function ptr allocation
 345                 _ => return Err(err)
 346             }
 347         })
 348     }
 349
 350     pub fn get_mut(
 351         &mut self,
 352         id: AllocId,
 353     ) -> EvalResult<'tcx, &mut Allocation> {
 354         // Static?
 355         if !self.alloc_map.contains_key(&id) {
 356             // Ask the machine for what to do
 357             if let Some(kind) = M::MUT_STATIC_KIND {
 358                 // The machine supports mutating statics.  Make a copy, use that.
 359                 self.deep_copy_static(id, MemoryKind::Machine(kind))?;
 360             } else {
 361                 return err!(ModifiedConstantMemory)
 362             }
 363         }
 364         // If we come here, we know the allocation is in our map
 365         let alloc = &mut self.alloc_map.get_mut(&id).unwrap().1;
 366         // See if we are allowed to mutate this
 367         if alloc.mutability == Mutability::Immutable {
 368             err!(ModifiedConstantMemory)
 369         } else {
 370             Ok(alloc)
 371         }
 372     }
 373
 374     pub fn get_fn(&self, ptr: Pointer) -> EvalResult<'tcx, Instance<'tcx>> {
 375         if ptr.offset.bytes() != 0 {
 376             return err!(InvalidFunctionPointer);
 377         }
 378         trace!("reading fn ptr: {}", ptr.alloc_id);
 379         match self.tcx.alloc_map.lock().get(ptr.alloc_id) {
 380             Some(AllocType::Function(instance)) => Ok(instance),
 381             _ => Err(EvalErrorKind::ExecuteMemory.into()),
 382         }
 383     }
 384
 385     /// For debugging, print an allocation and all allocations it points to, recursively.
 386     pub fn dump_alloc(&self, id: AllocId) {
 387         if !log_enabled!(::log::Level::Trace) {
 388             return;
 389         }
 390         self.dump_allocs(vec![id]);
 391     }
 392
 393     /// For debugging, print a list of allocations and all allocations they point to, recursively.
 394     pub fn dump_allocs(&self, mut allocs: Vec<AllocId>) {
 395         if !log_enabled!(::log::Level::Trace) {
 396             return;
 397         }
 398         use std::fmt::Write;
 399         allocs.sort();
 400         allocs.dedup();
 401         let mut allocs_to_print = VecDeque::from(allocs);
 402         let mut allocs_seen = FxHashSet::default();
 403
 404         while let Some(id) = allocs_to_print.pop_front() {
 405             let mut msg = format!("Alloc {:<5} ", format!("{}:", id));
 406             let prefix_len = msg.len();
 407             let mut relocations = vec![];
 408
 409             let (alloc, immutable) =
 410                 // normal alloc?
 411                 match self.alloc_map.get(&id) {
 412                     Some((kind, alloc)) => (alloc, match kind {
 413                         MemoryKind::Stack => " (stack)".to_owned(),
 414                         MemoryKind::Machine(m) => format!(" ({:?})", m),
 415                     }),
 416                     None => {
 417                         // static alloc?
 418                         match self.tcx.alloc_map.lock().get(id) {
 419                             Some(AllocType::Memory(a)) => (a, " (immutable)".to_owned()),
 420                             Some(AllocType::Function(func)) => {
 421                                 trace!("{} {}", msg, func);
 422                                 continue;
 423                             }
 424                             Some(AllocType::Static(did)) => {
 425                                 trace!("{} {:?}", msg, did);
 426                                 continue;
 427                             }
 428                             None => {
 429                                 trace!("{} (deallocated)", msg);
 430                                 continue;
 431                             }
 432                         }
 433                     },
 434                 };
 435
 436             for i in 0..(alloc.bytes.len() as u64) {
 437                 let i = Size::from_bytes(i);
 438                 if let Some(&target_id) = alloc.relocations.get(&i) {
 439                     if allocs_seen.insert(target_id) {
 440                         allocs_to_print.push_back(target_id);
 441                     }
 442                     relocations.push((i, target_id));
 443                 }
 444                 if alloc.undef_mask.is_range_defined(i, i + Size::from_bytes(1)).is_ok() {
 445                     // this `as usize` is fine, since `i` came from a `usize`
 446                     write!(msg, "{:02x} ", alloc.bytes[i.bytes() as usize]).unwrap();
 447                 } else {
 448                     msg.push_str("__ ");
 449                 }
 450             }
 451
 452             trace!(
 453                 "{}({} bytes, alignment {}){}",
 454                 msg,
 455                 alloc.bytes.len(),
 456                 alloc.align.abi(),
 457                 immutable
 458             );
 459
 460             if !relocations.is_empty() {
 461                 msg.clear();
 462                 write!(msg, "{:1$}", "", prefix_len).unwrap(); // Print spaces.
 463                 let mut pos = Size::ZERO;
 464                 let relocation_width = (self.pointer_size().bytes() - 1) * 3;
 465                 for (i, target_id) in relocations {
 466                     // this `as usize` is fine, since we can't print more chars than `usize::MAX`
 467                     write!(msg, "{:1$}", "", ((i - pos) * 3).bytes() as usize).unwrap();
 468                     let target = format!("({})", target_id);
 469                     // this `as usize` is fine, since we can't print more chars than `usize::MAX`
 470                     write!(msg, "└{0:─^1$}┘ ", target, relocation_width as usize).unwrap();
 471                     pos = i + self.pointer_size();
 472                 }
 473                 trace!("{}", msg);
 474             }
 475         }
 476     }
 477
 478     pub fn leak_report(&self) -> usize {
 479         trace!("### LEAK REPORT ###");
 480         let mut_static_kind = M::MUT_STATIC_KIND.map(|k| MemoryKind::Machine(k));
 481         let leaks: Vec<_> = self.alloc_map
 482             .iter()
 483             .filter_map(|(&id, &(kind, _))|
 484                 // exclude mutable statics
 485                 if Some(kind) == mut_static_kind { None } else { Some(id) } )
 486             .collect();
 487         let n = leaks.len();
 488         self.dump_allocs(leaks);
 489         n
 490     }
 491 }
 492
 493 /// Byte accessors
 494 impl<'a, 'mir, 'tcx, M: Machine<'mir, 'tcx>> Memory<'a, 'mir, 'tcx, M> {
 495     /// The last argument controls whether we error out when there are undefined
 496     /// or pointer bytes.  You should never call this, call `get_bytes` or
 497     /// `get_bytes_with_undef_and_ptr` instead,
 498     fn get_bytes_internal(
 499         &self,
 500         ptr: Pointer,
 501         size: Size,
 502         align: Align,
 503         check_defined_and_ptr: bool,
 504     ) -> EvalResult<'tcx, &[u8]> {
 505         assert_ne!(size.bytes(), 0, "0-sized accesses should never even get a `Pointer`");
 506         self.check_align(ptr.into(), align)?;
 507         // if ptr.offset is in bounds, then so is ptr (because offset checks for overflow)
 508         self.check_bounds(ptr.offset(size, &*self)?, true)?;
 509
 510         if check_defined_and_ptr {
 511             self.check_defined(ptr, size)?;
 512             self.check_relocations(ptr, size)?;
 513         } else {
 514             // We still don't want relocations on the *edges*
 515             self.check_relocation_edges(ptr, size)?;
 516         }
 517
 518         let alloc = self.get(ptr.alloc_id)?;
 519         assert_eq!(ptr.offset.bytes() as usize as u64, ptr.offset.bytes());
 520         assert_eq!(size.bytes() as usize as u64, size.bytes());
 521         let offset = ptr.offset.bytes() as usize;
 522         Ok(&alloc.bytes[offset..offset + size.bytes() as usize])
 523     }
 524
 525     #[inline]
 526     fn get_bytes(&self, ptr: Pointer, size: Size, align: Align) -> EvalResult<'tcx, &[u8]> {
 527         self.get_bytes_internal(ptr, size, align, true)
 528     }
 529
 530     /// It is the caller's responsibility to handle undefined and pointer bytes.
 531     /// However, this still checks that there are no relocations on the egdes.
 532     #[inline]
 533     fn get_bytes_with_undef_and_ptr(
 534         &self,
 535         ptr: Pointer,
 536         size: Size,
 537         align: Align
 538     ) -> EvalResult<'tcx, &[u8]> {
 539         self.get_bytes_internal(ptr, size, align, false)
 540     }
 541
 542     /// Just calling this already marks everything as defined and removes relocations,
 543     /// so be sure to actually put data there!
 544     fn get_bytes_mut(
 545         &mut self,
 546         ptr: Pointer,
 547         size: Size,
 548         align: Align,
 549     ) -> EvalResult<'tcx, &mut [u8]> {
 550         assert_ne!(size.bytes(), 0, "0-sized accesses should never even get a `Pointer`");
 551         self.check_align(ptr.into(), align)?;
 552         // if ptr.offset is in bounds, then so is ptr (because offset checks for overflow)
 553         self.check_bounds(ptr.offset(size, &self)?, true)?;
 554
 555         self.mark_definedness(ptr, size, true)?;
 556         self.clear_relocations(ptr, size)?;
 557
 558         let alloc = self.get_mut(ptr.alloc_id)?;
 559         assert_eq!(ptr.offset.bytes() as usize as u64, ptr.offset.bytes());
 560         assert_eq!(size.bytes() as usize as u64, size.bytes());
 561         let offset = ptr.offset.bytes() as usize;
 562         Ok(&mut alloc.bytes[offset..offset + size.bytes() as usize])
 563     }
 564 }
 565
 566 /// Reading and writing
 567 impl<'a, 'mir, 'tcx, M: Machine<'mir, 'tcx>> Memory<'a, 'mir, 'tcx, M> {
 568     /// mark an allocation as static and initialized, either mutable or not
 569     pub fn intern_static(
 570         &mut self,
 571         alloc_id: AllocId,
 572         mutability: Mutability,
 573     ) -> EvalResult<'tcx> {
 574         trace!(
 575             "mark_static_initialized {:?}, mutability: {:?}",
 576             alloc_id,
 577             mutability
 578         );
 579         // remove allocation
 580         let (kind, mut alloc) = self.alloc_map.remove(&alloc_id).unwrap();
 581         match kind {
 582             MemoryKind::Machine(_) => bug!("Static cannot refer to machine memory"),
 583             MemoryKind::Stack => {},
 584         }
 585         // ensure llvm knows not to put this into immutable memory
 586         alloc.mutability = mutability;
 587         let alloc = self.tcx.intern_const_alloc(alloc);
 588         self.tcx.alloc_map.lock().set_id_memory(alloc_id, alloc);
 589         // recurse into inner allocations
 590         for &alloc in alloc.relocations.values() {
 591             // FIXME: Reusing the mutability here is likely incorrect.  It is originally
 592             // determined via `is_freeze`, and data is considered frozen if there is no
 593             // `UnsafeCell` *immediately* in that data -- however, this search stops
 594             // at references.  So whenever we follow a reference, we should likely
 595             // assume immutability -- and we should make sure that the compiler
 596             // does not permit code that would break this!
 597             if self.alloc_map.contains_key(&alloc) {
 598                 // Not yet interned, so proceed recursively
 599                 self.intern_static(alloc, mutability)?;
 600             }
 601         }
 602         Ok(())
 603     }
 604
 605     /// The alloc_id must refer to a (mutable) static; a deep copy of that
 606     /// static is made into this memory.
 607     fn deep_copy_static(
 608         &mut self,
 609         id: AllocId,
 610         kind: MemoryKind<M::MemoryKinds>,
 611     ) -> EvalResult<'tcx> {
 612         let alloc = Self::get_static_alloc(self.tcx, id)?;
 613         if alloc.mutability == Mutability::Immutable {
 614             return err!(ModifiedConstantMemory);
 615         }
 616         let old = self.alloc_map.insert(id, (kind, alloc.clone()));
 617         assert!(old.is_none(), "deep_copy_static: must not overwrite existing memory");
 618         Ok(())
 619     }
 620
 621     pub fn copy(
 622         &mut self,
 623         src: Scalar,
 624         src_align: Align,
 625         dest: Scalar,
 626         dest_align: Align,
 627         size: Size,
 628         nonoverlapping: bool,
 629     ) -> EvalResult<'tcx> {
 630         self.copy_repeatedly(src, src_align, dest, dest_align, size, 1, nonoverlapping)
 631     }
 632
 633     pub fn copy_repeatedly(
 634         &mut self,
 635         src: Scalar,
 636         src_align: Align,
 637         dest: Scalar,
 638         dest_align: Align,
 639         size: Size,
 640         length: u64,
 641         nonoverlapping: bool,
 642     ) -> EvalResult<'tcx> {
 643         if size.bytes() == 0 {
 644             // Nothing to do for ZST, other than checking alignment and non-NULLness.
 645             self.check_align(src, src_align)?;
 646             self.check_align(dest, dest_align)?;
 647             return Ok(());
 648         }
 649         let src = src.to_ptr()?;
 650         let dest = dest.to_ptr()?;
 651
 652         // first copy the relocations to a temporary buffer, because
 653         // `get_bytes_mut` will clear the relocations, which is correct,
 654         // since we don't want to keep any relocations at the target.
 655         // (`get_bytes_with_undef_and_ptr` below checks that there are no
 656         // relocations overlapping the edges; those would not be handled correctly).
 657         let relocations = {
 658             let relocations = self.relocations(src, size)?;
 659             let mut new_relocations = Vec::with_capacity(relocations.len() * (length as usize));
 660             for i in 0..length {
 661                 new_relocations.extend(
 662                     relocations
 663                     .iter()
 664                     .map(|&(offset, alloc_id)| {
 665                     (offset + dest.offset - src.offset + (i * size * relocations.len() as u64),
 666                     alloc_id)
 667                     })
 668                 );
 669             }
 670
 671             new_relocations
 672         };
 673
 674         // This also checks alignment, and relocation edges on the src.
 675         let src_bytes = self.get_bytes_with_undef_and_ptr(src, size, src_align)?.as_ptr();
 676         let dest_bytes = self.get_bytes_mut(dest, size * length, dest_align)?.as_mut_ptr();
 677
 678         // SAFE: The above indexing would have panicked if there weren't at least `size` bytes
 679         // behind `src` and `dest`. Also, we use the overlapping-safe `ptr::copy` if `src` and
 680         // `dest` could possibly overlap.
 681         unsafe {
 682             assert_eq!(size.bytes() as usize as u64, size.bytes());
 683             if src.alloc_id == dest.alloc_id {
 684                 if nonoverlapping {
 685                     if (src.offset <= dest.offset && src.offset + size > dest.offset) ||
 686                         (dest.offset <= src.offset && dest.offset + size > src.offset)
 687                     {
 688                         return err!(Intrinsic(
 689                             "copy_nonoverlapping called on overlapping ranges".to_string(),
 690                         ));
 691                     }
 692                 }
 693
 694                 for i in 0..length {
 695                     ptr::copy(src_bytes,
 696                               dest_bytes.offset((size.bytes() * i) as isize),
 697                               size.bytes() as usize);
 698                 }
 699             } else {
 700                 for i in 0..length {
 701                     ptr::copy_nonoverlapping(src_bytes,
 702                                              dest_bytes.offset((size.bytes() * i) as isize),
 703                                              size.bytes() as usize);
 704                 }
 705             }
 706         }
 707
 708         // copy definedness to the destination
 709         self.copy_undef_mask(src, dest, size, length)?;
 710         // copy the relocations to the destination
 711         self.get_mut(dest.alloc_id)?.relocations.insert_presorted(relocations);
 712
 713         Ok(())
 714     }
 715
 716     pub fn read_c_str(&self, ptr: Pointer) -> EvalResult<'tcx, &[u8]> {
 717         let alloc = self.get(ptr.alloc_id)?;
 718         assert_eq!(ptr.offset.bytes() as usize as u64, ptr.offset.bytes());
 719         let offset = ptr.offset.bytes() as usize;
 720         match alloc.bytes[offset..].iter().position(|&c| c == 0) {
 721             Some(size) => {
 722                 let p1 = Size::from_bytes((size + 1) as u64);
 723                 self.check_relocations(ptr, p1)?;
 724                 self.check_defined(ptr, p1)?;
 725                 Ok(&alloc.bytes[offset..offset + size])
 726             }
 727             None => err!(UnterminatedCString(ptr)),
 728         }
 729     }
 730
 731     pub fn read_bytes(&self, ptr: Scalar, size: Size) -> EvalResult<'tcx, &[u8]> {
 732         // Empty accesses don't need to be valid pointers, but they should still be non-NULL
 733         let align = Align::from_bytes(1, 1).unwrap();
 734         if size.bytes() == 0 {
 735             self.check_align(ptr, align)?;
 736             return Ok(&[]);
 737         }
 738         self.get_bytes(ptr.to_ptr()?, size, align)
 739     }
 740
 741     pub fn write_bytes(&mut self, ptr: Scalar, src: &[u8]) -> EvalResult<'tcx> {
 742         // Empty accesses don't need to be valid pointers, but they should still be non-NULL
 743         let align = Align::from_bytes(1, 1).unwrap();
 744         if src.is_empty() {
 745             self.check_align(ptr, align)?;
 746             return Ok(());
 747         }
 748         let bytes = self.get_bytes_mut(ptr.to_ptr()?, Size::from_bytes(src.len() as u64), align)?;
 749         bytes.clone_from_slice(src);
 750         Ok(())
 751     }
 752
 753     pub fn write_repeat(&mut self, ptr: Scalar, val: u8, count: Size) -> EvalResult<'tcx> {
 754         // Empty accesses don't need to be valid pointers, but they should still be non-NULL
 755         let align = Align::from_bytes(1, 1).unwrap();
 756         if count.bytes() == 0 {
 757             self.check_align(ptr, align)?;
 758             return Ok(());
 759         }
 760         let bytes = self.get_bytes_mut(ptr.to_ptr()?, count, align)?;
 761         for b in bytes {
 762             *b = val;
 763         }
 764         Ok(())
 765     }
 766
 767     /// Read a *non-ZST* scalar
 768     pub fn read_scalar(
 769         &self,
 770         ptr: Pointer,
 771         ptr_align: Align,
 772         size: Size
 773     ) -> EvalResult<'tcx, ScalarMaybeUndef> {
 774         // get_bytes_unchecked tests alignment and relocation edges
 775         let bytes = self.get_bytes_with_undef_and_ptr(
 776             ptr, size, ptr_align.min(self.int_align(size))
 777         )?;
 778         // Undef check happens *after* we established that the alignment is correct.
 779         // We must not return Ok() for unaligned pointers!
 780         if self.check_defined(ptr, size).is_err() {
 781             // this inflates undefined bytes to the entire scalar, even if only a few
 782             // bytes are undefined
 783             return Ok(ScalarMaybeUndef::Undef);
 784         }
 785         // Now we do the actual reading
 786         let bits = read_target_uint(self.tcx.data_layout.endian, bytes).unwrap();
 787         // See if we got a pointer
 788         if size != self.pointer_size() {
 789             // *Now* better make sure that the inside also is free of relocations.
 790             self.check_relocations(ptr, size)?;
 791         } else {
 792             let alloc = self.get(ptr.alloc_id)?;
 793             match alloc.relocations.get(&ptr.offset) {
 794                 Some(&alloc_id) => {
 795                     let ptr = Pointer::new(alloc_id, Size::from_bytes(bits as u64));
 796                     return Ok(ScalarMaybeUndef::Scalar(ptr.into()))
 797                 }
 798                 None => {},
 799             }
 800         }
 801         // We don't. Just return the bits.
 802         Ok(ScalarMaybeUndef::Scalar(Scalar::from_uint(bits, size)))
 803     }
 804
 805     pub fn read_ptr_sized(&self, ptr: Pointer, ptr_align: Align)
 806         -> EvalResult<'tcx, ScalarMaybeUndef> {
 807         self.read_scalar(ptr, ptr_align, self.pointer_size())
 808     }
 809
 810     /// Write a *non-ZST* scalar
 811     pub fn write_scalar(
 812         &mut self,
 813         ptr: Pointer,
 814         ptr_align: Align,
 815         val: ScalarMaybeUndef,
 816         type_size: Size,
 817     ) -> EvalResult<'tcx> {
 818         let val = match val {
 819             ScalarMaybeUndef::Scalar(scalar) => scalar,
 820             ScalarMaybeUndef::Undef => return self.mark_definedness(ptr, type_size, false),
 821         };
 822
 823         let bytes = match val {
 824             Scalar::Ptr(val) => {
 825                 assert_eq!(type_size, self.pointer_size());
 826                 val.offset.bytes() as u128
 827             }
 828
 829             Scalar::Bits { bits, size } => {
 830                 assert_eq!(size as u64, type_size.bytes());
 831                 debug_assert_eq!(truncate(bits, Size::from_bytes(size.into())), bits,
 832                     "Unexpected value of size {} when writing to memory", size);
 833                 bits
 834             },
 835         };
 836
 837         {
 838             // get_bytes_mut checks alignment
 839             let endian = self.tcx.data_layout.endian;
 840             let dst = self.get_bytes_mut(ptr, type_size, ptr_align)?;
 841             write_target_uint(endian, dst, bytes).unwrap();
 842         }
 843
 844         // See if we have to also write a relocation
 845         match val {
 846             Scalar::Ptr(val) => {
 847                 self.get_mut(ptr.alloc_id)?.relocations.insert(
 848                     ptr.offset,
 849                     val.alloc_id,
 850                 );
 851             }
 852             _ => {}
 853         }
 854
 855         Ok(())
 856     }
 857
 858     pub fn write_ptr_sized(&mut self, ptr: Pointer, ptr_align: Align, val: ScalarMaybeUndef)
 859         -> EvalResult<'tcx> {
 860         let ptr_size = self.pointer_size();
 861         self.write_scalar(ptr.into(), ptr_align, val, ptr_size)
 862     }
 863
 864     fn int_align(&self, size: Size) -> Align {
 865         // We assume pointer-sized integers have the same alignment as pointers.
 866         // We also assume signed and unsigned integers of the same size have the same alignment.
 867         let ity = match size.bytes() {
 868             1 => layout::I8,
 869             2 => layout::I16,
 870             4 => layout::I32,
 871             8 => layout::I64,
 872             16 => layout::I128,
 873             _ => bug!("bad integer size: {}", size.bytes()),
 874         };
 875         ity.align(self)
 876     }
 877 }
 878
 879 /// Relocations
 880 impl<'a, 'mir, 'tcx, M: Machine<'mir, 'tcx>> Memory<'a, 'mir, 'tcx, M> {
 881     /// Return all relocations overlapping with the given ptr-offset pair.
 882     fn relocations(
 883         &self,
 884         ptr: Pointer,
 885         size: Size,
 886     ) -> EvalResult<'tcx, &[(Size, AllocId)]> {
 887         // We have to go back `pointer_size - 1` bytes, as that one would still overlap with
 888         // the beginning of this range.
 889         let start = ptr.offset.bytes().saturating_sub(self.pointer_size().bytes() - 1);
 890         let end = ptr.offset + size; // this does overflow checking
 891         Ok(self.get(ptr.alloc_id)?.relocations.range(Size::from_bytes(start)..end))
 892     }
 893
 894     /// Check that there ar eno relocations overlapping with the given range.
 895     #[inline(always)]
 896     fn check_relocations(&self, ptr: Pointer, size: Size) -> EvalResult<'tcx> {
 897         if self.relocations(ptr, size)?.len() != 0 {
 898             err!(ReadPointerAsBytes)
 899         } else {
 900             Ok(())
 901         }
 902     }
 903
 904     /// Remove all relocations inside the given range.
 905     /// If there are relocations overlapping with the edges, they
 906     /// are removed as well *and* the bytes they cover are marked as
 907     /// uninitialized.  This is a somewhat odd "spooky action at a distance",
 908     /// but it allows strictly more code to run than if we would just error
 909     /// immediately in that case.
 910     fn clear_relocations(&mut self, ptr: Pointer, size: Size) -> EvalResult<'tcx> {
 911         // Find the start and end of the given range and its outermost relocations.
 912         let (first, last) = {
 913             // Find all relocations overlapping the given range.
 914             let relocations = self.relocations(ptr, size)?;
 915             if relocations.is_empty() {
 916                 return Ok(());
 917             }
 918
 919             (relocations.first().unwrap().0,
 920              relocations.last().unwrap().0 + self.pointer_size())
 921         };
 922         let start = ptr.offset;
 923         let end = start + size;
 924
 925         let alloc = self.get_mut(ptr.alloc_id)?;
 926
 927         // Mark parts of the outermost relocations as undefined if they partially fall outside the
 928         // given range.
 929         if first < start {
 930             alloc.undef_mask.set_range(first, start, false);
 931         }
 932         if last > end {
 933             alloc.undef_mask.set_range(end, last, false);
 934         }
 935
 936         // Forget all the relocations.
 937         alloc.relocations.remove_range(first..last);
 938
 939         Ok(())
 940     }
 941
 942     /// Error if there are relocations overlapping with the egdes of the
 943     /// given memory range.
 944     #[inline]
 945     fn check_relocation_edges(&self, ptr: Pointer, size: Size) -> EvalResult<'tcx> {
 946         self.check_relocations(ptr, Size::ZERO)?;
 947         self.check_relocations(ptr.offset(size, self)?, Size::ZERO)?;
 948         Ok(())
 949     }
 950 }
 951
 952 /// Undefined bytes
 953 impl<'a, 'mir, 'tcx, M: Machine<'mir, 'tcx>> Memory<'a, 'mir, 'tcx, M> {
 954     // FIXME(solson): This is a very naive, slow version.
 955     fn copy_undef_mask(
 956         &mut self,
 957         src: Pointer,
 958         dest: Pointer,
 959         size: Size,
 960         repeat: u64,
 961     ) -> EvalResult<'tcx> {
 962         // The bits have to be saved locally before writing to dest in case src and dest overlap.
 963         assert_eq!(size.bytes() as usize as u64, size.bytes());
 964
 965         let undef_mask = self.get(src.alloc_id)?.undef_mask.clone();
 966         let dest_allocation = self.get_mut(dest.alloc_id)?;
 967
 968         for i in 0..size.bytes() {
 969             let defined = undef_mask.get(src.offset + Size::from_bytes(i));
 970
 971             for j in 0..repeat {
 972                 dest_allocation.undef_mask.set(
 973                     dest.offset + Size::from_bytes(i + (size.bytes() * j)),
 974                     defined
 975                 );
 976             }
 977         }
 978
 979         Ok(())
 980     }
 981
 982     /// Checks that a range of bytes is defined. If not, returns the `ReadUndefBytes`
 983     /// error which will report the first byte which is undefined.
 984     #[inline]
 985     fn check_defined(&self, ptr: Pointer, size: Size) -> EvalResult<'tcx> {
 986         let alloc = self.get(ptr.alloc_id)?;
 987         alloc.undef_mask.is_range_defined(
 988             ptr.offset,
 989             ptr.offset + size,
 990         ).or_else(|idx| err!(ReadUndefBytes(idx)))
 991     }
 992
 993     pub fn mark_definedness(
 994         &mut self,
 995         ptr: Pointer,
 996         size: Size,
 997         new_state: bool,
 998     ) -> EvalResult<'tcx> {
 999         if size.bytes() == 0 {
1000             return Ok(());
1001         }
1002         let alloc = self.get_mut(ptr.alloc_id)?;
1003         alloc.undef_mask.set_range(
1004             ptr.offset,
1005             ptr.offset + size,
1006             new_state,
1007         );
1008         Ok(())
1009     }
1010 }