2026/7/16大约 7 分钟内核组件内核内存管理BUDDY
BUDDY 算法
📚 本节导读
学习时长: 约 25 分钟
难度级别: ⭐⭐⭐☆☆
前置知识: 4.4.1 堆内存管理、2 的幂次方运算
BUDDY（伙伴系统）算法是 OneOS 支持的另一种内存分配算法。它基于 2 的幂次方大小管理内存，通过伙伴块的分裂和合并操作，在分配灵活性和碎片控制之间取得良好平衡。BUDDY 算法特别适合需要频繁分配和释放内存的场景。
🎯 学习目标
- 理解 BUDDY 算法的核心思想：伙伴分裂与合并
- 了解 BUDDY 的内部数据结构（层级管理、伙伴块）
- 掌握 BUDDY 算法的优缺点
- 能够对比 FIRSTFIT 和 BUDDY，选择适合场景的算法
一、配置
#define OS_USING_ALG_BUDDY当定义了 OS_USING_ALG_BUDDY 且未定义 OS_USING_ALG_FIRSTFIT 时，OS_MEM_ALG_DEFAULT 将使用 BUDDY 算法。
源文件：kernel/source/os_mem_buddy.c
二、算法原理
2.1 核心思想
BUDDY 算法将内存划分为 2 的幂次方大小的块（block），每个块有一个"伙伴"（buddy）——即相邻的、大小相同的块。两个伙伴块可以合并为一个更大的块。
┌──────────────────────────────────────────────────────────────────┐
│ BUDDY 伙伴系统原理 │
│ │
│ Level 0: [ 128B ] │
│ │
│ Level 1: [ 64B ][ 64B ] ← 伙伴关系 │
│ │
│ Level 2: [ 32B ][ 32B ][ 32B ][ 32B ] ← 伙伴关系 │
│ │
│ Level 3: [16B][16B][16B][16B][16B][16B][16B][16B] │
│ │
│ 伙伴关系：ID 为 0 和 1 的块是伙伴，2 和 3 是伙伴，以此类推 │
│ BLK_ID_TO_BUDDY_ID(id) = (id & 0x1) ? (id - 1) : (id + 1) │
└──────────────────────────────────────────────────────────────────┘2.2 分裂（Split）
当请求的大小小于当前可用块时，将大块不断分裂为两个更小的伙伴块，直到分裂出合适的大小。
分裂过程（请求 32B，当前只有 128B 空闲）：
Level 0: [ 128B 空闲 ]
↓ 分裂
Level 1: [ 64B 空闲 ][ 64B 分配给 level 1]
↓ 分裂
Level 2: [ 32B 分配 ][32B空闲][ 64B 分配给 level 1]
↑
这些块加入对应 level 的空闲链表2.3 合并（Merge）
释放时，检查被释放块的伙伴是否也空闲。如果伙伴也空闲，则将两个伙伴块合并为更大的块，并递归向上检查合并。
合并过程（释放 32B 块）：
Level 2: [ 32B 释放 ][32B空闲] → 伙伴空闲，合并！
Level 1: [ 64B 空闲 ] → 检查 Level 1 伙伴
Level 1: [ 64B 空闲 ][ 64B空闲 ] → 伙伴空闲，合并！
Level 0: [ 128B 空闲 ]三、内部数据结构
3.1 层级管理
#define MIN_BLOCK_SIZE 16 /* 最小块大小 16 字节 */
#define MAX_BUDDY_LEVEL 16 /* 最大层级数 16 */
struct buddy_heap
{
os_size_t heap_size; /* 堆总大小 */
os_size_t level_num; /* 实际层级数 */
os_size_t level_size[MAX_BUDDY_LEVEL]; /* 每层块大小 */
os_size_t level_blkid_max[MAX_BUDDY_LEVEL]; /* 每层最大块 ID */
os_list_node_t freelist[MAX_BUDDY_LEVEL]; /* 每层空闲链表 */
void *blk_start; /* 块区域起始 */
void *blk_end; /* 块区域结束 */
};层级关系：
| Level | 块大小 | 说明 |
|---|---|---|
| 0 | 最大块 | 由 MIN(MAX_BLOCK_SIZE, 总内存) 决定 |
| 1 | 最大块 / 2 | 上一级的一半 |
| 2 | 最大块 / 4 | … |
| N-1 | ≥ MIN_BLOCK_SIZE | 最小块，至少 16 字节 |
3.2 块结构
struct buddy_block
{
uint8_t level; /* 当前层级 */
uint8_t used; /* 使用状态: BLK_STAT_FREE / BLK_STAT_USED */
uint8_t duplicate; /* 重复标记: 用于对齐分配的辅助块标记 */
uint8_t magic_tag; /* 魔数标记: BLK_MAGIC_TAG (0x5A)，用于检测内存越界 */
os_list_node_t list_node; /* 空闲链表节点 */
};每个块头部大小为 BLK_HEAD_SIZE：
#define BLK_HEAD_TAG_SIZE 4 /* 4 字节头部标记 */
#ifdef OS_USING_MEM_TRACE
#define BLK_TASK_TAG_SIZE sizeof(os_base_t) /* 任务指针大小 */
#define BLK_HEAD_SIZE (BLK_HEAD_TAG_SIZE + BLK_TASK_TAG_SIZE)
#else
#define BLK_HEAD_SIZE (BLK_HEAD_TAG_SIZE)
#endif3.3 伙伴关系计算
/* 通过块 ID 和层级计算伙伴 ID */
#define BLK_ID_TO_BUDDY_ID(id) ((id & 0x1) ? (id - 1) : (id + 1))
/* 通过指针和层级计算块 ID */
#define BLK_PTR_TO_ID(h, ptr, level) \
(((uint8_t *)ptr - (uint8_t *)h->blk_start) / h->level_size[level])
/* 通过块 ID 和层级计算指针 */
#define BLK_ID_TO_PTR(h, id, level) \
(struct buddy_block *)((uint8_t *)h->blk_start + id * h->level_size[level])四、优缺点分析
4.1 优点
| 优点 | 说明 |
|---|---|
| 减少外部碎片 | 伙伴块自动合并，释放后立即回收为大块 |
| 合并速度快 | O(log N) 时间复杂度，最多合并 MAX_BUDDY_LEVEL 次 |
| 分配确定性 | 每层空闲链表 O(1) 取块，分配行为可预测 |
| 魔数检测 | 每个块头部有魔数标记（0x5A），可检测内存越界写入 |
| 多层级管理 | 支持 16 种不同大小的块，覆盖范围广 |
4.2 缺点
| 缺点 | 说明 |
|---|---|
| 内部碎片 | 分配大小向上取整到最近的 2 的幂次方，可能浪费多达 50% 的空间 |
| 元数据开销 | 每个块至少 4 字节头部（开启追踪时更多） |
| 最大块限制 | 最大块大小受 OS_ALG_BUDDY_MAX_BLOCK_SIZE 和堆大小限制 |
| 实现复杂度 | 相比 FIRSTFIT，代码实现更复杂 |
五、与 FIRSTFIT 对比
| 维度 | FIRSTFIT | BUDDY |
|---|---|---|
| 分配粒度 | 任意大小（8 字节对齐） | 2 的幂次方大小（最小 16 字节） |
| 外部碎片 | 较严重（长时间运行） | 较轻（伙伴自动合并） |
| 内部碎片 | 较小 | 较大（非 2 的幂向上取整） |
| 分配速度 | O(1)~O(n)（桶扫描） | O(1)~O(log N)（层级分裂） |
| 释放速度 | O(1)（合并相邻块） | O(log N)（伙伴合并） |
| 最坏情况 | 需扫描多个桶 | 需分裂多级 |
| 元数据开销 | 4~8 字节/chunk | 4 字节/块 + 层级管理结构 |
| 内存越界检测 | 通过 chunk 边界验证 | 魔数标记（0x5A） |
| 实现复杂度 | ★★☆☆☆ | ★★★☆☆ |
| 适用场景 | 通用嵌入式应用 | 频繁分配/释放，碎片敏感 |
六、适用场景
BUDDY 算法适合以下场景：
- ✅ 频繁分配/释放：伙伴合并机制能快速回收和重组内存
- ✅ 碎片敏感：外部碎片较少，适合长时间运行的系统
- ✅ 大小可预测：分配大小集中在某些 2 的幂次方附近
- ✅ 内存越界检测需求：每个块有魔数标记，便于检测非法写入
以下场景建议考虑 FIRSTFIT 算法：
- ❌ 内存分配大小分布广泛且不规则
- ❌ 内存资源非常紧张，需避免内部碎片浪费
- ❌ 简单的嵌入式应用，不需要复杂的碎片管理
七、内部工作流程
7.1 初始化
_k_buddy_mem_init()
│
├── 创建信号量 (用于并发保护)
├── 对齐内存起始地址到 OS_ALIGN_SIZE
├── 初始化 buddy_heap 结构体
│ ├── 计算层级大小 level_size[]
│ ├── 计算每层最大块数 level_blkid_max[]
│ └── 初始化所有 freelist 为空
├── 初始化空闲链表
│ ├── 按 Level 0 块大小划分初始块
│ ├── 处理剩余空间（按 2 的幂拆分为更小块）
│ └── 所有块加入对应层级的 freelist
└── 记录管理结构体占用7.2 分配流程
_k_buddy_mem_alloc()
│
├── 计算所需大小 (size + BLK_HEAD_SIZE)
├── 确定目标层级 (_k_size_to_level)
│
├── 获取信号量
├── _k_alloc_block()
│ ├── 从目标层级的 freelist 取块
│ │ └── 有 → 返回该块
│ └── 无 → 向上一级取块，再分裂
│ └── 递归直到找到可用块或到达 Level 0
│
├── 如果块层级 > 目标层级 → _k_split_block()
│ └── 逐级分裂，分裂出的子块加入对应 freelist
├── 标记块为已用
├── 记录分配任务 (OS_USING_MEM_TRACE 时)
└── 释放信号量，返回 BLK_TO_MEM(block)7.3 释放流程
_k_buddy_mem_free()
│
├── 获取信号量
├── 验证块状态 (检测 double-free)
├── 验证魔数标记 (检测内存越界)
│
├── _k_merge_block()
│ ├── 检查当前块的伙伴是否空闲
│ │ ├── 空闲 → 从 freelist 移除伙伴，合并为上级块
│ │ │ └── 递归检查上级块的伙伴
│ │ └── 不空闲 → 停止合并
│ └── 将合并后的块加入对应层级 freelist
│
└── 释放信号量📝 本节小结
- BUDDY 算法基于 2 的幂次方大小管理内存，通过伙伴分裂和合并实现分配和回收
- 最多支持 16 个层级，最小块 16 字节，支持多种块大小
- 每个块头包含魔数标记（0x5A），可检测内存越界写入
- 外部碎片较少（伙伴自动合并），但存在内部碎片（非 2 的幂向上取整）
- 与 FIRSTFIT 相比，BUDDY 在频繁分配/释放和碎片控制方面更优，但实现更复杂
- 选择原则：通用场景选 FIRSTFIT，频繁分配/释放、碎片敏感场景选 BUDDY