内存分配 入门

栈没人管。一次调用靠给 rsp 做减法给局部变量留位置，返回时加回同一个数，整件事里没有空闲链表、没有搜索、没有元数据。下面已经在栈上的那些帧压着当前调用刚压进去的那个。拖滑块走一遍调用深度：

注意什么都没被搜。那个指针按帧自己的大小挪一下，分配就完事了；释放是同一条指令换个符号。这也是为啥指向已经返回的帧的指针比「过期」更糟 —— 字节还在原地，而下一次调用会盖掉它们。

代价是这块区域是定死的。Linux 默认给 8 MiB，下面还有1 MiB 的保护间隙，谁都不许映射。选一个栈帧大小，把递归推过上限:

死在哪里完全由栈帧大小决定。64 字节的帧，栈能压 131,072 次；局部变量 8 KiB 就只剩 1,024 次 —— 同一段递归在一个函数里安全、换个函数就致命。把它推过上限, 失败至少是大声的：保护间隙没有映射，第一次碰它就在肇事指令上 SIGSEGV。

任何必须活得比调用长的东西改住堆, 而堆不过是一块内核愿意按请求扩的区域。拖break，看一次 brk 买到什么：

5 次调用就买下了全部。glibc 每次增长都多要 128 KiB —— M_TOP_PAD —— 所以一个用小块分配640 KiB的程序只做 5 次 brk，不是 5000 次。系统调用被摊薄掉了；剩下的是这块区域内部的记账，那就是 allocator。

可 break 只是一个数，所以它只能还回躺在最高那个在用分配之上的部分。挪一下还在用的那个分配，看剩下的怎么不再能还：

因为 break 是个水位，顶上一个 48 KiB 的分配就把它下面592 KiB钉住了 —— 在 allocator 眼里是空闲的，在内核眼里是常驻的。这是健康进程看起来像泄漏的头号原因，而且 free 再多也治不好，因为 free从来就不是负责还页的那个东西。

glibc 就在它给你的指针前面写一个 8 字节的字：这个 chunk 自己的大小,free(p) 就是靠它在没人告诉的情况下知道 p 有多大。你的请求之外的部分全是对齐。拖请求大小，看取整加了多少:

这个算术是精确的 —— (n + 8 + 15) & ~15，下限 32。malloc(24) 花 32 字节，malloc(25) 花 48 字节 —— 请求多 1 个字节，chunk 多 16 个。而对 17 字节的请求，malloc_usable_size 报的是 24, 因为下一个 chunk 的大小字只在本 chunk 空闲时才有用。

一个固定的字加一张 16 字节的栅格，对小对象是按比例收税，对大对象只是舍入误差。把请求横跨 4 个数量级走一遍，看开销怎么塌下去：

看左端。malloc(1) 为 1 个字节取走 32 个 —— 3,100% —— 而一条 24 字节节点的链表住在 32 字节的 chunk 里，四分之一的链表是没人读的大小字段。这才是 pool 和 arena 的真正理由：不是 malloc 慢，而是对象一小，按对象的记账就永远摊不薄。

过了某个阈值，arena 不再是正确答案，glibc 直接找内核。把请求滑过 128 KiB, 看路径怎么变：

在边界上变的是路径，不是大小。 chunk 变成它自己的一个映射、向上取整到整页，而每一对分配 / 释放从 0 次系统调用变成 2 次。 free 掉一个会把阈值抬到那个大小 —— 最高 32 MiB —— 所以循环用 1 MiB 缓冲区的程序只付一次系统调用，然后就不付了。

你要的和你拿到的之间那条缝，也是最安静的堆 bug 住的地方。把写入拖过一个 17 字节分配的末尾，看它够到什么：

那个分配其实拥有 24 个可用字节，所以越界的头7 个字节落在没人读的填充里，什么都没改：测试过、review 过、bug 上线。第 8 个字节盖掉下一个 chunk 的大小字段, 而崩溃要等很久以后一次毫不相干的 free 才到。大声的失败是走运的那种。

链表按释放顺序排，不按大小排，所以第一个够大的 chunk和最小的那个够大的 chunk通常不是同一个。设一个请求、换个规则，看链表被读了多少：

注意 malloc(104) 上的取舍。首次适配读 2 个 chunk，为了 112 字节把一个 512 的切碎；最佳适配读满 8 个，只剩 64。两边都不免费 —— 首次适配便宜但毁掉大块，最佳适配保住它们但是 O(n)。尺寸类靠索引链表而不是走链表，把两样都买下来。

把 chunk 放回去是另一半，而且是让链表不至于无限长的那一半。选一个顺序，一步步走过这些 free:

该读的数是最大连续段，不是总量。每次 free 检查它的两个邻居，不管合并出多大，最多只合并 2 次 —— 所以一串把整个堆塌成一个 chunk 的 free，每次仍然是常数时间。让中间那个 chunk活着， 304 个空闲字节就永远凑不出比 224 更大的段。

