BuddySystemAllocator

BuddySystemAllocator is a memory allocator that uses the buddy memory allocation algorithm to manage a contiguous pool of memory. Blocks are sized in powers of two, and each block has a unique buddy of the same size. When both buddies are free they can be coalesced into a larger block, and this process repeats up the size hierarchy to form larger free blocks as needed.

Allocation proceeds by rounding the requested size up to the next power of two and selecting the smallest free block of that order from the free lists. If no block of the required size is available, a larger block is split into two buddies of the next smaller order, with one used and the other returned to the appropriate free list. The pointer returned is aligned to the block boundary and is associated with metadata to support deallocation.

Deallocation checks the block’s buddy; if the buddy is free, the two are merged to form a block of the next higher order, and the process repeats until no merge is possible or the block reaches the maximum size. The allocator typically maintains a separate free list for each order and uses simple address arithmetic to locate buddies.

Advantages include predictable, logarithmic-time allocations and deallocations and bounded external fragmentation. Limitations include internal fragmentation due to rounding, potential contention in multithreaded environments, and the overhead of splitting and merging blocks. Real-time and kernel contexts often prefer buddy allocators for their determinism and simplicity, while general-purpose allocators may favor other strategies.

In practice, BuddySystemAllocator appears in operating system kernels, embedded systems, and custom memory pools where memory is preallocated as a large block and allocation requests are small and frequent. Related concepts include memory pools, power-of-two allocators, and slab allocators.