src/librustc/mir/interpret/mod.rs

   1 //! An interpreter for MIR used in CTFE and by miri
   2
   3 #[macro_export]
   4 macro_rules! throw_unsup {
   5     ($($tt:tt)*) => { return Err(err_unsup!($($tt)*).into()) };
   6 }
   7
   8 #[macro_export]
   9 macro_rules! throw_inval {
  10     ($($tt:tt)*) => { return Err(err_inval!($($tt)*).into()) };
  11 }
  12
  13 #[macro_export]
  14 macro_rules! throw_ub {
  15     ($($tt:tt)*) => {
  16         return Err($crate::mir::interpret::InterpError::UndefinedBehaviour(
  17             $crate::mir::interpret::UndefinedBehaviourInfo::$($tt)*
  18         ).into())
  19     };
  20 }
  21
  22 #[macro_export]
  23 macro_rules! throw_panic {
  24     ($($tt:tt)*) => { return Err(err_panic!($($tt)*).into()) };
  25 }
  26
  27 #[macro_export]
  28 macro_rules! throw_exhaust {
  29     ($($tt:tt)*) => { return Err(err_exhaust!($($tt)*).into()) };
  30 }
  31
  32 #[macro_export]
  33 macro_rules! err_inval {
  34     ($($tt:tt)*) => {
  35         $crate::mir::interpret::InterpError::InvalidProgram(
  36             $crate::mir::interpret::InvalidProgramInfo::$($tt)*
  37         )
  38     };
  39 }
  40
  41 #[macro_export]
  42 macro_rules! err_unsup {
  43     ($($tt:tt)*) => {
  44         $crate::mir::interpret::InterpError::Unsupported(
  45             $crate::mir::interpret::UnsupportedOpInfo::$($tt)*
  46         )
  47     };
  48 }
  49
  50 #[macro_export]
  51 macro_rules! err_exhaust {
  52     ($($tt:tt)*) => {
  53         $crate::mir::interpret::InterpError::ResourceExhaustion(
  54             $crate::mir::interpret::ResourceExhaustionInfo::$($tt)*
  55         )
  56     };
  57 }
  58
  59 #[macro_export]
  60 macro_rules! err_panic {
  61     ($($tt:tt)*) => {
  62         $crate::mir::interpret::InterpError::Panic(
  63             $crate::mir::interpret::PanicInfo::$($tt)*
  64         )
  65     };
  66 }
  67
  68 mod error;
  69 mod value;
  70 mod allocation;
  71 mod pointer;
  72
  73 pub use self::error::{
  74     InterpErrorInfo, InterpResult, InterpError, AssertMessage, ConstEvalErr, struct_error,
  75     FrameInfo, ConstEvalRawResult, ConstEvalResult, ErrorHandled, PanicInfo, UnsupportedOpInfo,
  76     InvalidProgramInfo, ResourceExhaustionInfo, UndefinedBehaviourInfo,
  77 };
  78
  79 pub use self::value::{Scalar, ScalarMaybeUndef, RawConst, ConstValue};
  80
  81 pub use self::allocation::{Allocation, AllocationExtra, Relocations, UndefMask};
  82
  83 pub use self::pointer::{Pointer, PointerArithmetic, CheckInAllocMsg};
  84
  85 use std::fmt;
  86 use crate::mir;
  87 use crate::hir::def_id::DefId;
  88 use crate::ty::{self, TyCtxt, Instance, subst::UnpackedKind};
  89 use crate::ty::layout::{self, Size};
  90 use std::io;
  91 use rustc_serialize::{Encoder, Decodable, Encodable};
  92 use rustc_data_structures::fx::FxHashMap;
  93 use rustc_data_structures::sync::{Lock as Mutex, HashMapExt};
  94 use rustc_data_structures::tiny_list::TinyList;
  95 use rustc_macros::HashStable;
  96 use byteorder::{WriteBytesExt, ReadBytesExt, LittleEndian, BigEndian};
  97 use crate::ty::codec::TyDecoder;
  98 use std::sync::atomic::{AtomicU32, Ordering};
  99 use std::num::NonZeroU32;
 100
 101 /// Uniquely identifies a specific constant or static.
 102 #[derive(Copy, Clone, Debug, Eq, PartialEq, Hash, RustcEncodable, RustcDecodable, HashStable)]
 103 pub struct GlobalId<'tcx> {
 104     /// For a constant or static, the `Instance` of the item itself.
 105     /// For a promoted global, the `Instance` of the function they belong to.
 106     pub instance: ty::Instance<'tcx>,
 107
 108     /// The index for promoted globals within their function's `mir::Body`.
 109     pub promoted: Option<mir::Promoted>,
 110 }
 111
 112 #[derive(Copy, Clone, Eq, Hash, Ord, PartialEq, PartialOrd, Debug)]
 113 pub struct AllocId(pub u64);
 114
 115 impl rustc_serialize::UseSpecializedEncodable for AllocId {}
 116 impl rustc_serialize::UseSpecializedDecodable for AllocId {}
 117
 118 #[derive(RustcDecodable, RustcEncodable)]
 119 enum AllocDiscriminant {
 120     Alloc,
 121     Fn,
 122     Static,
 123 }
 124
 125 pub fn specialized_encode_alloc_id<'tcx, E: Encoder>(
 126     encoder: &mut E,
 127     tcx: TyCtxt<'tcx>,
 128     alloc_id: AllocId,
 129 ) -> Result<(), E::Error> {
 130     let alloc: GlobalAlloc<'tcx> =
 131         tcx.alloc_map.lock().get(alloc_id).expect("no value for AllocId");
 132     match alloc {
 133         GlobalAlloc::Memory(alloc) => {
 134             trace!("encoding {:?} with {:#?}", alloc_id, alloc);
 135             AllocDiscriminant::Alloc.encode(encoder)?;
 136             alloc.encode(encoder)?;
 137         }
 138         GlobalAlloc::Function(fn_instance) => {
 139             trace!("encoding {:?} with {:#?}", alloc_id, fn_instance);
 140             AllocDiscriminant::Fn.encode(encoder)?;
 141             fn_instance.encode(encoder)?;
 142         }
 143         GlobalAlloc::Static(did) => {
 144             // referring to statics doesn't need to know about their allocations,
 145             // just about its DefId
 146             AllocDiscriminant::Static.encode(encoder)?;
 147             did.encode(encoder)?;
 148         }
 149     }
 150     Ok(())
 151 }
 152
 153 // Used to avoid infinite recursion when decoding cyclic allocations.
 154 type DecodingSessionId = NonZeroU32;
 155
 156 #[derive(Clone)]
 157 enum State {
 158     Empty,
 159     InProgressNonAlloc(TinyList<DecodingSessionId>),
 160     InProgress(TinyList<DecodingSessionId>, AllocId),
 161     Done(AllocId),
 162 }
 163
 164 pub struct AllocDecodingState {
 165     // For each AllocId we keep track of which decoding state it's currently in.
 166     decoding_state: Vec<Mutex<State>>,
 167     // The offsets of each allocation in the data stream.
 168     data_offsets: Vec<u32>,
 169 }
 170
 171 impl AllocDecodingState {
 172
 173     pub fn new_decoding_session(&self) -> AllocDecodingSession<'_> {
 174         static DECODER_SESSION_ID: AtomicU32 = AtomicU32::new(0);
 175         let counter = DECODER_SESSION_ID.fetch_add(1, Ordering::SeqCst);
 176
 177         // Make sure this is never zero
 178         let session_id = DecodingSessionId::new((counter & 0x7FFFFFFF) + 1).unwrap();
 179
 180         AllocDecodingSession {
 181             state: self,
 182             session_id,
 183         }
 184     }
 185
 186     pub fn new(data_offsets: Vec<u32>) -> AllocDecodingState {
 187         let decoding_state = vec![Mutex::new(State::Empty); data_offsets.len()];
 188
 189         AllocDecodingState {
 190             decoding_state,
 191             data_offsets,
 192         }
 193     }
 194 }
 195
 196 #[derive(Copy, Clone)]
 197 pub struct AllocDecodingSession<'s> {
 198     state: &'s AllocDecodingState,
 199     session_id: DecodingSessionId,
 200 }
 201
 202 impl<'s> AllocDecodingSession<'s> {
 203     // Decodes an AllocId in a thread-safe way.
 204     pub fn decode_alloc_id<D>(&self, decoder: &mut D) -> Result<AllocId, D::Error>
 205     where
 206         D: TyDecoder<'tcx>,
 207     {
 208         // Read the index of the allocation
 209         let idx = decoder.read_u32()? as usize;
 210         let pos = self.state.data_offsets[idx] as usize;
 211
 212         // Decode the AllocDiscriminant now so that we know if we have to reserve an
 213         // AllocId.
 214         let (alloc_kind, pos) = decoder.with_position(pos, |decoder| {
 215             let alloc_kind = AllocDiscriminant::decode(decoder)?;
 216             Ok((alloc_kind, decoder.position()))
 217         })?;
 218
 219         // Check the decoding state, see if it's already decoded or if we should
 220         // decode it here.
 221         let alloc_id = {
 222             let mut entry = self.state.decoding_state[idx].lock();
 223
 224             match *entry {
 225                 State::Done(alloc_id) => {
 226                     return Ok(alloc_id);
 227                 }
 228                 ref mut entry @ State::Empty => {
 229                     // We are allowed to decode
 230                     match alloc_kind {
 231                         AllocDiscriminant::Alloc => {
 232                             // If this is an allocation, we need to reserve an
 233                             // AllocId so we can decode cyclic graphs.
 234                             let alloc_id = decoder.tcx().alloc_map.lock().reserve();
 235                             *entry = State::InProgress(
 236                                 TinyList::new_single(self.session_id),
 237                                 alloc_id);
 238                             Some(alloc_id)
 239                         },
 240                         AllocDiscriminant::Fn | AllocDiscriminant::Static => {
 241                             // Fns and statics cannot be cyclic and their AllocId
 242                             // is determined later by interning
 243                             *entry = State::InProgressNonAlloc(
 244                                 TinyList::new_single(self.session_id));
 245                             None
 246                         }
 247                     }
 248                 }
 249                 State::InProgressNonAlloc(ref mut sessions) => {
 250                     if sessions.contains(&self.session_id) {
 251                         bug!("This should be unreachable")
 252                     } else {
 253                         // Start decoding concurrently
 254                         sessions.insert(self.session_id);
 255                         None
 256                     }
 257                 }
 258                 State::InProgress(ref mut sessions, alloc_id) => {
 259                     if sessions.contains(&self.session_id) {
 260                         // Don't recurse.
 261                         return Ok(alloc_id)
 262                     } else {
 263                         // Start decoding concurrently
 264                         sessions.insert(self.session_id);
 265                         Some(alloc_id)
 266                     }
 267                 }
 268             }
 269         };
 270
 271         // Now decode the actual data
 272         let alloc_id = decoder.with_position(pos, |decoder| {
 273             match alloc_kind {
 274                 AllocDiscriminant::Alloc => {
 275                     let allocation = <&'tcx Allocation as Decodable>::decode(decoder)?;
 276                     // We already have a reserved AllocId.
 277                     let alloc_id = alloc_id.unwrap();
 278                     trace!("decoded alloc {:?} {:#?}", alloc_id, allocation);
 279                     decoder.tcx().alloc_map.lock().set_alloc_id_same_memory(alloc_id, allocation);
 280                     Ok(alloc_id)
 281                 },
 282                 AllocDiscriminant::Fn => {
 283                     assert!(alloc_id.is_none());
 284                     trace!("creating fn alloc id");
 285                     let instance = ty::Instance::decode(decoder)?;
 286                     trace!("decoded fn alloc instance: {:?}", instance);
 287                     let alloc_id = decoder.tcx().alloc_map.lock().create_fn_alloc(instance);
 288                     Ok(alloc_id)
 289                 },
 290                 AllocDiscriminant::Static => {
 291                     assert!(alloc_id.is_none());
 292                     trace!("creating extern static alloc id at");
 293                     let did = DefId::decode(decoder)?;
 294                     let alloc_id = decoder.tcx().alloc_map.lock().create_static_alloc(did);
 295                     Ok(alloc_id)
 296                 }
 297             }
 298         })?;
 299
 300         self.state.decoding_state[idx].with_lock(|entry| {
 301             *entry = State::Done(alloc_id);
 302         });
 303
 304         Ok(alloc_id)
 305     }
 306 }
 307
 308 impl fmt::Display for AllocId {
 309     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 310         write!(f, "{}", self.0)
 311     }
 312 }
 313
 314 /// An allocation in the global (tcx-managed) memory can be either a function pointer,
 315 /// a static, or a "real" allocation with some data in it.
 316 #[derive(Debug, Clone, Eq, PartialEq, Hash, RustcDecodable, RustcEncodable, HashStable)]
 317 pub enum GlobalAlloc<'tcx> {
 318     /// The alloc ID is used as a function pointer
 319     Function(Instance<'tcx>),
 320     /// The alloc ID points to a "lazy" static variable that did not get computed (yet).
 321     /// This is also used to break the cycle in recursive statics.
 322     Static(DefId),
 323     /// The alloc ID points to memory.
 324     Memory(&'tcx Allocation),
 325 }
 326
 327 pub struct AllocMap<'tcx> {
 328     /// Lets you know what an `AllocId` refers to.
 329     alloc_map: FxHashMap<AllocId, GlobalAlloc<'tcx>>,
 330
 331     /// Used to ensure that statics and functions only get one associated `AllocId`.
 332     /// Should never contain a `GlobalAlloc::Memory`!
 333     /// FIXME: Should we just have two separate dedup maps for statics and functions each?
 334     dedup: FxHashMap<GlobalAlloc<'tcx>, AllocId>,
 335
 336     /// The `AllocId` to assign to the next requested ID.
 337     /// Always incremented, never gets smaller.
 338     next_id: AllocId,
 339 }
 340
 341 impl<'tcx> AllocMap<'tcx> {
 342     pub fn new() -> Self {
 343         AllocMap {
 344             alloc_map: Default::default(),
 345             dedup: Default::default(),
 346             next_id: AllocId(0),
 347         }
 348     }
 349
 350     /// Obtains a new allocation ID that can be referenced but does not
 351     /// yet have an allocation backing it.
 352     ///
 353     /// Make sure to call `set_alloc_id_memory` or `set_alloc_id_same_memory` before returning such
 354     /// an `AllocId` from a query.
 355     pub fn reserve(
 356         &mut self,
 357     ) -> AllocId {
 358         let next = self.next_id;
 359         self.next_id.0 = self.next_id.0
 360             .checked_add(1)
 361             .expect("You overflowed a u64 by incrementing by 1... \
 362                      You've just earned yourself a free drink if we ever meet. \
 363                      Seriously, how did you do that?!");
 364         next
 365     }
 366
 367     /// Reserve a new ID *if* this allocation has not been dedup-reserved before.
 368     /// Should only be used for function pointers and statics, we don't want
 369     /// to dedup IDs for "real" memory!
 370     fn reserve_and_set_dedup(&mut self, alloc: GlobalAlloc<'tcx>) -> AllocId {
 371         match alloc {
 372             GlobalAlloc::Function(..) | GlobalAlloc::Static(..) => {},
 373             GlobalAlloc::Memory(..) => bug!("Trying to dedup-reserve memory with real data!"),
 374         }
 375         if let Some(&alloc_id) = self.dedup.get(&alloc) {
 376             return alloc_id;
 377         }
 378         let id = self.reserve();
 379         debug!("creating alloc {:?} with id {}", alloc, id);
 380         self.alloc_map.insert(id, alloc.clone());
 381         self.dedup.insert(alloc, id);
 382         id
 383     }
 384
 385     /// Generates an `AllocId` for a static or return a cached one in case this function has been
 386     /// called on the same static before.
 387     pub fn create_static_alloc(&mut self, static_id: DefId) -> AllocId {
 388         self.reserve_and_set_dedup(GlobalAlloc::Static(static_id))
 389     }
 390
 391     /// Generates an `AllocId` for a function.  Depending on the function type,
 392     /// this might get deduplicated or assigned a new ID each time.
 393     pub fn create_fn_alloc(&mut self, instance: Instance<'tcx>) -> AllocId {
 394         // Functions cannot be identified by pointers, as asm-equal functions can get deduplicated
 395         // by the linker (we set the "unnamed_addr" attribute for LLVM) and functions can be
 396         // duplicated across crates.
 397         // We thus generate a new `AllocId` for every mention of a function. This means that
 398         // `main as fn() == main as fn()` is false, while `let x = main as fn(); x == x` is true.
 399         // However, formatting code relies on function identity (see #58320), so we only do
 400         // this for generic functions.  Lifetime parameters are ignored.
 401         let is_generic = instance.substs.into_iter().any(|kind| {
 402             match kind.unpack() {
 403                 UnpackedKind::Lifetime(_) => false,
 404                 _ => true,
 405             }
 406         });
 407         if is_generic {
 408             // Get a fresh ID
 409             let id = self.reserve();
 410             self.alloc_map.insert(id, GlobalAlloc::Function(instance));
 411             id
 412         } else {
 413             // Deduplicate
 414             self.reserve_and_set_dedup(GlobalAlloc::Function(instance))
 415         }
 416     }
 417
 418     /// Intern the `Allocation` and return a new `AllocId`, even if there's already an identical
 419     /// `Allocation` with a different `AllocId`.
 420     /// Statics with identical content will still point to the same `Allocation`, i.e.,
 421     /// their data will be deduplicated through `Allocation` interning -- but they
 422     /// are different places in memory and as such need different IDs.
 423     pub fn create_memory_alloc(&mut self, mem: &'tcx Allocation) -> AllocId {
 424         let id = self.reserve();
 425         self.set_alloc_id_memory(id, mem);
 426         id
 427     }
 428
 429     /// Returns `None` in case the `AllocId` is dangling. An `InterpretCx` can still have a
 430     /// local `Allocation` for that `AllocId`, but having such an `AllocId` in a constant is
 431     /// illegal and will likely ICE.
 432     /// This function exists to allow const eval to detect the difference between evaluation-
 433     /// local dangling pointers and allocations in constants/statics.
 434     #[inline]
 435     pub fn get(&self, id: AllocId) -> Option<GlobalAlloc<'tcx>> {
 436         self.alloc_map.get(&id).cloned()
 437     }
 438
 439     /// Panics if the `AllocId` does not refer to an `Allocation`
 440     pub fn unwrap_memory(&self, id: AllocId) -> &'tcx Allocation {
 441         match self.get(id) {
 442             Some(GlobalAlloc::Memory(mem)) => mem,
 443             _ => bug!("expected allocation id {} to point to memory", id),
 444         }
 445     }
 446
 447     /// Freeze an `AllocId` created with `reserve` by pointing it at an `Allocation`. Trying to
 448     /// call this function twice, even with the same `Allocation` will ICE the compiler.
 449     pub fn set_alloc_id_memory(&mut self, id: AllocId, mem: &'tcx Allocation) {
 450         if let Some(old) = self.alloc_map.insert(id, GlobalAlloc::Memory(mem)) {
 451             bug!("tried to set allocation id {}, but it was already existing as {:#?}", id, old);
 452         }
 453     }
 454
 455     /// Freeze an `AllocId` created with `reserve` by pointing it at an `Allocation`. May be called
 456     /// twice for the same `(AllocId, Allocation)` pair.
 457     fn set_alloc_id_same_memory(&mut self, id: AllocId, mem: &'tcx Allocation) {
 458         self.alloc_map.insert_same(id, GlobalAlloc::Memory(mem));
 459     }
 460 }
 461
 462 ////////////////////////////////////////////////////////////////////////////////
 463 // Methods to access integers in the target endianness
 464 ////////////////////////////////////////////////////////////////////////////////
 465
 466 #[inline]
 467 pub fn write_target_uint(
 468     endianness: layout::Endian,
 469     mut target: &mut [u8],
 470     data: u128,
 471 ) -> Result<(), io::Error> {
 472     let len = target.len();
 473     match endianness {
 474         layout::Endian::Little => target.write_uint128::<LittleEndian>(data, len),
 475         layout::Endian::Big => target.write_uint128::<BigEndian>(data, len),
 476     }
 477 }
 478
 479 #[inline]
 480 pub fn read_target_uint(endianness: layout::Endian, mut source: &[u8]) -> Result<u128, io::Error> {
 481     match endianness {
 482         layout::Endian::Little => source.read_uint128::<LittleEndian>(source.len()),
 483         layout::Endian::Big => source.read_uint128::<BigEndian>(source.len()),
 484     }
 485 }
 486
 487 ////////////////////////////////////////////////////////////////////////////////
 488 // Methods to facilitate working with signed integers stored in a u128
 489 ////////////////////////////////////////////////////////////////////////////////
 490
 491 /// Truncate `value` to `size` bits and then sign-extend it to 128 bits
 492 /// (i.e., if it is negative, fill with 1's on the left).
 493 #[inline]
 494 pub fn sign_extend(value: u128, size: Size) -> u128 {
 495     let size = size.bits();
 496     if size == 0 {
 497         // Truncated until nothing is left.
 498         return 0;
 499     }
 500     // sign extend
 501     let shift = 128 - size;
 502     // shift the unsigned value to the left
 503     // and back to the right as signed (essentially fills with FF on the left)
 504     (((value << shift) as i128) >> shift) as u128
 505 }
 506
 507 /// Truncate `value` to `size` bits.
 508 #[inline]
 509 pub fn truncate(value: u128, size: Size) -> u128 {
 510     let size = size.bits();
 511     if size == 0 {
 512         // Truncated until nothing is left.
 513         return 0;
 514     }
 515     let shift = 128 - size;
 516     // truncate (shift left to drop out leftover values, shift right to fill with zeroes)
 517     (value << shift) >> shift
 518 }