手写malloc：从一次真实故障到彻底看懂内存分配器

简介自己动手写内存分配函数是一份围绕C语言动态内存管理实现的源码教学包面向希望深入理解malloc内部机制的中高级开发者以及正在学习操作系统内存管理的院校学生。压缩包内共3个文件包括两个C语言源文件和一个头文件分别承载my_malloc实现、接口声明与测试程序包体仅3KB小巧清晰方便读者按函数调用顺序阅读。代码基于一段预分配的内存池展开演示了初始化、空闲块查找、块分裂、内存分配、块释放以及需要时扩展堆空间等关键操作并以注释解释内存碎片、内存块、内存池等核心概念测试文件给出了可运行场景读者可以调整分配参数或修改搜索策略实际观察首次适配等算法对碎片的影响从而理解真实malloc在性能和空间上的权衡。资源已有1825人学习下载适合用来打通内存分配的理论与实践并可作为后续实现对齐处理、并发控制等完善版分配器的起点。 周六晚上十一点我盯着一台刚宕掉的Java服务日志里有一行让我彻底失眠。原话是native memory allocation (malloc) failed to allocate 2046256 bytes for chunk2046256字节换算下来也就不到2MB。一台配置并不低的服务器怎么会连2MB都分配不出来当时我第一反应是物理内存满了扩容之后问题依旧。后来我才意识到这行日志背后藏着的是我对malloc这个天天都在用的函数最深的误解。为了把这个问题一次弄明白我决定用最笨也最有效的办法不看二手博客不抄现成源码自己动手写一个malloc函数。整个过程踩了不少坑但也因此把进程地址空间、brk、mmap、内存碎片这些概念真正串成了体系。这篇内容就是这段时间的完整记录写给那些遇到类似报错却无从下手的开发者也写给想真正理解内存分配器底层逻辑的人。1. 把malloc失败拆开看是谁拒绝了这次分配1.1 内存不够是最常见的误诊遇到malloc failed这类日志绝大多数人的第一反应都是物理内存不够了。我最初也这么想但加完机器、腾出大量空闲内存之后报错依然出现这就说明判断方向有问题。malloc返回NULL并不直接等于系统内存不够。它只代表一件事**在当前进程的虚拟地址空间里实在找不到能满足size要求的一块连续区域了。**这背后的原因可能是虚拟地址空间被耗尽也可能是进程的资源限制比如ulimit、容器层面的内存限制、或者Linux内核的overcommit策略主动拒绝了这次扩展。那个JVM日志里的malloc失败实际上是从glibc malloc返回了NULLJVM拿到NULL之后认为内存管理已经不可恢复直接打印日志并触发退出流程。所以排查的重点应该往前推glibc是在哪一步、因为什么原因才决定返回NULL的。1.2 2MB这个数字为什么会成为分水岭很多类似报错都出现在申请2MB左右的内存块时这本身就有信息量。glibc malloc内部有个重要的分界点**MMAP_THRESHOLD默认值是128KB。**小于等于128KB的分配请求走堆区arena从glibc维护的各种空闲链表里找内存找到就直接返回整个过程不会打扰内核大于128KB的请求glibc会直接调用mmap去内核申请一块全新的虚拟地址区间释放的时候再unmap归还。也就是说2MB的分配几乎每次都是一次真实的系统调用。一旦内核因为地址空间碎片、rlimit限制或者cgroup限制拒绝了mmapmalloc就只能返回NULL。而平时那些几十几百字节的小分配大多从glibc用户态缓存里就满足了即使系统已经逼近内存上限它们未必会立刻失败。这就是为什么小分配看起来还能工作而一个2MB的chunk反而先崩了。1.3 排查的顺序比结论更重要经历过这次误判我现在排查这类问题会固定按一个顺序来先看进程虚拟地址空间cat /proc/pid/limits里有没有弱化Max address space或者用pmap -x pid看有没有大量不可回收的保留区间。再看系统级限制/proc/meminfo里的CommitLimit和Committed_AS以及vm.overcommit_memory当前的值。最后才看物理内存和swap以及进程自身有没有明显泄漏。这个顺序的本质是malloc失败往往是虚拟地址空间管理器拒绝了你而不是物理内存条拒绝了你。把这个顺序搞反就会像我最初那样白折腾半天。2. 写malloc前必须补的课brk、mmap与128KB阈值2.1 进程地址空间里堆的位置很尴尬要自己写malloc第一步是搞清楚malloc到底从哪里变出内存。每个用户态进程都有一张虚拟地址空间地图从低地址到高地址大致是这样排列的代码段、已初始化数据段、未初始化数据段、堆然后再往上是一个独立的mmap映射区最后是栈。堆的顶部叫做program break也就是通常说的brk。brk指向当前堆区能使用的最高地址初始位置和未初始化数据段尾部紧挨着。用户态malloc的第一种进货渠道就是通过brk或sbrk系统调用把这个堆顶往上推推出来的这段新地址就归我们用了。但堆的位置很尴尬——它在数据段和mmap区之间只能向上增长。如果你申请了一大块、用了又释放掉堆顶并不能随之降回去这块空间只能留在堆区里继续被后续分配复用。这是后面所有碎片化问题的根源。2.2 sbrk/brk线性扩张的堆顶brk系统调用可以设置program break的绝对位置sbrk则是相对偏移传入一个增量返回调整前的旧brk地址。自己写malloc时最常用的就是sbrk(size)。void *request sbrk(size); if (request (void *)-1) { // 扩展失败 }值得一提的是sbrk只负责把虚拟地址空间划给你它不会清零内容也不会做任何对齐保证不过实际上堆在大部分情况下是页对齐的。它给你的是一块干净但原生的地址怎么在里面划分出一个个可管理的块完全看分配器自己怎么设计。sbrk的优点是开销小、线性扩展方便缺点是释放空间的回收极其困难。glibc虽然也会周期性地试图收缩堆但堆内存一旦在高地址处被分裂就很难再完整归还给操作系统。2.3 mmap大块内存的独立映射对于大块内存malloc还有第二条路mmap。它不像sbrk那样必须接在堆的尾巴上而是让内核在进程地址空间里找一块空闲区域建立匿名映射后把地址返回给你。匿名映射有两个关键特性第一映射大小通常是页4KB的整数倍内部还能按需加载物理页第二释放时可以直接munmap把整块区域立刻归还给内核。这意味着大块内存用完即走不会在堆区留下无法回收的空洞代价是每次mmap/munmap都要经过内核性能和TLB开销比小块分配高得多。所以malloc的设计者做了个聪明的妥协小块走sbrk聚合管理大块走mmap独立回收。2.4 128KB阈值不是拍脑袋定的为什么默认阈值是128KB因为在这个量级以下走堆区批量管理是很划算的超过这个量级与其让它在堆里形成空洞、拖累后续所有分配不如让mmap单独处理。而且glibc里的这个阈值不是固定的。它会动态调整当某个较大的块被释放时如果它的大小超过当前阈值glibc会把这个值调大让后续同类大小的分配也走堆区复用反过来如果堆区空间紧张它也可能调低阈值。这就是M_MMAP_THRESHOLD动态调节机制目的是尽可能兼顾减少系统调用和降低堆碎片。自己写malloc时我不推荐一上来就做动态阈值先用sbrk把路径跑通后面再考虑mmap补充这是更合理的推进顺序。2.5 用户态malloc的真正角色理解了sbrk和mmap就会明白一个关键结论**malloc并不是每次调用都在向操作系统要内存。**真正干活的是一大堆用户态管理逻辑——切块、合并、缓存、线程隔离。操作系统给的只是一大片地基malloc在上面盖了一整座仓库你的每次分配和释放大多数时候是在仓库里腾挪货架而不是重新买地。这也是为什么很多人误以为malloc失败系统内存不够其实更常见的是仓库内部碎片化或者限制导致的失败。3. 第一版实现单链表块头 first-fit分配器3.1 块头设计每个分配都是一个包裹实现一个简化的malloc最直观的办法是把每一块被管理的内存都包装成一个包裹包裹最前面是一段元数据我们叫它块头后面才是真正给调用者用的负载区。块头至少要记三件事负载区有多大、这块内存是否空闲、下一块内存的地址。我用了这样的结构typedef struct Block { size_t size; // 当前块的负载大小不含块头 int free; // 是否空闲 struct Block *next; // 指向连续布局中的下一块 } Block;所有块通过next指针串成一条单向链表head指向链表第一个块。malloc时遍历这条链表找空闲块free时把对应块的free标记位改成1。这个设计足够简单也足够暴露问题。3.2 三个关键函数find_free_block、extend_heap、split_block实现过程中有三个函数是绕不开的find_free_block负责遍历空闲链表找到一个负载空间不小于请求size的空闲块。它同时通过last指针记录上一次遍历位置这样extend_heap扩展堆时能直接把新块挂到链表尾部。extend_heap是向操作系统要内存的唯一入口。它调用sbrk(size)拿到一段新地址把这段地址包装成一个新块头设置好size和free字段挂到链表末尾。split_block负责拆块。当一个空闲块比请求的size大很多时如果整块直接分配出去会产生大量内部浪费所以要把块一分为二前半部分给调用者后半部分继续留作空闲块。3.3 mymalloc与myfree完整代码把上述思路串起来一个能跑的基础版本长这样#include stdio.h #include unistd.h #include stdint.h typedef struct Block { size_t size; int free; struct Block *next; } Block; #define ALIGNMENT 16 #define ALIGN(size) (((size) (ALIGNMENT - 1)) ~(ALIGNMENT - 1)) #define BLOCK_SIZE ALIGN(sizeof(Block)) static Block *head NULL; Block *find_free_block(Block **last, size_t size) { Block *cur head; while (cur !(cur-free cur-size size)) { *last cur; cur cur-next; } return cur; } Block *extend_heap(Block *last, size_t size) { void *request sbrk(size); if (request (void *)-1) { return NULL; } Block *block (Block *)request; block-size size - BLOCK_SIZE; block-free 0; block-next NULL; if (last) { last-next block; } return block; } void split_block(Block *block, size_t size) { if (block-size size BLOCK_SIZE ALIGNMENT) { Block *new_block (Block *)((char *)block BLOCK_SIZE size); new_block-size block-size - size - BLOCK_SIZE; new_block-free 1; new_block-next block-next; block-size size; block-next new_block; } } void *mymalloc(size_t size) { if (size 0) { return NULL; } size ALIGN(size); if (head NULL) { Block *block extend_heap(NULL, BLOCK_SIZE size); if (block NULL) { return NULL; } head block; return (char *)block BLOCK_SIZE; } Block *last head; Block *found find_free_block(last, size); if (found NULL) { Block *block extend_heap(last, BLOCK_SIZE size); if (block NULL) { return NULL; } found block; } else { found-free 0; split_block(found, size); } return (char *)found BLOCK_SIZE; } void myfree(void *ptr) { if (ptr NULL) { return; } Block *block (Block *)((char *)ptr - BLOCK_SIZE); block-free 1; // 简单合并释放后把相邻空闲块合并 Block *cur head; while (cur cur-next) { if (cur-free cur-next-free) { cur-size BLOCK_SIZE cur-next-size; cur-next cur-next-next; } else { cur cur-next; } } }需要注意的一点返回给调用者的地址是(char *)found BLOCK_SIZE而不是found 1。因为BLOCK_SIZE是sizeof(Block)对齐到16字节后的结果32字节而found 1只偏移24字节会破坏负载区的16字节对齐。这个坑不亲手踩一次很容易忽略。3.4 一次分配请求的完整旅程用一个小例子看看malloc一次请求的完整流程。假设第一次调用mymalloc(100)size对齐后变成112。head为NULL说明链表还没初始化。调用extend_heap(NULL, BLOCK_SIZE 112)sbrk向内核申请144字节。内核把堆顶往上推返回旧堆顶地址这段区域被包装成Blocksize112free0。返回block BLOCK_SIZE给调用者调用者拿到112字节可用空间。再来一次mymalloc(1000)时head已非空find_free_block遍历发现没有空闲块于是extend_heap(last, 1032)新块挂在链表尾部返回负载地址。4. 从能跑到能用的差距对齐、分割、合并与失败兜底4.1 16字节对齐不是玄学第一次写malloc很容易认为对齐只是为了好看。但malloc返回的地址如果不满足平台的字节对齐要求轻则性能下降重则直接崩溃。x86_64平台上的malloc要求返回的地址至少16字节对齐原因有两点第一SSE/AVX这类SIMD指令要求数据地址按16字节或32字节对齐否则触发异常第二C标准保证malloc返回的指针可以安全转换为任何类型的指针而long double、double、指针本身都有各自的自然对齐要求malloc必须取所有类型对齐要求的最大值并向上取整。对齐代码我是这样实现的#define ALIGNMENT 16 #define ALIGN(size) (((size) (ALIGNMENT - 1)) ~(ALIGNMENT - 1))这个宏把任意size向上取整到16的倍数。分配时无论调用者要什么size我在块头里记录的负载size始终是对齐后的值。这样每次负载区的起始地址天然满足16字节对齐。代价是多占几个字节但换来的是安全性和兼容性值。4.2 分割给大空闲块减肥split_block看起来简单但触发条件很关键。我在代码里用的是if (block-size size BLOCK_SIZE ALIGNMENT)为什么要这样判断如果空闲块只比需求大一点点额外的空间连放一个块头都不够那就不如整体整块分配让那点余量作为内部碎片消耗掉。只有当剩余空间足够容纳一个新块头至少一个最小负载分拆才划算。分拆之后前面的块留给调用者后面的块标记为free1并接到链表中间。这样后续的小分配可以直接复用后半部分不会因为一次大分配就浪费掉整块空间。4.3 合并与碎片化正面交锋释放时如果不做任何处理空闲块会像撒芝麻一样散落在链表中。最典型的情况交替分配和释放比如分配A、释放A、再分配B、释放B会让空闲块无法合并成大片连续内存。我在第一版myfree里做的是线性合并遍历链表如果一个块是空闲的并且它的下一个块也是空闲的就把两者合并成一个更大的块。这个方案能处理连续空闲块的合并但有个明显短板如果空闲状态在链表中是两个相邻空闲块之间夹着一个已占用块的交替模式当前方案什么也做不了。更合理的做法是按地址排序维护链表。释放时把块插入到链表的地址有序位置这样合并时就能天然照顾到物理相邻性。我后来把free逻辑改成了释放时按地址插入排序碎片率立刻下降了很多。这块后续空间足够再水一篇完整的文章这里只提一句思路。4.4 sbrk失败时别忘了errno自己写malloc时最容易忽略的错误处理就是extend_heap里sbrk返回-1的情况。很多人会直接返回NULL但不设置errno。这会导致调用方拿到了NULL却不知道具体原因。正确处理方式是在sbrk失败时把errno设置为ENOMEM模拟glibc的行为。这样调用方可以通过perror或strerror看到更准确的信息Block *extend_heap(Block *last, size_t size) { void *request sbrk(size); if (request (void *)-1) { errno ENOMEM; return NULL; } // ... }很多线上排查场景都是通过malloc失败时的errno来辅助判断的。自己写的时候养成这个习惯后面调试会舒服很多。5. 实测对比自己写的malloc到底差在哪5.1 基本分配释放测试写完之后我先跑了一轮基础用例。申请若干块不同大小内存、写入pattern、再释放、再申请确保数据内容没有被意外覆盖块头没有被写出边界。这类测试我验证了三件事第一不同size下返回的地址都是16字节对齐的第二写入和读取的内容完全一致说明负载区没有重叠第三释放后再次分配不会崩。基础路径顺利通过说明这个分配器的骨架是健康的。但通过只代表功能对不代表质量好真正的差距要在压力测试里才能暴露。5.2 压力测试碎片化下的性能退化我写了一段模拟代码随机申请1字节到64KB不等的内存随机释放循环100万次统计内存峰值和平均分配耗时。结果很直观内存峰值比glibc高不少因为我只做了相邻合并跨块的地址空洞无法有效回收。每次分配都要从头遍历链表空闲块越多链表越长分配耗时呈现明显的线性增长。没有线程锁保护多线程下如果直接使用链表指针瞬间被写烂。这三点其实都是malloc设计的经典话题碎片率控制、分配效率、线程安全性。我的简化版在每一点上都交了学费。5.3 对照glibc malloc的性能鸿沟拿一个简单benchmark和glibc对比差距立刻体现对比项我的实现glibc malloc单块头开销32字节约16字节分配策略first-fit线性遍历tcache/bins多级缓存空闲块查找平均O(n)多数情况O(1)系统调用触发sbrk频繁扩展小分配完全不触发多线程支持无多arena降低竞争glibc之所以快靠的不是某个单一魔法而是层次化的缓存体系。小内存走tcache稍大走fastbin再大走unsorted/small/large bins最后才是mmap。每一层都是为特定大小和特定频率设计的。真正读完这些再看自己写的分配器才能理解那些看似复杂的结构其实都是针对碎片和性能问题逐层补齐的。5.4 回到那行崩溃日志这次终于看懂了用自己的malloc经历了这么多失败场景再回头看那行报错思路完全不一样了。native memory allocation (malloc) failed to allocate 2046256 bytes for chunk里的2046256字节是一个接近2MB的大块请求。以glibc的默认策略这种size几乎一定走mmap。如果mmap被拒可能的原因无非几类进程的虚拟地址空间在长时间运行后被碎片化恰好无法找到一段连续足够大的映射区间或者进程碰上了rlimit限制又或者容器/内核层面的overcommit策略主动拒绝了新映射。排查动作也随之明确# 1. 看进程资源限制 cat /proc/pid/limits # 2. 看系统overcommit状态 cat /proc/meminfo | grep -E CommitLimit|Committed_AS sysctl vm.overcommit_memory # 3. 看进程地址空间分布 pmap -x pid三件套跑下来基本能定位是限制问题、碎片问题还是泄漏问题。这个经验在我看来比学会写malloc本身还要值钱。6. 写完自己的malloc之后我的排查思路发生了改变以前看到malloc failed优先级最高的是加内存、加机器、重启。现在我的第一反应是先看虚拟地址空间结构和限制条件因为绝大多数malloc失败并不是物理内存拒绝了你而是虚拟地址空间或者内核策略拒绝了你。如果你也想动手写一个malloc我建议按这个顺序来先用sbrk把核心分配路径跑通不要一上来就碰mmap和多线程然后把对齐和错误处理做对再逐步加入分割和合并逻辑最后才考虑按地址排序、多arena这类优化。每一个阶段都能踩出独立的坑而这些坑恰恰是理解glibc源码最好的钥匙。还有个额外收获现在看任何语言底层的out of memory报错我都会先问一句这个报错是从用户态分配器来的还是从内核映射来的这个问题的答案往往决定了排查方向对不对。学会自己写一次malloc相当于给这个判断装了一根校准过的标尺。本文还有配套的精品资源点击获取