#page-table #metadata #default #seq-cst

pagetable

Wait-free 4-level 64-bit pagetable for roughly-contiguous keys

24 releases

0.4.6 Aug 20, 2024
0.4.5 Aug 5, 2023
0.4.3 Jul 10, 2023
0.3.0 Oct 3, 2022
0.0.1 Jun 3, 2018

#312 in Database interfaces

Download history 165/week @ 2024-12-15 38/week @ 2024-12-22 64/week @ 2024-12-29 264/week @ 2025-01-05 187/week @ 2025-01-12 160/week @ 2025-01-19 99/week @ 2025-01-26 178/week @ 2025-02-02 277/week @ 2025-02-09 250/week @ 2025-02-16 295/week @ 2025-02-23 136/week @ 2025-03-02 130/week @ 2025-03-09 231/week @ 2025-03-16 149/week @ 2025-03-23 252/week @ 2025-03-30

764 downloads per month
Used in 15 crates (2 directly)

MIT/Apache

12KB
220 lines

pagetable

Wait-free 4-level page table that maps from a u64 key to an &AtomicU64 value. Page fan-out is 2^16. If a key doesn't exist, intermediate pages are atomically created while traversing down the levels, and the value is initialized to 0.

This is a somewhat specialized data structure, but it is useful for maintaining metadata in concurrent systems that need to track many items that have an associated logical ID that is allocated from a dense keyspace, like databases that would like to keep track of where a page lives based on its 64-bit ID, despite it being rewritten in random places during defragmentation.

API

#[derive(Default)]
pub struct PageTable { .. }

pub fn get(&self, key: u64) -> &AtomicU64 { .. }

Example

let pt = PageTable::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);
}

No runtime deps