glibc 内存分配器原理

内存管理是 C 程序员日常编码中最常见的技术点，能否用得 glibc 内置的内存管理函数，是衡量 C 程序员水平的重要标准。本文从几个 C 语言中常见的例子出发，深入剖析 malloc/free 这两个最常见内存管理函数的实现机制，并总结如何结合标准库写出高效的代码。

C/C++ 程序员对 malloc(new)、free(delete) 这对函数一定不陌生——我们从堆上申请、释放内存时都会用到它们。但它们究竟做了什么？如何才能高效地使用？下面从几个”奇怪的地址”说起。

奇怪的地址

程序 1：free 之后为什么有的能写、有的不能写？

int main()
{
    int* p1 = (int*)malloc(sizeof(long));
    free(p1);
    int* p2 = (int*)malloc(128 * 1024 * 1024);
    free(p2);
    printf("p1 = %p, p2 = %p\n", p1, p2);
    *p1 = 0;
    printf("ok here\n");
    *p2 = 0;
    return 0;
}

输出：

p1 = 0x501010, p2 = 0x7f579531a010
ok here
段错误 (core dumped)

同样是 malloc，返回的地址为什么差这么多？同样是 free 之后的内存，写 p1 就行，写 p2 就挂了？

程序 2：第二次申请到的地址，和第一次一样？

int main()
{
    void *p1 = malloc(sizeof(long));
    free(p1);
    void *p2 = malloc(sizeof(long));
    free(p2);
    printf("p1 = %p, p2 = %p\n", p1, p2);
    return 0;
}

输出：

p1 = 0x501010, p2 = 0x501010

第二次申请到的内存，恰好是第一次释放的内存——这一定不是巧合吧？

程序 3：线程申请小块内存，为何分到了 mmap 地址？

int main()
{
    const int thread_num = 8;
    pthread_t tids[thread_num] = {0};
    void *p[thread_num] = {0};
    for (int i = 0; i < thread_num; i++) {
        p[i] = malloc(1024);
        printf("p[%d] = %p\n", i, p[i]);
        assert(0 == pthread_create(tids + i, NULL, &thread_func, NULL));
    }
    for (int i = 0; i < thread_num; i++) {
        free(p[i]);
        assert(0 == pthread_join(tids[i], NULL));
    }
    return 0;
}

void* thread_func(void* param) {
    void *p = malloc(1024);
    printf("p = %p\n", p);
    sleep(1);
    free(p);
}

注意这个线程的输出：p = 0x7fc43a1008d0。为什么它分配到了这样一个地址上？

程序 4：申请 4 字节，地址却相隔 32 字节？

int main()
{
    void *p1 = malloc(4);
    void *p2 = malloc(4);
    printf("p1 = %p, p2 = %p\n", p1, p2);
    return 0;
}

输出：

p1 = 0x501010, p2 = 0x501030

申请两块 4 字节的内存，得到的地址却相隔 32 字节，为什么？

进程的地址空间分布

64 位进程在 Linux 中的地址空间分布如下图所示。结合前面的例子：p1 = 0x501010 属于 heap（堆）区域的地址，p2 = 0x7f579531a010 属于 mmap 区域的地址。

glibc 中，brk/sbrk 函数用来改变当前进程的堆结束地址，mmap 函数用来申请映射的内存空间。值得注意的是：

• 堆的地址是连续的，中间没有空洞；
• mmap 可以从任意地址开始申请指定大小的内存。

关于 ptmalloc

glibc 中负责内存管理的模块叫 ptmalloc，是一个支持多线程分配与回收的内存管理器。它加入了索引以加快搜索速度，可以把多个未被使用的块合并为一个大块，还支持缓存以便更快地复用最近释放的内存。

本文描述的 glibc 版本是 2.3.4，这也是线上机器的 glibc 版本。

谜底揭晓

先揭晓上面 4 个程序的答案，再分析 ptmalloc 分配与回收内存的策略。

