简介这份资源是自己动手实现 malloc 的配套代码包适合希望深入理解 C 语言动态内存管理的开发者和学生。资源以 my_malloc 为主线展示如何基于堆与空闲链表完成内存块分配、释放与合并并附带测试程序用于验证效果。全部共 3 个文件包含 2 个 C 源文件和 1 个头文件一个源文件实现分配器核心逻辑另一个用于测试运行效果头文件则提供接口声明压缩包仅 3KB结构简洁便于快速阅读和二次改造。目前已有 1825 人学习下载。通过分析这些代码可以掌握内存池初始化、首次适配、块拆分与合并等关键实现技巧也能从 malloc 的使用者进阶为内部机制的理解者是一份轻量而实用的入门资料。 干我们这一行的可能都动过“自己实现一遍malloc”的念头。但真正去动手的人不多多数人翻几页《深入理解计算机系统》就放下了觉得这是操作系统和编译器大神的事。我劝你把它捡起来因为亲手写一个malloc函数哪怕只是一个教学级的简化版你对指针、内存布局、系统调用乃至整个程序运行时状态的理解都会发生一次质变。这篇博客我就把完整的实现思路、代码和踩坑记录拿出来从零开始拆给你看行文里的代码可以直接抄抄完你跑一遍会比看十篇文章都管用。我自己是在处理一个线上程序频繁崩溃的下午决定写它的。当时那个应用没有任何段错误的征兆gdb进去一看堆区被改得乱七八糟malloc内部的数据结构被踩了。追了几条调用链发现问题的根子在于我对这块内存到底是怎么被管理的并没有形成直觉。后来花了两个晚上参照KR的思路手写了一个可以跑、可以测、也可以继续扩展的分配器从那以后再看这类问题脑子里的路径就清楚多了。我也建议任何写C/C的开发者或者正在学习操作系统原理的人都把这个项目做一遍。这不是造轮子而是为了在真正调试内存问题时你能瞬间意识到“这里可能会踩到header”“那里的空闲链表断掉了”“为什么堆顶有这么大一块空洞”。下面这份实现是基于隐式空闲链表加上首次适配策略做的。它不追求极致性能也不追求花哨的分离适配一切以“结构清晰、逻辑可验证”为第一优先级。我会把设计原因、代码细节、测试方案和常见坑位全部铺开保证你照着走能真正收获一个属于自己的malloc函数版本。1. 动手之前的设计决策先想清楚分配器要干什么1.1 核心问题拆解malloc到底在管理什么很多人以为malloc就是一个“拿内存”的函数其实不然。它要做的事远比“给我一块内存”更底层它要把操作系统通过系统调用已经分配给进程的那段连续、平坦的地址空间切成一个个不同大小的块然后根据调用者的请求去寻找一个合适的块、返回其中的一部分同时做好记录等free来回收。整个过程涉及三个核心问题第一怎么记录内存块的元数据。每个块是从哪个地址开始、有多大、当前是空闲还是已被占用这些信息必须有个地方存而且要高效。第二怎么在空闲块中选中一个满足size要求的块以及一个块放不下时是否要拆开。第三free的时候怎么把这块内存重新交回分配器并且能否和相邻的空闲块合并减少碎片。这三个问题对应着数据结构的选择和算法策略。我最终选了一条最简单也最经典的路径隐式空闲链表用“包头物理顺序串联”的方式把堆区想象成一句话接一句话的段落每次分配都从头遍历找第一个足够大的空闲段找到就切块切剩余部分当新空闲段free时标记为空闲然后检查前后物理相邻的块是否空闲是则合并。这个方案被KR的教材讲过被无数操作系统课程用过它不聪明但极度正确而且非常适合作为理解malloc内部机制的入门版本。1.2 系统调用选型sbrk为什么比mmap更合适真正从操作系统手里拿地址空间有两个入口sbrk/brk和mmap。sbrk的语义极简它可以通过传入一个增量来扩大或收缩进程堆区返回旧堆顶地址。这也是早期UNIX系统里malloc的主要实现方式。mmap则更现代化可以按页映射任意一块内存glibc在分配大块内存时就会直接用mmap因为它可以在free时整块归还给操作系统避免长期持有大块但用不上的内存。我的教学版选择sbrk核心原因是逻辑足够简单。你不需要处理页对齐、不需要维护映射表关系只要把sbrk返回的地址当作一块新的连续空间追加到链表尾部就行。这也更接近“你手上有1GB的连续内存现在我来管理它”的直觉。等你把这一版写通透了再去看glibc的多级分配器就顺理成章。需要提醒的是sbrk并不是线程安全的也不是如今高性能系统的首选所以这个版本本质上是个“单线程教学版”。要是你直接把它搬进多线程程序请一定加锁或改用mmap加原子操作否则很快就会踩到并发问题。这个我在第5章会展开讲。1.3 数据结构对比为什么选隐式空闲链表主流的空闲块管理方式有隐式链表、显式链表、分离适配等几种。方式分配时间复杂度free的时间复杂度合并相邻块实现复杂度隐式链表O(n)需要从头遍历O(n)标记空闲合并也要找相邻块方便但需要额外查找低适合学习显式空闲链表O(n)但只遍历空闲块通常更快O(1)插入空闲表相对麻烦需要边界标记或额外搜索中分离适配如slab接近O(1)按size分桶O(1)看具体实现高我的取舍逻辑很简单第一版优先保证实现正确、bug可肉眼排查。隐式链表天然使用了物理顺序所以合并相邻块时非常直观——你只需要拿到当前块地址加上当前块大小就定位到物理邻居了。而显式空闲链表虽然free很快但合并时需要额外的手段判断前后物理块是否空闲初次实现容易一脸懵。你用隐式链表先把所有逻辑跑通再考虑性能问题绝对不晚。2. 核心数据结构设计块头是整个分配器的灵魂2.1 块头设计与最小块约束在隐式链表里每个内存块都遵循同一个布局前面是固定大小的“块头”存放块的总大小和是否空闲两个字段块头之后是给调用者使用的数据区。这里有个关键点块头所记录的size是包含块头本身在内的总大小不是用户请求的bytes。这样设计的好处是当遇到一个块指针hd时下一块的地址直接就是(char *)hd hd-size。想找前一块则需要从头遍历到当前块。代价是分配时需要多遍历一些节点但换来了极简的物理寻址方式值。我当时第一次写就栽在了最小块约束上。你设想一下如果某次分配后剩余的空间只有6个字节而块头就有16字节那这个“空闲块”根本无法记录自己的元数据。所以必须设定一个下限如果一个块被分割后剩余部分连“块头8字节数据”都放不下就不要分割整个块整块分配出去。我代码里把MIN_BLOCK设置成header大小16表面上看是浪费了最后十几个字节实际上等于用微不足道的空间换取了链表的完整性和安全性。2.2 对齐问题别让你的返回地址惹怒CPUmalloc返回的指针需要满足最严格的对齐要求。在64位系统上通常需要8字节对齐部分平台要求16字节对齐。如果返回了未对齐的指针程序里只要出现把指针强制转成double或long long就会异常严重的直接总线错误。实现上我用了一个union保证块头大小是对齐的整数倍。这个设计非常讨巧union的成员要么是结构体要么是long。long本身就是8字节对齐的所以整个header_t的大小永远是8的倍数而block又是按header_t数组的方式推进的因此每一个数据区的起始地址天然就是8字节对齐。#include stdio.h #include stddef.h #include unistd.h typedef union header_t { struct { size_t size; // 当前块总大小包含header int is_free; // 1表示空闲0表示已分配 } s; long align; // 强制让块头按8字节对齐 } header_t; #define HEADER_SIZE sizeof(header_t) #define MIN_BLOCK_SIZE (HEADER_SIZE 16) static header_t *heap_base NULL;这段代码是整个分配器的地基。后续所有逻辑都是在这块“账本”上做文章。heap_base指向堆区起点它是全局唯一的链表头。3. 从零实现逐段拆解malloc和free3.1 向操作系统要内存扩展堆区分配器再聪明手上的空间用完了也得找系统要。扩展堆区的逻辑很简单先看现在的堆顶调用sbrk把堆顶抬高一段距离然后把这块区域包装成一个空闲块返回。不过这里我加了一个优化如果堆顶刚好就是一个空闲块那就别额外新增块了直接原地扩大它的size这样能显著减少堆顶碎片的堆积。这里还有个细节。第一次调用malloc时heap_base还是NULL需要先创建初始链表节点。后续扩展时新块会自然接在已有链表的物理末尾不需要额外的指针修改。static header_t *request_space(size_t size) { if (size MIN_BLOCK_SIZE) size MIN_BLOCK_SIZE; // 如果堆顶本身就是空闲块则原地扩展它 if (heap_base) { header_t *top heap_base; while ((header_t *)((char *)top top-s.size) (header_t *)sbrk(0)) { top (header_t *)((char *)top top-s.size); } if (top-s.is_free) { top-s.size size; return top; } } header_t *block (header_t *)sbrk(0); if (sbrk((intptr_t)size) (void *)-1) { return NULL; } block-s.size size; block-s.is_free 1; return block; }这里用了sbrk(0)来获取当前堆顶地址再用sbrk(size)申请空间。注意sbrk参数是intptr_t某些编译器直接传size_t可能警告转换一下更干净。3.2 mymalloc核心遍历查找与块分割分配的过程分三步走计算实际需要的size用户数据加header并且不小于最小块、从头遍历链表找第一个满足条件的空闲块、如果找不到就调用request_space扩展。找到空闲块后还有关键一步分割。如果块的大小减掉需要的size后剩下的空间仍然能容纳一个最小块就segment拆成两个块一个给用户一个作为新的空闲块留在链表中。如果不满足就整体分配宁可让用户多占几个字节也不能制造无法管理的碎片。void *my_malloc(size_t bytes) { size_t need HEADER_SIZE bytes; if (need MIN_BLOCK_SIZE) need MIN_BLOCK_SIZE; header_t *cur; if (!heap_base) { cur request_space(need); if (!cur) return NULL; heap_base cur; } else { // 首次适配从头遍历物理链找第一个足够大的空闲块 cur heap_base; while ((void *)cur sbrk(0)) { if (cur-s.is_free cur-s.size need) break; cur (header_t *)((char *)cur cur-s.size); } // 整个链表没有合适的空闲块扩展堆区 if ((void *)cur sbrk(0)) { cur request_space(need); if (!cur) return NULL; } } // 分割块剩余空间还能当新块用才分割 size_t remain cur-s.size - need; if (remain MIN_BLOCK_SIZE) { header_t *next_block (header_t *)((char *)cur need); next_block-s.size remain; next_block-s.is_free 1; cur-s.size need; } cur-s.is_free 0; return (void *)((char *)cur HEADER_SIZE); }这段代码看起来简单其实有两个非常容易被忽略的陷阱。第一个是遍历时用(void *)cur sbrk(0)判断是否越界这个写法在物理链上有效但如果在块内做指针加法时size被外部踩坏这个判断依然可能走进野地址。这也是为什么调试malloc问题时第一件事永远是怀疑哪个指针越界写了header。第二个陷阱是分割条件我最初用了一个固定值而不是MIN_BLOCK_SIZE结果分割出一个大小为8字节的块那块的header能写但数据区太小后面一旦被复用就脊背发凉。不要在这个条件上省空间。3.3 myfree与相邻合并把碎片缝起来free的核心任务有两个把块标记为空闲以及尽可能合并物理相邻的空闲块。合并是为了防止这样一类碎片化场景——你依次申请A、B、C三块内存然后释放A和C剩下B占用此时堆顶方向空出一大块但A和C各自都小于你要的新内存只有把它们都合并起来才能满足需求。由于我在free里把块标记成空闲后紧接着就要判断前后邻居是否空闲所以我采用了一点小技巧从头遍历整个物理链表找到当前块的物理前驱。如果前驱空闲先把当前块合并进前驱再直接定位物理后继如果后继空闲继续合并。这样最多两次合并逻辑清晰正确性容易验证。void my_free(void *ptr) { if (!ptr) return; header_t *hd (header_t *)((char *)ptr - HEADER_SIZE); hd-s.is_free 1; // 寻找物理前驱 header_t *cur heap_base; while (cur (header_t *)((char *)cur cur-s.size) ! hd) { cur (header_t *)((char *)cur cur-s.size); } // 前驱是空闲块则向前合并 if (cur cur-s.is_free) { cur-s.size hd-s.size; hd cur; } // 物理后继是空闲块则向后合并 header_t *nxt (header_t *)((char *)hd hd-s.size); if ((void *)nxt sbrk(0) nxt-s.is_free) { hd-s.size nxt-s.size; } }这里search-free的实现其实是O(n)的因为每次释放都要从头找前驱。讲真这也是隐式链表的典型代价。教学版完全可以接受但我在实际使用时发现一个更隐蔽的问题如果你手里的某个指针所指向的块已经损坏例如被写爆了size字段那free里所有指针计算都会偏离方向这个函数会直接把它们带进野区。所以在真正的生产环境里malloc实现往往会在header里放magic number来校验块完整性。我也建议你在后续玩的时候加上这个字段。3.4 调试好帮手打印整个堆区写分配器没有可视化调试等于闭眼开车。我强烈建议在实现阶段写一个打印函数把链表里每个块的地址、大小、状态都输出出来。别看这只是一段辅助代码它能在你怀疑某一步出错时直接告诉你堆区真实的分布状态。void print_heap(void) { header_t *cur heap_base; int index 0; printf(heap base: %p, brk: %p\n, (void *)heap_base, sbrk(0)); while (cur (void *)cur sbrk(0)) { printf(block[%d] addr%p size%zu free%d\n, index, (void *)cur, cur-s.size, cur-s.is_free); cur (header_t *)((char *)cur cur-s.size); } printf(-----------------\n); }4. 测试与验证写完了不等于能跑4.1 基础用例先验证最朴素的场景等你把上面的代码拼起来第一件事是写一个最小的main去验证基本逻辑。最朴素也最核心的checklist是连续分配多块不同大小内存、释放其中一块后再分配、观察free是否能复用旧块、释放相邻块能否合并。我当时的测试脚本长这样你可以直接抄int main(void) { int *a (int *)my_malloc(10 * sizeof(int)); char *b (char *)my_malloc(64); print_heap(); my_free(b); print_heap(); char *c (char *)my_malloc(32); print_heap(); int *d (int *)my_malloc(100 * sizeof(int)); print_heap(); my_free(a); my_free(c); my_free(d); print_heap(); return 0; }跑这个测试时你最想看到的输出是第一次free后b的块出现在空闲链表里并且c的地址大概率复用了它最后一次全部free后堆区出现了大块连续的空闲空间甚至是合并成一整块。如果全程打印的size字段加起来都等于brk相对于最初堆底的差值那基本就说明分配和回收是守恒的。4.2 压力与碎片测试基础用例过了不代表它真的能扛住真实负载。我强烈建议你写一个随机压力测试在循环里随机选择malloc或freemalloc的size也随机化同时维护一个指针数组跟踪所有未被释放的块。跑完以后检查三件事第一所有被分配的块之间是否重叠第二所有未被分配的空闲块和数据区是否写穿越第三全部释放后heap_base后面是否是一块完整的大空闲块。这个检查刚开始跑的时候十有八九你会发现自己的实现会在某一步size计算上出问题。最常见的现象是free后打印出来的链表里有一块的size字段明显不对比如变成负数或者天文数字这基本就是header被越界写了。我自己的第一版在分割逻辑上就出过这种错当时把remain计算成bytes而不是need导致整个链表错乱那一刻我才真正理解“内存管理就是在管账账本错了后面全错”。4.3 三个微信群里问烂了的坑在这块儿我汇总了新手包括当年的我最容易踩的三个坑避免你再走一遍弯路。注意第一不能用这个malloc和系统库的free混用。你把my_malloc出来的指针传给libc的free等于把内核向libc管理的内存区域之外去做释放行为未定义轻则崩溃重则静默损坏。第二递归分配不现实。my_malloc内部如果调用printf而printf内部又调用malloc就会死循环。教学版可以忍生产环境的malloc一般内部是不能直接用printf做日志的。第三该版本没有线程安全。两个线程同时调my_malloc没有锁就是数据竞争链表会乱掉一定要加互斥锁或者自旋锁。5. 顺着报错深挖malloc失败到底在说什么5.1 一行常见报错的排查路径你在网上搜malloc关键词时总能看到类似“native memory allocation (malloc) failed to allocate 2046256 bytes for chunk”这样的报错。这行信息很多程序运行时会出现尤其常见于Java虚拟机等运行时分配内存时。它的意思是底层C库的malloc函数尝试申请约2MB的连续内存申请失败了。看到这个报错很多人第一反应是“物理内存不足”但真实情况往往复杂得多。排查路径我一般按顺序走先看操作系统还有没有剩余物理内存这个用free或任务管理器看再看当前进程的虚拟内存是否已经逼近地址空间上限32位进程尤其容易踩到4GB边界然后检查进程是否受cgroup或容器限制这种“明明是宿主机内存很大可进程一申请就OOM”的场景非常典型最后再看是不是内存碎片化严重虽然虚拟内存总量很多但找不出一块足够大的连续虚拟地址区间不过这个问题在现代64位系统里相对少见因为虚拟地址空间足够大。以那行报错为例2046256字节正好约2MB如果是64位JVM很多时候反而是因为物理内存或容器内存配额真的不够了。不要一看到malloc失败就怀疑碎片先查限制条件。5.2 越界和踩内存才是隐藏杀手另一种“分配失败”非常诡秘它本身不是分配失败是malloc内部维护的元数据被踩坏了导致后续所有分配行为错乱。比如你分配了一块100字节的内存却往里写入了1000字节多出来的部分正好覆盖了后面空闲块或者已分配块的header头那下一次malloc遍历链表时size字段已经是乱码整个堆结构瞬间崩塌。这种问题最坑爹的地方是报错往往不是在你写越界的那个瞬间出现而是在下一次malloc或free时爆出来。我调过最久的一次线上崩溃over 30小时gdb单步最后发现是一个字符串拷贝没留终止符的空间把相邻块header里size低8位写成了0真的是分分钟教做人。所以当你自己的malloc函数出问题时第一件事永远是print_heap盯着size字段看有没有哪个块的大小不合常理。这比任何高端调试器都好用也是自己写malloc带来的最大收获你对“指针越界会造成什么后果”会有刻骨铭心的体感。5.3 多线程与真实生产malloc的方向写完教学版后如果你还想继续深入可以考虑三条进阶路线。第一条是加锁把my_malloc和my_free包进pthread_mutex虽然这会牺牲并发度但至少正确。第二条是改用显式空闲链表加边界标记让free的合并和查找都更快。第三条则是参考glibc的ptmalloc如何用chunk里的fd和bk指针组成bin或者参考tcmalloc如何在每个线程本地维护缓存。这个扩展方向非常诱人因为一旦你理解了malloc的底层债路再回去看Redis的jemalloc、JVM的TLAB等等内存池设计都会产生一种“原来如此”的通透感。很多所谓高性能中间件说到底都是在管理一套自定义的“malloc”只是规模更大、策略更聪明。最后说一点个人体会我始终觉得自己动手写一遍malloc函数是程序员这种职业少有的、完成一遍就能持续受益的小项目。它不复杂核心代码也就一百多行但它能让你把之前零零散散掌握的虚拟内存、地址空间、数据结构、指针运算和并发概念一次性串联起来。写完那一刻你再看那些“malloc failed”的报错或者free崩溃的段错误心态会完全不一样。关于这个项目后续你还可以这么玩给它加上magic number校验和异常检测日志或者在分割合并的策略上换成best-fit并做一轮性能对比甚至可以尝试用mmap来分配超大块并测试它是否能及时归还系统中。这些扩展方向每个都能单独写一篇博客但起点都是你现在手里这个看似简陋的版本。希望这篇文章能帮你迈出这一步也欢迎你在评论区贴出你跑出的print_heap结果或者踩到的奇怪坑位大家一起围观一起查。本文还有配套的精品资源点击获取