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