1. 先把层级关系捋清楚malloc 是库函数sbrk 是系统调用1.1 一次堆破坏排查引出的问题几年前排查过一个很典型的内存问题进程跑上几个小时内存占用只涨不跌最后被系统杀掉。日志里没有任何异常代码里该 free 的地方也都写了。当时把strace挂上去看发现brk调用的次数不多但每次请求的量都不小而堆顶那块内存始终没有被还回去。那次排查之后我才算真正把这条链路弄明白malloc是标准 C 库里给你的一层用户态分配器它自己维护着一片内存池向操作系统批发内存、再零售给调用方而sbrk是同名系统调用在用户态的薄封装干的事情只有一个——挪动程序断点program break。这两者之间隔着一整层运行时库很多人把它们当成一回事写出来的代码自然就会出问题。这篇内容想解决的是这么几件事搞清楚malloc和sbrk到底各自负责什么为什么一个简单的free之后内存不会立刻还给系统以及最重要的——怎样用一个sbrk手写出能跑、能验证、能解释清楚的分配器。适合的对象是写过 C、知道指针和链表、但没碰过内存管理底层的同学也适合那些被线上内存问题折腾过、想补上这块知识的人。代码我会给完整可编译的版本每一版都说清楚为什么要这么改。提醒下面所有实现都只用于学习和受控场景别直接塞进生产项目里替换标准库原因在第 6 章会讲透。1.2 一个形象的类比包工头与征地办把进程地址空间想象成一块正在开发的荒地。sbrk是征地办你报一个数字它就把地界界线往外推几米推完告诉你原来那条线在哪儿。它只管给地不管你怎么用也不管你会不会浪费。malloc是包工头。你跟他要 100 平米他不会真的跑去征地办申请 100 平米——他会先看看自己手上囤的地里有没有合适的空地有就直接划给你没有才去找征地办要一大片比如一次要 128KB然后切开了慢慢发。等你退租调用free地也只是回到包工头手上他留着下次用征地办那边的界线一动没动。这个类比解释了两个最常见的困惑为什么free之后top命令看内存没降地还在包工头手里以及为什么分配 1 字节和分配 100 字节在底层可能触发完全不同的行为切块策略不同。理解了这个层级关系后面所有的实现细节才有落脚点。1.3 brk 与 sbrk 的最小差别brk(addr)是直接设定新的断点地址成功返回 0失败返回 -1sbrk(increment)是相对挪动参数是有符号增量成功返回旧的断点地址失败返回(void *)-1并把errno设成ENOMEM。这个返回旧地址的设定是新手最容易踩的坑。很多人凭直觉以为返回的是新地址写出来的代码在单次调用时看起来没问题连续调用就全乱了。我第一次写的时候就把它当成了新地址结果第一块内存直接和头部数据重叠跑起来才发现结构体里的字段莫名其妙被改掉。sbrk(0)是一个特殊用法增量为 0断点不动返回当前断点位置。这个技巧在排查内存问题时特别有用你可以在关键路径前后各打一次差值就是这期间堆增长了多少字节。虽然sbrk在较新的标准里已经被标记为历史遗留接口但在主流的类 Unix 系统上依然可用做教学和原理验证足够了。2. 整体设计思路为什么要用 sbrk 手搓一个分配器2.1 先把需求边界定死动手之前必须先划清楚我不做什么否则很容易写成一个四不像。我要的这个分配器目标只有四条能向系统申请内存能返回满足对齐要求的指针释放后能被后续分配复用而不是永久浪费相邻的空闲块能合并避免外部碎片无限膨胀行为可观测、可验证每一步都能用数据说清楚明确不做的事情同样重要不做多线程优化后面单独讨论怎么加锁、不做大小分档不搞 fastbin/tcache 那一套、不做页对齐的独立映射、不做内存归还的激进策略。一个能跑通的小实现比一个半成品的复杂实现有价值得多。这个取舍背后的判断是学习型实现的价值在于把机制暴露出来而不是在性能上追平工业级实现。标准库的分配器经过几十年打磨你要真想在性能上超过它通常得先知道自己场景的特殊性在哪里。2.2 三个候选方案怎么选在决定用sbrk之前其实有三个方向可走我把它们的差别列成表方便你按自己的场景对号入座。方案申请方式释放行为优点代价sbrk / brk连续扩展堆顶只能整体收缩块级释放靠自己管理实现简单地址连续适合学习只能动堆顶归还困难mmap独立匿名映射munmap 直接还给系统归还干净无外部碎片每次映射有系统调用开销粒度大现成分配器库函数封装由库自己管理成熟稳定性能好机制不透明难定制标准库的实现其实是混用的小请求走brk/sbrk扩堆大请求超过某个阈值常见默认是 128KB 量级走mmap单独映射这样大块用完munmap就能干净还回去不会在堆里留下一大片空洞。我选sbrk做这个练习理由很实在它是理解堆这个概念最直接的入口。你写完一遍再去看/proc/self/maps里那个[heap]段为什么会一路长大就完全是另一种感受了。2.3 三层结构从系统调用到应用接口整个实现我拆成三层后面所有代码都按这个骨架往里填底层pool_grow()负责调sbrk拿一大块处理对齐记录剩余空间中层块管理负责切分、标记空闲、合并相邻块上层my_malloc()/my_free()对外只暴露这两个函数分层的意义在于当出现问题时你能快速定位是哪一层的锅。指针没对齐一定是底层分配出来的块互相重叠多半是切分逻辑内存占用一路涨那就是合并没生效。这种可分而治之的结构比把所有逻辑塞在一个函数里强太多。3. sbrk 的行为边界返回值、对齐和反直觉的地方3.1 返回值语义与错误判断先看一段最朴素的封装也是我建议所有人在动手前先写对的一段#include unistd.h #include stdint.h #include errno.h void *os_alloc(size_t bytes) { void *old sbrk(0); if (old (void *)-1) return NULL; if (sbrk((intptr_t)bytes) (void *)-1) { errno ENOMEM; return NULL; } return old; /* 返回的是挪动之前的断点即新区域的起点 */ }三个细节必须注意到。第一先取一次当前断点作为这块新内存的起始地址如果直接拿第二次调用的返回值当起点那就错位了。第二增量参数类型是intptr_t而不是size_t因为收缩时要用负数用无符号类型会把一个很小的负数变成巨大的正数直接申请失败或者更糟。第三失败返回值就是(void *)-1不能拿NULL去判断这是系统调用层和库函数层的一个典型差异。还有一个容易被忽略的点sbrk不会对返回的地址做任何对齐保证。它在多数系统上返回的断点往往是 16 字节对齐甚至页对齐的但这是实现细节不是契约。真要靠它吃饭就得自己对齐下一节展开。3.2 对齐16 字节不是随便定的对齐这件事很多人知道要做但说不清为什么是这个数。先说结论在 64 位平台上malloc返回的指针必须满足max_align_t的对齐要求通常是 16 字节。原因是如果返回的地址只满足 8 字节对齐那么在上面放一个含long double或 SIMD 类型的结构体就可能触发未对齐访问——轻则性能下降重则在某些架构上直接总线错误。对齐的写法很固定#define ALIGNMENT 16UL #define ALIGN_UP(x) (((x) (ALIGNMENT - 1)) ~(ALIGNMENT - 1))这里~ALIGNMENT - 1)是掩码把低 4 位清零。注意括号别写错的优先级低于漏括号会得到一个完全错误的结果而且编译器不一定报错。对齐带来的浪费是内部碎片的一部分。你申请 1 字节实际占掉 16 字节的载荷空间再加上块头总消耗可能就是 48 字节。这个比例在小对象密集的场景里非常可观所以工业级分配器才会搞出 size class 分档用固定档位减少浪费。还有一层对齐要考虑块头本身的尺寸也必须是 16 的倍数否则载荷区的起始地址就会偏移 8 字节前面算好的对齐全白费。我在下面设计块结构时会专门验证这一点。3.3 元数据放在哪堆内还是堆外每块内存都需要记录我多大我是不是空闲的我前后是谁。这些信息放哪儿是个设计决策。放堆外比如一个独立的数组或哈希表的好处是不占用用户可见的内存坏处是查找开销大、结构复杂而且一旦这个表本身分配失败整个系统就崩了。放堆内每块前面加一个头部的好处是定位是常数时间——拿到用户指针往前挪固定字节就是头部坏处是每个块都要付出固定的头部开销小对象上这个比例很吓人。标准库的选择是堆内头部而且做得极其紧凑64 位下最小块是 32 字节其中只有一部分是真正给用户用的。我这个实现也走堆内路线但头部会稍微奢侈一点因为要放双向链表指针方便合并。这是典型的用空间换实现复杂度的取舍在教学场景里我认为完全值得。4. 从零实现三版迭代把分配器跑起来4.1 第一版只进不出的 bump allocator最简单的形态是指针推进式分配一次性要一大片每来一个请求就把指针往后推推到头再要一片。它没有free但作为理解堆增长的第一步非常合适。#define POOL_CHUNK (256 * 1024) static char *g_pool NULL; static size_t g_pool_left 0; static int pool_grow(size_t need) { size_t want (need POOL_CHUNK / 2) ? ALIGN_UP(need) : POOL_CHUNK; char *base (char *)sbrk((intptr_t)want); if (base (char *)-1) return -1; char *aligned (char *)ALIGN_UP((uintptr_t)base); size_t skip (size_t)(aligned - base); g_pool aligned; g_pool_left want - skip; return 0; } void *bump_alloc(size_t n) { if (n 0) n 1; size_t need ALIGN_UP(n); if (g_pool_left need) { if (pool_grow(need) ! 0 || g_pool_left need) return NULL; } void *p g_pool; g_pool need; g_pool_left - need; return p; }这段代码里有两个值得说的点。want的取值做了个判断小请求按固定块大小要大请求按实际需要要目的是避免为了一个 4KB 的请求去要 256KB 造成浪费。skip记录了对齐时被牺牲掉的字节数这部分直接从可用空间里扣掉不能算进g_pool_left否则后面算出来的边界会超出实际申请范围写越界都不知道。第一版能验证的事情对齐是否正确、多次分配是否重叠、堆的增长节奏是否符合预期。它的缺陷也很明显——一旦分配出去就再也收不回来实际可用内存等于历史峰值。这显然不够得加释放。4.2 第二版加上块头、首次适配与分裂块头我用这样一个结构typedef struct block { size_t payload; /* 载荷字节数已对齐 */ struct block *prev; struct block *next; int free; int _pad; /* 显式补齐保证头部尺寸是 16 的倍数 */ } block_t; #define HDR_SIZE ALIGN_UP(sizeof(block_t)) /* 64 位下 32 */ #define MIN_BLOCK (HDR_SIZE ALIGNMENT) /* 64 位下 48 */_pad这个字段看起来多余其实是刻意的。算一下size_t8 字节两个指针 16 字节free4 字节不加_pad就是 28 字节结构体本身会因为对齐规则被补到 32加了_pad是 32 字节正好是 16 的倍数。两种写法sizeof都是 32但显式写出来意图更清楚也避免换平台后编译器行为不同带来的意外。HDR_SIZE再套一层ALIGN_UP是双保险。MIN_BLOCK的 48 字节是这么来的一个块至少要能装下自己的头部32加上一个最小可分配的载荷单元16。如果切分后剩下的空间小于这个数那就不该切——切出来的块连自己都养不活只会变成永远无法复用的死块。分配逻辑用首次适配从头扫到尾找到第一个够大的空闲块static void split_block(block_t *b, size_t need) { if (b-payload need MIN_BLOCK) return; /* 剩的不够养活一个新块整块给出 */ block_t *rest (block_t *)((char *)b HDR_SIZE need); rest-payload b-payload - need - HDR_SIZE; rest-free 1; rest-prev b; rest-next b-next; if (b-next) b-next-prev rest; else g_tail rest; b-next rest; b-payload need; } void *my_malloc(size_t n) { if (n 0) n 1; size_t need ALIGN_UP(n); for (block_t *b g_head; b; b b-next) { if (b-free b-payload need) { split_block(b, need); b-free 0; return (void *)((char *)b HDR_SIZE); } } block_t *b carve(need); /* 从 bump 池里切一块新的出来 */ if (!b) return NULL; return (void *)((char *)b HDR_SIZE); }为什么用首次适配而不是最佳适配最佳适配要扫完全表才能确定最优解在链表结构上代价太高首次适配平均扫描长度短得多虽然碎片率稍差但配合后面的合并策略实际表现完全够用。这也是个典型的工程取舍理论上更优的算法在常数因子上输掉时就不该选它。第二版有个已知缺陷如果整块给出去剩下的空间就浪费了因为不够最小块这个浪费会在极端情况下累积。我在实现里加了个计数器记录这种浪费的总量跑测试的时候看到数字不大就没继续优化。4.3 第三版双向链表与相邻块合并释放的关键不是把free置 1而是合并。一个 100 字节的空闲块旁边紧挨着另一个 100 字节的空闲块如果你不合并来了个 200 字节的请求就只能去申请新内存而实际上堆里明明有足够空间。这就是外部碎片。void my_free(void *p) { if (!p) return; block_t *b (block_t *)((char *)p - HDR_SIZE); b-free 1; /* 先向后合并注意顺序先并后面再并前面指针维护更简单 */ if (b-next b-next-free) { block_t *nb b-next; b-payload HDR_SIZE nb-payload; b-next nb-next; if (nb-next) nb-next-prev b; else g_tail b; } /* 再向前合并 */ if (b-prev b-prev-free) { block_t *pb b-prev; pb-payload HDR_SIZE b-payload; pb-next b-next; if (b-next) b-next-prev pb; else g_tail pb; b pb; } try_shrink(); }合并顺序很讲究。如果先向前合并b这个指针就失效了后面的操作全得换新指针容易写错。先向后合并能保持b一直指向合并后的块头逻辑更直白。这个细节在任何链表操作里都适用保持操作对象的指针稳定比省一次赋值重要得多。然后是try_shrink()也就是把堆顶空闲块还给系统static void try_shrink(void) { while (g_pool_left 0 g_tail g_tail-free) { char *end (char *)g_tail HDR_SIZE g_tail-payload; if (end ! (char *)sbrk(0)) break; /* 不是紧贴断点的块不能收缩 */ size_t total HDR_SIZE g_tail-payload; if (sbrk(-(intptr_t)total) (void *)-1) break; g_tail g_tail-prev; if (g_tail) g_tail-next NULL; else g_head NULL; } }这里的条件g_pool_left 0是关键也是最容易写错的地方。如果 bump 池里还有没用完的空间g_pool就不等于真正的断点位置这时候收缩会把还没分配出去的空间一起退掉但它们其实已经被算进可用池了——账就对不上了。顺带解释一下那句end ! (char *)sbrk(0)只有当这个空闲块的末尾正好是当前断点才能安全退回。否则中间夹着别的已分配块退回去就等于把活人的地给征了。while循环保证能连续回收多个相邻的空闲块。这个实现算不上激进很多情况下干脆不回收但它绝不会出错对学习型代码来说不出错比回收彻底重要得多。4.4 完整测试与验证方法代码写完不测等于没写。我一般从四个维度验证每个维度都对应一类典型 bug。#include assert.h #include string.h #include stdio.h static void test_alignment(void) { for (int i 1; i 300; i) { void *p my_malloc((size_t)(i * 7 1)); assert(p ! NULL); assert(((uintptr_t)p (ALIGNMENT - 1)) 0); } puts([ok] 对齐检查通过); } static void test_no_overlap(void) { char *a (char *)my_malloc(1000); char *b (char *)my_malloc(1000); assert(a b); memset(a, 0xAA, 1000); memset(b, 0xBB, 1000); for (int i 0; i 1000; i) assert((unsigned char)a[i] 0xAA); puts([ok] 无重叠检查通过); } static void test_reuse(void) { void *b1 my_malloc(512); my_free(b1); void *b2 my_malloc(512); assert((uintptr_t)b1 (uintptr_t)b2); /* 应复用同一块 */ puts([ok] 复用检查通过); } static void test_coalesce(void) { void *d my_malloc(256); void *e my_malloc(256); void *f my_malloc(256); my_free(d); my_free(f); my_free(e); /* 三块合并后约有 3*256 2*32 字节可用 */ void *big my_malloc(256 * 3 32); assert(big ! NULL); puts([ok] 合并检查通过); }四个测试对应的 bug 类型依次是对齐没做导致未定义行为、切分算错导致越界、释放后无法复用等于只进不出、不合并导致大块请求失败。第二个测试尤其值得多说一句。检查内存有没有重叠光看指针不安全得写满不同的标记再逐字节回读。这个手法在排查各种内存踩踏问题时都管用因为越界写入会在相邻块里留下可观测的痕迹。跑完这些测试我还会用系统调用跟踪工具看一眼实际的brk调用次数strace -e tracebrk,mmap,munmap ./myalloc 21 | grep brk | wc -l如果这个数字在几百次分配之后仍然只有个位数说明池化生效了如果是几百次那说明pool_grow的判断逻辑有问题每次都重新要内存。这个指标比任何性能计时都直观。5. 常见问题与排查实录5.1 高频故障速查表下面这些问题我自己踩过或者看别人踩过基本覆盖了手写分配器的绝大多数翻车现场。现象最可能的原因排查动作程序在 memset 时崩溃返回指针没对齐或算错了可用长度打印指针低 4 位检查是否全 0两个分配出来的块数据互相覆盖切分时头部尺寸算漏或忘了加 HDR_SIZE打印相邻块地址差与块的 payload 对照free 之后程序行为异常释放的指针不是分配返回的那个检查是否对指针做了运算后传进去堆内存只涨不跌没有合并或收缩条件永远不成立加计数器统计空闲块总数与总字节分配大块返回 NULL 但堆明明有空碎片化严重没有合适的连续块遍历链表打印每块大小看最大空闲块多线程下随机崩溃sbrk 和分配器本身都不是线程安全的加锁或改用线程局部池释放时崩溃在链表操作块头被越界写坏检查用户写入长度加哨兵值验证5.2 用跟踪工具和调试器定位光靠读代码找内存问题效率很低工具才是正道。三个手段按成本从低到高排第一在代码里埋计数。全局变量记录sbrk调用次数、当前堆大小、空闲块数量、碎片浪费总量程序退出时打印出来。这四个数字能覆盖大部分问题次数飙升是池化失效空闲块多但申请失败是碎片浪费总量大是对齐策略有问题。第二用系统调用跟踪看行为。strace -e tracebrk能看到每次断点挪动的增量和返回值。有一次我发现某段代码在循环里狂调brk一看增量都是 4096 的倍数就知道是某个大对象分配越过了池化阈值每次都单独扩堆。第三用调试器看内存布局。在分配失败的地方下断点把链表从头到尾打一遍每块的地址、大小、空闲标志一目了然。这时候如果发现某块的payload大得离谱比如接近 2^63基本可以确定是块头被越界写坏了。经验块头被写坏是最难查的一类问题因为它不会当场报错而是在后面某次链表遍历时才炸。我的做法是在块尾加一个 8 字节的魔数哨兵释放时校验坏了就立刻abort这样能第一时间定位到越界的那次写操作。5.3 几条踩出来的经验别在分配器里调用会再分配的东西。听起来像废话但真写代码的时候很容易顺手在错误分支里来个printf而printf内部可能要分配缓冲区于是分配器重入直接死锁或者栈溢出。调试日志要用预先分配好的静态缓冲区。用assert而不是if-return做内部校验。分配器的内部不变量一旦被破坏继续跑下去只会产生更难查的问题。宁可当场崩也不要带着错误状态走下去。每次改完都跑一遍全量测试。分配器的 bug 有很强的隐蔽性改一处合并逻辑可能把对齐搞坏而这种问题在小测试里根本看不出来。我吃过亏改完只测了malloc没测free结果上线前才发现释放路径的指针计算漏了一项。记住MIN_BLOCK这个数。48 字节在 64 位下是个硬门槛所有关于能不能切的判断都要拿它比。有次我写成了need HDR_SIZE b-payload少算了最小载荷切出来的块特别小后面分配时直接越界。6. 边界与延伸什么场景适合自己写什么场景该老实调库6.1 性能实测的对比方法自己写的分配器和标准库的差距有多大我给个可复现的测法你自己跑一遍比看任何数字都可信。准备三组负载小对象密集型循环 100 万次分配 32 字节然后统一释放、大小混合型一半 64 字节一半 4KB、长生命周期型分配 1000 个对象全程不释放。每组都分别跑标准库版本和自研版本用高精度时钟打点。结论仅供参考具体数值随机器和编译选项差异很大小对象密集场景标准库通常有明显优势因为它有分档缓存几乎不发系统调用大小混合场景差距会缩小长生命周期场景两者接近因为这时候瓶颈不在分配速度而在内存总量。真正能拉开差距的地方是可预测性。我这个实现在分配耗时上相当均匀没有突发的长尾而标准库在某些不常见的尺寸组合下可能出现抖动。如果你的场景对确定性要求高于绝对速度比如某些实时性要求高的模块自己写就有意义。反过来如果就是普通业务代码省下这份力气去做别的优化更划算。6.2 线程安全这件事绕不过去前面所有代码都是单线程假设。一旦进入多线程环境问题立刻出现两个线程同时调用my_malloc同时读到链表头部同时修改最终有一个的修改丢失两个线程拿到同一块内存。sbrk本身在内核层面是原子的断点不会挪两次但用户态读断点—挪断点—更新池指针这一串操作不是原子的。所以哪怕只是最简单的 bump 分配多线程下也会出问题。最省事的解法是加一把全局互斥锁代价是所有分配串行化。更好一点的做法是每线程一个独立的池线程之间不共享也就没有竞争代价是内存总量上去了而且跨线程释放会有麻烦A 线程分配的块 B 线程释放落到了错误的池里。标准库走的是更复杂的分档加每线程缓存路线这也是它性能好的关键。我这个实现如果要往这个方向演进第一步应该是加锁保证正确第二步才是做线程局部优化。先正确再快这个顺序不能反。还有一个容易忽略的点fork之后子进程里的堆状态。子进程继承了父进程的整个地址空间包括分配器的全局状态这是没问题的但如果子进程里继续分配两边就各自独立演化了互不影响。这个行为符合预期不需要特殊处理但得知道。6.3 还能往下挖的几个方向这个实现作为一个起点往深处走有几条清晰的路。第一条是分档。把请求按大小分成若干固定档位比如 16、32、64、128……每个档位一个独立的空闲链表。分配时直接取对应档位的头部引入一个数组索引O(1) 完成。代价是内部碎片变大得在速度和空间之间找平衡点。第二条是从链表换成位图 边界标记。链表遍历在块多的时候会成为瓶颈改成用位图标记块的占用状态配合每块的头部存前后块大小合并时不需要遍历就能直接定位邻居。第三条是混合策略。小请求走sbrk扩展的堆大请求直接mmap独立映射释放时munmap立即归还。这就是标准库走的路也是实践中效果最好的组合。第四条也是我个人觉得最有意思的把分配器的统计数据暴露出来。当前堆大小、活跃块数、碎片率、峰值使用量这些数字在排查线上问题时价值极高。标准库虽然不直接给但通过/proc/self/maps和系统提供的调试接口能间接拿到自己写就有完全的控制权。最后分享一个我在实际使用中的体会这套东西真正的价值不在于你能不能写出一个比标准库更快的分配器而在于当你看到内存曲线异常的时候脑子里能立刻浮现出那张块链表的样子。知道free之后指针去了哪儿、知道断点为什么停在那里、知道那块 4KB 的空闲内存为什么没被用上——这种看得见的感觉是调库函数永远给不了的。我后来排查过好几次内存相关的线上问题靠的就是当年写这个简陋分配器时留下的直觉。如果你想动手建议从第一版开始把四个测试跑通然后故意制造几个错误——把ALIGN_UP的括号去掉、把HDR_SIZE改成不补齐的版本、把合并顺序倒过来——看看会崩成什么样。崩溃现场的观察比一次顺利的编译收获大得多。