跳至主要內容

BUDDY 算法

学习阁2026/7/16大约 32 分钟内核组件内核内存管理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）——即相邻的、大小相同的块。两个伙伴块可以合并为一个更大的块。

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 层级管理

完整源码（kernel/source/os_mem_buddy.c，与项目逐字一致）：

来源：kernel/source/os_mem_buddy.c

字段含义：

字段含义
heap_size堆总大小（字节，对齐后）
level_num实际层级数
level_size[]每层块大小（字节），level_size[i] = level_size[i-1] / 2
level_blkid_max[]每层最大块 ID（该层最多块数）
freelist[]每层空闲链表头
blk_start块区域起始地址
blk_end块区域结束地址

关键宏：

宏含义
MIN_BLOCK_SIZE最小块大小 16 字节（不可再分裂的下限）
MAX_BUDDY_LEVEL最大层级数 16
INVALID_BUDDY_LEVEL非法层级标记（= 17），用于"请求过大、无对应层"的哨兵值

层级关系（level 0 最大，逐级减半）：

Level块大小说明
0最大块由 MIN(MAX_BLOCK_SIZE, 总内存) 决定
1最大块 / 2上一级的一半
2最大块 / 4…
N-1≥ MIN_BLOCK_SIZE最小块，至少 16 字节

层级关系：

Level块大小说明
0最大块由 MIN(MAX_BLOCK_SIZE, 总内存) 决定
1最大块 / 2上一级的一半
2最大块 / 4…
N-1≥ MIN_BLOCK_SIZE最小块，至少 16 字节

3.2 块结构

完整源码（kernel/source/os_mem_buddy.c，与项目逐字一致）：

来源：kernel/source/os_mem_buddy.c

struct buddy_block
{
    uint8_t        level;
    uint8_t        used;
    uint8_t        duplicate;
    uint8_t        magic_tag;
    os_list_node_t list_node;
};

字段含义：

字段含义
level当前层级（0 最大，逐级减小）
used使用状态：BLK_STAT_FREE(0) / BLK_STAT_USED(1)
duplicate重复标记：用于对齐分配的辅助块标记（BLK_TAG_NOT_DUPLICATE/BLK_TAG_DUPLICATE/BLK_TAG_ADJACENT）
magic_tag魔数标记 BLK_MAGIC_TAG(0x5A)，用于检测内存越界写入
list_node空闲链表节点

头部大小 BLK_HEAD_SIZE 完整源码：

来源：kernel/source/os_mem_buddy.c

#define BLK_HEAD_TAG_SIZE 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)
#endif

每个块在 buddy_block 结构之外还有一段头部，用于存魔数标记、任务标记等：

  • 不开启追踪：头部 4 字节（仅 BLK_HEAD_TAG_SIZE）。
  • 开启追踪：头部 4 + 任务指针大小（sizeof(os_base_t)）。

数值演算（32 位平台）：

配置BLK_HEAD_TAG_SIZEBLK_TASK_TAG_SIZEBLK_HEAD_SIZE
不追踪4—4 字节
追踪4sizeof(os_base_t)=48 字节

3.3 伙伴关系计算

完整源码（kernel/source/os_mem_buddy.c，与项目逐字一致）：

来源：kernel/source/os_mem_buddy.c

#define BLK_PTR_TO_ID(h, ptr, level) (((uint8_t *)ptr - (uint8_t *)h->blk_start) / h->level_size[level])
#define BLK_ID_TO_PTR(h, id, level)  (struct buddy_block *)((uint8_t *)h->blk_start + id * h->level_size[level])

#define BLK_ID_TO_BUDDY_ID(id) ((id & 0x1) ? (id - 1) : (id + 1))

#define BLK_TO_MEM(blk) ((void *)((uint8_t *)blk + BLK_HEAD_SIZE))
#define MEM_TO_BLK(ptr) ((struct buddy_block *)((uint8_t *)ptr - BLK_HEAD_SIZE))

#define BLK_HAS_BUDDY(h, level, blkid) (((blkid & (~1)) + 1) < h->level_blkid_max[level])

各宏含义与作用：

宏作用
BLK_PTR_TO_ID(h, ptr, level)指针 → 块 ID（(ptr - blk_start) / 每层块大小）
BLK_ID_TO_PTR(h, id, level)块 ID → 指针（blk_start + id * 每层块大小）
BLK_ID_TO_BUDDY_ID(id)算伙伴块 ID：偶数 id 的伙伴是 id+1，奇数 id 的伙伴是 id-1
BLK_TO_MEM(blk)块指针 → 用户数据指针（跳过头部 BLK_HEAD_SIZE）
MEM_TO_BLK(ptr)用户数据指针 → 块指针（回退头部）
BLK_HAS_BUDDY(h, level, blkid)判断该块在该层是否真的存在伙伴（不是最后一个无配对的块）

伙伴 ID 数值演算（BLK_ID_TO_BUDDY_ID）：

