buddy blocks

Concept

• partition into blocks of size 2ⁿ
• each block has an adjacent buddy of the same size
• if free, both can be merged into a larger block

Implementation

• table, A[0..n] where 2ⁿ is the largest allocatable block size
• A[j] is a linked list of the free blocks of size 2ʲ

Allocation

• for a block of size N

1. find the smallest j such that 2ʲ >= N
2. check A[j]
   • if there is a free block, allocate it, remove from the table
   • else, divide a larger block

Deallocation

• for a block of size N
• check in A[j] where 2ʲ == N
  • if the buddy is free, merge it up the table
  • else, insert it into the table

Identifying buddies

• for blocks of size 2ᵏ
• the address is identical, only the kth bit is flipped

the suffix is always all 0s