什么是 ‘Allocators’ 的分层设计？解析从 `arena` 到 `slab` 再到 `buddy` 的三层内存分配链

各位编程爱好者，大家好！

今天，我们将深入探讨内存管理领域中一个至关重要的概念：分层设计的内存分配器。在现代软件系统中，高效的内存管理是性能和稳定性的基石。然而，单一的、通用目的的内存分配器往往难以满足所有场景的需求。为了克服这一挑战，工程师们发展出了一套精妙的分层策略，将不同特点的分配器组合起来，形成一个高效、灵活的内存分配链。我们将聚焦于这条链上的三个核心组件：arena 分配器、slab 分配器，以及 buddy 分配器。它们各自在不同的抽象层级和应用场景下发挥作用，共同构筑起一套强大的内存管理体系。

内存分配的挑战与分层设计的必要性

在深入了解具体分配器之前，我们首先要理解为什么我们需要如此复杂的内存管理机制。通用内存分配器（例如 C 语言中的 malloc 和 free）虽然功能强大且灵活，但在许多高性能或资源受限的场景下，它们会暴露出一些固有的缺点：

1. 性能开销：每次 malloc 和 free 调用通常涉及查找空闲块、合并、分裂等操作，这些操作可能需要遍历数据结构或进行系统调用，带来显著的 CPU 和内存开销。
2. 内存碎片：
   • 内部碎片：分配的内存块大于实际请求的大小，导致未被利用的空间。例如，请求 17 字节，但分配器可能以 16 字节或 32 字节为单位进行分配。
   • 外部碎片：虽然总的空闲内存足够，但空闲块分散在内存的各个地方，无法找到一个足够大的连续块来满足新的请求。这在长时间运行的系统中尤为常见。
3. 缓存局部性：频繁分配和释放内存可能导致相关数据被分散到内存的不同区域，从而破坏 CPU 缓存的局部性，降低程序性能。
4. 同步开销：在多线程环境中，malloc 和 free 通常需要锁来保护内部数据结构，这在并发请求量大时会成为性能瓶颈。
5. 生命周期管理：某些对象具有相似的生命周期，例如在一次请求处理过程中创建的所有临时对象。如果逐个释放它们，效率低下且容易出错。

面对这些挑战，单一的“一刀切”式分配器显得力不从心。不同的应用程序和数据结构对内存的需求模式截然不同：有些需要频繁创建和销毁小对象，有些需要偶尔分配大块内存，还有些则需要管理具有相同生命周期的对象集合。为了更高效地满足这些多样化的需求，分层设计的内存分配器应运而生。

分层设计将内存管理任务分解为多个层次，每一层专注于解决特定类型的内存分配问题，并向上层提供更高级别的抽象，向下层请求更底层的内存块。这种模块化的方法带来了诸多优势：

• 专业化优化：每一层都可以针对其特定的分配模式进行高度优化。
• 降低复杂性：将复杂的内存管理问题分解为更小的、可管理的子问题。
• 提高性能：通过减少锁竞争、改善缓存局部性、避免不必要的系统调用等方式。
• 减少碎片：通过不同的策略来缓解内部和外部碎片问题。
• 灵活组合：根据应用程序的需求，可以灵活选择和组合不同层次的分配器。

接下来，我们将从顶层到底层，逐一解析 arena、slab 和 buddy 这三种经典的内存分配器，并阐述它们如何协同工作，形成一个强大的内存分配链。

第一层：Arena Allocator（内存池/竞技场分配器）

概念与设计哲学

Arena Allocator，也被称为内存池分配器，是内存分配链中的最顶层。它的核心思想是：一次性从底层分配器（如 malloc 或 slab）获取一大块连续的内存区域（即“竞技场”或“内存池”），然后应用程序的所有小额分配都在这个竞技场内部进行，通过简单地移动一个指针（“指针碰撞”）来完成。当竞技场中的所有对象都不再需要时，可以一次性释放整个竞技场，而不是逐个释放其中的对象。

Arena Allocator 的设计哲学是针对那些具有相同生命周期、或者在某个特定操作周期内创建和销毁的大量小对象。例如，在处理一个网络请求时，可能会创建多个临时对象（请求解析数据、会话信息、响应体等），这些对象在请求处理完毕后都可以被销毁。如果为每个对象都调用 malloc 和 free，效率会非常低下，并可能导致严重的内存碎片。使用 Arena Allocator，所有这些对象都在一个竞技场内分配，当请求处理结束，直接释放整个竞技场，效率极高。

主要特点与适用场景

• 极速分配：只需简单地递增一个指针（指针碰撞），没有复杂的查找、合并、分裂逻辑，通常比 malloc 快一个数量级。
• 极速释放：无需逐个释放对象，一次性释放整个竞技场，与分配一样高效。
• 消除外部碎片：在竞技场内部，内存是连续分配的，不会产生外部碎片。虽然多个竞技场之间可能存在外部碎片，但这可以通过管理竞技场自身来缓解。
• 改善缓存局部性：相关对象往往在竞技场内连续存放，有助于提高 CPU 缓存的命中率。
• 简化生命周期管理：适用于“all-or-nothing”的释放模式，当一组对象生命周期一致时，管理起来非常方便。
• 缺点：
  • 难以单独释放对象：竞技场的设计不方便单独释放其中的某个对象。如果需要单独释放，要么将该对象标记为“空闲”并在后续分配中重用（增加了复杂性），要么等待整个竞技场被释放。
  • 可能导致内部碎片：如果竞技场被分配了很大一块，但只使用了其中一小部分，那么剩余的内存就浪费了，直到整个竞技场被释放。
  • 不适用于长生命周期对象：如果竞技场中的某个对象生命周期很长，那么它会“钉死”整个竞技场，导致大量内存无法被释放。

