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