Lecture 14: 动态内存分配：高级 (Dynamic Memory Allocation: Advanced)

目录 · ← l13 · l15 →

Lecture 14: 动态内存分配：高级 (Dynamic Memory Allocation: Advanced)

讲义对应：CMU 15-213 Lecture 14 — Dynamic Memory Allocation: Advanced Concepts（素材：F25-14-malloc-advanced.txt） 教材对应：CS:APP3e 第 9 章 9.9.5–9.9.14（显式空闲链表、分离适配、简单分离存储）与 9.10–9.12（垃圾回收、C 语言常见内存错误、小结） 关联 Lab：L5b Malloc Lab（final）

14.1 概述

Lecture 13 的隐式空闲链表（implicit free list）结构极简、free 恒定时间，但 malloc 必须从头扫到尾（线性时间），故现实中无人使用。本讲要回答：如何在不放弃边界标记合并（boundary tag coalescing）的前提下，把分配从 $O(\text{块数})$ 降到近似 $O(1)$，同时不浪费内存？

两条正交技术：① 显式空闲链表（explicit free list）——只把空闲块串成链表，搜索范围从”所有块”缩到”空闲块”；② 分离空闲链表（segregated free list）——再按大小类（size class）切成一组链表，搜索范围进一步缩到一个桶。后半部分转向工程现实：realloc、延迟合并（deferred coalescing）、用最低位”偷”回脚部的 8 字节、glibc 的 malloc，以及 Malloc Lab 提分路线。

14.2 核心概念与底层机制图解

14.2.1 显式空闲链表（Explicit Free List）

• 定义与目的：只用 prev/next 指针把空闲块串成双向链表，链表头（root）是全局变量。
• 直观解释：隐式链表像按顺序装订的书，找空白页得逐页翻；显式链表像夹了一叠便利贴，直接指向各处空白页。
• 底层机制图解：关键洞察是”只跟踪空闲块，所以能用载荷区（payload）存指针“——已分配块的载荷被应用占用，空闲块的载荷反正没人用。

             显式空闲链表的物理布局（a = 已分配位，size 为块总字节数）
   低地址                                                                高地址
   +----------------+--------------------------------+----------------+
   | size | a  | 载荷与填充（应用数据）                | size | a  |  ← 已分配块：无指针
   +----------------+--------------------------------+----------------+
          ^ payload 返回给应用

   +----------------+---------------+---------------+----...----+----------------+
   | size | a=0 |      next（可指向堆中任意位置）  |  prev      | 未用 | size | a=0 |
   +----------------+---------------+---------------+----...----+----------------+
          ^                                         ^
          +--- 空闲块载荷区的前 16 字节被复用为指针 ---+

   逻辑顺序（链表）： 空闲块 C ---> 空闲块 A ---> 空闲块 B ---> NULL
   物理顺序（内存）： A(已分配) B(空闲) C(已分配) D(空闲) ...
                     逻辑与物理顺序无关，这是显式链表的本质特征

• 为什么”偏移量”比”指针”省空间（补充说明）：串联可用绝对指针（8 字节堆内地址）或相对偏移（4 字节堆基址下标）。教学堆只有几十 MB，4 字节偏移足够，一个空闲块可从 16 字节指针降到 8 字节偏移。代价是偏移量要求堆基址在整个生命周期内不变，跨 mmap 段时还要额外处理——”省空间但更脆”。
• 代价对比：分配从”扫描全部块”变”扫描空闲块”，内存越满加速比越大；代价是每空闲块多 16 字节开销，以及 free 要做”从链表摘除（splice out）”。

14.2.2 插入策略：LIFO 与地址有序（Insertion Policy）

• 定义与目的：新释放的块插到链表哪里？这直接决定碎片程度。
• LIFO（last-in-first-out）：插入头部，block->next = freelist; freelist = block;。简单、常数时间；但研究表明碎片比地址有序严重——刚释放的块被立刻复用，堆的”热区”反复被切碎。
• FIFO（first-in-first-out）：插入链表尾部，同样常数时间（维护尾指针），效果与 LIFO 接近，都不如地址有序。
• 地址有序（address-ordered）：保持 $\text{addr}(\text{prev}) < \text{addr}(\text{curr}) < \text{addr}(\text{next})$。碎片更低（相邻块在链表中也相邻）；代价是插入需搜索 $O(\text{空闲块数})$，但换来一个红利：可以省掉脚部（见 14.2.6）。
• 底层机制图解：”splice out”（摘除）与”coalesce”（合并）必须成对出现——被吞并的邻居要先从链表摘掉，否则出现悬空指针。

   LIFO 释放的四种情况（Root 为链表头；□=已分配 ▨=空闲）

   Case 1: 前后皆已分配                   Case 2: 后继空闲
     Before  Root -> ... -> [□]             Before  Root -> [▨] -> [□] -> [□]
     After   Root -> [▨] -> ...             After   Root -> [▨+□] -> [□]
     直接插入头部                            先摘除后继，再合并，插头部

   Case 3: 前驱空闲                       Case 4: 前后皆空闲
     Before  Root -> [□] -> [□] -> ...      Before  Root -> [▨] -> [□] -> [▨] -> ...
                     ↑待释放
     After   Root -> [▨+□] -> ...           After   Root -> [▨+□+▨] -> ...
     摘除前驱，合并，插头部                  摘除两邻居，三块合一，插头部

• 伪代码（地址有序插入 + 合并，最常用组合）：

/* 把空闲块 bp 按地址顺序插入链表，并完成与前后邻块的合并 */
insert_address_ordered(bp):
    prev = NULL
    curr = free_list_root
    while curr != NULL and curr < bp:          /* 找到第一个地址大于 bp 的节点 */
        prev = curr
        curr = next(curr)
    /* --- 此时有 prev < bp < curr（地址意义上） --- */
    set_next(bp, curr); set_prev(bp, prev)
    if prev != NULL: set_next(prev, bp) else: free_list_root = bp
    if curr != NULL: set_prev(curr, bp)
    coalesce(bp)                               /* 顺手检查物理相邻的 prev/curr 是否空闲 */

coalesce(bp):                                  /* 边界标记法：用 size 而非指针定位邻居 */
    if not allocated(prev_block(bp)):          /* 物理前驱空闲 */
        remove_from_list(prev_block(bp))       /* ← 必须摘除，否则悬空 */
        bp = merge(prev_block(bp), bp)
    if not allocated(next_block(bp)):          /* 物理后继空闲 */
        remove_from_list(next_block(bp))
        bp = merge(bp, next_block(bp))
    return bp

14.2.3 分离空闲链表（Segregated Free List）

