4. Buddy内存分配算法：从原理到GPU实战

说到显存碎片治理，Buddy算法是个绕不开的话题。我最早接触它是在做Linux内核驱动开发的时候，后来到了GPU驱动领域，发现它依然是显存管理的核心方案之一。今天我们就来聊聊这个老朋友。

4.1 Buddy算法原理：分而治之的智慧

Buddy算法的思想其实很简单。说白了，就是把内存块不断对半切分，直到满足分配需求。反过来，释放时就把相邻的兄弟块合并回去。

我习惯用个比喻来理解：想象你有一块2GB的显存，就像一张大饼。有人要256MB，你就对半切，再对半切，直到切出256MB的块。释放时，看看旁边的兄弟块是不是也空闲，是的话就合并回去。

具体来说，Buddy算法维护了一个空闲链表数组，每个索引对应一种大小的内存块：

// 简化版Buddy数据结构
#define MAX_ORDER 11  // 2^0 到 2^10 页

struct buddy_system {
    struct list_head free_area[MAX_ORDER];  // 每个order的空闲链表
    unsigned long *bitmap;                  // 伙伴状态位图
    unsigned long total_pages;              // 总页数
};

分配过程是这样的：

1. 计算需要的order（2^order页）
2. 从对应order的空闲链表找块
3. 如果链表为空，去更高order借一块
4. 借来的块对半切，一半放回低order链表
5. 另一半返回给调用者

4.2 Buddy在GPU驱动中的应用

在NVIDIA的GPU驱动中，Buddy算法被广泛用于显存管理。我记得有一次调试一个显存泄漏的问题，就是通过分析Buddy的空闲链表状态找到的线索。

GPU驱动中的Buddy实现比通用版本更复杂，主要因为：

• 显存对齐要求：GPU对显存地址对齐有严格限制
• 多级缓存：L1/L2 cache line对齐会影响分配策略
• 并发访问：多个SM同时分配显存，需要加锁保护

实际代码中，GPU驱动的Buddy分配器通常长这样：

// GPU驱动中的Buddy分配（伪代码）
gpu_mem_t *gpu_buddy_alloc(struct gpu_device *dev, 
                           size_t size, 
                           unsigned int align) {
    unsigned int order = size_to_order(size);
    struct buddy_block *block;
    
    // 加锁保护
    spin_lock(&dev->mem_lock);
    
    // 尝试分配
    block = __buddy_alloc(dev->buddy, order);
    if (!block) {
        // 触发显存压缩（defragmentation）
        gpu_mem_defrag(dev);
        block = __buddy_alloc(dev->buddy, order);
    }
    
    spin_unlock(&dev->mem_lock);
    
    if (!block) {
        // 真的没内存了，返回OOM
        return NULL;
    }
    
    // 地址对齐处理
    return align_block(block, align);
}

4.3 Buddy的优缺点：没有银弹

任何算法都有两面性，Buddy也不例外。我用一张表来总结：

优点	缺点
分配释放速度快（O(log N)）	内部碎片严重（最多浪费50%）
实现简单，代码量少	外部碎片依然存在
合并操作高效	对非2的幂次大小不友好
地址连续性好	大块分配容易失败

优点详解：

速度是真的快。我做过测试，Buddy分配器的平均分配时间只有slab分配器的1/5左右。为什么？因为不需要遍历链表，直接通过位运算就能定位到合适的块。

缺点详解：

内部碎片是个大问题。你想想看，如果我要分配3页，Buddy只能给我4页（2^2），那1页就浪费了。在显存动辄几十GB的今天，这点浪费似乎不算什么，但在嵌入式GPU上，这就是大问题。

4.4 实战中的优化技巧

既然Buddy有这些缺点，我们在实际项目中怎么优化呢？我分享几个经验：

1. 预分配大块：在初始化时一次性分配大块显存，然后自己管理
2. 对象池化：对固定大小的对象使用对象池，绕过Buddy
3. 碎片整理：定期触发显存压缩，合并空闲块
4. 分配策略调整：从低order开始分配，尽量不拆大块

嗯，这里要注意一点：碎片整理不是免费的。它需要移动数据，会带来性能开销。我一般建议在GPU空闲时做，或者设置一个碎片率阈值，超过阈值才触发。

4.5 知识体系总览

为了让你更直观地理解Buddy算法的全貌，我画了张图：

这张图把Buddy算法的核心要素都串起来了。从原理到应用，再到优化，是一个完整的闭环。

想要更多资料，联系可可