Simplify debug printing of the buddy allocator.

8 files changed, 97 insertions, 84 deletions

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]]
@@ -318,6 +319,10 @@ dependencies = [
 ]
 
 [[package]]
+name = "vernos_utils"
+version = "0.1.0"
+
+[[package]]
 name = "winapi"
 version = "0.3.9"
 source = "registry+https://github.com/rust-lang/crates.io-index"
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<const SIZE_CLASS_COUNT: usize>(NonNull<FreeListNode>);
-
-        impl<const SIZE_CLASS_COUNT: usize> fmt::Debug for FreeLists<SIZE_CLASS_COUNT> {
-            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<PAGE_SIZE, PAGE_SIZE_BITS>],
-            &'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::<SIZE_CLASS_COUNT>(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<const PAGE_SIZE: usize, const PAGE_SIZE_BITS: usize> Tree<PAGE_SIZE, PAGE_S
         let tree_addr_hi = tree_addr_lo + (PAGE_SIZE << self.size_class);
         (tree_addr_lo..tree_addr_hi).contains(&addr)
     }
-
-    /// Formats the region of the bitset corresponding to this tree.
-    pub fn debug_bitset<'a>(&'a self, bitset: &'a Bitset) -> impl 'a + fmt::Debug {
-        struct BitsetSlice<'a, const PAGE_SIZE: usize, const PAGE_SIZE_BITS: usize>(
-            &'a Tree<PAGE_SIZE, PAGE_SIZE_BITS>,
-            &'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<PAGE_SIZE, PAGE_SIZE_BITS>,
-            &'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>(F);
+
+    impl<F: Fn(&mut fmt::Formatter) -> fmt::Result> fmt::Debug for Debug<F> {
+        fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
+            (self.0)(fmt)
+        }
+    }
+
+    Debug(f)
+}