适用场景：

• 编译器或解释器：用于构建抽象语法树 (AST)、符号表等临时数据结构。
• Web 服务器或RPC框架：处理单个请求时创建的所有临时对象。
• 游戏引擎：在帧渲染、场景加载等过程中创建的临时对象。
• 解析器：如 JSON/XML 解析器，用于存储解析结果。
• 图形渲染：生成几何数据、纹理等。

实现原理与代码示例

Arena Allocator 的实现相对简单。它需要一个指向当前可用内存起始位置的指针，以及一个跟踪剩余可用内存大小的变量。

#include <cstddef> // For size_t
#include <stdexcept> // For std::bad_alloc
#include <iostream>
#include <vector> // For example usage

// Arena Allocator 定义
class ArenaAllocator {
public:
    // 构造函数：预分配一个指定大小的内存块
    ArenaAllocator(size_t initialSize) :
        _capacity(initialSize),
        _current(0)
    {
        // 从操作系统或其他底层分配器获取一大块内存
        // 这里使用 new char[] 模拟，实际中可能是 mmap 或从 buddy/slab 获取
        _buffer = new char[_capacity];
        if (!_buffer) {
            throw std::bad_alloc();
        }
        std::cout << "ArenaAllocator created with " << _capacity << " bytes." << std::endl;
    }

    // 析构函数：释放整个内存块
    ~ArenaAllocator() {
        delete[] _buffer;
        std::cout << "ArenaAllocator destroyed." << std::endl;
    }

    // 分配指定大小的内存
    void* allocate(size_t size, size_t alignment = alignof(std::max_align_t)) {
        // 确保分配的内存地址对齐
        size_t alignedCurrent = alignUp(_current, alignment);

        if (alignedCurrent + size > _capacity) {
            // 内存不足，可以抛出异常，或尝试从底层分配器获取新的竞技场
            std::cerr << "ArenaAllocator: Out of memory for allocation of " << size << " bytes." << std::endl;
            throw std::bad_alloc();
        }

        void* ptr = static_cast<void*>(_buffer + alignedCurrent);
        _current = alignedCurrent + size; // 移动指针

        std::cout << "Allocated " << size << " bytes at offset " << alignedCurrent << ". New current offset: " << _current << std::endl;
        return ptr;
    }

    // Arena Allocator 通常不提供单独的 free 方法
    // 因为它是为批量释放设计的。
    void deallocate(void* ptr, size_t size) {
        // do nothing, objects are freed when the arena is destroyed
        // Or, for debugging/tracking, one might assert ptr is within arena
        std::cout << "ArenaAllocator: deallocate called, but typically does nothing." << std::endl;
    }

    // 重置竞技场，使其可以重新使用（但不释放内存）
    void reset() {
        _current = 0;
        std::cout << "ArenaAllocator reset. All previous allocations are now invalid." << std::endl;
    }

    // 获取当前已用内存大小
    size_t getAllocatedSize() const {
        return _current;
    }

    // 获取竞技场总容量
    size_t getCapacity() const {
        return _capacity;
    }

private:
    char* _buffer;       // 内存块的起始地址
    size_t _capacity;    // 内存块的总容量
    size_t _current;     // 当前已分配内存的偏移量

    // 辅助函数：向上对齐地址
    size_t alignUp(size_t address, size_t alignment) {
        return (address + alignment - 1) & ~(alignment - 1);
    }

    // 禁用拷贝构造和赋值操作符，避免浅拷贝问题
    ArenaAllocator(const ArenaAllocator&) = delete;
    ArenaAllocator& operator=(const ArenaAllocator&) = delete;
};

// 示例类，用于在竞技场中分配
struct MyObject {
    int id;
    double value;
    char name[16];

    MyObject(int i, double v, const char* n) : id(i), value(v) {
        strncpy(name, n, sizeof(name) - 1);
        name[sizeof(name) - 1] = '';
        std::cout << "  MyObject(" << id << ", " << value << ", " << name << ") constructed." << std::endl;
    }
    ~MyObject() {
        std::cout << "  MyObject(" << id << ") destructed." << std::endl;
    }

    // 重载 new 和 delete 运算符，使其使用 ArenaAllocator
    // 这通常在更复杂的框架中实现，这里只是演示概念
    // 对于真正的竞技场，通常直接通过竞技场接口分配原始内存，然后 placement new
    void* operator new(size_t size, ArenaAllocator& arena) {
        return arena.allocate(size, alignof(MyObject));
    }
    void operator delete(void* ptr, ArenaAllocator& arena) {
        arena.deallocate(ptr, sizeof(MyObject));
    }
    // 还需要一个常规的 operator delete 来处理异常情况
    void operator delete(void* ptr, size_t size) {
        // Fallback for global delete if placement new throws
        ::operator delete(ptr);
    }
};

