3. 内存池核心数据结构：Block、Node、FreeList 的设计

好，咱们进入正题。

内存池这东西，说白了就是「自己管内存，不让操作系统插手」。你想想看，每次 new 和 delete 都要走系统调用，频繁了性能肯定扛不住。那怎么管？靠三个核心数据结构：内存块（Block）、内存节点（Node）、空闲链表（FreeList）。

我个人习惯把这三者比作「仓库、货架、库存清单」。Block 是整块整块向系统申请的大仓库，Node 是仓库里一个个小货架，FreeList 就是记录哪些货架是空着的清单。嗯，这个比喻你记住，后面好理解。

3.1 内存块（Block）—— 内存池的「地基」

Block 是什么？就是内存池向操作系统一次性申请的一大片连续内存。我见过不少新手一上来就搞一个全局大数组当内存池，其实不太灵活。真正的工程化做法，是用链表把多个 Block 串起来。

为什么需要多个 Block？因为业务是动态的。一开始你预估 64KB 够用，结果高峰期需要 128KB，怎么办？再申请一个 Block 挂上去就行了。我在项目中遇到过这种情况：某个游戏服务器启动时只分配了 4 个 Block，结果开服半小时后玩家涌入，内存池自动扩容到 16 个 Block，全程无感。

Block 的结构长这样：

struct MemoryBlock {
    void*     block_start;    // 块起始地址
    size_t    block_size;     // 块总大小（字节）
    size_t    used_size;      // 已使用大小
    MemoryBlock* next;        // 指向下一个 Block
};

这里有个细节：block_start 指向的是整块内存的头部，但实际可分配区域要从头部偏移一段距离开始。为什么？因为我们要在 Block 头部存一些元数据，比如这个 Block 属于哪个内存池、当前空闲节点数量等。嗯，这里要注意，元数据不要占用太多空间，否则得不偿失。

3.2 内存节点（Node）—— 最小的分配单元

Node 是啥？就是用户真正用到的内存单元。每个 Node 的大小在内存池创建时就固定了。比如你做一个 64 字节的固定大小内存池，那每个 Node 就是 64 字节。

Node 的设计有个坑：内存对齐。我曾经在项目里吃过亏——Node 大小没对齐到 8 字节，结果在 ARM 平台上跑的时候直接段错误。所以 Node 的大小必须是 2 的幂次，而且至少 8 字节（因为要存指针）。

Node 的结构其实很简单：

struct MemoryNode {
    MemoryNode* next;   // 指向下一个空闲节点
    // 用户数据紧随其后
};

你没看错，Node 本身只存一个指针。那用户数据放哪？就在这个指针后面。当 Node 被分配出去时，next 指针被覆盖成用户数据的一部分。当 Node 被归还时，next 指针重新生效，指向下一个空闲节点。

这种设计有个好处：零额外开销。Node 本身不占用额外内存，指针和用户数据共用同一片空间。说白了就是「人歇马不歇」，内存利用率极高。

3.3 空闲链表（FreeList）—— 内存池的「调度中心」

FreeList 就是一条把所有空闲 Node 串起来的链表。分配内存时，从链表头部取一个 Node；释放内存时，把 Node 放回链表头部。这就是所谓的 LIFO（后进先出）策略。

为什么用 LIFO？因为 CPU 缓存友好。刚释放的 Node 大概率还在缓存里，马上分配出去命中率高。我做过测试，LIFO 比 FIFO 在缓存命中率上能高出 15%-20%。

FreeList 的实现：

class FreeList {
private:
    MemoryNode* head_;   // 链表头指针
    size_t      count_;  // 空闲节点数量
public:
    FreeList() : head_(nullptr), count_(0) {}
    
    void push(MemoryNode* node) {
        node->next = head_;
        head_ = node;
        count_++;
    }
    
    MemoryNode* pop() {
        if (!head_) return nullptr;
        MemoryNode* node = head_;
        head_ = head_->next;
        count_--;
        return node;
    }
    
    bool empty() const { return count_ == 0; }
    size_t size() const { return count_; }
};

你看，代码就这么几行。但越简单的东西越容易出错。我曾经犯过一个低级错误：push 的时候忘了把 node->next 置空，结果链表出现了环，分配器死循环了。排查了整整一个下午才找到问题。

3.4 三者如何协同工作？

来，我画个图帮你理清关系：

这张图展示了核心逻辑：

• Block 是物理内存的载体，多个 Block 通过链表串联
• Node 是 Block 内部的最小单元，每个 Node 大小固定
• FreeList 是一个全局链表，把所有空闲 Node 串起来

分配时，直接从 FreeList 头部取一个 Node。如果 FreeList 为空，就从当前 Block 中切出一段新内存，或者申请新的 Block。释放时，把 Node 塞回 FreeList 头部。

你想想看，这套机制是不是很优雅？没有系统调用，没有内存碎片，分配和释放都是 O(1) 时间复杂度。

3.5 设计上的几个关键决策

嗯，数据结构这块就讲到这里。记住，设计内存池时不要追求花哨，把这三个基础结构搞扎实了，后面的一切都水到渠成。