Buddy Allocator

An allocator that supports power-of-two allocations and deallocations with automatic coalescing. Buddy allocators excel in scenarios requiring fast, deterministic allocation with low fragmentation overhead.

Source Code

Design

The BuddyAllocator manages memory within a contiguous buffer by maintaining a set of free lists, one per level, where each level corresponds to a power-of-two block size. The minimum block size is dependent on sizeof(Block), which stores the doubly linked list pointers used to maintain the free lists.

On allocation, the requested size is rounded up to the nearest power of two. If no block exists at the required level, a larger block is split into two buddies, with one inserted into the free list and the other used to satisfy the request. On deallocation, the block is returned to its free list and recursively coalesced with its buddy, reducing fragmentation.

Block levels are tracked in a flat levels array indexed by minimum-block offset, and a bitmap tracks which blocks are currently allocated, allowing O(1) buddy lookup and validity checking while coalescing.

The allocator allows for a BufferType template parameter, in which the caller can specify the type of memory (heap, stack, or external). BufferType::STACK uses a fixed-size array stored inline within the allocator object. BufferType::EXTERNAL signals a contract in which the allocator will allocate but not own or manage the memory's lifetime. The size of this external buffer must be known at compile time. When BufferType is not specified, the allocator defaults to BufferType::HEAP, dynamically allocating memory and managing the cleanup in its destructor. Hence, the copy, copy assignment, move, and move assignment operations are deleted per the rule of 5.

The allocator accepts a Tracking template parameter to either enable or disable internal tracking of allocator state. Tracking::ENABLED records allocation metadata as allocation and deallocations occur. The user can then call get_state() to obtain a JSON-formatted std::string that details the allocator's current live allocations and free space. Tracking::ENABLED is critical for enabling visualizer functionality. Tracking::DISABLED removes this bookkeeping entirely, and thus does not accrue any overhead beyond core allocator logic. Calling get_state() on a Tracking::DISABLED allocator is a compile error. When Tracking is not specified, the allocator defaults to Tracking::DISABLED.

Limitations

All allocations are rounded up to the nearest power-of-two, which may cause internal fragmentation for non power-of-two allocation sizes. The minimum allocation size is sizeof(Block), as the block metadata is stored within the free memory itself. The total capacity S must be a power-of-two greater than zero.

API Reference

Constructor

template <size_t S, BufferType B, Tracking Tr>
BuddyAllocator()

Creates a buddy allocator with capacity S bytes. Behavior depends on BufferType:

  • BufferType::HEAP : allocates S bytes on the heap
  • BufferType::STACK : uses a stack-allocated buffer of S bytes
  • BufferType::EXTERNAL : requires explicit buffer via BuddyAllocator(std::array<std::byte, S>&)

Memory Management

[[nodiscard]] std::byte* allocate(size_t size, size_t alignment) noexcept

Allocates a block of at least size bytes, rounded up to the nearest power-of-two. Searches the free lists and splits larger blocks as needed. Returns a pointer to allocated memory, or nullptr on failure (insufficient space). 

void deallocate(std::byte* ptr) noexcept

Reclaims the allocation at ptr without calling a destructor. Automatically coalesces with the buddy block if available, recursively merging upward as much as possible. The ptr must have been returned by allocate(). Passing nullptr returns immediately, with no operation. 

void reset() noexcept

Resets the allocator, reclaiming all allocated memory for reuse. Invalidates all previously allocated pointers without calling destructors. For non-trivial types, consider calling destroy<T>() before resetting.

Metrics

size_t get_used() const noexcept

Returns the number of bytes currently allocated.

size_t get_free() const noexcept

Returns the number of bytes not yet allocated.

Typed Helpers

template <typename T>
[[nodiscard]] T* allocate_as(size_t count = 1) noexcept

Typed allocation for count objects of type T. Aligns to count * sizeof(T), rounded up to the nearest power of two. Returns a typed pointer or nullptr on failure. 

template <typename T> 
            void deallocate(T* ptr) noexcept

Typed deallocation. Reclaims the ptr without calling a destructor. For non-trivial types, consider calling destroy<T>() before deallocation. 

template <typename T, typename... Args>
[[nodiscard]] T* emplace(Args&&... args)

Allocates space for type T and constructs an object in-place using constructor arguments args and std::construct_at(). Returns a pointer to the constructed object, or nullptr if allocation fails. 

template <typename T>
void destroy(T* ptr) noexcept

Calls destructor on object at ptr via std::destroy_at(). Only destroys the object and does not deallocate memory. Memory can only be reclaimed via deallocate<T>() reset().

Usage

#include "buddy_allocator.h"

// Heap-based allocator (1KB)
allocator::BuddyAllocator<1024, allocator::BufferType::HEAP> heap_alloc{};
            
// Allocate and construct objects
int* x {heap_alloc.emplace<int>(42)};
std::string* s {heap_alloc.emplace<std::string>("hello")};
            
heap_alloc.destroy(s);
heap_alloc.deallocate(s);
            
heap_alloc.destroy(x);
heap_alloc.deallocate(x);
            
// Stack-based allocator
allocator::BuddyAllocator<512, allocator::BufferType::STACK> stack_alloc{};
            
// Raw byte allocation
std::byte* buffer {stack_alloc.allocate(128)};  // rounded up to 128 bytes
stack_alloc.deallocate(buffer);
            
// External buffer
std::array<std::byte, 2048> my_buffer{};
allocator::BuddyAllocator<2048, allocator::BufferType::EXTERNAL> ext_alloc{my_buffer};
            
// Metrics
size_t in_use {heap_alloc.get_used()};
size_t available {heap_alloc.get_free()};