slab_allocator/slab.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
//! Slab Allocator
//!
//! Slab Allocator 是一种简单的内存分配器,它将内存分配为固定大小的块,并在需要时分配这些块。
//!
//! 在分配时,保持各个大小的 Slab 块数量的平衡,以适应不同大小的内存分配请求。
use core::{alloc::AllocError, ptr::NonNull};
use crate::Address;
/// Slab 内存块分配器。
///
/// ## 字段
/// - `block_size`:每个内存块的大小
/// - `block_num`:内存块的数量
/// - `free_list`:空闲内存块列表
pub struct Slab {
pub block_size: usize,
pub block_num: usize,
free_list: FreeList,
}
impl Slab {
/// 创建一个新的空的 `Slab` 实例。
///
/// ## 参数
/// - `block_size`:每个内存块的大小
/// ## 返回
/// 具有指定块大小的新 `Slab` 空实例,其中没有内存块。
pub const fn empty(block_size: usize) -> Self {
Slab {
block_size,
block_num: 0,
free_list: FreeList::empty(),
}
}
/// 创建一个新的 `Slab` 实例。
///
/// ## 参数
/// - `start`:内存块的起始地址
/// - `block_size`:每个内存块的大小
/// - `block_num`:内存块的数量
/// ## 返回
/// 具有指定参数的新 `Slab` 实例。
pub fn new(start: Address, block_size: usize, block_num: usize) -> Self {
Slab {
block_size,
block_num,
free_list: FreeList::new(start, block_size, block_num),
}
}
/// 扩展 `Slab` 实例的内存块。
///
/// ## 参数
/// - `start`:新内存块的起始地址
/// - `slab_size`:新内存块的总大小
pub fn grow(&mut self, start: Address, slab_size: usize) {
let block_num = slab_size / self.block_size;
self.block_num += block_num;
// 添加到 self.free_list
for i in 0..block_num {
let block = (start + i * self.block_size) as *mut FreeBlock;
let block = unsafe { &mut *block };
self.free_list.push(block);
}
}
/// 从 `Slab` 实例中分配一个内存块。
///
/// ## 返回
/// 如果成功分配内存块,则返回内存块的地址;否则返回 `None`。
pub fn alloc(&mut self) -> Result<NonNull<u8>, AllocError> {
self.free_list
.pop()
.map(|block| unsafe { NonNull::new_unchecked(block as *mut FreeBlock as *mut u8) })
.ok_or(AllocError)
}
/// 将一个内存块释放回 `Slab` 实例。
///
/// ## 参数
/// - `addr`:要释放的内存块的地址
pub fn dealloc(&mut self, addr: NonNull<u8>) {
let block = addr.as_ptr() as *mut FreeBlock;
let block = unsafe { &mut *block };
self.free_list.push(block);
}
}
/// 内存块空闲列表
struct FreeList {
/// 空闲列表的长度
len: usize,
/// 空闲列表的头部节点
head: Option<&'static mut FreeBlock>,
}
/// 表示一个空闲的内存块
struct FreeBlock {
/// 指向下一个空闲块的可选引用
next: Option<&'static mut FreeBlock>,
}
/// 为 `FreeList` 实现 `Drop` 特性,以便在 `FreeList` 被销毁时释放所有节点。
impl Drop for FreeList {
fn drop(&mut self) {
let mut current = self.head.take();
while let Some(node) = current {
current = node.next.take();
}
}
}
impl FreeList {
/// 建立一个新的空闲列表
pub const fn empty() -> Self {
FreeList { len: 0, head: None }
}
/// 建立一个新的空闲列表,其中包含指定数量的空闲块。
///
/// ## 参数
/// - `start`:内存块的起始地址
/// - `block_size`:每个内存块的大小
/// - `block_num`:内存块的数量
/// ## 返回
/// 具有指定参数的新 `FreeList` 实例。
pub fn new(start: Address, block_size: usize, block_num: usize) -> Self {
let mut list = FreeList { len: 0, head: None };
for i in (0..block_num).rev() {
let block = (start + i * block_size) as *mut FreeBlock;
let block = unsafe { &mut *block };
list.push(block);
}
list
}
/// 将一个空闲块推入空闲列表。
///
/// ## 参数
/// - `free_block`:要添加到列表中的空闲块的可变引用。
pub fn push(&mut self, free_block: &'static mut FreeBlock) {
free_block.next = self.head.take();
self.head = Some(free_block);
self.len += 1;
}
/// 从空闲列表中弹出一个空闲块。
///
/// ## 返回
/// 如果列表不为空,则包含对空闲块的可变引用的 `Option`,如果列表为空,则返回 `None`。
pub fn pop(&mut self) -> Option<&'static mut FreeBlock> {
self.head.take().map(|free_block| {
self.head = free_block.next.take();
self.len -= 1;
free_block
})
}
}