Rulloc

Rulloc (Rust 分配器) 是一个用 Rust 编写的通用内存分配器。它实现了 std::alloc::Allocator 和 std::alloc::GlobalAlloc 特性。所有内存都通过 Linux 上的 mmap 系统调用和 Windows 上的 VirtualAlloc 调用从内核请求。您可以按照以下方式运行示例

cargo run --example standalone
cargo run --example global
cargo run --example buckets
cargo run --example aligned

运行测试

cargo test

使用 Miri 运行

cargo miri test
cargo miri run --example standalone
cargo miri run --example buckets
cargo miri run --example aligned

全局分配器示例在 Miri 中无法工作，请参阅 examples/global.rs。

实现

我开始这个项目是为了学习，我知道确保你理解某件事的最佳方式就是向别人解释。因此，如果你对内存分配器的工作原理感兴趣，代码库中有很多文档和 ASCII 图表。首先阅读 src/allocator.rs 以获得快速概述，然后你会通过 内部文档链接 被重定向到其余文件。

块

如果你不想滚动数百行代码，这是一个内存块的外观

+----------------------------+
| pointer to next block      |   <------+
+----------------------------+          |
| pointer to prev block      |          |
+----------------------------+          |
| pointer to block region    |          |
+----------------------------+          | Block Header
| block size                 |          |
+----------------------------+          |
| is free flag (1 byte)      |          |
+----------------------------+          |
| padding (struct alignment) |   <------+
+----------------------------+
|       Block content        |   <------+
|            ...             |          |
|            ...             |          | Addressable content
|            ...             |          |
|            ...             |   <------+
+----------------------------+

区域

所有块都属于一个内存区域，这是一个可以存储多个页面的连续内存块。换句话说，每个区域的大小是当前平台虚拟内存页面大小的倍数，每个区域包含一个块的链表

+--------+--------------------------------------------------+
|        | +-------+    +-------+    +-------+    +-------+ |
| Region | | Block | -> | Block | -> | Block | -> | Block | |
|        | +-------+    +-------+    +-------+    +-------+ |
+--------+--------------------------------------------------+

桶

分配器可以在编译时配置为多个不同大小的分配桶，以减少碎片。每个桶存储一个内存区域链表和一个空闲列表，基本上是一个仅包含空闲块的链表

                   Next free block in the free list            Next free block
               +--------------------------------------+   +-----------------------+
               |                                      |   |                       |
+--------+-----|------------------+      +--------+---|---|-----------------------|-----+
|        | +---|---+    +-------+ |      |        | +-|---|-+    +-------+    +---|---+ |
| Region | | Free  | -> | Block | | ---> | Region | | Free  | -> | Block | -> | Free  | |
|        | +-------+    +-------+ |      |        | +-------+    +-------+    +-------+ |
+--------+------------------------+      ---------+-------------------------------------+

分配器

最后，将所有这些放在一起，分配器是一组桶的数组

                                 Next Free Block                    Next Free Block
                      +------------------------------------+   +-----------------------+
                      |                                    |   |                       |
     +--------+-------|----------------+      +--------+---|---|-----------------------|-----+
     |        | +-----|-+    +-------+ |      |        | +-|---|-+    +-------+    +---|---+ |
0 -> | Region | | Free  | -> | Block | | ---> | Region | | Free  | -> | Block | -> | Free  | |
     |        | +-------+    +-------+ |      |        | +-------+    +-------+    +-------+ |
     +--------+------------------------+      +--------+-------------------------------------+

                                              Next Free Block
                                 +----------------------------------------+
                                 |                                        |
     +--------+------------------|-----+      +--------+------------------|------------------+
     |        | +-------+    +---|---+ |      |        | +-------+    +---|---+    +-------+ |
1 -> | Region | | Block | -> | Free  | | ---> | Region | | Block | -> | Free  | -> | Block | |
     |        | +-------+    +-------+ |      |        | +-------+    +-------+    +-------+ |
     +--------+------------------------+      +--------+-------------------------------------+

..............................................................................................

                                        Next Free Block
                                 +---------------------------+
                                 |                           |
     +--------+------------------|-----+      +--------+-----|-------------------------------+
     |        | +-------+    +---|---+ |      |        | +---|---+    +-------+    +-------+ |
N -> | Region | | Block | -> | Free  | | ---> | Region | | Free  | -> | Block | -> | Block | |
     |        | +-------+    +-------+ |      |        | +-------+    +-------+    +-------+ |
     +--------+------------------------+      +--------+-------------------------------------+

所有这些数据结构都比那个复杂一些，但你需要阅读源代码以了解更多细节。

待办事项

• 多线程。目前分配器后面有一个互斥锁，这不是处理多个线程的最有效方式。我们还需要更好的测试，也许可以使用loom？参见src/allocator.rs以获取优化想法和底层细节。这里是一个简要总结

  1. 每个桶一个互斥锁，而不是一个全局互斥锁。
  2. 固定数量的分配器和线程之间的负载分配。
  3. 每个线程一个分配器。

• 减少分配和释放时的系统调用次数。分配器只从操作系统请求足够的内存来存储用户内容和头部，但这可能导致多次调用mmap（或其他平台的等效函数）。为了避免这种情况，我们可以找出通常需要请求多少额外的页面，例如，如果我们需要1页来存储我们的东西加上用户的东西，我们可以请求10页，以避免进一步的分配执行内核代码。

• 研究是否可以减少我们头部的尺寸。在64位机器上，每个块头的大小是40字节，每个区域头的大小是48字节。区域头并不那么重要，但块头对于小分配非常重要。

• 内存对齐优化。当前实现将填充添加到块内容的开始，以便对齐指针。这只在对齐约束大于当前机器的指针大小时执行，对于小对齐（例如16或32）没有问题，但它可能浪费过多的空间用于512及以上的对齐。这个问题的一个可能的起点是，内存区域已经对齐到页面大小（通常是4096），因此我们可以利用这一点。

• 免费块搜索算法优化。我们确实有一个空闲列表，这使得找到空闲块更容易，我们还有固定大小的桶，所以这并不是特别未优化。除非是不同大小的连续大分配。每当收到一个我们无法放入任何桶的分配请求，因为它太大时，我们使用动态桶，这只是一个不关心大小的桶的名字，可以存储1KB混合1GB的块。对于这个桶，至少我们可以实现一个堆来搜索空闲块，或者也许只是存储指向最大块的指针，这样我们就可以立即知道是否需要打扰内核。

• 当mmap或VirtualAlloc失败时我们应该做什么？恐慌？分配器的用户对失败一无所知，因为std::alloc::Allocator没有释放的返回类型。恐慌似乎不是最佳选择，因为程序可以继续正常运行，但我们应该如何以及何时将内存区域返回给内核呢？

• 当std::alloc::Allocator变得稳定时，删除std::alloc::GlobalAlloc实现。