块 ID idid & 0x1伙伴 ID说明
0（偶数）00+1 = 1块 0 和块 1 是伙伴
1（奇数）11-1 = 0块 1 和块 0 是伙伴
2（偶数）02+1 = 3块 2 和块 3 是伙伴
3（奇数）13-1 = 2块 3 和块 2 是伙伴
6（偶数）06+1 = 7块 6 和块 7 是伙伴
7（奇数）17-1 = 6块 7 和块 6 是伙伴

规律：每两个相邻块（ID 偶奇成对）互为伙伴，对应 2.1 图示中"0 和 1、2 和 3…是伙伴"。

BLK_HAS_BUDDY 为什么需要：当某层块数不是偶数时，最后一个块没有配对伙伴。((blkid & (~1)) + 1) 把 blkid 归到"它所在对的下界"+1，再判断是否小于该层最大 ID——若不小于，说明该块是末位无伙伴块，不能合并（详见 7.3 释放流程）。

四、优缺点分析

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 对比

维度FIRSTFITBUDDY
分配粒度任意大小（8 字节对齐）2 的幂次方大小（最小 16 字节）
外部碎片较严重（长时间运行）较轻（伙伴自动合并）
内部碎片较小较大（非 2 的幂向上取整）
分配速度O(1)~O(n)（桶扫描）O(1)~O(log N)（层级分裂）
释放速度O(1)（合并相邻块）O(log N)（伙伴合并）
最坏情况需扫描多个桶需分裂多级
元数据开销4~8 字节/chunk4 字节/块 + 层级管理结构
内存越界检测通过 chunk 边界验证魔数标记（0x5A）
实现复杂度★★☆☆☆★★★☆☆
适用场景通用嵌入式应用频繁分配/释放，碎片敏感

六、适用场景

BUDDY 算法适合以下场景：

  • ✅ 频繁分配/释放：伙伴合并机制能快速回收和重组内存
  • ✅ 碎片敏感：外部碎片较少，适合长时间运行的系统
  • ✅ 大小可预测：分配大小集中在某些 2 的幂次方附近
  • ✅ 内存越界检测需求：每个块有魔数标记，便于检测非法写入

以下场景建议考虑 FIRSTFIT 算法：

  • ❌ 内存分配大小分布广泛且不规则
  • ❌ 内存资源非常紧张，需避免内部碎片浪费
  • ❌ 简单的嵌入式应用，不需要复杂的碎片管理

七、内部工作流程

7.1 初始化

_k_buddy_mem_init 完整源码（kernel/source/os_mem_buddy.c，与项目逐字一致）：

来源：kernel/source/os_mem_buddy.c

分步详解：

第一步：创建并发保护信号量（无条件执行）

    os_semaphore_create(&h_mem->sem_id, "mem_b_sem", 1, 1);

创建名为 "mem_b_sem" 的二值信号量（初始值 1，最大值 1），用于保护后续分配/释放的互斥。为什么需要：堆是共享资源，多任务可能并发 os_malloc/os_free，而分配/释放涉及对 freelist、块头部的多步非原子操作，若无互斥会出现重复分配、链表损坏等竞态（详见 4.4.2 6.2 第一步的信号量讲解，机制相同）。

第二步：校验堆大小（无条件执行，不合格则断言崩溃）

    OS_ASSERT_EX(bytes > sizeof(struct buddy_heap), "heap size is too small");

    OS_ASSERT(bytes > OS_ALIGN_SIZE);
    start = OS_ALIGN_UP((os_size_t)mem, OS_ALIGN_SIZE);
    size  = OS_ALIGN_DOWN((os_size_t)mem + bytes - start, OS_ALIGN_SIZE);
    OS_ASSERT(size >= (OS_ALIGN_UP(sizeof(struct buddy_heap) + MIN_BLOCK_SIZE, OS_ALIGN_SIZE)));
  • 堆总字节数 bytes 必须 > sizeof(struct buddy_heap)（至少装得下管理结构）。
  • 计算对齐后的起始 start（向上对齐到 OS_ALIGN_SIZE）和可用大小 size（向下对齐）。
  • size 必须 ≥ 管理结构 + 最小块 16 字节，否则断言。

数值演算（假设 mem = 0x1008，bytes = 0x4000（16KB），OS_ALIGN_SIZE = 8）：

项计算结果
startOS_ALIGN_UP(0x1008, 8)0x1008（已对齐）
sizeOS_ALIGN_DOWN(0x1008 + 0x4000 - 0x1008, 8)0x4000
校验0x4000 >= sizeof(buddy_heap)+16？是（通过）

第三步：设置堆头 buddy_heap 并确定块区域起点（无条件执行）

    h             = (struct buddy_heap *)start;
    h->heap_size  = size;
    h->blk_start  = (void *)(start + OS_ALIGN_UP(sizeof(struct buddy_heap), OS_ALIGN_SIZE));
    h_mem->header = h;

    size -= OS_ALIGN_UP(sizeof(struct buddy_heap), OS_ALIGN_SIZE);
  • h 指向堆起始（存管理结构）；h->heap_size = size（总大小）。
  • h->blk_start = start 之后紧邻的块区域起点（跳过对齐后的 buddy_heap 结构）。
  • size 减去管理结构占用的字节，得到真正的可分配块区域大小。

