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 the PoolAllocator 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 the PoolAllocator or the BumpAllocator.

Efficiency

The allocator is synchronized internally with a lock, which is held only for a very short period each time an allocation is created and freed. 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.

Examples

Basic usage together with GenericMemoryAllocator, to allocate resources that have a moderately low life span (for example if you have a lot of images, each of which needs to be resized every now and then):

use std::sync::Arc;
use vulkano::memory::allocator::{
    BuddyAllocator, GenericMemoryAllocator, GenericMemoryAllocatorCreateInfo,
};

let memory_allocator = GenericMemoryAllocator::<Arc<BuddyAllocator>>::new(
    device.clone(),
    GenericMemoryAllocatorCreateInfo {
        // Your block sizes must be powers of two, because `BuddyAllocator` only accepts
        // power-of-two-sized regions.
        block_sizes: &[(0, 64 * 1024 * 1024)],
        ..Default::default()
    },
)
.unwrap();

// Now you can use `memory_allocator` to allocate whatever it is you need.

Implementations

impl BuddyAllocator

pub fn new(region: MemoryAlloc) -> Arc<Self>

Creates a new BuddyAllocator for the given region.

Panics

• Panics if region.allocation_type is not AllocationType::Unknown. This is done to avoid checking for a special case of buffer-image granularity conflict.
• Panics if region.size is not a power of two.
• Panics if region.size is not in the range [16B, 64GiB].
• Panics if region is a dedicated allocation.

Trait Implementations

impl Debug for BuddyAllocator

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

Formats the value using the given formatter.

impl DeviceOwned for BuddyAllocator

fn device(&self) -> &Arc<Device>

Returns the device that owns Self.