1 use std::cell::RefCell;
2 use std::collections::HashSet;
5 use std::num::NonZeroU64;
7 use rustc::ty::{self, layout::Size};
8 use rustc::hir::{MutMutable, MutImmutable};
9 use rustc::mir::RetagKind;
12 EvalResult, InterpError, MiriEvalContext, HelpersEvalContextExt, Evaluator, MutValueVisitor,
13 MemoryKind, MiriMemoryKind, RangeMap, Allocation, AllocationExtra,
14 Pointer, Immediate, ImmTy, PlaceTy, MPlaceTy,
17 pub type PtrId = NonZeroU64;
18 pub type CallId = NonZeroU64;
20 /// Tracking pointer provenance
21 #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
27 impl fmt::Display for Tag {
28 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
30 Tag::Tagged(id) => write!(f, "{}", id),
31 Tag::Untagged => write!(f, "<untagged>"),
36 /// Indicates which permission is granted (by this item to some pointers)
37 #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
39 /// Grants unique mutable access.
41 /// Grants shared mutable access.
43 /// Greants shared read-only access.
47 /// An item in the per-location borrow stack.
48 #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
50 /// The permission this item grants.
52 /// The pointers the permission is granted to.
54 /// An optional protector, ensuring the item cannot get popped until `CallId` is over.
55 protector: Option<CallId>,
58 impl fmt::Display for Item {
59 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
60 write!(f, "[{:?} for {}", self.perm, self.tag)?;
61 if let Some(call) = self.protector {
62 write!(f, " (call {})", call)?;
69 /// Extra per-location state.
70 #[derive(Clone, Debug, PartialEq, Eq)]
72 /// Used *mostly* as a stack; never empty.
73 /// We sometimes push into the middle but never remove from the middle.
74 /// The same tag may occur multiple times, e.g. from a two-phase borrow.
76 /// * Above a `SharedReadOnly` there can only be more `SharedReadOnly`.
81 /// Extra per-allocation state.
82 #[derive(Clone, Debug)]
84 // Even reading memory can have effects on the stack, so we need a `RefCell` here.
85 stacks: RefCell<RangeMap<Stack>>,
86 // Pointer to global state
90 /// Extra global state, available to the memory access hooks.
92 pub struct GlobalState {
95 active_calls: HashSet<CallId>,
97 pub type MemoryState = Rc<RefCell<GlobalState>>;
99 /// Indicates which kind of access is being performed.
100 #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
101 pub enum AccessKind {
106 impl fmt::Display for AccessKind {
107 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
109 AccessKind::Read => write!(f, "read"),
110 AccessKind::Write => write!(f, "write"),
115 /// Indicates which kind of reference is being created.
116 /// Used by high-level `reborrow` to compute which permissions to grant to the
118 #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
120 /// `&mut` and `Box`.
122 /// `&` with or without interior mutability.
124 /// `*mut`/`*const` (raw pointers).
125 Raw { mutable: bool },
128 impl fmt::Display for RefKind {
129 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
131 RefKind::Unique => write!(f, "unique"),
132 RefKind::Shared => write!(f, "shared"),
133 RefKind::Raw { mutable: true } => write!(f, "raw (mutable)"),
134 RefKind::Raw { mutable: false } => write!(f, "raw (constant)"),
139 /// Utilities for initialization and ID generation
140 impl Default for GlobalState {
141 fn default() -> Self {
143 next_ptr_id: NonZeroU64::new(1).unwrap(),
144 next_call_id: NonZeroU64::new(1).unwrap(),
145 active_calls: HashSet::default(),
151 pub fn new_ptr(&mut self) -> PtrId {
152 let id = self.next_ptr_id;
153 self.next_ptr_id = NonZeroU64::new(id.get() + 1).unwrap();
157 pub fn new_call(&mut self) -> CallId {
158 let id = self.next_call_id;
159 trace!("new_call: Assigning ID {}", id);
160 self.active_calls.insert(id);
161 self.next_call_id = NonZeroU64::new(id.get() + 1).unwrap();
165 pub fn end_call(&mut self, id: CallId) {
166 assert!(self.active_calls.remove(&id));
169 fn is_active(&self, id: CallId) -> bool {
170 self.active_calls.contains(&id)
174 // # Stacked Borrows Core Begin
176 /// We need to make at least the following things true:
178 /// U1: After creating a `Uniq`, it is at the top.
179 /// U2: If the top is `Uniq`, accesses must be through that `Uniq` or remove it it.
180 /// U3: If an access happens with a `Uniq`, it requires the `Uniq` to be in the stack.
182 /// F1: After creating a `&`, the parts outside `UnsafeCell` have our `SharedReadOnly` on top.
183 /// F2: If a write access happens, it pops the `SharedReadOnly`. This has three pieces:
184 /// F2a: If a write happens granted by an item below our `SharedReadOnly`, the `SharedReadOnly`
186 /// F2b: No `SharedReadWrite` or `Unique` will ever be added on top of our `SharedReadOnly`.
187 /// F3: If an access happens with an `&` outside `UnsafeCell`,
188 /// it requires the `SharedReadOnly` to still be in the stack.
190 impl Default for Tag {
192 fn default() -> Tag {
197 /// Core relations on `Permission` define which accesses are allowed:
198 /// On every access, we try to find a *granting* item, and then we remove all
199 /// *incompatible* items above it.
201 /// This defines for a given permission, whether it permits the given kind of access.
202 fn grants(self, access: AccessKind) -> bool {
203 match (self, access) {
204 // Unique and SharedReadWrite allow any kind of access.
205 (Permission::Unique, _) |
206 (Permission::SharedReadWrite, _) =>
208 // SharedReadOnly only permits read access.
209 (Permission::SharedReadOnly, AccessKind::Read) =>
211 (Permission::SharedReadOnly, AccessKind::Write) =>
216 /// This defines for a given permission, which other permissions it can tolerate "above" itself
217 /// when it is written to.
218 /// If true, then `other` is allowed to remain on top of `self` when a write access happens.
219 fn write_compatible_with(self, other: Permission) -> bool {
220 // Only writes to SharedRW can tolerate any other items above them, and they only
221 // tolerate other SharedRW. So, basically, searching the first write-incompatible item above X treats
222 // consecutive SharedRW as one "group", and skips to the first item outside X's group.
223 return self == Permission::SharedReadWrite && other == Permission::SharedReadWrite;
227 /// Core per-location operations: access, dealloc, reborrow.
229 /// Find the item granting the given kind of access to the given tag, and return where
230 /// *the first write-incompatible item above it* is on the stack.
231 fn check_granting(&self, access: AccessKind, tag: Tag) -> Option<usize> {
232 let (perm, idx) = self.borrows.iter()
233 .enumerate() // we also need to know *where* in the stack
234 .rev() // search top-to-bottom
235 // Return permission of first item that grants access.
236 // We require a permission with the right tag, ensuring U3 and F3.
237 .find_map(|(idx, item)|
238 if item.perm.grants(access) && tag == item.tag {
239 Some((item.perm, idx))
245 let mut first_incompatible_idx = idx+1;
246 while let Some(item) = self.borrows.get(first_incompatible_idx) {
247 if perm.write_compatible_with(item.perm) {
248 // Keep this, check next.
249 first_incompatible_idx += 1;
255 return Some(first_incompatible_idx);
258 /// Test if a memory `access` using pointer tagged `tag` is granted.
259 /// If yes, return the index of the item that granted it.
264 global: &GlobalState,
265 ) -> EvalResult<'tcx> {
266 // Two main steps: Find granting item, remove incompatible items above.
268 // Step 1: Find granting item.
269 let first_incompatible_idx = self.check_granting(access, tag)
270 .ok_or_else(|| InterpError::MachineError(format!(
271 "no item granting {} access to tag {} found in borrow stack",
275 // Step 2: Remove incompatible items above them. Make sure we do not remove protected
276 // items. Behavior differs for reads and writes.
278 // For writes, this is a simple stack, where everything starting with the first incompatible item
279 // gets removed. This makes sure read-only and unique pointers become invalid on write accesses
280 // (ensures F2a, and ensures U2 for write accesses).
282 // For reads, however, we just filter away the Unique items, which is sufficient to ensure U2 for read
283 // accesses. The reason is that in `let raw = &mut *x as *mut _; let _val = *x;`, the second statement
284 // would pop the `Unique` from the reborrow of the first statement, and subsequently also pop the
285 // `SharedReadWrite` for `raw`.
286 // This pattern occurs a lot in the standard library: create a raw pointer, then also create a shared
287 // reference and use that.
289 // Implemented with indices because there does not seem to be a nice iterator and range-based
291 let mut cur = first_incompatible_idx;
292 while let Some(item) = self.borrows.get(cur) {
293 // If this is a read, only remove Unique items!
294 if access == AccessKind::Read && item.perm != Permission::Unique {
295 // Keep this, check next.
298 // Aha! This is a bad one, remove it, and make sure it is not protected.
299 let item = self.borrows.remove(cur);
300 if let Some(call) = item.protector {
301 if global.is_active(call) {
302 return err!(MachineError(format!(
303 "not granting {} access to tag {} because incompatible item {} is protected",
308 trace!("access: removing item {}", item);
317 /// Deallocate a location: Like a write access, but also there must be no
318 /// active protectors at all.
322 global: &GlobalState,
323 ) -> EvalResult<'tcx> {
324 // Step 1: Find granting item.
325 self.check_granting(AccessKind::Write, tag)
326 .ok_or_else(|| InterpError::MachineError(format!(
327 "no item granting write access for deallocation to tag {} found in borrow stack",
331 // We must make sure there are no protected items remaining on the stack.
332 // Also clear the stack, no more accesses are possible.
333 for item in self.borrows.drain(..) {
334 if let Some(call) = item.protector {
335 if global.is_active(call) {
336 return err!(MachineError(format!(
337 "deallocating with active protector ({})", call
346 /// `reborrow` helper function: test that the stack invariants are still maintained.
347 fn test_invariants(&self) {
348 let mut saw_shared_read_only = false;
349 for item in self.borrows.iter() {
351 Permission::SharedReadOnly => {
352 saw_shared_read_only = true;
354 // Otherwise, if we saw one before, that's a bug.
355 perm if saw_shared_read_only => {
356 bug!("Found {:?} on top of a SharedReadOnly!", perm);
363 /// Derived a new pointer from one with the given tag.
364 /// `weak` controls whether this operation is weak or strong: weak granting does not act as
365 /// an access, and they add the new item directly on top of the one it is derived
366 /// from instead of all the way at the top of the stack.
372 global: &GlobalState,
373 ) -> EvalResult<'tcx> {
374 // Figure out which access `perm` corresponds to.
375 let access = if new.perm.grants(AccessKind::Write) {
380 // Now we figure out which item grants our parent (`derived_from`) this kind of access.
381 // We use that to determine where to put the new item.
382 let first_incompatible_idx = self.check_granting(access, derived_from)
383 .ok_or_else(|| InterpError::MachineError(format!(
384 "no item to reborrow for {:?} from tag {} found in borrow stack", new.perm, derived_from,
387 // Compute where to put the new item.
388 // Either way, we ensure that we insert the new item in a way that between
389 // `derived_from` and the new one, there are only items *compatible with* `derived_from`.
390 let new_idx = if weak {
391 // A weak SharedReadOnly reborrow might be added below other items, violating the
392 // invariant that only SharedReadOnly can sit on top of SharedReadOnly.
393 assert!(new.perm != Permission::SharedReadOnly, "Weak SharedReadOnly reborrows don't work");
394 // A very liberal reborrow because the new pointer does not expect any kind of aliasing guarantee.
395 // Just insert new permission as child of old permission, and maintain everything else.
396 // This inserts "as far down as possible", which is good because it makes this pointer as
397 // long-lived as possible *and* we want all the items that are incompatible with this
398 // to actually get removed from the stack. If we pushed a `SharedReadWrite` on top of
399 // a `SharedReadOnly`, we'd violate the invariant that `SaredReadOnly` are at the top
400 // and we'd allow write access without invalidating frozen shared references!
401 // This ensures F2b for `SharedReadWrite` by adding the new item below any
402 // potentially existing `SharedReadOnly`.
403 first_incompatible_idx
405 // A "safe" reborrow for a pointer that actually expects some aliasing guarantees.
406 // Here, creating a reference actually counts as an access, and pops incompatible
407 // stuff off the stack.
408 // This ensures F2b for `Unique`, by removing offending `SharedReadOnly`.
409 self.access(access, derived_from, global)?;
410 if access == AccessKind::Write {
411 // For write accesses, the position is the same as what it would have been weakly!
412 assert_eq!(first_incompatible_idx, self.borrows.len());
415 // We insert "as far up as possible": We know only compatible items are remaining
416 // on top of `derived_from`, and we want the new item at the top so that we
417 // get the strongest possible guarantees.
418 // This ensures U1 and F1.
422 // Put the new item there. As an optimization, deduplicate if it is equal to one of its new neighbors.
423 if self.borrows[new_idx-1] == new || self.borrows.get(new_idx) == Some(&new) {
424 // Optimization applies, done.
425 trace!("reborrow: avoiding adding redundant item {}", new);
427 trace!("reborrow: adding item {}", new);
428 self.borrows.insert(new_idx, new);
431 // Make sure that after all this, the stack's invariant is still maintained.
432 if cfg!(debug_assertions) {
433 self.test_invariants();
439 // # Stacked Borrows Core End
441 /// Map per-stack operations to higher-level per-location-range operations.
443 /// Creates new stack with initial tag.
449 let item = Item { perm: Permission::Unique, tag, protector: None };
454 stacks: RefCell::new(RangeMap::new(size, stack)),
459 /// Call `f` on every stack in the range.
464 f: impl Fn(&mut Stack, &GlobalState) -> EvalResult<'tcx>,
465 ) -> EvalResult<'tcx> {
466 let global = self.global.borrow();
467 let mut stacks = self.stacks.borrow_mut();
468 for stack in stacks.iter_mut(ptr.offset, size) {
475 /// Glue code to connect with Miri Machine Hooks
477 pub fn new_allocation(
480 kind: MemoryKind<MiriMemoryKind>,
482 let tag = match kind {
483 MemoryKind::Stack => {
484 // New unique borrow. This `Uniq` is not accessible by the program,
485 // so it will only ever be used when using the local directly (i.e.,
486 // not through a pointer). That is, whenever we directly use a local, this will pop
487 // everything else off the stack, invalidating all previous pointers,
488 // and in particular, *all* raw pointers. This subsumes the explicit
489 // `reset` which the blog post [1] says to perform when accessing a local.
491 // [1]: <https://www.ralfj.de/blog/2018/08/07/stacked-borrows.html>
492 Tag::Tagged(extra.borrow_mut().new_ptr())
498 let stack = Stacks::new(size, tag, Rc::clone(extra));
503 impl AllocationExtra<Tag> for Stacks {
505 fn memory_read<'tcx>(
506 alloc: &Allocation<Tag, Stacks>,
509 ) -> EvalResult<'tcx> {
510 trace!("read access with tag {}: {:?}, size {}", ptr.tag, ptr, size.bytes());
511 alloc.extra.for_each(ptr, size, |stack, global| {
512 stack.access(AccessKind::Read, ptr.tag, global)?;
518 fn memory_written<'tcx>(
519 alloc: &mut Allocation<Tag, Stacks>,
522 ) -> EvalResult<'tcx> {
523 trace!("write access with tag {}: {:?}, size {}", ptr.tag, ptr, size.bytes());
524 alloc.extra.for_each(ptr, size, |stack, global| {
525 stack.access(AccessKind::Write, ptr.tag, global)?;
531 fn memory_deallocated<'tcx>(
532 alloc: &mut Allocation<Tag, Stacks>,
535 ) -> EvalResult<'tcx> {
536 trace!("deallocation with tag {}: {:?}, size {}", ptr.tag, ptr, size.bytes());
537 alloc.extra.for_each(ptr, size, |stack, global| {
538 stack.dealloc(ptr.tag, global)
543 /// Retagging/reborrowing. There is some policy in here, such as which permissions
544 /// to grant for which references, when to add protectors, and how to realize two-phase
545 /// borrows in terms of the primitives above.
546 impl<'a, 'mir, 'tcx> EvalContextPrivExt<'a, 'mir, 'tcx> for crate::MiriEvalContext<'a, 'mir, 'tcx> {}
547 trait EvalContextPrivExt<'a, 'mir, 'tcx: 'a+'mir>: crate::MiriEvalContextExt<'a, 'mir, 'tcx> {
550 place: MPlaceTy<'tcx, Tag>,
556 ) -> EvalResult<'tcx> {
557 let this = self.eval_context_mut();
558 let protector = if protect { Some(this.frame().extra) } else { None };
559 let ptr = place.ptr.to_ptr()?;
560 trace!("reborrow: {:?} reference {} derived from {} (pointee {}): {:?}, size {}",
561 kind, new_tag, ptr.tag, place.layout.ty, ptr, size.bytes());
563 // Get the allocation. It might not be mutable, so we cannot use `get_mut`.
564 let alloc = this.memory().get(ptr.alloc_id)?;
565 alloc.check_bounds(this, ptr, size)?;
566 // Update the stacks.
567 // Make sure that raw pointers and mutable shared references are reborrowed "weak":
568 // There could be existing unique pointers reborrowed from them that should remain valid!
569 let perm = match kind {
570 RefKind::Unique => Permission::Unique,
571 RefKind::Raw { mutable: true } => Permission::SharedReadWrite,
572 RefKind::Shared | RefKind::Raw { mutable: false } => {
573 // Shared references and *const are a whole different kind of game, the
574 // permission is not uniform across the entire range!
575 // We need a frozen-sensitive reborrow.
576 return this.visit_freeze_sensitive(place, size, |cur_ptr, size, frozen| {
577 // We are only ever `SharedReadOnly` inside the frozen bits.
578 let perm = if frozen { Permission::SharedReadOnly } else { Permission::SharedReadWrite };
579 let weak = perm == Permission::SharedReadWrite;
580 let item = Item { perm, tag: new_tag, protector };
581 alloc.extra.for_each(cur_ptr, size, |stack, global| {
582 stack.grant(cur_ptr.tag, force_weak || weak, item, global)
587 debug_assert_ne!(perm, Permission::SharedReadOnly, "SharedReadOnly must be used frozen-sensitive");
588 let weak = perm == Permission::SharedReadWrite;
589 let item = Item { perm, tag: new_tag, protector };
590 alloc.extra.for_each(ptr, size, |stack, global| {
591 stack.grant(ptr.tag, force_weak || weak, item, global)
595 /// Retags an indidual pointer, returning the retagged version.
596 /// `mutbl` can be `None` to make this a raw pointer.
599 val: ImmTy<'tcx, Tag>,
603 ) -> EvalResult<'tcx, Immediate<Tag>> {
604 let this = self.eval_context_mut();
605 // We want a place for where the ptr *points to*, so we get one.
606 let place = this.ref_to_mplace(val)?;
607 let size = this.size_and_align_of_mplace(place)?
608 .map(|(size, _)| size)
609 .unwrap_or_else(|| place.layout.size);
610 if size == Size::ZERO {
611 // Nothing to do for ZSTs.
615 // Compute new borrow.
616 let new_tag = match kind {
617 RefKind::Raw { .. } => Tag::Untagged,
618 _ => Tag::Tagged(this.memory().extra.borrow_mut().new_ptr()),
622 // TODO: With `two_phase == true`, this performs a weak reborrow for a `Unique`. That
623 // can lead to some possibly surprising effects, if the parent permission is
624 // `SharedReadWrite` then we now have a `Unique` in the middle of them, which "splits"
625 // them in terms of what remains valid when the `Unique` gets used. Is that really
627 this.reborrow(place, size, kind, new_tag, /*force_weak:*/ two_phase, protect)?;
628 let new_place = place.replace_tag(new_tag);
629 // Handle two-phase borrows.
631 assert!(kind == RefKind::Unique, "two-phase shared borrows make no sense");
632 // Grant read access *to the parent pointer* with the old tag *derived from the new tag* (`new_place`).
633 // This means the old pointer has multiple items in the stack now, which otherwise cannot happen
634 // for unique references -- but in this case it precisely expresses the semantics we want.
635 let old_tag = place.ptr.to_ptr().unwrap().tag;
636 this.reborrow(new_place, size, RefKind::Shared, old_tag, /*force_weak:*/ false, /*protect:*/ false)?;
639 // Return new pointer.
640 Ok(new_place.to_ref())
644 impl<'a, 'mir, 'tcx> EvalContextExt<'a, 'mir, 'tcx> for crate::MiriEvalContext<'a, 'mir, 'tcx> {}
645 pub trait EvalContextExt<'a, 'mir, 'tcx: 'a+'mir>: crate::MiriEvalContextExt<'a, 'mir, 'tcx> {
649 place: PlaceTy<'tcx, Tag>
650 ) -> EvalResult<'tcx> {
651 let this = self.eval_context_mut();
652 // Determine mutability and whether to add a protector.
653 // Cannot use `builtin_deref` because that reports *immutable* for `Box`,
654 // making it useless.
655 fn qualify(ty: ty::Ty<'_>, kind: RetagKind) -> Option<(RefKind, bool)> {
657 // References are simple.
658 ty::Ref(_, _, MutMutable) =>
659 Some((RefKind::Unique, kind == RetagKind::FnEntry)),
660 ty::Ref(_, _, MutImmutable) =>
661 Some((RefKind::Shared, kind == RetagKind::FnEntry)),
662 // Raw pointers need to be enabled.
663 ty::RawPtr(tym) if kind == RetagKind::Raw =>
664 Some((RefKind::Raw { mutable: tym.mutbl == MutMutable }, false)),
665 // Boxes do not get a protector: protectors reflect that references outlive the call
666 // they were passed in to; that's just not the case for boxes.
667 ty::Adt(..) if ty.is_box() => Some((RefKind::Unique, false)),
672 // We need a visitor to visit all references. However, that requires
673 // a `MemPlace`, so we have a fast path for reference types that
674 // avoids allocating.
675 if let Some((mutbl, protector)) = qualify(place.layout.ty, kind) {
677 let val = this.read_immediate(this.place_to_op(place)?)?;
678 let val = this.retag_reference(val, mutbl, protector, kind == RetagKind::TwoPhase)?;
679 this.write_immediate(val, place)?;
682 let place = this.force_allocation(place)?;
684 let mut visitor = RetagVisitor { ecx: this, kind };
685 visitor.visit_value(place)?;
687 // The actual visitor.
688 struct RetagVisitor<'ecx, 'a, 'mir, 'tcx> {
689 ecx: &'ecx mut MiriEvalContext<'a, 'mir, 'tcx>,
692 impl<'ecx, 'a, 'mir, 'tcx>
693 MutValueVisitor<'a, 'mir, 'tcx, Evaluator<'tcx>>
695 RetagVisitor<'ecx, 'a, 'mir, 'tcx>
697 type V = MPlaceTy<'tcx, Tag>;
700 fn ecx(&mut self) -> &mut MiriEvalContext<'a, 'mir, 'tcx> {
704 // Primitives of reference type, that is the one thing we are interested in.
705 fn visit_primitive(&mut self, place: MPlaceTy<'tcx, Tag>) -> EvalResult<'tcx>
707 // Cannot use `builtin_deref` because that reports *immutable* for `Box`,
708 // making it useless.
709 if let Some((mutbl, protector)) = qualify(place.layout.ty, self.kind) {
710 let val = self.ecx.read_immediate(place.into())?;
711 let val = self.ecx.retag_reference(
715 self.kind == RetagKind::TwoPhase
717 self.ecx.write_immediate(val, place.into())?;