Buddy allocator

restricts allocations to powers of 2 to enable more efficient implementation, since allocation requests are usually of size $2^n$. could be used by kernel

split blocks into 2 until you can handle the request, for fast searching and merging avoids worst case of searching every single block in free list

can be implemented with multiple Linked list restrict requests to be $2^k$, $k\in [0,n]$ round up if needed our implementation uses $n+1$ free lists of blocks for each size for a request of size $2^k$, search free list until we find a big enough block search $k,k+1,k+2,\dots$ until we find one if way too big, recursively divide until correct size

insert “buddy” blocks into free lists for deallocations, “coalesce” buddy blocks back together, since contiguous based on how we split can also do this recursively

for example, allocate 28 from 256, we split into two 128s, which are buddies of each other keep splitting until we get the right size. mark as used try to allocate to buddies of each other if no buddies free, then we go up one level, split another buddy we might lose some bytes bc of internal fragmentation

if red, green allocated, we don’t have any more 32 blocks free. we go up one level to other 64, then split into 2 32 buddies if a bigger request comes in, not contiguous, can’t allocate

tldr fast simple avoids external fragmentation by keeping free pages contiguously cons: almost always has internal fragmentation always round up allocation size if not power of 2