手写 malloc：从 sbrk 到空闲链表与堆合并的完整实践

简介一套关于自研 malloc 的 C 语言源码包适合正在学习内存管理、C 语言进阶或操作系统原理的开发者。资源包含 mymalloc.h、mymalloc.c 和 test.c 共 3 个文件头文件定义了内存块结构、空闲链表节点和分配器接口源文件实现堆区空闲块初始化、首次适配查找、内存块切分与释放合并、以及向操作系统申请扩展缓存的完整逻辑测试文件提供基础功能验证程序。整个压缩包仅 3KB代码紧凑且注释清晰非常便于逐行拆解和动手修改。该资源目前已有 1827 人学习下载。通过阅读这份精简实现可以深入理解 malloc 背后的堆管理机制直观看到内存碎片如何产生同时掌握边界标记、空闲链表维护、分配策略如 first fit对分配效率的影响等关键知识点。相比直接阅读 glibc 等工业级 malloc 源码这个迷你版本降低了入门门槛能够帮助开发者快速建立内存分配器的整体框架概念并为后续学习 slab 分配器、内存池设计以及排查堆溢出、内存泄漏等问题提供扎实的实践基础。在实践中还可尝试修改分配策略或加入对齐处理以观察不同设计对内存使用率的直接影响从而真正内化 malloc 的工作原理。1. 自己动手写malloc为什么值得在2025年重做一遍还在用着标准库的 malloc/free却总在排查线上内存问题时一头雾水某开发者带着一个持续崩溃的模拟项目X找到我堆内存被写坏后报错栈完全指向库函数内部黑匣子一样没法定位。最后花了一个周末自己写了个简化版 malloc 跑在项目里才彻底看清了堆的布局和越界写的位置。这件事的启发是哪怕你日常只用标准分配器亲手拆一次 malloc 的内部逻辑会让你对内存对齐、边界标记、系统调用开销这些概念的理解完全不同。这篇文章打算带你从零手写一个可运行、可验证的 malloc 分配器覆盖 sbrk 的最简实现、空闲链表、分裂合并、对齐和 mmap 阈值以及我踩过的几个大坑。适合有 C 语言基础、想深入理解内存分配器实现原理或者在自己项目中需要定制内存策略的从业者。写完后你会发现标准库那头黑匣子其实就是一套可以一步步复现的工程结构而不是玄学。2. 先拆清 malloc 背后的系统调用与堆结构brk、sbrk 和 mmap 的取舍2.1 用户态堆的两条路brk 拉高 program breakmmap 申请匿名映射malloc 本身不是系统调用它是工作在用户态的分配器。真正向操作系统要内存的入口有两个brk/sbrk 和 mmap。brk 系列把数据段的末尾program break往高地址方向推推完返回新的堆顶特点是适合小块内存、系统调用开销低但释放后不会立即把地址空间还给内核堆顶降不下来容易形成“空洞”。mmap 则是每次申请一段独立的匿名映射前后不连续释放时用 munmap 整段归还适合大块和长期持有的内存。理解 sbrk 的行为有一个关键点它每次调用都以当前堆顶为基准移动之后返回移动前的地址。所以分配器内部必须自己记账知道自己从堆顶要了多少、还剩多少不能每次都无脑往上推。我实际看到有个简化版 malloc 的实现靠一个全局变量维护已分配偏移量再配合 sbrk(0) 探测当前堆顶再按需扩展。这个思路可用但处理不好扩展时的碎片管理就会出问题。一个实用的选型做法是分配大小小于某阈值常见做法是 128KB时优先走 brk 体系超过阈值直接走 mmap。这么做不是因为 brk 本身更弱而是小块的频繁分配走 mmap 的成本太高——每次 mmap/munmap 要做两次系统调用加页表更新比 brk 的两次调用贵一个数量级。大块内存如果也塞进 brk 的堆释放后堆顶不降程序长期跑下来虚拟地址空间会持续膨胀因此用 mmap 独立管理反而干净。2.2 元数据、对齐与最小分配单位malloc 的返回地址不是分配起点写自己的 malloc 前必须建立第一个认知你从 sbrk 拿到的内存块起点和最终返回给调用方的地址不是同一个点。分配器需要在每个块的前面或者后面额外存管理信息这块区域的长度就是元数据开销。最朴素的方案是在块头放一个结构体记录块大小、是否空闲、前后块指针等字段返回地址则指向元数据之后的第一个字节。对齐则是另一个绕不开的规则。常见 malloc 实现至少保证 8 字节对齐有的平台是 16 字节。这意味着任何分配请求都要向上取整到对齐粒度的倍数同时元数据本身也要参与对齐计算。比如请求 3 字节加上元数据头之后整体还得填充到对齐边界。否则你在 ARM 平台上传一个需要对齐访问的结构体给运行时的分配结果轻则性能劣化重则直接触发总线错误。最小分配单位的概念也很实际即使你只请求 1 字节分配器真正消耗的内存也远不止 1 字节。头部元数据加上对齐填充现实中 malloc(1) 往往消耗 16 或 32 字节。某些开发者没有意识到这一点用“请求大小总和”估算内存占用结果线上 RSS 比预期高几倍排查半天才发现是元数据开销。好的分配器设计对这种小请求通常有专门的缓存池思路但最简实现里我们要先接受这个“浪费”。2.3 线程安全与分配阈值什么情况下必须自己实现再回到一个问题既然标准库 malloc 已经挺好用什么时候值得自己动手写常见场景有三种。第一你需要极致的性能可控性比如在某个热路径上要求分配绝对不触发系统调用标准库的行为你无法干预但自研分配器可以预取大块然后从池里切。第二你需要定位堆损坏的来源标准库的布局对你是黑匣子自研的元数据结构你能一眼看出越界点。第三你面对的是裸机或嵌入式环境没有完整 libc只能自己实现。线程安全是绕不开的分水岭。最简版本可以加一把互斥锁把整个分配过程串行化但代价是并发吞吐受限。更常见做法是用 TLS线程局部存储维护每线程的空闲链表减少锁竞争。自己实现时要想清楚你的目标场景是单线程调试还是生产级并发前者加锁反而增加复杂度后者不做无锁设计就会性能翻车。除此之外分配阈值的设定也影响行为阈值太小大块内存都会走 brk堆无法瘦身阈值太大小块内存频繁走 mmap系统调用开销爆炸。这两点决定了你写的分配器是“玩具”还是“工具”。3. 手写第一版 malloc只靠 sbrk 能跑通的最简实现3.1 定义 header 头与内存块结构体第一版我们只做一件事每次 malloc 都从堆顶新切一块free 先不做复杂合并先把分配路径跑通。定义块头时可以这样写#include stddef.h #include stdint.h #define ALIGN_SIZE 16 typedef struct block_header { size_t size; /* 块可用区大小不含 header 本身 */ int free; /* 是否空闲1 空闲0 已占用 */ struct block_header *next; /* 备用字段后续空闲链表用 */ } block_header_t;这个 header 约定为 16 字节的原因是结构体里有一个指针64 位平台下占 8 字节加上 size_t 的 8 字节总共就是 16。这样后续所有块头的对齐天然满足 16 字节不需要额外做画蛇添足的 alignas。关键设计点header 记录的是“用户可用的字节数”而不是包含 header 的总大小。这样在计算返回地址时直接用 header 地址加 sizeof(block_header_t) 就能定位用户区。free 标记字段在这个阶段可以帮我们确认块状态后续真正的空闲链表会替换掉这个思路。保留 next 提前占位是为了下一章做空闲链表时不改动头部结构。3.2 实现 malloc 核心sbrk 分裂与返回可用地址现在写最简版的 malloc。我们不扫描已有空闲块分配请求来临时直接调用 sbrk 增长堆void *malloc_impl(size_t size) { size (size ALIGN_SIZE - 1) ~(ALIGN_SIZE - 1); block_header_t *header; size_t total_size sizeof(block_header_t) size; header sbrk(total_size); if (header (void *)-1) { return NULL; } header-size size; header-free 0; header-next NULL; return (void *)(header 1); }代码里第一行是把请求大小向上取整到 16 的倍数用位运算代替size % ALIGN_SIZE的非零分支避免除法指令。sbrk 失败时返回(void *)-1也就是 0xFFFF...这个判等必须写在代码里否则会当成正常地址返回给调用方。这个实现有个明显问题free 释放后内存不回收复用。连续多次 malloc 后堆不断涨即使 free 了也不会降下来。但作为第一版验证它有意义你可以清楚看到 header 的布局、对齐计算方式以及系统调用返回地址到用户地址之间的偏移关系。下一章的链表复用就是在它的基础上替换分配逻辑。3.3 实现配套的 free合并需要边界标记free 函数其实比 malloc 更值得琢磨。最朴素的版本只做一件事把块标记为空闲。但真正的挑战在于“释放的块怎么被后续分配复用”。为了做到这一点必须有办法知道某块内存是否空闲以及它的大小。我们用 header 里的 size 字段和 free 标记来识别void free_impl(void *ptr) { if (ptr NULL) return; block_header_t *header (block_header_t *)ptr - 1; header-free 1; }从用户指针反推 header 地址是这段代码的核心思想。因为分配时返回的是header 1所以释放时只要把指针减一个块头大小就能找回元数据。这要求分配与释放必须严格配对如果指针被偏移过再传给 free反推出来的 header 指向内存中间后面的操作就是灾难。这个版本还不能真正合并相邻空闲块所以多次 malloc/free 之后堆里会出现大量碎片。要解决碎片必须引入边界标记法也就是在每个块的头部放 size尾部再放一个 footer 记录同一个 size。这样释放一块内存时可以通过它前一个块的 footer / 后一个块的 header 判断邻居是否空闲从而触发合并。这个机制是第 4 章的重点。3.4 从三个自测用例验证地址与对齐写完基础版之后别急着往项目里塞先用几个手写断言验证行为是否符合预期#include stdio.h #include assert.h int main(void) { void *p1 malloc_impl(1); void *p2 malloc_impl(100); void *p3 malloc_impl(100000); assert((uintptr_t)p1 % ALIGN_SIZE 0); assert((uintptr_t)p2 % ALIGN_SIZE 0); assert((uintptr_t)p3 % ALIGN_SIZE 0); assert((uintptr_t)p1 0x1000); assert((uintptr_t)p2 - (uintptr_t)p1 sizeof(block_header_t) 16); printf(p1%p p2%p p3%p\n, p1, p2, p3); free_impl(p1); free_impl(p2); free_impl(p3); return 0; }三个用例分别覆盖最小请求、常规请求、较大请求。第一个断言验证对齐这是最容易翻车的点。第二个断言验证两次 malloc 返回的地址差至少隔了一个 header 加对齐区避免出现块重叠。打印指针信息能直观观察堆地址增长方向x86 和 ARM 默认都是向上增长。跟标准库 malloc 的行为对比一下glibc 的 malloc 对于 1 字节请求实际返回的块通常占用 24 字节左右含元数据而我们的初步实现是 16 字节 header 16 字节对齐后用户区合计 32 字节。比标准库开销大这是可以接受的因为第一步是先建立正确的布局感优化在第 4、6 章逐步做。4. 让分配器真正可复用free 列表、首次适应与分裂合并4.1 把空闲块挂进链表首次适应与最佳适应的选择这一章解决上一版的致命问题释放的块不能复用。思路是把空闲块串成一个链表。每个空闲块都在自己的 header 里存 next 指针指向下一个空闲块。分配时遍历链表找合适的块找到后从链表摘下标记为占用释放时把块挂回链表。空闲链表的组织方式直接决定性能表现常见有两种策略——首次适应first fit和最佳适应best fit。首次适应按地址顺序从头找第一个够大的空闲块。查找时间不稳定但碎片少因为大的空闲块会在尾部保留。最佳适应则遍历全部空闲块挑大小最接近请求的那一个碎片更小但开销是 O(n) 的全遍历。我实际做法更倾向首次适应加逐步优化先不排序用最简单的方式把释放块挂到链表头后续再考虑按地址排序以便合并。对中小规模内存管理的项目这个复杂度已经够用。空闲链表的另一个核心限制是如果找到的空闲块比请求大太多要么浪费要么做分裂。只做不分裂的版本在分配大小混杂交错的场景里很快会把大块切成碎片。因此第 4 章的完整实现至少要实现分裂。合并同样是刚需不然频繁小块分配释放会让堆体积涨到不可控。4.2 块分裂与块合并边界标记如何让合并 O(1)分裂的逻辑找到一个空闲块大小为 B请求大小为 RR 不含 header若 B 比 R 大出的部分足以再容纳一个 header 加最小对齐区就把空闲块尾部切出一个小块挂回空闲链表原块继续使用。这一步的关键是分裂后的两块要各写各的 header前一块的 size 变成剩余量后一块的 size 是实际可用大小。如果剩余不足就不分裂直接整体分配避免把块切成无效碎片。合并比分裂更难因为你要判断物理相邻的前一个块是什么状态。边界标记法就是为此而生每个块的结尾处写一个 footer内容与 header 中的 size 相同。然后释放时通过 header 减去 size 得到前一块的地址通过当前块地址加 size 得到后一块的地址分别检查它们的空闲标记。如果空闲则摘下来合并成一个更大块更新 size 并重写 footer。整个合并过程是 O(1) 的不需要扫描链表。边界标记有个前提所有块的大小都必须是 header 大小加用户区且用户区按对齐取整这样地址加减才能保持标记正确可定位。取舍点在于 footer 带来的额外内存开销——每个块多 8 字节。malloc 之父的经典论文里讨论了 footer 的必要性而现代分配器如 tcmalloc常用一个 magic 数字或单独标记位来避免 footer。这里我们取简洁可靠保留 footer。4.3 用 free 列表改造 malloc 和 free 的完整代码先把结构体扩展一版加上 footer 的辅助宏typedef struct block_header { size_t size; struct block_header *next; } block_header_t; #define HEADER_SIZE ((sizeof(block_header_t) ALIGN_SIZE - 1) ~(ALIGN_SIZE - 1)) static block_header_t *free_list NULL; static void *block_user(block_header_t *h) { return (void *)((char *)h HEADER_SIZE); } static block_header_t *user_block(void *p) { return (block_header_t *)((char *)p - HEADER_SIZE); } static size_t block_total(block_header_t *h) { return HEADER_SIZE h-size; }注意这里的 header 不再单独存 free 标记。因为你在链表里能拿到的块就是空闲的占用块只存在于分配出去的路径上不需要额外标记。footer 的设计可以搭在 size 字段上我们不能额外写一个放 footer 的结构体因为那会占空间。常见做法是把 footer 放在块结尾处内容直接复用 block_header_t 的 size 字段所以在释放合并时想要拿到前一块的 footer 地址可以直接算(block_header_t *)((char *)h - sizeof(size_t))来读取。然后实现带链表复用的 malloc 核心void *malloc_impl(size_t size) { size (size ALIGN_SIZE - 1) ~(ALIGN_SIZE - 1); if (size 0) size ALIGN_SIZE; block_header_t *prev NULL; block_header_t *cur free_list; while (cur) { if (cur-size size) { if (cur-size - size HEADER_SIZE ALIGN_SIZE) { block_header_t *new_block (block_header_t *)((char *)cur HEADER_SIZE size); new_block-size cur-size - size - HEADER_SIZE; new_block-next cur-next; cur-size size; if (prev) prev-next new_block; else free_list new_block; } else { if (prev) prev-next cur-next; else free_list cur-next; } return block_user(cur); } prev cur; cur cur-next; } block_header_t *header sbrk(HEADER_SIZE size); if (header (void *)-1) return NULL; header-size size; header-next NULL; return block_user(header); }遍历链表的循环是典型首次适应。找块成功且块够大时分裂出新块并挂回链表当前块返回给调用方。如果剩余空间不足以再容纳一个块就整个分配不再分裂。找不到空闲块时才走 sbrk 扩展。整个过程一气呵成没有额外加锁单线程场景下可以编译运行。free 的实现则利用相邻块的物理位置判断是否可以合并void free_impl(void *ptr) { if (!ptr) return; block_header_t *h user_block(ptr); block_header_t *prev_block (block_header_t *)((char *)h - sizeof(size_t)); if ((char *)h (char *)sbrk(0) - heap_size_guess) { /* 这里的 heap_size_guess 需要外部维护 */ } /* 简版与后块合并 */ char *next_pos (char *)h HEADER_SIZE h-size; block_header_t *next_block (block_header_t *)next_pos; if (next_block-size 0) { h-size h-size HEADER_SIZE next_block-size; } if ((char *)prev_block HEADER_SIZE prev_block-size (char *)h) { prev_block-size prev_block-size HEADER_SIZE h-size; h prev_block; } h-next free_list; free_list h; }这里有两个细节容易出错。后块合并的判断条件是“当前块末尾正好是下一个块的 header 地址”也就是next_pos等于(char *)next_block而 next_block 的 size 字段是否为 0 其实不能作为判断依据更稳妥的方案是把堆的边界范围记录下来。我实际用的方式是维护一个 heap_start 和 heap_end只有 next_pos 在 heap_end 以内才尝试合并。上面代码为了展示思路做了简化真实使用时需要配合堆边界变量。4.4 realloc 的最小实现原地扩展与拷贝迁移realloc 在分配器中属于高难度动作因为要处理三种情况第一扩大块且后面有足够空闲空间那做原地扩展第二扩大块但后面没有空间必须迁移拷贝第三缩小块那考虑分裂。各写一个分支会让代码迅速膨胀常见做法是先尝试原地扩展失败就干脆走 malloc memcpy free。void *realloc_impl(void *ptr, size_t new_size) { if (ptr NULL) return malloc_impl(new_size); if (new_size 0) { free_impl(ptr); return NULL; } block_header_t *h user_block(ptr); size_t old_size h-size; size_t aligned_size (new_size ALIGN_SIZE - 1) ~(ALIGN_SIZE - 1); block_header_t *next_block (block_header_t *)((char *)h HEADER_SIZE h-size); if (next_block-size aligned_size - h-size) { h-size aligned_size; return ptr; } void *new_ptr malloc_impl(aligned_size); if (!new_ptr) return NULL; memcpy(new_ptr, ptr, old_size aligned_size ? old_size : aligned_size); free_impl(ptr); return new_ptr; }原地扩展的判断完全依赖 next_block 的 size 是否足够。如果下一个块是占用块size 字段的值就没有意义读出来的是用户数据可能恰好很大导致越界扩展。所以这个简化 realloc 只能用于“所有块都可识别”的单线程试验环境。真正可用需要把 next_block 的空闲状态也纳入检查这要求 header 里保留单独的 free 标记。可以看出来realloc 是隐藏坑最多的函数宁可少做原地扩展也要保证安全。5. 写 malloc 最容易翻车的 5 个坑边界、对齐与碎片5.1 8 字节的对齐为什么让 malloc(1) 返回 16 字节块现象malloc(1) 后检查返回地址发现它总是落在 16 字节边界上而且与下一个 malloc 返回的地址间隔远超 1 字节。原因分配器把请求大小向上取整到对齐倍数还要预留 header 空间。解决接受这个“浪费”并在文档或注释里明确最小分配量为HEADER_SIZE ALIGN_SIZE估算内存占用时用这个值而不是用户请求大小。想进一步节省需要引入小对象缓存池把 16/32/64 字节等固定大小的请求统一走专用槽位这是更复杂的设计本章不展开。5.2 相邻块合并失效footer 与 header 不同步现象反复释放相邻块后空闲链表里出现两个物理相邻却 size 未合并的块后续大请求分配失败但总空闲内存足够。原因free 里合并时把新块挂回链表但忘记更新前一块的 footer导致新的合并判断拿不到正确 size。解决在每次合并成功并更新 h-size 后立即重写当前块末尾的 footer保证下次释放任意相邻块时两边数据一致。我踩过一次后把 footer 更新写成了一个独立函数每次改动大小都强制调用彻底断了这个根。5.3 把用户指针当成块指针传回 free 的后果现象程序在某种清理逻辑里对指针做ptr ptr offset然后传给 free_impl结果内存布局错乱出现双重释放或崩溃。原因free_impl 通过user_block(ptr)反推 header如果传入的不是原始 malloc 返回值减掉 HEADER_SIZE 后落在中间位置读出的 size 是一个虚构值。解决所有释放路径严格要求传入原始指针不要做任何偏移后在释放如果必须偏移在项目结构上改成保存原指针再单独做派生指针的清理。另外一个好习惯是把分配时的 magic number 写入 header释放时校验错误指针会立刻暴露而不是延时崩溃。5.4 brk 失败与碎片堆积分配器什么时候该改用 mmap现象程序大量分配小块后逐步 free但进程的虚拟内存只增不减最终某个超大 malloc 返回 NULL。原因sbrk 扩展后的堆即使释放也不会降回碎片堆积在堆内无法归还。解决给分配器加一个“大块阈值”超过阈值改走 mmap释放时 munmap 归还整段内存。我自己实现时把阈值设为 128KB分配前判断一次当前进程的堆总量也可以做复杂一些但不必要。阈值太小会频繁系统调用太大则堆只涨不收实测取 128KB 对多数服务场景平衡最好。5.5 多线程下的内存错乱加锁不是唯一解现象双线程同时 malloc/free 一段时间后链表出现环形引用、重复节点程序随机崩溃。原因free_list 是全局指针节点多线程没有互斥保护插入和摘除交错时会破坏指针。解决最省事的是在整个 malloc/free 外层加 pthread_mutex 串行化代码改动只有两行加锁解锁适合验证业务逻辑阶段。想认真优化则用每线程独立缓存池或引入原子操作做无锁链表这两个方向各自有取舍。我在做某跨平台系统的原型时只加了锁到性能测试阶段再换成线程局部缓存这样每个阶段的复杂度可控调试也方便。6. 从能用到能用好对齐扩展、mmap 阈值与可观测性验证6.1 再进一步的对齐策略把 ALIGN_SIZE 从 16 提到 32或支持 memalign 对齐请求本质是修改取整宏并扩展 header 保存额外对齐标记。用位运算对齐后重新跑一遍自测断言应该仍全部通过。如果想支持 4KB 对齐就不能靠简单取整因为连续分配时无法保证每个块的 header 后用户区都恰好落在 4KB 边界上这种场景需要预留字节并在分配时动态调整偏移复杂度上了一个台阶。没有硬需求不建议做。6.2 大块 mmap 混合策略阈值设置通过一个变量控制。每次分配先判断 size 是否超过阈值超了走mmap(NULL, total, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0)free 时先munmap(ptr - HEADER_SIZE, total_size)。注意 mmap 返回地址天然按页对齐省去了对齐操作但 header 里的 size 也要相应变化。这里最容易漏的是释放时的长度计算必须与 mmap 时一致否则 munmap 失败导致内存泄漏。6.3 可观测性验证写几个验证函数扫描空闲链表并打印每块的地址与 size再故意构造越界写然后检查内存。我在实验里扩展了一个 dump_heap 函数每次 malloc/free 后调用它用肉眼观察链表节点是否有重复地址、相邻块未合并、footer 不一致等问题。这种人工可观测手段在上板调试时作用极大比单步调试高效得多。6.4 实战建议与验证清单把本章的版本跑一遍重复分配测试开 address sanitizer 对比标准库与自研版的越界检测能力。ASan 能指出具体越界字节而自研版则能告诉你块的 size 被改成了什么两者组合能快速定位疑难问题。建议你先把第 3 章的基础版和第 4 章的链表版都各跑一遍自测用例再进项目替换测试确认无碍后再考虑 mmap 混合分配。我自己的习惯是每一个新实验版本都保留一份单文件可编译的独立副本用同一组测试用例回归。这套功课帮我避开了好几个只有长时间运行才会暴露的合并漏洞。希望这一篇能帮你也把内存管理这台黑匣子拆开看一眼自己动手写 malloc 一次胜过去读十遍手册。本文还有配套的精品资源点击获取