嵌入式现代C++教程——自定义分配器（Allocator）

在嵌入式世界里，内存不是"无限"的抽屉，而是那只随时会嫌你占空间的行李箱。默认的 new / malloc 对我们友好吗？有时候很友好（没错，方便）；但更多时候，它们是潜在的性能炸弹、不可预测的延迟来源、以及碎片化萌生地。于是，写一个"自定义分配器"——你自己的内存管理策略，就变成了工程师的基本修行。

---

为什么要自定义分配器？

想象一下这些场景：实时任务不能被偶发的 malloc 阻塞；启动阶段需要一次性分配若干对象以避免运行时分配；小对象分配频繁但大小恒定；或者你想把一大块内存划分给特定模块，便于追踪与回收。默认分配器往往无法同时满足：确定性、低内存占用、低碎片和高性能。

自定义分配器修改了像内存申请的具体模式，我们可以接入自己的固定大小池、栈式分配、快速分配器。在之前的博客中，我们的这些实现可以有效的避免堆碎片、提高局部性。

---

分配器的基础概念

分配器，归根结底就是两件事：分配（给出一段未被使用的内存）和释放（把内存归回池子）。在 C++ 里还要注意对齐（alignment）和对象的构造/析构（placement new、显式 destroy）。

常见策略有：Bump（指针上移）分配器、Free-list（空闲链表/内存池）、Stack（栈）分配器、以及更复杂的 TLSF/分级位图 等。下面我们通过代码直观对比。

---

最简单：Bump（线性）分配器 — 启动与临时用例的好朋友

特点：实现极其简单，分配 O(1)，不支持释放单个对象（可以一次性重置）。适合启动期分配或者短周期任务。

// bump_allocator.h - 非线程安全，简单演示
#include <cstddef>
#include <new>
#include <cassert>

class BumpAllocator {
    char* start_;
    char* ptr_;
    char* end_;
public:
    BumpAllocator(void* buffer, std::size_t size)
      : start_(static_cast<char*>(buffer)), ptr_(start_), end_(start_ + size) {}

    void* allocate(std::size_t n, std::size_t align = alignof(std::max_align_t)) noexcept {
        std::size_t space = end_ - ptr_;
        std::uintptr_t p = reinterpret_cast<std::uintptr_t>(ptr_);
        std::size_t mis = p % align;
        std::size_t offset = mis ? (align - mis) : 0;
        if (n + offset > space) return nullptr;
        ptr_ += offset;
        void* res = ptr_;
        ptr_ += n;
        return res;
    }

    void reset() noexcept { ptr_ = start_; }
};

使用场景：启动时分配所有必要对象，后面不再释放；或临时缓冲池。记住：不能释放单个对象，除非你支持回滚到某个快照点（可以实现"标记/回滚"）。

---

固定大小内存池（Free-list）

当你有大量相同大小的小对象（例如消息节点、连接对象）时，固定大小内存池非常高效。每个槽（slot）大小固定，释放时把槽 push 回空闲链表。分配/释放都 O(1)。

// simple_pool.h - 单线程示例
#include <cstddef>
#include <cassert>
#include <cstdint>

class SimpleFixedPool {
    struct Node { Node* next; };
    void* buffer_;
    Node* free_head_;
    std::size_t slot_size_;
    std::size_t slot_count_;
public:
    SimpleFixedPool(void* buf, std::size_t slot_size, std::size_t count)
      : buffer_(buf), free_head_(nullptr), slot_size_((slot_size < sizeof(Node*))? sizeof(Node*): slot_size), slot_count_(count) {
        // 初始化空闲链表
        char* p = static_cast<char*>(buffer_);
        for (std::size_t i = 0; i < slot_count_; ++i) {
            Node* n = reinterpret_cast<Node*>(p + i * slot_size_);
            n->next = free_head_;
            free_head_ = n;
        }
    }
    void* allocate() noexcept {
        if (!free_head_) return nullptr;
        Node* n = free_head_;
        free_head_ = n->next;
        return n;
    }
    void deallocate(void* p) noexcept {
        Node* n = static_cast<Node*>(p);
        n->next = free_head_;
        free_head_ = n;
    }
};

