06 - Buddy分配算法

难度: 🔴 困难级
预计学习时间: 90分钟
前置知识: 04-核心数据结构详解, 05-AMDGPU中的VRAM管理器

📋 概述

Buddy分配算法是整个内存管理的核心：

• 🎯主入口:drm_buddy_alloc_blocks()处理所有分配请求
• 🔍查找策略: 从合适的order开始查找空闲块
• ✂️分裂机制: 大块分裂成小块满足请求
• 📐对齐处理: 支持min_block_size参数控制对齐
• ⏱️时间复杂度: O(log n)，非常高效

本章深入分析Buddy分配算法的完整流程和实现细节。

6.1 分配请求处理流程

主入口函数

// drivers/gpu/drm/drm_buddy.c/** * drm_buddy_alloc_blocks - 分配内存块 * * @mm: buddy管理器 * @start: 起始地址 (0表示任意位置) * @end: 结束地址 (mm->size表示整个范围) * @size: 请求的大小 (字节) * @min_block_size: 最小块大小 (对齐要求) * @blocks: 输出的块链表 * @flags: 分配标志 (CONTIGUOUS/CLEAR/TOPDOWN/RANGE) * * 返回: 0成功, 负值失败 */intdrm_buddy_alloc_blocks(structdrm_buddy*mm,u64 start,u64 end,u64 size,u64 min_block_size,structlist_head*blocks,unsignedlongflags){structdrm_buddy_block*block=NULL;unsignedintorder;u64 original_size,original_min_size;u64 n_pages;// 1. 参数检查和归一化if(size<mm->chunk_size)return-EINVAL;if(min_block_size<mm->chunk_size)min_block_size=mm->chunk_size;if(!is_power_of_2(min_block_size))return-EINVAL;// 2. 检查是否有足够空间if(size>mm->avail)return-ENOSPC;// 3. 处理范围分配if(flags&DRM_BUDDY_RANGE_ALLOCATION){return__drm_buddy_alloc_range(mm,start,size,NULL,blocks);}// 4. 计算需要的ordern_pages=size>>ilog2(mm->chunk_size);order=fls(n_pages)-1;// log2(n_pages)original_size=size;original_min_size=min_block_size;// 5. 循环分配，直到满足sizeINIT_LIST_HEAD(blocks);while(size){// 5.1 计算当前迭代的ordern_pages=size>>ilog2(mm->chunk_size);order=fls(n_pages)-1;// 5.2 处理min_block_size约束if(BIT_ULL(order)*mm->chunk_size<min_block_size){order=ilog2(min_block_size)-ilog2(mm->chunk_size);}// 5.3 从空闲列表分配块block=alloc_from_freelist(mm,order,flags);if(IS_ERR(block)){// 分配失败，回滚已分配的块drm_buddy_free_list_internal(mm,blocks);returnPTR_ERR(block);}// 5.4 标记为已分配mark_allocated(block);mm->avail-=drm_buddy_block_size(mm,block);if(drm_buddy_block_is_clear(block))mm->clear_avail-=drm_buddy_block_size(mm,block);// 5.5 添加到输出链表list_add_tail(&block->link,blocks);// 5.6 更新剩余大小if(size>drm_buddy_block_size(mm,block))size-=drm_buddy_block_size(mm,block);elsesize=0;}return0;}EXPORT_SYMBOL(drm_buddy_alloc_blocks);

分配流程图

rm_buddy_alloc_blocks() | v +-------------------------------------+ | 1. Parameter validation & preprocess | | - check size >= chunk_size | | - align min_block_size | | - check available space | +------------------+------------------+ | v +--------------+ | range alloc? | +---+------+---+ yes | | no v v __drm_buddy_alloc_range() | | | v | +---------------------+ | | 2. loop alloc | | | while (size > 0) | | +----------+----------+ | | | v | +---------------------+ | | 3. compute order | | | order = log2(pages)| | +----------+----------+ | | | v | +---------------------+ | | 4. adjust min_block | | +----------+----------+ | | | v | +---------------------+ | | 5. alloc one block | | | alloc_from_freelist()| | +----------+----------+ | | | v | +---------------------+ | | 6. mark allocated | | | mark_allocated() | | +----------+----------+ | | | v | +---------------------+ | | 7. add to blocks | | | size -= block_size | | +----------+----------+ | | | +--- back to step 2 | +----> return success

6.2 查找合适大小的块

alloc_from_freelist 函数

