XMemoryPool

一个基于 C++17 实现的内存分配器，采用 TCMalloc 式三级缓存架构（ThreadCache -> CentralCache -> PageCache），页级内存由 mmap/munmap 管理，支持 Span 合并、Span 对象池与小对象 Span 回收。

核心架构

1. ThreadCache：线程本地缓存。基于 thread_local 每线程独享，小对象分配完全无锁；超过 256KB 的对象直接走 PageCache。
2. CentralCache：中心缓存。按大小类维护共享自由链，与 ThreadCache 批量搬运；每个大小类一把锁，向 PageCache 申请/切分 Span 时先释放桶锁，避免长时间持锁。
3. PageCache：页级管理。统一用 mmap/munmap 与系统交互，在页级做相邻 Span 合并，并用无锁基数树页表支持块→Span 反查。

---

关键技术点

1. 无锁基数树页表（PageMap）

PageCache 需要「给定内存块指针 → 所属 Span」的反查能力，是 Span 回收的前提。

• 结构：3 级 × 12 位页号（覆盖 36 位页号），节点懒分配、运行期只增不删。
• 读路径完全无锁：原子指针 acquire/release 同步，反查不加任何锁。
• 写路径：分配/拆分/合并/回收时在 pageMtx 下同步维护。
• 演进（实测驱动）：最初用 std::map + 全局锁 做反查，16 线程下比系统 malloc 慢约 2 倍；改用无锁页表后恢复为快于 malloc。

2. 小对象 Span 回收

• 每个 Span 记录 totalBlocks / useCount / freeList；CentralCache 按大小类维护「有空闲块的 Span 队列」。
• 块全部归还（useCount == 0）时，Span 交还 PageCache，可被其他大小类复用。
• 不变式：Span 在队列中 ⟺ useCount < totalBlocks，用于安全地判断入队/回收时机。

3. Span 对象池

Span 结构体不再逐个 new/delete，而是从上限 64 的侵入式空闲链表中复用，减少页级元数据操作的系统调用与分配开销。

4. 非线性 Size Class

约 100 个非线性字号（对标 TCMalloc），小对象粒度细、大对象粒度粗，替代 8B 线性分桶造成的数万桶位与管理开销。

5. Span 合并

PageCache 用按起始页号排序的 std::map 索引相邻 Span，dealloc 时向前/向后合并，减少外部碎片。

---

开发历程与关键决策

阶段	主要工作
初版	搭通三级缓存、mmap 页管理、批量搬运与大小类
并发优化	每桶自旋锁 → 分段互斥锁；批量大小与归还阈值调优
引入基数树	用基数树替换 std::map 做 PageID -> Span* 映射
正确性收尾	修复重复加锁与析构 double-free
重构	线性分桶 → 非线性 Size Class；基数树按需退回 std::map
回收与无锁页表	实现 Span 回收；反查因锁竞争回退，重建为无锁基数树页表

几个值得记录的踩坑：

• 重复加锁：SpanList 自带一把锁，而 PageCache 又持有全局锁，二者嵌套导致竞争/死锁隐患；改为「只在 PageCache 入口统一加锁」，SpanList 不再自行加锁。
• 析构 double-free：一个 Span 跨越多页，页表里同一 Span* 会出现多次；进程退出释放时必须两轮处理（先 munmap 页、再按指针去重后显式 ~Span() + free），否则重复释放。
• 无锁读的安全前提：页表写入只发生在「当前没有外部块」的 Span 上（由 useCount 保证），因此读到的页表项总是存活的 Span。

---

正确性验证

• 单元测试：基础分配、内存写入、多线程、边界、压力场景全部通过。
• Valgrind memcheck：0 errors, 0 leaks（含页表节点的析构释放）。
• ThreadSanitizer：单元测试与压测均无数据竞争报告。
  • WSL 下若 TSAN 报 unexpected memory mapping，可用 setarch $(uname -m) -R ./unit_test 关闭 ASLR 后运行。

---

性能基准

同一进程内交替测量，取 3 次运行的中位数（16 线程环境，受 CPU 核数与负载影响，仅供参考）：

测试场景	XMemoryPool	系统 new/delete	相对提升
小对象（8B）	14.4 ms	14.4 ms	≈ 持平
多线程（16 线程，混合 8–512B）	67.6 ms	94.2 ms	+28%
单线程混合尺寸（16B–2KB）	54.0 ms	99.7 ms	+46%

单线程 8B 场景两者接近；本分配器的优势主要体现在多线程竞争与混合尺寸高频分配/释放场景。

---

构建与运行

环境要求

• CMake 3.10+
• C++17 编译器 (GCC/Clang)
• Linux 系统 (支持 pthread & mmap)

编译步骤

mkdir build && cd build
cmake ..
make

使用

#include "MemoryPool.h"

using namespace XmemoryPool;

// 像使用 malloc/free 一样简单
void *ptr = MemoryPool::allocate(64);
MemoryPool::deallocate(ptr, 64);

---

致谢与参考

本项目参考了以下实现与设计思想：

• youngyangyang04/memory-pool：三级缓存架构的参考实现。
• Google TCMalloc：三级缓存与 Size Class 设计思想的来源。

在此基础上，本项目自行实现了非线性 Size Class、Span 对象池、小对象 Span 回收以及无锁基数树页表。