1 files changed, 72 insertions, 0 deletions
diff --git a/crates/buddy_allocator/src/free_list.rs b/crates/buddy_allocator/src/free_list.rs
new file mode 100644
index 0000000..5a633c3
--- /dev/null
+++ b/crates/buddy_allocator/src/free_list.rs
@@ -0,0 +1,72 @@
+//! A doubly-linked list of power-of-two-sized subregions.
+
+use core::{marker::PhantomPinned, pin::Pin, ptr};
+
+/// The magic number a non-sentinel node should have.
+const FREE_NODE_MAGIC: u64 = u64::from_ne_bytes(*b"FREENODE");
+
+/// The magic number a sentinel node should have.
+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)]
+pub struct FreeList {
+    sentinel: FreeListNode,
+}
+
+impl FreeList {
+    /// 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>) {
+        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;
+        *sentinel.as_mut().magic_mut() = SENTINEL_MAGIC;
+    }
+
+    /// Projects the sentinel node out of the list.
+    fn sentinel(self: Pin<&mut FreeList>) -> Pin<&mut FreeListNode> {
+        let mut sentinel = self.sentinel_unchecked();
+        assert_eq!(*sentinel.as_mut().magic_mut(), SENTINEL_MAGIC);
+        sentinel
+    }
+
+    /// Projects the sentinel node out of the list, without checking the magic number.
+    fn sentinel_unchecked(self: Pin<&mut FreeList>) -> Pin<&mut FreeListNode> {
+        // SAFETY: sentinel is structurally pinned.
+        unsafe { self.map_unchecked_mut(|list| &mut list.sentinel) }
+    }
+}
+
+#[derive(Debug)]
+struct FreeListNode {
+    next: *mut FreeListNode,
+    prev: *mut FreeListNode,
+    magic: u64,
+    _phantom: PhantomPinned,
+}
+
+impl FreeListNode {
+    /// Projects the `next` pointer out of the node.
+    fn next_mut(self: Pin<&mut FreeListNode>) -> &mut *mut FreeListNode {
+        // SAFETY: next is not structurally pinned.
+        unsafe { &mut self.get_unchecked_mut().next }
+    }
+
+    /// Projects the `prev` pointer out of the node.
+    fn prev_mut(self: Pin<&mut FreeListNode>) -> &mut *mut FreeListNode {
+        // SAFETY: prev is structurally pinned.
+        unsafe { &mut self.get_unchecked_mut().prev }
+    }
+
+    /// Projects the `magic` number out of the node.
+    fn magic_mut(self: Pin<&mut FreeListNode>) -> &mut u64 {
+        // SAFETY: magic is structurally pinned.
+        unsafe { &mut self.get_unchecked_mut().magic }
+    }
+}