第三节 bitmap 位分配器
（待确定）看看 [rust_index::bit_set] 能否直接引入，用于简化 bitmap 的实现。
在各种内存分配的实现方式中，基于 bitmap 数据结构来表示和管理内存块，是相对简单直接的一种。我们可以用每一位 bit 来代表一个内存块，通常 1 表示空闲可用，0 表示已分配；内存块的大小可以根据需要设定，粒度小到字节 byte，大到页面 page。
这一节我们实现一个 bitmap 位分配器，下一步它将作为正式的页分配器的核心，管理内存页的分配与释放。位分配器默认配置 1M 个位，每个位代表一个页（4K 字节），这样下节的页内存分配器可管理的内存总量就是：
1M * 4K = 4G
这足以支持我们内核的需要了。
出于对效率的考虑，我们进一步把这 1M 位以嵌套的方式进行层级化管理，形成若干级 bitmap，每一级 bitmap 包含 16 位，如图：
从上往下，第 1 级只有一个 bitmap，它每一位指向第 2 级的一个 bitmap，共 16 个；如此嵌套，直至最底层 leaf level，leaf level 对应 1M 位，所以包括 64K 个 bitmap（1M / 16 = 64K）。进一步来说，每一级的 bitmap 的 bit 位对应管理着不同数量的连续页空间，第 1 级 bitmap 的一个 bit 位代表 64K 个连续页（1M / 16 = 64K），而最底层 leaf level 上每个 bitmap 的每个 bit 位仅对应一个页。
当搜索空闲页面时，只需要从上向下逐级递归查找，如果发现一个位是 0 时，就说明它对应的连续页空间已经被完全占用，不必再递归下一级，直接查看下一个位；否则说明其下对应的范围内还有空闲页，需要递归进去进一步查找和确认。
创建新组件 bitmap_allocator，核心数据结构的定义：
#![no_std]
use bit_field::BitField;
use core::ops::Range;
// bitmap_allocator/src/lib.rs
pub type BitAlloc1M = BitAllocCascade16<BitAlloc64K>;
pub type BitAlloc64K = BitAllocCascade16<BitAlloc4K>;
pub type BitAlloc4K = BitAllocCascade16<BitAlloc256>;
pub type BitAlloc256 = BitAllocCascade16<BitAlloc16>;
#[derive(Default)]
pub struct BitAllocCascade16<T: BitAlloc> {
bitset: u16, // for each bit, 1 indicates available, 0 indicates inavailable
sub: [T; 16],
}
#[derive(Default)]
pub struct BitAlloc16(u16);
// bitmap_allocator/Cargo.toml
[dependencies]
bit_field = "0.10"我们需要的是包含 1M 个位的 BitAlloc1M，包括它自己共由 5 级 bitmap 嵌套构成。最基础的元素是 BitAlloc16，包含 16 个位。
每一级的 bitmap 都实现了相同的 trait BitAlloc，以简化实现：
// bitmap_allocator/src/lib.rs
pub trait BitAlloc: Default {
/// The bitmap has a total of CAP bits, numbered from 0 to CAP-1 inclusively.
const CAP: usize;
const DEFAULT: Self;
fn alloc(&mut self) -> Option<usize>;
fn alloc_contiguous(&mut self, size: usize, align_log2: usize) -> Option<usize>;
fn next(&self, key: usize) -> Option<usize>;
fn dealloc(&mut self, key: usize);
fn insert(&mut self, range: Range<usize>);
fn remove(&mut self, range: Range<usize>);
fn is_empty(&self) -> bool;
fn test(&self, key: usize) -> bool;
}其中比较重要的是 insert(...)，alloc(...) 和 alloc_contiguous(...) 三个方法。bitmap 初始化时，所有位都是 0，表示没有可用的空间，而 insert 负责按照空闲空间的位置插入 1。另两个分别是单个页和连续页的分配方法。
我们需要对 BitAllocCascade16 和 BitAlloc16 分别实现这个 trait：
// bitmap_allocator/src/lib.rs
impl<T: BitAlloc> BitAlloc for BitAllocCascade16<T> {
const CAP: usize = T::CAP * 16;
const DEFAULT: Self = BitAllocCascade16 {
bitset: 0,
sub: [T::DEFAULT; 16],
};
fn alloc(&mut self) -> Option<usize> {
if !self.is_empty() {
let i = self.bitset.trailing_zeros() as usize;
let res = self.sub[i].alloc().unwrap() + i * T::CAP;
self.bitset.set_bit(i, !self.sub[i].is_empty());
Some(res)
} else {
None
}
}
fn alloc_contiguous(&mut self, size: usize, align_log2: usize) -> Option<usize> {
if let Some(base) = find_contiguous(self, Self::CAP, size, align_log2) {
self.remove(base..base + size);
Some(base)
} else {
None
}
}
fn dealloc(&mut self, key: usize) {
let i = key / T::CAP;
self.sub[i].dealloc(key % T::CAP);
self.bitset.set_bit(i, true);
}
fn insert(&mut self, range: Range<usize>) {
self.for_range(range, |sub: &mut T, range| sub.insert(range));
}
fn remove(&mut self, range: Range<usize>) {
self.for_range(range, |sub: &mut T, range| sub.remove(range));
}
fn is_empty(&self) -> bool {
self.bitset == 0
}
fn test(&self, key: usize) -> bool {
self.sub[key / T::CAP].test(key % T::CAP)
}
fn next(&self, key: usize) -> Option<usize> {
let idx = key / T::CAP;
(idx..16).find_map(|i| {
if self.bitset.get_bit(i) {
let key = if i == idx { key - T::CAP * idx } else { 0 };
self.sub[i].next(key).map(|x| x + T::CAP * i)
} else {
None
}
})
}
}
impl<T: BitAlloc> BitAllocCascade16<T> {
fn for_range(&mut self, range: Range<usize>, f: impl Fn(&mut T, Range<usize>)) {
let Range { start, end } = range;
assert!(start <= end);
assert!(end <= Self::CAP);
for i in start / T::CAP..=(end - 1) / T::CAP {
let begin = if start / T::CAP == i { start % T::CAP } else { 0 };
let end = if end / T::CAP == i { end % T::CAP } else { T::CAP };
f(&mut self.sub[i], begin..end);
self.bitset.set_bit(i, !self.sub[i].is_empty());
}
}
}对于 BitAlloc16 的实现：
// bitmap_allocator/src/lib.rs
impl BitAlloc for BitAlloc16 {
const CAP: usize = u16::BITS as usize;
const DEFAULT: Self = Self(0);
fn alloc(&mut self) -> Option<usize> {
let i = self.0.trailing_zeros() as usize;
if i < Self::CAP {
self.0.set_bit(i, false);
Some(i)
} else {
None
}
}
fn alloc_contiguous(&mut self, size: usize, align_log2: usize) -> Option<usize> {
if let Some(base) = find_contiguous(self, Self::CAP, size, align_log2) {
self.remove(base..base + size);
Some(base)
} else {
None
}
}
fn dealloc(&mut self, key: usize) {
assert!(!self.test(key));
self.0.set_bit(key, true);
}
fn insert(&mut self, range: Range<usize>) {
self.0.set_bits(range.clone(), 0xffff.get_bits(range));
}
fn remove(&mut self, range: Range<usize>) {
self.0.set_bits(range, 0);
}
fn is_empty(&self) -> bool {
self.0 == 0
}
fn test(&self, key: usize) -> bool {
self.0.get_bit(key)
}
fn next(&self, key: usize) -> Option<usize> {
(key..Self::CAP).find(|&i| self.0.get_bit(i))
}
}另外，对于连续分配的方法 alloc_contiguous(...)，需要一个辅助函数：
pub fn find_contiguous(
ba: &impl BitAlloc,
capacity: usize,
size: usize,
align_log2: usize,
) -> Option<usize> {
if capacity < (1 << align_log2) || ba.is_empty() {
return None;
}
let mut base = 0;
let mut offset = base;
while offset < capacity {
if let Some(next) = ba.next(offset) {
if next != offset {
// it can be guarenteed that no bit in (offset..next) is free
// move to next aligned position after next-1
assert!(next > offset);
base = (((next - 1) >> align_log2) + 1) << align_log2;
assert_ne!(offset, next);
offset = base;
continue;
}
} else {
return None;
}
offset += 1;
if offset - base == size {
return Some(base);
}
}
None
}现在 bitmap 位分配器实现完成，它的核心就是对 bit 位的管理，我们来写几个测试用例验证一下这方面的功能：
// bitmap_allocator/tests/test_bitalloc.rs
use bitmap_allocator::*;
#[test]
fn bitalloc16() {
let mut ba = BitAlloc16::default();
assert_eq!(BitAlloc16::CAP, 16);
ba.insert(0..16);
for i in 0..16 {
assert!(ba.test(i));
}
ba.remove(2..8);
assert_eq!(ba.alloc(), Some(0));
assert_eq!(ba.alloc(), Some(1));
assert_eq!(ba.alloc(), Some(8));
ba.dealloc(0);
ba.dealloc(1);
ba.dealloc(8);
assert!(!ba.is_empty());
for _ in 0..10 {
assert!(ba.alloc().is_some());
}
assert!(ba.is_empty());
assert!(ba.alloc().is_none());
}
#[test]
fn bitalloc4k() {
let mut ba = BitAlloc4K::default();
assert_eq!(BitAlloc4K::CAP, 4096);
ba.insert(0..4096);
for i in 0..4096 {
assert!(ba.test(i));
}
ba.remove(2..4094);
for i in 0..4096 {
assert_eq!(ba.test(i), !(2..4094).contains(&i));
}
assert_eq!(ba.alloc(), Some(0));
assert_eq!(ba.alloc(), Some(1));
assert_eq!(ba.alloc(), Some(4094));
ba.dealloc(0);
ba.dealloc(1);
ba.dealloc(4094);
assert!(!ba.is_empty());
for _ in 0..4 {
assert!(ba.alloc().is_some());
}
assert!(ba.is_empty());
assert!(ba.alloc().is_none());
}
#[test]
fn bitalloc_contiguous() {
let mut ba0 = BitAlloc16::default();
ba0.insert(0..BitAlloc16::CAP);
ba0.remove(3..6);
assert_eq!(ba0.next(0), Some(0));
assert_eq!(ba0.alloc_contiguous(1, 1), Some(0));
assert_eq!(find_contiguous(&ba0, BitAlloc4K::CAP, 2, 0), Some(1));
let mut ba = BitAlloc4K::default();
assert_eq!(BitAlloc4K::CAP, 4096);
ba.insert(0..BitAlloc4K::CAP);
ba.remove(3..6);
assert_eq!(ba.next(0), Some(0));
assert_eq!(ba.alloc_contiguous(1, 1), Some(0));
assert_eq!(ba.next(0), Some(1));
assert_eq!(ba.next(1), Some(1));
assert_eq!(ba.next(2), Some(2));
assert_eq!(find_contiguous(&ba, BitAlloc4K::CAP, 2, 0), Some(1));
assert_eq!(ba.alloc_contiguous(2, 0), Some(1));
assert_eq!(ba.alloc_contiguous(2, 3), Some(8));
ba.remove(0..4096 - 64);
assert_eq!(ba.alloc_contiguous(128, 7), None);
assert_eq!(ba.alloc_contiguous(7, 3), Some(4096 - 64));
ba.insert(321..323);
assert_eq!(ba.alloc_contiguous(2, 1), Some(4096 - 64 + 8));
assert_eq!(ba.alloc_contiguous(2, 0), Some(321));
assert_eq!(ba.alloc_contiguous(64, 6), None);
assert_eq!(ba.alloc_contiguous(32, 4), Some(4096 - 48));
for i in 0..4096 - 64 + 7 {
ba.dealloc(i);
}
for i in 4096 - 64 + 8..4096 - 64 + 10 {
ba.dealloc(i);
}
for i in 4096 - 48..4096 - 16 {
ba.dealloc(i);
}
}执行 make test，所有测试用例通过！