Module acid_alloc::buddy
source · [−]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
A binary-buddy allocator.
The raw parts of a Buddy.