• 程序 1：ptmalloc 申请新内存时，对 128K 以上的请求会直接使用 mmap 申请，128K 以下的请求则先尝试从进程堆申请。free(p1) 之后，这块小内存被 ptmalloc 缓存起来，对进程而言该地址仍然可读写；而 free(p2) 之后，这块大内存被直接 munmap 还给系统，对进程而言该地址不再可读写。所以写 p1 可以、写 p2 就段错误。

• 程序 2：p1 被 free 后缓存了起来，malloc p2 时，ptmalloc 优先从缓存队列中找合适的空闲 buffer，因此分配到了之前 p1 的地址。

• 程序 3：某个线程申请小块内存却分到了 mmap 地址，是因为 ptmalloc 为支持多线程而维护了多个内存分配区（arena）。只有主分配区使用进程的堆分配内存，其他非主分配区都先从 mmap 申请 1M 的空间作为 sub_heap，再从中分配。多个线程会争抢这些分配区，那个特殊的线程就是因为没抢到主分配区，转而新建了一个非主分配区，在它上面申请小块内存，于是得到了 mmap 地址。

• 程序 4：ptmalloc 最终分配的大小是 max(32, (size + 8) align to 16)，所以即使只申请 4 字节，也会分配 32 字节的空间。申请 25 字节会分配 48 字节，申请 41 字节会分配 64 字节。

ptmalloc 的核心术语

术语	含义
chunk	内存块，ptmalloc 管理分配与回收的最小单位；后文提到的”申请大小”均指转换成 chunk_size 的大小，即 max(32, (size + 8) align to 16)
arena	分配区，对外分配和回收 chunk。一个 arena 中有多个 sub_heap，用链表串联，尾端的 sub_heap 代表当前对外分配回收所用的 heap。每个分配区都有一把锁、一份 fastbin、smallbin、largebin、unsortedbin 和 binmap
heap	ptmalloc 自己管理的”堆”，向非主分配区提供内存空间，每个 heap 大小都是 1M，从 mmap 区申请
fastbin	默认情况下，80 字节以下的申请与释放都优先在 fastbin 中缓存。每个 fastbin 有 7 个内存箱（32B~80B，步进 8B），每个箱下挂一个空闲链表。fastbin 中的空闲块不能被合并
smallbin	申请大小在 80B512B 时，从 smallbin 查找。每个分配区维护 62 个定长的 smallbin 内存箱（64B512B，步进 8B）
unsortedbin	free 堆上内存时，ptmalloc 把块收集到 unsortedbin 链表中；smallbin 查找失败时会到 unsortedbin 中查找。频繁申请、释放同样大小的块时效率很高
largebin	申请大小在 512B128K 时，从 largebin 查找。每个分配区维护 64 个 largebin 内存箱（32 个缓存 512B2048B，16 个缓存 513B10240B，8 个缓存 10241B40960B，4 个缓存 40961B131072B，2 个缓存 131073B524288B，1 个缓存 524288B 以上）
binmap	用位图标记 smallbin/largebin 是否有空闲块，用于快速定位内存箱
topchunk	每个分配区最顶端的一块空闲内存，代表该分配区不申请新 sub_heap 时还剩余的空闲 buffer 大小

malloc 的分配流程

1. 查看当前线程是否绑定了一个分配区。若已绑定，则尝试获取该分配区的锁，成功则进入下一步；否则从第一个非主分配区开始依次尝试加锁，成功后把该非主分配区绑定到当前线程；若都失败，则创建一个新分配区绑定到该线程。

2. 把申请大小转换为 chunk_size。若 chunk_size 属于 fastbin 范围，则查 fastbin 对应内存箱，有则摘下表头空闲块返回。

3. 若属于 smallbin 范围，则查 smallbin 对应内存箱，有则摘下表头空闲块返回。

