From 1867170d185c3480542773a74876175e341b91eb Mon Sep 17 00:00:00 2001 From: Nathan Ringo Date: Sun, 1 Sep 2024 18:32:38 -0500 Subject: Simplify debug printing of the buddy allocator. --- crates/Cargo.lock | 5 ++ crates/Cargo.toml | 2 +- crates/alloc_buddy/Cargo.toml | 1 + crates/alloc_buddy/src/free_list.rs | 1 - crates/alloc_buddy/src/lib.rs | 98 +++++++++++++++++++++++++------------ crates/alloc_buddy/src/tree.rs | 51 +------------------ crates/utils/Cargo.toml | 7 +++ crates/utils/src/lib.rs | 16 ++++++ 8 files changed, 97 insertions(+), 84 deletions(-) create mode 100644 crates/utils/Cargo.toml create mode 100644 crates/utils/src/lib.rs diff --git a/crates/Cargo.lock b/crates/Cargo.lock index 62c6ae4..7c772d4 100644 --- a/crates/Cargo.lock +++ b/crates/Cargo.lock @@ -307,6 +307,7 @@ dependencies = [ "proptest", "static_assertions", "vernos_alloc_physmem_free_list", + "vernos_utils", ] [[package]] @@ -317,6 +318,10 @@ dependencies = [ "contracts", ] +[[package]] +name = "vernos_utils" +version = "0.1.0" + [[package]] name = "winapi" version = "0.3.9" diff --git a/crates/Cargo.toml b/crates/Cargo.toml index 57dd03c..192869b 100644 --- a/crates/Cargo.toml +++ b/crates/Cargo.toml @@ -1,3 +1,3 @@ [workspace] -members = ["alloc_buddy", "alloc_physmem_free_list"] +members = ["alloc_buddy", "alloc_physmem_free_list", "utils"] resolver = "2" diff --git a/crates/alloc_buddy/Cargo.toml b/crates/alloc_buddy/Cargo.toml index 5e5c882..43e1cee 100644 --- a/crates/alloc_buddy/Cargo.toml +++ b/crates/alloc_buddy/Cargo.toml @@ -9,6 +9,7 @@ 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_alloc_physmem_free_list = { path = "../alloc_physmem_free_list" } +vernos_utils = { path = "../utils" } [dev-dependencies] proptest = { version = "0.9.6", default-features = false, features = ["std"] } diff --git a/crates/alloc_buddy/src/free_list.rs b/crates/alloc_buddy/src/free_list.rs index 973ad2c..803f5ad 100644 --- a/crates/alloc_buddy/src/free_list.rs +++ b/crates/alloc_buddy/src/free_list.rs @@ -82,7 +82,6 @@ impl FreeList { } } -/// This impl will panic until the sentinel has been self-linked. impl fmt::Debug for FreeList { fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { // SAFETY: This is sound as long as the sentinel was valid, which is a precondition of diff --git a/crates/alloc_buddy/src/lib.rs b/crates/alloc_buddy/src/lib.rs index a2a509b..bbed640 100644 --- a/crates/alloc_buddy/src/lib.rs +++ b/crates/alloc_buddy/src/lib.rs @@ -14,6 +14,7 @@ use allocator_api2::alloc::{AllocError, Layout, LayoutError}; use contracts::{ensures, requires}; use core::{fmt, mem, ptr::NonNull}; use vernos_alloc_physmem_free_list::FreeListAllocator; +use vernos_utils::debug; /// A buddy allocator. pub struct BuddyAllocator< @@ -409,42 +410,75 @@ impl< > fmt::Debug for BuddyAllocator<'allocator, PAGE_SIZE, PAGE_SIZE_BITS, SIZE_CLASS_COUNT> { fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { - struct FreeLists(NonNull); - - impl fmt::Debug for FreeLists { - fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { - fmt.debug_list() - .entries((0..SIZE_CLASS_COUNT).map(|size_class| { - // SAFETY: The free lists are kept valid, and the range of size classes is - // necessarily in-bounds. - unsafe { FreeList::from_sentinel(self.0.add(size_class)) } - })) - .finish() - } - } - - struct Bitsets<'allocator, const PAGE_SIZE: usize, const PAGE_SIZE_BITS: usize>( - &'allocator [Tree], - &'allocator Bitset, - ); - - impl<'allocator, const PAGE_SIZE: usize, const PAGE_SIZE_BITS: usize> fmt::Debug - for Bitsets<'allocator, PAGE_SIZE, PAGE_SIZE_BITS> - { - fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { - fmt.debug_list() - .entries(self.0.iter().map(|tree| tree.debug_bitset(self.1))) - .finish() - } - } - fmt.debug_struct("BuddyAllocator") .field( "free_lists", - &FreeLists::(self.free_list_sentinels), + &debug(|fmt| { + fmt.debug_list() + .entries((0..SIZE_CLASS_COUNT).map(|size_class| { + // SAFETY: The free lists are kept valid, and the range of size classes is + // necessarily in-bounds. + unsafe { + FreeList::from_sentinel(self.free_list_sentinels.add(size_class)) + } + })) + .finish() + }), + ) + .field( + "trees", + &debug(|fmt| { + fmt.debug_list() + .entries(self.trees.iter().map(|tree| { + let ptr_lo = tree.base_ptr.unwrap().as_ptr(); + let ptr_hi = ptr_lo.wrapping_add(1 << tree.size_class); + debug(move |fmt| { + fmt.debug_tuple("Tree") + .field(&debug(|fmt| { + write!( + fmt, + "{:?} ({} pages)", + (ptr_lo..ptr_hi), + 1 << tree.size_class + ) + })) + .field(&debug(move |fmt| { + fmt.debug_list() + .entries((0..=tree.size_class).rev().map( + |size_class| { + debug(move |fmt| { + for i in + 0..(1 << (tree.size_class - size_class)) + { + let offset_bytes = + i << (PAGE_SIZE_BITS + size_class); + let bit = match tree.bitset_get( + self.bitset, + size_class, + offset_bytes, + ) { + SubregionStatus::NotInFreeList => { + '0' + } + SubregionStatus::InFreeList => '1', + }; + write!(fmt, "{}", bit)?; + for _ in 0..(1 << size_class) - 1 { + write!(fmt, " ")?; + } + } + Ok(()) + }) + }, + )) + .finish() + })) + .finish() + }) + })) + .finish() + }), ) - .field("trees", &self.trees) - .field("bitsets", &Bitsets(self.trees, self.bitset)) .finish() } } diff --git a/crates/alloc_buddy/src/tree.rs b/crates/alloc_buddy/src/tree.rs index 787af21..e04605b 100644 --- a/crates/alloc_buddy/src/tree.rs +++ b/crates/alloc_buddy/src/tree.rs @@ -1,6 +1,6 @@ use crate::bitset::{Bitset, SubregionStatus, UnexpectedBitsetState}; use contracts::requires; -use core::{fmt, ptr::NonNull}; +use core::ptr::NonNull; /// A single region of the allocator. See the comment on the `crate::allocators::buddy` module for /// more information. @@ -97,53 +97,4 @@ impl Tree(&'a self, bitset: &'a Bitset) -> impl 'a + fmt::Debug { - struct BitsetSlice<'a, const PAGE_SIZE: usize, const PAGE_SIZE_BITS: usize>( - &'a Tree, - &'a Bitset, - usize, - ); - - impl<'a, const PAGE_SIZE: usize, const PAGE_SIZE_BITS: usize> fmt::Debug - for BitsetSlice<'a, PAGE_SIZE, PAGE_SIZE_BITS> - { - fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { - for i in 0..(1 << (self.0.size_class - self.2)) { - let offset_bytes = i << (PAGE_SIZE_BITS + self.2); - let bit = match self.0.bitset_get(self.1, self.2, offset_bytes) { - SubregionStatus::NotInFreeList => '0', - SubregionStatus::InFreeList => '1', - }; - write!(fmt, "{}", bit)?; - for _ in 0..(1 << self.2) - 1 { - write!(fmt, " ")?; - } - } - Ok(()) - } - } - - struct BitsetTree<'a, const PAGE_SIZE: usize, const PAGE_SIZE_BITS: usize>( - &'a Tree, - &'a Bitset, - ); - - impl<'a, const PAGE_SIZE: usize, const PAGE_SIZE_BITS: usize> fmt::Debug - for BitsetTree<'a, PAGE_SIZE, PAGE_SIZE_BITS> - { - fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { - fmt.debug_list() - .entries( - (0..=self.0.size_class) - .rev() - .map(|size_class| BitsetSlice(self.0, self.1, size_class)), - ) - .finish() - } - } - - BitsetTree(self, bitset) - } } diff --git a/crates/utils/Cargo.toml b/crates/utils/Cargo.toml new file mode 100644 index 0000000..a03aeac --- /dev/null +++ b/crates/utils/Cargo.toml @@ -0,0 +1,7 @@ +[package] +name = "vernos_utils" +version = "0.1.0" +edition = "2021" +publish = false + +[dependencies] diff --git a/crates/utils/src/lib.rs b/crates/utils/src/lib.rs new file mode 100644 index 0000000..248227a --- /dev/null +++ b/crates/utils/src/lib.rs @@ -0,0 +1,16 @@ +#![no_std] + +use core::fmt; + +/// Creates an ad-hoc `Debug` instance. +pub fn debug(f: impl Fn(&mut fmt::Formatter) -> fmt::Result) -> impl fmt::Debug { + struct Debug(F); + + impl fmt::Result> fmt::Debug for Debug { + fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { + (self.0)(fmt) + } + } + + Debug(f) +} -- cgit v1.2.3