buddy_core/lib.rs
1#![no_std]
2
3//! # Buddy Allocator Core (`#![no_std]`)
4//!
5//! A highly optimized, compile-time configurable **Binary Buddy Allocator** engine designed specifically
6//! for bare-metal systems, custom OS kernels, and embedded environments where a standard library (`std`)
7//! is unavailable.
8//!
9//! ## Architecture Overview
10//!
11//! The allocator is structurally split into three distinct layers of abstraction:
12//!
13//! 1. **[`BuddyBase`] (The Brain):** Coordinates the overall system. It handles high-level allocation requests,
14//! implements recursive buddy splitting, and triggers cascading buddy mergers (coalescing) when blocks are freed.
15//! 2. **[`BuddyOrder`] (The Layer Manager):** Manages a doubly-linked list of free blocks representing a specific
16//! power-of-two size class.
17//! 3. **[`IBuddyMdAdapter`] & [`IBuddyMetaData`] (The Hardware/Data Bridges):** Decouples the physical location
18//! of metadata from the allocator's logical operations. This allows metadata to be stored alongside the blocks
19//! (intrusive), in a flat global array, or even in a completely custom page-table-like structure.
20//!
21//! ---
22//!
23//! ## Designing a Custom Metadata Adapter
24//!
25//! To plug this engine into your system, you must implement two traits:
26//! * [`IBuddyMetaData`]: Defines how to read/write intrusive node linkages (`next`, `last`, `order`, etc.).
27//! * [`IBuddyMdAdapter`]: Defines how to retrieve a metadata handle from a raw physical block address (`u64`).
28//!
29//! # Examples
30//!
31//! Below is a comprehensive blueprint demonstrating how to implement the required traits using a mock static
32//! array for block metadata, and how to initialize and drive [`BuddyBase`].
33//!
34//!
35//! ```rust
36//! use buddy_core::{BuddyBase, IBuddyMdAdapter, IBuddyMetaData, BuddyError};
37//!
38//! // 1. Define our Node Metadata structure that actually lives in memory
39//! #[derive(Clone, Copy)]
40//! pub struct MyPageMetadata {
41//! next: Option<u64>,
42//! last: Option<u64>,
43//! order: u8,
44//! ceil_reduction: u8,
45//! is_linked: bool,
46//! }
47//!
48//! // 2. Define a Handle that wraps a raw pointer to the metadata.
49//! // This ensures modifications write back to the original table.
50//! #[derive(Clone, Copy)]
51//! pub struct MyPageMetadataHandle {
52//! ptr: *mut MyPageMetadata,
53//! }
54//!
55//! // 3. Implement the IBuddyMetaData interface by defining the Associated Type inside the body
56//! pub struct MyMetaInterface;
57//! impl IBuddyMetaData for MyMetaInterface {
58//! type MetaData = MyPageMetadataHandle;
59//!
60//! fn get_next(md: &Self::MetaData) -> Option<u64> {
61//! unsafe { (*md.ptr).next }
62//! }
63//! fn set_next(md: &mut Self::MetaData, next: Option<u64>) {
64//! unsafe { (*md.ptr).next = next; }
65//! }
66//! fn get_last(md: &Self::MetaData) -> Option<u64> {
67//! unsafe { (*md.ptr).last }
68//! }
69//! fn set_last(md: &mut Self::MetaData, last: Option<u64>) {
70//! unsafe { (*md.ptr).last = last; }
71//! }
72//! fn get_order(md: &Self::MetaData) -> u8 {
73//! unsafe { (*md.ptr).order }
74//! }
75//! fn set_order(md: &mut Self::MetaData, order: u8) {
76//! unsafe { (*md.ptr).order = order; }
77//! }
78//! fn get_ceil_reduction(md: &Self::MetaData) -> u8 {
79//! unsafe { (*md.ptr).ceil_reduction }
80//! }
81//! fn set_ceil_reduction(md: &mut Self::MetaData, reduct: u8) {
82//! unsafe { (*md.ptr).ceil_reduction = reduct; }
83//! }
84//! fn is_linked(md: &Self::MetaData) -> bool {
85//! unsafe { (*md.ptr).is_linked }
86//! }
87//! fn set_link(md: &mut Self::MetaData, linked: bool) {
88//! unsafe { (*md.ptr).is_linked = linked; }
89//! }
90//! }
91//!
92//! // 4. Set up a global metadata storage
93//! static mut METADATA_TABLE: [MyPageMetadata; 1024] = [MyPageMetadata {
94//! next: None,
95//! last: None,
96//! order: 0,
97//! ceil_reduction: 0,
98//! is_linked: false,
99//! }; 1024];
100//!
101//! // 5. Implement the Adapter to return the pointer-based Handle
102//! pub struct MySystemAdapter;
103//! impl IBuddyMdAdapter for MySystemAdapter {
104//! type MetaDataHandle = MyPageMetadataHandle;
105//! type Interface = MyMetaInterface;
106//!
107//! fn get_md(n: u64) -> Option<Self::MetaDataHandle> {
108//! let index = n as usize;
109//! if index < 1024 {
110//! unsafe {
111//! let ptr = core::ptr::addr_of_mut!(METADATA_TABLE[index]);
112//! Some(MyPageMetadataHandle { ptr })
113//! }
114//! } else {
115//! None
116//! }
117//! }
118//! }
119//!
120//! // 6. Drive the Buddy Allocator in a standard execution flow
121//! fn main() -> Result<(), BuddyError> {
122//! let mut allocator = BuddyBase::<MySystemAdapter, 8>::new();
123//!
124//! allocator.push_with_order(0, 0, 0)?;
125//! allocator.push_with_order(1, 0, 0)?;
126//!
127//! let allocated_block = allocator.pop(1)?;
128//! assert_eq!(allocated_block, 0);
129//!
130//! Ok(())
131//! }
132//! ```
133
134mod buddy_base;
135mod buddy_err;
136mod buddy_md_adapter_interface;
137mod buddy_md_interface;
138mod buddy_order;
139mod utils;
140
141pub use buddy_base::BuddyBase;
142pub use buddy_err::BuddyError;
143pub use buddy_md_adapter_interface::IBuddyMdAdapter;
144pub use buddy_md_interface::IBuddyMetaData;
145pub use utils::allocate_ceil_reductor;