Lecture 16: 动态内存分配 (Dynamic Memory Allocation)
Lecture 16: 动态内存分配 (Dynamic Memory Allocation)
概述
本讲要解决的问题是：当程序在编译时无法知道需要多少内存（用户会输入多少行、图里有多少个结点）时， 如何向操作系统申请、使用并归还内存。引入的机制是堆 (heap) 与 malloc/calloc/realloc/free 这一组函数，以及它们背后操作系统提供的 sbrk/brk 接口和分配器 (allocator) 的内部数据结构。 这一讲把第 15 讲的结构体与指针提升为”可变大小的对象”，是链表、树、动态数组、字符串处理 以及所有真实程序（包括课程 mem220 分配器）的基础，也解释了为什么 free 必须依赖元数据 (metadata)。
核心概念与底层机制图解
- 静态分配与栈分配为什么不够：
static/全局数组的大小编译期固定；栈上局部数组随帧生灭， 大小也必须编译期已知（C99 变长数组也不能超过帧的预算）。- 直观解释：静态数组像”买一套固定大小的房子”，栈数组像”借会议室开会”—— 会开完就收回；真实需求却常是”人来了再定房间”。
- 底层机制图解：程序的内存分为代码段、全局数据段、堆与栈； 堆的末端地址叫 break，
sbrk可以移动它：高地址 ┌──────────────────────┐ │ 系统空间 (内核) │ ├──────────────────────┤ │ 栈 (stack) │ ← 向低地址增长（局部变量、返回地址、帧） │ ↓ │ ├──────────────────────┤ │ ↑ │ │ 堆 (heap) │ ← 向高地址增长（malloc / mem220） ├──────────────────────┤ ← break（sbrk 改变这里） │ 全局数据段 (.bss/.data)│ ├──────────────────────┤ │ 代码段 (text) │ 低地址 └──────────────────────┘两段增长方向相反，中间的空隙就是它们共同的可用空间；堆撞上栈时进程就会崩溃。
- 作用域与存储期：堆对象的存储期由程序显式控制——从
malloc返回开始， 到free调用为止，与任何函数的作用域无关。这是它与栈对象最根本的区别， 也是”函数返回后指针仍然有效”（以及忘记free就永久泄漏）的原因。
sbrk与intptr_t：Linux 用void *sbrk (intptr_t increment);调整 break。- 直观解释：
sbrk像问物业”再给我扩 N 平方米”，物业把旧边界的位置告诉你，你就能算出新场地在哪。 - 底层机制图解：调用
sbrk(n)请求把 break 移动n字节，返回旧的 break （失败时返回(void*)-1）；参数为负则缩小堆。参数类型是intptr_t—— “足够装下一个指针的有符号整数”。为什么不允许用int？因为 64 位地址空间下int只有 32 位，装不下指针，也无法表示”负数增量”与地址的差值。 本讲示例里sbrk ((intptr_t)HEAP_BYTES)一次拿到0x831000..0x835000共 16384 字节。 - 作用域与存储期：
sbrk改变的是进程的内存映射，与函数作用域无关； 它申请的内存需要在程序结束前自己管理（我们的分配器从不把它还给 OS）。
- 直观解释：
- 四个函数的契约：
- 直观解释：
malloc是”给我一块地”，calloc是”给我一块除过草的地”，realloc是”我想把地扩大/缩小”，free是”这块地我不要了”。 底层机制图解：
调用 契约（必须逐条记住） void* malloc (size_t size)返回至少 size字节的未初始化内存块，失败返回NULLvoid* calloc (size_t n, size_t size)申请 n * size字节并全部置 0，失败返回NULLvoid* realloc (void* p, size_t size)改变已分配块的大小；可能搬到新地址（此时旧内容被复制、旧块被释放）；失败返回 NULL且旧块保持不变void free (void* p)归还 p指向的块；p必须是malloc/calloc/realloc返回的块首地址；free(NULL)是合法的空操作size_t是无符号整数类型（本机 64 位），”字节数”永远用它而不用int； 注意无符号的后果：malloc (n * sizeof (int))中若n很大，乘法会回绕成一个小数， 于是申请到一块太小的内存，随后越界写入。malloc返回void*：它可以被自动转换成任何指针类型（C 的隐式转换）， 但既不能解引用也不能做指针算术——必须先赋给具体类型的指针。- 作用域与存储期：这些对象都是 dynamic storage duration；
free之后指针值仍然存在，但它指向的存储期已经结束，继续使用是未定义行为 (UB)。
- 直观解释：
- 经典错误家族：全部与存储期有关。
- 直观解释：把内存想成停车位——忘了开走叫”泄漏”，车位被收回后还继续用叫”悬空指针”， 再退一次叫”重复释放”，停到线外叫”越界”，拿别人的车牌退租叫”释放非堆指针”， 把唯一的租约弄丢叫”丢失指针”。
底层机制图解：每种错误的机器层面后果如下：
错误 机理 典型后果 内存泄漏 (leak) 忘记 free，块永远占用堆内存持续增长，最终 malloc返回NULL悬空指针 (dangling pointer) free后指针值未变但存储期已结束读到别人的数据或已回收的元数据 释放后使用 (use-after-free) 同上，且写会破坏分配器元数据 程序”看起来正常”却悄悄损坏堆 重复释放 (double free) 同一块被插进自由链表两次 两个申请者拿到同一块内存 越界写 (buffer overflow) 写入 p[n]之外覆盖相邻块的头部（大小与链表指针） 释放非堆指针 free栈地址/全局地址/块中间地址分配器 abort 或堆结构被破坏 丢失唯一指针 指针被覆盖或离开作用域 等价于泄漏，且再也无法回收 - 作用域与存储期：判断一段代码是否安全只需两个问题： ① 该指针指向对象的存储期何时结束？② 结束时还有没有别的指针引用它？
- 动态数组的增长策略与摊销分析 (amortized analysis)：
- 直观解释：容量翻倍像”每次搬家都换一间大一倍的房子”——搬得次数少，虽然每次搬的东西多。
- 底层机制图解：容量翻倍时，第 k 次扩容复制
2^(k-1)个元素， 总复制量1 + 2 + … + n/2 < n，再加最后一次至多n，合计< 2n， 于是”每次追加的平均复制成本”是常数，即摊销 O(1)；若每次只加固定量（如 +4）， 总复制量4 + 8 + … + n ≈ n²/8，即总时间 O(n²)——实测（示例 1）加倍策略在n = 1000000时共复制 1048572 个元素（copies/n = 1.05），而固定 +4 策略 在n = 4000时就已复制 1998000 个（copies/n = 499.5）。代价是空间： 平均浪费约 38%（课程推导2(ln 2 − 1/2)），且realloc可能整块搬家导致指针失效 （扩容后必须使用realloc的返回值）。 - 作用域与存储期：数组在堆上（dynamic），描述它的
count/capacity通常在栈上， 两者必须一起更新，否则出现”容量说 100、实际只有 10”的不一致状态。
- 内部碎片与外部碎片 (internal / external fragmentation)：
- 直观解释：内部碎片是”租了一间 100 平米的房子只用了 60 平米”； 外部碎片是”空房间加起来有 200 平米，但没有一间能装下你要的 150 平米”。
- 底层机制图解：内部碎片来自分配粒度：
mem220按 2 的幂分配， 请求 1000 字节（加 16 字节头 = 1016）会拿到 1024 字节的块，浪费 8 字节； 实测反复申请 1000 字节时相邻块地址相差恰好 1024 字节。 外部碎片来自空洞：反复分配/释放不同大小的块会留下许多小空洞， 即使总空闲量足够，也可能没有一块连续区域满足大请求。 分配器的对策是分裂 (splitting) 与合并 (coalescing)（见示例 3）， 以及把块大小分箱 (binning) 成 2 的幂——这正是mem220的”最佳适配对数分配器”。 - 作用域与存储期：碎片是堆的全局性质，与任何单个变量无关； 它说明”程序的内存行为”不能只看单个对象，还要看整个生命周期的分配模式。
- 分配器如何工作：自由链表、首次适配、分裂与合并：
- 直观解释：自由链表是”空房间登记表”；首次适配是”从表头开始找第一间够大的房间”； 最佳适配是”找最接近需求的那一间”；分裂与合并是”把大房间隔成两间”与”把相邻空房间打通”。
- 底层机制图解：每个块前面有头部 (header) 记录大小与空闲标志，空闲块用头部的
next串成链表。分配时找到合适的块，必要时分裂成”用掉的 + 剩下的”；释放时插回链表并与 物理相邻的空闲块合并，否则堆会碎成一地小块。两种经典策略： 首次适配 (first fit) 取第一块够大的（快，但前部易留小碎片）； 最佳适配 (best fit) 取最接近需求的（省空间，但通常要遍历整个链表）。mem220用第三种：对数最佳适配 (best-fit logarithmic)——把大小量化成 2 的幂、 每种大小一条链表，”最佳适配”就变成查ceil(log2(size))那张表，O(1)。 - 作用域与存储期：链表里的块都来自
sbrk拿到的整片堆区，存储期贯穿整个进程； 分配器自己不把它们还给 OS（mem220只在初始化时malloc一次大块）。
malloc(0)、free为什么需要元数据：- 直观解释：
free(p)只收到一个地址，却必须知道这块有多大、属于哪张表—— 就像退房时只看房卡就知道房号、面积与租约，靠的是”卡片旁边的登记信息”。 - 底层机制图解：大小必须存在块旁边：
mem220把大小放在返回指针之前的mem_block_t.size里，free用mem_block[-1].size读回 （ptr[-1]等价于*(ptr - 1)，指针算术按sizeof (mem_block_t)缩放）。 示例分配器把头部放在(uint8_t*)ptr - sizeof (block_t)处，并用free标志 + 地址范围做检查。malloc(0)的返回值是实现定义的：可能返回NULL，也可能返回一个”不能解引用但可以free“的唯一指针；mem220明确选择返回NULL（其注释写明 0 字节请求返回NULL），实测mem220_allocate (0) = (nil)。 所以不要把malloc(0) == NULL当成”内存不足”的信号。 - 作用域与存储期：元数据与块同生共死；
free之后头部属于分配器， 此时读写p[-1]就是对分配器内部结构的破坏。
- 直观解释：
代码示例与底层机制分析
示例 1：动态数组的倍增长与摊销代价
代码 (C):
/* l4_grow.c
* 编译： gcc -g -std=c99 -Wall -Werror l4_grow.c -o l4_grow */
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
static int64_t copied = 0; /* elements moved by realloc */
static int64_t grows = 0;
static int32_t*
append (int32_t* arr, int32_t* n, int32_t* cap, int32_t value, int32_t doubling)
{
if (*n == *cap) {
int32_t new_cap = doubling ? (2 * *cap) : (*cap + 4);
int32_t* bigger = realloc (arr, (size_t)new_cap * sizeof (*arr));
if (NULL == bigger) {
exit (1); /* arr is still valid here */
}
copied += *n; /* realloc copies the live elements */
grows++;
arr = bigger;
*cap = new_cap;
}
arr[*n] = value;
(*n)++;
return arr;
}
static void
run (int32_t n, int32_t doubling, const char* label)
{
int32_t* arr = malloc (4 * sizeof (*arr));
int32_t count = 0, capacity = 4, i;
copied = 0;
grows = 0;
for (i = 0; n > i; i++) {
arr = append (arr, &count, &capacity, i, doubling);
}
printf ("%-10s n=%7d: grows=%5ld copies=%9ld copies/n=%7.2f\n",
label, (int)n, (long)grows, (long)copied,
(double)copied / (double)n);
free (arr);
}
int
main (void)
{
printf ("--- doubling the capacity (amortized O(1) per append) ---\n");
run (1000, 1, "double");
run (10000, 1, "double");
run (1000000, 1, "double");
printf ("\n--- adding a fixed increment of 4 (quadratic total work) ---\n");
run (1000, 0, "fixed +4");
run (2000, 0, "fixed +4");
run (4000, 0, "fixed +4");
return 0;
}
真实运行输出:
--- doubling the capacity (amortized O(1) per append) ---
double n= 1000: grows= 8 copies= 1020 copies/n= 1.02
double n= 10000: grows= 12 copies= 16380 copies/n= 1.64
double n=1000000: grows= 18 copies= 1048572 copies/n= 1.05
--- adding a fixed increment of 4 (quadratic total work) ---
fixed +4 n= 1000: grows= 249 copies= 124500 copies/n= 124.50
fixed +4 n= 2000: grows= 499 copies= 499000 copies/n= 249.50
fixed +4 n= 4000: grows= 999 copies= 1998000 copies/n= 499.50
【代码做什么？】
run先malloc一个容量为 4 的数组，然后反复调用append追加元素。append在count == capacity时扩容：加倍策略新容量为2 * cap，固定策略为cap + 4。- 每次扩容用
realloc，把被搬动的元素数累计进copied；失败则退出（此时旧块仍有效）。 - 三组加倍实验的
copies/n稳定在 1.02–1.64（与 n 无关，这正是摊销 O(1) 的含义）。 - 三组固定增量实验的
copies/n随 n 线性增长（124 → 249 → 499），总复制量 O(n²)。
【底层机制透视】 realloc 可能把整块内存搬到新地址（本机实验中确实发生了），所以必须用返回值更新 arr， 并把新地址传回调用者（append 返回 arr）。写成 realloc (arr, new_cap) 而忽略返回值， 就会同时造成”指针可能失效”与”失败时丢地址（泄漏）”两个问题。 另外 copies/n 在 n = 10000 时是 1.64 而不是 1.0x：容量从 4 开始翻倍， 总复制量是前面所有容量之和（4+8+…+8192 = 16380），相对当前 n 会有波动， 但永远小于 2n——摊销上界与某一时刻的具体值不是一回事。 加倍策略时间上最优，空间上却平均浪费约 38%（课程推导）， 且一次大搬家会造成短暂的”两份内存同时存在”的峰值需求。
【内存布局图解】
堆上的数组随扩容在地址上"跳":
容量 4: [0][1][2][3] ← malloc(16)
append 第 5 个元素时 → realloc 到容量 8:
旧块被释放（内容复制） 新块可能是完全不同的地址
容量 8: [0][1][2][3][4][5][6][7] ← 32 字节
...
容量 2^k: 复制了 2^(k-1) 个已有元素
总复制量 = 4 + 8 + ... + 2^(k-1) < 2^k ≤ 2n → 摊销 O(1)
栈: arr(指针) / count / capacity / i / n ← 每次调用 append 都会复制这 4 个整数
【与汇编的对应】
; append 的核心：比较 count 与 capacity，不等就直接写入，相等就扩容
; 注意：R5 是帧指针、R6 是栈指针、R4 是全局数据指针，临时值只用 R0-R3
APPEND LDR R0, R1, #0 ; R0 = count（R1 = &count，R3 = value）
LDR R2, R2, #0 ; R2 = capacity（R2 原本指向 capacity）
NOT R2, R2
ADD R2, R2, #1
ADD R2, R0, R2 ; R2 = count - capacity
BRnp STORE ; 不相等 -> 直接存
LDR R2, R0, #0 ; （示意）重新取 capacity
ADD R2, R2, R2 ; 2 * capacity（乘 2 就是左移一位）
ADD R6, R6, #-1
STR R2, R6, #0 ; 压入新容量作为参数（-> 被调用者的 R5+4）
JSR REALLOC ; 返回值放在参数正下方（被调用者的 R5+3）
LDR R1, R6, #0 ; R1 = 新块地址（失败时为 0）
ADD R6, R6, #2 ; 一条指令弹出参数与返回值槽
; ... R1 == 0 时保留旧指针并报错，否则 arr = R1 ...
STORE ADD R0, R0, #1 ; (*n)++
STR R0, R1, #0
RET
2 * capacity 在汇编里就是 ADD R5, R5, R5；realloc 是一次子程序调用—— “搬家”发生在库函数内部（可能 malloc 新块 + memcpy + free 旧块）。
示例 2：一个真正的分配器——自由链表 + 首次适配 + 分裂 + 合并
代码 (C)（完整的可编译程序）:
/*
* l6c_alloc.c -- a complete, compact first-fit free-list allocator on sbrk().
* Compile: gcc -g -std=c99 -Wall -Werror l6c_alloc.c -o l6c_alloc
*/
#define _DEFAULT_SOURCE 1 /* sbrk() under -std=c99 */
#include <stdio.h>
#include <stdint.h>
#include <stddef.h>
#include <stdlib.h>
#include <unistd.h>
#define HEAP_BYTES (16 * 1024)
#define ALIGN 16
/* The header lives immediately BEFORE the bytes handed to the caller.
Its size is deliberately 32 bytes (a multiple of ALIGN) so that the
payload always starts on a 16-byte boundary. */
typedef struct block {
size_t size; /* usable payload bytes */
struct block* next; /* link of the free list */
size_t free; /* 1 = free, 0 = in use */
size_t padding; /* keeps sizeof (block_t) == 32 */
} block_t;
static uint8_t* heap;
static size_t heap_bytes;
static block_t* free_list; /* kept sorted by address */
static block_t*
following (block_t* b)
{
return (block_t*)((uint8_t*)b + sizeof (block_t) + b->size);
}
static void
list_remove (block_t* b)
{
block_t** link = &free_list;
while (NULL != *link) {
if (*link == b) {
*link = b->next;
b->next = NULL;
return;
}
link = &(*link)->next;
}
}
static void
list_insert (block_t* b) /* insert, keeping the list sorted by address */
{
block_t** link = &free_list;
while (NULL != *link && *link < b) {
link = &(*link)->next;
}
b->next = *link;
*link = b;
}
static void*
my_malloc (size_t n_bytes)
{
block_t* b;
size_t need = (n_bytes + (ALIGN - 1)) & ~((size_t)ALIGN - 1); /* align up */
if (0 == n_bytes) {
return NULL;
}
for (b = free_list; NULL != b; b = b->next) { /* first fit */
if (need > b->size) {
continue;
}
if (b->size >= need + sizeof (block_t) + ALIGN) { /* split */
block_t* rest = (block_t*)((uint8_t*)b + sizeof (block_t) + need);
rest->size = b->size - need - sizeof (block_t);
rest->free = 1;
b->size = need;
list_remove (b);
list_insert (rest);
} else {
list_remove (b);
}
b->free = 0;
return (uint8_t*)b + sizeof (block_t);
}
return NULL;
}
static void
my_free (void* ptr)
{
block_t* b;
block_t* next;
if (NULL == ptr) {
return;
}
b = (block_t*)((uint8_t*)ptr - sizeof (block_t));
if (b < (block_t*)heap || b >= (block_t*)(heap + heap_bytes) || 0 != b->free) {
fprintf (stderr, "my_free: %p is not a live block (ignored)\n", ptr);
return;
}
b->free = 1;
list_insert (b);
next = following (b); /* coalesce with every following
free block, not just one */
while ((uint8_t*)next < heap + heap_bytes && 0 != next->free) {
list_remove (next);
b->size += sizeof (block_t) + next->size;
next = following (b);
}
}
static void
dump (void)
{
uint8_t* p = heap;
while (p < heap + heap_bytes) {
const block_t* b = (const block_t*)p;
printf (" [offset %6ld] size %6ld %s\n", (long)(p - heap),
(long)b->size, b->free ? "FREE" : "in use");
p += sizeof (block_t) + b->size;
}
}
int
main (void)
{
void* base = sbrk ((intptr_t)HEAP_BYTES);
uint8_t *a, *b, *c, *d;
int32_t local = 7;
if ((void*)-1 == base) {
perror ("sbrk");
return 1;
}
heap = base;
heap_bytes = (size_t)HEAP_BYTES;
free_list = (block_t*)heap; /* one big free block */
free_list->size = heap_bytes - sizeof (block_t);
free_list->next = NULL;
free_list->free = 1;
printf ("heap %p..%p (%ld bytes); first usable byte %p\n", (void*)heap,
(void*)(heap + heap_bytes), (long)heap_bytes,
(void*)(heap + sizeof (block_t)));
a = my_malloc (100); b = my_malloc (100); c = my_malloc (100);
printf ("a=%p b=%p c=%p ; b-a = %ld bytes = 112 payload + 32 header\n",
(void*)a, (void*)b, (void*)c, (long)(b - a));
my_free (b);
d = my_malloc (64);
printf ("a 64-byte request returned %p (%s b)\n", (void*)d,
(d == b) ? "the same address as" : "a different address from");
printf ("after splitting the hole:\n");
dump ();
my_free (c); my_free (d); my_free (a); /* descending address order */
printf ("after freeing c, d, a:\n");
dump ();
printf ("my_malloc (0) = %p\n", my_malloc (0));
printf ("freeing the stack address %p:\n", (void*)&local);
my_free (&local);
dump ();
return 0;
}
真实运行输出:
heap 0x831000..0x835000 (16384 bytes); first usable byte 0x831020
a=0x831020 b=0x8310b0 c=0x831140 ; b-a = 144 bytes = 112 payload + 32 header
a 64-byte request returned 0x8310b0 (the same address as b)
after splitting the hole:
[offset 0] size 112 in use
[offset 144] size 64 in use
[offset 240] size 16 FREE
[offset 288] size 112 in use
[offset 432] size 15920 FREE
after freeing c, d, a:
[offset 0] size 16352 FREE
my_malloc (0) = (nil)
freeing the stack address 0x7fff0a13cad4:
[offset 0] size 16352 FREE
（stderr: my_free: 0x7fff0a13cad4 is not a live block (ignored)）
【代码做什么？】
main用sbrk((intptr_t)16384)向操作系统要一整片堆，并把它做成一个巨大的空闲块（16352 字节有效载荷）。my_malloc(100)把请求向上取整到 16 的倍数（112），在自由链表里做首次适配： 大块够大，于是分裂成”用掉的 112 字节 + 剩下的空闲块”。- 三次 100 字节请求后，块以 144 字节（112 数据 + 32 头部）为步长依次排列。
my_free(b)把 b 标记为空闲并插回链表（按地址有序）；随后my_malloc(64)复用了 b 的地址 （0x8310b0），并再次分裂出 16 字节的空闲尾巴（64 + 32 头部 = 96，112 − 96 = 16）。- 按地址从高到低依次
my_free(c); my_free(d); my_free(a);时，合并循环把相邻空闲块逐个吞并， 最终重新拼成单个 16352 字节的空闲块——堆完全回到初始状态。 my_malloc(0)返回NULL；对栈地址调用my_free被”范围 + 已释放标志”检查拦下，堆保持完好。
【底层机制透视】 b - a = 144 把三件事一起说清了：头部开销（32 字节）、对齐粒度（16 字节）、 以及请求会被向上取整（100 → 112）。这 12 字节的差额就是内部碎片。 头部之所以刻意做成 32 字节（size/next/free 之后还留一个 padding）， 就是为了让”头部 + 16 的倍数”仍然落在 16 字节边界上——对齐要求会反过来影响分配器的设计。 分裂让大块满足小请求而不浪费太多；合并让相邻空闲块重新变大，否则堆会永久碎裂。 本例只做向前合并（following (b) 的地址 = b + 32 + size，看它是否也空闲，并循环直到遇到使用中的块）， 因此 my_free 需要按从高到低的地址顺序释放才能一次合并干净； 如果按从低到高释放，会留下多个相邻但未合并的空闲块——这正是”分裂容易、合并难”的根源。 真实分配器（如 glibc）在块尾也放一个边界标记 (boundary tag)，这样无需遍历链表就能找到前一个块并做双向合并。 最后，my_free 的”范围 + 已释放标志”检查说明：分配器必须对错误输入有防御， 否则一次 free 栈地址就会破坏整条链表；真实 glibc 会打印 free(): invalid pointer 并 abort。
【内存布局图解】
sbrk 拿到的 16 KiB 堆，每个块 = 32 字节头部 + 对齐到 16 的数据
偏移 0 32 144 176 288 320 432
┌─────────┬────────┬────────┬────────┬────────┬────────┬──────────────────┐
│ header │ a: 112 │ header │ b: 112 │ header │ c: 112 │ 空闲 15920 │
│ │ in use │ │ in use │ │ in use │ （整片剩余） │
└─────────┴────────┴────────┴────────┴────────┴────────┴──────────────────┘
释放 b 并再申请 64 字节后（复用 + 分裂出 16 字节尾巴）：
┌────────┬────────┬────────┬────┬────────┬────────────────────────────────┐
│ a: 112 │ d: 64 │ 空洞 16│ c:112│ 空闲 15920 │
└────────┴────────┴────────┴────┴────────┴────────────────────────────────┘
依次 free(c)、free(d)、free(a) → 合并成单个 16352 字节的空闲块（偏移 0 起）
free(ptr) 如何找到头部？ ptr ─ 32 字节 ─► header.size（这就是"元数据"）
返回给调用者的是 (uint8_t*)b + sizeof (block_t)，即"跳过一个头部"之后的地址
【与汇编的对应】
; my_malloc 的骨架：遍历自由链表 + 首次适配
MYMALLOC
LDR R1, FREE_LIST ; R1 = 链表头（文件作用域变量）
FITLOOP ADD R1, R1, #0
BRz NOMEM ; 链表空了 -> 返回 NULL
LDR R2, R1, #0 ; R2 = b->size
NOT R3, R0
ADD R3, R3, #1
ADD R3, R2, R3 ; R3 = b->size - need
BRn NEXTBLK ; 不够大 -> 看下一个
LDR R4, R1, #1 ; R4 = b->next
STR R4, FREE_LIST ; 从链表摘下来
; ... 够大时分裂成两块，并把后半块插回自由链表 ...
ADD R0, R1, #2 ; R0 = 返回给调用者的地址（跳过头部）
RET
NEXTBLK LDR R1, R1, #1
BRnzp FITLOOP
NOMEM AND R0, R0, #0
RET
free 侧的关键只有两步：从 ptr 往下取头部读出大小（负偏移访问）， 以及把块插回链表并检查地址是否相邻——相邻就是 prev + sizeof (header) + prev->size == b。
常见错误与调试技巧
- 内存泄漏：忘记
free，或中途把唯一的指针覆盖。实测valgrind --leak-check=full ./d4r_plain leak给出64 bytes in 1 blocks are definitely lost ... by 0x4011CB: get_block。 调试：valgrind --leak-check=full --show-leak-kinds=all ./prog； ASan（gcc -fsanitize=address -g）在本机因ulimit -v = 32 GB无法预留影子内存 （启动即报ReserveShadowMemoryRange failed），此时改用 valgrind。 - 释放后使用 / 悬空指针：
free(p)之后printf("%d", p[0])。普通运行可能”看起来正常”： 实测该程序输出uaf: after free, [0] reads as 1711并继续运行（值是垃圾，每次可能不同）， 而 valgrind 立刻报Invalid read of size 4 ... Address 0x4a6f040 is 0 bytes inside a block of size 16 free'd。 调试：valgrind --track-origins=yes ./prog；把指针free后置为NULL是好习惯。 - 重复释放：实测普通运行时
glibc报free(): double free detected in tcache 2并abort（退出码 134）， 而 valgrind 报Invalid free()后继续给出报告——同一份代码在两种环境下表现不同，这正是 UB 的特征。 调试：valgrind ./prog；MALLOC_CHECK_=3 ./prog让 glibc 做额外校验。 - 越界写：
p[4] = 1234（只分配了 4 个int32_t）。实测普通运行时毫无提示、输出仍是0 1 2 3； valgrind 报Invalid write of size 4 ... 0 bytes after a block of size 16 alloc'd。 调试：valgrind ./prog；gdb里x/8xw p观察块外内容是否被改写。 realloc直接赋回原指针：p = realloc (p, n);一旦失败，旧块地址丢失、永远泄漏。 正确写法是先用临时变量接住返回值（l5_realloc.c实测：请求 64 TiB 时返回NULL且errno = 12 (ENOMEM)，旧块内容p[0]=100 p[9]=109完好；随后一次真正的扩容成功并搬家）。 调试：valgrind --leak-check=full会指出失败路径上泄漏的块对应的源码行。- 释放非堆指针：对栈地址、全局地址或块中间地址调用
free。 实测 glibc 报free(): invalid pointer并abort；valgrind 报Address 0x1ffeffd0dc is on thread 1's stack。调试：valgrind ./prog；gdb下p ptr与bt对照，确认它是否来自malloc的返回值。
关键要点
- 堆对象具有 dynamic storage duration：生命周期由
malloc/free决定，与函数作用域无关—— 这既让函数可以返回新对象，也让忘记free变成永久泄漏。 - 每个
malloc都必须检查NULL，每个realloc都必须用临时变量接住返回值， 每个free都必须恰好一次、且只能传回malloc家族返回的块首地址。 - 动态数组用容量翻倍获得摊销 O(1) 的追加成本（总复制量 < 2n），固定增量则是 O(n²)； 代价是约 38% 的平均空间浪费与
realloc搬家的可能。 - 分配器的核心是元数据 + 自由链表：头部记录大小，分配时首次/最佳适配并分裂， 释放时插回链表并合并；
free无法知道大小，所以大小必须存在块旁边。 - 内存错误（泄漏、悬空、重复释放、越界）在普通运行中往往不可见， 必须用
valgrind/ASan 这类工具才能可靠发现——”跑起来没崩”绝不等于”内存管理正确”。
思考题（带答案）
问题 1：为什么 free (ptr) 只需要一个指针，就能把块归还给正确的链表？ 如果调用者传入的是 ptr + 1（块中间的地址），会发生什么？
答案：因为分配器把元数据放在返回指针之前。mem220 的 mem_block_t 存了块的字节数， free 用 mem_block[-1].size 读回它，再用 log2_ceil(size) 算出 bin 号并插进对应链表； 示例分配器同理：b = (block_t*)((uint8_t*)ptr - sizeof (block_t))。 传入 ptr + 1 时 b 落在块内部而非头部，读出的”大小”是用户数据的前几个字节， 算出的 bin 号毫无意义，插回链表时还会把用户数据当成链表指针—— 轻则下次 malloc 返回重叠内存，重则立即崩溃。示例分配器靠”地址范围 + free 标志”拦下这种错误 （实测对栈地址调用 my_free 被拒绝并打印警告，堆保持完好），真实分配器则直接 abort。
问题 2：mem220 为什么按 2 的幂分配块？这样做的收益与代价各是什么？
答案：收益有两个。① 最佳适配变成 O(1)：块大小只有 2^k 种，于是可以用数组 mem_bin[k] 存”大小为 2^k 的空闲块链表”，请求 n 字节时直接算 bin = ceil(log2(n + sizeof(header))) 查表，无需遍历所有空闲块。 ② 对齐自动满足：块都是 2 的幂且最小 32 字节，起始地址天然满足 malloc 的对齐要求。 代价是内部碎片：请求 1000 字节拿到 1024 字节的块（实测相邻地址相差 1024）， 请求 100 字节拿到 128 字节的块，请求 513 字节也要 1024 字节（浪费近一半），最坏浪费接近 50%； 而且它不分裂也不合并，被释放的 1024 字节块无法满足 2048 字节的请求—— “总空闲够”却可能分配失败。
问题 3：下面两段代码都想把数组增长到 2n，第二段为什么是危险的？请给出正确写法。
/* A */ arr = realloc (arr, 2 * n * sizeof (int32_t));
/* B */ int32_t* bigger = realloc (arr, 2 * n * sizeof (int32_t));
if (NULL == bigger) { /* 处理失败 */ } else { arr = bigger; }
答案：代码 A 把 realloc 的返回值直接写回唯一的指针：一旦失败返回 NULL， arr 立刻变成 NULL，原来那块内存的地址永久丢失——既不能使用也不能 free， 这就是经典的”失败路径泄漏”。代码 B 用临时变量接住返回值，失败时 arr 仍指向旧块 （内容完好，可继续使用或正常 free），成功时才更新。实测证据：l5_realloc.c 请求 64 TiB 时 realloc 返回 NULL、errno = 12 (ENOMEM)，而旧块的 p[0] = 100、p[9] = 109 仍可读， 随后一次正常扩容成功并把数据复制到新地址。另外 2 * n * sizeof (int32_t) 本身也可能溢出 size_t， 生产代码通常要检查 n > SIZE_MAX / (2 * sizeof (int32_t))。