最近在整理操作系统内核课程的一次实验时，我把“空闲内存的构建过程”从头到尾自己实现了一遍。这里说的“空闲内存构建”，不是单纯地在系统里看几行free -m的剩余量，而是真正从物理内存探测结束之后，把可用的内存页组织成一个可供分配器使用的结构：空闲页链表、位图、伙伴系统的多级空闲块数组，这些都属于“构建空闲内存”的范畴。如果你正在写小型内核、嵌入式固件，或者想理解 Linux 内核在启动早期对物理内存做了什么，这篇内容应该能帮上忙。
我现在遇到的环境是某高校操作系统课程配套的自制内核实验框架，平台是 32 位 ARM 模拟器，内存总量 256MB。实验要求很直接：在内存探测之后，把可用物理页面按照 4KB 页粒度建立好空闲内存池，然后实现最基础的分配与释放接口。看起来简单，真正写起来有不少细节，尤其是伙伴系统中空闲内存的初始构建，第一版我踩了不少坑，后面逐个归纳成了一套比较稳的步骤。下面分几个部分把整个构建过程、数据结构、边界问题、排错经验讲清楚。
1. 空闲内存构建到底在解决什么问题
1.1 为什么要在程序运行前先把空闲内存准备好
操作系统、嵌入式内核这类软件，都有一个共同的麻烦：内存是一块连续的物理地址空间，但程序上电之后，并不知道哪些地址能用、哪些地址被硬件映射占用、哪些区域属于保留区。如果分配程序在运行期临时扫描整块内存再决定返回哪里，性能差还好说，更致命的是会产生大量碎片，而且无法保证分配时间可控。
所以大多数内核的做法是：在系统启动早期，先做一次“内存盘点”，把物理内存中可用的部分切分成固定大小的页，然后用一个全局结构把所有空闲页串起来。这一步就是空闲内存的构建过程。构建完成之后，后续的malloc、进程页表分配、内核对象分配，都从这棵已经建好的空闲内存树上取页；释放的时候再挂回去。相当于你在营业之前先把货架摆好、货物分门别类入库，顾客来了直接取货，而不是现去仓库里翻。
我在实验里最直观的感受是：如果不做这个初始化，分配函数每次都要去读内存控制器寄存器，还得判断某块地址是不是被占用的，代码逻辑非常难维护。一旦把所有可用内存归一到free_area结构里，分配和释放就变成纯粹的数据结构操作，简单、可测试、可独立验证。
1.2 方案选型：位图、空闲链表、伙伴系统怎么选
构建空闲内存不是只有一种方法。我实验时纠结过三条路线，也分别做了小规模对比。
位图法：用一块内存记录每个页面的占用状态，0 表示空闲、1 表示已分配。优点是内存开销极小，256MB 内存 / 4KB 页大小只需要 256MB / 4096 / 8 = 8KB 位图空间；缺点是分配页面时要线性扫描位图，找到连续空闲页效率低，而且释放时合并相邻空闲页不直观。
空闲链表法：把每个空闲页的首部嵌入一个链表节点，所有空闲页串成一条或多条链表。分配时从头部取一页 O(1)，释放时把页面挂回去也是 O(1)，但处理连续多页分配时需要遍历链表找连续区间，碎片问题会比较明显。
伙伴系统：把空闲内存按大小分级，比如 4KB、8KB、16KB 直到最大块。分配时找最小满足需求的块，找不到就分裂更大块；释放时检查相邻块是否也是空闲的，如果是就合并回更大块。这是目前内核最常用的方案，也是实验要求的方向。
我在实际选择时没有盲目照搬完整内核的做法，而是先实现了一套简化版：用伙伴系统作为顶层分配策略，同时保留每页头的struct page结构记录状态。这样既满足课程实验要求，又能把构建过程拆得很清楚。
后续内容我都按这套方案展开。
1.3 我选择的小规模内存管理模型
为了不把复杂度一次拉满，我把模型缩小为：
- 页大小固定 4KB；
- 内存区域为一个连续物理段，起始地址是模拟器规定的
0x60000000，大小 256MB； - 保留低端 1MB 给内核镜像、页表、位图、各管理结构使用；
- 空闲内存从
0x60100000开始构建，到0x6FFFFFFF结束； - 伙伴系统最大阶数
MAX_ORDER = 10，也就是最大连续块为 4KB × 2^10 = 4MB。
这样做的好处是：地址计算很简单，调试时一眼能算出页号；同时保留区和空闲区界限清晰，不会出现把页表自己覆盖掉的问题。
2. 核心数据结构设计
2.1 物理内存布局与页结构体
要让空闲内存构建过程可控，第一步是定义“页”的抽象。在内核里，每个物理页对应一个描述结构，这里我简化成：
struct page { uint32_t flags; // 页面状态标志：PG_reserved、PG_free uint32_t order; // 伙伴系统阶数，仅在空闲块头部有效 struct page *free_list_next; struct page *free_list_prev; uint32_t refcnt; // 引用计数 uint32_t pfn; // 物理帧号，物理地址 >> 12 };这个结构本身存放在一个固定数组struct page mem_map[PAGE_COUNT]里，数组放在保留区，不参与空闲内存构建。刚开始我犯过一个错：把mem_map放进了空闲内存范围，结果初始化链表时第一个被链入的页面正好是存放struct page数组的内存，后续修改链表指针时直接把自己的描述结构写坏，表现为链表随机断链、分配函数偶发返回错误地址。
所以物理布局必须提前画好，我在实验文档里给出了一张表：
| 区域 | 地址范围 | 用途 |
|---|---|---|
| 保留区 | 0x60000000 - 0x600FFFFF | 内核镜像、页表、mem_map、位图 |
| 空闲区 | 0x60100000 - 0x6FFFFFFF | 可供构建的空闲内存页 |
| 设备映射区 | 0x70000000 - 0xFFFFFFFF | 外设 I/O 映射，不参与 |
这个布局看起来简单，但它直接决定了空闲内存构建的起点和终点，写代码前必须先定死，否则后面地址换算全是糊涂账。
2.2 空闲页链表与 free_area 数组
伙伴系统不是一条链表走天下，而是用一个数组free_area[MAX_ORDER]管理不同大小的空闲块。数组第order项是一个双向链表的头，链表里每个节点表示一个大小为2^order页的空闲连续块。
typedef struct free_area_struct { struct page *next; struct page *prev; uint32_t nr_free; } free_area_t; static free_area_t free_area[MAX_ORDER];构建空闲内存时，并不是把所有空闲页一股脑串到free_area[0]，而是要把整块可用内存先划分成尽可能大的块，再挂到对应阶数的链表中。例如从0x60100000到0x6FFFFFFF共有 63MB 可用内存，先切出一个最大的 2 的幂次块，也就是 32MB（2^13 页）挂到free_area[13]，但这里我设计的MAX_ORDER=10只能到 4MB，所以实际上最大块是 4MB。第二次构建时，我刻意把MAX_ORDER保持一致，以 4MB 为最大块，先不断地切 4MB 块挂在free_area[10]上，剩余不足 4MB 的部分再依次切成 2MB、1MB……直到剩余的零头挂进free_area[0]。
这就是“构建”的核心动作：把一段连续内存按 2 的幂次块拆分，分散到不同阶的空闲链表中，而不是全堆在最小的链表里。否则后续分配大内存时需要反复分裂，效率低且容易失败。
2.3 位图的作用和边界问题
实现伙伴系统时，需要知道一个块是否可以与相邻块合并。最简单的是看相邻块的头节点是否挂在同一个free_area[order]链表中，但判断“相邻块是否空闲且阶数相同”还需要额外的标志位。内核里用了 PageBuddy 这类页标志，我实现时给struct page的flags留了两位。
还有一个更经典的做法：使用分配状态位图unsigned long mem_map_bits[BITMAP_LEN]，每一位表示一个物理页是否被分配。构建空闲内存前把所有位清 0，表示全部空闲；把某个页加入空闲链表时该位保持 0，分配出去时置 1，释放时再清 0。
这里有个边界问题：位图本身要占一块内存，构建空闲内存的代码必须在位图初始化之后才能使用“取页/放页”的函数。我第一版在初始化位图之前就调用了list_add往free_area里挂页，结果位图区域被当作普通空闲页链入链表，然后又被分配给了内核对象，导致位图内容被覆盖。排查了很久才意识到，初始化顺序必须是：
- 计算物理页总数；
- 定位位图所在内存地址；
- 清空位图；
- 初始化 mem_map 数组；
- 再构建空闲链表。
3. 构建过程实现
3.1 初始化入口与内存探测
在实验中，我把入口函数定义成：
void mem_init(void) { uint32_t mem_start = 0x60100000; uint32_t mem_end = 0x6FFFFFFF; uint32_t page_count = (mem_end - mem_start) / PAGE_SIZE; bitmap_init(mem_start, page_count); mem_map_init(mem_start, page_count); free_area_init(mem_start, page_count); }mem_map_init的主要工作是给每个页的struct page填充pfn、flags，并把链表指针置空。这里有一个容易漏掉的点：物理内存模拟器可能没有完全按 4KB 对齐结束，比如mem_end是0x6FFFF123，那最后不足一页的尾巴不能计入空闲内存，直接丢弃。不能四舍五入成整数页，否则分配器会把不存在的内存页返回给调用者，一旦访问，模拟器直接异常退出。
探测物理内存大小这件事，模拟器环境里我直接用了链接脚本里定义的mem_end常量，并不复杂。如果换到真实硬件，需要解析设备树或内存控制器寄存器，但构建空闲内存的核心逻辑是一样的：确定可用区间的起始和结束地址，然后进入页管理阶段。
3.2 按页粒度建立空闲链表
最简单的构建方式是遍历所有可用页，把每个页节点用list_add_tail挂到free_area[0]链表尾部。这个“暴力构建”虽然能跑，但有一个问题：分配 64KB 内存时需要连续取 16 页，每次都从低地址页开始取，如果中间有一页被占用，后面即使有超过 16 个连续空闲页，也没法直接分配，只能遍历碎片集合拼接。所以实验要求的是伙伴系统，构建时就应该按块入链。
一个更接近内核的构建步骤是：
void free_area_init(uint32_t start, uint32_t end) { uint32_t addr = start; uint32_t order; uint32_t block; while (addr < end) { block = end - addr; order = __fls(block >> PAGE_SHIFT); if (order > MAX_ORDER - 1) order = MAX_ORDER - 1; if ((1 << order) * PAGE_SIZE > block) order--; while (order >= 0) { if (((1 << order) * PAGE_SIZE) <= block) { expand_zone(addr, order); addr += (1 << order) * PAGE_SIZE; block = end - addr; } order--; } } }expand_zone的职责是：把大小为2^order页的连续块的首个页节点初始化好，设置order字段，然后把块挂入free_area[order]。
这种构建方式保证了内存从一开始就是“大块链 + 小块链”的组合，后续分配大内存时，不需要从零开始分裂。
3.3 配合伙伴系统建立多级空闲块
最关键的是伙伴系统的多级结构。我定义了一个max_order = 10，可用内存 63MB。在free_area_init里循环时，会先尝试挂最大 4MB 的块：
- 63MB 可以切 15 个完整的 4MB 块，共 60MB；
- 剩余 3MB；
- 3MB 再切一个 2MB 块，剩余 1MB；
- 1MB 再切一个 1MB 块，剩余 0；
- 所以最后
free_area[10]有 15 个节点，free_area[9]有 1 个节点，free_area[8]有 1 个节点。
我特意加了调试打印，输出每个阶数的块数量。实际执行后：
free_area[10]: nr_free=15 free_area[9]: nr_free=1 free_area[8]: nr_free=1 free_area[0]: nr_free=0这说明构建过程符合预期。如果哪个阶数突然多了很多小块，说明构建时没有优先挂大块，而是把所有内存拆成了 4KB 小页，这种实现虽然也能跑，但失去了伙伴系统的意义。建议每位做类似实验的人都在初始化后打印一遍nr_free，对照内存总量验算是否一致：
总内存页数应该等于sum(nr_free[order] << order)。我那次验算是：
15×2^10 + 1×2^9 + 1×2^8 = 15360 + 512 + 256 = 16128 页，16128 × 4KB = 63MB。对上了。
4. 空闲内存的分配与回收联动
构建空闲内存只是第一步，它和后面分配、释放函数是联动关系。如果分配函数从free_area[0]拿了一个 4KB 小页，但链表里的小页已经被借用成大块了，就会导致重复分配。
4.1 分配时如何取空闲页
伙伴系统分配的核心是“找最小满足的块，必要时分裂”。我实现的简化版alloc_pages如下：
struct page *alloc_pages(uint32_t order) { uint32_t current_order; struct page *page; for (current_order = order; current_order < MAX_ORDER; current_order++) { if (!list_empty(&free_area[current_order])) { page = list_first_entry(&free_area[current_order], struct page, free_list_next); list_del(page); split_page(page, current_order, order); return page; } } return NULL; }注意split_page分裂时，要把多余的页块重新挂到低阶链表。这里的“重新挂回”就是又一次空闲内存构建过程：将原来高阶的大块拆成两部分，一部分返回给调用者，另一部分要立即构建成新的空闲块，挂在order-1对应链表上。所以“构建空闲块”不是一个只在启动初始化时执行的函数，而是每次分裂和每次释放合并时都在反复发生的动作。
4.2 释放与相邻合并
释放内存时不只是把页头挂回去，还要检查它和相邻的伙伴块是否同为空闲，如果同为空闲则合并成更大的空闲块，并继续往上尝试合并。判断伙伴的经典方法是通过物理页号异或：
buddy_pfn = page_pfn ^ (1 << order);如果mem_map[bndy_pfn].flags显示该块为空闲，并且它的阶数等于当前order，就可以从链表中摘下来，合并成一个新块。我在实现时连续写了几个if来判断边界，结果漏掉了一种情况：当要释放的页正好处于整个内存区间的起点时，它的伙伴在低地址方向可能越界。所以合并前必须检查：
if ((page_pfn & ((1 << order) - 1)) == 0) { return; // 该块不是某个更高阶块的右半部分，不能向上合并 }这个位运算检查的意义是：一个2^order大小的块的起始页号必须是2^order的整数倍，如果不是，说明它根本不属于这个阶层的“对齐块”，更不可能有合法的伙伴。这块不处理，释放函数会把不属于自己的内存也合并进来，破坏空闲内存池。
5. 常见问题与排查实录
5.1 链表节点被覆盖的典型特征
第一次跑完初始化，我用一个简单的测试循环分配 100 页，结果第二次分配时list_first_entry返回了空指针。查了很久，发现并不是链表真的空，而是free_area[0]链表头里被写入了全 0。原因是mem_map数组被放置在了保留区外，而初始化空闲链表时把这块内存挂进了空闲页表，随即又分配出去，指针操作破坏了链表的头节点。
定位这个问题的办法是加一个看门狗校验：每隔一段时间调用validate_free_lists()，遍历所有free_area链表，检查每个节点的page->magic是否等于预设值。我把magic放在struct page尾部，被覆盖的块会立刻暴露出来。
这个小工具建议每个人都在内核调试早期加上，它给我的收益远大于写一个完整调试器。
5.2 低端内存被分配导致页表损坏
有另一个问题：系统页表本身存放在0x60008000附近，我初始化的保留区只保留了 1MB。按理说不会动到页表，但我在位图初始化时用了一个大数组作为位图，而这个数组靠memset清零时把0x60008000后面的 32KB 覆盖了。现象是系统一旦开启分页立刻 page fault。
后来我把位图定义成静态数组，并且在链接脚本里加入. = ALIGN(4096);，确保位图和页表地址不重叠。实际教训是：初始化代码里所有大数组都要放到专门的数据段，并且地址要对齐到页边界，避免和硬件结构冲突。
5.3 伙伴合并失败的检查清单
合并逻辑看起来简单，但非常容易出小错。我整理了以下几种失败场景：
| 现象 | 可能原因 | 检查方式 |
|---|---|---|
| 释放 64KB 后总内存不变 | 相邻块不是空闲块 | 检查 buddy 页标志是否真的 PG_free |
| 释放后出现重复地址分配 | 合并时未检查块对齐 | 检查页号是否满足pfn % (1<<order)==0 |
| 合并后链表死循环 | 两个块头节点被同时链入同一条链表 | 关闭所有中断后单步看链表指针 |
| 大块释放后分裂碎片越来越多 | 释放时 order 值错误 | 打印释放块的page->order |
对每个场景，我都在初始化函数里加了断言：
BUG_ON(page->refcnt != 0); BUG_ON(addr % PAGE_SIZE != 0);当然，前提是 BUG_ON 之前已经把系统日志串口驱动拉起来，否则死在循环里没法定位。
5.4 并发访问空闲链表的安全问题
实验到后期，我开了两个核心来跑分配测试，结果出现偶发失败：两个 CPU 同时从free_area[0]取页，都取到了同一个页。原因很明显，构建的空闲链表没有保护机制。
解决办法是在alloc_pages和__free_pages入口处加自旋锁，锁住整个链表操作：
static spinlock_t free_list_lock = SPINLOCK_UNLOCKED; struct page *alloc_pages(uint32_t order) { unsigned long flags; struct page *page; spin_lock_irqsave(&free_list_lock, flags); page = __alloc_pages_inner(order); spin_unlock_irqrestore(&free_list_lock, flags); return page; }这里要强调，锁的保护范围必须覆盖分裂、入链、合并全过程，不能只锁一个list_del，否则释放路径会插入半个状态。加锁之后，并发压力测试连续跑了几万次分配释放，没有再出现重复分配。如果有兴趣做更精细的优化，可以对每个free_area[order]用独立锁，减少锁竞争，但课程实验里全局一把锁足够。
6. 我的一点课后补充
在整个实验环境里重建空闲内存池，给我留下的最深印象是：内存管理的绝大部分问题，在“构建阶段”就已经决定了。边界是否对齐、位图是否被覆盖、链表节点是否初始化完整，这些问题如果在构建时没有处理干净，后面分配越频繁，问题被放大得越厉害。
我给同实验组的同学分享过一个习惯：每次实现完构建流程，先写一个统计工具，把各阶空闲块数量和总和打印出来，再跑一遍分配释放随机序列，最后再打印一次统计。两次结果应该完全一致。这个简单闭环能过滤掉绝大多数链表污染、重复分配、越界合并问题。花十分钟写这个工具，比后期两天半夜调 bug 划算得多。
这个思路还可以继续扩展：把位图换成更精细的 per-CPU 页表缓存、给每个页增加 slab 内核对象缓存等，都是很自然的后续路径。不过基于标题“关于空闲内存的构建过程”，最核心的还是先把从连续物理内存到多级空闲链表这一步走扎实，后面的优化都是在这块地基上做文章。
