Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Buddy blocks: split powers of two and reunite partners

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A buddy pool covers a power-of-two capacity with one free root block. A request rounds up to the smallest power-of-two block that can hold it. When no block of that order is free, the allocator takes a larger block and repeatedly splits it into equal halves, returning one half to the free set at each level. The partner of a block beginning at an aligned address is found by toggling the bit for that block size. Release can merge two halves only when both are free and are true partners at the same order; two merely adjacent blocks of unequal size cannot be combined by that rule. The allocated map records both block order and requested size. This model stores sets of integer offsets and does not reserve or copy the actual payload bytes.

Operational case

A 128-unit pool serves a 13-unit pump request with a 16-unit block and a 19-unit valve request with a 32-unit block. The gap between requested and assigned capacity is internal fragmentation, not a leak. When the pump and valve blocks are released, each climbs the hierarchy only while its matching free buddy is present. Eventually the free root at offset zero covers all 128 units again. Releasing an unknown offset fails because no live allocation owns it. The example deliberately chooses the lowest free start at a found order for repeatable output; another tie rule could place the same requests differently without changing the buddy invariant.

Working Python program

python
class BuddyBlockPool:
    def __init__(self, capacity):
        if capacity < 1 or capacity & (capacity - 1):
            raise ValueError("capacity must be a power of two")
        self.capacity = capacity
        self.max_order = capacity.bit_length() - 1
        self.free_by_order = [set() for _ in range(self.max_order + 1)]
        self.free_by_order[self.max_order].add(0)
        self.allocated = {}

    def allocate(self, requested):
        if requested < 1:
            raise ValueError("requested size must be positive")
        order = (requested - 1).bit_length()
        found = next((level for level in range(order, self.max_order + 1)
                      if self.free_by_order[level]), None)
        if found is None:
            raise MemoryError("no suitable buddy block")
        start = min(self.free_by_order[found])
        self.free_by_order[found].remove(start)
        while found > order:
            found -= 1
            self.free_by_order[found].add(start + (1 << found))
        self.allocated[start] = (order, requested)
        return start

    def release(self, start):
        order, _ = self.allocated.pop(start)
        while order < self.max_order:
            buddy = start ^ (1 << order)
            if buddy not in self.free_by_order[order]:
                break
            self.free_by_order[order].remove(buddy)
            start = min(start, buddy)
            order += 1
        self.free_by_order[order].add(start)

    def free_units(self):
        return sum(len(blocks) * (1 << order)
                   for order, blocks in enumerate(self.free_by_order))


pool = BuddyBlockPool(128)
pump = pool.allocate(13)
valve = pool.allocate(19)
pool.release(pump)
pool.release(valve)
print("free=", pool.free_units(), " root=", sorted(pool.free_by_order[7]), sep="")

Output

Output
free=128 root=[0]

Time, space, and tradeoff

Let C be the capacity and F the number of free blocks at the selected order. Searching orders and splitting cost O(log C), while choosing the minimum from a Python set costs O(F); allocation here is therefore O(F + log C), not guaranteed logarithmic. Release probes at most log C buddy sets, giving expected O(log C) time with hash-set membership. The free sets and ownership map use O(C) metadata in the worst case of unit blocks, in addition to any payload store a real allocator would require. Power-of-two rounding can waste nearly half a selected block for a request just above the previous order. This model does not provide physical pages, locking, or operating-system reclamation.

Common Mistakes

  • Do not merge blocks merely because their addresses touch; both must be free buddies of one order.
  • Do not report requested bytes as the amount of block capacity held.
  • Do not assume min over a Python set is constant time.
  • Do not allow a non-power-of-two root capacity without a different covering scheme.

Connected lessons

Compare ownership and reuse with Checkpoint arenas: reclaim a region by lifetime, Free spans: first-fit allocation and adjacent coalescing, Slab slots: reuse fixed-size pages with generation checks, then run the storage audit and contract quiz.

data structures
range-query-structures
Storage details