动态内存分配：分裂、合并与不变量

分配器要把一片连续存储拆成大小不同、生命周期交错的对象。难点不在调用一次 malloc，而在任意合法申请释放序列之后，仍能保持块边界、对齐、链表和用户数据一致。Malloc Lab 的价值，就是让这些抽象变成可以被错误破坏的字节布局。

本仓库的 arena 模型

allocator.c 启动时向系统申请 4096 字节，后续所有块都从这片区域划分，不再增长。每块前有 header，保存载荷容量、空闲状态、物理前后邻居。链表包含所有块，寻找空闲块时线性扫描，因此属于隐式空闲链表；它不是仅链接空闲块的显式 free list。

arena 起点
  [header A][payload A][header B][payload B][header C][payload C]
       ↔                       ↔                      ↔
                prev / next 按物理地址顺序连接

用户只得到 payload 地址。arena_free 从该地址减去对齐后的 header 大小，找到元数据。这里要求传入 NULL 或当前有效的本分配器返回值；它不负责防御任意非法指针、全部重复释放或被破坏的元数据，不能作为系统 malloc 替代品。

对齐与溢出必须先处理

对齐单位为 _Alignof(max_align_t)；header 大小和载荷容量都向上取整到该单位。若对齐 A=8，请求 13 字节，实际载荷容量为 16。内部碎片为至少 3 字节，再加 header 开销。对齐不是为了好看，而是确保返回地址适合相应 C 对象。

向上取整表达式 (n + A - 1) / A * A 可能先在加法处溢出，因此先检查 n > SIZE_MAX - (A - 1)。同样，测试是否足够分裂时用 capacity - size >= HEADER_SIZE + ALIGNMENT，其中已确认 capacity≥size，避免盲目加大数。

first-fit 与分裂

分配从链表头开始，找到第一个空闲且足够大的块。如果剩余容量能容纳一个 header 和最小对齐载荷，就把剩余部分变成新空闲块；否则整个块交给请求者。

以 A=8、header=32 为本机示例，空闲块载荷 80，请求 16，剩余 64，可拆成新 header 32 加新载荷 32。分裂后必须同时更新新块 prev、next，原后继的 prev，以及旧块的 capacity 和 next。漏改一条反向指针，往往直到后续释放才暴露。

本仓库选择 first-fit 是为了简洁，不代表它普遍最优。best-fit 可能减少某些浪费却产生很多小碎片；分离适配用大小类别降低搜索成本但增加元数据复杂度。比较算法前，需要先保证完全相同的正确性约束。

合并为何要处理两侧

释放将块标为空闲，先与右侧空闲块合并，再尝试与左侧合并。合并时回收中间 header 的空间，因此容量相加还要加一个 HEADER_SIZE。最终不允许两个物理相邻的空闲块继续并存，这是立即合并策略的不变量。

flowchart TD
  A[free 当前有效块] --> B[标记为空闲]
  B --> C{右邻居空闲?}
  C -- 是 --> D[吞并右块与其 header]
  C -- 否 --> E{左邻居空闲?}
  D --> E
  E -- 是 --> F[由左块吞并当前块]
  E -- 否 --> G[检查整个 arena]
  F --> G

查看流程图文本

flowchart TD
  A[free 当前有效块] --> B[标记为空闲]
  B --> C{右邻居空闲?}
  C -- 是 --> D[吞并右块与其 header]
  C -- 否 --> E{左邻居空闲?}
  D --> E
  E -- 是 --> F[由左块吞并当前块]
  E -- 否 --> G[检查整个 arena]
  F --> G

注意“空闲链表相邻”与“物理内存相邻”不是同一个概念。在本实现中链表按物理顺序，所以 next 正好是物理邻居；若升级成独立显式空闲表，这个假设就不成立，必须另用边界标记或物理块信息确认。

堆检查器比猜测更有用

check_arena 验证：每块恰好从前一块结束处开始；prev/next 对称；header 和载荷满足对齐；容量为正且对齐；块没有越过区域；没有相邻空闲块；遍历结束恰好达到 arena 尾部。每次修改后运行它，把错误尽量定位在产生时，而不是几百次操作后崩溃时。

