探秘 `malloc`：超量分配背后的内存分配器难题与技术权衡！

深入探究为何 malloc 超量分配实现内存分配器竟有这么多难题2026 年 7 月 20 日阅读时长 11 分钟。几乎所有人在编写“安全”的 C 程序时都见过这样一行代码void *p malloc(13);我们知道这行代码的作用至少知道其目的请求 13 字节获得 13 字节。出于好奇在某个周五开始研究这个问题时我也是这么想的。然而在还没写一行代码的 30 分钟后我就意识到这种情况几乎不会发生。这简单的一行代码在底层其实涉及到了许多有趣的计算和内存分配操作。例如当请求 13 字节时实际预留的内存结构如下-------------------------------------------- | 头部 | 回指指针 | 填充 | 用户内存 | --------------------------------------------用户内存是我们唯一会使用的部分*p 返回的就是这块内存的起始地址。而其他部分只是存在那里并不会被使用。这是为什么呢我也有同样的疑问。与其空谈理论不如来构建一个内存分配器和释放器。最简单的内存分配器最简单的内存分配器甚至没有 free() 函数它被称为“指针偏移分配器”bump allocator。你需要预先给它一大块内存一个内存池arena每次分配只需将指针向前移动即可。typedef struct { uint8_t *cursor; uint8_t *limit; } Arena;cursor 是下一次分配的起始位置limit 是内存池的结束位置。这就是整个设计思路。void *bump_alloc(Arena *a, size_t size) { if (a-cursor size a-limit) return NULL; // 内存不足 void *ptr a-cursor; a-cursor size; return ptr; }就是这么简单。指针只能一直向前移动这是最快的分配器。但从功能上来说它对于长期运行的程序没什么用因为没有 free() 函数。你只能一次性释放整个内存池而不能释放其中的单个对象。这就引出了一个明显的问题如果不能释放单个对象那我怎么收回那 13 字节呢事实证明以这种设计是做不到的。要实现单个对象的 free() 功能分配器需要记录每次分配的相关信息。从这时起元数据就变得不可或缺了。为什么需要元数据free(ptr) 函数只接受一个参数即一个指针。如果分配器的任务是回收这块内存并使其可再次使用它就必须回答一个调用者从未告知的问题这次分配的内存有多大它实际从哪里开始唯一的解决办法是将答案存储在分配器之后能找到的地方而且只能通过 ptr 本身来查找。最明显的位置就是在分配给用户的内存之前。typedef struct { size_t size; } Header;所以现在 alloc() 函数不再只是返回原始内存而是这样操作[ 头部 ][ 用户内存 ] ^ 返回给调用者而 free(ptr) 函数则需要向后查找Header *h (Header *)ptr - 1; // 现在 h-size 告诉我们这个内存块有多大这是一种简单直接的方法但还有更多需要考虑的地方。简单头部与内存对齐的问题并非所有类型的数据都能存放在任意地址这就是所谓的“内存对齐”alignment。char 类型的数据对内存位置没有要求对齐值为 0。double 类型的数据在大多数平台上要求其起始地址是 8 的倍数对齐值为 8。不同类型的数据还有更多不同的对齐要求。虽然在使用不同对齐方式时程序编译不会受到严格限制但这可能会影响性能甚至导致程序意外崩溃。所以alloc() 函数不仅要返回一个指针还需要返回一个针对调用者要存储的数据类型正确“对齐”的指针。这意味着头部结束位置和用户指针实际起始位置之间可能会有一个间隙而且这个间隙的大小每次都不同取决于所请求的对齐方式。这个间隙就是所谓的“填充”padding。[ 头部 ][ ...可变填充... ][ 用户内存 ]这就是 header (Header *)ptr - 1 方法失效的原因。这种减法操作假设从 ptr 到头部的距离是固定的但填充的大小是可变的每次分配都不同。free() 函数无法知道针对这个特定指针插入了多少填充字节因此无法可靠地向后查找头部信息。回指指针的作用如果到头部的距离不固定那就不要依赖距离而是在一个固定位置存储一个指向头部的“回指指针”Back Pointer。[ 头部 ][ ...可变填充... ][ 回指指针 ][ 用户内存 ] ^ 始终在用户内存前 sizeof(void*) 字节处 无论前面有多少填充字节现在free() 函数不需要知道或重新计算填充字节的数量只需这样操作Header *h *(Header **)((uint8_t *)ptr - sizeof(void*));这个位置始终在用户指针前 sizeof(void*) 字节处无论对齐方式如何。头部可以位于任何位置距离多远都没关系回指指针只需指向它即可。到底是哪个指针需要对齐等等需要对齐的不是“内存池的指针”而是“用户指针”也就是实际返回给调用者的指针。内存池指针可以位于任意位置因为没有人会直接对其进行解引用操作。所以实际的计算过程如下候选地址 头部 sizeof(Header) sizeof(void*) 填充字节 对候选地址进行对齐操作 用户指针 候选地址 填充字节填充字节的数量也会存储在头部主要是因为这在后续的调试和测试中很有用你可以通过检查 user_ptr - 填充字节 是否正好回到候选地址来进行合理性检查。内部碎片问题当实现了头部、回指指针和内存对齐功能后看着内存布局一个明显的问题出现了元数据和实际对象之间的那些填充字节在整个分配周期内都闲置着为什么分配器不能重新使用它们呢因为分配的内存必须是一个连续的块。调用者被承诺从 user_ptr 开始有 N 个连续的字节如果说“这是你的内存但中间这 3 个字节属于其他东西”就会破坏分配的基本规则。所以这些字节虽然被分配了即它们属于这个内存块不能再分配给其他对象但实际上从未被使用过。这就是“内部碎片”internal fragmentation它是由于对齐要求而产生的浪费存在于每个需要填充的分配操作中。如何释放已分配的内存在大多数语言如 Python、Golang中解释器或编译器内部有一个称为“垃圾回收器”garbage collector的组件它会检查内存的生命周期如果内存超出作用域或不再使用就会清除其占用的空间。但在像 C 这样的老语言中必须手动释放已分配的内存这有一套规则需要单独写一篇博客来详细介绍。有了头部和回指指针后free() 函数终于可以实现了。但“指针偏移分配器”仍然无法做到这一点因为它没有内存重用的概念。所以设计需要改变不再使用只能向前移动的指针而是需要一个“空闲列表”free list这是一个由已释放的内存块组成的链表这些内存块可以再次被分配。typedef struct FreeNode { size_t size; struct FreeNode *next; } FreeNode;free(ptr) 函数通过回指指针找到头部然后将其添加到空闲列表的头部void push_free(FreeNode *node) { node-next free_list; free_list node; }现在alloc() 函数有两条路径遍历空闲列表查找足够大的内存块search_free。如果没有合适的内存块就回到原来移动指针的分配方式。“首次适应”first-fit是最简单的搜索策略即选择第一个足够大的内存块不用想得太复杂。更复杂的策略如“最佳适应”、按大小类划分的隔离列表会陷入更深的技术细节但“首次适应”足以证明这个概念是可行的。内存块分割我实现的第一个版本的内存分配器有一个很傻的问题。如果它找到一个足够大的空闲内存块即使只需要其中一小部分也会把整个内存块都分配出去。请求8 字节 空闲内存块 ------------------------------------------- | 200 字节 | ------------------------------------------- 结果 ------------------------------------------- | 所有 200 字节都被占用 | -------------------------------------------程序只使用了前几个字节但剩下的 192 字节在这个分配被释放之前无法被其他对象使用这就造成了内存浪费。解决办法是“分割”splitting。不再把整个内存块都分配出去而是把它切成两块。分割前 ------------------------------------------- | 空闲内存块 | ------------------------------------------- 分割后 ------------------------------------------ | 已分配内存 | 仍空闲的内存 | ------------------------------------------前面的部分成为分配的内存剩下的部分直接放回空闲列表等待下一个请求。说起来容易做起来难。我第一次实现时不小心把第二个内存块的起始位置弄错了。我忘记了第一个内存块的元数据也会占用空间没有在第一个内存块完全结束后再创建第二个内存块而是提前了一点。这个 bug 花了一段时间才找到因为分配器并没有立即崩溃而是在悄悄损坏自己。另一个经验是要知道“何时不进行分割”。假设分割后只剩下很少的字节这其实不能算一个新的空闲内存块只是一些零碎的空间。如果剩余的空间甚至不足以描述自身那就没有必要保留它。所以有时候浪费几个字节比创建一个永远无法再使用的小内存块要好。我把这个限制称为 min_split_size。内存块合并把碎片重新组合起来内存块分割会产生更小的内存块但最终会出现相反的问题。想象一下把一张纸剪成很多小碎片即使你总的纸张数量足够但可能没有一块碎片大到能满足你的需求。内存也是一样的道理。假设我分配了两个内存块---------------- | a | b | ----------------后来这两个内存块都被释放了---------------- | 空闲 a | 空闲 b | ----------------它们在内存中是相邻的合起来足够进行一次更大的分配。但我的分配器仍然认为它们是两个独立的内存块。所以如果有人请求一个比单个内存块都大的内存需要32 字节 可用内存 16 字节 16 字节分配会失败尽管总的内存是足够的。解决办法是“合并”coalescing这只是一个专业术语意思是把相邻的空闲内存块重新组合起来。合并前 ---------------- | 空闲 a | 空闲 b | ---------------- 合并后 ----------------- | 一个大内存块 | -----------------找到右边的内存块很容易因为每个内存块都知道自己的大小也就知道前一个内存块的结束位置但它们都不知道前一个内存块的起始位置。解决办法出奇的简单把大小信息写两遍一遍写在内存块的开头一遍写在结尾。------------------------- | 头部 | 数据 | 尾部 | -------------------------现在站在任何一个内存块的起始位置我都可以查看前一个位置从其尾部读取前一个内存块的大小然后直接跳到它的头部。只有这样我才能在两个方向上合并内存块。这是那种解决一个问题却又引入更多元数据的情况之一这和我一开始想让分配器“更精简”的预期完全相反。总结最初只是想“自己实现一个 malloc”但很快就陷入了一系列的权衡之中。引入内存对齐带来了填充字节的问题从此陷入了一个又一个的技术难题每个解决方案在解决一个问题的同时又会引入新的问题。这可能是我从这个项目中学到的最重要的一点。…更多有趣的内容以下内容没有包含在正文里但可能是我从中学到最多的 bug。bug #1“等等……为什么程序会崩溃”实现内存块分割后一切看起来都正常。然后我用 -fsanitizeundefined 选项编译程序出现了如下错误运行时错误对类型 struct FreeNode 进行成员访问时地址 0x61d000000173 未对齐该类型需要 8 字节对齐我首先想到的是“这没道理啊我已经对每个分配都进行对齐操作了。”结果发现我对齐的是“用户指针”而不是“剩余内存块的头部”。当一个大内存块被分割时我只是在剩余字节的起始位置直接放置一个 FreeNode 结构体。FreeNode *remainder (FreeNode *)((uint8_t *)header sizeof(FreeNode) needed);有时这个地址不能被 8 整除有时又可以这就解释了为什么这个 bug 只是偶尔出现。解决办法很简单在将剩余内存块视为 FreeNode 之前先进行对齐操作。之后这个检查工具安静了大约五分钟。bug #2400 次操作后出现内存损坏这个 bug 是最严重的。我的压力测试进行了数千次随机的内存分配和释放操作。一切看起来都正常但在数百次操作后一个从未被触及的内存分配突然损坏了。原因其实很简单我只在释放内存块或分割内存块时写入尾部信息普通的内存分配操作从未写入尾部信息。所以很久之后当进行合并操作时程序会读取尾部位置的随机字节这些随机字节被当作随机的内存块大小进而得到一个随机的指针。解决办法是每次内存块大小改变时都要写入尾部信息一定要这样做