4. 接下来轮到 largebin。在此之前，先把 fastbin 中的块尝试合并，按大小放入合适的 smallbin/largebin 内存箱。进入 largebin 前先查 unsortedbin：若只剩最后一个空闲块且属于 smallbin 范围，直接返回它；否则把它从 unsortedbin 摘下，放入对应的 smallbin/largebin，并把对应的 binmap 置 1。

5. unsortedbin 清理完毕后，按 chunk_size 定位合适的 largebin，从该 largebin 起按 binmap 依次向后查找第一个非空内存箱，摘下它的最后一个节点，按指定大小分割空闲块返回，剩余部分重新挂回 unsortedbin。

6. 若所有缓存箱都没有合适空闲块，只能从 topchunk 向上申请：若 topchunk 足够大，则分割出一块返回并调整 topchunk 大小。

7. 若 topchunk 也不满足，只能扩展进程堆地址或求助于 mmap。不过在此之前，再瞧一眼 fastbin 有没有新内存块（可能有别的线程刚释放了一些），有则合并放入相应内存箱，从头再试一遍。

8. 若 chunk_size 大于 128K，直接用 mmap 申请，成功后更新统计信息并返回。接下来分两种情况：

   • 在主分配区：根据上次的堆结束地址继续申请，尽量保证堆地址连续。若 sbrk 失败（堆空间用尽），只能用 mmap 从任意地址申请指定大小（即一个新 sub_heap），并标记当前分配区地址不连续。
   • 在非主分配区：先尝试扩展当前 sub_heap，失败则新建一个 sub_heap 并把 topchunk 切到新 sub_heap 上。若新地址与之前 topchunk 结束地址连续，则更新 topchunk 大小；否则把 topchunk 更新为新申请内存的起始地址，并释放原 topchunk。一切顺利的话，从新 topchunk 上分配出申请的内存返回。

heap 操作

这里的 heap 指 ptmalloc 自己维护的”堆”，与进程的堆是两个概念。一个分配区可以申请创建多个 sub_heap，用单向链表串联，链表尾端是当前分配区 topchunk 所在的 sub_heap。每个 sub_heap 大小都是 1M，用 mmap 申请。

• newheap：一次向 OS 申请 1M 的 mmap 空间。先尝试从上次 mmap 地址空间尾部继续申请，失败则从任意地址申请。只把应用层申请的大小映射为可读可写，并记录 sub_heap->size = size。一个 ptr 对应的 sub_heap 起始地址就是 ptr & ~(1M - 1)。
• deleteheap：调用 munmap 把内存还给 OS。
• growheap：在 sub_heap 的高地址页面上继续设置可读可写属性，这样应用层拿到这些页面就可以访问。
• shrinkheap：去除已申请堆空间中的可读可写页面映射，此时应用层再访问该地址就会挂掉。
• trimheap：若 topchunk 覆盖了整个 heap，则执行 deleteheap，并把当前分配区的 heap 切换到上一个 sub_heap；否则把 topchunk 占的大小从 heap 中 munmap 掉，即在当前 sub_heap 中释放掉 topchunk。

free 的回收流程

1. 把要 free 的地址转换为 chunk_addr。若所在 chunk 属于 fastbin 范围，则挂到对应内存箱的头部。

2. 查看当前 chunk 的属性，若是直接通过 mmap 申请的大块内存，则直接调用 munmap 还给操作系统。

3. 否则检查前一个 chunk 是否也空闲，是则合并；再检查后一个 chunk 是否空闲且不为 topchunk，是则再次合并。最后把合并后的大空闲块挂到 unsortedbin 头部。若后一个 chunk 空闲且是 topchunk，则把大空闲块合并进 topchunk。随后，若这次总共释放的空闲块大于 64K，则执行一次 fastbin 合并操作。最后看释放内存所在的分配区：主分配区则紧缩进程堆空间，把尾部空闲地址还给系统；非主分配区则调用 trimheap 紧缩当前 sub_heap，必要时直接把 sub_heap 释放掉。

