Enum IdempotentForeignAccess

Source
pub enum IdempotentForeignAccess {
    None,
    Read,
    Write,
}
Expand description

To speed up tree traversals, we want to skip traversing subtrees when we know the traversal will have no effect. This is often the case for foreign accesses, since usually foreign accesses happen several times in a row, but also foreign accesses are idempotent. In particular, see tests foreign_read_is_noop_after_foreign_write and all_transitions_idempotent. Thus, for each node we keep track of the “strongest idempotent foreign access” (SIFA), i.e. which foreign access can be skipped. Note that for correctness, it is not required that this is the strongest access, just any access it is idempotent under. In particular, setting it to None is always correct, but the point of this optimization is to have it be as strong as possible so that more accesses can be skipped. This enum represents the kinds of values we store:

  • None means that the node (and its subtrees) are not (guaranteed to be) idempotent under any foreign access.
  • Read means that the node (and its subtrees) are idempotent under foreign reads, but not (yet / necessarily) under foreign writes.
  • Write means that the node (and its subtrees) are idempotent under foreign writes. This also implies that it is idempotent under foreign reads, since reads are stronger than writes (see test foreign_read_is_noop_after_foreign_write). In other words, this node can be skipped for all foreign accesses.

Since a traversal does not just visit a node, but instead the entire subtree, the SIFA field for a given node indicates that the access to the entire subtree rooted at that node can be skipped. In order for this to work, we maintain the global invariant that at each location, the SIFA at each child must be stronger than that at the parent. For normal reads and writes, this is easily accomplished by tracking each foreign access as it occurs, so that then the next access can be skipped. This also obviously maintains the invariant, because if a node undergoes a foreign access, then all its children also see this as a foreign access. However, the invariant is broken during retags, because retags act across the entire allocation, but only emit a read event across a specific range. This means that for all nodes outside that range, the invariant is potentially broken, since a new child with a weaker SIFA is inserted. Thus, during retags, special care is taken to “manually” reset the parent’s SIFA to be at least as strong as the new child’s. This is accomplished with the ensure_no_stronger_than method.

Note that we derive Ord and PartialOrd, so the order in which variants are listed below matters: None < Read < Write. Do not change that order. See the test_order test.

Variants§

§

None

§

Read

§

Write

Implementations§

Source§

impl IdempotentForeignAccess

Source

pub fn can_skip_foreign_access( self, happening_next: IdempotentForeignAccess, ) -> bool

Returns true if a node where the strongest idempotent foreign access is self can skip the access happening_next. Note that if this returns true, then the entire subtree will be skipped.

Source

pub fn record_new(&mut self, just_happened: IdempotentForeignAccess)

Updates self to account for a foreign access.

Source

pub fn is_local(self) -> bool

Returns true if this access is local.

Source

pub fn is_foreign(self) -> bool

Returns true if this access is foreign, i.e. not local.

Source

pub fn from_foreign(acc: AccessKind) -> IdempotentForeignAccess

Constructs a foreign access from an AccessKind

Source

pub fn from_acc_and_rel( acc: AccessKind, rel: AccessRelatedness, ) -> IdempotentForeignAccess

Usually, tree traversals have an AccessKind and an AccessRelatedness. This methods converts these into the corresponding IdempotentForeignAccess, to be used to e.g. invoke can_skip_foreign_access.

Source

pub fn ensure_no_stronger_than( &mut self, strongest_allowed: IdempotentForeignAccess, ) -> bool

During retags, the SIFA needs to be weakened to account for children with weaker SIFAs being inserted. Thus, this method is called from the bottom up on each parent, until it returns false, which means the “children have stronger SIFAs” invariant is restored.

Trait Implementations§

Source§

impl Clone for IdempotentForeignAccess

Source§

fn clone(&self) -> IdempotentForeignAccess

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 IdempotentForeignAccess

Source§

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

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

impl Default for IdempotentForeignAccess

Source§

fn default() -> IdempotentForeignAccess

Returns the “default value” for a type. Read more
Source§

impl Hash for IdempotentForeignAccess

Source§

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher. Read more
1.3.0 · Source§

fn hash_slice<H>(data: &[Self], state: &mut H)
where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher. Read more
Source§

impl Ord for IdempotentForeignAccess

Source§

fn cmp(&self, other: &IdempotentForeignAccess) -> Ordering

This method returns an Ordering between self and other. Read more
1.21.0 · Source§

fn max(self, other: Self) -> Self
where Self: Sized,

Compares and returns the maximum of two values. Read more
1.21.0 · Source§

fn min(self, other: Self) -> Self
where Self: Sized,

Compares and returns the minimum of two values. Read more
1.50.0 · Source§

fn clamp(self, min: Self, max: Self) -> Self
where Self: Sized,

Restrict a value to a certain interval. Read more
Source§

impl PartialEq for IdempotentForeignAccess

Source§

fn eq(&self, other: &IdempotentForeignAccess) -> bool

Tests for self and other values to be equal, and is used by ==.
1.0.0 · Source§

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.
Source§

impl PartialOrd for IdempotentForeignAccess

Source§

fn partial_cmp(&self, other: &IdempotentForeignAccess) -> Option<Ordering>

This method returns an ordering between self and other values if one exists. Read more
1.0.0 · Source§

fn lt(&self, other: &Rhs) -> bool

Tests less than (for self and other) and is used by the < operator. Read more
1.0.0 · Source§

fn le(&self, other: &Rhs) -> bool

Tests less than or equal to (for self and other) and is used by the <= operator. Read more
1.0.0 · Source§

fn gt(&self, other: &Rhs) -> bool

Tests greater than (for self and other) and is used by the > operator. Read more
1.0.0 · Source§

fn ge(&self, other: &Rhs) -> bool

Tests greater than or equal to (for self and other) and is used by the >= operator. Read more
Source§

impl Copy for IdempotentForeignAccess

Source§

impl Eq for IdempotentForeignAccess

Source§

impl StructuralPartialEq for IdempotentForeignAccess

Auto Trait Implementations§

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> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dst: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dst. 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

Source§

type Output = T

Should always be Self
Source§

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

Source§

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>,

Source§

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>,

Source§

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: 1 byte

Size for each variant:

  • None: 0 bytes
  • Read: 0 bytes
  • Write: 0 bytes