• 定义与目的：维护一组空闲链表，每条只装某个大小类（size class）范围内的空闲块；先在目标类里找，找不到再去更大的类。
• 直观解释：图书馆按书脊厚度分书架——找 200 页的书直接去”150–250 页”那一格，没有才去更厚的一格。在窄范围里取第一块，天然接近”最佳适配”。
• 大小类划分示例（讲义的两种常见选择）：
  • 小尺寸逐档列举：{16} {32} {48} {64} {80} {96} {112} {128}；
  • 超过阈值后按 2 的幂分段：{129–256} {257–512} {513–1024} {1025–2048} {2049–4096} {4097–∞}；
  • 最后一个类必须无上界（严格说是 $2^{64}$），因为总可能出现超大请求。

   分离空闲链表的"大小类桶"结构（首适配 + 分离链表，教材推荐方案）

   segs[0..N-1]：N 个链表头（全局变量；lab 只给 128 字节可写全局空间！）
   +---------+
   | segs[0] |--> [48B ▨] <--> [48B ▨] --> NULL     类 0：size == 48
   +---------+
   | segs[1] |--> [64B ▨] --> NULL                  类 1：size == 64
   +---------+
   | segs[2] |--> [96B ▨] <--> [80B ▨] --> NULL     类 2：65..96
   +---------+
   |  ...    |
   +---------+
   | segs[k] |--> [512B ▨] --> [300B ▨] --> NULL    类 k：257..512
   +---------+
   | segs[N-1]|--> [1MB ▨] --> [65536B ▨] --> NULL  无上界类：4097..∞
   +---------+

   分配（asize = 对齐后的块大小）：
     for c = class(asize) to N-1:            ← 从目标类起，逐类向"更大的类"推进
         for bp in segs[c]:                  ← 类内首次适配
             if size(bp) >= asize: 分割并返回 bp 的载荷
     都没找到 -> sbrk 扩展堆，切出 asize，余量放进"合适的类"

• 分割细节：找到的块 $m \ge n$，余量够放一个最小块就分割（split），把碎片放回它自己所属的类（不是原类！）；余量太小则整块给出，接受内碎片。
• 为什么近似 $O(1)$：按 2 的幂分段时类数量是 $\log_2(\text{max size})$，逐类向后 $O(\log)$；类内首次适配则单类搜索是常数。极端情况：每尺寸一类即等价于最佳适配（best fit），利用率最高但链表头数组大到不可接受——”利用率 vs. 空间/时间”的经典权衡。

14.2.4 分离链表的两种组织方式

• 如何用单向链表省掉 prev：简单分离存储里每个类中的块大小完全相同，所以释放就是压入对应类的单向链表头（bp->next = segs[c]; segs[c] = bp;），分配就是弹出链表头。全程不需要 prev，也不需要脚部（永不合并），每个空闲块只花 8 字节指针。代价是必须以 chunk 为单位向系统要内存，且块大小取整带来可观内碎片——所以它适合分配尺寸高度集中的负载（内核对象缓存、固定尺寸网络缓冲区）。

14.2.5 四类分配器总对比

设 $F$ = 空闲块数，$B$ = 总块数，$C$ = 大小类数。下表把本讲与上一讲的技术放在同一标尺上（”内存开销”按每块额外字节计）：

读表要点：① 前三者都用边界标记合并，因此都能在 $O(1)$ 内完成 free；差别全在分配的搜索上。② 简单分离存储的”快”是用不合并 + 块大小取整换来的——它的内碎片可达 2 倍（请求 33 字节要到 64 字节的类），所以只适合固定尺寸负载。③ 分离适配是唯一在三个维度上都不差的方案，这正是教材推荐它、Malloc Lab 也以它为高分基线的原因。

14.2.6 省掉脚部：三种技巧

脚部存在的唯一理由是 free 时要向前找到前驱块的大小。若”前一块是否已分配”变成 $O(1)$ 可读的 1 bit，脚部就能只在空闲块里保留。

• 技巧 A：用块大小的低位存分配位。16 字节对齐保证块大小与地址的低 3 位恒为 0，header 里可白塞 3 个标志位。

   一个 8 字节 header 的位域划分（16 字节对齐 → 低 4 位全可用，这里用 2 位）
    63                                    4  3  2  1  0
   +--------------------------------------+--+--+--+--+
   |           块大小 size（≥16，低 4 位恒 0）|  |  |  |  |
   +--------------------------------------+--+--+--+--+
                                             |  |  |
                          bit0 = 本块已分配（ALLOCATED）
                          bit1 = 前一块已分配（PREV_ALLOC）
                          bit2/bit3 = 备用（讲义 bootcamp 提到 4 字节 header 压缩时用）

   于是：has_prev_footer(bp)  等价于  !(header(bp) >> 1 & 1)
        prev_block(bp)        = bp - size(footer(bp - 8))   当且仅当 bit1 == 0

• 技巧 B：用地址有序性推断前驱状态。若链表按地址排序，bp 的 prev 节点就是地址刚好小于 bp 的空闲块，于是 free(bp) 时 若 prev + size(prev) == bp，前驱物理相邻且必然空闲，可即刻合并，无需读任何脚部。代价是插入变成 $O(\text{空闲块数})$ 的搜索。
• 技巧 C：CS:APP 的 PREV_ALLOC 位（推荐）。在 header 的 bit1 中记录”物理前一块是否已分配“。释放 bp 时若 bit1 表明前驱空闲，就用 prev_block(bp) = bp - size(*(bp - 8)) 读前驱脚部（前驱空闲故有脚部）来定位；若前驱已分配，根本不读那一字节。于是：

   已分配块：[ header | payload ... ]                       ← 无脚部，省 8 字节
   空闲块  ：[ header | next | prev | ... | footer ]        ← 保留脚部

   free(bp) 的位运算：
     if (header(bp) & PREV_ALLOC) == 0:      /* 前驱空闲 */
         pp = bp - size(*(bp - 8))           /* 借前驱的脚部找到它 */
         摘除 pp，合并
     否则：                                   /* 前驱已分配 */
         什么都不读 —— 脚部被彻底省掉

   释放后还要顺手更新"后一块"的 PREV_ALLOC 位，这是最容易漏掉的一步！

• 收益量化（rec08 的例子）：malloc(24) 带脚部时 $24+8+8=40$ 取整到 16 倍数 → 48 字节，放不进 32 字节的块；去掉脚部后 $24+8=32$ → 正好放下。但去掉脚部不降低最小块——空闲块仍需 header+next+prev+footer = 32 字节。要真正降低最小块得再砍一个字段（简单分离存储砍 prev，或地址有序 + 省脚部砍到 24/16 字节）。

14.2.7 realloc 的实现（Reallocation）

• 语义（lab writeup 口径）：realloc(NULL,n) ≡ malloc(n)；realloc(p,0) ≡ free(p)；否则新块内容为旧块前 $\min(\text{old},\text{new})$ 字节，其余未初始化。
• 三条实现路径：

   ① 原地缩小（shrink in place）：new ≤ old
      [ header | payload(旧) ....................... ]
        └─> [ header | payload(新) | ▨ 余量块 ]         余量 ≥ 最小块才分割，挂回空闲链表
      吞吐率与利用率双赢：不搬数据，立刻回收空间

   ② 原地扩展（grow in place）：new > old 且物理后继块空闲且 csize + size(next) ≥ asize
      Before: [ header | payload(旧) ][ ▨ next 空闲 ]
      After : [ header | payload(新，地址不变) ][ ▨ 余量 ]（余量还回链表）
      收益：省一次 memcpy，且地址不变（对调用方缓存友好）

   ③ 搬移（move）：malloc(new) + memcpy(min(old,new)) + free(old)
      必做不可时的兜底；注意 memcpy 的长度必须取 min，绝不能直接 memcpy(new 的大小)

