atomic编程：从freelist到CAS无锁栈

来源：互联网 2026-07-21 07:54:02

从零实现C++内存池，从freelist固定大小分配器起步，逐步叠加多尺寸管理、thread_local无锁缓存、全局调剂、CAS无锁栈、内存对齐及越界检测。最终多线程场景下，线程本地缓存分配速度达malloc的2.5倍，零外部依赖。

从零手写 C++ 内存池 —— 从 freelist 到无锁并发

你可能会问：系统自带的 malloc/free 已经能处理各种大小、多线程竞争、碎片回收，内部逻辑极其复杂，为什么还要自己手写内存池？

答案很简单：很多场景不需要通用的 malloc。比如你的 muduo 在处理几十万个 TCP 连接时，每个连接的 Buffer 大小固定。每来一个新连接都要 new Buffer(4096)，频繁的系统调用会拖死性能。

长期稳定更新的攒劲资源： >>>点此立即查看<<<

atomic编程：从freelist到CAS无锁栈

内存池的核心逻辑只有一句话：预分配一大块内存，自己管理分配和回收，系统调用减少 90% 以上。

这篇文章从最简单的 freelist 开始，一步步加上多尺寸管理、线程本地缓存、全局调剂、CAS 无锁、内存对齐、越界检测。一共 6 个头文件，2000+ 行代码，零外部依赖。

第 1 层：FixedAllocator — freelist 复用

核心思路： 预分配一块连续内存，切成等大块。空闲块的前 8 字节存指针指向下一个空闲块——这就是 freelist。分配/回收都是 O(1)。

 复制代码预分配内存: [block][block][block][block]...
freelist:   head → block3 → block2 → block1 → block0 → nullptr

为什么 freelist 没有额外内存开销？ 空闲块的前 8 字节正好存 next 指针。分配出去后用户数据覆盖这块内存——不需要链表指针了。回收时重新写回 next。复用同一块内存存指针，零额外开销。

 复制代码template <size_t BlockSize, size_t Align, bool Debug>
class FixedAllocator {
    struct Block { Block* next; };   // 只用 8 字节存链表    Block* freeList_;                 // 空闲块链表头
    char* pool_;                      // 预分配的大块内存    void* allocate() {
        if (!freeList_) return nullptr;
        Block* b = freeList_;
        freeList_ = b->next;          // head 后移
        return b;
    }    void deallocate(void* p) {
        Block* b = static_cast(p);
        b->next = freeList_;          // 归还的块指向原来的 head
        freeList_ = b;                // 自己成为新 head
    }
};

构造时建 freelist： new char[BlockSize * numBlocks] → 切成等大块 → 每块 b->next = freeList_; freeList_ = b → 插到头。栈式释放——LIFO，最后归还的块被最先取走。

第 2 层：SlabAllocator — 多尺寸管理

FixedAllocator 只管理一种大小。实际需要支持多种大小——8 字节、16 字节、32 字节、64 字节... SlabAllocator 管理多个 FixedAllocator，根据请求大小分到合适的 slab：

 复制代码class SlabAllocator {
    FixedAllocator<8>   slab8;
    FixedAllocator<16>  slab16;
    FixedAllocator<32>  slab32;
    FixedAllocator<64>  slab64;
    // ...    void* allocate(size_t size) {
        size_t rounded = roundUp(size);    // 向上取整到 2 的幂次
        if (rounded <= 8)   return slab8.allocate();
        if (rounded <= 16)  return slab16.allocate();
        // ...
        return ::malloc(size);             // 超大 → 直接 malloc
    }
};

roundUp 位运算： n--; n |= n>>1; ...; return n+1 ——最高位的 1 扩散到所有低位，+1 得 2 的幂次。比如 30 → 32，60 → 64。经典算法。

第 3 层：ThreadCache — thread_local 无锁

多线程下多个线程共用一个 FixedAllocator 需要加锁——每个 allocate/deallocate 都要争锁。但如果每个线程有自己独立的 freelist，就不需要锁了。

 复制代码template <size_t BlockSize>
class ThreadCache {
    static thread_local FixedAllocator alloc_;    void* allocate() { return alloc_.allocate(); }     // 无锁！
    void deallocate(void* p) { alloc_.deallocate(p); }
};

thread_local 关键字做了什么： 每个线程有自己独立的 alloc_ 副本——物理上是两块不同的内存。线程 A 跟线程 B 同时调 allocate()，各自操作自己的 freelist，互不干扰。线程安全不是"加了锁"——是"根本没有共享数据"。

static + thread_local 组合：static = 所有 ThreadCache 对象共享一份 alloc_，thread_local = 但不同线程的副本独立。两个关键字各管各的。

