08 - 块的分裂与重组

难度: 🟡 进阶级
预计学习时间: 60分钟
前置知识: 06-Buddy分配算法, 07-Buddy释放与合并算法

---

📋 概述

分裂和重组是Buddy算法动态调整块大小的核心机制：

• ✂️分裂触发: 当没有合适大小的空闲块时触发
• 🌲二叉树构建: 分裂过程构建完整的二叉树结构
• 🔗Left/Right关系: 左右子块严格的位置关系
• 🔄递归实现: 可能需要递归分裂多次
• 📏深度限制: 最大分裂深度等于max_order

本章详细分析块的分裂机制和二叉树构建过程。

---

8.1 分裂的触发条件

何时需要分裂

// 场景1: 请求的order空闲列表为空请求 order=2(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: 清零要求不匹配请求 order=2,flags=CLEAR free_list[2]→[16KB,!CLEAR]✗ free_list[3]→[32KB,CLEAR]✓ 解决:分裂32KB块，子块继承CLEAR标志

分裂判断逻辑

// 在 alloc_from_freelist() 中// 1. 查找从order到max_order的空闲列表for(tmp=order;tmp<=mm->max_order;++tmp){list_for_each_entry_reverse(block,&mm->free_list[tmp],link){if(block_incompatible(block,flags))continue;// 清零状态不匹配found_block=block;break;}if(found_block)break;}// 2. 如果找到的块order大于目标order，需要分裂if(tmp>order){// 递归分裂 tmp → tmp-1 → ... → orderwhile(tmp!=order){split_block(mm,block);block=block->right;// 使用右子块tmp--;}}

---

8.2 二叉树构建过程

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. 计算子块参数unsignedintchild_order=block_order-1;u64 half_size=size/2;// 2. 创建左子块left=drm_block_alloc(mm,block,// parentchild_order,// orderoffset);// offsetif(!left)return-ENOMEM;// 3. 创建右子块right=drm_block_alloc(mm,block,child_order,offset+half_size);// offset偏移if(!right){drm_block_free(mm,left);return-ENOMEM;}// 4. 连接父子关系block->left=left;block->right=right;// 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块 (order=4) ┌─────────────────────────────────────────────────┐ │ [64KB, order=4, FREE] │ │ offset=0x0 │ │ 在 free_list[4] │ └─────────────────────────────────────────────────┘ 分裂第1次: split_block(64KB) [64KB, order=4, SPLIT] ← 从free_list[4]移除 offset=0x0 | ┌─────────┴─────────┐ ↓ ↓ [32KB, o=3, FREE] [32KB, o=3, FREE] offset=0x0 offset=0x8000 进入free_list[3] 进入free_list[3] 内存布局: 0x00000 ┌──────────────┐ │ 32KB左 │ ← left 0x08000 ├──────────────┤ │ 32KB右 │ ← right 0x10000 └──────────────┘ 分裂第2次: split_block(32KB右块) [64KB, order=4, SPLIT] | ┌─────────┴─────────┐ ↓ ↓ [32KB, FREE] [32KB, SPLIT] ← 从free_list[3]移除 | ┌─────────┴─────────┐ ↓ ↓ [16KB, o=2, FREE] [16KB, o=2, FREE] offset=0x8000 offset=0xC000 进入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, o=1, FREE] [8KB, o=1, FREE] offset=0xC000 offset=0xE000 进入free_list[1] 进入free_list[1] 最终二叉树 (完整4层): [64KB, o=4] | ┌─────────┴─────────┐ [32KB, o=3] [32KB, o=3] | | ┌─────┘ ┌─────┴─────┐ (未分裂) [16KB, o=2] [16KB, o=2] | | ┌─────┘ ┌─────┴─────┐ (未分裂) [8KB, o=1] [8KB, o=1]

---

8.3 Left/Right子块关系

位置规则

// 严格的位置关系父块:[offset,offset+size)左子块:[offset,offset+size/2)右子块:[offset+size/2,offset+size)// 数学性质1.左子块offset=父块offset2.右子块offset=父块offset+size/23.两子块大小相同=父块size/24.两子块连续，无间隙

示例计算

