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