Struct FreeList

pub struct FreeList<const N: usize> { /* private fields */ }

A free-list-based page/frame allocator.

This type can be used for managing (allocating and deallocating) physical and virtual memory at PAGE_SIZE granularity. This is useful for ensuring pages and frames being currently unused before mapping them.

The const N: usize generic specifies how many internal PageRanges the free list can hold before needing to allocate more memory from the global allocator.

Before allocating, the free list has to be provided a page range to allocate from via FreeList::deallocate.

Examples

use free_list::{FreeList, PageLayout};

let mut free_list = FreeList::<16>::new();

unsafe {
    free_list.deallocate((0x1000..0x5000).try_into().unwrap()).unwrap();
}
assert_eq!(free_list.free_space(), 0x4000);

let layout = PageLayout::from_size(0x4000).unwrap();
assert_eq!(free_list.allocate(layout).unwrap(), (0x1000..0x5000).try_into().unwrap());

Implementations

impl<const N: usize> FreeList<N>

pub const fn new() -> Self

Creates a new free list without any free space.

Examples

use free_list::FreeList;

let free_list = FreeList::<16>::new();

pub unsafe fn deallocate(&mut self, range: PageRange) -> Result<(), AllocError>

Attempts to deallocates a page range.

This should also be used to add more free pages to the allocator, such as after initialization. This returns an error, if range overlaps with any pages that are already deallocated.

Examples

use free_list::FreeList;

let mut free_list = FreeList::<16>::new();

unsafe {
    free_list.deallocate((0x1000..0x2000).try_into().unwrap()).unwrap();
}

Safety

range must be valid to be allocated and used (again).

pub fn allocate(&mut self, layout: PageLayout) -> Result<PageRange, AllocError>

Attempts to allocate a page range.

On success, returns a PageRange meeting the size and alignment guarantees of layout.

This call can only succeed if the free list has previously been provided a free page range to allocate from via FreeList::deallocate.

Examples

use free_list::{FreeList, PageLayout};

let mut free_list = FreeList::<16>::new();

unsafe {
    free_list.deallocate((0x1000..0x5000).try_into().unwrap()).unwrap();
}

let layout = PageLayout::from_size(0x4000).unwrap();
assert_eq!(free_list.allocate(layout).unwrap(), (0x1000..0x5000).try_into().unwrap());

pub fn allocate_at(&mut self, range: PageRange) -> Result<(), AllocError>

Attempts to allocate a specific page range.

Examples

use free_list::FreeList;

let mut free_list = FreeList::<16>::new();

unsafe {
    free_list.deallocate((0x1000..0x2000).try_into().unwrap()).unwrap();
    free_list.deallocate((0x3000..0x4000).try_into().unwrap()).unwrap();
}

free_list.allocate_at((0x3000..0x4000).try_into().unwrap()).unwrap();

pub fn allocate_outside_of( &mut self, layout: PageLayout, range: PageRange, ) -> Result<PageRange, AllocError>

Attempts to allocate a page range outside of a given page range.

On success, returns a PageRange meeting the size and alignment guarantees of layout outside of range.

Examples

use free_list::{FreeList, PageLayout, PageRange};

let mut free_list = FreeList::<16>::new();

unsafe {
    free_list.deallocate((0x1000..0x5000).try_into().unwrap()).unwrap();
}

let layout = PageLayout::from_size(0x1000).unwrap();
let range = PageRange::new(0x0000, 0x2000).unwrap();
let allocated = free_list.allocate_outside_of(layout, range);
assert_eq!(allocated.unwrap(), (0x2000..0x3000).try_into().unwrap());

pub fn allocate_with<F>(&mut self, f: F) -> Result<PageRange, AllocError>

where F: FnMut(PageRange) -> Option<PageRange>,

Attempts to allocate a page range according to a function.

On success, allocates and returns the first non-none PageRange returned by f.

Examples

use free_list::{FreeList, PageLayout};

let mut free_list = FreeList::<16>::new();

unsafe {
    free_list.deallocate((0x1000..0x2000).try_into().unwrap()).unwrap();
    free_list.deallocate((0x3000..0x4000).try_into().unwrap()).unwrap();
}

let layout = PageLayout::from_size(0x1000).unwrap();
let allocated = free_list.allocate_with(|range| {
    (range.start() > 0x2000)
        .then_some(range)
        .and_then(|range| range.fit(layout))
});
assert_eq!(allocated.unwrap(), (0x3000..0x4000).try_into().unwrap());

pub fn free_space(&self) -> usize

Returns how much free space this allocator has in bytes.

Examples

use free_list::FreeList;

let mut free_list = FreeList::<16>::new();

unsafe {
    free_list.deallocate((0x1000..0x5000).try_into().unwrap()).unwrap();
}
assert_eq!(free_list.free_space(), 0x4000);

Trait Implementations

impl<const N: usize> Debug for FreeList<N>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<const N: usize> Default for FreeList<N>

fn default() -> Self

Returns the “default value” for a type.

impl<const N: usize> Display for FreeList<N>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<S: PageSize, const N: usize> FrameAllocator<S> for FreeList<N>

fn allocate_frame(&mut self) -> Option<PhysFrame<S>>

Allocate a frame of the appropriate size and return it if possible.

impl<S: PageSize, const N: usize> FrameDeallocator<S> for FreeList<N>

unsafe fn deallocate_frame(&mut self, frame: PhysFrame<S>)

Deallocate the given unused frame.