简介一套以手写 my_malloc 为线索的源码示例面向希望深入理解动态内存分配的 C/C 开发者。资源覆盖堆管理、内存碎片、空闲块链表、相邻块合并等核心概念并体现首次适配、最佳适配等分配策略的应用场景帮助读者从使用层面进阶到实现层面。压缩包共 3 个文件包含两个 C 源文件与一个头文件分别对应分配器实现、测试程序与对外接口声明包体约 3KB结构紧凑适合直接阅读与动手编译。目前已有 1826 人学习下载。通过对照源码中分配与释放逻辑、测试用例的验证可以直观理解 malloc 的典型实现思路掌握用少量代码搭建可运行内存分配原型的方法还能理清内存块元数据、空闲链表维护与相邻块合并等细节为日后阅读 glibc 等真实分配器实现打下扎实基础。1. 自己动手写malloc先理解它替你扛了什么一个C程序里最频繁也最容易被冤枉的函数就是malloc函数。你写下int *p malloc(10 * sizeof(int))的时候根本不会去想它背后做了什么直到线上程序内存涨到几个GB或者free之后再次访问crash你才意识到分配器不是简单的“要内存就给”。自己动手写malloc不是为了在项目里替换glibc而是用一次从零实现去理解内存在操作系统和进程之间到底怎么流动、碎片从哪来、性能瓶颈在哪。这篇文章适合刚啃完指针和结构体的读者也适合想优化内存池的熟手。你会看到最小可用的分配器、合并策略、对齐参数以及那些一旦不注意就让你调试三天的问题。读完之后你可以照着代码改出第一版属于自己的malloc。2. 从brk/sbrk到第一版内存分配器最小可用的malloc函数长什么样2.1 进程的堆是从哪里来的标准C库里malloc函数的本质是向操作系统要一块连续虚拟内存然后切成小块交给应用。传统做法是调用sbrk/brk调整进程堆顶Linux下还有mmap。sbrk(0)返回当前断点sbrk(n)把断点往后挪n字节返回旧断点。这个“断点”就是data segment的末尾向上增长。很多教材都会先讲sbrk因为它是堆的起点逻辑最直接。需要注意sbrk维护的是一个线性连续空间一旦用sbrk扩展再想缩小很难。而mmap按页映射可以局部释放但每次都要换页和陷入内核代价大。所以常见做法是小块走sbrk大块走mmap。我们第一版为了让逻辑简单只用sbrk。这样malloc的堆就是一个连续地址区间空闲块和已分配块交替排列遍历时用size跳着走。后面你会看到这个“跳着走”的步长里藏着第一个坑。2.2 第一版代码用隐式空闲链表实现malloc函数隐式空闲链表的意思是所有块包括已分配和空闲都通过块头里的size字段连在一起不额外维护链表指针。遍历时从堆首开始下一个块地址 当前块头地址 块头大小 数据区大小。下面这个版本故意不做分裂也不做合并先把链路跑通。#include stdio.h #include stdlib.h #include unistd.h #define ALIGNMENT 8 #define ALIGN(size) (((size) (ALIGNMENT - 1)) ~(ALIGNMENT - 1)) #define HEADER_SIZE ALIGN(sizeof(block_header_t)) typedef struct block_header { size_t size; // 数据区大小已按8对齐 int free; // 1表示空闲0表示被占用 } block_header_t; static void *heap_start NULL; static void *heap_end NULL; // 拿到下一个块的header地址 static block_header_t *next_block(block_header_t *h) { return (block_header_t *)((char *)(h 1) h-size); } // 初始化堆把sbrk拿到的区域当成一个大的空闲块 static void *heap_init(size_t init_size) { void *p sbrk(init_size); if (p (void *)-1) return NULL; heap_start p; heap_end (char *)p init_size; block_header_t *h (block_header_t *)p; h-size init_size - HEADER_SIZE; h-free 1; return (void *)(h 1); } void *my_malloc(size_t n) { if (n 0) n 1; n ALIGN(n); // 第一次调用初始化堆 if (heap_start NULL) { if (heap_init(4096) NULL) return NULL; } // 遍历已有块找第一个足够大的空闲块 for (block_header_t *cur (block_header_t *)heap_start; cur (block_header_t *)heap_end; cur next_block(cur)) { if (cur-free cur-size n) { cur-free 0; return (void *)(cur 1); } } // 没有空闲块可用扩展堆新块直接作为分配结果 size_t need HEADER_SIZE n; if (sbrk(need) (void *)-1) return NULL; block_header_t *new_block (block_header_t *)heap_end; new_block-size n; new_block-free 0; heap_end (char *)heap_end need; return (void *)(new_block 1); } void my_free(void *ptr) { if (ptr NULL) return; block_header_t *h (block_header_t *)ptr - 1; h-free 1; } // 打印堆上的块链帮助观察 void dump_heap(void) { for (block_header_t *cur (block_header_t *)heap_start; cur (block_header_t *)heap_end; cur next_block(cur)) { printf([%p] size%zu free%d\n, (void *)cur, cur-size, cur-free); } } int main(void) { char *p1 my_malloc(10); char *p2 my_malloc(20); dump_heap(); my_free(p1); my_free(p2); return 0; }先看两个参数ALIGNMENT 8作用是让每次malloc返回的地址至少8字节对齐满足常见double和指针的访问要求。HEADER_SIZE ALIGN(sizeof(block_header_t))在64位平台上结构体size_t占8字节、int占4字节加上对齐后正好16字节所以块头本身也是8的倍数不会破坏后面数据区的对齐。代码里的遍历循环要重点理解cur是块头的地址(char *)(h 1)是数据区起始地址再加上h-size就跳过数据区走到下一块的header。这个公式是隐式空闲链表的命根子后面加footer、加分裂时都要改它但它表达的逻辑不变。2.3 第一次调用my_malloc之后内存长什么样运行上面的main第一次my_malloc(10)会初始化堆sbrk(4096)拿到的区域被当成一个空闲块block头里size4080free1。遍历时发现它足够大于是直接整个块标记为占用数据区是4080字节但你实际只需要10字节。第二次my_malloc(20)发现整块已经占用只能brk再扩一块。用dump_heap看到的结果就是两个块一个4080字节已占用一个20字节已占用。这个“大块被小请求整个吞掉”的浪费就是下一章要解决的分裂问题。如果你是第一次写分配器我强烈建议在这个版本上多做几个测试连续my_malloc(1)、my_malloc(1)、my_malloc(1)再dump_heap你会看到每个16字节的块都在堆尾增长因为前面那个大块被第一次分配占死了。这就是不分裂的代价。下一个版本加入分裂和空闲块合并free才算真正变成“后悔药”。提示这里的sbrk(need)每次只扩一个块的量生产环境不能这么干。真实分配器通常一次扩大一整个chunk否则malloc/free频繁时系统调用会拖垮性能。第五种版本讨论。3. 把free做成后悔药空闲块合并、边界标记与对齐参数怎么设3.1 只free不合并内存碎片是怎么养出来的假设你按顺序分配了A、B、C三个小块然后free(B)再free(A)。隐式链表里的状态是B空闲、A空闲但C仍然占用。此时A和B虽然相邻但因为没有合并逻辑它们在链表里还是两个独立的空闲块各自只有十几字节。如果这时来一个30字节的malloc即使AB的空闲总量超过30也会因为没有一个连续空闲块而分配失败最终触发sbrk扩展堆。程序跑得越久这种“外部碎片”就越严重总空闲内存很多但最大连续空闲块反而可能变小。解决思路是free时检查相邻块能合并就合并。要让合并足够快需要知道前一个块的边界。但隐式链表只靠当前块的size能往后走无法往前退。一个经典办法是边界标记在每个块的头部记录size同时在块尾也记录一个footer内容还是size。这样从当前块头往前看footer里就保存了前一块的大小。3.2 边界标记让合并在O(1)完成从这一版开始每个块都带footer所以next_block的步长要把footer算进去下一个块 当前块数据区 FOOTER_SIZE。同时分配块的footer也要写好否则free时无法向前合并。先定义结构和辅助函数#define ALIGNMENT 8 #define ALIGN(size) (((size) (ALIGNMENT - 1)) ~(ALIGNMENT - 1)) typedef struct block_header { size_t size; // 数据区大小按8对齐 int free; // 空闲标记 } block_header_t; typedef struct block_footer { size_t size; } block_footer_t; #define HEADER_SIZE ALIGN(sizeof(block_header_t)) #define FOOTER_SIZE ALIGN(sizeof(block_footer_t)) #define MIN_BLOCK_SIZE (HEADER_SIZE FOOTER_SIZE ALIGNMENT)在64位下header占16字节footer占8字节两者都按8对齐。MIN_BLOCK_SIZE是最小可分割单元后面解释。辅助函数这样写// 从当前块头跳到下一个块头 static block_header_t *next_block(block_header_t *h) { return (block_header_t *)((char *)(h 1) h-size FOOTER_SIZE); } // 通过当前块前面的footer找到前一个块头 static block_header_t *prev_block(block_header_t *h) { block_footer_t *prev_f (block_footer_t *)((char *)h - FOOTER_SIZE); size_t prev_size prev_f-size; return (block_header_t *)((char *)h - FOOTER_SIZE - prev_size - HEADER_SIZE); }注意prev_block的推导当前块header前面紧挨着上一个块的footer所以先用h - FOOTER_SIZE读footer得到prev_size再往前跳过prev_size数据区和HEADER_SIZE就是上一块的header。在堆首时不能调用它因为前面没有footer。带合并的free长这样void my_free(void *ptr) { if (ptr NULL) return; block_header_t *h (block_header_t *)ptr - 1; h-free 1; // 向前合并当前块不是堆首且前一块空闲 if ((char *)h ! (char *)heap_start) { block_header_t *prev_h prev_block(h); if (prev_h-free) { // 新size 前块size 前块footer 当前块header 当前块size size_t new_size prev_h-size FOOTER_SIZE HEADER_SIZE h-size; prev_h-size new_size; block_footer_t *new_f (block_footer_t *)((char *)(prev_h 1) new_size); new_f-size new_size; h prev_h; } } // 向后合并当前块后面还有块且后一块空闲 block_header_t *next_h next_block(h); if ((char *)next_h (char *)heap_end next_h-free) { size_t new_size h-size FOOTER_SIZE HEADER_SIZE next_h-size; h-size new_size; block_footer_t *new_f (block_footer_t *)((char *)(h 1) new_size); new_f-size new_size; } }合并公式看着绕实际就是把中间夹着的footer和header“消化”成数据区。比如当前块h和前块prev_h合并prev_h的数据区后面是prev_h的footer然后才是h的header再往后是h的数据区。合并后新数据区要把这两层簿记都吞进去所以多了FOOTER_SIZE HEADER_SIZE。向后合并且前向合并已发生时h已经变成新的大块next_block(h)会根据新size计算到正确的后继。分裂也要改。现在每个块带footer分裂时先写分配块的footer再在它后面创建空闲块void *my_malloc(size_t n) { if (n 0) n 1; n ALIGN(n); if (heap_start NULL) { if (heap_init(4096) NULL) return NULL; } for (block_header_t *cur (block_header_t *)heap_start; cur (block_header_t *)heap_end; cur next_block(cur)) { if (!cur-free || cur-size n) continue; size_t remain cur-size - n; if (remain MIN_BLOCK_SIZE) { // 从原块头部切出n字节给分配块剩余部分留在原地作为空闲块 block_footer_t *alloc_f (block_footer_t *)((char *)(cur 1) n); alloc_f-size n; block_header_t *free_h (block_header_t *)(alloc_f 1); size_t free_data_size remain - HEADER_SIZE - FOOTER_SIZE; free_h-size free_data_size; free_h-free 1; block_footer_t *free_f (block_footer_t *)((char *)(free_h 1) free_data_size); free_f-size free_data_size; cur-size n; cur-free 0; } else { // 剩余空间连最小块都放不下干脆整块分配 cur-free 0; block_footer_t *f (block_footer_t *)((char *)(cur 1) cur-size); f-size cur-size; } return (void *)(cur 1); } // 扩堆逻辑新块直接作为分配结果 size_t need HEADER_SIZE n FOOTER_SIZE; if (sbrk(need) (void *)-1) return NULL; block_header_t *new_block (block_header_t *)heap_end; new_block-size n; new_block-free 0; block_footer_t *f (block_footer_t *)((char *)(new_block 1) n); f-size n; heap_end (char *)heap_end need; return (void *)(new_block 1); }分裂的条件remain MIN_BLOCK_SIZE很关键。remain是原空闲块数据区减去n后剩下的字节数这剩余部分要容纳一个新块的header、一个footer和至少1字节对齐数据。如果不够就把整个块给用户否则会分裂出8字节甚至更小的碎块以后永远无法满足最小分配请求反而加重碎片。3.3 参数怎么设对齐、最小块、sbrk增量手写malloc最常调的三个参数是ALIGNMENT、MIN_BLOCK_SIZE和sbrk扩展增量。我习惯这样定参数我常用的值原因ALIGNMENT8特殊场景用168满足常见数据类型需要SIMD对齐时升到16FOOTER_SIZEALIGN(sizeof(block_footer_t))必须参与对齐计算否则footer位置偏掉MIN_BLOCK_SIZEHEADER_SIZE FOOTER_SIZE ALIGNMENT防止分裂出不可再用的碎片sbrk增量4096的倍数通常一次性扩8KB或16KB减少系统调用次数同时给堆留出余地ALIGNMENT并不是越大越好。升到16会减少可用块数量增加每个块尾部浪费的字节数。小块请求越多这种内部碎片越明显。如果你只是跟着教程跑通8足够如果要接SSE/AVX再认真改对齐位。sbrk增量是另一个容易被忽略的参数。第二版的代码每次malloc都单独扩堆这在性能上几乎不可用。我给学习版定4096生产场景会把申请量大但调用频率高的程序压测一轮看系统调用比例再决定是8KB还是64KB。一次扩太多会导致堆尾部长期被一个超大空闲块占着但这个代价通常比每个malloc都触发一次系统调用小得多。4. 避坑指南手写malloc最常见的5个翻车现场4.1 只free不merge运行一会就分配不出大块现象写了个小测试反复malloc/free前几次都成功跑到几千次后某个大请求返回NULL。原因free只是把free标志置1没有把相邻空闲块合并。空闲块总数越来越多但每块都很小无法满足大请求。解决别偷懒把上一章的向前合并和向后合并完整接上。合并后记得同步更新footer否则下一次prev_block读到的size是旧值会算错前驱地址。4.2 传回未对齐指针double一访问就崩现象double *d my_malloc(sizeof(double)); *d 1.0;直接段错误但char *没问题。原因块头没有参与对齐计算或者ALIGNMENT设置太小导致返回给用户的地址落在非8字节边界上。x86的未对齐访问有时候不崩但编译器可能生成需要对齐的SIMD指令一执行就炸。解决HEADER_SIZE必须用ALIGN(sizeof(header))计算而不是直接sizeof(header)。数据区大小也要ALIGN。如果你担心未来换平台可以把块头定义成union { struct {...} s; max_align_t align; }让编译器决定最严格对齐。4.3 sbrk返回值用错了拿-1当地址写现象内存耗尽时malloc没有返回NULL而是直接崩在赋值语句。原因sbrk失败返回(void *)-1但代码里没检查就把它赋值给heap_end或者在扩堆时直接往heap_end写块头。解决每次调用后立刻检查if (sbrk(need) (void *)-1) return NULL;。注意比较时要把-1强转成void *否则在某些平台上整型比较会发生符号扩展导致判断失效。4.4 double free和free非malloc指针现象同一个指针连续free两次第二次可能在free里死循环或者下一次malloc分配出已经被用户使用的内存。原因第一次free已经把块标记为空闲第二次free会再次执行合并逻辑。如果此时块已经和前后合并指针指向的header可能已经被挪作他用整个链表就坏了。更隐蔽的是free了栈上的地址编译器不报错运行起来全是玄学崩溃。解决在header里加一个magic numberfree时校验。同时校验指针落在heap_start和heap_end之间否则直接abort。实践里很多人还会维护一个显式的已分配链表free时从链表里找找不到就报错。这些手段不能阻止用户乱传指针但能把错误提前暴露。4.5 并发调用直接重复分配同一块现象多线程程序里两个线程同时my_malloc(100)返回了同一个地址后面数据互相踩踏。原因所有线程共享heap_start、heap_end和空闲链表。A线程刚找到空闲块还没标记占用B线程也找到同一块。解决在入口处加锁比如pthread_mutex_lock(alloc_lock)。这是最简单的线程安全化手段但会带来竞争开销。真实分配器会把全局锁拆成per-thread cache或者per-arena锁减少线程互相等待。这里只提醒一点第二版和第三版都不线程安全你把它用进多线程项目之前必须加锁。5. 性能升级从first-fit到分离空闲链表值不值得做5.1 first-fit的瓶颈遍历越来越慢空闲块越分越碎第三版用的是first-fit策略每次都从堆头开始扫描找到第一个足够大的空闲块就分配。它的优点是简单、合并逻辑好写缺点是分配越靠后的块扫描路径越长。更隐蔽的问题是first-fit倾向于把大块拆成小块而且拆出来的小块大多留在堆前部后面的空闲块被高地址的大块占着前面碎成一片。程序持续运行每次malloc都要一路跳过几十个碎片CPU时间全花在遍历上。best-fit能减少碎片但要遍历所有空闲块才能选中最合适的那一个代价更高。真正能同时改善二者的做法是把空闲块按照大小分类管理这就是分离适配。5.2 分离适配的核心按大小桶组织空闲链表分离适配的思想很简单把空闲块按大小范围分到几个桶桶内用双向链表串起来。malloc时先算请求属于哪个桶去桶里找找不到再向更大的桶借free时把块插回对应桶同时还是做前后合并。这样扫描范围从“整个堆”缩小到“几个相同量级的块”碎片也更容易控制。块头结构要扩展增加两个指针。为了让指针只在空闲时有效常见做法是复用数据区的前8个字节存prev/next但教学代码里直接用header字段更清晰typedef struct block_header { size_t size; int free; struct block_header *prev; // 仅空闲时使用 struct block_header *next; // 仅空闲时使用 } block_header_t;桶定义和插入删除逻辑是核心。下面是一个简化的5桶版本#define NUM_BUCKETS 5 static block_header_t *free_buckets[NUM_BUCKETS]; static int bucket_index(size_t n) { if (n 16) return 0; if (n 64) return 1; if (n 256) return 2; if (n 1024) return 3; return 4; } static void list_insert(block_header_t *h) { int idx bucket_index(h-size); h-prev NULL; h-next free_buckets[idx]; if (free_buckets[idx]) free_buckets[idx]-prev h; free_buckets[idx] h; } static void list_remove(block_header_t *h) { if (h-prev) h-prev-next h-next; else free_buckets[bucket_index(h-size)] h-next; if (h-next) h-next-prev h-prev; h-prev h-next NULL; }bucket_index的边界值要仔细选。如果请求是17字节按上面的分桶进64那一档资源浪费不可控所以生产级会用更细的对数档位比如16、32、64、128这样递增。学习版可以先按幂次分理解后再调间距。list_insert和list_remove是双向链表的标准操作注意在list_insert时处理旧链表头部的prev指针否则链表会出现环遍历死循环。把分离适配接进malloc时主体的变化是先尝试从对应桶取出一个块如果没有就向右找第一个非空桶从里面借一块。借来之后如果块太大还要分裂把剩余空闲块挂回正确桶。free则先做合并再把合并后的块插入对应桶。这里不再贴完整代码因为具体合并逻辑要把上一章的prev_block和footer全部兼容改动面很大。我个人的建议是先跑通第三版再用这版桶结构去替换第三版的遍历逻辑。5.3 什么时候值得上分离适配场景判断和成本分离适配不是银弹。每次插入删除要多维护两个指针内存里每个空闲块要额外付出16字节的链指针开销如果程序里的分配都是几十字节的小对象这个成本占比很高。适合上分离适配的场景有几个特征分配次数极多而且对象大小集中在几个档位比如游戏引擎里的vector、string、事件对象。这时桶里的块大小相近遍历极少缓存也友好。另一个特征是程序里有大量同一大小的临时对象free后立刻又分配分离适配能让它们从桶里直接命中不会触发brk。如果只是周期性分配大数组、分配后长时间持有first-fit加合并已经够用。更强的优化方向是线程本地缓存把每个线程的free对象暂时留在线程私有列表里避免全局锁竞争。但那是另一个工程深度了。判断标准很简单先跑基准看你的程序在malloc上花了多少CPU和系统调用时间占比不到5%别折腾。6. 尾声用统计和canary验证你的分配器外加一个习惯三分写七分验。手写malloc最怕的是逻辑看着对实际越界了却不崩。我会在header里加一个magic number并在分配块的数据区尾部埋canary字节free时检查它们有没有被改写。#define MAGIC 0x5A110C // header里加一行 unsigned int magic; // canary放在ALIGN后的空间末端例如请求10字节对齐16尾部6个字节放固定值 static void set_canary(void *ptr, size_t request, size_t aligned) { char *base (char *)ptr request; size_t len aligned - request; for (size_t i 0; i len; i) base[i] 0xCD; }这样用户只写request长度时canary区域不会被碰一旦越界写free时就能发现。配合全局计数器统计alloc_count、free_count、bytes_allocated在程序结束前打印出来能立刻看出有没有漏free。长期分配但free很少那个程序本身就有内存增长问题。我自己调试分配器的习惯是先以最小请求规模跑压力测试再开canary跑一遍最后关掉canary再去调性能。如果不先验证正确性就优化链表结构翻车之后想重新定位是合并bug还是越界写坏header成本会特别高。这个习惯帮我挡掉过好几次隐隐约约的越界问题希望你也能用上。希望帮到你。本文还有配套的精品资源点击获取