父块: offset=0x8000, size=32KB (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%size==0左子块对齐:offset%(size/2)==0∵ size/2<size ∴ offset%(size/2)==0✓ 右子块对齐:(offset+size/2)%(size/2)==0∵ size/2是2的幂次 ∴(offset+size/2)%(size/2)==0✓ 结论:分裂操作自动维护对齐

---

8.4 分裂的递归实现

递归分裂示例

// 场景: 请求order=0 (4KB)，只有order=3 (32KB)可用intrecursive_split_example(){structdrm_buddy_block*block;unsignedinttmp,order;order=0;// 目标ordertmp=3;// 当前块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]block=block->right;// 继续分裂右子块tmp--;printf("Now at order=%u\n",tmp);}printf("Final block: order=%u\n",tmp);return0;}// 输出:// Splitting order=3 block// Now at order=2// Splitting order=2 block// Now at order=1// Splitting order=1 block// Now at order=0// Final block: order=0

为什么总是使用右子块

策略: 分裂后使用右子块继续分裂，左子块放回空闲列表 原因1: 内存布局 - 右子块在高地址 - 左子块在低地址 - 保持低地址块空闲，便于后续范围分配 原因2: 简化实现 - 固定策略，代码简单 - 减少选择逻辑的复杂度 原因3: 局部性 - 高地址块使用，低地址块空闲 - 符合TOPDOWN分配策略 示例: 原始: [0x0, 64KB) 分裂: [0x0, 32KB) [32KB, 64KB) ↑ 空闲 ↑ 继续分裂 进一步分裂: [0x0, 32KB) [32KB, 48KB) [48KB, 64KB) ↑ 空闲 ↑ 空闲 ↑ 继续 最终: 低地址保留了大的连续空闲块

---

8.5 分裂深度限制

最大分裂深度

// 最大分裂深度 = max_order例如:8GB VRAM,chunk_size=4KB max_order=log2(8GB/4KB)=log2(2M)=21最大深度场景:-请求:order=0(4KB)-可用:order=21(8GB)-分裂次数:21分裂链:21→20→19→...→2→1→0

防止过度分裂

// 最小块大小限制unsignedintmin_order=ilog2(min_block_size)-ilog2(mm->chunk_size);// 例如: min_block_size = 64KB, chunk_size = 4KBmin_order=log2(64KB)-log2(4KB)=16-12=4// 分配时检查if(order<min_order)order=min_order;// 不允许比min_order更小// 效果: 限制分裂深度max_split_depth=max_order-min_order

分裂失败处理

// split_block() 可能失败intsplit_block(structdrm_buddy*mm,structdrm_buddy_block*block){// 分配左子块left=drm_block_alloc(mm,block,order-1,offset);if(!left)return-ENOMEM;// 失败！// 分配右子块right=drm_block_alloc(mm,block,order-1,offset+size/2);if(!right){drm_block_free(mm,left);// 回滚return-ENOMEM;}// 成功return0;}// 调用者处理失败err=split_block(mm,block);if(err){// 分裂失败，无法继续// 尝试其他块或返回错误returnERR_PTR(err);}

---

💡 重点提示

1. 分裂是延迟的: 只有在需要时才分裂，不预先分裂。

2. 左右关系固定: 左子块总是低地址，右子块总是高地址。

3. 继承清零标志: 子块自动继承父块的清零状态。

4. 递归深度可控: 通过min_block_size限制分裂深度。

5. 分裂可能失败: 需要分配新的block结构体，可能OOM。

6. 使用右子块策略: 简化实现，优化内存布局。

---

⚠️ 常见陷阱

❌陷阱1: “分裂后子块大小不同”

• ✅ 正确: 左右子块大小完全相同，都是父块的一半。

❌陷阱2: “可以任意分裂到order=0”

• ✅ 正确: 受min_block_size限制，不能无限分裂。

❌陷阱3: “分裂后父块消失”

• ✅ 正确: 父块保留但状态变为SPLIT，用于后续合并。

❌陷阱4: “左右子块可以互换”

• ✅ 正确: 位置固定，左子块必须在低地址。

---

📝 实践练习

1. 手动分裂:

   初始: [128KB, order=5, offset=0x0, FREE] 问题1: 分裂1次后的状态？ 问题2: 左子块的offset和size是多少？ 问题3: 右子块的offset和size是多少？ 问题4: 父块的状态变成什么？ 问题5: 子块在哪个free_list中？

2. 递归分裂追踪:

   场景: 请求order=1 (8KB)，只有order=4 (64KB) 填写分裂过程: 迭代1: 当前块: [64KB, order=4] 分裂成: [___ KB, order=___] + [___ KB, order=___] 使用: ___ (left/right) 剩余order: ___ 迭代2: 当前块: [___ KB, order=___] 分裂成: [___ KB, order=___] + [___ KB, order=___] 使用: ___ (left/right) 剩余order: ___ ... (继续直到order=1) 最终空闲块分布: free_list[0]: ___ free_list[1]: ___ free_list[2]: ___ free_list[3]: ___

3. 对齐验证:

   // 验证子块对齐voidverify_alignment(structdrm_buddy_block*block){u64 offset=drm_buddy_block_offset(block);u64 size=drm_buddy_block_size(mm,block);// 父块对齐检查assert(offset%size==0);split_block(mm,block);// 左子块对齐检查u64 left_offset=drm_buddy_block_offset(block->left);u64 left_size=drm_buddy_block_size(mm,block->left);assert(left_offset%left_size==0);// 右子块对齐检查u64 right_offset=drm_buddy_block_offset(block->right);u64 right_size=drm_buddy_block_size(mm,block->right);assert(right_offset%right_size==0);// 连续性检查assert(left_offset+left_size==right_offset);}

---

📚 本章小结

• 分裂触发: 当目标order空闲列表为空时从更高order分裂
• 二叉树构建: 每次分裂创建两个子块，构建完整二叉树
• Left/Right: 固定位置关系，左低右高，大小相同
• 递归实现: 可能需要多次分裂，使用右子块继续
• 深度限制: 最大max_order，可通过min_block_size限制
• 清零继承: 子块自动继承父块清零标志

块的分裂机制是Buddy算法灵活性的来源，通过递归分裂实现了任意大小的块分配。

---

➡️ 下一步

理解了分裂机制后，下一章将学习对齐和范围限制的实现，这是GPU显存分配的关键需求。

👉 09-对齐和范围限制

---