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 testforeign_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§
Implementations§
Source§impl IdempotentForeignAccess
impl IdempotentForeignAccess
Sourcepub fn can_skip_foreign_access(
self,
happening_next: IdempotentForeignAccess,
) -> bool
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.
Sourcepub fn record_new(&mut self, just_happened: IdempotentForeignAccess)
pub fn record_new(&mut self, just_happened: IdempotentForeignAccess)
Updates self
to account for a foreign access.
Sourcepub fn is_foreign(self) -> bool
pub fn is_foreign(self) -> bool
Returns true if this access is foreign, i.e. not local.
Sourcepub fn from_foreign(acc: AccessKind) -> IdempotentForeignAccess
pub fn from_foreign(acc: AccessKind) -> IdempotentForeignAccess
Constructs a foreign access from an AccessKind
Sourcepub fn from_acc_and_rel(
acc: AccessKind,
rel: AccessRelatedness,
) -> IdempotentForeignAccess
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
.
Sourcepub fn ensure_no_stronger_than(
&mut self,
strongest_allowed: IdempotentForeignAccess,
) -> bool
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
impl Clone for IdempotentForeignAccess
Source§fn clone(&self) -> IdempotentForeignAccess
fn clone(&self) -> IdempotentForeignAccess
1.0.0 · Source§fn clone_from(&mut self, source: &Self)
fn clone_from(&mut self, source: &Self)
source
. Read moreSource§impl Debug for IdempotentForeignAccess
impl Debug for IdempotentForeignAccess
Source§impl Default for IdempotentForeignAccess
impl Default for IdempotentForeignAccess
Source§fn default() -> IdempotentForeignAccess
fn default() -> IdempotentForeignAccess
Source§impl Hash for IdempotentForeignAccess
impl Hash for IdempotentForeignAccess
Source§impl Ord for IdempotentForeignAccess
impl Ord for IdempotentForeignAccess
Source§fn cmp(&self, other: &IdempotentForeignAccess) -> Ordering
fn cmp(&self, other: &IdempotentForeignAccess) -> Ordering
1.21.0 · Source§fn max(self, other: Self) -> Selfwhere
Self: Sized,
fn max(self, other: Self) -> Selfwhere
Self: Sized,
Source§impl PartialEq for IdempotentForeignAccess
impl PartialEq for IdempotentForeignAccess
Source§impl PartialOrd for IdempotentForeignAccess
impl PartialOrd for IdempotentForeignAccess
impl Copy for IdempotentForeignAccess
impl Eq for IdempotentForeignAccess
impl StructuralPartialEq for IdempotentForeignAccess
Auto Trait Implementations§
impl Freeze for IdempotentForeignAccess
impl RefUnwindSafe for IdempotentForeignAccess
impl Send for IdempotentForeignAccess
impl Sync for IdempotentForeignAccess
impl Unpin for IdempotentForeignAccess
impl UnwindSafe for IdempotentForeignAccess
Blanket Implementations§
Source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
Source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Source§impl<T> CloneToUninit for Twhere
T: Clone,
impl<T> CloneToUninit for Twhere
T: Clone,
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 bytesRead
: 0 bytesWrite
: 0 bytes