简单块分配器

用 Rust 编写的简单 no_std 分配器，用于在固定大小的块/块中管理内存。适用于基本的 no_std 二进制文件，其中您想管理几个兆字节的堆，而不需要复杂的特性，如分页/页面表管理。相反，此分配器从固定的/静态内存区域获取内存，并从该区域分配内存。此内存区域可以包含在使用此分配器的可执行文件中。请参阅下面的示例。

⚠ 其他具有不同属性（例如更好的内存利用率但性能较低）的分配器也存在。仓库的 README 文件中包含一个部分，讨论了此分配器与其他在 <crates.io> 上存在的分配器之间的关系。 ⚠

TL;DR

• ✅ no_std 分配器，具有测试覆盖率
• ✅ 使用静态内存作为后端存储（没有分页/页面表操作）
• ✅ 分配策略是 next-fit 和 best-fit 的组合
• ✅ 性能合理，代码复杂度低
• ✅ 兼容 const（无需运行时 init()）
• ✅ 在堆大小仅为几十兆字节的情况下效率高
• ✅ 用户友好的 API

内部和低级别的ChunkAllocator可以用作#[global_allocator]，与同步包装类型GlobalChunkAllocator一起使用。两者都可以与allocator_api功能一起使用。后者使得Rust标准库的多种类型可以使用，例如Vec::new_in或BTreeMap::new_in。这主要用于测试，但也可能使其他有趣的使用场景成为可能。

重点是const兼容性。分配器和支持内存可以在编译时初始化，无需运行时init()调用或类似操作。这意味着如果编译器接受它，那么分配在运行时也会工作。然而，您也可以在运行时创建分配器对象。

内部和低级别的ChunkAllocator是一个块分配器，也称为固定大小块分配器。它结合了next-fit和best-fit策略。它试图使用最小的间隙来满足分配请求以防止碎片化，但这没有保证。每次分配都是在低分配时间和防止碎片化之间的权衡。默认块大小为256字节，但可以通过编译时const generic来更改。拥有固定大小的块分配器可以通过位图实现简单的簿记算法，但代价是小型分配，如64字节，将至少占用所选块大小的一个块。

这个项目源于我的硕士论文项目。由于我最初在创建这个（我的第一个分配器）时遇到了很多困难，所以我将其外包出去以提高可测试性，并与他人分享我的知识和发现，希望有人能从中学习到任何东西。

最小代码示例

#![feature(const_mut_refs)]
#![feature(allocator_api)]

use simple_chunk_allocator::{heap, heap_bitmap, GlobalChunkAllocator, PageAligned};

// The macros help to get a correctly sized arrays types.
// I page-align them for better caching and to improve the availability of
// page-aligned addresses.

/// Backing storage for heap (1Mib). (read+write) static memory in final executable.
///
/// heap!: first argument is chunk amount, second argument is size of each chunk.
///        If no arguments are provided it falls back to defaults.
///        Example: `heap!(chunks=16, chunksize=256)`.
static mut HEAP: PageAligned<[u8; 1048576]> = heap!();
/// Backing storage for heap bookkeeping bitmap. (read+write) static memory in final executable.
///
/// heap_bitmap!: first argument is amount of chunks.
///               If no argument is provided it falls back to a default.
///               Example: `heap_bitmap!(chunks=16)`.
static mut HEAP_BITMAP: PageAligned<[u8; 512]> = heap_bitmap!();

// please make sure that the backing memory is at least CHUNK_SIZE aligned; better page-aligned
#[global_allocator]
static ALLOCATOR: GlobalChunkAllocator =
    unsafe { GlobalChunkAllocator::new(HEAP.deref_mut_const(), HEAP_BITMAP.deref_mut_const()) };

fn main() {
    // at this point, the allocator already got used a bit by the Rust runtime that executes
    // before main() gets called. This is not the case if a `no_std` binary gets produced.
    let old_usage = ALLOCATOR.usage();
    let mut vec = Vec::new();
    vec.push(1);
    vec.push(2);
    vec.push(3);
    assert!(ALLOCATOR.usage() > old_usage);

    // use "allocator_api"-feature. You can use this if "ALLOCATOR" is not registered as
    // the global allocator. Otherwise, it is already the default.
    let _boxed = Box::new_in([1, 2, 3], ALLOCATOR.allocator_api_glue());
}

另一个代码示例（独立Linux二进制文件）

这是摘录。代码可以在GitHub仓库的freestanding-linux-example中找到。