第四步：初始化层级 + 空闲链表（无条件执行，关键）

    _k_buddy_init_level_size(h, size);
    _k_buddy_init_free_list(h, size);
    BUDDY_MEM_INFO_INIT(h_mem, h->heap_size);
    BUDDY_MEM_USED_INC(h_mem, OS_ALIGN_UP(sizeof(struct buddy_heap), OS_ALIGN_SIZE));
  • _k_buddy_init_level_size(h, size)：计算各层块大小 level_size[] 和每层最大块 ID level_blkid_max[]（从最大块开始逐级减半，直到最小块 16 字节）。
  • _k_buddy_init_free_list(h, size)：把整块堆划分成初始空闲块，挂到各层 freelist（见 7.4 辅助函数详解）。
  • BUDDY_MEM_INFO_INIT：初始化统计（mem_total、mem_used、mem_maxused）。
  • BUDDY_MEM_USED_INC：把管理结构占用的字节计入 mem_used。

内存布局示意：

start ──► ┌───────────────────────────────┐
          │  struct buddy_heap（管理结构）  │  ← 对齐到 OS_ALIGN_SIZE
          ├───────────────────────────────┤
blk_start►│  块区域：被划分成各层空闲块      │  ← size 字节（可分配区域）
          │  Level 0 大块 / Level 1 / ...  │
          └───────────────────────────────┘

具体例子解释（假设：mem = 0x1000，bytes = 0x1100（4352 字节），OS_ALIGN_SIZE = 8，sizeof(struct buddy_heap) 对齐后占 0x40（64 字节））：

项计算结果
startOS_ALIGN_UP(0x1000, 8)0x1000
sizeOS_ALIGN_DOWN(0x1000 + 0x1100 - 0x1000, 8)0x1100（已对齐）
h = (buddy_heap*)start管理结构放在起始地址 0x1000，占 64 字节
blk_start0x1000 + 0x400x1040（块区域起点）
块区域大小0x1100 - 0x400x10C0 = 4288 字节

对应到地址的内存布局：

块区域 [0x1040, 0x2100) 共 4288 字节，初始化后按 2 的幂被划分成：4096 + 128 + 64 = 4288 字节。其中 Level 0 大块（4096）挂 freelist[0]，128 和 64 两个小块分别挂对应层的 freelist。

地址核算：

项计算结果
堆起始start0x1000
堆结束start + size0x1000 + 0x1100 = 0x2100
管理结构[0x1000, 0x1040)0x40 字节
blk_start0x1040块区域起点
块区域结束blk_start + 块区域大小0x1040 + 0x10C0 = 0x2100（= 堆结束 ✓）

划分细节：_k_buddy_init_level_size(h, 0x10C0) 算出最大块 level_size[0] = _k_cal_prev_power_of_2(4288) = 4096（小于 4288 的最大 2 的幂）。于是：

  • 整个 4288 字节先分成 1 个 4096 字节的 Level 0 大块（level_0_blk_num = 4288 / 4096 = 1），挂到 freelist[0]。
  • 剩余零头 4288 % 4096 = 192 字节，_k_buddy_init_free_list 继续拆成 2 的幂小块：_k_cal_prev_power_of_2(192) = 128 → 192 % 128 = 64 → 再拆 64 → 0。所以拆成 128 + 64 两个小块，挂到对应层 freelist。

最终布局（地址全对上，共 4288 字节）：

0x1040 ──► ┌─ Level 0 大块（4096 字节）─────┐   ← freelist[0] 里的第一个块
           │  [0x1040, 0x2040)              │
0x2040 ──► ├─ 小块（128 字节）──────────────┤   ← freelist[对应层]
           │  [0x2040, 0x20C0)              │
0x20C0 ──► ├─ 小块（64 字节）───────────────┤   ← freelist[对应层]
           │  [0x20C0, 0x2100)              │
0x2100 ──► └───────────────────────────────┘
           （堆结束）

校验：4096 + 128 + 64 = 4288 字节，正好填满块区域 [0x1040, 0x2100)；块区域结束 0x2100 恰等于堆结束，无空隙浪费（本例零头刚好被 128+64 拆尽）。

关键结论：初始化主要做了三件事——①创建互斥信号量；②把内存划分为"管理结构 + 块区域"；③把块区域按 2 的幂划分成初始空闲块并挂入各层 freelist。初始时整个堆是一个 Level 0 大空闲块（挂在 freelist[0]），后续分配从它分裂，释放后合并回它。

_k_buddy_init_level_size 与 _k_buddy_init_free_list 的完整源码与逐行详解见下方 7.4 核心辅助函数。

7.2 分配流程

_k_buddy_mem_alloc 完整源码（kernel/source/os_mem_buddy.c，与项目逐字一致）：

来源：kernel/source/os_mem_buddy.c

分步详解：

第一步：换算大小并确定目标层级（无条件执行）

    size      = SIZE_WITH_HEAD(bytes);
    level_req = _k_size_to_level(h, size);
  • SIZE_WITH_HEAD(bytes) = bytes + BLK_HEAD_SIZE：请求大小加上块头部，得到实际要占的内存。
  • _k_size_to_level(h, size)：把 size 换算成能容纳它的最小层级 level_req。例如 size 需要 40 字节，最小块 16 字节，则算到能装下 40 的层级（如 64 字节块那一级）。

