基本分配器

此包包含一个完全用 Rust 编写的自研内存分配器。它很简单，主要用于教学目的。

此 crate 有着大量的注释和文档。有关详细信息，请参阅 文档 或 代码本身。

开发

可以在 OSX 或 Linux 机器上本地进行开发，使用标准的 Rust 框架。此外，可以使用 Docker 在 Linux 上进行。

$ # Develop using the code mounted
$ docker build --target dev -t basicallocdev . && docker run -v `pwd`:/usr/src/basicalloc -it basicallocdev
[...]
root@0123456789ab:/usr/src/basicalloc# cargo test
[...]

lib.rs:

一个简单的内存分配器，用于教学目的。

此模块主要为了便于阅读代码而编写。封装的分配器可以作为 Rust 程序中的内存分配器使用。

用法

use basic_allocator::UnixAllocator;

#[global_allocator]
static ALLOCATOR: UnixAllocator = UnixAllocator::new();
fn main() {
    println!("It works!")
}

另请参阅 core::alloc::GlobalAlloc。

主要组件

此模块有几个部分。

BlockList

BlockList 是一个链表，包含未返回给操作系统的 已释放 内存，分配器可以重用这些内存。

空闲块以头部开始，之后是未使用的内存。头部为 16 字节，包含指向下一个块的指针和整个块的大小。

RawAlloc

RawAlloc 是一个单线程、非线程安全的堆和已释放内存管理器，实现了 core::alloc::GlobalAlloc。然而，因为它不是线程安全的，所以不能用作全局分配器。

UnixAllocator

UnixAllocator 使用自旋锁包装 RawAlloc 以使其线程安全，从而可以将其用作全局分配器。它还将 RawAlloc 与特定于 Unix 的 UnixHeapGrower 结合起来，以将虚拟内存页作为其底层基础来执行这些调用。

HeapGrower

HeapGrower 是一个简单的 trait 接口，旨在抽象化对操作系统进行堆扩展的调用。

实现

空闲内存以链表形式维护。分配器有一个指向第一个块的指针，每个块从带有指向下一个块和当前块大小的头开始。块是有序的，这样就可以轻松实现合并。

分配

当调用 RawAlloc 以分配 size 字节时

1. 遍历 BlockList，如果找到任何足够大的空闲块，则使用它。如果找到的块正好是所需的大小，则从链表中“弹出”，并返回作为空闲内存的块；否则，将块的最后一个 size 字节作为空闲内存返回，并根据需要调整块的头。
2. 如果在列表中没有找到合适的块，则调用适当的 HeapGrower 实例来“扩展堆”。对于 UnixHeapGrower，这意味着从操作系统请求一个或多个虚拟内存页面。返回前 size 字节，并将页的其余部分添加到 BlockList。

释放

当调用 RawAlloc 以释放指向 ptr 的 size 字节时

1. 遍历 BlockList 以找到 ptr 在列表中应保持排序的位置。
2. ptr 被插入，并尝试将其与前面的和后面的块合并。只有当涉及的块相邻时，每个尝试才成功。

可能的扩展

这是一个设计上非常简单的分配器。在功能和性能方面，它有很多改进的方式

1. 它可以在完成页面操作后将其返回给操作系统
2. 它不需要16字节对齐
3. 它可以有线程安全的链表实现，从而消除对自旋锁的需求
4. 它可以实现 realloc，这样容器在可能的情况下可以在原地调整大小

... 可能还有更多。除了这些基本功能之外，还有许多在其他分配器中的优化，使它们更高效。