src/operator.rs

   1 use rustc::ty::{Ty, layout::{Size, LayoutOf}};
   2 use rustc::mir;
   3
   4 use crate::*;
   5
   6 pub trait EvalContextExt<'tcx> {
   7     fn pointer_inbounds(
   8         &self,
   9         ptr: Pointer<Tag>
  10     ) -> InterpResult<'tcx>;
  11
  12     fn ptr_op(
  13         &self,
  14         bin_op: mir::BinOp,
  15         left: ImmTy<'tcx, Tag>,
  16         right: ImmTy<'tcx, Tag>,
  17     ) -> InterpResult<'tcx, (Scalar<Tag>, bool)>;
  18
  19     fn ptr_int_arithmetic(
  20         &self,
  21         bin_op: mir::BinOp,
  22         left: Pointer<Tag>,
  23         right: u128,
  24         signed: bool,
  25     ) -> InterpResult<'tcx, (Scalar<Tag>, bool)>;
  26
  27     fn ptr_eq(
  28         &self,
  29         left: Scalar<Tag>,
  30         right: Scalar<Tag>,
  31     ) -> InterpResult<'tcx, bool>;
  32
  33     fn pointer_offset_inbounds(
  34         &self,
  35         ptr: Scalar<Tag>,
  36         pointee_ty: Ty<'tcx>,
  37         offset: i64,
  38     ) -> InterpResult<'tcx, Scalar<Tag>>;
  39 }
  40
  41 impl<'mir, 'tcx> EvalContextExt<'tcx> for super::MiriEvalContext<'mir, 'tcx> {
  42     /// Test if the pointer is in-bounds of a live allocation.
  43     #[inline]
  44     fn pointer_inbounds(&self, ptr: Pointer<Tag>) -> InterpResult<'tcx> {
  45         let (size, _align) = self.memory().get_size_and_align(ptr.alloc_id, AllocCheck::Live)?;
  46         ptr.check_in_alloc(size, CheckInAllocMsg::InboundsTest)
  47     }
  48
  49     fn ptr_op(
  50         &self,
  51         bin_op: mir::BinOp,
  52         left: ImmTy<'tcx, Tag>,
  53         right: ImmTy<'tcx, Tag>,
  54     ) -> InterpResult<'tcx, (Scalar<Tag>, bool)> {
  55         use rustc::mir::BinOp::*;
  56
  57         trace!("ptr_op: {:?} {:?} {:?}", *left, bin_op, *right);
  58
  59         // If intptrcast is enabled, treat everything of integer *type* at integer *value*.
  60         if self.memory().extra.rng.is_some() && left.layout.ty.is_integral() {
  61             // This is actually an integer operation, so dispatch back to the core engine.
  62             // TODO: Once intptrcast is the default, librustc_mir should never even call us
  63             // for integer types.
  64             assert!(right.layout.ty.is_integral());
  65             let l_bits = self.force_bits(left.imm.to_scalar()?, left.layout.size)?;
  66             let r_bits = self.force_bits(right.imm.to_scalar()?, right.layout.size)?;
  67
  68             let left = ImmTy::from_scalar(Scalar::from_uint(l_bits, left.layout.size), left.layout);
  69             let right = ImmTy::from_scalar(Scalar::from_uint(r_bits, left.layout.size), right.layout);
  70
  71             return self.binary_op(bin_op, left, right);
  72         }
  73
  74         // Operations that support fat pointers
  75         match bin_op {
  76             Eq | Ne => {
  77                 let eq = match (*left, *right) {
  78                     (Immediate::Scalar(left), Immediate::Scalar(right)) =>
  79                         self.ptr_eq(left.not_undef()?, right.not_undef()?)?,
  80                     (Immediate::ScalarPair(left1, left2), Immediate::ScalarPair(right1, right2)) =>
  81                         self.ptr_eq(left1.not_undef()?, right1.not_undef()?)? &&
  82                         self.ptr_eq(left2.not_undef()?, right2.not_undef()?)?,
  83                     _ => bug!("Type system should not allow comparing Scalar with ScalarPair"),
  84                 };
  85                 return Ok((Scalar::from_bool(if bin_op == Eq { eq } else { !eq }), false));
  86             }
  87             _ => {},
  88         }
  89
  90         // Now we expect no more fat pointers.
  91         let left_layout = left.layout;
  92         let left = left.to_scalar()?;
  93         let right_layout = right.layout;
  94         let right = right.to_scalar()?;
  95         debug_assert!(left.is_ptr() || right.is_ptr() || bin_op == Offset);
  96
  97         match bin_op {
  98             Offset => {
  99                 let pointee_ty = left_layout.ty
 100                     .builtin_deref(true)
 101                     .expect("Offset called on non-ptr type")
 102                     .ty;
 103                 let ptr = self.pointer_offset_inbounds(
 104                     left,
 105                     pointee_ty,
 106                     right.to_isize(self)?,
 107                 )?;
 108                 Ok((ptr, false))
 109             }
 110             // These need both to be pointer, and fail if they are not in the same location
 111             Lt | Le | Gt | Ge | Sub if left.is_ptr() && right.is_ptr() => {
 112                 let left = left.to_ptr().expect("we checked is_ptr");
 113                 let right = right.to_ptr().expect("we checked is_ptr");
 114                 if left.alloc_id == right.alloc_id {
 115                     let res = match bin_op {
 116                         Lt => left.offset < right.offset,
 117                         Le => left.offset <= right.offset,
 118                         Gt => left.offset > right.offset,
 119                         Ge => left.offset >= right.offset,
 120                         Sub => {
 121                             // subtract the offsets
 122                             let left_offset = Scalar::from_uint(left.offset.bytes(), self.memory().pointer_size());
 123                             let right_offset = Scalar::from_uint(right.offset.bytes(), self.memory().pointer_size());
 124                             let layout = self.layout_of(self.tcx.types.usize)?;
 125                             return self.binary_op(
 126                                 Sub,
 127                                 ImmTy::from_scalar(left_offset, layout),
 128                                 ImmTy::from_scalar(right_offset, layout),
 129                             )
 130                         }
 131                         _ => bug!("We already established it has to be one of these operators."),
 132                     };
 133                     Ok((Scalar::from_bool(res), false))
 134                 } else {
 135                     // Both are pointers, but from different allocations.
 136                     err!(InvalidPointerMath)
 137                 }
 138             }
 139             Gt | Ge if left.is_ptr() && right.is_bits() => {
 140                 // "ptr >[=] integer" can be tested if the integer is small enough.
 141                 let left = left.to_ptr().expect("we checked is_ptr");
 142                 let right = right.to_bits(self.memory().pointer_size()).expect("we checked is_bits");
 143                 let (_alloc_size, alloc_align) = self.memory()
 144                     .get_size_and_align(left.alloc_id, AllocCheck::MaybeDead)
 145                     .expect("alloc info with MaybeDead cannot fail");
 146                 let min_ptr_val = u128::from(alloc_align.bytes()) + u128::from(left.offset.bytes());
 147                 let result = match bin_op {
 148                     Gt => min_ptr_val > right,
 149                     Ge => min_ptr_val >= right,
 150                     _ => bug!(),
 151                 };
 152                 if result {
 153                     // Definitely true!
 154                     Ok((Scalar::from_bool(true), false))
 155                 } else {
 156                     // Sorry, can't tell.
 157                     err!(InvalidPointerMath)
 158                 }
 159             }
 160             // These work if the left operand is a pointer, and the right an integer
 161             Add | BitAnd | Sub | Rem if left.is_ptr() && right.is_bits() => {
 162                 // Cast to i128 is fine as we checked the kind to be ptr-sized
 163                 self.ptr_int_arithmetic(
 164                     bin_op,
 165                     left.to_ptr().expect("we checked is_ptr"),
 166                     right.to_bits(self.memory().pointer_size()).expect("we checked is_bits"),
 167                     right_layout.abi.is_signed(),
 168                 )
 169             }
 170             // Commutative operators also work if the integer is on the left
 171             Add | BitAnd if left.is_bits() && right.is_ptr() => {
 172                 // This is a commutative operation, just swap the operands
 173                 self.ptr_int_arithmetic(
 174                     bin_op,
 175                     right.to_ptr().expect("we checked is_ptr"),
 176                     left.to_bits(self.memory().pointer_size()).expect("we checked is_bits"),
 177                     left_layout.abi.is_signed(),
 178                 )
 179             }
 180             // Nothing else works
 181             _ => err!(InvalidPointerMath),
 182         }
 183     }
 184
 185     fn ptr_eq(
 186         &self,
 187         left: Scalar<Tag>,
 188         right: Scalar<Tag>,
 189     ) -> InterpResult<'tcx, bool> {
 190         let size = self.pointer_size();
 191         if self.memory().extra.rng.is_some() {
 192             // Just compare the integers.
 193             // TODO: Do we really want to *always* do that, even when comparing two live in-bounds pointers?
 194             let left = self.force_bits(left, size)?;
 195             let right = self.force_bits(right, size)?;
 196             return Ok(left == right);
 197         }
 198         Ok(match (left, right) {
 199             (Scalar::Raw { .. }, Scalar::Raw { .. }) =>
 200                 left.to_bits(size)? == right.to_bits(size)?,
 201             (Scalar::Ptr(left), Scalar::Ptr(right)) => {
 202                 // Comparison illegal if one of them is out-of-bounds, *unless* they
 203                 // are in the same allocation.
 204                 if left.alloc_id == right.alloc_id {
 205                     left.offset == right.offset
 206                 } else {
 207                     // Make sure both pointers are in-bounds.
 208                     // This accepts one-past-the end. Thus, there is still technically
 209                     // some non-determinism that we do not fully rule out when two
 210                     // allocations sit right next to each other. The C/C++ standards are
 211                     // somewhat fuzzy about this case, so pragmatically speaking I think
 212                     // for now this check is "good enough".
 213                     // FIXME: Once we support intptrcast, we could try to fix these holes.
 214                     // Dead allocations in miri cannot overlap with live allocations, but
 215                     // on read hardware this can easily happen. Thus for comparisons we require
 216                     // both pointers to be live.
 217                     if self.pointer_inbounds(left).is_ok() && self.pointer_inbounds(right).is_ok() {
 218                         // Two in-bounds (and hence live) pointers in different allocations are different.
 219                         false
 220                     } else {
 221                         return err!(InvalidPointerMath);
 222                     }
 223                 }
 224             }
 225             // Comparing ptr and integer.
 226             (Scalar::Ptr(ptr), Scalar::Raw { data, size }) |
 227             (Scalar::Raw { data, size }, Scalar::Ptr(ptr)) => {
 228                 assert_eq!(size as u64, self.pointer_size().bytes());
 229                 let bits = data as u64;
 230
 231                 // Case I: Comparing real pointers with "small" integers.
 232                 // Really we should only do this for NULL, but pragmatically speaking on non-bare-metal systems,
 233                 // an allocation will never be at the very bottom of the address space.
 234                 // Such comparisons can arise when comparing empty slices, which sometimes are "fake"
 235                 // integer pointers (okay because the slice is empty) and sometimes point into a
 236                 // real allocation.
 237                 // The most common source of such integer pointers is `NonNull::dangling()`, which
 238                 // equals the type's alignment. i128 might have an alignment of 16 bytes, but few types have
 239                 // alignment 32 or higher, hence the limit of 32.
 240                 // FIXME: Once we support intptrcast, we could try to fix these holes.
 241                 if bits < 32 {
 242                     // Test if the pointer can be different from NULL or not.
 243                     // We assume that pointers that are not NULL are also not "small".
 244                     if !self.memory().ptr_may_be_null(ptr) {
 245                         return Ok(false);
 246                     }
 247                 }
 248
 249                 let (alloc_size, alloc_align) = self.memory()
 250                     .get_size_and_align(ptr.alloc_id, AllocCheck::MaybeDead)
 251                     .expect("alloc info with MaybeDead cannot fail");
 252
 253                 // Case II: Alignment gives it away
 254                 if ptr.offset.bytes() % alloc_align.bytes() == 0 {
 255                     // The offset maintains the allocation alignment, so we know `base+offset`
 256                     // is aligned by `alloc_align`.
 257                     // FIXME: We could be even more general, e.g., offset 2 into a 4-aligned
 258                     // allocation cannot equal 3.
 259                     if bits % alloc_align.bytes() != 0 {
 260                         // The integer is *not* aligned. So they cannot be equal.
 261                         return Ok(false);
 262                     }
 263                 }
 264                 // Case III: The integer is too big, and the allocation goes on a bit
 265                 // without wrapping around the address space.
 266                 {
 267                     // Compute the highest address at which this allocation could live.
 268                     // Substract one more, because it must be possible to add the size
 269                     // to the base address without overflowing; that is, the very last address
 270                     // of the address space is never dereferencable (but it can be in-bounds, i.e.,
 271                     // one-past-the-end).
 272                     let max_base_addr =
 273                         ((1u128 << self.pointer_size().bits())
 274                          - u128::from(alloc_size.bytes())
 275                          - 1
 276                         ) as u64;
 277                     if let Some(max_addr) = max_base_addr.checked_add(ptr.offset.bytes()) {
 278                         if bits > max_addr {
 279                             // The integer is too big, this cannot possibly be equal.
 280                             return Ok(false)
 281                         }
 282                     }
 283                 }
 284
 285                 // None of the supported cases.
 286                 return err!(InvalidPointerMath);
 287             }
 288         })
 289     }
 290
 291     fn ptr_int_arithmetic(
 292         &self,
 293         bin_op: mir::BinOp,
 294         left: Pointer<Tag>,
 295         right: u128,
 296         signed: bool,
 297     ) -> InterpResult<'tcx, (Scalar<Tag>, bool)> {
 298         use rustc::mir::BinOp::*;
 299
 300         fn map_to_primval((res, over): (Pointer<Tag>, bool)) -> (Scalar<Tag>, bool) {
 301             (Scalar::Ptr(res), over)
 302         }
 303
 304         Ok(match bin_op {
 305             Sub =>
 306                 // The only way this can overflow is by underflowing, so signdeness of the right
 307                 // operands does not matter.
 308                 map_to_primval(left.overflowing_signed_offset(-(right as i128), self)),
 309             Add if signed =>
 310                 map_to_primval(left.overflowing_signed_offset(right as i128, self)),
 311             Add if !signed =>
 312                 map_to_primval(left.overflowing_offset(Size::from_bytes(right as u64), self)),
 313
 314             BitAnd if !signed => {
 315                 let ptr_base_align = self.memory().get_size_and_align(left.alloc_id, AllocCheck::MaybeDead)
 316                     .expect("alloc info with MaybeDead cannot fail")
 317                     .1.bytes();
 318                 let base_mask = {
 319                     // FIXME: use `interpret::truncate`, once that takes a `Size` instead of a `Layout`.
 320                     let shift = 128 - self.memory().pointer_size().bits();
 321                     let value = !(ptr_base_align as u128 - 1);
 322                     // Truncate (shift left to drop out leftover values, shift right to fill with zeroes).
 323                     (value << shift) >> shift
 324                 };
 325                 let ptr_size = self.memory().pointer_size();
 326                 trace!("ptr BitAnd, align {}, operand {:#010x}, base_mask {:#010x}",
 327                     ptr_base_align, right, base_mask);
 328                 if right & base_mask == base_mask {
 329                     // Case 1: the base address bits are all preserved, i.e., right is all-1 there.
 330                     let offset = (left.offset.bytes() as u128 & right) as u64;
 331                     (
 332                         Scalar::Ptr(Pointer::new_with_tag(
 333                             left.alloc_id,
 334                             Size::from_bytes(offset),
 335                             left.tag,
 336                         )),
 337                         false,
 338                     )
 339                 } else if right & base_mask == 0 {
 340                     // Case 2: the base address bits are all taken away, i.e., right is all-0 there.
 341                     let v = Scalar::from_uint((left.offset.bytes() as u128) & right, ptr_size);
 342                     (v, false)
 343                 } else {
 344                     return err!(ReadPointerAsBytes);
 345                 }
 346             }
 347
 348             Rem if !signed => {
 349                 // Doing modulo a divisor of the alignment is allowed.
 350                 // (Intuition: modulo a divisor leaks less information.)
 351                 let ptr_base_align = self.memory().get_size_and_align(left.alloc_id, AllocCheck::MaybeDead)
 352                     .expect("alloc info with MaybeDead cannot fail")
 353                     .1.bytes();
 354                 let right = right as u64;
 355                 let ptr_size = self.memory().pointer_size();
 356                 if right == 1 {
 357                     // Modulo 1 is always 0.
 358                     (Scalar::from_uint(0u32, ptr_size), false)
 359                 } else if ptr_base_align % right == 0 {
 360                     // The base address would be cancelled out by the modulo operation, so we can
 361                     // just take the modulo of the offset.
 362                     (
 363                         Scalar::from_uint((left.offset.bytes() % right) as u128, ptr_size),
 364                         false,
 365                     )
 366                 } else {
 367                     return err!(ReadPointerAsBytes);
 368                 }
 369             }
 370
 371             _ => {
 372                 let msg = format!(
 373                     "unimplemented binary op on pointer {:?}: {:?}, {:?} ({})",
 374                     bin_op,
 375                     left,
 376                     right,
 377                     if signed { "signed" } else { "unsigned" }
 378                 );
 379                 return err!(Unimplemented(msg));
 380             }
 381         })
 382     }
 383
 384     /// Raises an error if the offset moves the pointer outside of its allocation.
 385     /// We consider ZSTs their own huge allocation that doesn't overlap with anything (and nothing
 386     /// moves in there because the size is 0). We also consider the NULL pointer its own separate
 387     /// allocation, and all the remaining integers pointers their own allocation.
 388     fn pointer_offset_inbounds(
 389         &self,
 390         ptr: Scalar<Tag>,
 391         pointee_ty: Ty<'tcx>,
 392         offset: i64,
 393     ) -> InterpResult<'tcx, Scalar<Tag>> {
 394         // FIXME: assuming here that type size is less than `i64::max_value()`.
 395         let pointee_size = self.layout_of(pointee_ty)?.size.bytes() as i64;
 396         let offset = offset
 397             .checked_mul(pointee_size)
 398             .ok_or_else(|| InterpError::Overflow(mir::BinOp::Mul))?;
 399         // Now let's see what kind of pointer this is.
 400         let ptr = if offset == 0 {
 401             match ptr {
 402                 Scalar::Ptr(ptr) => ptr,
 403                 Scalar::Raw { .. } => {
 404                     // Offset 0 on an integer. We accept that, pretending there is
 405                     // a little zero-sized allocation here.
 406                     return Ok(ptr);
 407                 }
 408             }
 409         } else {
 410             // Offset > 0. We *require* a pointer.
 411             self.force_ptr(ptr)?
 412         };
 413         // Both old and new pointer must be in-bounds of a *live* allocation.
 414         // (Of the same allocation, but that part is trivial with our representation.)
 415         self.pointer_inbounds(ptr)?;
 416         let ptr = ptr.signed_offset(offset, self)?;
 417         self.pointer_inbounds(ptr)?;
 418         Ok(Scalar::Ptr(ptr))
 419     }
 420 }