Binary Buddy Allocator

Tags

comp-arch

Is a segregated allocator which maintains its memory as a block of size \(2^n\) (times some base unit number of bytes) that's repeatedly halved until the smallest possible block that satisfies the request is produced. Two freed blocks can be coalesced back together only if they were split from the same parent block (that is if their buddies).

For example if we have one large block of 64KiB and receive a request for 18KiB, we'd first divide into 2 to get two blocks of 64KiB. Then divide one of the 64KiB blocks to get two 32KiB blocks and then return one of those blocks as allocated since dividing it once again leaves two blocks of 16KiB, neither of which can satisfy the request for 18KiB.