chunk 回到哪条链表只由它的大小决定，glibc 对这件事有 4 个答案。让一个 chunk 大小横着走过它们：

因为前 3 个是索引的，一次 free和复用它的那次 malloc 都只是写一个指针再弹一下。只有 largebin 要搜，而且按大小有序地搜 —— 这就是为啥 allocator 的最坏情况住在1 KiB 以上、而它的常见情况根本没有最坏情况。tcache 是 4 个里最新的，也是 glibc 追上来的原因：2.26 加入，每个 bin 7 个 chunk，完全不用锁。

glibc 的类就是上一节那张 16 字节栅格，每个对象前面顶着大小字。jemalloc 的是每翻倍 4 个 —— 8、16、32、48、64、80、96、112、128、160 —— 而且完全没有按对象的头，因为元数据住在 slab 里。换表，挪请求:

两张表输在相反的地方。16 字节时 glibc 拿 32、jemalloc 拿 16，因为一个固定的字把小对象直接翻倍。513 字节时 glibc 拿 528、 jemalloc 拿 640，因为每翻倍 4 个类，意味着下一个类比上一个高四分之一。

把整个小尺寸区间画出来，两张表只有一个交点。让请求走过它，一次读两边的浪费:

它们在 129 字节交叉。以下 glibc 的栅格更细、头就是全部成本；以上 jemalloc 的类间距占上风，并在越过边界 1 个字节时正好顶到 25% —— 在 8,277 字节处 jemalloc 付 23.7%,glibc 付 0.1%。一个 65 字节的结构体花 80; 压到 64 就白拿回五分之一。

类只是设计的一半。另一半是它被切出来的那块slab，而 slab 是整页的，所以页数是挑出来让尾料最小的。选一个类，看 slab 跟着它变：

别扭的类会占不止一页，因为 slab 是按尾料最小挑的：112 字节的格位在 1 页里困住 64 字节，在 2 页里只困住 16。要紧的是答案的形状 —— 每个 slab 一张位图，而不是每个对象一个头，这就是 16 字节的分配能只花 16 字节的原因。两张表都不错，它们只是按不同的分布定价；要是你的热点分配是个 9 KiB 的缓冲区，请把它凑到一个类上，而不是跟 allocator 争。

一个 arena、一把 mutex，每个线程的每次 malloc 都得排队。下面这个模型里临界区是 8 ns —— 索引一个 bin、摘下一个 chunk、写两个指针 —— 对上外面 40 ns 的活。加线程，看曲线怎么离开那条直线：

注意它停在哪。不管多少线程要，锁每 8 ns 只能服务一次分配，所以吞吐在 6 个线程就饱和，后面 26 个什么都买不到。那些常数是建模的选择，形状不是。任何固定的临界区都给出一条平线，唯一真正的解法是别拿这把锁。

这正是每线程缓存的用处。glibc 的 tcache每个尺寸类存 7 个 chunk，不问任何人。只 free 不再分配：

看第 8 个。7 个以内，一次 free 就是往线程本地的单链表上推一下 —— 没有原子操作、没有锁、十来条指令 —— 而配对的 malloc 就是弹一下。第 8 个溢出到arena，要为锁买单。64 个 bin 覆盖到 1,032 可用字节以内的所有请求，也就是绝大多数。

glibc 答案的另一半就是干脆多来几把锁：发现主 arena 忙的线程会拿到自己的一个 arena，每核最多 8 个。抬高线程数，看被保留了什么：

那些 arena 每个都是自己的一块 64 MiB 映射，所以 16 核机器上 65 个线程还什么都没分配就先保留了 4 GiB 地址空间。它是虚拟的、不是常驻的，碰之前不花钱 —— 但它也正是容器限额里被当成泄漏报出来的那个数。MALLOC_ARENA_MAX=2 是一行的解法，代价是把争用买回来。

有一种模式能击穿上面所有东西：在一个线程上分配、在另一个线程上 free 的 chunk。抬高跨线程比例，对比两种处理办法：

因为 chunk 属于它出生的那个 arena,glibc 必须拿那个 arena 的锁才能还回去，于是 free 的线程和属主线程串行了。在一半跨线程时，模型里 16 个线程从每秒 10.81 亿次跌到 2.34 亿次。 mimalloc 改成把 chunk 推到属主页的原子空闲链表上 —— 一次 compare-and-swap，后面没人要排队。

所以堆可以在程序的需求不涨的情况下长大。下面每一轮都释放在用分配里散落的三分之一，并立刻把同样多的字节分配回去，所以在用总量一个字节都不差。跑几轮，然后向堆要点东西：

