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*blockNULL;unsignedintorder;u64 original_size,original_min_size;u64 n_pages;// 1. 参数检查和归一化if(sizemm-chunk_size)return-EINVAL;if(min_block_sizemm-chunk_size)min_block_sizemm-chunk_size;if(!is_power_of_2(min_block_size))return-EINVAL;// 2. 检查是否有足够空间if(sizemm-avail)return-ENOSPC;// 3. 处理范围分配if(flagsDRM_BUDDY_RANGE_ALLOCATION){return__drm_buddy_alloc_range(mm,start,size,NULL,blocks);}// 4. 计算需要的ordern_pagessizeilog2(mm-chunk_size);orderfls(n_pages)-1;// log2(n_pages)original_sizesize;original_min_sizemin_block_size;// 5. 循环分配直到满足sizeINIT_LIST_HEAD(blocks);while(size){// 5.1 计算当前迭代的ordern_pagessizeilog2(mm-chunk_size);orderfls(n_pages)-1;// 5.2 处理min_block_size约束if(BIT_ULL(order)*mm-chunk_sizemin_block_size){orderilog2(min_block_size)-ilog2(mm-chunk_size);}// 5.3 从空闲列表分配块blockalloc_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(sizedrm_buddy_block_size(mm,block))size-drm_buddy_block_size(mm,block);elsesize0;}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 success6.2 查找合适大小的块alloc_from_freelist 函数// drivers/gpu/drm/drm_buddy.cstaticstructdrm_buddy_block*alloc_from_freelist(structdrm_buddy*mm,unsignedintorder,unsignedlongflags){structdrm_buddy_block*blockNULL;unsignedinttmp;interr;// 1. TOPDOWN分配从高地址开始if(flagsDRM_BUDDY_TOPDOWN_ALLOCATION){blockget_maxblock(mm,order,flags);if(block)tmpdrm_buddy_block_order(block);}// 2. 正常分配从低地址开始else{// 遍历从order到max_order的空闲列表for(tmporder;tmpmm-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;blocktmp_block;break;}if(block)break;}}// 3. 没找到合适的块if(!block)returnERR_PTR(-ENOSPC);BUG_ON(!drm_buddy_block_is_free(block));// 4. 分裂块直到目标orderwhile(tmp!order){errsplit_block(mm,block);if(unlikely(err))gotoerr_undo;blockblock-right;// 使用右子块tmp--;}returnblock;err_undo:if(tmp!order)__drm_buddy_free(mm,block,false);returnERR_PTR(err);}查找策略详解场景: 请求order2的块 (16KB) 初始状态: free_list[0] → 空 free_list[1] → 空 free_list[2] → 空 free_list[3] → [32KB块] → NULL free_list[4] → [64KB块] → NULL 步骤1: 查找order2的空闲列表 ↓ 空继续 步骤2: 查找order3的空闲列表 ↓ 找到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块] → NULLTOPDOWN分配// 获取最高地址的块staticstructdrm_buddy_block*get_maxblock(structdrm_buddy*mm,unsignedintorder,unsignedlongflags){structdrm_buddy_block*max_blockNULL,*blockNULL;unsignedinti;// 从order遍历到max_orderfor(iorder;imm-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;blocktmp_block;break;}if(!block)continue;// 更新最大offset的块if(!max_block){max_blockblock;continue;}if(drm_buddy_block_offset(block)drm_buddy_block_offset(max_block)){max_blockblock;}}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_orderdrm_buddy_block_order(block);u64 offsetdrm_buddy_block_offset(block);u64 sizedrm_buddy_block_size(mm,block);structdrm_buddy_block*left,*right;// 1. 创建左子块leftdrm_block_alloc(mm,block,block_order-1,offset);if(!left)return-ENOMEM;// 2. 创建右子块rightdrm_block_alloc(mm,block,block_order-1,offset(size/2));if(!right){drm_block_free(mm,left);return-ENOMEM;}// 3. 设置父块的子指针block-leftleft;block-rightright;// 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) │ │ offset0x0 stateFREE │ │ 在 free_list[4] 中 │ └─────────────────────────────────────┘ 调用 split_block(): 步骤1: 创建左子块 ┌──────────────────┐ │ 32KB (Order 3) │ │ offset0x0 │ │ parent 64KB块 │ └──────────────────┘ 步骤2: 创建右子块 ┌──────────────────┐ │ 32KB (Order 3) │ │ offset0x8000 │ │ parent 64KB块 │ └──────────────────┘ 步骤3: 设置父块指针 ┌─────────────────────────────────────┐ │ 64KB块 (Order 4) │ │ stateSPLIT ← 改变状态 │ │ left → 32KB左块 │ │ right → 32KB右块 │ │ 从 free_list[4] 移除 │ └─────────────────────────────────────┘ ↙ ↘ ┌──────────────────┐ ┌──────────────────┐ │ 32KB左 (O3) │ │ 32KB右 (O3) │ │ stateFREE │ │ stateFREE │ │ 进入free_list[3] │ │ 进入free_list[3] │ └──────────────────┘ └──────────────────┘ 最终二叉树: [64KB, SPLIT] / \ [32KB, FREE] [32KB, FREE]递归分裂示例请求: order0 (4KB) 可用: order3 (32KB) 在free_list[3] 分裂过程: 迭代1: tmp3, order0, 需要分裂 [32KB, O3] → split [16KB, O2, FREE] [16KB, O2, FREE] 使用右块: block [16KB, O2] tmp 2 迭代2: tmp2, order0, 继续分裂 [16KB, O2] → split [8KB, O1, FREE] [8KB, O1, FREE] 使用右块: block [8KB, O1] tmp 1 迭代3: tmp1, order0, 继续分裂 [8KB, O1] → split [4KB, O0, FREE] [4KB, O0, FREE] 使用右块: block [4KB, O0] tmp 0 迭代4: tmp0, order0, 完成 返回 [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_pagessize/mm-chunk_size;// 2. 向上取整到2的幂次unsignedintorderfls(n_pages)-1;// fls: Find Last Set (最高位1的位置)// 例如:// n_pages 1 (0b1) → fls1 → order0 → 1个chunk// n_pages 2 (0b10) → fls2 → order1 → 2个chunk// n_pages 3 (0b11) → fls2 → order1 → 2个chunk (不够!)// n_pages 4 (0b100) → fls3 → order2 → 4个chunk// n_pages 5 (0b101) → fls3 → order2 → 4个chunk (不够!)// 问题: 如果size不是2的幂次order会取小了// 解决: 需要向上对齐if(size(BIT_ULL(order)*mm-chunk_size-1)){// size不是块大小的整数倍需要更大的order// 但Buddy算法会通过多次分配来满足}对齐处理// min_block_size控制最小分配单元// 场景1: 请求1KBmin_block_size4KBsize1024;min_block_size4096;chunk_size4096;// 计算ordern_pages1024/40960→ order0(无效!)// 应用min_block_size约束if(BIT_ULL(order)*chunk_sizemin_block_size){orderilog2(min_block_size)-ilog2(chunk_size);// order log2(4096) - log2(4096) 0}// 结果: 分配4KB (order0)使用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 (order10) - 剩余3MB - 再分配2MB (order9) → 但2MB 64KB? 应用min_block_size: order log2(64KB/4KB) 4 - 分配64KB (order4) × 多次6.5 分配算法的时间复杂度理论分析操作 时间复杂度 说明 ──────────────────────────────────────── 查找空闲块 O(log n) 遍历max_order个链表 分裂块 O(log n) 最多分裂max_order次 标记分配 O(1) 修改header和链表操作 总体 O(log n) 主导因素是分裂次数 其中 n 总chunk数量 size / chunk_size最坏情况分析// 最坏场景: 请求最小块只有最大块可用size4KB(order0)available4GB(order20,假设chunk_size4KB)分裂次数:order20→19→18→...→1→0共20次分裂 每次分裂:-创建2个子块:O(1)-插入到空闲列表:O(1)(尾部插入)总共:20*O(1)O(20)O(log n)其中 n4GB/4KB1Mlog2(1M)20实际性能测试场景 (8GB VRAM, chunk_size4KB): 1. 分配4KB (order0): - 有order0空闲块: ~100ns - 需要从order10分裂: ~1μs (10次分裂) - 需要从order20分裂: ~2μs (20次分裂) 2. 分配64MB (order14): - 有order14空闲块: ~100ns - 需要从order20分裂: ~800ns (6次分裂) 3. 批量分配1000个4KB块: - 连续分配: ~100μs (平均100ns/块) - 随机释放后再分配: ~200μs (碎片影响) 结论: - 单次分配: 微秒级 - 批量分配: 接近O(1)均摊 - 碎片影响: 2-3倍性能下降 重点提示循环分配: 可能需要多次调用alloc_from_freelist()才能满足总size。分裂是递归的: 一次可能需要分裂多次才能得到目标order的块。使用右子块: 分裂后总是使用right子块继续分裂left子块放回空闲列表。对齐导致浪费: min_block_size会导致内部碎片这是权衡的结果。TOPDOWN优化: 对于不需要CPU访问的分配使用TOPDOWN节省珍贵的Visible区域。清零兼容性: 如果请求清零但块未清零会跳过该块寻找下一个。⚠️ 常见陷阱❌陷阱1: “分配size就返回size大小的块”✅ 正确: 可能返回多个块总和≥size每个块都是2的幂次大小。❌陷阱2: “order总是log2(size)”✅ 正确: 需要考虑min_block_size实际order可能更大。❌陷阱3: “分裂总是成功的”✅ 正确: 分裂需要分配新的block结构可能内存不足失败。❌陷阱4: “分配失败意味着没有空闲空间”✅ 正确: 可能有足够总量但没有足够大的连续块外部碎片。 实践练习手动模拟分配:初始: 64MB VRAM (order14, chunk4KB) 操作序列: 1. 分配16MB (order12) → 哪些块被分裂 2. 分配4MB (order10) → 从哪个空闲列表取 3. 分配8MB (order11) → 是否需要分裂 画出每步后的二叉树状态和空闲列表计算order:// 实现一个函数unsignedintcalculate_order(u64 size,u64 chunk_size){// 你的实现}// 测试calculate_order(4KB,4KB)→0calculate_order(8KB,4KB)→1calculate_order(7KB,4KB)→?(向上取整)calculate_order(1MB,4KB)→?分析碎片影响:场景: 8GB VRAM 分配模式A: 连续分配1000个4MB块 分配模式B: 交替分配4MB和64KB共1000次 问题: - 哪种模式产生的碎片更多 - 后续分配32MB块哪种更容易成功 - 如何通过分配顺序优化碎片 本章小结主入口:drm_buddy_alloc_blocks()处理所有分配支持多种模式查找策略: 从目标order开始向上查找TOPDOWN从高地址开始分裂机制: 递归分裂大块直到满足order要求对齐处理: min_block_size参数控制最小块大小时间复杂度: O(log n)非常高效多块分配: 循环调用分配单个块直到总和≥sizeBuddy分配算法通过巧妙的二叉树分裂和空闲列表组织实现了高效的内存分配。➡️ 下一步理解了分配算法后下一章将学习释放和合并算法看Buddy如何回收内存并自动整理碎片。 07-Buddy释放与合并算法