11.2 动态内存分配器
malloc(24) 只申请二十四个 byte，分配器却不能随便返回一段空间：地址要满足对齐，多个线程可能同时申请，释放后的空洞要重新利用，大块区域还要在合适时机归还操作系统。
11.1 锁是怎样工作的会出现在这些路径里，但分配器不是“一张空闲链表加一把全局锁”。现代实现会按大小分类、批量向操作系统取内存，并用 thread cache 或多个 arena 减少共享热点。这一课先实现一个可推演的小型固定块池，再说明真实分配器为什么更复杂。
1. 先弄清接口契约
在 C 中，动态分配至少涉及四个常用接口：
| 接口 | 作用 | 容易忽略的点 |
|---|---|---|
malloc(n) | 分配至少 n 字节 | 内容未初始化 |
calloc(count, size) | 分配数组并把所有位清零 | 需要处理乘法溢出 |
realloc(p, n) | 调整一块已有分配 | 正尺寸请求可能移动，失败时原块仍有效 |
free(p) | 结束对象的已分配生命周期 | free(NULL) 无操作 |
malloc 返回的地址满足具有基本对齐要求的对象；需要更强的对齐时，应使用 aligned_alloc 等专用接口，并满足支持的 alignment 和尺寸为 alignment 整数倍等约定。calloc 清零的是所有位，并不保证每种 C 实现的 null pointer 或浮点零都用全零位表示。申请 0 字节可能得到空指针，也可能得到一个可传给 free 的非空指针，程序不应解引用它。
传给 free 的非空指针必须原样来自兼容的分配函数，并且尚未释放；不能传入指向块内部的地址。释放后继续读写是 use-after-free；再次释放是 double free。两者都不是“偶尔出错”，而是未定义行为。
数组大小要先防溢出
下面的检查必须发生在乘法之前：
#include <stdint.h>
#include <stdlib.h>
void *allocate_array(size_t count, size_t element_size) {
if (count != 0 && element_size > SIZE_MAX / count) {
return NULL;
}
return malloc(count * element_size);
}否则一个很大的 count * element_size 可能回绕成较小的整数，随后按原来的元素个数写入就会越界。calloc 接收两个独立参数，可以检查乘法溢出并报告失败；预先算出已经回绕的总字节数再传给 malloc，丢失的信息就找不回来了。
realloc 不要直接覆盖原指针；零尺寸单独 free，避免 C 版本与实现差异（C23 中 realloc(p, 0) 为 UB）。下面是包含 stdlib.h 后放在函数内的片段，buffer 为有效分配或 NULL，失败处理函数由应用提供：
if (new_size == 0) {
free(buffer);
buffer = NULL;
} else {
void *new_buffer = realloc(buffer, new_size);
if (new_buffer == NULL) {
/* The old buffer remains valid. */
handle_allocation_failure();
} else {
buffer = new_buffer;
}
}2. 最小模型：固定块字节池
直接写一个缩小版 malloc 很容易把对齐、分割、合并和错误路径都写错。固定大小内存池更适合第一次动手：初始化时准备若干等大的块，用单链表串起空闲块，分配只取链表头；本例释放前线性查找合法块地址，再更新链表。保存为 pool.c。
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>
enum { BLOCK_SIZE = 64, BLOCK_COUNT = 128 };
typedef union block {
max_align_t alignment;
unsigned char bytes[BLOCK_SIZE];
union block *next;
} block_t;
typedef struct {
block_t blocks[BLOCK_COUNT];
block_t *free_head;
} pool_t;
_Static_assert(sizeof(block_t) >= BLOCK_SIZE,
"block is smaller than its payload");
static void pool_init(pool_t *pool) {
for (size_t i = 0; i + 1 < BLOCK_COUNT; ++i) {
pool->blocks[i].next = &pool->blocks[i + 1];
}
pool->blocks[BLOCK_COUNT - 1].next = NULL;
pool->free_head = &pool->blocks[0];
}
static void *pool_alloc(pool_t *pool) {
block_t *block = pool->free_head;
if (block == NULL) {
return NULL;
}
pool->free_head = block->next;
return (void *)block;
}
static int pool_owns(const pool_t *pool, const void *pointer) {
for (size_t i = 0; i < BLOCK_COUNT; ++i) {
if (pointer == (const void *)&pool->blocks[i]) {
return 1;
}
}
return 0;
}
static int pool_free(pool_t *pool, void *pointer) {
if (pointer == NULL) {
return 1;
}
if (!pool_owns(pool, pointer)) {
return 0;
}
block_t *block = pointer;
block->next = pool->free_head;
pool->free_head = block;
return 1;
}
int main(void) {
pool_t pool;
void *items[BLOCK_COUNT];
pool_init(&pool);
for (size_t i = 0; i < BLOCK_COUNT; ++i) {
items[i] = pool_alloc(&pool);
if (items[i] == NULL) {
return 1;
}
memset(items[i], (int)i, BLOCK_SIZE);
}
if (pool_alloc(&pool) != NULL) {
return 2;
}
for (size_t i = 0; i < BLOCK_COUNT; ++i) {
if (!pool_free(&pool, items[i])) {
return 3;
}
}
void *reused = pool_alloc(&pool);
puts(reused != NULL ? "reused" : "failed");
return reused != NULL ? 0 : 4;
}编译运行：
cc -std=c17 -O2 -Wall -Wextra -Werror pool.c
./a.out
# reused每块至少有 64 字节，并通过 max_align_t 获得基本对齐。池本身已有声明类型，所以这里提供的是可通过字节访问或 memcpy 使用的存储，不能只因地址对齐就把结果转成任意 T* 并读写。若要存放特定类型，可把该类型明确放入 union；通用对象存储则要另行满足 C 的 effective-type 规则。它仍有明确边界：
- 容量与块大小固定，使用期间 pool 地址不得改变或被复制；
- 不是线程安全的；
- 不检测重复释放或旧指针再次归还，调用者必须保证一个分配只释放一次；
pool_free只接受pool_alloc原样返回的地址；- 它不向操作系统申请或归还页面。
成员检查用指针相等比较，避免假设 uintptr_t 数值排序等同于对象布局。代价是释放的校验需要 O(BLOCK_COUNT) 次比较，链表更新本身仍是 O(1)。这些限制属于接口。一个专用对象池若能接受这些约束，路径会非常短；若需要任意大小、并发和错误防护，复杂度会迅速接近通用分配器。
3. 从固定块扩展到可变尺寸
固定块池很快，却会为较小请求浪费空间，也无法服务超过块大小的请求。当分配尺寸可变时，分配器就要切分大空闲块、合并相邻空洞，并在速度、碎片和 metadata 之间取舍。
假设分配器持有一段 128 字节的空闲区域，申请 40 字节时，可以把它分成“已分配 40”与“剩余空闲 88”。实际还要考虑块头、对齐和最小可分割尺寸：
初始：
[ free 128 ]
分割后：
[ header | used 40 ][ header | free remainder ]
中间块释放后：
[ used ][ free A ][ used ][ free B ]
相邻空闲块释放并合并：
[ used ][ larger free ]典型设计会为块保存大小和状态，并把空闲块组织成链表、树或按大小划分的 bin。分配时需要选择候选块：
- first fit 找到第一个足够大的块即停，最坏仍可能扫描整个空闲表，布局受顺序影响；
- best fit 寻找最接近的块，可能减少单次剩余，却增加搜索成本；
- size class 把大小映射到固定档位，查找快，但会舍入请求。
释放时，分配器尝试与相邻空闲块合并。边界标记可以帮助从块尾找到前一块，不过元数据越丰富，占用空间和攻击面也越大。
4. 两种碎片不是同一个问题
内部碎片发生在已分配块内部。例如申请 33 字节，大小类别给出 48 字节，其中未被应用使用的部分仍不能分配给别人。对齐、大小舍入与部分元数据都会增加这类开销。
外部碎片发生在已分配块之间。空闲字节总量可能足够，但被切成互不相邻的小洞，无法满足较大的连续请求。
通用堆通常不能随意移动活跃对象，因为 C 指针可能散落在程序各处。垃圾回收运行时若能更新引用，则有机会压缩对象，这是另一套内存模型。
判断碎片不能只看进程虚拟地址空间。还要区分：
- 应用请求的字节数；
- 分配器保留但当前未使用的字节；
- 已映射的虚拟内存；
- 当前驻留在物理内存中的页面。
“释放了对象但 RSS 没立刻下降”不等于内存泄漏。空闲块可能留在分配器中供后续复用，页面也可能因其中仍有活跃对象而无法整体归还。
5. 分配器与操作系统的边界
分配器通常成批向操作系统取得虚拟内存，再切成应用所需的小块。在类 Unix 系统上，底层来源可能包括：
- 调整 program break 的
brk路径； - 建立独立虚拟映射的
mmap路径； - 已经取得的大区域中尚未使用的页面。
大请求和小请求使用哪条路径、达到什么阈值才归还页面，都是实现策略，可能随版本、配置和运行时状态变化。应用不应假设“每次 malloc 都会系统调用”或“每次 free 都会把内存还给内核”。
第 6 章介绍的按需分页也在这里发挥作用：取得一段虚拟地址并不代表对应物理页已经全部进入驻留集。首次触碰页面时，才可能发生缺页并建立映射。
6. 多线程伸缩：减少共享，而不只是换一把快锁
若所有线程都经过同一张空闲链表和同一把锁，分配热点会被串行化。工程实现常组合以下策略：
多个 arena 或 heap 区域。 不同线程可以在不同区域分配，减少一把全局锁上的竞争。arena 数量与线程或 CPU 并非简单的一一对应，具体策略属于实现细节。
线程缓存。 常用小块暂存在当前线程附近，使许多分配与释放不触碰共享结构。代价是内存分散在线程缓存中，跨线程释放和线程退出还要处理转移或回收。
大小类别与批量搬运。 同尺寸对象使用相同空闲结构，线程缓存一次从中心结构取回一批，再逐个交给应用。这用更多暂存内存换取较少的同步。
每 CPU 缓存。 某些运行时或内核分配器把热点结构放在 CPU 本地，减少跨核心写共享。线程迁移、NUMA 距离与回收平衡随之成为新问题。
这些设计解释了一个常见现象：提升并发分配吞吐后，内存峰值可能上升。分片越彻底，空闲空间越难立即被其他分片利用。
7. 内核对象与用户堆不要混为一谈
Linux 内核常用伙伴系统管理较大、按 2 的幂组织的页块，再由 slab 类分配器复用固定类型或固定尺寸的小对象。用户空间 malloc 管理的是进程地址空间里的对象，两者层次不同。
“伙伴系统碎片少”也需要限定：它便于合并同阶伙伴并快速取得页块，但向上取整会产生内部浪费，长期运行仍可能遇到高阶页块不足。slab 类缓存复用固定尺寸对象并改善布局；支持并配置 constructor 时可保留部分初始化状态，但每次使用所需的业务字段初始化仍由对应接口保证。
8. 失败、安全与可观测性
分配失败不是只有“物理内存耗尽”一种原因。地址空间限制、进程配额、映射数量限制和过大的连续请求都可能返回空指针。Linux 的内存过量承诺还意味着“分配成功”不保证未来每个页面都能无条件使用。可靠程序必须明确失败策略。
堆错误通常在损坏发生后才暴露：
- 越界写破坏相邻对象或分配器元数据；
- use-after-free 读到已被复用的新对象；
- double free 把同一块重复放入空闲结构；
- 整数溢出导致分配过小；
- 不同分配器之间交叉分配和释放。
AddressSanitizer、Valgrind 类工具和分配器诊断选项可以把错误拉近到发生位置。生产排查则应同时观察分配速率、存活对象、峰值、大小分布、线程缓存、缺页和 RSS，避免把所有增长都笼统称作“泄漏”。
9. 什么时候值得自定义
自定义分配策略通常要有清晰的生命周期或尺寸规律：
- 一批对象同时创建、同时销毁，可以使用 arena/region，一次释放整个区域；
- 对象尺寸固定且上限明确，可以使用固定块池；
- 实时路径不能接受不可预测的搜索和系统调用，可以预分配；
- 高频临时对象可以使用栈式或 bump allocator。
如果对象任意释放、跨线程传递、尺寸变化大，还要求与通用库互操作，那么成熟的通用分配器往往更安全。自定义方案还要定义对齐、失败、线程安全、所有权和诊断接口；只写出一个空闲链表远远不够。
10. 小结
动态分配器做的是一组彼此牵制的选择：
- 分割提高利用率，却增加元数据与合并工作；
- 大小类别缩短查找，却带来内部碎片；
- arena 与线程缓存降低竞争，却可能提高内存保留量；
- 批量向操作系统取内存减少系统调用，却使
free与 RSS 的变化不同步。
固定块池让最小机制变得可见，通用 malloc 则必须同时处理任意大小、并发、碎片和错误防护。理解这条差距，比背某个实现的阈值更有用。
下一章进入死锁。分配器内部也要获取多种锁；一旦加锁顺序不一致，再精巧的空闲结构也可能停在原地。