第二步：判断层级是否合法（条件：INVALID_BUDDY_LEVEL != level_req）

    if (INVALID_BUDDY_LEVEL != level_req)
    {
        ...
    }
    return mem;   /* level_req 非法时 mem 保持 OS_NULL */
  • 条件成立（合法）：请求大小不超过最大块，进入分配。
  • 条件不成立（非法）：_k_size_to_level 返回 INVALID_BUDDY_LEVEL（请求超过最大块），mem 保持 OS_NULL，直接返回空。

第三步：获取信号量 + 找块（条件：层级合法才执行）

        (void)os_semaphore_wait(&h_mem->sem_id, OS_WAIT_FOREVER);

        block = _k_alloc_block(h, level_req);
  • 进入临界区（互斥保护）。
  • _k_alloc_block(h, level_req)：从 level_req 层开始找空闲块。若该层有块，直接取；若无，向上一级找并递归（见 7.4 辅助函数详解）。

第四步：处理找到的块（条件：block 非空）

  • 条件 block 非空（找到块）：
    • 子分支：block->level < level_req（块来自更上层、比所需大）→ _k_split_block(h, block, level_req) 逐级分裂成合适大小（见 7.4）。
    • 设置块头：level = level_req、used = USED、duplicate = NOT_DUPLICATE、magic_tag = MAGIC_TAG。
    • 追踪时记录分配任务；mem = BLK_TO_MEM(block) 返回用户数据指针；统计 mem_used。
  • 条件 block 为空（找不到块）→ mem 保持 OS_NULL。

第五步：释放信号量，返回（无条件执行）

        (void)os_semaphore_post(&h_mem->sem_id);
    }

    return mem;

离开临界区，返回 mem（成功为数据指针，失败为 OS_NULL）。

if-else 条件走向总结（树状图）：

数值演算示例（沿用 7.1 初始化例子的数据：level_size[] = {4096, 2048, 1024, 512, 256, 128, 64, 32, 16}，level_num = 9，头部 4）：

用户申请 bytes = 20 字节：

项计算结果
size20 + 424 字节
level_req_k_size_to_level(h, 24)需 ≥24 字节的最小层级 → 32 字节块 → Level 7（索引 7，level_size[7]=32）
_k_alloc_block从 Level 7 找块若无，向 Level 6/5... 递归找
分裂若找到 64 字节块（Level 6）分裂成 2 个 32 字节块，一个用、一个挂回 Level 7
返回BLK_TO_MEM(block)返回数据指针（跳过 4 字节头部）

对应关系：level_size[8]=16（最小块）、level_size[7]=32、level_size[6]=64、level_size[0]=4096（最大块）。

核心思想：BUDDY 总是分配刚好够大的 2 的幂块。目标层没有就向大层找，找到后再分裂成两半，一半用、一半挂回 freelist。这就是"分配时分裂"。

7.3 释放流程

_k_buddy_mem_free 完整源码（kernel/source/os_mem_buddy.c，与项目逐字一致）：

来源：kernel/source/os_mem_buddy.c

分步详解：

第一步：指针判空 + 地址校验（条件：mem 非空）

    if (mem)
    {
        h = h_mem->header;
        OS_ASSERT_EX((mem >= h->blk_start) && (mem <= h->blk_end),
                     "unexpected mem addr (invalid addr?) for memory at %p",
                     mem);
        block = MEM_TO_BLK(mem);
  • 条件 mem 非空：进入释放流程；mem == OS_NULL 时为空操作（安全）。
  • 校验 mem 在 [blk_start, blk_end] 范围内（非法指针则断言崩溃）。
  • block = MEM_TO_BLK(mem)：用户数据指针回退头部，得到块指针。

第二步：获取信号量 + 状态校验（无条件执行）

        (void)os_semaphore_wait(&h_mem->sem_id, OS_WAIT_FOREVER);

        OS_ASSERT_EX(block->used == BLK_STAT_USED,
                     "unexpected mem state (double-free? or invalid addr?) for memory at %p",
                     mem);
        OS_ASSERT_EX(block->magic_tag == BLK_MAGIC_TAG,
                     "unexpected header info (been write illegal?) for memory at %p",
                     mem);
  • 进入临界区。
  • double-free 检测：块必须处于 BLK_STAT_USED，若已是空闲则断言（说明重复释放）。
  • 内存越界检测：块头的 magic_tag 必须等于 BLK_MAGIC_TAG(0x5A)，若被写坏则断言（说明越界写入破坏了块头）。

第三步：处理对齐分配产生的重复块头（条件：duplicate 标记）

  • 条件成立（duplicate 为 DUPLICATE/ADJACENT）：说明这个指针是对齐分配时产生的"重复块头"，真正的块头在别处。用 BLK_PTR_TO_ID 算回真实块，校验后把 block 指回真实块头。
  • 条件不成立（普通块）→ 直接使用当前 block。

第四步：合并 + 统计 + 释放信号量（无条件执行）

        level = block->level;
        BUDDY_MEM_USED_DEC(h_mem, h->level_size[level]);
        _k_merge_block(h, block);

        (void)os_semaphore_post(&h_mem->sem_id);
    }
  • level = block->level：记录块层级。
  • BUDDY_MEM_USED_DEC：统计 mem_used 减去该块大小。
  • _k_merge_block(h, block)：与伙伴合并——若伙伴也空闲则合并成更大块，并递归向上合并（见 7.4 辅助函数详解）。
  • 释放信号量，离开临界区。