要点提示：slot_size 应包含对齐与控制信息；线程安全时需要加锁或使用 lock-free 结构（复杂度上升）。内存利用率高，碎片少。

---

Stack（栈）分配器 — LIFO 场景的神器

当你分配/释放呈 LIFO（后进先出）模式时，栈分配器速度最快，可以释放一系列分配到某个"标记"为止。

// stack_allocator.h - 支持标记回滚
class StackAllocator {
    char* start_;
    char* top_;
    char* end_;
public:
    StackAllocator(void* buf, std::size_t size) : start_(static_cast<char*>(buf)), top_(start_), end_(start_+size) {}
    void* allocate(std::size_t n, std::size_t align = alignof(std::max_align_t)) noexcept {
        // 类似Bump的对齐处理
        // ...
    }
    // 标记与回滚API
    using Marker = char*;
    Marker mark() noexcept { return top_; }
    void rollback(Marker m) noexcept { top_ = m; }
};

适用：短生命周期链、任务栈式分配、帧分配（每帧分配，帧结束统一回收）。

---

用 C++ 风格包装（placement new 与析构）

分配器只提供原始内存；对象的构造/析构工作还是你的任务。示例如下：

#include <new> // placement new

// allocate memory for T and construct
template<typename T, typename Alloc, typename... Args>
T* construct_with(Alloc& a, Args&&... args) {
    void* mem = a.allocate(sizeof(T), alignof(T));
    if (!mem) return nullptr;
    return new (mem) T(std::forward<Args>(args)...);
}

// 销毁并归还内存（手动调用析构）
template<typename T, typename Alloc>
void destroy_with(Alloc& a, T* obj) noexcept {
    if (!obj) return;
    obj->~T();
    a.deallocate(static_cast<void*>(obj));
}

重要：在嵌入式中，禁用异常或在异常敏感代码中使用 noexcept 的 allocate 是常见实践；因此好多实现返回 nullptr 而不是抛异常。

---

如何把自定义分配器和 STL 一起用

标准库的 std::allocator 接口在老标准中较为笨重。C++17/20 引入了 std::pmr::memory_resource（更现代）用于替换默认分配策略。但在嵌入式里往往不启用完整的 <memory_resource>，于是你可以自己：

• 为容器写一个简单的 wrapper，内部使用你的池分配节点。
• 或实现兼容 std::allocator 接口的类（需要一堆 typedef 和 rebind），然后传给 std::vector<T, MyAlloc<T>>。

如果构建环境允许，优先考虑 std::pmr —— 它语义更清晰，但开销与支持度要看你的平台。

查看完整可编译示例

// bump_allocator.h - 非线程安全的线性分配器
#pragma once
#include <cstddef>
#include <new>
#include <cstdint>
#include <cstring>

class BumpAllocator {
    char* start_;
    char* ptr_;
    char* end_;

public:
    BumpAllocator(void* buffer, std::size_t size)
        : start_(static_cast<char*>(buffer))
        , ptr_(start_)
        , end_(start_ + size)
    {}

    void* allocate(std::size_t n, std::size_t align = alignof(std::max_align_t)) noexcept {
        std::size_t space = end_ - ptr_;
        std::uintptr_t p = reinterpret_cast<std::uintptr_t>(ptr_);
        std::size_t mis = p % align;
        std::size_t offset = mis ? (align - mis) : 0;

        if (n + offset > space) return nullptr;

        ptr_ += offset;
        void* res = ptr_;
        ptr_ += n;
        return res;
    }

    // 不支持单个释放，只能重置
    void deallocate(void* p) noexcept {
        // Bump allocator 不支持单个释放
        (void)p;
    }

    void reset() noexcept { ptr_ = start_; }

    std::size_t used() const noexcept { return ptr_ - start_; }
    std::size_t available() const noexcept { return end_ - ptr_; }
    std::size_t capacity() const noexcept { return end_ - start_; }
};

// bump_allocator_demo.cpp - 线性分配器演示
#include "bump_allocator.h"
#include <iostream>
#include <iomanip>

