Rename crates.

1 files changed, 164 insertions, 0 deletions

diff --git a/crates/alloc_buddy/src/free_list.rs b/crates/alloc_buddy/src/free_list.rs
new file mode 100644
index 0000000..9b470fd
--- /dev/null
+++ b/crates/alloc_buddy/src/free_list.rs
@@ -0,0 +1,164 @@
+//! A circular doubly-linked list of power-of-two-sized subregions.
+
+use contracts::{ensures, requires};
+use core::{fmt, ptr::NonNull};
+
+/// The magic number a non-sentinel node should have.
+const FREE_NODE_MAGIC: u64 = u64::from_ne_bytes(*b"FREENODE");
+
+/// The magic number set into the spot for a node's magic number when it is initialized, but not
+/// linked into a list.
+const INITED_NODE_MAGIC: u64 = u64::from_ne_bytes(*b"NODEINIT");
+
+/// The magic number a sentinel node should have.
+const SENTINEL_MAGIC: u64 = u64::from_ne_bytes(*b"SENTINEL");
+
+/// The magic number set into the spot for a node's magic number when it gets unlinked.
+const USED_NODE_MAGIC: u64 = u64::from_ne_bytes(*b"ALLOC'ED");
+
+/// A pointer to the sentinel node of a circular doubly-linked list of power-of-two-sized subregions.
+pub struct FreeList(NonNull<FreeListNode>);
+
+impl FreeList {
+    /// Creates a free-list wrapper for a sentinel node's pointer.
+    ///
+    /// # Safety
+    ///
+    /// - `sentinel` must be a pointer to the sentinel of a valid circular doubly-linked list.
+    #[requires(unsafe { (*sentinel.as_ptr()).next }.is_some())]
+    #[requires(unsafe { (*sentinel.as_ptr()).prev }.is_some())]
+    #[requires(unsafe { (*sentinel.as_ptr()).magic } == SENTINEL_MAGIC)]
+    #[requires(unsafe { (*sentinel.as_ptr()).self_addr } == sentinel.as_ptr() as usize)]
+    pub unsafe fn from_sentinel(sentinel: NonNull<FreeListNode>) -> FreeList {
+        FreeList(sentinel)
+    }
+
+    /// Returns whether the free-list is empty.
+    pub fn is_empty(&self) -> bool {
+        let sentinel = self.0.as_ptr();
+        // SAFETY: This is sound as long as the sentinel was valid, which is a precondition of
+        // `FreeList::from_sentinel()`.
+        unsafe {
+            // UNWRAP: This is a precondition of the method.
+            let next = (*sentinel).next.unwrap();
+            (*sentinel).self_addr == next.as_ptr() as usize
+        }
+    }
+
+    /// Pops a subregion from the free-list, returning ownership to the caller.
+    pub fn pop(&mut self) -> Option<NonNull<u8>> {
+        if self.is_empty() {
+            // If the list is empty, return `None`.
+            None
+        } else {
+            // SAFETY: This is sound as long as the sentinel was valid, which is a precondition of
+            // `FreeList::from_sentinel()`.
+            unsafe {
+                // UNWRAP: In a valid circular doubly-linked list, the pointers are all non-null.
+                let node = (*self.0.as_ptr()).next.unwrap();
+                let prev = (*node.as_ptr()).prev.unwrap();
+                let next = (*node.as_ptr()).next.unwrap();
+
+                (*prev.as_ptr()).next = Some(next);
+                (*next.as_ptr()).prev = Some(prev);
+
+                (*node.as_ptr()).next = None;
+                (*node.as_ptr()).prev = None;
+                (*node.as_ptr()).magic = USED_NODE_MAGIC;
+                Some(node.cast())
+            }
+        }
+    }
+
+    /// 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, subregion_ptr: NonNull<u8>) {
+        let node = FreeListNode::init(subregion_ptr);
+
+        let prev = self.0;
+        // UNWRAP: In a valid circular doubly-linked list, the pointers are all non-null.
+        let next = (*self.0.as_ptr()).next.unwrap();
+
+        (*node.as_ptr()).prev = Some(prev);
+        (*node.as_ptr()).next = Some(next);
+        (*node.as_ptr()).magic = FREE_NODE_MAGIC;
+
+        (*prev.as_ptr()).next = Some(node);
+        (*next.as_ptr()).prev = Some(node);
+    }
+}
+
+/// 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 {
+        // SAFETY: This is sound as long as the sentinel was valid, which is a precondition of
+        // `FreeList::from_sentinel()`.
+        let sentinel_addr = unsafe { (*self.0.as_ptr()).self_addr };
+
+        let mut fmt = fmt.debug_list();
+        let mut ptr = self.0;
+        loop {
+            // 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_ptr()).next.unwrap() };
+            if unsafe { (*ptr.as_ptr()).self_addr } == sentinel_addr {
+                break fmt.finish();
+            }
+            fmt.entry(&ptr);
+        }
+    }
+}
+
+/// A node in a free list. This should not be moved without careful thought.
+///
+/// This type is valid when zero-initialized.
+///
+/// # Safety
+///
+/// - This type is valid only if it is zero-initialized or if it contains a valid circular
+///   doubly-linked list of subregions of the correct size, which it owns.
+#[derive(Debug)]
+pub struct FreeListNode {
+    next: Option<NonNull<FreeListNode>>,
+    prev: Option<NonNull<FreeListNode>>,
+    magic: u64,
+    self_addr: usize,
+}
+
+impl FreeListNode {
+    /// Initializes a sentinel node.
+    ///
+    /// # Safety
+    ///
+    /// The pointer must convey exclusive access and point to a large-enough allocation.
+    #[ensures(unsafe { (*ptr.as_ptr()).magic } == SENTINEL_MAGIC)]
+    #[ensures(unsafe { (*ptr.as_ptr()).self_addr } == ptr.as_ptr() as usize)]
+    pub unsafe fn init_sentinel(ptr: NonNull<FreeListNode>) {
+        (*ptr.as_ptr()).next = Some(ptr);
+        (*ptr.as_ptr()).prev = Some(ptr);
+        (*ptr.as_ptr()).magic = SENTINEL_MAGIC;
+        (*ptr.as_ptr()).self_addr = ptr.as_ptr() as usize;
+    }
+
+    /// Initializes a non-sentinel node.
+    ///
+    /// # Safety
+    ///
+    /// The pointer must convey ownership and point to a large-enough allocation.
+    #[ensures(ptr.as_ptr() as usize == ret.as_ptr() as usize)]
+    #[ensures(unsafe { (*ret.as_ptr()).magic } == INITED_NODE_MAGIC)]
+    #[ensures(unsafe { (*ret.as_ptr()).self_addr } == ptr.as_ptr() as usize)]
+    unsafe fn init(ptr: NonNull<u8>) -> NonNull<FreeListNode> {
+        let ptr = ptr.cast();
+        ptr.write(FreeListNode {
+            next: None,
+            prev: None,
+            magic: INITED_NODE_MAGIC,
+            self_addr: ptr.as_ptr() as usize,
+        });
+        ptr
+    }
+}