]> git.lizzy.rs Git - rust.git/blob - src/librustc_mir/interpret/validity.rs
Rollup merge of #59462 - taiki-e:no-core, r=petrochenkov
[rust.git] / src / librustc_mir / interpret / validity.rs
1 use std::fmt::Write;
2 use std::hash::Hash;
3 use std::ops::RangeInclusive;
4
5 use syntax_pos::symbol::Symbol;
6 use rustc::ty::layout::{self, Size, Align, TyLayout, LayoutOf, VariantIdx};
7 use rustc::ty;
8 use rustc_data_structures::fx::FxHashSet;
9 use rustc::mir::interpret::{
10     Scalar, AllocKind, EvalResult, EvalErrorKind,
11 };
12
13 use super::{
14     OpTy, Machine, InterpretCx, ValueVisitor, MPlaceTy,
15 };
16
17 macro_rules! validation_failure {
18     ($what:expr, $where:expr, $details:expr) => {{
19         let where_ = path_format(&$where);
20         let where_ = if where_.is_empty() {
21             String::new()
22         } else {
23             format!(" at {}", where_)
24         };
25         err!(ValidationFailure(format!(
26             "encountered {}{}, but expected {}",
27             $what, where_, $details,
28         )))
29     }};
30     ($what:expr, $where:expr) => {{
31         let where_ = path_format(&$where);
32         let where_ = if where_.is_empty() {
33             String::new()
34         } else {
35             format!(" at {}", where_)
36         };
37         err!(ValidationFailure(format!(
38             "encountered {}{}",
39             $what, where_,
40         )))
41     }};
42 }
43
44 macro_rules! try_validation {
45     ($e:expr, $what:expr, $where:expr, $details:expr) => {{
46         match $e {
47             Ok(x) => x,
48             Err(_) => return validation_failure!($what, $where, $details),
49         }
50     }};
51
52     ($e:expr, $what:expr, $where:expr) => {{
53         match $e {
54             Ok(x) => x,
55             Err(_) => return validation_failure!($what, $where),
56         }
57     }}
58 }
59
60 /// We want to show a nice path to the invalid field for diagnostics,
61 /// but avoid string operations in the happy case where no error happens.
62 /// So we track a `Vec<PathElem>` where `PathElem` contains all the data we
63 /// need to later print something for the user.
64 #[derive(Copy, Clone, Debug)]
65 pub enum PathElem {
66     Field(Symbol),
67     Variant(Symbol),
68     ClosureVar(Symbol),
69     ArrayElem(usize),
70     TupleElem(usize),
71     Deref,
72     Tag,
73     DynDowncast,
74 }
75
76 /// State for tracking recursive validation of references
77 pub struct RefTracking<T> {
78     pub seen: FxHashSet<T>,
79     pub todo: Vec<(T, Vec<PathElem>)>,
80 }
81
82 impl<'tcx, T: Copy + Eq + Hash> RefTracking<T> {
83     pub fn new(op: T) -> Self {
84         let mut ref_tracking = RefTracking {
85             seen: FxHashSet::default(),
86             todo: vec![(op, Vec::new())],
87         };
88         ref_tracking.seen.insert(op);
89         ref_tracking
90     }
91 }
92
93 /// Format a path
94 fn path_format(path: &Vec<PathElem>) -> String {
95     use self::PathElem::*;
96
97     let mut out = String::new();
98     for elem in path.iter() {
99         match elem {
100             Field(name) => write!(out, ".{}", name),
101             Variant(name) => write!(out, ".<downcast-variant({})>", name),
102             ClosureVar(name) => write!(out, ".<closure-var({})>", name),
103             TupleElem(idx) => write!(out, ".{}", idx),
104             ArrayElem(idx) => write!(out, "[{}]", idx),
105             Deref =>
106                 // This does not match Rust syntax, but it is more readable for long paths -- and
107                 // some of the other items here also are not Rust syntax.  Actually we can't
108                 // even use the usual syntax because we are just showing the projections,
109                 // not the root.
110                 write!(out, ".<deref>"),
111             Tag => write!(out, ".<enum-tag>"),
112             DynDowncast => write!(out, ".<dyn-downcast>"),
113         }.unwrap()
114     }
115     out
116 }
117
118 // Test if a range that wraps at overflow contains `test`
119 fn wrapping_range_contains(r: &RangeInclusive<u128>, test: u128) -> bool {
120     let (lo, hi) = r.clone().into_inner();
121     if lo > hi {
122         // Wrapped
123         (..=hi).contains(&test) || (lo..).contains(&test)
124     } else {
125         // Normal
126         r.contains(&test)
127     }
128 }
129
130 // Formats such that a sentence like "expected something {}" to mean
131 // "expected something <in the given range>" makes sense.
132 fn wrapping_range_format(r: &RangeInclusive<u128>, max_hi: u128) -> String {
133     let (lo, hi) = r.clone().into_inner();
134     debug_assert!(hi <= max_hi);
135     if lo > hi {
136         format!("less or equal to {}, or greater or equal to {}", hi, lo)
137     } else {
138         if lo == 0 {
139             debug_assert!(hi < max_hi, "should not be printing if the range covers everything");
140             format!("less or equal to {}", hi)
141         } else if hi == max_hi {
142             format!("greater or equal to {}", lo)
143         } else {
144             format!("in the range {:?}", r)
145         }
146     }
147 }
148
149 struct ValidityVisitor<'rt, 'a: 'rt, 'mir: 'rt, 'tcx: 'a+'rt+'mir, M: Machine<'a, 'mir, 'tcx>+'rt> {
150     /// The `path` may be pushed to, but the part that is present when a function
151     /// starts must not be changed!  `visit_fields` and `visit_array` rely on
152     /// this stack discipline.
153     path: Vec<PathElem>,
154     ref_tracking: Option<&'rt mut RefTracking<MPlaceTy<'tcx, M::PointerTag>>>,
155     const_mode: bool,
156     ecx: &'rt InterpretCx<'a, 'mir, 'tcx, M>,
157 }
158
159 impl<'rt, 'a, 'mir, 'tcx, M: Machine<'a, 'mir, 'tcx>> ValidityVisitor<'rt, 'a, 'mir, 'tcx, M> {
160     fn aggregate_field_path_elem(
161         &mut self,
162         layout: TyLayout<'tcx>,
163         field: usize,
164     ) -> PathElem {
165         match layout.ty.sty {
166             // generators and closures.
167             ty::Closure(def_id, _) | ty::Generator(def_id, _, _) => {
168                 if let Some(upvar) = self.ecx.tcx.optimized_mir(def_id).upvar_decls.get(field) {
169                     PathElem::ClosureVar(upvar.debug_name)
170                 } else {
171                     // Sometimes the index is beyond the number of freevars (seen
172                     // for a generator).
173                     PathElem::ClosureVar(Symbol::intern(&field.to_string()))
174                 }
175             }
176
177             // tuples
178             ty::Tuple(_) => PathElem::TupleElem(field),
179
180             // enums
181             ty::Adt(def, ..) if def.is_enum() => {
182                 // we might be projecting *to* a variant, or to a field *in*a variant.
183                 match layout.variants {
184                     layout::Variants::Single { index } =>
185                         // Inside a variant
186                         PathElem::Field(def.variants[index].fields[field].ident.name),
187                     _ => bug!(),
188                 }
189             }
190
191             // other ADTs
192             ty::Adt(def, _) => PathElem::Field(def.non_enum_variant().fields[field].ident.name),
193
194             // arrays/slices
195             ty::Array(..) | ty::Slice(..) => PathElem::ArrayElem(field),
196
197             // dyn traits
198             ty::Dynamic(..) => PathElem::DynDowncast,
199
200             // nothing else has an aggregate layout
201             _ => bug!("aggregate_field_path_elem: got non-aggregate type {:?}", layout.ty),
202         }
203     }
204
205     fn visit_elem(
206         &mut self,
207         new_op: OpTy<'tcx, M::PointerTag>,
208         elem: PathElem,
209     ) -> EvalResult<'tcx> {
210         // Remember the old state
211         let path_len = self.path.len();
212         // Perform operation
213         self.path.push(elem);
214         self.visit_value(new_op)?;
215         // Undo changes
216         self.path.truncate(path_len);
217         Ok(())
218     }
219 }
220
221 impl<'rt, 'a, 'mir, 'tcx, M: Machine<'a, 'mir, 'tcx>>
222     ValueVisitor<'a, 'mir, 'tcx, M> for ValidityVisitor<'rt, 'a, 'mir, 'tcx, M>
223 {
224     type V = OpTy<'tcx, M::PointerTag>;
225
226     #[inline(always)]
227     fn ecx(&self) -> &InterpretCx<'a, 'mir, 'tcx, M> {
228         &self.ecx
229     }
230
231     #[inline]
232     fn visit_field(
233         &mut self,
234         old_op: OpTy<'tcx, M::PointerTag>,
235         field: usize,
236         new_op: OpTy<'tcx, M::PointerTag>
237     ) -> EvalResult<'tcx> {
238         let elem = self.aggregate_field_path_elem(old_op.layout, field);
239         self.visit_elem(new_op, elem)
240     }
241
242     #[inline]
243     fn visit_variant(
244         &mut self,
245         old_op: OpTy<'tcx, M::PointerTag>,
246         variant_id: VariantIdx,
247         new_op: OpTy<'tcx, M::PointerTag>
248     ) -> EvalResult<'tcx> {
249         let name = old_op.layout.ty.ty_adt_def().unwrap().variants[variant_id].ident.name;
250         self.visit_elem(new_op, PathElem::Variant(name))
251     }
252
253     #[inline]
254     fn visit_value(&mut self, op: OpTy<'tcx, M::PointerTag>) -> EvalResult<'tcx>
255     {
256         trace!("visit_value: {:?}, {:?}", *op, op.layout);
257         // Translate some possible errors to something nicer.
258         match self.walk_value(op) {
259             Ok(()) => Ok(()),
260             Err(err) => match err.kind {
261                 EvalErrorKind::InvalidDiscriminant(val) =>
262                     validation_failure!(
263                         val, self.path, "a valid enum discriminant"
264                     ),
265                 EvalErrorKind::ReadPointerAsBytes =>
266                     validation_failure!(
267                         "a pointer", self.path, "plain (non-pointer) bytes"
268                     ),
269                 _ => Err(err),
270             }
271         }
272     }
273
274     fn visit_primitive(&mut self, value: OpTy<'tcx, M::PointerTag>) -> EvalResult<'tcx>
275     {
276         let value = self.ecx.read_immediate(value)?;
277         // Go over all the primitive types
278         let ty = value.layout.ty;
279         match ty.sty {
280             ty::Bool => {
281                 let value = value.to_scalar_or_undef();
282                 try_validation!(value.to_bool(),
283                     value, self.path, "a boolean");
284             },
285             ty::Char => {
286                 let value = value.to_scalar_or_undef();
287                 try_validation!(value.to_char(),
288                     value, self.path, "a valid unicode codepoint");
289             },
290             ty::Float(_) | ty::Int(_) | ty::Uint(_) => {
291                 // NOTE: Keep this in sync with the array optimization for int/float
292                 // types below!
293                 let size = value.layout.size;
294                 let value = value.to_scalar_or_undef();
295                 if self.const_mode {
296                     // Integers/floats in CTFE: Must be scalar bits, pointers are dangerous
297                     try_validation!(value.to_bits(size),
298                         value, self.path, "initialized plain (non-pointer) bytes");
299                 } else {
300                     // At run-time, for now, we accept *anything* for these types, including
301                     // undef. We should fix that, but let's start low.
302                 }
303             }
304             ty::RawPtr(..) => {
305                 if self.const_mode {
306                     // Integers/floats in CTFE: For consistency with integers, we do not
307                     // accept undef.
308                     let _ptr = try_validation!(value.to_scalar_ptr(),
309                         "undefined address in raw pointer", self.path);
310                     let _meta = try_validation!(value.to_meta(),
311                         "uninitialized data in raw fat pointer metadata", self.path);
312                 } else {
313                     // Remain consistent with `usize`: Accept anything.
314                 }
315             }
316             _ if ty.is_box() || ty.is_region_ptr() => {
317                 // Handle fat pointers.
318                 // Check metadata early, for better diagnostics
319                 let ptr = try_validation!(value.to_scalar_ptr(),
320                     "undefined address in pointer", self.path);
321                 let meta = try_validation!(value.to_meta(),
322                     "uninitialized data in fat pointer metadata", self.path);
323                 let layout = self.ecx.layout_of(value.layout.ty.builtin_deref(true).unwrap().ty)?;
324                 if layout.is_unsized() {
325                     let tail = self.ecx.tcx.struct_tail(layout.ty);
326                     match tail.sty {
327                         ty::Dynamic(..) => {
328                             let vtable = try_validation!(meta.unwrap().to_ptr(),
329                                 "non-pointer vtable in fat pointer", self.path);
330                             try_validation!(self.ecx.read_drop_type_from_vtable(vtable),
331                                 "invalid drop fn in vtable", self.path);
332                             try_validation!(self.ecx.read_size_and_align_from_vtable(vtable),
333                                 "invalid size or align in vtable", self.path);
334                             // FIXME: More checks for the vtable.
335                         }
336                         ty::Slice(..) | ty::Str => {
337                             try_validation!(meta.unwrap().to_usize(self.ecx),
338                                 "non-integer slice length in fat pointer", self.path);
339                         }
340                         ty::Foreign(..) => {
341                             // Unsized, but not fat.
342                         }
343                         _ =>
344                             bug!("Unexpected unsized type tail: {:?}", tail),
345                     }
346                 }
347                 // Make sure this is non-NULL and aligned
348                 let (size, align) = self.ecx.size_and_align_of(meta, layout)?
349                     // for the purpose of validity, consider foreign types to have
350                     // alignment and size determined by the layout (size will be 0,
351                     // alignment should take attributes into account).
352                     .unwrap_or_else(|| (layout.size, layout.align.abi));
353                 match self.ecx.memory.check_align(ptr, align) {
354                     Ok(_) => {},
355                     Err(err) => {
356                         error!("{:?} is not aligned to {:?}", ptr, align);
357                         match err.kind {
358                             EvalErrorKind::InvalidNullPointerUsage =>
359                                 return validation_failure!("NULL reference", self.path),
360                             EvalErrorKind::AlignmentCheckFailed { required, has } =>
361                                 return validation_failure!(format!("unaligned reference \
362                                     (required {} byte alignment but found {})",
363                                     required.bytes(), has.bytes()), self.path),
364                             _ =>
365                                 return validation_failure!(
366                                     "dangling (out-of-bounds) reference (might be NULL at \
367                                         run-time)",
368                                     self.path
369                                 ),
370                         }
371                     }
372                 }
373                 // Recursive checking
374                 if let Some(ref mut ref_tracking) = self.ref_tracking {
375                     assert!(self.const_mode, "We should only do recursie checking in const mode");
376                     let place = self.ecx.ref_to_mplace(value)?;
377                     if size != Size::ZERO {
378                         // Non-ZST also have to be dereferencable
379                         let ptr = try_validation!(place.ptr.to_ptr(),
380                             "integer pointer in non-ZST reference", self.path);
381                         // Skip validation entirely for some external statics
382                         let alloc_kind = self.ecx.tcx.alloc_map.lock().get(ptr.alloc_id);
383                         if let Some(AllocKind::Static(did)) = alloc_kind {
384                             // `extern static` cannot be validated as they have no body.
385                             // FIXME: Statics from other crates are also skipped.
386                             // They might be checked at a different type, but for now we
387                             // want to avoid recursing too deeply.  This is not sound!
388                             if !did.is_local() || self.ecx.tcx.is_foreign_item(did) {
389                                 return Ok(());
390                             }
391                         }
392                         // Maintain the invariant that the place we are checking is
393                         // already verified to be in-bounds.
394                         try_validation!(
395                             self.ecx.memory
396                                 .get(ptr.alloc_id)?
397                                 .check_bounds(self.ecx, ptr, size),
398                             "dangling (not entirely in bounds) reference", self.path);
399                     }
400                     // Check if we have encountered this pointer+layout combination
401                     // before.  Proceed recursively even for integer pointers, no
402                     // reason to skip them! They are (recursively) valid for some ZST,
403                     // but not for others (e.g., `!` is a ZST).
404                     if ref_tracking.seen.insert(place) {
405                         trace!("Recursing below ptr {:#?}", *place);
406                         // We need to clone the path anyway, make sure it gets created
407                         // with enough space for the additional `Deref`.
408                         let mut new_path = Vec::with_capacity(self.path.len()+1);
409                         new_path.clone_from(&self.path);
410                         new_path.push(PathElem::Deref);
411                         // Remember to come back to this later.
412                         ref_tracking.todo.push((place, new_path));
413                     }
414                 }
415             }
416             ty::FnPtr(_sig) => {
417                 let value = value.to_scalar_or_undef();
418                 let ptr = try_validation!(value.to_ptr(),
419                     value, self.path, "a pointer");
420                 let _fn = try_validation!(self.ecx.memory.get_fn(ptr),
421                     value, self.path, "a function pointer");
422                 // FIXME: Check if the signature matches
423             }
424             // This should be all the primitive types
425             _ => bug!("Unexpected primitive type {}", value.layout.ty)
426         }
427         Ok(())
428     }
429
430     fn visit_uninhabited(&mut self) -> EvalResult<'tcx>
431     {
432         validation_failure!("a value of an uninhabited type", self.path)
433     }
434
435     fn visit_scalar(
436         &mut self,
437         op: OpTy<'tcx, M::PointerTag>,
438         layout: &layout::Scalar,
439     ) -> EvalResult<'tcx> {
440         let value = self.ecx.read_scalar(op)?;
441         // Determine the allowed range
442         let (lo, hi) = layout.valid_range.clone().into_inner();
443         // `max_hi` is as big as the size fits
444         let max_hi = u128::max_value() >> (128 - op.layout.size.bits());
445         assert!(hi <= max_hi);
446         // We could also write `(hi + 1) % (max_hi + 1) == lo` but `max_hi + 1` overflows for `u128`
447         if (lo == 0 && hi == max_hi) || (hi + 1 == lo) {
448             // Nothing to check
449             return Ok(());
450         }
451         // At least one value is excluded. Get the bits.
452         let value = try_validation!(value.not_undef(),
453             value,
454             self.path,
455             format!(
456                 "something {}",
457                 wrapping_range_format(&layout.valid_range, max_hi),
458             )
459         );
460         let bits = match value {
461             Scalar::Ptr(ptr) => {
462                 if lo == 1 && hi == max_hi {
463                     // only NULL is not allowed.
464                     // We can call `check_align` to check non-NULL-ness, but have to also look
465                     // for function pointers.
466                     let non_null =
467                         self.ecx.memory.check_align(
468                             Scalar::Ptr(ptr), Align::from_bytes(1).unwrap()
469                         ).is_ok() ||
470                         self.ecx.memory.get_fn(ptr).is_ok();
471                     if !non_null {
472                         // could be NULL
473                         return validation_failure!("a potentially NULL pointer", self.path);
474                     }
475                     return Ok(());
476                 } else {
477                     // Conservatively, we reject, because the pointer *could* have this
478                     // value.
479                     return validation_failure!(
480                         "a pointer",
481                         self.path,
482                         format!(
483                             "something that cannot possibly fail to be {}",
484                             wrapping_range_format(&layout.valid_range, max_hi)
485                         )
486                     );
487                 }
488             }
489             Scalar::Bits { bits, size } => {
490                 assert_eq!(size as u64, op.layout.size.bytes());
491                 bits
492             }
493         };
494         // Now compare. This is slightly subtle because this is a special "wrap-around" range.
495         if wrapping_range_contains(&layout.valid_range, bits) {
496             Ok(())
497         } else {
498             validation_failure!(
499                 bits,
500                 self.path,
501                 format!("something {}", wrapping_range_format(&layout.valid_range, max_hi))
502             )
503         }
504     }
505
506     fn visit_aggregate(
507         &mut self,
508         op: OpTy<'tcx, M::PointerTag>,
509         fields: impl Iterator<Item=EvalResult<'tcx, Self::V>>,
510     ) -> EvalResult<'tcx> {
511         match op.layout.ty.sty {
512             ty::Str => {
513                 let mplace = op.to_mem_place(); // strings are never immediate
514                 try_validation!(self.ecx.read_str(mplace),
515                     "uninitialized or non-UTF-8 data in str", self.path);
516             }
517             ty::Array(tys, ..) | ty::Slice(tys) if {
518                 // This optimization applies only for integer and floating point types
519                 // (i.e., types that can hold arbitrary bytes).
520                 match tys.sty {
521                     ty::Int(..) | ty::Uint(..) | ty::Float(..) => true,
522                     _ => false,
523                 }
524             } => {
525                 // bailing out for zsts is ok, since the array element type can only be int/float
526                 if op.layout.is_zst() {
527                     return Ok(());
528                 }
529                 // non-ZST array cannot be immediate, slices are never immediate
530                 let mplace = op.to_mem_place();
531                 // This is the length of the array/slice.
532                 let len = mplace.len(self.ecx)?;
533                 // zero length slices have nothing to be checked
534                 if len == 0 {
535                     return Ok(());
536                 }
537                 // This is the element type size.
538                 let ty_size = self.ecx.layout_of(tys)?.size;
539                 // This is the size in bytes of the whole array.
540                 let size = ty_size * len;
541
542                 let ptr = mplace.ptr.to_ptr()?;
543
544                 // NOTE: Keep this in sync with the handling of integer and float
545                 // types above, in `visit_primitive`.
546                 // In run-time mode, we accept pointers in here.  This is actually more
547                 // permissive than a per-element check would be, e.g., we accept
548                 // an &[u8] that contains a pointer even though bytewise checking would
549                 // reject it.  However, that's good: We don't inherently want
550                 // to reject those pointers, we just do not have the machinery to
551                 // talk about parts of a pointer.
552                 // We also accept undef, for consistency with the type-based checks.
553                 match self.ecx.memory.get(ptr.alloc_id)?.check_bytes(
554                     self.ecx,
555                     ptr,
556                     size,
557                     /*allow_ptr_and_undef*/!self.const_mode,
558                 ) {
559                     // In the happy case, we needn't check anything else.
560                     Ok(()) => {},
561                     // Some error happened, try to provide a more detailed description.
562                     Err(err) => {
563                         // For some errors we might be able to provide extra information
564                         match err.kind {
565                             EvalErrorKind::ReadUndefBytes(offset) => {
566                                 // Some byte was undefined, determine which
567                                 // element that byte belongs to so we can
568                                 // provide an index.
569                                 let i = (offset.bytes() / ty_size.bytes()) as usize;
570                                 self.path.push(PathElem::ArrayElem(i));
571
572                                 return validation_failure!(
573                                     "undefined bytes", self.path
574                                 )
575                             },
576                             // Other errors shouldn't be possible
577                             _ => return Err(err),
578                         }
579                     }
580                 }
581             }
582             _ => {
583                 self.walk_aggregate(op, fields)? // default handler
584             }
585         }
586         Ok(())
587     }
588 }
589
590 impl<'a, 'mir, 'tcx, M: Machine<'a, 'mir, 'tcx>> InterpretCx<'a, 'mir, 'tcx, M> {
591     /// This function checks the data at `op`. `op` is assumed to cover valid memory if it
592     /// is an indirect operand.
593     /// It will error if the bits at the destination do not match the ones described by the layout.
594     ///
595     /// `ref_tracking` can be None to avoid recursive checking below references.
596     /// This also toggles between "run-time" (no recursion) and "compile-time" (with recursion)
597     /// validation (e.g., pointer values are fine in integers at runtime).
598     pub fn validate_operand(
599         &self,
600         op: OpTy<'tcx, M::PointerTag>,
601         path: Vec<PathElem>,
602         ref_tracking: Option<&mut RefTracking<MPlaceTy<'tcx, M::PointerTag>>>,
603         const_mode: bool,
604     ) -> EvalResult<'tcx> {
605         trace!("validate_operand: {:?}, {:?}", *op, op.layout.ty);
606
607         // Construct a visitor
608         let mut visitor = ValidityVisitor {
609             path,
610             ref_tracking,
611             const_mode,
612             ecx: self,
613         };
614
615         // Run it
616         visitor.visit_value(op)
617     }
618 }