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 等专用接口。申请 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 会替调用者完成这类检查，但自算总字节数时仍要显式处理。

realloc 也不要直接覆盖原指针：

void *new_buffer = realloc(buffer, new_size);
if (new_buffer == NULL && new_size != 0) {
    /* buffer 仍然有效 */
    handle_allocation_failure();
} else {
    buffer = new_buffer;
}

2. 一个诚实的最小模型：固定块内存池

直接写一个缩小版 malloc 很容易把对齐、分割、合并和错误路径都写错。固定大小内存池更适合第一次动手：初始化时准备若干等大的块，用单链表串起空闲块，分配和释放都只改链表头。

#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) {
    uintptr_t begin = (uintptr_t)&pool->blocks[0];
    uintptr_t end = (uintptr_t)&pool->blocks[BLOCK_COUNT];
    uintptr_t address = (uintptr_t)pointer;

    return address >= begin
        && address < end
        && (address - begin) % sizeof(block_t) == 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;
        }
    }

    puts(pool_alloc(&pool) != NULL ? "reused" : "failed");
    return 0;
}

编译运行：

bash

cc -std=c17 -O2 -Wall -Wextra pool.c
./a.out
# reused

这个例子保证每块至少有 64 字节，并通过 max_align_t 让块具备基本类型所需的对齐。它仍有明确边界：

容量与块大小固定；
不是线程安全的；
不检测重复释放；
pool_free 只接受 pool_alloc 原样返回的地址；
它不向操作系统申请或归还页面。

这些限制不是脚注，而是接口的一部分。一个专用对象池若能接受这些约束，路径会非常短；若需要任意大小、并发和错误防护，复杂度会迅速接近通用分配器。

3. 仓库改收可变尺寸领料单

固定块池像每个格子尺寸完全相同的货架，快，却会浪费不合尺寸的空间。真实领料单大小不同，分配器就要切分大空闲块、回收相邻空洞，并在速度、碎片和 metadata 之间取舍。

假设分配器持有一段 128 字节的空闲区域，申请 40 字节时，可以把它分成“已分配 40”与“剩余空闲 88”。实际还要考虑块头、对齐和最小可分割尺寸：

text

初始：
[                 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 类缓存则通过复用已经构造过的对象降低初始化成本，并改善小对象布局。

8. 失败、安全与可观测性

分配失败不是只有“物理内存耗尽”一种原因。地址空间限制、进程配额、映射数量限制和过大的连续请求都可能返回空指针。Linux 的内存过量承诺还意味着“分配成功”不保证未来每个页面都能无条件使用。可靠程序必须明确失败策略。

堆错误通常在损坏发生后才暴露：

越界写破坏相邻对象或分配器元数据；
use-after-free 读到已被复用的新对象；
double free 把同一块重复放入空闲结构；
整数溢出导致分配过小；
不同分配器之间交叉分配和释放。

AddressSanitizer、Valgrind 类工具和分配器诊断选项可以把错误拉近到发生位置。生产排查则应同时观察分配速率、存活对象、峰值、大小分布、线程缓存、缺页和 RSS，避免把所有增长都笼统称作“泄漏”。

9. 什么时候值得自定义

自定义分配策略通常要有清晰的生命周期或尺寸规律：

一批对象同时创建、同时销毁，可以使用 arena/region，一次释放整个区域；
对象尺寸固定且上限明确，可以使用固定块池；
实时路径不能接受不可预测的搜索和系统调用，可以预分配；
高频临时对象可以使用栈式或 bump allocator。

如果对象任意释放、跨线程传递、尺寸变化大，还要求与通用库互操作，那么成熟的通用分配器往往更安全。自定义方案还要定义对齐、失败、线程安全、所有权和诊断接口；只写出一个空闲链表远远不够。

10. 小结

动态分配器做的是一组彼此牵制的选择：

分割提高利用率，却增加元数据与合并工作；
大小类别缩短查找，却带来内部碎片；
arena 与线程缓存降低竞争，却可能提高内存保留量；
批量向操作系统取内存减少系统调用，却使 free 与 RSS 的变化不同步。

固定块池让最小机制变得可见，通用 malloc 则必须同时处理任意大小、并发、碎片和错误防护。理解这条差距，比背某个实现的阈值更有用。

下一章进入死锁。分配器内部也要获取多种锁；一旦加锁顺序不一致，再精巧的空闲结构也可能停在原地。

第1章逻辑

第2章集合论

第3章证明方法

第4章递归、归纳与递推

第5章关系与函数

第6章组合数学

第7章图论

第8章概率与统计

第9章数论

第10章线性代数

第11章微积分与优化

第12章信息论与数值计算