src/lib.rs

   1 #![feature(
   2     rustc_private,
   3     catch_expr,
   4 )]
   5
   6 #![cfg_attr(feature = "cargo-clippy", allow(cast_lossless))]
   7
   8 #[macro_use]
   9 extern crate log;
  10
  11 // From rustc.
  12 #[macro_use]
  13 extern crate rustc;
  14 extern crate rustc_data_structures;
  15 extern crate rustc_mir;
  16 extern crate rustc_target;
  17 extern crate syntax;
  18
  19 use rustc::ty::{self, TyCtxt};
  20 use rustc::ty::layout::{TyLayout, LayoutOf, Size};
  21 use rustc::ty::subst::Subst;
  22 use rustc::hir::def_id::DefId;
  23 use rustc::mir;
  24
  25 use rustc_data_structures::fx::FxHasher;
  26
  27 use syntax::ast::Mutability;
  28 use syntax::codemap::Span;
  29
  30 use std::collections::{HashMap, BTreeMap};
  31 use std::hash::{Hash, Hasher};
  32
  33 pub use rustc::mir::interpret::*;
  34 pub use rustc_mir::interpret::*;
  35
  36 mod fn_call;
  37 mod operator;
  38 mod intrinsic;
  39 mod helpers;
  40 mod memory;
  41 mod tls;
  42 mod locks;
  43 mod range_map;
  44 mod validation;
  45
  46 use fn_call::EvalContextExt as MissingFnsEvalContextExt;
  47 use operator::EvalContextExt as OperatorEvalContextExt;
  48 use intrinsic::EvalContextExt as IntrinsicEvalContextExt;
  49 use tls::EvalContextExt as TlsEvalContextExt;
  50 use locks::LockInfo;
  51 use locks::MemoryExt as LockMemoryExt;
  52 use validation::EvalContextExt as ValidationEvalContextExt;
  53 use range_map::RangeMap;
  54 use validation::{ValidationQuery, AbsPlace};
  55
  56 pub trait ScalarExt {
  57     fn null(size: Size) -> Self;
  58     fn from_i32(i: i32) -> Self;
  59     fn from_uint(i: impl Into<u128>, ptr_size: Size) -> Self;
  60     fn from_int(i: impl Into<i128>, ptr_size: Size) -> Self;
  61     fn from_f32(f: f32) -> Self;
  62     fn from_f64(f: f64) -> Self;
  63     fn to_usize<'a, 'mir, 'tcx>(self, ecx: &rustc_mir::interpret::EvalContext<'a, 'mir, 'tcx, Evaluator<'tcx>>) -> EvalResult<'static, u64>;
  64     fn is_null(self) -> bool;
  65     /// HACK: this function just extracts all bits if `defined != 0`
  66     /// Mainly used for args of C-functions and we should totally correctly fetch the size
  67     /// of their arguments
  68     fn to_bytes(self) -> EvalResult<'static, u128>;
  69 }
  70
  71 impl ScalarExt for Scalar {
  72     fn null(size: Size) -> Self {
  73         Scalar::Bits { bits: 0, size: size.bytes() as u8 }
  74     }
  75
  76     fn from_i32(i: i32) -> Self {
  77         Scalar::Bits { bits: i as u32 as u128, size: 4 }
  78     }
  79
  80     fn from_uint(i: impl Into<u128>, ptr_size: Size) -> Self {
  81         Scalar::Bits { bits: i.into(), size: ptr_size.bytes() as u8 }
  82     }
  83
  84     fn from_int(i: impl Into<i128>, ptr_size: Size) -> Self {
  85         Scalar::Bits { bits: i.into() as u128, size: ptr_size.bytes() as u8 }
  86     }
  87
  88     fn from_f32(f: f32) -> Self {
  89         Scalar::Bits { bits: f.to_bits() as u128, size: 4 }
  90     }
  91
  92     fn from_f64(f: f64) -> Self {
  93         Scalar::Bits { bits: f.to_bits() as u128, size: 8 }
  94     }
  95
  96     fn to_usize<'a, 'mir, 'tcx>(self, ecx: &rustc_mir::interpret::EvalContext<'a, 'mir, 'tcx, Evaluator<'tcx>>) -> EvalResult<'static, u64> {
  97         let b = self.to_bits(ecx.memory.pointer_size())?;
  98         assert_eq!(b as u64 as u128, b);
  99         Ok(b as u64)
 100     }
 101
 102     fn is_null(self) -> bool {
 103         match self {
 104             Scalar::Bits { bits, .. } => bits == 0,
 105             Scalar::Ptr(_) => false
 106         }
 107     }
 108
 109     fn to_bytes(self) -> EvalResult<'static, u128> {
 110         match self {
 111             Scalar::Bits { bits, size } => {
 112                 assert_ne!(size, 0);
 113                 Ok(bits)
 114             },
 115             Scalar::Ptr(_) => err!(ReadPointerAsBytes),
 116         }
 117     }
 118 }
 119
 120 pub fn create_ecx<'a, 'mir: 'a, 'tcx: 'mir>(
 121     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 122     main_id: DefId,
 123     start_wrapper: Option<DefId>,
 124 ) -> EvalResult<'tcx, (EvalContext<'a, 'mir, 'tcx, Evaluator<'tcx>>, Option<Pointer>)> {
 125     let mut ecx = EvalContext::new(
 126         tcx.at(syntax::codemap::DUMMY_SP),
 127         ty::ParamEnv::reveal_all(),
 128         Default::default(),
 129         MemoryData::new()
 130     );
 131
 132     let main_instance = ty::Instance::mono(ecx.tcx.tcx, main_id);
 133     let main_mir = ecx.load_mir(main_instance.def)?;
 134     let mut cleanup_ptr = None; // Scalar to be deallocated when we are done
 135
 136     if !main_mir.return_ty().is_nil() || main_mir.arg_count != 0 {
 137         return err!(Unimplemented(
 138             "miri does not support main functions without `fn()` type signatures"
 139                 .to_owned(),
 140         ));
 141     }
 142     let ptr_size = ecx.memory.pointer_size();
 143
 144     if let Some(start_id) = start_wrapper {
 145         let main_ret_ty = ecx.tcx.fn_sig(main_id).output();
 146         let main_ret_ty = main_ret_ty.no_late_bound_regions().unwrap();
 147         let start_instance = ty::Instance::resolve(
 148             ecx.tcx.tcx,
 149             ty::ParamEnv::reveal_all(),
 150             start_id,
 151             ecx.tcx.mk_substs(
 152                 ::std::iter::once(ty::subst::Kind::from(main_ret_ty)))
 153             ).unwrap();
 154         let start_mir = ecx.load_mir(start_instance.def)?;
 155
 156         if start_mir.arg_count != 3 {
 157             return err!(AbiViolation(format!(
 158                 "'start' lang item should have three arguments, but has {}",
 159                 start_mir.arg_count
 160             )));
 161         }
 162
 163         // Return value
 164         let size = ecx.tcx.data_layout.pointer_size;
 165         let align = ecx.tcx.data_layout.pointer_align;
 166         let ret_ptr = ecx.memory_mut().allocate(size, align, MemoryKind::Stack)?;
 167         cleanup_ptr = Some(ret_ptr);
 168
 169         // Push our stack frame
 170         ecx.push_stack_frame(
 171             start_instance,
 172             start_mir.span,
 173             start_mir,
 174             Place::from_ptr(ret_ptr, align),
 175             StackPopCleanup::None,
 176         )?;
 177
 178         let mut args = ecx.frame().mir.args_iter();
 179
 180         // First argument: pointer to main()
 181         let main_ptr = ecx.memory_mut().create_fn_alloc(main_instance);
 182         let dest = ecx.eval_place(&mir::Place::Local(args.next().unwrap()))?;
 183         let main_ty = main_instance.ty(ecx.tcx.tcx);
 184         let main_ptr_ty = ecx.tcx.mk_fn_ptr(main_ty.fn_sig(ecx.tcx.tcx));
 185         ecx.write_value(
 186             ValTy {
 187                 value: Value::Scalar(Scalar::Ptr(main_ptr).into()),
 188                 ty: main_ptr_ty,
 189             },
 190             dest,
 191         )?;
 192
 193         // Second argument (argc): 1
 194         let dest = ecx.eval_place(&mir::Place::Local(args.next().unwrap()))?;
 195         let ty = ecx.tcx.types.isize;
 196         ecx.write_scalar(dest, Scalar::from_int(1, ptr_size), ty)?;
 197
 198         // FIXME: extract main source file path
 199         // Third argument (argv): &[b"foo"]
 200         let dest = ecx.eval_place(&mir::Place::Local(args.next().unwrap()))?;
 201         let ty = ecx.tcx.mk_imm_ptr(ecx.tcx.mk_imm_ptr(ecx.tcx.types.u8));
 202         let foo = ecx.memory.allocate_bytes(b"foo\0");
 203         let ptr_align = ecx.tcx.data_layout.pointer_align;
 204         let foo_ptr = ecx.memory.allocate(ptr_size, ptr_align, MemoryKind::Stack)?;
 205         ecx.memory.write_scalar(foo_ptr.into(), ptr_align, Scalar::Ptr(foo).into(), ptr_size, ptr_align, false)?;
 206         ecx.memory.mark_static_initialized(foo_ptr.alloc_id, Mutability::Immutable)?;
 207         ecx.write_ptr(dest, foo_ptr.into(), ty)?;
 208
 209         assert!(args.next().is_none(), "start lang item has more arguments than expected");
 210     } else {
 211         ecx.push_stack_frame(
 212             main_instance,
 213             main_mir.span,
 214             main_mir,
 215             Place::from_scalar_ptr(Scalar::from_int(1, ptr_size).into(), ty::layout::Align::from_bytes(1, 1).unwrap()),
 216             StackPopCleanup::None,
 217         )?;
 218
 219         // No arguments
 220         let mut args = ecx.frame().mir.args_iter();
 221         assert!(args.next().is_none(), "main function must not have arguments");
 222     }
 223
 224     Ok((ecx, cleanup_ptr))
 225 }
 226
 227 pub fn eval_main<'a, 'tcx: 'a>(
 228     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 229     main_id: DefId,
 230     start_wrapper: Option<DefId>,
 231 ) {
 232     let (mut ecx, cleanup_ptr) = create_ecx(tcx, main_id, start_wrapper).expect("Couldn't create ecx");
 233
 234     let res: EvalResult = do catch {
 235         while ecx.step()? {}
 236         ecx.run_tls_dtors()?;
 237         if let Some(cleanup_ptr) = cleanup_ptr {
 238             ecx.memory_mut().deallocate(
 239                 cleanup_ptr,
 240                 None,
 241                 MemoryKind::Stack,
 242             )?;
 243         }
 244     };
 245
 246     match res {
 247         Ok(()) => {
 248             let leaks = ecx.memory().leak_report();
 249             if leaks != 0 {
 250                 // TODO: Prevent leaks which aren't supposed to be there
 251                 //tcx.sess.err("the evaluated program leaked memory");
 252             }
 253         }
 254         Err(e) => {
 255             if let Some(frame) = ecx.stack().last() {
 256                 let block = &frame.mir.basic_blocks()[frame.block];
 257                 let span = if frame.stmt < block.statements.len() {
 258                     block.statements[frame.stmt].source_info.span
 259                 } else {
 260                     block.terminator().source_info.span
 261                 };
 262
 263                 let e = e.to_string();
 264                 let msg = format!("constant evaluation error: {}", e);
 265                 let mut err = struct_error(ecx.tcx.tcx.at(span), msg.as_str());
 266                 let (frames, span) = ecx.generate_stacktrace(None);
 267                 err.span_label(span, e);
 268                 for FrameInfo { span, location, .. } in frames {
 269                     err.span_note(span, &format!("inside call to `{}`", location));
 270                 }
 271                 err.emit();
 272             } else {
 273                 ecx.tcx.sess.err(&e.to_string());
 274             }
 275
 276             for (i, frame) in ecx.stack().iter().enumerate() {
 277                 trace!("-------------------");
 278                 trace!("Frame {}", i);
 279                 trace!("    return: {:#?}", frame.return_place);
 280                 for (i, local) in frame.locals.iter().enumerate() {
 281                     if let Ok(local) = local.access() {
 282                         trace!("    local {}: {:?}", i, local);
 283                     }
 284                 }
 285             }
 286         }
 287     }
 288 }
 289
 290 #[derive(Clone, Default, PartialEq, Eq)]
 291 pub struct Evaluator<'tcx> {
 292     /// Environment variables set by `setenv`
 293     /// Miri does not expose env vars from the host to the emulated program
 294     pub(crate) env_vars: HashMap<Vec<u8>, Pointer>,
 295
 296     /// Places that were suspended by the validation subsystem, and will be recovered later
 297     pub(crate) suspended: HashMap<DynamicLifetime, Vec<ValidationQuery<'tcx>>>,
 298 }
 299
 300 impl<'tcx> Hash for Evaluator<'tcx> {
 301     fn hash<H: Hasher>(&self, state: &mut H) {
 302         let Evaluator {
 303             env_vars,
 304             suspended: _,
 305         } = self;
 306
 307         env_vars.iter()
 308             .map(|(env, ptr)| {
 309                 let mut h = FxHasher::default();
 310                 env.hash(&mut h);
 311                 ptr.hash(&mut h);
 312                 h.finish()
 313             })
 314             .fold(0u64, |acc, hash| acc.wrapping_add(hash))
 315             .hash(state);
 316     }
 317 }
 318
 319 pub type TlsKey = u128;
 320
 321 #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
 322 pub struct TlsEntry<'tcx> {
 323     data: Scalar, // Will eventually become a map from thread IDs to `Scalar`s, if we ever support more than one thread.
 324     dtor: Option<ty::Instance<'tcx>>,
 325 }
 326
 327 #[derive(Clone, PartialEq, Eq)]
 328 pub struct MemoryData<'tcx> {
 329     /// The Key to use for the next thread-local allocation.
 330     next_thread_local: TlsKey,
 331
 332     /// pthreads-style thread-local storage.
 333     thread_local: BTreeMap<TlsKey, TlsEntry<'tcx>>,
 334
 335     /// Memory regions that are locked by some function
 336     ///
 337     /// Only mutable (static mut, heap, stack) allocations have an entry in this map.
 338     /// The entry is created when allocating the memory and deleted after deallocation.
 339     locks: HashMap<AllocId, RangeMap<LockInfo<'tcx>>>,
 340
 341     statics: HashMap<GlobalId<'tcx>, AllocId>,
 342 }
 343
 344 impl<'tcx> MemoryData<'tcx> {
 345     fn new() -> Self {
 346         MemoryData {
 347             next_thread_local: 1, // start with 1 as we must not use 0 on Windows
 348             thread_local: BTreeMap::new(),
 349             locks: HashMap::new(),
 350             statics: HashMap::new(),
 351         }
 352     }
 353 }
 354
 355 impl<'tcx> Hash for MemoryData<'tcx> {
 356     fn hash<H: Hasher>(&self, state: &mut H) {
 357         let MemoryData {
 358             next_thread_local: _,
 359             thread_local,
 360             locks: _,
 361             statics: _,
 362         } = self;
 363
 364         thread_local.hash(state);
 365     }
 366 }
 367
 368 impl<'mir, 'tcx: 'mir> Machine<'mir, 'tcx> for Evaluator<'tcx> {
 369     type MemoryData = MemoryData<'tcx>;
 370     type MemoryKinds = memory::MemoryKind;
 371
 372     /// Returns Ok() when the function was handled, fail otherwise
 373     fn eval_fn_call<'a>(
 374         ecx: &mut EvalContext<'a, 'mir, 'tcx, Self>,
 375         instance: ty::Instance<'tcx>,
 376         destination: Option<(Place, mir::BasicBlock)>,
 377         args: &[ValTy<'tcx>],
 378         span: Span,
 379         sig: ty::FnSig<'tcx>,
 380     ) -> EvalResult<'tcx, bool> {
 381         ecx.eval_fn_call(instance, destination, args, span, sig)
 382     }
 383
 384     fn call_intrinsic<'a>(
 385         ecx: &mut rustc_mir::interpret::EvalContext<'a, 'mir, 'tcx, Self>,
 386         instance: ty::Instance<'tcx>,
 387         args: &[ValTy<'tcx>],
 388         dest: Place,
 389         dest_layout: TyLayout<'tcx>,
 390         target: mir::BasicBlock,
 391     ) -> EvalResult<'tcx> {
 392         ecx.call_intrinsic(instance, args, dest, dest_layout, target)
 393     }
 394
 395     fn try_ptr_op<'a>(
 396         ecx: &rustc_mir::interpret::EvalContext<'a, 'mir, 'tcx, Self>,
 397         bin_op: mir::BinOp,
 398         left: Scalar,
 399         left_ty: ty::Ty<'tcx>,
 400         right: Scalar,
 401         right_ty: ty::Ty<'tcx>,
 402     ) -> EvalResult<'tcx, Option<(Scalar, bool)>> {
 403         ecx.ptr_op(bin_op, left, left_ty, right, right_ty)
 404     }
 405
 406     fn mark_static_initialized<'a>(
 407         mem: &mut Memory<'a, 'mir, 'tcx, Self>,
 408         id: AllocId,
 409         _mutability: Mutability,
 410     ) -> EvalResult<'tcx, bool> {
 411         use memory::MemoryKind::*;
 412         match mem.get_alloc_kind(id) {
 413             // FIXME: This could be allowed, but not for env vars set during miri execution
 414             Some(MemoryKind::Machine(Env)) => err!(Unimplemented("statics can't refer to env vars".to_owned())),
 415             _ => Ok(false), // TODO: What does the bool mean?
 416         }
 417     }
 418
 419     fn init_static<'a>(
 420         ecx: &mut EvalContext<'a, 'mir, 'tcx, Self>,
 421         cid: GlobalId<'tcx>,
 422     ) -> EvalResult<'tcx, AllocId> {
 423         // Step 1: If the static has already been evaluated return the cached version
 424         if let Some(alloc_id) = ecx.memory.data.statics.get(&cid) {
 425             return Ok(*alloc_id);
 426         }
 427
 428         let tcx = ecx.tcx.tcx;
 429
 430         // Step 2: Load mir
 431         let mut mir = ecx.load_mir(cid.instance.def)?;
 432         if let Some(index) = cid.promoted {
 433             mir = &mir.promoted[index];
 434         }
 435         assert!(mir.arg_count == 0);
 436
 437         // Step 3: Allocate storage
 438         let layout = ecx.layout_of(mir.return_ty().subst(tcx, cid.instance.substs))?;
 439         assert!(!layout.is_unsized());
 440         let ptr = ecx.memory.allocate(
 441             layout.size,
 442             layout.align,
 443             MemoryKind::Stack,
 444         )?;
 445
 446         // Step 4: Cache allocation id for recursive statics
 447         assert!(ecx.memory.data.statics.insert(cid, ptr.alloc_id).is_none());
 448
 449         // Step 5: Push stackframe to evaluate static
 450         let cleanup = StackPopCleanup::None;
 451         ecx.push_stack_frame(
 452             cid.instance,
 453             mir.span,
 454             mir,
 455             Place::from_ptr(ptr, layout.align),
 456             cleanup,
 457         )?;
 458
 459         // Step 6: Step until static has been initialized
 460         let call_stackframe = ecx.stack().len();
 461         while ecx.step()? && ecx.stack().len() >= call_stackframe {
 462             if ecx.stack().len() == call_stackframe {
 463                 let frame = ecx.frame_mut();
 464                 let bb = &frame.mir.basic_blocks()[frame.block];
 465                 if bb.statements.len() == frame.stmt && !bb.is_cleanup {
 466                     if let ::rustc::mir::TerminatorKind::Return = bb.terminator().kind {
 467                         for (local, _local_decl) in mir.local_decls.iter_enumerated().skip(1) {
 468                             // Don't deallocate locals, because the return value might reference them
 469                             frame.storage_dead(local);
 470                         }
 471                     }
 472                 }
 473             }
 474         }
 475
 476         // TODO: Freeze immutable statics without copying them to the global static cache
 477
 478         // Step 7: Return the alloc
 479         Ok(ptr.alloc_id)
 480     }
 481
 482     fn box_alloc<'a>(
 483         ecx: &mut EvalContext<'a, 'mir, 'tcx, Self>,
 484         ty: ty::Ty<'tcx>,
 485         dest: Place,
 486     ) -> EvalResult<'tcx> {
 487         let layout = ecx.layout_of(ty)?;
 488
 489         // Call the `exchange_malloc` lang item
 490         let malloc = ecx.tcx.lang_items().exchange_malloc_fn().unwrap();
 491         let malloc = ty::Instance::mono(ecx.tcx.tcx, malloc);
 492         let malloc_mir = ecx.load_mir(malloc.def)?;
 493         ecx.push_stack_frame(
 494             malloc,
 495             malloc_mir.span,
 496             malloc_mir,
 497             dest,
 498             // Don't do anything when we are done.  The statement() function will increment
 499             // the old stack frame's stmt counter to the next statement, which means that when
 500             // exchange_malloc returns, we go on evaluating exactly where we want to be.
 501             StackPopCleanup::None,
 502         )?;
 503
 504         let mut args = ecx.frame().mir.args_iter();
 505         let usize = ecx.tcx.types.usize;
 506         let ptr_size = ecx.memory.pointer_size();
 507
 508         // First argument: size
 509         let dest = ecx.eval_place(&mir::Place::Local(args.next().unwrap()))?;
 510         ecx.write_value(
 511             ValTy {
 512                 value: Value::Scalar(Scalar::from_uint(match layout.size.bytes() {
 513                     0 => 1,
 514                     size => size,
 515                 }, ptr_size).into()),
 516                 ty: usize,
 517             },
 518             dest,
 519         )?;
 520
 521         // Second argument: align
 522         let dest = ecx.eval_place(&mir::Place::Local(args.next().unwrap()))?;
 523         ecx.write_value(
 524             ValTy {
 525                 value: Value::Scalar(Scalar::from_uint(layout.align.abi(), ptr_size).into()),
 526                 ty: usize,
 527             },
 528             dest,
 529         )?;
 530
 531         // No more arguments
 532         assert!(args.next().is_none(), "exchange_malloc lang item has more arguments than expected");
 533         Ok(())
 534     }
 535
 536     fn global_item_with_linkage<'a>(
 537         _ecx: &mut EvalContext<'a, 'mir, 'tcx, Self>,
 538         _instance: ty::Instance<'tcx>,
 539         _mutability: Mutability,
 540     ) -> EvalResult<'tcx> {
 541         panic!("remove this function from rustc");
 542     }
 543
 544     fn check_locks<'a>(
 545         mem: &Memory<'a, 'mir, 'tcx, Self>,
 546         ptr: Pointer,
 547         size: Size,
 548         access: AccessKind,
 549     ) -> EvalResult<'tcx> {
 550         mem.check_locks(ptr, size.bytes(), access)
 551     }
 552
 553     fn add_lock<'a>(
 554         mem: &mut Memory<'a, 'mir, 'tcx, Self>,
 555         id: AllocId,
 556     ) {
 557         mem.data.locks.insert(id, RangeMap::new());
 558     }
 559
 560     fn free_lock<'a>(
 561         mem: &mut Memory<'a, 'mir, 'tcx, Self>,
 562         id: AllocId,
 563         len: u64,
 564     ) -> EvalResult<'tcx> {
 565         mem.data.locks
 566             .remove(&id)
 567             .expect("allocation has no corresponding locks")
 568             .check(
 569                 Some(mem.cur_frame),
 570                 0,
 571                 len,
 572                 AccessKind::Read,
 573             )
 574             .map_err(|lock| {
 575                 EvalErrorKind::DeallocatedLockedMemory {
 576                     //ptr, FIXME
 577                     ptr: Pointer {
 578                         alloc_id: AllocId(0),
 579                         offset: Size::from_bytes(0),
 580                     },
 581                     lock: lock.active,
 582                 }.into()
 583             })
 584     }
 585
 586     fn end_region<'a>(
 587         ecx: &mut EvalContext<'a, 'mir, 'tcx, Self>,
 588         reg: Option<::rustc::middle::region::Scope>,
 589     ) -> EvalResult<'tcx> {
 590         ecx.end_region(reg)
 591     }
 592
 593     fn validation_op<'a>(
 594         _ecx: &mut EvalContext<'a, 'mir, 'tcx, Self>,
 595         _op: ::rustc::mir::ValidationOp,
 596         _operand: &::rustc::mir::ValidationOperand<'tcx, ::rustc::mir::Place<'tcx>>,
 597     ) -> EvalResult<'tcx> {
 598         // FIXME: prevent this from ICEing
 599         //ecx.validation_op(op, operand)
 600         Ok(())
 601     }
 602 }