Struct Heap

pub struct Heap { /* private fields */ }

A fixed size heap backed by a linked list of free memory blocks.

Implementations

impl Heap

pub const fn empty() -> Heap

Creates an empty heap. All allocate calls will return None.

pub unsafe fn init(&mut self, heap_bottom: *mut u8, heap_size: usize)

Initializes an empty heap

The heap_bottom pointer is automatically aligned, so the bottom() method might return a pointer that is larger than heap_bottom after construction.

The given heap_size must be large enough to store the required metadata, otherwise this function will panic. Depending on the alignment of the hole_addr pointer, the minimum size is between 2 * size_of::<usize> and 3 * size_of::<usize>.

The usable size for allocations will be truncated to the nearest alignment of align_of::<usize>. Any extra bytes left at the end will be reclaimed once sufficient additional space is given to extend.

Safety

This function must be called at most once and must only be used on an empty heap.

The bottom address must be valid and the memory in the [heap_bottom, heap_bottom + heap_size) range must not be used for anything else. This function is unsafe because it can cause undefined behavior if the given address is invalid.

The provided memory range must be valid for the 'static lifetime.

pub fn init_from_slice(&mut self, mem: &'static mut [MaybeUninit<u8>])

Initialize an empty heap with provided memory.

The caller is responsible for procuring a region of raw memory that may be utilized by the allocator. This might be done via any method such as (unsafely) taking a region from the program’s memory, from a mutable static, or by allocating and leaking such memory from another allocator.

The latter approach may be especially useful if the underlying allocator does not perform deallocation (e.g. a simple bump allocator). Then the overlaid linked-list-allocator can provide memory reclamation.

The usable size for allocations will be truncated to the nearest alignment of align_of::<usize>. Any extra bytes left at the end will be reclaimed once sufficient additional space is given to extend.

Panics

This method panics if the heap is already initialized.

It also panics when the length of the given mem slice is not large enough to store the required metadata. Depending on the alignment of the slice, the minimum size is between 2 * size_of::<usize> and 3 * size_of::<usize>.

pub unsafe fn new(heap_bottom: *mut u8, heap_size: usize) -> Heap

Creates a new heap with the given bottom and size.

The heap_bottom pointer is automatically aligned, so the bottom() method might return a pointer that is larger than heap_bottom after construction.

The given heap_size must be large enough to store the required metadata, otherwise this function will panic. Depending on the alignment of the hole_addr pointer, the minimum size is between 2 * size_of::<usize> and 3 * size_of::<usize>.

The usable size for allocations will be truncated to the nearest alignment of align_of::<usize>. Any extra bytes left at the end will be reclaimed once sufficient additional space is given to extend.

Safety

The bottom address must be valid and the memory in the [heap_bottom, heap_bottom + heap_size) range must not be used for anything else. This function is unsafe because it can cause undefined behavior if the given address is invalid.

The provided memory range must be valid for the 'static lifetime.

pub fn from_slice(mem: &'static mut [MaybeUninit<u8>]) -> Heap

Creates a new heap from a slice of raw memory.

This is a convenience function that has the same effect as calling [init_from_slice] on an empty heap. All the requirements of init_from_slice apply to this function as well.

pub fn allocate_first_fit(&mut self, layout: Layout) -> Result<NonNull<u8>, ()>

Allocates a chunk of the given size with the given alignment. Returns a pointer to the beginning of that chunk if it was successful. Else it returns None. This function scans the list of free memory blocks and uses the first block that is big enough. The runtime is in O(n) where n is the number of free blocks, but it should be reasonably fast for small allocations.

pub unsafe fn deallocate(&mut self, ptr: NonNull<u8>, layout: Layout)

Frees the given allocation. ptr must be a pointer returned by a call to the allocate_first_fit function with identical size and alignment.

This function walks the list of free memory blocks and inserts the freed block at the correct place. If the freed block is adjacent to another free block, the blocks are merged again. This operation is in O(n) since the list needs to be sorted by address.

Safety

ptr must be a pointer returned by a call to the [allocate_first_fit] function with identical layout. Undefined behavior may occur for invalid arguments.

pub fn bottom(&self) -> *mut u8

Returns the bottom address of the heap.

The bottom pointer is automatically aligned, so the returned pointer might be larger than the bottom pointer used for initialization.

pub fn size(&self) -> usize

Returns the size of the heap.

This is the size the heap is using for allocations, not necessarily the total amount of bytes given to the heap. To determine the exact memory boundaries, use bottom and top.

pub fn top(&self) -> *mut u8

Return the top address of the heap.

Note: The heap may choose to not use bytes at the end for allocations until there is enough room for metadata, but it still retains ownership over memory from bottom to the address returned.

pub fn used(&self) -> usize

Returns the size of the used part of the heap

pub fn free(&self) -> usize

Returns the size of the free part of the heap

pub unsafe fn extend(&mut self, by: usize)

Extends the size of the heap by creating a new hole at the end.

Small extensions are not guaranteed to grow the usable size of the heap. In order to grow the Heap most effectively, extend by at least 2 * size_of::<usize>, keeping the amount a multiple of size_of::<usize>.

Calling this method on an uninitialized Heap will panic.

Safety

The amount of data given in by MUST exist directly after the original range of data provided when constructing the Heap. The additional data must have the same lifetime of the original range of data.

Even if this operation doesn’t increase the usable size by exactly by bytes, those bytes are still owned by the Heap for later use.

Trait Implementations

impl Send for Heap