miri/borrow_tracker/
mod.rs

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

miri/borrow_tracker/
mod.rs
