手写内存池

实现满足对齐要求的固定块自由链表、页级扩容和 pmr::memory_resource 适配器。

本系列代码使用 C++20 和 oc::handmade 命名空间，目标是解释实现机制、复杂度和工程边界，不是替代标准库。普通容器与缓存核心不内置互斥锁；这不代表 lock-free。

一、学习目标

区分内存分配与对象构造
实现 O(1) 块分配回收
适配 polymorphic_allocator

二、前置条件

掌握对象生命周期、对齐、operator new 和互斥锁。

Linux/macOS：

cmake -S . -B build -DCMAKE_BUILD_TYPE=Debug
cmake --build build -j
ctest --test-dir build --output-on-failure

Windows PowerShell：

cmake -S . -B build -DCMAKE_BUILD_TYPE=Debug
cmake --build build --config Debug
ctest --test-dir build -C Debug --output-on-failure

三、问题与设计选择

每页切分为固定大小槽位，空闲槽位自身保存 next 指针。大尺寸或更高对齐请求委托 upstream；同步包装只保护自由链和页表。

这里刻意保留一条边界：教学实现覆盖构造、复制移动、核心修改、查找和迭代契约，但不复刻标准库全部重载、ABI、constexpr、异构查找或节点句柄。

四、内存布局与核心不变量

每个槽位恰处于空闲链或已借出状态；页地址满足最大对齐；析构前已借出计数必须为 0。

每个修改操作都按“准备资源 → 构造新状态 → 提交连接或指针 → 清理旧状态”的顺序设计。提交点之前发生异常，应保持原对象可继续使用；无法提供强保证时，会在接口说明中明确基本保证。

五、核心实现

void* allocate_block() {
    std::scoped_lock lock(mutex_);
    if (!free_) add_page();
    free_node* result = free_;
    free_ = free_->next;
    ++outstanding_;
    return result;
}

void deallocate_block(void* p) noexcept {
    std::scoped_lock lock(mutex_);
    auto* node = static_cast<free_node*>(p);
    node->next = free_;
    free_ = node;
    --outstanding_;
}

上面先聚焦最容易写错的核心步骤；若本篇对应一个独立组件，下一节给出统一工程中的完整教学实现。代码没有放入 std 命名空间，避免未定义行为和名称冲突。

六、完整教学实现

下面是统一工程中经过 GCC、Clang、GoogleTest 和 Sanitizer 验证的完整组件。它依赖前序文章已经实现的公共类型以及头文件中的标准库 #include。

namespace oc::handmade {

class fixed_block_pool {
    struct free_node { free_node* next; };
    struct page { void* memory; };
    std::size_t block_size_;
    std::size_t alignment_;
    std::size_t blocks_per_page_;
    free_node* free_{};
    std::vector<page> pages_;
    std::size_t outstanding_{};
    mutable std::mutex mutex_;