第 4 层：CentralCache — 全局调剂

ThreadCache 容量有限（默认 1024 块）。用完了返回 nullptr——需要从全局池补货。CentralCache 是线程间的"块交换中心"：

 复制代码线程 A: allocate() → ThreadCache 空了 → 找 CentralCache 批量要
线程 B: deallocate() → ThreadCache 太多了 → 批量还给 CentralCacheCentralCache: 持有 FixedAllocator + mutex。只在批量转移时加锁

 复制代码template <size_t BlockSize>
class CentralCache {
    FixedAllocator alloc_;
    std::mutex mutex_;    void* allocate() {
        std::lock_guard lock(mutex_);
        return alloc_.allocate();
    }
};

ThreadCache 99% 的请求不碰锁——只在补货/回收时锁一次。跟 jemalloc 的 tcache + ecache 两层缓存一个道理。

第 5 层：LockFreeStack — CAS 无锁 freelist

CentralCache 的互斥锁在竞争激烈时成为瓶颈。CAS（Compare And Swap）原子指令可以替代锁——多线程并发 push/pop 不需要任何锁。

CAS 原理： "如果这块内存还是原来的值，就把新值写进去；如果被别的线程改了，重试。"

 复制代码void push(Node* node) {
    node->next = head_.load();        // 新节点指向当前头
    while (!head_.compare_exchange_weak(
               node->next, node)) {   // CAS: 如果 head 没变 → 改成 node
        // CAS 失败 → 其他线程抢先了 → 重试
    }
}Node* pop() {
    Node* node = head_.load();        // 记住当前头
    while (node && !head_.compare_exchange_weak(
                      node, node->next)) {
        // CAS 失败 → 重试
    }
    return node;
}

为什么不会死锁： CAS 失败不阻塞——原地重试。其他线程的修改帮你的链表维护好了，你重读一次新的头就行。"合作式无锁"——每个线程的修改对其他线程有利。

内存序： push 用 release——保证写入后对其他线程可见。pop 用 acquire——保证读到前一个 push 的完整数据。失败都用 relaxed——反正是重试，无所谓。这是 CPU 的内存模型——先记住固定搭配，以后看 OSTEP 理解。

第 6 层：内存对齐

SIMD 指令（A VX/SSE）要求数据地址是 16/32/64 的倍数。alignas 关键字让编译器保证对齐：

 复制代码struct alignas(64) Block {
    Block* next;
};// 每个块的起始地址必须是 64 的倍数
// stride = (BlockSize + Align - 1) & ~(Align - 1)  — 向上取整 BlockSize 到 Align 倍数

(addr + Align - 1) & ~(Align - 1) 向上取整地址到 Align 的倍数。比如 addr=0x1003, Align=64：(0x1003+63) & ~63 = 0x1040 。位运算比 ceil(a/64)*64 快。

第 7 层：Debug 模式 — guard bytes 检测越界

每个块前后放哨兵字节（0xDEADBEEFCAFEBABE）。deallocate 时检查哨兵是否被改——被改了说明有越界写。

 复制代码分配: [next 8B] [front guard 8B] [用户数据 BlockSize] [back guard 8B]
        ↑         ↑               ↑                    ↑
        b        b+8            b+16               b+stride-8
                      allocate 返回 b+16

 复制代码void deallocate(void* p) {
    Block* b = reinterpret_cast(reinterpret_cast<char*>(p) - 16);
    uint64_t* front = reinterpret_cast<uint64_t*>(reinterpret_cast<char*>(b) + 8);
    assert(*front == GUARD && "front guard corrupted!");
    // 检查 back guard...
}

if constexpr (Debug) 决定是否编译 guard 代码。Debug=false 时全部跳过——零运行时开销。

性能数据

多线程 4 核，100K 次 alloc+free per thread：

 复制代码FixedAllocator + mutex:  18M ops/s
malloc           + mutex: 13M ops/s
ThreadCache      no lock: 33M ops/s  — 2.5x faster than malloc

单线程 SlabAllocator vs malloc 基本持平——微基准的差异在毫秒级。多线程场景 thread_local 无锁的优势明显。

项目结构

 复制代码memory-pool/
├── fixed_allocator.h    — freelist 单链表 + 对齐 + Debug guard
├── slab_allocator.h     — 多尺寸管理 + roundUp 位运算
├── thread_cache.h       — thread_local 无锁分配
├── central_cache.h      — mutex 全局调剂
├── lockfree_stack.h     — CAS 原子无锁栈
├── bench.cpp            — 单线程 benchmark
├── bench_mt.cpp         — 多线程 benchmark
├── main.cpp             — 综合测试
└── README.md

6 个头文件，2000+ 行代码，零外部依赖。