0. 概述
在曾经的一篇文章：malloc 和 free 的底层实现 中，我介绍过 GLibc 的 malloc 实现思路，但是，很多使用 C/C++ 的程序底层的动态内存管理都不用 Glibc 的 malloc 和 free，而是选择其他的 malloc 或者干脆自己实现。其中，Google 也是如此，因为它发现 Glibc 的 malloc 并不是那么适合自己的应用场景，于是就实现了自己的 TCMalloc，这里我就来学习一下关于 TCMalloc 的知识。
1. 概念
和 Glibc 的 malloc 一样，TCMalloc 也是有一些内部结构的，分别是：
- Page：8K 内存，可以被划分为多个小 Object
- Span：连续的 Page，可以包含不定数量的 Page（甚至一块）
- Central Heap：用于存放中型大小的块（256K ≤ size ≤ 1MB ）
2. 内存组织形式
在 TCMalloc 中，内存可能被逻辑上分为两部分，分别是 Thread Cache 和 Central Heap：
在物理上内存划分为小内存，中内存和大内存，划分的标准为：
- 小内存：size < 256K
- 中内存：256K ≤ size ≤ 1MB
- 大内存：size > 1MB
其中小内存会存在与 Thread Cache 和 Central Heap 中，并且在这中逻辑概念中的物理存放形式还不一样，在 Thread Local 中，存放是以 size 范围来存放的：
这里分为 88 个等级，小区间以 8 bytes 为间隔，然后大一点的空间以 16 bytes 为间隔，然后再大一点就 32 bytes，依此类推，类似于：
| class | 块大小 |
|---|---|
| 0 | 0-8 |
| 1 | 8-16 |
| … | .. |
| - | 961-1024 |
这样，需要一块内存的时候，直接上取整找对应的链表来分配。这是在 Thread Local 中的形式，对于在 Central Heap 中，就多了一层 Span，也就是说，每个级别的第一层的 Linked List 是 Span，然后对于 Span 内部还维护这一个小内存的 Linked List。
对于中型大小的内存，则只有在 Central Heap 中存在，他的组织形式是以 page 为单位，在 Central Heap 中有一个 128 长度的数组，每隔数组对应这 1.2.3…128 个 page 的内存块：
对于大内存，也是直接放在 Central Heap 中，是以红黑树的形式有序的存放。除此之外，TCMalloc 还在 Central Heap 中以 Radix Tree 的形式存放了 Page 的 Span 信息。
在 32位系统中，是两层结构，第一层是包含 32 个元素，然后第二层的每隔叶子节点包含 214 个元素，因为 32 位系统可以划分为 219 个 8K 内存，所以每个叶子的大小是 214，因此 TCMalloc 运行的时候 Central 就需要提前浪费掉 64 KB（214 * 4 byte）内存（why？没有很理解）。
如果在 64 位系统中，会采用 3 层的 Radix Tree。
3. 内存分配
当理解完 TCMaclloc 的内部内存存放之后，对于内存分配就比较简单了，对于小内存，分配的步骤为：
- 根据需要的内存大小，先确定分配的 class，然后从 Thread Local 中查找，如果有，那么就直接用
- 如果在 Thread Local 中没有合适的大小，那么就从 Central Heap 中对应的 class 链表中获取一部分过来，分配一个来用，其他放回 Thread Local 的链表
- 如果 Central Heap 中对应 class 的链表上也没有，那么就从 Central heap 中获取一些 Page，然后再划分为对应大小的 Object，先放到 Central Heap 中对应 class 的链表上，再给一部分 Thread Local
对于中块大小的内存，因为只在 Central Heap 中存放，那么获取起来就简单一些了：
- 根据需要的大小确定对应的 page 数，然后取对应 page 数的链表，如果有空闲的，直接拿来用
- 如果对应的 page 索引下没有空闲块了，那么就从下一个大小的 page 索引中获取
- 如果都没有空闲块了，那么就当作大内存来分配
那么大内存的分配策略又是如何：
- 先根据需要的内存大小，在红黑树（大内存的存储结构）中查找最接近需要内存的合适块，如果有，那么拿来用
- 如果大内存中都没有，那么就得从 OS 中分配一块了
如果大内存中找到的空闲块比实际需要的大，那么可以对大内存进行切分，切分出来的空闲块根据他的大小，放会到对应的（大内存/中型内存/小内存）存储结构中。这就是整个的分配策略。
4. 内存释放
有借有还，再借不难，既然分配了，那么还回来要怎么处理也是值得学习的。这里也要区分内存的大小，如果是小内存，那么就直接放回 Thread Local 的对应的 class 的链表中，如果 Thread Local 中的小内存数量超过一定限制（2 MB），那么就需要执行依次垃圾回收（下一级）了。
如果是中型内存，没有太复杂的操作，直接放到 Central Heap 对应的 page 索引的链表中，如果是大块内存（[p, q]，那么在放到 Central Heap 的红黑树中之前，还会确认一下前后的 page（p - 1 和 q + 1） 是否空闲，如果有空闲，那么先合并一波再放回 Central Heap 中。
5. 垃圾回收
当 Thread Local 中，小内存数量太多（超过 2MB）之后，TCMalloc 就会选取一些还给 Central Heap，选取的标准为每个 Thread Local 都有一个链表最短长度 L，超过 L 长度的内存都会还给 Central Heap，如果都不超过 L 且总内存还太大，那么就减小一半 L（L= L/2），再进行一遍。
当小内存从 Thread Local 还回去 Central Heap 中的 Span 中的链表之后，如果对应 Span 链表中的空闲数（链表长度）等于 Span 被划分的块数，那么这个 Span 就会被还回给对应的 Page 数组（因为它已经是空闲的了）。