08 - 块的分裂与重组

难度: 进阶级预计学习时间: 60分钟前置知识: 06-Buddy分配算法, 07-Buddy释放与合并算法 概述分裂和重组是Buddy算法动态调整块大小的核心机制✂️分裂触发: 当没有合适大小的空闲块时触发二叉树构建: 分裂过程构建完整的二叉树结构Left/Right关系: 左右子块严格的位置关系递归实现: 可能需要递归分裂多次深度限制: 最大分裂深度等于max_order本章详细分析块的分裂机制和二叉树构建过程。8.1 分裂的触发条件何时需要分裂// 场景1: 请求的order空闲列表为空请求 order2(16KB)free_list[2]→ 空 ✗ free_list[3]→[32KB块]✓ 解决:分裂32KB块 → 两个16KB块// 场景2: 需要特定范围的块请求16KB范围[0x1000,0x5000]free_list[2]→[16KB 0x0]✗(范围外)[16KB 0x8000]✗(范围外)free_list[3]→[32KB 0x0]✓(包含范围)解决:分裂32KB块使用合适的子块// 场景3: 清零要求不匹配请求 order2,flagsCLEAR free_list[2]→[16KB,!CLEAR]✗ free_list[3]→[32KB,CLEAR]✓ 解决:分裂32KB块子块继承CLEAR标志分裂判断逻辑// 在 alloc_from_freelist() 中// 1. 查找从order到max_order的空闲列表for(tmporder;tmpmm-max_order;tmp){list_for_each_entry_reverse(block,mm-free_list[tmp],link){if(block_incompatible(block,flags))continue;// 清零状态不匹配found_blockblock;break;}if(found_block)break;}// 2. 如果找到的块order大于目标order需要分裂if(tmporder){// 递归分裂 tmp → tmp-1 → ... → orderwhile(tmp!order){split_block(mm,block);blockblock-right;// 使用右子块tmp--;}}8.2 二叉树构建过程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. 计算子块参数unsignedintchild_orderblock_order-1;u64 half_sizesize/2;// 2. 创建左子块leftdrm_block_alloc(mm,block,// parentchild_order,// orderoffset);// offsetif(!left)return-ENOMEM;// 3. 创建右子块rightdrm_block_alloc(mm,block,child_order,offsethalf_size);// offset偏移if(!right){drm_block_free(mm,left);return-ENOMEM;}// 4. 连接父子关系block-leftleft;block-rightright;// 5. 从空闲列表移除父块标记为SPLITmark_split(block);// 6. 将子块加入空闲列表标记为FREEmark_free(mm,left);mark_free(mm,right);// 7. 继承父块的清零标志if(drm_buddy_block_is_clear(block)){mark_cleared(left);mark_cleared(right);}return0;}二叉树结构演变初始状态: 单个64KB块 (order4) ┌─────────────────────────────────────────────────┐ │ [64KB, order4, FREE] │ │ offset0x0 │ │ 在 free_list[4] │ └─────────────────────────────────────────────────┘ 分裂第1次: split_block(64KB) [64KB, order4, SPLIT] ← 从free_list[4]移除 offset0x0 | ┌─────────┴─────────┐ ↓ ↓ [32KB, o3, FREE] [32KB, o3, FREE] offset0x0 offset0x8000 进入free_list[3] 进入free_list[3] 内存布局: 0x00000 ┌──────────────┐ │ 32KB左 │ ← left 0x08000 ├──────────────┤ │ 32KB右 │ ← right 0x10000 └──────────────┘ 分裂第2次: split_block(32KB右块) [64KB, order4, SPLIT] | ┌─────────┴─────────┐ ↓ ↓ [32KB, FREE] [32KB, SPLIT] ← 从free_list[3]移除 | ┌─────────┴─────────┐ ↓ ↓ [16KB, o2, FREE] [16KB, o2, FREE] offset0x8000 offset0xC000 进入free_list[2] 进入free_list[2] 内存布局: 0x00000 ┌──────────────┐ │ 32KB左 │ ← 未分裂 0x08000 ├──────────┬───┤ │ 16KB左 │ │ ← 新的left 0x0C000 ├──────────┤ │ │ 16KB右 │ │ ← 新的right 0x10000 └──────────┴───┘ 分裂第3次: split_block(16KB右块) [64KB, SPLIT] | ┌─────────┴─────────┐ ↓ ↓ [32KB, FREE] [32KB, SPLIT] | ┌─────────┴─────────┐ ↓ ↓ [16KB, FREE] [16KB, SPLIT] | ┌─────────┴─────────┐ ↓ ↓ [8KB, o1, FREE] [8KB, o1, FREE] offset0xC000 offset0xE000 进入free_list[1] 进入free_list[1] 最终二叉树 (完整4层): [64KB, o4] | ┌─────────┴─────────┐ [32KB, o3] [32KB, o3] | | ┌─────┘ ┌─────┴─────┐ (未分裂) [16KB, o2] [16KB, o2] | | ┌─────┘ ┌─────┴─────┐ (未分裂) [8KB, o1] [8KB, o1]8.3 Left/Right子块关系位置规则// 严格的位置关系父块:[offset,offsetsize)左子块:[offset,offsetsize/2)右子块:[offsetsize/2,offsetsize)// 数学性质1.左子块offset父块offset2.右子块offset父块offsetsize/23.两子块大小相同父块size/24.两子块连续无间隙示例计算父块: offset0x8000, size32KB (0x8000) 左子块: offset 0x8000 size 32KB / 2 16KB (0x4000) range [0x8000, 0xC000) 右子块: offset 0x8000 0x4000 0xC000 size 16KB (0x4000) range [0xC000, 0x10000) 验证: - 左子块结束 0xC000 - 右子块开始 0xC000 ✓ 连续 - 右子块结束 0x10000 父块结束 ✓对齐保证// 子块天然对齐父块对齐:offset%size0左子块对齐:offset%(size/2)0∵ size/2size ∴ offset%(size/2)0✓ 右子块对齐:(offsetsize/2)%(size/2)0∵ size/2是2的幂次 ∴(offsetsize/2)%(size/2)0✓ 结论:分裂操作自动维护对齐8.4 分裂的递归实现递归分裂示例// 场景: 请求order0 (4KB)只有order3 (32KB)可用intrecursive_split_example(){structdrm_buddy_block*block;unsignedinttmp,order;order0;// 目标ordertmp3;// 当前块orderblock/* 32KB块 */;// 递归分裂while(tmp!order){printf(Splitting order%u block\n,tmp);split_block(mm,block);// 分裂后:// - parent: [32KB, SPLIT]// - left: [16KB, FREE] → 加入free_list[tmp-1]// - right: [16KB, FREE]blockblock-right;// 继续分裂右子块tmp--;printf(Now at order%u\n,tmp);}printf(Final block: order%u\n,tmp);return0;}// 输出:// Splitting order3 block// Now at order2// Splitting order2 block// Now at order1// Splitting order1 block// Now at order0// Final block: order0为什么总是使用右子块策略: 分裂后使用右子块继续分裂左子块放回空闲列表 原因1: 内存布局 - 右子块在高地址 - 左子块在低地址 - 保持低地址块空闲便于后续范围分配 原因2: 简化实现 - 固定策略代码简单 - 减少选择逻辑的复杂度 原因3: 局部性 - 高地址块使用低地址块空闲 - 符合TOPDOWN分配策略 示例: 原始: [0x0, 64KB) 分裂: [0x0, 32KB) [32KB, 64KB) ↑ 空闲 ↑ 继续分裂 进一步分裂: [0x0, 32KB) [32KB, 48KB) [48KB, 64KB) ↑ 空闲 ↑ 空闲 ↑ 继续 最终: 低地址保留了大的连续空闲块8.5 分裂深度限制最大分裂深度// 最大分裂深度 max_order例如:8GB VRAM,chunk_size4KB max_orderlog2(8GB/4KB)log2(2M)21最大深度场景:-请求:order0(4KB)-可用:order21(8GB)-分裂次数:21分裂链:21→20→19→...→2→1→0防止过度分裂// 最小块大小限制unsignedintmin_orderilog2(min_block_size)-ilog2(mm-chunk_size);// 例如: min_block_size 64KB, chunk_size 4KBmin_orderlog2(64KB)-log2(4KB)16-124// 分配时检查if(ordermin_order)ordermin_order;// 不允许比min_order更小// 效果: 限制分裂深度max_split_depthmax_order-min_order分裂失败处理// split_block() 可能失败intsplit_block(structdrm_buddy*mm,structdrm_buddy_block*block){// 分配左子块leftdrm_block_alloc(mm,block,order-1,offset);if(!left)return-ENOMEM;// 失败// 分配右子块rightdrm_block_alloc(mm,block,order-1,offsetsize/2);if(!right){drm_block_free(mm,left);// 回滚return-ENOMEM;}// 成功return0;}// 调用者处理失败errsplit_block(mm,block);if(err){// 分裂失败无法继续// 尝试其他块或返回错误returnERR_PTR(err);} 重点提示分裂是延迟的: 只有在需要时才分裂不预先分裂。左右关系固定: 左子块总是低地址右子块总是高地址。继承清零标志: 子块自动继承父块的清零状态。递归深度可控: 通过min_block_size限制分裂深度。分裂可能失败: 需要分配新的block结构体可能OOM。使用右子块策略: 简化实现优化内存布局。⚠️ 常见陷阱❌陷阱1: “分裂后子块大小不同”✅ 正确: 左右子块大小完全相同都是父块的一半。❌陷阱2: “可以任意分裂到order0”✅ 正确: 受min_block_size限制不能无限分裂。❌陷阱3: “分裂后父块消失”✅ 正确: 父块保留但状态变为SPLIT用于后续合并。❌陷阱4: “左右子块可以互换”✅ 正确: 位置固定左子块必须在低地址。 实践练习手动分裂:初始: [128KB, order5, offset0x0, FREE] 问题1: 分裂1次后的状态 问题2: 左子块的offset和size是多少 问题3: 右子块的offset和size是多少 问题4: 父块的状态变成什么 问题5: 子块在哪个free_list中递归分裂追踪:场景: 请求order1 (8KB)只有order4 (64KB) 填写分裂过程: 迭代1: 当前块: [64KB, order4] 分裂成: [___ KB, order___] [___ KB, order___] 使用: ___ (left/right) 剩余order: ___ 迭代2: 当前块: [___ KB, order___] 分裂成: [___ KB, order___] [___ KB, order___] 使用: ___ (left/right) 剩余order: ___ ... (继续直到order1) 最终空闲块分布: free_list[0]: ___ free_list[1]: ___ free_list[2]: ___ free_list[3]: ___对齐验证:// 验证子块对齐voidverify_alignment(structdrm_buddy_block*block){u64 offsetdrm_buddy_block_offset(block);u64 sizedrm_buddy_block_size(mm,block);// 父块对齐检查assert(offset%size0);split_block(mm,block);// 左子块对齐检查u64 left_offsetdrm_buddy_block_offset(block-left);u64 left_sizedrm_buddy_block_size(mm,block-left);assert(left_offset%left_size0);// 右子块对齐检查u64 right_offsetdrm_buddy_block_offset(block-right);u64 right_sizedrm_buddy_block_size(mm,block-right);assert(right_offset%right_size0);// 连续性检查assert(left_offsetleft_sizeright_offset);} 本章小结分裂触发: 当目标order空闲列表为空时从更高order分裂二叉树构建: 每次分裂创建两个子块构建完整二叉树Left/Right: 固定位置关系左低右高大小相同递归实现: 可能需要多次分裂使用右子块继续深度限制: 最大max_order可通过min_block_size限制清零继承: 子块自动继承父块清零标志块的分裂机制是Buddy算法灵活性的来源通过递归分裂实现了任意大小的块分配。➡️ 下一步理解了分裂机制后下一章将学习对齐和范围限制的实现这是GPU显存分配的关键需求。 09-对齐和范围限制