核心数据结构设计：空闲链表与块管理

好，咱们开始动手了。上一章我们聊了显存池的整体思路，说白了就是「先借一大块，再自己慢慢分」。那怎么分？用什么数据结构来记录哪些内存是空闲的、哪些被占用了？这就是本章要解决的核心问题。

我个人习惯，在设计任何内存管理器之前，先把数据结构想清楚。数据结构定好了，代码写起来就是水到渠成的事。你想想看，如果连「空闲块怎么存」都没想明白，后面那些分配、释放的逻辑根本没法写。

空闲链表（FreeList）的基本思想

最简单的方案，就是用链表把空闲块串起来。每个空闲块的开头放一个节点，节点里记录两个信息：这块内存的起始地址和这块内存的大小。然后把这些节点串成一个单向链表。

为什么用链表？因为显存分配和释放是动态的，频繁地创建和销毁块。链表天然支持 O(1) 的插入和删除，非常适合这种场景。数组的话，你想想看，中间插入一个元素要移动后面所有数据，那性能就炸了。

我在项目中遇到过一个问题：有人把节点数据单独用 malloc 分配在系统内存里。结果显存池本身管理的是 GPU 显存，节点却放在 CPU 内存里，每次分配释放都要跨 PCIe 总线去读写节点信息。那性能，惨不忍睹。所以记住：管理数据要跟被管理的数据放在同一个存储介质里。

块的数据结构定义

好，我们直接看代码。一个空闲链表节点长什么样？

// 空闲链表节点
struct FreeBlock {
    size_t size;        // 当前空闲块的大小（字节数）
    size_t offset;      // 当前空闲块在显存池中的偏移量
    FreeBlock* next;    // 指向下一个空闲块节点
};

嗯，这里要注意：offset 是相对于显存池基地址的偏移量，不是绝对地址。为什么用偏移量？因为显存池的基地址可能在运行时才能确定，用偏移量更灵活，也方便做地址重定位。

那分配出去的内存块呢？我们也需要一个头部信息，记录这块内存的大小和所有者信息。这样在释放时才能正确归还给空闲链表。

// 已分配块头部（位于每个分配块的最前面）
struct AllocHeader {
    size_t size;        // 用户数据区的大小
    uint32_t magic;     // 魔数，用于校验（防止野指针释放）
    AllocHeader* next;  // 指向下一个已分配块（用于遍历）
};

空闲链表的初始化

显存池刚创建时，整块显存都是空闲的。所以空闲链表里只有一个节点，它代表整块显存。

void free_list_init(FreeBlock* head, size_t pool_size) {
    head->size   = pool_size - sizeof(FreeBlock);
    head->offset = sizeof(FreeBlock);  // 第一个节点占用了开头
    head->next   = nullptr;
}

注意看，offset 从 sizeof(FreeBlock) 开始。为什么？因为节点本身要占空间，这个节点就放在显存池的最开头。所以真正可用的空闲空间，要从节点后面开始算。

我曾经犯过一个错误：初始化时把 offset 设成了 0，结果分配出去的内存跟节点数据重叠了。调试了整整一个下午才找到原因。嗯，从那以后我每次初始化都会多看一眼偏移量的计算。

分配时的块分裂

当用户请求一块大小为 N 的显存时，我们需要在空闲链表里找到一块足够大的空闲块。如果找到的块比 N 大，就要把它分裂成两块：一块大小为 N 分配给用户，剩下的部分作为新的空闲块留在链表中。

这个过程用图来表示更清楚：

代码实现大致是这样的：

