diff options
Diffstat (limited to 'crates/alloc_buddy/src/tree.rs')
| -rw-r--r-- | crates/alloc_buddy/src/tree.rs | 69 |
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) + } } |