diff options
Diffstat (limited to 'crates/physmem_free_list/src/lib.rs')
| -rw-r--r-- | crates/physmem_free_list/src/lib.rs | 153 |
1 files changed, 82 insertions, 71 deletions
diff --git a/crates/physmem_free_list/src/lib.rs b/crates/physmem_free_list/src/lib.rs index cb28362..f99b30f 100644 --- a/crates/physmem_free_list/src/lib.rs +++ b/crates/physmem_free_list/src/lib.rs @@ -33,8 +33,20 @@ impl<'allocator, const PAGE_SIZE: usize> FreeListAllocator<'allocator, PAGE_SIZE self.head = Some(FreeListPtr::new(ptr, len_pages, self.head.take())); } - /// Allocates memory. This is like `Allocator::allocate`, but it takes `&mut self`. - pub fn allocate(&mut self, layout: Layout) -> Result<NonNull<[u8]>, AllocError> { + /// 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(); @@ -48,33 +60,24 @@ impl<'allocator, const PAGE_SIZE: usize> FreeListAllocator<'allocator, PAGE_SIZE return Err(AllocError); }; - // If the node we're looking for is the first one, and we're not planning on splitting it, - // we have a special case. - // - // UNWRAP: The list can't have been empty or .min() above would've returned None. - 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. - let node = self.head.take().unwrap(); - let (ptr, header) = node.consume(); - self.head = header.next; - Ok(NonNull::slice_from_raw_parts( - ptr.cast(), - header.len_pages * PAGE_SIZE, - )) - } else { - // Otherwise, we want to get a node that's directly before a node that has exactly the - // right length. - let node_before_node_to_remove = if selected_node_len == len_pages { - // If the node we're looking for has the same length as the allocation, we just - // need to iterate through the list to find it. The special case where it's the - // first element was already handled above. + 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 { @@ -87,50 +90,43 @@ impl<'allocator, const PAGE_SIZE: usize> FreeListAllocator<'allocator, PAGE_SIZE next = ptr.next_mut(); } - // UNWRAP: We had to find the node in the first place. - node_before_node_to_remove.unwrap() - } else { - // In the normal case, we'll split the node. First, we iterate to the node we - // selected. - let mut next = self.head.as_mut(); - let mut node_to_split = None; - while let Some(ptr) = next { - if ptr.len_pages() == selected_node_len { - node_to_split = Some(ptr); - break; - } - next = ptr.next_mut(); - } - - // UNWRAP: We had to find the node in the first place. - let node_to_split = node_to_split.unwrap(); - - // Split the node. The part we're going to remove gets inserted after `node_to_split`, - // so we can just return the node after this. - node_to_split.split(len_pages); - node_to_split + // 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() }; - // Unlink the next node. - // - // UNWRAP: The next node must exist because of the above. - let (ptr, unlinked_len_pages) = node_before_node_to_remove.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(); + } - /// Allocates zeroed-out memory. - pub fn allocate_zeroed(&mut self, layout: Layout) -> Result<NonNull<[u8]>, AllocError> { - let ptr = self.allocate(layout)?; - // SAFETY: The pointer has to have a valid size. - unsafe { - ptr.cast::<u8>().write_bytes(0, ptr.len()); + // 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, + )) } - Ok(ptr) } /// Returns an iterator over the page ranges in the free list, as pairs of `ptr` and @@ -147,13 +143,28 @@ impl<'allocator, const PAGE_SIZE: usize> FreeListAllocator<'allocator, PAGE_SIZE }) } - /// Splits all the nodes until each page range is of a power-of-two size. - pub fn split_to_powers_of_two(&mut self) { + /// 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 { - // Compute the size the page range would have if it were - // let log2_smaller_size = ptr.len_pages().trailing_zeros(); - // let smaller_size = 1 << log2_smaller_size; + 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(); } @@ -265,7 +276,7 @@ impl<'allocator, const PAGE_SIZE: usize> FreeListPtr<'allocator, PAGE_SIZE> { header.next.as_mut() } - /// Returns the underlying pointer, which should not be accessed. + /// Returns the underlying pointer. Using this may violate invariants. pub fn ptr(&self) -> NonNull<[u8; PAGE_SIZE]> { self.ptr.cast() } @@ -310,7 +321,7 @@ impl<'allocator, const PAGE_SIZE: usize> FreeListPtr<'allocator, PAGE_SIZE> { } } - /// Unlinks and returns the _next_ node, returning its pointer and length. + /// 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() }; |