From e9a79a0ed79609c1e293c7b221fce577200b2eb7 Mon Sep 17 00:00:00 2001 From: Nathan Ringo Date: Sat, 31 Aug 2024 20:23:24 -0500 Subject: The start of a new librarified organization. --- crates/Cargo.lock | 348 +++++++++++++++++++++++++ crates/Cargo.toml | 3 + crates/buddy_allocator/Cargo.toml | 16 ++ crates/buddy_allocator/src/bitvec.rs | 59 +++++ crates/buddy_allocator/src/free_list.rs | 72 ++++++ crates/buddy_allocator/src/lib.rs | 222 ++++++++++++++++ crates/buddy_allocator/src/stripe.rs | 148 +++++++++++ crates/buddy_allocator/src/tree.rs | 130 ++++++++++ crates/buddy_allocator/tests/hosted_test.rs | 252 +++++++++++++++++++ crates/physmem_free_list/Cargo.toml | 9 + crates/physmem_free_list/src/lib.rs | 378 ++++++++++++++++++++++++++++ crates/utils/Cargo.toml | 8 + crates/utils/src/lib.rs | 3 + crates/utils/src/pin.rs | 25 ++ 14 files changed, 1673 insertions(+) create mode 100644 crates/Cargo.lock create mode 100644 crates/Cargo.toml create mode 100644 crates/buddy_allocator/Cargo.toml create mode 100644 crates/buddy_allocator/src/bitvec.rs create mode 100644 crates/buddy_allocator/src/free_list.rs create mode 100644 crates/buddy_allocator/src/lib.rs create mode 100644 crates/buddy_allocator/src/stripe.rs create mode 100644 crates/buddy_allocator/src/tree.rs create mode 100644 crates/buddy_allocator/tests/hosted_test.rs create mode 100644 crates/physmem_free_list/Cargo.toml create mode 100644 crates/physmem_free_list/src/lib.rs create mode 100644 crates/utils/Cargo.toml create mode 100644 crates/utils/src/lib.rs create mode 100644 crates/utils/src/pin.rs (limited to 'crates') diff --git a/crates/Cargo.lock b/crates/Cargo.lock new file mode 100644 index 0000000..843d740 --- /dev/null +++ b/crates/Cargo.lock @@ -0,0 +1,348 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 3 + +[[package]] +name = "allocator-api2" +version = "0.2.18" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5c6cb57a04249c6480766f7f7cef5467412af1490f8d1e243141daddada3264f" + +[[package]] +name = "autocfg" +version = "0.1.8" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "0dde43e75fd43e8a1bf86103336bc699aa8d17ad1be60c76c0bdfd4828e19b78" +dependencies = [ + "autocfg 1.3.0", +] + +[[package]] +name = "autocfg" +version = "1.3.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "0c4b4d0bd25bd0b74681c0ad21497610ce1b7c91b1022cd21c80c6fbdd9476b0" + +[[package]] +name = "bitflags" +version = "1.3.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "bef38d45163c2f1dde094a7dfd33ccf595c92905c8f8f4fdc18d06fb1037718a" + +[[package]] +name = "bitflags" +version = "2.6.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b048fb63fd8b5923fc5aa7b340d8e156aec7ec02f0c78fa8a6ddc2613f6f71de" + +[[package]] +name = "byteorder" +version = "1.5.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1fd0f2584146f6f2ef48085050886acf353beff7305ebd1ae69500e27c67f64b" + +[[package]] +name = "cfg-if" +version = "1.0.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "baf1de4339761588bc0619e3cbc0120ee582ebb74b53b4efbf79117bd2da40fd" + +[[package]] +name = "cfg_aliases" +version = "0.2.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "613afe47fcd5fac7ccf1db93babcb082c5994d996f20b8b159f2ad1658eb5724" + +[[package]] +name = "cloudabi" +version = "0.0.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ddfc5b9aa5d4507acaf872de71051dfd0e309860e88966e1051e462a077aac4f" +dependencies = [ + "bitflags 1.3.2", +] + +[[package]] +name = "contracts" +version = "0.6.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f1d1429e3bd78171c65aa010eabcdf8f863ba3254728dbfb0ad4b1545beac15c" +dependencies = [ + "proc-macro2", + "quote", + "syn", +] + +[[package]] +name = "fuchsia-cprng" +version = "0.1.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a06f77d526c1a601b7c4cdd98f54b5eaabffc14d5f2f0296febdc7f357c6d3ba" + +[[package]] +name = "lazy_static" +version = "1.5.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "bbd2bcb4c963f2ddae06a2efc7e9f3591312473c50c6685e1f298068316e66fe" + +[[package]] +name = "libc" +version = "0.2.158" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d8adc4bb1803a324070e64a98ae98f38934d91957a99cfb3a43dcbc01bc56439" + +[[package]] +name = "nix" +version = "0.29.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "71e2746dc3a24dd78b3cfcb7be93368c6de9963d30f43a6a73998a9cf4b17b46" +dependencies = [ + "bitflags 2.6.0", + "cfg-if", + "cfg_aliases", + "libc", +] + +[[package]] +name = "num-traits" +version = "0.2.19" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "071dfc062690e90b734c0b2273ce72ad0ffa95f0c74596bc250dcfd960262841" +dependencies = [ + "autocfg 1.3.0", +] + +[[package]] +name = "proc-macro2" +version = "1.0.86" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5e719e8df665df0d1c8fbfd238015744736151d4445ec0836b8e628aae103b77" +dependencies = [ + "unicode-ident", +] + +[[package]] +name = "proptest" +version = "0.9.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "01c477819b845fe023d33583ebf10c9f62518c8d79a0960ba5c36d6ac8a55a5b" +dependencies = [ + "bitflags 1.3.2", + "byteorder", + "lazy_static", + "num-traits", + "quick-error", + "rand", + "rand_chacha", + "rand_xorshift", + "regex-syntax", +] + +[[package]] +name = "quick-error" +version = "1.2.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a1d01941d82fa2ab50be1e79e6714289dd7cde78eba4c074bc5a4374f650dfe0" + +[[package]] +name = "quote" +version = "1.0.37" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b5b9d34b8991d19d98081b46eacdd8eb58c6f2b201139f7c5f643cc155a633af" +dependencies = [ + "proc-macro2", +] + +[[package]] +name = "rand" +version = "0.6.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "6d71dacdc3c88c1fde3885a3be3fbab9f35724e6ce99467f7d9c5026132184ca" +dependencies = [ + "autocfg 0.1.8", + "libc", + "rand_chacha", + "rand_core 0.4.2", + "rand_hc", + "rand_isaac", + "rand_jitter", + "rand_os", + "rand_pcg", + "rand_xorshift", + "winapi", +] + +[[package]] +name = "rand_chacha" +version = "0.1.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "556d3a1ca6600bfcbab7c7c91ccb085ac7fbbcd70e008a98742e7847f4f7bcef" +dependencies = [ + "autocfg 0.1.8", + "rand_core 0.3.1", +] + +[[package]] +name = "rand_core" +version = "0.3.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "7a6fdeb83b075e8266dcc8762c22776f6877a63111121f5f8c7411e5be7eed4b" +dependencies = [ + "rand_core 0.4.2", +] + +[[package]] +name = "rand_core" +version = "0.4.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "9c33a3c44ca05fa6f1807d8e6743f3824e8509beca625669633be0acbdf509dc" + +[[package]] +name = "rand_hc" +version = "0.1.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "7b40677c7be09ae76218dc623efbf7b18e34bced3f38883af07bb75630a21bc4" +dependencies = [ + "rand_core 0.3.1", +] + +[[package]] +name = "rand_isaac" +version = "0.1.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ded997c9d5f13925be2a6fd7e66bf1872597f759fd9dd93513dd7e92e5a5ee08" +dependencies = [ + "rand_core 0.3.1", +] + +[[package]] +name = "rand_jitter" +version = "0.1.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1166d5c91dc97b88d1decc3285bb0a99ed84b05cfd0bc2341bdf2d43fc41e39b" +dependencies = [ + "libc", + "rand_core 0.4.2", + "winapi", +] + +[[package]] +name = "rand_os" +version = "0.1.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "7b75f676a1e053fc562eafbb47838d67c84801e38fc1ba459e8f180deabd5071" +dependencies = [ + "cloudabi", + "fuchsia-cprng", + "libc", + "rand_core 0.4.2", + "rdrand", + "winapi", +] + +[[package]] +name = "rand_pcg" +version = "0.1.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "abf9b09b01790cfe0364f52bf32995ea3c39f4d2dd011eac241d2914146d0b44" +dependencies = [ + "autocfg 0.1.8", + "rand_core 0.4.2", +] + +[[package]] +name = "rand_xorshift" +version = "0.1.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "cbf7e9e623549b0e21f6e97cf8ecf247c1a8fd2e8a992ae265314300b2455d5c" +dependencies = [ + "rand_core 0.3.1", +] + +[[package]] +name = "rdrand" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "678054eb77286b51581ba43620cc911abf02758c91f93f479767aed0f90458b2" +dependencies = [ + "rand_core 0.3.1", +] + +[[package]] +name = "regex-syntax" +version = "0.6.29" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f162c6dd7b008981e4d40210aca20b4bd0f9b60ca9271061b07f78537722f2e1" + +[[package]] +name = "static_assertions" +version = "1.1.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a2eb9349b6444b326872e140eb1cf5e7c522154d69e7a0ffb0fb81c06b37543f" + +[[package]] +name = "syn" +version = "1.0.109" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "72b64191b275b66ffe2469e8af2c1cfe3bafa67b529ead792a6d0160888b4237" +dependencies = [ + "proc-macro2", + "quote", + "unicode-ident", +] + +[[package]] +name = "unicode-ident" +version = "1.0.12" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "3354b9ac3fae1ff6755cb6db53683adb661634f67557942dea4facebec0fee4b" + +[[package]] +name = "vernos_buddy_allocator" +version = "0.1.0" +dependencies = [ + "allocator-api2", + "contracts", + "nix", + "proptest", + "static_assertions", + "vernos_physmem_free_list", + "vernos_utils", +] + +[[package]] +name = "vernos_physmem_free_list" +version = "0.1.0" +dependencies = [ + "allocator-api2", + "contracts", +] + +[[package]] +name = "vernos_utils" +version = "0.1.0" +dependencies = [ + "contracts", +] + +[[package]] +name = "winapi" +version = "0.3.9" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5c839a674fcd7a98952e593242ea400abe93992746761e38641405d28b00f419" +dependencies = [ + "winapi-i686-pc-windows-gnu", + "winapi-x86_64-pc-windows-gnu", +] + +[[package]] +name = "winapi-i686-pc-windows-gnu" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ac3b87c63620426dd9b991e5ce0329eff545bccbbb34f3be09ff6fb6ab51b7b6" + +[[package]] +name = "winapi-x86_64-pc-windows-gnu" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "712e227841d057c1ee1cd2fb22fa7e5a5461ae8e48fa2ca79ec42cfc1931183f" diff --git a/crates/Cargo.toml b/crates/Cargo.toml new file mode 100644 index 0000000..0911a19 --- /dev/null +++ b/crates/Cargo.toml @@ -0,0 +1,3 @@ +[workspace] +members = ["buddy_allocator", "physmem_free_list", "utils"] +resolver = "2" diff --git a/crates/buddy_allocator/Cargo.toml b/crates/buddy_allocator/Cargo.toml new file mode 100644 index 0000000..e2a85d3 --- /dev/null +++ b/crates/buddy_allocator/Cargo.toml @@ -0,0 +1,16 @@ +[package] +name = "vernos_buddy_allocator" +version = "0.1.0" +edition = "2021" +publish = false + +[dependencies] +allocator-api2 = { version = "0.2.18", default-features = false } +contracts = { version = "0.6.3", default-features = false } +static_assertions = { version = "1.1.0", default-features = false } +vernos_physmem_free_list = { path = "../physmem_free_list" } +vernos_utils = { path = "../utils" } + +[dev-dependencies] +proptest = { version = "0.9.6", default-features = false, features = ["std"] } +nix = { version = "0.29.0", default-features = false, features = ["mman"] } diff --git a/crates/buddy_allocator/src/bitvec.rs b/crates/buddy_allocator/src/bitvec.rs new file mode 100644 index 0000000..856d579 --- /dev/null +++ b/crates/buddy_allocator/src/bitvec.rs @@ -0,0 +1,59 @@ +use contracts::requires; +use core::{fmt, mem::transmute}; + +/// A fixed-length vector of bits. +pub struct BitVec([usize]); + +impl BitVec { + fn from_mut(words: &mut [usize]) -> &mut BitVec { + // SAFETY: The types have a newtype relationship. + unsafe { transmute(words) } + } + + fn from_ref(words: &[usize]) -> &BitVec { + // SAFETY: The types have a newtype relationship. + unsafe { transmute(words) } + } + + /// Retrieves the value of a bit from the BitVec. + #[requires(i < self.len())] + pub fn get(&self, i: usize) -> bool { + let word_index = i / usize::BITS as usize; + let subword_index = i % usize::BITS as usize; + let one_hot = 1 << subword_index; + (self.0[word_index] & one_hot) != 0 + } + + /// Returns whether the BitVec is empty. + pub fn is_empty(&self) -> bool { + self.0.is_empty() + } + + /// Returns the number of bits in the BitVec. + pub fn len(&self) -> usize { + self.0.len() * usize::BITS as usize + } + + /// Sets the value of a bit in the BitVec. + #[requires(i < self.len())] + pub fn set(&mut self, i: usize, value: bool) { + let word_index = i / usize::BITS as usize; + let subword_index = i % usize::BITS as usize; + let one_hot = 1 << subword_index; + if value { + self.0[word_index] |= one_hot; + } else { + self.0[word_index] &= !one_hot; + } + } +} + +impl fmt::Debug for BitVec { + fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { + write!(fmt, "BitVec(")?; + for word in &self.0 { + write!(fmt, "{word:064b}")?; + } + write!(fmt, ")") + } +} diff --git a/crates/buddy_allocator/src/free_list.rs b/crates/buddy_allocator/src/free_list.rs new file mode 100644 index 0000000..5a633c3 --- /dev/null +++ b/crates/buddy_allocator/src/free_list.rs @@ -0,0 +1,72 @@ +//! A doubly-linked list of power-of-two-sized subregions. + +use core::{marker::PhantomPinned, pin::Pin, ptr}; + +/// The magic number a non-sentinel node should have. +const FREE_NODE_MAGIC: u64 = u64::from_ne_bytes(*b"FREENODE"); + +/// The magic number a sentinel node should have. +const SENTINEL_MAGIC: u64 = u64::from_ne_bytes(*b"SENTINEL"); + +/// A doubly-linked list of power-of-two-sized subregions. +/// +/// This type is valid when zero-initialized. +#[derive(Debug)] +pub struct FreeList { + sentinel: FreeListNode, +} + +impl FreeList { + /// Performs self-linking. This must be done before the free list is used in any other way. + pub fn self_link(mut self: Pin<&mut FreeList>) { + assert_eq!(self.sentinel.next, ptr::null_mut()); + assert_eq!(self.sentinel.prev, ptr::null_mut()); + + let self_ptr = &self.sentinel as *const FreeListNode as *mut FreeListNode; + let mut sentinel = self.sentinel_unchecked(); + *sentinel.as_mut().next_mut() = self_ptr; + *sentinel.as_mut().prev_mut() = self_ptr; + *sentinel.as_mut().magic_mut() = SENTINEL_MAGIC; + } + + /// Projects the sentinel node out of the list. + fn sentinel(self: Pin<&mut FreeList>) -> Pin<&mut FreeListNode> { + let mut sentinel = self.sentinel_unchecked(); + assert_eq!(*sentinel.as_mut().magic_mut(), SENTINEL_MAGIC); + sentinel + } + + /// Projects the sentinel node out of the list, without checking the magic number. + fn sentinel_unchecked(self: Pin<&mut FreeList>) -> Pin<&mut FreeListNode> { + // SAFETY: sentinel is structurally pinned. + unsafe { self.map_unchecked_mut(|list| &mut list.sentinel) } + } +} + +#[derive(Debug)] +struct FreeListNode { + next: *mut FreeListNode, + prev: *mut FreeListNode, + magic: u64, + _phantom: PhantomPinned, +} + +impl FreeListNode { + /// Projects the `next` pointer out of the node. + fn next_mut(self: Pin<&mut FreeListNode>) -> &mut *mut FreeListNode { + // SAFETY: next is not structurally pinned. + unsafe { &mut self.get_unchecked_mut().next } + } + + /// Projects the `prev` pointer out of the node. + fn prev_mut(self: Pin<&mut FreeListNode>) -> &mut *mut FreeListNode { + // SAFETY: prev is structurally pinned. + unsafe { &mut self.get_unchecked_mut().prev } + } + + /// Projects the `magic` number out of the node. + fn magic_mut(self: Pin<&mut FreeListNode>) -> &mut u64 { + // SAFETY: magic is structurally pinned. + unsafe { &mut self.get_unchecked_mut().magic } + } +} diff --git a/crates/buddy_allocator/src/lib.rs b/crates/buddy_allocator/src/lib.rs new file mode 100644 index 0000000..fa86de7 --- /dev/null +++ b/crates/buddy_allocator/src/lib.rs @@ -0,0 +1,222 @@ +//! A buddy allocator, used to allocate pages. +//! +//! The allocator can be split into three abstractions: stripes, trees, and the allocator. +//! +//! TODO: See if there's standard terminology for these. +//! +//! ## Stripes +//! +//! The buddy allocator works in terms of size classes, which are power-of-two sized, starting at a +//! single page and going up from there. Each stripe corresponds to a single size class and a +//! particular region of memory. +//! +//! A stripe contains a circular doubly-linked free-list for subregions of that size class, and a +//! bitset marking whether a particular region has been allocated or not. Being a circular +//! doubly-linked list makes it cheap to remove an element whose address we know, as well as cheap +//! to push and pop elements. +//! +//! It's efficient to go from the address of a subregion to the index of its corresponding bit, so +//! when we hand out a subregion from the free-list or put one back, it's cheap to read or write +//! its bit. +//! +//! ## Trees +//! +//! A tree is logically a collection of stripes, one per size class. To pack the structures more +//! efficiently, they are stored interleaved with each other, and the tree manages this. +//! +//! The important logic at the level of trees happens when we allocate a subregion from a size +//! class whose stripe's free-list is empty, and when we free subregions. +//! +//! When a stripe's free-list is empty, the tree instead allocates a subregion of a larger size +//! from the next stripe. It can then store the unused portion in the current size class. +//! +//! The really important bit is the ability to merge subregions when they're freed. When we free a +//! subregion of a certain size class, we can check whether its neighbor (its buddy) is unallocated +//! as well. If so, we can remove it from the free-list by its address. We can combine the two +//! subregions into one of the next larger size class, and then return that subregion to the next +//! stripe. +//! +//! ## The buddy allocator +//! +//! Finally, the overall buddy allocator needs to be able to handle multiple memory regions. To +//! facilitate this, the trees are stored in an array, which forms the overall allocator. +#![no_std] + +mod bitvec; +mod free_list; +mod tree; + +// mod stripe; + +use crate::{bitvec::BitVec, free_list::FreeList, tree::Tree}; +use allocator_api2::alloc::{AllocError, Layout, LayoutError}; +use contracts::requires; +use core::{mem, pin::Pin, ptr::NonNull}; +use vernos_physmem_free_list::FreeListAllocator; +use vernos_utils::pin::pin_project_slice_mut_iter; + +/// A buddy allocator. +#[derive(Debug)] +pub struct BuddyAllocator< + 'allocator, + const PAGE_SIZE: usize, + const PAGE_SIZE_BITS: usize, + const SIZE_CLASS_COUNT: usize, +> { + /// The free lists. + free_lists: Pin<&'allocator mut [FreeList; SIZE_CLASS_COUNT]>, + + /// The metadata associated with each tree. + trees: &'allocator mut [Tree<'allocator, PAGE_SIZE, PAGE_SIZE_BITS>], + + /// The shared bitset. + bitset: &'allocator mut BitVec, +} + +impl< + 'allocator, + const PAGE_SIZE: usize, + const PAGE_SIZE_BITS: usize, + const SIZE_CLASS_COUNT: usize, + > BuddyAllocator<'allocator, PAGE_SIZE, PAGE_SIZE_BITS, SIZE_CLASS_COUNT> +{ + /// Returns a buddy allocator backed by the page ranges in the free list. + pub fn new( + mut free_list: FreeListAllocator<'allocator, PAGE_SIZE>, + ) -> Result, AllocError> + { + assert_eq!(PAGE_SIZE, 1 << PAGE_SIZE_BITS); + assert_ne!(SIZE_CLASS_COUNT, 0); + + // We use one contiguous region to store the free lists and all the information about each + // tree (the base, the maximum order, and the bitset). We do one pass through the free list + // to find out how much storage we need, then we try to find a convenient spot to prune the + // storage we need from a page range in the list. + let mut range_count = 0; + let mut size_class_counts = [0; SIZE_CLASS_COUNT]; + for (_, mut len_pages) in free_list.iter() { + while len_pages > 0 { + let size_class = (len_pages.trailing_zeros() as usize).min(SIZE_CLASS_COUNT - 1); + range_count += 1; + size_class_counts[size_class] += 1; + len_pages -= 1 << size_class; + } + } + + // Lay out the metadata. The error here really ought to be impossible, because the pages in + // the free list needed to fit in there in the first place. + let metadata_layout = MetadataLayout::::new( + range_count, + size_class_counts, + ) + .map_err(|_| AllocError)?; + + // Allocate space for the metadata. + let metadata = free_list.allocate_zeroed(metadata_layout.layout)?; + + // Break out each component of the metadata. + // + // SAFETY: The layout is computed to make all of this sound if the data is valid. All of + // these types are valid when zero-initialized. + let free_lists: &'allocator mut [FreeList; SIZE_CLASS_COUNT] = unsafe { + metadata + .byte_add(metadata_layout.free_lists_offset) + .cast() + .as_mut() + }; + let trees: &'allocator mut [Tree] = unsafe { + NonNull::slice_from_raw_parts( + metadata.byte_add(metadata_layout.trees_offset).cast(), + metadata_layout.trees_len, + ) + .as_mut() + }; + let bitset: &'allocator mut BitVec = unsafe { + mem::transmute::<&mut [usize], &mut BitVec>( + NonNull::slice_from_raw_parts( + metadata.byte_add(metadata_layout.bitset_offset).cast(), + metadata_layout.bitset_len, + ) + .as_mut(), + ) + }; + + // Pin and self-link each free list. Although they're valid in a UB sense when zeroed, + // they're not yet ready to use until this is done. + // + // SAFETY: We never provide the ability to move out of a free list. + let mut free_lists = unsafe { Pin::new_unchecked(free_lists) }; + for free_list in pin_project_slice_mut_iter(free_lists.as_mut()) { + free_list.self_link(); + } + + // TODO: Actually initialize the trees with ranges from the allocator... + + // Make the buddy allocator and return. + Ok(BuddyAllocator { + free_lists, + trees, + bitset, + }) + } + + /// Tries to allocate a subregion of a particular size class from the allocator. + #[requires((0..SIZE_CLASS_COUNT).contains(&size_class))] + pub fn alloc(&mut self, size_class: usize) -> Result, AllocError> { + Err(AllocError) + } +} + +#[derive(Debug)] +struct MetadataLayout< + const PAGE_SIZE: usize, + const PAGE_SIZE_BITS: usize, + const SIZE_CLASS_COUNT: usize, +> { + layout: Layout, + free_lists_offset: usize, + trees_offset: usize, + trees_len: usize, + bitset_offset: usize, + bitset_len: usize, +} + +impl + MetadataLayout +{ + fn new( + range_count: usize, + mut size_class_counts: [usize; SIZE_CLASS_COUNT], + ) -> Result, LayoutError> { + let trees_len = range_count; + let mut bitset_len_bits = 0; + // TODO: Is there a cleaner way to compute this? + for i in (0..size_class_counts.len()).rev() { + let count = size_class_counts[i]; + if count != 0 { + bitset_len_bits += count; + if i > 0 { + size_class_counts[i - 1] += count * 2; + } + } + } + let bitset_len = (bitset_len_bits + usize::BITS as usize - 1) / usize::BITS as usize; + + let free_lists_layout = Layout::new::<[FreeList; SIZE_CLASS_COUNT]>(); + let trees_layout = Layout::array::>(trees_len)?; + let bitset_layout = Layout::array::(bitset_len)?; + + let free_lists_offset = 0; + let (layout, trees_offset) = free_lists_layout.extend(trees_layout)?; + let (layout, bitset_offset) = layout.extend(bitset_layout)?; + + Ok(MetadataLayout { + layout, + free_lists_offset, + trees_offset, + trees_len, + bitset_offset, + bitset_len, + }) + } +} diff --git a/crates/buddy_allocator/src/stripe.rs b/crates/buddy_allocator/src/stripe.rs new file mode 100644 index 0000000..2ff686b --- /dev/null +++ b/crates/buddy_allocator/src/stripe.rs @@ -0,0 +1,148 @@ +use crate::{bitvec::BitVec, PAGE_SIZE_BITS}; +use core::ptr::NonNull; + +/// A single size class for a single region of the allocator. See the comment on the +/// `crate::allocators::buddy` module for more information. +pub struct Stripe<'buddy> { + /// The base address of the tree this stripe is a part of. + pub base: *const (), + + /// The order of the stripe. Order `n` means the subregions are `2ⁿ` pages in size. + pub order: usize, + + /// The sentinel node of the free-list for this node. As an invariant of the type, there are no + /// live references to any node in this list. + pub free_list: NonNull, + + /// The bitset used to track whether a given subregion is allocated or not. A `true` bit + /// corresponds to an allocated subregion. + pub bitset: &'buddy mut BitVec, + + /// The offset from the start of the bitset to the region used by this stripe. + pub bitset_offset: usize, +} + +impl<'buddy> Stripe<'buddy> { + /// Returns the buddy of the given pointer. + /// + /// ## Safety + /// + /// - The pointer must actually be part of this region. + unsafe fn buddy_of(&self, ptr: NonNull) -> NonNull { + let index = self.buddy_of_index(self.index_of(ptr)); + let addr = self.base as usize + (index << (PAGE_SIZE_BITS + self.order)); + NonNull::new_unchecked(addr as *mut FreeListNode) + } + + /// Returns the buddy of the given index. + fn buddy_of_index(&self, index: usize) -> usize { + index ^ (1 << (PAGE_SIZE_BITS + self.order)) + } + + /// Returns the index the given pointer should have in the BitVec. + fn index_of(&self, ptr: NonNull) -> usize { + (ptr.as_ptr() as usize - self.base as usize) >> (PAGE_SIZE_BITS + self.order) + } + + /// Pops a subregion from the free-list. + pub fn pop(&mut self) -> Option> { + // SAFETY: The `free_list` is guaranteed to be valid by the invariants of the buddy + // allocator. Retrieving the next pointer doesn't, on its own, break aliasing rules. + let next = unsafe { self.free_list.read().next }; + + // If the sentinel and the next pointer refer to the same spot, the free-list was empty, so + // we can't pop from it. + if self.free_list == next { + return None; + } + + // Otherwise, remove the node from the free-list. + unsafe { + FreeListNode::remove(next); + } + + // Finally, mark the node as allocated in the bitvec. + let index = self.index_of(next); + assert!(self.bitset.get(self.bitset_offset + index)); + self.bitset.set(self.bitset_offset + index, true); + + Some(next) + } + + /// Pushes a subregion back into the free-list. + /// + /// # Safety + /// + /// - There must be no live references to `subregion`. + /// - `subregion` must not be a member of any list. + pub unsafe fn push(&mut self, subregion: NonNull) { + // Insert the subregion as the first element of the free-list. + // + // SAFETY: The free-list is guaranteed to be valid by the invariants of the buddy + // allocator. + unsafe { + FreeListNode::insert(self.free_list, subregion); + } + + // Mark the node as unallocated in the bitvec. + let index = self.index_of(subregion); + assert!(self.bitset.get(self.bitset_offset + index)); + self.bitset.set(self.bitset_offset + index, false); + } + + /// Pushes a subregion into the free-list for the first time. + /// + /// # Safety + /// + /// - There must be no live references to `subregion`. + /// - `subregion` must not be a member of any list. + pub unsafe fn push_initial(&mut self, subregion: NonNull) { + // Insert the subregion as the first element of the free-list. + // + // SAFETY: The free-list is guaranteed to be valid by the invariants of the buddy + // allocator. + unsafe { + FreeListNode::insert(self.free_list, subregion); + } + + // Mark the node as unallocated in the bitvec. + let index = self.index_of(subregion); + assert!(self.bitset.get(self.bitset_offset + index)); + self.bitset.set(self.bitset_offset + index, false); + } +} + +pub struct FreeListNode { + next: NonNull, + prev: NonNull, +} + +impl FreeListNode { + /// Inserts `new` after `prev`, initializing it. `prev` may be the sentinel. + /// + /// # Safety + /// + /// - There must be no live references to any node in the list that includes `prev`, including + /// the sentinel. + /// - There must be no live references to `new`. + /// - `new` must not be a member of any list. + pub unsafe fn insert(prev: NonNull, new: NonNull) { + let next = prev.read().next; + (*prev.as_ptr()).next = new; + (*next.as_ptr()).prev = new; + new.write(FreeListNode { next, prev }); + } + + /// Removes this node from the free list it is a part of. + /// + /// # Safety + /// + /// - The pointer must point to a node that is part of a free list. + /// - There must be no live references to any node in the list, including the sentinel. + /// - The pointer must not point to the sentinel node. + pub unsafe fn remove(ptr: NonNull) { + let FreeListNode { next, prev } = ptr.read(); + (*next.as_ptr()).prev = prev; + (*prev.as_ptr()).next = next; + } +} diff --git a/crates/buddy_allocator/src/tree.rs b/crates/buddy_allocator/src/tree.rs new file mode 100644 index 0000000..a303d40 --- /dev/null +++ b/crates/buddy_allocator/src/tree.rs @@ -0,0 +1,130 @@ +/// A single region of the allocator. See the comment on the `crate::allocators::buddy` module for +/// more information. +/// +/// This type is valid when zero-initialized. +#[derive(Debug)] +pub struct Tree<'buddy, const PAGE_SIZE: usize, const PAGE_SIZE_BITS: usize> { + /// The base address of the tree. + pub base: *const (), + + /// The log2 of the number of pages in the region represented by the tree. + pub log2_page_count: usize, + + /// The offset in the bitset to the bits responsible for this tree's pages. + bitset_offset: usize, + + // /// The bitset used to track whether subregion are allocated or not in this tree. + // pub bitset: &'buddy mut BitVec, + phantom: core::marker::PhantomData<&'buddy mut [u8; PAGE_SIZE]>, +} + +/* +use crate::{ + bitvec::BitVec, + stripe::{FreeListNode, Stripe}, + MAX_ORDER, PAGE_SIZE_BITS, +}; +use contracts::requires; + +/// A single region of the allocator. See the comment on the `crate::allocators::buddy` module for +/// more information. +pub struct Tree<'buddy> { + /// The base address of the tree. + pub base: *const (), + + /// The log2 of the number of pages in the region represented by the tree. + pub log2_page_count: usize, + + /// The array of sentinel nodes of the free-list for this node. As an invariant of the type, + /// there are no live references to any node in any list in this array, and there are + /// MAX_ORDER + 1 nodes. + pub free_lists: NonNull, + + /// The bitset used to track whether subregion are allocated or not in this tree. + pub bitset: &'buddy mut BitVec, +} + +impl<'buddy> Tree<'buddy> { + /// Tries to allocate a subregion with the given order, possibly splitting a larger subregion + /// in order to so so. + #[requires(order <= MAX_ORDER)] + pub fn alloc(&mut self, order: usize) -> Option> { + if let Some(ptr) = self.stripe(order).pop() { + Some(ptr) + } else if order == MAX_ORDER { + None + } else { + // Get a larger region. + let ptr = self.alloc(order + 1)?; + + // Get a pointer to the higher half. + // + // SAFETY: This has to be in-bounds, it's part of the same allocation! + let higher_half = unsafe { ptr.byte_add(1 << (PAGE_SIZE_BITS + order)) }; + + // Put the higher half in the current buddy's stripe. + // + // SAFETY: The higher half is from this region, not in the higher stripe, and of the + // right size. + unsafe { + self.stripe(order).push(higher_half); + } + + // Return the pointer. + Some(ptr) + } + } + + /// Returns the stripe with the given order. + #[requires(order <= MAX_ORDER)] + fn stripe<'stripe>(&'stripe mut self, order: usize) -> Stripe<'stripe> { + // TODO: There should be some smart bitwise-math version of this... + let mut bitset_offset = 0; + for i in 0..order { + bitset_offset += (1 << self.log2_page_count) >> i; + } + + Stripe { + base: self.base, + order, + // SAFETY: order is constrained to be in-bounds. + free_list: unsafe { self.free_lists.add(order) }, + bitset: self.bitset, + bitset_offset, + } + } +} + +/// Evil bitwise version of the reasonable loop to compute the `bitset_offset` of a stripe. +#[requires(log2_page_count < usize::BITS as usize)] +#[requires(order < usize::BITS as usize)] +fn compute_bitset_offset(log2_page_count: usize, order: usize) -> usize { + let ones = |i: usize| !(usize::MAX << i); + + if order > log2_page_count + 1 { + ones(log2_page_count + 1) + } else { + ones(order).wrapping_shl((log2_page_count + 1 - order) as u32) + } +} + +#[test] +fn compute_bitset_offset_test() { + fn compute_bitset_offset_loop(log2_page_count: usize, order: usize) -> usize { + let mut bitset_offset = 0; + for i in 0..order { + bitset_offset += (1 << log2_page_count) >> i; + } + bitset_offset + } + + for log2_page_count in 0..64 { + for order in 0..64 { + assert_eq!( + compute_bitset_offset(log2_page_count, order), + compute_bitset_offset_loop(log2_page_count, order), + ); + } + } +} +*/ diff --git a/crates/buddy_allocator/tests/hosted_test.rs b/crates/buddy_allocator/tests/hosted_test.rs new file mode 100644 index 0000000..d13895c --- /dev/null +++ b/crates/buddy_allocator/tests/hosted_test.rs @@ -0,0 +1,252 @@ +use core::{fmt, num::NonZero, slice}; +use nix::sys::mman::{mmap_anonymous, munmap, MapFlags, ProtFlags}; +use proptest::prelude::*; +use vernos_buddy_allocator::BuddyAllocator; +use vernos_physmem_free_list::FreeListAllocator; + +proptest! { + #![proptest_config(proptest::test_runner::Config { + failure_persistence: None, + ..Default::default() + })] + + #[test] + fn test_scenario(scenario in Scenario::any()) { + scenario.run(true) + } +} + +#[test] +fn test_simple_scenario() { + let scenario = Scenario { + range_sizes: vec![4], + actions: vec![ + Action::Debug, + Action::Alloc { + sentinel_value: 0xaa, + size_class: 0, + }, + Action::Debug, + ], + }; + scenario.run(false) +} + +const PAGE_SIZE: usize = (size_of::<*const ()>() * 4).next_power_of_two(); +const PAGE_SIZE_BITS: usize = PAGE_SIZE.trailing_zeros() as usize; +const SIZE_CLASS_COUNT: usize = 4; + +/// A single action the property test should perform. +#[derive(Debug)] +enum Action { + /// Makes an allocation. + Alloc { + /// A sentinel value, which is expected to be present when the allocation is freed. + sentinel_value: u8, + + /// The size class, which is constrained to be less than `SIZE_CLASS_COUNT`. + size_class: usize, + }, + + /// Deallocates an allocation. + Dealloc { + /// The index of the allocation in the set of live allocations, which is taken to be a + /// circular list (so this is always in-bounds if there are any allocations). + index: usize, + }, + + /// Prints the allocator and all live allocations, for debugging purposes. This is never + /// automatically generated. + Debug, + + /// Overwrites an allocation, changing its sentinel. + Overwrite { + /// The index of the allocation in the set of live allocations, which is taken to be a + /// circular list (so this is always in-bounds if there are any allocations). + index: usize, + + /// The new sentinel value. + sentinel_value: u8, + }, +} + +impl Action { + /// Generates a random action. + pub fn any() -> impl Strategy { + prop_oneof![ + (any::(), 0..SIZE_CLASS_COUNT).prop_map(|(sentinel_value, size_class)| { + Action::Alloc { + sentinel_value, + size_class, + } + }), + any::().prop_map(|index| { Action::Dealloc { index } }), + (any::(), any::()).prop_map(|(index, sentinel_value)| { + Action::Overwrite { + index, + sentinel_value, + } + }) + ] + } + + /// Runs an action. + pub fn run( + &self, + buddy: &mut BuddyAllocator, + allocs: &mut Vec, + allow_errors: bool, + ) { + match *self { + Action::Alloc { + sentinel_value, + size_class, + } => match buddy.alloc(size_class) { + Ok(ptr) => unsafe { + let slice = slice::from_raw_parts_mut(ptr.as_ptr(), PAGE_SIZE << size_class); + slice.fill(sentinel_value); + allocs.push(Alloc { + slice, + sentinel_value, + }); + }, + Err(err) => { + if !allow_errors { + Err(err).unwrap() + } + } + }, + Action::Dealloc { index } => { + if allow_errors && allocs.is_empty() { + return; + } + + let index = index % allocs.len(); + let alloc = allocs.remove(index); + alloc.check_sentinel(); + todo!("{alloc:?}") + } + Action::Debug => { + dbg!(buddy); + dbg!(allocs); + } + Action::Overwrite { + index, + sentinel_value, + } => { + if allow_errors && allocs.is_empty() { + return; + } + + let index = index % allocs.len(); + let alloc = &mut allocs[index]; + alloc.slice.fill(sentinel_value); + alloc.sentinel_value = sentinel_value; + } + } + } +} + +/// The entire series of actions to be performed. +#[derive(Debug)] +struct Scenario { + /// The sizes of the ranges the buddy allocator should be initialized with. + range_sizes: Vec, + + /// Actions to perform after initializing the buddy allocator. + actions: Vec, +} + +impl Scenario { + /// Generates a random scenario. + pub fn any() -> impl Strategy { + ( + prop::collection::vec(1usize..1 << (SIZE_CLASS_COUNT + 2), 0..4), + prop::collection::vec(Action::any(), 0..64), + ) + .prop_map(|(range_sizes, actions)| Scenario { + range_sizes, + actions, + }) + } + + /// Runs the scenario. + pub fn run(&self, allow_errors: bool) { + // Allocate each of the page ranges. + let backing_mem = self + .range_sizes + .iter() + .map(|&size| unsafe { + mmap_anonymous( + None, + NonZero::new(size * PAGE_SIZE).unwrap(), + ProtFlags::PROT_READ | ProtFlags::PROT_WRITE, + MapFlags::MAP_PRIVATE, + ) + .expect("failed to allocate memory") + }) + .collect::>(); + + // Create the free list allocator and move the pages there. + let mut free_list: FreeListAllocator = FreeListAllocator::new(); + for (&size, &ptr) in self.range_sizes.iter().zip(backing_mem.iter()) { + unsafe { + free_list.add(ptr.cast(), size); + } + } + + // Create the buddy allocator and move the pages from the free list to there. + match BuddyAllocator::::new(free_list) { + Ok(mut buddy) => { + let mut allocs = Vec::new(); + + // Run each of the actions. + for action in &self.actions { + action.run(&mut buddy, &mut allocs, allow_errors); + + // Check each allocation. + for alloc in &allocs { + alloc.check_sentinel(); + } + } + } + Err(err) => { + if !allow_errors { + Err(err).unwrap() + } + } + } + + // Free each of the page ranges. + for (&size, ptr) in self.range_sizes.iter().zip(backing_mem) { + unsafe { + munmap(ptr, size * PAGE_SIZE).expect("failed to free memory"); + } + } + } +} + +/// Information about an allocation we've made from the buddy allocator. +struct Alloc<'alloc> { + slice: &'alloc mut [u8], + sentinel_value: u8, +} + +impl<'alloc> Alloc<'alloc> { + pub fn check_sentinel(&self) { + let s = self.sentinel_value; + for (i, &b) in self.slice.iter().enumerate() { + assert_eq!(b, s, "at index {i}, {b} != {s}",); + } + } +} + +impl<'alloc> fmt::Debug for Alloc<'alloc> { + fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { + fmt.debug_struct("Alloc") + .field("ptr", &self.slice.as_ptr()) + .field("len", &self.slice.len()) + .field("sentinel_value", &self.sentinel_value) + .finish() + } +} diff --git a/crates/physmem_free_list/Cargo.toml b/crates/physmem_free_list/Cargo.toml new file mode 100644 index 0000000..c1aadd8 --- /dev/null +++ b/crates/physmem_free_list/Cargo.toml @@ -0,0 +1,9 @@ +[package] +name = "vernos_physmem_free_list" +version = "0.1.0" +edition = "2021" +publish = false + +[dependencies] +allocator-api2 = { version = "0.2.18", default-features = false } +contracts = { version = "0.6.3", default-features = false } diff --git a/crates/physmem_free_list/src/lib.rs b/crates/physmem_free_list/src/lib.rs new file mode 100644 index 0000000..cb28362 --- /dev/null +++ b/crates/physmem_free_list/src/lib.rs @@ -0,0 +1,378 @@ +//! A free-list allocator for physical memory ranges. This is only used when bootstrapping the +//! buddy allocator, since it provides a way to store and manipulate physical memory ranges without +//! needing a working allocator. +#![no_std] + +use allocator_api2::alloc::{AllocError, Layout}; +use contracts::requires; +use core::{fmt, iter, marker::PhantomData, mem::size_of, ptr::NonNull, slice}; + +/// The free-list allocator. +pub struct FreeListAllocator<'allocator, const PAGE_SIZE: usize> { + head: Option>, +} + +impl<'allocator, const PAGE_SIZE: usize> FreeListAllocator<'allocator, PAGE_SIZE> { + /// Creates a new, empty allocator. + pub fn new() -> FreeListAllocator<'allocator, PAGE_SIZE> { + assert!(size_of::>() <= PAGE_SIZE); + + FreeListAllocator { head: None } + } + + /// Pushes a page range into the free list. + /// + /// # Safety + /// + /// - `ptr` must be a pointer that conveys ownership over the page range. + /// - The page range must be untyped memory. + /// - The page range must be aligned to `PAGE_SIZE`. + /// - The page range must live for `'allocator`. + /// - `len_pages` must be accurate. + pub unsafe fn add(&mut self, ptr: NonNull<[u8; PAGE_SIZE]>, len_pages: usize) { + self.head = Some(FreeListPtr::new(ptr, len_pages, self.head.take())); + } + + /// Allocates memory. This is like `Allocator::allocate`, but it takes `&mut self`. + pub fn allocate(&mut self, layout: Layout) -> Result, AllocError> { + assert!(PAGE_SIZE.is_power_of_two()); + let len_pages = (layout.size() + PAGE_SIZE - 1) >> PAGE_SIZE.trailing_zeros(); + + // Find the size of the smallest page range that would fit this. + let Some(selected_node_len) = self + .iter() + .map(|(_, range_len_pages)| range_len_pages) + .filter(|&range_len_pages| len_pages <= range_len_pages) + .min() + else { + return Err(AllocError); + }; + + // If the node we're looking for is the first one, and we're not planning on splitting it, + // we have a special case. + // + // UNWRAP: The list can't have been empty or .min() above would've returned None. + if self + .head + .as_ref() + .map(|node| node.len_pages() == len_pages) + .unwrap() + { + // In that case, just unlink the node and hand it back. + // + // UNWRAP: The list can't have been empty or .min() above would've returned None. + let node = self.head.take().unwrap(); + let (ptr, header) = node.consume(); + self.head = header.next; + Ok(NonNull::slice_from_raw_parts( + ptr.cast(), + header.len_pages * PAGE_SIZE, + )) + } else { + // Otherwise, we want to get a node that's directly before a node that has exactly the + // right length. + let node_before_node_to_remove = if selected_node_len == len_pages { + // If the node we're looking for has the same length as the allocation, we just + // need to iterate through the list to find it. The special case where it's the + // first element was already handled above. + let mut next = self.head.as_mut(); + let mut node_before_node_to_remove = None; + while let Some(ptr) = next { + if let Some(next_header) = &ptr.header().next { + if next_header.len_pages() == selected_node_len { + node_before_node_to_remove = Some(ptr); + break; + } + } + next = ptr.next_mut(); + } + + // UNWRAP: We had to find the node in the first place. + node_before_node_to_remove.unwrap() + } else { + // In the normal case, we'll split the node. First, we iterate to the node we + // selected. + let mut next = self.head.as_mut(); + let mut node_to_split = None; + while let Some(ptr) = next { + if ptr.len_pages() == selected_node_len { + node_to_split = Some(ptr); + break; + } + next = ptr.next_mut(); + } + + // UNWRAP: We had to find the node in the first place. + let node_to_split = node_to_split.unwrap(); + + // Split the node. The part we're going to remove gets inserted after `node_to_split`, + // so we can just return the node after this. + node_to_split.split(len_pages); + node_to_split + }; + + // Unlink the next node. + // + // UNWRAP: The next node must exist because of the above. + let (ptr, unlinked_len_pages) = node_before_node_to_remove.unlink_next().unwrap(); + assert_eq!(len_pages, unlinked_len_pages); + Ok(NonNull::slice_from_raw_parts( + ptr.cast(), + len_pages * PAGE_SIZE, + )) + } + } + + /// Allocates zeroed-out memory. + pub fn allocate_zeroed(&mut self, layout: Layout) -> Result, AllocError> { + let ptr = self.allocate(layout)?; + // SAFETY: The pointer has to have a valid size. + unsafe { + ptr.cast::().write_bytes(0, ptr.len()); + } + Ok(ptr) + } + + /// Returns an iterator over the page ranges in the free list, as pairs of `ptr` and + /// `len_pages`. The returned pointers should not be accessed. + pub fn iter(&self) -> impl '_ + Iterator, usize)> { + let mut next: Option<&_> = self.head.as_ref(); + iter::from_fn(move || match next { + Some(ptr) => { + let out = (ptr.ptr(), ptr.len_pages()); + next = ptr.next(); + Some(out) + } + None => None, + }) + } + + /// Splits all the nodes until each page range is of a power-of-two size. + pub fn split_to_powers_of_two(&mut self) { + let mut next = self.head.as_mut(); + while let Some(ptr) = next { + // Compute the size the page range would have if it were + // let log2_smaller_size = ptr.len_pages().trailing_zeros(); + // let smaller_size = 1 << log2_smaller_size; + + next = ptr.next_mut(); + } + } +} + +impl<'allocator, const PAGE_SIZE: usize> fmt::Debug for FreeListAllocator<'allocator, PAGE_SIZE> { + fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { + let mut next: Option<&_> = self.head.as_ref(); + fmt.debug_list() + .entries(iter::from_fn(|| match next { + Some(ptr) => { + next = ptr.next(); + Some(ptr) + } + None => None, + })) + .finish() + } +} + +/// A pointer to a page range, which start with a header in the first page. +/// +/// # Safety +/// +/// - `ptr` must be a pointer that conveys ownership over the page range. +/// - The page range must be untyped memory. +/// - The page range must be non-empty. +/// - The first page must have a correct header written to it. +/// - The page range must live for `'allocator`. +struct FreeListPtr<'allocator, const PAGE_SIZE: usize> { + ptr: NonNull>, + _phantom: PhantomData<&'allocator FreeListNodeHeader<'allocator, PAGE_SIZE>>, +} + +impl<'allocator, const PAGE_SIZE: usize> FreeListPtr<'allocator, PAGE_SIZE> { + /// Initialize the given page range as a node in the free list. + /// + /// # Safety + /// + /// - `ptr` must be a pointer that conveys ownership over the page range. + /// - The page range must be untyped memory. + /// - The page range must be aligned to `PAGE_SIZE`. + /// - The page range must live for `'allocator`. + /// - `len_pages` must be accurate. + #[requires(len_pages > 0)] + pub unsafe fn new( + ptr: NonNull<[u8; PAGE_SIZE]>, + len_pages: usize, + next: Option>, + ) -> FreeListPtr<'allocator, PAGE_SIZE> { + assert!(size_of::>() <= PAGE_SIZE); + + let ptr: NonNull> = ptr.cast(); + // SAFETY: The safety invariants plus the assertion guarantee this write is valid. + unsafe { + ptr.write(FreeListNodeHeader { next, len_pages }); + } + FreeListPtr { + ptr, + _phantom: PhantomData, + } + } + + /// Consumes the node, returning the pointer and header. + pub fn consume( + self, + ) -> ( + NonNull<[u8; PAGE_SIZE]>, + FreeListNodeHeader<'allocator, PAGE_SIZE>, + ) { + // SAFETY: The invariants of the type ensure that the header is present and owned by us. + let header = unsafe { self.ptr.read() }; + (self.ptr.cast(), header) + } + + /// Returns a reference to the header of the page range. + fn header(&self) -> &FreeListNodeHeader<'allocator, PAGE_SIZE> { + // SAFETY: The invariants of the type ensure that the header is present and owned by us. + unsafe { self.ptr.as_ref() } + } + + /// Returns an exclusive reference to the header of the page range. + /// + /// # Safety + /// + /// The invariants of the type must be upheld. + unsafe fn header_mut(&mut self) -> &mut FreeListNodeHeader<'allocator, PAGE_SIZE> { + // SAFETY: The invariants of the type ensure that the header is present and owned by us. + unsafe { self.ptr.as_mut() } + } + + /// Returns the length of the node in pages. + pub fn len_pages(&self) -> usize { + self.header().len_pages + } + + /// Returns a shared reference to the next node in the free list. Returns `None` when there + /// are no further nodes. + pub fn next(&self) -> Option<&FreeListPtr<'allocator, PAGE_SIZE>> { + self.header().next.as_ref() + } + + /// Returns an exclusive reference to the next node in the free list. Returns `None` when there + /// are no further nodes. + pub fn next_mut(&mut self) -> Option<&mut FreeListPtr<'allocator, PAGE_SIZE>> { + // SAFETY: We just lend out the next pointer, which can't violate our invariants. + let header = unsafe { self.header_mut() }; + header.next.as_mut() + } + + /// Returns the underlying pointer, which should not be accessed. + pub fn ptr(&self) -> NonNull<[u8; PAGE_SIZE]> { + self.ptr.cast() + } + + /// Splits the page range in two, with the second having the given length in pages. + #[requires(split_len < self.len_pages())] + pub fn split(&mut self, split_len: usize) { + // Get the old header. After this point, `self.ptr` is considered uninitialized, since + // we've moved out of it, so we can't panic. + // + // SAFETY: The invariants of the type ensure that the header is present and owned by us. + let old_header = unsafe { self.ptr.read() }; + + // We call the two new nodes `a` and `b`. + let a_len = old_header.len_pages - split_len; + let b_len = split_len; + // SAFETY: The invariants of the type ensure this is still in-bounds, since + // the header must have been valid and `a_len <= old_header.len_pages`. + let b_ptr: NonNull<[u8; PAGE_SIZE]> = unsafe { self.ptr().add(a_len) }; + + // Construct a new node for `b`. + // + // SAFETY: The safety invariants are simply inherited from the memory being valid in the + // first place, except for the `len_pages` invariant. This is upheld because the length + // math is correct. + // + // The assertion panic in `FreeListPtr::new()` must be unreachable, or it would have been + // triggered when constructing this type in the first place. + let b = unsafe { FreeListPtr::new(b_ptr, b_len, old_header.next) }; + + // Reinitialize the header for `a`. After this point, `self.ptr` is considered initialized + // again, so we may panic again. + // + // SAFETY: The safety invariants are simply inherited from the memory being valid in the + // first place, except for the `len_pages` invariant. This is upheld because the length + // math is correct. + unsafe { + self.ptr.write(FreeListNodeHeader { + next: Some(b), + len_pages: a_len, + }); + } + } + + /// Unlinks and returns the _next_ node, returning its pointer and length. + pub fn unlink_next(&mut self) -> Option<(NonNull<[u8; PAGE_SIZE]>, usize)> { + // SAFETY: We uphold the invariants. + let header = unsafe { self.header_mut() }; + let next = header.next.take()?; + let (next_ptr, next_header) = next.consume(); + header.next = next_header.next; + Some((next_ptr, next_header.len_pages)) + } +} + +impl<'allocator, const PAGE_SIZE: usize> fmt::Debug for FreeListPtr<'allocator, PAGE_SIZE> { + fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { + write!(fmt, "[{:p} × {}]", self.ptr, self.len_pages()) + } +} + +#[derive(Debug)] +struct FreeListNodeHeader<'allocator, const PAGE_SIZE: usize> { + /// The next node in the linked list. + next: Option>, + + /// The length of the allocation in pages. + len_pages: usize, +} + +/// Returns an iterator over power-of-two-sized subslices of this slice, which are returned from +/// smallest to largest. +pub fn power_of_two_subslices_mut(slice: &mut [T]) -> impl Iterator { + // Decompose the slice to its raw parts. Yep, we're gonna be doing unsafe stuff. + let mut ptr = slice.as_mut_ptr(); + let mut len = slice.len(); + + iter::from_fn(move || { + if len == 0 { + None + } else { + // Make the slice to return. + // + // SAFETY: The pointer and length must be valid, since we got them from the valid + // slice. Before returning `out`, we advance them, so that we never give out multiple + // exclusive references to the same subslice. + let out_len = 1 << len.trailing_zeros(); + let out = unsafe { slice::from_raw_parts_mut(ptr, out_len) }; + + // Advance the pointer and length. + // + // SAFETY: out_len < len, and we got len from an existing slice. + ptr = unsafe { ptr.add(out_len) }; + len -= out_len; + + Some(out) + } + }) +} + +#[test] +fn power_of_two_subslices_mut_test() { + extern crate std; + use std::vec::Vec; + + let mut data = [0, 1, 2, 3, 4, 5, 6, 7, 8]; + let subslices = power_of_two_subslices_mut(&mut data).collect::>(); + + assert_eq!(subslices, &[&[0] as &[_], &[1, 2, 3, 4, 5, 6, 7, 8]]); +} diff --git a/crates/utils/Cargo.toml b/crates/utils/Cargo.toml new file mode 100644 index 0000000..5b55a5c --- /dev/null +++ b/crates/utils/Cargo.toml @@ -0,0 +1,8 @@ +[package] +name = "vernos_utils" +version = "0.1.0" +edition = "2021" +publish = false + +[dependencies] +contracts = { version = "0.6.3", default-features = false } diff --git a/crates/utils/src/lib.rs b/crates/utils/src/lib.rs new file mode 100644 index 0000000..57143bc --- /dev/null +++ b/crates/utils/src/lib.rs @@ -0,0 +1,3 @@ +//! Common utilities. + +pub mod pin; diff --git a/crates/utils/src/pin.rs b/crates/utils/src/pin.rs new file mode 100644 index 0000000..202904d --- /dev/null +++ b/crates/utils/src/pin.rs @@ -0,0 +1,25 @@ +//! Utilities having to do with pinning. I sure hope these are sound! + +use contracts::requires; +use core::pin::Pin; +use std::ptr::NonNull; + +/// Iterates over projections of elements out of a pinned slice. +pub fn pin_project_slice_mut_iter(slice: Pin<&mut [T]>) -> impl Iterator> { + let base_ptr: NonNull = NonNull::from(slice.as_ref().get_ref()).cast(); + (0..slice.len()).map(move |i| { + // SAFETY: This is in-bounds, since the original slice was valid. No other references to + // the data can exist, since we visit each index once and have an exclusive borrow on the + // slice. + let ptr = unsafe { base_ptr.add(i).as_mut() }; + // SAFETY: This is not certainly sound; see https://github.com/rust-lang/rust/issues/104108 + unsafe { Pin::new_unchecked(ptr) } + }) +} + +/// Projects a single element out of a pinned slice. +#[requires(index < slice.len())] +pub fn pin_project_slice_mut(slice: Pin<&mut [T]>, index: usize) -> Pin<&mut T> { + // SAFETY: This is not certainly sound; see https://github.com/rust-lang/rust/issues/104108 + unsafe { slice.map_unchecked_mut(|slice| &mut slice[index]) } +} -- cgit v1.2.3