miri/borrow_tracker/
mod.rs

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