Rename crates.

1 files changed, 0 insertions, 389 deletions

diff --git a/crates/physmem_free_list/src/lib.rs b/crates/physmem_free_list/src/lib.rs
deleted file mode 100644
index f99b30f..0000000
--- a/crates/physmem_free_list/src/lib.rs
+++ /dev/null
@@ -1,389 +0,0 @@
-//! A free-list allocator for physical memory ranges. This is only used when bootstrapping the
-//! buddy allocator, since it provides a way to store and manipulate physical memory ranges without
-//! needing a working allocator.
-#![no_std]
-
-use allocator_api2::alloc::{AllocError, Layout};
-use contracts::requires;
-use core::{fmt, iter, marker::PhantomData, mem::size_of, ptr::NonNull, slice};
-
-/// The free-list allocator.
-pub struct FreeListAllocator<'allocator, const PAGE_SIZE: usize> {
-    head: Option<FreeListPtr<'allocator, PAGE_SIZE>>,
-}
-
-impl<'allocator, const PAGE_SIZE: usize> FreeListAllocator<'allocator, PAGE_SIZE> {
-    /// Creates a new, empty allocator.
-    pub fn new() -> FreeListAllocator<'allocator, PAGE_SIZE> {
-        assert!(size_of::<FreeListNodeHeader<'allocator, PAGE_SIZE>>() <= PAGE_SIZE);
-
-        FreeListAllocator { head: None }
-    }
-
-    /// Pushes a page range into the free list.
-    ///
-    /// # Safety
-    ///
-    /// - `ptr` must be a pointer that conveys ownership over the page range.
-    /// - The page range must be untyped memory.
-    /// - The page range must be aligned to `PAGE_SIZE`.
-    /// - The page range must live for `'allocator`.
-    /// - `len_pages` must be accurate.
-    pub unsafe fn add(&mut self, ptr: NonNull<[u8; PAGE_SIZE]>, len_pages: usize) {
-        self.head = Some(FreeListPtr::new(ptr, len_pages, self.head.take()));
-    }
-
-    /// Allocates memory, *without necessarily removing it from the allocator*.
-    ///
-    /// The memory will only be removed from the allocator if there is a node from which no
-    /// additional pages would be able to be allocated into. If the node is not removed, the
-    /// returned pointer will not point into the first page, so it will not be altered by metadata
-    /// updates.
-    ///
-    /// Obviously, this is unsound to call while the previous allocation is alive. It is also
-    /// unsound to split any nodes after calling this, since splitting the node that was allocated
-    /// into might write the new node's metadata into that allocation.
-    pub unsafe fn allocate_without_always_removing_the_node(
-        &mut self,
-        layout: Layout,
-    ) -> Result<NonNull<[u8]>, AllocError> {
-        assert!(PAGE_SIZE.is_power_of_two());
-        let len_pages = (layout.size() + PAGE_SIZE - 1) >> PAGE_SIZE.trailing_zeros();
-
-        // Find the size of the smallest page range that would fit this.
-        let Some(selected_node_len) = self
-            .iter()
-            .map(|(_, range_len_pages)| range_len_pages)
-            .filter(|&range_len_pages| len_pages <= range_len_pages)
-            .min()
-        else {
-            return Err(AllocError);
-        };
-
-        if selected_node_len == len_pages {
-            // The less-scary case is when we're removing an entire node; we're just aiming to find
-            // it and unlink it.
-
-            // If the node we're looking for is the first one, slightly different code is used to
-            // unlink it.
-            let (ptr, unlinked_len_pages) = if self
-                .head
-                .as_ref()
-                .map(|node| node.len_pages() == len_pages)
-                .unwrap()
-            {
-                // In that case, just unlink the node and hand it back.
-                //
-                // UNWRAP: The list can't have been empty or .min() above would've returned None.
-                self.pop().unwrap()
-            } else {
-                // Otherwise, we need to iterate through the list to find the node before it.
-                let mut next = self.head.as_mut();
-                let mut node_before_node_to_remove = None;
-                while let Some(ptr) = next {
-                    if let Some(next_header) = &ptr.header().next {
-                        if next_header.len_pages() == selected_node_len {
-                            node_before_node_to_remove = Some(ptr);
-                            break;
-                        }
-                    }
-                    next = ptr.next_mut();
-                }
-
-                // UNWRAP: We had to find the node in the first place, so it must be in the list.
-                node_before_node_to_remove.unwrap().unlink_next().unwrap()
-            };
-
-            assert_eq!(len_pages, unlinked_len_pages);
-            Ok(NonNull::slice_from_raw_parts(
-                ptr.cast(),
-                len_pages * PAGE_SIZE,
-            ))
-        } else {
-            // The scary case is when we're trying to give back memory that's part of a different
-            // node. First, we need to iterate through the list to find the node.
-            let mut next = self.head.as_mut();
-            let mut node_to_steal_from = None;
-            while let Some(ptr) = next {
-                if ptr.len_pages() == selected_node_len {
-                    node_to_steal_from = Some(ptr);
-                    break;
-                }
-                next = ptr.next_mut();
-            }
-
-            // UNWRAP: We had to find the node in the first place, so it must be in the list.
-            let node_to_steal_from = node_to_steal_from.unwrap();
-
-            // Then, we can simply do the address arithmetic to get a pointer out with the right
-            // bounds.
-            //
-            // SAFETY: The node had sufficient length to add `selected_node_len`, so it must have
-            // sufficient length to add a lesser quantity.
-            let ptr = unsafe { node_to_steal_from.ptr().add(selected_node_len - len_pages) };
-
-            Ok(NonNull::slice_from_raw_parts(
-                ptr.cast(),
-                len_pages * PAGE_SIZE,
-            ))
-        }
-    }
-
-    /// Returns an iterator over the page ranges in the free list, as pairs of `ptr` and
-    /// `len_pages`. The returned pointers should not be accessed.
-    pub fn iter(&self) -> impl '_ + Iterator<Item = (NonNull<[u8; PAGE_SIZE]>, usize)> {
-        let mut next: Option<&_> = self.head.as_ref();
-        iter::from_fn(move || match next {
-            Some(ptr) => {
-                let out = (ptr.ptr(), ptr.len_pages());
-                next = ptr.next();
-                Some(out)
-            }
-            None => None,
-        })
-    }
-
-    /// Pops the first page range from the allocator and returns it, along with its length in pages.
-    pub fn pop(&mut self) -> Option<(NonNull<[u8; PAGE_SIZE]>, usize)> {
-        let node = self.head.take()?;
-        let (ptr, header) = node.consume();
-        self.head = header.next;
-        Some((ptr, header.len_pages))
-    }
-
-    /// Splits all the nodes until each page range is of a power-of-two size no larger than
-    /// `max_len_pages`.
-    pub fn split_to_powers_of_two_no_larger_than(&mut self, max_len_pages: usize) {
-        let mut next = self.head.as_mut();
-        while let Some(ptr) = next {
-            while ptr.len_pages() > max_len_pages {
-                ptr.split(max_len_pages);
-            }
-
-            while !ptr.len_pages().is_power_of_two() {
-                let log2_smaller_size = ptr.len_pages().trailing_zeros();
-                let smaller_size = 1 << log2_smaller_size;
-                ptr.split(smaller_size);
-            }
-
-            next = ptr.next_mut();
-        }
-    }
-}
-
-impl<'allocator, const PAGE_SIZE: usize> fmt::Debug for FreeListAllocator<'allocator, PAGE_SIZE> {
-    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
-        let mut next: Option<&_> = self.head.as_ref();
-        fmt.debug_list()
-            .entries(iter::from_fn(|| match next {
-                Some(ptr) => {
-                    next = ptr.next();
-                    Some(ptr)
-                }
-                None => None,
-            }))
-            .finish()
-    }
-}
-
-/// A pointer to a page range, which start with a header in the first page.
-///
-/// # Safety
-///
-/// - `ptr` must be a pointer that conveys ownership over the page range.
-/// - The page range must be untyped memory.
-/// - The page range must be non-empty.
-/// - The first page must have a correct header written to it.
-/// - The page range must live for `'allocator`.
-struct FreeListPtr<'allocator, const PAGE_SIZE: usize> {
-    ptr: NonNull<FreeListNodeHeader<'allocator, PAGE_SIZE>>,
-    _phantom: PhantomData<&'allocator FreeListNodeHeader<'allocator, PAGE_SIZE>>,
-}
-
-impl<'allocator, const PAGE_SIZE: usize> FreeListPtr<'allocator, PAGE_SIZE> {
-    /// Initialize the given page range as a node in the free list.
-    ///
-    /// # Safety
-    ///
-    /// - `ptr` must be a pointer that conveys ownership over the page range.
-    /// - The page range must be untyped memory.
-    /// - The page range must be aligned to `PAGE_SIZE`.
-    /// - The page range must live for `'allocator`.
-    /// - `len_pages` must be accurate.
-    #[requires(len_pages > 0)]
-    pub unsafe fn new(
-        ptr: NonNull<[u8; PAGE_SIZE]>,
-        len_pages: usize,
-        next: Option<FreeListPtr<'allocator, PAGE_SIZE>>,
-    ) -> FreeListPtr<'allocator, PAGE_SIZE> {
-        assert!(size_of::<FreeListNodeHeader<'allocator, PAGE_SIZE>>() <= PAGE_SIZE);
-
-        let ptr: NonNull<FreeListNodeHeader<'allocator, PAGE_SIZE>> = ptr.cast();
-        // SAFETY: The safety invariants plus the assertion guarantee this write is valid.
-        unsafe {
-            ptr.write(FreeListNodeHeader { next, len_pages });
-        }
-        FreeListPtr {
-            ptr,
-            _phantom: PhantomData,
-        }
-    }
-
-    /// Consumes the node, returning the pointer and header.
-    pub fn consume(
-        self,
-    ) -> (
-        NonNull<[u8; PAGE_SIZE]>,
-        FreeListNodeHeader<'allocator, PAGE_SIZE>,
-    ) {
-        // SAFETY: The invariants of the type ensure that the header is present and owned by us.
-        let header = unsafe { self.ptr.read() };
-        (self.ptr.cast(), header)
-    }
-
-    /// Returns a reference to the header of the page range.
-    fn header(&self) -> &FreeListNodeHeader<'allocator, PAGE_SIZE> {
-        // SAFETY: The invariants of the type ensure that the header is present and owned by us.
-        unsafe { self.ptr.as_ref() }
-    }
-
-    /// Returns an exclusive reference to the header of the page range.
-    ///
-    /// # Safety
-    ///
-    /// The invariants of the type must be upheld.
-    unsafe fn header_mut(&mut self) -> &mut FreeListNodeHeader<'allocator, PAGE_SIZE> {
-        // SAFETY: The invariants of the type ensure that the header is present and owned by us.
-        unsafe { self.ptr.as_mut() }
-    }
-
-    /// Returns the length of the node in pages.
-    pub fn len_pages(&self) -> usize {
-        self.header().len_pages
-    }
-
-    /// Returns a shared reference to the next node in the free list. Returns `None` when there
-    /// are no further nodes.
-    pub fn next(&self) -> Option<&FreeListPtr<'allocator, PAGE_SIZE>> {
-        self.header().next.as_ref()
-    }
-
-    /// Returns an exclusive reference to the next node in the free list. Returns `None` when there
-    /// are no further nodes.
-    pub fn next_mut(&mut self) -> Option<&mut FreeListPtr<'allocator, PAGE_SIZE>> {
-        // SAFETY: We just lend out the next pointer, which can't violate our invariants.
-        let header = unsafe { self.header_mut() };
-        header.next.as_mut()
-    }
-
-    /// Returns the underlying pointer. Using this may violate invariants.
-    pub fn ptr(&self) -> NonNull<[u8; PAGE_SIZE]> {
-        self.ptr.cast()
-    }
-
-    /// Splits the page range in two, with the second having the given length in pages.
-    #[requires(split_len < self.len_pages())]
-    pub fn split(&mut self, split_len: usize) {
-        // Get the old header. After this point, `self.ptr` is considered uninitialized, since
-        // we've moved out of it, so we can't panic.
-        //
-        // SAFETY: The invariants of the type ensure that the header is present and owned by us.
-        let old_header = unsafe { self.ptr.read() };
-
-        // We call the two new nodes `a` and `b`.
-        let a_len = old_header.len_pages - split_len;
-        let b_len = split_len;
-        // SAFETY: The invariants of the type ensure this is still in-bounds, since
-        // the header must have been valid and `a_len <= old_header.len_pages`.
-        let b_ptr: NonNull<[u8; PAGE_SIZE]> = unsafe { self.ptr().add(a_len) };
-
-        // Construct a new node for `b`.
-        //
-        // SAFETY: The safety invariants are simply inherited from the memory being valid in the
-        // first place, except for the `len_pages` invariant. This is upheld because the length
-        // math is correct.
-        //
-        // The assertion panic in `FreeListPtr::new()` must be unreachable, or it would have been
-        // triggered when constructing this type in the first place.
-        let b = unsafe { FreeListPtr::new(b_ptr, b_len, old_header.next) };
-
-        // Reinitialize the header for `a`. After this point, `self.ptr` is considered initialized
-        // again, so we may panic again.
-        //
-        // SAFETY: The safety invariants are simply inherited from the memory being valid in the
-        // first place, except for the `len_pages` invariant. This is upheld because the length
-        // math is correct.
-        unsafe {
-            self.ptr.write(FreeListNodeHeader {
-                next: Some(b),
-                len_pages: a_len,
-            });
-        }
-    }
-
-    /// Unlinks and returns the _next_ node, returning its pointer and length in pages.
-    pub fn unlink_next(&mut self) -> Option<(NonNull<[u8; PAGE_SIZE]>, usize)> {
-        // SAFETY: We uphold the invariants.
-        let header = unsafe { self.header_mut() };
-        let next = header.next.take()?;
-        let (next_ptr, next_header) = next.consume();
-        header.next = next_header.next;
-        Some((next_ptr, next_header.len_pages))
-    }
-}
-
-impl<'allocator, const PAGE_SIZE: usize> fmt::Debug for FreeListPtr<'allocator, PAGE_SIZE> {
-    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
-        write!(fmt, "[{:p} × {}]", self.ptr, self.len_pages())
-    }
-}
-
-#[derive(Debug)]
-struct FreeListNodeHeader<'allocator, const PAGE_SIZE: usize> {
-    /// The next node in the linked list.
-    next: Option<FreeListPtr<'allocator, PAGE_SIZE>>,
-
-    /// The length of the allocation in pages.
-    len_pages: usize,
-}
-
-/// Returns an iterator over power-of-two-sized subslices of this slice, which are returned from
-/// smallest to largest.
-pub fn power_of_two_subslices_mut<T>(slice: &mut [T]) -> impl Iterator<Item = &mut [T]> {
-    // Decompose the slice to its raw parts. Yep, we're gonna be doing unsafe stuff.
-    let mut ptr = slice.as_mut_ptr();
-    let mut len = slice.len();
-
-    iter::from_fn(move || {
-        if len == 0 {
-            None
-        } else {
-            // Make the slice to return.
-            //
-            // SAFETY: The pointer and length must be valid, since we got them from the valid
-            // slice. Before returning `out`, we advance them, so that we never give out multiple
-            // exclusive references to the same subslice.
-            let out_len = 1 << len.trailing_zeros();
-            let out = unsafe { slice::from_raw_parts_mut(ptr, out_len) };
-
-            // Advance the pointer and length.
-            //
-            // SAFETY: out_len < len, and we got len from an existing slice.
-            ptr = unsafe { ptr.add(out_len) };
-            len -= out_len;
-
-            Some(out)
-        }
-    })
-}
-
-#[test]
-fn power_of_two_subslices_mut_test() {
-    extern crate std;
-    use std::vec::Vec;
-
-    let mut data = [0, 1, 2, 3, 4, 5, 6, 7, 8];
-    let subslices = power_of_two_subslices_mut(&mut data).collect::<Vec<_>>();
-
-    assert_eq!(subslices, &[&[0] as &[_], &[1, 2, 3, 4, 5, 6, 7, 8]]);
-}