简介围绕C语言动态内存分配这一核心主题面向希望深入理解malloc内部机制的开发者通过亲手实现一个简化版my_malloc来剖析内存管理的关键原理。内容覆盖堆区管理、内存碎片来源、内存块元信息与内存池设计等基础概念并给出了分配、释放、合并空闲块及向系统扩展内存的完整思路。zip压缩包体积仅3KB共含3个文件包括2个C源文件与1个头文件其中C文件分别对应算法实现与测试调用头文件用于声明接口结构紧凑适合在本地快速编译验证。资源已有1829人学习适合计算机专业学生、嵌入式开发者及对系统底层感兴趣的C语言使用者作为入门与进阶参考。通过研究并运行这份mini实现读者可以直观理解首次适配等分配策略、减少碎片的合并方式以及真实malloc面对的对齐与并发等复杂问题从而提升自主实现和优化内存管理代码的能力。1. 自己动手写malloc一次把内存管理看个明白在 Linux 下调 malloc 是件习以为常的事但内存到底从哪来的对很多人来说一直是个黑匣子。我之前做一个图像处理 Demo程序频繁分配又释放小对象系统的默认分配器表现总有点玄学一会快一会慢。后来我一狠心抛开标准库自己实现了这套 malloc 替代品只用一个空闲链表加 first-fit 策略配合 sbrk 系统调用管理堆内存核心代码不到 300 行测试用例全部跑通。这个项目能帮你把“内存到底怎么管理”这层纸捅破适合搞不懂内存分配原理的学生也适合在嵌入式环境里需要定制分配器的开发者。看完你可以直接拿它跑测试、改策略、加统计甚至把里面的想法搬到你自己的项目里。2. 项目定位与技术选型sbrk、空闲链表与first-fit的取舍2.1 malloc到底要做什么malloc(size) 的职责我总结下来其实是三件事一是从某个地方找到一块空闲内存至少 size 个字节二是保证返回的地址满足对齐要求不然某些 CPU 直接坑你三是把这块内存从“空闲”状态切到“已分配”状态也就是标个记避免和后续分配冲突。大多数人以为 malloc 背后的内存是“凭空变出来的”其实不是。系统里有两种基本的内存来源一个是 sbrk/brk 调整的“堆”一个是 mmap 映射出来的匿名内存区。glibc 的默认分配器在分配超过一定阈值的大块时走 mmap其余从小堆上分配。我们这个小项目不需要那么复杂直接全走 sbrk。sbrk 是一个很原始的系统调用它只做一件事把堆的边界往上推。推一次你就拥有了一段新的连续内存。参数说明sbrk(0) 不会改变边界只返回当前堆顶地址常用来“探路”sbrk(n) 把堆顶往上推 n 字节返回推之前的位置失败时返回 (void *)-1注意不是 NULL这两个值并不同。2.2 为什么选择这个方案很多同学会问自己写 malloc 是不是纯折腾。我觉得不是。脱开标准库自己管理内存至少能看到几层东西之前被隐藏的空闲块查找、分裂、合并逻辑全部露出来了调试器和错误日志会是什么样的表现还能自己定制行为策略比如换成 best-fit改一下查找条件就行。学校里讲内存管理讲完段页式就考试了也不知道实际的分配器长什么样。这个项目就是补上这段“黑匣子”的。性能上我们做的这个分配器肯定打不过 glibc但这不是它的目标。它的目标是正确、好读、可改。glibc 默认分配器那套 bins、fastbins、top chunk 比较复杂一上来就照它做会顾此失彼。所以我的建议是先做一个简单的跑通测试再逐步加优化。第一版用最朴素的办法跑通了再优化这句话我后来每次写库都会默念一遍。2.3 数据结构选型单链表与first-fit结构选的空闲链表free list这是个特别直白的选择。我们维护一个全局的单链表每个节点代表一段内存块块里有个标志位记录它空闲还是被占用。分配的时候从头往后扫找到第一个大小足够的空闲块这就是 first-fit。有人会问为什么不把空闲块直接存成一个 array因为内存块的大小是运行期才决定的而且块的位置就是内存地址本身链表把管理信息塞到同一条物理内存里省掉索引表也不用额外分配空间。块大小的表示上有一个约定每个块的头部记录它自己的 size但这个 size 不包含头部本身的字节数。用户向 malloc 申请 100 字节实际要用的空间是 BLOCK_SIZE 100头部固定大小之后才是用户区域。这样设计的原因很简单用户拿到指针后往前偏移 BLOCK_SIZE 就能找到头部无需额外表。还要提一下最小块的概念。分配的时候不是看到一个块大小足够就直接用如果块比申请的大很多就得把它“切”成两半后半部分作为新空闲块插回链表不然几十次分配下来每个块里面都拖着大量用不上的空隙内存浪费很快。这就引出了分裂split操作。反过来free 的时候如果发现相邻块也空闲要把它们拼回去不然链表越拉越长、越来越碎。2.4 项目目录与编译方式项目的文件结构比较简单五个文件把全部逻辑装下了my-malloc/ ├── malloc.c # 核心实现块结构、find/merge/split、malloc/free/realloc/calloc ├── malloc.h # 对外声明 ├── test_my_malloc.c # 单元测试与边界测试 ├── Makefile # 编译与运行入口 └── README.md # 使用说明malloc.c 是主角大概 200 行测试文件里写了几十组用例。用 gcc 编译Makefile 里开了 -Wall -Wextra -g这样编译期警告能全露出来。整个目录就五个文件很适合把每一行都读完。跑起来只需要 make make run测试程序会在终端输出 all tests passed说明分配器通过了全部断言。3. 核心模块拆解块头、分裂、合并与完整分配流程3.1 块头设计24字节的内存布局先看最核心的结构体定义typedef struct block block_t; struct block { size_t size; // 用户数据区大小不含头部 block_t *next; // 指向下一个块 int free; // 空闲标记1空闲0已占用 char padding[4]; // 显式补齐保证BLOCK_SIZE为8的倍数 }; #define BLOCK_SIZE sizeof(block_t)三个字段加 4 字节补丁在 64 位系统下 BLOCK_SIZE 等于 24是 8 的倍数。为什么要把整体大小补到 8 的倍数因为 sbrk 返回的地址天然是页对齐的通常至少 4K但用户拿到的是 (char *)b BLOCK_SIZE如果 BLOCK_SIZE 是 24那这个指针相对于页基址的位置偏移是 24而 24 能被 8 整除所以用户数据区仍然保持 8 字节对齐。如果某个平台上的 size_t 是 8、指针是 8、int 是 4结构体本身大概率也会被编译器补到 24但我还是写了显式的 padding这样不管编译器怎么排BLOCK_SIZE 都明确是 8 的倍数后续对齐的逻辑不会被编译器版本坑到。参数说明size 记录的是“用户数据区的长度”而不是整个块的长度。用户申请 100 字节分配器要分配 BLOCK_SIZE 100并把块头里的 size 记为 100。多一个 next 和 free 字段不会从用户请求里扣因为是额外的头部开销。还有个细节malloc(size) 和 free(ptr) 之间靠的就是指针偏移。用户拿到 ptr (char *)block BLOCK_SIZEfree 的时候先往前跳 24 字节找到块头再操作链表。所以块头足足 24 字节对小分配来说开销不小但自写分配器第一步要把正确性先做出来开销是后话。3.2 空闲链表查找first-fit扫描的细节空闲链表是全局单链表所有块无论空闲还是占用都串在这条链上方便做合并。如果只串空闲块合并时找前驱会特别麻烦。我的选择是“全量链表 free 标记”实现简单遍历时有标记判断即可。查找函数长这样static block_t *find_block(block_t **last, size_t size) { block_t *b head; while (b !(b-free b-size size)) { *last b; b b-next; } return b; }这个函数做的是 first-fit 查找从链表头开始逐个看只要当前块不满足“空闲且够大”的条件就把 *last 更新成当前节点继续往后走。找到了就返回块的指针找不到时 last 保存的是链表最后一个节点。为什么需要 last因为如果整个链表都找不到合适的空闲块接下来要调 sbrk 扩展堆需要把新块挂到链表的末尾提前记录尾节点可以少遍历一次。参数说明last 是“块指针的指针”调用者通常这么用block_t *last NULL; block_t *b find_block(last, size); 如果返回 NULLlast 就是一个非空的块或者还是 NULL可以把它当作新分配块的连接点。这样设计是为了省掉一次从头扫描链表找尾节点的开销虽然查找本身已经是 O(n)但链表长了以后能省一次就是一次。判断条件里有一个常见误用有人写 b-size size 就完了把 free 1 的检查漏掉结果分配器反复返回同一个块导致严重踩踏。自写 malloc 排错难度高细节上一定要稳。3.3 块分裂大块切小块的关键判断当查找命中一个块而块的实际大小比申请的大不少时就要执行分裂。比如申请 16 字节命中了一个 512 字节的空闲块直接把这 512 全给出去是灾难剩余的空闲块会越来越少链表全是胖块。分裂逻辑如下static void split_block(block_t *b, size_t size) { block_t *new_b (block_t *)((char *)b BLOCK_SIZE size); new_b-size b-size - size - BLOCK_SIZE; new_b-next b-next; new_b-free 1; b-size size; b-next new_b; }new_b 的位置计算是理解这段代码的关键以块 b 的起始地址为起点跳过 b 的头部BLOCK_SIZE 字节再跳过用户数据区 size 字节剩下的就是从 new_b 开始。相当于把原块分成前后两段前段留给用户后段作为新空闲节点挂在原块的 next 位置。new_b 的 size 就是原 size 减去前段头部和数据区后的余量如果余量小于一个块头加最少数据分裂就不划算所以调用方要先判断。参数说明size 是用户申请的值不是块的物理大小。b-size size BLOCK_SIZE 4 这个判断用来避免“为省 2 字节制造新碎片”最小分裂余量取 4 是一个常见做法。这样不会因为极小余量反复分裂还能把分配率保持在合理区间。注意分裂完后 b-free 要置成 0表示已分配。这个操作在 malloc 主流程里做不在 split_block 里做因为 split_block 只负责拆free 标记归调用方管。这也是一个代码组织上的小约定。3.4 相邻合并避免空闲块碎片化free 的时候如果把一个已占用块标记为空闲就完事看起来很简单但如果不合并连续释放多个相邻块时链表里会出现一连串小空闲块再次申请大块时 first-fit 扫描会次次碰壁分配性能直线下滑。合并做法是释放一个块之后遍历链表如果当前块是空闲且它的 next 也是空闲就把两块拼成一块。合并的核心是调整 size而不是移动内存static void merge_blocks(void) { block_t *cur head; int merged; do { merged 0; cur head; while (cur cur-next) { if (cur-free cur-next-free) { cur-size BLOCK_SIZE cur-next-size; cur-next cur-next-next; merged 1; } cur cur-next; } } while (merged); }为什么用 do-while因为合并后 cur 块的 size 变大它可能又可以跟新的 next 合并一轮扫描里如果做了一次合并指针跳到新 next 后可能漏掉“第一个块现在可以吞并后面连续空闲块”的情况。外层 do-while 保证只要这一轮发生过合并就再扫一遍直到一轮下来没有合并动作。链表不长时这个开销可以接受。合并涉及的三块内存原封不动只是把头部信息改掉。被合并的 next 块头部会被新大块覆盖内存地址上它“消失”了但它是空闲块所以没问题。这里要强调我们不做向前合并只是单向向后合并连续释放三块第一次释放后触发一轮合并第二次释放再一轮能正确合成一块。4. 代码全落地malloc、free、realloc与测试用例4.1 malloc入口分配逻辑的两条路径有了数据结构和三个内部函数malloc 入口就简单了。完整代码如下void *my_malloc(size_t size) { block_t *last NULL; block_t *b; if (size 0) { return NULL; } last head; b find_block(last, size); if (b) { // 大块分裂避免整块占用 if (b-size size BLOCK_SIZE 4) { split_block(b, size); } b-free 0; } else { // 没找到合适的空闲块向操作系统要内存 b extend_heap(last, size); if (!b) { return NULL; } } return (void *)((char *)b BLOCK_SIZE); }逻辑分支只有两条find_block 找到了空闲块就检查是否要分裂然后标记已分配找不到就调 extend_heap 向操作系统要一块全新的内存挂到链表尾部。返回地址统一偏移 BLOCK_SIZE让用户 ptr 直接落在数据区起点。这段代码还承担了分配统计钩子的职责。后面做内存审计时只需要在 b 被确定之后、返回之前插入几个计数器累加不需要改其他函数改造面很小。参数说明size 是用户请求的字节数不能为 0返回 NULL 时调用方应该认为分配失败。注意这里没有处理 size 为负的情况因为 size_t 是无符号类型用户传负数会变成极大的正数系统 malloc 也是类似行为。这个边界问题我们留到避坑章节讨论。4.2 extend_heap与操作系统打交道的边界extend_heap 是整段代码里最容易出错的地方static block_t *extend_heap(block_t *last, size_t size) { block_t *b; b sbrk(0); // 先取当前堆顶地址 if (sbrk(BLOCK_SIZE size) (void *)-1) { return NULL; } b-size size; b-free 0; b-next NULL; if (last) { last-next b; } else { head b; } return b; }这里要注意 sbrk 的两次调用之间不能夹任何可能调 malloc 的代码否则取回来的堆顶地址可能已变了。我们这里当然没有嵌套调用但写成“sbrk(0) 取地址再 sbrk(BLOCK_SIZE size) 扩展”这种两段式写法时从工程上要留个心眼。更稳的写法是先用本地变量接收 sbrk 的返回值再把它转成 block_t 指针。参数说明sbrk(BLOCK_SIZE size) 表示一次分配头部加用户区大小返回值是失败标志 (void *)-1与 NULL 不同做判断时不能写成 if (sbrk(...) NULL)这是真实翻车现场。sbrk(0) 返回的地址如果已经是页对齐的那么块头加用户区的偏移之后还能保持对齐吗这取决于 BLOCK_SIZE所以第 3 章那个 padding 字段不是白加的。当 last 为 NULL 时说明链表是空的head 要指向新块否则把新块接到链表尾部。这个分支容易漏漏掉之后新分配的块将永远无法被 free 追踪到泄漏得无声无息。4.3 calloc和realloc基于malloc的薄封装void *my_calloc(size_t nmemb, size_t size) { void *p; p my_malloc(nmemb * size); if (p) { memset(p, 0, nmemb * size); } return p; } void *my_realloc(void *ptr, size_t size) { block_t *b; void *new_p; if (!ptr) { return my_malloc(size); } if (size 0) { my_free(ptr); return NULL; } b (block_t *)((char *)ptr - BLOCK_SIZE); if (b-size size) { // 如果现有块已经够大直接原地返回减少拷贝 return ptr; } new_p my_malloc(size); if (!new_p) { return NULL; } memcpy(new_p, ptr, b-size); my_free(ptr); return new_p; }calloc 就是 malloc 加 memset没有更多玄机。realloc 有一个重要的优化路径如果原来的块 size 本来就不小于请求的 size直接原地返回这不浪费拷贝也不释放重分配。只有原块不够大时才走“分配新块 拷贝旧数据 释放旧块”的三部曲。拷贝长度不是 size而是 b-size这一点容易写错写错会导致读越界或拷贝不完整。这里也要提醒一个常见误用realloc 失败时旧指针还有效应该保留。旧块不能提前 free所以先 malloc 新内存成功后再 free 旧块。上面代码的顺序是malloc 新块、检查 NULL、memcpy、my_free 旧块。这个顺序是唯一正确的反过来就会把旧数据弄丢。4.4 测试与编译Makefile和调试建议测试文件覆盖了几类场景基础写入验证、零大小返回 NULL、128 个小块连续分配释放验证链表伸缩、不同大小交替分配验证分裂与合并、realloc 缩小和扩大。完整测试代码#include stdio.h #include string.h #include assert.h void *my_malloc(size_t size); void my_free(void *ptr); void *my_realloc(void *ptr, size_t size); void *my_calloc(size_t nmemb, size_t size); int main(void) { int *arr; void *ptrs[128]; char *a, *b; int i; // 用例1基础分配和写入 arr (int *)my_malloc(10 * sizeof(int)); assert(arr ! NULL); for (i 0; i 10; i) { arr[i] i * 2; } for (i 0; i 10; i) { assert(arr[i] i * 2); } my_free(arr); // 用例2零大小 assert(my_malloc(0) NULL); // 用例3128个小块轮流分配与逆序释放 for (i 0; i 128; i) { ptrs[i] my_malloc(64); assert(ptrs[i] ! NULL); } for (i 127; i 0; i--) { my_free(ptrs[i]); } // 用例4交替分配不同大小后释放 a (char *)my_malloc(100); b (char *)my_malloc(200); strcpy(a, my-malloc); strcpy(b, free-list); assert(strcmp(a, my-malloc) 0); assert(strcmp(b, free-list) 0); my_free(a); my_free(b); // 用例5realloc缩小和扩大 a (char *)my_malloc(16); strcpy(a, realloc demo); a (char *)my_realloc(a, 64); assert(a ! NULL); assert(strcmp(a, realloc demo) 0); my_free(a); printf(all tests passed\n); return 0; }MakefileCCgcc CFLAGS-Wall -Wextra -g -O2 all: test_malloc test_malloc: malloc.c malloc.h test_my_malloc.c $(CC) $(CFLAGS) -o $ test_my_malloc.c malloc.c run: test_malloc ./test_malloc clean: rm -f test_malloc在这个测试里能观察到一些有意思的现象第 3 个用例 128 个小块逆序释放时merge_blocks 会被多次触发如果把释放顺序改成乱序碎片化会更明显但后续分配仍能跑通说明合并逻辑在起作用。你可以把 my_malloc 换成系统的 malloc 跑一遍同样的用例行为一致说明我们的基础功能没有明显缺陷。gdb 调试的时候在 find_block 里打断点打印 b-free 和 b-next很快能看到链表有没有被破坏。如果出现段错误先用 bt 看调用栈大部分时候是 find_block 里 b-next 访问到了非法地址。按这个线索往回找是谁改了 next多半是越界写。几乎所有初学者遇到 malloc 崩溃第一反应都是“分配器写错了”但实际用 gdb 查下来分配器本身逻辑往往没问题反而是用户代码越界或者释放顺序不对。多调试几次就能养成先怀疑自己代码的习惯。5. 避坑手册自己实现malloc时踩过的五个坑5.1 sbrk两段式调用的竞态现象程序偶尔正常偶尔出现在 malloc 内部立刻段错误而且只在分配大块时出现。原因把 sbrk 写成一个单独的函数里面做 sbrk(0) 然后 sbrk(size)这两次系统调用之间如果发生了其他堆操作比如调试打印里偷偷 calloc 了一次堆顶变了第一次拿到的地址就作废了。第二次 sbrk 返回的地址才是真正可用的内存但你已经把旧的 sbrk(0) 结果当成新块地址写入了。解决把 sbrk(0) 和实际扩展合并成一次操作或者至少保证这两次调用中间不做任何可能触发堆分配的事。我的建议是写一个函数它只负责要内存一次调用完成 sbrk(0) 探址紧接着马上 sbrk(n) 扩展中间不插入任何可能分配内存的代码。检查失败时一定用 (void *)-1不要用 NULL。5.2 越界访问悄悄破坏链表现象malloc 返回的指针正常往里面写数据也不报错但后续某次 malloc 或 free 时突然段错误而且 gdb 看到的链表指针既不是 NULL 也不是合法地址。原因用户数据区越界了。比如分配了 16 字节向里面写了 32 字节多出来的 16 字节直接覆盖了下一个块的块头。链表指针被改成随机值直到某次遍历才暴露。解决在块头里加一个 magic 字段free 时校验有没有被覆盖。这是最省事的检测手段。我后来在测试里故意写了一个越界版本观察到的现象非常典型第一次分配正常第二次 malloc 时在 find_block 里崩溃。从那以后我所有自写的分配器都会在头部加一个 magic 字段不贵但排查越界能省半天时间。5.3 重复free导致链表成环或死循环现象同一指针被 free 两次第一次正常第二次程序进入无限循环CPU 占用 100%。原因第一次 free 后块被标记为空闲并做了合并第二次 free 时因为 ptr 前移找块头而这块可能已经被合并进更大的空闲块块的 size 和 next 已经变了继续置 free 可能出现奇怪状态。更严重的如果这块被再次分配给用户第二次 free 会把一个正在使用的块标记为空闲链表完整性彻底破坏。解决free 里加 if (!b-free) 判断至少能挡住“已释放块再次释放”的部分问题。但用户角度看正确姿势是 free 之后立刻把指针置为 NULL。项目里如果统一用一个 free_ptr 宏来做就省心很多。这个防护不能解决所有情况但在教学项目里能显著降低踩坑概率。5.4 堆只涨不缩现象程序反复分配释放小内存观察进程 RSS 一路走高free 之后内存并没有还给系统。原因sbrk 分配的堆是进程地址空间的一段连续区域释放后的块只是在链表里被标记为空闲并没有把堆顶降低。只有释放了堆顶的那一块并且上一块也空闲时sbrk(-n) 才能收缩这个逻辑比简单的“释放即归还”复杂得多。解决对刚实现起来的小型分配器来说“只涨不缩”是可接受的行为。如果内存占用是硬指标可以考虑两个方向一是超过某个阈值的大块改用 mmap 分配munmap 天然能归还二是调用 sbrk(-n) 实现堆顶收缩但要精确维护“只有最后一个块空闲才能缩”的状态。这个优化留给二次开发第一版先接受 RSS 缓慢上升。5.5 平台一换就对齐崩溃现象在自己笔记本上跑得好好的移植到某个嵌入式平台后分配返回的地址总不是 8 的倍数一用就崩。原因结构体大小在不同平台上不一样如果 BLOCK_SIZE 不是 8 的倍数那么 (char *)b BLOCK_SIZE 就会把对齐破坏掉。系统 malloc 保证返回的指针满足最大对齐要求自己实现的分配器如果忽略这一点在有的平台上会非常隐蔽地翻车。解决块头里 size 和 next 都用 size_tfree 用 int然后手动加 padding 字段再在代码里加一行静态断言_Static_assert(BLOCK_SIZE % 8 0, BLOCK_SIZE must be multiple of 8);编译期就把这个问题拦住比运行期一个块一个块去试探要省心得多。接嵌入式项目时这个断言尤其管用目标平台可能和开发机长得完全不一样。6. 二次开发给分配器加审计、改策略、上锁6.1 加内存审计统计分配次数与总字节想在现有分配器上做统计不需要大改只需加两个全局计数器和钩子。在 my_malloc 里面累加 size在 my_free 里减掉就能实时掌握当前存活字节数static size_t alloc_calls 0; static size_t alloc_bytes 0; static size_t free_calls 0; void *my_malloc(size_t size) { block_t *b; // 原有的查找、扩展逻辑保持不变 // 在返回前插入统计 alloc_calls; alloc_bytes size; return (void *)((char *)b BLOCK_SIZE); } void my_free(void *ptr) { block_t *b; if (!ptr) return; b (block_t *)((char *)ptr - BLOCK_SIZE); if (b-free) return; free_calls; alloc_bytes - b-size; b-free 1; merge_blocks(); }验证方法跑测试用例后检查 free_calls 是否等于 alloc_callsalloc_bytes 是否归零。如果归零说明所有块都正确释放了这是单线程下最直接的泄漏判定。注意 realloc 内部会先走 my_free 再走 my_malloc统计口径统一反而方便。把计数器和审计函数挂到测试程序末尾每次跑完直接看到结果。6.2 泄漏检测器退出时扫描未释放块更实用的做法是提供一个 audit_exit 函数在程序退出时遍历整个链表把所有 free 0 的块打印出来void audit_exit(void) { block_t *b; int leaked 0; for (b head; b; b b-next) { if (!b-free) { printf(leaked block: %p, size%zu\n, (void *)((char *)b BLOCK_SIZE), b-size); leaked; } } if (leaked) { printf(memory leak detected: %d blocks\n, leaked); } else { printf(no leak detected\n); } }把 audit_exit 放在程序 return 前调用就能在开发期快速发现泄漏。注意这个检测依赖链表遍历块数量到十万级时 O(n) 的开销会明显可见工程里可以维护一棵二叉搜索树按地址查块但教学阶段这个版本够了。6.3 换best-fit与加锁的起步改造想验证不同分配策略的效果最简单的改法是 find_block 里加一个最小余量跟踪static block_t *find_best(block_t **last, size_t size) { block_t *b; block_t *best NULL; size_t best_size 0; for (b head; b; b b-next) { if (b-free b-size size) { if (!best || b-size best_size) { best b; best_size b-size; } } } return best; }这就是 best-fit。代价是必然扫描完整条链表好处是留下的空闲块余量更均匀。先跑通 first-fit再替换成 best-fit对比同一份测试用例下重复分配的命中率是很直观的实验。多线程起步改造就是在 my_malloc 和 my_free 的入口各加一把 pthread_mutex粒度最粗但能保证正确。熟练以后可以再换细粒度锁每个块加一个锁或者用原子操作改 free 标记。第一版加锁会牺牲吞吐但能跑对就是好的开始。最后说一个习惯。每次改完分配器我都会把一个固定顺序的测试跑三遍第一遍用 128 个小块验证碎片第二遍故意越界验证 magic第三遍开着审计退出验证泄漏。这三关过了才敢说这个版本可以做下一步。希望帮到你。本文还有配套的精品资源点击获取
简介围绕C语言动态内存分配这一核心主题面向希望深入理解malloc内部机制的开发者通过亲手实现一个简化版my_malloc来剖析内存管理的关键原理。内容覆盖堆区管理、内存碎片来源、内存块元信息与内存池设计等基础概念并给出了分配、释放、合并空闲块及向系统扩展内存的完整思路。zip压缩包体积仅3KB共含3个文件包括2个C源文件与1个头文件其中C文件分别对应算法实现与测试调用头文件用于声明接口结构紧凑适合在本地快速编译验证。资源已有1829人学习适合计算机专业学生、嵌入式开发者及对系统底层感兴趣的C语言使用者作为入门与进阶参考。通过研究并运行这份mini实现读者可以直观理解首次适配等分配策略、减少碎片的合并方式以及真实malloc面对的对齐与并发等复杂问题从而提升自主实现和优化内存管理代码的能力。1. 自己动手写malloc一次把内存管理看个明白在 Linux 下调 malloc 是件习以为常的事但内存到底从哪来的对很多人来说一直是个黑匣子。我之前做一个图像处理 Demo程序频繁分配又释放小对象系统的默认分配器表现总有点玄学一会快一会慢。后来我一狠心抛开标准库自己实现了这套 malloc 替代品只用一个空闲链表加 first-fit 策略配合 sbrk 系统调用管理堆内存核心代码不到 300 行测试用例全部跑通。这个项目能帮你把“内存到底怎么管理”这层纸捅破适合搞不懂内存分配原理的学生也适合在嵌入式环境里需要定制分配器的开发者。看完你可以直接拿它跑测试、改策略、加统计甚至把里面的想法搬到你自己的项目里。2. 项目定位与技术选型sbrk、空闲链表与first-fit的取舍2.1 malloc到底要做什么malloc(size) 的职责我总结下来其实是三件事一是从某个地方找到一块空闲内存至少 size 个字节二是保证返回的地址满足对齐要求不然某些 CPU 直接坑你三是把这块内存从“空闲”状态切到“已分配”状态也就是标个记避免和后续分配冲突。大多数人以为 malloc 背后的内存是“凭空变出来的”其实不是。系统里有两种基本的内存来源一个是 sbrk/brk 调整的“堆”一个是 mmap 映射出来的匿名内存区。glibc 的默认分配器在分配超过一定阈值的大块时走 mmap其余从小堆上分配。我们这个小项目不需要那么复杂直接全走 sbrk。sbrk 是一个很原始的系统调用它只做一件事把堆的边界往上推。推一次你就拥有了一段新的连续内存。参数说明sbrk(0) 不会改变边界只返回当前堆顶地址常用来“探路”sbrk(n) 把堆顶往上推 n 字节返回推之前的位置失败时返回 (void *)-1注意不是 NULL这两个值并不同。2.2 为什么选择这个方案很多同学会问自己写 malloc 是不是纯折腾。我觉得不是。脱开标准库自己管理内存至少能看到几层东西之前被隐藏的空闲块查找、分裂、合并逻辑全部露出来了调试器和错误日志会是什么样的表现还能自己定制行为策略比如换成 best-fit改一下查找条件就行。学校里讲内存管理讲完段页式就考试了也不知道实际的分配器长什么样。这个项目就是补上这段“黑匣子”的。性能上我们做的这个分配器肯定打不过 glibc但这不是它的目标。它的目标是正确、好读、可改。glibc 默认分配器那套 bins、fastbins、top chunk 比较复杂一上来就照它做会顾此失彼。所以我的建议是先做一个简单的跑通测试再逐步加优化。第一版用最朴素的办法跑通了再优化这句话我后来每次写库都会默念一遍。2.3 数据结构选型单链表与first-fit结构选的空闲链表free list这是个特别直白的选择。我们维护一个全局的单链表每个节点代表一段内存块块里有个标志位记录它空闲还是被占用。分配的时候从头往后扫找到第一个大小足够的空闲块这就是 first-fit。有人会问为什么不把空闲块直接存成一个 array因为内存块的大小是运行期才决定的而且块的位置就是内存地址本身链表把管理信息塞到同一条物理内存里省掉索引表也不用额外分配空间。块大小的表示上有一个约定每个块的头部记录它自己的 size但这个 size 不包含头部本身的字节数。用户向 malloc 申请 100 字节实际要用的空间是 BLOCK_SIZE 100头部固定大小之后才是用户区域。这样设计的原因很简单用户拿到指针后往前偏移 BLOCK_SIZE 就能找到头部无需额外表。还要提一下最小块的概念。分配的时候不是看到一个块大小足够就直接用如果块比申请的大很多就得把它“切”成两半后半部分作为新空闲块插回链表不然几十次分配下来每个块里面都拖着大量用不上的空隙内存浪费很快。这就引出了分裂split操作。反过来free 的时候如果发现相邻块也空闲要把它们拼回去不然链表越拉越长、越来越碎。2.4 项目目录与编译方式项目的文件结构比较简单五个文件把全部逻辑装下了my-malloc/ ├── malloc.c # 核心实现块结构、find/merge/split、malloc/free/realloc/calloc ├── malloc.h # 对外声明 ├── test_my_malloc.c # 单元测试与边界测试 ├── Makefile # 编译与运行入口 └── README.md # 使用说明malloc.c 是主角大概 200 行测试文件里写了几十组用例。用 gcc 编译Makefile 里开了 -Wall -Wextra -g这样编译期警告能全露出来。整个目录就五个文件很适合把每一行都读完。跑起来只需要 make make run测试程序会在终端输出 all tests passed说明分配器通过了全部断言。3. 核心模块拆解块头、分裂、合并与完整分配流程3.1 块头设计24字节的内存布局先看最核心的结构体定义typedef struct block block_t; struct block { size_t size; // 用户数据区大小不含头部 block_t *next; // 指向下一个块 int free; // 空闲标记1空闲0已占用 char padding[4]; // 显式补齐保证BLOCK_SIZE为8的倍数 }; #define BLOCK_SIZE sizeof(block_t)三个字段加 4 字节补丁在 64 位系统下 BLOCK_SIZE 等于 24是 8 的倍数。为什么要把整体大小补到 8 的倍数因为 sbrk 返回的地址天然是页对齐的通常至少 4K但用户拿到的是 (char *)b BLOCK_SIZE如果 BLOCK_SIZE 是 24那这个指针相对于页基址的位置偏移是 24而 24 能被 8 整除所以用户数据区仍然保持 8 字节对齐。如果某个平台上的 size_t 是 8、指针是 8、int 是 4结构体本身大概率也会被编译器补到 24但我还是写了显式的 padding这样不管编译器怎么排BLOCK_SIZE 都明确是 8 的倍数后续对齐的逻辑不会被编译器版本坑到。参数说明size 记录的是“用户数据区的长度”而不是整个块的长度。用户申请 100 字节分配器要分配 BLOCK_SIZE 100并把块头里的 size 记为 100。多一个 next 和 free 字段不会从用户请求里扣因为是额外的头部开销。还有个细节malloc(size) 和 free(ptr) 之间靠的就是指针偏移。用户拿到 ptr (char *)block BLOCK_SIZEfree 的时候先往前跳 24 字节找到块头再操作链表。所以块头足足 24 字节对小分配来说开销不小但自写分配器第一步要把正确性先做出来开销是后话。3.2 空闲链表查找first-fit扫描的细节空闲链表是全局单链表所有块无论空闲还是占用都串在这条链上方便做合并。如果只串空闲块合并时找前驱会特别麻烦。我的选择是“全量链表 free 标记”实现简单遍历时有标记判断即可。查找函数长这样static block_t *find_block(block_t **last, size_t size) { block_t *b head; while (b !(b-free b-size size)) { *last b; b b-next; } return b; }这个函数做的是 first-fit 查找从链表头开始逐个看只要当前块不满足“空闲且够大”的条件就把 *last 更新成当前节点继续往后走。找到了就返回块的指针找不到时 last 保存的是链表最后一个节点。为什么需要 last因为如果整个链表都找不到合适的空闲块接下来要调 sbrk 扩展堆需要把新块挂到链表的末尾提前记录尾节点可以少遍历一次。参数说明last 是“块指针的指针”调用者通常这么用block_t *last NULL; block_t *b find_block(last, size); 如果返回 NULLlast 就是一个非空的块或者还是 NULL可以把它当作新分配块的连接点。这样设计是为了省掉一次从头扫描链表找尾节点的开销虽然查找本身已经是 O(n)但链表长了以后能省一次就是一次。判断条件里有一个常见误用有人写 b-size size 就完了把 free 1 的检查漏掉结果分配器反复返回同一个块导致严重踩踏。自写 malloc 排错难度高细节上一定要稳。3.3 块分裂大块切小块的关键判断当查找命中一个块而块的实际大小比申请的大不少时就要执行分裂。比如申请 16 字节命中了一个 512 字节的空闲块直接把这 512 全给出去是灾难剩余的空闲块会越来越少链表全是胖块。分裂逻辑如下static void split_block(block_t *b, size_t size) { block_t *new_b (block_t *)((char *)b BLOCK_SIZE size); new_b-size b-size - size - BLOCK_SIZE; new_b-next b-next; new_b-free 1; b-size size; b-next new_b; }new_b 的位置计算是理解这段代码的关键以块 b 的起始地址为起点跳过 b 的头部BLOCK_SIZE 字节再跳过用户数据区 size 字节剩下的就是从 new_b 开始。相当于把原块分成前后两段前段留给用户后段作为新空闲节点挂在原块的 next 位置。new_b 的 size 就是原 size 减去前段头部和数据区后的余量如果余量小于一个块头加最少数据分裂就不划算所以调用方要先判断。参数说明size 是用户申请的值不是块的物理大小。b-size size BLOCK_SIZE 4 这个判断用来避免“为省 2 字节制造新碎片”最小分裂余量取 4 是一个常见做法。这样不会因为极小余量反复分裂还能把分配率保持在合理区间。注意分裂完后 b-free 要置成 0表示已分配。这个操作在 malloc 主流程里做不在 split_block 里做因为 split_block 只负责拆free 标记归调用方管。这也是一个代码组织上的小约定。3.4 相邻合并避免空闲块碎片化free 的时候如果把一个已占用块标记为空闲就完事看起来很简单但如果不合并连续释放多个相邻块时链表里会出现一连串小空闲块再次申请大块时 first-fit 扫描会次次碰壁分配性能直线下滑。合并做法是释放一个块之后遍历链表如果当前块是空闲且它的 next 也是空闲就把两块拼成一块。合并的核心是调整 size而不是移动内存static void merge_blocks(void) { block_t *cur head; int merged; do { merged 0; cur head; while (cur cur-next) { if (cur-free cur-next-free) { cur-size BLOCK_SIZE cur-next-size; cur-next cur-next-next; merged 1; } cur cur-next; } } while (merged); }为什么用 do-while因为合并后 cur 块的 size 变大它可能又可以跟新的 next 合并一轮扫描里如果做了一次合并指针跳到新 next 后可能漏掉“第一个块现在可以吞并后面连续空闲块”的情况。外层 do-while 保证只要这一轮发生过合并就再扫一遍直到一轮下来没有合并动作。链表不长时这个开销可以接受。合并涉及的三块内存原封不动只是把头部信息改掉。被合并的 next 块头部会被新大块覆盖内存地址上它“消失”了但它是空闲块所以没问题。这里要强调我们不做向前合并只是单向向后合并连续释放三块第一次释放后触发一轮合并第二次释放再一轮能正确合成一块。4. 代码全落地malloc、free、realloc与测试用例4.1 malloc入口分配逻辑的两条路径有了数据结构和三个内部函数malloc 入口就简单了。完整代码如下void *my_malloc(size_t size) { block_t *last NULL; block_t *b; if (size 0) { return NULL; } last head; b find_block(last, size); if (b) { // 大块分裂避免整块占用 if (b-size size BLOCK_SIZE 4) { split_block(b, size); } b-free 0; } else { // 没找到合适的空闲块向操作系统要内存 b extend_heap(last, size); if (!b) { return NULL; } } return (void *)((char *)b BLOCK_SIZE); }逻辑分支只有两条find_block 找到了空闲块就检查是否要分裂然后标记已分配找不到就调 extend_heap 向操作系统要一块全新的内存挂到链表尾部。返回地址统一偏移 BLOCK_SIZE让用户 ptr 直接落在数据区起点。这段代码还承担了分配统计钩子的职责。后面做内存审计时只需要在 b 被确定之后、返回之前插入几个计数器累加不需要改其他函数改造面很小。参数说明size 是用户请求的字节数不能为 0返回 NULL 时调用方应该认为分配失败。注意这里没有处理 size 为负的情况因为 size_t 是无符号类型用户传负数会变成极大的正数系统 malloc 也是类似行为。这个边界问题我们留到避坑章节讨论。4.2 extend_heap与操作系统打交道的边界extend_heap 是整段代码里最容易出错的地方static block_t *extend_heap(block_t *last, size_t size) { block_t *b; b sbrk(0); // 先取当前堆顶地址 if (sbrk(BLOCK_SIZE size) (void *)-1) { return NULL; } b-size size; b-free 0; b-next NULL; if (last) { last-next b; } else { head b; } return b; }这里要注意 sbrk 的两次调用之间不能夹任何可能调 malloc 的代码否则取回来的堆顶地址可能已变了。我们这里当然没有嵌套调用但写成“sbrk(0) 取地址再 sbrk(BLOCK_SIZE size) 扩展”这种两段式写法时从工程上要留个心眼。更稳的写法是先用本地变量接收 sbrk 的返回值再把它转成 block_t 指针。参数说明sbrk(BLOCK_SIZE size) 表示一次分配头部加用户区大小返回值是失败标志 (void *)-1与 NULL 不同做判断时不能写成 if (sbrk(...) NULL)这是真实翻车现场。sbrk(0) 返回的地址如果已经是页对齐的那么块头加用户区的偏移之后还能保持对齐吗这取决于 BLOCK_SIZE所以第 3 章那个 padding 字段不是白加的。当 last 为 NULL 时说明链表是空的head 要指向新块否则把新块接到链表尾部。这个分支容易漏漏掉之后新分配的块将永远无法被 free 追踪到泄漏得无声无息。4.3 calloc和realloc基于malloc的薄封装void *my_calloc(size_t nmemb, size_t size) { void *p; p my_malloc(nmemb * size); if (p) { memset(p, 0, nmemb * size); } return p; } void *my_realloc(void *ptr, size_t size) { block_t *b; void *new_p; if (!ptr) { return my_malloc(size); } if (size 0) { my_free(ptr); return NULL; } b (block_t *)((char *)ptr - BLOCK_SIZE); if (b-size size) { // 如果现有块已经够大直接原地返回减少拷贝 return ptr; } new_p my_malloc(size); if (!new_p) { return NULL; } memcpy(new_p, ptr, b-size); my_free(ptr); return new_p; }calloc 就是 malloc 加 memset没有更多玄机。realloc 有一个重要的优化路径如果原来的块 size 本来就不小于请求的 size直接原地返回这不浪费拷贝也不释放重分配。只有原块不够大时才走“分配新块 拷贝旧数据 释放旧块”的三部曲。拷贝长度不是 size而是 b-size这一点容易写错写错会导致读越界或拷贝不完整。这里也要提醒一个常见误用realloc 失败时旧指针还有效应该保留。旧块不能提前 free所以先 malloc 新内存成功后再 free 旧块。上面代码的顺序是malloc 新块、检查 NULL、memcpy、my_free 旧块。这个顺序是唯一正确的反过来就会把旧数据弄丢。4.4 测试与编译Makefile和调试建议测试文件覆盖了几类场景基础写入验证、零大小返回 NULL、128 个小块连续分配释放验证链表伸缩、不同大小交替分配验证分裂与合并、realloc 缩小和扩大。完整测试代码#include stdio.h #include string.h #include assert.h void *my_malloc(size_t size); void my_free(void *ptr); void *my_realloc(void *ptr, size_t size); void *my_calloc(size_t nmemb, size_t size); int main(void) { int *arr; void *ptrs[128]; char *a, *b; int i; // 用例1基础分配和写入 arr (int *)my_malloc(10 * sizeof(int)); assert(arr ! NULL); for (i 0; i 10; i) { arr[i] i * 2; } for (i 0; i 10; i) { assert(arr[i] i * 2); } my_free(arr); // 用例2零大小 assert(my_malloc(0) NULL); // 用例3128个小块轮流分配与逆序释放 for (i 0; i 128; i) { ptrs[i] my_malloc(64); assert(ptrs[i] ! NULL); } for (i 127; i 0; i--) { my_free(ptrs[i]); } // 用例4交替分配不同大小后释放 a (char *)my_malloc(100); b (char *)my_malloc(200); strcpy(a, my-malloc); strcpy(b, free-list); assert(strcmp(a, my-malloc) 0); assert(strcmp(b, free-list) 0); my_free(a); my_free(b); // 用例5realloc缩小和扩大 a (char *)my_malloc(16); strcpy(a, realloc demo); a (char *)my_realloc(a, 64); assert(a ! NULL); assert(strcmp(a, realloc demo) 0); my_free(a); printf(all tests passed\n); return 0; }MakefileCCgcc CFLAGS-Wall -Wextra -g -O2 all: test_malloc test_malloc: malloc.c malloc.h test_my_malloc.c $(CC) $(CFLAGS) -o $ test_my_malloc.c malloc.c run: test_malloc ./test_malloc clean: rm -f test_malloc在这个测试里能观察到一些有意思的现象第 3 个用例 128 个小块逆序释放时merge_blocks 会被多次触发如果把释放顺序改成乱序碎片化会更明显但后续分配仍能跑通说明合并逻辑在起作用。你可以把 my_malloc 换成系统的 malloc 跑一遍同样的用例行为一致说明我们的基础功能没有明显缺陷。gdb 调试的时候在 find_block 里打断点打印 b-free 和 b-next很快能看到链表有没有被破坏。如果出现段错误先用 bt 看调用栈大部分时候是 find_block 里 b-next 访问到了非法地址。按这个线索往回找是谁改了 next多半是越界写。几乎所有初学者遇到 malloc 崩溃第一反应都是“分配器写错了”但实际用 gdb 查下来分配器本身逻辑往往没问题反而是用户代码越界或者释放顺序不对。多调试几次就能养成先怀疑自己代码的习惯。5. 避坑手册自己实现malloc时踩过的五个坑5.1 sbrk两段式调用的竞态现象程序偶尔正常偶尔出现在 malloc 内部立刻段错误而且只在分配大块时出现。原因把 sbrk 写成一个单独的函数里面做 sbrk(0) 然后 sbrk(size)这两次系统调用之间如果发生了其他堆操作比如调试打印里偷偷 calloc 了一次堆顶变了第一次拿到的地址就作废了。第二次 sbrk 返回的地址才是真正可用的内存但你已经把旧的 sbrk(0) 结果当成新块地址写入了。解决把 sbrk(0) 和实际扩展合并成一次操作或者至少保证这两次调用中间不做任何可能触发堆分配的事。我的建议是写一个函数它只负责要内存一次调用完成 sbrk(0) 探址紧接着马上 sbrk(n) 扩展中间不插入任何可能分配内存的代码。检查失败时一定用 (void *)-1不要用 NULL。5.2 越界访问悄悄破坏链表现象malloc 返回的指针正常往里面写数据也不报错但后续某次 malloc 或 free 时突然段错误而且 gdb 看到的链表指针既不是 NULL 也不是合法地址。原因用户数据区越界了。比如分配了 16 字节向里面写了 32 字节多出来的 16 字节直接覆盖了下一个块的块头。链表指针被改成随机值直到某次遍历才暴露。解决在块头里加一个 magic 字段free 时校验有没有被覆盖。这是最省事的检测手段。我后来在测试里故意写了一个越界版本观察到的现象非常典型第一次分配正常第二次 malloc 时在 find_block 里崩溃。从那以后我所有自写的分配器都会在头部加一个 magic 字段不贵但排查越界能省半天时间。5.3 重复free导致链表成环或死循环现象同一指针被 free 两次第一次正常第二次程序进入无限循环CPU 占用 100%。原因第一次 free 后块被标记为空闲并做了合并第二次 free 时因为 ptr 前移找块头而这块可能已经被合并进更大的空闲块块的 size 和 next 已经变了继续置 free 可能出现奇怪状态。更严重的如果这块被再次分配给用户第二次 free 会把一个正在使用的块标记为空闲链表完整性彻底破坏。解决free 里加 if (!b-free) 判断至少能挡住“已释放块再次释放”的部分问题。但用户角度看正确姿势是 free 之后立刻把指针置为 NULL。项目里如果统一用一个 free_ptr 宏来做就省心很多。这个防护不能解决所有情况但在教学项目里能显著降低踩坑概率。5.4 堆只涨不缩现象程序反复分配释放小内存观察进程 RSS 一路走高free 之后内存并没有还给系统。原因sbrk 分配的堆是进程地址空间的一段连续区域释放后的块只是在链表里被标记为空闲并没有把堆顶降低。只有释放了堆顶的那一块并且上一块也空闲时sbrk(-n) 才能收缩这个逻辑比简单的“释放即归还”复杂得多。解决对刚实现起来的小型分配器来说“只涨不缩”是可接受的行为。如果内存占用是硬指标可以考虑两个方向一是超过某个阈值的大块改用 mmap 分配munmap 天然能归还二是调用 sbrk(-n) 实现堆顶收缩但要精确维护“只有最后一个块空闲才能缩”的状态。这个优化留给二次开发第一版先接受 RSS 缓慢上升。5.5 平台一换就对齐崩溃现象在自己笔记本上跑得好好的移植到某个嵌入式平台后分配返回的地址总不是 8 的倍数一用就崩。原因结构体大小在不同平台上不一样如果 BLOCK_SIZE 不是 8 的倍数那么 (char *)b BLOCK_SIZE 就会把对齐破坏掉。系统 malloc 保证返回的指针满足最大对齐要求自己实现的分配器如果忽略这一点在有的平台上会非常隐蔽地翻车。解决块头里 size 和 next 都用 size_tfree 用 int然后手动加 padding 字段再在代码里加一行静态断言_Static_assert(BLOCK_SIZE % 8 0, BLOCK_SIZE must be multiple of 8);编译期就把这个问题拦住比运行期一个块一个块去试探要省心得多。接嵌入式项目时这个断言尤其管用目标平台可能和开发机长得完全不一样。6. 二次开发给分配器加审计、改策略、上锁6.1 加内存审计统计分配次数与总字节想在现有分配器上做统计不需要大改只需加两个全局计数器和钩子。在 my_malloc 里面累加 size在 my_free 里减掉就能实时掌握当前存活字节数static size_t alloc_calls 0; static size_t alloc_bytes 0; static size_t free_calls 0; void *my_malloc(size_t size) { block_t *b; // 原有的查找、扩展逻辑保持不变 // 在返回前插入统计 alloc_calls; alloc_bytes size; return (void *)((char *)b BLOCK_SIZE); } void my_free(void *ptr) { block_t *b; if (!ptr) return; b (block_t *)((char *)ptr - BLOCK_SIZE); if (b-free) return; free_calls; alloc_bytes - b-size; b-free 1; merge_blocks(); }验证方法跑测试用例后检查 free_calls 是否等于 alloc_callsalloc_bytes 是否归零。如果归零说明所有块都正确释放了这是单线程下最直接的泄漏判定。注意 realloc 内部会先走 my_free 再走 my_malloc统计口径统一反而方便。把计数器和审计函数挂到测试程序末尾每次跑完直接看到结果。6.2 泄漏检测器退出时扫描未释放块更实用的做法是提供一个 audit_exit 函数在程序退出时遍历整个链表把所有 free 0 的块打印出来void audit_exit(void) { block_t *b; int leaked 0; for (b head; b; b b-next) { if (!b-free) { printf(leaked block: %p, size%zu\n, (void *)((char *)b BLOCK_SIZE), b-size); leaked; } } if (leaked) { printf(memory leak detected: %d blocks\n, leaked); } else { printf(no leak detected\n); } }把 audit_exit 放在程序 return 前调用就能在开发期快速发现泄漏。注意这个检测依赖链表遍历块数量到十万级时 O(n) 的开销会明显可见工程里可以维护一棵二叉搜索树按地址查块但教学阶段这个版本够了。6.3 换best-fit与加锁的起步改造想验证不同分配策略的效果最简单的改法是 find_block 里加一个最小余量跟踪static block_t *find_best(block_t **last, size_t size) { block_t *b; block_t *best NULL; size_t best_size 0; for (b head; b; b b-next) { if (b-free b-size size) { if (!best || b-size best_size) { best b; best_size b-size; } } } return best; }这就是 best-fit。代价是必然扫描完整条链表好处是留下的空闲块余量更均匀。先跑通 first-fit再替换成 best-fit对比同一份测试用例下重复分配的命中率是很直观的实验。多线程起步改造就是在 my_malloc 和 my_free 的入口各加一把 pthread_mutex粒度最粗但能保证正确。熟练以后可以再换细粒度锁每个块加一个锁或者用原子操作改 free 标记。第一版加锁会牺牲吞吐但能跑对就是好的开始。最后说一个习惯。每次改完分配器我都会把一个固定顺序的测试跑三遍第一遍用 128 个小块验证碎片第二遍故意越界验证 magic第三遍开着审计退出验证泄漏。这三关过了才敢说这个版本可以做下一步。希望帮到你。本文还有配套的精品资源点击获取
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
