Struct vulkano::memory::allocator::suballocator::BuddyAllocator

pub struct BuddyAllocator { /* private fields */ }

A suballocator whose structure forms a binary tree of power-of-two-sized suballocations.

That is, all allocation sizes are rounded up to the next power of two. This helps reduce external fragmentation by a lot, at the expense of possibly severe internal fragmentation if you’re not careful. For example, if you needed an allocation size of 64MiB, you would be wasting no memory. But with an allocation size of 70MiB, you would use a whole 128MiB instead, wasting 45% of the memory. Use this algorithm if you need to create and free a lot of allocations, which would cause too much external fragmentation when using FreeListAllocator. However, if the sizes of your allocations are more or less the same, then using an allocation pool would be a better choice and would eliminate external fragmentation completely.

See also the Suballocator implementation.

Algorithm

Say you have a region of size 256MiB, and you want to allocate 14MiB. Assuming there are no existing allocations, the BuddyAllocator would split the 256MiB root node into two 128MiB nodes. These two nodes are called buddies. The allocator would then proceed to split the left node recursively until it wouldn’t be able to fit the allocation anymore. In this example, that would happen after 4 splits and end up with a node size of 16MiB. Since the allocation requested was 14MiB, 2MiB would become internal fragmentation and be unusable for the lifetime of the allocation. When an allocation is freed, this process is done backwards, checking if the buddy of each node on the way up is free and if so they are coalesced.

Each possible node size has an order, with the smallest node size being of order 0 and the largest of the highest order. With this notion, node sizes are proportional to 2ⁿ where n is the order. The highest order is determined from the size of the region and a constant minimum node size, which we chose to be 16B: log(region size / 16) or equiavalently log(region size) - 4 (assuming region size ≥ 16).

It’s safe to say that this algorithm works best if you have some level of control over your allocation sizes, so that you don’t end up allocating twice as much memory. An example of this would be when you need to allocate regions for other allocators, such as for an allocation pool or the BumpAllocator.

Efficiency

The time complexity of both allocation and freeing is O(m) in the worst case where m is the highest order, which equates to O(log (n)) where n is the size of the region.

Trait Implementations

impl Debug for BuddyAllocator

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

Formats the value using the given formatter.

impl Suballocator for BuddyAllocator

fn new(region: Region) -> Self

Creates a new BuddyAllocator for the given region.

Panics

• Panics if region.size is not a power of two.
• Panics if region.size is not in the range [16B, 32GiB].

fn free_size(&self) -> DeviceSize

Returns the total amount of free space left in the region that is available to the allocator, which means that internal fragmentation is excluded.

fn allocate( &self, layout: DeviceLayout, allocation_type: AllocationType, buffer_image_granularity: DeviceAlignment ) -> Result<Suballocation, SuballocatorError>

Creates a new suballocation within the region.

unsafe fn deallocate(&self, suballocation: Suballocation)

Deallocates the given suballocation.

fn cleanup(&mut self)

Tries to free some space, if applicable.