src/librustc_mir/interpret/memory.rs

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