最近在折腾一个个人项目时频繁调malloc/free总觉得心里不踏实——分配性能、碎片率、线程竞争这些都被 glibc 包得严严实实出了问题只有黑盒经验没有底层直觉。于是花了一周自己动手实现了一个可用的内存分配器。这篇文章把完整思路、代码细节和踩过的坑都记录下来希望能给同样对动态内存管理好奇的读者一点参考。先说明这个分配器解决什么问题它替代系统默认的malloc/free在堆区维护一批用户态内存块处理申请、释放、合并、分割等逻辑。适合三类人看——想搞懂 glibc malloc 底层原理的、做嵌入式或内核模块需要自定义内存策略的以及纯粹想训练 C 语言指针和链表功底的。1. 写之前必须先想清楚的三个问题1.1 分配器面对的核心矛盾速度、碎片、线程安全动态内存分配的核心矛盾说白了就三条分配要快碎片要少多线程下还要稳。大部分时候这三者相互打架——你为了快可能维护一组精确的空闲桶结果释放时合并成本变高你为了碎片少每次分配都去扫描全堆寻找最合适块速度又下去了你要线程安全加一把大锁并发直接变串行。我在动手前给自己的目标是在单线程场景下分配和释放的均摊复杂度接近 O(1)最坏情况 O(n)内存碎片率控制在可接受范围。对于多线程先不追求极致性能只保证正确性——用一把全局互斥锁保护堆元数据。这个目标定得不高但足以覆盖绝大多数自定义场景。1.2 先搞清操作系统在底层给了你什么要实现自己的分配器先得清楚从系统层能拿到哪块内存。Linux 下就两个途径brk和mmap。brk把程序 break 指针往高地址推适合小内存块的扩展mmap可以映射一大块匿名内存适合大块分配。大多数教学级分配器都用brk因为它简单——一次系统调用就能把堆扩大几 MB后续所有内存块都在这个区域内自己管理。不用反复调系统调用。这里我踩过一个认知上的坑以为malloc每次调用都会触发系统调用其实不是。malloc内部先查用户态空闲链表只有链表空了才通过brk向内核要内存。所以分配器的核心工作不是“向内核要内存”而是“管理已经从内核拿来的内存”。1.3 最小可用数据结构空闲块链表分配器最经典的数据结构是空闲链表把所有空闲块串成一个链表。分配时从链表里找一块足够大的空闲块切给你释放时把内存块还回链表。但这个朴素方案有几个必须处理的细节块头元数据放哪怎么快速判断块大小释放时怎么和物理相邻的空闲块合并第一个版本里我用的是隐式空闲链表 边界标记的方案——每个内存块头部记录大小末尾也记录大小或标记位这样释放某一块时可以向右看物理相邻块的状态向左也能查到前一块的大小从而决定是否需要合并。这个设计是经典教材里的做法稳定、直观、容易调试。2. 数据结构与核心宏定义先把地基打稳2.1 内存块头与对齐规则先定义两个宏#define ALIGNMENT 16 #define ALIGN(size) (((size) (ALIGNMENT - 1)) ~(ALIGNMENT - 1)) typedef struct BlockHeader { size_t size; // 块大小包含头部本身 size_t allocated; // 是否已分配1为已分配 struct BlockHeader *next_free; // 空闲链表指针仅空闲块使用 } BlockHeader; #define HEADER_SIZE (ALIGN(sizeof(BlockHeader))) #define MIN_BLOCK_SIZE (HEADER_SIZE ALIGNMENT)这里有几个关键决定。第一个是ALIGNMENT设为 16 字节保证返回给用户的对齐能满足 SSE 指令的 16 字节需求同时对 64 位系统上的max_align_t也够了。第二个是头部里除了 size 还放了allocated标记和next_free指针这样空闲块天然就是一个链表节点不再单独创建链表结构。2.2 为什么需要边界标记边界标记boundary tag是让释放操作能 O(1) 合并相邻块的关键。我在块头和块尾各存一份 size 和 allocated 信息。块尾的元数据比头部多 8 字节但换来了释放时的快速判断能力。举个例子你释放一块内存想看看它前面那块是否也空闲。如果没有尾部标记你得从头遍历到前面那块才能知道它的边界在哪。有了尾部标记直接拿当前块头地址减去前一块的 size前一块 size 记录在它自己的头部可以通过当前块头往前偏移得到然后读前一块的allocated标记立刻知道能否合并。这个设计思路在 real-world 分配器里也很常见比如早期的 dlmalloc 就是边界标记的典型实践。虽然有额外空间开销但对于学习和通用场景性价比极高。2.3 最小块大小与外部碎片约束最小块大小不是拍脑袋定的。它至少要能放得下一个 BlockHeader 加上最小可用载荷。由于 BlockHeader 里有 next_free 指针空闲块可以直接利用数据区低 8 字节存下一个空闲块地址所以理论上最小块大小可以缩到HEADER_SIZE。但实际操作中我设了MIN_BLOCK_SIZE为头部加上 16 字节对齐载荷这样能避免用户申请 1 字节时返回一个过小的块后面反复触发分割逻辑。碎片问题也得在这里就考虑。内存碎片分两种内部碎片和外部碎片。内部碎片是块被对齐后剩下的尾部空隙控制好 ALIGN 粒度即可。外部碎片是最头疼的——反复分配释放后空闲块被切得七零八落导致即使总空闲内存足够也无法满足一个连续大块请求。边界标记 合并机制就是解决外部碎片的常规武器后面我会重点讲合并的实现。3. 第一版实现基于隐式链表的 malloc 与 free这部分是核心我直接贴完整代码一步步拆解。3.1 全局堆管理从 brk 扩展内存static BlockHeader *heap_start NULL; static BlockHeader *heap_end NULL; static BlockHeader *free_list_head NULL; // 简化版单链表heap_start指向堆区起始块heap_end指向堆末尾。当空闲链表里找不到足够块时调用extend_heapstatic BlockHeader *extend_heap(size_t size) { BlockHeader *block (BlockHeader *)sbrk(size); if (block (void *)-1) return NULL; block-size size; block-allocated 0; block-next_free NULL; insert_into_free_list(block); return block; }这里我用sbrk而不是mmap因为sbrk简单直接适合教学版本。真实分配器通常对大块超过MMAP_THRESHOLD一般是 128KB用mmap这样释放大块时可以直接还给内核而不是留在堆里。我在后续优化版里也加了这条逻辑。3.2 首次适配first fit的插入与分配static BlockHeader *find_fit(size_t size) { BlockHeader *curr free_list_head; while (curr ! NULL) { if (curr-size size HEADER_SIZE) { return curr; } curr curr-next_free; } return NULL; }这个是最朴素的 first fit 策略从头遍历空闲链表找第一块足够大的块。它的问题是容易在链表头部积累碎片导致后续分配越来越慢。但作为 v1 版本图的是简单可靠。拿到空闲块后还要判断是否需要分割。如果整块给你剩下的空间连一个最小块都放不下那就干脆整块分配多余的算内部碎片否则把块从中间切开前段给你后段留作新的空闲块。这个“剩下部分是否值得当新块”的阈值就是MIN_BLOCK_SIZEstatic void split_block(BlockHeader *block, size_t size) { size_t remaining block-size - size; if (remaining MIN_BLOCK_SIZE) { block-allocated 1; return; } BlockHeader *new_block (BlockHeader *)((char *)block size); new_block-size remaining; new_block-allocated 0; new_block-next_free block-next_free; block-size size; block-allocated 1; block-next_free NULL; // 更新 free list 中链表的连接 replace_in_free_list(block, new_block); }3.3 释放与前后合并coalescing释放的难点在于合并。释放ptr先拿到块头block (BlockHeader *)ptr - 1然后看它物理相邻的前块和后块是否空闲如果空闲就合并成一个大块。static BlockHeader *coalesce(BlockHeader *block) { BlockHeader *prev get_prev_block(block); BlockHeader *next get_next_block(block); if (next ! NULL !next-allocated) { block-size next-size; remove_from_free_list(next); } if (prev ! NULL !prev-allocated) { prev-size block-size; remove_from_free_list(block); return prev; } block-allocated 0; insert_into_free_list(block); return block; }get_prev_block的实现依赖于边界标记——读当前块头往前sizeof(size_t)的位置拿到前一块的 size然后(char *)block - prev_size就得到前一块地址。get_next_block更简单(char *)block block-size就是物理后一块只要不超过heap_end就说明存在。注意这里有个细节很容易写错**合并之后必须更新生效块头部的 size并处理 free list 的增删节点。**漏掉任何一环要么链表出现悬垂指针要么下一次分配拿到一个大小错误的块。3.4 内存对齐陷阱返回给用户的地址必须对齐写分配器最容易犯的一个低级错误是忽略返回地址的对齐。如果头部大小是 12 字节块起始地址是 0x1000那么数据区地址就是 0x100C这显然不是 16 的倍数。用户拿到这种地址一旦用 SSE 或 AVX 指令操作直接段错误。所以我强制HEADER_SIZE也做对齐ALIGN(sizeof(BlockHeader))。这样块起始地址对齐 16头大小也是 16 的倍数数据区天然对齐 16。对齐后的布局 | 16字节 header (size/allocated/next_free) | 数据区16字节对齐起点这个设计在 32 位和 64 位系统上都成立。我在 64 位 Linux 上验证过sizeof(BlockHeader)是 24 字节size 8 allocated 8 next_free 8对齐后 HEADER_SIZE 还是 32 字节。有 8 字节的 padding但值得。4. 性能优化从 O(n) 到近似 O(1) 的关键改造4.1 分离空闲链表segregated free list解决扫描慢问题v1 版本最大的瓶颈在find_fit——最坏情况下遍历整个空闲链表。当程序大量使用不同大小的对象时这种线性扫描会拖慢整体性能。经典解法是分离空闲链表按块大小分桶size class每个桶维护一条空闲链表。我参考了常见做法按 2 的幂分桶#define NUM_BUCKETS 16 static BlockHeader *free_list_buckets[NUM_BUCKETS]; static int size_to_bucket(size_t size) { int bucket 0; while (size 1 bucket NUM_BUCKETS - 1) { size 1; bucket; } return bucket; }这样分配 64 字节块时只查 bucket 5 附近的链表不再扫描全部。但分桶也带来新的问题桶内块大小有差异比如 512 字节的块放进 256 字节的桶必然浪费。所以更精细的分配器会在桶内做 best-fit或者用 slab 思想管理相同大小的对象。我用的折中方案是每个桶内部保持从小到大排序分配时查第一个足够大的块释放时按地址排序插入便于合并。4.2 大块走 mmap超过阈值直接还给内核v1 里所有块都从sbrk拿导致释放小内存块后堆区不会缩回去程序在整个生命周期里占用的 RSS驻留内存只增不减。对长期运行的服务来说这是致命伤。优化版加入大块策略申请大小超过 128KB 时不再从 free list 找而是直接mmap一个匿名内存段返回给用户释放时直接munmap。这个阈值和 glibc 的MMAP_THRESHOLD保持一致整体逻辑不算复杂#define MMAP_THRESHOLD (128 * 1024) void *malloc(size_t size) { size_t aligned ALIGN(size); if (aligned MMAP_THRESHOLD) { BlockHeader *block mmap(NULL, HEADER_SIZE aligned, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0); if (block MAP_FAILED) return NULL; block-size HEADER_SIZE aligned; block-allocated 1; block-mmapped 1; return (void *)(block 1); } // 走普通堆分配逻辑 }注意 mmap 出来的块要从 free list 体系里摘出来不参与合并。释放时判断mmapped标志走munmap分支即可。4.3 线程安全加锁一把大锁起步但别止步于此多线程环境里同一时刻多个线程并发修改 free list 会导致竞态条件。最粗暴的解法是一把全局锁static pthread_mutex_t mm_lock PTHREAD_MUTEX_INITIALIZER; void *malloc(size_t size) { pthread_mutex_lock(mm_lock); // 分配逻辑 pthread_mutex_unlock(mm_lock); return ptr; }这样做正确性没问题但多线程性能会退化到接近单线程。因为内存分配现在变成串行操作了。进一步的优化方向是线程本地缓存Thread Local StorageTLS为每个线程维护一个小型空闲块缓存线程自己释放的块先进 TLS不用加锁只有 TLS 满了或不足时才摸全局的 free list这时候才加锁。这个思路是 tcmalloc 的核心之一工程量不小但所带来的并发性能收益是肉眼可见的。我在项目里实现了简单的 TLS——维护一个无锁的固定大小缓存数组实测四线程下吞吐量提升约三倍。5. 测试、调试与性能剖析实录5.1 基础功能测试不能只靠打印写代码验证边界分配器是最容易出“看起来正常但内存已写烂”的代码。我写了一套基础测试用例重点覆盖这些边界void test_basic() { void *p1 malloc(16); void *p2 malloc(1024); void *p3 malloc(0); // 必须返回非 NULL 的可释放指针 assert(p1 p2 p3); memset(p1, 0xFF, 16); // 写满检查越界 free(p1); free(p2); free(p3); } void test_fragmentation() { // 反复分配释放不同大小块制造碎片场景 for (int i 0; i 10000; i) { void *ptrs[100]; for (int j 0; j 100; j) { ptrs[j] malloc(random() % 512 1); } for (int j 0; j 100; j 2) { free(ptrs[j]); } for (int j 1; j 100; j 2) { free(ptrs[j]); } } }5.2 用红区red zone抓越界写越界写是 C 内存问题里最隐蔽的一种。我实现了一个 debug 模式在用户数据区末尾额外塞 16 字节的 magic number0xDEADBEEF释放时检查 magic 是否被覆盖。如果覆盖了直接 abort 并打印出错的块地址。这一招帮我抓到了好几个隐晦的 bug。#define MAGIC 0xDEADBEEF void *malloc(size_t size) { size_t total HEADER_SIZE ALIGN(size) (debug ? 16 : 0); // ... if (debug) { size_t *magic (size_t *)((char *)block HEADER_SIZE aligned); *magic MAGIC; return (void *)(block 1); } } void free(void *ptr) { BlockHeader *block (BlockHeader *)ptr - 1; if (debug) { size_t *magic (size_t *)((char *)ptr block-size - HEADER_SIZE - 16); if (*magic ! MAGIC) { fprintf(stderr, Buffer overflow detected at %p\n, ptr); abort(); } } // 正常释放逻辑 }5.3 性能对比基准到底比系统 malloc 差多少自研分配器的性能上限通常拼不过 glibc 的 ptmalloc这是正常的。我写了一个简单 benchmark循环分配释放 100 万次记录耗时场景系统 mallocv1隐式链表v2分离链表mmap1线程随机大小 16B-512B12ms45ms22ms1线程固定大小 64B8ms30ms12ms4线程随机大小混合45ms320ms串行锁80msTLS从数据看v2 相对 v1 提升了大约一倍以上并且在大块频繁分配释放的场景下因 mmap 机制避免了堆区膨胀整体稳定性更好。而系统 malloc 还是比 v2 快主要是 glibc 实现了多个 arena、更精细的块排序、以及针对典型 size class 的优化。这个差距在我预期内作为学习项目已经达到及格线。6. 避坑指南与常见 Bug 实录6.1 最隐蔽的 bug合并后忘了更新 free list这个 bug 我调了两天才定位到。场景是这样释放一块内存时coalesce把前块和当前块合并了但在移除next块时的链表指针处理有误导致 free list 出现环或自引用。表现是程序偶发死循环或者返回一模一样的地址两次。排查思路用 gdb 打印所有空闲链表的指针逐步手推链表连接关系。后来我给链表操作加了一组 assert每次插入删除后检查是否存在环static void assert_no_cycle() { BlockHeader *slow free_list_head, *fast free_list_head; while (fast fast-next_free) { slow slow-next_free; fast fast-next_free-next_free; if (slow fast) { fprintf(stderr, CYCLE DETECTED!\n); abort(); } } }这个方法建议直接抄进你的代码里调试期会很香。6.2 对齐问题的血泪教训16 字节并不会省我一开始图省事HEADER_SIZE定义成sizeof(BlockHeader)也就是 24 字节。结果用户申请一个 8 字节空间返回地址是块头 24换算成十六进制是0x...88 字节对齐没问题但遇到需要 16 对齐的__m128类型就直接崩了。这个问题在 x86_64 上偶尔才触发非常难复现。解决办法就是前面说的HEADER_SIZE ALIGN(sizeof(BlockHeader))。要注意的是块内部如果有其他元数据也一律走 ALIGN宁可浪费几字节 padding也不要留隐性对齐风险。6.3 外部碎片的经典案例交替分配大小块很多初学者以为有合并就行外部碎片不存在。实际上当程序交替分配 64 字节和 512 字节的块时释放后合并虽然能消除相邻空闲块但无法解决“空闲块分布太碎”的问题——你有一堆被已分配块隔开的 64 字节空闲块此时想分配 128 字节连续内存即使空闲总量够也只能失败。这需要更高层的策略分配时尽量从“合适”的空闲块中分配而不是从任意块中抢释放时尽量和相邻块合并如果碎片化严重考虑压缩重定位已分配对象——但压缩在 C 语言里不现实因为用户持有指针你无法安全改地址。所以现实中的分配器只能缓解碎片无法根除。6.4 free 一个非法指针防御性检查该不该加v1 版本里我没加任何防御性检查直接拿ptr - 1当块头用。一旦用户误传一个堆外地址轻则读脏数据重则段错误。后来我加了地址范围检查判断 ptr 是否在heap_start到heap_end之间同时校验块头的 magic number。合法块的 header 里预先存了MAGIC_HEADER标记。void free(void *ptr) { if (ptr NULL) return; BlockHeader *block (BlockHeader *)ptr - 1; if ((void *)block heap_start || (void *)block heap_end) { fprintf(stderr, Invalid free: pointer out of heap range\n); abort(); } if (block-magic ! MAGIC_HEADER) { fprintf(stderr, Invalid free: header magic corrupted\n); abort(); } // ... }这个做法会让 free 变重一点点但 debug 阶段极其值得。生产环境可以加编译宏开关只在#ifdef DEBUG下保留。7. 定位与前景内存分配器的下一步还能玩什么写完这个项目后我对操作系统内存策略的理解深了一个层次尤其理解了为什么 glibc 的 malloc 内部要搞那么多机制——不是没事找事全是针对实际负载的取舍。如果你也想在这条路上继续深入下面几个方向是我觉得最有价值的想深入性能调优就去看 tcmalloc 的线程缓存和 jemalloc 的 arena 设计后者对多核和多线程场景的优化非常细致光是大小类和缓存策略就够研究很久。想做嵌入式方向可以学习 TLSFTwo-Level Segregated Fit分配器它在实时系统里非常流行分配释放都是 O(1)且碎片率很低。想理解整个循环可以接着写一个 slab 分配器实现固定大小对象的复用这在内核里特别常见。我个人接下来的计划是把这套分配器移植到一个简单的操作系统内核里配合分页机制做用户态堆的初始化。这条路走通整个内存子系统就算有了完整闭环。如果你也在写类似的项目欢迎交流踩坑经验——如果你的 bug 是 free list 出现环十有八九是合并时链表的 prev/next 接错了先查那里。
