Implements block merging and fixes a provenance bug.

1 files changed, 57 insertions, 12 deletions

diff --git a/crates/alloc_buddy/src/tree.rs b/crates/alloc_buddy/src/tree.rs
index b713285..787af21 100644
--- a/crates/alloc_buddy/src/tree.rs
+++ b/crates/alloc_buddy/src/tree.rs
@@ -1,13 +1,13 @@
 use crate::bitset::{Bitset, SubregionStatus, UnexpectedBitsetState};
 use contracts::requires;
-use core::ptr::NonNull;
+use core::{fmt, ptr::NonNull};
 
 /// 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> {
+pub struct Tree<const PAGE_SIZE: usize, const PAGE_SIZE_BITS: usize> {
     /// The base address of the tree.
     pub base_ptr: Option<NonNull<[u8; PAGE_SIZE]>>,
 
@@ -16,13 +16,9 @@ pub struct Tree<'buddy, const PAGE_SIZE: usize, const PAGE_SIZE_BITS: usize> {
 
     /// The offset in the bitset to the bits responsible for this tree's pages.
     pub bitset_offset: usize,
-
-    phantom: core::marker::PhantomData<&'buddy mut [u8; PAGE_SIZE]>,
 }
 
-impl<'buddy, const PAGE_SIZE: usize, const PAGE_SIZE_BITS: usize>
-    Tree<'buddy, PAGE_SIZE, PAGE_SIZE_BITS>
-{
+impl<const PAGE_SIZE: usize, const PAGE_SIZE_BITS: usize> Tree<PAGE_SIZE, PAGE_SIZE_BITS> {
     /// Returns the base address of the tree.
     #[requires(self.base_ptr.is_some())]
     pub fn base_addr(&self) -> usize {
@@ -31,11 +27,11 @@ impl<'buddy, const PAGE_SIZE: usize, const PAGE_SIZE_BITS: usize>
 
     /// Reads a bit from the bitset.
     #[requires(size_class <= self.size_class)]
-    #[requires(offset_bytes <= (PAGE_SIZE << self.size_class))]
+    #[requires(offset_bytes < (PAGE_SIZE << (self.size_class + 1)))]
     #[requires(offset_bytes.trailing_zeros() as usize >= PAGE_SIZE_BITS + size_class)]
     pub fn bitset_get(
         &self,
-        bitset: &mut Bitset,
+        bitset: &Bitset,
         size_class: usize,
         offset_bytes: usize,
     ) -> SubregionStatus {
@@ -45,7 +41,7 @@ impl<'buddy, const PAGE_SIZE: usize, const PAGE_SIZE_BITS: usize>
     /// Returns the index of a bit in the bitset that corresponds to the given size class and
     /// offset.
     #[requires(size_class <= self.size_class)]
-    #[requires(offset_bytes <= (PAGE_SIZE << self.size_class))]
+    #[requires(offset_bytes < (PAGE_SIZE << (self.size_class + 1)))]
     #[requires(offset_bytes.trailing_zeros() as usize >= PAGE_SIZE_BITS + size_class)]
     fn bitset_index(&self, size_class: usize, offset_bytes: usize) -> usize {
         // We store the largest size classes first in the bitset. Count how many we are away from
@@ -62,7 +58,7 @@ impl<'buddy, const PAGE_SIZE: usize, const PAGE_SIZE_BITS: usize>
 
     /// Changes a bit in the bitset from `InFreeList` to `NotInFreeList`.
     #[requires(size_class <= self.size_class)]
-    #[requires(offset_bytes <= (PAGE_SIZE << self.size_class))]
+    #[requires(offset_bytes < (PAGE_SIZE << (self.size_class + 1)))]
     #[requires(offset_bytes.trailing_zeros() as usize >= PAGE_SIZE_BITS + size_class)]
     pub fn bitset_mark_as_absent(
         &self,
@@ -79,7 +75,7 @@ impl<'buddy, const PAGE_SIZE: usize, const PAGE_SIZE_BITS: usize>
 
     /// Changes a bit in the bitset from `NotInFreeList` to `InFreeList`.
     #[requires(size_class <= self.size_class)]
-    #[requires(offset_bytes <= (PAGE_SIZE << self.size_class))]
+    #[requires(offset_bytes < (PAGE_SIZE << (self.size_class + 1)))]
     #[requires(offset_bytes.trailing_zeros() as usize >= PAGE_SIZE_BITS + size_class)]
     pub fn bitset_mark_as_present(
         &self,
@@ -101,4 +97,53 @@ impl<'buddy, const PAGE_SIZE: usize, const PAGE_SIZE_BITS: usize>
         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)
+    }
 }