static mut HEAP: PageAligned<[u8; 256]> = heap!(chunks = 16, chunksize = 16);
static mut HEAP_BITMAP: PageAligned<[u8; 2]> = heap_bitmap!(chunks = 16);

// please make sure that the backing memory is at least CHUNK_SIZE aligned; better page-aligned
#[global_allocator]
static ALLOCATOR: GlobalChunkAllocator<16> =
    unsafe { GlobalChunkAllocator::<16>::new(HEAP.deref_mut_const(), HEAP_BITMAP.deref_mut_const()) };

/// Referenced as entry by linker argument. Entry into the code.
#[no_mangle]
fn start() -> ! {
    write!(StdoutWriter, "Hello :)\n").unwrap();
    let mut vec = Vec::new();
    (0..10).for_each(|x| vec.push(x));
    write!(StdoutWriter, "vec: {:#?}\n", vec).unwrap();
    exit();
}

MSRV

因为这个crate只与Rust的nightly版本一起构建，因为它使用了许多仅限nightly的功能。我使用版本1.61.0-nightly（2022-03-05）开发它。较老的nightly版本可能也可以工作。到目前为止，还没有稳定版本的Rust编译器可以编译这个。

性能

默认CHUNK_SIZE为256字节。这是性能和有效内存使用之间的权衡。

我在Intel i7-1165G7 CPU和160MB堆上以发布模式执行了我的示例bench，以获得以下结果。我使用RUSTFLAGS="-C target-cpu=native" cargo run --release --example bench以获得最大性能执行基准测试。基准测试模拟了单线程程序中堆的重度使用，许多随机分配和释放。当堆接近100%时，基准测试停止。分配的大小在对齐方面有所不同。下面的表格显示了该基准测试的结果，单位是时钟周期。

信息：自从我测量了这些值以来，我对基准做了一些轻微的修改。

由于每个运行都会受到一些随机性的影响，结果会有轻微的波动。可以看到，随着块数的增加，性能会变慢。增加块大小会减小账本位图的大小，从而加速查找。然而，当只需要非常小的分配时，较小的块大小会占用更少的堆空间。

注意，当堆使用频率较低且没有完全运行时，性能将比上述列出的更好。

与其他分配器的区别

链表分配器

在crates.io上，我找到了链表分配器是唯一另一个适合且维护良好的通用无标准分配器。

我的块分配器的优点

• 中位数分配时间快得多
• 平均分配时间快得多[只有当堆接近满时才适用]
• 在某些情况下优化realloc（在某些情况下几乎是无操作）
• 使用相对简单的算法（但需要专门的堆和账本支持存储）

链表分配器的优点

• 更好的内存利用率（更少碎片化）
• 在大多数测试运行中最坏情况的分配时间更好
• 平均分配时间更好[只有当堆接近满时才适用]
• 只需要一块内存，并使用后备内存本身管理堆

基准比较：我运行了$ cargo run --example bench --release，与两个分配器进行了比较，并获得了以下结果。基准执行不同大小和对齐的随机分配，并释放一些较旧的分配。随着时间的推移，堆会变满，这就是为什么成功分配的数量与尝试分配的数量之间的差异更高的原因。

运行时间：1秒（大部分时间有很多堆可用）

RESULTS OF BENCHMARK: Chunk Allocator
     53360 allocations,  16211 successful_allocations,  37149 deallocations
    median=   878 ticks, average=  1037 ticks, min=   158 ticks, max= 7178941 ticks

RESULTS OF BENCHMARK: Linked List Allocator
     31627 allocations,   9374 successful_allocations,  22253 deallocations
    median= 18582 ticks, average= 44524 ticks, min=    71 ticks, max=44126026 ticks

我们看到，只要大部分分配都是在有很多空间可用的堆上进行的，块分配器在中位数和平均性能上更快。

运行时间：10秒（大部分时间堆几乎满）

RESULTS OF BENCHMARK: Chunk Allocator
     74909 allocations,  23753 successful_allocations,  51156 deallocations
    median=   961 ticks, average=273362 ticks, min=   167 ticks, max=53330953 ticks

RESULTS OF BENCHMARK: Linked List Allocator
     81884 allocations,  24792 successful_allocations,  57092 deallocations
    median=100196 ticks, average=179495 ticks, min=    69 ticks, max=43937820 ticks

我们看到，当堆几乎满时，块分配器的中位数性能更快，但最坏情况的分配时间更差。当链表分配器接近满时，它在平均性能上表现更好（但在中位数上不一定）。