2026/7/16大约 6 分钟内核组件内核内存管理FIRSTFIT
FIRSTFIT 算法
📚 本节导读
学习时长: 约 20 分钟
难度级别: ⭐⭐⭐☆☆
前置知识: 4.4.1 堆内存管理、链表数据结构
FIRSTFIT（首次适应）算法是 OneOS 支持的一种经典内存分配算法。它通过维护空闲块链表，在分配时从链表头部开始扫描，找到第一个足够大的空闲块即进行分配。该算法实现简单、分配速度快，是嵌入式系统的常用选择。
🎯 学习目标
- 理解 FIRSTFIT 算法的核心思想和工作流程
- 了解 FIRSTFIT 的内部数据结构（chunk、bucket）
- 掌握 FIRSTFIT 的优缺点
- 明确 FIRSTFIT 的适用场景
一、配置
#define OS_USING_ALG_FIRSTFIT当定义了 OS_USING_ALG_FIRSTFIT 且未定义 OS_USING_ALG_BUDDY 时，OS_MEM_ALG_DEFAULT 将使用 FIRSTFIT 算法。
源文件：kernel/source/os_mem_firstfit.c
二、算法原理
2.1 核心思想
FIRSTFIT 维护一个按大小分桶的空闲块链表。分配时，从对应大小的桶开始扫描，找到第一个满足请求大小的空闲块即进行分配。
┌──────────────────────────────────────────────────────────────────┐
│ FIRSTFIT 分配流程 │
│ │
│ 分配请求(size) │
│ │ │
│ ▼ │
│ ┌─────────────┐ │
│ │ 计算需要的 │ │
│ │ chunk 大小 │ │
│ └──────┬──────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────────────────────────────────┐ │
│ │ 从对应 bucket 开始扫描空闲链表 │ │
│ │ │ │
│ │ bucket[0] → [8B] ⇄ [8B] │ │
│ │ bucket[1] → [16B] ⇄ [16B] │ │
│ │ bucket[2] → [32B] ⇄ [32B] │ │
│ │ ... │ │
│ │ bucket[n] → [2^n×8B] │ │
│ └──────────────────────┬──────────────────────┘ │
│ │ │
│ ┌───────────┴───────────┐ │
│ ▼ ▼ │
│ ┌─────────────┐ ┌─────────────┐ │
│ │ 找到合适的块 │ │ 未找到 │ │
│ │ 分配并切分 │ │ 返回 NULL │ │
│ │ 剩余部分放回 │ │ │ │
│ └─────────────┘ └─────────────┘ │
└──────────────────────────────────────────────────────────────────┘2.2 分配策略
FIRSTFIT 的分配采用近似最佳匹配策略：
- 优先尝试精确桶：从请求大小对应的 bucket 开始，最多尝试
CONFIG_SYS_HEAP_ALLOC_LOOPS（默认为 8）个块 - 回退到更大桶：如果精确桶中找不到合适的块，从更大的桶中取最小可用块
- 切分剩余空间：如果找到的块大于请求大小，将其切分为已分配块和剩余空闲块，剩余部分重新加入空闲链表
2.3 释放与合并
释放内存时，FIRSTFIT 尝试与相邻空闲块合并：
释放前： [已用块A] [空闲块B] [已用块C]
释放A： [空闲块A] [空闲块B] [已用块C]
↓ 合并
合并后： [空闲块A+B(更大)] [已用块C]合并策略：先尝试与右侧空闲块合并，再尝试与左侧空闲块合并。
三、内部数据结构
3.1 Chunk（内存块）
FIRSTFIT 以 chunk 为基本管理单位，每个 chunk 大小为 CHUNK_UNIT（8 字节）。所有 chunk 从堆起始地址开始连续编号。
每个 chunk 包含以下字段：
┌────────────────────────────────────────────────────────────┐
│ Chunk 结构 │
│ │
│ ┌──────────┬───────────────┬──────────────────────────┐ │
│ │ LEFT_SIZE│ SIZE_AND_USED │ 数据区 / 空闲指针 │ │
│ │ (左邻大小)│ (大小+使用标志)│ │ │
│ └──────────┴───────────────┴──────────────────────────┘ │
│ │
│ 已用块: LEFT_SIZE | SIZE_AND_USED | 用户数据 │
│ 空闲块: LEFT_SIZE | SIZE_AND_USED | FREE_PREV | FREE_NEXT │
│ │
│ (启用 OS_USING_MEM_TRACE 时) │
│ 已用块: LEFT_SIZE | SIZE_AND_USED | TASK_ID | 用户数据 │
└────────────────────────────────────────────────────────────┘- LEFT_SIZE：左侧相邻 chunk 的大小（chunk 单位），用于反向遍历
- SIZE_AND_USED：当前 chunk 的大小（chunk 单位），最低位为使用标志（1 = 已用，0 = 空闲）
- FREE_PREV / FREE_NEXT：空闲链表中的前驱和后继指针（仅空闲块有效）
- TASK_ID：分配该块的当前任务指针（仅当
OS_USING_MEM_TRACE启用时）
3.2 Bucket 桶
空闲块按大小分桶管理，每个桶是一个双向循环链表：
struct z_heap_bucket
{
chunkid_t next; /* 桶中第一个空闲块的 chunk ID */
};
struct z_heap
{
uint64_t chunk0_hdr_area;
uint32_t len; /* 总 chunk 数 */
uint32_t avail_buckets; /* 位图，标记哪些桶非空 */
struct z_heap_bucket *buckets; /* 桶数组 */
};桶索引通过 __builtin_clz 指令快速计算，实现 O(1) 查找目标桶。
3.3 大小端适配
FIRSTFIT 根据堆大小自动选择字段宽度：
| 堆大小 | 字段宽度 | 最大支持 |
|---|---|---|
| ≤ 256KB | 16 位 | 0x7FFF 个 chunk |
| > 256KB | 32 位 | 约 16GB 堆空间 |
由 _k_big_heap() 函数自动判断。
四、优缺点分析
4.1 优点
| 优点 | 说明 |
|---|---|
| 分配速度快 | 从桶中直接取第一个足够大的块，常数时间操作 |
| 实现简单 | 代码结构清晰，易于理解和维护 |
| 内存利用率高 | 切分大块，剩余部分可继续使用 |
| 自动合并 | 释放时自动与相邻空闲块合并，减少碎片 |
| 自适应字段宽度 | 根据堆大小自动选择 16 位或 32 位字段，节省元数据开销 |
4.2 缺点
| 缺点 | 说明 |
|---|---|
| 外部碎片 | 长时间运行后，频繁分配/释放不同大小的块可能产生碎片 |
| 非确定性分配时间 | 最坏情况下可能需要扫描多个桶 |
| 元数据开销 | 每个 chunk 至少需要 4~8 字节的头部信息 |
五、适用场景
FIRSTFIT 算法适合以下场景：
- ✅ 通用嵌入式应用：内存分配模式多样化，不要求最坏情况确定性
- ✅ 内存资源有限：字段宽度自适应，节省元数据存储
- ✅ 简单应用：不需要复杂的碎片管理策略
- ✅ 快速原型开发：实现简单，调试方便
以下场景建议考虑 BUDDY 算法：
- ❌ 频繁分配和释放小块内存
- ❌ 对内存碎片非常敏感的系统
- ❌ 需要更可预测的分配行为
六、内部工作流程
6.1 初始化
_k_firstfit_mem_init()
│
├── 创建信号量 (用于并发保护)
├── 对齐内存起始地址到 CHUNK_UNIT
├── 初始化 z_heap 结构体
│ ├── 设置 chunk 总数
│ ├── 创建 bucket 数组
│ └── 初始化 bucket 为空
├── 创建 chunk0 (管理开销)
├── 创建初始空闲 chunk (覆盖剩余所有空间)
└── 将初始空闲 chunk 加入空闲链表6.2 分配流程
_k_firstfit_mem_alloc()
│
├── 计算所需 chunk 大小
├── 获取信号量
│
├── _k_alloc_chunk()
│ ├── 从精确桶开始扫描 (最多 8 个块)
│ │ └── 找到 → 从链表移除，返回该 chunk
│ └── 从更大桶中取最小可用块
│
├── 如果需要切分 → _k_split_chunks()
│ └── 剩余部分重新加入空闲链表
├── 标记 chunk 为已用
├── 记录分配任务 (OS_USING_MEM_TRACE 时)
└── 释放信号量，返回数据指针6.3 释放流程
_k_firstfit_mem_free()
│
├── 获取信号量
├── 验证 chunk 状态 (检测 double-free)
├── 验证内存边界 (检测缓冲区溢出)
├── 标记 chunk 为空闲
├── _k_free_chunk()
│ ├── 尝试与右侧空闲块合并
│ └── 尝试与左侧空闲块合并
│ └── 合并后重新加入空闲链表
└── 释放信号量📝 本节小结
- FIRSTFIT 算法从空闲链表中找到第一个足够大的块进行分配，实现简单高效
- 内部以 chunk（8 字节）为基本单位，按大小分桶管理空闲块
- 分配时优先尝试精确桶（最多 8 次尝试），失败后从更大桶取最小块
- 释放时自动与相邻空闲块合并，减少外部碎片
- 字段宽度根据堆大小自动选择 16 位或 32 位，节省元数据开销
- 适合通用嵌入式应用，但对频繁分配/释放小块内存的场景可能产生碎片