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: Vec<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],
 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     // TODO(tsion): Track which allocations were returned from __rust_allocate and report an error
 120     // when reallocating/deallocating any others.
 121     pub fn reallocate(&mut self, ptr: Pointer, new_size: usize) -> EvalResult<()> {
 122         if ptr.offset != 0 {
 123             // TODO(tsion): Report error about non-__rust_allocate'd pointer.
 124             panic!()
 125         }
 126
 127         let alloc = try!(self.get_mut(ptr.alloc_id));
 128         let size = alloc.bytes.len();
 129         if new_size > size {
 130             let amount = new_size - size;
 131             alloc.bytes.extend(iter::repeat(0).take(amount));
 132             alloc.undef_mask.grow(amount, false);
 133         } else if size > new_size {
 134             unimplemented!()
 135             // alloc.bytes.truncate(new_size);
 136             // alloc.undef_mask.len = new_size;
 137             // TODO: potentially remove relocations
 138         }
 139
 140         Ok(())
 141     }
 142
 143     // TODO(tsion): See comment on `reallocate`.
 144     pub fn deallocate(&mut self, ptr: Pointer) -> EvalResult<()> {
 145         if ptr.offset != 0 {
 146             // TODO(tsion): Report error about non-__rust_allocate'd pointer.
 147             panic!()
 148         }
 149
 150         if self.alloc_map.remove(&ptr.alloc_id.0).is_none() {
 151             // TODO(tsion): Report error about erroneous free. This is blocked on properly tracking
 152             // already-dropped state since this if-statement is entered even in safe code without
 153             // it.
 154         }
 155
 156         Ok(())
 157     }
 158
 159     ////////////////////////////////////////////////////////////////////////////////
 160     // Allocation accessors
 161     ////////////////////////////////////////////////////////////////////////////////
 162
 163     pub fn get(&self, id: AllocId) -> EvalResult<&Allocation> {
 164         self.alloc_map.get(&id.0).ok_or(EvalError::DanglingPointerDeref)
 165     }
 166
 167     pub fn get_mut(&mut self, id: AllocId) -> EvalResult<&mut Allocation> {
 168         self.alloc_map.get_mut(&id.0).ok_or(EvalError::DanglingPointerDeref)
 169     }
 170
 171     /// Print an allocation and all allocations it points to, recursively.
 172     pub fn dump(&self, id: AllocId) {
 173         let mut allocs_seen = HashSet::new();
 174         let mut allocs_to_print = VecDeque::new();
 175         allocs_to_print.push_back(id);
 176
 177         while let Some(id) = allocs_to_print.pop_front() {
 178             allocs_seen.insert(id.0);
 179             let prefix = format!("Alloc {:<5} ", format!("{}:", id.0));
 180             print!("{}", prefix);
 181             let mut relocations = vec![];
 182
 183             let alloc = match self.alloc_map.get(&id.0) {
 184                 Some(a) => a,
 185                 None => {
 186                     println!("(deallocated)");
 187                     continue;
 188                 }
 189             };
 190
 191             for i in 0..alloc.bytes.len() {
 192                 if let Some(&target_id) = alloc.relocations.get(&i) {
 193                     if !allocs_seen.contains(&target_id.0) {
 194                         allocs_to_print.push_back(target_id);
 195                     }
 196                     relocations.push((i, target_id.0));
 197                 }
 198                 if alloc.undef_mask.is_range_defined(i, i+1) {
 199                     print!("{:02x} ", alloc.bytes[i]);
 200                 } else {
 201                     print!("__ ");
 202                 }
 203             }
 204             println!("({} bytes)", alloc.bytes.len());
 205
 206             if !relocations.is_empty() {
 207                 print!("{:1$}", "", prefix.len()); // Print spaces.
 208                 let mut pos = 0;
 209                 let relocation_width = (self.pointer_size - 1) * 3;
 210                 for (i, target_id) in relocations {
 211                     print!("{:1$}", "", (i - pos) * 3);
 212                     print!("└{0:─^1$}┘ ", format!("({})", target_id), relocation_width);
 213                     pos = i + self.pointer_size;
 214                 }
 215                 println!("");
 216             }
 217         }
 218     }
 219
 220     ////////////////////////////////////////////////////////////////////////////////
 221     // Byte accessors
 222     ////////////////////////////////////////////////////////////////////////////////
 223
 224     fn get_bytes_unchecked(&self, ptr: Pointer, size: usize) -> EvalResult<&[u8]> {
 225         let alloc = try!(self.get(ptr.alloc_id));
 226         if ptr.offset + size > alloc.bytes.len() {
 227             return Err(EvalError::PointerOutOfBounds);
 228         }
 229         Ok(&alloc.bytes[ptr.offset..ptr.offset + size])
 230     }
 231
 232     fn get_bytes_unchecked_mut(&mut self, ptr: Pointer, size: usize) -> EvalResult<&mut [u8]> {
 233         let alloc = try!(self.get_mut(ptr.alloc_id));
 234         if ptr.offset + size > alloc.bytes.len() {
 235             return Err(EvalError::PointerOutOfBounds);
 236         }
 237         Ok(&mut alloc.bytes[ptr.offset..ptr.offset + size])
 238     }
 239
 240     fn get_bytes(&self, ptr: Pointer, size: usize) -> EvalResult<&[u8]> {
 241         if try!(self.relocations(ptr, size)).count() != 0 {
 242             return Err(EvalError::ReadPointerAsBytes);
 243         }
 244         try!(self.check_defined(ptr, size));
 245         self.get_bytes_unchecked(ptr, size)
 246     }
 247
 248     fn get_bytes_mut(&mut self, ptr: Pointer, size: usize) -> EvalResult<&mut [u8]> {
 249         try!(self.clear_relocations(ptr, size));
 250         try!(self.mark_definedness(ptr, size, true));
 251         self.get_bytes_unchecked_mut(ptr, size)
 252     }
 253
 254     ////////////////////////////////////////////////////////////////////////////////
 255     // Reading and writing
 256     ////////////////////////////////////////////////////////////////////////////////
 257
 258     pub fn copy(&mut self, src: Pointer, dest: Pointer, size: usize) -> EvalResult<()> {
 259         try!(self.check_relocation_edges(src, size));
 260
 261         let src_bytes = try!(self.get_bytes_unchecked_mut(src, size)).as_mut_ptr();
 262         let dest_bytes = try!(self.get_bytes_mut(dest, size)).as_mut_ptr();
 263
 264         // SAFE: The above indexing would have panicked if there weren't at least `size` bytes
 265         // behind `src` and `dest`. Also, we use the overlapping-safe `ptr::copy` if `src` and
 266         // `dest` could possibly overlap.
 267         unsafe {
 268             if src.alloc_id == dest.alloc_id {
 269                 ptr::copy(src_bytes, dest_bytes, size);
 270             } else {
 271                 ptr::copy_nonoverlapping(src_bytes, dest_bytes, size);
 272             }
 273         }
 274
 275         try!(self.copy_undef_mask(src, dest, size));
 276         try!(self.copy_relocations(src, dest, size));
 277
 278         Ok(())
 279     }
 280
 281     pub fn write_bytes(&mut self, ptr: Pointer, src: &[u8]) -> EvalResult<()> {
 282         self.get_bytes_mut(ptr, src.len()).map(|dest| dest.clone_from_slice(src))
 283     }
 284
 285     pub fn read_ptr(&self, ptr: Pointer) -> EvalResult<Pointer> {
 286         let size = self.pointer_size;
 287         try!(self.check_defined(ptr, size));
 288         let offset = try!(self.get_bytes_unchecked(ptr, size))
 289             .read_uint::<NativeEndian>(size).unwrap() as usize;
 290         let alloc = try!(self.get(ptr.alloc_id));
 291         match alloc.relocations.get(&ptr.offset) {
 292             Some(&alloc_id) => Ok(Pointer { alloc_id: alloc_id, offset: offset }),
 293             None => Err(EvalError::ReadBytesAsPointer),
 294         }
 295     }
 296
 297     pub fn write_ptr(&mut self, dest: Pointer, ptr: Pointer) -> EvalResult<()> {
 298         {
 299             let size = self.pointer_size;
 300             let mut bytes = try!(self.get_bytes_mut(dest, size));
 301             bytes.write_uint::<NativeEndian>(ptr.offset as u64, size).unwrap();
 302         }
 303         try!(self.get_mut(dest.alloc_id)).relocations.insert(dest.offset, ptr.alloc_id);
 304         Ok(())
 305     }
 306
 307     pub fn write_primval(&mut self, ptr: Pointer, val: PrimVal) -> EvalResult<()> {
 308         let pointer_size = self.pointer_size;
 309         match val {
 310             PrimVal::Bool(b) => self.write_bool(ptr, b),
 311             PrimVal::I8(n)   => self.write_int(ptr, n as i64, 1),
 312             PrimVal::I16(n)  => self.write_int(ptr, n as i64, 2),
 313             PrimVal::I32(n)  => self.write_int(ptr, n as i64, 4),
 314             PrimVal::I64(n)  => self.write_int(ptr, n as i64, 8),
 315             PrimVal::U8(n)   => self.write_uint(ptr, n as u64, 1),
 316             PrimVal::U16(n)  => self.write_uint(ptr, n as u64, 2),
 317             PrimVal::U32(n)  => self.write_uint(ptr, n as u64, 4),
 318             PrimVal::U64(n)  => self.write_uint(ptr, n as u64, 8),
 319             PrimVal::IntegerPtr(n) => self.write_uint(ptr, n as u64, pointer_size),
 320             PrimVal::AbstractPtr(_p) => unimplemented!(),
 321         }
 322     }
 323
 324     pub fn read_bool(&self, ptr: Pointer) -> EvalResult<bool> {
 325         let bytes = try!(self.get_bytes(ptr, 1));
 326         match bytes[0] {
 327             0 => Ok(false),
 328             1 => Ok(true),
 329             _ => Err(EvalError::InvalidBool),
 330         }
 331     }
 332
 333     pub fn write_bool(&mut self, ptr: Pointer, b: bool) -> EvalResult<()> {
 334         self.get_bytes_mut(ptr, 1).map(|bytes| bytes[0] = b as u8)
 335     }
 336
 337     pub fn read_int(&self, ptr: Pointer, size: usize) -> EvalResult<i64> {
 338         self.get_bytes(ptr, size).map(|mut b| b.read_int::<NativeEndian>(size).unwrap())
 339     }
 340
 341     pub fn write_int(&mut self, ptr: Pointer, n: i64, size: usize) -> EvalResult<()> {
 342         self.get_bytes_mut(ptr, size).map(|mut b| b.write_int::<NativeEndian>(n, size).unwrap())
 343     }
 344
 345     pub fn read_uint(&self, ptr: Pointer, size: usize) -> EvalResult<u64> {
 346         self.get_bytes(ptr, size).map(|mut b| b.read_uint::<NativeEndian>(size).unwrap())
 347     }
 348
 349     pub fn write_uint(&mut self, ptr: Pointer, n: u64, size: usize) -> EvalResult<()> {
 350         self.get_bytes_mut(ptr, size).map(|mut b| b.write_uint::<NativeEndian>(n, size).unwrap())
 351     }
 352
 353     pub fn read_isize(&self, ptr: Pointer) -> EvalResult<i64> {
 354         self.read_int(ptr, self.pointer_size)
 355     }
 356
 357     pub fn write_isize(&mut self, ptr: Pointer, n: i64) -> EvalResult<()> {
 358         let size = self.pointer_size;
 359         self.write_int(ptr, n, size)
 360     }
 361
 362     pub fn read_usize(&self, ptr: Pointer) -> EvalResult<u64> {
 363         self.read_uint(ptr, self.pointer_size)
 364     }
 365
 366     pub fn write_usize(&mut self, ptr: Pointer, n: u64) -> EvalResult<()> {
 367         let size = self.pointer_size;
 368         self.write_uint(ptr, n, size)
 369     }
 370
 371     ////////////////////////////////////////////////////////////////////////////////
 372     // Relocations
 373     ////////////////////////////////////////////////////////////////////////////////
 374
 375     fn relocations(&self, ptr: Pointer, size: usize)
 376         -> EvalResult<btree_map::Range<usize, AllocId>>
 377     {
 378         let start = ptr.offset.saturating_sub(self.pointer_size - 1);
 379         let end = start + size;
 380         Ok(try!(self.get(ptr.alloc_id)).relocations.range(Included(&start), Excluded(&end)))
 381     }
 382
 383     fn clear_relocations(&mut self, ptr: Pointer, size: usize) -> EvalResult<()> {
 384         // Find all relocations overlapping the given range.
 385         let keys: Vec<_> = try!(self.relocations(ptr, size)).map(|(&k, _)| k).collect();
 386         if keys.len() == 0 { return Ok(()); }
 387
 388         // Find the start and end of the given range and its outermost relocations.
 389         let start = ptr.offset;
 390         let end = start + size;
 391         let first = *keys.first().unwrap();
 392         let last = *keys.last().unwrap() + self.pointer_size;
 393
 394         let alloc = try!(self.get_mut(ptr.alloc_id));
 395
 396         // Mark parts of the outermost relocations as undefined if they partially fall outside the
 397         // given range.
 398         if first < start { alloc.undef_mask.set_range(first, start, false); }
 399         if last > end { alloc.undef_mask.set_range(end, last, false); }
 400
 401         // Forget all the relocations.
 402         for k in keys { alloc.relocations.remove(&k); }
 403
 404         Ok(())
 405     }
 406
 407     fn check_relocation_edges(&self, ptr: Pointer, size: usize) -> EvalResult<()> {
 408         let overlapping_start = try!(self.relocations(ptr, 0)).count();
 409         let overlapping_end = try!(self.relocations(ptr.offset(size as isize), 0)).count();
 410         if overlapping_start + overlapping_end != 0 {
 411             return Err(EvalError::ReadPointerAsBytes);
 412         }
 413         Ok(())
 414     }
 415
 416     fn copy_relocations(&mut self, src: Pointer, dest: Pointer, size: usize) -> EvalResult<()> {
 417         let relocations: Vec<_> = try!(self.relocations(src, size))
 418             .map(|(&offset, &alloc_id)| {
 419                 // Update relocation offsets for the new positions in the destination allocation.
 420                 (offset + dest.offset - src.offset, alloc_id)
 421             })
 422             .collect();
 423         try!(self.get_mut(dest.alloc_id)).relocations.extend(relocations);
 424         Ok(())
 425     }
 426
 427     ////////////////////////////////////////////////////////////////////////////////
 428     // Undefined bytes
 429     ////////////////////////////////////////////////////////////////////////////////
 430
 431     // FIXME(tsino): This is a very naive, slow version.
 432     fn copy_undef_mask(&mut self, src: Pointer, dest: Pointer, size: usize) -> EvalResult<()> {
 433         // The bits have to be saved locally before writing to dest in case src and dest overlap.
 434         let mut v = Vec::with_capacity(size);
 435         for i in 0..size {
 436             let defined = try!(self.get(src.alloc_id)).undef_mask.get(src.offset + i);
 437             v.push(defined);
 438         }
 439         for (i, defined) in v.into_iter().enumerate() {
 440             try!(self.get_mut(dest.alloc_id)).undef_mask.set(dest.offset + i, defined);
 441         }
 442         Ok(())
 443     }
 444
 445     fn check_defined(&self, ptr: Pointer, size: usize) -> EvalResult<()> {
 446         let alloc = try!(self.get(ptr.alloc_id));
 447         if !alloc.undef_mask.is_range_defined(ptr.offset, ptr.offset + size) {
 448             return Err(EvalError::ReadUndefBytes);
 449         }
 450         Ok(())
 451     }
 452
 453     pub fn mark_definedness(&mut self, ptr: Pointer, size: usize, new_state: bool)
 454         -> EvalResult<()>
 455     {
 456         let mut alloc = try!(self.get_mut(ptr.alloc_id));
 457         alloc.undef_mask.set_range(ptr.offset, ptr.offset + size, new_state);
 458         Ok(())
 459     }
 460 }
 461
 462 ////////////////////////////////////////////////////////////////////////////////
 463 // Undefined byte tracking
 464 ////////////////////////////////////////////////////////////////////////////////
 465
 466 type Block = u64;
 467 const BLOCK_SIZE: usize = 64;
 468
 469 #[derive(Clone, Debug)]
 470 pub struct UndefMask {
 471     blocks: Vec<Block>,
 472     len: usize,
 473 }
 474
 475 impl UndefMask {
 476     fn new(size: usize) -> Self {
 477         let mut m = UndefMask {
 478             blocks: vec![],
 479             len: 0,
 480         };
 481         m.grow(size, false);
 482         m
 483     }
 484
 485     /// Check whether the range `start..end` (end-exclusive) is entirely defined.
 486     fn is_range_defined(&self, start: usize, end: usize) -> bool {
 487         if end > self.len { return false; }
 488         for i in start..end {
 489             if !self.get(i) { return false; }
 490         }
 491         true
 492     }
 493
 494     fn set_range(&mut self, start: usize, end: usize, new_state: bool) {
 495         let len = self.len;
 496         if end > len { self.grow(end - len, new_state); }
 497         self.set_range_inbounds(start, end, new_state);
 498     }
 499
 500     fn set_range_inbounds(&mut self, start: usize, end: usize, new_state: bool) {
 501         for i in start..end { self.set(i, new_state); }
 502     }
 503
 504     fn get(&self, i: usize) -> bool {
 505         let (block, bit) = bit_index(i);
 506         (self.blocks[block] & 1 << bit) != 0
 507     }
 508
 509     fn set(&mut self, i: usize, new_state: bool) {
 510         let (block, bit) = bit_index(i);
 511         if new_state {
 512             self.blocks[block] |= 1 << bit;
 513         } else {
 514             self.blocks[block] &= !(1 << bit);
 515         }
 516     }
 517
 518     fn grow(&mut self, amount: usize, new_state: bool) {
 519         let unused_trailing_bits = self.blocks.len() * BLOCK_SIZE - self.len;
 520         if amount > unused_trailing_bits {
 521             let additional_blocks = amount / BLOCK_SIZE + 1;
 522             self.blocks.extend(iter::repeat(0).take(additional_blocks));
 523         }
 524         let start = self.len;
 525         self.len += amount;
 526         self.set_range_inbounds(start, start + amount, new_state);
 527     }
 528 }
 529
 530 // fn uniform_block(state: bool) -> Block {
 531 //     if state { !0 } else { 0 }
 532 // }
 533
 534 fn bit_index(bits: usize) -> (usize, usize) {
 535     (bits / BLOCK_SIZE, bits % BLOCK_SIZE)
 536 }