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