void runArenaExample() {
    std::cout << "n--- Arena Allocator Example ---" << std::endl;
    try {
        ArenaAllocator myArena(1024); // 创建一个 1KB 的竞技场

        // 在竞技场中分配 MyObject
        MyObject* obj1 = new (myArena) MyObject(1, 10.5, "First");
        MyObject* obj2 = new (myArena) MyObject(2, 20.3, "Second");

        // 分配一个原始 char 数组
        char* buffer = static_cast<char*>(myArena.allocate(32));
        strncpy(buffer, "Hello Arena!", 31);
        buffer[31] = '';
        std::cout << "Raw buffer content: " << buffer << std::endl;

        // 再次分配 MyObject，演示连续性
        MyObject* obj3 = new (myArena) MyObject(3, 30.7, "Third");

        std::cout << "Current allocated size: " << myArena.getAllocatedSize() << " bytes." << std::endl;

        // 如果尝试分配超出容量的内存
        // myArena.allocate(1000); // 这会抛出 std::bad_alloc

        // 在Arena Allocator中，通常不会单独 delete 对象
        // 而是当整个任务完成后，Arena本身被销毁
        // 或者调用 reset() 清空 arena 以便重用
        // delete (myArena) obj1; // 这种语法不常见，且通常不建议在arena中使用

        std::cout << "nResetting Arena..." << std::endl;
        myArena.reset(); // 重置竞技场，所有之前的分配都失效

        // 再次分配，会从头开始
        MyObject* obj4 = new (myArena) MyObject(4, 40.0, "Fourth");
        std::cout << "Current allocated size after reset: " << myArena.getAllocatedSize() << " bytes." << std::endl;

    } catch (const std::bad_alloc& e) {
        std::cerr << "Allocation error: " << e.what() << std::endl;
    }
    std::cout << "--- Arena Allocator Example End ---" << std::endl;
}

在上述代码中，ArenaAllocator 从 new char[] 获取大块内存。在实际的分层设计中，这块大内存可能来自 slab 分配器，或者直接来自 buddy 分配器。当 ArenaAllocator 对象超出作用域时，它的析构函数会释放整个预分配的内存块，从而一次性释放所有在其中分配的对象，无需逐个调用析构函数或 free。当然，对于 C++ 对象，如果需要调用析构函数，则需要在 ArenaAllocator 销毁前手动遍历并调用 obj->~MyObject()。

第二层：Slab Allocator（Slab 分配器）

概念与设计哲学

Slab Allocator，Slab 分配器，是内存分配链中的中间层，它专门用于高效地管理固定大小的对象。其核心思想是：将内存划分为不同大小的“缓存”（caches），每个缓存专门管理一种固定大小的对象。当需要分配某个类型的对象时，从对应的缓存中获取一个预先初始化好的“块”（slab），然后从 slab 中分配一个“槽位”（chunk）给用户。当对象释放时，它被返回到其所属的 slab，并最终返回到缓存的空闲列表。

Slab Allocator 最初由 Jeff Bonwick 为 SunOS 内核开发，旨在解决内核对象（如进程描述符、文件句柄、inode 等）频繁创建和销毁带来的性能和碎片问题。它通过将对象按类型（大小）分组，并预先分配和初始化内存，显著提高了效率。

主要特点与适用场景

• 消除内部碎片：由于每个缓存都管理固定大小的对象，分配的内存块与请求的对象大小完全匹配（或非常接近，考虑到对齐），从而极大地减少了内部碎片。
• 减少外部碎片：通过将相同大小的对象集中管理，Slab Allocator 减少了不同大小内存块混合导致的外部碎片。
• 提高分配/释放速度：一旦 slab 被分配，对象的分配和释放只需要在 slab 内部的空闲列表中操作，避免了底层复杂的数据结构查找。
• 改善缓存局部性：相同类型的对象（通常也是相同大小的）被分配在相邻的内存区域，这有助于提高 CPU 缓存的命中率。
• 对象初始化优化：可以预先对 slab 中的内存块进行初始化，例如清零，避免每次分配时都重复初始化，提高效率。
• 缺点：
  • 仅适用于固定大小对象：这是其最主要的限制。对于变长对象，Slab Allocator 无法直接使用。
  • 不同类型的内部碎片：如果应用程序需要多种不同大小的固定对象，但这些大小又不是标准缓存尺寸，那么可能需要创建多个略微不同但最终浪费空间的小缓存。

适用场景：

• 操作系统内核：管理各种内核数据结构，如 task_struct (进程描述符), inode (文件节点), dentry (目录项), file (文件结构) 等。Linux 内核的 kmem_cache 就是典型的 Slab Allocator。
• 数据库系统：管理固定大小的记录、索引节点、缓存页等。
• 网络服务器：管理连接对象、请求/响应缓冲区等。
• 对象池：任何需要频繁创建和销毁固定大小对象的场景，如线程池中的线程对象，内存池中的固定大小节点。
• 作为 Arena Allocator 的底层：Arena Allocator 可以从 Slab Allocator 获取大块内存。例如，如果一个竞技场需要 4KB 的内存，它可以从一个专门管理 4KB 块的 Slab 缓存中获取。

实现原理与代码示例

