1 //! Check the validity invariant of a given value, and tell the user
2 //! where in the value it got violated.
3 //! In const context, this goes even further and tries to approximate const safety.
4 //! That's useful because it means other passes (e.g. promotion) can rely on `const`s
8 use std::ops::RangeInclusive;
10 use syntax_pos::symbol::{sym, Symbol};
12 use rustc::ty::layout::{self, TyLayout, LayoutOf, VariantIdx};
14 use rustc_data_structures::fx::FxHashSet;
19 GlobalAlloc, InterpResult, CheckInAllocMsg,
20 Scalar, OpTy, Machine, InterpCx, ValueVisitor, MPlaceTy,
23 macro_rules! throw_validation_failure {
24 ($what:expr, $where:expr, $details:expr) => {{
25 let where_ = path_format(&$where);
26 let where_ = if where_.is_empty() {
29 format!(" at {}", where_)
31 throw_unsup!(ValidationFailure(format!(
32 "encountered {}{}, but expected {}",
33 $what, where_, $details,
36 ($what:expr, $where:expr) => {{
37 let where_ = path_format(&$where);
38 let where_ = if where_.is_empty() {
41 format!(" at {}", where_)
43 throw_unsup!(ValidationFailure(format!(
50 macro_rules! try_validation {
51 ($e:expr, $what:expr, $where:expr, $details:expr) => {{
54 Err(_) => throw_validation_failure!($what, $where, $details),
58 ($e:expr, $what:expr, $where:expr) => {{
61 Err(_) => throw_validation_failure!($what, $where),
66 /// We want to show a nice path to the invalid field for diagnostics,
67 /// but avoid string operations in the happy case where no error happens.
68 /// So we track a `Vec<PathElem>` where `PathElem` contains all the data we
69 /// need to later print something for the user.
70 #[derive(Copy, Clone, Debug)]
74 GeneratorState(VariantIdx),
83 /// State for tracking recursive validation of references
84 pub struct RefTracking<T, PATH = ()> {
85 pub seen: FxHashSet<T>,
86 pub todo: Vec<(T, PATH)>,
89 impl<T: Copy + Eq + Hash + std::fmt::Debug, PATH: Default> RefTracking<T, PATH> {
90 pub fn empty() -> Self {
92 seen: FxHashSet::default(),
96 pub fn new(op: T) -> Self {
97 let mut ref_tracking_for_consts = RefTracking {
98 seen: FxHashSet::default(),
99 todo: vec![(op, PATH::default())],
101 ref_tracking_for_consts.seen.insert(op);
102 ref_tracking_for_consts
105 pub fn track(&mut self, op: T, path: impl FnOnce() -> PATH) {
106 if self.seen.insert(op) {
107 trace!("Recursing below ptr {:#?}", op);
109 // Remember to come back to this later.
110 self.todo.push((op, path));
116 fn path_format(path: &Vec<PathElem>) -> String {
117 use self::PathElem::*;
119 let mut out = String::new();
120 for elem in path.iter() {
122 Field(name) => write!(out, ".{}", name),
123 Variant(name) => write!(out, ".<downcast-variant({})>", name),
124 GeneratorState(idx) => write!(out, ".<generator-state({})>", idx.index()),
125 ClosureVar(name) => write!(out, ".<closure-var({})>", name),
126 TupleElem(idx) => write!(out, ".{}", idx),
127 ArrayElem(idx) => write!(out, "[{}]", idx),
129 // This does not match Rust syntax, but it is more readable for long paths -- and
130 // some of the other items here also are not Rust syntax. Actually we can't
131 // even use the usual syntax because we are just showing the projections,
133 write!(out, ".<deref>"),
134 Tag => write!(out, ".<enum-tag>"),
135 DynDowncast => write!(out, ".<dyn-downcast>"),
141 // Test if a range that wraps at overflow contains `test`
142 fn wrapping_range_contains(r: &RangeInclusive<u128>, test: u128) -> bool {
143 let (lo, hi) = r.clone().into_inner();
146 (..=hi).contains(&test) || (lo..).contains(&test)
153 // Formats such that a sentence like "expected something {}" to mean
154 // "expected something <in the given range>" makes sense.
155 fn wrapping_range_format(r: &RangeInclusive<u128>, max_hi: u128) -> String {
156 let (lo, hi) = r.clone().into_inner();
157 debug_assert!(hi <= max_hi);
159 format!("less or equal to {}, or greater or equal to {}", hi, lo)
161 format!("equal to {}", lo)
163 debug_assert!(hi < max_hi, "should not be printing if the range covers everything");
164 format!("less or equal to {}", hi)
165 } else if hi == max_hi {
166 debug_assert!(lo > 0, "should not be printing if the range covers everything");
167 format!("greater or equal to {}", lo)
169 format!("in the range {:?}", r)
173 struct ValidityVisitor<'rt, 'mir, 'tcx, M: Machine<'mir, 'tcx>> {
174 /// The `path` may be pushed to, but the part that is present when a function
175 /// starts must not be changed! `visit_fields` and `visit_array` rely on
176 /// this stack discipline.
178 ref_tracking_for_consts: Option<&'rt mut RefTracking<
179 MPlaceTy<'tcx, M::PointerTag>,
182 ecx: &'rt InterpCx<'mir, 'tcx, M>,
185 impl<'rt, 'mir, 'tcx, M: Machine<'mir, 'tcx>> ValidityVisitor<'rt, 'mir, 'tcx, M> {
186 fn aggregate_field_path_elem(
188 layout: TyLayout<'tcx>,
191 match layout.ty.kind {
192 // generators and closures.
193 ty::Closure(def_id, _) | ty::Generator(def_id, _, _) => {
195 if def_id.is_local() {
196 let tables = self.ecx.tcx.typeck_tables_of(def_id);
197 if let Some(upvars) = tables.upvar_list.get(&def_id) {
198 // Sometimes the index is beyond the number of upvars (seen
200 if let Some((&var_hir_id, _)) = upvars.get_index(field) {
201 let node = self.ecx.tcx.hir().get(var_hir_id);
202 if let hir::Node::Binding(pat) = node {
203 if let hir::PatKind::Binding(_, _, ident, _) = pat.kind {
204 name = Some(ident.name);
211 PathElem::ClosureVar(name.unwrap_or_else(|| {
212 // Fall back to showing the field index.
218 ty::Tuple(_) => PathElem::TupleElem(field),
221 ty::Adt(def, ..) if def.is_enum() => {
222 // we might be projecting *to* a variant, or to a field *in*a variant.
223 match layout.variants {
224 layout::Variants::Single { index } =>
226 PathElem::Field(def.variants[index].fields[field].ident.name),
232 ty::Adt(def, _) => PathElem::Field(def.non_enum_variant().fields[field].ident.name),
235 ty::Array(..) | ty::Slice(..) => PathElem::ArrayElem(field),
238 ty::Dynamic(..) => PathElem::DynDowncast,
240 // nothing else has an aggregate layout
241 _ => bug!("aggregate_field_path_elem: got non-aggregate type {:?}", layout.ty),
247 new_op: OpTy<'tcx, M::PointerTag>,
249 ) -> InterpResult<'tcx> {
250 // Remember the old state
251 let path_len = self.path.len();
253 self.path.push(elem);
254 self.visit_value(new_op)?;
256 self.path.truncate(path_len);
260 fn check_wide_ptr_meta(
262 meta: Option<Scalar<M::PointerTag>>,
263 pointee: TyLayout<'tcx>,
264 ) -> InterpResult<'tcx> {
265 let tail = self.ecx.tcx.struct_tail_erasing_lifetimes(pointee.ty, self.ecx.param_env);
268 let vtable = meta.unwrap();
270 self.ecx.memory.check_ptr_access(
272 3*self.ecx.tcx.data_layout.pointer_size, // drop, size, align
273 self.ecx.tcx.data_layout.pointer_align.abi,
275 "dangling or unaligned vtable pointer in wide pointer or too small vtable",
278 try_validation!(self.ecx.read_drop_type_from_vtable(vtable),
279 "invalid drop fn in vtable", self.path);
280 try_validation!(self.ecx.read_size_and_align_from_vtable(vtable),
281 "invalid size or align in vtable", self.path);
282 // FIXME: More checks for the vtable.
284 ty::Slice(..) | ty::Str => {
285 let _len = try_validation!(meta.unwrap().to_usize(self.ecx),
286 "non-integer slice length in wide pointer", self.path);
287 // We do not check that `len * elem_size <= isize::MAX`:
288 // that is only required for references, and there it falls out of the
289 // "dereferencable" check performed by Stacked Borrows.
292 // Unsized, but not wide.
295 bug!("Unexpected unsized type tail: {:?}", tail),
302 impl<'rt, 'mir, 'tcx, M: Machine<'mir, 'tcx>> ValueVisitor<'mir, 'tcx, M>
303 for ValidityVisitor<'rt, 'mir, 'tcx, M>
305 type V = OpTy<'tcx, M::PointerTag>;
308 fn ecx(&self) -> &InterpCx<'mir, 'tcx, M> {
315 old_op: OpTy<'tcx, M::PointerTag>,
317 new_op: OpTy<'tcx, M::PointerTag>
318 ) -> InterpResult<'tcx> {
319 let elem = self.aggregate_field_path_elem(old_op.layout, field);
320 self.visit_elem(new_op, elem)
326 old_op: OpTy<'tcx, M::PointerTag>,
327 variant_id: VariantIdx,
328 new_op: OpTy<'tcx, M::PointerTag>
329 ) -> InterpResult<'tcx> {
330 let name = match old_op.layout.ty.kind {
331 ty::Adt(adt, _) => PathElem::Variant(adt.variants[variant_id].ident.name),
332 // Generators also have variants
333 ty::Generator(..) => PathElem::GeneratorState(variant_id),
334 _ => bug!("Unexpected type with variant: {:?}", old_op.layout.ty),
336 self.visit_elem(new_op, name)
340 fn visit_value(&mut self, op: OpTy<'tcx, M::PointerTag>) -> InterpResult<'tcx>
342 trace!("visit_value: {:?}, {:?}", *op, op.layout);
343 // Translate some possible errors to something nicer.
344 match self.walk_value(op) {
346 Err(err) => match err.kind {
347 err_ub!(InvalidDiscriminant(val)) =>
348 throw_validation_failure!(
349 val, self.path, "a valid enum discriminant"
351 err_unsup!(ReadPointerAsBytes) =>
352 throw_validation_failure!(
353 "a pointer", self.path, "plain (non-pointer) bytes"
360 fn visit_primitive(&mut self, value: OpTy<'tcx, M::PointerTag>) -> InterpResult<'tcx>
362 let value = self.ecx.read_immediate(value)?;
363 // Go over all the primitive types
364 let ty = value.layout.ty;
367 let value = value.to_scalar_or_undef();
368 try_validation!(value.to_bool(),
369 value, self.path, "a boolean");
372 let value = value.to_scalar_or_undef();
373 try_validation!(value.to_char(),
374 value, self.path, "a valid unicode codepoint");
376 ty::Float(_) | ty::Int(_) | ty::Uint(_) => {
377 // NOTE: Keep this in sync with the array optimization for int/float
379 let size = value.layout.size;
380 let value = value.to_scalar_or_undef();
381 if self.ref_tracking_for_consts.is_some() {
382 // Integers/floats in CTFE: Must be scalar bits, pointers are dangerous
383 try_validation!(value.to_bits(size),
384 value, self.path, "initialized plain (non-pointer) bytes");
386 // At run-time, for now, we accept *anything* for these types, including
387 // undef. We should fix that, but let's start low.
391 // We are conservative with undef for integers, but try to
392 // actually enforce our current rules for raw pointers.
393 let place = try_validation!(self.ecx.ref_to_mplace(value),
394 "undefined pointer", self.path);
395 if place.layout.is_unsized() {
396 self.check_wide_ptr_meta(place.meta, place.layout)?;
399 _ if ty.is_box() || ty.is_region_ptr() => {
400 // Handle wide pointers.
401 // Check metadata early, for better diagnostics
402 let place = try_validation!(self.ecx.ref_to_mplace(value),
403 "undefined pointer", self.path);
404 if place.layout.is_unsized() {
405 self.check_wide_ptr_meta(place.meta, place.layout)?;
407 // Make sure this is dereferencable and all.
408 let (size, align) = self.ecx.size_and_align_of(place.meta, place.layout)?
409 // for the purpose of validity, consider foreign types to have
410 // alignment and size determined by the layout (size will be 0,
411 // alignment should take attributes into account).
412 .unwrap_or_else(|| (place.layout.size, place.layout.align.abi));
413 let ptr: Option<_> = match
414 self.ecx.memory.check_ptr_access_align(
418 CheckInAllocMsg::InboundsTest,
424 "{:?} did not pass access check for size {:?}, align {:?}",
425 place.ptr, size, align
428 err_unsup!(InvalidNullPointerUsage) =>
429 throw_validation_failure!("NULL reference", self.path),
430 err_unsup!(AlignmentCheckFailed { required, has }) =>
431 throw_validation_failure!(format!("unaligned reference \
432 (required {} byte alignment but found {})",
433 required.bytes(), has.bytes()), self.path),
434 err_unsup!(ReadBytesAsPointer) =>
435 throw_validation_failure!(
436 "dangling reference (created from integer)",
440 throw_validation_failure!(
441 "dangling reference (not entirely in bounds)",
447 // Recursive checking
448 if let Some(ref mut ref_tracking) = self.ref_tracking_for_consts {
449 if let Some(ptr) = ptr { // not a ZST
450 // Skip validation entirely for some external statics
451 let alloc_kind = self.ecx.tcx.alloc_map.lock().get(ptr.alloc_id);
452 if let Some(GlobalAlloc::Static(did)) = alloc_kind {
453 // `extern static` cannot be validated as they have no body.
454 // FIXME: Statics from other crates are also skipped.
455 // They might be checked at a different type, but for now we
456 // want to avoid recursing too deeply. This is not sound!
457 if !did.is_local() || self.ecx.tcx.is_foreign_item(did) {
462 // Proceed recursively even for ZST, no reason to skip them!
463 // `!` is a ZST and we want to validate it.
464 // Normalize before handing `place` to tracking because that will
465 // check for duplicates.
466 let place = if size.bytes() > 0 {
467 self.ecx.force_mplace_ptr(place)
468 .expect("we already bounds-checked")
472 let path = &self.path;
473 ref_tracking.track(place, || {
474 // We need to clone the path anyway, make sure it gets created
475 // with enough space for the additional `Deref`.
476 let mut new_path = Vec::with_capacity(path.len() + 1);
477 new_path.clone_from(path);
478 new_path.push(PathElem::Deref);
484 let value = value.to_scalar_or_undef();
485 let _fn = try_validation!(
486 value.not_undef().and_then(|ptr| self.ecx.memory.get_fn(ptr)),
487 value, self.path, "a function pointer"
489 // FIXME: Check if the signature matches
491 // This should be all the primitive types
492 _ => bug!("Unexpected primitive type {}", value.layout.ty)
497 fn visit_uninhabited(&mut self) -> InterpResult<'tcx>
499 throw_validation_failure!("a value of an uninhabited type", self.path)
504 op: OpTy<'tcx, M::PointerTag>,
505 layout: &layout::Scalar,
506 ) -> InterpResult<'tcx> {
507 let value = self.ecx.read_scalar(op)?;
508 // Determine the allowed range
509 let (lo, hi) = layout.valid_range.clone().into_inner();
510 // `max_hi` is as big as the size fits
511 let max_hi = u128::max_value() >> (128 - op.layout.size.bits());
512 assert!(hi <= max_hi);
513 // We could also write `(hi + 1) % (max_hi + 1) == lo` but `max_hi + 1` overflows for `u128`
514 if (lo == 0 && hi == max_hi) || (hi + 1 == lo) {
518 // At least one value is excluded. Get the bits.
519 let value = try_validation!(value.not_undef(),
524 wrapping_range_format(&layout.valid_range, max_hi),
527 let bits = match value.to_bits_or_ptr(op.layout.size, self.ecx) {
529 if lo == 1 && hi == max_hi {
530 // Only NULL is the niche. So make sure the ptr is NOT NULL.
531 if self.ecx.memory.ptr_may_be_null(ptr) {
532 throw_validation_failure!(
533 "a potentially NULL pointer",
536 "something that cannot possibly fail to be {}",
537 wrapping_range_format(&layout.valid_range, max_hi)
543 // Conservatively, we reject, because the pointer *could* have a bad
545 throw_validation_failure!(
549 "something that cannot possibly fail to be {}",
550 wrapping_range_format(&layout.valid_range, max_hi)
558 // Now compare. This is slightly subtle because this is a special "wrap-around" range.
559 if wrapping_range_contains(&layout.valid_range, bits) {
562 throw_validation_failure!(
565 format!("something {}", wrapping_range_format(&layout.valid_range, max_hi))
572 op: OpTy<'tcx, M::PointerTag>,
573 fields: impl Iterator<Item=InterpResult<'tcx, Self::V>>,
574 ) -> InterpResult<'tcx> {
575 match op.layout.ty.kind {
577 let mplace = op.assert_mem_place(); // strings are never immediate
578 try_validation!(self.ecx.read_str(mplace),
579 "uninitialized or non-UTF-8 data in str", self.path);
581 ty::Array(tys, ..) | ty::Slice(tys) if {
582 // This optimization applies only for integer and floating point types
583 // (i.e., types that can hold arbitrary bytes).
585 ty::Int(..) | ty::Uint(..) | ty::Float(..) => true,
589 // bailing out for zsts is ok, since the array element type can only be int/float
590 if op.layout.is_zst() {
593 // non-ZST array cannot be immediate, slices are never immediate
594 let mplace = op.assert_mem_place();
595 // This is the length of the array/slice.
596 let len = mplace.len(self.ecx)?;
597 // zero length slices have nothing to be checked
601 // This is the element type size.
602 let ty_size = self.ecx.layout_of(tys)?.size;
603 // This is the size in bytes of the whole array.
604 let size = ty_size * len;
605 // Size is not 0, get a pointer.
606 let ptr = self.ecx.force_ptr(mplace.ptr)?;
608 // NOTE: Keep this in sync with the handling of integer and float
609 // types above, in `visit_primitive`.
610 // In run-time mode, we accept pointers in here. This is actually more
611 // permissive than a per-element check would be, e.g., we accept
612 // an &[u8] that contains a pointer even though bytewise checking would
613 // reject it. However, that's good: We don't inherently want
614 // to reject those pointers, we just do not have the machinery to
615 // talk about parts of a pointer.
616 // We also accept undef, for consistency with the slow path.
617 match self.ecx.memory.get(ptr.alloc_id)?.check_bytes(
621 /*allow_ptr_and_undef*/ self.ref_tracking_for_consts.is_none(),
623 // In the happy case, we needn't check anything else.
625 // Some error happened, try to provide a more detailed description.
627 // For some errors we might be able to provide extra information
629 err_unsup!(ReadUndefBytes(offset)) => {
630 // Some byte was undefined, determine which
631 // element that byte belongs to so we can
633 let i = (offset.bytes() / ty_size.bytes()) as usize;
634 self.path.push(PathElem::ArrayElem(i));
636 throw_validation_failure!("undefined bytes", self.path)
638 // Other errors shouldn't be possible
639 _ => return Err(err),
645 self.walk_aggregate(op, fields)? // default handler
652 impl<'mir, 'tcx, M: Machine<'mir, 'tcx>> InterpCx<'mir, 'tcx, M> {
653 /// This function checks the data at `op`. `op` is assumed to cover valid memory if it
654 /// is an indirect operand.
655 /// It will error if the bits at the destination do not match the ones described by the layout.
657 /// `ref_tracking_for_consts` can be `None` to avoid recursive checking below references.
658 /// This also toggles between "run-time" (no recursion) and "compile-time" (with recursion)
659 /// validation (e.g., pointer values are fine in integers at runtime) and various other const
660 /// specific validation checks.
661 pub fn validate_operand(
663 op: OpTy<'tcx, M::PointerTag>,
665 ref_tracking_for_consts: Option<&mut RefTracking<
666 MPlaceTy<'tcx, M::PointerTag>,
669 ) -> InterpResult<'tcx> {
670 trace!("validate_operand: {:?}, {:?}", *op, op.layout.ty);
672 // Construct a visitor
673 let mut visitor = ValidityVisitor {
675 ref_tracking_for_consts,
679 // Try to cast to ptr *once* instead of all the time.
680 let op = self.force_op_ptr(op).unwrap_or(op);
683 visitor.visit_value(op)