模拟一次 malloc/free

以 30K、40K、200K、100K 的四次申请与释放为例，逐步观察 ptmalloc 的行为：

1. 进程启动时，edata 指针指向当前进程堆的起始地址。

2. A = malloc(30K)：从堆上分配 30K。

3. B = malloc(40K)：从堆上再分配 40K（与 A 相邻）。

4. C = malloc(200K)：200K > 128K，直接 mmap 一块独立内存。

5. D = malloc(100K)：从堆上再分配 100K。

6. free(C)：C 对应的 mmap 内存直接被释放掉。

7. free(B)：B 的内存并没有还给系统——进程的堆地址只能从分配尾端向前回收，无法像 mmap 一样在任意位置释放。B 这块 40K 空闲内存其实被 ptmalloc 缓存起来，放进了 unsortedbin。

8. free(D)：B 和 D 相邻、都已空闲，被合并成一块 140K 的空闲内存。

9. 默认情况下，当最高地址空间的空闲内存超过 128K（可由 M_TRIM_THRESHOLD 调节）时，执行内存紧缩（trim）。上一步 free 时发现最高地址空闲内存已超过 128K，于是触发紧缩，把尾部空闲内存还给系统。

一个极端的例子

下面是一个很有代表性的例子，来自 StackOverflow。

int main()
{
    std::list<char*> ptrs;
    for(size_t i = 0; i < 50000; i++) {
        ptrs.push_back( new char[1024] );
    }
    for(size_t i = 0; i < 50000; i++) {
        delete[] ptrs.back();
        ptrs.pop_back();
    }
    ptrs.clear();
    sleep(100);
    return 0;
}

用 ps aux 得到的结果是：

pay 1546 0.1 0.0 59484 53068 pts/9 S 18:22 0:00 ./test1

再对比另一个写法：

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

int main() {
    char** ptrs = new char*[50000];
    for(size_t i = 0; i < 50000; i++) {
        ptrs[i] = new char[1024];
    }
    for(size_t i = 0; i < 50000; i++) {
        delete[] ptrs[i];
    }
    delete[] ptrs;
    sleep(100);
    return 0;
}

用 ps aux 得到的结果是：

pay 3209 0.4 0.0 7208 856 pts/9 S 18:23 0:00 ./test2

ps aux 每一列的含义是：USER、PID、%CPU、%MEM、VSZ（虚拟内存）、RSS（物理内存）、TTY、STAT、START、TIME、COMMAND。

为什么同样把内存都释放掉，test1 的 VSZ 和 RSS 仍然高居不下呢？结合上面的原理再看 test1 的代码：ptrs.push_back(new char[1024]) 实际上每次都 malloc 了两块内存——一个 1K、一个 8B（chunk_size 对齐后为 32B），这两块内存在进程的虚拟地址空间中连续，一共 50000 对这样的块。

执行完 50000 次 delete[] ptrs[i] 后，所有 1K 内存块都放进了 largebin；而执行 ptrs.clear() 时，所有指针（8B 的块）都被放回了 fastbin。前面提到过，free 时 fastbin 中的空闲块无法与相邻空闲块合并，这就导致释放掉的 1K 内存无法与 topchunk 会合，也就无法触发 topchunk 的紧缩回收机制——大量内存积压在 ptmalloc 中，无法还给操作系统。而 free 时唯一回收 fastbin 的时机是 topchunk 大于 128K，但由于大量 8B 小内存块的存在，这个机制始终无法触发。

小结与思考

• 其实 test2 的代码稍作修改——提前把 50000 个指针分配好，再统一分配大块的 1K 内存——就能避免问题。

• 得到的经验是：使用 ptmalloc 时，尽量要避免大块内存和小块内存混合申请，以免产生堆碎片。

• 操作 STL 容器时，若能大致预估要用的元素个数，可以提前 reserve 好大块内存，而不是一点一点地申请。