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