• 为什么”独立的 realloc“是提分关键：若写成 p2 = malloc(n); memcpy; free(p)，在 realloc 密集的 trace（realloc-bal、realloc2-bal）上会不断搬移，吞吐率低且堆被撑大；实现路径 ① ② 后两个 trace 都大幅改善。

14.2.8 延迟合并（Deferred Coalescing）

• 定义与目的：free 时只标记空闲并插入链表，不与邻居合并；等 malloc 找不到可用块时才集中做一轮全堆合并，再试一次。
• 直观解释：像收拾房间——不是碰掉一张纸就归位，而是一律丢进”待整理箱”，满了再一次性分类。
• 与立即合并的取舍：

• Malloc Lab 的坑：实现了延迟合并却忘了在 mm_checkheap 里放宽”no contiguous free blocks”这条不变量，堆检查器会把合法状态报成错误。bootcamp 明确点出：”no contiguous free blocks unless you defer coalescing“。

14.3 代码示例与底层机制分析

14.3.1 完整实现：分离空闲链表分配器（含 mm_malloc/mm_free/mm_realloc）

代码 (C)：

/* mmseg.c · 分离空闲链表分配器（16B 对齐 / 已分配块无脚部 / PREV_ALLOC 位）
 * 已分配：[header 8B | payload...]   空闲：[header | next | prev | ... | footer]
 * header：bit0 = 本块已分配；bit1 = 前一块已分配 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

#define WSIZE 8
#define DSIZE 16
#define CHUNK (1 << 12)          /* 一次多要 4 KB，摊薄 sbrk 开销 */
#define ALIGNMENT 16
#define MINBLK 32                /* header+next+prev+footer */
#define NCLASS 16

#define MAX(a, b)       ((a) > (b) ? (a) : (b))
#define ALIGN(s)        ((((size_t)(s)) + (ALIGNMENT-1)) & ~(size_t)(ALIGNMENT-1))
#define PACK(sz, a, pa) ((size_t)(sz) | (size_t)(a) | ((size_t)(pa) << 1))

static char   heap[1 << 20] __attribute__((aligned(16)));
static size_t heap_size = 0;
static char  *heap_end = NULL;   /* 结尾块 */
static void  *segs[NCLASS];      /* 各大小类链表头 */

static void *mem_sbrk(size_t incr) { void *p = heap + heap_size; heap_size += incr; return p; }

/* 块原语 */
static size_t get(void *p)             { return *(size_t *)p; }
static void   put(void *p, size_t v)   { *(size_t *)p = v; }
static size_t blk_size(void *bp)       { return get(bp) & ~(size_t)0xF; }
static int    blk_alloc(void *bp)      { return (int)(get(bp) & 0x1); }
static int    blk_prev_alloc(void *bp) { return (int)((get(bp) >> 1) & 0x1); }
static void   blk_set(void *bp, size_t sz, int a, int pa) { put(bp, PACK(sz,a,pa)); }
static void  *blk_footer(void *bp)     { return (char *)bp + blk_size(bp) - WSIZE; }
static void  *payload(void *bp)        { return (char *)bp + WSIZE; }
static void  *hdr_of(void *p)          { return (char *)p - WSIZE; }
static void  *next_blk(void *bp)       { return (char *)bp + blk_size(bp); }
static void  *NEXTP(void *bp)          { return (char *)bp + WSIZE; }  /* next */
static void  *PREVP(void *bp)          { return (char *)bp + DSIZE; }  /* prev */
static void  *prev_blk(void *bp)       { return (char *)bp - (get((char *)bp - WSIZE) & ~(size_t)0xF); }

/* 大小类：32..128 各一类，其后按 2 的幂分段 */
static int size_class(size_t size)
{
    if (size <= 128) return (int)(size / 16) - 2;      /* 32->0 ... 128->6 */
    size_t s = (size - 1) >> 7; int k = 0;
    while (s > 1) { s >>= 1; k++; }
    int c = 7 + k;
    return c >= NCLASS ? NCLASS - 1 : c;
}
static size_t class_lo(int c)   /* 某大小类的下限，仅用于调试打印 */
{
    if (c <= 6) return (size_t)(c + 2) * 16;
    return ((size_t)1 << (c - 7)) * 128 + 1;
}

/* 空闲链表：LIFO 双向 */
static void list_insert(void *bp)
{
    int   c = size_class(blk_size(bp));
    void *head = segs[c];
    *(void **)NEXTP(bp) = head;
    *(void **)PREVP(bp) = NULL;
    if (head) *(void **)PREVP(head) = bp;
    segs[c] = bp;
}
static void list_remove(void *bp)
{
    int   c  = size_class(blk_size(bp));
    void *pr = *(void **)PREVP(bp);
    void *nx = *(void **)NEXTP(bp);
    if (pr) *(void **)NEXTP(pr) = nx; else segs[c] = nx;
    if (nx) *(void **)PREVP(nx) = pr;
}

/* 合并：借 PREV_ALLOC 位发现前驱 */
static void *coalesce(void *bp)
{
    size_t size = blk_size(bp);
    if (!blk_prev_alloc(bp)) {              /* 前块空闲：摘除 + 合并 */
        void *pp  = prev_blk(bp);
        int   ppa = blk_prev_alloc(pp);
        list_remove(pp);
        size += blk_size(pp);
        bp = pp;
        blk_set(bp, size, 0, ppa);
    } else {
        blk_set(bp, size, 0, 1);
    }
    void *nb = (char *)bp + size;
    if (blk_size(nb) > 0 && !blk_alloc(nb)) {   /* 后块空闲（排除结尾块） */
        list_remove(nb);
        size += blk_size(nb);
        blk_set(bp, size, 0, blk_prev_alloc(bp));
    }
    put(blk_footer(bp), size);
    void *after = (char *)bp + size;            /* 更新后块的 PREV_ALLOC = 0 */
    blk_set(after, blk_size(after), blk_alloc(after), 0);
    list_insert(bp);
    return bp;
}

static void *extend_heap(size_t bytes)
{
    size_t asize = ALIGN(bytes < MINBLK ? MINBLK : bytes);
    /* 关键：新块 header 落在旧 epilogue 上，把它"顶掉" */
    char  *bp = (char *)mem_sbrk(asize) - WSIZE;
    int    pa = blk_prev_alloc(heap_end);
    blk_set(bp, asize, 0, pa);
    put(blk_footer(bp), asize);
    heap_end = bp + asize;
    blk_set(heap_end, 0, 1, 0);                 /* 新结尾块 */
    return coalesce(bp);
}

/* 首次适配 + 分离链表 */
static void *find_fit(size_t asize)
{
    for (int c = size_class(asize); c < NCLASS; c++)
        for (void *bp = segs[c]; bp; bp = *(void **)NEXTP(bp))
            if (blk_size(bp) >= asize) return bp;
    return NULL;
}