// 用于测试的结构
struct TestData {
    int id;
    double value;
    char name[16];

    TestData(int i, double v, const char* n) : id(i), value(v) {
        std::strncpy(name, n, sizeof(name) - 1);
        name[sizeof(name) - 1] = '\0';
    }

    void display() const {
        std::cout << "  Data[" << id << "]: " << name
                  << " = " << value << '\n';
    }
};

int main() {
    std::cout << "=== Bump Allocator Demo ===\n\n";

    // 创建缓冲区
    constexpr std::size_t BUFFER_SIZE = 1024;
    static char buffer[BUFFER_SIZE];

    BumpAllocator allocator(buffer, BUFFER_SIZE);

    std::cout << "Initial state:\n";
    std::cout << "  Capacity: " << allocator.capacity() << " bytes\n";
    std::cout << "  Used: " << allocator.used() << " bytes\n";
    std::cout << "  Available: " << allocator.available() << " bytes\n\n";

    // 分配一些对象
    std::cout << "=== Allocating objects ===\n";
    TestData* d1 = static_cast<TestData*>(allocator.allocate(sizeof(TestData)));
    if (d1) {
        new (d1) TestData(1, 3.14, "Pi");
        d1->display();
    }

    TestData* d2 = static_cast<TestData*>(allocator.allocate(sizeof(TestData)));
    if (d2) {
        new (d2) TestData(2, 2.71, "Euler");
        d2->display();
    }

    // 分配一个大块
    std::cout << "\nAllocating large block...\n";
    void* large_block = allocator.allocate(512);
    if (large_block) {
        std::cout << "  Allocated 512 bytes at " << large_block << '\n';
    }

    std::cout << "\nState after allocations:\n";
    std::cout << "  Used: " << allocator.used() << " bytes\n";
    std::cout << "  Available: " << allocator.available() << " bytes\n\n";

    // 尝试分配超过剩余空间的大小
    std::cout << "=== Attempting over-allocation ===\n";
    void* fail = allocator.allocate(allocator.available() + 100);
    if (!fail) {
        std::cout << "  Correctly failed to allocate (buffer exhausted)\n";
    }

    // 重置并重新使用
    std::cout << "\n=== Resetting allocator ===\n";
    allocator.reset();

    std::cout << "After reset:\n";
    std::cout << "  Used: " << allocator.used() << " bytes\n";
    std::cout << "  Available: " << allocator.available() << " bytes\n\n";

    // 可以重新分配
    std::cout << "=== Allocating after reset ===\n";
    TestData* d3 = static_cast<TestData*>(allocator.allocate(sizeof(TestData)));
    if (d3) {
        new (d3) TestData(3, 1.41, "Sqrt(2)");
        d3->display();
    }

    std::cout << "\n=== Key characteristics ===\n";
    std::cout << "- O(1) allocation\n";
    std::cout << "- No individual deallocation\n";
    std::cout << "- Reset clears all at once\n";
    std::cout << "- Perfect for startup/phase allocation\n";
    std::cout << "- Zero fragmentation\n";

    return 0;
}

查看更多示例：固定大小内存池、栈分配器、placement new

// fixed_pool.h - 单线程固定大小内存池
#pragma once
#include <cstddef>
#include <cstdint>

class SimpleFixedPool {
    struct Node { Node* next; };

    void* buffer_;
    Node* free_head_;
    std::size_t slot_size_;
    std::size_t slot_count_;

public:
    SimpleFixedPool(void* buf, std::size_t slot_size, std::size_t count)
        : buffer_(buf)
        , free_head_(nullptr)
        , slot_size_((slot_size < sizeof(Node*)) ? sizeof(Node*) : slot_size)
        , slot_count_(count)
    {
        // 初始化空闲链表
        char* p = static_cast<char*>(buffer_);
        for (std::size_t i = 0; i < slot_count_; ++i) {
            Node* n = reinterpret_cast<Node*>(p + i * slot_size_);
            n->next = free_head_;
            free_head_ = n;
        }
    }