一个 Slab Allocator 通常包含以下组件：

1. kmem_cache (或 ObjectCache)：代表一种特定大小对象的缓存。
2. slab：一个或多个连续的内存页，被划分为固定大小的“槽位”。
3. 空闲列表 (Free List)：每个 slab 内部维护一个链表，指向所有空闲的槽位。

当请求分配一个对象时：

1. 查找对应大小的 kmem_cache。
2. 如果 kmem_cache 有可用的 slab（即 slab 中有空闲槽位），则从空闲列表中取出一个槽位。
3. 如果所有 slab 都已满，则从底层分配器（如 buddy 分配器）获取一个新的内存页，将其划分为槽位，并添加到 kmem_cache 的 slab 列表和空闲列表中。

当请求释放一个对象时：

1. 将对象返回到其所属 slab 的空闲列表。
2. 如果一个 slab 中的所有槽位都变为空闲，该 slab 可能会被返还给底层分配器（以减少外部碎片），但通常会保留一段时间以备后续使用。

下面是一个简化的 Slab Allocator 示例，它不包含复杂的缓存管理和内存页获取逻辑，但展示了核心的 Slab 和 Free List 概念。

#include <cstddef>
#include <vector>
#include <list>
#include <iostream>
#include <stdexcept>

// Slab Allocator 定义
// 简化版：仅管理一种固定大小的对象，且 slab 本身从堆分配
// 实际的 Slab Allocator 会有多个 cache 来管理不同大小的对象，
// 并且 slab 会从 buddy allocator 等底层获取大块内存。
class SimpleSlabAllocator {
public:
    // Slab 结构：一个连续的内存块，内部维护空闲列表
    struct Slab {
        char* memory;           // Slab 的起始内存地址
        size_t objectSize;      // 每个对象的大小
        size_t objectCount;     // Slab 中可容纳的对象总数
        std::list<void*> freeList; // 空闲对象指针列表

        Slab(size_t objSize, size_t numObjects) :
            objectSize(objSize), objectCount(numObjects) {

            // Slab 的总大小 = 对象大小 * 对象数量
            // 实际中可能还需要考虑对齐和 Slab 管理信息
            size_t slabTotalSize = objectSize * objectCount;
            memory = new char[slabTotalSize];
            if (!memory) {
                throw std::bad_alloc();
            }

            // 初始化 freeList
            for (size_t i = 0; i < objectCount; ++i) {
                freeList.push_back(memory + i * objectSize);
            }
            std::cout << "  Slab created: " << slabTotalSize << " bytes, "
                      << objectCount << " objects of size " << objectSize << "." << std::endl;
        }

        ~Slab() {
            delete[] memory;
            std::cout << "  Slab destroyed." << std::endl;
        }

        bool hasFreeObjects() const {
            return !freeList.empty();
        }

        void* allocate() {
            if (freeList.empty()) {
                return nullptr; // 没有空闲对象
            }
            void* ptr = freeList.front();
            freeList.pop_front();
            return ptr;
        }

        void deallocate(void* ptr) {
            // 简单检查 ptr 是否在当前 slab 的范围内
            if (static_cast<char*>(ptr) >= memory &&
                static_cast<char*>(ptr) < memory + objectSize * objectCount) {
                freeList.push_back(ptr);
            } else {
                std::cerr << "Warning: Deallocating pointer not belonging to this slab." << std::endl;
            }
        }

        bool isFullyFree() const {
            return freeList.size() == objectCount;
        }
    };

    // 构造函数：指定要管理的单个对象大小，以及每个 slab 容纳的对象数量
    SimpleSlabAllocator(size_t objSize, size_t objectsPerSlab = 16) :
        _objectSize(objSize), _objectsPerSlab(objectsPerSlab) {
        std::cout << "SimpleSlabAllocator created for objects of size " << _objectSize
                  << ", with " << _objectsPerSlab << " objects per slab." << std::endl;
        // 初始时可能不创建 slab，等到第一次分配时再创建
    }

    ~SimpleSlabAllocator() {
        for (Slab* slab : _slabs) {
            delete slab;
        }
        std::cout << "SimpleSlabAllocator destroyed." << std::endl;
    }

    void* allocate() {
        // 尝试从现有 slab 分配
        for (Slab* slab : _slabs) {
            if (slab->hasFreeObjects()) {
                std::cout << "Allocating from existing slab." << std::endl;
                return slab->allocate();
            }
        }

        // 所有 slab 都已满，创建新的 slab
        std::cout << "All slabs full, creating new slab." << std::endl;
        Slab* newSlab = new Slab(_objectSize, _objectsPerSlab);
        _slabs.push_back(newSlab);
        return newSlab->allocate();
    }

    void deallocate(void* ptr) {
        if (!ptr) return;

        // 查找 ptr 属于哪个 slab
        for (Slab* slab : _slabs) {
            // 粗略判断 ptr 是否在 slab 的内存范围内
            // 实际中可能需要更精确的查找机制，例如维护一个 ptr 到 slab 的映射
            if (static_cast<char*>(ptr) >= slab->memory &&
                static_cast<char*>(ptr) < slab->memory + slab->objectSize * slab->objectCount) {
                slab->deallocate(ptr);
                std::cout << "Deallocated object. Slab has " << slab->freeList.size() << " free objects." << std::endl;
                // 如果 slab 完全空闲，可以考虑将其回收
                // 暂时不实现回收逻辑，简化示例
                return;
            }
        }
        std::cerr << "Error: Attempted to deallocate unknown pointer." << std::endl;
        // 如果 ptr 不属于任何 slab，可能需要调用底层 free 或报错
    }

private:
    size_t _objectSize;
    size_t _objectsPerSlab;
    std::vector<Slab*> _slabs; // 管理所有 slab 的列表

