Skip to main content

NodeOwner

ostd::specs::mm::page_table::node::owners

Struct NodeOwner 

Source 
pub struct NodeOwner<C: PageTableConfig> {
    pub meta_own: PageMetaOwner,
    pub children_perm: PointsTo<C::E, NR_ENTRIES>,
    pub level: PagingLevel,
    pub tree_level: int,
    pub slot_index: usize,
}
Expand description

§Verification Design

The owner type for a page table node. It contains:

  • meta_own, a PageMetaOwner, which holds the permissions for node-specific metadata fields, nr_children and stray
  • children_perm is an array permission for the underlying frame in which the node is allocated, interpreted as an array of NR_ENTRIES page table entries
  • slot_index identifies the underlying frame’s index in the metadata region
  • Each node is a page table with a level between 1 and 4 (on x86); level tracks the level of this node.
  • tree_level is the level field of the ghost_tree::Node that carries this object. Carried here for convenience, though it can be computed from level.

Fields§

§meta_own: PageMetaOwner§children_perm: PointsTo<C::E, NR_ENTRIES>§level: PagingLevel§tree_level: int§slot_index: usize

Implementations§

Source§

impl<C: PageTableConfig> NodeOwner<C>

Source

pub open spec fn meta_addr_self(self) -> Vaddr

{ meta_addr(self.slot_index) }

The meta address of this node’s slot, computed from slot_index. Always equals self.meta_perm.addr() under inv().

Source

pub open spec fn meta_perm_of( self, regions: MetaRegionOwners, ) -> PointsTo<MetaSlot, Metadata<PageTablePageMeta<C>>>

{
    vstd_extra::cast_ptr::PointsTo::new_spec(
        regions.slots[self.slot_index],
        regions.slot_owners[self.slot_index].inner_perms,
    )
}

Reconstructs a metadata cast_ptr from regions at self.slot_index. The borrow-model home of the node’s metadata perm.

Source

pub open spec fn metaregion_sound_node(self, regions: MetaRegionOwners) -> bool

{
    let idx = self.slot_index;
    &&& regions.slots.contains_key(idx)
    &&& self.meta_perm_of(regions).is_init()
    &&& self.meta_perm_of(regions).wf(&self.meta_perm_of(regions).inner_perms)
    &&& self.meta_perm_of(regions).value().metadata.wf(self.meta_own)
    &&& self.level == self.meta_perm_of(regions).value().metadata.level
    &&& self.meta_own.nr_children.id()
        == self.meta_perm_of(regions).value().metadata.nr_children.id()
    &&& regions.slot_owners[self.slot_index].usage == PageUsage::PageTable
    &&& self.count_consistent()

}

Regions-tied invariants that used to live in NodeOwner::inv() via the now-removed meta_perm field. Establishes the bridge between the NodeOwner and the slot perm parked in regions.

Source

pub open spec fn count_consistent(self) -> bool

{ self.meta_own.nr_children.value() == count_present(self.children_perm.value()) }

nr_children equals the number of present PTEs in children_perm. Held by a settled node (see metaregion_sound_node’s use site).

Source§

impl<C: PageTableConfig> NodeOwner<C>

Source

pub uninterp spec fn set_children_perm(self, idx: usize, pte: C::E) -> Self

Source

pub proof fn set_children_perm_axiom(self, idx: usize, pte: C::E)

requires
self.inv(),
idx < NR_ENTRIES,
ensures
self.set_children_perm(idx, pte).inv(),
self.set_children_perm(idx, pte).meta_own == self.meta_own,
self.set_children_perm(idx, pte).slot_index == self.slot_index,
self.set_children_perm(idx, pte).level == self.level,
self.set_children_perm(idx, pte).tree_level == self.tree_level,
self.set_children_perm(idx, pte).children_perm.addr() == self.children_perm.addr(),
self.set_children_perm(idx, pte).children_perm.value()
    == self.children_perm.value().update(idx as int, pte),
Source

pub proof fn nr_children_absent_slot_bound(self, idx: usize)

requires
self.inv(),
self.count_consistent(),
self.children_perm.value().len() == NR_ENTRIES,
idx < NR_ENTRIES,
!self.children_perm.value()[idx as int].is_present(),
ensures
self.meta_own.nr_children.value() < NR_ENTRIES,

If a slot in children_perm holds a non-present PTE, then nr_children < NR_ENTRIES. Proven (no longer axiomatized) from the count_consistent invariant: nr_children counts present PTEs, and an absent slot means not all NR_ENTRIES slots are present.

Source

pub proof fn nr_children_present_slot_bound(self, idx: usize)

