Struct miri::Tree

source ·
pub struct Tree {
    pub(super) tag_mapping: UniKeyMap<BorTag>,
    pub(super) nodes: UniValMap<Node>,
    pub(super) rperms: RangeMap<UniValMap<LocationState>>,
    pub(super) root: UniIndex,
}
Expand description

Tree structure with both parents and children since we want to be able to traverse the tree efficiently in both directions.

Fields§

§tag_mapping: UniKeyMap<BorTag>

Mapping from tags to keys. The key obtained can then be used in any of the UniValMap relative to this allocation, i.e. both the nodes and rperms of the same Tree. The parent-child relationship in Node is encoded in terms of these same keys, so traversing the entire tree needs exactly one access to tag_mapping.

§nodes: UniValMap<Node>

All nodes of this tree.

§rperms: RangeMap<UniValMap<LocationState>>

Maps a tag and a location to a perm, with possible lazy initialization.

NOTE: not all tags registered in nodes are necessarily in all ranges of rperms, because rperms is in part lazily initialized. Just because nodes.get(key) is Some(_) does not mean you can safely unwrap any perm.get(key).

We do uphold the fact that keys(perms) is a subset of keys(nodes)

§root: UniIndex

The index of the root node.

Implementations§

source§

impl<'tcx> Tree

source

fn nth_parent(&self, tag: BorTag, nth_parent: u8) -> Option<BorTag>

Climb the tree to get the tag of a distant ancestor. Allows operations on tags that are unreachable by the program but still exist in the tree. Not guaranteed to perform consistently if provenance-gc=1.

source

pub fn give_pointer_debug_name( &mut self, tag: BorTag, nth_parent: u8, name: &str, ) -> InterpResult<'tcx>

Debug helper: assign name to tag.

source

pub fn is_allocation_of(&self, tag: BorTag) -> bool

Debug helper: determines if the tree contains a tag.

source§

impl<'tcx> Tree

source

pub fn print_tree( &self, protected_tags: &FxHashMap<BorTag, ProtectorKind>, show_unnamed: bool, ) -> InterpResult<'tcx>

Display the contents of the tree.

source§

impl Tree

source

pub fn new(root_tag: BorTag, size: Size, span: Span) -> Self

Create a new tree, with only a root pointer.

source§

impl<'tcx> Tree

source

pub fn new_child( &mut self, parent_tag: BorTag, new_tag: BorTag, default_initial_perm: Permission, reborrow_range: AllocRange, span: Span, ) -> InterpResult<'tcx>

Insert a new tag in the tree

source

pub fn dealloc( &mut self, tag: BorTag, access_range: AllocRange, global: &RefCell<GlobalStateInner>, alloc_id: AllocId, span: Span, ) -> InterpResult<'tcx>

Deallocation requires

  • a pointer that permits write accesses
  • the absence of Strong Protectors anywhere in the allocation
source

pub fn perform_access( &mut self, access_kind: AccessKind, tag: BorTag, access_range: Option<AllocRange>, global: &RefCell<GlobalStateInner>, alloc_id: AllocId, span: Span, access_cause: AccessCause, ) -> InterpResult<'tcx>

Map the per-node and per-location LocationState::perform_access to each location of access_range, on every tag of the allocation.

If access_range is None, this is interpreted as the special access that is applied on protector release:

  • the access will be applied only to initialized locations of the allocation,
  • and it will not be visible to children.

LocationState::perform_access will take care of raising transition errors and updating the initialized status of each location, this traversal adds to that:

  • inserting into the map locations that do not exist yet,
  • trimming the traversal,
  • recording the history.
source§

impl Tree

Integration with the BorTag garbage collector

source

pub fn remove_unreachable_tags(&mut self, live_tags: &FxHashSet<BorTag>)

source

fn keep_only_needed(&mut self, idx: UniIndex, live: &FxHashSet<BorTag>) -> bool

Traverses the entire tree looking for useless tags. Returns true iff the tag it was called on is still live or has live children, and removes from the tree all tags that have no live children.

NOTE: This leaves in the middle of the tree tags that are unreachable but have reachable children. There is a potential for compacting the tree by reassigning children of dead tags to the nearest live parent, but it must be done with care not to remove UB.

Example: Consider the tree root - parent - child, with parent: Frozen and child: Reserved. This tree can exist. If we blindly delete parent and reassign child to be a direct child of root then Writes to child are now permitted whereas they were not when parent was still there.

source§

impl<'tcx> Tree

source

pub fn new_allocation( id: AllocId, size: Size, state: &mut GlobalStateInner, _kind: MemoryKind, machine: &MiriMachine<'tcx>, ) -> Self

Create a new allocation, i.e. a new tree

source

pub fn before_memory_access( &mut self, access_kind: AccessKind, alloc_id: AllocId, prov: ProvenanceExtra, range: AllocRange, machine: &MiriMachine<'tcx>, ) -> InterpResult<'tcx>

Check that an access on the entire range is permitted, and update the tree.

source

pub fn before_memory_deallocation( &mut self, alloc_id: AllocId, prov: ProvenanceExtra, size: Size, machine: &MiriMachine<'tcx>, ) -> InterpResult<'tcx>

Check that this pointer has permission to deallocate this range.

source

pub fn expose_tag(&mut self, _tag: BorTag)

source

pub fn release_protector( &mut self, machine: &MiriMachine<'tcx>, global: &RefCell<GlobalStateInner>, tag: BorTag, alloc_id: AllocId, ) -> InterpResult<'tcx>

A tag just lost its protector.

This emits a special kind of access that is only applied to initialized locations, as a protection against other tags not having been made aware of the existence of this protector.

Trait Implementations§

source§

impl Clone for Tree

source§

fn clone(&self) -> Tree

Returns a copy of the value. Read more
1.0.0 · source§

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source. Read more
source§

impl Debug for Tree

source§

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more
source§

impl VisitProvenance for Tree

source§

fn visit_provenance(&self, visit: &mut VisitWith<'_>)

Auto Trait Implementations§

§

impl Freeze for Tree

§

impl RefUnwindSafe for Tree

§

impl Send for Tree

§

impl Sync for Tree

§

impl Unpin for Tree

§

impl UnwindSafe for Tree

Blanket Implementations§

source§

impl<T> Any for T
where T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for T
where T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T, U> Into<U> for T
where U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

impl<T> Same for T

§

type Output = T

Should always be Self
source§

impl<T> ToOwned for T
where T: Clone,

§

type Owned = T

The resulting type after obtaining ownership.
source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.
§

impl<V, T> VZip<V> for T
where V: MultiLane<T>,

§

fn vzip(self) -> V

Layout§

Note: Most layout information is completely unstable and may even differ between compilations. The only exception is types with certain repr(...) attributes. Please see the Rust Reference's “Type Layout” chapter for details on type layout guarantees.

Size: 112 bytes