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        let _trace = enter_trace_span!(borrow_tracker::new_allocation, ?id, ?alloc_size, ?kind);
264        match self.borrow_tracker_method {
265            BorrowTrackerMethod::StackedBorrows =>
266                AllocState::StackedBorrows(Box::new(RefCell::new(Stacks::new_allocation(
267                    id, alloc_size, self, kind, machine,
268                )))),
269            BorrowTrackerMethod::TreeBorrows { .. } =>
270                AllocState::TreeBorrows(Box::new(RefCell::new(Tree::new_allocation(
271                    id, alloc_size, self, kind, machine,
272                )))),
273        }
274    }
275}
276
277impl<'tcx> EvalContextExt<'tcx> for crate::MiriInterpCx<'tcx> {}
278pub trait EvalContextExt<'tcx>: crate::MiriInterpCxExt<'tcx> {
279    fn retag_ptr_value(
280        &mut self,
281        kind: RetagKind,
282        val: &ImmTy<'tcx>,
283    ) -> InterpResult<'tcx, ImmTy<'tcx>> {
284        let _trace = enter_trace_span!(borrow_tracker::retag_ptr_value, ?kind, ?val.layout);
285        let this = self.eval_context_mut();
286        let method = this.machine.borrow_tracker.as_ref().unwrap().borrow().borrow_tracker_method;
287        match method {
288            BorrowTrackerMethod::StackedBorrows => this.sb_retag_ptr_value(kind, val),
289            BorrowTrackerMethod::TreeBorrows { .. } => this.tb_retag_ptr_value(kind, val),
290        }
291    }
292
293    fn retag_place_contents(
294        &mut self,
295        kind: RetagKind,
296        place: &PlaceTy<'tcx>,
297    ) -> InterpResult<'tcx> {
298        let _trace = enter_trace_span!(borrow_tracker::retag_place_contents, ?kind, ?place);
299        let this = self.eval_context_mut();
300        let method = this.machine.borrow_tracker.as_ref().unwrap().borrow().borrow_tracker_method;
301        match method {
302            BorrowTrackerMethod::StackedBorrows => this.sb_retag_place_contents(kind, place),
303            BorrowTrackerMethod::TreeBorrows { .. } => this.tb_retag_place_contents(kind, place),
304        }
305    }
306
307    fn protect_place(&mut self, place: &MPlaceTy<'tcx>) -> InterpResult<'tcx, MPlaceTy<'tcx>> {
308        let _trace = enter_trace_span!(borrow_tracker::protect_place, ?place);
309        let this = self.eval_context_mut();
310        let method = this.machine.borrow_tracker.as_ref().unwrap().borrow().borrow_tracker_method;
311        match method {
312            BorrowTrackerMethod::StackedBorrows => this.sb_protect_place(place),
313            BorrowTrackerMethod::TreeBorrows { .. } => this.tb_protect_place(place),
314        }
315    }
316
317    fn expose_tag(&self, alloc_id: AllocId, tag: BorTag) -> InterpResult<'tcx> {
318        let _trace =
319            enter_trace_span!(borrow_tracker::expose_tag, alloc_id = alloc_id.0, tag = tag.0);
320        let this = self.eval_context_ref();
321        let method = this.machine.borrow_tracker.as_ref().unwrap().borrow().borrow_tracker_method;
322        match method {
323            BorrowTrackerMethod::StackedBorrows => this.sb_expose_tag(alloc_id, tag),
324            BorrowTrackerMethod::TreeBorrows { .. } => this.tb_expose_tag(alloc_id, tag),
325        }
326    }
327
328    fn give_pointer_debug_name(
329        &mut self,
330        ptr: Pointer,
331        nth_parent: u8,
332        name: &str,
333    ) -> InterpResult<'tcx> {
334        let this = self.eval_context_mut();
335        let method = this.machine.borrow_tracker.as_ref().unwrap().borrow().borrow_tracker_method;
336        match method {
337            BorrowTrackerMethod::StackedBorrows => {
338                this.tcx.tcx.dcx().warn("Stacked Borrows does not support named pointers; `miri_pointer_name` is a no-op");
339                interp_ok(())
340            }
341            BorrowTrackerMethod::TreeBorrows { .. } =>
342                this.tb_give_pointer_debug_name(ptr, nth_parent, name),
343        }
344    }
345
346    fn print_borrow_state(&mut self, alloc_id: AllocId, show_unnamed: bool) -> InterpResult<'tcx> {
347        let this = self.eval_context_mut();
348        let Some(borrow_tracker) = &this.machine.borrow_tracker else {
349            eprintln!("attempted to print borrow state, but no borrow state is being tracked");
350            return interp_ok(());
351        };
352        let method = borrow_tracker.borrow().borrow_tracker_method;
353        match method {
354            BorrowTrackerMethod::StackedBorrows => this.print_stacks(alloc_id),
355            BorrowTrackerMethod::TreeBorrows { .. } => this.print_tree(alloc_id, show_unnamed),
356        }
357    }
358
359    fn on_stack_pop(
360        &self,
361        frame: &Frame<'tcx, Provenance, FrameExtra<'tcx>>,
362    ) -> InterpResult<'tcx> {
363        let _trace = enter_trace_span!(borrow_tracker::on_stack_pop);
364        let this = self.eval_context_ref();
365        let borrow_tracker = this.machine.borrow_tracker.as_ref().unwrap();
366        // The body of this loop needs `borrow_tracker` immutably
367        // so we can't move this code inside the following `end_call`.
368        for (alloc_id, tag) in &frame
369            .extra
370            .borrow_tracker
371            .as_ref()
372            .expect("we should have borrow tracking data")
373            .protected_tags
374        {
375            // Just because the tag is protected doesn't guarantee that
376            // the allocation still exists (weak protectors allow deallocations)
377            // so we must check that the allocation exists.
378            // If it does exist, then we have the guarantee that the
379            // pointer is readable, and the implicit read access inserted
380            // will never cause UB on the pointer itself.
381            let kind = this.get_alloc_info(*alloc_id).kind;
382            if matches!(kind, AllocKind::LiveData) {
383                let alloc_extra = this.get_alloc_extra(*alloc_id)?; // can still fail for `extern static`
384                let alloc_borrow_tracker = &alloc_extra.borrow_tracker.as_ref().unwrap();
385                alloc_borrow_tracker.release_protector(
386                    &this.machine,
387                    borrow_tracker,
388                    *tag,
389                    *alloc_id,
390                )?;
391            }
392        }
393        borrow_tracker.borrow_mut().end_call(&frame.extra);
394        interp_ok(())
395    }
396}
397
398/// Extra per-allocation data for borrow tracking
399#[derive(Debug, Clone)]
400pub enum AllocState {
401    /// Data corresponding to Stacked Borrows
402    StackedBorrows(Box<RefCell<stacked_borrows::AllocState>>),
403    /// Data corresponding to Tree Borrows
404    TreeBorrows(Box<RefCell<tree_borrows::AllocState>>),
405}
406
407impl machine::AllocExtra<'_> {
408    #[track_caller]
409    pub fn borrow_tracker_sb(&self) -> &RefCell<stacked_borrows::AllocState> {
410        match self.borrow_tracker {
411            Some(AllocState::StackedBorrows(ref sb)) => sb,
412            _ => panic!("expected Stacked Borrows borrow tracking, got something else"),
413        }
414    }
415
416    #[track_caller]
417    pub fn borrow_tracker_sb_mut(&mut self) -> &mut RefCell<stacked_borrows::AllocState> {
418        match self.borrow_tracker {
419            Some(AllocState::StackedBorrows(ref mut sb)) => sb,
420            _ => panic!("expected Stacked Borrows borrow tracking, got something else"),
421        }
422    }
423
424    #[track_caller]
425    pub fn borrow_tracker_tb(&self) -> &RefCell<tree_borrows::AllocState> {
426        match self.borrow_tracker {
427            Some(AllocState::TreeBorrows(ref tb)) => tb,
428            _ => panic!("expected Tree Borrows borrow tracking, got something else"),
429        }
430    }
431}
432
433impl AllocState {
434    pub fn before_memory_read<'tcx>(
435        &self,
436        alloc_id: AllocId,
437        prov_extra: ProvenanceExtra,
438        range: AllocRange,
439        machine: &MiriMachine<'tcx>,
440    ) -> InterpResult<'tcx> {
441        let _trace = enter_trace_span!(borrow_tracker::before_memory_read, alloc_id = alloc_id.0);
442        match self {
443            AllocState::StackedBorrows(sb) =>
444                sb.borrow_mut().before_memory_read(alloc_id, prov_extra, range, machine),
445            AllocState::TreeBorrows(tb) =>
446                tb.borrow_mut().before_memory_access(
447                    AccessKind::Read,
448                    alloc_id,
449                    prov_extra,
450                    range,
451                    machine,
452                ),
453        }
454    }
455
456    pub fn before_memory_write<'tcx>(
457        &mut self,
458        alloc_id: AllocId,
459        prov_extra: ProvenanceExtra,
460        range: AllocRange,
461        machine: &MiriMachine<'tcx>,
462    ) -> InterpResult<'tcx> {
463        let _trace = enter_trace_span!(borrow_tracker::before_memory_write, alloc_id = alloc_id.0);
464        match self {
465            AllocState::StackedBorrows(sb) =>
466                sb.get_mut().before_memory_write(alloc_id, prov_extra, range, machine),
467            AllocState::TreeBorrows(tb) =>
468                tb.get_mut().before_memory_access(
469                    AccessKind::Write,
470                    alloc_id,
471                    prov_extra,
472                    range,
473                    machine,
474                ),
475        }
476    }
477
478    pub fn before_memory_deallocation<'tcx>(
479        &mut self,
480        alloc_id: AllocId,
481        prov_extra: ProvenanceExtra,
482        size: Size,
483        machine: &MiriMachine<'tcx>,
484    ) -> InterpResult<'tcx> {
485        let _trace =
486            enter_trace_span!(borrow_tracker::before_memory_deallocation, alloc_id = alloc_id.0);
487        match self {
488            AllocState::StackedBorrows(sb) =>
489                sb.get_mut().before_memory_deallocation(alloc_id, prov_extra, size, machine),
490            AllocState::TreeBorrows(tb) =>
491                tb.get_mut().before_memory_deallocation(alloc_id, prov_extra, size, machine),
492        }
493    }
494
495    pub fn remove_unreachable_tags(&self, tags: &FxHashSet<BorTag>) {
496        let _trace = enter_trace_span!(borrow_tracker::remove_unreachable_tags);
497        match self {
498            AllocState::StackedBorrows(sb) => sb.borrow_mut().remove_unreachable_tags(tags),
499            AllocState::TreeBorrows(tb) => tb.borrow_mut().remove_unreachable_tags(tags),
500        }
501    }
502
503    /// Tree Borrows needs to be told when a tag stops being protected.
504    pub fn release_protector<'tcx>(
505        &self,
506        machine: &MiriMachine<'tcx>,
507        global: &GlobalState,
508        tag: BorTag,
509        alloc_id: AllocId, // diagnostics
510    ) -> InterpResult<'tcx> {
511        let _trace = enter_trace_span!(
512            borrow_tracker::release_protector,
513            alloc_id = alloc_id.0,
514            tag = tag.0
515        );
516        match self {
517            AllocState::StackedBorrows(_sb) => interp_ok(()),
518            AllocState::TreeBorrows(tb) =>
519                tb.borrow_mut().release_protector(machine, global, tag, alloc_id),
520        }
521    }
522}
523
524impl VisitProvenance for AllocState {
525    fn visit_provenance(&self, visit: &mut VisitWith<'_>) {
526        let _trace = enter_trace_span!(borrow_tracker::visit_provenance);
527        match self {
528            AllocState::StackedBorrows(sb) => sb.visit_provenance(visit),
529            AllocState::TreeBorrows(tb) => tb.visit_provenance(visit),
530        }
531    }
532}
miri/borrow_tracker/mod.rs

miri/borrow_tracker/
mod.rs
