简介：这份资源面向希望深入理解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返回空闲块后调place，place负责决定是整块给还是分割：剩余部分够大就切成两个块，不够就整块给，避免产生无法使用的碎片。找不到就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. 避坑与排查：那些让我熬夜的分配器 bug
5.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里不立即合并，而是把块标记为「待合并」，攒到一定数量或堆利用率低于阈值时再批量合并。这样释放路径变短，吞吐提升，代价是峰值内存略高。实现时用一个待合并队列，队列满了触发一次全堆合并。这个策略在短生命周期对象多的场景下效果明显，但队列本身要占内存，得设上限防止失控。
从那以后我每次改分配器，都强制先跑一遍功能测试再跑性能测试，功能没过绝不看性能数据——顺序反了，调出来的优化全是假的。希望帮到你。
本文还有配套的精品资源，点击获取
