固定大小分配器

使用Rust实现的固定大小分配器

• 固定大小分配器
• 基本用法
• 工作原理
  • 分配器初始化
  • 分配和释放内存
  • 将块地址转换为空闲表索引及反之
• 许可

基本用法

创建和使用分配器

const BLOCK_SIZE: usize = mem::size_of::<u32>();
const BLOCK_COUNT: usize = 64;

const INITIALIZE_WITH_ZEROS: bool = false;

// Create an allocator that is placed on the standard system allocator's heap.
let mut alloc = FixedSizeAllocator::<BLOCK_SIZE, BLOCK_COUNT>::new(INITIALIZE_WITH_ZEROS);

// Allocate memory
let ptr = alloc.as_mut().alloc::<u32>()
    .unwrap_or_else(|| panic!("Failed to allocate"));

// Initialize the allocated memory
unsafe {
    ptr.write(89);
    assert_eq!(ptr.read(), 89);
    *ptr.as_ptr() = 43;
    assert_eq!(*ptr.as_ptr(), 43);
}

// Finally, free the pointer
alloc.as_mut().free_nonnull(ptr)
    .unwrap_or_else(|err| panic!("Failed to free pointer: {:?}", err));

在栈上创建分配器。如果标准系统分配器不可用或您不想使用它，则必须在栈上实例化分配器。

const BLOCK_SIZE: usize = mem::size_of::<u32>();
const BLOCK_COUNT: usize = 64;

const INITIALIZE_WITH_ZEROS: bool = false;

// Create an allocator on the stack and pin it in place.
// Pinning is required to use the allocator safely.
let mut alloc = pin!( unsafe {
    FixedSizeAllocator::<BLOCK_SIZE, BLOCK_COUNT>::new_unpinned(INITIALIZE_WITH_ZEROS)
});

// Allocate memory
let ptr = alloc.as_mut().alloc::<u32>()
    .unwrap_or_else(|| panic!("Failed to allocate"));

// Initialize the allocated memory
unsafe {
    ptr.write(89);
    assert_eq!(ptr.read(), 89);
    *ptr.as_ptr() = 43;
    assert_eq!(*ptr.as_ptr(), 43);
}

// Finally, free the pointer
alloc.as_mut().free_nonnull(ptr)
    .unwrap_or_else(|err| panic!("Failed to free pointer: {:?}", err));

工作原理

分配器初始化

固定大小分配器通过预分配一块内存来实现，这块内存可以容纳任意数量的 N 个内存块，每个块大小为 S 字节，其中 S 是一个正非零整数，N 是一个正整数。因此，总堆大小为 S * N。堆逻辑上分为 N 块，每块大小为 S 字节，并使用一个空闲表来跟踪哪些块是空闲的，哪些已被分配。

空闲表实现为一个大小为 N 的布尔值数组，每个布尔值代表一个内存块的状态：如果为 true，则表示该块是空闲的；如果为 false，则表示该块已被分配。

分配和释放内存

在分配请求时，分配器使用二分查找算法遍历空闲表，如果找到一个空闲块，则将其标记为已分配，并返回指向该块起始地址的指针。

在用户请求释放时，分配器根据给定的指针计算出该内存块元数据在空闲表中的索引。然后，该内存块在空闲表中被标记为空闲。

将块地址转换为空闲表索引及反之

由于堆被固定在内存中，其内存地址不能改变。这意味着在堆上分配的内存块的指针在整个分配器的生命周期内保持有效。

空闲表按地址递增顺序存储内存块元数据。从堆开始处的偏移量与空闲表中内存块的索引成正比，因此 偏移量 = 索引 * 块大小。然后通过在堆开始处加上计算出的偏移量来计算内存块的实地址：块地址 = 堆地址 + (块索引 * 块大小)。

然后通过上述算法的逆过程计算空闲表中内存块元数据的索引：块索引 = (块地址 - 堆地址) / 块大小。

许可

此存储库及其所有文件均根据 MIT许可证 发布。