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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
// Copyright (C) 2026 COOLJAPAN OU (Team KitaSan)
// SPDX-License-Identifier: Apache-2.0
#![allow(dead_code)]
//! Binary buddy allocator stub — manages a power-of-two address space by
//! recursively splitting and merging "buddy" blocks to satisfy allocations.
/// Order of the allocator: manages 2^order minimum-sized units.
pub struct BuddyAllocator {
max_order: usize,
/// free_lists[order] holds the starting indices of free blocks at that order.
free_lists: Vec<Vec<usize>>,
total_units: usize,
}
impl BuddyAllocator {
/// Create a buddy allocator spanning `2^max_order` minimum units.
pub fn new(max_order: usize) -> Self {
let mut free_lists = vec![Vec::new(); max_order + 1];
free_lists[max_order].push(0);
let total_units = 1 << max_order;
Self {
max_order,
free_lists,
total_units,
}
}
/// Allocate a block of `2^order` units. Returns the block start index.
pub fn allocate(&mut self, order: usize) -> Option<usize> {
if order > self.max_order {
return None;
}
/* find the smallest available order >= requested */
let mut found = None;
for o in order..=self.max_order {
if !self.free_lists[o].is_empty() {
found = Some(o);
break;
}
}
let found_order = found?;
let block = self.free_lists[found_order].pop()?;
/* split down to the requested order */
let mut o = found_order;
while o > order {
o -= 1;
let buddy = block + (1 << o);
self.free_lists[o].push(buddy);
}
Some(block)
}
/// Free a block of `2^order` units starting at `addr`.
pub fn free(&mut self, addr: usize, order: usize) {
let mut current = addr;
let mut o = order;
while o < self.max_order {
let buddy = current ^ (1 << o);
/* check if buddy is free at this order */
if let Some(pos) = self.free_lists[o].iter().position(|&b| b == buddy) {
self.free_lists[o].remove(pos);
current = current.min(buddy);
o += 1;
} else {
break;
}
}
self.free_lists[o].push(current);
}
/// Number of free units summed across all orders.
pub fn free_units(&self) -> usize {
self.free_lists
.iter()
.enumerate()
.map(|(o, list)| list.len() * (1 << o))
.sum()
}
/// Total capacity in minimum units.
pub fn total_units(&self) -> usize {
self.total_units
}
/// Maximum order this allocator supports.
pub fn max_order(&self) -> usize {
self.max_order
}
}
/// Create a buddy allocator of 2^`max_order` minimum units.
pub fn new_buddy_allocator(max_order: usize) -> BuddyAllocator {
BuddyAllocator::new(max_order)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_alloc_order_zero() {
let mut b = BuddyAllocator::new(4);
let addr = b.allocate(0);
assert!(addr.is_some()); /* order-0 alloc succeeds */
}
#[test]
fn test_alloc_max_order() {
let mut b = BuddyAllocator::new(3);
let addr = b.allocate(3).expect("should succeed");
assert_eq!(addr, 0); /* whole block starts at 0 */
assert!(b.allocate(0).is_none()); /* pool exhausted */
}
#[test]
fn test_free_and_realloc() {
let mut b = BuddyAllocator::new(3);
let addr = b.allocate(3).expect("should succeed");
b.free(addr, 3);
assert!(b.allocate(3).is_some()); /* full block available again */
}
#[test]
fn test_split_and_merge() {
let mut b = BuddyAllocator::new(2);
/* allocate two order-0 blocks, free both — they should merge */
let a0 = b.allocate(0).expect("should succeed");
let a1 = b.allocate(0).expect("should succeed");
b.free(a0, 0);
b.free(a1, 0);
/* now order-1 buddy pair should be merged back, order-2 may coalesce */
assert_eq!(b.free_units(), 4); /* all units free */
}
#[test]
fn test_total_units() {
let b = BuddyAllocator::new(4);
assert_eq!(b.total_units(), 16); /* 2^4 */
}
#[test]
fn test_free_units_initially_full() {
let b = BuddyAllocator::new(3);
assert_eq!(b.free_units(), 8); /* 2^3 units free at start */
}
#[test]
fn test_max_order() {
let b = BuddyAllocator::new(5);
assert_eq!(b.max_order(), 5); /* accessor correct */
}
#[test]
fn test_alloc_beyond_max_order() {
let mut b = BuddyAllocator::new(2);
assert!(b.allocate(10).is_none()); /* order too large */
}
#[test]
fn test_new_helper() {
let b = new_buddy_allocator(3);
assert_eq!(b.total_units(), 8); /* helper works */
}
}