这篇文章单独记录 Malloc Lab。它是 CSAPP 里最能训练 C 指针、堆布局和内存管理的一组实验。

0. 目标

Malloc Lab 要自己实现：

1
2
3
void *malloc(size_t size);
void free(void *ptr);
void *realloc(void *ptr, size_t size);

核心目标：

  • 正确性
  • 空间利用率
  • 吞吐量

1. 堆块布局

一个最基本的 block 通常包含：

1
2
3
header
payload
footer

header 里通常记录：

  • block 大小
  • 是否已分配

因为对齐要求，block size 通常是 8 或 16 的倍数。

2. 隐式空闲链表

最简单的实现是 implicit free list：

1
2
从堆开头一路扫描 block
看到空闲且足够大的 block 就分配

优点：

  • 思路简单
  • 适合入门

缺点：

  • 每次分配都可能扫很久
  • 吞吐量差

3. 显式空闲链表

explicit free list 只把空闲块串起来：

1
free block -> free block -> free block

优点：

  • 查找更快
  • 性能更好

代价：

  • 指针操作更复杂
  • 更容易写出内存破坏 bug

4. 嵌入式关联

Malloc Lab 对嵌入式的价值：

  • 理解堆碎片
  • 理解长期运行程序为什么会内存退化
  • 理解内存池设计
  • 理解 RTOS / 裸机里为什么常常限制动态分配
  • 更容易排查 double free、use-after-free、越界写

5. 复盘重点

学完后要能回答：

  • malloc 返回的是 block 的哪一部分？
  • 为什么需要对齐？
  • 内部碎片和外部碎片有什么区别？
  • free 后相邻空闲块为什么要合并？
  • 隐式链表和显式链表的权衡是什么？