Linux 动态内存分配

动态内存分配器

进程中名为 heap 的 VM area 就是由动态内存分配器（dynamic memory allocator）来维护的。Heap 会向高地址（向上）增长。对每个进程，内核维护着一个名为 brk 的变量，该变量指向 Heap 的顶部，如下图所示：

Allocator 将 Heap 视为一组不同大小的 block 组成的集合来维护。这里 block 和 chunk 的概念是等价的，该 block 要么是已分配的（allocated），要么是空闲的（free）。

Each block is a contiguous chunk of virtual memory that is either allocated or free.

Allocator 可以分为显式分配器（explicit allocator）和隐式分配器（implicit allocator）。

• 显示分配器要求应用显示地释放任何已分配的块，分配也需要手动分配。例如 C 中的 malloc 和 free，C++ 中的 new 和 delete；
• 隐式分配器又被称为垃圾收集（garbage collection），例如 Java、C#。

malloc 和 free

$32$ 位系统中，malloc 返回的地址总是 $8$ 的倍数，即 malloc 返回的地址的最低三位总是 $0$，亦即 malloc 分配的 block 至少占据 $8$ 的倍数个 byte；而 $64$ 位系统中，malloc 返回的地址总是 $16$ 的倍数。

即 $32$ 系统中，malloc 分配内存是 $8$ 字节对齐的；$64$ 位系统中，malloc 分配内存是 $16$ 字节对齐的。

Allocator 的设计要求和目标

显式分配器必须在一些相当严格的约束条件下也能正常工作：

• 处理任意请求序列：不能假设所有分配都有相匹配的释放请求等；
• 立即响应请求：不允许分配器为了提高性能重新排列或者缓冲请求；
• 只使用 Heap
• 对齐（aligning） block：$32$ 位系统 $8$ 字节对齐，$64$ 位系统 $16$ 字节对齐；
• 不允许修改已分配的 block：一旦 block 被分配就不允许修改或者移动，除非被释放（free）；

同时我们希望设计的分配器能最大化内存利用率并最大化吞吐率（即每秒能完成的分配或者释放请求数量）。

碎片（Fragmentation）

碎片分为内部碎片（internal fragmentation）和外部碎片（external fragmentation）。

内部碎片即要分配的 $size$ 只占分配的 $block size$ 的一部分的情况，例如分配一个 $2$ 字节的空间，由于要求至少 $8$ 字节对齐，那么必然有一部分用不到的空间为了满足对齐要求也被分配了出来。

外部碎片即空闲的空间总和大于要分配的 $size$，但是没有一个单独的 $block$ 的 $size$ 大到可以处理该分配请求。

分配器实现

分配器实现过程中，我们需要考虑以下问题：

• 空闲 block 组织：如何记录空闲 block？
• 放置：如何选择一个合适的空闲 block来放置一个新分配的 block？
• 分割：将一个新分配的块放置到某个空闲 block 之后，如何处理空闲 block 的剩余部分？
• 合并：如何处理一个刚刚释放的 block（例如前或者后也有 free 的 block 呢）？

隐式空闲链表

一般来说，allocator 需要一些数据结构，从而区分 block 的边界并区分 allocated block 和 free block。大多数的 allocator 将信息嵌入这个块本身，就像 elf 文件有一个 elf header 一样，block 中也会有一个 header，存储了该 block 是否空闲，占据的空间 size 等信息。

假设 malloc 返回的指针是 p，由于 header 占据了 $32$ 个字节，header 本身是 uint32_t 类型的。那么 block 的起始地址 start：

uint64_t start = (uint64_t)p - 4; // block 的起始地址
uint32_t header_val = *((uint32_t *)start); // header 的值
int allocated = header_val & 0x1; // 为 1 表示已分配，为 0 表示块仍然是空闲的
int size = header_val & 0xfffffffe; // 即将 header_val 的最后一位置 0

这种结构被称为隐式空闲链表，我们可以利用 block 的 header_val 中的 size 找到下一个块：next = (uint64_t)start + size;

隐式空闲链表的主要优点是简单，缺点则是：任何操作都可能需要遍历 heap 中的所有 block，时间复杂度是 $O(n)$ 的，此外还有个缺点是可能造成内部碎片。