Struct Buddy

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

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

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

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.

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.

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.

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 .

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

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.

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

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).

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

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

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

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

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

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

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

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.

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

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

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

Formats the value using the given formatter.

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

fn drop(&mut self)

Executes the destructor for this type.

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

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