不太懂 atomic？我花了一下午从 freelist 写到 CAS 无锁栈

从零手写 C 内存池 —— 从 freelist 到无锁并发一个下午10 个功能从固定大小分配器到 CAS 无锁栈。这篇文章记录每一层的设计思路和核心代码。适合想理解malloc 内部怎么工作的 C 初学者。为什么要手写内存池malloc/free是通用目的的内存分配器——它要处理各种大小、多线程竞争、碎片回收内部逻辑极其复杂。但很多场景不需要通用的 malloc——你的 muduo 在处理几十万个 TCP 连接时每个连接的 Buffer 大小固定。每来一个新连接都要new Buffer(4096)频繁的系统调用拖死性能。内存池做一件事预分配一大块内存自己管理分配和回收系统调用减少 90% 以上。这篇文章从最简单的 freelist 开始一步步加上多尺寸管理、线程本地缓存、全局调剂、CAS 无锁、内存对齐、越界检测。代码在 GitHub 上MIT 协议memory-poolhttps://github.com/ch0sen1pm/memory-pool第 1 层FixedAllocator — freelist 复用核心思路预分配一块连续内存切成等大块。空闲块的前 8 字节存指针指向下一个空闲块——这就是 freelist。分配/回收都是 O(1)。预分配内存: [block][block][block][block]... freelist: head → block3 → block2 → block1 → block0 → nullptr为什么 freelist 没有额外内存开销空闲块的前 8 字节正好存next指针。分配出去后用户数据覆盖这块内存——不需要链表指针了。回收时重新写回next。复用同一块内存存指针零额外开销。templatesize_t BlockSize,size_t Align,boolDebugclassFixedAllocator{structBlock{Block*next;};// 只用 8 字节存链表Block*freeList_;// 空闲块链表头char*pool_;// 预分配的大块内存void*allocate(){if(!freeList_)returnnullptr;Block*bfreeList_;freeList_b-next;// head 后移returnb;}voiddeallocate(void*p){Block*bstatic_castBlock*(p);b-nextfreeList_;// 归还的块指向原来的 headfreeList_b;// 自己成为新 head}};构造时建 freelistnew char[BlockSize * numBlocks]→ 切成等大块 → 每块b-next freeList_; freeList_ b→ 插到头。栈式释放——LIFO最后归还的块被最先取走。第 2 层SlabAllocator — 多尺寸管理FixedAllocator 只管理一种大小。实际需要支持多种大小——8 字节、16 字节、32 字节、64 字节… SlabAllocator 管理多个 FixedAllocator根据请求大小分到合适的 slabclassSlabAllocator{FixedAllocator8slab8;FixedAllocator16slab16;FixedAllocator32slab32;FixedAllocator64slab64;// ...void*allocate(size_t size){size_t roundedroundUp(size);// 向上取整到 2 的幂次if(rounded8)returnslab8.allocate();if(rounded16)returnslab16.allocate();// ...return::malloc(size);// 超大 → 直接 malloc}};roundUp 位运算n--; n | n1; ...; return n1——最高位的 1 扩散到所有低位1 得 2 的幂次。比如 30 → 3260 → 64。经典算法。第 3 层ThreadCache — thread_local 无锁多线程下多个线程共用一个 FixedAllocator 需要加锁——每个 allocate/deallocate 都要争锁。但如果每个线程有自己独立的 freelist就不需要锁了。templatesize_t BlockSizeclassThreadCache{staticthread_localFixedAllocatorBlockSizealloc_;void*allocate(){returnalloc_.allocate();}// 无锁voiddeallocate(void*p){alloc_.deallocate(p);}};thread_local关键字做了什么每个线程有自己独立的alloc_副本——物理上是两块不同的内存。线程 A 跟线程 B 同时调allocate()各自操作自己的 freelist互不干扰。线程安全不是加了锁——是根本没有共享数据。staticthread_local组合static 所有 ThreadCache 对象共享一份 alloc_thread_local 但不同线程的副本独立。两个关键字各管各的。第 4 层CentralCache — 全局调剂ThreadCache 容量有限默认 1024 块。用完了返回 nullptr——需要从全局池补货。CentralCache 是线程间的块交换中心线程 A: allocate() → ThreadCache 空了 → 找 CentralCache 批量要 线程 B: deallocate() → ThreadCache 太多了 → 批量还给 CentralCache CentralCache: 持有 FixedAllocator mutex。只在批量转移时加锁templatesize_t BlockSizeclassCentralCache{FixedAllocatorBlockSizealloc_;std::mutex mutex_;void*allocate(){std::lock_guardstd::mutexlock(mutex_);returnalloc_.allocate();}};ThreadCache 99% 的请求不碰锁——只在补货/回收时锁一次。跟 jemalloc 的tcacheecache两层缓存一个道理。第 5 层LockFreeStack — CAS 无锁 freelistCentralCache 的互斥锁在竞争激烈时成为瓶颈。CASCompare And Swap原子指令可以替代锁——多线程并发 push/pop 不需要任何锁。CAS 原理“如果这块内存还是原来的值就把新值写进去如果被别的线程改了重试。”voidpush(Node*node){node-nexthead_.load();// 新节点指向当前头while(!head_.compare_exchange_weak(node-next,node)){// CAS: 如果 head 没变 → 改成 node// CAS 失败 → 其他线程抢先了 → 重试}}Node*pop(){Node*nodehead_.load();// 记住当前头while(node!head_.compare_exchange_weak(node,node-next)){// CAS 失败 → 重试}returnnode;}为什么不会死锁CAS 失败不阻塞——原地重试。其他线程的修改帮你的链表维护好了你重读一次新的头就行。“合作式无锁”——每个线程的修改对其他线程有利。内存序push 用release——保证写入后对其他线程可见。pop 用acquire——保证读到前一个 push 的完整数据。失败都用relaxed——反正是重试无所谓。这是 CPU 的内存模型——先记住固定搭配以后看 OSTEP 理解。第 6 层内存对齐SIMD 指令AVX/SSE要求数据地址是 16/32/64 的倍数。alignas关键字让编译器保证对齐structalignas(64)Block{Block*next;};// 每个块的起始地址必须是 64 的倍数// stride (BlockSize Align - 1) ~(Align - 1) — 向上取整 BlockSize 到 Align 倍数(addr Align - 1) ~(Align - 1)向上取整地址到 Align 的倍数。比如 addr0x1003, Align64(0x100363) ~63 0x1040✅。位运算比ceil(a/64)*64快。第 7 层Debug 模式 — guard bytes 检测越界每个块前后放哨兵字节0xDEADBEEFCAFEBABE。deallocate 时检查哨兵是否被改——被改了说明有越界写。分配: [next 8B] [front guard 8B] [用户数据 BlockSize] [back guard 8B] ↑ ↑ ↑ ↑ b b8 b16 bstride-8 allocate 返回 b16voiddeallocate(void*p){Block*breinterpret_castBlock*(reinterpret_castchar*(p)-16);uint64_t*frontreinterpret_castuint64_t*(reinterpret_castchar*(b)8);assert(*frontGUARDfront guard corrupted!);// 检查 back guard...}if constexpr (Debug)决定是否编译 guard 代码。Debugfalse时全部跳过——零运行时开销。性能数据多线程 4 核100K 次 allocfree per threadFixedAllocator 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.md6 个头文件2000 行代码零外部依赖。更新记录7/19 FixedAllocator — freelist 固定大小分配器7/19 SlabAllocator — 多尺寸 roundUp7/19 Benchmark vs malloc单线程7/19 ThreadCache — thread_local 无锁7/19 CentralCache — mutex 全局池7/19 LockFreeStack — CAS 原子无锁栈7/19 内存对齐 — alignas stride 向上取整7/19 Debug 模式 — guard bytes 越界检测7/19 Benchmark vs malloc多线程— ThreadCache 2.5x 更快项目已完结。一个下午从 freelist 到 CAS 无锁。代码在 GitHub 上MIT 协议欢迎 star ⭐memory-poolhttps://github.com/ch0sen1pm/memory-pool配套项目my_muduoReactor 网络库my_logger日志库