    void* allocate() noexcept {
        if (!free_head_) return nullptr;
        Node* n = free_head_;
        free_head_ = n->next;
        return n;
    }

    void deallocate(void* p) noexcept {
        Node* n = static_cast<Node*>(p);
        n->next = free_head_;
        free_head_ = n;
    }

    std::size_t slot_size() const noexcept { return slot_size_; }
    std::size_t slot_count() const noexcept { return slot_count_; }
    std::size_t capacity() const noexcept { return slot_count_ * slot_size_; }
};

// fixed_pool_demo.cpp - 固定大小内存池演示
#include "fixed_pool.h"
#include <iostream>
#include <cstring>

// 消息结构
struct Message {
    int id;
    int priority;
    char data[32];

    Message(int i, int p, const char* d) : id(i), priority(p) {
        std::strncpy(data, d, sizeof(data) - 1);
        data[sizeof(data) - 1] = '\0';
    }

    void display() const {
        std::cout << "  Message " << id << " (pri=" << priority
                  << "): " << data << '\n';
    }
};

int main() {
    std::cout << "=== Fixed Size Pool Demo ===\n\n";

    // 创建内存池
    constexpr std::size_t NUM_MESSAGES = 8;
    constexpr std::size_t MESSAGE_SIZE = sizeof(Message);
    alignas(Message) static char buffer[NUM_MESSAGES * MESSAGE_SIZE];

    SimpleFixedPool pool(buffer, MESSAGE_SIZE, NUM_MESSAGES);

    std::cout << "Pool configuration:\n";
    std::cout << "  Slot size: " << pool.slot_size() << " bytes\n";
    std::cout << "  Slot count: " << pool.slot_count() << '\n';
    std::cout << "  Total capacity: " << pool.capacity() << " bytes\n\n";

    // 分配消息
    std::cout << "=== Allocating messages ===\n";
    Message* msg1 = static_cast<Message*>(pool.allocate());
    if (msg1) {
        new (msg1) Message(1, 10, "Hello");
        msg1->display();
    }

    Message* msg2 = static_cast<Message*>(pool.allocate());
    if (msg2) {
        new (msg2) Message(2, 5, "World");
        msg2->display();
    }

    Message* msg3 = static_cast<Message*>(pool.allocate());
    if (msg3) {
        new (msg3) Message(3, 8, "Embedded");
        msg3->display();
    }

    std::cout << "\n=== Deallocating msg2 ===\n";
    msg2->~Message();
    pool.deallocate(msg2);

    // 重新分配
    std::cout << "\n=== Allocating new message ===\n";
    Message* msg4 = static_cast<Message*>(pool.allocate());
    if (msg4) {
        new (msg4) Message(4, 3, "Systems");
        msg4->display();
    }

    // 填满池子
    std::cout << "\n=== Filling the pool ===\n";
    Message* msgs[NUM_MESSAGES];
    msgs[0] = msg1;
    msgs[1] = msg3;
    msgs[2] = msg4;

    for (int i = 3; i < NUM_MESSAGES; ++i) {
        msgs[i] = static_cast<Message*>(pool.allocate());
        if (msgs[i]) {
            new (msgs[i]) Message(i + 1, i, "Filler");
            std::cout << "  Allocated message " << (i + 1) << '\n';
        }
    }

    // 尝试过度分配
    std::cout << "\n=== Attempting over-allocation ===\n";
    Message* fail = static_cast<Message*>(pool.allocate());
    if (!fail) {
        std::cout << "  Correctly failed (pool exhausted)\n";
    }

    // 清理
    std::cout << "\n=== Cleanup ===\n";
    for (int i = 0; i < NUM_MESSAGES; ++i) {
        if (msgs[i]) {
            msgs[i]->~Message();
            pool.deallocate(msgs[i]);
        }
    }

    std::cout << "All messages deallocated\n";

    std::cout << "\n=== Key benefits ===\n";
    std::cout << "- O(1) allocation and deallocation\n";
    std::cout << "- Zero fragmentation\n";
    std::cout << "- High memory utilization\n";
    std::cout << "- Perfect for same-sized objects\n";
    std::cout << "- Cache-friendly (local allocation)\n";

    return 0;
}

