More buddy work, but we've got UB again... This time relating to stacked borrows...

1 files changed, 36 insertions, 18 deletions

diff --git a/crates/buddy_allocator/src/bitvec.rs b/crates/buddy_allocator/src/bitvec.rs
index 856d579..5cabc5e 100644
--- a/crates/buddy_allocator/src/bitvec.rs
+++ b/crates/buddy_allocator/src/bitvec.rs
@@ -1,59 +1,77 @@
 use contracts::requires;
 use core::{fmt, mem::transmute};
 
-/// A fixed-length vector of bits.
-pub struct BitVec([usize]);
+/// A fixed-length vector of bits used for determining whether a subregion is in the free lists or
+/// not.
+pub struct Bitset([usize]);
 
-impl BitVec {
-    fn from_mut(words: &mut [usize]) -> &mut BitVec {
+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]) -> &BitVec {
+    fn from_ref(words: &[usize]) -> &Bitset {
         // SAFETY: The types have a newtype relationship.
         unsafe { transmute(words) }
     }
 
-    /// Retrieves the value of a bit from the BitVec.
+    /// Retrieves the value of a bit from the Bitset.
     #[requires(i < self.len())]
-    pub fn get(&self, i: usize) -> bool {
+    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;
-        (self.0[word_index] & one_hot) != 0
+        if (self.0[word_index] & one_hot) == 0 {
+            SubregionStatus::NotInFreeList
+        } else {
+            SubregionStatus::InFreeList
+        }
     }
 
-    /// Returns whether the BitVec is empty.
+    /// Returns whether the Bitset is empty.
     pub fn is_empty(&self) -> bool {
         self.0.is_empty()
     }
 
-    /// Returns the number of bits in the BitVec.
+    /// 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 BitVec.
+    /// Sets the value of a bit in the Bitset.
     #[requires(i < self.len())]
-    pub fn set(&mut self, i: usize, value: bool) {
+    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;
-        if value {
-            self.0[word_index] |= one_hot;
-        } else {
-            self.0[word_index] &= !one_hot;
+        match status {
+            SubregionStatus::NotInFreeList => {
+                self.0[word_index] &= !one_hot;
+            }
+            SubregionStatus::InFreeList => {
+                self.0[word_index] |= one_hot;
+            }
         }
     }
 }
 
-impl fmt::Debug for BitVec {
+impl fmt::Debug for Bitset {
     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
-        write!(fmt, "BitVec(")?;
+        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,
+}