miri/borrow_tracker/
mod.rs

1use std::cell::RefCell;
2use std::num::NonZero;
3use std::{fmt, mem};
4
5use rustc_abi::Size;
6use rustc_data_structures::fx::{FxHashMap, FxHashSet};
7use rustc_middle::ty::Ty;
8use smallvec::SmallVec;
9
10use crate::*;
11pub mod stacked_borrows;
12pub mod tree_borrows;
13
14/// Indicates which kind of access is being performed.
15#[derive(Copy, Clone, Hash, PartialEq, Eq, Debug)]
16pub enum AccessKind {
17    Read,
18    Write,
19}
20
21impl fmt::Display for AccessKind {
22    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
23        match self {
24            AccessKind::Read => write!(f, "read access"),
25            AccessKind::Write => write!(f, "write access"),
26        }
27    }
28}
29
30/// Tracking pointer provenance
31#[derive(Copy, Clone, Hash, PartialEq, Eq, PartialOrd, Ord)]
32pub struct BorTag(NonZero<u64>);
33
34impl BorTag {
35    pub fn new(i: u64) -> Option<Self> {
36        NonZero::new(i).map(BorTag)
37    }
38
39    pub fn get(&self) -> u64 {
40        self.0.get()
41    }
42
43    pub fn inner(&self) -> NonZero<u64> {
44        self.0
45    }
46
47    pub fn succ(self) -> Option<Self> {
48        self.0.checked_add(1).map(Self)
49    }
50
51    /// The minimum representable tag
52    pub fn one() -> Self {
53        Self::new(1).unwrap()
54    }
55}
56
57impl std::default::Default for BorTag {
58    /// The default to be used when borrow tracking is disabled
59    fn default() -> Self {
60        Self::one()
61    }
62}
63
64impl fmt::Debug for BorTag {
65    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
66        write!(f, "<{}>", self.0)
67    }
68}
69
70/// Per-call-stack-frame data for borrow tracking
71#[derive(Debug)]
72pub struct FrameState {
73    /// If this frame is protecting any tags, they are listed here. We use this list to do
74    /// incremental updates of the global list of protected tags stored in the
75    /// `stacked_borrows::GlobalState` upon function return, and if we attempt to pop a protected
76    /// tag, to identify which call is responsible for protecting the tag.
77    /// See `Stack::item_invalidated` for more explanation.
78    /// Tree Borrows also needs to know which allocation these tags
79    /// belong to so that it can perform a read through them immediately before
80    /// the frame gets popped.
81    ///
82    /// This will contain one tag per reference passed to the function, so
83    /// a size of 2 is enough for the vast majority of functions.
84    protected_tags: SmallVec<[(AllocId, BorTag); 2]>,
85}
86
87impl VisitProvenance for FrameState {
88    fn visit_provenance(&self, visit: &mut VisitWith<'_>) {
89        // Visit all protected tags. At least in Tree Borrows,
90        // protected tags can not be GC'd because they still have
91        // an access coming when the protector ends. Additionally,
92        // the tree compacting mechanism of TB's GC relies on the fact
93        // that all protected tags are marked as live for correctness,
94        // so we _have_ to visit them here.
95        for (id, tag) in &self.protected_tags {
96            visit(Some(*id), Some(*tag));
97        }
98    }
99}
100
101/// Extra global state, available to the memory access hooks.
102#[derive(Debug)]
103pub struct GlobalStateInner {
104    /// Borrow tracker method currently in use.
105    borrow_tracker_method: BorrowTrackerMethod,
106    /// The currently active retag mode.
107    retag_mode: RetagMode,
108    /// Next unused pointer ID (tag).
109    next_ptr_tag: BorTag,
110    /// Table storing the "root" tag for each allocation.
111    /// The root tag is the one used for the initial pointer.
112    /// We need this in a separate table to handle cyclic statics.
113    root_ptr_tags: FxHashMap<AllocId, BorTag>,
114    /// All currently protected tags.
115    /// We add tags to this when they are created with a protector in `reborrow`, and
116    /// we remove tags from this when the call which is protecting them returns, in
117    /// `GlobalStateInner::end_call`. See `Stack::item_invalidated` for more details.
118    protected_tags: FxHashMap<BorTag, ProtectorKind>,
119    /// The pointer ids to trace
120    tracked_pointer_tags: FxHashSet<BorTag>,
121}
122
123impl VisitProvenance for GlobalStateInner {
124    fn visit_provenance(&self, _visit: &mut VisitWith<'_>) {
125        // All the provenance in protected_tags is also stored in FrameState, and visited there.
126        // The only other candidate is base_ptr_tags, and that does not need visiting since we don't ever
127        // GC the bottommost/root tag.
128    }
129}
130
131/// We need interior mutable access to the global state.
132pub type GlobalState = RefCell<GlobalStateInner>;
133
134/// The flavor of the protector.
135#[derive(Copy, Clone, Debug, PartialEq, Eq)]
136pub enum ProtectorKind {
137    /// Protected against aliasing violations from other pointers.
138    ///
139    /// Items protected like this cause UB when they are invalidated, *but* the pointer itself may
140    /// still be used to issue a deallocation.
141    ///
142    /// This is required for LLVM IR pointers that are `noalias` but *not* `dereferenceable`.
143    WeakProtector,
144
145    /// Protected against any kind of invalidation.
146    ///
147    /// Items protected like this cause UB when they are invalidated or the memory is deallocated.
148    /// This is strictly stronger protection than `WeakProtector`.
149    ///
150    /// This is required for LLVM IR pointers that are `dereferenceable` (and also allows `noalias`).
151    StrongProtector,
152}
153
154/// Utilities for initialization and ID generation
155impl GlobalStateInner {
156    pub fn new(
157        borrow_tracker_method: BorrowTrackerMethod,
158        tracked_pointer_tags: FxHashSet<BorTag>,
159    ) -> Self {
160        GlobalStateInner {
161            borrow_tracker_method,
162            retag_mode: RetagMode::Default,
163            next_ptr_tag: BorTag::one(),
164            root_ptr_tags: FxHashMap::default(),
165            protected_tags: FxHashMap::default(),
166            tracked_pointer_tags,
167        }
168    }
169
170    /// Generates a new pointer tag. Remember to also check track_pointer_tags and log its creation!
171    fn new_ptr(&mut self) -> BorTag {
172        let id = self.next_ptr_tag;
173        self.next_ptr_tag = id.succ().unwrap();
174        id
175    }
176
177    pub fn new_frame(&mut self) -> FrameState {
178        FrameState { protected_tags: SmallVec::new() }
179    }
180
181    fn end_call(&mut self, frame: &machine::FrameExtra<'_>) {
182        for (_, tag) in &frame
183            .borrow_tracker
184            .as_ref()
185            .expect("we should have borrow tracking data")
186            .protected_tags
187        {
188            self.protected_tags.remove(tag);
189        }
190    }
191
192    pub fn root_ptr_tag(&mut self, id: AllocId, machine: &MiriMachine<'_>) -> BorTag {
193        self.root_ptr_tags.get(&id).copied().unwrap_or_else(|| {
194            let tag = self.new_ptr();
195            if self.tracked_pointer_tags.contains(&tag) {
196                machine.emit_diagnostic(NonHaltingDiagnostic::CreatedPointerTag(
197                    tag.inner(),
198                    None,
199                    None,
200                ));
201            }
202            trace!("New allocation {:?} has rpot tag {:?}", id, tag);
203            self.root_ptr_tags.try_insert(id, tag).unwrap();
204            tag
205        })
206    }
207
208    pub fn remove_unreachable_allocs(&mut self, allocs: &LiveAllocs<'_, '_>) {
209        self.root_ptr_tags.retain(|id, _| allocs.is_live(*id));
210    }
211
212    pub fn borrow_tracker_method(&self) -> BorrowTrackerMethod {
213        self.borrow_tracker_method
214    }
215}
216
217/// Which borrow tracking method to use
218#[derive(Debug, Copy, Clone, PartialEq, Eq)]
219pub enum BorrowTrackerMethod {
220    /// Stacked Borrows, as implemented in borrow_tracker/stacked_borrows
221    StackedBorrows,
222    /// Tree borrows, as implemented in borrow_tracker/tree_borrows
223    TreeBorrows(TreeBorrowsParams),
224}
225
226/// Parameters that Tree Borrows can take.
227#[derive(Debug, Copy, Clone, PartialEq, Eq)]
228pub struct TreeBorrowsParams {
229    /// Controls whether we track `UnsafeCell` with byte precision.
230    pub precise_interior_mut: bool,
231    /// Controls whether `&mut` function arguments are immediately activated with an implicit write.
232    pub implicit_writes: bool,
233    /// Controls whether `Box` with custom allocator is considered unique.
234    pub box_custom_allocator_unique: bool,
235}
236
237impl BorrowTrackerMethod {
238    pub fn instantiate_global_state(self, config: &MiriConfig) -> GlobalState {
239        RefCell::new(GlobalStateInner::new(self, config.tracked_pointer_tags.clone()))
240    }
241
242    #[track_caller]
243    pub fn get_tree_borrows_params(self) -> TreeBorrowsParams {
244        match self {
245            BorrowTrackerMethod::TreeBorrows(params) => params,
246            _ => panic!("can only be called when `BorrowTrackerMethod` is `TreeBorrows`"),
247        }
248    }
249}
250
251impl GlobalStateInner {
252    pub fn new_allocation(
253        &mut self,
254        id: AllocId,
255        alloc_size: Size,
256        kind: MemoryKind,
257        machine: &MiriMachine<'_>,
258    ) -> AllocState {
259        let _trace = enter_trace_span!(borrow_tracker::new_allocation, ?id, ?alloc_size, ?kind);
260        match self.borrow_tracker_method {
261            BorrowTrackerMethod::StackedBorrows =>
262                AllocState::StackedBorrows(Box::new(RefCell::new(Stacks::new_allocation(
263                    id, alloc_size, self, kind, machine,
264                )))),
265            BorrowTrackerMethod::TreeBorrows { .. } =>
266                AllocState::TreeBorrows(Box::new(RefCell::new(Tree::new_allocation(
267                    id, alloc_size, self, kind, machine,
268                )))),
269        }
270    }
271}
272
273impl<'tcx> EvalContextExt<'tcx> for crate::MiriInterpCx<'tcx> {}
274pub trait EvalContextExt<'tcx>: crate::MiriInterpCxExt<'tcx> {
275    fn retag_ptr_value(
276        &mut self,
277        val: &ImmTy<'tcx>,
278        ty: Ty<'tcx>,
279    ) -> InterpResult<'tcx, Option<ImmTy<'tcx>>> {
280        let _trace = enter_trace_span!(borrow_tracker::retag_ptr_value, ?ty);
281        let this = self.eval_context_mut();
282        let state = this.machine.borrow_tracker.as_mut().unwrap().get_mut();
283        let method = state.borrow_tracker_method;
284        let retag_mode = state.retag_mode;
285        info!("retag_ptr_value: type={ty}, mode={retag_mode:?}, val={:?}", **val);
286        match method {
287            BorrowTrackerMethod::StackedBorrows => this.sb_retag_ptr_value(val, ty, retag_mode),
288            BorrowTrackerMethod::TreeBorrows { .. } => this.tb_retag_ptr_value(val, ty, retag_mode),
289        }
290    }
291
292    fn with_retag_mode<T>(
293        &mut self,
294        mode: RetagMode,
295        f: impl FnOnce(&mut Self) -> InterpResult<'tcx, T>,
296    ) -> InterpResult<'tcx, T> {
297        // Set up new mode, remembering the old mode.
298        let state = self.eval_context_mut().machine.borrow_tracker.as_mut().unwrap().get_mut();
299        let old_mode = mem::replace(&mut state.retag_mode, mode);
300
301        let ret = f(self);
302
303        // Restore old mode.
304        let state = self.eval_context_mut().machine.borrow_tracker.as_mut().unwrap().get_mut();
305        state.retag_mode = old_mode;
306
307        ret
308    }
309
310    fn protect_place(&mut self, place: &MPlaceTy<'tcx>) -> InterpResult<'tcx, MPlaceTy<'tcx>> {
311        let _trace = enter_trace_span!(borrow_tracker::protect_place, ?place);
312        let this = self.eval_context_mut();
313        let method = this.machine.borrow_tracker.as_mut().unwrap().get_mut().borrow_tracker_method;
314        match method {
315            BorrowTrackerMethod::StackedBorrows => this.sb_protect_place(place),
316            BorrowTrackerMethod::TreeBorrows { .. } => this.tb_protect_place(place),
317        }
318    }
319
320    fn expose_tag(&self, alloc_id: AllocId, tag: BorTag) -> InterpResult<'tcx> {
321        let _trace =
322            enter_trace_span!(borrow_tracker::expose_tag, alloc_id = alloc_id.0, tag = tag.0);
323        let this = self.eval_context_ref();
324        let method = this.machine.borrow_tracker.as_ref().unwrap().borrow().borrow_tracker_method;
325        match method {
326            BorrowTrackerMethod::StackedBorrows => this.sb_expose_tag(alloc_id, tag),
327            BorrowTrackerMethod::TreeBorrows { .. } => this.tb_expose_tag(alloc_id, tag),
328        }
329    }
330
331    fn give_pointer_debug_name(
332        &mut self,
333        ptr: Pointer,
334        nth_parent: u8,
335        name: &str,
336    ) -> InterpResult<'tcx> {
337        let this = self.eval_context_mut();
338        let method = this.machine.borrow_tracker.as_mut().unwrap().get_mut().borrow_tracker_method;
339        match method {
340            BorrowTrackerMethod::StackedBorrows => {
341                this.tcx.tcx.dcx().warn("Stacked Borrows does not support named pointers; `miri_pointer_name` is a no-op");
342                interp_ok(())
343            }
344            BorrowTrackerMethod::TreeBorrows { .. } =>
345                this.tb_give_pointer_debug_name(ptr, nth_parent, name),
346        }
347    }
348
349    fn print_borrow_state(&mut self, alloc_id: AllocId, show_unnamed: bool) -> InterpResult<'tcx> {
350        let this = self.eval_context_mut();
351        let Some(borrow_tracker) = &mut this.machine.borrow_tracker else {
352            eprintln!("attempted to print borrow state, but no borrow state is being tracked");
353            return interp_ok(());
354        };
355        let method = borrow_tracker.get_mut().borrow_tracker_method;
356        match method {
357            BorrowTrackerMethod::StackedBorrows => this.print_stacks(alloc_id),
358            BorrowTrackerMethod::TreeBorrows { .. } => this.print_tree(alloc_id, show_unnamed),
359        }
360    }
361
362    fn on_stack_pop(
363        &self,
364        frame: &Frame<'tcx, Provenance, FrameExtra<'tcx>>,
365    ) -> InterpResult<'tcx> {
366        let _trace = enter_trace_span!(borrow_tracker::on_stack_pop);
367        let this = self.eval_context_ref();
368        let borrow_tracker = this.machine.borrow_tracker.as_ref().unwrap();
369        // The body of this loop needs `borrow_tracker` immutably
370        // so we can't move this code inside the following `end_call`.
371
372        for (alloc_id, tag) in &frame
373            .extra
374            .borrow_tracker
375            .as_ref()
376            .expect("we should have borrow tracking data")
377            .protected_tags
378        {
379            // Just because the tag is protected doesn't guarantee that
380            // the allocation still exists (weak protectors allow deallocations)
381            // so we must check that the allocation exists.
382            // If it does exist, then we have the guarantee that the
383            // pointer is readable, and the implicit read access inserted
384            // will never cause UB on the pointer itself.
385            let kind = this.get_alloc_info(*alloc_id).kind;
386            if matches!(kind, AllocKind::LiveData) {
387                let alloc_extra = this.get_alloc_extra(*alloc_id)?; // can still fail for `extern static`
388                let alloc_borrow_tracker = &alloc_extra.borrow_tracker.as_ref().unwrap();
389                alloc_borrow_tracker.release_protector(
390                    &this.machine,
391                    borrow_tracker,
392                    *tag,
393                    *alloc_id,
394                )?;
395            }
396        }
397        borrow_tracker.borrow_mut().end_call(&frame.extra);
398
399        interp_ok(())
400    }
401}
402
403/// Extra per-allocation data for borrow tracking
404#[derive(Debug, Clone)]
405pub enum AllocState {
406    /// Data corresponding to Stacked Borrows
407    StackedBorrows(Box<RefCell<stacked_borrows::AllocState>>),
408    /// Data corresponding to Tree Borrows
409    TreeBorrows(Box<RefCell<tree_borrows::AllocState>>),
410}
411
412impl machine::AllocExtra<'_> {
413    #[track_caller]
414    pub fn borrow_tracker_sb(&self) -> &RefCell<stacked_borrows::AllocState> {
415        match self.borrow_tracker {
416            Some(AllocState::StackedBorrows(ref sb)) => sb,
417            _ => panic!("expected Stacked Borrows borrow tracking, got something else"),
418        }
419    }
420
421    #[track_caller]
422    pub fn borrow_tracker_sb_mut(&mut self) -> &mut RefCell<stacked_borrows::AllocState> {
423        match self.borrow_tracker {
424            Some(AllocState::StackedBorrows(ref mut sb)) => sb,
425            _ => panic!("expected Stacked Borrows borrow tracking, got something else"),
426        }
427    }
428
429    #[track_caller]
430    pub fn borrow_tracker_tb(&self) -> &RefCell<tree_borrows::AllocState> {
431        match self.borrow_tracker {
432            Some(AllocState::TreeBorrows(ref tb)) => tb,
433            _ => panic!("expected Tree Borrows borrow tracking, got something else"),
434        }
435    }
436}
437
438impl AllocState {
439    pub fn before_memory_read<'tcx>(
440        &self,
441        alloc_id: AllocId,
442        prov_extra: ProvenanceExtra,
443        range: AllocRange,
444        machine: &MiriMachine<'tcx>,
445    ) -> InterpResult<'tcx> {
446        let _trace = enter_trace_span!(borrow_tracker::before_memory_read, alloc_id = alloc_id.0);
447        match self {
448            AllocState::StackedBorrows(sb) =>
449                sb.borrow_mut().before_memory_read(alloc_id, prov_extra, range, machine),
450            AllocState::TreeBorrows(tb) =>
451                tb.borrow_mut().before_memory_access(
452                    AccessKind::Read,
453                    alloc_id,
454                    prov_extra,
455                    range,
456                    machine,
457                ),
458        }
459    }
460
461    pub fn before_memory_write<'tcx>(
462        &mut self,
463        alloc_id: AllocId,
464        prov_extra: ProvenanceExtra,
465        range: AllocRange,
466        machine: &MiriMachine<'tcx>,
467    ) -> InterpResult<'tcx> {
468        let _trace = enter_trace_span!(borrow_tracker::before_memory_write, alloc_id = alloc_id.0);
469        match self {
470            AllocState::StackedBorrows(sb) =>
471                sb.get_mut().before_memory_write(alloc_id, prov_extra, range, machine),
472            AllocState::TreeBorrows(tb) =>
473                tb.get_mut().before_memory_access(
474                    AccessKind::Write,
475                    alloc_id,
476                    prov_extra,
477                    range,
478                    machine,
479                ),
480        }
481    }
482
483    pub fn before_memory_deallocation<'tcx>(
484        &mut self,
485        alloc_id: AllocId,
486        prov_extra: ProvenanceExtra,
487        size: Size,
488        machine: &MiriMachine<'tcx>,
489    ) -> InterpResult<'tcx> {
490        let _trace =
491            enter_trace_span!(borrow_tracker::before_memory_deallocation, alloc_id = alloc_id.0);
492        match self {
493            AllocState::StackedBorrows(sb) =>
494                sb.get_mut().before_memory_deallocation(alloc_id, prov_extra, size, machine),
495            AllocState::TreeBorrows(tb) =>
496                tb.get_mut().before_memory_deallocation(alloc_id, prov_extra, size, machine),
497        }
498    }
499
500    pub fn remove_unreachable_tags(&self, tags: &FxHashSet<BorTag>) {
501        let _trace = enter_trace_span!(borrow_tracker::remove_unreachable_tags);
502        match self {
503            AllocState::StackedBorrows(sb) => sb.borrow_mut().remove_unreachable_tags(tags),
504            AllocState::TreeBorrows(tb) => tb.borrow_mut().remove_unreachable_tags(tags),
505        }
506    }
507
508    /// Tree Borrows needs to be told when a tag stops being protected.
509    pub fn release_protector<'tcx>(
510        &self,
511        machine: &MiriMachine<'tcx>,
512        global: &GlobalState,
513        tag: BorTag,
514        alloc_id: AllocId, // diagnostics
515    ) -> InterpResult<'tcx> {
516        let _trace = enter_trace_span!(
517            borrow_tracker::release_protector,
518            alloc_id = alloc_id.0,
519            tag = tag.0
520        );
521        match self {
522            AllocState::StackedBorrows(_sb) => interp_ok(()),
523            AllocState::TreeBorrows(tb) =>
524                tb.borrow_mut().release_protector(machine, global, tag, alloc_id),
525        }
526    }
527}
528
529impl VisitProvenance for AllocState {
530    fn visit_provenance(&self, visit: &mut VisitWith<'_>) {
531        let _trace = enter_trace_span!(borrow_tracker::visit_provenance);
532        match self {
533            AllocState::StackedBorrows(sb) => sb.visit_provenance(visit),
534            AllocState::TreeBorrows(tb) => tb.visit_provenance(visit),
535        }
536    }
537}
miri/borrow_tracker/mod.rs

miri/borrow_tracker/
mod.rs