requires
self.inv(),
self.count_consistent(),
self.children_perm.value().len() == NR_ENTRIES,
idx < NR_ENTRIES,
self.children_perm.value()[idx as int].is_present(),
ensures
self.meta_own.nr_children.value() > 0,

If a slot in children_perm holds a present PTE, then nr_children > 0. Dual of Self::nr_children_absent_slot_bound; proven from count_consistent.

Source§

impl<'rcu, C: PageTableConfig> NodeOwner<C>

Source

pub open spec fn relate_guard(self, guard: PageTableGuard<'rcu, C>) -> bool

{
    &&& guard.inner.inner@.ptr.addr() == self.meta_addr_self()
    &&& guard.inner.inner@.wf(self)

}

Trait Implementations§

Source§

impl<C: PageTableConfig> Inv for NodeOwner<C>

Source§

open spec fn inv(self) -> bool

{
    &&& self.meta_own.inv()
    &&& 0 <= self.meta_own.nr_children.value() <= NR_ENTRIES
    &&& 1 <= self.level <= NR_LEVELS
    &&& self.children_perm.is_init_all()
    &&& self.children_perm.addr()
        == paddr_to_vaddr(meta_to_frame(meta_addr(self.slot_index)))
    &&& self.tree_level == INC_LEVELS - self.level - 1
    &&& self.slot_index < max_meta_slots() as usize
    &&& FRAME_METADATA_RANGE.start <= meta_addr(self.slot_index)
        < FRAME_METADATA_RANGE.end
    &&& meta_addr(self.slot_index) % META_SLOT_SIZE == 0
    &&& meta_to_frame(meta_addr(self.slot_index))
        < VMALLOC_BASE_VADDR - LINEAR_MAPPING_BASE_VADDR
    &&& meta_to_frame(meta_addr(self.slot_index)) < MAX_PADDR
    &&& meta_to_frame(meta_addr(self.slot_index)) == self.children_perm.addr()
    &&& self.slot_index == frame_to_index(meta_to_frame(meta_addr(self.slot_index)))

}
Source§

impl<C: PageTableConfig> InvView for NodeOwner<C>

Source§

proof fn view_preserves_inv(self)

Source§

impl<C: PageTableConfig> View for NodeOwner<C>

Source§

open spec fn view(&self) -> <Self as View>::V

{
    NodeModel {
        level: self.level,
        _phantom: core::marker::PhantomData,
    }
}
Source§

type V = NodeModel<C>

Auto Trait Implementations§

§

impl<C> Freeze for NodeOwner<C>

§

impl<C> RefUnwindSafe for NodeOwner<C>
where <C as PageTableConfig>::E: RefUnwindSafe,

§

impl<C> Send for NodeOwner<C>

§

impl<C> Sync for NodeOwner<C>

§

impl<C> Unpin for NodeOwner<C>
where <C as PageTableConfig>::E: Unpin,

§

impl<C> UnsafeUnpin for NodeOwner<C>

§

impl<C> UnwindSafe for NodeOwner<C>
where <C as PageTableConfig>::E: UnwindSafe,

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.

§

impl<T, VERUS_SPEC__A> FromSpec<T> for VERUS_SPEC__A
where VERUS_SPEC__A: From<T>,

§

fn obeys_from_spec() -> bool

§

fn from_spec(v: T) -> VERUS_SPEC__A

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.

§

impl<T, VERUS_SPEC__A> IntoSpec<T> for VERUS_SPEC__A
where VERUS_SPEC__A: Into<T>,

§

fn obeys_into_spec() -> bool

§

fn into_spec(self) -> T

§

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

§

fn obeys_into_spec() -> bool

§

fn into_spec(self) -> U

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.
§

impl<T, VERUS_SPEC__A> TryFromSpec<T> for VERUS_SPEC__A
where VERUS_SPEC__A: TryFrom<T>,

§

fn obeys_try_from_spec() -> bool

§

fn try_from_spec( v: T, ) -> Result<VERUS_SPEC__A, <VERUS_SPEC__A as TryFrom<T>>::Error>

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<T, VERUS_SPEC__A> TryIntoSpec<T> for VERUS_SPEC__A
where VERUS_SPEC__A: TryInto<T>,

§

fn obeys_try_into_spec() -> bool

§

fn try_into_spec(self) -> Result<T, <VERUS_SPEC__A as TryInto<T>>::Error>

§

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

§

fn obeys_try_into_spec() -> bool

§

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

§

impl<A> SpecEq<&A> for A
where A: ?Sized,

§

impl<A> SpecEq<&mut A> for A
where A: ?Sized,

§

impl<A> SpecEq<A> for A
where A: ?Sized,

§

impl<A> SpecEq<Ghost<A>> for A

§

impl<A> SpecEq<Tracked<A>> for A