src/librustc_mir/interpret/memory.rs

   1 use byteorder::{ReadBytesExt, WriteBytesExt, LittleEndian, BigEndian};
   2 use std::collections::{btree_map, BTreeMap, HashMap, HashSet, VecDeque};
   3 use std::{fmt, iter, ptr, mem, io, ops};
   4
   5 use rustc::ty;
   6 use rustc::ty::layout::{self, TargetDataLayout, HasDataLayout};
   7 use syntax::ast::Mutability;
   8 use rustc::middle::region::CodeExtent;
   9
  10 use error::{EvalError, EvalResult};
  11 use value::{PrimVal, Pointer};
  12 use eval_context::EvalContext;
  13
  14 ////////////////////////////////////////////////////////////////////////////////
  15 // Locks
  16 ////////////////////////////////////////////////////////////////////////////////
  17
  18 mod range {
  19     use super::*;
  20
  21     // The derived `Ord` impl sorts first by the first field, then, if the fields are the same,
  22     // by the second field.
  23     // This is exactly what we need for our purposes, since a range query on a BTReeSet/BTreeMap will give us all
  24     // `MemoryRange`s whose `start` is <= than the one we're looking for, but not > the end of the range we're checking.
  25     // At the same time the `end` is irrelevant for the sorting and range searching, but used for the check.
  26     // This kind of search breaks, if `end < start`, so don't do that!
  27     #[derive(Eq, PartialEq, Ord, PartialOrd, Debug)]
  28     pub struct MemoryRange {
  29         start: u64,
  30         end: u64,
  31     }
  32
  33     impl MemoryRange {
  34         pub fn new(offset: u64, len: u64) -> MemoryRange {
  35             assert!(len > 0);
  36             MemoryRange {
  37                 start: offset,
  38                 end: offset + len,
  39             }
  40         }
  41
  42         pub fn offset(&self) -> u64 {
  43             self.start
  44         }
  45
  46         pub fn len(&self) -> u64 {
  47             self.end - self.start
  48         }
  49
  50         pub fn range(offset: u64, len: u64) -> ops::Range<MemoryRange> {
  51             assert!(len > 0);
  52             // We select all elements that are within
  53             // the range given by the offset into the allocation and the length.
  54             // This is sound if "self.contains() || self.overlaps() == true" implies that self is in-range.
  55             let left = MemoryRange {
  56                 start: 0,
  57                 end: offset,
  58             };
  59             let right = MemoryRange {
  60                 start: offset + len + 1,
  61                 end: 0,
  62             };
  63             left..right
  64         }
  65
  66         pub fn contained_in(&self, offset: u64, len: u64) -> bool {
  67             assert!(len > 0);
  68             offset <= self.start && self.end <= (offset + len)
  69         }
  70
  71         pub fn overlaps(&self, offset: u64, len: u64) -> bool {
  72             assert!(len > 0);
  73             //let non_overlap = (offset + len) <= self.start || self.end <= offset;
  74             (offset + len) > self.start && self.end > offset
  75         }
  76     }
  77 }
  78 use self::range::*;
  79
  80 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
  81 pub enum AccessKind {
  82     Read,
  83     Write,
  84 }
  85
  86 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
  87 struct DynamicLifetime {
  88     pub frame: usize,
  89     pub region: Option<CodeExtent>, // "None" indicates "until the function ends"
  90 }
  91
  92 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
  93 enum LockStatus {
  94     Held,
  95     RecoverAfter(CodeExtent), // the frame is given by the surrounding LockInfo's lifetime.
  96 }
  97
  98 /// Information about a lock that is or will be held.
  99 #[derive(Copy, Clone, Debug)]
 100 pub struct LockInfo {
 101     kind: AccessKind,
 102     lifetime: DynamicLifetime,
 103     status: LockStatus,
 104 }
 105
 106 impl LockInfo {
 107     fn access_permitted(&self, frame: usize, access: AccessKind) -> bool {
 108         use self::AccessKind::*;
 109         match (self.kind, access) {
 110             (Read, Read) => true, // Read access to read-locked region is okay, no matter who's holding the read lock.
 111             (Write, _) if self.lifetime.frame == frame => true, // All access is okay when we hold the write lock.
 112             _ => false, // Somebody else holding the write lock is not okay
 113         }
 114     }
 115 }
 116
 117 ////////////////////////////////////////////////////////////////////////////////
 118 // Allocations and pointers
 119 ////////////////////////////////////////////////////////////////////////////////
 120
 121 #[derive(Copy, Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
 122 pub struct AllocId(pub u64);
 123
 124 impl fmt::Display for AllocId {
 125     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 126         write!(f, "{}", self.0)
 127     }
 128 }
 129
 130 #[derive(Debug)]
 131 pub struct Allocation {
 132     /// The actual bytes of the allocation.
 133     /// Note that the bytes of a pointer represent the offset of the pointer
 134     pub bytes: Vec<u8>,
 135     /// Maps from byte addresses to allocations.
 136     /// Only the first byte of a pointer is inserted into the map.
 137     pub relocations: BTreeMap<u64, AllocId>,
 138     /// Denotes undefined memory. Reading from undefined memory is forbidden in miri
 139     pub undef_mask: UndefMask,
 140     /// The alignment of the allocation to detect unaligned reads.
 141     pub align: u64,
 142     /// Whether the allocation may be modified.
 143     pub mutable: Mutability,
 144     /// Use the `mark_static_initalized` method of `Memory` to ensure that an error occurs, if the memory of this
 145     /// allocation is modified or deallocated in the future.
 146     /// Helps guarantee that stack allocations aren't deallocated via `rust_deallocate`
 147     pub kind: Kind,
 148     /// Memory regions that are locked by some function
 149     locks: BTreeMap<MemoryRange, Vec<LockInfo>>,
 150 }
 151
 152 impl Allocation {
 153     fn iter_locks<'a>(&'a self, offset: u64, len: u64) -> impl Iterator<Item=&'a LockInfo> + 'a {
 154         self.locks.range(MemoryRange::range(offset, len))
 155             .filter(move |&(range, _)| range.overlaps(offset, len))
 156             .flat_map(|(_, locks)| locks.iter())
 157     }
 158
 159     fn iter_lock_vecs_mut<'a>(&'a mut self, offset: u64, len: u64) -> impl Iterator<Item=(&'a MemoryRange, &'a mut Vec<LockInfo>)> + 'a {
 160         self.locks.range_mut(MemoryRange::range(offset, len))
 161             .filter(move |&(range, _)| range.overlaps(offset, len))
 162     }
 163
 164     fn check_locks<'tcx>(&self, frame: usize, offset: u64, len: u64, access: AccessKind) -> Result<(), LockInfo> {
 165         if len == 0 {
 166             return Ok(())
 167         }
 168         for lock in self.iter_locks(offset, len) {
 169             // Check if the lock is active, and is in conflict with the access.
 170             if lock.status == LockStatus::Held && !lock.access_permitted(frame, access) {
 171                 return Err(*lock);
 172             }
 173         }
 174         Ok(())
 175     }
 176 }
 177
 178 #[derive(Debug, PartialEq, Copy, Clone)]
 179 pub enum Kind {
 180     /// Error if deallocated any other way than `rust_deallocate`
 181     Rust,
 182     /// Error if deallocated any other way than `free`
 183     C,
 184     /// Error if deallocated except during a stack pop
 185     Stack,
 186     /// Static in the process of being initialized.
 187     /// The difference is important: An immutable static referring to a
 188     /// mutable initialized static will freeze immutably and would not
 189     /// be able to distinguish already initialized statics from uninitialized ones
 190     UninitializedStatic,
 191     /// May never be deallocated
 192     Static,
 193     /// Part of env var emulation
 194     Env,
 195 }
 196
 197 #[derive(Copy, Clone, Debug, Eq, PartialEq)]
 198 pub struct MemoryPointer {
 199     pub alloc_id: AllocId,
 200     pub offset: u64,
 201 }
 202
 203 impl<'tcx> MemoryPointer {
 204     pub fn new(alloc_id: AllocId, offset: u64) -> Self {
 205         MemoryPointer { alloc_id, offset }
 206     }
 207
 208     pub(crate) fn wrapping_signed_offset<C: HasDataLayout>(self, i: i64, cx: C) -> Self {
 209         MemoryPointer::new(self.alloc_id, cx.data_layout().wrapping_signed_offset(self.offset, i))
 210     }
 211
 212     pub(crate) fn overflowing_signed_offset<C: HasDataLayout>(self, i: i128, cx: C) -> (Self, bool) {
 213         let (res, over) = cx.data_layout().overflowing_signed_offset(self.offset, i);
 214         (MemoryPointer::new(self.alloc_id, res), over)
 215     }
 216
 217     pub(crate) fn signed_offset<C: HasDataLayout>(self, i: i64, cx: C) -> EvalResult<'tcx, Self> {
 218         Ok(MemoryPointer::new(self.alloc_id, cx.data_layout().signed_offset(self.offset, i)?))
 219     }
 220
 221     pub(crate) fn overflowing_offset<C: HasDataLayout>(self, i: u64, cx: C) -> (Self, bool) {
 222         let (res, over) = cx.data_layout().overflowing_offset(self.offset, i);
 223         (MemoryPointer::new(self.alloc_id, res), over)
 224     }
 225
 226     pub(crate) fn offset<C: HasDataLayout>(self, i: u64, cx: C) -> EvalResult<'tcx, Self> {
 227         Ok(MemoryPointer::new(self.alloc_id, cx.data_layout().offset(self.offset, i)?))
 228     }
 229 }
 230
 231 ////////////////////////////////////////////////////////////////////////////////
 232 // Top-level interpreter memory
 233 ////////////////////////////////////////////////////////////////////////////////
 234
 235 pub type TlsKey = usize;
 236
 237 #[derive(Copy, Clone, Debug)]
 238 pub struct TlsEntry<'tcx> {
 239     data: Pointer, // Will eventually become a map from thread IDs to `Pointer`s, if we ever support more than one thread.
 240     dtor: Option<ty::Instance<'tcx>>,
 241 }
 242
 243 pub struct Memory<'a, 'tcx> {
 244     /// Actual memory allocations (arbitrary bytes, may contain pointers into other allocations).
 245     alloc_map: HashMap<AllocId, Allocation>,
 246
 247     /// The AllocId to assign to the next new allocation. Always incremented, never gets smaller.
 248     next_id: AllocId,
 249
 250     /// Set of statics, constants, promoteds, vtables, ... to prevent `mark_static_initalized` from
 251     /// stepping out of its own allocations. This set only contains statics backed by an
 252     /// allocation. If they are ByVal or ByValPair they are not here, but will be inserted once
 253     /// they become ByRef.
 254     static_alloc: HashSet<AllocId>,
 255
 256     /// Number of virtual bytes allocated.
 257     memory_usage: u64,
 258
 259     /// Maximum number of virtual bytes that may be allocated.
 260     memory_size: u64,
 261
 262     /// Function "allocations". They exist solely so pointers have something to point to, and
 263     /// we can figure out what they point to.
 264     functions: HashMap<AllocId, ty::Instance<'tcx>>,
 265
 266     /// Inverse map of `functions` so we don't allocate a new pointer every time we need one
 267     function_alloc_cache: HashMap<ty::Instance<'tcx>, AllocId>,
 268
 269     /// Target machine data layout to emulate.
 270     pub layout: &'a TargetDataLayout,
 271
 272     /// A cache for basic byte allocations keyed by their contents. This is used to deduplicate
 273     /// allocations for string and bytestring literals.
 274     literal_alloc_cache: HashMap<Vec<u8>, AllocId>,
 275
 276     /// pthreads-style thread-local storage.
 277     thread_local: BTreeMap<TlsKey, TlsEntry<'tcx>>,
 278
 279     /// The Key to use for the next thread-local allocation.
 280     next_thread_local: TlsKey,
 281
 282     /// To avoid having to pass flags to every single memory access, we have some global state saying whether
 283     /// alignment checking is currently enforced for read and/or write accesses.
 284     reads_are_aligned: bool,
 285     writes_are_aligned: bool,
 286
 287     /// The current stack frame.  Used to check accesses against locks.
 288     cur_frame: usize,
 289 }
 290
 291 impl<'a, 'tcx> Memory<'a, 'tcx> {
 292     pub fn new(layout: &'a TargetDataLayout, max_memory: u64) -> Self {
 293         Memory {
 294             alloc_map: HashMap::new(),
 295             functions: HashMap::new(),
 296             function_alloc_cache: HashMap::new(),
 297             next_id: AllocId(0),
 298             layout,
 299             memory_size: max_memory,
 300             memory_usage: 0,
 301             static_alloc: HashSet::new(),
 302             literal_alloc_cache: HashMap::new(),
 303             thread_local: BTreeMap::new(),
 304             next_thread_local: 0,
 305             reads_are_aligned: true,
 306             writes_are_aligned: true,
 307             cur_frame: usize::max_value(),
 308         }
 309     }
 310
 311     pub fn allocations(&self) -> ::std::collections::hash_map::Iter<AllocId, Allocation> {
 312         self.alloc_map.iter()
 313     }
 314
 315     pub fn create_fn_alloc(&mut self, instance: ty::Instance<'tcx>) -> MemoryPointer {
 316         if let Some(&alloc_id) = self.function_alloc_cache.get(&instance) {
 317             return MemoryPointer::new(alloc_id, 0);
 318         }
 319         let id = self.next_id;
 320         debug!("creating fn ptr: {}", id);
 321         self.next_id.0 += 1;
 322         self.functions.insert(id, instance);
 323         self.function_alloc_cache.insert(instance, id);
 324         MemoryPointer::new(id, 0)
 325     }
 326
 327     pub fn allocate_cached(&mut self, bytes: &[u8]) -> EvalResult<'tcx, MemoryPointer> {
 328         if let Some(&alloc_id) = self.literal_alloc_cache.get(bytes) {
 329             return Ok(MemoryPointer::new(alloc_id, 0));
 330         }
 331
 332         let ptr = self.allocate(bytes.len() as u64, 1, Kind::UninitializedStatic)?;
 333         self.write_bytes(ptr.into(), bytes)?;
 334         self.mark_static_initalized(ptr.alloc_id, Mutability::Immutable)?;
 335         self.literal_alloc_cache.insert(bytes.to_vec(), ptr.alloc_id);
 336         Ok(ptr)
 337     }
 338
 339     pub fn allocate(&mut self, size: u64, align: u64, kind: Kind) -> EvalResult<'tcx, MemoryPointer> {
 340         assert_ne!(align, 0);
 341         assert!(align.is_power_of_two());
 342
 343         if self.memory_size - self.memory_usage < size {
 344             return Err(EvalError::OutOfMemory {
 345                 allocation_size: size,
 346                 memory_size: self.memory_size,
 347                 memory_usage: self.memory_usage,
 348             });
 349         }
 350         self.memory_usage += size;
 351         assert_eq!(size as usize as u64, size);
 352         let alloc = Allocation {
 353             bytes: vec![0; size as usize],
 354             relocations: BTreeMap::new(),
 355             undef_mask: UndefMask::new(size),
 356             align,
 357             kind,
 358             mutable: Mutability::Mutable,
 359             locks: BTreeMap::new(),
 360         };
 361         let id = self.next_id;
 362         self.next_id.0 += 1;
 363         self.alloc_map.insert(id, alloc);
 364         Ok(MemoryPointer::new(id, 0))
 365     }
 366
 367     pub fn reallocate(&mut self, ptr: MemoryPointer, old_size: u64, old_align: u64, new_size: u64, new_align: u64, kind: Kind) -> EvalResult<'tcx, MemoryPointer> {
 368         use std::cmp::min;
 369
 370         if ptr.offset != 0 {
 371             return Err(EvalError::ReallocateNonBasePtr);
 372         }
 373         if let Ok(alloc) = self.get(ptr.alloc_id) {
 374             if alloc.kind != kind {
 375                 return Err(EvalError::ReallocatedWrongMemoryKind(alloc.kind, kind));
 376             }
 377         }
 378
 379         // For simplicities' sake, we implement reallocate as "alloc, copy, dealloc"
 380         let new_ptr = self.allocate(new_size, new_align, kind)?;
 381         self.copy(ptr.into(), new_ptr.into(), min(old_size, new_size), min(old_align, new_align), /*nonoverlapping*/true)?;
 382         self.deallocate(ptr, Some((old_size, old_align)), kind)?;
 383
 384         Ok(new_ptr)
 385     }
 386
 387     pub fn deallocate(&mut self, ptr: MemoryPointer, size_and_align: Option<(u64, u64)>, kind: Kind) -> EvalResult<'tcx> {
 388         if ptr.offset != 0 {
 389             return Err(EvalError::DeallocateNonBasePtr);
 390         }
 391
 392         let alloc = match self.alloc_map.remove(&ptr.alloc_id) {
 393             Some(alloc) => alloc,
 394             None => return Err(EvalError::DoubleFree),
 395         };
 396
 397         // It is okay for us to still holds locks on deallocation -- for example, we could store data we own
 398         // in a local, and the local could be deallocated (from StorageDead) before the function returns.
 399         // However, we should check *something*.  For now, we make sure that there is no conflicting write
 400         // lock by another frame.  We *have* to permit deallocation if we hold a read lock.
 401         // TODO: Figure out the exact rules here.
 402         alloc.check_locks(self.cur_frame, 0, alloc.bytes.len() as u64, AccessKind::Read)
 403             .map_err(|lock| EvalError::DeallocatedLockedMemory { ptr, lock })?;
 404
 405         if alloc.kind != kind {
 406             return Err(EvalError::DeallocatedWrongMemoryKind(alloc.kind, kind));
 407         }
 408         if let Some((size, align)) = size_and_align {
 409             if size != alloc.bytes.len() as u64 || align != alloc.align {
 410                 return Err(EvalError::IncorrectAllocationInformation);
 411             }
 412         }
 413
 414         self.memory_usage -= alloc.bytes.len() as u64;
 415         debug!("deallocated : {}", ptr.alloc_id);
 416
 417         Ok(())
 418     }
 419
 420     pub fn pointer_size(&self) -> u64 {
 421         self.layout.pointer_size.bytes()
 422     }
 423
 424     pub fn endianess(&self) -> layout::Endian {
 425         self.layout.endian
 426     }
 427
 428     /// Check that the pointer is aligned AND non-NULL.
 429     pub fn check_align(&self, ptr: Pointer, align: u64) -> EvalResult<'tcx> {
 430         let offset = match ptr.into_inner_primval() {
 431             PrimVal::Ptr(ptr) => {
 432                 let alloc = self.get(ptr.alloc_id)?;
 433                 if alloc.align < align {
 434                     return Err(EvalError::AlignmentCheckFailed {
 435                         has: alloc.align,
 436                         required: align,
 437                     });
 438                 }
 439                 ptr.offset
 440             },
 441             PrimVal::Bytes(bytes) => {
 442                 let v = ((bytes as u128) % (1 << self.pointer_size())) as u64;
 443                 if v == 0 {
 444                     return Err(EvalError::InvalidNullPointerUsage);
 445                 }
 446                 v
 447             },
 448             PrimVal::Undef => return Err(EvalError::ReadUndefBytes),
 449         };
 450         if offset % align == 0 {
 451             Ok(())
 452         } else {
 453             Err(EvalError::AlignmentCheckFailed {
 454                 has: offset % align,
 455                 required: align,
 456             })
 457         }
 458     }
 459
 460     pub(crate) fn check_bounds(&self, ptr: MemoryPointer, access: bool) -> EvalResult<'tcx> {
 461         let alloc = self.get(ptr.alloc_id)?;
 462         let allocation_size = alloc.bytes.len() as u64;
 463         if ptr.offset > allocation_size {
 464             return Err(EvalError::PointerOutOfBounds { ptr, access, allocation_size });
 465         }
 466         Ok(())
 467     }
 468
 469     pub(crate) fn set_cur_frame(&mut self, cur_frame: usize) {
 470         self.cur_frame = cur_frame;
 471     }
 472
 473     pub(crate) fn create_tls_key(&mut self, dtor: Option<ty::Instance<'tcx>>) -> TlsKey {
 474         let new_key = self.next_thread_local;
 475         self.next_thread_local += 1;
 476         self.thread_local.insert(new_key, TlsEntry { data: Pointer::null(), dtor });
 477         trace!("New TLS key allocated: {} with dtor {:?}", new_key, dtor);
 478         return new_key;
 479     }
 480
 481     pub(crate) fn delete_tls_key(&mut self, key: TlsKey) -> EvalResult<'tcx> {
 482         return match self.thread_local.remove(&key) {
 483             Some(_) => {
 484                 trace!("TLS key {} removed", key);
 485                 Ok(())
 486             },
 487             None => Err(EvalError::TlsOutOfBounds)
 488         }
 489     }
 490
 491     pub(crate) fn load_tls(&mut self, key: TlsKey) -> EvalResult<'tcx, Pointer> {
 492         return match self.thread_local.get(&key) {
 493             Some(&TlsEntry { data, .. }) => {
 494                 trace!("TLS key {} loaded: {:?}", key, data);
 495                 Ok(data)
 496             },
 497             None => Err(EvalError::TlsOutOfBounds)
 498         }
 499     }
 500
 501     pub(crate) fn store_tls(&mut self, key: TlsKey, new_data: Pointer) -> EvalResult<'tcx> {
 502         return match self.thread_local.get_mut(&key) {
 503             Some(&mut TlsEntry { ref mut data, .. }) => {
 504                 trace!("TLS key {} stored: {:?}", key, new_data);
 505                 *data = new_data;
 506                 Ok(())
 507             },
 508             None => Err(EvalError::TlsOutOfBounds)
 509         }
 510     }
 511
 512     /// Returns a dtor, its argument and its index, if one is supposed to run
 513     ///
 514     /// An optional destructor function may be associated with each key value.
 515     /// At thread exit, if a key value has a non-NULL destructor pointer,
 516     /// and the thread has a non-NULL value associated with that key,
 517     /// the value of the key is set to NULL, and then the function pointed
 518     /// to is called with the previously associated value as its sole argument.
 519     /// The order of destructor calls is unspecified if more than one destructor
 520     /// exists for a thread when it exits.
 521     ///
 522     /// If, after all the destructors have been called for all non-NULL values
 523     /// with associated destructors, there are still some non-NULL values with
 524     /// associated destructors, then the process is repeated.
 525     /// If, after at least {PTHREAD_DESTRUCTOR_ITERATIONS} iterations of destructor
 526     /// calls for outstanding non-NULL values, there are still some non-NULL values
 527     /// with associated destructors, implementations may stop calling destructors,
 528     /// or they may continue calling destructors until no non-NULL values with
 529     /// associated destructors exist, even though this might result in an infinite loop.
 530     pub(crate) fn fetch_tls_dtor(&mut self, key: Option<TlsKey>) -> EvalResult<'tcx, Option<(ty::Instance<'tcx>, Pointer, TlsKey)>> {
 531         use std::collections::Bound::*;
 532         let start = match key {
 533             Some(key) => Excluded(key),
 534             None => Unbounded,
 535         };
 536         for (&key, &mut TlsEntry { ref mut data, dtor }) in self.thread_local.range_mut((start, Unbounded)) {
 537             if !data.is_null()? {
 538                 if let Some(dtor) = dtor {
 539                     let ret = Some((dtor, *data, key));
 540                     *data = Pointer::null();
 541                     return Ok(ret);
 542                 }
 543             }
 544         }
 545         return Ok(None);
 546     }
 547 }
 548
 549 /// Locking
 550 impl<'a, 'tcx> Memory<'a, 'tcx> {
 551     pub(crate) fn check_locks(&self, ptr: MemoryPointer, len: u64, access: AccessKind) -> EvalResult<'tcx> {
 552         if len == 0 {
 553             return Ok(())
 554         }
 555         let alloc = self.get(ptr.alloc_id)?;
 556         alloc.check_locks(self.cur_frame, ptr.offset, len, access)
 557             .map_err(|lock| EvalError::MemoryLockViolation { ptr, len, access, lock })
 558     }
 559
 560     /// Acquire the lock for the given lifetime
 561     pub(crate) fn acquire_lock(&mut self, ptr: MemoryPointer, len: u64, region: Option<CodeExtent>, kind: AccessKind) -> EvalResult<'tcx> {
 562         assert!(len > 0);
 563         trace!("Acquiring {:?} lock at {:?}, size {} for region {:?}", kind, ptr, len, region);
 564         self.check_bounds(ptr.offset(len, self.layout)?, true)?; // if ptr.offset is in bounds, then so is ptr (because offset checks for overflow)
 565         self.check_locks(ptr, len, kind)?; // make sure we have the access we are acquiring
 566         let lifetime = DynamicLifetime { frame: self.cur_frame, region };
 567         let alloc = self.get_mut_unchecked(ptr.alloc_id)?;
 568         alloc.locks.entry(MemoryRange::new(ptr.offset, len)).or_insert_with(|| Vec::new()).push(LockInfo { lifetime, kind, status: LockStatus::Held });
 569         Ok(())
 570     }
 571
 572     /// Release a write lock prematurely. If there's just read locks, do nothing.
 573     pub(crate) fn release_write_lock_until(&mut self, ptr: MemoryPointer, len: u64, release_until: Option<CodeExtent>) -> EvalResult<'tcx> {
 574         assert!(len > 0);
 575         let cur_frame = self.cur_frame;
 576         let alloc = self.get_mut_unchecked(ptr.alloc_id)?;
 577
 578         for (range, locks) in alloc.iter_lock_vecs_mut(ptr.offset, len) {
 579             // Check all locks in this region; make sure there are no conflicting write locks of other frames.
 580             // Also, if we will recover later, perform our release by changing the lock status.
 581             for lock in locks.iter_mut() {
 582                 if lock.kind == AccessKind::Read || lock.status != LockStatus::Held { continue; }
 583                 if lock.lifetime.frame != cur_frame {
 584                     return Err(EvalError::InvalidMemoryLockRelease { ptr, len });
 585                 }
 586                 if !range.contained_in(ptr.offset, len) {
 587                     return Err(EvalError::Unimplemented(format!("miri does not support release part of a write-locked region")));
 588                 }
 589                 let ptr = MemoryPointer { alloc_id : ptr.alloc_id, offset: range.offset() };
 590                 trace!("Releasing write lock at {:?}, size {} until {:?}", ptr, range.len(), release_until);
 591                 if let Some(region) = release_until {
 592                     lock.status = LockStatus::RecoverAfter(region);
 593                 }
 594             }
 595
 596             // If we will not recover, we did not do anything above except for some checks. Now, erase the locks from the list.
 597             if let None = release_until {
 598                 // Delete everything that's a held write lock.  We already checked above that these are ours.
 599                 // Unfortunately, this duplicates the condition from above.  Is there anything we can do about this?
 600                 locks.retain(|lock| lock.kind == AccessKind::Read || lock.status != LockStatus::Held);
 601             }
 602         }
 603
 604         Ok(())
 605     }
 606
 607     pub(crate) fn locks_lifetime_ended(&mut self, ending_region: Option<CodeExtent>) {
 608         trace!("Releasing locks that expire at {:?}", ending_region);
 609         let cur_frame = self.cur_frame;
 610         let has_ended =  |lock: &LockInfo| -> bool {
 611             if lock.lifetime.frame != cur_frame {
 612                 return false;
 613             }
 614             match ending_region {
 615                 None => true, // When a function ends, we end *all* its locks. It's okay for a function to still have lifetime-related locks
 616                               // when it returns, that can happen e.g. with NLL when a lifetime can, but does not have to, extend beyond the
 617                               // end of a function.  Same for a function still having recoveries.
 618                 Some(ending_region) => lock.lifetime.region == Some(ending_region),
 619             }
 620         };
 621
 622         for alloc in self.alloc_map.values_mut() {
 623             for (_range, locks) in alloc.locks.iter_mut() {
 624                 // Delete everything that ends now -- i.e., keep only all the other lifetimes.
 625                 locks.retain(|lock| !has_ended(lock));
 626                 // Activate locks that get recovered now
 627                 if let Some(ending_region) = ending_region {
 628                     for lock in locks.iter_mut() {
 629                         if lock.lifetime.frame == cur_frame && lock.status == LockStatus::RecoverAfter(ending_region) {
 630                             // FIXME: Check if this triggers a conflict between active locks
 631                             lock.status = LockStatus::Held;
 632                         }
 633                     }
 634                 }
 635             }
 636         }
 637         // TODO: It may happen now that we leave empty vectors in the map.  Is it worth getting rid of them?
 638     }
 639 }
 640
 641 /// Allocation accessors
 642 impl<'a, 'tcx> Memory<'a, 'tcx> {
 643     pub fn get(&self, id: AllocId) -> EvalResult<'tcx, &Allocation> {
 644         match self.alloc_map.get(&id) {
 645             Some(alloc) => Ok(alloc),
 646             None => match self.functions.get(&id) {
 647                 Some(_) => Err(EvalError::DerefFunctionPointer),
 648                 None => Err(EvalError::DanglingPointerDeref),
 649             }
 650         }
 651     }
 652
 653     fn get_mut_unchecked(&mut self, id: AllocId) -> EvalResult<'tcx, &mut Allocation> {
 654         match self.alloc_map.get_mut(&id) {
 655             Some(alloc) => Ok(alloc),
 656             None => match self.functions.get(&id) {
 657                 Some(_) => Err(EvalError::DerefFunctionPointer),
 658                 None => Err(EvalError::DanglingPointerDeref),
 659             }
 660         }
 661     }
 662
 663     pub fn get_mut(&mut self, id: AllocId) -> EvalResult<'tcx, &mut Allocation> {
 664         let alloc = self.get_mut_unchecked(id)?;
 665         if alloc.mutable == Mutability::Mutable {
 666             Ok(alloc)
 667         } else {
 668             Err(EvalError::ModifiedConstantMemory)
 669         }
 670     }
 671
 672     pub fn get_fn(&self, ptr: MemoryPointer) -> EvalResult<'tcx, ty::Instance<'tcx>> {
 673         if ptr.offset != 0 {
 674             return Err(EvalError::InvalidFunctionPointer);
 675         }
 676         debug!("reading fn ptr: {}", ptr.alloc_id);
 677         match self.functions.get(&ptr.alloc_id) {
 678             Some(&fndef) => Ok(fndef),
 679             None => match self.alloc_map.get(&ptr.alloc_id) {
 680                 Some(_) => Err(EvalError::ExecuteMemory),
 681                 None => Err(EvalError::InvalidFunctionPointer),
 682             }
 683         }
 684     }
 685
 686     /// For debugging, print an allocation and all allocations it points to, recursively.
 687     pub fn dump_alloc(&self, id: AllocId) {
 688         self.dump_allocs(vec![id]);
 689     }
 690
 691     /// For debugging, print a list of allocations and all allocations they point to, recursively.
 692     pub fn dump_allocs(&self, mut allocs: Vec<AllocId>) {
 693         use std::fmt::Write;
 694         allocs.sort();
 695         allocs.dedup();
 696         let mut allocs_to_print = VecDeque::from(allocs);
 697         let mut allocs_seen = HashSet::new();
 698
 699         while let Some(id) = allocs_to_print.pop_front() {
 700             let mut msg = format!("Alloc {:<5} ", format!("{}:", id));
 701             let prefix_len = msg.len();
 702             let mut relocations = vec![];
 703
 704             let alloc = match (self.alloc_map.get(&id), self.functions.get(&id)) {
 705                 (Some(a), None) => a,
 706                 (None, Some(instance)) => {
 707                     trace!("{} {}", msg, instance);
 708                     continue;
 709                 },
 710                 (None, None) => {
 711                     trace!("{} (deallocated)", msg);
 712                     continue;
 713                 },
 714                 (Some(_), Some(_)) => bug!("miri invariant broken: an allocation id exists that points to both a function and a memory location"),
 715             };
 716
 717             for i in 0..(alloc.bytes.len() as u64) {
 718                 if let Some(&target_id) = alloc.relocations.get(&i) {
 719                     if allocs_seen.insert(target_id) {
 720                         allocs_to_print.push_back(target_id);
 721                     }
 722                     relocations.push((i, target_id));
 723                 }
 724                 if alloc.undef_mask.is_range_defined(i, i + 1) {
 725                     // this `as usize` is fine, since `i` came from a `usize`
 726                     write!(msg, "{:02x} ", alloc.bytes[i as usize]).unwrap();
 727                 } else {
 728                     msg.push_str("__ ");
 729                 }
 730             }
 731
 732             let immutable = match (alloc.kind, alloc.mutable) {
 733                 (Kind::UninitializedStatic, _) => " (static in the process of initialization)",
 734                 (Kind::Static, Mutability::Mutable) => " (static mut)",
 735                 (Kind::Static, Mutability::Immutable) => " (immutable)",
 736                 (Kind::Env, _) => " (env var)",
 737                 (Kind::C, _) => " (malloc)",
 738                 (Kind::Rust, _) => " (heap)",
 739                 (Kind::Stack, _) => " (stack)",
 740             };
 741             trace!("{}({} bytes, alignment {}){}", msg, alloc.bytes.len(), alloc.align, immutable);
 742
 743             if !relocations.is_empty() {
 744                 msg.clear();
 745                 write!(msg, "{:1$}", "", prefix_len).unwrap(); // Print spaces.
 746                 let mut pos = 0;
 747                 let relocation_width = (self.pointer_size() - 1) * 3;
 748                 for (i, target_id) in relocations {
 749                     // this `as usize` is fine, since we can't print more chars than `usize::MAX`
 750                     write!(msg, "{:1$}", "", ((i - pos) * 3) as usize).unwrap();
 751                     let target = format!("({})", target_id);
 752                     // this `as usize` is fine, since we can't print more chars than `usize::MAX`
 753                     write!(msg, "└{0:─^1$}┘ ", target, relocation_width as usize).unwrap();
 754                     pos = i + self.pointer_size();
 755                 }
 756                 trace!("{}", msg);
 757             }
 758         }
 759     }
 760
 761     pub fn leak_report(&self) -> usize {
 762         trace!("### LEAK REPORT ###");
 763         let leaks: Vec<_> = self.alloc_map
 764             .iter()
 765             .filter_map(|(&key, val)| {
 766                 if val.kind != Kind::Static {
 767                     Some(key)
 768                 } else {
 769                     None
 770                 }
 771             })
 772             .collect();
 773         let n = leaks.len();
 774         self.dump_allocs(leaks);
 775         n
 776     }
 777 }
 778
 779 /// Byte accessors
 780 impl<'a, 'tcx> Memory<'a, 'tcx> {
 781     fn get_bytes_unchecked(&self, ptr: MemoryPointer, size: u64, align: u64) -> EvalResult<'tcx, &[u8]> {
 782         // Zero-sized accesses can use dangling pointers, but they still have to be aligned and non-NULL
 783         if self.reads_are_aligned {
 784             self.check_align(ptr.into(), align)?;
 785         }
 786         if size == 0 {
 787             return Ok(&[]);
 788         }
 789         self.check_locks(ptr, size, AccessKind::Read)?;
 790         self.check_bounds(ptr.offset(size, self)?, true)?; // if ptr.offset is in bounds, then so is ptr (because offset checks for overflow)
 791         let alloc = self.get(ptr.alloc_id)?;
 792         assert_eq!(ptr.offset as usize as u64, ptr.offset);
 793         assert_eq!(size as usize as u64, size);
 794         let offset = ptr.offset as usize;
 795         Ok(&alloc.bytes[offset..offset + size as usize])
 796     }
 797
 798     fn get_bytes_unchecked_mut(&mut self, ptr: MemoryPointer, size: u64, align: u64) -> EvalResult<'tcx, &mut [u8]> {
 799         // Zero-sized accesses can use dangling pointers, but they still have to be aligned and non-NULL
 800         if self.writes_are_aligned {
 801             self.check_align(ptr.into(), align)?;
 802         }
 803         if size == 0 {
 804             return Ok(&mut []);
 805         }
 806         self.check_locks(ptr, size, AccessKind::Write)?;
 807         self.check_bounds(ptr.offset(size, self.layout)?, true)?; // if ptr.offset is in bounds, then so is ptr (because offset checks for overflow)
 808         let alloc = self.get_mut(ptr.alloc_id)?;
 809         assert_eq!(ptr.offset as usize as u64, ptr.offset);
 810         assert_eq!(size as usize as u64, size);
 811         let offset = ptr.offset as usize;
 812         Ok(&mut alloc.bytes[offset..offset + size as usize])
 813     }
 814
 815     fn get_bytes(&self, ptr: MemoryPointer, size: u64, align: u64) -> EvalResult<'tcx, &[u8]> {
 816         assert_ne!(size, 0);
 817         if self.relocations(ptr, size)?.count() != 0 {
 818             return Err(EvalError::ReadPointerAsBytes);
 819         }
 820         self.check_defined(ptr, size)?;
 821         self.get_bytes_unchecked(ptr, size, align)
 822     }
 823
 824     fn get_bytes_mut(&mut self, ptr: MemoryPointer, size: u64, align: u64) -> EvalResult<'tcx, &mut [u8]> {
 825         assert_ne!(size, 0);
 826         self.clear_relocations(ptr, size)?;
 827         self.mark_definedness(ptr.into(), size, true)?;
 828         self.get_bytes_unchecked_mut(ptr, size, align)
 829     }
 830 }
 831
 832 /// Reading and writing
 833 impl<'a, 'tcx> Memory<'a, 'tcx> {
 834     /// mark an allocation as being the entry point to a static (see `static_alloc` field)
 835     pub fn mark_static(&mut self, alloc_id: AllocId) {
 836         trace!("mark_static: {:?}", alloc_id);
 837         if !self.static_alloc.insert(alloc_id) {
 838             bug!("tried to mark an allocation ({:?}) as static twice", alloc_id);
 839         }
 840     }
 841
 842     /// mark an allocation pointed to by a static as static and initialized
 843     pub fn mark_inner_allocation(&mut self, alloc: AllocId, mutability: Mutability) -> EvalResult<'tcx> {
 844         // relocations into other statics are not "inner allocations"
 845         if !self.static_alloc.contains(&alloc) {
 846             self.mark_static_initalized(alloc, mutability)?;
 847         }
 848         Ok(())
 849     }
 850
 851     /// mark an allocation as static and initialized, either mutable or not
 852     pub fn mark_static_initalized(&mut self, alloc_id: AllocId, mutability: Mutability) -> EvalResult<'tcx> {
 853         trace!("mark_static_initalized {:?}, mutability: {:?}", alloc_id, mutability);
 854         // do not use `self.get_mut(alloc_id)` here, because we might have already marked a
 855         // sub-element or have circular pointers (e.g. `Rc`-cycles)
 856         let relocations = match self.alloc_map.get_mut(&alloc_id) {
 857             Some(&mut Allocation { ref mut relocations, ref mut kind, ref mut mutable, .. }) => {
 858                 match *kind {
 859                     // const eval results can refer to "locals".
 860                     // E.g. `const Foo: &u32 = &1;` refers to the temp local that stores the `1`
 861                     Kind::Stack |
 862                     // The entire point of this function
 863                     Kind::UninitializedStatic |
 864                     // In the future const eval will allow heap allocations so we'll need to protect them
 865                     // from deallocation, too
 866                     Kind::Rust |
 867                     Kind::C => {},
 868                     Kind::Static => {
 869                         trace!("mark_static_initalized: skipping already initialized static referred to by static currently being initialized");
 870                         return Ok(());
 871                     },
 872                     // FIXME: This could be allowed, but not for env vars set during miri execution
 873                     Kind::Env => return Err(EvalError::Unimplemented("statics can't refer to env vars".to_owned())),
 874                 }
 875                 *kind = Kind::Static;
 876                 *mutable = mutability;
 877                 // take out the relocations vector to free the borrow on self, so we can call
 878                 // mark recursively
 879                 mem::replace(relocations, Default::default())
 880             },
 881             None if !self.functions.contains_key(&alloc_id) => return Err(EvalError::DanglingPointerDeref),
 882             _ => return Ok(()),
 883         };
 884         // recurse into inner allocations
 885         for &alloc in relocations.values() {
 886             self.mark_inner_allocation(alloc, mutability)?;
 887         }
 888         // put back the relocations
 889         self.alloc_map.get_mut(&alloc_id).expect("checked above").relocations = relocations;
 890         Ok(())
 891     }
 892
 893     pub fn copy(&mut self, src: Pointer, dest: Pointer, size: u64, align: u64, nonoverlapping: bool) -> EvalResult<'tcx> {
 894         if size == 0 {
 895             // Empty accesses don't need to be valid pointers, but they should still be aligned
 896             if self.reads_are_aligned {
 897                 self.check_align(src, align)?;
 898             }
 899             if self.writes_are_aligned {
 900                 self.check_align(dest, align)?;
 901             }
 902             return Ok(());
 903         }
 904         let src = src.to_ptr()?;
 905         let dest = dest.to_ptr()?;
 906         self.check_relocation_edges(src, size)?;
 907
 908         let src_bytes = self.get_bytes_unchecked(src, size, align)?.as_ptr();
 909         let dest_bytes = self.get_bytes_mut(dest, size, align)?.as_mut_ptr();
 910
 911         // SAFE: The above indexing would have panicked if there weren't at least `size` bytes
 912         // behind `src` and `dest`. Also, we use the overlapping-safe `ptr::copy` if `src` and
 913         // `dest` could possibly overlap.
 914         unsafe {
 915             assert_eq!(size as usize as u64, size);
 916             if src.alloc_id == dest.alloc_id {
 917                 if nonoverlapping {
 918                     if (src.offset <= dest.offset && src.offset + size > dest.offset) ||
 919                        (dest.offset <= src.offset && dest.offset + size > src.offset) {
 920                         return Err(EvalError::Intrinsic(format!("copy_nonoverlapping called on overlapping ranges")));
 921                     }
 922                 }
 923                 ptr::copy(src_bytes, dest_bytes, size as usize);
 924             } else {
 925                 ptr::copy_nonoverlapping(src_bytes, dest_bytes, size as usize);
 926             }
 927         }
 928
 929         self.copy_undef_mask(src, dest, size)?;
 930         self.copy_relocations(src, dest, size)?;
 931
 932         Ok(())
 933     }
 934
 935     pub fn read_c_str(&self, ptr: MemoryPointer) -> EvalResult<'tcx, &[u8]> {
 936         let alloc = self.get(ptr.alloc_id)?;
 937         assert_eq!(ptr.offset as usize as u64, ptr.offset);
 938         let offset = ptr.offset as usize;
 939         match alloc.bytes[offset..].iter().position(|&c| c == 0) {
 940             Some(size) => {
 941                 if self.relocations(ptr, (size + 1) as u64)?.count() != 0 {
 942                     return Err(EvalError::ReadPointerAsBytes);
 943                 }
 944                 self.check_defined(ptr, (size + 1) as u64)?;
 945                 self.check_locks(ptr, (size + 1) as u64, AccessKind::Read)?;
 946                 Ok(&alloc.bytes[offset..offset + size])
 947             },
 948             None => Err(EvalError::UnterminatedCString(ptr)),
 949         }
 950     }
 951
 952     pub fn read_bytes(&self, ptr: Pointer, size: u64) -> EvalResult<'tcx, &[u8]> {
 953         if size == 0 {
 954             // Empty accesses don't need to be valid pointers, but they should still be non-NULL
 955             if self.reads_are_aligned {
 956                 self.check_align(ptr, 1)?;
 957             }
 958             return Ok(&[]);
 959         }
 960         self.get_bytes(ptr.to_ptr()?, size, 1)
 961     }
 962
 963     pub fn write_bytes(&mut self, ptr: Pointer, src: &[u8]) -> EvalResult<'tcx> {
 964         if src.is_empty() {
 965             // Empty accesses don't need to be valid pointers, but they should still be non-NULL
 966             if self.writes_are_aligned {
 967                 self.check_align(ptr, 1)?;
 968             }
 969             return Ok(());
 970         }
 971         let bytes = self.get_bytes_mut(ptr.to_ptr()?, src.len() as u64, 1)?;
 972         bytes.clone_from_slice(src);
 973         Ok(())
 974     }
 975
 976     pub fn write_repeat(&mut self, ptr: Pointer, val: u8, count: u64) -> EvalResult<'tcx> {
 977         if count == 0 {
 978             // Empty accesses don't need to be valid pointers, but they should still be non-NULL
 979             if self.writes_are_aligned {
 980                 self.check_align(ptr, 1)?;
 981             }
 982             return Ok(());
 983         }
 984         let bytes = self.get_bytes_mut(ptr.to_ptr()?, count, 1)?;
 985         for b in bytes { *b = val; }
 986         Ok(())
 987     }
 988
 989     pub fn read_ptr(&self, ptr: MemoryPointer) -> EvalResult<'tcx, Pointer> {
 990         let size = self.pointer_size();
 991         self.check_relocation_edges(ptr, size)?; // Make sure we don't read part of a pointer as a pointer
 992         let endianess = self.endianess();
 993         let bytes = self.get_bytes_unchecked(ptr, size, size)?;
 994         // Undef check happens *after* we established that the alignment is correct.
 995         // We must not return Ok() for unaligned pointers!
 996         if self.check_defined(ptr, size).is_err() {
 997             return Ok(PrimVal::Undef.into());
 998         }
 999         let offset = read_target_uint(endianess, bytes).unwrap();