static void split_alloc(void *bp, size_t asize)
{
    size_t csize = blk_size(bp);
    int    pa    = blk_prev_alloc(bp);
    list_remove(bp);
    if (csize - asize >= MINBLK) {              /* 分割，余量放回自己的类 */
        blk_set(bp, asize, 1, pa);
        void *rb = (char *)bp + asize;
        blk_set(rb, csize - asize, 0, 1);
        put(blk_footer(rb), csize - asize);
        void *after = (char *)rb + (csize - asize);
        blk_set(after, blk_size(after), blk_alloc(after), 0);
        list_insert(rb);
    } else {                                    /* 余量太小，整块给出 */
        blk_set(bp, csize, 1, pa);
        void *after = (char *)bp + csize;
        blk_set(after, blk_size(after), blk_alloc(after), 1);
    }
}

static void shrink_alloc(void *bp, size_t asize)
{
    size_t csize = blk_size(bp);
    if (csize - asize < MINBLK) return;
    int pa = blk_prev_alloc(bp);
    blk_set(bp, asize, 1, pa);
    void *rb = (char *)bp + asize;
    blk_set(rb, csize - asize, 0, 1);
    put(blk_footer(rb), csize - asize);
    void *after = (char *)rb + (csize - asize);
    blk_set(after, blk_size(after), blk_alloc(after), 0);
    coalesce(rb);
}

int mm_init(void)
{
    memset(segs, 0, sizeof(segs));
    heap_size = 0;
    char *p = (char *)mem_sbrk(WSIZE + DSIZE + WSIZE); /* 垫块+序言块+结尾块 */
    if (p == NULL) return -1;
    put(p, 0);                       /* 垫块：首块地址 ≡ 8 (mod 16) */
    blk_set(p + WSIZE, DSIZE, 1, 1); /* 序言块（无脚部） */
    heap_end = p + WSIZE + DSIZE;
    blk_set(heap_end, 0, 1, 1);      /* 结尾块 */
    if (extend_heap(CHUNK) == NULL) return -1;
    return 0;
}

void *mm_malloc(size_t size)
{
    if (size == 0) return NULL;                 /* 讲义：返回 NULL */
    size_t asize = ALIGN(size + WSIZE);
    if (asize < MINBLK) asize = MINBLK;
    void *bp = find_fit(asize);
    if (!bp) bp = extend_heap(MAX(asize, CHUNK));
    if (!bp) return NULL;                       /* 堆耗尽 */
    split_alloc(bp, asize);
    return payload(bp);
}

void mm_free(void *p)
{
    if (p == NULL) return;
    void  *bp   = hdr_of(p);
    size_t size = blk_size(bp);
    blk_set(bp, size, 0, blk_prev_alloc(bp));
    put(blk_footer(bp), size);
    coalesce(bp);
}

void *mm_realloc(void *p, size_t size)
{
    if (p == NULL) return mm_malloc(size);      /* == malloc(n) */
    if (size == 0) { mm_free(p); return NULL; } /* == free(p)   */
    void  *bp    = hdr_of(p);
    size_t csize = blk_size(bp);
    size_t asize = ALIGN(size + WSIZE);
    if (asize < MINBLK) asize = MINBLK;

    if (asize <= csize) { shrink_alloc(bp, asize); return p; }   /* ① 缩小 */

    void *nb = next_blk(bp);                                     /* ② 原地扩展 */
    if (blk_size(nb) > 0 && !blk_alloc(nb) && csize + blk_size(nb) >= asize) {
        list_remove(nb);
        size_t nsize = csize + blk_size(nb);
        blk_set(bp, nsize, 1, blk_prev_alloc(bp));
        void *after = (char *)bp + nsize;
        blk_set(after, blk_size(after), blk_alloc(after), 1);
        shrink_alloc(bp, asize);
        return p;
    }
    void *np = mm_malloc(size);                                  /* ③ 搬移 */
    if (!np) return NULL;                       /* 旧块必须保持有效！ */
    size_t copy = csize - WSIZE < size ? csize - WSIZE : size;
    memcpy(np, p, copy);
    mm_free(p);
    return np;
}
/* mm_checkheap 与测试 main 的输出见 14.3.2 */

【代码做什么？】

1. mm_init：要 24 字节写垫块（让首个真实块地址 $\equiv 8 \pmod{16}$，从而 payload = bp + 8 是 16 倍数）、序言块（16 字节、已分配、无脚部、永不释放，用于消灭 coalesce 的边界判断）与结尾块（size = 0、已分配）；再用 extend_heap(4096) 备好第一块空闲内存。
2. mm_malloc：size + 8 向 16 取整得 asize（< 32 取 32）。find_fit 从 size_class(asize) 逐类向后扫（”首次适配 + 分离链表”）。命中后 split_alloc 摘除该节点，余量 ≥ MINBLK 就切两半并把余量插入它自己的类，否则整块给出。
3. mm_free：header 的 bit0 清零、补写脚部，然后 coalesce。coalesce 先看 bit1（PREV_ALLOC）：为 0 则前块空闲，用 bp - *(bp-8) 读前驱脚部定位、从链表摘除、合并；再查物理后继——因为已分配块没有脚部，只能靠 bp + size 定位，并用 size(nb) > 0 排除结尾块。收尾必须把后一块的 PREV_ALLOC 位清零，否则下次释放会去读不存在的前驱脚部。
4. mm_realloc：先试原地缩小，再试原地扩展，都不行才”分配 + 拷贝 + 释放”；memcpy 长度取 $\min(\text{csize}-8,\ \text{size})$，且 mm_malloc 失败时必须保持旧块有效。

【底层机制透视】

• 位域复用为何必须靠对齐：blk_size 用 & ~0xF 抹掉低 4 位，只有”所有块大小都是 16 的倍数”时才无损；也正因如此 prev_blk 才能直接用前驱脚部的大小值做减法。
• extend_heap 的”顶掉 epilogue”技巧：mem_sbrk(n) 返回新内存首字节，减 8 即旧 epilogue 地址；新块 header 写在这里正好覆盖它，再在 bp + n 写新 epilogue。若直接用 mem_sbrk(n) 当新块起点，就会留下 8 字节”黑洞”，破坏”堆内每字节都属于某块”的不变量并让堆遍历走歪（这是我实测中最初踩到的 bug）。
• 搜索复杂度：类数 $\approx \log_2$，类内长度取决于插入策略。LIFO 下刚释放的块总在头部，时间局部性好；地址有序每次插入 $O(\text{空闲块数})$ 但碎片更低。讲义的结论是”分离链表把首次适配近似成对整个堆的最佳适配“。
• 与硬件的对应：get/put 是 movq，blk_size 是 andq $-16, %rax，payload() 是 leaq 8(%rdi), %rax。分配器的耗时不在”算术”而在访存——find_fit 每走一个节点都要读 header 与 next，节点分散 ⇒ cache miss 多 ⇒ 吞吐率低。这正是”分离链表能提速”的硬件层原因：把搜索限制在小链表里 = 把随机访存变成局部访存。