    SimpleSlabAllocator(const SimpleSlabAllocator&) = delete;
    SimpleSlabAllocator& operator=(const SimpleSlabAllocator&) = delete;
};

// 示例类，用于在 Slab Allocator 中分配
struct MySlabObject {
    int data1;
    char data2[24]; // 确保总大小固定

    MySlabObject(int d1, const char* d2) : data1(d1) {
        strncpy(data2, d2, sizeof(data2) - 1);
        data2[sizeof(data2) - 1] = '';
        std::cout << "    MySlabObject(" << data1 << ", " << data2 << ") constructed." << std::endl;
    }
    ~MySlabObject() {
        std::cout << "    MySlabObject(" << data1 << ") destructed." << std::endl;
    }
};

void runSlabExample() {
    std::cout << "n--- Slab Allocator Example ---" << std::endl;
    // 分配器管理 MySlabObject，每个 slab 容纳 4 个 MySlabObject
    SimpleSlabAllocator slabAllocator(sizeof(MySlabObject), 4);

    std::vector<MySlabObject*> objects;
    for (int i = 0; i < 6; ++i) { // 分配 6 个对象，将创建 2 个 slab
        void* mem = slabAllocator.allocate();
        MySlabObject* obj = new (mem) MySlabObject(i + 100, ("SlabObj" + std::to_string(i)).c_str());
        objects.push_back(obj);
    }

    std::cout << "nDeallocating some objects..." << std::endl;
    slabAllocator.deallocate(objects[1]); // 释放第二个对象
    objects[1] = nullptr;
    slabAllocator.deallocate(objects[3]); // 释放第四个对象
    objects[3] = nullptr;
    slabAllocator.deallocate(objects[5]); // 释放第六个对象
    objects[5] = nullptr;

    std::cout << "nAllocating more objects..." << std::endl;
    // 再次分配，会重用之前释放的槽位
    void* mem1 = slabAllocator.allocate();
    MySlabObject* obj7 = new (mem1) MySlabObject(107, "NewSlabObj7");
    objects.push_back(obj7);

    void* mem2 = slabAllocator.allocate();
    MySlabObject* obj8 = new (mem2) MySlabObject(108, "NewSlabObj8");
    objects.push_back(obj8);

    std::cout << "nCalling destructors for all objects..." << std::endl;
    for (MySlabObject* obj : objects) {
        if (obj) {
            obj->~MySlabObject(); // 手动调用析构函数
        }
    }

    // Slab Allocator 析构时会释放所有 slab
    std::cout << "--- Slab Allocator Example End ---" << std::endl;
}

在 SimpleSlabAllocator 中，每个 Slab 都是通过 new char[] 从系统堆中获取的。在真实的内核或高性能用户空间分配器中，Slab 的内存通常是从底层 buddy 分配器以页为单位获取的。

第三层：Buddy Allocator（伙伴分配器）

概念与设计哲学

Buddy Allocator，伙伴分配器，是内存分配链中的最底层（通常直接与操作系统或物理内存交互）。它的核心思想是：将一大块连续的内存区域（通常是物理内存页）以 2 的幂次方大小进行管理。当需要分配内存时，它会从可用的最大块开始，将其递归地分裂成两个大小相等的“伙伴”块，直到找到一个足够小的块来满足请求。当内存被释放时，它会检查其伙伴块是否也空闲。如果两个伙伴块都空闲，它们就会被合并成一个更大的块，从而减少外部碎片。

Buddy Allocator 的设计目标是高效地管理可变大小的内存请求，同时尽可能地减少外部碎片。它通过强制内存块大小为 2 的幂次方来简化合并和分裂逻辑，使得查找伙伴和合并操作非常高效。

主要特点与适用场景

• 减少外部碎片：通过合并相邻的空闲伙伴块，Buddy Allocator 能够将小的空闲块重新聚合成大的连续空闲块，有效对抗外部碎片。
• 高效的分配和释放：分配和释放操作通常只需要对数时间（O(logN)，其中 N 是总内存大小），因为每次操作都只涉及一个或几个级别的分裂或合并。
• 管理大块内存：非常适合管理操作系统中的物理内存页，或者作为用户空间中管理大块虚拟内存的底层机制。
• 缺点：
  • 内部碎片：这是 Buddy Allocator 最大的缺点。由于内存块大小必须是 2 的幂次方，如果请求的内存大小不是精确的 2 的幂次方，那么分配的块会比请求的大，导致内部碎片。最坏情况下，请求 $2^k + 1$ 字节，会分配 $2^{k+1}$ 字节，内部碎片接近 50%。
  • 实现相对复杂：需要维护不同大小的空闲列表，以及跟踪每个块是否已被分配或其伙伴块的状态。

适用场景：