测试还给活跃 payload 填入不同字节模式，持续验证所有在用块内容，防止元数据检查通过但两个活跃块重叠。4000 步固定伪随机序列可重复制造碎片；可重复性让首次失败点能稳定重现。

make -C labs/csapp allocator
./labs/csapp/allocator
make -C labs/csapp sanitize

本机输出 alignment=8, header=32，其他 ABI 可以不同。预期消息包含 split/coalesce/payload checks passed。算法正确性不应依赖你记住这个 header 数字，而应使用程序实际计算的值。

/* Fixed arena with an implicit free list. Block headers follow physical order.
 * Valid pointers from this allocator only; no realloc, threading, or heap growth. */
#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Block {
    size_t capacity;
    bool available;
    struct Block *prev, *next;
} Block;

typedef struct { unsigned char *memory; size_t bytes; Block *first; } Arena;
#define ALIGNMENT _Alignof(max_align_t)
#define HEADER_SIZE ((sizeof(Block) + ALIGNMENT - 1) / ALIGNMENT * ALIGNMENT)

static bool arena_init(Arena *a, size_t bytes) {
    bytes = bytes / ALIGNMENT * ALIGNMENT;
    if (bytes < HEADER_SIZE + ALIGNMENT) return false;
    a->memory = malloc(bytes);
    if (!a->memory) return false;
    a->bytes = bytes;
    a->first = (Block *)(void *)a->memory;
    *a->first = (Block){bytes - HEADER_SIZE, true, NULL, NULL};
    return true;
}

static void check_arena(const Arena *a) {
    const unsigned char *cursor = a->memory;
    const Block *previous = NULL;
    for (const Block *b = a->first; b; b = b->next) {
        assert((const unsigned char *)(const void *)b == cursor);
        assert(b->prev == previous);
        assert((uintptr_t)b % ALIGNMENT == 0);
        assert(b->capacity >= ALIGNMENT && b->capacity % ALIGNMENT == 0);
        assert(cursor + HEADER_SIZE + b->capacity <= a->memory + a->bytes);
        assert(!previous || !(previous->available && b->available));
        cursor += HEADER_SIZE + b->capacity;
        previous = b;
    }
    assert(cursor == a->memory + a->bytes);
}

static void *arena_alloc(Arena *a, size_t requested) {
    if (!requested || requested > SIZE_MAX - (ALIGNMENT - 1)) return NULL;
    size_t size = (requested + ALIGNMENT - 1) / ALIGNMENT * ALIGNMENT;
    for (Block *b = a->first; b; b = b->next) {
        if (!b->available || b->capacity < size) continue;
        if (b->capacity - size >= HEADER_SIZE + ALIGNMENT) {
            Block *rest = (Block *)(void *)((unsigned char *)(void *)b + HEADER_SIZE + size);
            *rest = (Block){b->capacity - size - HEADER_SIZE, true, b, b->next};
            if (rest->next) rest->next->prev = rest;
            b->next = rest;
            b->capacity = size;
        }
        b->available = false;
        check_arena(a);
        return (unsigned char *)(void *)b + HEADER_SIZE;
    }
    return NULL;
}

static void merge_next(Block *b) {
    Block *next = b->next;
    assert(next && b->available && next->available);
    b->capacity += HEADER_SIZE + next->capacity;
    b->next = next->next;
    if (b->next) b->next->prev = b;
}

static void arena_free(Arena *a, void *pointer) {
    if (!pointer) return;
    Block *b = (Block *)(void *)((unsigned char *)pointer - HEADER_SIZE);
    assert(!b->available); /* Some double frees; stale merged headers are not supported. */
    b->available = true;
    if (b->next && b->next->available) merge_next(b);
    if (b->prev && b->prev->available) merge_next(b->prev);
    check_arena(a);
}

