共计 3843 个字符，预计需要花费 10 分钟才能阅读完成。
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 的详细信息，它包含：
- start 和 length：记录 Span 蕴含的 Page 范畴
- prev 和 next：Span 类型的指针，用于将 Span 连接成 Spanlist
- objects：记录 Span 决裂成的小内存块的链表
- span_iter_space：记录 Span 在 SpanSet（Page Heap 中的 Span 汇合）中的迭代器，不便 Span 从 SpanSet 中移除
- sizeclass 示意 Span 决裂成的小内存块的大小类型（0 示意没有决裂成小内存）
- refcount 示意 Span 决裂成的小内存块的援用计数，即调配给 Thread Cache 应用的 object 数量
- 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 形成的链表，并应用嵌入式指针连贯以进步内存利用率。
调配小内存的流程如下：
- 通过 Size Map 将其大小映射到相应的大小类型
- 在 Thread Cache 中查找该大小类型对应的 freelist
- 如果 freelist 不为空，咱们从列表中删除第一个 object 并返回它。因为线程内不存在内存的并发申请，这个过程无需取得任何锁
如果 Thread Cache 的 freelist 为空：
- 咱们从 Central Cache 中该大小类型的 freelist 即 Central freelist 上获取一堆 object（因为 Central Cache 由所有 Thread 持锁并发拜访，内存在 Thread Cache 和 Central Cache 之间传递时，每次传递 num_objects_to_move 个 object，以进步内存传递的效率）
- 将它们放在 Thread Cache 的 freelist 中
- 将新获取的 object 之一返回给申请者
如果 Central freelist 也是空的：
- 咱们以 Page 为单位从 Page Heap 调配一系列间断 Page（即一个 Span），具体的 Page 数是从 SizeMap 获取的该大小类型的 class_to_pages 值
- 将这些 Page 拆分为该大小类型的一组 object
- 将新的 object 放在 Central freelist 中
- 和以前一样，将其中一些 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 中。这样的解决对缩小内存碎片颇有帮忙。