• 操作系统内核：作为物理内存页的主要分配器。例如，Linux 内核的页分配器就是基于 Buddy System。
• 虚拟内存管理：分配和管理虚拟内存区域。
• 游戏引擎：管理大型资源（如纹理、模型）的内存。
• 作为 Slab 和 Arena Allocator 的底层：为 Slab Allocator 提供构成 slab 的内存页，或为 Arena Allocator 提供大块初始内存。

实现原理与代码示例

Buddy Allocator 通常维护一系列空闲列表，每个列表对应一个特定大小（2 的幂次方）的内存块。

1. 初始化：将整个内存区域作为一个最大的块添加到对应的空闲列表。
2. 分配 (allocate)：
   • 根据请求大小，找到最小的、大于等于请求大小的 2 的幂次方块。
   • 从对应大小的空闲列表中查找。如果找到，则分配并返回。
   • 如果该列表为空，则向上找一个更大的块（例如，如果需要 256 字节，但 256 列表为空，则从 512 列表查找）。
   • 找到更大的块后，将其从其空闲列表中移除，并分裂成两个伙伴块。其中一个伙伴用于满足请求（或继续分裂），另一个伙伴添加到相应大小的空闲列表中。
   • 重复此过程，直到找到一个合适大小的块。
3. 释放 (deallocate)：
   • 将释放的块添加到其对应大小的空闲列表。
   • 检查该块的“伙伴”是否也空闲。伙伴块的地址可以通过异或操作快速计算出来。
   • 如果伙伴也空闲，则将两者从空闲列表中移除，合并成一个更大的块，然后将新合并的块添加到其对应大小的空闲列表。
   • 重复此合并过程，直到无法再合并，或者达到最大块大小。

下面是一个简化的 Buddy Allocator 示例，它在预设的内存池上操作，并支持固定范围的 2 的幂次方大小。

#include <cstddef>
#include <vector>
#include <list>
#include <cmath> // For log2
#include <iostream>
#include <algorithm> // For std::min

// Buddy Allocator 定义
// 简化版：在预分配的固定大小内存上操作
class BuddyAllocator {
public:
    // 构造函数：指定总内存大小，以及最小和最大块大小
    // 总内存大小必须是 2 的幂次方
    // minBlockSize 也必须是 2 的幂次方
    BuddyAllocator(size_t totalMemorySize, size_t minBlockSize = 4096) :
        _totalMemorySize(totalMemorySize),
        _minBlockSize(minBlockSize),
        _maxOrder(static_cast<int>(std::log2(totalMemorySize))),
        _minOrder(static_cast<int>(std::log2(minBlockSize)))
    {
        if (totalMemorySize == 0 || (totalMemorySize & (totalMemorySize - 1)) != 0) {
            throw std::invalid_argument("Total memory size must be a power of 2.");
        }
        if (minBlockSize == 0 || (minBlockSize & (minBlockSize - 1)) != 0 || minBlockSize > totalMemorySize) {
            throw std::invalid_argument("Min block size must be a power of 2 and <= total memory size.");
        }

        _memory = new char[_totalMemorySize];
        if (!_memory) {
            throw std::bad_alloc();
        }

        // 初始化空闲列表：一个 vector，每个元素是一个链表，存储对应 order 的空闲块
        // order 'i' 对应大小为 2^i bytes 的块
        _freeLists.resize(_maxOrder + 1);

        // 将整个内存区域作为最大块添加到对应的空闲列表
        _freeLists[_maxOrder].push_back(_memory);

        std::cout << "BuddyAllocator created with " << _totalMemorySize << " bytes. "
                  << "Min block size: " << _minBlockSize << ", Max order: " << _maxOrder << std::endl;
    }

    ~BuddyAllocator() {
        delete[] _memory;
        std::cout << "BuddyAllocator destroyed." << std::endl;
    }

    void* allocate(size_t size) {
        if (size == 0) return nullptr;

        // 找到满足请求的最小 2 的幂次方块大小
        size_t actualSize = _minBlockSize;
        while (actualSize < size) {
            actualSize <<= 1;
        }

        // 确保分配的块大小不超过总内存
        if (actualSize > _totalMemorySize) {
             std::cerr << "BuddyAllocator: Requested size " << size << " (actual " << actualSize << ") too large for total memory " << _totalMemorySize << "." << std::endl;
             return nullptr;
        }

        int order = static_cast<int>(std::log2(actualSize));
        if (order < _minOrder) order = _minOrder; // 确保不分配小于最小块的内存

        std::cout << "  Allocate request for " << size << " bytes, seeking order " << order << " (size " << (1ULL << order) << ")." << std::endl;

        // 尝试从当前 order 向上查找
        for (int currentOrder = order; currentOrder <= _maxOrder; ++currentOrder) {
            if (!_freeLists[currentOrder].empty()) {
                char* block = _freeLists[currentOrder].front();
                _freeLists[currentOrder].pop_front();

                // 如果找到的块比请求的块大，则分裂
                while (currentOrder > order) {
                    currentOrder--;
                    size_t buddySize = (1ULL << currentOrder);
                    char* buddyBlock = block + buddySize;
                    _freeLists[currentOrder].push_back(buddyBlock); // 将伙伴块添加到空闲列表
                    std::cout << "  Split order " << currentOrder + 1 << " block at "
                              << (void*)block << " into two order " << currentOrder << " blocks. Buddy at "
                              << (void*)buddyBlock << " added to free list." << std::endl;
                }
                std::cout << "  Allocated order " << order << " block at " << (void*)block << std::endl;
                return static_cast<void*>(block);
            }
        }
        std::cerr << "BuddyAllocator: Out of memory for allocation of " << size << " bytes." << std::endl;
        return nullptr; // 内存不足
    }

