src/librustc_mir/interpret/memory.rs

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