Expand description
Binary-buddy allocation.
The buddy algorithm divides the managed region into a fixed number of equal, power-of-two-sized blocks. Each block can be recursively split in half a fixed number of times in order to provide finer-grained allocations. Buddy allocators excel in cases where most allocations have a power-of-two size.
§Characteristics
§Time complexity
| Operation | Best-case | Worst-case |
|---|---|---|
| Allocate (size <= align) | O(1) | O(log2levels) |
| Deallocate | O(1) | O(log2levels) |
§Fragmentation
Buddy allocators exhibit limited external fragmentation, but suffer up to 50% internal fragmentation because all allocatable blocks have a power-of-two size.
Structs§
- Buddy
- A binary-buddy allocator.
- RawBuddy
Parts - The raw parts of a
Buddy.