//! for further information.
use std::cell::RefCell;
-use std::collections::{HashMap, HashSet};
-use std::rc::Rc;
use std::fmt;
use std::num::NonZeroU64;
+use std::rc::Rc;
-use rustc::ty::{self, layout::Size};
-use rustc::hir::Mutability::{Mutable, Immutable};
+use rustc_data_structures::fx::{FxHashMap, FxHashSet};
use rustc::mir::RetagKind;
+use rustc::ty::{self, layout::Size};
+use rustc_hir::Mutability;
-use crate::{
- InterpResult, HelpersEvalContextExt,
- MemoryKind, MiriMemoryKind, RangeMap, AllocId, Pointer, Immediate, ImmTy, PlaceTy, MPlaceTy,
-};
+use crate::*;
pub type PtrId = NonZeroU64;
pub type CallId = NonZeroU64;
borrows: Vec<Item>,
}
-
/// Extra per-allocation state.
#[derive(Clone, Debug)]
pub struct Stacks {
/// Table storing the "base" tag for each allocation.
/// The base tag is the one used for the initial pointer.
/// We need this in a separate table to handle cyclic statics.
- base_ptr_ids: HashMap<AllocId, Tag>,
+ base_ptr_ids:
FxHashMap<AllocId, Tag>,
/// Next unused call ID (for protectors).
next_call_id: CallId,
/// Those call IDs corresponding to functions that are still running.
- active_calls: HashSet<CallId>,
+ active_calls: FxHashSet<CallId>,
+ /// The id to trace in this execution run
+ tracked_pointer_tag: Option<PtrId>,
}
/// Memory extra state gives us interior mutable access to the global state.
pub type MemoryExtra = Rc<RefCell<GlobalState>>;
}
/// Utilities for initialization and ID generation
-impl Default for GlobalState {
- fn default() -> Self {
+impl GlobalState {
+ pub fn new(tracked_pointer_tag: Option<PtrId>) -> Self {
GlobalState {
next_ptr_id: NonZeroU64::new(1).unwrap(),
- base_ptr_ids: HashMap::default(),
+ base_ptr_ids: FxHashMap::default(),
next_call_id: NonZeroU64::new(1).unwrap(),
- active_calls: HashSet::default(),
+ active_calls: FxHashSet::default(),
+ tracked_pointer_tag,
}
}
-}
-impl GlobalState {
fn new_ptr(&mut self) -> PtrId {
let id = self.next_ptr_id;
self.next_ptr_id = NonZeroU64::new(id.get() + 1).unwrap();
self.active_calls.contains(&id)
}
- pub fn static_base_ptr(&mut self, id: AllocId) -> Tag {
+ pub fn global_base_ptr(&mut self, id: AllocId) -> Tag {
self.base_ptr_ids.get(&id).copied().unwrap_or_else(|| {
let tag = Tag::Tagged(self.new_ptr());
trace!("New allocation {:?} has base tag {:?}", id, tag);
}
}
+/// Error reporting
+fn err_sb_ub(msg: String) -> InterpError<'static> {
+ err_machine_stop!(TerminationInfo::ExperimentalUb {
+ msg,
+ url: format!("https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md"),
+ })
+}
+
// # Stacked Borrows Core Begin
/// We need to make at least the following things true:
/// This defines for a given permission, whether it permits the given kind of access.
fn grants(self, access: AccessKind) -> bool {
// Disabled grants nothing. Otherwise, all items grant read access, and except for SharedReadOnly they grant write access.
- self != Permission::Disabled && (access == AccessKind::Read || self != Permission::SharedReadOnly)
+ self != Permission::Disabled
+ && (access == AccessKind::Read || self != Permission::SharedReadOnly)
}
}
/// Find the item granting the given kind of access to the given tag, and return where
/// it is on the stack.
fn find_granting(&self, access: AccessKind, tag: Tag) -> Option<usize> {
- self.borrows.iter()
+ self.borrows
+ .iter()
.enumerate() // we also need to know *where* in the stack
.rev() // search top-to-bottom
// Return permission of first item that grants access.
// We require a permission with the right tag, ensuring U3 and F3.
- .find_map(|(idx, item)|
- if tag == item.tag && item.perm.grants(access) {
- Some(idx)
- } else {
- None
- }
+ .find_map(
+ |(idx, item)| {
+ if tag == item.tag && item.perm.grants(access) { Some(idx) } else { None }
+ },
)
}
fn find_first_write_incompatible(&self, granting: usize) -> usize {
let perm = self.borrows[granting].perm;
match perm {
- Permission::SharedReadOnly =>
- bug!("Cannot use SharedReadOnly for writing"),
- Permission::Disabled =>
- bug!("Cannot use Disabled for anything"),
- Permission::Unique =>
- // On a write, everything above us is incompatible.
- granting + 1,
+ Permission::SharedReadOnly => bug!("Cannot use SharedReadOnly for writing"),
+ Permission::Disabled => bug!("Cannot use Disabled for anything"),
+ // On a write, everything above us is incompatible.
+ Permission::Unique => granting + 1,
Permission::SharedReadWrite => {
// The SharedReadWrite *just* above us are compatible, to skip those.
let mut idx = granting + 1;
/// Check if the given item is protected.
fn check_protector(item: &Item, tag: Option<Tag>, global: &GlobalState) -> InterpResult<'tcx> {
+ if let Tag::Tagged(id) = item.tag {
+ if Some(id) == global.tracked_pointer_tag {
+ register_diagnostic(NonHaltingDiagnostic::PoppedTrackedPointerTag(item.clone()));
+ }
+ }
if let Some(call) = item.protector {
if global.is_active(call) {
if let Some(tag) = tag {
- throw_ub!(UbExperimental(format!(
+ Err(err_sb_ub(format!(
"not granting access to tag {:?} because incompatible item is protected: {:?}",
tag, item
- )));
+ )))?
} else {
- throw_ub!(UbExperimental(format!(
- "deallocating while item is protected: {:?}", item
- )));
+ Err(err_sb_ub(format!(
+ "deallocating while item is protected: {:?}",
+ item
+ )))?
}
}
}
/// Test if a memory `access` using pointer tagged `tag` is granted.
/// If yes, return the index of the item that granted it.
- fn access(
- &mut self,
- access: AccessKind,
- tag: Tag,
- global: &GlobalState,
- ) -> InterpResult<'tcx> {
+ fn access(&mut self, access: AccessKind, tag: Tag, global: &GlobalState) -> InterpResult<'tcx> {
// Two main steps: Find granting item, remove incompatible items above.
// Step 1: Find granting item.
- let granting_idx = self.find_granting(access, tag)
- .ok_or_else(|| err_ub!(UbExperimental(format!(
- "no item granting {} to tag {:?} found in borrow stack",
- access, tag,
- ))))?;
+ let granting_idx = self.find_granting(access, tag).ok_or_else(|| {
+ err_sb_ub(format!(
+ "no item granting {} to tag {:?} found in borrow stack.",
+ access, tag
+ ))
+ })?;
// Step 2: Remove incompatible items above them. Make sure we do not remove protected
// items. Behavior differs for reads and writes.
// This pattern occurs a lot in the standard library: create a raw pointer, then also create a shared
// reference and use that.
// We *disable* instead of removing `Unique` to avoid "connecting" two neighbouring blocks of SRWs.
- for idx in (granting_idx+1 .. self.borrows.len()).rev() {
+ for idx in ((granting_idx + 1)..self.borrows.len()).rev() {
let item = &mut self.borrows[idx];
if item.perm == Permission::Unique {
trace!("access: disabling item {:?}", item);
/// Deallocate a location: Like a write access, but also there must be no
/// active protectors at all because we will remove all items.
- fn dealloc(
- &mut self,
- tag: Tag,
- global: &GlobalState,
- ) -> InterpResult<'tcx> {
+ fn dealloc(&mut self, tag: Tag, global: &GlobalState) -> InterpResult<'tcx> {
// Step 1: Find granting item.
- self.find_granting(AccessKind::Write, tag)
- .ok_or_else(|| err_ub!(UbExperimental(format!(
+ self.find_granting(AccessKind::Write, tag).ok_or_else(|| {
+ err_sb_ub(format!(
"no item granting write access for deallocation to tag {:?} found in borrow stack",
tag,
- ))))?;
+ ))
+ })?;
// Step 2: Remove all items. Also checks for protectors.
for item in self.borrows.drain(..).rev() {
/// `weak` controls whether this operation is weak or strong: weak granting does not act as
/// an access, and they add the new item directly on top of the one it is derived
/// from instead of all the way at the top of the stack.
- fn grant(
- &mut self,
- derived_from: Tag,
- new: Item,
- global: &GlobalState,
- ) -> InterpResult<'tcx> {
+ fn grant(&mut self, derived_from: Tag, new: Item, global: &GlobalState) -> InterpResult<'tcx> {
// Figure out which access `perm` corresponds to.
- let access = if new.perm.grants(AccessKind::Write) {
- AccessKind::Write
- } else {
- AccessKind::Read
- };
+ let access =
+ if new.perm.grants(AccessKind::Write) { AccessKind::Write } else { AccessKind::Read };
// Now we figure out which item grants our parent (`derived_from`) this kind of access.
// We use that to determine where to put the new item.
let granting_idx = self.find_granting(access, derived_from)
- .ok_or_else(|| err_ub!(UbExperimental(format!(
- "trying to reborrow for {:?}, but parent tag {:?} does not have an appropriate item in the borrow stack", new.perm, derived_from,
- ))))?;
+ .ok_or_else(|| err_sb_ub(format!(
+ "trying to reborrow for {:?}, but parent tag {:?} does not have an appropriate item in the borrow stack",
+ new.perm, derived_from,
+ )))?;
// Compute where to put the new item.
// Either way, we ensure that we insert the new item in a way such that between
// `derived_from` and the new one, there are only items *compatible with* `derived_from`.
let new_idx = if new.perm == Permission::SharedReadWrite {
- assert!(access == AccessKind::Write, "this case only makes sense for stack-like accesses");
+ assert!(
+ access == AccessKind::Write,
+ "this case only makes sense for stack-like accesses"
+ );
// SharedReadWrite can coexist with "existing loans", meaning they don't act like a write
// access. Instead of popping the stack, we insert the item at the place the stack would
// be popped to (i.e., we insert it above all the write-compatible items).
};
// Put the new item there. As an optimization, deduplicate if it is equal to one of its new neighbors.
- if self.borrows[new_idx-1] == new || self.borrows.get(new_idx) == Some(&new) {
+ if self.borrows[new_idx - 1] == new || self.borrows.get(new_idx) == Some(&new) {
// Optimization applies, done.
trace!("reborrow: avoiding adding redundant item {:?}", new);
} else {
/// Map per-stack operations to higher-level per-location-range operations.
impl<'tcx> Stacks {
/// Creates new stack with initial tag.
- fn new(
- size: Size,
- perm: Permission,
- tag: Tag,
- extra: MemoryExtra,
- ) -> Self {
+ fn new(size: Size, perm: Permission, tag: Tag, extra: MemoryExtra) -> Self {
let item = Item { perm, tag, protector: None };
- let stack = Stack {
- borrows: vec![item],
- };
+ let stack = Stack { borrows: vec![item] };
- Stacks {
- stacks: RefCell::new(RangeMap::new(size, stack)),
- global: extra,
- }
+ Stacks { stacks: RefCell::new(RangeMap::new(size, stack)), global: extra }
}
/// Call `f` on every stack in the range.
kind: MemoryKind<MiriMemoryKind>,
) -> (Self, Tag) {
let (tag, perm) = match kind {
- MemoryKind::Stack =>
- // New unique borrow. This tag is not accessible by the program,
- // so it will only ever be used when using the local directly (i.e.,
- // not through a pointer). That is, whenever we directly write to a local, this will pop
- // everything else off the stack, invalidating all previous pointers,
- // and in particular, *all* raw pointers.
- (Tag::Tagged(extra.borrow_mut().new_ptr()), Permission::Unique),
- MemoryKind::Machine(MiriMemoryKind::Static) =>
- (extra.borrow_mut().static_base_ptr(id), Permission::SharedReadWrite),
- _ =>
- (Tag::Untagged, Permission::SharedReadWrite),
+ // New unique borrow. This tag is not accessible by the program,
+ // so it will only ever be used when using the local directly (i.e.,
+ // not through a pointer). That is, whenever we directly write to a local, this will pop
+ // everything else off the stack, invalidating all previous pointers,
+ // and in particular, *all* raw pointers.
+ MemoryKind::Stack => (Tag::Tagged(extra.borrow_mut().new_ptr()), Permission::Unique),
+ // Global memory can be referenced by global pointers from `tcx`.
+ // Thus we call `global_base_ptr` such that the global pointers get the same tag
+ // as what we use here.
+ // `Machine` is used for extern statics, and thus must also be listed here.
+ // `Env` we list because we can get away with precise tracking there.
+ // The base pointer is not unique, so the base permission is `SharedReadWrite`.
+ MemoryKind::Machine(MiriMemoryKind::Global | MiriMemoryKind::Machine | MiriMemoryKind::Env) =>
+ (extra.borrow_mut().global_base_ptr(id), Permission::SharedReadWrite),
+ // Everything else we handle entirely untagged for now.
+ // FIXME: experiment with more precise tracking.
+ _ => (Tag::Untagged, Permission::SharedReadWrite),
};
- let stack = Stacks::new(size, perm, tag, extra);
- (stack, tag)
+ (Stacks::new(size, perm, tag, extra), tag)
}
#[inline(always)]
- pub fn memory_read<'tcx>(
- &self,
- ptr: Pointer<Tag>,
- size: Size,
- ) -> InterpResult<'tcx> {
+ pub fn memory_read<'tcx>(&self, ptr: Pointer<Tag>, size: Size) -> InterpResult<'tcx> {
trace!("read access with tag {:?}: {:?}, size {}", ptr.tag, ptr.erase_tag(), size.bytes());
self.for_each(ptr, size, |stack, global| {
stack.access(AccessKind::Read, ptr.tag, global)?;
}
#[inline(always)]
- pub fn memory_written<'tcx>(
- &mut self,
- ptr: Pointer<Tag>,
- size: Size,
- ) -> InterpResult<'tcx> {
+ pub fn memory_written<'tcx>(&mut self, ptr: Pointer<Tag>, size: Size) -> InterpResult<'tcx> {
trace!("write access with tag {:?}: {:?}, size {}", ptr.tag, ptr.erase_tag(), size.bytes());
self.for_each(ptr, size, |stack, global| {
stack.access(AccessKind::Write, ptr.tag, global)?;
size: Size,
) -> InterpResult<'tcx> {
trace!("deallocation with tag {:?}: {:?}, size {}", ptr.tag, ptr.erase_tag(), size.bytes());
- self.for_each(ptr, size, |stack, global| {
- stack.dealloc(ptr.tag, global)
- })
+ self.for_each(ptr, size, |stack, global| stack.dealloc(ptr.tag, global))
}
}
protect: bool,
) -> InterpResult<'tcx> {
let this = self.eval_context_mut();
- let protector = if protect { Some(this.frame().extra) } else { None };
- let ptr = place.ptr.to_ptr().expect("we should have a proper pointer");
- trace!("reborrow: {} reference {:?} derived from {:?} (pointee {}): {:?}, size {}",
- kind, new_tag, ptr.tag, place.layout.ty, ptr.erase_tag(), size.bytes());
+ let protector = if protect { Some(this.frame().extra.call_id) } else { None };
+ let ptr = place.ptr.assert_ptr();
+ trace!(
+ "reborrow: {} reference {:?} derived from {:?} (pointee {}): {:?}, size {}",
+ kind,
+ new_tag,
+ ptr.tag,
+ place.layout.ty,
+ ptr.erase_tag(),
+ size.bytes()
+ );
// Get the allocation. It might not be mutable, so we cannot use `get_mut`.
let extra = &this.memory.get_raw(ptr.alloc_id)?.extra;
- let stacked_borrows = extra.stacked_borrows.as_ref().expect("we should have Stacked Borrows data");
+ let stacked_borrows =
+ extra.stacked_borrows.as_ref().expect("we should have Stacked Borrows data");
// Update the stacks.
// Make sure that raw pointers and mutable shared references are reborrowed "weak":
// There could be existing unique pointers reborrowed from them that should remain valid!
// We need a frozen-sensitive reborrow.
return this.visit_freeze_sensitive(place, size, |cur_ptr, size, frozen| {
// We are only ever `SharedReadOnly` inside the frozen bits.
- let perm = if frozen { Permission::SharedReadOnly } else { Permission::SharedReadWrite };
+ let perm = if frozen {
+ Permission::SharedReadOnly
+ } else {
+ Permission::SharedReadWrite
+ };
let item = Item { perm, tag: new_tag, protector };
stacked_borrows.for_each(cur_ptr, size, |stack, global| {
stack.grant(cur_ptr.tag, item, global)
}
};
let item = Item { perm, tag: new_tag, protector };
- stacked_borrows.for_each(ptr, size, |stack, global| {
- stack.grant(ptr.tag, item, global)
- })
+ stacked_borrows.for_each(ptr, size, |stack, global| stack.grant(ptr.tag, item, global))
}
/// Retags an indidual pointer, returning the retagged version.
let this = self.eval_context_mut();
// We want a place for where the ptr *points to*, so we get one.
let place = this.ref_to_mplace(val)?;
- let size = this.size_and_align_of_mplace(place)?
+ let size = this
+ .size_and_align_of_mplace(place)?
.map(|(size, _)| size)
.unwrap_or_else(|| place.layout.size);
// We can see dangling ptrs in here e.g. after a Box's `Unique` was
// Compute new borrow.
let new_tag = match kind {
+ // Give up tracking for raw pointers.
+ // FIXME: Experiment with more precise tracking. Blocked on `&raw`
+ // because `Rc::into_raw` currently creates intermediate references,
+ // breaking `Rc::from_raw`.
RefKind::Raw { .. } => Tag::Untagged,
- _ => Tag::Tagged(this.memory.extra.stacked_borrows.borrow_mut().new_ptr()),
+ // All other pointesr are properly tracked.
+ _ => Tag::Tagged(
+ this.memory.extra.stacked_borrows.as_ref().unwrap().borrow_mut().new_ptr(),
+ ),
};
// Reborrow.
impl<'mir, 'tcx> EvalContextExt<'mir, 'tcx> for crate::MiriEvalContext<'mir, 'tcx> {}
pub trait EvalContextExt<'mir, 'tcx: 'mir>: crate::MiriEvalContextExt<'mir, 'tcx> {
- fn retag(
- &mut self,
- kind: RetagKind,
- place: PlaceTy<'tcx, Tag>
- ) -> InterpResult<'tcx> {
+ fn retag(&mut self, kind: RetagKind, place: PlaceTy<'tcx, Tag>) -> InterpResult<'tcx> {
let this = self.eval_context_mut();
// Determine mutability and whether to add a protector.
// Cannot use `builtin_deref` because that reports *immutable* for `Box`,
fn qualify(ty: ty::Ty<'_>, kind: RetagKind) -> Option<(RefKind, bool)> {
match ty.kind {
// References are simple.
- ty::Ref(_, _, Mutable) =>
- Some((RefKind::Unique { two_phase: kind == RetagKind::TwoPhase}, kind == RetagKind::FnEntry)),
- ty::Ref(_, _, Immutable) =>
+ ty::Ref(_, _, Mutability::Mut) => Some((
+ RefKind::Unique { two_phase: kind == RetagKind::TwoPhase },
+ kind == RetagKind::FnEntry,
+ )),
+ ty::Ref(_, _, Mutability::Not) =>
Some((RefKind::Shared, kind == RetagKind::FnEntry)),
// Raw pointers need to be enabled.
ty::RawPtr(tym) if kind == RetagKind::Raw =>
- Some((RefKind::Raw { mutable: tym.mutbl == Mutable }, false)),
+ Some((RefKind::Raw { mutable: tym.mutbl == Mutability::Mut }, false)),
// Boxes do not get a protector: protectors reflect that references outlive the call
// they were passed in to; that's just not the case for boxes.
ty::Adt(..) if ty.is_box() => Some((RefKind::Unique { two_phase: false }, false)),
projects / rust.git / blobdiff