简介这份资源面向希望深入理解C语言动态内存管理的开发者与计算机专业学生围绕“自己动手写malloc函数”这一主题提供一份可编译运行的简易内存分配器实现。压缩包共3个文件包含2个C源文件与1个头文件整体约3KB其中头文件声明接口源文件分别实现内存分配核心逻辑与测试用例便于读者对照代码理解堆管理、内存块划分与空闲链表维护等关键机制。资源通过my_malloc的完整实现展示了首次适配、内存碎片合并以及向操作系统扩展内存池的基本思路并留有对齐、并发控制等进阶问题的讨论空间。目前已有1827人学习下载适合作为操作系统或C语言进阶课程的配套实验素材帮助读者从调用者视角转向实现者视角掌握内存分配器的设计取舍与性能优化方向。1. 从一次内存踩踏说起为什么我要自己写一个 malloc线上服务每隔几天就 core 一次gdb 回溯指向同一行free()但指针明明刚分配过。查了三天最后发现是某处malloc(0)返回的指针被写了一个字节——标准库的 malloc 在零长度请求上行为未定义而我们的代码默认它至少给一块可写内存。这种玄学问题光看 man page 是看不出来的。于是我决定自己动手写一个 malloc把分配器的黑匣子拆开看个明白。这份资源就是一个从零实现内存分配器的完整项目包含隐式空闲链表、显式空闲链表、分离空闲链表三种组织方式以及首次适配、下次适配、最佳适配三种放置策略还带边界标签合并、内存对齐、堆扩展这些工程细节。适合已经会写 C、但对「指针背后到底发生了什么」一直没底的人也适合准备系统课大作业或面试被问「malloc 怎么实现」时想拿出真东西的开发者。2. 分配器架构拆解堆、块与空闲链表怎么串起来2.1 从sbrk到堆内存分配器的地基自己写 malloc第一件事不是写链表而是搞清楚内存从哪来。用户态程序没法直接碰物理内存分配器能拿到的只有进程虚拟地址空间里一段连续的堆区。在 Linux 上扩展堆区最直接的系统调用是sbrk它把 program break 指针往高地址推推多少就多出多少可用堆空间。#include unistd.h /* 把堆扩展 incr 字节返回旧 break 地址失败返回 (void *)-1 */ static void *mem_sbrk(int incr) { char *old_brk (char *)sbrk(0); /* 当前 break */ if (incr 0) return old_brk; if ((long)sbrk(incr) -1) /* 尝试扩展 */ return (void *)-1; return old_brk; /* 返回扩展前的起点 */ }这段代码是整个分配器的入口。sbrk(0)不扩展只返回当前 break 地址常用来探测堆顶sbrk(incr)成功返回旧 break失败返回 -1。参数incr是请求扩展的字节数通常按页大小4096向上取整避免频繁陷入内核。注意sbrk返回的是void *直接做指针运算在部分编译器上会告警所以先转成char *。堆扩展是分配器唯一向操作系统要内存的通道后面所有块管理都在这块连续区域里做文章。2.2 块格式与边界标签让合并成为可能堆拿到手是一整块裸内存分配器要把它切成「块」。每个块由头部、有效载荷、填充可选组成。头部记录块大小和分配状态这是后面遍历和合并的依据。/* 块头部低 3 位做标志高位存块大小8 字节对齐 */ #define WSIZE 4 /* 字大小 */ #define DSIZE 8 /* 双字对齐单位 */ #define CHUNKSIZE (1 12) /* 默认扩展 4KB */ #define PACK(size, alloc) ((size) | (alloc)) /* 大小与标志打包 */ #define GET(p) (*(unsigned int *)(p)) #define PUT(p, val) (*(unsigned int *)(p) (val)) #define GET_SIZE(p) (GET(p) ~0x7) /* 取块大小 */ #define GET_ALLOC(p) (GET(p) 0x1) /* 取分配位 */这里用低 3 位存标志是因为块大小按 8 字节对齐低 3 位天然为 0可以白捡来用。PACK把大小和分配位或在一起写进头部GET_SIZE用掩码抹掉标志位还原大小。边界标签是这套设计的精髓每个块除了头部末尾再放一个脚部内容和头部一致。这样从任意块出发既能通过头部往后走也能通过脚部往前走合并相邻空闲块时不用从头遍历整个堆。代价是每个块多 4 字节开销换来 O(1) 的前向合并能力这笔账在通用分配器里是划算的。2.3 隐式空闲链表最朴素的遍历方式有了块格式把所有块用头部串起来就是隐式空闲链表。它没有真正的指针靠块大小一步步跳。/* 从块指针 bp 出发找下一个块 */ #define NEXT_BLKP(bp) ((char *)(bp) GET_SIZE(((char *)(bp) - WSIZE))) /* 找上一个块靠前一个块的脚部 */ #define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE))) static void *find_fit(size_t asize) { void *bp; /* 从堆起始块开始逐块扫描 */ for (bp heap_listp; GET_SIZE(HDRP(bp)) 0; bp NEXT_BLKP(bp)) { if (!GET_ALLOC(HDRP(bp)) GET_SIZE(HDRP(bp)) asize) return bp; /* 首次适配第一个够大的空闲块 */ } return NULL; /* 没找到 */ }NEXT_BLKP用当前块大小跳过头部和载荷落到下一块头部PREV_BLKP往前退一个双字到前块脚部读出前块大小再退回去。find_fit是首次适配策略从头扫到尾返回第一个满足asize的空闲块。参数asize是「请求大小 头部 脚部 对齐填充」后的实际块大小不是用户原始请求。隐式链表实现简单但分配时间与堆中块总数成正比堆一大就慢这是它最大的短板。2.4 显式空闲链表与分离链表把空闲块单独管起来隐式链表扫描时把已分配块也扫了一遍纯属浪费。显式空闲链表只把空闲块用前驱后继指针串成双向链表分配时只遍历空闲块。/* 空闲块载荷区前两个双字放前驱和后继指针 */ #define PREV_FREEP(bp) (*(void **)(bp)) #define NEXT_FREEP(bp) (*(void **)((char *)(bp) DSIZE)) static void insert_free(void *bp) { /* 头插法新空闲块插到链表头部 */ NEXT_FREEP(bp) free_listp; PREV_FREEP(bp) NULL; if (free_listp) PREV_FREEP(free_listp) bp; free_listp bp; }空闲块的有效载荷区在空闲时是没用的正好拿来存前驱后继指针不额外占空间。insert_free用头插法把块挂进链表O(1) 完成。分离空闲链表在此基础上按大小分桶比如 16 字节以下一桶、16 到 32 一桶每桶一个链表分配时先查对应桶找不到再查更大桶。这样既缩小了搜索范围又保留了最佳适配的近似效果。三种组织方式在项目里是递进实现的建议按隐式、显式、分离的顺序读每一步都能看到上一版的性能瓶颈在哪。3. 跑起来编译、测试与性能对比3.1 目录结构与构建方式项目按功能拆成几个源文件头文件放公共宏和函数声明测试代码单独放方便替换不同版本的分配器做对比。malloc-lab/ ├── include/ │ └── mm.h # 块格式宏、函数声明 ├── src/ │ ├── mm.c # 分配器核心实现 │ └── memlib.c # 堆内存管理封装 ├── tests/ │ ├── trace_test.c # 功能正确性测试 │ └── perf_test.c # 吞吐与利用率测试 └── Makefilemm.c是主战场memlib.c把sbrk包一层提供mem_init、mem_heap_lo、mem_heap_hi这些接口让分配器代码不直接依赖系统调用方便在模拟堆上跑测试。Makefile里通常有make、make test、make perf几个目标编译时开-Wall -O2优化级别会影响内联和指针运算测性能时别用-O0。3.2 功能测试正确性先过关功能测试覆盖分配、释放、重分配、合并、对齐这些基本路径。下面是一段典型的测试驱动。#include mm.h #include assert.h #include stdio.h int main(void) { mm_init(); /* 初始化堆和空闲链表 */ void *p1 mm_malloc(16); /* 分配 16 字节 */ void *p2 mm_malloc(32); assert(p1 p2); assert(((size_t)p1 % 8) 0); /* 检查 8 字节对齐 */ mm_free(p1); /* 释放 p1 */ void *p3 mm_malloc(16); /* 应复用 p1 的空间 */ assert(p3 p1); mm_free(p2); mm_free(p3); printf(all tests passed\n); return 0; }mm_init负责初始化堆、创建序言块和结尾块序言块是永远分配的对齐块结尾块大小为零做哨兵。mm_malloc返回的指针必须 8 字节对齐这是 ABI 要求不对齐在部分架构上直接崩。mm_free后立即mm_malloc同样大小期望复用刚释放的块这是检验空闲链表是否正常工作的最小用例。跑通这个再上更复杂的随机分配释放序列。3.3 性能测试吞吐率与内存利用率正确性过了不代表能用分配器还要看两个指标吞吐率和内存利用率。吞吐率是单位时间完成的分配释放次数利用率是峰值载荷除以堆大小。# 编译并运行性能测试 make perf ./perf_test --trace traces/random.rep --iters 100000--trace指定分配释放序列文件--iters控制迭代次数。测试程序会输出平均每次操作耗时和堆利用率。隐式链表在随机序列上通常吞吐最低分离链表最高但分离链表因为分桶可能产生内部碎片利用率略低。这个权衡没有标准答案取决于负载特征短生命周期小对象多用分离链表长生命周期大对象多用显式链表配最佳适配。测的时候多跑几组不同分布的 trace别只看一组数据就下结论。注意性能测试结果受编译优化、机器负载、trace 分布影响很大同一份代码在不同环境跑出两倍差距很正常对比时务必固定编译选项和运行环境。4. 核心代码逐段讲分配、释放与合并4.1mm_malloc从请求到块的完整链路mm_malloc是用户唯一入口它要把用户请求的字节数翻译成块大小找到合适空闲块没有就扩展堆最后返回载荷指针。void *mm_malloc(size_t size) { size_t asize; /* 调整后的块大小 */ size_t extendsize; /* 需要扩展的字节数 */ char *bp; if (size 0) return NULL; /* 零请求直接拒绝 */ if (size DSIZE) /* 最小块 16 字节 */ asize 2 * DSIZE; else asize DSIZE * ((size DSIZE (DSIZE - 1)) / DSIZE); if ((bp find_fit(asize)) ! NULL) { /* 找到空闲块 */ place(bp, asize); /* 放置并可能分割 */ return bp; } extendsize MAX(asize, CHUNKSIZE); /* 至少扩展 4KB */ if ((bp extend_heap(extendsize / WSIZE)) NULL) return NULL; place(bp, asize); return bp; }size 0直接返回 NULL这是比标准库更明确的行为避免调用方误写。size DSIZE时块大小取2 * DSIZE因为块至少要容纳头部、脚部和前驱后继两个指针。asize的计算把请求大小加上头部脚部开销再向上取整到 8 的倍数保证对齐。find_fit返回空闲块后调placeplace负责决定是整块给还是分割剩余部分够大就切成两个块不够就整块给避免产生无法使用的碎片。找不到就extend_heap扩展扩展量取asize和CHUNKSIZE的较大者减少系统调用次数。4.2place与coalesce分割与合并的细节place和coalesce是分配器里最容易写错的两个函数一个管切一个管合。static void place(void *bp, size_t asize) { size_t csize GET_SIZE(HDRP(bp)); /* 当前空闲块大小 */ if ((csize - asize) (2 * DSIZE)) { /* 剩余够放一个最小块 */ PUT(HDRP(bp), PACK(asize, 1)); /* 前半分配 */ PUT(FTRP(bp), PACK(asize, 1)); bp NEXT_BLKP(bp); /* 后半变空闲块 */ PUT(HDRP(bp), PACK(csize - asize, 0)); PUT(FTRP(bp), PACK(csize - asize, 0)); insert_free(bp); /* 挂回空闲链表 */ } else { PUT(HDRP(bp), PACK(csize, 1)); /* 整块分配 */ PUT(FTRP(bp), PACK(csize, 1)); } } static void *coalesce(void *bp) { size_t prev_alloc GET_ALLOC(FTRP(PREV_BLKP(bp))); size_t next_alloc GET_ALLOC(HDRP(NEXT_BLKP(bp))); size_t size GET_SIZE(HDRP(bp)); if (prev_alloc next_alloc) { /* 两边都占用 */ return bp; } else if (prev_alloc !next_alloc) { /* 只合并后块 */ size GET_SIZE(HDRP(NEXT_BLKP(bp))); remove_free(NEXT_BLKP(bp)); } else if (!prev_alloc next_alloc) { /* 只合并前块 */ size GET_SIZE(HDRP(PREV_BLKP(bp))); bp PREV_BLKP(bp); remove_free(bp); } else { /* 两边都空闲 */ size GET_SIZE(HDRP(PREV_BLKP(bp))) GET_SIZE(HDRP(NEXT_BLKP(bp))); remove_free(PREV_BLKP(bp)); remove_free(NEXT_BLKP(bp)); bp PREV_BLKP(bp); } PUT(HDRP(bp), PACK(size, 0)); PUT(FTRP(bp), PACK(size, 0)); return bp; }place里判断剩余空间是否够2 * DSIZE这是最小块大小不够就不切否则切出来的小块永远无法被复用。切完把后半块头部脚部都写成空闲再insert_free挂回链表。coalesce用前块脚部和后块头部判断相邻块状态四种情况分别处理合并后更新头部脚部大小。注意合并前要先把被吞并的空闲块从链表里摘掉否则链表里会残留已失效节点后续遍历直接踩空。这个顺序错了就是血泪经验调试时表现为随机崩溃。4.3mm_free释放与立即合并释放本身很简单把块标记为空闲再尝试合并即可。void mm_free(void *ptr) { if (ptr NULL) return; /* 释放 NULL 是合法的 */ size_t size GET_SIZE(HDRP(ptr)); PUT(HDRP(ptr), PACK(size, 0)); /* 标记为空闲 */ PUT(FTRP(ptr), PACK(size, 0)); coalesce(ptr); /* 立即合并相邻空闲块 */ }ptr NULL直接返回和标准库行为一致调用方不用额外判空。标记空闲后立刻调coalesce这是「立即合并」策略好处是空闲块不会碎片化坏处是每次释放都有合并开销。另一种做法是延迟合并释放时只标记分配时再合并吞吐更高但碎片更多。项目里默认立即合并想改成延迟合并只需把coalesce调用挪到find_fit之前改动很小适合拿来对比两种策略的实际差异。5. 避坑与排查那些让我熬夜的分配器 bug5.1 现象随机崩溃在free或malloc里原因通常是块头部被越界写坏。用户申请 16 字节却写了 17 字节多出的一个字节覆盖了下一块的头部标志位导致GET_SIZE读出天文数字NEXT_BLKP直接跳到非法地址。解决方法是加保护字在载荷末尾多留 4 字节写魔数释放时校验不匹配就报错并打印块地址。调试期还可以在place里加断言检查asize和csize关系是否合理。5.2 现象合并后链表里出现重复节点原因是coalesce里先合并再摘链表或者摘链表时只更新了一侧指针。正确顺序是先把要被吞并的块从空闲链表摘除再改头部脚部。摘除时前驱后继四个指针都要维护漏一个就断链。排查时可以在insert_free和remove_free里加计数器运行结束检查链表节点数和实际空闲块数是否一致。5.3 现象内存利用率异常低常见于place的分割阈值设得太小切出大量 8 字节、16 字节的碎片块这些块永远无法满足后续稍大的请求。把阈值从DSIZE提到2 * DSIZE甚至4 * DSIZE能明显改善。另一个原因是extend_heap每次只扩展请求大小导致堆里全是小块改成至少扩展CHUNKSIZE并向上取整到页大小利用率和吞吐都会好转。5.4 现象对齐断言在特定请求下失败mm_malloc(1)到mm_malloc(8)这些请求如果asize计算没考虑头部脚部返回的载荷指针可能不是 8 的倍数。检查asize公式里有没有加DSIZE再向上取整。另外序言块和结尾块的初始化也要保证对齐mem_init里第一次mem_sbrk的偏移量要对齐到DSIZE否则整个堆从起点就歪了。5.5 现象性能测试吞吐远低于预期先确认编译开了-O2-O0下指针运算和函数调用开销能差好几倍。再看find_fit是不是每次从头扫显式链表如果没做分离大堆上退化成线性扫描。最后检查insert_free是不是头插头插会让最近释放的块最先被复用缓存局部性好尾插则相反。这几个点逐个排查通常能找回大部分性能。6. 二次开发换策略、加统计、接真实负载拿到这份代码后最值得做的改造是把放置策略做成可配置的。现在find_fit写死了首次适配改成函数指针数组运行时通过环境变量或配置文件选择首次、下次、最佳适配就能在同一份测试上横向对比。typedef void *(*fit_fn)(size_t); static fit_fn fit_policy find_fit_first; /* 默认首次适配 */ void *mm_malloc(size_t size) { /* ... 前面的 asize 计算不变 ... */ if ((bp fit_policy(asize)) ! NULL) { place(bp, asize); return bp; } /* ... 扩展逻辑不变 ... */ }fit_fn是函数指针类型fit_policy默认指向首次适配想换策略就改这一行或从外部注入。下次适配需要记录上次搜索位置用一个静态指针存last_bp每次从它开始扫扫到结尾再绕回头。最佳适配则要遍历整个空闲链表记录最小满足块吞吐会降但利用率升。三种策略都实现后用同一组 trace 跑对比数据比嘴说有力。第二个改造方向是加统计埋点。在mm_malloc、mm_free、coalesce里累加计数器总分配次数、总释放次数、合并次数、扩展次数、当前空闲块数、峰值堆大小。这些数据在mm_init时清零程序结束前打印。有了统计调优时不用猜直接看哪个指标异常。比如合并次数远小于释放次数说明相邻空闲块少碎片已经严重扩展次数居高不下说明CHUNKSIZE太小。第三个方向是接真实负载。项目自带的 trace 是合成的分布未必贴近你的场景。可以把分配器编译成动态库用LD_PRELOAD挂到真实程序上拦截malloc、free、realloc、calloc记录真实请求大小分布和生命周期。跑一段时间后把记录导出成 trace 文件再喂给性能测试这样测出来的数据才有参考价值。注意LD_PRELOAD只影响动态链接的程序静态链接的得重新编译。最后一个技巧是给分配器加「后悔药」在mm_free里不立即合并而是把块标记为「待合并」攒到一定数量或堆利用率低于阈值时再批量合并。这样释放路径变短吞吐提升代价是峰值内存略高。实现时用一个待合并队列队列满了触发一次全堆合并。这个策略在短生命周期对象多的场景下效果明显但队列本身要占内存得设上限防止失控。从那以后我每次改分配器都强制先跑一遍功能测试再跑性能测试功能没过绝不看性能数据——顺序反了调出来的优化全是假的。希望帮到你。本文还有配套的精品资源点击获取