// stack_allocator.h - 支持标记回滚的栈分配器
#pragma once
#include <cstddef>
#include <cstdint>
#include <new>

class StackAllocator {
    char* start_;
    char* top_;
    char* end_;

public:
    StackAllocator(void* buf, std::size_t size)
        : start_(static_cast<char*>(buf))
        , top_(start_)
        , end_(start_ + size)
    {}

    void* allocate(std::size_t n, std::size_t align = alignof(std::max_align_t)) noexcept {
        // 对齐处理
        std::uintptr_t p = reinterpret_cast<std::uintptr_t>(top_);
        std::size_t mis = p % align;
        std::size_t offset = mis ? (align - mis) : 0;

        if (top_ + offset + n > end_) return nullptr;

        top_ += offset;
        void* res = top_;
        top_ += n;
        return res;
    }

    // 标记当前栈位置
    using Marker = char*;
    Marker mark() noexcept { return top_; }

    // 回滚到指定标记
    void rollback(Marker m) noexcept {
        if (m >= start_ && m <= top_) {
            top_ = m;
        }
    }

    void reset() noexcept { top_ = start_; }

    std::size_t used() const noexcept { return top_ - start_; }
    std::size_t available() const noexcept { return end_ - top_; }
    std::size_t capacity() const noexcept { return end_ - start_; }
};

// stack_allocator_demo.cpp - 栈分配器演示
#include "stack_allocator.h"
#include <iostream>
#include <cstring>

struct FrameData {
    int frame_num;
    float values[8];

    FrameData(int fn) : frame_num(fn) {
        for (int i = 0; i < 8; ++i) {
            values[i] = fn * 0.1f + i;
        }
    }

    void display() const {
        std::cout << "  Frame " << frame_num << ": [";
        for (int i = 0; i < 8; ++i) {
            std::cout << values[i];
            if (i < 7) std::cout << ", ";
        }
        std::cout << "]\n";
    }
};

int main() {
    std::cout << "=== Stack Allocator Demo ===\n\n";

    constexpr std::size_t BUFFER_SIZE = 4096;
    static char buffer[BUFFER_SIZE];
    StackAllocator allocator(buffer, BUFFER_SIZE);

    std::cout << "Initial state:\n";
    std::cout << "  Capacity: " << allocator.capacity() << " bytes\n";
    std::cout << "  Used: " << allocator.used() << " bytes\n\n";

    // 模拟帧分配
    std::cout << "=== Frame 1 allocation ===\n";
    auto mark1 = allocator.mark();

    FrameData* frame1 = static_cast<FrameData*>(allocator.allocate(sizeof(FrameData)));
    if (frame1) {
        new (frame1) FrameData(1);
        frame1->display();
    }

    // 临时分配
    float* temp_data = static_cast<float*>(allocator.allocate(32 * sizeof(float)));
    if (temp_data) {
        std::cout << "  Allocated 32 floats for temp data\n";
    }

    std::cout << "  Used after frame 1: " << allocator.used() << " bytes\n\n";

    std::cout << "=== Frame 2 allocation ===\n";
    auto mark2 = allocator.mark();

    FrameData* frame2 = static_cast<FrameData*>(allocator.allocate(sizeof(FrameData)));
    if (frame2) {
        new (frame2) FrameData(2);
        frame2->display();
    }

    double* more_temp = static_cast<double*>(allocator.allocate(16 * sizeof(double)));
    if (more_temp) {
        std::cout << "  Allocated 16 doubles for temp data\n";
    }

    std::cout << "  Used after frame 2: " << allocator.used() << " bytes\n\n";

    std::cout << "=== Rolling back to mark2 ===\n";
    allocator.rollback(mark2);
    std::cout << "  Used after rollback: " << allocator.used() << " bytes\n\n";

    std::cout << "=== Frame 3 allocation ===\n";
    FrameData* frame3 = static_cast<FrameData*>(allocator.allocate(sizeof(FrameData)));
    if (frame3) {
        new (frame3) FrameData(3);
        frame3->display();
    }
    std::cout << "  Used after frame 3: " << allocator.used() << " bytes\n\n";

    // 清理 frame1
    frame1->~FrameData();
    allocator.rollback(mark1);

    std::cout << "=== After rolling back to mark1 ===\n";
    std::cout << "  Used: " << allocator.used() << " bytes\n\n";

    std::cout << "=== Key use cases ===\n";
    std::cout << "- Frame-based allocation (games, simulations)\n";
    std::cout << "- Temporary scratch buffers\n";
    std::cout << "- Scope-based resource cleanup\n";
    std::cout << "- Exception-safe rollback\n";

    return 0;
}