【内存布局 / 数据结构图解】（实测 init 与 malloc(24) 之后的真实堆）

   地址              内容                       说明
   0x405080 ┌──────────────────────┐
            │ 0x0000000000000000   │  垫块（4 字节对齐填充，8 字节占位）
   0x405088 ├──────────────────────┤
            │ 0x0000000000000013   │  序言块 header：size=16, alloc=1, prev_alloc=1
   0x405090 ├──────────────────────┤  ← 序言块在这一行"结束"，无脚部
            │ 0x0000000000000023   │  malloc(24) 的块 header：size=32, alloc=1, prev_alloc=1
   0x405098 ├──────────────────────┤  ← payload（返回给应用，16 字节对齐 ✓）
            │ 24 字节应用数据       │
   0x4050b0 ├──────────────────────┤
            │ 0x0000000000000FE3   │  空闲余量 header：size=4064, alloc=0, prev_alloc=1
   0x4050b8 ├──────────────────────┤  ← 该空闲块的 next 指针（复用载荷区）
            │ next = NULL          │
   0x4050c0 ├──────────────────────┤
            │ prev = NULL          │
            │   ...未使用...        │
   0x405fb8 ├──────────────────────┤
            │ 0x0000000000000FE0   │  空闲块脚部：size=4064, alloc=0
   0x405fc0 ├──────────────────────┤
            │ 0x0000000000000001   │  结尾块：size=0, alloc=1, prev_alloc=0
   0x405fc8 └──────────────────────┘  堆结束（heap_size = 4128）

【与汇编 / 硬件的对应】（gcc -O2 -S 对 blk_size 与 payload 的实际产物）

# size_t blk_size(void *bp) { return *(size_t*)bp & ~(size_t)0xF; }
blk_size:
        movq    (%rdi), %rax
        andq    $-16, %rax          # 抹掉低 4 位（分配位 + PREV_ALLOC 位）
        ret

# void *payload(void *bp) { return (char*)bp + 8; }
payload:
        leaq    8(%rdi), %rax
        ret

# int blk_prev_alloc(void *bp) { return (*(size_t*)bp >> 1) & 1; }
blk_prev_alloc:
        movq    (%rdi), %rax
        shrq    $1, %rax            # 右移 1 位，把 bit1 降到最低位
        andl    $1, %eax
        ret

14.3.2 实测验证：分配 / 释放 / 分割 / 合并 / realloc

编译与运行（真实输出）：

$ gcc -g -Wall -std=c11 /tmp/mmseg.c -o /tmp/mmseg && /tmp/mmseg
==== 1) mm_init：序言块 + 结尾块 + 首个 4KB 空闲块 ====
  堆大小 = 4128 字节
  [init            ] 4096:F/pa=1 | epilogue(0)

==== 2) 分配：从大空闲块中分割 ====
  malloc(24)   = 0x4050a0  16 字节对齐: 是
  [malloc(24)      ] 32:A/pa=1 4064:F/pa=1 | epilogue(0)
  malloc(1000) = 0x4050c0
  [malloc(1000)    ] 32:A/pa=1 1008:A/pa=1 3056:F/pa=1 | epilogue(0)

==== 3) free 与立即合并 ====
   free(p2) → 与后续空闲余量块合并
  [after free(p2)  ] 32:A/pa=1 4064:F/pa=1 | epilogue(0)
   malloc(64) x2 = 0x4050c0, 0x405110
  [malloc(64) x2   ] 32:A/pa=1 80:A/pa=1 80:A/pa=1 3904:F/pa=1 | epilogue(0)
   free(p3) → 前后皆为已分配块（case 1），自成独立空闲块
  [after free(p3)  ] 32:A/pa=1 80:F/pa=1 80:A/pa=0 3904:F/pa=1 | epilogue(0)
   free(p4) → 与前块（case 3）合并
  [after free(p4)  ] 32:A/pa=1 4064:F/pa=1 | epilogue(0)

==== 4) realloc：原地扩展 / 原地缩小 ====
  q = malloc(64) = 0x4050c0
  [malloc(64)=q    ] 32:A/pa=1 80:A/pa=1 3984:F/pa=1 | epilogue(0)
  realloc(q,200)  = 0x4050c0  → 原地扩展（地址不变）
  原 64 字节数据完整保留 ✓
  [realloc grow    ] 32:A/pa=1 208:A/pa=1 3856:F/pa=1 | epilogue(0)
  realloc(q2,16)  = 0x4050c0  → 原地缩小，余量挂回空闲链表
  [realloc shrink  ] 32:A/pa=1 32:A/pa=1 4032:F/pa=1 | epilogue(0)

==== 5) realloc：搬移路径 ====
  r = malloc(64) = 0x4050e0
  [malloc(64)=r    ] 32:A/pa=1 32:A/pa=1 80:A/pa=1 3952:F/pa=1 | epilogue(0)
  realloc(r,4096) = 0x405130  → 搬移（malloc + memcpy + free）
  原 64 字节数据完整保留 ✓
  [realloc 4096    ] 32:A/pa=1 32:A/pa=1 80:F/pa=1 4112:A/pa=0 3952:F/pa=1 | epilogue(0)

==== 6) 边界语义 ====
  malloc(0)        = (nil)   （讲义：返回 NULL）
  realloc(NULL, 8) = 0x4050e0   （≡ malloc(8)）
  realloc(r2, 0)   = (nil)   （≡ free(r2)，返回 NULL）
  [after realloc(,0)] 32:A/pa=1 32:A/pa=1 32:A/pa=1 8112:F/pa=1 | epilogue(0)

==== 7) 不变量检查 mm_checkheap ====
  mm_checkheap(1) = PASS ✓

==== 8) 利用率 mini-trace（mdriver 口径：峰值载荷 / 堆大小）====
  64 次 malloc(900) → 释放全部偶数下标 → 32 次 malloc(400) 填回空档
  峰值载荷 = 57600 字节，堆大小 = 61472 字节
  peak utilization = 57600/61472 = 0.9370 （93.70%）
  mm_checkheap = PASS ✓

==== 9) 各大小类的空闲块分布 ====
  class  3 (>= 80) : 16 个空闲块
  class  9 (>= 513) : 16 个空闲块
  class 11 (>= 2049) : 1 个空闲块

格式：32:A/pa=1 = 块大小 32 字节、A 已分配（F 空闲）、pa 即 PREV_ALLOC 位。

随机压力测试（同一份源码，把接口当黑盒）：

$ gcc -g -Wall -std=c11 /tmp/mmstress.c -o /tmp/mmstress && /tmp/mmstress
200000 步随机操作全部通过，最终 mm_checkheap = PASS，堆 = 167968 字节

逐条解读：