FreeBlock* split_block(FreeBlock* block, size_t request_size) {
    // 计算分裂后剩余块的大小
    size_t remaining = block->size - request_size - sizeof(AllocHeader);
    
    if (remaining < sizeof(FreeBlock)) {
        // 剩余空间太小，不够放一个空闲节点，干脆整块分配出去
        return nullptr;  // 表示不分裂
    }
    
    // 创建新的空闲块，放在已分配块的后面
    FreeBlock* new_block = (FreeBlock*)((char*)pool_base + block->offset 
                                        + sizeof(AllocHeader) + request_size);
    new_block->size   = remaining;
    new_block->offset = block->offset + sizeof(AllocHeader) + request_size;
    new_block->next   = block->next;
    
    // 更新当前块为已分配块
    block->size = request_size;
    block->next = (FreeBlock*)new_block;  // 这里复用 next 指针指向剩余块
    
    return new_block;
}

释放时的块合并

释放操作比分配更麻烦。因为释放后，我们要把这块内存重新插入到空闲链表中。而且，如果它跟相邻的空闲块是连续的，还要合并成一块更大的空闲块——这叫「合并（coalescing）」。

为什么要合并？你想想看，如果不合并，频繁分配释放会产生大量小碎片。比如你分配了 A、B、C 三块，释放了 B 和 A，但 A 和 B 中间隔着一个 C，它们没法合并。等 C 也释放了，A、B、C 才能合并成一块大的。如果不做合并，这三块就会一直以三个小碎片的形式存在，后续大块分配就失败了。

合并的逻辑其实不复杂：

void free_and_merge(FreeBlock* freelist, AllocHeader* alloc) {
    // 1. 把已分配块转换成空闲块
    FreeBlock* freed = (FreeBlock*)alloc;
    freed->size   = alloc->size;
    freed->offset = /* 计算偏移量 */;
    
    // 2. 在空闲链表中找到合适的位置插入（按地址排序）
    FreeBlock* prev = nullptr;
    FreeBlock* curr = freelist;
    while (curr && curr->offset < freed->offset) {
        prev = curr;
        curr = curr->next;
    }
    
    // 3. 检查是否能与前一个块合并
    if (prev && prev->offset + prev->size == freed->offset) {
        prev->size += freed->size;
        freed = prev;  // 合并后的块以 prev 为准
    } else {
        // 不能合并，直接插入
        freed->next = curr;
        if (prev) prev->next = freed;
    }
    
    // 4. 检查是否能与后一个块合并
    if (curr && freed->offset + freed->size == curr->offset) {
        freed->size += curr->size;
        freed->next = curr->next;
    }
}

这段代码有个关键点：按地址排序插入。为什么？因为只有按地址排序，才能快速判断相邻块是否可以合并。如果不排序，每次释放都要遍历整个链表去检查相邻关系，那时间复杂度就变成 O(n²) 了。

空闲链表的遍历策略

分配时怎么选块？常见的有三种策略：

策略	描述	优点	缺点
First Fit	从头遍历，找到第一个足够大的块	速度快，简单	容易产生碎片
Best Fit	遍历所有块，找到最接近请求大小的块	碎片最少	速度慢，O(n) 遍历
Next Fit	从上一次分配的位置继续找	避免头部碎片堆积	实现稍复杂

我个人习惯在 GPU 显存池中用 First Fit。为什么？因为 GPU 显存分配通常是大块为主，First Fit 的碎片问题没那么严重。而且 GPU 程序对延迟敏感，Best Fit 的遍历开销有时候得不偿失。

不过，如果你的场景是频繁分配释放小块（比如每个线程分配几百字节），那 Best Fit 可能更合适。我在做某个深度学习框架的内存优化时，就遇到过这种情况——First Fit 导致碎片率高达 30%，换成 Best Fit 后降到了 5% 以下。

本章小结

核心数据结构就这么简单：一个空闲链表，每个节点记录偏移量和大小。分配时做块分裂，释放时做块合并。再配合合适的遍历策略，就能实现一个可用的显存池了。

当然，这只是最基础的版本。实际工程中还要考虑线程安全、对齐要求、大块内存的专门处理等等。但数据结构是根基，根基稳了，后面加功能就是锦上添花的事。

下一章我们会在这些数据结构的基础上，真正写出分配器和释放器的代码。到时候你会发现，只要数据结构设计得好，代码写起来就像填空一样简单。

想要更多资料，联系可可