Skip to main content

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;