// drivers/gpu/drm/drm_buddy.cstaticstructdrm_buddy_block*alloc_from_freelist(structdrm_buddy*mm,unsignedintorder,unsignedlongflags){structdrm_buddy_block*block=NULL;unsignedinttmp;interr;// 1. TOPDOWN分配：从高地址开始if(flags&DRM_BUDDY_TOPDOWN_ALLOCATION){block=get_maxblock(mm,order,flags);if(block)tmp=drm_buddy_block_order(block);}// 2. 正常分配：从低地址开始else{// 遍历从order到max_order的空闲列表for(tmp=order;tmp<=mm->max_order;++tmp){structdrm_buddy_block*tmp_block;// 从链表尾部开始查找（地址低的块）list_for_each_entry_reverse(tmp_block,&mm->free_list[tmp],link){// 检查块是否兼容（清零状态）if(block_incompatible(tmp_block,flags))continue;block=tmp_block;break;}if(block)break;}}// 3. 没找到合适的块if(!block)returnERR_PTR(-ENOSPC);BUG_ON(!drm_buddy_block_is_free(block));// 4. 分裂块直到目标orderwhile(tmp!=order){err=split_block(mm,block);if(unlikely(err))gotoerr_undo;block=block->right;// 使用右子块tmp--;}returnblock;err_undo:if(tmp!=order)__drm_buddy_free(mm,block,false);returnERR_PTR(err);}

查找策略详解

场景: 请求order=2的块 (16KB) 初始状态: free_list[0] → 空 free_list[1] → 空 free_list[2] → 空 free_list[3] → [32KB块] → NULL free_list[4] → [64KB块] → NULL 步骤1: 查找order=2的空闲列表 ↓ 空，继续 步骤2: 查找order=3的空闲列表 ↓ 找到32KB块 步骤3: 判断是否需要分裂 tmp = 3 (块的order) order = 2 (目标order) tmp != order → 需要分裂 步骤4: 分裂32KB块 [32KB, O3] ↓ split_block() [16KB, O2] [16KB, O2] left right 步骤5: 使用右子块 block = block->right tmp = 2 步骤6: 检查是否到达目标 tmp == order → 完成 返回 [16KB, O2] 块 最终状态: free_list[0] → 空 free_list[1] → 空 free_list[2] → [16KB左块] → NULL ← 新增 free_list[3] → 空 free_list[4] → [64KB块] → NULL

TOPDOWN分配

// 获取最高地址的块staticstructdrm_buddy_block*get_maxblock(structdrm_buddy*mm,unsignedintorder,unsignedlongflags){structdrm_buddy_block*max_block=NULL,*block=NULL;unsignedinti;// 从order遍历到max_orderfor(i=order;i<=mm->max_order;++i){structdrm_buddy_block*tmp_block;// 反向遍历（从高地址开始）list_for_each_entry_reverse(tmp_block,&mm->free_list[i],link){if(block_incompatible(tmp_block,flags))continue;block=tmp_block;break;}if(!block)continue;// 更新最大offset的块if(!max_block){max_block=block;continue;}if(drm_buddy_block_offset(block)>drm_buddy_block_offset(max_block)){max_block=block;}}returnmax_block;}

TOPDOWN使用场景：

VRAM布局: 0x00000000 ┌──────────────────┐ │ Visible VRAM │ ← CPU可访问，珍贵 0x20000000 ├──────────────────┤ │ Invisible VRAM │ ← GPU专用 0x200000000└──────────────────┘ 策略: - Display buffer: 必须在Visible区域 → 从低地址分配 - Compute buffer: 任意位置 → TOPDOWN从高地址分配 原因: - 节省Visible区域给真正需要的分配 - 减少碎片化

6.3 块的分裂（Split）过程

split_block 函数

// drivers/gpu/drm/drm_buddy.cstaticintsplit_block(structdrm_buddy*mm,structdrm_buddy_block*block){unsignedintblock_order=drm_buddy_block_order(block);u64 offset=drm_buddy_block_offset(block);u64 size=drm_buddy_block_size(mm,block);structdrm_buddy_block*left,*right;// 1. 创建左子块left=drm_block_alloc(mm,block,block_order-1,offset);if(!left)return-ENOMEM;// 2. 创建右子块right=drm_block_alloc(mm,block,block_order-1,offset+(size/2));if(!right){drm_block_free(mm,left);return-ENOMEM;}// 3. 设置父块的子指针block->left=left;block->right=right;// 4. 标记父块为SPLIT状态mark_split(block);// 5. 标记左右子块为FREEmark_free(mm,left);mark_free(mm,right);// 6. 继承清零标志if(drm_buddy_block_is_clear(block)){mark_cleared(left);mark_cleared(right);}return0;}

分裂过程可视化

