src/librustc_mir/interpret/snapshot.rs

   1 //! This module contains the machinery necessary to detect infinite loops
   2 //! during const-evaluation by taking snapshots of the state of the interpreter
   3 //! at regular intervals.
   4
   5 // This lives in `interpret` because it needs access to all sots of private state.  However,
   6 // it is not used by the general miri engine, just by CTFE.
   7
   8 use std::hash::{Hash, Hasher};
   9
  10 use rustc::ich::StableHashingContextProvider;
  11 use rustc::mir;
  12 use rustc::mir::interpret::{
  13     AllocId, Pointer, Scalar,
  14     Relocations, Allocation, UndefMask,
  15     InterpResult, InterpError, ResourceExhaustionInfo::*,
  16 };
  17
  18 use rustc::ty::{self, TyCtxt};
  19 use rustc::ty::layout::Align;
  20 use rustc_data_structures::fx::FxHashSet;
  21 use rustc_data_structures::indexed_vec::IndexVec;
  22 use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
  23 use syntax::ast::Mutability;
  24 use syntax::source_map::Span;
  25
  26 use super::eval_context::{LocalState, StackPopCleanup};
  27 use super::{Frame, Memory, Operand, MemPlace, Place, Immediate, ScalarMaybeUndef, LocalValue};
  28 use crate::const_eval::CompileTimeInterpreter;
  29
  30 #[derive(Default)]
  31 pub(crate) struct InfiniteLoopDetector<'mir, 'tcx> {
  32     /// The set of all `InterpSnapshot` *hashes* observed by this detector.
  33     ///
  34     /// When a collision occurs in this table, we store the full snapshot in
  35     /// `snapshots`.
  36     hashes: FxHashSet<u64>,
  37
  38     /// The set of all `InterpSnapshot`s observed by this detector.
  39     ///
  40     /// An `InterpSnapshot` will only be fully cloned once it has caused a
  41     /// collision in `hashes`. As a result, the detector must observe at least
  42     /// *two* full cycles of an infinite loop before it triggers.
  43     snapshots: FxHashSet<InterpSnapshot<'mir, 'tcx>>,
  44 }
  45
  46 impl<'mir, 'tcx> InfiniteLoopDetector<'mir, 'tcx> {
  47     pub fn observe_and_analyze(
  48         &mut self,
  49         tcx: TyCtxt<'tcx>,
  50         span: Span,
  51         memory: &Memory<'mir, 'tcx, CompileTimeInterpreter<'mir, 'tcx>>,
  52         stack: &[Frame<'mir, 'tcx>],
  53     ) -> InterpResult<'tcx, ()> {
  54         // Compute stack's hash before copying anything
  55         let mut hcx = tcx.get_stable_hashing_context();
  56         let mut hasher = StableHasher::<u64>::new();
  57         stack.hash_stable(&mut hcx, &mut hasher);
  58         let hash = hasher.finish();
  59
  60         // Check if we know that hash already
  61         if self.hashes.is_empty() {
  62             // FIXME(#49980): make this warning a lint
  63             tcx.sess.span_warn(span,
  64                 "Constant evaluating a complex constant, this might take some time");
  65         }
  66         if self.hashes.insert(hash) {
  67             // No collision
  68             return Ok(())
  69         }
  70
  71         // We need to make a full copy. NOW things that to get really expensive.
  72         info!("snapshotting the state of the interpreter");
  73
  74         if self.snapshots.insert(InterpSnapshot::new(memory, stack)) {
  75             // Spurious collision or first cycle
  76             return Ok(())
  77         }
  78
  79         // Second cycle
  80         Err(InterpError::ResourceExhaustion(InfiniteLoop).into())
  81     }
  82 }
  83
  84 trait SnapshotContext<'a> {
  85     fn resolve(&'a self, id: &AllocId) -> Option<&'a Allocation>;
  86 }
  87
  88 /// Taking a snapshot of the evaluation context produces a view of
  89 /// the state of the interpreter that is invariant to `AllocId`s.
  90 trait Snapshot<'a, Ctx: SnapshotContext<'a>> {
  91     type Item;
  92     fn snapshot(&self, ctx: &'a Ctx) -> Self::Item;
  93 }
  94
  95 macro_rules! __impl_snapshot_field {
  96     ($field:ident, $ctx:expr) => ($field.snapshot($ctx));
  97     ($field:ident, $ctx:expr, $delegate:expr) => ($delegate);
  98 }
  99
 100 // This assumes the type has two type parameters, first for the tag (set to `()`),
 101 // then for the id
 102 macro_rules! impl_snapshot_for {
 103     (enum $enum_name:ident {
 104         $( $variant:ident $( ( $($field:ident $(-> $delegate:expr)?),* ) )? ),* $(,)?
 105     }) => {
 106
 107         impl<'a, Ctx> self::Snapshot<'a, Ctx> for $enum_name
 108             where Ctx: self::SnapshotContext<'a>,
 109         {
 110             type Item = $enum_name<(), AllocIdSnapshot<'a>>;
 111
 112             #[inline]
 113             fn snapshot(&self, __ctx: &'a Ctx) -> Self::Item {
 114                 match *self {
 115                     $(
 116                         $enum_name::$variant $( ( $(ref $field),* ) )? => {
 117                             $enum_name::$variant $(
 118                                 ( $( __impl_snapshot_field!($field, __ctx $(, $delegate)?) ),* )
 119                             )?
 120                         }
 121                     )*
 122                 }
 123             }
 124         }
 125     };
 126
 127     (struct $struct_name:ident { $($field:ident $(-> $delegate:expr)?),*  $(,)? }) => {
 128         impl<'a, Ctx> self::Snapshot<'a, Ctx> for $struct_name
 129             where Ctx: self::SnapshotContext<'a>,
 130         {
 131             type Item = $struct_name<(), AllocIdSnapshot<'a>>;
 132
 133             #[inline]
 134             fn snapshot(&self, __ctx: &'a Ctx) -> Self::Item {
 135                 let $struct_name {
 136                     $(ref $field),*
 137                 } = *self;
 138
 139                 $struct_name {
 140                     $( $field: __impl_snapshot_field!($field, __ctx $(, $delegate)?) ),*
 141                 }
 142             }
 143         }
 144     };
 145 }
 146
 147 impl<'a, Ctx, T> Snapshot<'a, Ctx> for Option<T>
 148     where Ctx: SnapshotContext<'a>,
 149           T: Snapshot<'a, Ctx>
 150 {
 151     type Item = Option<<T as Snapshot<'a, Ctx>>::Item>;
 152
 153     fn snapshot(&self, ctx: &'a Ctx) -> Self::Item {
 154         match self {
 155             Some(x) => Some(x.snapshot(ctx)),
 156             None => None,
 157         }
 158     }
 159 }
 160
 161 #[derive(Eq, PartialEq)]
 162 struct AllocIdSnapshot<'a>(Option<AllocationSnapshot<'a>>);
 163
 164 impl<'a, Ctx> Snapshot<'a, Ctx> for AllocId
 165     where Ctx: SnapshotContext<'a>,
 166 {
 167     type Item = AllocIdSnapshot<'a>;
 168
 169     fn snapshot(&self, ctx: &'a Ctx) -> Self::Item {
 170         AllocIdSnapshot(ctx.resolve(self).map(|alloc| alloc.snapshot(ctx)))
 171     }
 172 }
 173
 174 impl_snapshot_for!(struct Pointer {
 175     alloc_id,
 176     offset -> *offset, // just copy offset verbatim
 177     tag -> *tag, // just copy tag
 178 });
 179
 180 impl<'a, Ctx> Snapshot<'a, Ctx> for Scalar
 181     where Ctx: SnapshotContext<'a>,
 182 {
 183     type Item = Scalar<(), AllocIdSnapshot<'a>>;
 184
 185     fn snapshot(&self, ctx: &'a Ctx) -> Self::Item {
 186         match self {
 187             Scalar::Ptr(p) => Scalar::Ptr(p.snapshot(ctx)),
 188             Scalar::Raw{ size, data } => Scalar::Raw {
 189                 data: *data,
 190                 size: *size,
 191             },
 192         }
 193     }
 194 }
 195
 196 impl_snapshot_for!(enum ScalarMaybeUndef {
 197     Scalar(s),
 198     Undef,
 199 });
 200
 201 impl_stable_hash_for!(struct crate::interpret::MemPlace {
 202     ptr,
 203     align,
 204     meta,
 205 });
 206 impl_snapshot_for!(struct MemPlace {
 207     ptr,
 208     meta,
 209     align -> *align, // just copy alignment verbatim
 210 });
 211
 212 impl_stable_hash_for!(enum crate::interpret::Place {
 213     Ptr(mem_place),
 214     Local { frame, local },
 215 });
 216 impl<'a, Ctx> Snapshot<'a, Ctx> for Place
 217     where Ctx: SnapshotContext<'a>,
 218 {
 219     type Item = Place<(), AllocIdSnapshot<'a>>;
 220
 221     fn snapshot(&self, ctx: &'a Ctx) -> Self::Item {
 222         match self {
 223             Place::Ptr(p) => Place::Ptr(p.snapshot(ctx)),
 224
 225             Place::Local{ frame, local } => Place::Local{
 226                 frame: *frame,
 227                 local: *local,
 228             },
 229         }
 230     }
 231 }
 232
 233 impl_stable_hash_for!(enum crate::interpret::Immediate {
 234     Scalar(x),
 235     ScalarPair(x, y),
 236 });
 237 impl_snapshot_for!(enum Immediate {
 238     Scalar(s),
 239     ScalarPair(s, t),
 240 });
 241
 242 impl_stable_hash_for!(enum crate::interpret::Operand {
 243     Immediate(x),
 244     Indirect(x),
 245 });
 246 impl_snapshot_for!(enum Operand {
 247     Immediate(v),
 248     Indirect(m),
 249 });
 250
 251 impl_stable_hash_for!(enum crate::interpret::LocalValue {
 252     Dead,
 253     Uninitialized,
 254     Live(x),
 255 });
 256 impl_snapshot_for!(enum LocalValue {
 257     Dead,
 258     Uninitialized,
 259     Live(v),
 260 });
 261
 262 impl<'a, Ctx> Snapshot<'a, Ctx> for Relocations
 263     where Ctx: SnapshotContext<'a>,
 264 {
 265     type Item = Relocations<(), AllocIdSnapshot<'a>>;
 266
 267     fn snapshot(&self, ctx: &'a Ctx) -> Self::Item {
 268         Relocations::from_presorted(self.iter()
 269             .map(|(size, ((), id))| (*size, ((), id.snapshot(ctx))))
 270             .collect())
 271     }
 272 }
 273
 274 #[derive(Eq, PartialEq)]
 275 struct AllocationSnapshot<'a> {
 276     bytes: &'a [u8],
 277     relocations: Relocations<(), AllocIdSnapshot<'a>>,
 278     undef_mask: &'a UndefMask,
 279     align: &'a Align,
 280     mutability: &'a Mutability,
 281 }
 282
 283 impl<'a, Ctx> Snapshot<'a, Ctx> for &'a Allocation
 284     where Ctx: SnapshotContext<'a>,
 285 {
 286     type Item = AllocationSnapshot<'a>;
 287
 288     fn snapshot(&self, ctx: &'a Ctx) -> Self::Item {
 289         let Allocation { bytes, relocations, undef_mask, align, mutability, extra: () } = self;
 290
 291         AllocationSnapshot {
 292             bytes,
 293             undef_mask,
 294             align,
 295             mutability,
 296             relocations: relocations.snapshot(ctx),
 297         }
 298     }
 299 }
 300
 301 impl_stable_hash_for!(enum crate::interpret::eval_context::StackPopCleanup {
 302     Goto(block),
 303     None { cleanup },
 304 });
 305
 306 #[derive(Eq, PartialEq)]
 307 struct FrameSnapshot<'a, 'tcx> {
 308     instance: &'a ty::Instance<'tcx>,
 309     span: &'a Span,
 310     return_to_block: &'a StackPopCleanup,
 311     return_place: Option<Place<(), AllocIdSnapshot<'a>>>,
 312     locals: IndexVec<mir::Local, LocalValue<(), AllocIdSnapshot<'a>>>,
 313     block: &'a mir::BasicBlock,
 314     stmt: usize,
 315 }
 316
 317 impl_stable_hash_for!(impl<> for struct Frame<'mir, 'tcx> {
 318     body,
 319     instance,
 320     span,
 321     return_to_block,
 322     return_place -> (return_place.as_ref().map(|r| &**r)),
 323     locals,
 324     block,
 325     stmt,
 326     extra,
 327 });
 328
 329 impl<'a, 'mir, 'tcx, Ctx> Snapshot<'a, Ctx> for &'a Frame<'mir, 'tcx>
 330     where Ctx: SnapshotContext<'a>,
 331 {
 332     type Item = FrameSnapshot<'a, 'tcx>;
 333
 334     fn snapshot(&self, ctx: &'a Ctx) -> Self::Item {
 335         let Frame {
 336             body: _,
 337             instance,
 338             span,
 339             return_to_block,
 340             return_place,
 341             locals,
 342             block,
 343             stmt,
 344             extra: _,
 345         } = self;
 346
 347         FrameSnapshot {
 348             instance,
 349             span,
 350             return_to_block,
 351             block,
 352             stmt: *stmt,
 353             return_place: return_place.map(|r| r.snapshot(ctx)),
 354             locals: locals.iter().map(|local| local.snapshot(ctx)).collect(),
 355         }
 356     }
 357 }
 358
 359 impl<'a, 'tcx, Ctx> Snapshot<'a, Ctx> for &'a LocalState<'tcx>
 360     where Ctx: SnapshotContext<'a>,
 361 {
 362     type Item = LocalValue<(), AllocIdSnapshot<'a>>;
 363
 364     fn snapshot(&self, ctx: &'a Ctx) -> Self::Item {
 365         let LocalState { value, layout: _ } = self;
 366         value.snapshot(ctx)
 367     }
 368 }
 369
 370 impl_stable_hash_for!(struct LocalState<'tcx> {
 371     value,
 372     layout -> _,
 373 });
 374
 375 impl<'b, 'mir, 'tcx> SnapshotContext<'b>
 376     for Memory<'mir, 'tcx, CompileTimeInterpreter<'mir, 'tcx>>
 377 {
 378     fn resolve(&'b self, id: &AllocId) -> Option<&'b Allocation> {
 379         self.get(*id).ok()
 380     }
 381 }
 382
 383 /// The virtual machine state during const-evaluation at a given point in time.
 384 /// We assume the `CompileTimeInterpreter` has no interesting extra state that
 385 /// is worth considering here.
 386 struct InterpSnapshot<'mir, 'tcx> {
 387     memory: Memory<'mir, 'tcx, CompileTimeInterpreter<'mir, 'tcx>>,
 388     stack: Vec<Frame<'mir, 'tcx>>,
 389 }
 390
 391 impl InterpSnapshot<'mir, 'tcx> {
 392     fn new(
 393         memory: &Memory<'mir, 'tcx, CompileTimeInterpreter<'mir, 'tcx>>,
 394         stack: &[Frame<'mir, 'tcx>],
 395     ) -> Self {
 396         InterpSnapshot {
 397             memory: memory.clone(),
 398             stack: stack.into(),
 399         }
 400     }
 401
 402     // Used to compare two snapshots
 403     fn snapshot(&'b self)
 404         -> Vec<FrameSnapshot<'b, 'tcx>>
 405     {
 406         // Start with the stack, iterate and recursively snapshot
 407         self.stack.iter().map(|frame| frame.snapshot(&self.memory)).collect()
 408     }
 409 }
 410
 411 impl<'mir, 'tcx> Hash for InterpSnapshot<'mir, 'tcx> {
 412     fn hash<H: Hasher>(&self, state: &mut H) {
 413         // Implement in terms of hash stable, so that k1 == k2 -> hash(k1) == hash(k2)
 414         let mut hcx = self.memory.tcx.get_stable_hashing_context();
 415         let mut hasher = StableHasher::<u64>::new();
 416         self.hash_stable(&mut hcx, &mut hasher);
 417         hasher.finish().hash(state)
 418     }
 419 }
 420
 421 impl_stable_hash_for!(impl<> for struct InterpSnapshot<'mir, 'tcx> {
 422     // Not hashing memory: Avoid hashing memory all the time during execution
 423     memory -> _,
 424     stack,
 425 });
 426
 427 impl<'mir, 'tcx> Eq for InterpSnapshot<'mir, 'tcx> {}
 428
 429 impl<'mir, 'tcx> PartialEq for InterpSnapshot<'mir, 'tcx> {
 430     fn eq(&self, other: &Self) -> bool {
 431         // FIXME: This looks to be a *ridiculously expensive* comparison operation.
 432         // Doesn't this make tons of copies?  Either `snapshot` is very badly named,
 433         // or it does!
 434         self.snapshot() == other.snapshot()
 435     }
 436 }