承接 lesson16 PMM 与 lesson17 VMM：已经能按页申请物理内存，也能建立页表映射。
本课目标：在「页」之上再做一层任意字节大小的内核堆，提供 kmalloc / kfree。

内核里到处是小对象：任务控制块、缓冲区描述符、文件系统节点……每次都 pmm_alloc_page() 会浪费大量内存，也不方便管理寿命。堆分配器是 PMM/VMM 之后最自然的下一层抽象。

---

一、为什么需要内核堆？

层级	接口	粒度	典型用途
PMM	pmm_alloc_page	4KB	页表页、大缓冲区、堆的「原料」
VMM	vmm_map_page	4KB 映射	虚拟地址布局
Heap	kmalloc / kfree	任意字节（对齐后）	内核小对象

可以继续用「仓库」类比：

• PMM：按整托盘进出货
• VMM：决定托盘放在仓库哪号货位
• Heap：把一托盘拆成小包裹发给各个科室，用完再收回拼回去

没有堆，后面做多任务 PCB、文件对象、管道缓冲都会非常别扭。

---

二、本课在学习链中的位置

PMM(物理页) → VMM(页表) → ★ kmalloc(堆) → 用户态 / 系统调用 / 文件系统
   16            17            18              19+

• lesson16：哪一页物理内存空闲？
• lesson17：虚拟地址对应哪一页？
• lesson18：给我 24 字节，用完还回去——不必关心页

本课堆建立在已恒等映射的物理页上：先 pmm_alloc_page 连续领取 16 页（64KB），再在这段线性地址上跑空闲链表。暂不引入「堆自动扩容 + 缺页」，把分配算法本身吃透。

---

三、核心概念：块头、空闲链、First-Fit、合并

3.1 堆区示意图

堆起始地址 →
┌──────────────┐
│ block A (free)│ → free_list[0]
└──────────────┘

┌──────────────┐
│ block B (used)│
└──────────────┘

┌──────────────┐
│ block C (free)│ → free_list[1]
└──────────────┘

┌──────────────┐
│ block D (used)│
└──────────────┘

┌──────────────┐
│ block E (free)│ → free_list[2]
└──────────────┘
← 堆结束地址

3.2 块（Block）长什么样？

堆被切成连续的「块」，每块前面有固定大小的块头，后面是调用方拿到的载荷（payload）：

+------------------+---------------------------+
| magic | size | … |  payload（kmalloc 返回值） |
+------------------+---------------------------+
      块头 16 字节              size 字节

本课块头字段：

字段	含义
magic	HEAP_MAGIC_USED / HEAP_MAGIC_FREE，防重复释放与野指针
size	载荷字节数（不含块头）
next	仅空闲块使用：串在空闲链表上
_pad	凑齐 16 字节，保证载荷 8 字节对齐

kmalloc 返回的是载荷地址，不是块头：

ptr = (uint8_t*)block + sizeof(heap_block_t)
kfree 时再 ptr - 头大小 → 找回块头

3.3 First-Fit（首次适应）

空闲块用链表串起来。分配时从链头往后扫，第一块足够大的就用：

• 优点：实现简单、分配快
• 缺点：链前部容易碎成小洞（外部碎片）

教学阶段足够；以后可换成 Best-Fit、Buddy、Slab 等。

3.4 拆分（Split）

若空闲块远大于需求，把尾巴拆成新的空闲块，避免「要 16 字节却吃掉整页剩余」。

本课规则：剩余部分至少还能再放下「一块头 + 最小对齐载荷」，才拆分。

3.5 合并（Coalesce）

kfree 后若物理上前后邻居也是空闲，就合并成更大块，否则堆会碎成无法满足稍大请求的碎片。

释放 B 之前:  [A 空闲][B 占用][C 空闲]
释放 B 之后:  [A+B+C 一大块空闲]   ← 理想情况

实现上：空闲链按地址升序排列，便于判断「下一块是否相邻」。

向后合并

释放块 B：

┌──────┐┌──────┐
│ B ││ C │ C 是空闲块 → 合并
└──────┘└──────┘

合并后：

┌───────────────┐
│ B’ │ size = B.size + header + C.size
└───────────────┘

向前合并

free_list 中有块 A：

┌──────┐┌──────┐
│ A ││ B │ B 是释放块 → 合并到 A
└──────┘└──────┘

合并后：

┌────────────────┐
│ A’ │
└────────────────┘

---

四、本课代码结构

文件	职责
kernel/heap.h / heap.c	堆初始化、kmalloc / kfree（本课核心）
kernel/pmm.* / vmm.*	物理页与分页（承接 16/17）
kernel/main.c	PMM→VMM→HEAP→分配冒烟测试

kernel_main
  ├─ pmm_init
  ├─ vmm_init
  ├─ heap_init          ← 连续领取 16 页，建成一大空闲块
  └─ kmalloc / kfree 演示

---

五、源码解析