1000         assert_eq!(offset as u64 as u128, offset);
1001         let offset = offset as u64;
1002         let alloc = self.get(ptr.alloc_id)?;
1003         match alloc.relocations.get(&ptr.offset) {
1004             Some(&alloc_id) => Ok(PrimVal::Ptr(MemoryPointer::new(alloc_id, offset)).into()),
1005             None => Ok(PrimVal::Bytes(offset as u128).into()),
1006         }
1007     }
1008
1009     pub fn write_ptr(&mut self, dest: MemoryPointer, ptr: MemoryPointer) -> EvalResult<'tcx> {
1010         self.write_usize(dest, ptr.offset as u64)?;
1011         self.get_mut(dest.alloc_id)?.relocations.insert(dest.offset, ptr.alloc_id);
1012         Ok(())
1013     }
1014
1015     pub fn write_primval(
1016         &mut self,
1017         dest: Pointer,
1018         val: PrimVal,
1019         size: u64,
1020     ) -> EvalResult<'tcx> {
1021         match val {
1022             PrimVal::Ptr(ptr) => {
1023                 assert_eq!(size, self.pointer_size());
1024                 self.write_ptr(dest.to_ptr()?, ptr)
1025             }
1026
1027             PrimVal::Bytes(bytes) => {
1028                 // We need to mask here, or the byteorder crate can die when given a u64 larger
1029                 // than fits in an integer of the requested size.
1030                 let mask = match size {
1031                     1 => !0u8 as u128,
1032                     2 => !0u16 as u128,
1033                     4 => !0u32 as u128,
1034                     8 => !0u64 as u128,
1035                     16 => !0,
1036                     n => bug!("unexpected PrimVal::Bytes size: {}", n),
1037                 };
1038                 self.write_uint(dest.to_ptr()?, bytes & mask, size)
1039             }
1040
1041             PrimVal::Undef => self.mark_definedness(dest, size, false),
1042         }
1043     }
1044
1045     pub fn read_bool(&self, ptr: MemoryPointer) -> EvalResult<'tcx, bool> {
1046         let bytes = self.get_bytes(ptr, 1, self.layout.i1_align.abi())?;
1047         match bytes[0] {
1048             0 => Ok(false),
1049             1 => Ok(true),
1050             _ => Err(EvalError::InvalidBool),
1051         }
1052     }
1053
1054     pub fn write_bool(&mut self, ptr: MemoryPointer, b: bool) -> EvalResult<'tcx> {
1055         let align = self.layout.i1_align.abi();
1056         self.get_bytes_mut(ptr, 1, align)
1057             .map(|bytes| bytes[0] = b as u8)
1058     }
1059
1060     fn int_align(&self, size: u64) -> EvalResult<'tcx, u64> {
1061         match size {
1062             1 => Ok(self.layout.i8_align.abi()),
1063             2 => Ok(self.layout.i16_align.abi()),
1064             4 => Ok(self.layout.i32_align.abi()),
1065             8 => Ok(self.layout.i64_align.abi()),
1066             16 => Ok(self.layout.i128_align.abi()),
1067             _ => bug!("bad integer size: {}", size),
1068         }
1069     }
1070
1071     pub fn read_int(&self, ptr: MemoryPointer, size: u64) -> EvalResult<'tcx, i128> {
1072         let align = self.int_align(size)?;
1073         self.get_bytes(ptr, size, align).map(|b| read_target_int(self.endianess(), b).unwrap())
1074     }
1075
1076     pub fn write_int(&mut self, ptr: MemoryPointer, n: i128, size: u64) -> EvalResult<'tcx> {
1077         let align = self.int_align(size)?;
1078         let endianess = self.endianess();
1079         let b = self.get_bytes_mut(ptr, size, align)?;
1080         write_target_int(endianess, b, n).unwrap();
1081         Ok(())
1082     }
1083
1084     pub fn read_uint(&self, ptr: MemoryPointer, size: u64) -> EvalResult<'tcx, u128> {
1085         let align = self.int_align(size)?;
1086         self.get_bytes(ptr, size, align).map(|b| read_target_uint(self.endianess(), b).unwrap())
1087     }
1088
1089     pub fn write_uint(&mut self, ptr: MemoryPointer, n: u128, size: u64) -> EvalResult<'tcx> {
1090         let align = self.int_align(size)?;
1091         let endianess = self.endianess();
1092         let b = self.get_bytes_mut(ptr, size, align)?;
1093         write_target_uint(endianess, b, n).unwrap();
1094         Ok(())
1095     }
1096
1097     pub fn read_isize(&self, ptr: MemoryPointer) -> EvalResult<'tcx, i64> {
1098         self.read_int(ptr, self.pointer_size()).map(|i| i as i64)
1099     }
1100
1101     pub fn write_isize(&mut self, ptr: MemoryPointer, n: i64) -> EvalResult<'tcx> {
1102         let size = self.pointer_size();
1103         self.write_int(ptr, n as i128, size)
1104     }
1105
1106     pub fn read_usize(&self, ptr: MemoryPointer) -> EvalResult<'tcx, u64> {
1107         self.read_uint(ptr, self.pointer_size()).map(|i| i as u64)
1108     }
1109
1110     pub fn write_usize(&mut self, ptr: MemoryPointer, n: u64) -> EvalResult<'tcx> {
1111         let size = self.pointer_size();
1112         self.write_uint(ptr, n as u128, size)
1113     }
1114
1115     pub fn write_f32(&mut self, ptr: MemoryPointer, f: f32) -> EvalResult<'tcx> {
1116         let endianess = self.endianess();
1117         let align = self.layout.f32_align.abi();
1118         let b = self.get_bytes_mut(ptr, 4, align)?;
1119         write_target_f32(endianess, b, f).unwrap();
1120         Ok(())
1121     }
1122
1123     pub fn write_f64(&mut self, ptr: MemoryPointer, f: f64) -> EvalResult<'tcx> {
1124         let endianess = self.endianess();
1125         let align = self.layout.f64_align.abi();
1126         let b = self.get_bytes_mut(ptr, 8, align)?;
1127         write_target_f64(endianess, b, f).unwrap();
1128         Ok(())
1129     }
1130
1131     pub fn read_f32(&self, ptr: MemoryPointer) -> EvalResult<'tcx, f32> {
1132         self.get_bytes(ptr, 4, self.layout.f32_align.abi())
1133             .map(|b| read_target_f32(self.endianess(), b).unwrap())
1134     }
1135
1136     pub fn read_f64(&self, ptr: MemoryPointer) -> EvalResult<'tcx, f64> {
1137         self.get_bytes(ptr, 8, self.layout.f64_align.abi())
1138             .map(|b| read_target_f64(self.endianess(), b).unwrap())
1139     }
1140 }
1141
1142 /// Relocations
1143 impl<'a, 'tcx> Memory<'a, 'tcx> {
1144     fn relocations(&self, ptr: MemoryPointer, size: u64)
1145         -> EvalResult<'tcx, btree_map::Range<u64, AllocId>>
1146     {
1147         let start = ptr.offset.saturating_sub(self.pointer_size() - 1);
1148         let end = ptr.offset + size;
1149         Ok(self.get(ptr.alloc_id)?.relocations.range(start..end))
1150     }
1151
1152     fn clear_relocations(&mut self, ptr: MemoryPointer, size: u64) -> EvalResult<'tcx> {
1153         // Find all relocations overlapping the given range.
1154         let keys: Vec<_> = self.relocations(ptr, size)?.map(|(&k, _)| k).collect();
1155         if keys.is_empty() { return Ok(()); }
1156
1157         // Find the start and end of the given range and its outermost relocations.
1158         let start = ptr.offset;
1159         let end = start + size;
1160         let first = *keys.first().unwrap();
1161         let last = *keys.last().unwrap() + self.pointer_size();
1162
1163         let alloc = self.get_mut(ptr.alloc_id)?;
1164
1165         // Mark parts of the outermost relocations as undefined if they partially fall outside the
1166         // given range.
1167         if first < start { alloc.undef_mask.set_range(first, start, false); }
1168         if last > end { alloc.undef_mask.set_range(end, last, false); }
1169
1170         // Forget all the relocations.
1171         for k in keys { alloc.relocations.remove(&k); }
1172
1173         Ok(())
1174     }
1175
1176     fn check_relocation_edges(&self, ptr: MemoryPointer, size: u64) -> EvalResult<'tcx> {
1177         let overlapping_start = self.relocations(ptr, 0)?.count();
1178         let overlapping_end = self.relocations(ptr.offset(size, self.layout)?, 0)?.count();
1179         if overlapping_start + overlapping_end != 0 {
1180             return Err(EvalError::ReadPointerAsBytes);
1181         }
1182         Ok(())
1183     }
1184
1185     fn copy_relocations(&mut self, src: MemoryPointer, dest: MemoryPointer, size: u64) -> EvalResult<'tcx> {
1186         let relocations: Vec<_> = self.relocations(src, size)?
1187             .map(|(&offset, &alloc_id)| {
1188                 // Update relocation offsets for the new positions in the destination allocation.
1189                 (offset + dest.offset - src.offset, alloc_id)
1190             })
1191             .collect();
1192         self.get_mut(dest.alloc_id)?.relocations.extend(relocations);
1193         Ok(())
1194     }
1195 }
1196
1197 /// Undefined bytes
1198 impl<'a, 'tcx> Memory<'a, 'tcx> {
1199     // FIXME(solson): This is a very naive, slow version.
1200     fn copy_undef_mask(&mut self, src: MemoryPointer, dest: MemoryPointer, size: u64) -> EvalResult<'tcx> {
1201         // The bits have to be saved locally before writing to dest in case src and dest overlap.
1202         assert_eq!(size as usize as u64, size);
1203         let mut v = Vec::with_capacity(size as usize);
1204         for i in 0..size {
1205             let defined = self.get(src.alloc_id)?.undef_mask.get(src.offset + i);
1206             v.push(defined);
1207         }
1208         for (i, defined) in v.into_iter().enumerate() {
1209             self.get_mut(dest.alloc_id)?.undef_mask.set(dest.offset + i as u64, defined);
1210         }
1211         Ok(())
1212     }
1213
1214     fn check_defined(&self, ptr: MemoryPointer, size: u64) -> EvalResult<'tcx> {
1215         let alloc = self.get(ptr.alloc_id)?;
1216         if !alloc.undef_mask.is_range_defined(ptr.offset, ptr.offset + size) {
1217             return Err(EvalError::ReadUndefBytes);
1218         }
1219         Ok(())
1220     }
1221
1222     pub fn mark_definedness(
1223         &mut self,
1224         ptr: Pointer,
1225         size: u64,
1226         new_state: bool
1227     ) -> EvalResult<'tcx> {
1228         if size == 0 {
1229             return Ok(())
1230         }
1231         let ptr = ptr.to_ptr()?;
1232         let mut alloc = self.get_mut(ptr.alloc_id)?;
1233         alloc.undef_mask.set_range(ptr.offset, ptr.offset + size, new_state);
1234         Ok(())
1235     }
1236 }
1237
1238 ////////////////////////////////////////////////////////////////////////////////
1239 // Methods to access integers in the target endianess
1240 ////////////////////////////////////////////////////////////////////////////////
1241
1242 fn write_target_uint(endianess: layout::Endian, mut target: &mut [u8], data: u128) -> Result<(), io::Error> {
1243     let len = target.len();
1244     match endianess {
1245         layout::Endian::Little => target.write_uint128::<LittleEndian>(data, len),
1246         layout::Endian::Big => target.write_uint128::<BigEndian>(data, len),
1247     }
1248 }
1249 fn write_target_int(endianess: layout::Endian, mut target: &mut [u8], data: i128) -> Result<(), io::Error> {
1250     let len = target.len();
1251     match endianess {
1252         layout::Endian::Little => target.write_int128::<LittleEndian>(data, len),
1253         layout::Endian::Big => target.write_int128::<BigEndian>(data, len),
1254     }
1255 }
1256
1257 fn read_target_uint(endianess: layout::Endian, mut source: &[u8]) -> Result<u128, io::Error> {
1258     match endianess {
1259         layout::Endian::Little => source.read_uint128::<LittleEndian>(source.len()),
1260         layout::Endian::Big => source.read_uint128::<BigEndian>(source.len()),
1261     }
1262 }
1263 fn read_target_int(endianess: layout::Endian, mut source: &[u8]) -> Result<i128, io::Error> {
1264     match endianess {
1265         layout::Endian::Little => source.read_int128::<LittleEndian>(source.len()),
1266         layout::Endian::Big => source.read_int128::<BigEndian>(source.len()),
1267     }
1268 }
1269
1270 ////////////////////////////////////////////////////////////////////////////////
1271 // Methods to access floats in the target endianess
1272 ////////////////////////////////////////////////////////////////////////////////
1273
1274 fn write_target_f32(endianess: layout::Endian, mut target: &mut [u8], data: f32) -> Result<(), io::Error> {
1275     match endianess {
1276         layout::Endian::Little => target.write_f32::<LittleEndian>(data),
1277         layout::Endian::Big => target.write_f32::<BigEndian>(data),
1278     }
1279 }
1280 fn write_target_f64(endianess: layout::Endian, mut target: &mut [u8], data: f64) -> Result<(), io::Error> {
1281     match endianess {
1282         layout::Endian::Little => target.write_f64::<LittleEndian>(data),
1283         layout::Endian::Big => target.write_f64::<BigEndian>(data),
1284     }
1285 }
1286
1287 fn read_target_f32(endianess: layout::Endian, mut source: &[u8]) -> Result<f32, io::Error> {
1288     match endianess {
1289         layout::Endian::Little => source.read_f32::<LittleEndian>(),
1290         layout::Endian::Big => source.read_f32::<BigEndian>(),
1291     }
1292 }
1293 fn read_target_f64(endianess: layout::Endian, mut source: &[u8]) -> Result<f64, io::Error> {
1294     match endianess {
1295         layout::Endian::Little => source.read_f64::<LittleEndian>(),
1296         layout::Endian::Big => source.read_f64::<BigEndian>(),
1297     }
1298 }
1299
1300 ////////////////////////////////////////////////////////////////////////////////
1301 // Undefined byte tracking
1302 ////////////////////////////////////////////////////////////////////////////////
1303
1304 type Block = u64;
1305 const BLOCK_SIZE: u64 = 64;
1306
1307 #[derive(Clone, Debug)]
1308 pub struct UndefMask {
1309     blocks: Vec<Block>,
1310     len: u64,
1311 }
1312
1313 impl UndefMask {
1314     fn new(size: u64) -> Self {
1315         let mut m = UndefMask {
1316             blocks: vec![],
1317             len: 0,
1318         };
1319         m.grow(size, false);
1320         m
1321     }
1322
1323     /// Check whether the range `start..end` (end-exclusive) is entirely defined.
1324     pub fn is_range_defined(&self, start: u64, end: u64) -> bool {
1325         if end > self.len { return false; }
1326         for i in start..end {
1327             if !self.get(i) { return false; }
1328         }
1329         true
1330     }
1331
1332     fn set_range(&mut self, start: u64, end: u64, new_state: bool) {
1333         let len = self.len;
1334         if end > len { self.grow(end - len, new_state); }
1335         self.set_range_inbounds(start, end, new_state);
1336     }
1337
1338     fn set_range_inbounds(&mut self, start: u64, end: u64, new_state: bool) {
1339         for i in start..end { self.set(i, new_state); }
1340     }
1341
1342     fn get(&self, i: u64) -> bool {
1343         let (block, bit) = bit_index(i);
1344         (self.blocks[block] & 1 << bit) != 0
1345     }
1346
1347     fn set(&mut self, i: u64, new_state: bool) {
1348         let (block, bit) = bit_index(i);
1349         if new_state {
1350             self.blocks[block] |= 1 << bit;
1351         } else {
1352             self.blocks[block] &= !(1 << bit);
1353         }
1354     }
1355
1356     fn grow(&mut self, amount: u64, new_state: bool) {
1357         let unused_trailing_bits = self.blocks.len() as u64 * BLOCK_SIZE - self.len;
1358         if amount > unused_trailing_bits {
1359             let additional_blocks = amount / BLOCK_SIZE + 1;
1360             assert_eq!(additional_blocks as usize as u64, additional_blocks);
1361             self.blocks.extend(iter::repeat(0).take(additional_blocks as usize));
1362         }
1363         let start = self.len;
1364         self.len += amount;
1365         self.set_range_inbounds(start, start + amount, new_state);
1366     }
1367 }
1368
1369 fn bit_index(bits: u64) -> (usize, usize) {
1370     let a = bits / BLOCK_SIZE;
1371     let b = bits % BLOCK_SIZE;
1372     assert_eq!(a as usize as u64, a);
1373     assert_eq!(b as usize as u64, b);
1374     (a as usize, b as usize)
1375 }
1376
1377 ////////////////////////////////////////////////////////////////////////////////
1378 // Unaligned accesses
1379 ////////////////////////////////////////////////////////////////////////////////
1380
1381 pub(crate) trait HasMemory<'a, 'tcx> {
1382     fn memory_mut(&mut self) -> &mut Memory<'a, 'tcx>;
1383     fn memory(&self) -> &Memory<'a, 'tcx>;
1384
1385     // These are not supposed to be overriden.
1386     fn read_maybe_aligned<F, T>(&mut self, aligned: bool, f: F) -> EvalResult<'tcx, T>
1387         where F: FnOnce(&mut Self) -> EvalResult<'tcx, T>
1388     {
1389         assert!(self.memory_mut().reads_are_aligned, "Unaligned reads must not be nested");
1390         self.memory_mut().reads_are_aligned = aligned;
1391         let t = f(self);
1392         self.memory_mut().reads_are_aligned = true;
1393         t
1394     }
1395
1396     fn write_maybe_aligned<F, T>(&mut self, aligned: bool, f: F) -> EvalResult<'tcx, T>
1397         where F: FnOnce(&mut Self) -> EvalResult<'tcx, T>
1398     {
1399         assert!(self.memory_mut().writes_are_aligned, "Unaligned writes must not be nested");
1400         self.memory_mut().writes_are_aligned = aligned;
1401         let t = f(self);
1402         self.memory_mut().writes_are_aligned = true;
1403         t
1404     }
1405 }
1406
1407 impl<'a, 'tcx> HasMemory<'a, 'tcx> for Memory<'a, 'tcx> {
1408     #[inline]
1409     fn memory_mut(&mut self) -> &mut Memory<'a, 'tcx> {
1410         self
1411     }
1412
1413     #[inline]
1414     fn memory(&self) -> &Memory<'a, 'tcx> {
1415         self
1416     }
1417 }
1418
1419 impl<'a, 'tcx> HasMemory<'a, 'tcx> for EvalContext<'a, 'tcx> {
1420     #[inline]
1421     fn memory_mut(&mut self) -> &mut Memory<'a, 'tcx> {
1422         &mut self.memory
1423     }
1424
1425     #[inline]
1426     fn memory(&self) -> &Memory<'a, 'tcx> {
1427         &self.memory
1428     }
1429 }
1430
1431 ////////////////////////////////////////////////////////////////////////////////
1432 // Pointer arithmetic
1433 ////////////////////////////////////////////////////////////////////////////////
1434
1435 pub trait PointerArithmetic : layout::HasDataLayout {
1436     // These are not supposed to be overriden.
1437
1438     //// Trunace the given value to the pointer size; also return whether there was an overflow
1439     fn truncate_to_ptr(self, val: u128) -> (u64, bool) {
1440         let max_ptr_plus_1 = 1u128 << self.data_layout().pointer_size.bits();
1441         ((val % max_ptr_plus_1) as u64, val >= max_ptr_plus_1)
1442     }
1443
1444     // Overflow checking only works properly on the range from -u64 to +u64.
1445     fn overflowing_signed_offset(self, val: u64, i: i128) -> (u64, bool) {
1446         // FIXME: is it possible to over/underflow here?
1447         if i < 0 {
1448             // trickery to ensure that i64::min_value() works fine
1449             // this formula only works for true negative values, it panics for zero!
1450             let n = u64::max_value() - (i as u64) + 1;
1451             val.overflowing_sub(n)
1452         } else {
1453             self.overflowing_offset(val, i as u64)
1454         }
1455     }
1456
1457     fn overflowing_offset(self, val: u64, i: u64) -> (u64, bool) {
1458         let (res, over1) = val.overflowing_add(i);
1459         let (res, over2) = self.truncate_to_ptr(res as u128);
1460         (res, over1 || over2)
1461     }
1462
1463     fn signed_offset<'tcx>(self, val: u64, i: i64) -> EvalResult<'tcx, u64> {
1464         let (res, over) = self.overflowing_signed_offset(val, i as i128);
1465         if over {
1466             Err(EvalError::OverflowingMath)
1467         } else {
1468             Ok(res)
1469         }
1470     }
1471
1472     fn offset<'tcx>(self, val: u64, i: u64) -> EvalResult<'tcx, u64> {
1473         let (res, over) = self.overflowing_offset(val, i);
1474         if over {
1475             Err(EvalError::OverflowingMath)
1476         } else {
1477             Ok(res)
1478         }
1479     }
1480
1481     fn wrapping_signed_offset(self, val: u64, i: i64) -> u64 {
1482         self.overflowing_signed_offset(val, i as i128).0
1483     }
1484 }
1485
1486 impl<T: layout::HasDataLayout> PointerArithmetic for T {}
1487
1488 impl<'a, 'tcx> layout::HasDataLayout for &'a Memory<'a, 'tcx> {
1489     #[inline]
1490     fn data_layout(&self) -> &TargetDataLayout {
1491         self.layout
1492     }
1493 }
1494 impl<'a, 'tcx> layout::HasDataLayout for &'a EvalContext<'a, 'tcx> {
1495     #[inline]
1496     fn data_layout(&self) -> &TargetDataLayout {
1497         self.memory().layout
1498     }
1499 }
1500
1501 impl<'c, 'b, 'a, 'tcx> layout::HasDataLayout for &'c &'b mut EvalContext<'a, 'tcx> {
1502     #[inline]
1503     fn data_layout(&self) -> &TargetDataLayout {
1504         self.memory().layout
1505     }
1506 }