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