1 files changed, 63 insertions, 6 deletions

diff --git a/crates/buddy_allocator/src/free_list.rs b/crates/buddy_allocator/src/free_list.rs
index 5a633c3..2e3afe2 100644
--- a/crates/buddy_allocator/src/free_list.rs
+++ b/crates/buddy_allocator/src/free_list.rs
@@ -1,6 +1,11 @@
 //! A doubly-linked list of power-of-two-sized subregions.
 
-use core::{marker::PhantomPinned, pin::Pin, ptr};
+use core::{
+    fmt,
+    marker::PhantomPinned,
+    pin::Pin,
+    ptr::{self, NonNull},
+};
 
 /// The magic number a non-sentinel node should have.
 const FREE_NODE_MAGIC: u64 = u64::from_ne_bytes(*b"FREENODE");
@@ -11,21 +16,51 @@ const SENTINEL_MAGIC: u64 = u64::from_ne_bytes(*b"SENTINEL");
 /// A doubly-linked list of power-of-two-sized subregions.
 ///
 /// This type is valid when zero-initialized.
-#[derive(Debug)]
+///
+/// # Safety
+///
+/// - This type is valid only if it is zero-initialized or if it contains a valid doubly-linked
+///   list of subregions of the correct size, which it owns.
 pub struct FreeList {
     sentinel: FreeListNode,
 }
 
 impl FreeList {
+    /// Pushes a subregion into the free-list.
+    ///
+    /// # Safety
+    ///
+    /// - `subregion_ptr` must convey ownership over untyped memory of the correct size.
+    pub unsafe fn push(mut self: Pin<&mut FreeList>, subregion_ptr: NonNull<u8>) {
+        assert_ne!(self.sentinel.next, ptr::null_mut());
+        assert_ne!(self.sentinel.prev, ptr::null_mut());
+
+        // Write the header the node should have to the node.
+        let sentinel = &self.sentinel as *const FreeListNode as *mut FreeListNode;
+        let next = *self.as_mut().sentinel().next_mut();
+        let node = subregion_ptr.cast();
+        node.write(FreeListNode {
+            next,
+            prev: sentinel,
+            magic: FREE_NODE_MAGIC,
+            _phantom: PhantomPinned,
+        });
+
+        // Link the node into the list.
+        *self.sentinel().next_mut() = node.as_ptr();
+        (*next).prev = node.as_ptr();
+    }
+
     /// Performs self-linking. This must be done before the free list is used in any other way.
-    pub fn self_link(mut self: Pin<&mut FreeList>) {
+    pub fn self_link(self: Pin<&mut FreeList>) {
         assert_eq!(self.sentinel.next, ptr::null_mut());
         assert_eq!(self.sentinel.prev, ptr::null_mut());
 
-        let self_ptr = &self.sentinel as *const FreeListNode as *mut FreeListNode;
         let mut sentinel = self.sentinel_unchecked();
-        *sentinel.as_mut().next_mut() = self_ptr;
-        *sentinel.as_mut().prev_mut() = self_ptr;
+        // SAFETY: We do not use this pointer to move out of the sentinel.
+        let sentinel_ptr = unsafe { sentinel.as_mut().get_unchecked_mut() as *mut FreeListNode };
+        *sentinel.as_mut().next_mut() = sentinel_ptr;
+        *sentinel.as_mut().prev_mut() = sentinel_ptr;
         *sentinel.as_mut().magic_mut() = SENTINEL_MAGIC;
     }
 
@@ -43,6 +78,28 @@ 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 {
+        assert_ne!(self.sentinel.next, ptr::null_mut());
+        assert_ne!(self.sentinel.prev, ptr::null_mut());
+
+        let sentinel = &self.sentinel as *const FreeListNode;
+
+        // SAFETY: The invariants of FreeList guarantee that the list is valid. In a valid list,
+        // the next pointer is always valid and non-null.
+        let mut ptr = unsafe { sentinel.as_ref().unwrap().next as *const FreeListNode };
+        let mut fmt = fmt.debug_list();
+        while ptr != sentinel {
+            fmt.entry(&ptr);
+            // SAFETY: The invariants of FreeList guarantee that the list is valid. In a valid
+            // list, the next pointer is always valid and non-null.
+            ptr = unsafe { ptr.as_ref().unwrap().next as *const FreeListNode };
+        }
+        fmt.finish()
+    }
+}
+
 #[derive(Debug)]
 struct FreeListNode {
     next: *mut FreeListNode,