Struct pagetable::PageTable

pub struct PageTable<T: Zeroable> { /* private fields */ }

A simple 4-level wait-free atomic pagetable. Punches through to the last level and installs any necessary pages along the way.

Works well for big contiguous metadata. Defaults all values to zeroed bits, so this only works with atomic values, as it’s not distinguishable whether a value was ever set to 0 or simply never initialized.

Warning: don’t use this for sparse keyspaces, as any time a key in a 2^16 range is touched for the first time, the zeroed slabs of values and parents (each with 2^16 children) will be created. For 64-bit values (and parent levels that point down) each slab is 8 * 2^16 bytes of memory, or 512kb. It is expected that this page table will be used for very hot global shared metadata.

There are some simple optimizations for when only the lowest bits in the u64 are used, which skips allocation and traversal of parent levels. For tables where only keys 0..2^16 are used, traversals can jump directly to the leaf slab, and avoid allocations.

The same principle is applied for avoiding levels when only the bottom 32 or 48 bits are used for keys.

Examples

use std::sync::atomic::{AtomicU64, Ordering};

let pt = pagetable::PageTable::<AtomicU64>::default();

for i in 0..100_000_000 {
    pt.get(i).fetch_add(1, Ordering::SeqCst);
}

for i in 0..100_000_000 {
    let value = pt.get(i).load(Ordering::SeqCst);
    assert_eq!(value, 1);
}

Implementations

impl<T: Zeroable> PageTable<T>

pub fn get(&self, key: u64) -> &T

Get the AtomicU64 associated with the provided key, installing all required pages if it does not exist yet. Defaults to 0.

Examples found in repository

examples/bench.rs (line 52)

fn main() {
    let before = Instant::now();
    let pt = PageTable::<AtomicUsize>::default();

    for i in 0_u64..(1 << 33) {
        pt.get(i);
    }

    dbg!(before.elapsed());

    dbg!(allocated());
    dbg!(freed());
    dbg!(resident());

    drop(pt);
    println!("after drop:");
    dbg!(before.elapsed());

    dbg!(allocated());
    dbg!(freed());
    dbg!(resident());
}

Trait Implementations

impl<T: Zeroable> Clone for PageTable<T>

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Default + Zeroable> Default for PageTable<T>

fn default() -> PageTable<T>

Returns the “default value” for a type.

impl<T: Zeroable, I: Into<u64>> Index<I> for PageTable<T>

type Output = T

The returned type after indexing.

fn index(&self, index: I) -> &Self::Output

Performs the indexing (container[index]) operation.