Struct acid_alloc::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 ofBLK_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 thanusize::BITS
.- The minumum block size must be at least
2 * mem::size_of<usize>()
; it can be calculated with the formulaBLK_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
sourceimpl<const BLK_SIZE: usize, const LEVELS: usize> Buddy<BLK_SIZE, LEVELS, Raw>
impl<const BLK_SIZE: usize, const LEVELS: usize> Buddy<BLK_SIZE, LEVELS, Raw>
sourcepub unsafe fn new_raw(
metadata: NonNull<u8>,
region: NonNull<u8>,
num_blocks: usize
) -> Result<Buddy<BLK_SIZE, LEVELS, Raw>, AllocInitError>
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 theLayout
returned bySelf::region_layout(num_blocks)
, and it must be valid for reads and writes for the entire size indicated by thatLayout
.metadata
must be a pointer to a region that satisfies theLayout
returned bySelf::metadata_layout(num_blocks)
, and it must be valid for reads and writes for the entire size indicated by thatLayout
.- The regions pointed to by
region
andmetadata
must not overlap. - No references to the memory at
region
ormetadata
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 returnedBuddy
. - No accesses may be made to the memory at
metadata
.
- No accesses may be made to the memory at
Errors
This constructor returns an error if the allocator configuration is invalid.
sourcepub unsafe fn new_raw_unpopulated(
metadata: NonNull<u8>,
region: NonNull<u8>,
num_blocks: usize
) -> Result<Buddy<BLK_SIZE, LEVELS, Raw>, AllocInitError>
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 theLayout
returned bySelf::region_layout(num_blocks)
.metadata
must be a pointer to a region that satisfies theLayout
returned bySelf::metadata_layout(num_blocks)
, and it must be valid for reads and writes for the entire size indicated by thatLayout
.- The regions pointed to by
region
andmetadata
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 atmetadata
.
sourcepub unsafe fn add_region(&mut self, addr_range: Range<NonZeroUsize>)
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 bySelf::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 byaddr_range
except by way of methods onself
.
sourcepub unsafe fn into_raw_parts(self) -> RawBuddyParts
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 .
sourceimpl<const BLK_SIZE: usize, const LEVELS: usize, A: Allocator> Buddy<BLK_SIZE, LEVELS, A>
impl<const BLK_SIZE: usize, const LEVELS: usize, A: Allocator> Buddy<BLK_SIZE, LEVELS, A>
sourcepub fn try_new_in(
num_blocks: usize,
allocator: A
) -> Result<Buddy<BLK_SIZE, LEVELS, A>, AllocInitError>
Available on crate feature unstable
only.
pub fn try_new_in(
num_blocks: usize,
allocator: A
) -> Result<Buddy<BLK_SIZE, LEVELS, A>, AllocInitError>
unstable
only.Attempts to construct a new Buddy
backed by allocator
.
Errors
If allocation fails, returns Err(AllocError)
.
sourceimpl<const BLK_SIZE: usize, const LEVELS: usize, A: BackingAllocator> Buddy<BLK_SIZE, LEVELS, A>
impl<const BLK_SIZE: usize, const LEVELS: usize, A: BackingAllocator> Buddy<BLK_SIZE, LEVELS, A>
sourcepub const fn min_block_size() -> Result<usize, AllocInitError>
pub const fn min_block_size() -> Result<usize, AllocInitError>
Returns the smallest block size that can be allocated by an allocator of this type.
sourcepub fn region_layout(num_blocks: usize) -> Result<Layout, AllocInitError>
pub fn region_layout(num_blocks: usize) -> Result<Layout, AllocInitError>
Returns the layout requirements of the region managed by an allocator of this type.
sourcepub fn metadata_layout(num_blocks: usize) -> Result<Layout, AllocInitError>
pub fn metadata_layout(num_blocks: usize) -> Result<Layout, AllocInitError>
Returns the layout requirements of the metadata region for an allocator of this type.
sourcepub fn allocate(&mut self, layout: Layout) -> Result<NonNull<[u8]>, AllocError>
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.
sourcepub unsafe fn deallocate(&mut self, ptr: NonNull<u8>)
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
sourceimpl<const BLK_SIZE: usize, const LEVELS: usize, A: BackingAllocator> Debug for Buddy<BLK_SIZE, LEVELS, A>
impl<const BLK_SIZE: usize, const LEVELS: usize, A: BackingAllocator> Debug for Buddy<BLK_SIZE, LEVELS, A>
sourceimpl<const BLK_SIZE: usize, const LEVELS: usize, A: BackingAllocator> Drop for Buddy<BLK_SIZE, LEVELS, A>
impl<const BLK_SIZE: usize, const LEVELS: usize, A: BackingAllocator> Drop for Buddy<BLK_SIZE, LEVELS, A>
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>
Auto Trait Implementations
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
sourceimpl<T> BorrowMut<T> for T where
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
const: unstable · sourcefn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more