Skip to main content

Binary Buddies

Introduction​

This document explains the binary buddy system.

info

This implementation is more complex than buckets or linked-lists, but provides low fragmentation and systematic block merging.

Main characteristics:

  • Low fragmentation.
  • Allocation may be slow.
  • Complexity and performance highly depend on additional data structures used to track free blocks.

Principle​

  • Manage a contiguous memory region of size n (with n a power of two).
  • This region can be:
    • Given to the user as a whole
    • Split recursively into two equal halves.
  • The two halves are called buddies.
  • Each block’s (divided or not) size is always a power of two, with a predefined minimum block size.

Binary Buddies Structure​

Linked-list

Memory Management​

Allocation​

  1. User calls malloc(s).
  2. Compute s2p = smallest power of two ≥ s + metadata_size.
  3. Find the smallest available block of at least s2p.
  4. If the block is more than twice the requested size, split recursively into buddies until the block matches s2p.
  5. Return the address of the buddy and mark it as used.

Free​

  1. Mark the block as free.
  2. If its buddy is also free, merge them into a larger free block.
  3. Repeat recursively until no further merge is possible.
  4. If the whole page is free, it can be unmapped.

Video example of a binary buddies implementation​

Metadata​

Each block stores metadata:

  • Block status (allocated/free).
  • Block size (power of two).