• 步骤 2 的分割：4096 的空闲块被切成 32:A（服务 malloc(24)）与 4064:F（落在 class 11，≥2049）。
• 步骤 3 是合并正确性的关键证据：free(p3) 让 80 字节块变空闲，其后块的 pa 立刻从 1 变 0——正是”更新后块 PREV_ALLOC 位”在起作用；free(p4) 因 pa=0 正确找到前驱并合并回 4064。
• 步骤 4 是原地路径：realloc(q,200) 后块从 80 涨到 208，地址完全不变（0x4050c0）；realloc(q2,16) 缩回 32 并把 176 字节余量挂回链表。
• 步骤 5 是搬移路径：4096 > “80 + 后继 3952”，只能新分配并 memcpy；旧块 80:F 释放后与后面合并成 8112:F（步骤 6）。原 64 字节数据完整保留，验证了 memcpy 的 min 语义。
• 步骤 8：64 个 900 字节块先撑到峰值，隔一个释放一个再填 400 字节请求，分离链表把小块精确塞进空档，得 peak utilization = 93.70%。

14.3.3 利用率计算示例（含内部 / 外部碎片）

模型：教材 9.9 的隐式空闲链表——4B header + 4B footer，8 字节对齐，最小块 16 字节，首次适配、立即合并、按需扩展（不预取）。堆布局为 [填充 4B \| 序言块 8B \| 第一个真实块 ...]，序言块永不释放但计入堆大小。$w(n)$ 为块总大小，故 $w(4)=w(5)=w(6)=16$。

序列 A：p1=malloc(4); p2=malloc(5); p3=malloc(6); free(p2); p4=malloc(2);

$ gcc -g -Wall -std=c11 util.c -o util && ./util
== 序列 A: malloc(4); malloc(5); malloc(6); free(p2); malloc(2);  ==
   init          堆= 32 |  8:A 16:F | 请求载荷= 0
   malloc(4)p1   堆= 32 |  8:A 16:A | 请求载荷= 4
   malloc(5)p2   堆= 48 |  8:A 16:A 16:A | 请求载荷= 9
   malloc(6)p3   堆= 64 |  8:A 16:A 16:A 16:A | 请求载荷=15
   free(p2)      堆= 64 |  8:A 16:A 16:F 16:A | 请求载荷=10
   malloc(2)p4   堆= 64 |  8:A 16:A 16:A 16:A | 请求载荷=12

   峰值载荷 = 15, 终态堆 = 64
   peak utilization = 15/64 = 0.2344 (23.44%)
   终态载荷 = 12, 已分配块可用容量 = 24 -> 内部碎片 = 12 B
   终态空闲(外部碎片) = 0 B

推导：峰值载荷出现在 p1+p2+p3 = 15 字节，此刻堆 = 序言 8B + 三个 16B 块 = 56；随后 malloc(2) 复用了 free(p2) 留下的 16 字节空洞，堆不再增长，故终态堆仍为 64——$U$ 的分母就是 64：

碎片分解（终态：序言块 + 16:A(p1) + 16:A(p4) + 16:A(p3)）：

• 内碎片（internal fragmentation）：三个已分配块共 48 字节，扣掉各自头脚（每块 8 字节，共 24 字节）后可用 24 字节，而请求只有 $4+2+6=12$ 字节 → 内碎片 = 24 − 12 = 12 字节，来自把所有小请求抬到最小块可用 8 字节的那道取整。
• 外碎片（external fragmentation）：终态无空闲块（free(p2) 的洞被 malloc(2) 精确填满），故为 0。但这是运气：若第 5 个请求是 100 字节，那 16 字节空洞立刻变成外部碎片，并迫使堆再长 112 字节。
• 对照（预取 1 KB）：同一序列若一次 sbrk 预取 1 KB，堆直接到约 1048 字节，利用率暴跌到 15/1048 ≈ 1.4%——利用率直接受 chunk size 影响：预取提升吞吐率却拖低利用率（见 14.4）。

14.3.4 glibc 的 malloc：真实实现概览

glibc 的 malloc 不是”一个链表”，而是brk 与 mmap 双路径 + 多层 bins 的复合体：

• 分配路径：小请求走 brk 扩展 主分配区（main arena）；大请求（默认 ≥ MMAP_THRESHOLD = 128 KB）直接用 mmap，free 时立刻 munmap 归还内核——这就是”大块立刻还、小块囤着”的来源。多线程下还有 per-thread arena。
• 多层 bins：tcache（per-thread 快速缓存，每类最多 7 个，不加锁、不合并）→ fastbins（小块单向链表，也不合并）→ unsorted bin（刚释放的块先扔这里，延迟合并的体现）→ smallbins/largebins（按尺寸分桶）。这就是本讲技术的工业化版本：tcache = 简单分离存储，small/large bins = 分离适配。
• 调参接口：mallopt(M_MMAP_THRESHOLD, ...)、M_TRIM_THRESHOLD、M_MMAP_MAX、M_TOP_PAD、M_ARENA_MAX。注意 M_MMAP_THRESHOLD 有动态自适应：释放一个大 mmap 块会把阈值往上调，以减少系统调用次数。
• 观察工具：mallinfo()/mallinfo2()（返回 arena、hblkhd、uordblks）、malloc_stats()、malloc_usable_size()、环境变量 MALLOC_CHECK_=3。

实测：malloc_usable_size 与 mallinfo2（真实输出）

$ gcc -g -Wall -std=c11 /tmp/gi.c -o /tmp/gi && /tmp/gi
=== malloc_usable_size：请求大小 vs 实际可用 ===
  malloc(   1) -> usable =   24
  malloc(   8) -> usable =   24
  malloc(  16) -> usable =   24
  malloc(  24) -> usable =   24
  malloc(  25) -> usable =   40
  malloc(  32) -> usable =   40
  malloc(  40) -> usable =   40
  malloc( 100) -> usable =  104
  malloc( 128) -> usable =  136
  malloc(1000) -> usable = 1000

=== malloc(0) 的行为 ===
  malloc(0) = 0xaa62b0 （非 NULL：返回可 free 的唯一指针）
  malloc(0) = 0xaa67f0 （两次调用不相同）

=== mmap 阈值：小请求走 brk，大请求走 mmap ===
  初始: arena = 135168, hblkhd(mmap 区) = 0
  64×malloc(4096) 后: arena = 270336, hblkhd = 0  (仍走 brk)
  8×malloc(256KB) 后: arena = 270336, hblkhd = 2129920  (hblkhd 增长 = 走 mmap)
  释放后:            arena = 270336, hblkhd = 0  (mmap 区立即归还内核)

读法：① malloc(1..24) 实际给 24 字节（32 - 8 头），malloc(25..40) 给 40 字节（48 - 8）——glibc 的粒度是 16 字节，开销 8 字节；② malloc(0) 在 glibc 上返回一个非 NULL 的唯一指针，与讲义”F25-13 简明口径：size == 0 返回 NULL”不同，这是标准允许的实现自由度（C 标准要求”要么返回 NULL，要么返回一个可 free 的唯一指针”）；③ hblkhd 从 0 涨到约 2 MB 又归零，精确证明了 mmap 阈值路径的存在。

14.3.5 glibc 的两类真实报错（double free 与堆溢出）

⚠️ 仅供演示，请勿模仿——以下两个程序都是故意的未定义行为。

/* ⚠️ 仅供演示，请勿模仿：double free（同一指针释放两次） */
#include <stdio.h>
#include <stdlib.h>
int main(void) {
    char *p = malloc(32);
    printf("p = %p\n", (void *)p);
    free(p);
    printf("第一次 free(p) 完成\n");
    fflush(stdout);
    free(p);                     /* ← double free：UB，glibc 会中止进程 */
    printf("这行不该被打印\n");
    return 0;
}

