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/// 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    /// Next unused pointer ID (tag).
107    next_ptr_tag: BorTag,
108    /// Table storing the "root" tag for each allocation.
109    /// The root tag is the one used for the initial pointer.
110    /// We need this in a separate table to handle cyclic statics.
111    root_ptr_tags: FxHashMap<AllocId, BorTag>,
112    /// All currently protected tags.
113    /// We add tags to this when they are created with a protector in `reborrow`, and
114    /// we remove tags from this when the call which is protecting them returns, in
115    /// `GlobalStateInner::end_call`. See `Stack::item_invalidated` for more details.
116    protected_tags: FxHashMap<BorTag, ProtectorKind>,
117    /// The pointer ids to trace
118    tracked_pointer_tags: FxHashSet<BorTag>,
119    /// Whether to recurse into datatypes when searching for pointers to retag.
120    retag_fields: RetagFields,
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/// Policy on whether to recurse into fields to retag
135#[derive(Copy, Clone, Debug)]
136pub enum RetagFields {
137    /// Don't retag any fields.
138    No,
139    /// Retag all fields.
140    Yes,
141    /// Only retag fields of types with Scalar and ScalarPair layout,
142    /// to match the LLVM `noalias` we generate.
143    OnlyScalar,
144}
145
146/// The flavor of the protector.
147#[derive(Copy, Clone, Debug, PartialEq, Eq)]
148pub enum ProtectorKind {
149    /// Protected against aliasing violations from other pointers.
150    ///
151    /// Items protected like this cause UB when they are invalidated, *but* the pointer itself may
152    /// still be used to issue a deallocation.
153    ///
154    /// This is required for LLVM IR pointers that are `noalias` but *not* `dereferenceable`.
155    WeakProtector,
156
157    /// Protected against any kind of invalidation.
158    ///
159    /// Items protected like this cause UB when they are invalidated or the memory is deallocated.
160    /// This is strictly stronger protection than `WeakProtector`.
161    ///
162    /// This is required for LLVM IR pointers that are `dereferenceable` (and also allows `noalias`).
163    StrongProtector,
164}
165
166/// Utilities for initialization and ID generation
167impl GlobalStateInner {
168    pub fn new(
169        borrow_tracker_method: BorrowTrackerMethod,
170        tracked_pointer_tags: FxHashSet<BorTag>,
171        retag_fields: RetagFields,
172    ) -> Self {
173        GlobalStateInner {
174            borrow_tracker_method,
175            next_ptr_tag: BorTag::one(),
176            root_ptr_tags: FxHashMap::default(),
177            protected_tags: FxHashMap::default(),
178            tracked_pointer_tags,
179            retag_fields,
180        }
181    }
182
183    /// Generates a new pointer tag. Remember to also check track_pointer_tags and log its creation!
184    fn new_ptr(&mut self) -> BorTag {
185        let id = self.next_ptr_tag;
186        self.next_ptr_tag = id.succ().unwrap();
187        id
188    }
189
190    pub fn new_frame(&mut self) -> FrameState {
191        FrameState { protected_tags: SmallVec::new() }
192    }
193
194    fn end_call(&mut self, frame: &machine::FrameExtra<'_>) {
195        for (_, tag) in &frame
196            .borrow_tracker
197            .as_ref()
198            .expect("we should have borrow tracking data")
199            .protected_tags
200        {
201            self.protected_tags.remove(tag);
202        }
203    }
204
205    pub fn root_ptr_tag(&mut self, id: AllocId, machine: &MiriMachine<'_>) -> BorTag {
206        self.root_ptr_tags.get(&id).copied().unwrap_or_else(|| {
207            let tag = self.new_ptr();
208            if self.tracked_pointer_tags.contains(&tag) {
209                machine.emit_diagnostic(NonHaltingDiagnostic::CreatedPointerTag(
210                    tag.inner(),
211                    None,
212                    None,
213                ));
214            }
215            trace!("New allocation {:?} has rpot tag {:?}", id, tag);
216            self.root_ptr_tags.try_insert(id, tag).unwrap();
217            tag
218        })
219    }
220
221    pub fn remove_unreachable_allocs(&mut self, allocs: &LiveAllocs<'_, '_>) {
222        self.root_ptr_tags.retain(|id, _| allocs.is_live(*id));
223    }
224
225    pub fn borrow_tracker_method(&self) -> BorrowTrackerMethod {
226        self.borrow_tracker_method
227    }
228}
229
230/// Which borrow tracking method to use
231#[derive(Debug, Copy, Clone, PartialEq, Eq)]
232pub enum BorrowTrackerMethod {
233    /// Stacked Borrows, as implemented in borrow_tracker/stacked_borrows
234    StackedBorrows,
235    /// Tree borrows, as implemented in borrow_tracker/tree_borrows
236    TreeBorrows(TreeBorrowsParams),
237}
238
239/// Parameters that Tree Borrows can take.
240#[derive(Debug, Copy, Clone, PartialEq, Eq)]
241pub struct TreeBorrowsParams {
242    pub precise_interior_mut: bool,
243}
244
245impl BorrowTrackerMethod {
246    pub fn instantiate_global_state(self, config: &MiriConfig) -> GlobalState {
247        RefCell::new(GlobalStateInner::new(
248            self,
249            config.tracked_pointer_tags.clone(),
250            config.retag_fields,
251        ))
252    }
253
254    pub fn get_tree_borrows_params(self) -> TreeBorrowsParams {
255        match self {
256            BorrowTrackerMethod::TreeBorrows(params) => params,
257            _ => panic!("can only be called when `BorrowTrackerMethod` is `TreeBorrows`"),
258        }
259    }
260}
261
262impl GlobalStateInner {
263    pub fn new_allocation(
264        &mut self,
265        id: AllocId,
266        alloc_size: Size,
267        kind: MemoryKind,
268        machine: &MiriMachine<'_>,
269    ) -> AllocState {
270        let _trace = enter_trace_span!(borrow_tracker::new_allocation, ?id, ?alloc_size, ?kind);
271        match self.borrow_tracker_method {
272            BorrowTrackerMethod::StackedBorrows =>
273                AllocState::StackedBorrows(Box::new(RefCell::new(Stacks::new_allocation(
274                    id, alloc_size, self, kind, machine,
275                )))),
276            BorrowTrackerMethod::TreeBorrows { .. } =>
277                AllocState::TreeBorrows(Box::new(RefCell::new(Tree::new_allocation(
278                    id, alloc_size, self, kind, machine,
279                )))),
280        }
281    }
282}
283
284impl<'tcx> EvalContextExt<'tcx> for crate::MiriInterpCx<'tcx> {}
285pub trait EvalContextExt<'tcx>: crate::MiriInterpCxExt<'tcx> {
286    fn retag_ptr_value(
287        &mut self,
288        kind: RetagKind,
289        val: &ImmTy<'tcx>,
290    ) -> InterpResult<'tcx, ImmTy<'tcx>> {
291        let _trace = enter_trace_span!(borrow_tracker::retag_ptr_value, ?kind, ?val.layout);
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_retag_ptr_value(kind, val),
296            BorrowTrackerMethod::TreeBorrows { .. } => this.tb_retag_ptr_value(kind, val),
297        }
298    }
299
300    fn retag_place_contents(
301        &mut self,
302        kind: RetagKind,
303        place: &PlaceTy<'tcx>,
304    ) -> InterpResult<'tcx> {
305        let _trace = enter_trace_span!(borrow_tracker::retag_place_contents, ?kind, ?place);
306        let this = self.eval_context_mut();
307        let method = this.machine.borrow_tracker.as_ref().unwrap().borrow().borrow_tracker_method;
308        match method {
309            BorrowTrackerMethod::StackedBorrows => this.sb_retag_place_contents(kind, place),
310            BorrowTrackerMethod::TreeBorrows { .. } => this.tb_retag_place_contents(kind, place),
311        }
312    }
313
314    fn protect_place(&mut self, place: &MPlaceTy<'tcx>) -> InterpResult<'tcx, MPlaceTy<'tcx>> {
315        let _trace = enter_trace_span!(borrow_tracker::protect_place, ?place);
316        let this = self.eval_context_mut();
317        let method = this.machine.borrow_tracker.as_ref().unwrap().borrow().borrow_tracker_method;
318        match method {
319            BorrowTrackerMethod::StackedBorrows => this.sb_protect_place(place),
320            BorrowTrackerMethod::TreeBorrows { .. } => this.tb_protect_place(place),
321        }
322    }
323
324    fn expose_tag(&self, alloc_id: AllocId, tag: BorTag) -> InterpResult<'tcx> {
325        let _trace =
326            enter_trace_span!(borrow_tracker::expose_tag, alloc_id = alloc_id.0, tag = tag.0);
327        let this = self.eval_context_ref();
328        let method = this.machine.borrow_tracker.as_ref().unwrap().borrow().borrow_tracker_method;
329        match method {
330            BorrowTrackerMethod::StackedBorrows => this.sb_expose_tag(alloc_id, tag),
331            BorrowTrackerMethod::TreeBorrows { .. } => this.tb_expose_tag(alloc_id, tag),
332        }
333    }
334
335    fn give_pointer_debug_name(
336        &mut self,
337        ptr: Pointer,
338        nth_parent: u8,
339        name: &str,
340    ) -> InterpResult<'tcx> {
341        let this = self.eval_context_mut();
342        let method = this.machine.borrow_tracker.as_ref().unwrap().borrow().borrow_tracker_method;
343        match method {
344            BorrowTrackerMethod::StackedBorrows => {
345                this.tcx.tcx.dcx().warn("Stacked Borrows does not support named pointers; `miri_pointer_name` is a no-op");
346                interp_ok(())
347            }
348            BorrowTrackerMethod::TreeBorrows { .. } =>
349                this.tb_give_pointer_debug_name(ptr, nth_parent, name),
350        }
351    }
352
353    fn print_borrow_state(&mut self, alloc_id: AllocId, show_unnamed: bool) -> InterpResult<'tcx> {
354        let this = self.eval_context_mut();
355        let Some(borrow_tracker) = &this.machine.borrow_tracker else {
356            eprintln!("attempted to print borrow state, but no borrow state is being tracked");
357            return interp_ok(());
358        };
359        let method = borrow_tracker.borrow().borrow_tracker_method;
360        match method {
361            BorrowTrackerMethod::StackedBorrows => this.print_stacks(alloc_id),
362            BorrowTrackerMethod::TreeBorrows { .. } => this.print_tree(alloc_id, show_unnamed),
363        }
364    }
365
366    fn on_stack_pop(
367        &self,
368        frame: &Frame<'tcx, Provenance, FrameExtra<'tcx>>,
369    ) -> InterpResult<'tcx> {
370        let _trace = enter_trace_span!(borrow_tracker::on_stack_pop);
371        let this = self.eval_context_ref();
372        let borrow_tracker = this.machine.borrow_tracker.as_ref().unwrap();
373        // The body of this loop needs `borrow_tracker` immutably
374        // so we can't move this code inside the following `end_call`.
375        for (alloc_id, tag) in &frame
376            .extra
377            .borrow_tracker
378            .as_ref()
379            .expect("we should have borrow tracking data")
380            .protected_tags
381        {
382            // Just because the tag is protected doesn't guarantee that
383            // the allocation still exists (weak protectors allow deallocations)
384            // so we must check that the allocation exists.
385            // If it does exist, then we have the guarantee that the
386            // pointer is readable, and the implicit read access inserted
387            // will never cause UB on the pointer itself.
388            let kind = this.get_alloc_info(*alloc_id).kind;
389            if matches!(kind, AllocKind::LiveData) {
390                let alloc_extra = this.get_alloc_extra(*alloc_id)?; // can still fail for `extern static`
391                let alloc_borrow_tracker = &alloc_extra.borrow_tracker.as_ref().unwrap();
392                alloc_borrow_tracker.release_protector(
393                    &this.machine,
394                    borrow_tracker,
395                    *tag,
396                    *alloc_id,
397                )?;
398            }
399        }
400        borrow_tracker.borrow_mut().end_call(&frame.extra);
401        interp_ok(())
402    }
403}
404
405/// Extra per-allocation data for borrow tracking
406#[derive(Debug, Clone)]
407pub enum AllocState {
408    /// Data corresponding to Stacked Borrows
409    StackedBorrows(Box<RefCell<stacked_borrows::AllocState>>),
410    /// Data corresponding to Tree Borrows
411    TreeBorrows(Box<RefCell<tree_borrows::AllocState>>),
412}
413
414impl machine::AllocExtra<'_> {
415    #[track_caller]
416    pub fn borrow_tracker_sb(&self) -> &RefCell<stacked_borrows::AllocState> {
417        match self.borrow_tracker {
418            Some(AllocState::StackedBorrows(ref sb)) => sb,
419            _ => panic!("expected Stacked Borrows borrow tracking, got something else"),
420        }
421    }
422
423    #[track_caller]
424    pub fn borrow_tracker_sb_mut(&mut self) -> &mut RefCell<stacked_borrows::AllocState> {
425        match self.borrow_tracker {
426            Some(AllocState::StackedBorrows(ref mut sb)) => sb,
427            _ => panic!("expected Stacked Borrows borrow tracking, got something else"),
428        }
429    }
430
431    #[track_caller]
432    pub fn borrow_tracker_tb(&self) -> &RefCell<tree_borrows::AllocState> {
433        match self.borrow_tracker {
434            Some(AllocState::TreeBorrows(ref tb)) => tb,
435            _ => panic!("expected Tree Borrows borrow tracking, got something else"),
436        }
437    }
438}
439
440impl AllocState {
441    pub fn before_memory_read<'tcx>(
442        &self,
443        alloc_id: AllocId,
444        prov_extra: ProvenanceExtra,
445        range: AllocRange,
446        machine: &MiriMachine<'tcx>,
447    ) -> InterpResult<'tcx> {
448        let _trace = enter_trace_span!(borrow_tracker::before_memory_read, alloc_id = alloc_id.0);
449        match self {
450            AllocState::StackedBorrows(sb) =>
451                sb.borrow_mut().before_memory_read(alloc_id, prov_extra, range, machine),
452            AllocState::TreeBorrows(tb) =>
453                tb.borrow_mut().before_memory_access(
454                    AccessKind::Read,
455                    alloc_id,
456                    prov_extra,
457                    range,
458                    machine,
459                ),
460        }
461    }
462
463    pub fn before_memory_write<'tcx>(
464        &mut self,
465        alloc_id: AllocId,
466        prov_extra: ProvenanceExtra,
467        range: AllocRange,
468        machine: &MiriMachine<'tcx>,
469    ) -> InterpResult<'tcx> {
470        let _trace = enter_trace_span!(borrow_tracker::before_memory_write, alloc_id = alloc_id.0);
471        match self {
472            AllocState::StackedBorrows(sb) =>
473                sb.get_mut().before_memory_write(alloc_id, prov_extra, range, machine),
474            AllocState::TreeBorrows(tb) =>
475                tb.get_mut().before_memory_access(
476                    AccessKind::Write,
477                    alloc_id,
478                    prov_extra,
479                    range,
480                    machine,
481                ),
482        }
483    }
484
485    pub fn before_memory_deallocation<'tcx>(
486        &mut self,
487        alloc_id: AllocId,
488        prov_extra: ProvenanceExtra,
489        size: Size,
490        machine: &MiriMachine<'tcx>,
491    ) -> InterpResult<'tcx> {
492        let _trace =
493            enter_trace_span!(borrow_tracker::before_memory_deallocation, alloc_id = alloc_id.0);
494        match self {
495            AllocState::StackedBorrows(sb) =>
496                sb.get_mut().before_memory_deallocation(alloc_id, prov_extra, size, machine),
497            AllocState::TreeBorrows(tb) =>
498                tb.get_mut().before_memory_deallocation(alloc_id, prov_extra, size, machine),
499        }
500    }
501
502    pub fn remove_unreachable_tags(&self, tags: &FxHashSet<BorTag>) {
503        let _trace = enter_trace_span!(borrow_tracker::remove_unreachable_tags);
504        match self {
505            AllocState::StackedBorrows(sb) => sb.borrow_mut().remove_unreachable_tags(tags),
506            AllocState::TreeBorrows(tb) => tb.borrow_mut().remove_unreachable_tags(tags),
507        }
508    }
509
510    /// Tree Borrows needs to be told when a tag stops being protected.
511    pub fn release_protector<'tcx>(
512        &self,
513        machine: &MiriMachine<'tcx>,
514        global: &GlobalState,
515        tag: BorTag,
516        alloc_id: AllocId, // diagnostics
517    ) -> InterpResult<'tcx> {
518        let _trace = enter_trace_span!(
519            borrow_tracker::release_protector,
520            alloc_id = alloc_id.0,
521            tag = tag.0
522        );
523        match self {
524            AllocState::StackedBorrows(_sb) => interp_ok(()),
525            AllocState::TreeBorrows(tb) =>
526                tb.borrow_mut().release_protector(machine, global, tag, alloc_id),
527        }
528    }
529}
530
531impl VisitProvenance for AllocState {
532    fn visit_provenance(&self, visit: &mut VisitWith<'_>) {
533        let _trace = enter_trace_span!(borrow_tracker::visit_provenance);
534        match self {
535            AllocState::StackedBorrows(sb) => sb.visit_provenance(visit),
536            AllocState::TreeBorrows(tb) => tb.visit_provenance(visit),
537        }
538    }
539}
miri/borrow_tracker/mod.rs

miri/borrow_tracker/
mod.rs
