Struct Buddy

Source
pub struct Buddy<const BLK_SIZE: usize, const LEVELS: usize, A: BackingAllocator> { /* private fields */ }
Expand description

A binary-buddy allocator.

For a discussion of the buddy algorithm, see the module-level documentation.

§Configuration

This type has two const parameters:

  • BLK_SIZE is the size of the largest allocations the allocator can make.
  • LEVELS is the number of levels in the allocator.

Each constructor also takes one runtime parameter:

  • num_blocks is the number of top-level blocks of BLK_SIZE bytes managed by the allocator.

These parameters are subject to the following invariants:

  • BLK_SIZE must be a power of two.
  • LEVELS must be nonzero and less than usize::BITS.
  • The minumum block size must be at least 2 * mem::size_of<usize>(); it can be calculated with the formula BLK_SIZE >> (LEVELS - 1).
  • The total size in bytes of the managed region must be less than usize::MAX.

Attempting to construct a Buddy whose const parameters violate these invariants will result in an error.

§Unpopulated initialization

A Buddy can be initialized for a region of memory without immediately allowing it to access any of that memory using the Buddy::new_raw_unpopulated constructor. Memory in that region can then be added to the allocator over time.

This is particularly useful when using a Buddy to allocate discontiguous regions of physical memory. For example, consider a 16 KiB region of physical memory in which the region between 4-8 KiB is reserved by the platform for memory-mapped I/O.

      | RAM              | MMIO             | RAM               | RAM             |
  0x##0000           0x##1000           0x##2000            0x##3000          0x##4000

Initializing an allocator normally for the entire region would result in writes to the MMIO region, with unpredictable consequences.

// These values result in a minimum block size of 4096.
type Buddy = acid_alloc::Buddy<16384, 3, acid_alloc::Raw>;

let region = /* ... */;
let metadata = /* ... */;

// ⚠ Bad Things occur!
let buddy = unsafe { Buddy::new_raw(region, metadata, 1).unwrap() };

However, creating the allocator using new_raw_unpopulated() does not issue any writes. Instead, valid subregions can be added to the allocator explicitly.

// Define the usable regions of memory.
let low_start = NonZeroUsize::new(region.as_ptr() as usize).unwrap();
let low_end = NonZeroUsize::new(low_start.get() + 4096).unwrap();
let high_start = NonZeroUsize::new(low_start.get() + 8192).unwrap();
let high_end = NonZeroUsize::new(low_start.get() + 16384).unwrap();

unsafe {
    // No accesses to `region` are made during this call.
    let mut buddy = Buddy::new_raw_unpopulated(region, metadata, 1).unwrap();

    // The allocator has no memory yet, so it can't make allocations.
    assert!(buddy.allocate(Layout::new::<[u8; 4096]>()).is_err());

    // Add the valid regions to the allocator.
    buddy.add_region(low_start..low_end);
    buddy.add_region(high_start..high_end);

    // Now allocations succeed.
    let block = buddy.allocate(Layout::new::<[u8; 4096]>()).unwrap();
}

§Example

use core::{alloc::Layout, mem::MaybeUninit, ptr::NonNull};

use acid_alloc::{Buddy, Global};

// Minimum block size == BLK_SIZE >> (LEVELS - 1)
//                 16 ==     4096 >> (     9 - 1)
type CustomBuddy = Buddy<4096, 9, Global>;

// Create a new `Buddy` with four 4KiB blocks, backed by the global allocator.
let mut buddy = CustomBuddy::try_new(4).expect("buddy initialization failed.");

// Allocate space for an array of `u64`s.
let len = 8;
let layout = Layout::array::<u64>(len).expect("layout overflowed");
let mut buf: NonNull<[u8]> = buddy.allocate(layout).expect("allocation failed");
let mut uninit: NonNull<[MaybeUninit<u64>; 8]> = buf.cast();

// Initialize the array.
unsafe {
    let mut arr: &mut [MaybeUninit<u64>; 8] = uninit.as_mut();
    for (i, elem) in arr.iter_mut().enumerate() {
        elem.as_mut_ptr().write(i as u64);
    }
}

// Deallocate the array.
unsafe { buddy.deallocate(buf.cast()) };

Implementations§

Source§

impl<const BLK_SIZE: usize, const LEVELS: usize> Buddy<BLK_SIZE, LEVELS, Raw>

Source

pub unsafe fn new_raw( metadata: NonNull<u8>, region: NonNull<u8>, num_blocks: usize, ) -> Result<Buddy<BLK_SIZE, LEVELS, Raw>, AllocInitError>

Constructs a new Buddy from raw pointers.

§Safety

The caller must uphold the following invariants:

  • region must be a pointer to a region that satisfies the Layout returned by Self::region_layout(num_blocks), and it must be valid for reads and writes for the entire size indicated by that Layout.
  • metadata must be a pointer to a region that satisfies the Layout returned by Self::metadata_layout(num_blocks), and it must be valid for reads and writes for the entire size indicated by that Layout.
  • The regions pointed to by region and metadata must not overlap.
  • No references to the memory at region or metadata may exist when this function is called.
  • As long as the returned Buddy exists:
    • No accesses may be made to the memory at region except by way of methods on the returned Buddy.
    • No accesses may be made to the memory at metadata.
§Errors