$ gcc -g -Wall -std=c11 /tmp/df.c -o /tmp/df && /tmp/df
p = 0x23e42a0
第一次 free(p) 完成
free(): double free detected in tcache 2
Aborted (core dumped)          # exit code 134 (SIGABRT)

tcache 2 指的是”第 2 个 tcache 桶”：glibc 把刚释放的小块放进 per-thread 的 tcache，插入时发现该 chunk 已在桶内，于是直接 malloc_printerr 并 abort。注意 -Wall 同时给出了提示：warning: pointer 'p' used after 'free' [-Wuse-after-free]。

/* ⚠️ 仅供演示，请勿模仿：溢出写穿 top chunk 的 size 字段 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
int main(void) {
    mallopt(M_MMAP_THRESHOLD, 64 * 1024 * 1024); /* 强制大块走 brk 而非 mmap */
    char *big = malloc(1 << 20);
    printf("big = %p (走 brk)\n", (void *)big);
    free(big);                                   /* 归还给 top chunk */
    fflush(stdout);

    char *p = malloc(1000);
    printf("p = %p, usable = %zu\n", (void *)p, malloc_usable_size(p));
    fflush(stdout);

    memset(p, 0xAB, 1000 + 16 + 8);              /* ← 越界 1024 字节，覆盖 top->size */
    char *q = malloc(64);                        /* _int_malloc 校验 top->size 失败 */
    printf("q = %p\n", (void *)q);
    return 0;
}

$ gcc -g -w -std=c11 /tmp/ovf7.c -o /tmp/ovf7 && /tmp/ovf7
big = 0x7fbd2a467010 (走 brk)
p = 0x15492b0, usable = 1000
准备从 p 越界写 1024 字节，落点覆盖 top->size
malloc(): corrupted top size
Aborted (core dumped)          # exit code 134 (SIGABRT)

机理：p 的块总长 1008 字节，下一个 chunk 头（即 top chunk）的 size 字段在 p + 1008 + 8 处。越界写入把 top->size 改成 0xABAB…。下一次 malloc 走 _int_malloc，在 use_top 分支里用 chunksize(victim) > av->system_mem 之类的一致性判断识破了它，于是报 corrupted top size 并 abort。这正是讲义”堆溢出如何破坏元数据”的现场——你的分配器里，同样的一幕会表现为 coalesce 读到荒谬的块大小、走进错误的地址。这类缺陷的定位手段是 gdb 硬件观察点 watch *addr、valgrind，或写严格的堆检查器与契约断言。

14.4 实验关联：L5b Malloc Lab（final）

评分公式（writeup 与 mdriver.c 一致）：

• $U$ = 空间利用率（space utilization）。eval_mm_util 的做法：模拟一遍 trace，累计”已分配未释放的字节数”，取峰值 max_total_size 除以 mem_heapsize()。它统计”请求字节数”而非”块大小”，故内碎片与头脚开销都由 $U$ 承担；且分母是跑完整条 trace 后的堆高水位——一次失败的 find_fit 造成的扩展会永久拉低分数。
• $T$ = 吞吐率（Kops/s），每秒完成的 malloc/realloc/free 操作数；超过 600 Kops/s 不再加分（防止”只会快、不会省”）。
• 结构：正确性 20 + 性能 35 + 风格 10；风格里 5 分给堆检查器、5 分给结构注释——白送的分，别丢。

优化路线图（checkpoint → final）：

final 的三个硬指标与常见坑：

• 16 字节对齐是硬要求：mdriver 会检查 ALIGNMENT，要求载荷指针 ptr % 16 == 0（不是块头）。因块头 + 8 = 载荷，所有块头必须 $\equiv 8 \pmod{16}$；堆基址对齐无法保证，必须用一个垫块把首个真实块推到 $\equiv 8 \pmod{16}$。
• mem_sbrk 扩展的序言/结尾块处理：新块 header 必须恰好落在旧 epilogue 地址上（mem_sbrk(asize) - WSIZE），否则留 8 字节黑洞；新 epilogue 写在 bp + asize，别忘更新它的 PREV_ALLOC 位。
• mm_realloc 失败必须保持旧块有效：mm_malloc 返回 NULL 时直接返回 NULL，绝不 free 旧块。memcpy 长度必须取 $\min$。
• find_fit 的起点：每次从类 0 起扫（first fit）会让堆头部反复被切碎；rover / next fit（从上次成功处继续）常能同时提升两项。bootcamp 还提到 better fit（首适配后再往后多看 20 个块取最优）——但每次改动都要用 mdriver -v 重新测量。

调试要点（rec08 实录）：

• mdriver 报 “has N garbled bytes” = 你的分配器覆盖了已分配块里的用户数据。rec08 用 gdb --args ./mdriver-dbg1 -c ./traces/syn-struct-short.rep + watch *0x8000000a0 硬件观察点，gdb 停在第一个写入该地址的语句：write_block() at mm.c:333, Old value = 129, New value = 32。改用写契约（contract）更快：加 assert((unsigned long)footerp < ((long)block + size)) 后立刻报 Assertion ... failed。
• mdriver -D 尽早检测 garbled bytes，-V 定位是哪条 trace 出错。Valgrind 不能用于 Malloc Lab（你要替换的就是 malloc）。
• 堆检查器要随实现升级：加了分离链表就检查”块是否在正确的大小类”；用了延迟合并就要允许”相邻空闲块共存”；空闲链表无环可用 hare & tortoise 算法；”堆中空闲块数 == 链表中空闲块数”是高价值不变量。

14.5 常见错误与调试技巧

• 忘记更新后块的 PREV_ALLOC 位：free 时用错误偏移读前驱脚部，读到垃圾 → 随机崩溃或”头脚不一致”。调试：在 coalesce、split_alloc 末尾加 CHECKHEAP(1)，用 gdb 的 x/4gx <bp> 比对位域。这是去脚部实现中最高频的错误。
• extend_heap 没有”顶掉”旧 epilogue：8 字节黑洞让堆遍历停在错误位置。调试：对比 p mem_heapsize() 与 p (char*)mem_heap_hi()-(char*)mem_heap_lo()，或让 mm_checkheap 从 mem_heap_lo() 走到 mem_heap_hi() 检查每步是否落在块边界。
• memcpy 长度写成请求的新大小：realloc 增大时读出越界数据。调试：断在 mm_realloc，对照 p csize、p size、p copy。
• realloc 失败时释放了旧块：数据丢失 + 双重释放。调试：在独立测试程序（不是 mdriver）上跑 valgrind --leak-check=full。
• 双重释放（double free）：glibc 报 free(): double free detected in tcache 2 并 SIGABRT；自写分配器则表现为”同一块被插入链表两次 → 链表成环 → 无限循环”。调试：gdb 崩溃后 bt，再用 hare & tortoise 遍历链表查环；或 setenv MALLOC_CHECK_ 3。
• 堆溢出破坏元数据：典型报错 malloc(): corrupted top size、munmap_chunk(): invalid pointer。调试：gcc -fsanitize=address（受限环境可能因巨大 shadow 内存无法启动）、valgrind，或 gdb 硬件观察点 watch *addr。
• mm_checkheap 调用时机错误：在 coalesce 中途调用会看到”相邻空闲块未合并”的假报警。调试：只在 mm_malloc 返回前、mm_free 返回后调用。
• CHUNK 过大拉低利用率：预取 1 KB 在小型 trace 上就能把 $U$ 打到 12%。调试：用 mdriver -v 对比 util 列；MAX_HEAP 是 20 MB，CHUNK 太大会提前 OOM。

