wait-free 4-level 64-bit pagetable for contiguous low-contention concurrent metadata

Overview

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);
}
You might also like...
Rust library to convert RGB 24-bit colors into ANSI 256 (8-bit) color codes with zero dependencies and at compile-time.
Rust library to convert RGB 24-bit colors into ANSI 256 (8-bit) color codes with zero dependencies and at compile-time.

rgb2ansi256 rgb2ansi256 is a small Rust library to convert RGB 24-bit colors into ANSI 256 (8-bit) color codes with zero dependencies and const fn. Th

A bit like tee, a bit like script, but all with a fake tty. Lets you remote control and watch a process

teetty teetty is a wrapper binary to execute a command in a pty while providing remote control facilities. This allows logging the stdout of a process

Rust lib for a Vec-like structure that can store different types of different sizes contiguous with each other in memory.

hvec In memory of Anna Harren, who coined the term turbofish - which you'll see a lot of if you use this crate. The main purpose of this crate is the

Compact, efficient data structures in contiguous byte arrays

Sokoban Compact, efficient data structures in contiguous byte arrays. Benchmarks Based on simple benchmarks, the naive performance of Sokoban data str

High-performance, lock-free local and concurrent object memory pool with automated allocation, cleanup, and verification.

Opool: Fast lock-free concurrent and local object pool Opool is a high-performance Rust library that offers a concurrent and local object pool impleme

StdFuzzer - StdFuzzer is the reference implementation of a generic bit-level fuzzer with LibAFL

StdFuzzer StdFuzzer is the reference implementation of a generic bit-level fuzzer with LibAFL Building Build with $ cargo build --release Compiling a

Simple bit-level protocol definitions in Rust.

bin-proto Simple & fast structured bit-level binary co/dec in Rust. An improved and modernized fork of protocol. A more efficient but (slightly) less

Use free svg icons in your Dioxus projects easily with dioxus-free-icons.

dioxus-free-icons Use free svg icons in your Dioxus projects easily with dioxus-free-icons. More information about this crate can be found in the crat

Provide free GPT-3.5 API service by reverse engineering the login-free ChatGPT website.

ChatGPT Free API Provide free GPT-3.5 API service by reverse engineering the login-free ChatGPT website. Note: This service requires the IP to be able

Low-level Rust library for implementing terminal command line interface, like in embedded systems.

Terminal CLI Need to build an interactive command prompt, with commands, properties and with full autocomplete? This is for you. Example, output only

A low-level ncurses wrapper for Rust

ncurses-rs This is a very thin wrapper around the ncurses TUI lib. NOTE: The ncurses lib is terribly unsafe and ncurses-rs is only the lightest wrappe

Rust bindings to Core Foundation and other low level libraries on Mac OS X and iOS

core-foundation-rs Compatibility Targets macOS 10.7 by default. To enable features added in macOS 10.8, set Cargo feature mac_os_10_8_features. To hav

Cross-platform, low level networking using the Rust programming language.

libpnet Linux ∪ OS X Build Status: Windows Build Status: Discussion and support: #libpnet on freenode / #rust-networking on irc.mozilla.org / #rust on

Low level HTTP server library in Rust

tiny-http Documentation Tiny but strong HTTP server in Rust. Its main objectives are to be 100% compliant with the HTTP standard and to provide an eas

A low-ish level tool for easily writing and hosting WASM based plugins.

A low-ish level tool for easily writing and hosting WASM based plugins. The goal of wasm_plugin is to make communicating across the host-plugin bounda

Low level access to T-Head Xuantie RISC-V processors

XuanTie Low level access to T-Head XuanTie RISC-V processors Contributing We welcome contribution! Please send an issue or pull request if you are rea

A low-level I/O ownership and borrowing library

This library introduces OwnedFd, BorrowedFd, and supporting types and traits, and corresponding features for Windows, which implement safe owning and

libnotcurses-sys is a low-level Rust wrapper for the notcurses C library

libnotcurses-sys is a low-level Rust wrapper for the notcurses C library This library is built with several layers of zero-overhead abstractions over

Verified Rust for low-level systems code

See Goals for a brief description of the project's goals. Building the project The main project source is in source. tools contains scripts for settin

Owner
Komora
Komora
A tiny 32 bit kernel written in Rust

rustboot A tiny 32 bit kernel written in Rust. I was inspired to download Rust and try to do this after seeing zero.rs - a stub that lets Rust program

Charlie Somerville 1.5k Dec 30, 2022
A lock-free, partially wait-free, eventually consistent, concurrent hashmap.

A lock-free, partially wait-free, eventually consistent, concurrent hashmap. This map implementation allows reads to always be wait-free on certain pl

Ian Smith 216 Nov 18, 2022
Rust library for concurrent data access, using memory-mapped files, zero-copy deserialization, and wait-free synchronization.

mmap-sync mmap-sync is a Rust crate designed to manage high-performance, concurrent data access between a single writer process and multiple reader pr

Cloudflare 97 Jun 26, 2023
Wait Service is a pure rust program to test and wait on the availability of a service.

Wait Service Wait Service is a pure rust program to test and wait on the availability of a service.

Magic Len (Ron Li) 3 Jan 18, 2022
wait-for-pid -- Wait for processes to exit

wait-for-pid -- Wait for processes to exit wait-for-pid PID is similar to the bash built-in command wait, except it works even when the processes star

Tv 2 Feb 2, 2022
Easy c̵̰͠r̵̛̠ö̴̪s̶̩̒s̵̭̀-t̶̲͝h̶̯̚r̵̺͐e̷̖̽ḁ̴̍d̶̖̔ ȓ̵͙ė̶͎ḟ̴͙e̸̖͛r̶̖͗ë̶̱́ṉ̵̒ĉ̷̥e̷͚̍ s̷̹͌h̷̲̉a̵̭͋r̷̫̊ḭ̵̊n̷̬͂g̵̦̃ f̶̻̊ơ̵̜ṟ̸̈́ R̵̞̋ù̵̺s̷̖̅ţ̸͗!̸̼͋

Rust S̵̓i̸̓n̵̉ I̴n̴f̶e̸r̵n̷a̴l mutability! Howdy, friendly Rust developer! Ever had a value get m̵̯̅ð̶͊v̴̮̾ê̴̼͘d away right under your nose just when

null 294 Dec 23, 2022
Simple image metadata scrubber. Will remove EXIF, XMP and IPTC metadata.

Simple image metadata scrubber. Will remove EXIF, XMP and IPTC metadata.

Jae Lo Presti 12 Nov 29, 2022
dovi_meta is a CLI tool for creating Dolby Vision XML metadata from an encoded deliverable with binary metadata.

dovi_meta dovi_meta is a CLI tool for creating Dolby Vision XML metadata from an encoded deliverable with binary metadata. Building Toolchain The mini

Rainbaby 12 Dec 14, 2022
wait-free spsc linked-list queue with individually reusable nodes

A wait-free single-producer single-consumer linked-list queue with individually reusable nodes.

glowcoil 22 Dec 26, 2022
A rust library for sharing and updating arbitrary slices between threads, optimized for wait-free reads

atomicslice A Rust library for thread-safe shared slices that are just about as fast as possible to read while also being writable. Overview Use Atomi

Tim Straubinger 5 Dec 6, 2023