最近在整理操作系统内核课程的一次实验时我把“空闲内存的构建过程”从头到尾自己实现了一遍。这里说的“空闲内存构建”不是单纯地在系统里看几行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 的幂次块也就是 32MB2^13 页挂到free_area[13]但这里我设计的MAX_ORDER10只能到 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剩余 3MB3MB 再切一个 2MB 块剩余 1MB1MB 再切一个 1MB 块剩余 0所以最后free_area[10]有 15 个节点free_area[9]有 1 个节点free_area[8]有 1 个节点。我特意加了调试打印输出每个阶数的块数量。实际执行后free_area[10]: nr_free15 free_area[9]: nr_free1 free_area[8]: nr_free1 free_area[0]: nr_free0这说明构建过程符合预期。如果哪个阶数突然多了很多小块说明构建时没有优先挂大块而是把所有内存拆成了 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 % (1order)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 内核对象缓存等都是很自然的后续路径。不过基于标题“关于空闲内存的构建过程”最核心的还是先把从连续物理内存到多级空闲链表这一步走扎实后面的优化都是在这块地基上做文章。