int main(void) {
    Arena arena;
    assert(arena_init(&arena, 4096));
    assert(arena_alloc(&arena, 0) == NULL);
    assert(arena_alloc(&arena, SIZE_MAX) == NULL);
    unsigned char *a = arena_alloc(&arena, 48);
    unsigned char *b = arena_alloc(&arena, 80);
    unsigned char *c = arena_alloc(&arena, 48);
    assert(a && b && c);
    memset(a, 0xa1, 48); memset(b, 0xb2, 80); memset(c, 0xc3, 48);
    arena_free(&arena, b);
    unsigned char *reuse = arena_alloc(&arena, 16);
    assert(reuse == b); /* first-fit reuses the hole, potentially splitting it */
    memset(reuse, 0xdd, 16);
    for (size_t i = 0; i < 48; ++i) assert(a[i] == 0xa1 && c[i] == 0xc3);
    arena_free(&arena, reuse);
    arena_free(&arena, a);
    arena_free(&arena, c); /* coalesce with both sides */
    assert(arena.first->available && arena.first->next == NULL);
    assert(arena.first->capacity == arena.bytes - HEADER_SIZE);
    void *whole = arena_alloc(&arena, arena.bytes - HEADER_SIZE);
    assert(whole && arena_alloc(&arena, 1) == NULL);
    arena_free(&arena, whole);
    /* Deterministic fragmentation workload; inspect every live payload. */
    unsigned char *slots[32] = {0};
    size_t sizes[32] = {0};
    uint32_t rng = 7;
    for (unsigned step = 0; step < 4000; ++step) {
        rng = rng * UINT32_C(1664525) + UINT32_C(1013904223);
        unsigned slot = (rng >> 16) % 32;
        if (slots[slot]) {
            for (size_t i = 0; i < sizes[slot]; ++i) assert(slots[slot][i] == (unsigned char)slot);
            arena_free(&arena, slots[slot]); slots[slot] = NULL;
        } else {
            sizes[slot] = (rng >> 24) + 1;
            slots[slot] = arena_alloc(&arena, sizes[slot]);
            if (slots[slot]) memset(slots[slot], (int)slot, sizes[slot]);
        }
        check_arena(&arena);
        for (unsigned j = 0; j < 32; ++j)
            if (slots[j]) for (size_t i = 0; i < sizes[j]; ++i) assert(slots[j][i] == (unsigned char)j);
    }
    for (unsigned j = 0; j < 32; ++j) arena_free(&arena, slots[j]);
    assert(arena.first->next == NULL && arena.first->capacity == arena.bytes - HEADER_SIZE);
    printf("allocator: split/coalesce/payload checks passed (alignment=%zu, header=%zu)\n",
           (size_t)ALIGNMENT, (size_t)HEADER_SIZE);
    free(arena.memory);
    return 0;
}

怎样推进到 Malloc Lab

官方实验要求实现它规定的分配接口，并在给定模拟堆与 trace driver 下评价正确性和性能。Malloc Lab 说明

建议先做最简单可靠版本：堆布局与对齐 → 顺序分配 → free 标记 → 分裂 → 四类相邻合并 → realloc。实现 realloc 时，先处理 NULL 与零大小的接口约定，再尝试原地缩小或吞并右侧空闲空间；不成功时申请新块、复制 min(旧对象大小, 新请求大小) 字节、释放旧块。分配失败必须保留旧对象有效，不能先 free 再尝试申请。

之后再引入显式空闲链表：空闲载荷里存 prev_free/next_free，已分配块不需要这两个指针。分裂或合并前把相关块从空闲表移除，布局更新完成后插入新块。堆检查器增加“所有空闲块恰好在空闲表出现一次”和“表内没有已分配块”两条。

吞吐量与空间利用率有张力；先用短 trace 定位正确性，再用完整 trace 比较策略。一次测量应保存实现版本、编译选项、trace 和指标，避免只引用一个脱离环境的“很快”。

自测：总空闲空间 200 字节，为什么 120 字节请求仍可能失败？

如果空闲空间被活跃对象隔成多个不相邻小块，没有一块达到 120 字节加所需开销，就会出现外部碎片。合并只能合并物理相邻的空闲块，不能移动仍被用户指针引用的活跃对象。

自测：ASan 没报错，为什么还需要堆检查器？

ASan 通常看到的是一次合法的 4096 字节系统分配，并不知道 arena 内你划分的小块所有权。跨内部块的错误可能仍位于系统分配范围内。元数据不变量与载荷模式检查补上这一层语义。

下一章：并发与同步。