简介：围绕 CSAPP 的 malloc 实验整理的分析资料包，面向正在学习《深入理解计算机系统》、需要动手实现动态内存分配器的学生与自学者。内容聚焦内存池管理、块头与空闲链表组织、内外碎片控制、地址对齐以及 free 与 realloc 的释放和扩展策略，帮助读者把教材中抽象的内存管理机制落到可运行的代码与实验分析中。压缩包共 9 个文件，约 781KB，以 C/C++ 源码和可执行程序为主，另含实验分析演示文稿、备份文件与运行截图，覆盖实现、调试到结果展示的完整链路；源码可对照阅读分配、合并与分裂逻辑，演示文稿适合梳理实验思路和性能优化要点，备份文件则保留实现版本痕迹。已有 964 人学习，适合在 malloc lab 前后对照复盘，理解分配器设计取舍、碎片处理细节与常见排错方向，对内部碎片与外部碎片的权衡、空闲链表查找策略和分配器吞吐率形成更直观的认识。
1. 知识地图：malloc lab 真正考的是四件事的组合
CSAPP 讲虚拟内存那一章后面挂着这个实验。多数人第一次打开它，以为任务就是写 malloc 和 free 两个函数，真正卡住的地方却在别处：堆怎么布局、块怎么切、空闲块用什么结构管理、边界条件怎么兜底，以及利用率（utilization）和吞吐量（throughput）这两个互相拉扯的指标怎么平衡。系统学 CSAPP 的人在这一关翻车，往往不是 C 语言不熟，而是脑子里没有一张从 mem_sbrk 一路连到评分函数的完整地图。这条主线其实很短：把一段连续堆切成块，用一种链表结构管理空闲块，在空间利用和查找速度之间选一个位置站好。下面按这条主线一层层拆。
2. 堆与块：从 mem_sbrk 到边界标记的内存布局
布局是整个实验的地基。地基一旦歪了，后面所有查找和合并逻辑都会在某个长 trace 上突然崩掉，而且报错位置离真正出错的地方可能隔着几千次操作，这也是这个实验最难受的地方。先把堆的形状和块的格式确定下来，再写逻辑，能省掉大量反复排查。
2.1 堆从哪里来：mem_sbrk 的语义与序言块
实验环境里的堆不是你自己声明的数组，而是由一组封装好的内存接口提供。mem_init负责在进程里划出一块堆区，mem_sbrk(incr)把堆顶指针向高地址移动 incr 个字节，返回的是移动之前的旧断点，失败时返回(void *)-1。这里有个关键限制：它只能往高地址长，传负数出去不会报错，行为是未定义的，别指望用它来缩堆。所以释放内存并不真的还给系统，只是把块标记成空闲，等着被后续的 malloc 复用。
第一次调用 malloc 时要完成初始化。教材里的经典做法是申请 4 个字：第一个字做对齐填充，第二个字做序言块头部，第三个字做序言块脚部，第四个字做结尾块头部。序言块本身是「已分配、大小 8」的假块，结尾块是「已分配、大小 0」的假块，两个都不能被分配出去，也不能被合并掉。
int mm_init(void) { /* 申请 4 个字：填充 + 序言块头 + 序言块脚 + 结尾块头 */ if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1) return -1; PUT(heap_listp, 0); /* 对齐填充，保证 8 字节对齐 */ PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1)); /* 序言块头部：大小 8，已分配 */ PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1)); /* 序言块脚部 */ PUT(heap_listp + (3 * WSIZE), PACK(0, 1)); /* 结尾块头部：大小 0，已分配 */ heap_listp += (2 * WSIZE); /* 指向序言块的「块指针」位置 */ /* 预先扩一块出来，减少后续 mem_sbrk 的调用次数 */ if (extend_heap(CHUNKSIZE / WSIZE) == NULL) return -1; return 0; }heap_listp指向的是序言块的块指针位置，也就是序言块脚部那个字。这样写的好处是：第一个真实区块调用PREV_BLKP时，往前读到的是序言块脚部，它的已分配位为 1，合并逻辑会自动停住；最后一个真实块调用NEXT_BLKP时，往后读到的是结尾块头部，大小为 0、已分配为 1，所有遍历循环都能靠这个条件干净地终止。
这两个假块看着多余，其实是整个实验的「后悔药」。少了序言块，第一个块的向前合并会读到堆外或者填充区里的随机值；少了结尾块，所有for循环都会跑飞。很多人在调试时发现程序在长 trace 的中段突然段错误，根因就是初始化时头脚两个字写反了，导致结尾块的已分配位是 0，被当成空闲块合了进去。
2.2 块格式：头部、脚部与载荷的三角关系
一个块的布局是「头部 4 字节 + 载荷 + 脚部 4 字节」。头部存两样东西：整块大小和分配位。因为块大小按 8 字节对齐，二进制末尾三位恒为 0，于是最低位被拿来当已分配标记，0 表示空闲、1 表示已分配，另外两位留空备用。脚部是头部的完整拷贝，它存在的唯一理由是让合并变成 O(1)：有了脚部，给定一个块指针往前一步就能读到前一个块的大小，不需要从头遍历。
载荷的起点就是平时返回给调用方的指针。在隐式链表版本里，载荷的最小容量是 8 字节，因为对齐要求返回指针 8 字节对齐；在显式链表版本里，载荷要能塞下两个指针，各 4 字节，正好也是 8 字节。所以两种实现的最小块大小都能压在 16 字节：头 4 + 载荷 8 + 脚 4。
这里最容易忽略的细节是：头部里记录的是「整块」大小，包含头部和脚部，不是载荷大小。调用方请求 n 字节，实际要申请的块是「n 向上取整到 8 的倍数，再加 8 字节头脚开销」。如果把这个换算搞混，返回的指针和块头就会错位，表现出来往往是第一次 free 就崩。
2.3 对齐、最小块与一组必须写对的宏
块的操作最终都落在几个宏上，这几个宏写错了，后面所有函数都会跟着错。它们被反复调用，写成宏比函数更合适。
#define WSIZE 4 /* 字长，头部/脚部的大小 */ #define DSIZE 8 /* 双字长，也就是对齐单位 */ #define CHUNKSIZE (1 << 12) /* 每次扩展堆的默认字节数：4096 */ #define MAX(x, y) ((x) > (y) ? (x) : (y)) #define PACK(size, alloc) ((size) | (alloc)) /* 低 3 位是标志位，可以或进去 */ #define GET(p) (*(unsigned int *)(p)) /* 读一个字 */ #define PUT(p, val) (*(unsigned int *)(p) = (val)) /* 写一个字 */ #define GET_SIZE(p) (GET(p) & ~0x7) /* 清掉低 3 位，取块大小 */ #define GET_ALLOC(p) (GET(p) & 0x1) /* 只看最低位，取分配标记 */ /* bp 是块指针（载荷起点），下面四个宏在 bp 和头/脚之间来回换算 */ #define HDRP(bp) ((char *)(bp) - WSIZE) #define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE) #define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE((char *)(bp) - WSIZE)) #define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE((char *)(bp) - DSIZE))GET_SIZE用~0x7做掩码，而不是~0x1，因为块大小永远是 8 的倍数，低三位一定为 0，多清两位不影响结果，还能顺带兼容将来往标志位里加信息。FTRP依赖本块自己的头部大小，所以「先改头部再算脚部」的顺序在分裂和合并里必须严格遵守，顺序反了算出来的脚部地址就是旧值。
NEXT_BLKP和PREV_BLKP的区别值得单独记一下：往前跳只读本块的头部，往后退只读前一块的脚部，两者都不需要遍历，这就是边界标记的价值。代价是每个空闲块都要多花 4 字节存脚部，如果追求极致利用率，有人会去掉空闲块的脚部，只在已分配块里保留，但那会让合并逻辑复杂一大截，不建议一上来就这么干。
CHUNKSIZE取 4096 是个经验值。取太小，mem_sbrk 调用次数多，吞吐量掉；取太大，堆里长期躺着一大块用不上的空闲区，利用率掉。mdriver 的评分里这两个指标是互相拉扯的，所以这个常数后期往往要拿具体 trace 试几组值再定。
3. 三种空闲链表：隐式、显式与分离适配的取舍
把块管起来的方式只有三类：不建链表、建一条链表、建一堆链表。它们的差别不在于「能不能跑通」，而在于同样一组 trace 跑出来的吞吐量和利用率差多少。理解这三者的取舍，比背下任何一份实现都重要，因为评分函数惩罚的正是选错结构。
3.1 隐式空闲链表：把整个堆当成一条链表
隐式链表的思路最朴素：不额外存任何指针，靠块头里的大小信息在堆上跳跃遍历。从头部的下一个位置开始，读大小、跳到下一块，一直走到结尾块为止，遇到空闲且足够大的块就用。它本质上是一条用块大小隐式串起来的链表，名字就是这么来的。
好处是实现量小、没有额外空间开销，每个块只需要头脚 8 字节。缺点也很直接：查找时要经过堆里每一个块，包括大量已分配的块，随着 trace 变长，每次 malloc 的代价线性上升，吞吐量在所有方案里垫底。它适合先跑通用，先让-V校验全绿，把合并逻辑和边界条件都验证对，再考虑换结构。
用隐式链表时有一个小优化值得知道：查找循环里可以用GET_SIZE的返回值直接推进指针，同时把已分配位判断放在大小判断前面，短路求值能让大部分块只读一次头部就跳过。这种微调在长 trace 上能省下可观的指令数，但对数量级的提升没有帮助。
3.2 显式空闲链表：双向指针与 LIFO/地址序
显式链表把空闲块单独串成一条双向链表，指针就存在空闲块的载荷里。因为空闲块的载荷本来也没人用，等于白嫖了两个指针位置，最小块依然是 16 字节，不需要增大。
/* 空闲块载荷里的前驱和后继指针 */ #define PREV_FREEP(bp) (*(void **)(bp)) #define NEXT_FREEP(bp) (*(void **)((char *)(bp) + WSIZE))查找时只走空闲块，跳过了所有已分配块，效率比隐式链表高一个档次。删除是双向链表的常规操作，O(1)；插入有两种策略，选择不同，后面的表现差别很大。
LIFO 策略把新释放的块插到链表头部。优点是插入完全 O(1)，而且刚释放的块最可能还在缓存里，下次分配立刻就能命中，吞吐量好看。缺点是链表顺序和地址顺序完全脱节，相邻的空闲块在链表里可能隔得很远，不利于后续的地址序合并优化。
地址序策略要求链表按块地址从小到大排列。插入时要遍历找到位置，慢一些，但相邻空闲块在链表里也相邻，合并和分裂时能顺手做掉，长期看碎片更少、利用率更高。选哪个，取决于你更想保住吞吐量还是利用率，两个指标权重相同时，我一般先上 LIFO 看基线分数，再换地址序对比。
3.3 分离空闲链表：大小类怎么划、适配策略怎么选
分离空闲链表维护一组链表，每个链表管一个大小区间，块按大小归入对应的类。分配时先算请求属于哪一类，在该类里找，找不到再去更大的类里找。这是真实分配器最常见的做法，也是这个实验冲高分的主流路线。
大小类的划分方式直接影响效果。简单做法是按 2 的幂切：16~31、32~63、64~127，以此类推；更细的做法是在小尺寸区间用线性划分，比如 16、32、48、64 各一类，尺寸大了再按 2 的幂合并。小块多分几类是因为小请求最密集，分类粗了会在一个类里塞进大量尺寸不一的块，最佳适配退化成近似随机适配。
配套还要选适配策略。首次适配挑第一个够大的块，实现简单、命中快；最佳适配遍历整类找最贴近的块，利用率好但慢；下次适配从上次的位置继续找，理论上分布均匀，实测收益不稳定。在分离链表里，首次适配通常就够了，因为分类本身已经把搜索范围压得很小，再追求最佳适配的边际收益不高。
| 结构 | 查找代价 | 每空闲块额外开销 | 利用率 | 实现难度 | 适合阶段 |
|---|---|---|---|---|---|
| 隐式空闲链表 | 走遍堆中所有块 | 0 字节（头脚已含） | 中 | 低 | 先跑通、验证正确性 |
| 显式空闲链表 | 走遍空闲块 | 8 字节（前驱+后继） | 中偏高 | 中 | 稳定在中等分数 |
| 分离空闲链表 | 只走目标大小类 | 8 字节 + 类头数组 | 高 | 高 | 冲高分、压碎片 |
关于分离链表还有一个分支要分清：简单分离存储不分裂、不合并，分配多快有多快，但一个 4096 字节的空闲块被请求 16 字节时也只能整块给出去，利用率会掉得很惨。分离适配则允许分裂和合并，是真正能上分的版本。名字只差两个字，行为差一个数量级。
4. 四个核心函数：分配、释放、合并与 realloc 的写法
四个接口里，malloc 和 free 是主干，realloc 和 calloc 是常被轻视的配角。真正拉开分数差距的往往是 realloc，因为它既能省掉一次拷贝，又能把一个块原地撑大，做得好能同时改善两个指标。这一章按调用顺序把这四个函数拆开看。
4.1 malloc 主流程：先找空闲块，找不到再扩堆
malloc 的流程可以压成四步：调整请求大小、查空闲链表、命中就（可选）分裂、没命中就扩堆后重试。调整大小这一步要同时做三件事：加上头脚开销、向上取整到 8 的倍数、保证不低于最小块 16 字节。三件事漏一件，后面都会出问题。
void *mm_malloc(size_t size) { size_t asize; /* 调整后的块大小 */ size_t extendsize; /* 需要扩展的字节数 */ char *bp; if (size == 0) /* 约定：请求 0 字节返回 NULL 或最小块，二者选一但要统一 */ return NULL; /* 载荷至少 8 字节，整块至少 16 字节，并对齐到 8 的倍数 */ if (size <= DSIZE) asize = 2 * DSIZE; else asize = DSIZE * ((size + DSIZE + (DSIZE - 1)) / DSIZE); if ((bp = find_fit(asize)) != NULL) { place(bp, asize); /* 找到就放，剩余够大就分裂 */ return bp; } /* 没找到：至少扩一个 CHUNKSIZE，或者扩够本次所需 */ extendsize = MAX(asize, CHUNKSIZE); if ((bp = extend_heap(extendsize / WSIZE)) == NULL) return NULL; place(bp, asize); return bp; }place里最关键的是一个判断：剩余部分够不够构成一个合法的最小块。如果够，就把原块切成「已分配的前半 + 空闲的后半」，注意先改头部再算脚部，最后给后半块补上头脚；如果不够，就把整块都给出去，内部碎片虽然浪费了，但总比制造一个 8 字节的非法块强。这个判断条件写错，是后面所有诡异崩溃的源头之一。
extend_heap要做的事情比看上去多：调 mem_sbrk 拿旧断点、在新空间头部写块大小、在新空间末尾写新的结尾块、把原来的结尾块覆盖掉、然后对新块做一次合并。最后这一步容易被跳过，结果新扩出来的空间永远无法和它前面的空闲块合并，堆里逐渐散落一堆相邻但不相连的空闲块。
4.2 free 与 coalesce：四种情形逐一过
free 本身只有两行：把头部和脚部的分配位清掉，然后调 coalesce 尝试合并。真正的工作量全在合并里，而合并只有四种情形，按前后两个块的分配状态组合穷举即可。
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))); PUT(HDRP(bp), PACK(size, 0)); /* 必须先改头 */ PUT(FTRP(bp), PACK(size, 0)); /* 再算脚，因为 FTRP 依赖新头部 */ } else if (!prev_alloc && next_alloc) { /* 情形三：只并前面 */ size += GET_SIZE(HDRP(PREV_BLKP(bp))); PUT(FTRP(bp), PACK(size, 0)); /* 先写旧块的脚，此时头部还没变 */ PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0)); bp = PREV_BLKP(bp); /* 返回合并后的新块指针 */ } else { /* 情形四：两侧都空闲，三块合一 */ void *prev = PREV_BLKP(bp); void *next = NEXT_BLKP(bp); size += GET_SIZE(HDRP(prev)) + GET_SIZE(HDRP(next)); PUT(HDRP(prev), PACK(size, 0)); PUT(FTRP(next), PACK(size, 0)); bp = prev; } return bp; }几个写法上的讲究。情形二里必须先写头部再写脚部，因为FTRP(bp)会重新读一次头部大小来定位脚部，头部没更新的话算出来还是旧位置，脚部就写到块中间去了。情形三里顺序反过来，要先写脚部，因为此时bp的头部还是旧值，写完新头部之后再算FTRP(bp)会得到错误位置。情形四用两个临时变量存住前后块指针，避免在改写头部之后还得依赖旧值去推地址。
如果用的是显式链表，合并完成之后还要把被吞掉的那些空闲块从链表里摘掉，再把合并后的新块插回去。摘除时记得处理「被删的块正好是链表头」的情况，否则链表头会指向一个已经被合并掉的地址。这个 bug 的典型症状是：单独跑短 trace 全对，跑长 trace 到某一段突然访问非法地址。
4.3 realloc 与 calloc：两个最容易被轻视的接口
realloc 的语义是「把 oldptr 指向的块调整到 size 字节，尽量原地完成」。它能原地就原地，不能原地才走 malloc + 拷贝 + free 的老路。原地扩展的条件是：后一个块空闲，且它的大小加上本块大小，够放下新的请求。
void *mm_realloc(void *oldptr, size_t size) { size_t oldsize, nextsize, newsize; void *newptr; if (oldptr == NULL) /* 等价于 malloc(size) */ return mm_malloc(size); if (size == 0) { /* 等价于 free(oldptr)，返回 NULL */ mm_free(oldptr); return NULL; } oldsize = GET_SIZE(HDRP(oldptr)) - DSIZE; /* 旧块可用的载荷字节数 */ /* 情形一：新请求更小，原地返回，必要时切掉尾部变成空闲块 */ if (size <= oldsize) return oldptr; /* 情形二：看后一个块是不是空闲的，能不能并进来凑够 */ nextsize = GET_SIZE(HDRP(NEXT_BLKP(oldptr))); if (!GET_ALLOC(HDRP(NEXT_BLKP(oldptr))) && oldsize + nextsize >= size + DSIZE) { /* 合并后足够：吞掉后块，切成新块和剩余空闲块 */ coalesce(oldptr); place(oldptr, DSIZE * ((size + DSIZE + (DSIZE - 1)) / DSIZE)); return oldptr; } /* 情形三：原地做不到，老老实实搬家 */ newsize = size; if ((newptr = mm_malloc(newsize)) == NULL) return NULL; memcpy(newptr, oldptr, (oldsize < newsize) ? oldsize : newsize); mm_free(oldptr); return newptr; }几个细节。拷贝长度必须取新旧大小的较小值，写成固定的 newsize 会多读一段不属于自己的内存，写成固定的 oldsize 在扩大时会把堆里别的内容带过去。情形二里判断够不够的时候，要把块头的开销也算进去，判断写成oldsize + nextsize >= size会差出一个头部，结果就是合并之后发现放不下，块已经被改坏，只能从头查。
calloc 常见做法是调 malloc 再memset清零。这里有个小陷阱：清零的长度是请求的 size，不是调整后的块大小，清多了会覆盖相邻块的头部。它本身不是评分重点，但 trace 里只要出现一次，堆校验就会挂。
5. 易错点与评分：五个翻车现场和双指标的调优
这一章把最常见的问题集中列一遍，每一条都按「易漏点 → 为什么漏 → 怎么补」写，后面再讲评分函数是怎么牵引实现选择的。写完能跑只是起点，能稳定跑完所有 trace 才算过线。
5.1 五个最容易翻车的点
第一处：序言块和结尾块的初始化顺序错。为什么漏：这几行 PUT 看起来像仪式代码，教材上也是一笔带过，很多人直接照抄却不知道每一行对应堆里的哪 4 个字节，改错一个偏移量也看不出来。怎么补：在纸上画一张 16 字节的堆头示意图，标出 padding、序言头、序言脚、结尾块的位置和heap_listp落在哪，然后手动模拟第一次 malloc 时每个宏的取值。这一步花十分钟，能省掉半天断点调试。
第二处：合并后脚部没更新，或者更新顺序反了。为什么漏：合并逻辑本身写对了，头部的值也对，只有脚部是旧值，程序照样能跑，直到某次向前合并读到一个过时的脚部，把相邻的块误判成空闲。怎么补：把所有涉及头脚同改的地方统一成固定顺序——先算 size，再写头部，最后用新头部算脚部写脚部；碰到合并前块的情况，先把旧块的脚部写掉再动头部。写完 grep 一遍所有PUT(FTRP的位置，逐个核对。
第三处：分裂时剩余部分不够最小块还硬分。为什么漏：分裂的代码里只判断了「剩余 > 0」，没判断「剩余 >= 16」，短 trace 里请求都是 16 的整数倍，剩余刚好够，测不出问题。怎么补：把条件写死成if (size - asize >= 2 * DSIZE)，并且专门构造一次请求 17 字节的用例，走一遍分裂路径。凡是能被 8 整除但不够 16 的剩余量，一律不分，整块给出去。
第四处：realloc 的拷贝长度和原地扩展判断。为什么漏：大部分 trace 里 realloc 都是缩小的，缩小走原地返回那条路，压根不触发拷贝；一旦遇到扩大的 trace，数据就悄悄截断了，而 mdriver 只在最后校验内容，报错位置和出错位置隔了很远。怎么补：给 realloc 单独写三条断言用例——扩大、缩小、扩大且后块空闲，分别验证返回指针、内容完整性和堆结构；拷贝长度那行写成(oldsize < newsize) ? oldsize : newsize，不要图省事。
第五处：对齐换算里少加或多加了头脚开销。为什么漏：asize的公式有两处取整，一处加 DSIZE 一处加 DSIZE-1，看起来像重复，其实一个都不能少，删掉任何一个在特定尺寸下都会算小一个单位，返回的指针和下一个块的头部重叠。怎么补：拿 1、7、8、9、16、17 六个尺寸手算一遍asize，确认结果都是 8 的倍数且不小于 16；再写一个循环，从 1 到 64 逐个请求、逐个检查返回指针是否 8 字节对齐、块头大小是否为 8 的倍数。
还有一处值得单独提：空闲链表删除节点时，如果删除的是链表头，要记得把类头指针或者全局头指针一起更新。这个问题典型的症状是同一个块被分配两次，两个不同的指针指向同一片内存，写起来不报错，最后校验内容时才发现互相覆盖。
5.2 利用率与吞吐量：两个指标怎么牵引实现选择
评分由两个维度合成。利用率是「峰值有效载荷字节数除以峰值堆大小」，注意分母是 mem_heapsize 的峰值，不是当前值，所以前期扩出去的堆永远不会缩回来，一开始就猛扩 CHUNKSIZE 会直接压低利用率。吞吐量是每秒完成的操作数，由 trace 里所有 malloc、free、realloc 的总耗时折算。两个指标各自归一化后按权重做加权几何平均，权重由驱动配置决定，常见做法是二者对半。
这个结构决定了优化的方向不是「两头都求极限」，而是「别让任何一头掉到地板上」。利用率被压得很低时，几何平均的惩罚比吞吐量低更重，所以宁可多花点时间做合并和最佳适配，也别放任碎片堆积。反过来，利用率已经接近上限时，再抠那一点点空间不如把查找路径缩短。
落到实现上，几个选择的影响是可以预期的：分裂阈值调大，利用率升、吞吐量略降；每次扩堆的 CHUNKSIZE 调大，吞吐量升、利用率降；分离链表的大小类划细，best fit 的命中率升，但每类链表头和遍历开销也跟着涨；realloc 支持原地扩展，两个指标同时受益，属于少见的纯赚项，值得优先做。
我的习惯是分四轮迭代：第一轮隐式链表跑通所有 trace，-V全绿；第二轮换显式链表，记录一组基线分数；第三轮上分离链表，先只分类不优化适配策略；第四轮才逐项微调 CHUNKSIZE、分裂阈值和大小类边界。每一轮都保留一份能跑的版本，任何一次改动导致分数下降就立刻回退。最怕的是一口气把三个优化全塞进去，分数掉了却不知道是哪一个拖的后腿。
5.3 用 mdriver 的 -V 和 trace 做验证
驱动程序的用法不复杂，但两个开关一定要会用。-f指定单条 trace 文件，-v输出每次操作的详情，-V打开堆一致性校验，也就是每执行一次操作就把整个堆从头扫一遍，检查块大小是否对齐、头脚是否一致、空闲链表里的块是否都在堆范围内。-V会让运行速度慢一个数量级，但它是唯一能在崩溃之前把问题揪出来的手段。
trace 文件是纯文本，每行形如「操作符 序号 大小」，操作符是 m、f、r 三种。调试时先从最短的、只有 malloc 和 free 的 trace 开始，确认基本路径没问题；再换带 realloc 的；最后才跑那些几万次操作的长 trace。顺序反了，长 trace 上任何一个早期错误都会在后面放大成一堆无效信息。
除了驱动自带的校验，自己写一个check_heap也很好用：从堆头走到结尾块，逐块核对头脚是否相等、大小是否是 8 的倍数、相邻块是否重叠；再遍历所有空闲链表，确认链表里的每个节点都在堆范围内、且它的分配位确实是 0；最后数一遍链表节点总数和全堆扫描到的空闲块数是否相等。三个检查只要有一个不过，问题范围立刻缩小到某一段。
/* 简化的堆检查骨架：扫描全堆，核对块结构 */ static void check_heap(void) { char *bp = heap_listp + WSIZE; /* 跳过序言块，指向首个真实块 */ size_t total_free = 0; while (GET_SIZE(HDRP(bp)) > 0) { /* 遇到结尾块(size=0)停 */ size_t size = GET_SIZE(HDRP(bp)); if (size % DSIZE != 0) /* 检查一：大小必须 8 字节对齐 */ fprintf(stderr, "bad size at %p\n", bp); if (GET(HDRP(bp)) != GET(FTRP(bp))) /* 检查二：头脚必须完全一致 */ fprintf(stderr, "hdr/ftr mismatch at %p\n", bp); if (!GET_ALLOC(HDRP(bp))) total_free += size; /* 累加空闲块总字节数 */ bp = NEXT_BLKP(bp); } /* 检查三：把 total_free 和空闲链表遍历出来的总量对比，不一致说明链表漏节点或多了节点 */ }这个骨架里三个检查对应三类最常见的错误源，实际用的时候可以把「大小是否越界」「是否落在 mem_heap_lo 到 mem_heap_hi 之间」也加进去。检查函数不要留在提交版本里，它会让吞吐量评分惨不忍睹，只在调试阶段打开。
6. 复习清单：用 -V 和 trace 做一次完整的查漏补缺
复习这个实验，别从代码第一行开始读，从评分结果倒推更有效率。我的做法是准备一张检查表，从上往下过一遍，任何一项不过就停下来修，修完再从头跑。这张表覆盖的是「能不能稳定拿分」，不是「写得漂不漂亮」。
| 检查项 | 怎么验 | 通过标准 |
|---|---|---|
| 堆头初始化 | 画 16 字节示意图，手算第一次 malloc 的指针 | 首个真实块前能读到已分配的序言块脚部 |
| 块大小换算 | 1 到 64 逐个请求，检查返回指针和块头 | 指针 8 字节对齐，块大小是 8 的倍数且不小于 16 |
| 四种合并情形 | 构造前后各状态组合的短 trace | 每次合并后头脚一致，块指针指向合并后的块 |
| 分裂阈值 | 请求 17、24、25 字节 | 剩余不足 16 字节时不分 |
| realloc 三条路径 | 扩大、缩小、扩大且后块空闲 | 内容完整、指针合法、堆结构未坏 |
| 空闲链表一致性 | 自写 check_heap，比对链表节点数与扫描结果 | 两者相等，且都在堆范围内 |
| 边界条件 | 连续 free 同一个块、free(NULL)、malloc(0) | 不崩、不重复入链 |
| 全部 trace | 每条 trace 单独跑一遍 -v | 单条全绿，再跑合成长 trace |
| 利用率基线 | 记录每轮迭代的 util | 不低于 0.75 这条常见的达标线 |
| 吞吐量基线 | 记录每轮迭代的 Kops | 相比上一轮不下降 |
表里最后两行是给自己留的对照。每改一次实现，就把 util 和 Kops 两个数抄在旁边，涨了记原因、跌了记怀疑点，几轮下来会得到一张很有用的因果表：CHUNKSIZE 从 4096 调到 8192 换来了多少吞吐量、付出了多少利用率，分裂阈值从 16 调到 32 又是什么结果。这张表比任何教程都贴合自己的机器和 trace 集。
复习时间紧的时候，优先级这样排：先把-V能在最短的 trace 上跑通，这一步能拦掉八成以上的结构性错误；再把四种合并情形和 realloc 三条路径各自验证一遍，这是长 trace 里最容易暴露的地方；最后才是调参数。反过来做，先追分数，往往是花了两小时调 CHUNKSIZE，结果发现根本原因是某次合并漏写了脚部，前面所有调参数据全部作废。
我当初踩得最狠的一个坑，是显式链表里删节点时没更新链表头，短 trace 一次都没触发，长 trace 跑到第七千多次才崩，报错位置在一段完全无关的 malloc 里。从那以后我每次动空闲链表相关代码，都强制先跑一遍带-V的最短 trace 加一条带 realloc 的中等 trace，两个都过了才继续往下写。这个习惯并不聪明，只是把排查成本从半天压到了五分钟。
这份笔记里的实现骨架、四类合并的写法、realloc 的三条路径和那张检查表，我都整理在了一份带详细注释的完整代码里，配合 trace 逐条对照着看，基本能一次走完从跑通到拿分的全程。希望帮到你。
本文还有配套的精品资源，点击获取
