From bdc5f0702a85fa2b8c84c12a78afee95915be4ab Mon Sep 17 00:00:00 2001 From: Nathan Ringo Date: Sun, 1 Sep 2024 13:33:31 -0500 Subject: Fix a bitset indexing bug, change a panic to be more informative. --- crates/alloc_buddy/src/bitset.rs | 88 ++++++++++++++++++++++++++++++++++++++++ crates/alloc_buddy/src/bitvec.rs | 77 ----------------------------------- crates/alloc_buddy/src/lib.rs | 16 +++++--- crates/alloc_buddy/src/tree.rs | 26 +++++++----- 4 files changed, 114 insertions(+), 93 deletions(-) create mode 100644 crates/alloc_buddy/src/bitset.rs delete mode 100644 crates/alloc_buddy/src/bitvec.rs (limited to 'crates') diff --git a/crates/alloc_buddy/src/bitset.rs b/crates/alloc_buddy/src/bitset.rs new file mode 100644 index 0000000..b5f12d2 --- /dev/null +++ b/crates/alloc_buddy/src/bitset.rs @@ -0,0 +1,88 @@ +use contracts::requires; +use core::fmt; + +/// A fixed-length vector of bits used for determining whether a subregion is in the free lists or +/// not. +pub struct Bitset([usize]); + +impl Bitset { + /// Retrieves the value of a bit from the bitset. + #[requires(i < self.len())] + pub fn get(&self, i: usize) -> SubregionStatus { + let word_index = i / usize::BITS as usize; + let subword_index = i % usize::BITS as usize; + let one_hot = 1 << subword_index; + if (self.0[word_index] & one_hot) == 0 { + SubregionStatus::NotInFreeList + } else { + SubregionStatus::InFreeList + } + } + + /// Returns the number of bits in the bitset. + pub fn len(&self) -> usize { + self.0.len() * usize::BITS as usize + } + + /// Replaces a bit in the bitset. + #[requires(i < self.len())] + pub fn replace( + &mut self, + i: usize, + status_before: SubregionStatus, + status_after: SubregionStatus, + ) -> Result<(), UnexpectedBitsetState> { + if self.get(i) == status_before { + self.set(i, status_after); + Ok(()) + } else { + Err(UnexpectedBitsetState) + } + } + + /// Sets the value of a bit in the bitset. + #[requires(i < self.len())] + pub fn set(&mut self, i: usize, status: SubregionStatus) { + let word_index = i / usize::BITS as usize; + let subword_index = i % usize::BITS as usize; + let one_hot = 1 << subword_index; + match status { + SubregionStatus::NotInFreeList => { + self.0[word_index] &= !one_hot; + } + SubregionStatus::InFreeList => { + self.0[word_index] |= one_hot; + } + } + } +} + +impl fmt::Debug for Bitset { + fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { + write!(fmt, "Bitset(")?; + for i in 0..self.len() { + write!( + fmt, + "{}", + match self.get(i) { + SubregionStatus::NotInFreeList => '0', + SubregionStatus::InFreeList => '1', + } + )?; + } + write!(fmt, ")") + } +} + +/// An error returned when the `replace` method does not find the expected bit. +pub struct UnexpectedBitsetState; + +/// The status of a subregion, as tracked by `Bitset`. +#[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)] +pub enum SubregionStatus { + /// The region is not in the free list. + NotInFreeList = 0, + + /// The region is in the free list. + InFreeList = 1, +} diff --git a/crates/alloc_buddy/src/bitvec.rs b/crates/alloc_buddy/src/bitvec.rs deleted file mode 100644 index 5cabc5e..0000000 --- a/crates/alloc_buddy/src/bitvec.rs +++ /dev/null @@ -1,77 +0,0 @@ -use contracts::requires; -use core::{fmt, mem::transmute}; - -/// A fixed-length vector of bits used for determining whether a subregion is in the free lists or -/// not. -pub struct Bitset([usize]); - -impl Bitset { - fn from_mut(words: &mut [usize]) -> &mut Bitset { - // SAFETY: The types have a newtype relationship. - unsafe { transmute(words) } - } - - fn from_ref(words: &[usize]) -> &Bitset { - // SAFETY: The types have a newtype relationship. - unsafe { transmute(words) } - } - - /// Retrieves the value of a bit from the Bitset. - #[requires(i < self.len())] - pub fn get(&self, i: usize) -> SubregionStatus { - let word_index = i / usize::BITS as usize; - let subword_index = i % usize::BITS as usize; - let one_hot = 1 << subword_index; - if (self.0[word_index] & one_hot) == 0 { - SubregionStatus::NotInFreeList - } else { - SubregionStatus::InFreeList - } - } - - /// Returns whether the Bitset is empty. - pub fn is_empty(&self) -> bool { - self.0.is_empty() - } - - /// Returns the number of bits in the Bitset. - pub fn len(&self) -> usize { - self.0.len() * usize::BITS as usize - } - - /// Sets the value of a bit in the Bitset. - #[requires(i < self.len())] - pub fn set(&mut self, i: usize, status: SubregionStatus) { - let word_index = i / usize::BITS as usize; - let subword_index = i % usize::BITS as usize; - let one_hot = 1 << subword_index; - match status { - SubregionStatus::NotInFreeList => { - self.0[word_index] &= !one_hot; - } - SubregionStatus::InFreeList => { - self.0[word_index] |= one_hot; - } - } - } -} - -impl fmt::Debug for Bitset { - fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { - write!(fmt, "Bitset(")?; - for word in &self.0 { - write!(fmt, "{word:064b}")?; - } - write!(fmt, ")") - } -} - -/// The status of a subregion, as tracked by `Bitset`. -#[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)] -pub enum SubregionStatus { - /// The region is not in the free list. - NotInFreeList = 0, - - /// The region is in the free list. - InFreeList = 1, -} diff --git a/crates/alloc_buddy/src/lib.rs b/crates/alloc_buddy/src/lib.rs index d0d4818..fc5d17e 100644 --- a/crates/alloc_buddy/src/lib.rs +++ b/crates/alloc_buddy/src/lib.rs @@ -44,12 +44,12 @@ extern crate std; // TODO: Remove me -mod bitvec; +mod bitset; mod free_list; mod tree; use crate::{ - bitvec::{Bitset, SubregionStatus}, + bitset::{Bitset, SubregionStatus}, free_list::{FreeList, FreeListNode}, tree::Tree, }; @@ -230,7 +230,9 @@ impl< unsafe { free_list.push(tree.base_ptr.unwrap().cast()) }; // Then, set a bit in the bitset to say that this region is present. - tree.bitset_mark_as_present(bitset, tree.size_class, 0); + let Ok(()) = tree.bitset_mark_as_present(bitset, tree.size_class, 0) else { + panic!("the first bit was already set in {tree:#?}\nbitset = {bitset:?}") + }; } } @@ -253,7 +255,9 @@ impl< let tree = &mut self.trees[tree_index]; // Mark the pointer as no longer being in the tree. - tree.bitset_mark_as_absent(&mut self.bitset, size_class, offset); + let Ok(()) = tree.bitset_mark_as_absent(self.bitset, size_class, offset) else { + panic!("the bit for tree {tree_index}, offset {offset} was not set in {self:#?}") + }; // Return the pointer. Ok(ptr) @@ -289,7 +293,9 @@ impl< } // Mark the pointer as being in the tree. - tree.bitset_mark_as_present(&mut self.bitset, size_class, offset); + let Ok(()) = tree.bitset_mark_as_present(self.bitset, size_class, offset) else { + panic!("the bit for tree {tree_index}, offset {offset} was already set in {self:#?}") + }; // Return the pointer to the appropriate free list. self.free_list(size_class).push(ptr); diff --git a/crates/alloc_buddy/src/tree.rs b/crates/alloc_buddy/src/tree.rs index 72ee466..b713285 100644 --- a/crates/alloc_buddy/src/tree.rs +++ b/crates/alloc_buddy/src/tree.rs @@ -1,4 +1,4 @@ -use crate::bitvec::{Bitset, SubregionStatus}; +use crate::bitset::{Bitset, SubregionStatus, UnexpectedBitsetState}; use contracts::requires; use core::ptr::NonNull; @@ -56,8 +56,8 @@ impl<'buddy, const PAGE_SIZE: usize, const PAGE_SIZE_BITS: usize> // Next, find our index in the size class. let bits_skipped_for_index = offset_bytes >> (PAGE_SIZE_BITS + size_class); - // The sum of those two is simply our index. - bits_skipped_for_size_class + bits_skipped_for_index + // The sum of those two with our offset is simply our index. + self.bitset_offset + bits_skipped_for_size_class + bits_skipped_for_index } /// Changes a bit in the bitset from `InFreeList` to `NotInFreeList`. @@ -69,10 +69,12 @@ impl<'buddy, const PAGE_SIZE: usize, const PAGE_SIZE_BITS: usize> bitset: &mut Bitset, size_class: usize, offset_bytes: usize, - ) { - let index = self.bitset_index(size_class, offset_bytes); - assert_eq!(bitset.get(index), SubregionStatus::InFreeList); - bitset.set(index, SubregionStatus::NotInFreeList) + ) -> Result<(), UnexpectedBitsetState> { + bitset.replace( + self.bitset_index(size_class, offset_bytes), + SubregionStatus::InFreeList, + SubregionStatus::NotInFreeList, + ) } /// Changes a bit in the bitset from `NotInFreeList` to `InFreeList`. @@ -84,10 +86,12 @@ impl<'buddy, const PAGE_SIZE: usize, const PAGE_SIZE_BITS: usize> bitset: &mut Bitset, size_class: usize, offset_bytes: usize, - ) { - let index = self.bitset_index(size_class, offset_bytes); - assert_eq!(bitset.get(index), SubregionStatus::NotInFreeList); - bitset.set(index, SubregionStatus::InFreeList) + ) -> Result<(), UnexpectedBitsetState> { + bitset.replace( + self.bitset_index(size_class, offset_bytes), + SubregionStatus::NotInFreeList, + SubregionStatus::InFreeList, + ) } /// Returns whether the tree contains an address. -- cgit v1.2.3