๐ What is this?
buddy-core is not a ready-to-use page allocator. It is the engine โ the pure algorithmic
core of a binary buddy allocator, completely decoupled from where and how block metadata
is actually stored.
Think of it like this:
- You decide where the metadata lives (a static array, a slab, a page-table-like structure, intrusive headers inside the block itself โ anything).
buddy-coredecides when to split blocks, when to merge (coalesce) them, and how to keep track of free lists per order โ the actual buddy-system logic.
This separation is done through two small traits (IBuddyMdAdapter and IBuddyMetaData), which act
as a bridge between the allocator's logic and your storage of choice. Because of this, buddy-core
has zero dependency on alloc and works in the most constrained bare-metal environments โ
OS kernels, bootloaders, and embedded firmware.
๐ง The Core Idea: Buddy Allocation
A binary buddy allocator manages memory in power-of-two sized blocks, organized into "orders":
Order 0 โ block size 1 unit
Order 1 โ block size 2 units
Order 2 โ block size 4 units
Order 3 โ block size 8 units
...
Order N โ block size 2^N units
Every block at order o has exactly one buddy: the adjacent block of the same size that,
together with it, forms a single block at order o + 1. The buddy's address is computed with a
single XOR:
buddy(n, order) = n ^ (1 << order)
This is the mathematical trick that makes buddy allocators fast โ no searching required to find a block's partner, just one bitwise operation.
Splitting (on allocation)
If you ask for a block at order k and none is free, the allocator recursively climbs to the
next order up looking for a free block. Once found, it splits that block in half:
Order 3 block [0..8) "found free"
โ
โผ split
Order 2 block [0..4) Order 2 block [4..8)
(returned to you) (pushed back as free)
If the order-2 half is still bigger than requested, it keeps splitting downward until it reaches the requested order.
Coalescing (on free)
When you free a block, the allocator checks whether its buddy is also free. If it is, they merge back into a single block at the next order up โ and the process repeats recursively, bubbling upward, until a busy buddy is found or the top order is reached.
Free block 4 (order 2)
โ
is buddy (block 0, order 2) free? โ yes
โ
โผ merge
Order 3 block [0..8) is now free
โ
is buddy (block 8, order 3) free? โ check again...
This recursive merge is what keeps external fragmentation low over time.
๐ Architecture
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ BuddyBase โ
โ The orchestrator. Owns one BuddyOrder per order level. โ
โ Implements recursive splitting (buddy_emission) and โ
โ recursive coalescing (insert_fix). โ
โโโโโโโโโโโโโโโโโโโโโโโโโฌโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ owns [ BuddyOrder; ORDER_COUNT ]
โผ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ BuddyOrder โ
โ Manages ONE order's free list (a doubly linked list). โ
โ push() / pop() / try_remove_at_order() โ head and โ
โ middle-of-list insert/extract operations. โ
โโโโโโโโโโโโโโโโโโโโโโโโโฌโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ reads/writes node state via
โผ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ IBuddyMdAdapter + IBuddyMetaData โ
โ Your bridge. You decide WHERE metadata for a block โ
โ index lives (static array, intrusive header, etc.) and โ
โ provide get/set for: next, last, order, ceil_reduction, โ
โ is_linked. โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
BuddyBase<Adapter, ORDER_COUNT> โ the brain
new()โ buildsORDER_COUNTindependentBuddyOrderlayers.push_with_order(addr, order, ceil_reduct)โ bootstraps a raw block into the system at a given order, with an optional "ceiling" limiting how far it's allowed to merge upward (useful for carving reserved zones that shouldn't blend with other memory regions).push(addr)โ frees a block, verifies alignment, detects double-frees by checking the buddy's state, and hands off toinsert_fixfor recursive coalescing.pop(order)โ allocates a block at the given order. Tries the direct free list first, and if empty, callsbuddy_emissionto recursively split a larger block down.insert_fix(private) โ the recursive merge engine. Looks up the buddy, tries to unlink it from its free list; if found, merges and recurses one order higher; if not found (buddy is busy), the block is simply pushed into its own free list.buddy_emission(private) โ the recursive split engine. Climbs orders upward until a free block is found, then splits it back down, pushing the leftover half into the free list at each step.
BuddyOrder<ORDER_COUNT, Adapter> โ a single order's free list
A hand-rolled doubly linked list over your metadata, addressed by raw u64 block index instead
of pointers:
push(n)โ inserts at the head. Errors on double-free (is_linkedalreadytrue).pop(target_order)โ removes the head, bumps its recorded order totarget_order.try_remove_at_order(n, target_order)โ dispatches to eitherpop(ifnis the head) ortry_unlink_at_order(ifnis somewhere in the middle of the list), so merges can grab a buddy no matter where it sits in the list.try_unlink_at_order(private) โ classic doubly-linked-list middle-removal: stitches the neighbors'next/lastpointers together.can_be_at_order(private) โ a ceiling check ensuring a block isn't merged past its assigned reduction limit.
IBuddyMdAdapter / IBuddyMetaData โ the storage bridge
Two traits you implement once for your environment:
Why a "handle" and not a direct reference? Methods take &Self::MetaData (a reference to
the handle, not to the raw struct). If your handle is itself &'static mut SomeStruct, this
becomes a reference-to-a-mutable-reference. That extra layer of indirection is what lets the
allocator read and write several different blocks' metadata in the same scope (e.g. a block and
its buddy) without the borrow checker treating it as two live mutable borrows of the same data โ
all without runtime-checked wrappers like RefCell.
๐ Quick Start
use ;
// 1. Your metadata struct โ however you want to store per-block state.
// 2. A handle wrapping a raw pointer, so writes go back to the original table.
// 3. Implement the get/set interface.
;
// 4. Global storage for 1024 blocks' metadata.
static mut TABLE: = ;
// 5. The adapter maps a raw block index -> a handle into that table.
;
๐ Key Concepts Explained Simply
| Concept | Plain-English Explanation |
|---|---|
| Order | A "size class". Order o means a block of size 2^o. Order 0 is the smallest unit. |
| Buddy | The specific neighboring block that combines with yours to form the next-size-up block. Found instantly via XOR, no search needed. |
| Splitting | Breaking a big free block into two smaller (buddy) blocks when a smaller size is requested and none is directly available. |
| Coalescing | Merging a freed block with its buddy (if also free) into a bigger block, recursively, to fight fragmentation. |
Ceiling / ceil_reduction |
An optional cap that stops a block from merging past a certain order โ useful for keeping separate memory regions (e.g. DMA-safe memory vs normal RAM) from blending together during coalescing. |
| Metadata Adapter | The plug-in point where you tell the allocator how to fetch a block's bookkeeping data (order, links, etc.) from wherever you choose to store it. |
| Double-free protection | Before merging, the allocator peeks at the buddy's recorded order. If the buddy looks "already free at a higher order" than expected, that's a red flag for a double free, and it errors out instead of corrupting state. |
๐งฑ Deep Dive: ceil_reduction โ pinning a block below a certain order
Normally, when a block is freed, insert_fix keeps merging it with its buddy, upward,
order after order, for as long as a free buddy is available. Left unchecked, this means
any two adjacent free blocks can eventually combine into the largest possible block size โ
even if they came from two logically different memory regions that just happen to sit next
to each other in address space.
ceil_reduction is how you tell the allocator: "this specific block is allowed to merge
upward, but only up to this order โ never past it." It acts as a personal ceiling, carried
in the block's own metadata, checked on every merge attempt.
How it's computed
let ceiled_max_ord = - ceil_reductor;
So ceil_reduct isn't the ceiling order itself โ it's how many orders below ORDER_COUNT
the ceiling sits. A ceil_reduct of 0 means "no restriction, allowed to merge all the way
to the top order." A larger ceil_reduct pulls that ceiling further down.
This check happens in two places:
BuddyBase::insert_fixโ before recursing toorder + 1, it checks(order + 1) >= ceiled_max_ord. If the next merge would cross the ceiling, it stops and pushes the block into its current order's free list instead of climbing further.BuddyOrder::can_be_at_orderโ a second, symmetric guard used duringpop/unlink, making sure a block being pulled out for a merge is actually still allowed to exist at the target order:(target_order + ceil_reduct) < ORDER_COUNT.
Worked example
Say ORDER_COUNT = 13 (orders 0..=12 exist, order 12 is the biggest). You have two separate
memory zones sitting next to each other in address space โ a small reserved DMA zone and the
regular general-purpose zone โ and you don't want blocks from one ever coalescing into the
other:
// General-purpose zone: free to merge all the way up to order 12.
allocator.push_with_order?; // ceil_reduct = 0 -> ceiling = order 12 (no cap)
// DMA-reserved zone: only 3 pages (order 0..=9 sized blocks), never allowed to
// grow into a block bigger than order 9.
allocator.push_with_order?; // ceil_reduct = 3 -> ceiling = 13 - 3 = order 10
For the second block: even if its buddy is free and merging would normally continue, the
moment the recursive merge in insert_fix would produce a block at order 10 or higher
((order + 1) >= ceiled_max_ord, i.e. >= 10), it stops climbing and simply rests as a free
block at whatever order it reached โ order 9 at most. It can never accidentally fuse with a
neighboring block from the general-purpose zone into something order 10 or larger.
Why this matters in practice
- Zone isolation โ keep DMA-safe, NUMA-local, or otherwise "special" memory regions from silently merging with regular memory during coalescing.
- Bounded worst case โ you can guarantee a region never grows past a known maximum block size, which matters for allocators that reserve fixed-size regions for specific subsystems.
- No extra bookkeeping cost โ the ceiling travels with the block's own metadata
(
get_ceil_reduction/set_ceil_reduction), so there's no global table or extra pass needed to enforce it; it's checked as a cheap arithmetic comparison right inside the existing merge/split recursion.
๐งช Testing
The crate ships with a logic + fuzz test (tests/logic_test.rs in the example test suite) that:
- Sets up a realistic mixed allocator โ nine blocks pushed at different orders (12, 11, 11,
12, 10, 10, 10, 9, 9) with matching
ceil_reductvalues, simulating a real memory layout with segmented zones. - Drains everything down to order 0, shuffles the resulting addresses (to remove any ordering bias), then frees them all back โ exercising the full split/merge pipeline under randomized conditions.
- Asserts
alloc_count == dealloc_countโ every allocation must be matched by exactly one deallocation, proving no blocks are silently lost or duplicated. - Exhaustively drains each top order (12 โ 9) and asserts the exact expected block count
comes out before hitting
BuddyError::NotFoundโ proving the coalescing pipeline correctly reassembled all fragments back into their original large blocks.
Run it with:
โ ๏ธ Error Reference
| Variant | Meaning |
|---|---|
BuddyError::DoubleFree |
A block was freed while already marked as linked/free โ classic double-free bug caught before it can corrupt the free list. |
BuddyError::DataCorrupted |
A metadata lookup failed (get_md returned None) where a valid handle was expected โ usually points to an out-of-bounds or invalid index. |
BuddyError::NotFound |
No free block available at the requested order, and nothing higher could be split (allocator is out of memory at that size), or a buddy couldn't be located for a merge/unlink. |
BuddyError::AlignmentMismatch |
The address isn't aligned to its order's boundary, or the order requested exceeds the block's allowed ceiling. |
๐ฆ Installation
[]
= "0.1.1"
edition = "2024", #![no_std], no alloc dependency.
๐ License
This project is licensed under the MIT License. See the LICENSE file for details.