    static std::size_t round_up(std::size_t value, std::size_t alignment) {
        return (value + alignment - 1) / alignment * alignment;
    }
    void add_page_locked() {
        const std::size_t bytes = block_size_ * blocks_per_page_;
        void* memory = ::operator new(bytes, std::align_val_t(alignment_));
        pages_.push_back({memory});
        auto* raw = static_cast<std::byte*>(memory);
        for (std::size_t i = 0; i < blocks_per_page_; ++i) {
            auto* item = reinterpret_cast<free_node*>(raw + i * block_size_);
            item->next = free_;
            free_ = item;
        }
    }

public:
    fixed_block_pool(
        std::size_t requested_size,
        std::size_t requested_alignment = alignof(std::max_align_t),
        std::size_t blocks_per_page = 256
    )
        : alignment_(std::max(requested_alignment, alignof(void*))),
          blocks_per_page_(blocks_per_page) {
        if (blocks_per_page_ == 0 || (alignment_ & (alignment_ - 1)) != 0)
            throw std::invalid_argument("invalid fixed_block_pool configuration");
        block_size_ = round_up(std::max(requested_size, sizeof(free_node)), alignment_);
    }
    fixed_block_pool(const fixed_block_pool&) = delete;
    fixed_block_pool& operator=(const fixed_block_pool&) = delete;
    ~fixed_block_pool() {
        for (auto& value : pages_)
            ::operator delete(value.memory, std::align_val_t(alignment_));
    }
    void* allocate_block() {
        std::scoped_lock lock(mutex_);
        if (!free_) add_page_locked();
        free_node* result = free_;
        free_ = free_->next;
        ++outstanding_;
        return result;
    }
    void deallocate_block(void* memory) noexcept {
        if (!memory) return;
        std::scoped_lock lock(mutex_);
        auto* item = static_cast<free_node*>(memory);
        item->next = free_;
        free_ = item;
        assert(outstanding_ > 0);
        --outstanding_;
    }
    std::size_t outstanding() const {
        std::scoped_lock lock(mutex_);
        return outstanding_;
    }
    std::size_t block_size() const noexcept { return block_size_; }
    std::size_t alignment() const noexcept { return alignment_; }
};

class fixed_block_resource : public std::pmr::memory_resource {
    fixed_block_pool pool_;
    std::pmr::memory_resource* upstream_;
protected:
    void* do_allocate(std::size_t bytes, std::size_t alignment) override {
        if (bytes <= pool_.block_size() && alignment <= pool_.alignment())
            return pool_.allocate_block();
        return upstream_->allocate(bytes, alignment);
    }
    void do_deallocate(void* memory, std::size_t bytes, std::size_t alignment) override {
        if (bytes <= pool_.block_size() && alignment <= pool_.alignment())
            pool_.deallocate_block(memory);
        else
            upstream_->deallocate(memory, bytes, alignment);
    }
    bool do_is_equal(const std::pmr::memory_resource& other) const noexcept override {
        return this == &other;
    }
public:
    fixed_block_resource(
        std::size_t block_size,
        std::size_t alignment = alignof(std::max_align_t),
        std::pmr::memory_resource* upstream = std::pmr::get_default_resource()
    ) : pool_(block_size, alignment), upstream_(upstream) {}
};

}  // namespace oc::handmade

生产级标准库还要处理完整 allocator 传播、全部重载、ABI、调试迭代器和平台特化；这里保留的是能够独立推导核心数据结构的教学边界。

七、使用示例与输出

预期输出或状态：

首次申请触发一页扩容；随后 1024 次同尺寸申请不再调用 upstream，归还后 outstanding 为 0。

示例必须在文章对应的测试目标中实际编译。涉及顺序的输出只依赖接口明确承诺的顺序；无序容器不会把某次桶顺序写成稳定结果。

八、复杂度与失效规则

操作	复杂度	说明
allocate 小块	O(1)	空链时申请一页
deallocate 小块	O(1)	压回自由链
大块请求	取决于 upstream	透明转发
析构	O(页数)	释放整页

复杂度中的 O(1) 若标记为“平均”或“摊还”，不能在面试中省略限定词。任何重新分配、节点删除、rehash 或缓存淘汰都必须单独说明迭代器、引用与指针是否失效。

九、异常安全与资源管理

获取资源后立即交给 RAII 对象或明确记录已构造数量。
用户类型构造、复制、移动、比较器和哈希器都可能抛异常。
只有在所有后续步骤不会失败时才修改不可回滚的链接。
析构、释放和关闭路径不得抛异常。
并发包装通过回调在锁内访问，避免返回保护对象的裸引用。

十、常见错误

1. 块大小小于 next 指针

块大小小于 next 指针会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

2. 忽略用户请求的 alignment

忽略用户请求的 alignment会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

3. 池析构时仍有对象存活

池析构时仍有对象存活会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

十一、面试追问

内存池为什么不等于对象池？
自由链写入已释放内存是否合法？
多线程池如何避免全局锁争用？

回答时先说数据结构不变量，再给复杂度，最后说明异常、迭代器或并发边界，通常比背诵结论更有说服力。

十二、练习与自测

实现 pmr 适配器
增加调试双重释放检测
比较全局锁与线程本地缓存

自测标准：能够不看代码画出内存或节点关系，解释一次成功操作和一次失败回滚，并写出至少一个会击穿错误实现的测试。

十三、官方资料与延伸阅读

上一篇：手写 std::weak_ptr ｜下一篇：手写对象池