miri/borrow_tracker/tree_borrows/
tree.rs

1//! In this file we handle the "Tree" part of Tree Borrows, i.e. all tree
2//! traversal functions, optimizations to trim branches, and keeping track of
3//! the relative position of the access to each node being updated. This of course
4//! also includes the definition of the tree structure.
5//!
6//! Functions here manipulate permissions but are oblivious to them: as
7//! the internals of `Permission` are private, the update process is a black
8//! box. All we need to know here are
9//! - the fact that updates depend only on the old state, the status of protectors,
10//!   and the relative position of the access;
11//! - idempotency properties asserted in `perms.rs` (for optimizations)
12
13use std::ops::Range;
14use std::{cmp, fmt, mem};
15
16use rustc_abi::Size;
17use rustc_data_structures::fx::FxHashSet;
18use rustc_span::Span;
19use smallvec::SmallVec;
20
21use crate::borrow_tracker::tree_borrows::Permission;
22use crate::borrow_tracker::tree_borrows::diagnostics::{
23    self, NodeDebugInfo, TbError, TransitionError,
24};
25use crate::borrow_tracker::tree_borrows::foreign_access_skipping::IdempotentForeignAccess;
26use crate::borrow_tracker::tree_borrows::perms::PermTransition;
27use crate::borrow_tracker::tree_borrows::unimap::{UniEntry, UniIndex, UniKeyMap, UniValMap};
28use crate::borrow_tracker::{GlobalState, ProtectorKind};
29use crate::*;
30
31mod tests;
32
33/// Data for a single *location*.
34#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
35pub(super) struct LocationState {
36    /// A location is "accessed" when it is child-accessed for the first time (and the initial
37    /// retag initializes the location for the range covered by the type), and it then stays
38    /// accessed forever.
39    /// For accessed locations, "permission" is the current permission. However, for
40    /// non-accessed locations, we still need to track the "future initial permission": this will
41    /// start out to be `default_initial_perm`, but foreign accesses need to be taken into account.
42    /// Crucially however, while transitions to `Disabled` would usually be UB if this location is
43    /// protected, that is *not* the case for non-accessed locations. Instead we just have a latent
44    /// "future initial permission" of `Disabled`, causing UB only if an access is ever actually
45    /// performed.
46    /// Note that the tree root is also always accessed, as if the allocation was a write access.
47    accessed: bool,
48    /// This pointer's current permission / future initial permission.
49    permission: Permission,
50    /// See `foreign_access_skipping.rs`.
51    /// Stores an idempotent foreign access for this location and its children.
52    /// For correctness, this must not be too strong, and the recorded idempotent foreign access
53    /// of all children must be at least as strong as this. For performance, it should be as strong as possible.
54    idempotent_foreign_access: IdempotentForeignAccess,
55}
56
57impl LocationState {
58    /// Constructs a new initial state. It has neither been accessed, nor been subjected
59    /// to any foreign access yet.
60    /// The permission is not allowed to be `Unique`.
61    /// `sifa` is the (strongest) idempotent foreign access, see `foreign_access_skipping.rs`
62    pub fn new_non_accessed(permission: Permission, sifa: IdempotentForeignAccess) -> Self {
63        assert!(permission.is_initial() || permission.is_disabled());
64        Self { permission, accessed: false, idempotent_foreign_access: sifa }
65    }
66
67    /// Constructs a new initial state. It has not yet been subjected
68    /// to any foreign access. However, it is already marked as having been accessed.
69    /// `sifa` is the (strongest) idempotent foreign access, see `foreign_access_skipping.rs`
70    pub fn new_accessed(permission: Permission, sifa: IdempotentForeignAccess) -> Self {
71        Self { permission, accessed: true, idempotent_foreign_access: sifa }
72    }
73
74    /// Check if the location has been accessed, i.e. if it has
75    /// ever been accessed through a child pointer.
76    pub fn accessed(&self) -> bool {
77        self.accessed
78    }
79
80    pub fn permission(&self) -> Permission {
81        self.permission
82    }
83
84    /// Apply the effect of an access to one location, including
85    /// - applying `Permission::perform_access` to the inner `Permission`,
86    /// - emitting protector UB if the location is accessed,
87    /// - updating the accessed status (child accesses produce accessed locations).
88    fn perform_access(
89        &mut self,
90        access_kind: AccessKind,
91        rel_pos: AccessRelatedness,
92        protected: bool,
93    ) -> Result<PermTransition, TransitionError> {
94        let old_perm = self.permission;
95        let transition = Permission::perform_access(access_kind, rel_pos, old_perm, protected)
96            .ok_or(TransitionError::ChildAccessForbidden(old_perm))?;
97        self.accessed |= !rel_pos.is_foreign();
98        self.permission = transition.applied(old_perm).unwrap();
99        // Why do only accessed locations cause protector errors?
100        // Consider two mutable references `x`, `y` into disjoint parts of
101        // the same allocation. A priori, these may actually both be used to
102        // access the entire allocation, as long as only reads occur. However,
103        // a write to `y` needs to somehow record that `x` can no longer be used
104        // on that location at all. For these non-accessed locations (i.e., locations
105        // that haven't been accessed with `x` yet), we track the "future initial state":
106        // it defaults to whatever the initial state of the tag is,
107        // but the access to `y` moves that "future initial state" of `x` to `Disabled`.
108        // However, usually a `Reserved -> Disabled` transition would be UB due to the protector!
109        // So clearly protectors shouldn't fire for such "future initial state" transitions.
110        //
111        // See the test `two_mut_protected_same_alloc` in `tests/pass/tree_borrows/tree-borrows.rs`
112        // for an example of safe code that would be UB if we forgot to check `self.accessed`.
113        if protected && self.accessed && transition.produces_disabled() {
114            return Err(TransitionError::ProtectedDisabled(old_perm));
115        }
116        Ok(transition)
117    }
118
119    /// Like `perform_access`, but ignores the concrete error cause and also uses state-passing
120    /// rather than a mutable reference. As such, it returns `Some(x)` if the transition succeeded,
121    /// or `None` if there was an error.
122    #[cfg(test)]
123    fn perform_access_no_fluff(
124        mut self,
125        access_kind: AccessKind,
126        rel_pos: AccessRelatedness,
127        protected: bool,
128    ) -> Option<Self> {
129        match self.perform_access(access_kind, rel_pos, protected) {
130            Ok(_) => Some(self),
131            Err(_) => None,
132        }
133    }
134
135    /// Tree traversal optimizations. See `foreign_access_skipping.rs`.
136    /// This checks if such a foreign access can be skipped.
137    fn skip_if_known_noop(
138        &self,
139        access_kind: AccessKind,
140        rel_pos: AccessRelatedness,
141    ) -> ContinueTraversal {
142        if rel_pos.is_foreign() {
143            let happening_now = IdempotentForeignAccess::from_foreign(access_kind);
144            let mut new_access_noop =
145                self.idempotent_foreign_access.can_skip_foreign_access(happening_now);
146            if self.permission.is_disabled() {
147                // A foreign access to a `Disabled` tag will have almost no observable effect.
148                // It's a theorem that `Disabled` node have no protected accessed children,
149                // and so this foreign access will never trigger any protector.
150                // (Intuition: You're either protected accessed, and thus can't become Disabled
151                // or you're already Disabled protected, but not accessed, and then can't
152                // become accessed since that requires a child access, which Disabled blocks.)
153                // Further, the children will never be able to read or write again, since they
154                // have a `Disabled` parent. So this only affects diagnostics, such that the
155                // blocking write will still be identified directly, just at a different tag.
156                new_access_noop = true;
157            }
158            if self.permission.is_frozen() && access_kind == AccessKind::Read {
159                // A foreign read to a `Frozen` tag will have almost no observable effect.
160                // It's a theorem that `Frozen` nodes have no `Unique` children, so all children
161                // already survive foreign reads. Foreign reads in general have almost no
162                // effect, the only further thing they could do is make protected `Reserved`
163                // nodes become conflicted, i.e. make them reject child writes for the further
164                // duration of their protector. But such a child write is already rejected
165                // because this node is frozen. So this only affects diagnostics, but the
166                // blocking read will still be identified directly, just at a different tag.
167                new_access_noop = true;
168            }
169            if new_access_noop {
170                // Abort traversal if the new access is indeed guaranteed
171                // to be noop.
172                // No need to update `self.idempotent_foreign_access`,
173                // the type of the current streak among nonempty read-only
174                // or nonempty with at least one write has not changed.
175                ContinueTraversal::SkipSelfAndChildren
176            } else {
177                // Otherwise propagate this time, and also record the
178                // access that just occurred so that we can skip the propagation
179                // next time.
180                ContinueTraversal::Recurse
181            }
182        } else {
183            // A child access occurred, this breaks the streak of foreign
184            // accesses in a row and the sequence since the previous child access
185            // is now empty.
186            ContinueTraversal::Recurse
187        }
188    }
189
190    /// Records a new access, so that future access can potentially be skipped
191    /// by `skip_if_known_noop`. This must be called on child accesses, and otherwise
192    /// shoud be called on foreign accesses for increased performance. It should not be called
193    /// when `skip_if_known_noop` indicated skipping, since it then is a no-op.
194    /// See `foreign_access_skipping.rs`
195    fn record_new_access(&mut self, access_kind: AccessKind, rel_pos: AccessRelatedness) {
196        debug_assert!(matches!(
197            self.skip_if_known_noop(access_kind, rel_pos),
198            ContinueTraversal::Recurse
199        ));
200        self.idempotent_foreign_access
201            .record_new(IdempotentForeignAccess::from_acc_and_rel(access_kind, rel_pos));
202    }
203}
204
205impl fmt::Display for LocationState {
206    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
207        write!(f, "{}", self.permission)?;
208        if !self.accessed {
209            write!(f, "?")?;
210        }
211        Ok(())
212    }
213}
214
215/// Tree structure with both parents and children since we want to be
216/// able to traverse the tree efficiently in both directions.
217#[derive(Clone, Debug)]
218pub struct Tree {
219    /// Mapping from tags to keys. The key obtained can then be used in
220    /// any of the `UniValMap` relative to this allocation, i.e. both the
221    /// `nodes` and `rperms` of the same `Tree`.
222    /// The parent-child relationship in `Node` is encoded in terms of these same
223    /// keys, so traversing the entire tree needs exactly one access to
224    /// `tag_mapping`.
225    pub(super) tag_mapping: UniKeyMap<BorTag>,
226    /// All nodes of this tree.
227    pub(super) nodes: UniValMap<Node>,
228    /// Maps a tag and a location to a perm, with possible lazy
229    /// initialization.
230    ///
231    /// NOTE: not all tags registered in `nodes` are necessarily in all
232    /// ranges of `rperms`, because `rperms` is in part lazily initialized.
233    /// Just because `nodes.get(key)` is `Some(_)` does not mean you can safely
234    /// `unwrap` any `perm.get(key)`.
235    ///
236    /// We do uphold the fact that `keys(perms)` is a subset of `keys(nodes)`
237    pub(super) rperms: DedupRangeMap<UniValMap<LocationState>>,
238    /// The index of the root node.
239    pub(super) root: UniIndex,
240}
241
242/// A node in the borrow tree. Each node is uniquely identified by a tag via
243/// the `nodes` map of `Tree`.
244#[derive(Clone, Debug)]
245pub(super) struct Node {
246    /// The tag of this node.
247    pub tag: BorTag,
248    /// All tags except the root have a parent tag.
249    pub parent: Option<UniIndex>,
250    /// If the pointer was reborrowed, it has children.
251    // FIXME: bench to compare this to FxHashSet and to other SmallVec sizes
252    pub children: SmallVec<[UniIndex; 4]>,
253    /// Either `Reserved`,  `Frozen`, or `Disabled`, it is the permission this tag will
254    /// lazily be initialized to on the first access.
255    /// It is only ever `Disabled` for a tree root, since the root is initialized to `Unique` by
256    /// its own separate mechanism.
257    default_initial_perm: Permission,
258    /// The default initial (strongest) idempotent foreign access.
259    /// This participates in the invariant for `LocationState::idempotent_foreign_access`
260    /// in cases where there is no location state yet. See `foreign_access_skipping.rs`,
261    /// and `LocationState::idempotent_foreign_access` for more information
262    default_initial_idempotent_foreign_access: IdempotentForeignAccess,
263    /// Some extra information useful only for debugging purposes
264    pub debug_info: NodeDebugInfo,
265}
266
267/// Data given to the transition function
268struct NodeAppArgs<'node> {
269    /// Node on which the transition is currently being applied
270    node: &'node mut Node,
271    /// Mutable access to its permissions
272    perm: UniEntry<'node, LocationState>,
273    /// Relative position of the access
274    rel_pos: AccessRelatedness,
275}
276/// Data given to the error handler
277struct ErrHandlerArgs<'node, InErr> {
278    /// Kind of error that occurred
279    error_kind: InErr,
280    /// Tag that triggered the error (not the tag that was accessed,
281    /// rather the parent tag that had insufficient permissions or the
282    /// non-parent tag that had a protector).
283    conflicting_info: &'node NodeDebugInfo,
284    /// Information about the tag that was accessed just before the
285    /// error was triggered.
286    accessed_info: &'node NodeDebugInfo,
287}
288/// Internal contents of `Tree` with the minimum of mutable access for
289/// the purposes of the tree traversal functions: the permissions (`perms`) can be
290/// updated but not the tree structure (`tag_mapping` and `nodes`)
291struct TreeVisitor<'tree> {
292    tag_mapping: &'tree UniKeyMap<BorTag>,
293    nodes: &'tree mut UniValMap<Node>,
294    perms: &'tree mut UniValMap<LocationState>,
295}
296
297/// Whether to continue exploring the children recursively or not.
298enum ContinueTraversal {
299    Recurse,
300    SkipSelfAndChildren,
301}
302
303#[derive(Clone, Copy)]
304pub enum ChildrenVisitMode {
305    VisitChildrenOfAccessed,
306    SkipChildrenOfAccessed,
307}
308
309enum RecursionState {
310    BeforeChildren,
311    AfterChildren,
312}
313
314/// Stack of nodes left to explore in a tree traversal.
315/// See the docs of `traverse_this_parents_children_other` for details on the
316/// traversal order.
317struct TreeVisitorStack<NodeContinue, NodeApp, ErrHandler> {
318    /// Identifier of the original access.
319    initial: UniIndex,
320    /// Function describing whether to continue at a tag.
321    /// This is only invoked for foreign accesses.
322    f_continue: NodeContinue,
323    /// Function to apply to each tag.
324    f_propagate: NodeApp,
325    /// Handler to add the required context to diagnostics.
326    err_builder: ErrHandler,
327    /// Mutable state of the visit: the tags left to handle.
328    /// Every tag pushed should eventually be handled,
329    /// and the precise order is relevant for diagnostics.
330    /// Since the traversal is piecewise bottom-up, we need to
331    /// remember whether we're here initially, or after visiting all children.
332    /// The last element indicates this.
333    /// This is just an artifact of how you hand-roll recursion,
334    /// it does not have a deeper meaning otherwise.
335    stack: Vec<(UniIndex, AccessRelatedness, RecursionState)>,
336}
337
338impl<NodeContinue, NodeApp, InnErr, OutErr, ErrHandler>
339    TreeVisitorStack<NodeContinue, NodeApp, ErrHandler>
340where
341    NodeContinue: Fn(&NodeAppArgs<'_>) -> ContinueTraversal,
342    NodeApp: Fn(NodeAppArgs<'_>) -> Result<(), InnErr>,
343    ErrHandler: Fn(ErrHandlerArgs<'_, InnErr>) -> OutErr,
344{
345    fn should_continue_at(
346        &self,
347        this: &mut TreeVisitor<'_>,
348        idx: UniIndex,
349        rel_pos: AccessRelatedness,
350    ) -> ContinueTraversal {
351        let node = this.nodes.get_mut(idx).unwrap();
352        let args = NodeAppArgs { node, perm: this.perms.entry(idx), rel_pos };
353        (self.f_continue)(&args)
354    }
355
356    fn propagate_at(
357        &mut self,
358        this: &mut TreeVisitor<'_>,
359        idx: UniIndex,
360        rel_pos: AccessRelatedness,
361    ) -> Result<(), OutErr> {
362        let node = this.nodes.get_mut(idx).unwrap();
363        (self.f_propagate)(NodeAppArgs { node, perm: this.perms.entry(idx), rel_pos }).map_err(
364            |error_kind| {
365                (self.err_builder)(ErrHandlerArgs {
366                    error_kind,
367                    conflicting_info: &this.nodes.get(idx).unwrap().debug_info,
368                    accessed_info: &this.nodes.get(self.initial).unwrap().debug_info,
369                })
370            },
371        )
372    }
373
374    fn go_upwards_from_accessed(
375        &mut self,
376        this: &mut TreeVisitor<'_>,
377        accessed_node: UniIndex,
378        visit_children: ChildrenVisitMode,
379    ) -> Result<(), OutErr> {
380        // We want to visit the accessed node's children first.
381        // However, we will below walk up our parents and push their children (our cousins)
382        // onto the stack. To ensure correct iteration order, this method thus finishes
383        // by reversing the stack. This only works if the stack is empty initially.
384        assert!(self.stack.is_empty());
385        // First, handle accessed node. A bunch of things need to
386        // be handled differently here compared to the further parents
387        // of `accesssed_node`.
388        {
389            self.propagate_at(this, accessed_node, AccessRelatedness::This)?;
390            if matches!(visit_children, ChildrenVisitMode::VisitChildrenOfAccessed) {
391                let accessed_node = this.nodes.get(accessed_node).unwrap();
392                // We `rev()` here because we reverse the entire stack later.
393                for &child in accessed_node.children.iter().rev() {
394                    self.stack.push((
395                        child,
396                        AccessRelatedness::AncestorAccess,
397                        RecursionState::BeforeChildren,
398                    ));
399                }
400            }
401        }
402        // Then, handle the accessed node's parents. Here, we need to
403        // make sure we only mark the "cousin" subtrees for later visitation,
404        // not the subtree that contains the accessed node.
405        let mut last_node = accessed_node;
406        while let Some(current) = this.nodes.get(last_node).unwrap().parent {
407            self.propagate_at(this, current, AccessRelatedness::StrictChildAccess)?;
408            let node = this.nodes.get(current).unwrap();
409            // We `rev()` here because we reverse the entire stack later.
410            for &child in node.children.iter().rev() {
411                if last_node == child {
412                    continue;
413                }
414                self.stack.push((
415                    child,
416                    AccessRelatedness::CousinAccess,
417                    RecursionState::BeforeChildren,
418                ));
419            }
420            last_node = current;
421        }
422        // Reverse the stack, as discussed above.
423        self.stack.reverse();
424        Ok(())
425    }
426
427    fn finish_foreign_accesses(&mut self, this: &mut TreeVisitor<'_>) -> Result<(), OutErr> {
428        while let Some((idx, rel_pos, step)) = self.stack.last_mut() {
429            let idx = *idx;
430            let rel_pos = *rel_pos;
431            match *step {
432                // How to do bottom-up traversal, 101: Before you handle a node, you handle all children.
433                // For this, you must first find the children, which is what this code here does.
434                RecursionState::BeforeChildren => {
435                    // Next time we come back will be when all the children are handled.
436                    *step = RecursionState::AfterChildren;
437                    // Now push the children, except if we are told to skip this subtree.
438                    let handle_children = self.should_continue_at(this, idx, rel_pos);
439                    match handle_children {
440                        ContinueTraversal::Recurse => {
441                            let node = this.nodes.get(idx).unwrap();
442                            for &child in node.children.iter() {
443                                self.stack.push((child, rel_pos, RecursionState::BeforeChildren));
444                            }
445                        }
446                        ContinueTraversal::SkipSelfAndChildren => {
447                            // skip self
448                            self.stack.pop();
449                            continue;
450                        }
451                    }
452                }
453                // All the children are handled, let's actually visit this node
454                RecursionState::AfterChildren => {
455                    self.stack.pop();
456                    self.propagate_at(this, idx, rel_pos)?;
457                }
458            }
459        }
460        Ok(())
461    }
462
463    fn new(
464        initial: UniIndex,
465        f_continue: NodeContinue,
466        f_propagate: NodeApp,
467        err_builder: ErrHandler,
468    ) -> Self {
469        Self { initial, f_continue, f_propagate, err_builder, stack: Vec::new() }
470    }
471}
472
473impl<'tree> TreeVisitor<'tree> {
474    /// Applies `f_propagate` to every vertex of the tree in a piecewise bottom-up way: First, visit
475    /// all ancestors of `start` (starting with `start` itself), then children of `start`, then the rest,
476    /// going bottom-up in each of these two "pieces" / sections.
477    /// This ensures that errors are triggered in the following order
478    /// - first invalid accesses with insufficient permissions, closest to the accessed node first,
479    /// - then protector violations, bottom-up, starting with the children of the accessed node, and then
480    ///   going upwards and outwards.
481    ///
482    /// The following graphic visualizes it, with numbers indicating visitation order and `start` being
483    /// the node that is visited first ("1"):
484    ///
485    /// ```text
486    ///         3
487    ///        /|
488    ///       / |
489    ///      9  2
490    ///      |  |\
491    ///      |  | \
492    ///      8  1  7
493    ///        / \
494    ///       4   6
495    ///           |
496    ///           5
497    /// ```
498    ///
499    /// `f_propagate` should follow the following format: for a given `Node` it updates its
500    /// `Permission` depending on the position relative to `start` (given by an
501    /// `AccessRelatedness`).
502    /// `f_continue` is called earlier on foreign nodes, and describes whether to even start
503    /// visiting the subtree at that node. If it e.g. returns `SkipSelfAndChildren` on node 6
504    /// above, then nodes 5 _and_ 6 would not be visited by `f_propagate`. It is not used for
505    /// notes having a child access (nodes 1, 2, 3).
506    ///
507    /// Finally, remember that the iteration order is not relevant for UB, it only affects
508    /// diagnostics. It also affects tree traversal optimizations built on top of this, so
509    /// those need to be reviewed carefully as well whenever this changes.
510    fn traverse_this_parents_children_other<InnErr, OutErr>(
511        mut self,
512        start: BorTag,
513        f_continue: impl Fn(&NodeAppArgs<'_>) -> ContinueTraversal,
514        f_propagate: impl Fn(NodeAppArgs<'_>) -> Result<(), InnErr>,
515        err_builder: impl Fn(ErrHandlerArgs<'_, InnErr>) -> OutErr,
516    ) -> Result<(), OutErr> {
517        let start_idx = self.tag_mapping.get(&start).unwrap();
518        let mut stack = TreeVisitorStack::new(start_idx, f_continue, f_propagate, err_builder);
519        // Visits the accessed node itself, and all its parents, i.e. all nodes
520        // undergoing a child access. Also pushes the children and the other
521        // cousin nodes (i.e. all nodes undergoing a foreign access) to the stack
522        // to be processed later.
523        stack.go_upwards_from_accessed(
524            &mut self,
525            start_idx,
526            ChildrenVisitMode::VisitChildrenOfAccessed,
527        )?;
528        // Now visit all the foreign nodes we remembered earlier.
529        // For this we go bottom-up, but also allow f_continue to skip entire
530        // subtrees from being visited if it would be a NOP.
531        stack.finish_foreign_accesses(&mut self)
532    }
533
534    /// Like `traverse_this_parents_children_other`, but skips the children of `start`.
535    fn traverse_nonchildren<InnErr, OutErr>(
536        mut self,
537        start: BorTag,
538        f_continue: impl Fn(&NodeAppArgs<'_>) -> ContinueTraversal,
539        f_propagate: impl Fn(NodeAppArgs<'_>) -> Result<(), InnErr>,
540        err_builder: impl Fn(ErrHandlerArgs<'_, InnErr>) -> OutErr,
541    ) -> Result<(), OutErr> {
542        let start_idx = self.tag_mapping.get(&start).unwrap();
543        let mut stack = TreeVisitorStack::new(start_idx, f_continue, f_propagate, err_builder);
544        // Visits the accessed node itself, and all its parents, i.e. all nodes
545        // undergoing a child access. Also pushes the other cousin nodes to the
546        // stack, but not the children of the accessed node.
547        stack.go_upwards_from_accessed(
548            &mut self,
549            start_idx,
550            ChildrenVisitMode::SkipChildrenOfAccessed,
551        )?;
552        // Now visit all the foreign nodes we remembered earlier.
553        // For this we go bottom-up, but also allow f_continue to skip entire
554        // subtrees from being visited if it would be a NOP.
555        stack.finish_foreign_accesses(&mut self)
556    }
557}
558
559impl Tree {
560    /// Create a new tree, with only a root pointer.
561    pub fn new(root_tag: BorTag, size: Size, span: Span) -> Self {
562        // The root has `Disabled` as the default permission,
563        // so that any access out of bounds is invalid.
564        let root_default_perm = Permission::new_disabled();
565        let mut tag_mapping = UniKeyMap::default();
566        let root_idx = tag_mapping.insert(root_tag);
567        let nodes = {
568            let mut nodes = UniValMap::<Node>::default();
569            let mut debug_info = NodeDebugInfo::new(root_tag, root_default_perm, span);
570            // name the root so that all allocations contain one named pointer
571            debug_info.add_name("root of the allocation");
572            nodes.insert(
573                root_idx,
574                Node {
575                    tag: root_tag,
576                    parent: None,
577                    children: SmallVec::default(),
578                    default_initial_perm: root_default_perm,
579                    // The root may never be skipped, all accesses will be local.
580                    default_initial_idempotent_foreign_access: IdempotentForeignAccess::None,
581                    debug_info,
582                },
583            );
584            nodes
585        };
586        let rperms = {
587            let mut perms = UniValMap::default();
588            // We manually set it to `Unique` on all in-bounds positions.
589            // We also ensure that it is accessed, so that no `Unique` but
590            // not yet accessed nodes exist. Essentially, we pretend there
591            // was a write that initialized these to `Unique`.
592            perms.insert(
593                root_idx,
594                LocationState::new_accessed(
595                    Permission::new_unique(),
596                    IdempotentForeignAccess::None,
597                ),
598            );
599            DedupRangeMap::new(size, perms)
600        };
601        Self { root: root_idx, nodes, rperms, tag_mapping }
602    }
603}
604
605impl<'tcx> Tree {
606    /// Insert a new tag in the tree.
607    ///
608    /// `inside_perm` defines the initial permissions for a block of memory starting at
609    /// `base_offset`. These may nor may not be already marked as "accessed".
610    /// `outside_perm` defines the initial permission for the rest of the allocation.
611    /// These are definitely not "accessed".
612    pub(super) fn new_child(
613        &mut self,
614        base_offset: Size,
615        parent_tag: BorTag,
616        new_tag: BorTag,
617        inside_perms: DedupRangeMap<LocationState>,
618        outside_perm: Permission,
619        protected: bool,
620        span: Span,
621    ) -> InterpResult<'tcx> {
622        let idx = self.tag_mapping.insert(new_tag);
623        let parent_idx = self.tag_mapping.get(&parent_tag).unwrap();
624        assert!(outside_perm.is_initial());
625
626        let default_strongest_idempotent =
627            outside_perm.strongest_idempotent_foreign_access(protected);
628        // Create the node
629        self.nodes.insert(
630            idx,
631            Node {
632                tag: new_tag,
633                parent: Some(parent_idx),
634                children: SmallVec::default(),
635                default_initial_perm: outside_perm,
636                default_initial_idempotent_foreign_access: default_strongest_idempotent,
637                debug_info: NodeDebugInfo::new(new_tag, outside_perm, span),
638            },
639        );
640        // Register new_tag as a child of parent_tag
641        self.nodes.get_mut(parent_idx).unwrap().children.push(idx);
642
643        // We need to know the weakest SIFA for `update_idempotent_foreign_access_after_retag`.
644        let mut min_sifa = default_strongest_idempotent;
645        for (Range { start, end }, &perm) in
646            inside_perms.iter(Size::from_bytes(0), inside_perms.size())
647        {
648            assert!(perm.permission.is_initial());
649            assert_eq!(
650                perm.idempotent_foreign_access,
651                perm.permission.strongest_idempotent_foreign_access(protected)
652            );
653
654            min_sifa = cmp::min(min_sifa, perm.idempotent_foreign_access);
655            for (_perms_range, perms) in self
656                .rperms
657                .iter_mut(Size::from_bytes(start) + base_offset, Size::from_bytes(end - start))
658            {
659                perms.insert(idx, perm);
660            }
661        }
662
663        // Inserting the new perms might have broken the SIFA invariant (see
664        // `foreign_access_skipping.rs`) if the SIFA we inserted is weaker than that of some parent.
665        // We now weaken the recorded SIFA for our parents, until the invariant is restored. We
666        // could weaken them all to `None`, but it is more efficient to compute the SIFA for the new
667        // permission statically, and use that. For this we need the *minimum* SIFA (`None` needs
668        // more fixup than `Write`).
669        self.update_idempotent_foreign_access_after_retag(parent_idx, min_sifa);
670
671        interp_ok(())
672    }
673
674    /// Restores the SIFA "children are stronger"/"parents are weaker" invariant after a retag:
675    /// reduce the SIFA of `current` and its parents to be no stronger than `strongest_allowed`.
676    /// See `foreign_access_skipping.rs` and [`Tree::new_child`].
677    fn update_idempotent_foreign_access_after_retag(
678        &mut self,
679        mut current: UniIndex,
680        strongest_allowed: IdempotentForeignAccess,
681    ) {
682        if strongest_allowed == IdempotentForeignAccess::Write {
683            // Nothing is stronger than `Write`.
684            return;
685        }
686        // We walk the tree upwards, until the invariant is restored
687        loop {
688            let current_node = self.nodes.get_mut(current).unwrap();
689            // Call `ensure_no_stronger_than` on all SIFAs for this node: the per-location SIFA, as well
690            // as the default SIFA for not-yet-initialized locations.
691            // Record whether we did any change; if not, the invariant is restored and we can stop the traversal.
692            let mut any_change = false;
693            for (_, map) in self.rperms.iter_mut_all() {
694                // Check if this node has a state for this location (or range of locations).
695                if let Some(perm) = map.get_mut(current) {
696                    // Update the per-location SIFA, recording if it changed.
697                    any_change |=
698                        perm.idempotent_foreign_access.ensure_no_stronger_than(strongest_allowed);
699                }
700            }
701            // Now update `default_initial_idempotent_foreign_access`, which stores the default SIFA for not-yet-initialized locations.
702            any_change |= current_node
703                .default_initial_idempotent_foreign_access
704                .ensure_no_stronger_than(strongest_allowed);
705
706            if any_change {
707                let Some(next) = self.nodes.get(current).unwrap().parent else {
708                    // We have arrived at the root.
709                    break;
710                };
711                current = next;
712                continue;
713            } else {
714                break;
715            }
716        }
717    }
718
719    /// Deallocation requires
720    /// - a pointer that permits write accesses
721    /// - the absence of Strong Protectors anywhere in the allocation
722    pub fn dealloc(
723        &mut self,
724        tag: BorTag,
725        access_range: AllocRange,
726        global: &GlobalState,
727        alloc_id: AllocId, // diagnostics
728        span: Span,        // diagnostics
729    ) -> InterpResult<'tcx> {
730        self.perform_access(
731            tag,
732            Some((access_range, AccessKind::Write, diagnostics::AccessCause::Dealloc)),
733            global,
734            alloc_id,
735            span,
736        )?;
737        for (perms_range, perms) in self.rperms.iter_mut(access_range.start, access_range.size) {
738            TreeVisitor { nodes: &mut self.nodes, tag_mapping: &self.tag_mapping, perms }
739                .traverse_this_parents_children_other(
740                    tag,
741                    // visit all children, skipping none
742                    |_| ContinueTraversal::Recurse,
743                    |args: NodeAppArgs<'_>| -> Result<(), TransitionError> {
744                        let NodeAppArgs { node, perm, .. } = args;
745                        let perm =
746                            perm.get().copied().unwrap_or_else(|| node.default_location_state());
747                        if global.borrow().protected_tags.get(&node.tag)
748                            == Some(&ProtectorKind::StrongProtector)
749                            // Don't check for protector if it is a Cell (see `unsafe_cell_deallocate` in `interior_mutability.rs`).
750                            // Related to https://github.com/rust-lang/rust/issues/55005.
751                            && !perm.permission.is_cell()
752                            // Only trigger UB if the accessed bit is set, i.e. if the protector is actually protecting this offset. See #4579.
753                            && perm.accessed
754                        {
755                            Err(TransitionError::ProtectedDealloc)
756                        } else {
757                            Ok(())
758                        }
759                    },
760                    |args: ErrHandlerArgs<'_, TransitionError>| -> InterpErrorKind<'tcx> {
761                        let ErrHandlerArgs { error_kind, conflicting_info, accessed_info } = args;
762                        TbError {
763                            conflicting_info,
764                            access_cause: diagnostics::AccessCause::Dealloc,
765                            alloc_id,
766                            error_offset: perms_range.start,
767                            error_kind,
768                            accessed_info,
769                        }
770                        .build()
771                    },
772                )?;
773        }
774        interp_ok(())
775    }
776
777    /// Map the per-node and per-location `LocationState::perform_access`
778    /// to each location of the first component of `access_range_and_kind`,
779    /// on every tag of the allocation.
780    ///
781    /// If `access_range_and_kind` is `None`, this is interpreted as the special
782    /// access that is applied on protector release:
783    /// - the access will be applied only to accessed locations of the allocation,
784    /// - it will not be visible to children,
785    /// - it will be recorded as a `FnExit` diagnostic access
786    /// - and it will be a read except if the location is `Unique`, i.e. has been written to,
787    ///   in which case it will be a write.
788    ///
789    /// `LocationState::perform_access` will take care of raising transition
790    /// errors and updating the `accessed` status of each location,
791    /// this traversal adds to that:
792    /// - inserting into the map locations that do not exist yet,
793    /// - trimming the traversal,
794    /// - recording the history.
795    pub fn perform_access(
796        &mut self,
797        tag: BorTag,
798        access_range_and_kind: Option<(AllocRange, AccessKind, diagnostics::AccessCause)>,
799        global: &GlobalState,
800        alloc_id: AllocId, // diagnostics
801        span: Span,        // diagnostics
802    ) -> InterpResult<'tcx> {
803        use std::ops::Range;
804        // Performs the per-node work:
805        // - insert the permission if it does not exist
806        // - perform the access
807        // - record the transition
808        // to which some optimizations are added:
809        // - skip the traversal of the children in some cases
810        // - do not record noop transitions
811        //
812        // `perms_range` is only for diagnostics (it is the range of
813        // the `RangeMap` on which we are currently working).
814        let node_skipper = |access_kind: AccessKind, args: &NodeAppArgs<'_>| -> ContinueTraversal {
815            let NodeAppArgs { node, perm, rel_pos } = args;
816
817            let old_state = perm.get().copied().unwrap_or_else(|| node.default_location_state());
818            old_state.skip_if_known_noop(access_kind, *rel_pos)
819        };
820        let node_app = |perms_range: Range<u64>,
821                        access_kind: AccessKind,
822                        access_cause: diagnostics::AccessCause,
823                        args: NodeAppArgs<'_>|
824         -> Result<(), TransitionError> {
825            let NodeAppArgs { node, mut perm, rel_pos } = args;
826
827            let old_state = perm.or_insert(node.default_location_state());
828
829            // Call this function now, which ensures it is only called when
830            // `skip_if_known_noop` returns `Recurse`, due to the contract of
831            // `traverse_this_parents_children_other`.
832            old_state.record_new_access(access_kind, rel_pos);
833
834            let protected = global.borrow().protected_tags.contains_key(&node.tag);
835            let transition = old_state.perform_access(access_kind, rel_pos, protected)?;
836            // Record the event as part of the history
837            if !transition.is_noop() {
838                node.debug_info.history.push(diagnostics::Event {
839                    transition,
840                    is_foreign: rel_pos.is_foreign(),
841                    access_cause,
842                    access_range: access_range_and_kind.map(|x| x.0),
843                    transition_range: perms_range,
844                    span,
845                });
846            }
847            Ok(())
848        };
849
850        // Error handler in case `node_app` goes wrong.
851        // Wraps the faulty transition in more context for diagnostics.
852        let err_handler = |perms_range: Range<u64>,
853                           access_cause: diagnostics::AccessCause,
854                           args: ErrHandlerArgs<'_, TransitionError>|
855         -> InterpErrorKind<'tcx> {
856            let ErrHandlerArgs { error_kind, conflicting_info, accessed_info } = args;
857            TbError {
858                conflicting_info,
859                access_cause,
860                alloc_id,
861                error_offset: perms_range.start,
862                error_kind,
863                accessed_info,
864            }
865            .build()
866        };
867
868        if let Some((access_range, access_kind, access_cause)) = access_range_and_kind {
869            // Default branch: this is a "normal" access through a known range.
870            // We iterate over affected locations and traverse the tree for each of them.
871            for (perms_range, perms) in self.rperms.iter_mut(access_range.start, access_range.size)
872            {
873                TreeVisitor { nodes: &mut self.nodes, tag_mapping: &self.tag_mapping, perms }
874                    .traverse_this_parents_children_other(
875                        tag,
876                        |args| node_skipper(access_kind, args),
877                        |args| node_app(perms_range.clone(), access_kind, access_cause, args),
878                        |args| err_handler(perms_range.clone(), access_cause, args),
879                    )?;
880            }
881        } else {
882            // This is a special access through the entire allocation.
883            // It actually only affects `accessed` locations, so we need
884            // to filter on those before initiating the traversal.
885            //
886            // In addition this implicit access should not be visible to children,
887            // thus the use of `traverse_nonchildren`.
888            // See the test case `returned_mut_is_usable` from
889            // `tests/pass/tree_borrows/tree-borrows.rs` for an example of
890            // why this is important.
891            for (perms_range, perms) in self.rperms.iter_mut_all() {
892                let idx = self.tag_mapping.get(&tag).unwrap();
893                // Only visit accessed permissions
894                if let Some(p) = perms.get(idx)
895                    && let Some(access_kind) = p.permission.protector_end_access()
896                    && p.accessed
897                {
898                    let access_cause = diagnostics::AccessCause::FnExit(access_kind);
899                    TreeVisitor { nodes: &mut self.nodes, tag_mapping: &self.tag_mapping, perms }
900                        .traverse_nonchildren(
901                        tag,
902                        |args| node_skipper(access_kind, args),
903                        |args| node_app(perms_range.clone(), access_kind, access_cause, args),
904                        |args| err_handler(perms_range.clone(), access_cause, args),
905                    )?;
906                }
907            }
908        }
909        interp_ok(())
910    }
911}
912
913/// Integration with the BorTag garbage collector
914impl Tree {
915    pub fn remove_unreachable_tags(&mut self, live_tags: &FxHashSet<BorTag>) {
916        self.remove_useless_children(self.root, live_tags);
917        // Right after the GC runs is a good moment to check if we can
918        // merge some adjacent ranges that were made equal by the removal of some
919        // tags (this does not necessarily mean that they have identical internal representations,
920        // see the `PartialEq` impl for `UniValMap`)
921        self.rperms.merge_adjacent_thorough();
922    }
923
924    /// Checks if a node is useless and should be GC'ed.
925    /// A node is useless if it has no children and also the tag is no longer live.
926    fn is_useless(&self, idx: UniIndex, live: &FxHashSet<BorTag>) -> bool {
927        let node = self.nodes.get(idx).unwrap();
928        node.children.is_empty() && !live.contains(&node.tag)
929    }
930
931    /// Checks whether a node can be replaced by its only child.
932    /// If so, returns the index of said only child.
933    /// If not, returns none.
934    fn can_be_replaced_by_single_child(
935        &self,
936        idx: UniIndex,
937        live: &FxHashSet<BorTag>,
938    ) -> Option<UniIndex> {
939        let node = self.nodes.get(idx).unwrap();
940
941        let [child_idx] = node.children[..] else { return None };
942
943        // We never want to replace the root node, as it is also kept in `root_ptr_tags`.
944        if live.contains(&node.tag) || node.parent.is_none() {
945            return None;
946        }
947        // Since protected nodes are never GC'd (see `borrow_tracker::FrameExtra::visit_provenance`),
948        // we know that `node` is not protected because otherwise `live` would
949        // have contained `node.tag`.
950        let child = self.nodes.get(child_idx).unwrap();
951        // Check that for that one child, `can_be_replaced_by_child` holds for the permission
952        // on all locations.
953        for (_, data) in self.rperms.iter_all() {
954            let parent_perm =
955                data.get(idx).map(|x| x.permission).unwrap_or_else(|| node.default_initial_perm);
956            let child_perm = data
957                .get(child_idx)
958                .map(|x| x.permission)
959                .unwrap_or_else(|| child.default_initial_perm);
960            if !parent_perm.can_be_replaced_by_child(child_perm) {
961                return None;
962            }
963        }
964
965        Some(child_idx)
966    }
967
968    /// Properly removes a node.
969    /// The node to be removed should not otherwise be usable. It also
970    /// should have no children, but this is not checked, so that nodes
971    /// whose children were rotated somewhere else can be deleted without
972    /// having to first modify them to clear that array.
973    fn remove_useless_node(&mut self, this: UniIndex) {
974        // Due to the API of UniMap we must make sure to call
975        // `UniValMap::remove` for the key of this node on *all* maps that used it
976        // (which are `self.nodes` and every range of `self.rperms`)
977        // before we can safely apply `UniKeyMap::remove` to truly remove
978        // this tag from the `tag_mapping`.
979        let node = self.nodes.remove(this).unwrap();
980        for (_perms_range, perms) in self.rperms.iter_mut_all() {
981            perms.remove(this);
982        }
983        self.tag_mapping.remove(&node.tag);
984    }
985
986    /// Traverses the entire tree looking for useless tags.
987    /// Removes from the tree all useless child nodes of root.
988    /// It will not delete the root itself.
989    ///
990    /// NOTE: This leaves in the middle of the tree tags that are unreachable but have
991    /// reachable children. There is a potential for compacting the tree by reassigning
992    /// children of dead tags to the nearest live parent, but it must be done with care
993    /// not to remove UB.
994    ///
995    /// Example: Consider the tree `root - parent - child`, with `parent: Frozen` and
996    /// `child: Reserved`. This tree can exist. If we blindly delete `parent` and reassign
997    /// `child` to be a direct child of `root` then Writes to `child` are now permitted
998    /// whereas they were not when `parent` was still there.
999    fn remove_useless_children(&mut self, root: UniIndex, live: &FxHashSet<BorTag>) {
1000        // To avoid stack overflows, we roll our own stack.
1001        // Each element in the stack consists of the current tag, and the number of the
1002        // next child to be processed.
1003
1004        // The other functions are written using the `TreeVisitorStack`, but that does not work here
1005        // since we need to 1) do a post-traversal and 2) remove nodes from the tree.
1006        // Since we do a post-traversal (by deleting nodes only after handling all children),
1007        // we also need to be a bit smarter than "pop node, push all children."
1008        let mut stack = vec![(root, 0)];
1009        while let Some((tag, nth_child)) = stack.last_mut() {
1010            let node = self.nodes.get(*tag).unwrap();
1011            if *nth_child < node.children.len() {
1012                // Visit the child by pushing it to the stack.
1013                // Also increase `nth_child` so that when we come back to the `tag` node, we
1014                // look at the next child.
1015                let next_child = node.children[*nth_child];
1016                *nth_child += 1;
1017                stack.push((next_child, 0));
1018                continue;
1019            } else {
1020                // We have processed all children of `node`, so now it is time to process `node` itself.
1021                // First, get the current children of `node`. To appease the borrow checker,
1022                // we have to temporarily move the list out of the node, and then put the
1023                // list of remaining children back in.
1024                let mut children_of_node =
1025                    mem::take(&mut self.nodes.get_mut(*tag).unwrap().children);
1026                // Remove all useless children.
1027                children_of_node.retain_mut(|idx| {
1028                    if self.is_useless(*idx, live) {
1029                        // Delete `idx` node everywhere else.
1030                        self.remove_useless_node(*idx);
1031                        // And delete it from children_of_node.
1032                        false
1033                    } else {
1034                        if let Some(nextchild) = self.can_be_replaced_by_single_child(*idx, live) {
1035                            // `nextchild` is our grandchild, and will become our direct child.
1036                            // Delete the in-between node, `idx`.
1037                            self.remove_useless_node(*idx);
1038                            // Set the new child's parent.
1039                            self.nodes.get_mut(nextchild).unwrap().parent = Some(*tag);
1040                            // Save the new child in children_of_node.
1041                            *idx = nextchild;
1042                        }
1043                        // retain it
1044                        true
1045                    }
1046                });
1047                // Put back the now-filtered vector.
1048                self.nodes.get_mut(*tag).unwrap().children = children_of_node;
1049
1050                // We are done, the parent can continue.
1051                stack.pop();
1052                continue;
1053            }
1054        }
1055    }
1056}
1057
1058impl Node {
1059    pub fn default_location_state(&self) -> LocationState {
1060        LocationState::new_non_accessed(
1061            self.default_initial_perm,
1062            self.default_initial_idempotent_foreign_access,
1063        )
1064    }
1065}
1066
1067impl VisitProvenance for Tree {
1068    fn visit_provenance(&self, visit: &mut VisitWith<'_>) {
1069        // To ensure that the root never gets removed, we visit it
1070        // (the `root` node of `Tree` is not an `Option<_>`)
1071        visit(None, Some(self.nodes.get(self.root).unwrap().tag))
1072    }
1073}
1074
1075/// Relative position of the access
1076#[derive(Clone, Copy, Debug, PartialEq, Eq)]
1077pub enum AccessRelatedness {
1078    /// The accessed pointer is the current one
1079    This,
1080    /// The accessed pointer is a (transitive) child of the current one.
1081    // Current pointer is excluded (unlike in some other places of this module
1082    // where "child" is inclusive).
1083    StrictChildAccess,
1084    /// The accessed pointer is a (transitive) parent of the current one.
1085    // Current pointer is excluded.
1086    AncestorAccess,
1087    /// The accessed pointer is neither of the above.
1088    // It's a cousin/uncle/etc., something in a side branch.
1089    CousinAccess,
1090}
1091
1092impl AccessRelatedness {
1093    /// Check that access is either Ancestor or Distant, i.e. not
1094    /// a transitive child (initial pointer included).
1095    pub fn is_foreign(self) -> bool {
1096        matches!(self, AccessRelatedness::AncestorAccess | AccessRelatedness::CousinAccess)
1097    }
1098}