    void deallocate(void* ptr, size_t size) {
        if (!ptr) return;

        // 找到对应的 order
        size_t actualSize = _minBlockSize;
        while (actualSize < size) {
            actualSize <<= 1;
        }
        int order = static_cast<int>(std::log2(actualSize));
        if (order < _minOrder) order = _minOrder;

        char* block = static_cast<char*>(ptr);
        std::cout << "  Deallocating order " << order << " block at " << (void*)block << "." << std::endl;

        // 尝试合并伙伴
        while (order < _maxOrder) {
            char* buddyBlock = getBuddy(block, order);
            bool buddyFound = false;

            // 检查伙伴是否在当前 order 的空闲列表中
            for (auto it = _freeLists[order].begin(); it != _freeLists[order].end(); ++it) {
                if (*it == buddyBlock) {
                    _freeLists[order].erase(it); // 移除伙伴
                    buddyFound = true;
                    break;
                }
            }

            if (buddyFound) {
                // 合并两个伙伴
                block = std::min(block, buddyBlock); // 总是取地址较小的作为合并后的块
                order++;
                std::cout << "  Merged order " << order - 1 << " blocks at " << (void*)buddyBlock << " and "
                          << (void*)block << " into order " << order << " block at " << (void*)block << "." << std::endl;
            } else {
                break; // 伙伴不空闲，停止合并
            }
        }
        _freeLists[order].push_back(block); // 将最终的块添加到空闲列表
        std::cout << "  Final block at " << (void*)block << " (order " << order << ") added to free list." << std::endl;
    }

private:
    char* _memory;
    size_t _totalMemorySize;
    size_t _minBlockSize;
    int _maxOrder; // log2(totalMemorySize)
    int _minOrder; // log2(minBlockSize)

    std::vector<std::list<char*>> _freeLists; // 存储不同 order 的空闲块

    // 计算给定块的伙伴地址
    char* getBuddy(char* block, int order) {
        size_t blockSize = (1ULL << order); // 2^order
        size_t offset = block - _memory; // 块相对于总内存起始的偏移
        // 伙伴的偏移 = 块偏移 ^ 块大小
        size_t buddyOffset = offset ^ blockSize; 
        return _memory + buddyOffset;
    }

    BuddyAllocator(const BuddyAllocator&) = delete;
    BuddyAllocator& operator=(const BuddyAllocator&) = delete;
};

void runBuddyExample() {
    std::cout << "n--- Buddy Allocator Example ---" << std::endl;
    try {
        // 总内存 16KB, 最小块 1KB
        BuddyAllocator buddyAllocator(16 * 1024, 1024); 

        void* p1 = buddyAllocator.allocate(3 * 1024); // 请求 3KB -> 分配 4KB (order 12)
        void* p2 = buddyAllocator.allocate(1 * 1024); // 请求 1KB -> 分配 1KB (order 10)
        void* p3 = buddyAllocator.allocate(5 * 1024); // 请求 5KB -> 分配 8KB (order 13)
        void* p4 = buddyAllocator.allocate(1 * 1024); // 请求 1KB -> 分配 1KB (order 10)

        // 尝试分配更多，应该会失败
        void* p5 = buddyAllocator.allocate(10 * 1024); // 剩余 2KB, 请求 10KB -> 16KB，失败

        std::cout << "nDeallocating blocks..." << std::endl;
        buddyAllocator.deallocate(p1, 3 * 1024); // 释放 p1 (4KB)
        buddyAllocator.deallocate(p2, 1 * 1024); // 释放 p2 (1KB)
        buddyAllocator.deallocate(p3, 5 * 1024); // 释放 p3 (8KB)
        buddyAllocator.deallocate(p4, 1 * 1024); // 释放 p4 (1KB)

        // 再次分配，应该成功
        std::cout << "nAllocating after deallocations..." << std::endl;
        void* p6 = buddyAllocator.allocate(10 * 1024); // 此时应该可以合并出 16KB，然后分配 16KB
        if (p6) {
            std::cout << "Successfully allocated 16KB after merges." << std::endl;
            buddyAllocator.deallocate(p6, 10 * 1024);
        }

    } catch (const std::exception& e) {
        std::cerr << "Buddy Allocator error: " << e.what() << std::endl;
    }
    std::cout << "--- Buddy Allocator Example End ---" << std::endl;
}

在上述 Buddy Allocator 示例中，_memory 数组是预先通过 new char[] 分配的。在操作系统内核中，这块内存将是直接管理的物理内存页。

三层内存分配链的协同工作

现在，我们已经分别了解了 arena、slab 和 buddy 分配器，是时候将它们串联起来，看看它们如何协同工作，形成一个高效的分层内存分配链。

