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，底层是用红黑树实现的）中管理。

当申请 K 个 page 的内存时，从第 K 对 SpanList 开始搜索，如果该对 SpanList 为空，查看下一对 SpanList，以此类推。

如果找到长度 ≥K 的 Span，则切出长度为 K 的 Span 返回，剩余部分被重新插入合适的 SpanList 中。如果没有 SpanList 可以满足分配，则通过 std::set 提供的 upper_bound 接口，从 SpanSet 中找到大于等于 K 个 page 的最小 Span，同样切割后进行返回，剩余部分根据大小插入 SpanSet 或合适的 SpanList。

如果没有找到满足需求的 Span，将通过 System Allocator 从系统获取内存后重复上述搜索过程。从 System Allocator 获取内存时，如果实际需要的内存不满 1M，先尝试申请 1M 内存；如果申请失败，再尝试申请实际需要的内存大小。

在上述流程的实现中，我们依然找到了一些有意思的细节：

一对 SpanList，包含 normal 和 returned 两条链表，搜索时先查找 normal，如果 normal 为空，再查找 returned。从 System Allocator 获取的或从 Central Cache 归还的空闲 Span 挂在 normal 上，从 normal 上释放给操作系统的 Span 挂在 returned 上。

这里使用了一个特殊的技巧来提高 Page Heap 的效率：returned 上的 Span 并没有真的被释放，只是使用 MADV_FREE 标记了这块内存，内核会等到内存紧张时才真正将其释放。在真正释放之前，这块内存依然可以随时复用。SpanSet 同理。

释放给 Page Heap 的 Span 会尽可能合并：Span 结构体中记录了 Span 的 Page 范围以及它的 location（位于 normal 还是 returned 链表中）。当一个 Span 被释放回 Page Heap  时，假设 Page 范围是 [p, q]，我们查找 Page p-1 和 q+1 所在的 Span。

如果有相邻且 location 相同的空闲 Span，就将它（们）与 Span[p, q] 合并。合并成的 Span 根据大小被插入到合适的 SpanList 中或 SpanSet 中。这样的处理对减少内存碎片颇有帮助。