1. 项目概述为什么要自己写一个内存分配器内存分配器简单说就是程序向操作系统“批发”内存、再按需“零售”给代码用的那一层。平时我们用malloc和free感觉像是呼吸一样自然但真正动手自己实现一个完全是另外一回事——这中间涉及地址对齐、空间复用、碎片整理、链表操作这些底层细节任何一个环节想偷懒最后都会以诡异崩溃的形式找上门来。我在接手一个嵌入式项目时被迫做了这件事系统里有个模块高频创建和销毁大小不一的结构体默认的glibc malloc行为在这种场景下不但慢碎片率还高。换了几套现成的分配器源码之后我发现与其花时间调别人的轮子不如自己写一个高度裁剪、行为可控的分配器。于是就有了这篇文章里这套基于 free list first fit 的产物。这篇内容适合三类人第一类是系统编程方向的学生想亲眼看看malloc底层大概是什么样第二类是业务里遇到内存碎片、分配性能问题的工程师需要一个可改造的基础版本第三类是纯粹的好奇派想知道 glibc 和 jemalloc 那套复杂机制最初是从哪起步的。只要你有基本的 C 语言基础能看懂指针和结构体剩下的所有细节我都会摊开讲清楚。需要提前说明的是这里实现的分配器属于“教学级 实用级”的中间地带——比入门教程里那个只有几行sbrk的玩具复杂得多但远没有 tcmalloc 那种工业强度。它解决的是“可控”和“透明”这两个问题你清楚每一字节从哪里来、到哪里去出了 bug 一眼就能定位。2. 整体设计内存分配器的核心思路拆解2.1 先想清楚这个分配器要扛住什么场景动手写代码之前必须先回答一个问题我要这个分配器在什么场景下工作不同场景对分配器的要求天差地别通用场景程序里有大块数组、小块结构体、临时字符串分配和释放顺序乱七八糟。高并发场景多线程同时malloc/free分配器得加锁或者做线程局部缓存。嵌入式场景可用地址空间就是一块固定区域不能依赖sbrk扩展堆还要避免碎片。专用场景只分配固定大小对象比如网络包缓冲区、日志记录节点。我遇到的嵌入式场景属于第三类偏多但出于通用性考虑我还是按“通用分配器”的思路来设计只是不引入线程安全——单线程模型能让你先看清所有逻辑加锁是后面一行代码的事。另一个关键决策是使用sbrk还是mmap来向操作系统申请底层内存答案取决于你想让分配器多“原始”。sbrk是最传统的堆扩展方式语义简单把程序的 break 位置往高地址挪返回旧地址这就是一块新内存。mmap灵活但每次映射至少一个页小块分配用它是浪费。实现首选sbrk它是体验“操作系统给你分配内存”这个过程最直接的途径。2.2 空间换时间的设计free list 怎么选分配器的核心数据结构无非三种路线free list空闲链表、buddy system伙伴系统、slab分层缓存。Buddy 做的地址合并很有意思但按 2 的幂分块内部碎片能到 50%不适合小块密集场景。Slab 适合固定大小对象灵活性不够。所以 free list 是最自然的起点。Free list 又有几种组织方式隐式空闲链表遍历所有块找空闲块慢但结构最简单。显式空闲链表只把空闲块串成链表分配时只遍历空闲块节省时间。分离空闲链表不同大小的空闲块挂在不同链上分配近似 O(1)但回收逻辑复杂。我选了“显式空闲链表 first fit”。原因很直接数据结构的操作复杂度可控对每个空闲块额外付出的代价只是两个指针next和prev约 16 字节64 位系统。First fit 虽然要从头遍历但配合“适当时拆分大块”的策略实际分配块数有限时遍历成本很低。2.3 一个字节都不能浪费理解块头边界标记任何一个分配器都要能回答一个问题给你一个指针你怎么知道这块内存多大、是不是空闲答案是在“用户数据区”前面藏一个块头header里面记录块大小和状态。真正返回给用户的指针是跳过块头之后的位置。当用户调用free(p)时分配器正是通过p往回退固定大小拿到块头才知道这块区域属于谁。这里有个经典设计点边界标记。也就是在每个块的末尾也存一份“大小 状态”的记录。为什么这么干因为释放块时要做合并coalesce而判断“当前块的前一个邻居是否空闲”需要用到前一个块的块尾标记。如果没有边界标记你就得遍历整条链表才能找到前一个块的头部这个退化到 O(n) 的操作在频繁free的场景下很难接受。代价呢每个块多出 8 字节的尾部标记。这对大块无所谓对小块的浪费偏大。但设计上有一个经典优化空闲块本身有next/prev指针和大小字段完全可以把这些字段复用为“尾部标记”的替代品——空闲块不需要太多 metadata所以可以把next指针所在的位置当作前一个块的“尾部标记位”来用。为了讲解清晰我还是用了独立的尾部标记这块内容会在后续代码部分表现出来。注意写分配器最忌讳“为了省 8 字节省出 bug”。先实现正确再考虑优化。等到整体跑通再通过宏开关把尾部标记裁掉这才是稳妥路线。3. 数据结构和分配原理详解3.1 元数据设计块头和尾部标记64 位系统下对任意地址做 8 字节对齐是基本要求。块头设计如下typedef struct block_header { size_t size; // 当前块的总大小含头部、尾部、用户区 int free; // 1 表示空闲0 表示已分配 struct block_header *next; // 仅空闲时有效指向下一个空闲块 struct block_header *prev; // 仅空闲时有效指向前一个空闲块 } block_header_t;尾部标记是typedef struct block_footer { size_t size; // 与头部 size 一致用于向前查找 int free; // 与头部 free 一致 } block_footer_t;返回给用户的指针是(char*)header sizeof(block_header_t)。用户拿到这块地址一切对用户透明但代码必须时刻记住这个指针不是块起点真正能管理的是 header 层面的数据。尾部标记放在什么地方假设块总大小是size块头占sizeof(block_header_t)那么尾部标记的地址就是(char*)header size - sizeof(block_footer_t)。这个标记让“往后回溯前一块”这个动作只花两次内存读取。3.2 分配器怎么“找”合适的内存块分配内存时一个基础问题是用户要 100 字节但链上只有 256 字节的空闲块给不给直接给就浪费了 156 字节不给就分配失败但后续可能有很多 50 字节的请求。这时要做split分裂把 256 字节的空闲块切成两块——一块正好装下 100 字节含块头块尾另一块成为新的空闲块还挂在链上。split 的分界大小计算得小心。如果分裂后剩余的部分连一个最小块都算不上最小块至少要装下块头 尾部 8 字节用户空间那分裂就没有意义直接把整个大块给用户反而节省 metadata。通常的阈值是size_t remain old_size - req_size; if (remain sizeof(block_header_t) sizeof(block_footer_t) MIN_ALLOC_SIZE) { // 可以分裂 } else { // 不分裂整块给出 }MIN_ALLOC_SIZE 设成 8 字节足够保证内部碎片可接受。3.3 释放时的“逆操作”合并的工作原理free最迷人的逻辑在于合并coalesce。假设你释放了一块内存它的前一块空闲、后一块也空闲物理上它们是连续的但链表上分开挂着。如果不合并这个分配器在用一段时间后就会出现大量“看起来不连续的小洞”碎片率飙升。合并操作分三种情况前一块空闲后一块不空闲和前一块合并更新前一块 size。前一块不空闲后一块空闲和后一块合并更新当前块 size再把当前块插入空闲链表。前后都空闲三块合并成一块从链表删除后一块。判断前一块是否空闲用尾部标记往前跳prev_footer-size就是前一块的头部。判断后一块是否空闲用后一块头部当前块头地址加上当前size就是后一块头。一个常见坑合并时如果把前一块从空闲链表里摘除需要 O(n) 遍历找到它的前驱。为了避免这个时间消耗我在链表实现里保留prev指针双向链表从链上摘除任意节点只需操作相邻节点不用从头遍历。这是空间换时间的典型。3.4 探测邻居边界标记里的地址算术这块最容易出错。我用一个例子走一遍假设当前块头位于地址0x1000总大小0x200。块头本身占 0x20尾部标记占 0x10。那么当前块结束地址 0x1000 0x200 0x1200下一块头地址 0x1200当前块尾部标记地址 0x1200 - 0x10 0x11F0上一块的尾部标记地址 0x1000 - 0x10 0x0FF0上一块头部地址 0x0FF0处的 size 字段回退即0x0FF0 - prev_size注意上一块的尾部标记“紧挨”着当前块头但上一块头的自由空间要从0x0FF0 - prev_size开始。这个回退是上一块头地址 (char*)footer_of_prev - header_size_of_prev也就是从上一块尾部标记的size字段里拿到上一块总大小然后把指针移动到正确起点。每次写这种指针运算建议画一张地址图别靠心算。我在实现时吃过一次“差一个 header 大小导致合并错乱”的亏最后用 gdb 逐一打印块头地址才定位到。4. 完整实现从零手写一个可用分配器4.1 系统调用层申请和扩展堆底层的内存获取用sbrk。代码#include sys/types.h #include unistd.h #include stdint.h #include stdio.h #include string.h static block_header_t *heap_start NULL; static block_header_t *free_head NULL; static block_header_t *last_block NULL; // 堆的最后一个块方便扩展 static void *request_space(size_t size) { void *ptr sbrk((intptr_t)size); if (ptr (void *)-1) { return NULL; } return ptr; }sbrk(0)可以拿当前 break 地址但不能作为分配手段。实际扩展时计算需要的总字节数total header 对齐后用户大小 footer。调用sbrk(total)拿一块新区域。如果堆上已有last_block且它是free状态可以尝试直接扩展它而不是新建块。这个“扩展最后一块”的优化非常实用很多程序都是连续分配小对象然后逐个释放堆尾的空闲块被反复扩展和压缩可以减少大量合并动作。4.2 基础工具函数对齐和块遍历写几组工具函数后面的逻辑会清爽很多#define ALIGN8(x) (((x) 7) ~((size_t)7)) static size_t align_size(size_t s) { return ALIGN8(s); } static block_footer_t *get_footer(block_header_t *blk) { return (block_footer_t *)((char *)blk blk-size - sizeof(block_footer_t)); } static block_header_t *get_next_block(block_header_t *blk) { return (block_header_t *)((char *)blk blk-size); } static block_header_t *get_prev_block(block_header_t *blk) { block_footer_t *prev_footer (block_footer_t *)((char *)blk - sizeof(block_footer_t)); return (block_header_t *)((char *)blk - prev_footer-size); }这里有个容易忽略的问题blk-size里的值必须是块总数也就是用户大小、header、footer 全部加一起然后对齐到 8 的倍数。对齐的是“整个块”而不是“用户区”。假如只对齐用户区任何加的 metadata 都会破坏后续块的对齐性这是一个必须修正的设计细节。4.3 核心操作一空闲链表的摘除和插入空闲链表用双向链表节点就是block_header_t本身free1时才挂链。辅助函数非常简单直接static void list_remove(block_header_t *blk) { if (blk-prev) blk-prev-next blk-next; else free_head blk-next; if (blk-next) blk-next-prev blk-prev; blk-next NULL; blk-prev NULL; } static void list_insert(block_header_t *blk) { blk-next free_head; blk-prev NULL; if (free_head) free_head-prev blk; free_head blk; }list_insert默认插链表头部好处是 O(1)坏处是容易让链表顺序混乱。但合并机制会定期整理物理相邻的空闲块所以链顺序乱一些不影响正确性。若要改善局部性可以实现按地址排序插入代价是 O(n)实测对高碎片场景收益有限基础版本不做。4.4 核心操作二分裂split分配时找到的blk-size可能远大于需求。这时执行分裂static void split_block(block_header_t *blk, size_t req_total) { size_t remain blk-size - req_total; if (remain sizeof(block_header_t) sizeof(block_footer_t) MIN_ALLOC_SIZE) { block_header_t *new_blk (block_header_t *)((char *)blk req_total); new_blk-size remain; new_blk-free 1; block_footer_t *new_footer get_footer(new_blk); new_footer-size new_blk-size; new_footer-free 1; list_insert(new_blk); blk-size req_total; block_footer_t *footer get_footer(blk); footer-size blk-size; footer-free 0; } }注意分裂后blk被标记为已分配new_blk 标记为空闲并入链。这个操作在逻辑上要严格按顺序执行先设新块元数据再改旧块元数据最后挂链避免中间状态导致遍历出错。4.5 核心操作三合并coalesce释放时核心逻辑如下static void *coalesce(block_header_t *blk) { block_header_t *prev NULL; block_header_t *next get_next_block(blk); int prev_free 0; if ((char *)blk ! (char *)heap_start) { block_footer_t *prev_footer (block_footer_t *)((char *)blk - sizeof(block_footer_t)); if (prev_footer-free) { prev (block_header_t *)((char *)blk - prev_footer-size); prev_free 1; } } if (prev_free) { list_remove(prev); if (next-free) { list_remove(next); prev-size prev-size blk-size next-size; } else { prev-size prev-size blk-size; } block_footer_t *f get_footer(prev); f-size prev-size; f-free 1; list_insert(prev); return prev; } else { if (next-free) { list_remove(next); blk-size blk-size next-size; block_footer_t *f get_footer(blk); f-size blk-size; f-free 1; list_insert(blk); return blk; } list_insert(blk); return blk; } }这里有个关键点判断“当前块是不是堆尾”很重要。如果next的地址已经超出堆范围就不能访问next-free。所以在分配器里维护了last_blockif ((char*)next_block (char*)last_block)就代表当前块是堆尾。我最初写的时候忽略了结果在边界上读到野指针崩得稀里哗啦。另一个细节三块合并时next-free判断必须在移除prev之前做因为list_remove会改掉next的prev指针但next-free不受影响。逻辑顺序最好是在移除之前先把所有状态读出来避免后续对已摘除节点的二次访问。4.6 malloc 和 free 主流程void *my_malloc(size_t n) { if (n 0) return NULL; size_t user_size align_size(n); size_t total sizeof(block_header_t) user_size sizeof(block_footer_t); block_header_t *blk free_head; while (blk) { if (blk-size total) { list_remove(blk); split_block(blk, total); blk-free 0; block_footer_t *f get_footer(blk); f-free 0; memset((char *)blk sizeof(block_header_t), 0, user_size); return (char *)blk sizeof(block_header_t); } blk blk-next; } // 没有空闲块扩展堆 block_header_t *new_block request_space(total); if (!new_block) return NULL; new_block-size total; new_block-free 0; new_block-next NULL; new_block-prev NULL; block_footer_t *f get_footer(new_block); f-size total; f-free 0; if (last_block last_block-free) { // 合并到最后一个空闲块节省元数据 last_block-size total; block_footer_t *lf get_footer(last_block); lf-size last_block-size; lf-free 0; return (char *)last_block sizeof(block_header_t); } // 正常补充链表 list_insert(new_block); list_remove(new_block); new_block-free 0; if (!heap_start) heap_start new_block; last_block new_block; return (char *)new_block sizeof(block_header_t); }这段代码里注意一个细节list_insert(new_block); list_remove(new_block);这两行看起来很“多此一举”但其实是为了让 free list 的指针正确初始化list_insert会把prev/next置好然后立刻移除从而得到一个干净的节点。这个写法是我自己的习惯可能不优雅但它保证了新块不会残留脏指针。free主流程void my_free(void *ptr) { if (!ptr) return; block_header_t *blk (block_header_t *)((char *)ptr - sizeof(block_header_t)); if (blk-free) { fprintf(stderr, double free detected!\n); return; } blk-free 1; block_footer_t *f get_footer(blk); f-free 1; block_header_t *merged coalesce(blk); (void)merged; }这里我加了一个double free检测虽然不能拦截所有非法释放但至少能挡住最蠢的重复释放。真正完整的检测需要维护一个“已分配块表”复杂度大幅上升教学版不搞。4.7 参数计算一个具体例子的完整推演假设用户调用my_malloc(100)。n 100align_size(100) 1048 对齐后是 104。total sizeof(block_header_t) 104 sizeof(block_footer_t)。64 位系统block_header_t是 4 个 8 字节字段共 32 字节size、free、next、prevblock_footer_t是两个 8 字节字段共 16 字节。所以total 32 104 16 152。对齐后块大小 152 是 8 的倍数满足后续所有块的地址对齐。查找空闲链表如果找到一个 512 字节的空闲块remain 512 - 152 360远超最小分裂阈值于是分裂出 360 字节的新空闲块。返回给用户的地址是blk 32字节偏移处用户最多可以安全写入 104 字节因为后面还有 16 字节的 footer 不能动。这里最容易被误解的是虽然用户申请 100 字节但分配器实际消耗了 152 字节内存。如果你用sbrk统计总扩展量最终会明显大于所有malloc请求之和。这正是“内存分配器有元数据开销”的直观体现。4.8 加一个 macro 开关测试方便为了观察不同元数据策略的影响可以加宏控制边界标记的有无#ifdef USE_BOUNDARY_TAG // 带 footer 的逻辑 #else // 不带 footer合并时改用 prev/next 指针判断前一块 #endif实测下来去掉 footer 能省约 10% 元数据开销但合并逻辑复杂度上升一个量级。对初学者我强烈建议保留 footer。对性能敏感且块平均大小较大的系统再去掉 footer。5. 常见问题与排查技巧实录5.1 为什么 free 之后程序访问旧指针没崩溃因为free只是把块标记为空闲并入链并没有把内存归还操作系统也没有清零。后续my_malloc可能把这个块重新分配出去并覆盖数据于是“悬空指针”看起来刚开始没事等重新分配后才炸。这是所有手写分配器的经典陷阱。调试建议free时往用户区填充固定模式比如0xDEADBEEF下次读到这个标记就知道是已释放内存被误用。这种“毒化内存”技巧在工业级分配器里是标配。5.2 对齐错误导致的奇偶地址崩溃如果你的header结构体里有size_t8 字节但header起点不在 8 字节边界上size字段的读写可能触发总线错误尤其在某些嵌入式架构上。保证对齐最简单的办法是所有块总大小按 8 对齐初始heap_start也按 8 对齐。sbrk返回的地址通常已经页对齐没问题但如果你把分配器跑在自己的大数组上比如static char heap[65536]数组本身的起始地址可能只按 1 字节对齐这时要先做手工对齐char *heap_raw (char *)heap_region; uintptr_t aligned (uintptr_t)heap_raw; if (aligned % 8 ! 0) { aligned 8 - aligned % 8; }不处理这个问题的话跑几次就会遇到莫名其妙的SIGBUS。5.3 first fit 导致的最大块问题First fit 策略虽然简单但有一个隐蔽缺点它容易在链表头部积累大量小碎片而一个大块请求到来时会遍历很久才找到合适的大块。一个非常有效的改造是next fit每次查找不是从头开始而是链表指针记下上次找到的位置从那里继续。实现改动不超过十行却能把典型的分配序列的性能提升 30% 以上。另一个改造是best fit遍历所有空闲块选一个“刚好够”的最小块。它在碎片率上通常优于 first fit但 O(n) 遍历不可避免。对块数量很大的场景可以先考虑拆分大块 first fit 的组合。5.4 多个分配器实例如何共存嵌入式里常见的情况是一个程序多个内存池A 模块用池 1B 模块用池 2。此时分配器需要支持“指定池”的接口而不是全局只用一个堆。改造方式是把全局变量包进一个结构体typedef struct allocator { block_header_t *heap_start; block_header_t *free_head; block_header_t *last_block; } allocator_t;所有函数第一个参数都传allocator_t *。这个改动对原有实现来说不算难但需要仔细排查每一处用到全局变量的地方。我自己在改这块时踩过坑有个函数内部居然直接读了free_head没走参数结果两个池互相污染数据乱成一锅粥。5.5 free 的块在链上“丢了”新手经常遇到一个问题某次释放后链上的空闲块数量明显不对或者合并后指针断裂。排查思路就三句话打印链表长度、打印每个块地址、验证地址连续性。写一个 debug 函数void debug_dump_free_list() { int cnt 0; for (block_header_t *b free_head; b; b b-next) { printf([%d] addr%p size%zu free%d\n, cnt, (void *)b, b-size, b-free); cnt; if (cnt 100) break; // 防死循环 } printf(total free blocks %d\n, cnt); }同时验证每个空闲块的(char*)b b-size是否正好等于物理上下一块的地址。如果不等说明合并时 size 更新错了或者 footer 写错。这一步能定位大多数链表断裂问题。5.6 死循环链表成环了如果某个块被list_insert插了两次就可能成环。另一个常见的成环原因是list_remove里给free_head赋值时没考虑blk-prev NULL的情形。成环比“丢块”更好查只要在 debug 函数里加一个计数器上限超过阈值就打印“疑似死循环”。5.7 性能测试的基准手段写完分配器后要不要替换系统malloc跑一轮真实负载我的建议是先跑一个简单的压力测试int main() { const int N 100000; void *ptrs[N]; srand(12345); for (int i 0; i N; i) { int size rand() % 512 1; ptrs[i] my_malloc(size); if (ptrs[i]) memset(ptrs[i], 0xAA, size); if (i % 3 0 i 0) { my_free(ptrs[i / 3]); } } return 0; }对比glibc malloc你会发现自己的分配器在小块分配上可能并不慢但碎片率更高。如果把free顺序改成“全部释放后再分配”差距会更明显。这些指标可以量化打印sbrk(0)前后的差值和用户申请的总字节数相除就能得到“分配效率”通常在 70%–90% 这个区间就算合格。6. 后续还能怎么扩展这个基础版本已经能跑但离可以“搬到生产项目里”还有几道坎。按优先级排列加锁多线程场景下最简单的是在my_malloc和my_free入口加一把全局互斥锁。性能会下降但正确性问题解决了。要更好的性能可以用线程局部缓存每线程持有小对象池。分离链表把空闲块按大小分类8~16、16~64、64~256……每类一条链。分配时直接去对应链找查找时间大幅缩短。这是从“教学版”走向“实用版”最重要的一步。收缩堆当前实现只会向操作系统“要内存”从不“归还”。对于长期运行的进程这很浪费。当last_block空闲时可以用sbrk负数参数减少堆空间。栅栏检测在用户区和 footer 之间插入“canary”值例如0xFEDCBA9876543210分配和释放时验证它是否被改写。一旦发现被改写立刻报错并精确定位越界写入点。我在实际项目中最终做到了第 3 步因为嵌入式系统的 RAM 上限摆在那里不回收堆尾会导致长时间运行时内存持续增长。做到第 4 步之后一次“某模块越界写坏下一块 footer”的严重 bug 被当场抓到省了不知道多少 debug 时间。这段经验我到现在都记得很清楚内存分配器这个领域看起来是把指针搬来搬去但真正拉开工程差距的永远是边界条件的处理——链表的边界、地址对齐的边界、堆尾的边界。每一条都是血泪换来的。 手写内存分配器：深入理解malloc/free底层原理与实现
1. 项目概述为什么要自己写一个内存分配器内存分配器简单说就是程序向操作系统“批发”内存、再按需“零售”给代码用的那一层。平时我们用malloc和free感觉像是呼吸一样自然但真正动手自己实现一个完全是另外一回事——这中间涉及地址对齐、空间复用、碎片整理、链表操作这些底层细节任何一个环节想偷懒最后都会以诡异崩溃的形式找上门来。我在接手一个嵌入式项目时被迫做了这件事系统里有个模块高频创建和销毁大小不一的结构体默认的glibc malloc行为在这种场景下不但慢碎片率还高。换了几套现成的分配器源码之后我发现与其花时间调别人的轮子不如自己写一个高度裁剪、行为可控的分配器。于是就有了这篇文章里这套基于 free list first fit 的产物。这篇内容适合三类人第一类是系统编程方向的学生想亲眼看看malloc底层大概是什么样第二类是业务里遇到内存碎片、分配性能问题的工程师需要一个可改造的基础版本第三类是纯粹的好奇派想知道 glibc 和 jemalloc 那套复杂机制最初是从哪起步的。只要你有基本的 C 语言基础能看懂指针和结构体剩下的所有细节我都会摊开讲清楚。需要提前说明的是这里实现的分配器属于“教学级 实用级”的中间地带——比入门教程里那个只有几行sbrk的玩具复杂得多但远没有 tcmalloc 那种工业强度。它解决的是“可控”和“透明”这两个问题你清楚每一字节从哪里来、到哪里去出了 bug 一眼就能定位。2. 整体设计内存分配器的核心思路拆解2.1 先想清楚这个分配器要扛住什么场景动手写代码之前必须先回答一个问题我要这个分配器在什么场景下工作不同场景对分配器的要求天差地别通用场景程序里有大块数组、小块结构体、临时字符串分配和释放顺序乱七八糟。高并发场景多线程同时malloc/free分配器得加锁或者做线程局部缓存。嵌入式场景可用地址空间就是一块固定区域不能依赖sbrk扩展堆还要避免碎片。专用场景只分配固定大小对象比如网络包缓冲区、日志记录节点。我遇到的嵌入式场景属于第三类偏多但出于通用性考虑我还是按“通用分配器”的思路来设计只是不引入线程安全——单线程模型能让你先看清所有逻辑加锁是后面一行代码的事。另一个关键决策是使用sbrk还是mmap来向操作系统申请底层内存答案取决于你想让分配器多“原始”。sbrk是最传统的堆扩展方式语义简单把程序的 break 位置往高地址挪返回旧地址这就是一块新内存。mmap灵活但每次映射至少一个页小块分配用它是浪费。实现首选sbrk它是体验“操作系统给你分配内存”这个过程最直接的途径。2.2 空间换时间的设计free list 怎么选分配器的核心数据结构无非三种路线free list空闲链表、buddy system伙伴系统、slab分层缓存。Buddy 做的地址合并很有意思但按 2 的幂分块内部碎片能到 50%不适合小块密集场景。Slab 适合固定大小对象灵活性不够。所以 free list 是最自然的起点。Free list 又有几种组织方式隐式空闲链表遍历所有块找空闲块慢但结构最简单。显式空闲链表只把空闲块串成链表分配时只遍历空闲块节省时间。分离空闲链表不同大小的空闲块挂在不同链上分配近似 O(1)但回收逻辑复杂。我选了“显式空闲链表 first fit”。原因很直接数据结构的操作复杂度可控对每个空闲块额外付出的代价只是两个指针next和prev约 16 字节64 位系统。First fit 虽然要从头遍历但配合“适当时拆分大块”的策略实际分配块数有限时遍历成本很低。2.3 一个字节都不能浪费理解块头边界标记任何一个分配器都要能回答一个问题给你一个指针你怎么知道这块内存多大、是不是空闲答案是在“用户数据区”前面藏一个块头header里面记录块大小和状态。真正返回给用户的指针是跳过块头之后的位置。当用户调用free(p)时分配器正是通过p往回退固定大小拿到块头才知道这块区域属于谁。这里有个经典设计点边界标记。也就是在每个块的末尾也存一份“大小 状态”的记录。为什么这么干因为释放块时要做合并coalesce而判断“当前块的前一个邻居是否空闲”需要用到前一个块的块尾标记。如果没有边界标记你就得遍历整条链表才能找到前一个块的头部这个退化到 O(n) 的操作在频繁free的场景下很难接受。代价呢每个块多出 8 字节的尾部标记。这对大块无所谓对小块的浪费偏大。但设计上有一个经典优化空闲块本身有next/prev指针和大小字段完全可以把这些字段复用为“尾部标记”的替代品——空闲块不需要太多 metadata所以可以把next指针所在的位置当作前一个块的“尾部标记位”来用。为了讲解清晰我还是用了独立的尾部标记这块内容会在后续代码部分表现出来。注意写分配器最忌讳“为了省 8 字节省出 bug”。先实现正确再考虑优化。等到整体跑通再通过宏开关把尾部标记裁掉这才是稳妥路线。3. 数据结构和分配原理详解3.1 元数据设计块头和尾部标记64 位系统下对任意地址做 8 字节对齐是基本要求。块头设计如下typedef struct block_header { size_t size; // 当前块的总大小含头部、尾部、用户区 int free; // 1 表示空闲0 表示已分配 struct block_header *next; // 仅空闲时有效指向下一个空闲块 struct block_header *prev; // 仅空闲时有效指向前一个空闲块 } block_header_t;尾部标记是typedef struct block_footer { size_t size; // 与头部 size 一致用于向前查找 int free; // 与头部 free 一致 } block_footer_t;返回给用户的指针是(char*)header sizeof(block_header_t)。用户拿到这块地址一切对用户透明但代码必须时刻记住这个指针不是块起点真正能管理的是 header 层面的数据。尾部标记放在什么地方假设块总大小是size块头占sizeof(block_header_t)那么尾部标记的地址就是(char*)header size - sizeof(block_footer_t)。这个标记让“往后回溯前一块”这个动作只花两次内存读取。3.2 分配器怎么“找”合适的内存块分配内存时一个基础问题是用户要 100 字节但链上只有 256 字节的空闲块给不给直接给就浪费了 156 字节不给就分配失败但后续可能有很多 50 字节的请求。这时要做split分裂把 256 字节的空闲块切成两块——一块正好装下 100 字节含块头块尾另一块成为新的空闲块还挂在链上。split 的分界大小计算得小心。如果分裂后剩余的部分连一个最小块都算不上最小块至少要装下块头 尾部 8 字节用户空间那分裂就没有意义直接把整个大块给用户反而节省 metadata。通常的阈值是size_t remain old_size - req_size; if (remain sizeof(block_header_t) sizeof(block_footer_t) MIN_ALLOC_SIZE) { // 可以分裂 } else { // 不分裂整块给出 }MIN_ALLOC_SIZE 设成 8 字节足够保证内部碎片可接受。3.3 释放时的“逆操作”合并的工作原理free最迷人的逻辑在于合并coalesce。假设你释放了一块内存它的前一块空闲、后一块也空闲物理上它们是连续的但链表上分开挂着。如果不合并这个分配器在用一段时间后就会出现大量“看起来不连续的小洞”碎片率飙升。合并操作分三种情况前一块空闲后一块不空闲和前一块合并更新前一块 size。前一块不空闲后一块空闲和后一块合并更新当前块 size再把当前块插入空闲链表。前后都空闲三块合并成一块从链表删除后一块。判断前一块是否空闲用尾部标记往前跳prev_footer-size就是前一块的头部。判断后一块是否空闲用后一块头部当前块头地址加上当前size就是后一块头。一个常见坑合并时如果把前一块从空闲链表里摘除需要 O(n) 遍历找到它的前驱。为了避免这个时间消耗我在链表实现里保留prev指针双向链表从链上摘除任意节点只需操作相邻节点不用从头遍历。这是空间换时间的典型。3.4 探测邻居边界标记里的地址算术这块最容易出错。我用一个例子走一遍假设当前块头位于地址0x1000总大小0x200。块头本身占 0x20尾部标记占 0x10。那么当前块结束地址 0x1000 0x200 0x1200下一块头地址 0x1200当前块尾部标记地址 0x1200 - 0x10 0x11F0上一块的尾部标记地址 0x1000 - 0x10 0x0FF0上一块头部地址 0x0FF0处的 size 字段回退即0x0FF0 - prev_size注意上一块的尾部标记“紧挨”着当前块头但上一块头的自由空间要从0x0FF0 - prev_size开始。这个回退是上一块头地址 (char*)footer_of_prev - header_size_of_prev也就是从上一块尾部标记的size字段里拿到上一块总大小然后把指针移动到正确起点。每次写这种指针运算建议画一张地址图别靠心算。我在实现时吃过一次“差一个 header 大小导致合并错乱”的亏最后用 gdb 逐一打印块头地址才定位到。4. 完整实现从零手写一个可用分配器4.1 系统调用层申请和扩展堆底层的内存获取用sbrk。代码#include sys/types.h #include unistd.h #include stdint.h #include stdio.h #include string.h static block_header_t *heap_start NULL; static block_header_t *free_head NULL; static block_header_t *last_block NULL; // 堆的最后一个块方便扩展 static void *request_space(size_t size) { void *ptr sbrk((intptr_t)size); if (ptr (void *)-1) { return NULL; } return ptr; }sbrk(0)可以拿当前 break 地址但不能作为分配手段。实际扩展时计算需要的总字节数total header 对齐后用户大小 footer。调用sbrk(total)拿一块新区域。如果堆上已有last_block且它是free状态可以尝试直接扩展它而不是新建块。这个“扩展最后一块”的优化非常实用很多程序都是连续分配小对象然后逐个释放堆尾的空闲块被反复扩展和压缩可以减少大量合并动作。4.2 基础工具函数对齐和块遍历写几组工具函数后面的逻辑会清爽很多#define ALIGN8(x) (((x) 7) ~((size_t)7)) static size_t align_size(size_t s) { return ALIGN8(s); } static block_footer_t *get_footer(block_header_t *blk) { return (block_footer_t *)((char *)blk blk-size - sizeof(block_footer_t)); } static block_header_t *get_next_block(block_header_t *blk) { return (block_header_t *)((char *)blk blk-size); } static block_header_t *get_prev_block(block_header_t *blk) { block_footer_t *prev_footer (block_footer_t *)((char *)blk - sizeof(block_footer_t)); return (block_header_t *)((char *)blk - prev_footer-size); }这里有个容易忽略的问题blk-size里的值必须是块总数也就是用户大小、header、footer 全部加一起然后对齐到 8 的倍数。对齐的是“整个块”而不是“用户区”。假如只对齐用户区任何加的 metadata 都会破坏后续块的对齐性这是一个必须修正的设计细节。4.3 核心操作一空闲链表的摘除和插入空闲链表用双向链表节点就是block_header_t本身free1时才挂链。辅助函数非常简单直接static void list_remove(block_header_t *blk) { if (blk-prev) blk-prev-next blk-next; else free_head blk-next; if (blk-next) blk-next-prev blk-prev; blk-next NULL; blk-prev NULL; } static void list_insert(block_header_t *blk) { blk-next free_head; blk-prev NULL; if (free_head) free_head-prev blk; free_head blk; }list_insert默认插链表头部好处是 O(1)坏处是容易让链表顺序混乱。但合并机制会定期整理物理相邻的空闲块所以链顺序乱一些不影响正确性。若要改善局部性可以实现按地址排序插入代价是 O(n)实测对高碎片场景收益有限基础版本不做。4.4 核心操作二分裂split分配时找到的blk-size可能远大于需求。这时执行分裂static void split_block(block_header_t *blk, size_t req_total) { size_t remain blk-size - req_total; if (remain sizeof(block_header_t) sizeof(block_footer_t) MIN_ALLOC_SIZE) { block_header_t *new_blk (block_header_t *)((char *)blk req_total); new_blk-size remain; new_blk-free 1; block_footer_t *new_footer get_footer(new_blk); new_footer-size new_blk-size; new_footer-free 1; list_insert(new_blk); blk-size req_total; block_footer_t *footer get_footer(blk); footer-size blk-size; footer-free 0; } }注意分裂后blk被标记为已分配new_blk 标记为空闲并入链。这个操作在逻辑上要严格按顺序执行先设新块元数据再改旧块元数据最后挂链避免中间状态导致遍历出错。4.5 核心操作三合并coalesce释放时核心逻辑如下static void *coalesce(block_header_t *blk) { block_header_t *prev NULL; block_header_t *next get_next_block(blk); int prev_free 0; if ((char *)blk ! (char *)heap_start) { block_footer_t *prev_footer (block_footer_t *)((char *)blk - sizeof(block_footer_t)); if (prev_footer-free) { prev (block_header_t *)((char *)blk - prev_footer-size); prev_free 1; } } if (prev_free) { list_remove(prev); if (next-free) { list_remove(next); prev-size prev-size blk-size next-size; } else { prev-size prev-size blk-size; } block_footer_t *f get_footer(prev); f-size prev-size; f-free 1; list_insert(prev); return prev; } else { if (next-free) { list_remove(next); blk-size blk-size next-size; block_footer_t *f get_footer(blk); f-size blk-size; f-free 1; list_insert(blk); return blk; } list_insert(blk); return blk; } }这里有个关键点判断“当前块是不是堆尾”很重要。如果next的地址已经超出堆范围就不能访问next-free。所以在分配器里维护了last_blockif ((char*)next_block (char*)last_block)就代表当前块是堆尾。我最初写的时候忽略了结果在边界上读到野指针崩得稀里哗啦。另一个细节三块合并时next-free判断必须在移除prev之前做因为list_remove会改掉next的prev指针但next-free不受影响。逻辑顺序最好是在移除之前先把所有状态读出来避免后续对已摘除节点的二次访问。4.6 malloc 和 free 主流程void *my_malloc(size_t n) { if (n 0) return NULL; size_t user_size align_size(n); size_t total sizeof(block_header_t) user_size sizeof(block_footer_t); block_header_t *blk free_head; while (blk) { if (blk-size total) { list_remove(blk); split_block(blk, total); blk-free 0; block_footer_t *f get_footer(blk); f-free 0; memset((char *)blk sizeof(block_header_t), 0, user_size); return (char *)blk sizeof(block_header_t); } blk blk-next; } // 没有空闲块扩展堆 block_header_t *new_block request_space(total); if (!new_block) return NULL; new_block-size total; new_block-free 0; new_block-next NULL; new_block-prev NULL; block_footer_t *f get_footer(new_block); f-size total; f-free 0; if (last_block last_block-free) { // 合并到最后一个空闲块节省元数据 last_block-size total; block_footer_t *lf get_footer(last_block); lf-size last_block-size; lf-free 0; return (char *)last_block sizeof(block_header_t); } // 正常补充链表 list_insert(new_block); list_remove(new_block); new_block-free 0; if (!heap_start) heap_start new_block; last_block new_block; return (char *)new_block sizeof(block_header_t); }这段代码里注意一个细节list_insert(new_block); list_remove(new_block);这两行看起来很“多此一举”但其实是为了让 free list 的指针正确初始化list_insert会把prev/next置好然后立刻移除从而得到一个干净的节点。这个写法是我自己的习惯可能不优雅但它保证了新块不会残留脏指针。free主流程void my_free(void *ptr) { if (!ptr) return; block_header_t *blk (block_header_t *)((char *)ptr - sizeof(block_header_t)); if (blk-free) { fprintf(stderr, double free detected!\n); return; } blk-free 1; block_footer_t *f get_footer(blk); f-free 1; block_header_t *merged coalesce(blk); (void)merged; }这里我加了一个double free检测虽然不能拦截所有非法释放但至少能挡住最蠢的重复释放。真正完整的检测需要维护一个“已分配块表”复杂度大幅上升教学版不搞。4.7 参数计算一个具体例子的完整推演假设用户调用my_malloc(100)。n 100align_size(100) 1048 对齐后是 104。total sizeof(block_header_t) 104 sizeof(block_footer_t)。64 位系统block_header_t是 4 个 8 字节字段共 32 字节size、free、next、prevblock_footer_t是两个 8 字节字段共 16 字节。所以total 32 104 16 152。对齐后块大小 152 是 8 的倍数满足后续所有块的地址对齐。查找空闲链表如果找到一个 512 字节的空闲块remain 512 - 152 360远超最小分裂阈值于是分裂出 360 字节的新空闲块。返回给用户的地址是blk 32字节偏移处用户最多可以安全写入 104 字节因为后面还有 16 字节的 footer 不能动。这里最容易被误解的是虽然用户申请 100 字节但分配器实际消耗了 152 字节内存。如果你用sbrk统计总扩展量最终会明显大于所有malloc请求之和。这正是“内存分配器有元数据开销”的直观体现。4.8 加一个 macro 开关测试方便为了观察不同元数据策略的影响可以加宏控制边界标记的有无#ifdef USE_BOUNDARY_TAG // 带 footer 的逻辑 #else // 不带 footer合并时改用 prev/next 指针判断前一块 #endif实测下来去掉 footer 能省约 10% 元数据开销但合并逻辑复杂度上升一个量级。对初学者我强烈建议保留 footer。对性能敏感且块平均大小较大的系统再去掉 footer。5. 常见问题与排查技巧实录5.1 为什么 free 之后程序访问旧指针没崩溃因为free只是把块标记为空闲并入链并没有把内存归还操作系统也没有清零。后续my_malloc可能把这个块重新分配出去并覆盖数据于是“悬空指针”看起来刚开始没事等重新分配后才炸。这是所有手写分配器的经典陷阱。调试建议free时往用户区填充固定模式比如0xDEADBEEF下次读到这个标记就知道是已释放内存被误用。这种“毒化内存”技巧在工业级分配器里是标配。5.2 对齐错误导致的奇偶地址崩溃如果你的header结构体里有size_t8 字节但header起点不在 8 字节边界上size字段的读写可能触发总线错误尤其在某些嵌入式架构上。保证对齐最简单的办法是所有块总大小按 8 对齐初始heap_start也按 8 对齐。sbrk返回的地址通常已经页对齐没问题但如果你把分配器跑在自己的大数组上比如static char heap[65536]数组本身的起始地址可能只按 1 字节对齐这时要先做手工对齐char *heap_raw (char *)heap_region; uintptr_t aligned (uintptr_t)heap_raw; if (aligned % 8 ! 0) { aligned 8 - aligned % 8; }不处理这个问题的话跑几次就会遇到莫名其妙的SIGBUS。5.3 first fit 导致的最大块问题First fit 策略虽然简单但有一个隐蔽缺点它容易在链表头部积累大量小碎片而一个大块请求到来时会遍历很久才找到合适的大块。一个非常有效的改造是next fit每次查找不是从头开始而是链表指针记下上次找到的位置从那里继续。实现改动不超过十行却能把典型的分配序列的性能提升 30% 以上。另一个改造是best fit遍历所有空闲块选一个“刚好够”的最小块。它在碎片率上通常优于 first fit但 O(n) 遍历不可避免。对块数量很大的场景可以先考虑拆分大块 first fit 的组合。5.4 多个分配器实例如何共存嵌入式里常见的情况是一个程序多个内存池A 模块用池 1B 模块用池 2。此时分配器需要支持“指定池”的接口而不是全局只用一个堆。改造方式是把全局变量包进一个结构体typedef struct allocator { block_header_t *heap_start; block_header_t *free_head; block_header_t *last_block; } allocator_t;所有函数第一个参数都传allocator_t *。这个改动对原有实现来说不算难但需要仔细排查每一处用到全局变量的地方。我自己在改这块时踩过坑有个函数内部居然直接读了free_head没走参数结果两个池互相污染数据乱成一锅粥。5.5 free 的块在链上“丢了”新手经常遇到一个问题某次释放后链上的空闲块数量明显不对或者合并后指针断裂。排查思路就三句话打印链表长度、打印每个块地址、验证地址连续性。写一个 debug 函数void debug_dump_free_list() { int cnt 0; for (block_header_t *b free_head; b; b b-next) { printf([%d] addr%p size%zu free%d\n, cnt, (void *)b, b-size, b-free); cnt; if (cnt 100) break; // 防死循环 } printf(total free blocks %d\n, cnt); }同时验证每个空闲块的(char*)b b-size是否正好等于物理上下一块的地址。如果不等说明合并时 size 更新错了或者 footer 写错。这一步能定位大多数链表断裂问题。5.6 死循环链表成环了如果某个块被list_insert插了两次就可能成环。另一个常见的成环原因是list_remove里给free_head赋值时没考虑blk-prev NULL的情形。成环比“丢块”更好查只要在 debug 函数里加一个计数器上限超过阈值就打印“疑似死循环”。5.7 性能测试的基准手段写完分配器后要不要替换系统malloc跑一轮真实负载我的建议是先跑一个简单的压力测试int main() { const int N 100000; void *ptrs[N]; srand(12345); for (int i 0; i N; i) { int size rand() % 512 1; ptrs[i] my_malloc(size); if (ptrs[i]) memset(ptrs[i], 0xAA, size); if (i % 3 0 i 0) { my_free(ptrs[i / 3]); } } return 0; }对比glibc malloc你会发现自己的分配器在小块分配上可能并不慢但碎片率更高。如果把free顺序改成“全部释放后再分配”差距会更明显。这些指标可以量化打印sbrk(0)前后的差值和用户申请的总字节数相除就能得到“分配效率”通常在 70%–90% 这个区间就算合格。6. 后续还能怎么扩展这个基础版本已经能跑但离可以“搬到生产项目里”还有几道坎。按优先级排列加锁多线程场景下最简单的是在my_malloc和my_free入口加一把全局互斥锁。性能会下降但正确性问题解决了。要更好的性能可以用线程局部缓存每线程持有小对象池。分离链表把空闲块按大小分类8~16、16~64、64~256……每类一条链。分配时直接去对应链找查找时间大幅缩短。这是从“教学版”走向“实用版”最重要的一步。收缩堆当前实现只会向操作系统“要内存”从不“归还”。对于长期运行的进程这很浪费。当last_block空闲时可以用sbrk负数参数减少堆空间。栅栏检测在用户区和 footer 之间插入“canary”值例如0xFEDCBA9876543210分配和释放时验证它是否被改写。一旦发现被改写立刻报错并精确定位越界写入点。我在实际项目中最终做到了第 3 步因为嵌入式系统的 RAM 上限摆在那里不回收堆尾会导致长时间运行时内存持续增长。做到第 4 步之后一次“某模块越界写坏下一块 footer”的严重 bug 被当场抓到省了不知道多少 debug 时间。这段经验我到现在都记得很清楚内存分配器这个领域看起来是把指针搬来搬去但真正拉开工程差距的永远是边界条件的处理——链表的边界、地址对齐的边界、堆尾的边界。每一条都是血泪换来的。