Appearance
动态内存分配：堆是怎么管的
概念
上一篇讲的是栈——但它有四条硬局限：
| 局限 | 具体表现 |
|---|---|
| ① 生命周期由函数定 | 函数一返回，栈上的东西就没了——无法"活得比函数久" |
| ② 大小编译期就要定 | 运行时才知道要开多大（如文件长度）时，栈上开不了 |
| ③ 有硬上限 | 8 MiB——开个 100 MB 的数组直接崩 |
| ④ 无法"部分释放" | 栈是后进先出的，只能整帧回收 |
这四条限制，指向同一类需求："运行时才知道要多大、要活多久"的数据——链表、动态数组、字符串缓冲区、树节点……
这就是堆（heap）：
C 里访问堆的核心就两个函数：
c
void *p = malloc(n); /* 申请 n 字节，返回首地址（失败返回 NULL） */
free(p); /* 归还 —— 注意：不用传长度！ */"不用传长度"这件事本身就藏着一个问题：
free(p)只看一个指针，它是怎么知道"要还多少字节"的？答案：malloc在返回给你的那块内存"前面"多留了几个字节，偷偷记下了大小。这就是"块头（chunk header）"——也是"malloc(1)实际占用 32 字节"的原因。
本篇在主线上的位置：
lang/05-syscall.md里讲过sbrk——那就是"向内核要堆内存"的系统调用。 本篇要把中间那一层补上：malloc不是"每次要 4 字节就问内核"，它是"一次要一大块，自己在用户态切片分给调用者"——中间加了一层"用户态分配器"。这一层引出的问题（碎片、泄漏、UAF），是 L4 操作系统内存管理的前奏。
原理
一、栈 vs 堆：一张表看清分工
| 维度 | 栈 | 堆 |
|---|---|---|
| 谁分配 | 编译器自动（addiu $sp, $sp, -N） | 程序显式调用 malloc |
| 谁释放 | 编译器自动（函数返回即回收） | 程序显式 free（不 free 就泄漏） |
| 大小 | 编译期已知（帧大小是常量） | 运行时决定 |
| 上限 | 8 MiB（默认） | 几乎等于可用物理内存 + 交换区 |
| 速度 | 极快（一条减法指令） | 较慢（要跑分配算法） |
| 碎片 | 没有（LIFO 天然紧凑） | 有（内部 + 外部碎片，见第五节） |
| 生长方向 | 向下 | 向上（sbrk 抬高堆顶） |
| 典型错误 | 栈溢出、返回局部变量地址 | 泄漏、double free、use after free |
"向上 vs 向下"在进程内存映像里特别直观（lang/24-image.md 会画全图）：
低地址 ┌──────────────┐
│ 代码段 │
├──────────────┤
│ 数据段 │
├──────────────┤
│ 堆 ↓↑ 生长 │ ← 堆向上长（sbrk 抬高 break）
│ │
│ （空隙） │
│ │
│ 栈 ↑↓ 生长 │ ← 栈向下长
├──────────────┤
高地址 │ 环境/参数 │
└──────────────┘"堆和栈相向生长"是经典图示——它们共用中间那片地址空间，谁长过头撞到对方就出问题。现实中现代系统有 ASLR 与分离的映射区域，但概念图上仍然这样画（因为**"同一片地址空间被两头夹住"这个直觉是对的**）。
二、malloc 家族的接口与语义
| 函数 | 签名 | 语义 |
|---|---|---|
malloc | void *malloc(size_t n) | 申请 n 字节（不初始化） |
calloc | void *calloc(size_t n, size_t sz) | 申请 n×sz 字节并清零 |
realloc | void *realloc(void *p, size_t n) | 把已分配块改大小（可能搬家） |
free | void free(void *p) | 归还 |
六条必须记住的语义细节：
| 细节 | 说明 |
|---|---|
返回 void*，失败返回 NULL | 必须检查——失败时直接写 a[0] 就是段错误 |
| 内容不初始化 | malloc 不清零（可能含上次释放的旧数据）——要用 calloc 或 memset |
free(NULL) 是合法的 | 什么都不做（所以"初始化成 NULL + 统一 free"是安全模式） |
free 不改变指针的值 | free(p) 不会把 p 变成 NULL → 必须手动 p = NULL（回链 lang/11 的悬垂指针） |
只能 free 由 malloc 得来的地址 | free(&x)、free(buf + 1)、重复 free 都是未定义行为 |
realloc 可能搬家 | 必须写 p = realloc(p, n)——丢弃返回值会导致旧指针悬垂且内存泄漏 |
realloc 的三种行为（理解它是"原地扩 + 兜底搬家"）：
① 原地扩大：后面还有足够空闲 → 改块头，返回原地址
② 原地缩小：总是可以 → 改块头，返回原地址
③ 搬家：后面不够 → 新开一块、拷贝、free 旧的，返回新地址"
realloc会搬家"是 bug 高发区：它可能悄悄把数据搬到别处，而你手里的旧指针就悬垂了。正确写法永远是p = realloc(p, newn)。 另外：realloc(p, 0)的行为是实现相关的（可能等价于free并返回NULL），别依赖它。
三、块头：分配器怎么记住"这块多大"
核心洞察：
分配器在你看到的内存"前面"多留了 8 字节（glibc，64 位）：
你拿到并使用的区域
┌───────────────────────────────┐
┌────────┬────────┴───────────────────────────────┐
│ 块起点 │ 块头（8 字节） 数据 │
│ │ size | flags │
└────────┴────────────────────────────────────────┘
↑
malloc 返回的是这个位置（块头之后）"块头"里存什么？
| 字段 | 作用 |
|---|---|
| size | 本块总大小（含块头）——这就是 free 能知道"还多少"的原因 |
| flags（低 3 位） | ① 前一块是否正在使用（PREV_INUSE）② 是否由 mmap 得来 ③ 是否属于非主分配区 |
关键设计："前一块是否空闲"这个标志位被挤进了 size 的低位——因为块大小一定是 16 的倍数，低 3 位永远是 0，正好用来放标志。
这是"对齐换来的免费空间"——和
lang/12-layout.md里"结构体填充"是同一种思路的两面： 那边是"为了对齐浪费几个字节"；这边是"既然已经对齐了，那几位空着也是空着，拿来存标志"。
于是块大小就是对"请求字节数"做一次向上取整：
读法："请求量 + 8 字节块头"再向上对齐到 16 的倍数；最小 32 字节（glibc 的 MINSIZE，因为空闲块至少要有 prev_size + size + fd + bk 四个字段的位置）。
这就解释了那个经典数字：
malloc(1)实际占用 32 字节——你只要了 1 字节，分配器给了 32 字节（其中 24 字节可用，但按 16 对齐后你能用的还是 1）。1000 个malloc(1)的小对象，实际吃掉 32 KB，而你"以为"只用了 1 KB。这是"小对象要合并成一个池"的第一性理由（回链lang/05的"缓冲区"思想——同一种病：固定开销 vs 有效载荷）。
四、空闲块怎么找：三种适配策略
分配器要维护"哪些块是空闲的"。最简单的是隐式空闲链表（不真的存指针，靠块头 + 大小"走过去"）：
块1 块头│数据│ 块2 块头│数据│ 块3 块头│数据│ …
↑ 从块头读 size → 跳过块1 → 落在块2 的块头 → 再读 size → …
这就是"隐式"：链表指针不用存，靠"大小"导航有了空闲块集合，malloc(n) 就得回答"挑哪一块"——三种策略：
| 策略 | 规则 | 优点 | 缺点 |
|---|---|---|---|
| 首次适配（first fit） | 从链表头找第一个够大的 | 快、实现简单 | 低地址处容易积小碎片 |
| 最佳适配（best fit） | 找"最小的、但够大的" | 剩余碎片最小 | 要遍历整个链表；且会留下极小的"不可用碎片" |
| 下次适配（next fit） | 从上次位置继续往后找 | 分布更均匀 | 整体性能与首次适配相近 |
还有个"最差适配（worst fit）"：挑最大的块——剩余块最大、最可用，但会迅速把大块切碎。实践中很少用。
真实分配器（glibc）用的是"分离空闲链表（segregated free list）"：按大小分箱（bin），小请求走小箱子直接取，大请求走大箱子。这样"首次适配"只在一个很小的范围里做，又快又省碎片——"用空间分类换时间"，和
circuit/14-register.md里"选择电路按规模分档"是同一种手法。
五、碎片：内部与外部
| 类型 | 定义 | 例子 |
|---|---|---|
| 内部碎片 | 分配给你的块里，"归你但用不到"的部分 | malloc(1) 拿到 32 字节块 → 内部浪费 31 字节 |
| 外部碎片 | 空闲总量够，但都是零散的，拼不出一个足够大的连续块 | 三个 16 字节空闲块，要 24 字节 → 失败 |
外部碎片的图示（要申请 24 字节，总空闲 48 字节却不够）：
[已用 16][空闲 16][已用 16][空闲 16][空闲 16]
↑ 太小 ↑ 太小
总空闲 = 48 字节 > 24，但没有一个"连续 24 字节" → malloc(24) 失败
（后两个空闲块若相邻并被合并，就能满足 —— 见例 3）对抗碎片的两招：
| 招法 | 做法 | 代价 |
|---|---|---|
| 合并（coalescing） | free 时检查前后块，若空闲就合成一块 | 每次 free 多一点开销（靠 PREV_INUSE 标志 + 块头导航） |
| 紧凑（compaction） | 把所有活着的数据搬到一起 | C 做不到——因为指针会失效 |
"为什么 C 不能做紧凑？" 这是理解 C 与托管语言差别的关键一问： 紧凑意味着"对象会搬家"，而对象一搬家，所有指向它的指针都必须被改。C 里指针就是裸地址（回链
lang/11），运行时根本不知道"哪里存着指向它的指针" → 搬了就全乱。Java/Go 能做到，是因为它们的运行时"知道每个对象的类型与指针位置"（类型信息没被丢掉）。反过来看，lang/10-type.md那句"类型只存在于编译器眼中"在这里收到了代价：省了运行时的类型信息，就换不来 GC 的搬家能力。
六、向内核要内存：两条路
分配器自己怎么拿到内存？ 两种系统调用（回链 lang/05-syscall.md）：
| 路径 | 何时用 | 特点 |
|---|---|---|
sbrk / brk | 小请求（如 < 128 KiB） | 抬高"堆顶（program break）"；一次要一大块，自己切 |
mmap | 大请求（如 ≥ 128 KiB） | 直接映射一块匿名的独立虚拟内存；free 时能整块还给内核 |
"一次要一大块"到底省了多少？ 算一笔账：
假设每次
malloc(16)都去问内核：10 万次分配 = 10 万次syscall——按lang/05的量级（约 500 ns/次），光系统调用就 50 ms。而"一次要 128 KiB（8192 个 16 字节块），自己切"：头一次syscall之后就再也不用进内核——快了约四个数量级。和"逐字节读文件 vs 按块读"完全是同一个道理：系统调用贵 → 攒够了一次做。
七、四类经典错误
| 错误 | 代码 | 后果 |
|---|---|---|
| 内存泄漏（leak） | malloc 了没 free（尤其 return 的路径上） | 进程内存持续增长，最终被 OOM 杀掉 |
| double free | 同一指针 free 两次 | 分配器内部链表被破坏 → 后续 malloc 崩（崩在哪不可预测） |
| use after free（UAF） | free(p) 之后还读写 p | 读到"新主人"的数据；写会破坏别人的数据——也是最常被利用的漏洞 |
| 越界写（heap overflow） | p[n] 写到 malloc(n) 之外 | 破坏下一块的块头——下次 malloc/free 时崩 |
四条的防御：
c
int *p = malloc(n * sizeof(int));
if (p == NULL) { /* 处理失败 */ } /* ① 检查返回值 */
...
free(p);
p = NULL; /* ② 用后置空（同时防 UAF 与 double free） */"检查返回值 + 用后置空"这两条，能挡掉一大半堆相关 bug。再加一条：任何写入都要带上"这块只有多大"（回链
lang/13-callstack.md的缓冲区溢出）——堆溢出和栈溢出是同一个病的两个部位。
示例
例 1：malloc 的真实开销——你要 1 字节，系统给你 32
任务：按 glibc 的块大小公式，算出各种请求的实际占用。
c
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
int main(void) {
size_t reqs[] = {1, 8, 16, 24, 25, 40, 41, 100, 1000};
for (int i = 0; i < 9; i++) {
void *p = malloc(reqs[i]);
/* malloc_usable_size 返回"实际可用字节数"（glibc 扩展） */
printf("malloc(%4zu) 可用 %4zu 字节\n", reqs[i], malloc_usable_size(p));
free(p);
}
return 0;
}用 Python 复算 glibc 的块大小公式：
python
import unicodedata
def w(s):
return sum(2 if unicodedata.east_asian_width(c) in "WF" else 1 for c in s)
def pad(s, n):
return s + " " * max(0, n - w(s))
HEADER, ALIGN, MINSIZE = 8, 16, 32 # 块头 8 字节、16 字节对齐、最小块 32
def align_up(x, a):
return (x + a - 1) // a * a
def chunk_of(req):
"""glibc：chunk = max(32, align16(req + 8))；可用 = chunk - 8"""
raw = align_up(req + HEADER, ALIGN)
return max(raw, MINSIZE)
print(" " + pad("请求字节", 10) + pad("req+8", 8) + pad("向上取整16", 12)
+ pad("chunk", 8) + pad("可用", 8) + "浪费率")
for req in (1, 8, 16, 24, 25, 40, 41, 100, 1000):
ch = chunk_of(req)
print(" " + pad(str(req), 10) + pad(str(req + HEADER), 8)
+ pad(str(align_up(req + HEADER, ALIGN)), 12)
+ pad(str(ch), 8) + pad(str(ch - HEADER), 8) + f"{1 - req / ch:.1%}")
print("\n === 台阶规律 ===")
print(" 请求 1 ~ 24 → chunk 32（可用 24）")
print(" 请求 25 ~ 40 → chunk 48（可用 40）")
print(" 请求 41 ~ 56 → chunk 64（可用 56）")
print(" 每 16 字节一个台阶，且最小 32 —— 对齐带来的'分档'")
print("\n === 小对象的代价（1000 个对象）===")
for req in (1, 8, 16, 24, 25, 100):
ch = chunk_of(req)
print(f" malloc({req:>3}) × 1000 → 真实占用 {ch * 1000:>8} 字节"
f"（你以为用了 {req * 1000:>6}，放大 {ch / req:.1f} 倍）")预期输出：
请求字节 req+8 向上取整16 chunk 可用 浪费率
1 9 16 32 24 96.9%
8 16 16 32 24 75.0%
16 24 32 32 24 50.0%
24 32 32 32 24 25.0%
25 33 48 48 40 47.9%
40 48 48 48 40 16.7%
41 49 64 64 56 35.9%
100 108 112 112 104 10.7%
1000 1008 1008 1008 1000 0.8%
=== 台阶规律 ===
请求 1 ~ 24 → chunk 32（可用 24）
请求 25 ~ 40 → chunk 48（可用 40）
请求 41 ~ 56 → chunk 64（可用 56）
每 16 字节一个台阶，且最小 32 —— 对齐带来的'分档'
=== 小对象的代价（1000 个对象）===
malloc( 1) × 1000 → 真实占用 32000 字节（你以为用了 1000，放大 32.0 倍）
malloc( 8) × 1000 → 真实占用 32000 字节（你以为用了 8000，放大 4.0 倍）
malloc( 16) × 1000 → 真实占用 32000 字节（你以为用了 16000，放大 2.0 倍）
malloc( 24) × 1000 → 真实占用 32000 字节（你以为用了 24000，放大 1.3 倍）
malloc( 25) × 1000 → 真实占用 48000 字节（你以为用了 25000，放大 1.9 倍）
malloc(100) × 1000 → 真实占用 112000 字节（你以为用了 100000，放大 1.1 倍）三条结论：
| 结论 | 说明 |
|---|---|
| 最小块 32 字节 | malloc(1) 也要 32 字节——96.9% 是内部碎片 |
| 块大小按 16 字节分档 | 请求 1~24 都是 32；25~40 都是 48——每 16 字节一档 |
| 小对象必须成池 | 1000 个 malloc(1) 占 32 KB——这就是"对象池/内存池"的第一性理由 |
例 2：首次适配 vs 最佳适配
任务：对比两种策略的选择逻辑。
c
/* 伪代码：分配器的核心循环 */
void *first_fit(size_t n) {
for (块 = 链表头; 块 != NULL; 块 = 下一个(块))
if (块->size >= n) return 切分(块, n); /* 第一个够大的就用 */
return 扩展堆并分配(n);
}
void *best_fit(size_t n) {
最优 = NULL;
for (块 = 链表头; 块 != NULL; 块 = 下一个(块))
if (块->size >= n && (最优 == NULL || 块->size < 最优->size))
最优 = 块; /* 找"最小的够大的" */
return 最优 ? 切分(最优, n) : 扩展堆并分配(n);
}用 Python 在一个"有多个空闲块"的场景里对比：
python
import unicodedata
def w(s):
return sum(2 if unicodedata.east_asian_width(c) in "WF" else 1 for c in s)
def pad(s, n):
return s + " " * max(0, n - w(s))
# 先造出多个不同大小的空闲块：[已用][空 32][空 64][空 48][已用]
FREE = [32, 64, 48]
def pick_first(n):
for i, s in enumerate(FREE):
if s >= n:
return i, s
return -1, None
def pick_best(n):
best = None
for i, s in enumerate(FREE):
if s >= n and (best is None or s < FREE[best]):
best = i
return (best, FREE[best]) if best is not None else (-1, None)
print(" 空闲块（按地址顺序）：" + " → ".join(f"空{s}" for s in FREE))
print()
print(" " + pad("请求", 6) + pad("首次适配挑中", 14) + pad("剩余", 8)
+ pad("最佳适配挑中", 14) + pad("剩余", 8) + "对比")
for n in (24, 40, 56, 80):
i1, s1 = pick_first(n)
i2, s2 = pick_best(n)
a = f"空{s1}(剩 {s1-n})" if i1 >= 0 else "需扩堆"
b = f"空{s2}(剩 {s2-n})" if i2 >= 0 else "需扩堆"
same = "一致" if i1 == i2 else "不同"
print(" " + pad(str(n), 6) + pad(a, 14) + pad(str(s1 - n) if i1 >= 0 else "-", 8)
+ pad(b, 14) + pad(str(s2 - n) if i2 >= 0 else "-", 8) + same)
print("\n === 两种策略的取舍 ===")
print(" 首次适配：找到就停 → O(k) 就返回，快；但低地址的块被反复切，容易积小碎片")
print(" 最佳适配：必须看完全部 → O(全部块)，慢；剩余最小，但会留下 1~15 字节的'死碎片'")
print(" 取中：下一次适配（记住上次位置）；真解法：按大小分箱（glibc 的做法）")预期输出：
空闲块（按地址顺序）：空32 → 空64 → 空48
请求 首次适配挑中 剩余 最佳适配挑中 剩余 对比
24 空32(剩 8) 8 空32(剩 8) 8 一致
40 空64(剩 24) 24 空48(剩 8) 8 不同
56 空64(剩 8) 8 空64(剩 8) 8 一致
80 需扩堆 - 需扩堆 - 一致
=== 两种策略的取舍 ===
首次适配：找到就停 → O(k) 就返回，快；但低地址的块被反复切，容易积小碎片
最佳适配：必须看完全部 → O(全部块)，慢；剩余最小，但会留下 1~15 字节的'死碎片'
取中：下一次适配（记住上次位置）；真解法：按大小分箱（glibc 的做法）三条结论：
| 结论 | 说明 |
|---|---|
| 请求 40 时两者分歧 | 首次适配挑 64（剩 24），最佳适配挑 48（剩 8） |
| "最佳"不一定更好 | 剩 8 比剩 24 更接近"死碎片"——下次要 16 就用不上了 |
| 真实解是分箱 | 按大小分类，只在同类里找第一个——兼顾速度与碎片 |
例 3：碎片是怎么长出来的——以及"合并"救不救得了
任务：用"分配 → 释放 → 再分配"的序列制造外部碎片，看合并的作用。
c
/* 让两个空闲块"相邻但一个装不下"的经典序列 */
void *a = malloc(16);
void *b = malloc(16);
void *c = malloc(16);
void *d = malloc(16);
free(c); /* 挖两个相邻的洞 */
free(d);
void *e = malloc(24); /* 要 24：不合并 → 三个 16 都不够；合并 → 48 正好 */用 Python 模拟"有合并 vs 无合并"的差别：
python
import unicodedata
def w(s):
return sum(2 if unicodedata.east_asian_width(c) in "WF" else 1 for c in s)
def pad(s, n):
return s + " " * max(0, n - w(s))
def show(blocks, tag):
parts = []
for name, sz in blocks:
parts.append("[%s:%d]" % ("空" if name is None else name, sz))
print(" " + pad(tag, 16) + "".join(parts))
def first_fit(blocks, size):
for i, (name, sz) in enumerate(blocks):
if name is None and sz >= size:
rest = sz - size
newb = [("新", size)]
if rest > 0:
newb.append((None, rest))
return True, blocks[:i] + newb + blocks[i+1:]
return False, blocks
def coalesce(blocks):
out = []
for name, sz in blocks:
if name is None and out and out[-1][0] is None:
out[-1] = (None, out[-1][1] + sz)
else:
out.append((name, sz))
return out
def free_by(blocks, label):
for i, (nm, sz) in enumerate(list(blocks)):
if nm == label:
blocks[i] = (None, sz)
return blocks
for do_coalesce in (False, True):
tag = "有合并" if do_coalesce else "不合并"
print(f"=== {tag} ===")
blocks = [("a", 16), ("b", 16), ("c", 16), ("d", 16), (None, 16)]
show(blocks, "初始")
blocks = free_by(blocks, "c"); show(blocks, "free(c)")
blocks = free_by(blocks, "d"); show(blocks, "free(d)")
if do_coalesce:
blocks = coalesce(blocks); show(blocks, "合并后")
ok, blocks = first_fit(blocks, 24)
show(blocks, "malloc(24)")
frees = [sz for nm, sz in blocks if nm is None]
small = [s for s in frees if s < 24]
verdict = "有" if any(s >= 24 for s in frees) else "没有"
print(f" → malloc(24) {'成功' if ok else '失败'}；剩余空闲块 {frees}")
print(f" → 是否有连续 ≥24 的空闲？{verdict}"
+ (f"；不可用碎片（<24）{small}" if small else ""))
print()
print("=== 结论 ===")
print(" 不合并：三个 16 字节的洞，每个都 < 24 → 24 装不进去（外部碎片）")
print(" 有合并：c、d 与尾部空闲相邻 → 合成一块 48 → 分配成功")
print(" ★ 合并靠的是“块头里存着'前一块是否空闲'与'本块大小'”（回链第三节）")预期输出：
=== 不合并 ===
初始 [a:16][b:16][c:16][d:16][空:16]
free(c) [a:16][b:16][空:16][d:16][空:16]
free(d) [a:16][b:16][空:16][空:16][空:16]
malloc(24) [a:16][b:16][空:16][空:16][空:16]
→ malloc(24) 失败；剩余空闲块 [16, 16, 16]
→ 是否有连续 ≥24 的空闲？没有；不可用碎片（<24）[16, 16, 16]
=== 有合并 ===
初始 [a:16][b:16][c:16][d:16][空:16]
free(c) [a:16][b:16][空:16][d:16][空:16]
free(d) [a:16][b:16][空:16][空:16][空:16]
合并后 [a:16][b:16][空:48]
malloc(24) [a:16][b:16][新:24][空:24]
→ malloc(24) 成功；剩余空闲块 [24]
→ 是否有连续 ≥24 的空闲？有
=== 结论 ===
不合并：三个 16 字节的洞，每个都 < 24 → 24 装不进去（外部碎片）
有合并：c、d 与尾部空闲相邻 → 合成一块 48 → 分配成功
★ 合并靠的是“块头里存着'前一块是否空闲'与'本块大小'”（回链第三节）三条结论：
| 结论 | 说明 |
|---|---|
| 外部碎片的定义特征 | 总空闲够、但没有一个连续块够大（48 > 24 却分配失败） |
| 合并是对症药 | 相邻空闲块合成后立刻可用——所以"释放时顺手合并"是标配 |
| 紧凑才是根治 | 但 C 做不到（指针是裸地址，搬家会失效）——这是 C 与 GC 语言的分野 |
例 4：堆是怎么长大的——一次要一大块
任务：把"malloc 一次向内核要一大块"的账算清楚。
c
#include <stdio.h>
#include <stdlib.h>
int main(void) {
/* 10 万次小分配：如果每次都进内核就惨了 */
for (int i = 0; i < 100000; i++) {
void *p = malloc(16);
free(p); /* 立刻释放：同一个块被反复复用 */
}
return 0;
}用 Python 算两种策略的系统调用次数：
python
import unicodedata
def w(s):
return sum(2 if unicodedata.east_asian_width(c) in "WF" else 1 for c in s)
def pad(s, n):
return s + " " * max(0, n - w(s))
N = 100000
CHUNK, REQ = 32, 16 # glibc 的 16 字节请求 → 32 字节块
ARENA = 128 * 1024 # 一次向内核要 128 KiB
SYS_NS = 500 # 系统调用量级（回链 lang/05）
print("=== 策略 A：每次 malloc 都进内核（假想中的“无分配器”）===")
calls_a = N
time_a = calls_a * SYS_NS / 1e6
print(f" 分配次数 {N:,} → 系统调用 {calls_a:,} 次 → 约 {time_a:.0f} ms")
print(f"\n=== 策略 B：一次要 {ARENA // 1024} KiB，用户态自己切（真实 malloc）===")
per_arena = ARENA // CHUNK
arenas = -(- (N * 1) // per_arena) # 但注意：free 之后同一个块会被复用！
print(f" 一个 arena（{ARENA} 字节）能切出 {per_arena:,} 个 {CHUNK} 字节块")
print(f" 若每个块只用一次（不复用）：需要 {arenas} 个 arena → 系统调用 {arenas} 次")
print(f" ★ 但例中的代码是“分配后立刻 free”，分配器会把刚释放的块原样再给你")
print(f" → 实际永远只用 1 个块 → 系统调用仅 1 次（首次扩容）")
print(f" → 耗时约 {SYS_NS / 1e6:.3f} ms，而不是 {time_a:.0f} ms")
print("\n=== 倍数对比 ===")
print(" " + pad("策略", 30) + pad("系统调用次数", 14) + "耗时（量级）")
for name, c in (("每次进内核", N), ("一次要 128 KiB", 1)):
t = c * SYS_NS / 1e6
print(" " + pad(name, 30) + pad(f"{c:,}", 14)
+ (f"{t:.3f} ms" if t < 1 else f"{t:.0f} ms"))
print(f"\n 差距 ≈ {N:,} 倍")
print("\n=== 另一个数字：128 KiB 阈值 ===")
print(" glibc 对 >= 128 KiB 的请求改走 mmap（独立映射，free 时整块还给内核）")
print(" " + pad("请求大小", 14) + pad("路径", 12) + "free 时")
for r in (1024, 128 * 1024, 1024 * 1024):
path = "sbrk 堆" if r < 128 * 1024 else "mmap"
back = "归还给分配器的空闲链表" if path == "sbrk 堆" else "整块归还给内核"
print(" " + pad(f"{r // 1024} KiB", 14) + pad(path, 12) + back)预期输出：
=== 策略 A：每次 malloc 都进内核（假想中的“无分配器”）===
分配次数 100,000 → 系统调用 100,000 次 → 约 50 ms
=== 策略 B：一次要 128 KiB，用户态自己切（真实 malloc）===
一个 arena（131072 字节）能切出 4,096 个 32 字节块
若每个块只用一次（不复用）：需要 25 个 arena → 系统调用 25 次
★ 但例中的代码是“分配后立刻 free”，分配器会把刚释放的块原样再给你
→ 实际永远只用 1 个块 → 系统调用仅 1 次（首次扩容）
→ 耗时约 0.001 ms，而不是 50 ms
=== 倍数对比 ===
策略 系统调用次数 耗时（量级）
每次进内核 100,000 50 ms
一次要 128 KiB 1 0.001 ms
差距 ≈ 100,000 倍
=== 另一个数字：128 KiB 阈值 ===
glibc 对 >= 128 KiB 的请求改走 mmap（独立映射，free 时整块还给内核）
请求大小 路径 free 时
1 KiB sbrk 堆 归还给分配器的空闲链表
128 KiB mmap 整块归还给内核
1024 KiB mmap 整块归还给内核三条结论：
| 结论 | 说明 |
|---|---|
malloc 不是"每次问内核" | 它一次要 128 KiB，用户态自己切——差 5 个数量级 |
| "分配-释放-再分配"会被复用 | free 的块进入空闲链表，下次同样大小直接给——这也是"分配器为何要记空闲块"的意义 |
大块走 mmap | ≥128 KiB 独立映射，free 时整块还给内核——大内存不会长期占住堆 |
考点
考点
1. 栈 vs 堆（对比题）
- 栈：编译器管、LIFO、8 MiB 上限、零碎片、向下长；
- 堆：程序管、任意生命周期、几乎等于物理内存、有碎片、向上长；
- 栈上的地址不能返回（回链
lang/13）；堆上的地址能返回，但要记得free。
2. malloc 家族语义
malloc不清零、calloc清零；free(NULL)合法；free后指针值不变 → 必须p = NULL；- 只能
free由malloc/calloc/realloc返回的原地址； realloc可能搬家 → 必须p = realloc(p, n)；- 返回值必须检查
NULL。
3. 块头与开销（计算题）
- 块头 8 字节（存 size + flags）；
free靠它知道要还多少； chunk = max(32, align16(req + 8))；可用 = chunk − 8；malloc(1)占 32 字节；每 16 字节一档台阶；- flags 挤在 size 低位——因为块大小 16 对齐，低 3 位恒 0。
4. 三种适配策略
| 策略 | 规则 | 特点 |
|---|---|---|
| 首次适配 | 第一个够大的 | 快；低地址易积碎片 |
| 最佳适配 | 最小的够大的 | 碎片最小；慢；留死碎片 |
| 下次适配 | 从上次位置继续 | 分布较均匀 |
- 真实分配器（glibc）用"分离空闲链表（分箱）"——按大小分类，兼顾速度与碎片。
5. 碎片
- 内部碎片：块内用不到的部分（
malloc(1)→ 31 字节）； - 外部碎片：空闲总量够但无连续块（三个 16 装不下 24）；
- 合并（coalescing）：
free时与相邻空闲块合并——标配； - 紧凑（compaction）：C 做不到——因为指针是裸地址，搬家会失效；GC 语言能做，因为运行时知道类型与指针位置。
6. 向内核要内存
sbrk/brk：抬高堆顶；小请求走这条；mmap：≥128 KiB 的请求走独立匿名映射，free时能整块还内核；- 核心策略：一次要一大块、用户态自己切——"系统调用贵"（回链
lang/05）的直接推论。
7. 四类错误
- 泄漏：分配了没
free（尤其return路径）； - double free：同一个指针
free两次 → 破坏分配器结构； - use after free：
free后继续用（最难查、最常被利用）； - 堆溢出：越界写破坏下一块块头；
- 两条防御：① 检查返回值 ②
free后置NULL；再加"写入必带长度上限"。
8. 高频易错点
free(p + 1)非法（必须是原地址）；realloc后必须用返回值，别用旧指针；malloc(0)的行为是实现相关的（可能返回NULL，也可能返回一个可free的非空指针）；malloc的内存不含"边界信息"给用户——越界检查要靠工具（valgrind/ASan）；- "栈向上/堆向下"的直觉常搞反：栈向下长、堆向上长。
小结
- 栈有四条局限（生命周期短、大小编译期定、8 MiB 上限、不能部分释放），所以需要堆。
- 堆 = 程序自己管的内存：
malloc申请、free归还、想活多久活多久。 free不用传长度，是因为malloc在前面留了 8 字节块头（存 size + flags）。chunk = max(32, align16(req+8))：malloc(1)也要 32 字节——小对象必须成池。- 空闲块靠链表管理：隐式链表（靠 size 导航）/ 显式链表 / glibc 的分箱（分离空闲链表）。
- 三种适配：首次（快）、最佳（省但慢且留死碎片）、下次（折中）；真正解是分箱。
- 碎片两类：内部（块内浪费）/ 外部（空闲够但无连续块）；合并能治外部碎片，紧凑才是根治但 C 做不到。
- 两条"向内核要内存"的路：
sbrk（小请求、抬高堆顶）/mmap（≥128 KiB、可整块归还）；核心是"一次要一大块"。 - 四类错误：泄漏、double free、use after free、堆溢出；防御：检查返回值 + 用后置空 + 写入带长度。
realloc可能搬家，必须p = realloc(p, n)。
回到主线：到这里，"一个 C 程序内部的一切"都讲完了——类型、指针、布局、栈、堆。
但真实程序从不是"一个
.c文件"。#include <stdio.h>到底做了什么？为什么"声明"和"定义"要分开？为什么两个文件里写同一个全局变量会"重复定义"，而写同一个函数声明却没事？——下一篇：预处理、多文件编译、头文件。
下一篇：预处理、多文件编译、头文件
评论（0）
当前浏览器不允许本地存储，评论无法保存。
还没有评论，来说两句。