compiler/rustc_middle/src/mir/interpret/allocation.rs

   1 //! The virtual memory representation of the MIR interpreter.
   2
   3 use std::borrow::Cow;
   4 use std::convert::TryFrom;
   5 use std::iter;
   6 use std::ops::{Deref, DerefMut, Range};
   7 use std::ptr;
   8
   9 use rustc_ast::Mutability;
  10 use rustc_data_structures::sorted_map::SortedMap;
  11 use rustc_target::abi::{Align, HasDataLayout, Size};
  12
  13 use super::{
  14     read_target_uint, write_target_uint, AllocId, InterpError, InterpResult, Pointer,
  15     ResourceExhaustionInfo, Scalar, ScalarMaybeUninit, UndefinedBehaviorInfo, UninitBytesAccess,
  16     UnsupportedOpInfo,
  17 };
  18
  19 /// This type represents an Allocation in the Miri/CTFE core engine.
  20 ///
  21 /// Its public API is rather low-level, working directly with allocation offsets and a custom error
  22 /// type to account for the lack of an AllocId on this level. The Miri/CTFE core engine `memory`
  23 /// module provides higher-level access.
  24 #[derive(Clone, Debug, Eq, PartialEq, PartialOrd, Ord, Hash, TyEncodable, TyDecodable)]
  25 #[derive(HashStable)]
  26 pub struct Allocation<Tag = (), Extra = ()> {
  27     /// The actual bytes of the allocation.
  28     /// Note that the bytes of a pointer represent the offset of the pointer.
  29     bytes: Vec<u8>,
  30     /// Maps from byte addresses to extra data for each pointer.
  31     /// Only the first byte of a pointer is inserted into the map; i.e.,
  32     /// every entry in this map applies to `pointer_size` consecutive bytes starting
  33     /// at the given offset.
  34     relocations: Relocations<Tag>,
  35     /// Denotes which part of this allocation is initialized.
  36     init_mask: InitMask,
  37     /// The alignment of the allocation to detect unaligned reads.
  38     /// (`Align` guarantees that this is a power of two.)
  39     pub align: Align,
  40     /// `true` if the allocation is mutable.
  41     /// Also used by codegen to determine if a static should be put into mutable memory,
  42     /// which happens for `static mut` and `static` with interior mutability.
  43     pub mutability: Mutability,
  44     /// Extra state for the machine.
  45     pub extra: Extra,
  46 }
  47
  48 /// We have our own error type that does not know about the `AllocId`; that information
  49 /// is added when converting to `InterpError`.
  50 #[derive(Debug)]
  51 pub enum AllocError {
  52     /// Encountered a pointer where we needed raw bytes.
  53     ReadPointerAsBytes,
  54     /// Using uninitialized data where it is not allowed.
  55     InvalidUninitBytes(Option<UninitBytesAccess>),
  56 }
  57 pub type AllocResult<T = ()> = Result<T, AllocError>;
  58
  59 impl AllocError {
  60     pub fn to_interp_error<'tcx>(self, alloc_id: AllocId) -> InterpError<'tcx> {
  61         match self {
  62             AllocError::ReadPointerAsBytes => {
  63                 InterpError::Unsupported(UnsupportedOpInfo::ReadPointerAsBytes)
  64             }
  65             AllocError::InvalidUninitBytes(info) => InterpError::UndefinedBehavior(
  66                 UndefinedBehaviorInfo::InvalidUninitBytes(info.map(|b| (alloc_id, b))),
  67             ),
  68         }
  69     }
  70 }
  71
  72 /// The information that makes up a memory access: offset and size.
  73 #[derive(Copy, Clone, Debug)]
  74 pub struct AllocRange {
  75     pub start: Size,
  76     pub size: Size,
  77 }
  78
  79 /// Free-starting constructor for less syntactic overhead.
  80 #[inline(always)]
  81 pub fn alloc_range(start: Size, size: Size) -> AllocRange {
  82     AllocRange { start, size }
  83 }
  84
  85 impl AllocRange {
  86     #[inline(always)]
  87     pub fn end(self) -> Size {
  88         self.start + self.size // This does overflow checking.
  89     }
  90
  91     /// Returns the `subrange` within this range; panics if it is not a subrange.
  92     #[inline]
  93     pub fn subrange(self, subrange: AllocRange) -> AllocRange {
  94         let sub_start = self.start + subrange.start;
  95         let range = alloc_range(sub_start, subrange.size);
  96         assert!(range.end() <= self.end(), "access outside the bounds for given AllocRange");
  97         range
  98     }
  99 }
 100
 101 // The constructors are all without extra; the extra gets added by a machine hook later.
 102 impl<Tag> Allocation<Tag> {
 103     /// Creates an allocation initialized by the given bytes
 104     pub fn from_bytes<'a>(
 105         slice: impl Into<Cow<'a, [u8]>>,
 106         align: Align,
 107         mutability: Mutability,
 108     ) -> Self {
 109         let bytes = slice.into().into_owned();
 110         let size = Size::from_bytes(bytes.len());
 111         Self {
 112             bytes,
 113             relocations: Relocations::new(),
 114             init_mask: InitMask::new(size, true),
 115             align,
 116             mutability,
 117             extra: (),
 118         }
 119     }
 120
 121     pub fn from_bytes_byte_aligned_immutable<'a>(slice: impl Into<Cow<'a, [u8]>>) -> Self {
 122         Allocation::from_bytes(slice, Align::ONE, Mutability::Not)
 123     }
 124
 125     /// Try to create an Allocation of `size` bytes, failing if there is not enough memory
 126     /// available to the compiler to do so.
 127     pub fn uninit(size: Size, align: Align) -> InterpResult<'static, Self> {
 128         let mut bytes = Vec::new();
 129         bytes.try_reserve(size.bytes_usize()).map_err(|_| {
 130             InterpError::ResourceExhaustion(ResourceExhaustionInfo::MemoryExhausted)
 131         })?;
 132         bytes.resize(size.bytes_usize(), 0);
 133         bytes.fill(0);
 134         Ok(Allocation {
 135             bytes: bytes,
 136             relocations: Relocations::new(),
 137             init_mask: InitMask::new(size, false),
 138             align,
 139             mutability: Mutability::Mut,
 140             extra: (),
 141         })
 142     }
 143 }
 144
 145 impl Allocation<()> {
 146     /// Add Tag and Extra fields
 147     pub fn with_tags_and_extra<T, E>(
 148         self,
 149         mut tagger: impl FnMut(AllocId) -> T,
 150         extra: E,
 151     ) -> Allocation<T, E> {
 152         Allocation {
 153             bytes: self.bytes,
 154             relocations: Relocations::from_presorted(
 155                 self.relocations
 156                     .iter()
 157                     // The allocations in the relocations (pointers stored *inside* this allocation)
 158                     // all get the base pointer tag.
 159                     .map(|&(offset, ((), alloc))| {
 160                         let tag = tagger(alloc);
 161                         (offset, (tag, alloc))
 162                     })
 163                     .collect(),
 164             ),
 165             init_mask: self.init_mask,
 166             align: self.align,
 167             mutability: self.mutability,
 168             extra,
 169         }
 170     }
 171 }
 172
 173 /// Raw accessors. Provide access to otherwise private bytes.
 174 impl<Tag, Extra> Allocation<Tag, Extra> {
 175     pub fn len(&self) -> usize {
 176         self.bytes.len()
 177     }
 178
 179     pub fn size(&self) -> Size {
 180         Size::from_bytes(self.len())
 181     }
 182
 183     /// Looks at a slice which may describe uninitialized bytes or describe a relocation. This differs
 184     /// from `get_bytes_with_uninit_and_ptr` in that it does no relocation checks (even on the
 185     /// edges) at all.
 186     /// This must not be used for reads affecting the interpreter execution.
 187     pub fn inspect_with_uninit_and_ptr_outside_interpreter(&self, range: Range<usize>) -> &[u8] {
 188         &self.bytes[range]
 189     }
 190
 191     /// Returns the mask indicating which bytes are initialized.
 192     pub fn init_mask(&self) -> &InitMask {
 193         &self.init_mask
 194     }
 195
 196     /// Returns the relocation list.
 197     pub fn relocations(&self) -> &Relocations<Tag> {
 198         &self.relocations
 199     }
 200 }
 201
 202 /// Byte accessors.
 203 impl<Tag: Copy, Extra> Allocation<Tag, Extra> {
 204     /// The last argument controls whether we error out when there are uninitialized
 205     /// or pointer bytes. You should never call this, call `get_bytes` or
 206     /// `get_bytes_with_uninit_and_ptr` instead,
 207     ///
 208     /// This function also guarantees that the resulting pointer will remain stable
 209     /// even when new allocations are pushed to the `HashMap`. `copy_repeatedly` relies
 210     /// on that.
 211     ///
 212     /// It is the caller's responsibility to check bounds and alignment beforehand.
 213     fn get_bytes_internal(
 214         &self,
 215         cx: &impl HasDataLayout,
 216         range: AllocRange,
 217         check_init_and_ptr: bool,
 218     ) -> AllocResult<&[u8]> {
 219         if check_init_and_ptr {
 220             self.check_init(range)?;
 221             self.check_relocations(cx, range)?;
 222         } else {
 223             // We still don't want relocations on the *edges*.
 224             self.check_relocation_edges(cx, range)?;
 225         }
 226
 227         Ok(&self.bytes[range.start.bytes_usize()..range.end().bytes_usize()])
 228     }
 229
 230     /// Checks that these bytes are initialized and not pointer bytes, and then return them
 231     /// as a slice.
 232     ///
 233     /// It is the caller's responsibility to check bounds and alignment beforehand.
 234     /// Most likely, you want to use the `PlaceTy` and `OperandTy`-based methods
 235     /// on `InterpCx` instead.
 236     #[inline]
 237     pub fn get_bytes(&self, cx: &impl HasDataLayout, range: AllocRange) -> AllocResult<&[u8]> {
 238         self.get_bytes_internal(cx, range, true)
 239     }
 240
 241     /// It is the caller's responsibility to handle uninitialized and pointer bytes.
 242     /// However, this still checks that there are no relocations on the *edges*.
 243     ///
 244     /// It is the caller's responsibility to check bounds and alignment beforehand.
 245     #[inline]
 246     pub fn get_bytes_with_uninit_and_ptr(
 247         &self,
 248         cx: &impl HasDataLayout,
 249         range: AllocRange,
 250     ) -> AllocResult<&[u8]> {
 251         self.get_bytes_internal(cx, range, false)
 252     }
 253
 254     /// Just calling this already marks everything as defined and removes relocations,
 255     /// so be sure to actually put data there!
 256     ///
 257     /// It is the caller's responsibility to check bounds and alignment beforehand.
 258     /// Most likely, you want to use the `PlaceTy` and `OperandTy`-based methods
 259     /// on `InterpCx` instead.
 260     pub fn get_bytes_mut(&mut self, cx: &impl HasDataLayout, range: AllocRange) -> &mut [u8] {
 261         self.mark_init(range, true);
 262         self.clear_relocations(cx, range);
 263
 264         &mut self.bytes[range.start.bytes_usize()..range.end().bytes_usize()]
 265     }
 266
 267     /// A raw pointer variant of `get_bytes_mut` that avoids invalidating existing aliases into this memory.
 268     pub fn get_bytes_mut_ptr(&mut self, cx: &impl HasDataLayout, range: AllocRange) -> *mut [u8] {
 269         self.mark_init(range, true);
 270         self.clear_relocations(cx, range);
 271
 272         assert!(range.end().bytes_usize() <= self.bytes.len()); // need to do our own bounds-check
 273         let begin_ptr = self.bytes.as_mut_ptr().wrapping_add(range.start.bytes_usize());
 274         let len = range.end().bytes_usize() - range.start.bytes_usize();
 275         ptr::slice_from_raw_parts_mut(begin_ptr, len)
 276     }
 277 }
 278
 279 /// Reading and writing.
 280 impl<Tag: Copy, Extra> Allocation<Tag, Extra> {
 281     /// Validates that `ptr.offset` and `ptr.offset + size` do not point to the middle of a
 282     /// relocation. If `allow_uninit_and_ptr` is `false`, also enforces that the memory in the
 283     /// given range contains neither relocations nor uninitialized bytes.
 284     pub fn check_bytes(
 285         &self,
 286         cx: &impl HasDataLayout,
 287         range: AllocRange,
 288         allow_uninit_and_ptr: bool,
 289     ) -> AllocResult {
 290         // Check bounds and relocations on the edges.
 291         self.get_bytes_with_uninit_and_ptr(cx, range)?;
 292         // Check uninit and ptr.
 293         if !allow_uninit_and_ptr {
 294             self.check_init(range)?;
 295             self.check_relocations(cx, range)?;
 296         }
 297         Ok(())
 298     }
 299
 300     /// Reads a *non-ZST* scalar.
 301     ///
 302     /// ZSTs can't be read because in order to obtain a `Pointer`, we need to check
 303     /// for ZSTness anyway due to integer pointers being valid for ZSTs.
 304     ///
 305     /// It is the caller's responsibility to check bounds and alignment beforehand.
 306     /// Most likely, you want to call `InterpCx::read_scalar` instead of this method.
 307     pub fn read_scalar(
 308         &self,
 309         cx: &impl HasDataLayout,
 310         range: AllocRange,
 311     ) -> AllocResult<ScalarMaybeUninit<Tag>> {
 312         // `get_bytes_unchecked` tests relocation edges.
 313         let bytes = self.get_bytes_with_uninit_and_ptr(cx, range)?;
 314         // Uninit check happens *after* we established that the alignment is correct.
 315         // We must not return `Ok()` for unaligned pointers!
 316         if self.is_init(range).is_err() {
 317             // This inflates uninitialized bytes to the entire scalar, even if only a few
 318             // bytes are uninitialized.
 319             return Ok(ScalarMaybeUninit::Uninit);
 320         }
 321         // Now we do the actual reading.
 322         let bits = read_target_uint(cx.data_layout().endian, bytes).unwrap();
 323         // See if we got a pointer.
 324         if range.size != cx.data_layout().pointer_size {
 325             // Not a pointer.
 326             // *Now*, we better make sure that the inside is free of relocations too.
 327             self.check_relocations(cx, range)?;
 328         } else {
 329             // Maybe a pointer.
 330             if let Some(&(tag, alloc_id)) = self.relocations.get(&range.start) {
 331                 let ptr = Pointer::new_with_tag(alloc_id, Size::from_bytes(bits), tag);
 332                 return Ok(ScalarMaybeUninit::Scalar(ptr.into()));
 333             }
 334         }
 335         // We don't. Just return the bits.
 336         Ok(ScalarMaybeUninit::Scalar(Scalar::from_uint(bits, range.size)))
 337     }
 338
 339     /// Writes a *non-ZST* scalar.
 340     ///
 341     /// ZSTs can't be read because in order to obtain a `Pointer`, we need to check
 342     /// for ZSTness anyway due to integer pointers being valid for ZSTs.
 343     ///
 344     /// It is the caller's responsibility to check bounds and alignment beforehand.
 345     /// Most likely, you want to call `InterpCx::write_scalar` instead of this method.
 346     pub fn write_scalar(
 347         &mut self,
 348         cx: &impl HasDataLayout,
 349         range: AllocRange,
 350         val: ScalarMaybeUninit<Tag>,
 351     ) -> AllocResult {
 352         let val = match val {
 353             ScalarMaybeUninit::Scalar(scalar) => scalar,
 354             ScalarMaybeUninit::Uninit => {
 355                 self.mark_init(range, false);
 356                 return Ok(());
 357             }
 358         };
 359
 360         let bytes = match val.to_bits_or_ptr(range.size, cx) {
 361             Err(val) => u128::from(val.offset.bytes()),
 362             Ok(data) => data,
 363         };
 364
 365         let endian = cx.data_layout().endian;
 366         let dst = self.get_bytes_mut(cx, range);
 367         write_target_uint(endian, dst, bytes).unwrap();
 368
 369         // See if we have to also write a relocation.
 370         if let Scalar::Ptr(val) = val {
 371             self.relocations.insert(range.start, (val.tag, val.alloc_id));
 372         }
 373
 374         Ok(())
 375     }
 376 }
 377
 378 /// Relocations.
 379 impl<Tag: Copy, Extra> Allocation<Tag, Extra> {
 380     /// Returns all relocations overlapping with the given pointer-offset pair.
 381     pub fn get_relocations(
 382         &self,
 383         cx: &impl HasDataLayout,
 384         range: AllocRange,
 385     ) -> &[(Size, (Tag, AllocId))] {
 386         // We have to go back `pointer_size - 1` bytes, as that one would still overlap with
 387         // the beginning of this range.
 388         let start = range.start.bytes().saturating_sub(cx.data_layout().pointer_size.bytes() - 1);
 389         self.relocations.range(Size::from_bytes(start)..range.end())
 390     }
 391
 392     /// Checks that there are no relocations overlapping with the given range.
 393     #[inline(always)]
 394     fn check_relocations(&self, cx: &impl HasDataLayout, range: AllocRange) -> AllocResult {
 395         if self.get_relocations(cx, range).is_empty() {
 396             Ok(())
 397         } else {
 398             Err(AllocError::ReadPointerAsBytes)
 399         }
 400     }
 401
 402     /// Removes all relocations inside the given range.
 403     /// If there are relocations overlapping with the edges, they
 404     /// are removed as well *and* the bytes they cover are marked as
 405     /// uninitialized. This is a somewhat odd "spooky action at a distance",
 406     /// but it allows strictly more code to run than if we would just error
 407     /// immediately in that case.
 408     fn clear_relocations(&mut self, cx: &impl HasDataLayout, range: AllocRange) {
 409         // Find the start and end of the given range and its outermost relocations.
 410         let (first, last) = {
 411             // Find all relocations overlapping the given range.
 412             let relocations = self.get_relocations(cx, range);
 413             if relocations.is_empty() {
 414                 return;
 415             }
 416
 417             (
 418                 relocations.first().unwrap().0,
 419                 relocations.last().unwrap().0 + cx.data_layout().pointer_size,
 420             )
 421         };
 422         let start = range.start;
 423         let end = range.end();
 424
 425         // Mark parts of the outermost relocations as uninitialized if they partially fall outside the
 426         // given range.
 427         if first < start {
 428             self.init_mask.set_range(first, start, false);
 429         }
 430         if last > end {
 431             self.init_mask.set_range(end, last, false);
 432         }
 433
 434         // Forget all the relocations.
 435         self.relocations.remove_range(first..last);
 436     }
 437
 438     /// Errors if there are relocations overlapping with the edges of the
 439     /// given memory range.
 440     #[inline]
 441     fn check_relocation_edges(&self, cx: &impl HasDataLayout, range: AllocRange) -> AllocResult {
 442         self.check_relocations(cx, alloc_range(range.start, Size::ZERO))?;
 443         self.check_relocations(cx, alloc_range(range.end(), Size::ZERO))?;
 444         Ok(())
 445     }
 446 }
 447
 448 /// Uninitialized bytes.
 449 impl<Tag: Copy, Extra> Allocation<Tag, Extra> {
 450     /// Checks whether the given range  is entirely initialized.
 451     ///
 452     /// Returns `Ok(())` if it's initialized. Otherwise returns the range of byte
 453     /// indexes of the first contiguous uninitialized access.
 454     fn is_init(&self, range: AllocRange) -> Result<(), Range<Size>> {
 455         self.init_mask.is_range_initialized(range.start, range.end()) // `Size` addition
 456     }
 457
 458     /// Checks that a range of bytes is initialized. If not, returns the `InvalidUninitBytes`
 459     /// error which will report the first range of bytes which is uninitialized.
 460     fn check_init(&self, range: AllocRange) -> AllocResult {
 461         self.is_init(range).or_else(|idx_range| {
 462             Err(AllocError::InvalidUninitBytes(Some(UninitBytesAccess {
 463                 access_offset: range.start,
 464                 access_size: range.size,
 465                 uninit_offset: idx_range.start,
 466                 uninit_size: idx_range.end - idx_range.start, // `Size` subtraction
 467             })))
 468         })
 469     }
 470
 471     pub fn mark_init(&mut self, range: AllocRange, is_init: bool) {
 472         if range.size.bytes() == 0 {
 473             return;
 474         }
 475         self.init_mask.set_range(range.start, range.end(), is_init);
 476     }
 477 }
 478
 479 /// Run-length encoding of the uninit mask.
 480 /// Used to copy parts of a mask multiple times to another allocation.
 481 pub struct InitMaskCompressed {
 482     /// Whether the first range is initialized.
 483     initial: bool,
 484     /// The lengths of ranges that are run-length encoded.
 485     /// The initialization state of the ranges alternate starting with `initial`.
 486     ranges: smallvec::SmallVec<[u64; 1]>,
 487 }
 488
 489 impl InitMaskCompressed {
 490     pub fn no_bytes_init(&self) -> bool {
 491         // The `ranges` are run-length encoded and of alternating initialization state.
 492         // So if `ranges.len() > 1` then the second block is an initialized range.
 493         !self.initial && self.ranges.len() == 1
 494     }
 495 }
 496
 497 /// Transferring the initialization mask to other allocations.
 498 impl<Tag, Extra> Allocation<Tag, Extra> {
 499     /// Creates a run-length encoding of the initialization mask.
 500     pub fn compress_uninit_range(&self, src: Pointer<Tag>, size: Size) -> InitMaskCompressed {
 501         // Since we are copying `size` bytes from `src` to `dest + i * size` (`for i in 0..repeat`),
 502         // a naive initialization mask copying algorithm would repeatedly have to read the initialization mask from
 503         // the source and write it to the destination. Even if we optimized the memory accesses,
 504         // we'd be doing all of this `repeat` times.
 505         // Therefore we precompute a compressed version of the initialization mask of the source value and
 506         // then write it back `repeat` times without computing any more information from the source.
 507
 508         // A precomputed cache for ranges of initialized / uninitialized bits
 509         // 0000010010001110 will become
 510         // `[5, 1, 2, 1, 3, 3, 1]`,
 511         // where each element toggles the state.
 512
 513         let mut ranges = smallvec::SmallVec::<[u64; 1]>::new();
 514         let initial = self.init_mask.get(src.offset);
 515         let mut cur_len = 1;
 516         let mut cur = initial;
 517
 518         for i in 1..size.bytes() {
 519             // FIXME: optimize to bitshift the current uninitialized block's bits and read the top bit.
 520             if self.init_mask.get(src.offset + Size::from_bytes(i)) == cur {
 521                 cur_len += 1;
 522             } else {
 523                 ranges.push(cur_len);
 524                 cur_len = 1;
 525                 cur = !cur;
 526             }
 527         }
 528
 529         ranges.push(cur_len);
 530
 531         InitMaskCompressed { ranges, initial }
 532     }
 533
 534     /// Applies multiple instances of the run-length encoding to the initialization mask.
 535     pub fn mark_compressed_init_range(
 536         &mut self,
 537         defined: &InitMaskCompressed,
 538         dest: Pointer<Tag>,
 539         size: Size,
 540         repeat: u64,
 541     ) {
 542         // An optimization where we can just overwrite an entire range of initialization
 543         // bits if they are going to be uniformly `1` or `0`.
 544         if defined.ranges.len() <= 1 {
 545             self.init_mask.set_range_inbounds(
 546                 dest.offset,
 547                 dest.offset + size * repeat, // `Size` operations
 548                 defined.initial,
 549             );
 550             return;
 551         }
 552
 553         for mut j in 0..repeat {
 554             j *= size.bytes();
 555             j += dest.offset.bytes();
 556             let mut cur = defined.initial;
 557             for range in &defined.ranges {
 558                 let old_j = j;
 559                 j += range;
 560                 self.init_mask.set_range_inbounds(
 561                     Size::from_bytes(old_j),
 562                     Size::from_bytes(j),
 563                     cur,
 564                 );
 565                 cur = !cur;
 566             }
 567         }
 568     }
 569 }
 570
 571 /// Relocations.
 572 #[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, TyEncodable, TyDecodable)]
 573 pub struct Relocations<Tag = (), Id = AllocId>(SortedMap<Size, (Tag, Id)>);
 574
 575 impl<Tag, Id> Relocations<Tag, Id> {
 576     pub fn new() -> Self {
 577         Relocations(SortedMap::new())
 578     }
 579
 580     // The caller must guarantee that the given relocations are already sorted
 581     // by address and contain no duplicates.
 582     pub fn from_presorted(r: Vec<(Size, (Tag, Id))>) -> Self {
 583         Relocations(SortedMap::from_presorted_elements(r))
 584     }
 585 }
 586
 587 impl<Tag> Deref for Relocations<Tag> {
 588     type Target = SortedMap<Size, (Tag, AllocId)>;
 589
 590     fn deref(&self) -> &Self::Target {
 591         &self.0
 592     }
 593 }
 594
 595 impl<Tag> DerefMut for Relocations<Tag> {
 596     fn deref_mut(&mut self) -> &mut Self::Target {
 597         &mut self.0
 598     }
 599 }
 600
 601 /// A partial, owned list of relocations to transfer into another allocation.
 602 pub struct AllocationRelocations<Tag> {
 603     relative_relocations: Vec<(Size, (Tag, AllocId))>,
 604 }
 605
 606 impl<Tag: Copy, Extra> Allocation<Tag, Extra> {
 607     pub fn prepare_relocation_copy(
 608         &self,
 609         cx: &impl HasDataLayout,
 610         src: AllocRange,
 611         dest: Size,
 612         count: u64,
 613     ) -> AllocationRelocations<Tag> {
 614         let relocations = self.get_relocations(cx, src);
 615         if relocations.is_empty() {
 616             return AllocationRelocations { relative_relocations: Vec::new() };
 617         }
 618
 619         let size = src.size;
 620         let mut new_relocations = Vec::with_capacity(relocations.len() * (count as usize));
 621
 622         for i in 0..count {
 623             new_relocations.extend(relocations.iter().map(|&(offset, reloc)| {
 624                 // compute offset for current repetition
 625                 let dest_offset = dest + size * i; // `Size` operations
 626                 (
 627                     // shift offsets from source allocation to destination allocation
 628                     (offset + dest_offset) - src.start, // `Size` operations
 629                     reloc,
 630                 )
 631             }));
 632         }
 633
 634         AllocationRelocations { relative_relocations: new_relocations }
 635     }
 636
 637     /// Applies a relocation copy.
 638     /// The affected range, as defined in the parameters to `prepare_relocation_copy` is expected
 639     /// to be clear of relocations.
 640     pub fn mark_relocation_range(&mut self, relocations: AllocationRelocations<Tag>) {
 641         self.relocations.insert_presorted(relocations.relative_relocations);
 642     }
 643 }
 644
 645 ////////////////////////////////////////////////////////////////////////////////
 646 // Uninitialized byte tracking
 647 ////////////////////////////////////////////////////////////////////////////////
 648
 649 type Block = u64;
 650
 651 /// A bitmask where each bit refers to the byte with the same index. If the bit is `true`, the byte
 652 /// is initialized. If it is `false` the byte is uninitialized.
 653 #[derive(Clone, Debug, Eq, PartialEq, PartialOrd, Ord, Hash, TyEncodable, TyDecodable)]
 654 #[derive(HashStable)]
 655 pub struct InitMask {
 656     blocks: Vec<Block>,
 657     len: Size,
 658 }
 659
 660 impl InitMask {
 661     pub const BLOCK_SIZE: u64 = 64;
 662
 663     pub fn new(size: Size, state: bool) -> Self {
 664         let mut m = InitMask { blocks: vec![], len: Size::ZERO };
 665         m.grow(size, state);
 666         m
 667     }
 668
 669     /// Checks whether the range `start..end` (end-exclusive) is entirely initialized.
 670     ///
 671     /// Returns `Ok(())` if it's initialized. Otherwise returns a range of byte
 672     /// indexes for the first contiguous span of the uninitialized access.
 673     #[inline]
 674     pub fn is_range_initialized(&self, start: Size, end: Size) -> Result<(), Range<Size>> {
 675         if end > self.len {
 676             return Err(self.len..end);
 677         }
 678
 679         // FIXME(oli-obk): optimize this for allocations larger than a block.
 680         let idx = (start.bytes()..end.bytes()).map(Size::from_bytes).find(|&i| !self.get(i));
 681
 682         match idx {
 683             Some(idx) => {
 684                 let uninit_end = (idx.bytes()..end.bytes())
 685                     .map(Size::from_bytes)
 686                     .find(|&i| self.get(i))
 687                     .unwrap_or(end);
 688                 Err(idx..uninit_end)
 689             }
 690             None => Ok(()),
 691         }
 692     }
 693
 694     pub fn set_range(&mut self, start: Size, end: Size, new_state: bool) {
 695         let len = self.len;
 696         if end > len {
 697             self.grow(end - len, new_state);
 698         }
 699         self.set_range_inbounds(start, end, new_state);
 700     }
 701
 702     pub fn set_range_inbounds(&mut self, start: Size, end: Size, new_state: bool) {
 703         let (blocka, bita) = bit_index(start);
 704         let (blockb, bitb) = bit_index(end);
 705         if blocka == blockb {
 706             // First set all bits except the first `bita`,
 707             // then unset the last `64 - bitb` bits.
 708             let range = if bitb == 0 {
 709                 u64::MAX << bita
 710             } else {
 711                 (u64::MAX << bita) & (u64::MAX >> (64 - bitb))
 712             };
 713             if new_state {
 714                 self.blocks[blocka] |= range;
 715             } else {
 716                 self.blocks[blocka] &= !range;
 717             }
 718             return;
 719         }
 720         // across block boundaries
 721         if new_state {
 722             // Set `bita..64` to `1`.
 723             self.blocks[blocka] |= u64::MAX << bita;
 724             // Set `0..bitb` to `1`.
 725             if bitb != 0 {
 726                 self.blocks[blockb] |= u64::MAX >> (64 - bitb);
 727             }
 728             // Fill in all the other blocks (much faster than one bit at a time).
 729             for block in (blocka + 1)..blockb {
 730                 self.blocks[block] = u64::MAX;
 731             }
 732         } else {
 733             // Set `bita..64` to `0`.
 734             self.blocks[blocka] &= !(u64::MAX << bita);
 735             // Set `0..bitb` to `0`.
 736             if bitb != 0 {
 737                 self.blocks[blockb] &= !(u64::MAX >> (64 - bitb));
 738             }
 739             // Fill in all the other blocks (much faster than one bit at a time).
 740             for block in (blocka + 1)..blockb {
 741                 self.blocks[block] = 0;
 742             }
 743         }
 744     }
 745
 746     #[inline]
 747     pub fn get(&self, i: Size) -> bool {
 748         let (block, bit) = bit_index(i);
 749         (self.blocks[block] & (1 << bit)) != 0
 750     }
 751
 752     #[inline]
 753     pub fn set(&mut self, i: Size, new_state: bool) {
 754         let (block, bit) = bit_index(i);
 755         self.set_bit(block, bit, new_state);
 756     }
 757
 758     #[inline]
 759     fn set_bit(&mut self, block: usize, bit: usize, new_state: bool) {
 760         if new_state {
 761             self.blocks[block] |= 1 << bit;
 762         } else {
 763             self.blocks[block] &= !(1 << bit);
 764         }
 765     }
 766
 767     pub fn grow(&mut self, amount: Size, new_state: bool) {
 768         if amount.bytes() == 0 {
 769             return;
 770         }
 771         let unused_trailing_bits =
 772             u64::try_from(self.blocks.len()).unwrap() * Self::BLOCK_SIZE - self.len.bytes();
 773         if amount.bytes() > unused_trailing_bits {
 774             let additional_blocks = amount.bytes() / Self::BLOCK_SIZE + 1;
 775             self.blocks.extend(
 776                 // FIXME(oli-obk): optimize this by repeating `new_state as Block`.
 777                 iter::repeat(0).take(usize::try_from(additional_blocks).unwrap()),
 778             );
 779         }
 780         let start = self.len;
 781         self.len += amount;
 782         self.set_range_inbounds(start, start + amount, new_state); // `Size` operation
 783     }
 784 }
 785
 786 #[inline]
 787 fn bit_index(bits: Size) -> (usize, usize) {
 788     let bits = bits.bytes();
 789     let a = bits / InitMask::BLOCK_SIZE;
 790     let b = bits % InitMask::BLOCK_SIZE;
 791     (usize::try_from(a).unwrap(), usize::try_from(b).unwrap())
 792 }