slab_allocator/lib.rs
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 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360
//! 基于 Slab Allocator 的堆内存分配器
//! 使用 Linked List Allocator 作为备选分配器,分配大于 4096 字节的内存
//!
//! ## Example
//! ```no_run
//! use slab_allocator::LockedHeap;
//!
//! let mut heap = LockedHeap::empty();
//! unsafe {
//! heap.lock().init(begin, size);
//! }
//! ```
//! Credits:
//! - 接口参考 [buddy_system_allocator - A buddy system allocator in pure Rust.](https://github.com/rcore-os/buddy_system_allocator) (MIT License)
//! - 实现参考 [slab_allocator - Slab allocator for no_std systems. ](https://github.com/weclaw1/slab_allocator/tree/master) (MIT License)
#![no_std]
#![feature(allocator_api)]
#![allow(dead_code)]
use core::{
alloc::{self, AllocError, Layout},
ptr::NonNull,
};
use linked_list_allocator;
use slab::Slab;
#[cfg(feature = "use_spin")]
use spin::Mutex;
mod slab;
pub type Address = usize;
pub const MIN_ALLOC_SIZE: usize = 64;
pub const MAX_SLAB_SIZE: usize = 4096;
/// 所有 Slab 和 Fallback 的数量
pub const ALLOCATORS_NUM: usize = 8;
pub const SLABS_NUM: usize = ALLOCATORS_NUM - 1;
/// 根据大小获取对应的 Slab 索引
///
/// ## 参数
/// - `size`: 要分配的内存大小
/// ## 返回
/// 返回对应的 Slab 索引,如果大小超过最大 Slab 大小,则返回 Fallback 分配器的索引
pub fn get_slab_index(mut size: usize) -> usize {
if size <= MIN_ALLOC_SIZE {
return 0;
}
if size > MAX_SLAB_SIZE {
return ALLOCATORS_NUM - 1; // 回退到链表分配器
}
// 64 -> 0, 65-128 -> 1, 129-256 -> 2, ...
size = size.next_power_of_two();
size.trailing_zeros() as usize - 6
}
/// 堆内存分配器
pub struct Heap {
/// Slab 分配器数组
slabs: [slab::Slab; SLABS_NUM],
/// Fallback Linked List Allocator
fallback: linked_list_allocator::Heap,
/// 用户请求的字节数
user: usize,
/// 实际分配的字节数
allocated: usize,
/// 堆中的总字节数
total: usize,
}
/// 分配器类型
enum AllocType {
/// Slab 分配器,包含索引
Slab(usize),
/// 对于大于 4096 字节的内存分配申请,使用 Fallback (Linked List Allocator)
Fallback,
}
impl Heap {
/// 创建一个空的堆内存分配器
pub const fn new() -> Self {
Heap {
// 初始化 Slab 分配器数组,每个 Slab 分配器的块大小分别为 64, 128, 256, 512, 1024, 2048, 4096 字节
slabs: [
Slab::empty(64),
Slab::empty(128),
Slab::empty(256),
Slab::empty(512),
Slab::empty(1024),
Slab::empty(2048),
Slab::empty(4096),
],
fallback: linked_list_allocator::Heap::empty(),
user: 0,
allocated: 0,
total: 0,
}
}
/// 创建一个空的堆内存分配器
pub fn empty() -> Self {
Self::new()
}
/// 根据索引获取分配器类型
///
/// ## 参数
/// - `index`: 分配器索引
/// ## 返回
/// 返回对应的分配器类型,如果索引小于 ALLOCATORS_NUM - 1,则返回 Slab 分配器,
/// 否则返回 Fallback 分配器
fn get_inner(&self, index: usize) -> AllocType {
if index < ALLOCATORS_NUM - 1 {
AllocType::Slab(index)
} else {
AllocType::Fallback
}
}
/// 添加一段内存[start, end)到堆中
///
/// 由于 Linked List Allocator 需要一个连续的内存块,
/// 所以不会在此被扩展
pub unsafe fn add_to_heap(&mut self, mut start: usize, mut end: usize) {
// 避免在有些平台上出现未对齐的访问
start = (start + size_of::<usize>() - 1) & (!size_of::<usize>() + 1);
end &= !size_of::<usize>() + 1;
assert!(start <= end);
let new_heap_size = end - start;
self.total += new_heap_size;
let slab_size = new_heap_size / SLABS_NUM;
for slab_i in 0..SLABS_NUM {
let slab_start = start + slab_i * slab_size;
match self.get_inner(slab_i) {
AllocType::Slab(i) => {
self.slabs[i].grow(slab_start, slab_size);
}
AllocType::Fallback => {
unreachable!("Fallback allocator should not be initialized here");
}
}
}
}
/// 初始化 Fallback Allocator (Linked List Allocator)
///
/// 只能被调用一次
unsafe fn init_fallback(&mut self, mut start: usize, size: usize) {
// 避免在有些平台上出现未对齐的访问
start = (start + size_of::<usize>() - 1) & (!size_of::<usize>() + 1);
unsafe {
// 初始化链表分配器
self.fallback.init(start as *mut u8, size);
}
// 更新堆中的总字节数
self.total += size;
}
/// 扩展 Fallback Allocator (Linked List Allocator) 的内存
///
/// 仅扩展 Linked List Allocator 之后的内存,需要确保 Linked List Allocator 已经初始化
/// 并且内存空间 [start + original_size, start + original_size + size) 未被使用
pub unsafe fn extend_fallback(&mut self, size: usize) {
unsafe {
self.fallback.extend(size);
}
self.total += size;
}
/// 初始化堆内存分配器
///
/// ## 参数
/// - `start`: 内存起始地址
/// - `size`: 内存大小
/// ## 说明
/// 将内存分配给 Slab 分配器和 Fallback 分配器
pub unsafe fn init(&mut self, start: usize, size: usize) {
// 计算每个分配器的分配大小
let alloc_size = size / ALLOCATORS_NUM;
// 计算所有 Slab 分配器的总大小
let total_slab_size = alloc_size * SLABS_NUM;
// 计算 Fallback 分配器的大小
let fallback_size = alloc_size;
unsafe {
// 添加内存到 Slab 分配器
self.add_to_heap(start, start + total_slab_size);
// 初始化 Fallback 分配器
self.init_fallback(start + total_slab_size, fallback_size);
}
}
/// 根据内存布局选择合适的分配器
///
/// ## 参数
/// - `layout`: 内存布局
/// ## 返回
/// 返回对应的分配器类型,如果大小小于等于最大 Slab 大小,则返回 Slab 分配器,
/// 否则返回 Fallback 分配器
fn select_allocator(&self, layout: &Layout) -> AllocType {
let size = layout.size();
let index = get_slab_index(size);
self.get_inner(index)
}
/// 从堆中分配一段满足 `layout` 要求的内存
///
/// ## 参数
/// - `layout`: 内存布局
/// ## 返回
/// 返回一个指向分配内存的指针,如果分配失败,则返回错误
pub fn alloc(&mut self, layout: Layout) -> Result<NonNull<u8>, AllocError> {
let size = layout.size();
match self.select_allocator(&layout) {
AllocType::Slab(i) => {
let ret = self.slabs[i].alloc();
if ret.is_ok() {
self.user += size;
self.allocated += self.slabs[i].block_size;
}
ret
}
AllocType::Fallback => {
let ret = self.fallback.allocate_first_fit(layout);
if ret.is_ok() {
self.user += size;
self.allocated += size;
Ok(ret.unwrap())
} else {
Err(AllocError)
}
}
}
}
/// 从堆中释放一段内存
pub fn dealloc(&mut self, ptr: NonNull<u8>, layout: Layout) {
let size = layout.size();
match self.select_allocator(&layout) {
AllocType::Slab(i) => {
self.slabs[i].dealloc(ptr);
self.user -= size;
self.allocated -= self.slabs[i].block_size;
}
AllocType::Fallback => {
unsafe { self.fallback.deallocate(ptr, layout) };
self.user -= size;
self.allocated -= size;
}
}
}
/// 返回用户请求的字节数
pub fn stats_alloc_user(&self) -> usize {
self.user
}
/// 返回实际分配的字节数
pub fn stats_alloc_actual(&self) -> usize {
self.allocated
}
/// 返回堆中的总字节数
pub fn stats_total_bytes(&self) -> usize {
self.total
}
}
impl core::fmt::Debug for Heap {
/// 用于格式化输出 Heap 结构体的信息
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
write!(
f,
"Heap {{ user: {}, allocated: {}, total: {} }}",
// 获取用户分配的内存
self.stats_alloc_user(),
// 获取实际分配的内存
self.stats_alloc_actual(),
// 获取总内存
self.stats_total_bytes()
)
}
}
/// 互斥的 `Heap`
///
/// 用于在多线程环境下使用 `Heap` 分配器,作为临界资源,避免竞争
///
/// ## 用法
/// 创建一个互斥的堆并添加一个内存区域:
/// ```no_run
/// use buddy_system_allocator::*;
/// # use core::mem::size_of;
/// let mut heap = LockedHeap::new();
/// # let space: [usize; 100] = [0; 100];
/// # let begin: usize = space.as_ptr() as usize;
/// # let end: usize = begin + 100 * size_of::<usize>();
/// # let size: usize = 100 * size_of::<usize>();
/// unsafe {
/// heap.lock().init(begin, size);
/// // 或者添加到堆中
/// heap.lock().add_to_heap(begin, end);
/// }
/// ```
#[cfg(feature = "use_spin")]
pub struct LockedHeap(Mutex<Heap>);
#[cfg(feature = "use_spin")]
impl LockedHeap {
/// 创建一个新的 `LockedHeap`
pub fn new() -> Self {
LockedHeap(Mutex::new(Heap::new()))
}
/// 锁定堆并获取内部 `Heap` 的可变引用
pub fn lock(&self) -> spin::MutexGuard<Heap> {
self.0.lock()
}
/// 创建一个空的堆
pub const fn empty() -> Self {
LockedHeap(Mutex::new(Heap::new()))
}
}
#[cfg(feature = "use_spin")]
impl core::ops::Deref for LockedHeap {
type Target = Mutex<Heap>;
/// 实现 Deref trait,使 LockedHeap 可以像引用 Mutex<Heap> 一样使用
fn deref(&self) -> &Self::Target {
&self.0
}
}
#[cfg(feature = "use_spin")]
unsafe impl alloc::GlobalAlloc for LockedHeap {
/// 分配
///
/// 分配内存,根据传入的 `layout` 参数返回一个指向分配内存的指针。
/// 如果分配失败,返回一个空指针。
unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
self.0
.lock()
.alloc(layout)
.ok()
.map_or(core::ptr::null_mut(), |allocation| allocation.as_ptr())
}
/// 释放
///
/// 释放内存,根据传入的指针 `ptr` 和 `layout` 参数释放对应的内存。
unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) {
self.0
.lock()
.dealloc(unsafe { NonNull::new_unchecked(ptr) }, layout)
}
}