分配器类型	优点	缺点	适用场景	通常从何处获取内存
Arena	极速分配/释放，减少碎片，改善缓存局部性，简化生命周期管理	难以单独释放，可能内部碎片（若用量小），不适合长生命周期对象	临时对象集合，生命周期一致（请求、帧、AST）	Slab/Buddy/malloc
Slab	消除内部碎片（固定大小），减少外部碎片，提高缓存局部性，初始化优化	仅限固定大小对象，需要为每种大小设置缓存	内核对象，对象池，固定大小且频繁创建/销毁对象	Buddy/mmap
Buddy	减少外部碎片（合并），高效处理变长请求，管理大块内存	内部碎片（2的幂次方对齐），实现复杂	物理内存页管理，大块内存分配	OS/物理内存

这条分层链的典型调用路径如下：

1. 应用程序请求内存：

   • 场景一：大量临时小对象，生命周期一致
     应用程序向一个 Arena Allocator 请求内存。Arena 通过简单地移动其内部指针，快速返回一块内存。
   • 场景二：固定大小且频繁创建/销毁的对象
     应用程序（或上层分配器）向一个 Slab Allocator 请求一个特定大小的对象。Slab 从其对应的 kmem_cache 中查找一个空闲槽位并返回。
   • 场景三：较大且变长的内存块
     应用程序直接向底层分配器（如 Buddy Allocator 或 malloc/mmap）请求。

2. Arena 从 Slab 获取内存（或直接从 Buddy/OS）：
   当一个 Arena Allocator 自身的内部缓冲区不足时，它不会直接向 malloc 请求小块内存，而是会向一个专门为竞技场提供大块内存的 Slab Allocator (例如，一个管理 4KB 或 8KB 块的 Slab) 请求一个新的“竞技场”块。如果 Arena 是最顶层且没有 Slab 作为中间层，它可能会直接向 Buddy 或操作系统（通过 mmap/sbrk）请求大块内存。

3. Slab 从 Buddy 获取内存：
   当一个 Slab Allocator 的所有 slab 都已满，需要创建新的 slab 时，它会向 Buddy Allocator 请求一个或多个物理内存页（通常是 4KB 或 8KB 的 2 的幂次方大小）。Buddy Allocator 会根据请求的大小，分裂其管理的内存块，并返回一个连续的内存块给 Slab Allocator。

4. Buddy 与操作系统/物理内存交互：
   Buddy Allocator 作为最底层，在操作系统内核中，它直接管理物理内存页。在用户空间，它会通过系统调用（如 mmap）向操作系统请求大块的虚拟内存，然后在其内部进行管理。

这种分层设计带来的核心优势包括：

• 性能最大化：每一层都针对其特定的分配模式进行了优化。顶层的 Arena 提供极致的速度，中间层的 Slab 针对固定大小对象提供高效管理和缓存局部性，底层的 Buddy 则确保了物理内存的有效利用和碎片化控制。
• 碎片最小化：Arena 内部无碎片，批量释放消除生命周期碎片。Slab 消除固定大小对象的内部碎片，并通过集中管理减少外部碎片。Buddy 通过合并伙伴块来积极对抗外部碎片。
• 缓存友好：Arena 和 Slab 倾向于将相关对象放置在内存的相邻区域，极大地改善了 CPU 缓存的命中率。
• 模块化与可维护性：每一层都是相对独立的模块，职责清晰，易于开发、测试和维护。
• 灵活性：可以根据应用程序的具体需求，选择性地使用或组合这些分配器。例如，某些应用可能不需要 Slab 层，直接让 Arena 从 Buddy 获取内存。

真实世界中的应用与考量

在真实的操作系统内核（如 Linux）中，这种分层设计被广泛实践。Linux 内核的页分配器就是基于 Buddy Allocator，它管理着所有的物理内存页。在其之上，kmem_cache (Slab Allocator 的实现) 从页分配器获取内存页，然后将其划分为固定大小的缓存，供内核中的各种子系统使用。而 Arena 风格的分配器则在内核的特定上下文（如文件系统、网络协议栈等）中用于管理生命周期短暂的临时数据结构。

在用户空间，像 jemalloc、tcmalloc、ptmalloc (glibc 的 malloc 实现) 等高性能内存分配库也采用了类似的分层思想。它们通常会为小对象维护一系列类似 Slab 的固定大小块，以提高分配速度和减少碎片。对于中等大小的请求，它们可能有自己的 bin 管理机制。对于大块内存，它们通常会直接通过 mmap 向操作系统请求，并可能在内部使用类似 Buddy 的策略来管理这些大块内存。用户也可以在这些通用分配器之上，自己实现 Arena 或 Object Pool 来进一步优化特定场景。

选择合适的分配器或组合方案，需要深入理解应用程序的内存访问模式、对象生命周期以及性能要求。

结论与展望

分层内存分配设计，以 arena、slab 和 buddy 为代表，是现代高性能软件系统内存管理的核心策略。它通过将内存管理任务分解到不同层次，并针对不同模式进行优化，有效解决了传统通用分配器在性能、碎片和缓存局部性方面的挑战。理解并掌握这些分配器的原理及其协同工作方式，对于编写高效、稳定、可扩展的系统级代码至关重要。随着硬件架构的演进和编程范式的变化，内存管理技术也在不断发展，但这种分层、专业化的设计思想，仍将是未来内存管理策略演进的基石。