src/memory.rs

   1 use byteorder::{ByteOrder, NativeEndian, ReadBytesExt, WriteBytesExt};
   2 use std::collections::Bound::{Included, Excluded};
   3 use std::collections::{btree_map, BTreeMap, HashMap, HashSet, VecDeque};
   4 use std::{iter, mem, ptr};
   5
   6 use error::{EvalError, EvalResult};
   7 use primval::PrimVal;
   8
   9 ////////////////////////////////////////////////////////////////////////////////
  10 // Value representations
  11 ////////////////////////////////////////////////////////////////////////////////
  12
  13 #[derive(Clone, Debug, Eq, PartialEq)]
  14 pub enum Repr {
  15     /// Representation for a non-aggregate type such as a boolean, integer, character or pointer.
  16     Primitive {
  17         size: usize
  18     },
  19
  20     /// The representation for aggregate types including structs, enums, and tuples.
  21     Aggregate {
  22         /// The size of the discriminant (an integer). Should be between 0 and 8. Always 0 for
  23         /// structs and tuples.
  24         discr_size: usize,
  25
  26         /// The size of the entire aggregate, including the discriminant.
  27         size: usize,
  28
  29         /// The representations of the contents of each variant.
  30         variants: Vec<Vec<FieldRepr>>,
  31     },
  32
  33     Array {
  34         elem_size: usize,
  35
  36         /// Number of elements.
  37         length: usize,
  38     },
  39 }
  40
  41 #[derive(Copy, Clone, Debug, Eq, PartialEq)]
  42 pub struct FieldRepr {
  43     pub offset: usize,
  44     pub size: usize,
  45 }
  46
  47 impl Repr {
  48     pub fn size(&self) -> usize {
  49         match *self {
  50             Repr::Primitive { size } => size,
  51             Repr::Aggregate { size, .. } => size,
  52             Repr::Array { elem_size, length } => elem_size * length,
  53         }
  54     }
  55 }
  56
  57 ////////////////////////////////////////////////////////////////////////////////
  58 // Allocations and pointers
  59 ////////////////////////////////////////////////////////////////////////////////
  60
  61 #[derive(Copy, Clone, Debug, Eq, PartialEq)]
  62 pub struct AllocId(u64);
  63
  64 #[derive(Debug)]
  65 pub struct Allocation {
  66     pub bytes: Box<[u8]>,
  67     pub relocations: BTreeMap<usize, AllocId>,
  68     pub undef_mask: UndefMask,
  69 }
  70
  71 #[derive(Copy, Clone, Debug, Eq, PartialEq)]
  72 pub struct Pointer {
  73     pub alloc_id: AllocId,
  74     pub offset: usize,
  75 }
  76
  77 impl Pointer {
  78     pub fn offset(self, i: isize) -> Self {
  79         Pointer { offset: (self.offset as isize + i) as usize, ..self }
  80     }
  81 }
  82
  83 ////////////////////////////////////////////////////////////////////////////////
  84 // Top-level interpreter memory
  85 ////////////////////////////////////////////////////////////////////////////////
  86
  87 pub struct Memory {
  88     alloc_map: HashMap<u64, Allocation>,
  89     next_id: u64,
  90     pub pointer_size: usize,
  91 }
  92
  93 impl Memory {
  94     pub fn new() -> Self {
  95         Memory {
  96             alloc_map: HashMap::new(),
  97             next_id: 0,
  98
  99             // TODO(tsion): Should this be host's or target's usize?
 100             pointer_size: mem::size_of::<usize>(),
 101         }
 102     }
 103
 104     pub fn allocate(&mut self, size: usize) -> Pointer {
 105         let id = AllocId(self.next_id);
 106         let alloc = Allocation {
 107             bytes: vec![0; size].into_boxed_slice(),
 108             relocations: BTreeMap::new(),
 109             undef_mask: UndefMask::new(size),
 110         };
 111         self.alloc_map.insert(self.next_id, alloc);
 112         self.next_id += 1;
 113         Pointer {
 114             alloc_id: id,
 115             offset: 0,
 116         }
 117     }
 118
 119     ////////////////////////////////////////////////////////////////////////////////
 120     // Allocation accessors
 121     ////////////////////////////////////////////////////////////////////////////////
 122
 123     pub fn get(&self, id: AllocId) -> EvalResult<&Allocation> {
 124         self.alloc_map.get(&id.0).ok_or(EvalError::DanglingPointerDeref)
 125     }
 126
 127     pub fn get_mut(&mut self, id: AllocId) -> EvalResult<&mut Allocation> {
 128         self.alloc_map.get_mut(&id.0).ok_or(EvalError::DanglingPointerDeref)
 129     }
 130
 131     /// Print an allocation and all allocations it points to, recursively.
 132     pub fn dump(&self, id: AllocId) {
 133         let mut allocs_seen = HashSet::new();
 134         let mut allocs_to_print = VecDeque::new();
 135         allocs_to_print.push_back(id);
 136
 137         while let Some(id) = allocs_to_print.pop_front() {
 138             allocs_seen.insert(id.0);
 139             let alloc = self.get(id).unwrap();
 140             let prefix = format!("Alloc {:<5} ", format!("{}:", id.0));
 141             print!("{}", prefix);
 142             let mut relocations = vec![];
 143
 144             for i in 0..alloc.bytes.len() {
 145                 if let Some(&target_id) = alloc.relocations.get(&i) {
 146                     if !allocs_seen.contains(&target_id.0) {
 147                         allocs_to_print.push_back(target_id);
 148                     }
 149                     relocations.push((i, target_id.0));
 150                 }
 151                 if alloc.undef_mask.is_range_defined(i, i+1) {
 152                     print!("{:02x} ", alloc.bytes[i]);
 153                 } else {
 154                     print!("__ ");
 155                 }
 156             }
 157             println!("");
 158
 159             if !relocations.is_empty() {
 160                 print!("{:1$}", "", prefix.len()); // Print spaces.
 161                 let mut pos = 0;
 162                 let relocation_width = (self.pointer_size - 1) * 3;
 163                 for (i, target_id) in relocations {
 164                     print!("{:1$}", "", (i - pos) * 3);
 165                     print!("└{0:─^1$}┘ ", format!("({})", target_id), relocation_width);
 166                     pos = i + self.pointer_size;
 167                 }
 168                 println!("");
 169             }
 170         }
 171     }
 172
 173     ////////////////////////////////////////////////////////////////////////////////
 174     // Byte accessors
 175     ////////////////////////////////////////////////////////////////////////////////
 176
 177     fn get_bytes_unchecked(&self, ptr: Pointer, size: usize) -> EvalResult<&[u8]> {
 178         let alloc = try!(self.get(ptr.alloc_id));
 179         if ptr.offset + size > alloc.bytes.len() {
 180             return Err(EvalError::PointerOutOfBounds);
 181         }
 182         Ok(&alloc.bytes[ptr.offset..ptr.offset + size])
 183     }
 184
 185     fn get_bytes_unchecked_mut(&mut self, ptr: Pointer, size: usize) -> EvalResult<&mut [u8]> {
 186         let alloc = try!(self.get_mut(ptr.alloc_id));
 187         if ptr.offset + size > alloc.bytes.len() {
 188             return Err(EvalError::PointerOutOfBounds);
 189         }
 190         Ok(&mut alloc.bytes[ptr.offset..ptr.offset + size])
 191     }
 192
 193     fn get_bytes(&self, ptr: Pointer, size: usize) -> EvalResult<&[u8]> {
 194         if try!(self.relocations(ptr, size)).count() != 0 {
 195             return Err(EvalError::ReadPointerAsBytes);
 196         }
 197         try!(self.check_defined(ptr, size));
 198         self.get_bytes_unchecked(ptr, size)
 199     }
 200
 201     fn get_bytes_mut(&mut self, ptr: Pointer, size: usize) -> EvalResult<&mut [u8]> {
 202         try!(self.clear_relocations(ptr, size));
 203         try!(self.mark_definedness(ptr, size, true));
 204         self.get_bytes_unchecked_mut(ptr, size)
 205     }
 206
 207     ////////////////////////////////////////////////////////////////////////////////
 208     // Reading and writing
 209     ////////////////////////////////////////////////////////////////////////////////
 210
 211     pub fn copy(&mut self, src: Pointer, dest: Pointer, size: usize) -> EvalResult<()> {
 212         try!(self.check_relocation_edges(src, size));
 213
 214         let src_bytes = try!(self.get_bytes_unchecked_mut(src, size)).as_mut_ptr();
 215         let dest_bytes = try!(self.get_bytes_mut(dest, size)).as_mut_ptr();
 216
 217         // SAFE: The above indexing would have panicked if there weren't at least `size` bytes
 218         // behind `src` and `dest`. Also, we use the overlapping-safe `ptr::copy` if `src` and
 219         // `dest` could possibly overlap.
 220         unsafe {
 221             if src.alloc_id == dest.alloc_id {
 222                 ptr::copy(src_bytes, dest_bytes, size);
 223             } else {
 224                 ptr::copy_nonoverlapping(src_bytes, dest_bytes, size);
 225             }
 226         }
 227
 228         try!(self.copy_undef_mask(src, dest, size));
 229         try!(self.copy_relocations(src, dest, size));
 230
 231         Ok(())
 232     }
 233
 234     pub fn write_bytes(&mut self, ptr: Pointer, src: &[u8]) -> EvalResult<()> {
 235         self.get_bytes_mut(ptr, src.len()).map(|dest| dest.clone_from_slice(src))
 236     }
 237
 238     pub fn read_ptr(&self, ptr: Pointer) -> EvalResult<Pointer> {
 239         let size = self.pointer_size;
 240         try!(self.check_defined(ptr, size));
 241         let offset = try!(self.get_bytes_unchecked(ptr, size))
 242             .read_uint::<NativeEndian>(size).unwrap() as usize;
 243         let alloc = try!(self.get(ptr.alloc_id));
 244         match alloc.relocations.get(&ptr.offset) {
 245             Some(&alloc_id) => Ok(Pointer { alloc_id: alloc_id, offset: offset }),
 246             None => Err(EvalError::ReadBytesAsPointer),
 247         }
 248     }
 249
 250     pub fn write_ptr(&mut self, dest: Pointer, ptr: Pointer) -> EvalResult<()> {
 251         {
 252             let size = self.pointer_size;
 253             let mut bytes = try!(self.get_bytes_mut(dest, size));
 254             bytes.write_uint::<NativeEndian>(ptr.offset as u64, size).unwrap();
 255         }
 256         try!(self.get_mut(dest.alloc_id)).relocations.insert(dest.offset, ptr.alloc_id);
 257         Ok(())
 258     }
 259
 260     pub fn write_primval(&mut self, ptr: Pointer, val: PrimVal) -> EvalResult<()> {
 261         let pointer_size = self.pointer_size;
 262         match val {
 263             PrimVal::Bool(b) => self.write_bool(ptr, b),
 264             PrimVal::I8(n)   => self.write_int(ptr, n as i64, 1),
 265             PrimVal::I16(n)  => self.write_int(ptr, n as i64, 2),
 266             PrimVal::I32(n)  => self.write_int(ptr, n as i64, 4),
 267             PrimVal::I64(n)  => self.write_int(ptr, n as i64, 8),
 268             PrimVal::U8(n)   => self.write_uint(ptr, n as u64, 1),
 269             PrimVal::U16(n)  => self.write_uint(ptr, n as u64, 2),
 270             PrimVal::U32(n)  => self.write_uint(ptr, n as u64, 4),
 271             PrimVal::U64(n)  => self.write_uint(ptr, n as u64, 8),
 272             PrimVal::IntegerPtr(n) => self.write_uint(ptr, n as u64, pointer_size),
 273             PrimVal::AbstractPtr(_p) => unimplemented!(),
 274         }
 275     }
 276
 277     pub fn read_bool(&self, ptr: Pointer) -> EvalResult<bool> {
 278         let bytes = try!(self.get_bytes(ptr, 1));
 279         match bytes[0] {
 280             0 => Ok(false),
 281             1 => Ok(true),
 282             _ => Err(EvalError::InvalidBool),
 283         }
 284     }
 285
 286     pub fn write_bool(&mut self, ptr: Pointer, b: bool) -> EvalResult<()> {
 287         self.get_bytes_mut(ptr, 1).map(|bytes| bytes[0] = b as u8)
 288     }
 289
 290     pub fn read_int(&self, ptr: Pointer, size: usize) -> EvalResult<i64> {
 291         self.get_bytes(ptr, size).map(|mut b| b.read_int::<NativeEndian>(size).unwrap())
 292     }
 293
 294     pub fn write_int(&mut self, ptr: Pointer, n: i64, size: usize) -> EvalResult<()> {
 295         self.get_bytes_mut(ptr, size).map(|mut b| b.write_int::<NativeEndian>(n, size).unwrap())
 296     }
 297
 298     pub fn read_uint(&self, ptr: Pointer, size: usize) -> EvalResult<u64> {
 299         self.get_bytes(ptr, size).map(|mut b| b.read_uint::<NativeEndian>(size).unwrap())
 300     }
 301
 302     pub fn write_uint(&mut self, ptr: Pointer, n: u64, size: usize) -> EvalResult<()> {
 303         self.get_bytes_mut(ptr, size).map(|mut b| b.write_uint::<NativeEndian>(n, size).unwrap())
 304     }
 305
 306     pub fn read_isize(&self, ptr: Pointer) -> EvalResult<i64> {
 307         self.read_int(ptr, self.pointer_size)
 308     }
 309
 310     pub fn write_isize(&mut self, ptr: Pointer, n: i64) -> EvalResult<()> {
 311         let size = self.pointer_size;
 312         self.write_int(ptr, n, size)
 313     }
 314
 315     pub fn read_usize(&self, ptr: Pointer) -> EvalResult<u64> {
 316         self.read_uint(ptr, self.pointer_size)
 317     }
 318
 319     pub fn write_usize(&mut self, ptr: Pointer, n: u64) -> EvalResult<()> {
 320         let size = self.pointer_size;
 321         self.write_uint(ptr, n, size)
 322     }
 323
 324     ////////////////////////////////////////////////////////////////////////////////
 325     // Relocations
 326     ////////////////////////////////////////////////////////////////////////////////
 327
 328     fn relocations(&self, ptr: Pointer, size: usize)
 329         -> EvalResult<btree_map::Range<usize, AllocId>>
 330     {
 331         let start = ptr.offset.saturating_sub(self.pointer_size - 1);
 332         let end = start + size;
 333         Ok(try!(self.get(ptr.alloc_id)).relocations.range(Included(&start), Excluded(&end)))
 334     }
 335
 336     fn clear_relocations(&mut self, ptr: Pointer, size: usize) -> EvalResult<()> {
 337         // Find all relocations overlapping the given range.
 338         let keys: Vec<_> = try!(self.relocations(ptr, size)).map(|(&k, _)| k).collect();
 339         if keys.len() == 0 { return Ok(()); }
 340
 341         // Find the start and end of the given range and its outermost relocations.
 342         let start = ptr.offset;
 343         let end = start + size;
 344         let first = *keys.first().unwrap();
 345         let last = *keys.last().unwrap() + self.pointer_size;
 346
 347         let alloc = try!(self.get_mut(ptr.alloc_id));
 348
 349         // Mark parts of the outermost relocations as undefined if they partially fall outside the
 350         // given range.
 351         if first < start { alloc.undef_mask.set_range(first, start, false); }
 352         if last > end { alloc.undef_mask.set_range(end, last, false); }
 353
 354         // Forget all the relocations.
 355         for k in keys { alloc.relocations.remove(&k); }
 356
 357         Ok(())
 358     }
 359
 360     fn check_relocation_edges(&self, ptr: Pointer, size: usize) -> EvalResult<()> {
 361         let overlapping_start = try!(self.relocations(ptr, 0)).count();
 362         let overlapping_end = try!(self.relocations(ptr.offset(size as isize), 0)).count();
 363         if overlapping_start + overlapping_end != 0 {
 364             return Err(EvalError::ReadPointerAsBytes);
 365         }
 366         Ok(())
 367     }
 368
 369     fn copy_relocations(&mut self, src: Pointer, dest: Pointer, size: usize) -> EvalResult<()> {
 370         let relocations: Vec<_> = try!(self.relocations(src, size))
 371             .map(|(&offset, &alloc_id)| {
 372                 // Update relocation offsets for the new positions in the destination allocation.
 373                 (offset + dest.offset - src.offset, alloc_id)
 374             })
 375             .collect();
 376         try!(self.get_mut(dest.alloc_id)).relocations.extend(relocations);
 377         Ok(())
 378     }
 379
 380     ////////////////////////////////////////////////////////////////////////////////
 381     // Undefined bytes
 382     ////////////////////////////////////////////////////////////////////////////////
 383
 384     // FIXME(tsino): This is a very naive, slow version.
 385     fn copy_undef_mask(&mut self, src: Pointer, dest: Pointer, size: usize) -> EvalResult<()> {
 386         // The bits have to be saved locally before writing to dest in case src and dest overlap.
 387         let mut v = Vec::with_capacity(size);
 388         for i in 0..size {
 389             let defined = try!(self.get(src.alloc_id)).undef_mask.get(src.offset + i);
 390             v.push(defined);
 391         }
 392         for (i, defined) in v.into_iter().enumerate() {
 393             try!(self.get_mut(dest.alloc_id)).undef_mask.set(dest.offset + i, defined);
 394         }
 395         Ok(())
 396     }
 397
 398     fn check_defined(&self, ptr: Pointer, size: usize) -> EvalResult<()> {
 399         let alloc = try!(self.get(ptr.alloc_id));
 400         if !alloc.undef_mask.is_range_defined(ptr.offset, ptr.offset + size) {
 401             return Err(EvalError::ReadUndefBytes);
 402         }
 403         Ok(())
 404     }
 405
 406     pub fn mark_definedness(&mut self, ptr: Pointer, size: usize, new_state: bool)
 407         -> EvalResult<()>
 408     {
 409         let mut alloc = try!(self.get_mut(ptr.alloc_id));
 410         alloc.undef_mask.set_range(ptr.offset, ptr.offset + size, new_state);
 411         Ok(())
 412     }
 413 }
 414
 415 ////////////////////////////////////////////////////////////////////////////////
 416 // Undefined byte tracking
 417 ////////////////////////////////////////////////////////////////////////////////
 418
 419 type Block = u64;
 420 const BLOCK_SIZE: usize = 64;
 421
 422 #[derive(Clone, Debug)]
 423 pub struct UndefMask {
 424     blocks: Vec<Block>,
 425     len: usize,
 426 }
 427
 428 impl UndefMask {
 429     fn new(size: usize) -> Self {
 430         let mut m = UndefMask {
 431             blocks: vec![],
 432             len: 0,
 433         };
 434         m.grow(size, false);
 435         m
 436     }
 437
 438     /// Check whether the range `start..end` (end-exclusive) is entirely defined.
 439     fn is_range_defined(&self, start: usize, end: usize) -> bool {
 440         if end > self.len { return false; }
 441         for i in start..end {
 442             if !self.get(i) { return false; }
 443         }
 444         true
 445     }
 446
 447     fn set_range(&mut self, start: usize, end: usize, new_state: bool) {
 448         let len = self.len;
 449         if end > len { self.grow(end - len, new_state); }
 450         self.set_range_inbounds(start, end, new_state);
 451     }
 452
 453     fn set_range_inbounds(&mut self, start: usize, end: usize, new_state: bool) {
 454         for i in start..end { self.set(i, new_state); }
 455     }
 456
 457     fn get(&self, i: usize) -> bool {
 458         let (block, bit) = bit_index(i);
 459         (self.blocks[block] & 1 << bit) != 0
 460     }
 461
 462     fn set(&mut self, i: usize, new_state: bool) {
 463         let (block, bit) = bit_index(i);
 464         if new_state {
 465             self.blocks[block] |= 1 << bit;
 466         } else {
 467             self.blocks[block] &= !(1 << bit);
 468         }
 469     }
 470
 471     fn grow(&mut self, amount: usize, new_state: bool) {
 472         let unused_trailing_bits = self.blocks.len() * BLOCK_SIZE - self.len;
 473         if amount > unused_trailing_bits {
 474             let additional_blocks = amount / BLOCK_SIZE + 1;
 475             self.blocks.extend(iter::repeat(0).take(additional_blocks));
 476         }
 477         let start = self.len;
 478         self.len += amount;
 479         self.set_range_inbounds(start, start + amount, new_state);
 480     }
 481 }
 482
 483 // fn uniform_block(state: bool) -> Block {
 484 //     if state { !0 } else { 0 }
 485 // }
 486
 487 fn bit_index(bits: usize) -> (usize, usize) {
 488     (bits / BLOCK_SIZE, bits % BLOCK_SIZE)
 489 }