Lecture 13: 动态内存分配：基础 (Dynamic Memory Allocation: Basic)
Lecture 13: 动态内存分配：基础 (Dynamic Memory Allocation: Basic)
讲义对应：CMU 15-213 Lecture 13 — Dynamic Memory Allocation: Basic（素材：
F25-13-malloc-basic.txt） 教材对应：CS:APP3e 第 9 章 9.9（动态内存分配） 关联 Lab：L5a Malloc Lab（checkpoint）（习题课与 bootcamp：F25-rec07_slides.txt、F25-malloc-bootcamp.txt）
13.1 概述
第 11、12 讲我们把虚拟内存讲到了页表与缺页处理，知道了进程的地址空间里有一段”运行时堆（run-time heap）”，可由 brk 系统调用伸缩。本讲回答一个随之而来的问题：这段堆由谁管理、怎样管理？ 答案是动态内存分配器（dynamic memory allocator）。我们先把 malloc/calloc/realloc/free 的接口语义与分配器必须服从的硬性约束钉死，再定义两个彼此冲突的性能目标——吞吐率（throughput）与峰值内存利用率（peak memory utilization），接着剖析两类碎片（fragmentation）；然后动手实现最经典的数据结构——隐式空闲链表（implicit free list），并用 Knuth 的边界标记（boundary tags）把合并做到 $O(1)$。本讲为 L5a Malloc Lab 的 checkpoint 提供全部理论装备；下一讲（Lecture 14）在此基础上改进吞吐率与利用率（显式空闲链表、分离空闲链表、延迟合并、footer 优化）。
13.2 核心概念与底层机制图解
13.2.1 为什么需要动态内存分配（Why Dynamic Allocation）
- 定义与目的：静态/全局变量的大小与偏移必须在编译期定死（见 Lecture 7：
.data/.bss段的大小写死在可执行文件里）；函数内的局部数组虽由栈帧在运行期建立，却受生命周期约束——函数一返回，栈帧整个消失（见 Lecture 5）。于是两类需求无法满足：① 长度编译期不可知（链表节点个数、读文件得到的内容）；② 生命周期要超出创建它的函数。动态内存分配就是为这两类需求准备的：运行期申请任意大小的内存，用多久由程序员决定，用完显式归还。 - 直观解释：把地址空间想成一栋楼：
.text/.data是设计图上画死的承重墙；栈是前台的折叠桌，人一走就收；堆是一整层毛坯仓库，你随时找管理员（分配器）要地方，走时把钥匙交还。 - 底层机制图解（进程地址空间与”the break”）：
高地址 0x7fffffffffff
+-------------------------------+
| 内核虚拟内存（用户代码不可见） |
+-------------------------------+
| 用户栈（运行时创建） %rsp 在此 |
| | |
| v 向下增长 |
| ... |
| ^ 向上增长 |
| 共享库内存映射区（如 libc） |
+-------------------------------+
| ^ |
| | <-- brk 指针("the break") 可由 sbrk 调整
+-------------------------------+ <-- heap_end（堆顶，随 sbrk 上移）
| |
| 运行时堆（heap，malloc 创建） |
| |
+-------------------------------+ <-- heap_start（堆起点，固定）
| 读/写段 .data、.bss |
+-------------------------------+
| 只读段 .init、.text、.rodata |
+-------------------------------+
| 未使用（从低地址起） |
+-------------------------------+ 0
低地址
- 与机器码/硬件的对应：
malloc系列是库函数，不是系统调用；它们最终通过brk/sbrk（或大块时mmap）向内核要内存，见 13.4。注意 CS:APP 的一个约定：每次课里的”1 个方块 = 1 个字 = 8 字节”（x86-64 LP64 下long与指针都是 8 字节），本章所有堆示意图都按这个换算。
13.2.2 malloc 包的接口语义（The malloc Package）
- 定义与目的（接口原样照录官方语义）：
| 函数 | 语义 | 失败/边界行为 |
|---|---|---|
void *malloc(size_t size) | 返回指向至少 size 字节的块的指针；在 x86-64 上按 16 字节边界对齐 | 失败返回 NULL 并置 errno |
void free(void *p) | 把 p 指向的块归还空闲池 | p 必须来自此前的 malloc/calloc/realloc |
void *calloc(size_t n, size_t size) | malloc 的版本，把块清零 | 同上 |
void *realloc(void *p, size_t size) | 改变已分配块的大小 | 可能搬移到新地址，旧内容保留 min(旧, 新) 字节 |
void *sbrk(intptr_t incr) | 分配器内部用它伸缩堆 | 不是给应用程序用的 |
- 直观解释：
malloc是”毛坯交付“——不擦内存，里面的字节是上次用剩的垃圾；calloc是”精装修交付“（清零）；free是”退钥匙“，不把内存还给操作系统，只把这块地标为可再用。 - 底层机制图解（关键陷阱）：
free只能接受分配器自己发出去的载荷指针：
堆中一个块
+--------+---------------------------+--------+
| header | payload | footer |
+--------+---------------------------+--------+
^ ^
| |
合法的 p ✗ 非法的"中部指针" p+8
(malloc 的返回值) (free 它是 UB!)
栈变量: int x; free(&x); ✗ UB!（那不是堆地址）
- 补充说明：讲义幻灯片写”
size == 0时返回NULL“。C 标准允许实现返回NULL或一个可被free的唯一指针；glibc 实测返回非NULL（本章 13.3.4 实测输出）。写代码时两种都要能正确处理——这也是 Malloc Lab 里mm_malloc(0)必须自行裁决的地方。
13.2.3 分配器的硬性约束（Constraints）
- 定义与目的：应用可以发出任意顺序的
malloc/free请求，free的参数必须是malloc过的块；分配器不知道未来的大小分布。与此同时： - 必须立即响应：不能重排（reorder）或缓冲（buffer）请求——
malloc一被调用就必须立刻返回可用内存。 - 只能用堆区域：块只能放在空闲内存里，且不能移动已分配的块（不允许压缩 compaction），因为应用程序持有裸指针，一搬移就全部失效。
- 必须满足对齐与隔离：x86-64 上返回 16 字节对齐的指针（Malloc Lab 放宽到 8 字节）；已分配块的内容分配器一律不能碰。
13.2.4 两个性能目标：吞吐率与内存利用率（Throughput vs. Utilization）
- 吞吐率：单位时间内完成的请求数。例：10 秒内完成 5,000 次
malloc与 5,000 次free→ 吞吐率 = 1,000 operations/second。 - 聚合载荷（aggregate payload） $P_k$：第 $k$ 次请求后当前所有已分配载荷之和。设请求 $R_i$ 的载荷为 $p_i$，则 $P_k=\sum_{\text{当前已分配}} p_i$。峰值聚合载荷 $\max_{i\le k}P_i$ 是序列到第 $k$ 步为止的最大值。
- 当前堆大小 $H_k$：假定堆只在分配器调用
sbrk时增长、从不收缩。 - 开销（overhead）：$O_k=\dfrac{H_k}{\max_{i\le k}P_i}-1.0$，即”没有用于程序数据的那部分堆空间的占比”。
- 峰值内存利用率（peak utilization）：
- 直观解释：吞吐率是”仓库管理员发货多快”，利用率是”仓库里有多少空间真的放了货”。两者天然冲突：要发货快就选第一个看得过去的空位（留下碎片），要放得满就得把所有空位翻个底朝天（慢）。Malloc Lab 用一个加权性能指数把它们捆在一起：$P=wU+(1-w)\min\left(1,\dfrac{T}{T_{libc}}\right)$，默认 $w=0.6$，$T_{libc}=600$ Kops/s——利用率权重更高，但也不能靠”极慢但极省内存”取胜。
- 基准示例（
syn-array-short）：讲义给出的 trace 共 20 步（a=allocate，f=free），分配总量峰值出现在第 11 步：a 7 33856之后 Allocated $=90036$，Peak $=90036$；第 20 步全部释放后 Allocated $=0$，Peak 仍是 $90036$。因此峰值利用率的分母就是这 90036。
13.2.5 碎片（Fragmentation）
- 内部碎片（internal fragmentation）：一个块内，块大小大于载荷请求的部分。
三个来源：① 维护堆数据结构的开销（头部/脚部）；② 为对齐而填充（padding）；③ 显式策略决定（例如”为了不产生太小的碎块，把一个大块整个给你”）。它只取决于过去请求的模式，所以容易度量。讲义给出的该基准上”分配器数据 + 对齐填充”的开销约为 1.5%，并强调这是实践中达不到的（因为不允许移动已分配块）。
- 外部碎片（external fragmentation）：空闲内存总量足够，但没有一个连续空闲块大到能满足当前请求。它取决于未来请求的模式，因此难以度量，只能估计。讲义基准上”最佳适配（best fit）”策略的总开销是 8.3%。
- 直观解释：内部碎片像”租了 10 平米仓库，实际只放得下 8 平米的货”；外部碎片像”停车场总共还剩 5 个空位，但每个都被夹在两辆车之间，5 米长的货车一辆都进不去”。
- 底层机制图解（外部碎片：总量够、单块不够）：
p1=malloc(32) p2=malloc(40) p3=malloc(48)
+----+ +----+ +----+ +--------+
| p1 | | p2 | | p3 | | 空闲 |
+----+ +----+ +----+ +--------+
free(p2)
+----+ +----+ +----+ +--------+
| p1 | |空闲 | | p3 | | 空闲 |
+----+ +----+ +----+ +--------+
p4 = malloc(64) --> ✗ 失败：
空闲合计 = 40 + 一大块，但 p2 那块只有 40 字节，
不满足 64 字节的**单个连续**要求。
- 与机器码/硬件的对应：碎片是纯软件现象，与硬件无关；但它直接决定缺页次数（堆越大、触碰的页越多，见 Lecture 11/12 的按需分页），因此是系统性能问题而非代码风格问题。
13.2.6 隐式空闲链表与块格式（Implicit Free List）
- 定义与目的：为了知道”给一个指针该释放多少内存”“下一个块在哪”“这块空不空”，每个块前面放一个头部（header），记录块大小与分配标志。头部+大小串起来就成了一条隐式空闲链表（implicit free list）：不需要显式 next/prev 指针，靠”长度”隐式串联所有块。
- 标准技巧：与其用两个字分别存大小和状态（浪费），不如利用对齐——块大小是 16 的倍数时低 4 位恒为 0，于是把最低位当作
a（allocated）标志；读大小时必须屏蔽它（header & ~0xf）。 - 块格式图解（对齐的位域划分，1 word = 8 字节）：
一个 head word（8 字节 = 64 位）
63 4 3 2 1 0
+-----------------------------------------------------------+--+--+--+--+
| Size (块总大小, 16 的倍数) |0 |0 |0 | a|
+-----------------------------------------------------------+--+--+--+--+
a = 1: 已分配块 a = 0: 空闲块
Size: 含头部与填充的总块大小（字节）
已分配块: [ Size | a ] [ payload ................. ] [ 可选 padding ]
空闲块 : [ Size | a ] [ 空闲（可放 next/prev 指针） ] [ 可选 padding ]
^8 字节
双字对齐(double-word aligned)：
heap 起点 16 字节对齐 => 每个块的头部地址都是 8 (mod 16)，
因此 payload 起点必为 16 的倍数。注意：
**头部本身不在对齐位置，payload 才对齐。**
- 与机器码/硬件的对应（真实的
gcc -O2 -S输出，读头部只需一条and）：
get_size: get_alloc:
movq (%rdi), %rax movq (%rdi), %rax
andq $-16, %rax andl $1, %eax
ret ret
init_header(b, size, alloc): find_next(b): /* b + get_size(b) */
orq %rdx, %rsi movq (%rdi), %rax
movq %rsi, (%rdi) andq $-16, %rax
ret addq %rdi, %rax
ret
注意 andq $-16 就是 & ~0xf——一条指令同时完成”提取大小”与”屏蔽标志位”。
- 讲义给出的数据结构和访问函数（
offsetof与零长数组是关键技巧）：
typedef uint64_t word_t;
typedef struct block
{
word_t header;
unsigned char payload[0]; /* GNU C 零长数组: sizeof(payload) == 0 */
} block_t;
/* 从块指针得到载荷指针 */
return (void *) (block->payload);
/* 从载荷指针反推块指针（offsetof 给出成员偏移） */
return (block_t *) ((unsigned char *) bp - offsetof(block_t, payload));
/* 读标志位 / 读大小 / 写头部 */
return header & 0x1; /* get_alloc */
return header & ~0xfL; /* get_size */
block->header = size | alloc; /* write_header */
补充说明：payload[0] 是 GCC 扩展（C99 的正式写法是柔性数组成员 payload[]）。它的价值在于”结构体固定部分只有头部，载荷长度随块变化”——这正是分配器需要的类型双关技巧（见 F25-rec07_slides.txt 与 bootcamp 的”Zero-Length Arrays”）。
13.2.7 隐式空闲链表的整体布局（ASCII 图）
讲义给出的标准示例，头部标注为”以字为单位的大小 / 分配位“：
heap_start（双字对齐）
+-------------+------------------------------------------------------------+
| 16/0 | 32/1 | 32/1 | 64/0 | 8/1 |
| 空闲块(2字) | 已分配(4字) | 已分配(4字) | 空闲块(8字) | 结尾块(1字) |
+-------------+-------------+-------------+-------------+----------------+
^ heap_end
序言/填充块
规则：
* 已分配块：涂阴影（shaded）；空闲块：不涂。
* 头部写在"非对齐位置"（8 mod 16），所以 payload 才是 16 字节对齐的。
* 走链表：next = (char *)block + get_size(block) ← 唯一的"指针"
* 结尾块 8/1（size=8, allocated）充当哨兵，使遍历不必判断越界。
- 直观解释：隐式空闲链表就像一本只有页码、没有目录的书。要找某段内容（某个大小的空闲块），你必须从第 1 页逐页翻——这决定了它的分配操作是线性时间。
13.2.8 边界标记与常量时间的合并（Boundary Tags）
- 定义与目的：最简单的
free只需清掉分配位，但这会导致假碎片（false fragmentation）：明明有两块相邻的空闲内存，分配器却看不到它们是连续的。解决办法是合并（coalescing）。与后块合并很容易（current + size）；与前块合并却有个难题：怎么知道前一个块的起点和它是否空闲？ 顺着链表走可以从头找到它，但那是 $O(n)$ 的。Knuth 的边界标记（boundary tags）技巧【Knuth73】：在每个块的末尾再复制一份头部信息（脚部 footer）。于是从当前块的头部往回退 8 字节，正好落在前一个块的脚部上，一次性读出前块的大小与状态——合并变成 $O(1)$。 - 为什么能 $O(1)$ 找到前驱（关键 ASCII 图）：
... 内存里是连续排布的这一段 ...
地址: 低 <----------------------------------------------> 高
+----------+----------------+----------+ +----------+----------------+----------+
| 前块 head | 前块 payload | 前块 foot | | 本块 head | 本块 payload | 本块 foot |
| size=m | | size=m | | size=n | | size=n |
+----------+----------------+----------+ +----------+----------------+----------+
^ ^
| <---- 回退 8 字节 --- |
+--------------------------------------+ |
| |
本块 head 地址 = 前块 foot 地址 + 8 ------------+ |
=> prev_head = (char*)head - 8 - get_size(foot)
^
从本块 head 回退 8 字节即读到前块 foot
- 代价：每个块多花 8 字节，即内部碎片增加。这正是 bootcamp 里”Eliminate footers in allocated blocks“优化的动机：脚部只在需要被后一个块回溯时才需要，而只有空闲块才需要被合并，所以 13.2.10 会给出只用 2 个标志位（
b = 前块是否已分配）省掉已分配块脚部的做法。 - 替代方案：延迟合并（deferred coalescing）——
free时只标记不合并；等到malloc找不到合适块时再一次性扫描堆、合并所有相邻空闲块。它把合并成本从”每次free“挪到”偶尔扫描”，代价是两次合并之间可能浪费内存。
13.2.9 合并的四种情况（Constant Time Coalescing）
设当前被释放的块大小为 $n$，前块 $m_1$、后块 $m_2$（记 1=已分配，0=空闲）：
情况 1: 前=已分配, 后=已分配 情况 2: 前=已分配, 后=空闲
+----+----+----+ +----+----+----+
| m1 | n | m2 | | m1 | n | m2 |
| 1 |1 | 1 | | 1 |1 | 0 |
+----+----+----+ +----+----+----+
=> 只清 n 的分配位 => n 与 m2 合并为 n+m2，状态=0
情况 3: 前=空闲, 后=已分配 情况 4: 前=空闲, 后=空闲
+----+----+----+ +----+----+----+
| m1 | n | m2 | | m1 | n | m2 |
| 0 |1 | 1 | | 0 |1 | 0 |
+----+----+----+ +----+----+----+
=> n 与 m1 合并为 n+m1，状态=0 => 三者合并为 n+m1+m2，状态=0
- 伪代码（与讲义一致，注意情况 4 中要事先保存后块指针）：
coalesce(bp):
prev_alloc = footer(bp - 8) 的分配位 # 回退 8 字节读前块脚部
next = bp + size(bp) # ★ 必须在 bp 被改写前算出来
next_alloc = header(next) 的分配位
size = size(bp)
if prev_alloc and next_alloc: # 情况 1
pass
elif prev_alloc and not next_alloc: # 情况 2
size += size(next)
elif not prev_alloc and next_alloc: # 情况 3
bp = bp - size(footer(bp - 8)) # 前块头部
size += size(bp)
else: # 情况 4
bp = bp - size(footer(bp - 8))
size += size(bp) + size(next) # next 仍是"原来的后块"
write_header(bp, size, FREE)
write_footer(bp, size, FREE)
return bp
- 与机器码/硬件的对应：整个过程只有几次
movq+and+add，没有任何循环——这就是”常量时间合并”的含义；代价是每个块那 8 字节脚部，以及”每块至少 16 字节（head+foot）”的最小块大小。 - ⚠️ 真实踩坑（本章代码实测发现）：情况 4 里如果先执行
bp = prev_block(bp)再去算next_block(bp)，next_block就会以前块为基准走，得到一个完全错误的地址，进而写出损坏的脚部、让堆检查断言失败。这是实现coalesce时最容易犯的 bug 之一，务必先把next存成局部变量。
13.2.10 堆结构与序言/结尾块（Prologue & Epilogue）
- 问题：
coalesce要读”前块的脚部”和”后块的头部”，但堆的第一个块前面没有脚部、最后一个块后面没有头部，会越界读写。 - 解法：在
mm_init里放置两个哨兵：
heap_start（16 字节对齐）
+----------------+----------------+----------+ +-------------+----------------+
| 填充 8B | 序言头 8B | 序言脚 8B | | 块0 ... | 结尾头 |
| （对齐用） | size=16, a=1 | size=16,1 | | | size=0, a=1 |
+----------------+----------------+----------+ +-------------+----------------+
^ ^ ^
| | |
序言块(已分配,永远不释放) heap_listp 指向此处 遍历终止哨兵
=> 释放第一个真实块时, "前块" 读到的是序言脚部(已分配) -> 情况 1 或 2
=> 结尾头 size=0、alloc=1, 使 find_fit 的循环条件
(get_size(header) > 0) 自然终止, 且释放最后一个块时 "后块" 是已分配
- 直观解释：序言块是起跑线前的挡板，结尾头是跑道尽头的墙——
coalesce里那两次看似越界的访问因此都读到”合法的、标记为已分配的块”，四种情况的分支不需要任何if (bp == heap_start)之类的特判。bootcamp 把它表述为”载荷必须 16 字节对齐，但载荷大小不必是 16 的倍数、块大小必须是；所有malloc出来的东西都要落在序言与结尾之间”。 - 讲义里的等价做法：幻灯片画的是”Dummy footer before first header（标记为已分配，防止释放第一个块时误合并）”+”Dummy header after last footer（防止释放最后一个块时误合并）“，与序言/结尾是同一件事的两种画法。
13.3 代码示例与底层机制分析
13.3.1 完整可运行的隐式空闲链表分配器（带边界标记与 $O(1)$ 合并）
代码 (C)：堆用一块 16 字节对齐的静态数组模拟（heap_end 扮演 brk），四个接口与 mm.c 同名，另加一个 dump_heap 打印每块大小与空闲状态并断言 header == footer。
/* c13_alloc_demo.c 编译: gcc -g -Wall -std=c11 c13_alloc_demo.c -o c13_alloc_demo */
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stddef.h>
#include <assert.h>
typedef uint64_t word_t;
static const size_t WSIZE = sizeof(word_t); /* 8 : 一个字 */
static const size_t DSIZE = 2 * sizeof(word_t); /* 16 : 头部+脚部 */
#define HEAP_CAP (1u << 16)
static _Alignas(16) unsigned char heap_area[HEAP_CAP];
static void *heap_start = heap_area; /* 堆起点(16 对齐) */
static void *heap_end = heap_area; /* 当前 brk */
/* ---------------- 头部 / 脚部 访问 ---------------- */
static size_t get_size(void *b) { return *(word_t *)b & ~0xFUL; }
static size_t get_alloc(void *b) { return *(word_t *)b & 0x1UL; }
static void write_tag(void *b, size_t size, size_t alloc)
{
*(word_t *)b = (word_t)(size | alloc);
}
static void *next_block(void *b) { return (char *)b + get_size(b); }
/* 前一个块的头部: 从当前头部回退 8 字节正好读到前一个块的脚部 */
static void *prev_block(void *b) { return (char *)b - get_size((char *)b - WSIZE); }
static void *header_of(void *payload) { return (char *)payload - WSIZE; }
static void *payload_of(void *b) { return (char *)b + WSIZE; }
/* ---------------- 打印整个堆 ---------------- */
static void dump_heap(const char *tag)
{
printf("---- %s ----\n", tag);
printf(" %-4s %-12s %-6s %-7s %s\n", "blk", "hdr_addr", "size", "alloc", "note");
int i = 0;
for (void *b = (char *)heap_start + WSIZE; b != heap_end; b = next_block(b), i++) {
size_t sz = get_size(b), a = get_alloc(b);
printf(" #%-3d %-12p %-6zu %-7s %s\n", i, b, sz, a ? "1" : "0",
a ? "allocated" : "free(含脚部)");
if (!a) /* 堆不变量: 空闲块 header == footer */
assert(*(word_t *)((char *)b + sz - WSIZE) == *(word_t *)b);
}
printf("\n");
}
/* ---------------- 立即合并: 四种情况，都是 O(1) ---------------- */
static void *coalesce(void *b)
{
size_t prev_alloc = get_alloc((char *)b - WSIZE); /* 前一个块的脚部 */
void *nextb = next_block(b); /* ★ 先记下后块! */
size_t next_alloc = get_alloc(nextb);
size_t size = get_size(b);
if (prev_alloc && next_alloc) { /* 情况 1 */
printf(" [coalesce] 情况1 前后都分配 -> 仅清标志, size=%zu\n", size);
} else if (prev_alloc && !next_alloc) { /* 情况 2 */
size += get_size(nextb);
printf(" [coalesce] 情况2 只有后块空闲 -> 合并得 size=%zu\n", size);
} else if (!prev_alloc && next_alloc) { /* 情况 3 */
b = prev_block(b);
size += get_size(b);
printf(" [coalesce] 情况3 只有前块空闲 -> 合并得 size=%zu\n", size);
} else { /* 情况 4 */
b = prev_block(b);
size += get_size(b) + get_size(nextb);
printf(" [coalesce] 情况4 前后都空闲 -> 三者合并得 size=%zu\n", size);
}
write_tag(b, size, 0);
write_tag((char *)b + size - WSIZE, size, 0); /* 新脚部 */
return b;
}
/* ---------------- 分割 ---------------- */
static void split_block(void *b, size_t asize)
{
size_t bsize = get_size(b);
if (bsize - asize >= 2 * DSIZE) { /* 余下部分至少能装一个最小块 */
write_tag(b, asize, 1);
write_tag((char *)b + asize - WSIZE, asize, 1);
void *rest = (char *)b + asize;
write_tag(rest, bsize - asize, 0);
write_tag((char *)rest + (bsize - asize) - WSIZE, bsize - asize, 0);
printf(" [split] %zu -> 分配 %zu + 空闲 %zu\n", bsize, asize, bsize - asize);
} else { /* 整块给出，产生内部碎片 */
write_tag(b, bsize, 1);
write_tag((char *)b + bsize - WSIZE, bsize, 1);
printf(" [split] 剩余 %zu < 最小块 %zu, 整块分配(内部碎片 %zu 字节)\n",
bsize - asize, 2 * DSIZE, bsize - asize);
}
}
/* ---------------- 首次适配 ---------------- */
static void *find_fit(size_t asize)
{
for (void *b = (char *)heap_start + WSIZE; b != heap_end; b = next_block(b)) {
if (!get_alloc(b) && asize <= get_size(b)) {
printf(" [find_fit] 首次适配命中 %p (size=%zu >= %zu)\n", b, get_size(b), asize);
return b;
}
}
printf(" [find_fit] 遍历整个隐式链表, 无可用空闲块\n");
return NULL;
}
/* ---------------- 扩展堆 (等价于 mem_sbrk) ---------------- */
static void *extend_heap(size_t bytes)
{
if ((size_t)((char *)heap_end - (char *)heap_start) + bytes > HEAP_CAP) return NULL;
void *b = heap_end;
write_tag(b, bytes, 0);
write_tag((char *)b + bytes - WSIZE, bytes, 0);
heap_end = (char *)heap_end + bytes;
write_tag(heap_end, 8, 1); /* 新的结尾头部(8/1) */
printf(" [extend] 扩堆 %zu 字节, 新空闲块 @ %p\n", bytes, b);
return b;
}
/* ---------------- 四个对外接口 ---------------- */
static int mm_init(void)
{
heap_end = heap_start;
write_tag((char *)heap_start, 8, 1); /* 序言脚部: 8/1 */
heap_end = (char *)heap_start + WSIZE;
write_tag(heap_end, 8, 1); /* 结尾头部: 8/1 */
return 0;
}
static void *mm_malloc(size_t size)
{
if (size == 0) size = 1;
size_t asize = (size + DSIZE + 15) & ~(size_t)0xF; /* 头部+脚部, 向上取整到16 */
printf(" [malloc] 请求 %zu 字节 -> asize=%zu\n", size, asize);
void *b = find_fit(asize);
if (b == NULL) {
size_t need = asize > 4096 ? asize : 4096; /* 一次多要一点 */
b = extend_heap((need + 15) & ~(size_t)0xF);
if (b == NULL) return NULL;
}
split_block(b, asize);
return payload_of(b);
}
static void mm_free(void *p)
{
if (p == NULL) return;
void *b = header_of(p);
size_t size = get_size(b);
printf(" [free] payload %p -> block %p, size=%zu\n", p, b, size);
write_tag(b, size, 0); /* 1. 清分配位 */
write_tag((char *)b + size - WSIZE, size, 0);
coalesce(b); /* 2. 立即合并 */
}
最后的 main 正是本章的验证程序：它按顺序演示四种合并情况、malloc(1) 的内部碎片与 realloc 的搬移，每步之后打印整条链表。
static void *mm_realloc(void *p, size_t size)
{
if (p == NULL) return mm_malloc(size);
if (size == 0) { mm_free(p); return NULL; }
void *nb = mm_malloc(size);
if (nb == NULL) return NULL;
size_t old = get_size(header_of(p)) - DSIZE;
memcpy(nb, p, old < size ? old : size);
mm_free(p);
return nb;
}
/* ---------------- 内部碎片与利用率统计 ---------------- */
static size_t req_now = 0, req_peak = 0;
static void note_alloc(size_t s) { req_now += s; if (req_now > req_peak) req_peak = req_now; }
static void note_free(size_t s) { req_now -= s; }
static void report(void)
{
size_t heap_used = 0, payload = 0;
for (void *b = (char *)heap_start + WSIZE; b != heap_end; b = next_block(b)) {
heap_used += get_size(b);
if (get_alloc(b)) payload += get_size(b) - DSIZE;
}
printf(" 堆已用 %zu 字节; 已分配块的载荷(可用)合计 %zu 字节\n", heap_used, payload);
printf(" 聚合利用率 U_k = 已分配载荷/堆大小 = %zu/%zu = %.3f\n",
payload, heap_used, (double)payload / (double)heap_used);
printf(" 峰值利用率 = 峰值载荷/堆大小 = %zu/%zu = %.3f\n",
req_peak, heap_used, (double)req_peak / (double)heap_used);
printf(" 内部碎片合计 = 载荷 %zu - 当前请求 %zu = %zu 字节\n",
payload, req_now, payload - req_now);
}
int main(void)
{
setvbuf(stdout, NULL, _IONBF, 0);
printf("=== 隐式空闲链表分配器演示 (word=8B, 块大小为 16B 的倍数) ===\n\n");
mm_init();
printf("[1] 连续四次 malloc(32), 块大小 = (32+16) 向上取整 = 48\n");
void *p1 = mm_malloc(32); note_alloc(32);
void *p2 = mm_malloc(32); note_alloc(32);
void *p3 = mm_malloc(32); note_alloc(32);
void *p4 = mm_malloc(32); note_alloc(32);
printf(" p1=%p p2=%p p3=%p p4=%p\n\n", p1, p2, p3, p4);
dump_heap("四次 malloc 之后");
printf("[2] free(p2): 前(p1)后(p3)都分配 -> 情况 1\n");
mm_free(p2); note_free(32);
dump_heap("free(p2) 之后");
printf("[3] free(p1): 前是序言块(已分配), 后块(p2)空闲 -> 情况 2\n");
mm_free(p1); note_free(32);
dump_heap("free(p1) 之后: p1+p2 合成 96B 空闲块?");
printf("[4] free(p3): 前块(96B 空闲), 后块(p4)已分配 -> 情况 3\n");
mm_free(p3); note_free(32);
dump_heap("free(p3) 之后: 合成 144B 空闲块?");
printf("[5] free(p4): 前块空闲 + 后块(扩堆余量)空闲 -> 情况 4\n");
mm_free(p4); note_free(32);
dump_heap("free(p4) 之后: 与堆尾空闲块合并");
printf("[6] p5 = malloc(100): asize=128, 首次适配命中该空闲块并分割\n");
void *p5 = mm_malloc(100); note_alloc(100);
printf(" p5=%p\n\n", p5);
dump_heap("malloc(100) 之后");
printf("[7] 演示内部碎片: malloc(1) 得到 32B 的块\n");
void *p6 = mm_malloc(1); note_alloc(1);
printf(" p6=%p (请求 1 字节, 块 32 字节 -> 载荷 16, 内部碎片 15)\n\n", p6);
dump_heap("malloc(1) 之后");
printf("[8] 内容保留验证: 先用已知模式填满 p5 的 100 字节\n");
static unsigned char snapshot[100];
memset(p5, 0xA5, 100);
memcpy(snapshot, p5, 100);
printf(" p7 = mm_realloc(p5, 200): 需要 asize=224 > 128, 必须搬移\n");
void *p7 = mm_realloc(p5, 200);
if (p7) { note_alloc(200); note_free(100); }
printf(" p5=%p -> p7=%p (%s)\n", p5, p7, p5 == p7 ? "原地" : "已搬移");
printf(" 前 100 字节内容是否逐字节保留: %s\n\n",
memcmp(p7, snapshot, 100) == 0 ? "是" : "否");
dump_heap("realloc 之后");
mm_free(p6); note_free(1);
mm_free(p7); note_free(200);
printf("[9] 释放 p6/p7 后做统计\n");
report();
printf("\n=== 所有 dump_heap 断言通过: 每个空闲块 header == footer ===\n");
return 0;
}
【代码做什么？】
mm_init在堆起始处写一个8/1的序言脚部，再写8/1的结尾头部，此时堆里没有任何可用空闲块。- 第一次
mm_malloc(32)：asize = (32+16+15) & ~0xF = 48；find_fit扫不到空闲块 →extend_heap(4096)造出 4096 字节空闲块 →split_block切成”48 已分配 + 4048 空闲”。 - 后续
malloc直接命中那个大空闲块继续切分：首次适配总命中最靠前的空闲块，所以每次切下的位置紧跟前一块之后。 mm_free(p)：把该块头部与脚部都写成size \| 0，然后coalesce走四种情况之一，最后统一写新头部与新脚部。dump_heap顺序遍历所有块，打印size与alloc，并断言每个空闲块的头部与脚部完全一致。
【底层机制透视】
asize的计算是本讲的”块大小公式”：asize = (size + DSIZE + 15) & ~0xF。本设计里已分配块也保留脚部，头部+脚部即 16 字节固定开销，再向上取整到 16 的倍数；公式同时保证了 16 字节对齐（块大小是 16 的倍数，且所有块起点都是 16 的倍数）。prev_block是整章的魔法所在：(char *)b - get_size((char *)b - WSIZE)。它先读b-8处的脚部得到前块大小，再用这个大小回退到前块头部——这就是”边界标记让前驱在 $O(1)$ 内可找”的字面实现。- 为什么一个
for循环就能走完整个堆：每个块自带长度，隐式链表的”指针”就是长度本身。
【内存布局 / 数据结构图解】（首次适配切分三次之后，真实地址来自 13.3.3 的实测输出）：
heap_area (0x4050a8 起, 假设)
+--------------+--------------+--------------+--------------+--------------+----------+
| 序言脚 8/1 | #0: 48/1 | #1: 48/1 | #2: 48/1 | #3: 48/1 | 3904/0 |
| heap_start | hdr@0x4050a8 | hdr@0x4050d8 | hdr@0x405108 | hdr@0x405138 | hdr@ ... |
+--------------+--------------+--------------+--------------+--------------+----------+
^ ^ ^
| payload p1=0x4050b0 (16 对齐!) 堆尾空闲块
序言
每个块内部（以 #1 为例, 48 字节）:
+----------+--------------------------+----------+
| 48 | 1 | payload 32 字节 | 48 | 1 | <- 已分配块也有脚部
+----------+--------------------------+----------+
0x4050d8 0x4050e0 0x405100 0x405108
空闲块 #4（3904 字节）:
+----------+--------------------------------------+----------+
| 3904 | 0 | 空闲（可放 next/prev 指针） | 3904 | 0 |
+----------+--------------------------------------+----------+
0x405168 ... 0x4051a8
【与汇编 / 硬件的对应】：见 13.2.6 的 gcc -O2 -S 片段——get_size/get_alloc/find_next 各编译成 2–3 条指令，write_header 是 orq+movq。整个分配器里没有任何系统调用，唯一的”硬件交互”是写入堆内存引起的缺页（若该页尚未映射，由 Lecture 12 的缺页处理程序换入）。
【实测验证】：13.3.3 给出真实编译运行输出。
13.3.2 mm.c 风格的伪代码与真实片段（mm_init / extend_heap / coalesce / mm_free）
下面是 Malloc Lab 里真正要写的东西的骨架。与 13.3.1 的唯一区别是：用 mem_sbrk 扩展堆，并且用结尾头 size == 0 作为遍历终止条件（不要去和 brk 比较地址！）。
typedef unsigned long word_t;
#define WSIZE 8
#define DSIZE 16
#define CHUNKSIZE (1 << 12)
#define PACK(size, alloc) ((size) | (alloc))
#define GET(p) (*(word_t *)(p))
#define PUT(p, val) (*(word_t *)(p) = (word_t)(val))
#define GET_SIZE(p) (GET(p) & ~0xFUL)
#define GET_ALLOC(p) (GET(p) & 0x1UL)
#define HDRP(bp) ((char *)(bp) - WSIZE)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE((char *)(bp) - DSIZE))
static char *heap_listp; /* 指向序言块的"载荷"（即序言脚部） */
/* 1) 初始化：填充 + 序言头 + 序言脚 + 结尾头，然后扩一次堆 */
int mm_init(void)
{
if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1) return -1;
PUT(heap_listp, 0); /* 对齐填充 */
PUT(heap_listp + WSIZE, PACK(DSIZE, 1)); /* 序言头部 */
PUT(heap_listp + 2 * WSIZE, PACK(DSIZE, 1)); /* 序言脚部 */
PUT(heap_listp + 3 * WSIZE, PACK(0, 1)); /* 结尾头部 */
heap_listp += DSIZE; /* 指向序言载荷 */
if (extend_heap(CHUNKSIZE / WSIZE) == NULL) return -1;
return 0;
}
/* 2) 扩堆：用 mem_sbrk 拿 words 个字，造一个新空闲块并合并 */
static void *extend_heap(size_t words)
{
char *bp;
size_t size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE; /* 16 的倍数 */
if ((long)(bp = mem_sbrk((int)size)) == -1) return NULL;
PUT(HDRP(bp), PACK(size, 0)); /* 覆盖旧结尾头 -> 新空闲块头 */
PUT(FTRP(bp), PACK(size, 0)); /* 新空闲块脚部 */
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /* 新的结尾头 */
return coalesce(bp); /* 与前面的空闲块合并 */
}
/* 3) 合并：四种情况，O(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) { /* 情况 1: 不合并 */
} else if (prev_alloc && !next_alloc) { /* 情况 2: 与后块合并 */
size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
} else if (!prev_alloc && next_alloc) { /* 情况 3: 与前块合并 */
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 { /* 情况 4: 前后都合并 */
size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(HDRP(NEXT_BLKP(bp)));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
bp = PREV_BLKP(bp);
}
return bp;
}
/* 4) 释放：清两个标志位 + 立即合并 */
void mm_free(void *bp)
{
size_t size;
if (bp == NULL) return; /* free(NULL) 必须是空操作 */
size = GET_SIZE(HDRP(bp));
PUT(HDRP(bp), PACK(size, 0)); /* 1. 清分配位 */
PUT(FTRP(bp), PACK(size, 0)); /* 脚部同步 */
coalesce(bp); /* 2. 立即合并 */
}
/* 5) 首次适配：用"结尾头 size == 0"终止遍历 */
static void *find_fit(size_t asize)
{
char *bp;
for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp))
if (!GET_ALLOC(HDRP(bp)) && asize <= GET_SIZE(HDRP(bp))) return bp;
return NULL;
}
【代码做什么？】 这五个函数构成了 checkpoint 的”最小正确骨架”：mm_init 铺好哨兵、extend_heap 用 mem_sbrk 加内存并顺手合并、find_fit 线性搜索、place 分割、mm_free 清标志后合并。
【底层机制透视】 两个必须记住的细节：
mem_sbrk而不是sbrk：lab 的memlib.c用一块 20 MB 的malloc区域模拟堆，并把”学生的分配器”与”libc 的 malloc”隔离开。直接用sbrk会和 libc 自己的堆管理打架。另外mem_sbrk只接受正数（incr < 0直接报错返回-1）——所以 Malloc Lab 里堆不能收缩。- 遍历终止条件是结尾头，不是地址比较：
extend_heap每次都会在新堆顶写一个size=0, alloc=1的结尾头，find_fit靠GET_SIZE(HDRP(bp)) > 0停下。若改成”bp != brk“之类的地址比较，一旦你自己维护的brk变量与mem_sbrk的实际返回值不同步（极易发生），就会走飞并死循环。
13.3.3 实测输出：合并全过程与利用率统计
编译与运行命令（真实执行）：
$ gcc -g -Wall -std=c11 c13_alloc_demo.c -o c13_alloc_demo && ./c13_alloc_demo
真实输出（节选，含四次 malloc 后的堆快照、四种合并情况、malloc(1) 的内部碎片、realloc 搬移、利用率统计）：
[1] 连续四次 malloc(32), 块大小 = (32+16) 向上取整 = 48
[malloc] 请求 32 字节 -> asize=48
[find_fit] 遍历整个隐式链表, 无可用空闲块
[extend] 扩堆 4096 字节, 新空闲块 @ 0x4050a8
[split] 4096 -> 分配 48 + 空闲 4048
[malloc] 请求 32 字节 -> asize=48
[find_fit] 首次适配命中 0x4050d8 (size=4048 >= 48)
[split] 4048 -> 分配 48 + 空闲 4000
... (第三、四次类似)
p1=0x4050b0 p2=0x4050e0 p3=0x405110 p4=0x405140
---- 四次 malloc 之后 ----
blk hdr_addr size alloc note
#0 0x4050a8 48 1 allocated
#1 0x4050d8 48 1 allocated
#2 0x405108 48 1 allocated
#3 0x405138 48 1 allocated
#4 0x405168 3904 0 free(含脚部)
[2] free(p2): 前(p1)后(p3)都分配 -> 情况 1
[coalesce] 情况1 前后都分配 -> 仅清标志, size=48
[3] free(p1): 前是序言块(已分配), 后块(p2)空闲 -> 情况 2
[coalesce] 情况2 只有后块空闲 -> 合并得 size=96
---- free(p1) 之后: p1+p2 合成 96B 空闲块? ----
#0 0x4050a8 96 0 free(含脚部)
#1 0x405108 48 1 allocated
#2 0x405138 48 1 allocated
#3 0x405168 3904 0 free(含脚部)
[4] free(p3): 前块(96B 空闲), 后块(p4)已分配 -> 情况 3
[coalesce] 情况3 只有前块空闲 -> 合并得 size=144
---- free(p3) 之后: 合成 144B 空闲块? ----
#0 0x4050a8 144 0 free(含脚部)
[5] free(p4): 前块空闲 + 后块(扩堆余量)空闲 -> 情况 4
[coalesce] 情况4 前后都空闲 -> 三者合并得 size=4096
---- free(p4) 之后: 与堆尾空闲块合并 ----
#0 0x4050a8 4096 0 free(含脚部) <-- 整个堆合并回一块!
[6] p5 = malloc(100): asize=128, 首次适配命中该空闲块并分割
[split] 4096 -> 分配 128 + 空闲 3968
p5=0x4050b0
[7] 演示内部碎片: malloc(1) 得到 32B 的块
[malloc] 请求 1 字节 -> asize=32
p6=0x405130 (请求 1 字节, 块 32 字节 -> 载荷 16, 内部碎片 15)
[8] 内容保留验证: 先用已知模式填满 p5 的 100 字节
p7 = mm_realloc(p5, 200): 需要 asize=224 > 128, 必须搬移
[malloc] 请求 200 字节 -> asize=224
[split] 3936 -> 分配 224 + 空闲 3712
[free] payload 0x4050b0 -> block 0x4050a8, size=128
p5=0x4050b0 -> p7=0x405150 (已搬移)
前 100 字节内容是否逐字节保留: 是
[9] 释放 p6/p7 后做统计
堆已用 4096 字节; 已分配块的载荷(可用)合计 0 字节
聚合利用率 U_k = 已分配载荷/堆大小 = 0/4096 = 0.000
峰值利用率 = 峰值载荷/堆大小 = 301/4096 = 0.073
内部碎片合计 = 载荷 0 - 当前请求 0 = 0 字节
=== 所有 dump_heap 断言通过: 每个空闲块 header == footer ===
从输出里能读出的三件事：
- 四种合并情况各被真实触发了一次（步骤 2/3/4/5），且步骤 5 把整个堆合并回一个 4096 字节的空闲块——这证明边界标记的 $O(1)$ 双向合并正确。
malloc(1)得到 32 字节的块，载荷只有 16 字节可用 → 内部碎片 $=16-1=15$ 字节。这是”块大小公式 + 最小块约束”的必然结果，也是 Malloc Lab 里malloc小对象时利用率上不去的主因。realloc会搬移：p5=0x4050b0 → p7=0x405150，但前 100 字节被逐字节保留（memcmp验证为”是”）。注意输出里[coalesce] 情况3 只有前块空闲出现在最后释放p6时——搬移后留下的 128 字节空洞被后续free的合并吃掉了，这正是边界标记带来的”空洞可回收”能力。
13.3.4 mm.c 风格实现在真实 memlib.c 上的运行结果
把 13.3.2 的代码配上 lab handout 的 memlib.c 真正编译运行（注意 memlib.c 里用了 getpagesize()，需要 -D_GNU_SOURCE）：
$ gcc -g -Wall -std=c11 -D_GNU_SOURCE c13_mm_impl.c memlib.c -o c13_mm && ./c13_mm
真实输出：
mm_init: 堆大小 = 4128 字节
块 0 @ 0x7ff05b7ff020 size=16 alloc=1 <-- 序言块
块 1 @ 0x7ff05b7ff030 size=4096 alloc=0 <-- extend_heap 造的空闲块
=> 2 个块, 其中 1 个空闲; 结尾头 size=0 alloc=1
四次 mm_malloc(32):
p[0] = 0x7ff05b7ff030 p[1] = 0x7ff05b7ff060
p[2] = 0x7ff05b7ff090 p[3] = 0x7ff05b7ff0c0
块 1 @ 0x7ff05b7ff030 size=48 alloc=1
块 2 @ 0x7ff05b7ff060 size=48 alloc=1
块 3 @ 0x7ff05b7ff090 size=48 alloc=1
块 4 @ 0x7ff05b7ff0c0 size=48 alloc=1
块 5 @ 0x7ff05b7ff0f0 size=3904 alloc=0
mm_free(p[1]); mm_free(p[2]); -> p[1] 与 p[2] 应合并为 96B 空闲块
块 2 @ 0x7ff05b7ff060 size=96 alloc=0
mm_free(p[0]); mm_free(p[3]); -> 最终与堆尾空闲块合成一大块
块 1 @ 0x7ff05b7ff030 size=4096 alloc=0
q = mm_malloc(100) (asize=128, 首次适配 + 分割):
q = 0x7ff05b7ff030
块 1 @ 0x7ff05b7ff030 size=128 alloc=1
块 2 @ 0x7ff05b7ff0b0 size=3968 alloc=0
堆一致性检查: PASS
堆大小 = 4128 字节, 载荷指针 16 字节对齐: 是
几个值得记住的数字：0x7ff05b7ff030 是 16 的倍数（16 字节对齐 ✓）；0x7ff05b7ff060 - 0x7ff05b7ff030 = 0x30 = 48 字节，与”块大小 48”完全吻合；序言块 16 字节（头+脚）在 heap_listp 之前，永远标记为已分配，因此释放堆中第一个真实块时不会去和”不存在的”前块合并。
13.3.5 首次适配 vs 最佳适配 vs 下次适配：真实实测对比
讲义给出的基准总开销是：Perfect Fit 1.6% < Best Fit 8.3% < First Fit 11.9% < Next Fit 21.6%。下面用同一个隐式空闲链表骨架、同一条随机 trace（4000 次 malloc(8..2007)，再隔一个 free 一个，然后用同分布再 malloc 2000 次）实测三种策略：
$ gcc -g -Wall -std=c11 c13_fitcompare.c -o c13_fitcompare && ./c13_fitcompare
真实输出：
first fit (首次适配):
堆大小 = 4227080 字节, 扩堆次数 = 1032
最终载荷 = 4059792 字节 -> 最终利用率 = 0.960
峰值载荷 = 4011660 字节 -> 峰值利用率 = 0.949
扫描块数合计 = 12795663 (越小吞吐率越高)
best fit (最佳适配):
堆大小 = 4145160 字节, 扩堆次数 = 1012
最终载荷 = 4058624 字节 -> 最终利用率 = 0.979
峰值载荷 = 4011660 字节 -> 峰值利用率 = 0.968
扫描块数合计 = 15625862 (越小吞吐率越高)
next fit (下次适配):
堆大小 = 4677640 字节, 扩堆次数 = 1142
最终载荷 = 4056624 字节 -> 最终利用率 = 0.867
峰值载荷 = 4011660 字节 -> 峰值利用率 = 0.858
扫描块数合计 = 4035516 (越小吞吐率越高)
结论（与讲义定性一致、并有量化证据）：
| 策略 | 复杂度 | 利用率 | 扫描量（吞吐率） | 碎片倾向 |
|---|---|---|---|---|
| 首次适配 first fit | 遍历到第一个足够大的块即停；最坏 $O(n)$ | 0.960 | 12.80 M | 易在链表开头堆积小碎块（splinters） |
| 最佳适配 best fit | 必须扫完整个堆；最坏 $O(n)$，常数更大 | 0.979（最好） | 15.63 M（最慢） | 留下最小的剩余块 → 碎片小，但会产生大量极小的不可用碎块 |
| 下次适配 next fit | 从上次结束处继续；常比 first fit 快 | 0.867（最差） | 4.04 M（最快，约 1/3） | 一些研究表明碎片更严重（实测堆最大、利用率最低） |
为什么 next fit 扫描量只有 first fit 的 1/3，利用率却最差？ 因为它的游标一直在堆里”漂移”，把大空闲块切成零散的小块后就再也不回头用它们，导致堆不断被迫向 sbrk 要新内存。这正说明吞吐率与利用率是一对冲突目标，也是 Malloc Lab 的性能指数把两者加权（$w=0.6$）的原因。
13.3.6 接口边界的真实行为（malloc(0)、free(NULL)、errno）
/* c13_m0.c 编译: gcc -g -Wall -std=c11 c13_m0.c -o c13_m0 */
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
int main(void){
void *p = malloc(0);
printf("malloc(0) = %p\n", p);
free(p); /* C 标准要求 malloc(0) 的返回值可被 free */
free(NULL); /* 必须是空操作 */
printf("free(NULL) 正常返回\n");
errno = 0;
void *q = malloc((size_t)1<<62); /* 必然失败 */
printf("malloc(2^62) = %p, errno=%d\n", q, errno);
void *r = calloc(4, 8);
unsigned char *c = r;
int allz = 1; for (int i=0;i<32;i++) if (c[i]) allz = 0;
printf("calloc(4,8) 全零: %s\n", allz?"是":"否");
free(r);
return 0;
}
真实运行输出：
malloc(0) = 0x6802a0
free(NULL) 正常返回
malloc(2^62) = (nil), errno=12 (ENOMEM)
calloc(4,8) 全零: 是
要点：① glibc 的 malloc(0) 返回非 NULL 的可释放指针（与讲义幻灯片的简化说法不同，属”补充说明”，也是 mm_malloc(0) 需要自己裁决的地方）；② errno=12 就是 ENOMEM，”失败返回 NULL 且置 errno“两条都要满足；③ calloc 确实清零——注意它清零的是 n*size 字节，n*size 溢出是经典漏洞（现代 glibc 会检测并返回 NULL）。
13.4 实验关联
L5a Malloc Lab（checkpoint）：本讲是 checkpoint 的直接理论来源。
- 要写的四个函数（
mm.c，只提交这一个文件）：mm_init、mm_malloc、mm_free、mm_realloc，声明在mm.h里，不能改接口。 - 性能指数：$P=wU+(1-w)\min\left(1,\dfrac{T}{T_{libc}}\right)$，$w=0.6$，$T_{libc}=600$ Kops/s（
config.h的AVG_LIBC_THRUPUT）。利用率占 60 分权重，但吞吐率超过 libc 后不再加分——所以别为了省内存做到慢得离谱。 - 硬性规则（违反直接 0 分）：不得调用任何内存管理相关的库函数/系统调用（
malloc/calloc/free/realloc/sbrk/brk及其变体）；不得定义任何全局或静态的复合数据结构（数组、结构体、树、链表），只允许标量全局变量——这正是 13.2.3 第 ③ 条”只能用堆区域、不能拿别的数据结构作弊”的落实：所有元数据必须存在堆里；必须返回 8 字节对齐的指针。 - 必须用
mem_sbrk：memlib.c用一块MAX_HEAP = 20 MB的区域模拟堆，提供mem_sbrk/mem_heap_lo/mem_heap_hi/mem_heapsize/mem_pagesize；mem_sbrk只接受正数，堆不可缩小。 mdriver用法（本讲必须会）：
$ make # 编译出 mdriver / mdriver-dbg
$ ./mdriver -V # 最详细输出：逐 trace 诊断，调试时用
$ ./mdriver -v # 每个 trace 的性能表格
$ ./mdriver -V -f short1-bal.rep # 只跑一个小 trace，开发期首选
$ ./mdriver -t <tracedir> # 换 trace 目录
$ ./mdriver -l # 同时测 libc malloc 作为对照
$ gdb ./mdriver-dbg # 断言只在 -dbg 版本里生效（rec07 强调）
- checkpoint 的关键交付物：堆一致性检查器（heap checker），
int mm_check(void)（recitation 里也叫mm_checkheap(int verbose)）。checkpoint 会按堆检查器的质量给分，建议的路线图顺序是：0. 先写堆检查器 → 1. 实现coalesce_block()→ 2. 换显式空闲链表 → 3. 再做分离空闲链表 → 4. 进一步优化（已分配块去脚部、降低最小块大小、压缩头部）。注意：提交前把所有mm_check调用去掉，否则吞吐率会被拖垮。 - 堆不变量（写检查器时逐条查）：块级——header 与 footer 一致、载荷对齐且大小合法、不存在相邻空闲块（除非你用延迟合并）；链表级——next/prev 一致、空闲链表里不能有已分配块、所有空闲块都必须在链表里、无环（可用龟兔赛跑 hare-and-tortoise 算法检测）、分离链表中块大小落在正确 size class；堆级——所有块都在堆边界内、哨兵块正确。
- 常见坑（recitation 点名的三类现象）：Garbled bytes = 覆盖了已分配块的数据；Overlapping payloads = 两个不同块的载荷在内存上重叠（几乎总是 size 算错或分割越界）；segfault = 访问非法地址。调试手段：
break mm.c:213、break find_fit if size == 24、watch heap_listp、backtrace+frame 1回看mm_malloc的局部变量、把printf换成条件编译的DBG_PRINTF/CHECKHEAP(...)（用#define DEBUG一键开关）。 - 建议的下一步：checkpoint 通过后再读 Lecture 14——显式空闲链表把”遍历所有块”变成”只遍历空闲块”（吞吐率），分离空闲链表让”找一个够大的块”更快、并近似实现最佳适配（利用率），footer 消除与最小块降到 16 字节则是利用率上最后的几个百分点。
本讲无直接关联的其他 lab，但为 L5b 与 Lecture 15（代码优化，分配器吞吐率是绝佳优化对象）提供前提。
13.5 常见错误与调试技巧
free非malloc返回的指针：free(p + 8)（中部指针）、free(&stack_var)、二次free(p)全是 UB——现象是之后某次malloc返回重叠地址或直接 SIGSEGV。调试：valgrind --leak-check=full ./mdriver -f short1-bal.rep；gdb 里watch *0x...盯住被破坏的头部。mm_malloc(0)未处理：asize算出 0 或find_fit(0)命中任意空闲块并把它切成0，后续遍历遇到size == 0的块会死循环。调试：在find_fit里加assert(GET_SIZE(HDRP(bp)) > 0)，用mdriver-dbg跑。- 忘记在
split_block后写新块的脚部：头部对了、脚部是垃圾，下一次coalesce用前块脚部回退时会跳到任意地址。现象是随机 segfault，且只在使用首次适配时偶尔出现。调试：写堆检查器断言GET(HDRP(bp)) == GET(FTRP(bp))（本章dump_heap就是这么做的），在每个malloc/free前后调用。 coalesce情况 4 的指针次序错（本章实测踩到的真 bug）：先把bp改成前块，再去算next_block(bp)，就把前块当成了当前块。现象是合并出一个”大小比堆还大”的块，堆检查器立刻报header != footer。调试：printf("合并: bp=%p prev=%p next=%p\n", ...)；gdb 里在小 trace 上单步coalesce_block。- 遍历不终止 / 死循环：把
for (bp = heap_listp; bp != brk; ...)当成终止条件，而自己维护的brk与mem_sbrk不同步。正确做法：用结尾头的size == 0终止。调试：gdb ./mdriver -ex 'b find_fit' -ex run，然后p/x *(unsigned long*)((char*)bp-8)看头部值。 - 非法使用 libc 函数：在
mm.c里#include <stdlib.h>后用malloc/memcpy（memcpy允许），或直接用sbrk。现象是 lab 规则判 0 分或堆互相踩踏。调试：nm mm.o \| grep -E 'malloc\|free\|sbrk'检查未定义符号；只在必要处用mem_sbrk。 - 对齐被破坏：
asize忘了向上取整到 16，或用了ALIGN(size + 8)（只加一个头，忘了脚部）。现象是mdriver报”payload not aligned”。调试：在mm_malloc返回前assert(((unsigned long)bp % 16) == 0)；用p/x bp直接看低 4 位。 - 在
free里写了已分配块之外的字节：比如用GET_SIZE(HDRP(bp))之前bp已经被改。调试：gdb的awatch *addr在任何访问（读或写）该地址时停下；rwatch只在读时停——定位”谁改了这个头部”极其有效。
13.6 关键要点
- 动态分配的不可替代性来自两条需求：编译期不知道大小、生命周期超出函数栈帧；分配器只能管理堆，
brk是它与内核的唯一接口（sbrk/mem_sbrk）。 - 分配器的五条硬约束中，最不可动摇的是”不能移动已分配块”——正因为它，碎片（内部与外部）无法通过压缩消除，只能靠放置策略、分割策略与合并策略缓解。
- 吞吐率与峰值利用率天然冲突：$U=\max_k P_k / H_n$ 度量前者之外的另一半，Malloc Lab 用 $P=wU+(1-w)\min(1,T/T_{libc})$（$w=0.6$）把它们绑在一起，逼你找平衡点。
- 块头部的精髓是”把对齐留下的空位当标志位用”：
header = size \| a，读大小时& ~0xf。块大小是 16 的倍数 ⇒ 低 4 位可用于标志（a、b）。 - 边界标记（footer）是 $O(1)$ 双向合并的钥匙：从当前头回退 8 字节即可读到前块脚部；代价是每块 8 字节。四种合并情况的伪代码必须背下来。
- 隐式空闲链表简单但分配是线性时间：除特殊用途外实践中不用它做
malloc/free，但分割（splitting）与边界标记合并（boundary tag coalescing）这两个概念对所有分配器都通用，是 Lecture 14 一切优化的地基。 - 序言块与结尾头不是装饰，是”消边界特判”的工程手段：
8/1的序言脚部让第一个块的前驱”合法且已分配”，size=0的结尾头让遍历与合并有终止条件。
13.7 思考题（带答案）
题 1（计算题：算内部碎片、算利用率、手画链表布局）：某隐式空闲链表分配器（4 字节头、4 字节脚部、块大小 8 的倍数、最小块 16 字节、载荷需 8 字节对齐）依次执行：
p1 = malloc(1); p2 = malloc(20); p3 = malloc(12); free(p2); p4 = malloc(4);
(a) 每个块的总大小是多少？各块的内部碎片是多少？(b) 设堆除了这些块之外没有别的空闲空间浪费，画出 5 步之后堆的 ASCII 布局（标注每块的 size/alloc）；(c) 若 free(p2) 采用立即合并，p4 = malloc(4) 能否复用 p2 的空间？若采用”只清标志不合并”的简化 free，结果是否相同？
答：(a) 块大小 $=(\text{请求}+\text{头 4}+\text{脚 4})$ 向上取整到 8，且不小于 16 字节：
| 请求 | 计算 | 块大小 | 载荷可用 | 内部碎片 |
|---|---|---|---|---|
malloc(1) | $1+8=9\to16$ | 16 | 8 | $8-1=7$ |
malloc(20) | $20+8=28\to32$ | 32 | 24 | $24-20=4$ |
malloc(12) | $12+8=20\to24$ | 24 | 16 | $16-12=4$ |
malloc(4) | $4+8=12\to16$ | 16 | 8 | $8-4=4$ |
(b) free(p2) 后 p2 块（32 字节空闲）夹在两个已分配块中间，情况 1，只能原地标记为空闲：
堆起点
+----------+----------+----------+----------+----------+
| 16/1 p1 | 32/0 p2 | 24/1 p3 | 16/1 p4 | 结尾 8/1 |
+----------+----------+----------+----------+----------+
内部碎片 7 空闲 内部碎片4 内部碎片4
(c) 能。malloc(4) 需要 16 字节，p2 的空闲块是 32 字节：$32-16=16\ge$ 最小块 16，于是分割成”16/1 的 p4 + 16/0 的空闲块”。若 free 只清标志不合并，本小题结果看起来相同（因为 p2 前后都是已分配块，情况 1 本来就不合并）——这正是”假碎片”难以察觉的原因：只有相邻空闲块出现时差异才暴露（见题 3）。
题 2（计算题：算峰值利用率）：用讲义 syn-array-short 基准的数据：峰值聚合载荷 $\max_k P_k=90036$ 字节，最终 Allocated 回到 0。若你的分配器为了完成这 20 次请求把堆扩到了 $H_n = 110000$ 字节，(a) 峰值利用率 $U$ 是多少？(b) 开销 $O_k$ 是多少？(c) 若每个已分配块平均多出 12 字节的头部+填充，估算这 1.5% 级别的内部碎片贡献了多少利用率损失，并解释为什么”Perfect Fit 1.6%”在实践中达不到。
答：(a) $U=\dfrac{\max_k P_k}{H_n}=\dfrac{90036}{110000}\approx 0.8185$（约 81.9%）。 (b) 在峰值处 $\max_k P_k=90036$，开销 $O=\dfrac{H}{P_{\max}}-1=\dfrac{110000}{90036}-1\approx 0.2217$，即 22.2% 的堆空间没有装程序数据。 (c) 峰值时有若干个已分配块，每个 12 字节 ⇒ 若峰值时约 10 个块，则多耗约 120 字节，占 90036 仅 $0.13\%$；真正的损耗来自外部碎片（空闲但无法使用的洞），而不是这 12 字节的头部。讲义指出”Perfect Fit 1.6%（只含内部碎片与对齐）”在实践中达不到，原因正是 compaction 不允许：已分配块一旦发出就不能移动，碎片只能靠放置/分割/合并策略缓解，永远消不掉；所以任何真实分配器的利用率都低于 Perfect Fit。
题 3（辨析题）：”既然 free(p) 时把分配位清成 0 就够了，合并（coalescing）只是性能优化，不做也不会错。”这句话错在哪？
答：错在把正确性与最优性搞混。不合并不会算错地址，但会让分配器在明明有足够连续空闲内存时仍然 sbrk 要新内存——讲义把这叫假碎片（false fragmentation）：三个相邻空闲块 32/0, 32/0, 16/0 合计 80 字节，而 malloc(40)（需 40 字节块）在首次适配下逐个检查，每个都不够大，于是返回 NULL 或扩堆。对 Malloc Lab 这直接表现为利用率暴跌，并且违反堆不变量”不允许存在相邻空闲块”。所以合并不只是”更快”，而是正确实现该策略的前提（除非你显式选择延迟合并，并在 malloc 前统一清扫）。
题 4（辨析题）：”我把堆的元数据（一个空闲块的表）放在 mm.c 里一个全局 static 结构体数组里，这样 find_fit 就是 $O(1)$ 了，比边界标记高明。”这错在哪？
答：错两处，而且都是致命的。第一，违反 lab 规则：编程规则明确禁止在 mm.c 里定义任何全局/静态复合数据结构（数组、结构体、树、链表），只允许标量全局变量——原因正是分配器的元数据必须放在它所管理的堆里，否则”用一个外部结构管理堆”就等于作弊，也破坏了”分配器只有堆可用”这条硬约束。第二，逻辑上循环：全局数组的大小是编译期固定的，而堆需要处理任意大小、任意数量的块；且你要在数组里存”哪些地址空闲”，这些地址本身就需要被分配器管理的内存来记录（否则数组会随块数增长而溢出）——这正是显式空闲链表（把 next/prev 指针放进空闲块的载荷区里） 的设计动机，也是 Lecture 14 的内容。正确的”$O(1)$ 找块”不是靠外挂表，而是靠改变堆内数据结构：显式链表只遍历空闲块，分离链表按 size class 分桶。