if-else 条件走向总结（树状图）：

数值演算示例（延续 7.2 分配例子：Level 7 的 32 字节块被分配，现在释放）：

步骤计算/操作结果
① 回退头部MEM_TO_BLK(mem)得到 32 字节块的 block
② 校验used == USED、magic_tag == 0x5A通过
③ duplicate普通分配 → 非 DUPLICATE直接使用
④ 合并_k_merge_block(h, block)检查伙伴是否空闲
⑤ 若伙伴空闲移除伙伴，合并成 64 字节块递归检查 64 的伙伴…
⑥ 入桶合并后的块挂回对应 freelist完成释放

核心思想：释放时尽可能向上合并成更大的空闲块，恢复到分配前的状态。这正是 BUDDY 能抑制外部碎片的关键——伙伴块总是能精确合并回上一级。

7.4 核心辅助函数

分配、释放主流程调用了多个内部辅助函数。按规范，这里把它们单独成节逐一详解，主流程只调用不展开。

7.4.1 _k_size_to_level —— 请求大小 → 目标层级

完整源码（kernel/source/os_mem_buddy.c，与项目逐字一致）：

来源：kernel/source/os_mem_buddy.c

分步详解：

  • 第一步：lvl 从最小层（level_num - 1，块最小）开始。
  • 第二步（条件 size > h->level_size[0]）：请求超过最大块大小 →
    • 若超过 OS_ALG_BUDDY_MAX_BLOCK_SIZE，打印告警；
    • 返回 INVALID_BUDDY_LEVEL（非法，分配失败）。
  • 第三步（条件不成立，size 在合法范围）：while 循环 lvl--，从最小层往大层找，找到第一个块大小 ≥ size 的层级。

数值演算（沿用 7.1 数据：level_size[] = {4096, 2048, 1024, 512, 256, 128, 64, 32, 16}，level_num = 9）：

请求 size从最小层开始扫描结果 lvl
2016<20 → 32≥20Level 7（32 字节块）
10016/32/64<100 → 128≥100Level 5（128 字节块）
512512≥512Level 3（512 字节块）
20482048≥2048Level 1（2048 字节块）
50005000 > 4096（最大）INVALID_BUDDY_LEVEL

层级索引对照：level_size[8]=16、level_size[7]=32、level_size[6]=64、level_size[5]=128、level_size[4]=256、level_size[3]=512、level_size[2]=1024、level_size[1]=2048、level_size[0]=4096。

关键点：找到的层级是能装下请求的最小 2 的幂块，尽量少浪费（内部碎片最小）。

7.4.2 _k_cal_prev_power_of_2 —— 前一个 2 的幂

完整源码（kernel/source/os_mem_buddy.c，与项目逐字一致）：

来源：kernel/source/os_mem_buddy.c

分步详解：

  • 第一步（条件 0U == size）：size 为 0 → val = 0。
  • 第二步（否则）：不断右移 size（size >>= 1）直到 size ≤ 1，记录位移次数 i；val = 1 << i 即 2^i。
  • 结果：_k_cal_prev_power_of_2(size) = 小于等于 size 的最大 2 的幂。

数值演算：

size右移过程ival = 1<<i
0——0
55→2→1（位移 2 次）24
1616→8→4→2→1（位移 4 次）416
4040→20→10→5→2→1（位移 5 次）532

关键点：用于把任意大小归到最近的 2 的幂（向下），配合层级划分和剩余空间拆分。

7.4.3 _k_alloc_block —— 从某层取空闲块

完整源码（kernel/source/os_mem_buddy.c，与项目逐字一致）：

来源：kernel/source/os_mem_buddy.c

分步详解：

  • 第一步：block = OS_NULL（默认未找到）。
  • 第二步（while(1) 循环）：从 level 层开始找：
    • node = os_list_first(&freelist[level])：取该层链表首节点。
    • 子分支 node 非空（该层有块）→ os_list_del 移出，block 指向它，OS_ASSERT 校验层级，break。
    • 子分支 node 为空（该层无块）→ if (level-- == 0) 判断是否已到 Level 0：是则 break（找不到）；否则 level-- 向上一级继续找。

if-else 条件走向总结（树状图）：

关键点：_k_alloc_block 从目标层开始，若该层无块就向上一级（更大块）找，直到找到或到 Level 0。找到的块可能比需要的大，后续由 _k_split_block 分裂。

7.4.4 _k_split_block —— 逐级分裂块

完整源码（kernel/source/os_mem_buddy.c，与项目逐字一致）：

