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

通过 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 的详细信息，它包括：

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

分配小内存的流程如下：

如果 Thread Cache 的 freelist 为空：

如果 Central 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。

超过 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 中。这样的处理对减少内存碎片颇有帮助。