5.1 heap_init：把页变成堆

for (i = 0; i < HEAP_PAGES; i++) {
    pages[i] = pmm_alloc_page();
    /* 要求 pages[i] == pages[0] + i * 4096 */
}
heap.start = (uint32_t)pages[0];
heap.end   = heap.start + HEAP_SIZE;

/* 整段做成一个大空闲块，挂到 free_list */
first->magic = HEAP_MAGIC_FREE;
first->size  = HEAP_SIZE - BLOCK_HEADER_SIZE;
free_list = first;

本课堆用单一线性区间 + 相邻块合并；恒等映射下线性地址 = 物理地址，页不连续就无法当成一块连续堆。PMM 的 first-fit 在低址空闲区通常能给出连续页；若失败会打印 pages not contiguous。

初始化运行后输出：

HEAP: init OK base=0x00015000 size=65536 free=65520

其中的 base=0x00015000 就是堆起始地址（heap.start）。后面 a=0x00015010 比它大一点，多出来的一般是块头元数据。

我们这里使用64K是简化做法，而对于现代化的操作系统来说，是有一块可扩展区域，不够再扩，而不是固定的。

5.2 kmalloc：对齐 → First-Fit → 可选拆分

need = align_up_size(size);          /* 向上到 8 字节 */
/* 遍历 free_list，找 size >= need 的第一块 */
/* 从空闲链摘下 → maybe_split → 标 USED → 返回载荷指针 */

统计字段：

• heap.used_bytes / free_bytes：载荷层面的占用（不含块头开销的精细账在拆分/合并时微调）
• heap.alloc_count：尚未 kfree 的次数

5.3 kfree：校验魔数 → 挂回空闲链 → 合并

b = ptr - HEADER;
if (magic == FREE)  → 双重释放，拒绝
if (magic != USED)  → 坏指针 / 踩踏，拒绝
标 FREE，插入地址有序空闲链，coalesce(b)

unmap 物理页仍归 PMM 管：本课 kfree 只把字节还回堆，不把 64KB 堆区还给 PMM。堆是内核长期持有的缓存池。

5.4 main.c 演示在证明什么？

1. kmalloc(16) / kmalloc(32) 得到不同指针，可读写
2. kfree 后 used 降、free 升、allocs 归零
3. 再 kmalloc(16)，在合并成功时往往复用原先 a 的地址（First-Fit 从堆头开始）

这证明：分配器能切开大块、回收、合并，而不是每次偷偷再向 PMM 要页。

---

六、和 PMM / VMM 的边界

操作	谁负责
堆初始化要页	pmm_alloc_page × N
堆地址可访问	lesson17 恒等映射（页已在 0…16MB）
24 字节对象	kmalloc
再要一张页表	仍走 pmm_alloc_page，不经过堆

原则：页级资源走 PMM，对象级资源走 Heap，不要混用导致「一半按页释放、一半按块释放」的混乱。

---

七、本课刻意简化的点

主题	说明
堆扩容	固定 64KB；用尽即 kmalloc 失败，不会自动 map 新页
多核锁	单核无锁；对称多处理时 kmalloc 需加自旋锁
对齐超大对象	未实现 posix_memalign；大块可直接 PMM
Buddy / Slab	性能与碎片更好，但概念更重，留给后续
用户态 malloc	需独立堆或 brk/mmap 系统调用，本课仅内核

---

八、构建与运行

cd lesson18
make
make install
make run

预期输出（要点）

Lesson18: Kernel Heap (kmalloc)
=== PMM Init ===
=== VMM Init ===
VMM: paging ON ...
=== HEAP Init ===
HEAP: init OK  base=0x........  size=65536  free=...
=== kmalloc Demo ===
a=0x........  b=0x........
write/read: OK
used=...  free=...  allocs=2
after kfree: used=0  free=...  allocs=0
realloc c=0x........  (reused a OK)
Done. PMM free pages: ...

关注：write/read: OK、kfree 后 allocs=0、再次分配尽量出现 reused a OK。

---

九、建议实验

1. 把 HEAP_PAGES 改成 4，反复 kmalloc 直到失败，观察行为
2. 分配三个块，只释放中间一块，再申请更大块——体会合并与碎片
3. 故意 kfree(a) 两次，确认打印 double free
4. 对比：同样存 100 个 32 字节对象，用堆 vs 每次 pmm_alloc_page 的页消耗

---

十、小结

本课在页分配器之上补齐了内核最常用的内存接口：

• 用块头 + 空闲链表 + First-Fit 实现 kmalloc / kfree
• 支持拆分与相邻合并，减轻外部碎片
• 用魔数做一次基础的错误检测

---

参考

• lesson16 物理内存管理（PMM）
• lesson17 分页与虚拟内存（VMM）
• 《自己动手写操作系统》中与内存管理 / malloc 相关章节
  代码开源地址：
  https://gitee.com/xundh/learn-os