来源：kernel/source/os_mem_buddy.c

分步详解：

  • 循环（for）：从 block->level + 1 到 level，逐级分裂。
  • 每级：block_new = block + level_size[level_new]（取块的后半部分作为子块），设置其 level、used=FREE、duplicate、magic_tag，并 os_list_add 挂到该层 freelist。

数值演算（沿用 7.1 数据：level_size[] = {4096, 2048, 1024, 512, 256, 128, 64, 32, 16}，把一个 Level 1（2048 字节）块分裂到 Level 4（256 字节））：

分裂前： 块（2048 字节，Level 1）
分裂过程：
  level_new=2: 分出 1024 字节块 → 挂 freelist[2]
  level_new=3: 分出 512 字节块 → 挂 freelist[3]
  level_new=4: 分出 256 字节块 → 挂 freelist[4]
分裂后：原块变为 Level 4（256 字节），其余 1024/512/256 子块挂回各层

关键点：分裂只把块的一半逐级拆出挂回 freelist，不复制数据，只是改块头、重组空闲链表。分裂出的子块都标记 FREE，供后续分配使用。

7.4.5 _k_merge_block —— 释放时与伙伴合并

完整源码（kernel/source/os_mem_buddy.c，与项目逐字一致）：

来源：kernel/source/os_mem_buddy.c

分步详解：

第一步：初始化合并游标（无条件执行）

    blkid_merge       = BLK_PTR_TO_ID(h, block, block->level);
    level_merge       = block->level;
    block_merge->used = BLK_STAT_FREE;
  • 算当前块的块 ID blkid_merge、层级 level_merge，并先把当前块标记为空闲。

第二步：循环尝试与伙伴合并（条件：层级 > 0 且该块有伙伴）

  • 循环条件：level_merge > 0（Level 0 不可合并）且 BLK_HAS_BUDDY（该块确实有伙伴）。
  • 块内：
    • 算伙伴 ID block_buddy_id、伙伴指针 block_buddy。
    • 子分支：伙伴已用 或 伙伴层级不同 → break（无法合并，停止）。
    • 子分支：伙伴空闲且同层 → 把伙伴从 freelist 移除（os_list_del），level_merge--、blkid_merge >>= 1（上升到父块），block_merge 指到父块，break 条件满足则继续向上合并。

第三步：把合并后的块挂回 freelist（无条件执行）

    os_list_add(&h->freelist[level_merge], &block_merge->list_node);

把合并后的（或未合并的）块 block_merge 挂到 level_merge 层 freelist。

数值演算（沿用 7.1 数据，level_size[2] = 1024，合并 Level 2 的块 6 和块 7，各 1024 字节）：

步骤操作结果
① 初始blkid_merge=6，level_merge=2块 6，Level 2
② 找伙伴BLK_ID_TO_BUDDY_ID(6)=7块 7
③ 判断块 7 空闲且同层？是 → 合并
④ 上升level_merge=1，blkid_merge=6>>1=3父块 ID=3，Level 1
⑤ 继续检查块 3 的伙伴（块 2）若空闲则继续合并…
⑥ 入桶最终合并块挂回 freelist[level_merge]完成

关键点：合并是向上递归的——伙伴都空闲就合并成父块，再检查父块的伙伴，直到 Level 0 或伙伴不空闲。这保证释放后能最大化回收大块，抑制外部碎片。

7.4.6 _k_buddy_init_level_size —— 计算各层块大小

完整源码（kernel/source/os_mem_buddy.c，与项目逐字一致）：

来源：kernel/source/os_mem_buddy.c

分步详解：

  • 第一步：max_block_size = MIN(MAX_BLOCK_SIZE, size)（取最大块上限与实际堆大小的较小者）；level_size = _k_cal_prev_power_of_2(max_block_size)（归到 2 的幂）。
  • 第二步（for 循环）：从最大块开始，level_size[i] = level_size，level_blkid_max[i] = size / level_size（该层最多块数），然后 level_size >>= 1（减半）。直到 level_size < MIN_BLOCK_SIZE 或达到 MAX_BUDDY_LEVEL。
  • 第三步：h->level_num = i（实际层级数），并断言 ≥ 1。

数值演算（沿用 7.1 数据：块区域 size = 4288，MAX_BLOCK_SIZE 足够大，最大块 = _k_cal_prev_power_of_2(4288) = 4096，MIN_BLOCK_SIZE = 16）：

ilevel_size[i]level_blkid_max[i]（= 4288 / level_size[i]）说明
040961最大块
120482
210244
35128
425616
512833
66467
732134
816268最小块，循环停止

level_num = 9，与 7.1 例子一致。

关键点：层级从最大块（2 的幂）开始，逐级减半到 16 字节。level_blkid_max[i] 记录每层最多能有多少个块，用于 BLK_HAS_BUDDY 判断伙伴是否存在。

7.4.7 _k_buddy_init_free_list —— 划分初始空闲块

完整源码（kernel/source/os_mem_buddy.c，与项目逐字一致）：

来源：kernel/source/os_mem_buddy.c

分步详解：