// placement_new_demo.cpp - 演示 placement new 与对象构造/析构
#include <iostream>
#include <new>
#include <cstring>

// 简单的分配器接口
class SimpleAllocator {
public:
    virtual void* allocate(std::size_t n) = 0;
    virtual void deallocate(void* p) = 0;
};

// 示例对象
struct Widget {
    int id;
    char name[32];
    bool initialized;

    Widget(int i, const char* n) : id(i), initialized(true) {
        std::strncpy(name, n, sizeof(name) - 1);
        name[sizeof(name) - 1] = '\0';
        std::cout << "  Widget " << id << " constructed\n";
    }

    ~Widget() {
        std::cout << "  Widget " << id << " destroyed\n";
        initialized = false;
    }

    void greet() const {
        if (initialized) {
            std::cout << "    Hello, I'm Widget " << id << " (" << name << ")\n";
        }
    }
};

// C++ 风格的构造包装器
template<typename T, typename Alloc, typename... Args>
T* construct_with(Alloc& a, Args&&... args) {
    void* mem = a.allocate(sizeof(T));
    if (!mem) return nullptr;
    return new (mem) T(std::forward<Args>(args)...);
}

// C++ 风格的析构包装器
template<typename T, typename Alloc>
void destroy_with(Alloc& a, T* obj) noexcept {
    if (!obj) return;
    obj->~T();
    a.deallocate(static_cast<void*>(obj));
}

// 简单的线性分配器用于演示
class DemoAllocator : public SimpleAllocator {
    char buffer[1024];
    char* ptr;

public:
    DemoAllocator() : ptr(buffer) {}

    void* allocate(std::size_t n) override {
        if (ptr + n > buffer + sizeof(buffer)) return nullptr;
        void* res = ptr;
        ptr += n;
        return res;
    }

    void deallocate(void* p) override {
        // 线性分配器不支持单个释放
        (void)p;
    }
};

int main() {
    std::cout << "=== Placement New Demo ===\n\n";

    DemoAllocator alloc;

    std::cout << "=== Using construct_with ===\n";
    Widget* w1 = construct_with<Widget>(alloc, 1, "Alpha");
    Widget* w2 = construct_with<Widget>(alloc, 2, "Beta");
    Widget* w3 = construct_with<Widget>(alloc, 3, "Gamma");

    std::cout << "\n=== Using widgets ===\n";
    if (w1) w1->greet();
    if (w2) w2->greet();
    if (w3) w3->greet();

    std::cout << "\n=== Using destroy_with ===\n";
    destroy_with(alloc, w2);
    std::cout << "Widget 2 destroyed\n";

    std::cout << "\n=== Manual placement new demo ===\n";
    // 手动 placement new
    char storage[sizeof(Widget)];
    Widget* w_manual = new (storage) Widget(99, "Manual");

    std::cout << "\n";
    w_manual->greet();

    std::cout << "\n=== Manual cleanup ===\n";
    // 必须手动调用析构函数
    w_manual->~Widget();

    // 清理剩余对象
    std::cout << "\n=== Cleanup remaining ===\n";
    destroy_with(alloc, w1);
    destroy_with(alloc, w3);

    std::cout << "\n=== Key points ===\n";
    std::cout << "- Placement new separates allocation from construction\n";
    std::cout << "- Must manually call destructor for placement-new objects\n";
    std::cout << "- Perfect for custom allocators and object pools\n";
    std::cout << "- Always pair new (mem) Type with ptr->~Type()\n";

    return 0;
}