初始状态: ┌─────────────────────────────────────┐ │ 64KB块 (Order 4) │ │ offset=0x0 state=FREE │ │ 在 free_list[4] 中 │ └─────────────────────────────────────┘ 调用 split_block(): 步骤1: 创建左子块 ┌──────────────────┐ │ 32KB (Order 3) │ │ offset=0x0 │ │ parent = 64KB块 │ └──────────────────┘ 步骤2: 创建右子块 ┌──────────────────┐ │ 32KB (Order 3) │ │ offset=0x8000 │ │ parent = 64KB块 │ └──────────────────┘ 步骤3: 设置父块指针 ┌─────────────────────────────────────┐ │ 64KB块 (Order 4) │ │ state=SPLIT ← 改变状态 │ │ left → 32KB左块 │ │ right → 32KB右块 │ │ 从 free_list[4] 移除 │ └─────────────────────────────────────┘ ↙ ↘ ┌──────────────────┐ ┌──────────────────┐ │ 32KB左 (O3) │ │ 32KB右 (O3) │ │ state=FREE │ │ state=FREE │ │ 进入free_list[3] │ │ 进入free_list[3] │ └──────────────────┘ └──────────────────┘ 最终二叉树: [64KB, SPLIT] / \ [32KB, FREE] [32KB, FREE]

递归分裂示例

请求: order=0 (4KB) 可用: order=3 (32KB) 在free_list[3] 分裂过程: 迭代1: tmp=3, order=0, 需要分裂 [32KB, O3] → split [16KB, O2, FREE] [16KB, O2, FREE] 使用右块: block = [16KB, O2] tmp = 2 迭代2: tmp=2, order=0, 继续分裂 [16KB, O2] → split [8KB, O1, FREE] [8KB, O1, FREE] 使用右块: block = [8KB, O1] tmp = 1 迭代3: tmp=1, order=0, 继续分裂 [8KB, O1] → split [4KB, O0, FREE] [4KB, O0, FREE] 使用右块: block = [4KB, O0] tmp = 0 迭代4: tmp=0, order=0, 完成！ 返回 [4KB, O0] 块 结果状态: [32KB, O3, SPLIT] / \ [16KB, O2, FREE] [16KB, O2, SPLIT] / \ [8KB, O1, FREE] [8KB, O1, SPLIT] / \ [4KB, O0, FREE] [4KB, O0, 返回] 空闲列表: free_list[0] → [4KB左] → NULL free_list[1] → [8KB左] → NULL free_list[2] → [16KB左] → NULL free_list[3] → 空

6.4 order计算和对齐处理

order计算公式

// 计算容纳size所需的order// 1. 计算需要多少个chunku64 n_pages=size/mm->chunk_size;// 2. 向上取整到2的幂次unsignedintorder=fls(n_pages)-1;// fls: Find Last Set (最高位1的位置)// 例如:// n_pages = 1 (0b1) → fls=1 → order=0 → 1个chunk// n_pages = 2 (0b10) → fls=2 → order=1 → 2个chunk// n_pages = 3 (0b11) → fls=2 → order=1 → 2个chunk (不够!)// n_pages = 4 (0b100) → fls=3 → order=2 → 4个chunk// n_pages = 5 (0b101) → fls=3 → order=2 → 4个chunk (不够!)// 问题: 如果size不是2的幂次，order会取小了！// 解决: 需要向上对齐if(size&(BIT_ULL(order)*mm->chunk_size-1)){// size不是块大小的整数倍，需要更大的order// 但Buddy算法会通过多次分配来满足}

对齐处理

// min_block_size控制最小分配单元// 场景1: 请求1KB，min_block_size=4KBsize=1024;min_block_size=4096;chunk_size=4096;// 计算ordern_pages=1024/4096=0→ order=0(无效!)// 应用min_block_size约束if(BIT_ULL(order)*chunk_size<min_block_size){order=ilog2(min_block_size)-ilog2(chunk_size);// order = log2(4096) - log2(4096) = 0}// 结果: 分配4KB (order=0)，使用1KB，浪费3KB

对齐示例：

请求: 8MB, 对齐64KB chunk_size = 4KB min_block_size = 64KB 计算: n_pages = 8MB / 4KB = 2048 order = log2(2048) = 11 → 块大小 = 4KB * 2^11 = 8MB 检查对齐: 8MB % 64KB = 0 ✓ 天然对齐 但如果请求: 7MB, 对齐64KB n_pages = 7MB / 4KB = 1792 order = log2(1792) = 10 → 块大小 = 4MB (不够!) 解决: 多次分配 - 分配4MB (order=10) - 剩余3MB - 再分配2MB (order=9) → 但2MB < 64KB? 应用min_block_size: order = log2(64KB/4KB) = 4 - 分配64KB (order=4) × 多次