14.6 关键要点

1. 显式空闲链表的决定性优势：搜索范围从”所有块”缩到”空闲块”，且因为只跟踪空闲块，prev/next 可直接复用载荷区。
2. 插入策略是设计决策：LIFO 常数时间但碎片高；地址有序需搜索但碎片低，且是”省掉脚部”的前提之一。
3. 分离链表 = 大小类分桶 + 首次适配：先用 $O(\log)$ 个类把范围缩小，换来近似最佳适配的利用率与近似 $O(1)$ 的分配时间。
4. 两条分支必须分清：简单分离存储（不分割、不合并、单向链表、只花 8 字节指针）vs 分离适配（可分割、可合并、需边界标记）——前者快而浪费，后者是教材与 lab 的推荐方案。
5. 去掉脚部不降低最小块：脚部只影响已分配块的内碎片；最小块仍受空闲块 header+next+prev+footer 约束，要降它必须再砍一个字段。
6. 利用率与吞吐率在 Malloc Lab 里加权对抗：$P=0.6U+0.4\min(1,T/600\text{K})$，任何”多预取”或”多扫几块”都在用一个指标换另一个，必须用 mdriver -v 量化后再决定。

14.7 思考题（带答案）

Q1（计算题：分离链表的分段划分） 若采用”小尺寸逐档 16 字节步进到 128，之后按 2 的幂分段”的方案，请列出全部大小类，并指出 asize = 1160 的块应放入第几类；若该类为空，find_fit 接下来会检查哪些类？

答：类划分（16 类，下标 0 起）：

asize = 1160：$1024 < 1160 \le 2048$，落入 class 10（[1025, 2048]）。若 class 10 为空，find_fit 依次查 class 11 → 12 → 13 → 14 → 15（2049 到 ∞），每类内做首次适配。可见：类越细，跨类步数越多但匹配越准；类越粗，搜索越快但内碎片越大。

Q2（计算题：判断 realloc 能否原地扩展） 某分配器：16 字节对齐，header 8 字节，已分配块无脚部，最小块 32 字节。当前状态为 [A: 48 字节 \| B: 64 字节(空闲) \| C: 96 字节]，指针 p 指向 A 的载荷。 分别判断 realloc(p, 40)、realloc(p, 88)、realloc(p, 120) 能否原地扩展？若不能，说明走哪条路径。

答：A 的 csize = 48。

• realloc(p,40)：asize = ALIGN(48) = 48，$48 \le 48$ → 原地缩小（余量 0 < 32，不分割，直接返回 p）。
• realloc(p,88)：asize = ALIGN(96) = 96；B 空闲且 $48 + 64 = 112 \ge 96$ → 可原地扩展：合并后块长 112，切 96 给 A，余量 $112-96=16 < 32$ → 不分割，A 实占 112 字节（16 字节内碎片）。地址不变。
• realloc(p,120)：asize = ALIGN(128) = 128；$48+64=112 < 128$ → 不能原地扩展，走搬移：malloc(120) + memcpy(40 字节) + free(p)。拷贝长度是 $48-8=40$，不是 48 或 120。

Q3（”直观但错误的想法”错在哪） “分离空闲链表比显式空闲链表快，所以给每个可能的块大小都单独建一条链表，就能同时拿到最高的吞吐率和最高的利用率。”

答：错在两处。① 链表头数组本身要空间。Malloc Lab 只给 128 字节可写全局空间，若按最大块 20 MB、16 字节步进建表需上百万个指针，数组自己就比堆还大。② “每尺寸一类”只优化搜索，不优化碎片：它把最佳适配变成 $O(1)$，于是内碎片最大——最佳适配总选中”刚好装下”的块，把略大的块一直留着，长期产生的”小碎块”最难被后续请求利用；极端情况下（每类恰好剩一个小块）会出现”总空闲很大却无法满足任何请求”的外部碎片灾难。工程解是折中：小尺寸细粒度、大尺寸按 2 的幂粗粒度，再配 rover 起点与延迟合并。

Q4（计算题：利用率与碎片） 沿用 14.3.3 的隐式链表模型（4 字节 header + 4 字节 footer，8 字节对齐，最小块 16 字节，序言块 8 字节，按需扩展）。序列为 p1=malloc(3); p2=malloc(12); free(p1); p3=malloc(9);，求 peak utilization，并给出终态的内部碎片与外部碎片。

答（实测输出见下）：

== 序列 B (Q4): malloc(3); malloc(12); free(p1); malloc(9);  ==
   init          堆= 32 |  8:A 16:F | 请求载荷= 0
   malloc(3)p1   堆= 32 |  8:A 16:A | 请求载荷= 3
   malloc(12)p2  堆= 56 |  8:A 16:A 24:A | 请求载荷=15
        -> 峰值载荷 = 15 (此刻堆 = 56)
   free(p1)      堆= 56 |  8:A 16:F 24:A | 请求载荷=12
   malloc(9)p3   堆= 80 |  8:A 16:F 24:A 24:A | 请求载荷=21

   峰值载荷 = 15, 终态堆 = 80
   peak utilization = 15/80 = 0.1875 (18.75%)
   终态载荷 = 21, 已分配块可用容量 = 32 -> 内部碎片 = 11 B
   终态空闲(外部碎片) = 16 B

• w(3)=16（$3+8=11\to16$），w(12)=24（$12+8=20\to24$）。峰值载荷 $=3+12=15$，此刻堆 = 序言 8 + 16 + 24 = 56。
• free(p1) 后 w(9)=24（$9+8=17\to24$）。空闲块只有 16 字节，$16<24$ 放不下 → 必须扩展，堆从 56 涨到 80。终态载荷 $=12+9=21$。
• peak utilization $=15/80=0.1875$（18.75%）——分母是跑完整个序列后的堆高水位 80，而不是峰值那一刻的 56。
• 内碎片：终态已分配块为 24:A(p2) 与 24:A(p3)，共 48 字节，扣掉各自头脚 8 字节后可用 32 字节，请求载荷 21 → 内部碎片 = 32 − 21 = 11 字节。
• 外碎片：free(p1) 留下的 16 字节空闲块无法满足 24 字节请求，且终态无人再申请 → 外部碎片 = 16 字节。
• 要点：分母是”跑完全过程后的堆高水位”而非峰值那一刻的堆大小——这正是 mdriver 的 eval_mm_util 口径，也是”一次失败的 find_fit 造成的扩展会永久拉低分数”的原因。