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