第一步：初始化所有 freelist（无条件执行）

    level_0_blk_num = size / h->level_size[0];
    residual_size   = size % h->level_size[0];

    for (i = 0; i < MAX_BUDDY_LEVEL; i++)
    {
        os_list_init(&h->freelist[i]);
    }
  • 算出能装下几个 Level 0 大块（level_0_blk_num）和剩余零头（residual_size）。
  • 清空所有层 freelist。

第二步：挂 Level 0 大块（无条件执行）

把 level_0_blk_num 个 Level 0 大块依次挂到 freelist[0]。

第三步：处理剩余空间（条件：residual_size >= MIN_BLOCK_SIZE）

  • 条件成立（剩余 ≥ 16 字节）：把剩余空间按 2 的幂拆分成小块，逐块挂到对应层 freelist，直到剩余 < 16。
  • 条件不成立（剩余 < 16）：跳过。

第四步：修正堆大小 + 记录结束地址（条件：还有零头）

    if (residual_size > 0)
    {
        h->heap_size -= residual_size;
    }
    h->blk_end = blk;
  • 条件 residual_size > 0：heap_size 减去无法利用的零头（<16 字节的尾巴）。
  • h->blk_end 记录块区域结束地址。

数值演算（沿用 7.1 数据，level_size[0] = 4096，块区域 size = 4288）：

项计算结果
level_0_blk_num4288 / 40961 个 Level 0 大块
residual_size4288 % 4096192 字节
拆零头（循环）192→128（余64）→64（余0）拆成 128 + 64 两块

边界演示（零头不足被丢弃）：若块区域为 size = 4104（level_size[0]=4096），则 4104 % 4096 = 8 字节，8 < MIN_BLOCK_SIZE(16)，while 循环不执行，这 8 字节无法形成空闲块，被丢弃：h->heap_size -= 8。这正是初始化"丢弃 <16 零头"的场景。

关键点：初始化把整块堆划分成"若干 Level 0 大块 + 剩余的 2 的幂小块"，全部挂到对应 freelist。初始时堆是整块空闲（挂 freelist[0]），剩余零头被丢弃并修正 heap_size。

补充：freelist 一开始就存在，但里面的"块"不是一开始全有

  • 链表头（freelist[] 数组）从一开始就有：它是 struct buddy_heap 的结构体成员，_k_buddy_init_free_list 开头的 os_list_init(&h->freelist[i]) 循环会把 16 个链表头全部初始化，但初始都是空链表。
  • 链表里的块不是一开始全有：初始化只挂入大块（如 freelist[0] 挂 4096、freelist[5] 挂 128、freelist[6] 挂 64）。其余层（如 freelist[7] 的 32 字节块）初始是空的。
  • 小块按需分裂后挂入：当分配需要 32 字节块而 freelist[7] 为空时，_k_alloc_block 向大层找到 128 字节块，再经 _k_split_block 逐级对半分裂，把每级多出的右半块 os_list_add 挂到对应层。所以 freelist[7] 里的块是分配那一刻临时分裂产生的，不是初始化时就有的。

为什么按需分裂而不是初始化全建好？ 若初始化就把大块全拆成小块，堆就全是 32 字节块，无法满足大块分配（如要 2048 字节）。保留大块 + 按需分裂，既能分配大块，又能在需要小块时现拆，避免浪费。

7.4.8 _k_split_block_aligned —— 对齐分配的分裂

_k_buddy_mem_aligned_alloc（对齐分配接口）会调用它，把一个块反复二分，直到内存地址满足对齐要求，并在块头打上 duplicate 标记供释放时还原。

完整源码（kernel/source/os_mem_buddy.c，与项目逐字一致）：

来源：kernel/source/os_mem_buddy.c

分步详解：

第一步：初始化对齐目标与边界（无条件执行）

    blk_split   = block;
    mem         = (void *)OS_ALIGN_UP((os_size_t)BLK_TO_MEM(block), align);
    blk_size    = h->level_size[block->level];
    blk_begin   = block;
    blk_end     = (struct buddy_block *)((os_size_t)blk_begin + blk_size);
    blk_mid     = (struct buddy_block *)((os_size_t)blk_begin + (blk_size >> 1));
    mem_begin   = (void *)((os_size_t)mem - BLK_HEAD_SIZE);
    mem_end     = (void *)OS_ALIGN_UP((os_size_t)mem + bytes, OS_ALIGN_SIZE);
    level_split = block->level;
  • mem = 块数据区向上对齐到 align 的地址；blk_begin/blk_mid/blk_end 分别是块的起点、中点、终点。
  • mem_begin/mem_end 是用户数据实际要占的范围（含对齐）。

第二步：循环二分直到块装下对齐后的内存（条件：数据落在当前块半区）

  • 循环条件：数据落在块的前半或后半（说明当前块还能缩小）。
  • 子分支 mem_begin >= blk_mid（数据在右半）→ 左半 blk_begin 标 FREE 入桶，blk_split = blk_mid，继续往右半分裂。
  • 子分支（数据在左半）→ 右半 blk_mid 标 FREE 入桶，blk_split = blk_begin，继续往左半分裂。
  • level_split >= level_num-1 时停止（已到最小层）。