6.5 分配算法的时间复杂度

理论分析

操作 时间复杂度 说明 ──────────────────────────────────────── 查找空闲块 O(log n) 遍历max_order个链表 分裂块 O(log n) 最多分裂max_order次 标记分配 O(1) 修改header和链表操作 总体 O(log n) 主导因素是分裂次数 其中 n = 总chunk数量 = size / chunk_size

最坏情况分析

// 最坏场景: 请求最小块，只有最大块可用size=4KB(order=0)available=4GB(order=20,假设chunk_size=4KB)分裂次数:order20→19→18→...→1→0共20次分裂 每次分裂:-创建2个子块:O(1)-插入到空闲列表:O(1)(尾部插入)总共:20*O(1)=O(20)=O(log n)其中 n=4GB/4KB=1Mlog2(1M)=20

实际性能

测试场景 (8GB VRAM, chunk_size=4KB): 1. 分配4KB (order=0): - 有order=0空闲块: ~100ns - 需要从order=10分裂: ~1μs (10次分裂) - 需要从order=20分裂: ~2μs (20次分裂) 2. 分配64MB (order=14): - 有order=14空闲块: ~100ns - 需要从order=20分裂: ~800ns (6次分裂) 3. 批量分配1000个4KB块: - 连续分配: ~100μs (平均100ns/块) - 随机释放后再分配: ~200μs (碎片影响) 结论: - 单次分配: 微秒级 - 批量分配: 接近O(1)均摊 - 碎片影响: 2-3倍性能下降

💡 重点提示

1. 循环分配: 可能需要多次调用alloc_from_freelist()才能满足总size。

2. 分裂是递归的: 一次可能需要分裂多次才能得到目标order的块。

3. 使用右子块: 分裂后总是使用right子块继续分裂，left子块放回空闲列表。

4. 对齐导致浪费: min_block_size会导致内部碎片，这是权衡的结果。

5. TOPDOWN优化: 对于不需要CPU访问的分配，使用TOPDOWN节省珍贵的Visible区域。

6. 清零兼容性: 如果请求清零但块未清零，会跳过该块寻找下一个。

⚠️ 常见陷阱

❌陷阱1: “分配size就返回size大小的块”

• ✅ 正确: 可能返回多个块，总和≥size，每个块都是2的幂次大小。

❌陷阱2: “order总是log2(size)”

• ✅ 正确: 需要考虑min_block_size，实际order可能更大。

❌陷阱3: “分裂总是成功的”

• ✅ 正确: 分裂需要分配新的block结构，可能内存不足失败。

❌陷阱4: “分配失败意味着没有空闲空间”

• ✅ 正确: 可能有足够总量但没有足够大的连续块（外部碎片）。

📝 实践练习

1. 手动模拟分配:

   初始: 64MB VRAM (order=14, chunk=4KB) 操作序列: 1. 分配16MB (order=12) → 哪些块被分裂？ 2. 分配4MB (order=10) → 从哪个空闲列表取？ 3. 分配8MB (order=11) → 是否需要分裂？ 画出每步后的二叉树状态和空闲列表

2. 计算order:

   // 实现一个函数unsignedintcalculate_order(u64 size,u64 chunk_size){// 你的实现}// 测试calculate_order(4KB,4KB)→0calculate_order(8KB,4KB)→1calculate_order(7KB,4KB)→?(向上取整)calculate_order(1MB,4KB)→?

3. 分析碎片影响:

   场景: 8GB VRAM 分配模式A: 连续分配1000个4MB块 分配模式B: 交替分配4MB和64KB，共1000次 问题: - 哪种模式产生的碎片更多？ - 后续分配32MB块，哪种更容易成功？ - 如何通过分配顺序优化碎片？

📚 本章小结

• 主入口:drm_buddy_alloc_blocks()处理所有分配，支持多种模式
• 查找策略: 从目标order开始向上查找，TOPDOWN从高地址开始
• 分裂机制: 递归分裂大块直到满足order要求
• 对齐处理: min_block_size参数控制最小块大小
• 时间复杂度: O(log n)，非常高效
• 多块分配: 循环调用分配单个块，直到总和≥size

Buddy分配算法通过巧妙的二叉树分裂和空闲列表组织，实现了高效的内存分配。

➡️ 下一步

理解了分配算法后，下一章将学习释放和合并算法，看Buddy如何回收内存并自动整理碎片。

👉 07-Buddy释放与合并算法