TCMalloc 是 Google 开发的 gperftools 中的一款内存分配工具，在 Golang 等诸多知名项目中均有使用。今天我们一起走近技术细节，解密它的高效内核。

一、总体架构

TCMalloc 按照内存大小区间划分为小/中/大三类，由不同的数据结构进行管理。

通过 SizeMap，还可以对小内存继续细分。SizeMap 将用户申请的不超过 256K 的内存大小映射到 85 种对齐的大小类型（size class），最小 8 字节，最大 256K，并记录了大小类型到 num_objects_to_move、class_to_pages 的映射关系。（这两个整型数值的意义详见后文）

大块连续的内存按照 Page (8K) 为最小单位进行追踪，一个或多个连续的 Page 构成一个 Span。Page ID 与 Span 的映射关系由 Page Map（通过 radix-tree 实现，如下图）进行维护。

一个 Span 可能作为一块连续的中/大内存直接分配给用户使用，也可能分裂成小内存块（object）放到 Central Cache 或者 Thread Cache 中，再分配给用户。Span 结构体记录一个 Span 的详细信息，它包括：

1. start 和 length：记录 Span 包含的 Page 范围
2. prev 和 next ：Span 类型的指针，用于将 Span 连接成 Spanlist
3. objects ：记录 Span 分裂成的小内存块的链表
4. span_iter_space：记录 Span 在 SpanSet（Page Heap中的Span集合）中的迭代器，方便 Span 从 SpanSet 中移除
5. sizeclass 表示 Span 分裂成的小内存块的大小类型（0 表示没有分裂成小内存）
6. refcount 表示 Span 分裂成的小内存块的引用计数，即分配给 Thread Cache 使用的 object 数量
7. location 枚举变量记录 Span 所在的位置（pageID 相邻且 location 相同的空闲 Span 可以合并成更大的 Span）

TCMalloc 的总体架构以及申请释放内存的流程如下图所示，其中 System Allocator 使用的是 mmap 和 sbrk：

二、Central Cache 与 Thread Cache

小内存（Size≤256 K）通过 Thread Cache 和 Central Cache 分配，每个线程都有一个 Thread Cache，所有线程共享一个 Central Cache。

它们都由 85 条固定大小类型（最小 8 字节，最大 256K）的 freelist 构成。freelist 包含相同大小类型的 object 构成的链表，并使用嵌入式指针连接以提高内存利用率。

分配小内存的流程如下：

1. 通过 Size Map 将其大小映射到相应的大小类型
2. 在 Thread Cache 中查找该大小类型对应的 freelist
3. 如果 freelist 不为空，我们从列表中删除第一个 object 并返回它。由于线程内不存在内存的并发申请，这个过程无需获得任何锁

如果 Thread Cache 的 freelist 为空：

1. 我们从 Central Cache 中该大小类型的 freelist 即 Central freelist 上获取一堆 object（由于 Central Cache 由所有 Thread 持锁并发访问，内存在 Thread Cache 和 Central Cache 之间传递时，每次传递 num_objects_to_move个object，以提高内存传递的效率）
2. 将它们放在 Thread Cache 的 freelist 中
3. 将新获取的 object 之一返回给申请者

如果 Central freelist 也是空的：

1. 我们以 Page 为单位从 Page Heap 分配一系列连续 Page（即一个 Span），具体的 Page 数是从 SizeMap 获取的该大小类型的 class_to_pages 值
2. 将这些 Page 拆分为该大小类型的一组 object
3. 将新的 object 放在 Central freelist 中
4. 和以前一样，将其中一些 object 移到 Thread Cache 的 freelist 中

上述的流程在实现上有很多重要的细节：
每条 Central freelist 通过 empty 和 nonempty 两条链表记录从 Page Heap 获取的 Span，empty 表示 Span 全部传递给了 Thread Cache。Span 先分裂成该大小类型的 objects 并挂在 nonempty 上，refcount 初始值为 0，当 object 传递给 Thread Cache 时 refcount 增加。

为了方便地在 Thread Cache 和 Central Cache 之间进行 num_objects_to_move 个内存块的传递，每条 Central freelist 上都有一个定长 64 的插槽数组 tc_slots_，存用于放从 Thread cache 回收的 objects，数组元素为 TCEntry，每个 entry 记录 num_objects_to_move 个 object 的头尾指针，即一次移动的 objects 放在一个插槽里。

通过 max_cache_size=min(64, 1M/(num_objects_to_move*size_bytes))，每条 Central freelist 就能把 tc_slots_ 总大小限制在 1M 以内，插槽数不超过 64 个且有一个初始的 cache_size（≤max_cache_size）。

Central freelist 收到 thread cache 交还的 objects 后，如果 Central Cache 还有空间，即 freelist 还有插槽可用（即 used<cache_size），或者能让随机一条其他 size class 的 Central freelist 的 cache_size 减少，使得本条 freelist 的cache_size 增加且不超过 max_cache_size（只需要随机到的这条 Central freelist 的 cache_size>0 就能满足）。

把这些 objects 插入空闲的插槽；否则把 objects 逐一释放给对应的 Span，Span 的 refcount 也相应地减少，当 refcount 为 0 时，说明整个 Span 都是空闲的，将其释放回 Page Heap 中。

Thread Cache 向 Central Cache 申请内存时，会优先从插槽数组 tc_slots_ 获取，如果 tc_slots_ 为空，再从 nonempty 链表上的 Span 中获取。

另外，为了使线程可以快速获取 Thread Cache，Thread Cache 的指针被保存在了 _thread 修饰的静态变量 threadlocal_data_中。该修饰符表示对于每一个线程，都有一个线程本地的静态变量，线程之间互不千扰。

为了自动销毁 Thread Cache，使用 pthread 的 pthread_key_create 接口注册 DestroyThreadCache 方法，该方法将在线程结束时执行以销毁 Thread Cache。

三、Page Heap

超过 256K 的内存以及 Central Cache 以 page 为单位申请的内存都由 Page Heap 分配。

Page Heap 有 128 对 SpanList，分别放置内存大小 1 page 到 128 page 的 Span。超过 128 page 的 Span 则放在一对 SpanSet（使用 std::set，底层是用红黑树实现的）中管理。