第三步：返回分裂后的块（无条件执行）

    return blk_split;

返回包含对齐后内存的那半个块。上层用 OS_ALIGN_UP(BLK_TO_MEM(block), align) 作为返回给用户的对齐指针，并在块头打 duplicate 标记。

关键点：对齐分配通过不断二分 + 把不含数据的半区挂回 freelist，最终得到一个"内部包含对齐地址"的块。由于数据可能在块中部而非开头，块头会与实际数据区错位，因此释放时需靠 duplicate 标记找回真实块头（见 7.3 第三步）。

数值演算示例（沿用 7.1 数据：level_size[] = {4096, 2048, 1024, 512, 256, 128, 64, 32, 16}；一个 Level 0 大块地址 0x1040，请求 bytes = 32、对齐 align = 256）：

第一步：算对齐后的内存范围

项计算结果
数据区起点BLK_TO_MEM(块) = 0x1040 + 40x1044
对齐后 memOS_ALIGN_UP(0x1044, 256)0x1100
mem_begin0x1100 - 40x10FC
mem_endOS_ALIGN_UP(0x1100 + 32, 8)0x1120

第二步：反复二分，把不含数据的半区挂回 freelist

初始块：[0x1040, 0x2040)  大小 4096（Level 0），中点 0x1440
  数据 [0x10FC, 0x1120) 落在左半区 → 右半 [0x1440, 0x2040) 挂回 freelist，继续左半
左半  [0x1040, 0x1440)  大小 2048，中点 0x1240
  数据在左半 → 右半 [0x1240, 0x1440) 挂回，继续左半
左半  [0x1040, 0x1240)  大小 1024，中点 0x1140
  数据在左半 → 右半 [0x1140, 0x1240) 挂回，继续左半
左半  [0x1040, 0x1140)  大小 512，中点 0x10C0
  数据 [0x10FC, 0x1120) 跨越中点！停止二分
最终块：[0x1040, 0x1140)  大小 512（Level 3），数据位于其内部偏移 0xBC 处

第三步：返回

  • 返回块 [0x1040, 0x1140)（512 字节，Level 3）；用户拿到的对齐指针 = 0x1100（数据区起点，256 对齐）。
  • 块头（0x1040 处）与实际数据区（0x1100）错位，故块头打 duplicate 标记，供释放时还原。

关键点：对齐分配通过不断二分 + 把不含数据的半区挂回 freelist，最终得到一个"内部包含对齐地址"的块。由于数据可能在块中部而非开头，块头会与实际数据区错位，因此释放时需靠 duplicate 标记找回真实块头（见 7.3 第三步）。

📝 本节小结

核心要点回顾

  • 核心思想：BUDDY 把内存按 2 的幂分层（Level 0 最大，逐级减半到 16 字节），通过伙伴块的分裂（分配时）和合并（释放时）管理内存。
  • 关键数据结构：buddy_heap（管理结构）+ buddy_block（块头：level/used/duplicate/magic_tag）+ 每层 freelist。
  • 伙伴关系：BLK_ID_TO_BUDDY_ID(id) = 偶数的伙伴是 id+1、奇数的伙伴是 id-1；BLK_HAS_BUDDY 判断末位块无伙伴。
  • 分配流程（7.2）：算目标层级 → _k_alloc_block 从目标层找（无则向大层递归）→ 块过大则 _k_split_block 分裂 → 标记已用。
  • 释放流程（7.3）：校验（double-free/越界）→ duplicate 还原真实块头 → _k_merge_block 向上递归合并 → 入桶。
  • 优缺点：外部碎片少（伙伴自动合并）、有魔数越界检测；但存在内部碎片（非 2 的幂向上取整）、实现复杂。

关键易错点速查表

易错点说明对应章节
伙伴 ID 算反偶数块伙伴是 id+1，奇数块伙伴是 id-1，别记反3.3
末位块无伙伴每层块数不偶时，最后一块无伙伴，BLK_HAS_BUDDY 返回假，不可合并3.3、7.4.5
请求超过最大块_k_size_to_level 返回 INVALID_BUDDY_LEVEL，分配返回 OS_NULL7.2、7.4.1
内部碎片分配向上取整到 2 的幂，可能浪费近 50%四、优缺点
double-free释放已释放块 → used 非 USED → 断言崩溃7.3
越界破坏块头 magic_tag 被写坏 → 断言崩溃7.3
对齐分配的 duplicate对齐分配产生重复块头，释放时需 BLK_PTR_TO_ID 还原真实块头7.3
最小块 16 字节MIN_BLOCK_SIZE=16，不可再分裂的下限3.1、7.4.7
零头丢弃初始化剩余 <16 字节的尾巴被丢弃，heap_size 修正7.4.7

下一步

继续学习 4.4.4 内存池，了解另一种固定大小块的分配方式，以及它与 BUDDY 动态分裂的区别。

  • 选择原则：通用场景选 FIRSTFIT，频繁分配/释放、碎片敏感场景选 BUDDY

🔗 相关链接

OneOS-Lite 文档 | 学习阁
Copyright © 2026 学习阁