This constructor returns an error if the allocator configuration is invalid.

Source

pub unsafe fn new_raw_unpopulated( metadata: NonNull<u8>, region: NonNull<u8>, num_blocks: usize, ) -> Result<Buddy<BLK_SIZE, LEVELS, Raw>, AllocInitError>

Constructs a new Buddy from raw pointers without populating it.

The returned Buddy will be unable to allocate until address ranges are made available to it using Buddy::add_region. See unpopulated initialization for details.

§Safety

The caller must uphold the following invariants:

  • region must be a pointer to a region that satisfies the Layout returned by Self::region_layout(num_blocks).
  • metadata must be a pointer to a region that satisfies the Layout returned by Self::metadata_layout(num_blocks), and it must be valid for reads and writes for the entire size indicated by that Layout.
  • The regions pointed to by region and metadata must not overlap.
  • No references to the memory at metadata may exist when this function is called.
  • As long as the returned Buddy exists, no accesses may be made to the memory at metadata.
Source

pub unsafe fn add_region(&mut self, addr_range: Range<NonZeroUsize>)

Populates a region not already managed by this allocator.

§Panics

This method panics if any of the following are true:

  • Either bound of addr_range falls outside the allocator region.
  • Either bound of addr_range is not aligned to the value returned by Self::min_block_size().
§Safety

The caller must uphold the following invariants:

  • range must not overlap any range of addresses already managed by this allocator.
  • No references to the memory indicated by addr_range may exist when this function is called.
  • As long as self exists, no accesses may be made to the memory indicated by addr_range except by way of methods on self.
Source

pub unsafe fn into_raw_parts(self) -> RawBuddyParts

Decomposes the allocator into its raw parts.

§Safety

This function must only be called if no references to outstanding allocations exist .

Source§

impl<const BLK_SIZE: usize, const LEVELS: usize> Buddy<BLK_SIZE, LEVELS, Global>

Source

pub fn try_new( num_blocks: usize, ) -> Result<Buddy<BLK_SIZE, LEVELS, Global>, AllocInitError>

Available on crate feature alloc only.

Attempts to construct a new Buddy backed by the global allocator.

§Errors

If allocation fails, or if the allocator configuration is invalid, returns Err.

Source§

impl<const BLK_SIZE: usize, const LEVELS: usize, A: Allocator> Buddy<BLK_SIZE, LEVELS, A>

Source

pub fn try_new_in( num_blocks: usize, allocator: A, ) -> Result<Buddy<BLK_SIZE, LEVELS, A>, AllocInitError>

Available on crate feature unstable only.

Attempts to construct a new Buddy backed by allocator.

§Errors

If allocation fails, returns Err(AllocError).

Source§

impl<const BLK_SIZE: usize, const LEVELS: usize, A: BackingAllocator> Buddy<BLK_SIZE, LEVELS, A>

Source

pub const fn min_block_size() -> Result<usize, AllocInitError>

Returns the smallest block size that can be allocated by an allocator of this type.

Source

pub fn region_layout(num_blocks: usize) -> Result<Layout, AllocInitError>

Returns the layout requirements of the region managed by an allocator of this type.

Source

pub fn metadata_layout(num_blocks: usize) -> Result<Layout, AllocInitError>

Returns the layout requirements of the metadata region for an allocator of this type.

Source

pub fn allocate(&mut self, layout: Layout) -> Result<NonNull<[u8]>, AllocError>

Attempts to allocate a block of memory.

On success, returns a NonNull<[u8]> which satisfies layout.

The contents of the block are uninitialized.

§Errors

Returns Err if a suitable block could not be allocated.

Source

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

Deallocates the memory referenced by ptr.

§Safety

ptr must denote a block of memory currently allocated via this allocator.

Trait Implementations§

Source§

impl<const BLK_SIZE: usize, const LEVELS: usize, A: BackingAllocator> Debug for Buddy<BLK_SIZE, LEVELS, A>

Source§

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

Formats the value using the given formatter. Read more
Source§

impl<const BLK_SIZE: usize, const LEVELS: usize, A: BackingAllocator> Drop for Buddy<BLK_SIZE, LEVELS, A>

Source§

fn drop(&mut self)

Executes the destructor for this type. Read more
Source§

impl<const BLK_SIZE: usize, const LEVELS: usize, A: BackingAllocator + Send> Send for Buddy<BLK_SIZE, LEVELS, A>

Source§

impl<const BLK_SIZE: usize, const LEVELS: usize, A: BackingAllocator + Sync> Sync for Buddy<BLK_SIZE, LEVELS, A>

Auto Trait Implementations§

§

impl<const BLK_SIZE: usize, const LEVELS: usize, A> Freeze for Buddy<BLK_SIZE, LEVELS, A>
where A: Freeze,

§

impl<const BLK_SIZE: usize, const LEVELS: usize, A> RefUnwindSafe for Buddy<BLK_SIZE, LEVELS, A>
where A: RefUnwindSafe,

§

impl<const BLK_SIZE: usize, const LEVELS: usize, A> Unpin for Buddy<BLK_SIZE, LEVELS, A>
where A: Unpin,

§

impl<const BLK_SIZE: usize, const LEVELS: usize, A> UnwindSafe for Buddy<BLK_SIZE, LEVELS, A>
where A: UnwindSafe,

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.