注意哪个数才回答得了请求。30 轮之后有 768 个空闲字节，而最大的那一段是 352, 所以一个 512 字节的请求哪儿都放不下，堆只好再长 —— 而在用集还是开头那 3,360 字节。总空闲量是个统计数字；那些洞才是你真正拥有的。

这种增长在运维唯一在乎的意义上是永久的。沿着两分钟的突发负载拖一遍，把常驻和在用放一起比：

看两条曲线在第一次突发时分开，然后再也没合上。峰值变成了常驻的地板：free 把那些字节还给了某个 bin，页还映射着、还脏着，两分钟以后内核仍然按 440 MiB 收费，而程序只用 180。除非有谁专门把页还回去，否则 RSS 就是一个只增不减的最大值。

确实有谁能。jemalloc 跑一个衰减 purger，把程序有一阵没碰的页madvise 掉。设一个窗口, 看那个天花板怎么降下来：

窗口必须比突发之间的间隔短。10 秒时常驻一路跟着在用往下走； 30 秒时它根本不 purge，因为页在窗口关上之前又脏了。而且 purge 不免费 —— 重新缺页 260 MiB 大约要 67 ms 的次缺页，由下一个碰这些页的人买单。

只看最后一个点的话，3 种不同机制画出同一张图。挑一个，走一遍曲线：

其中 2 条在两分钟处落在彼此 5 MiB 之内，而它们不是同一个 bug。碎片靠越爬越慢到达 410 MiB，因为洞终究会被复用；泄漏沿一条不见平台的直线到 415, 也是唯一一个要在你自己代码里修的。取整在 229 走平，自己就露了馅。一小时的形状才是诊断；末尾那个数不是。

如果一块区域里的东西从来不单独释放，分配就根本不再需要数据结构 ——一个只往一个方向走的指针、一次和上限的比较、一次跳转。把新生代填满，把两个代价并排放：

比例就是全部。把 8 MiB 全填满、每个对象 48 字节，就是 174,762 次分配： 0.35 ms 的推指针，对上 2.1 ms 的tcache 命中 —— 而 tcache 命中本来就是快路径。没有空闲链表，没有尺寸类。运行时仍然写对象头，但那是写给类型系统的，不是写给 allocator 的。

账单在回收的时候到，而账单的形状才是关键。设一下有多少活下来，看什么被碰到了：

看什么没被碰。复制式回收器走一遍幸存者，把它们搬出去，剩下的靠把指针拨回起点就回收了 —— 所以垃圾不花钱，代价只跟活着的东西成正比。10% 存活时，那是 0.35 ms 分配之上再加 0.10 ms 复制，仍然比同样这些对象的 malloc + free 便宜 4.6 倍。

搬家是 malloc 抄不来的那部分，而且不是努力就行的。把那个 chunk横着拖走，看程序手里还攥着什么：

因为 C 的指针就是地址，把 chunk 搬走之后，那个指针指的是现在住在旧地址上的东西。回收器搬得动，是因为它知道每一个根、每一条引用，还能改写它们；malloc 从来没被告知它的指针去了哪。所以 C 的堆只能靠重启进程来整理碎片。

于是回收器彻底躲开了碎片 —— 并为此所需的余地收费。设一下堆是在用集的几倍:

Hertz 和 Berger 测出了这条曲线插值的 3 个点：在用集的 5 倍时，分代回收器追平显式的 malloc 和 free;3 倍时慢 17%;2 倍时慢 70%。这就是一个数字里的取舍。要选的不是快和慢 —— 而是选花内存，还是花你自己在生命周期上的注意力。

4 种负载里只有 2 种会分出胜负。单线程工具上 3 个打平， glibc 靠「已经链进去了」取胜。在16 线程的流水线上 —— 生产者分配、消费者 free —— glibc 只跑到mimalloc 的五分之一。突发型服务上吞吐打平，而常驻集不打平： 432 MiB 对 191 MiB。

3 件 review 时值得标出来的事，全都是上面几节的后果：

• 热循环里对小于 64 字节的对象 malloc。头就占对象的四分之一。把分配提出去，或者用 arena。
• 结构体大小刚好越过类边界。65 字节花 80 ——sizeof 一下，压回 64。
• 拿 VSZ 报警。它把没人碰过的 arena 也算进去。用 RSS 报警，并且看它的斜率。

要紧的是最后一级。一块新的 1 MiB 映射在程序读到一个字节之前就花掉 256 µs ——一次推指针的 128,000 倍 —— 而第二轮迭代就把它摊掉了，吞吐 benchmark 里看不到。 p99 曲线就是拿这个堆出来的。

/* the chunk one malloc(n) really takes */
size_t c = (n + 8 + 15) & ~(size_t)15;
if (c < 32) c = 32;      /* MINSIZE   */
/* usable = c - 8                     */
/* own mmap when c >= 128 * 1024      */