TCMalloc解密

By wallen

On 2018年11月22日

In C/C++

写在前面

本文首先简单介绍TCMalloc及其使用方法，然后解释TCMalloc替代系统的内存分配函数的原理，再从宏观上讨论其内存分配的策略，在此之后再深入讨论实现细节。

有几点需要说明：

本文只讨论gperftools中TCMalloc部分的代码，对应版本gperftools-2.7。
本文是根据TCMalloc源码以及简短的官方介绍作出的个人理解，难免有纰漏之处，且难以覆盖TCMalloc的方方面面，不足之处还请各位看官留言指正。
除非特别说明，以下讨论均以32位系统、TCMalloc默认page大小（8KB）为基础，不同架构或不同page大小，有些相关数值可能不一样，但基本原理是相似的。
为了控制篇幅，我会尽量少贴大段代码，只给出关键代码的位置或函数名，各位看官可自行参阅TCMalloc相关代码。

TCMalloc是什么

TCMalloc全称Thread-Caching Malloc，即线程缓存的malloc，实现了高效的多线程内存管理，用于替代系统的内存分配相关的函数（malloc、free，new，new[]等）。

TCMalloc是gperftools的一部分，除TCMalloc外，gperftools还包括heap-checker、heap-profiler和cpu-profiler。本文只讨论gperftools的TCMalloc部分。

git仓库：https://github.com/gperftools/gperftools.git

官方介绍：https://gperftools.github.io/gperftools/TCMalloc.html（里面有些内容已经过时了）

如何使用TCMalloc

安装

以下是比较常规的安装步骤，详细可参考gperftools中的INSTALL。

0. 从git仓库clone版本的gperftools的安装依赖autoconf、automake、libtool，以Debian为例：

# apt install autoconf automake libtool

1. 生成configure等一系列文件

   $ ./autogen.sh

2. 生成Makefile

   $ ./configure

3. 编译

   $ make

4. 安装

   # make install

默认安装在/usr/local/下的相关路径（bin、lib、share），可在configure时以--prefix=PATH指定其他路径。

64位Linux系统需要注意

在64位Linux环境下，gperftools使用glibc内置的stack-unwinder可能会引发死锁，因此官方推荐在配置和安装gperftools之前，先安装libunwind-0.99-beta，最好就用这个版本，版本太新或太旧都可能会有问题。

即便使用libunwind，在64位系统上还是会有问题，但只影响heap-checker、heap-profiler和cpu-profiler，TCMalloc不受影响，因此不再赘述，感兴趣的读者可参阅gperftools的INSTALL。

如果不希望安装libunwind，也可以用gperftools内置的stack unwinder，但需要应用程序、TCMalloc库、系统库（比如libc）在编译时开启帧指针（frame pointer）选项。

在x86-64下，编译时开启帧指针选项并不是默认行为。因此需要指定-fno-omit-frame-pointer编译所有应用程序，然后在configure时通过--enable-frame-pointers选项使用内置的gperftools stack unwinder。

使用

以动态库的方式

安装之后，通过-ltcmalloc或-ltcmalloc_minimal将TCMalloc链接到应用程序即可。

#include <stdlib.h>

int main( int argc, char *argv[] )
{   
    malloc(1);
}

$ g++ -O0 -g -ltcmalloc test.cc && gdb a.out

(gdb) b test.cc:5
Breakpoint 1 at 0x7af: file test.cc, line 5.
(gdb) r
Starting program: /home/wanglong/test/tcmalloc/a.out 
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".

Breakpoint 1, main (argc=1, argv=0x7fffffffddd8) at test.cc:5
5           malloc(1);
(gdb) s
tc_malloc (size=1) at src/tcmalloc.cc:1892
1892      return malloc_fast_path<tcmalloc::malloc_oom>(size);
(gdb)

通过gdb断点可以看到对malloc()的调用已经替换为TCMalloc的实现。

以静态库的方式

gperftools的README中说静态库应该使用libtcmalloc_and_profiler.a库而不是libprofiler.a和libtcmalloc.a，但简单测试后者也是OK的，而且在实际项目中也是用的后者，不知道是不是文档太过老旧了。

$ g++ -O0 -g -pthread test.cc /usr/local/lib/libtcmalloc_and_profiler.a

如果使用了libunwind，需要指定-Wl,--eh-frame-hdr选项，以确保libunwind可以找到编译器生成的信息来进行栈回溯。

eh-frame（exception handling frame）参考资料：

TCMalloc是如何生效的

为什么指定-ltcmalloc或者与libtcmalloc_and_profiler.a连接之后，对malloc、free、new、delete等的调用就由默认的libc中的函数调用变为TCMalloc中相应的函数调用了呢？答案在libc_override.h中，下面只讨论常见的两种情况：使用了glibc，或者使用了GCC编译器。其余情况可自行查看相应的libc_override头文件。

使用glibc（但没有使用GCC编译器）

在glibc中，内存分配相关的函数都是弱符号（weak symbol），因此TCMalloc只需要定义自己的函数将其覆盖即可，以malloc和free为例：

libc_override_redefine.h

extern "C" { 
  void* malloc(size_t s)                         { return tc_malloc(s); }
  void  free(void* p)                            { tc_free(p);          }
}  // extern "C"

可以看到，TCMalloc将malloc()和free()分别定义为对tc_malloc()和tc_free()的调用，并在tc_malloc()和tc_free()中实现具体的内存分配和回收逻辑。

new和delete也类似：

void* operator new(size_t size)                  { return tc_new(size); }
void operator delete(void* p) CPP_NOTHROW        { tc_delete(p);        }

使用GCC编译器

如果使用了GCC编译器，则使用其支持的函数属性：alias。

libc_override_gcc_and_weak.h：

#define ALIAS(tc_fn)   __attribute__ ((alias (#tc_fn), used))

extern "C" { 
  void* malloc(size_t size) __THROW               ALIAS(tc_malloc);
  void free(void* ptr) __THROW                    ALIAS(tc_free);
}   // extern "C"

将宏展开，__attribute__ ((alias ("tc_malloc"), used))表明tc_malloc是malloc的别名。

具体可参阅GCC相关文档：

alias ("target")
The alias attribute causes the declaration to be emitted as an alias for another symbol, which must be specified. For instance,
void __f () { /* Do something. */; }
void f () __attribute__ ((weak, alias ("__f")));
defines f to be a weak alias for __f. In C++, the mangled name for the target must be used. It is an error if __f is not defined in the same translation unit.
Not all target machines support this attribute.
used
This attribute, attached to a function, means that code must be emitted for the function even if it appears that the function is not referenced. This is useful, for example, when the function is referenced only in inline assembly.
When applied to a member function of a C++ class template, the attribute also means that the function will be instantiated if the class itself is instantiated.

TCMalloc的初始化

何时初始化

TCMalloc定义了一个类TCMallocGuard，并在文件tcmalloc.cc中定义了该类型的静态变量module_enter_exit_hook，在其构造函数中执行TCMalloc的初始化逻辑，以确保TCMalloc在main()函数之前完成初始化，防止在初始化之前就有多个线程。

tcmalloc.cc：

static TCMallocGuard module_enter_exit_hook;

如果需要确保TCMalloc在某些全局构造函数运行之前就初始化完成，则需要在文件顶部创建一个静态TCMallocGuard实例。

如何初始化

TCMallocGuard的构造函数实现：

static int tcmallocguard_refcount = 0;  // no lock needed: runs before main()
TCMallocGuard::TCMallocGuard() {
  if (tcmallocguard_refcount++ == 0) {
    ReplaceSystemAlloc();    // defined in libc_override_*.h
    tc_free(tc_malloc(1));
    ThreadCache::InitTSD();
    tc_free(tc_malloc(1));
    // Either we, or debugallocation.cc, or valgrind will control memory
    // management.  We register our extension if we're the winner.
#ifdef TCMALLOC_USING_DEBUGALLOCATION
    // Let debugallocation register its extension.
#else
    if (RunningOnValgrind()) {
      // Let Valgrind uses its own malloc (so don't register our extension).
    } else {
      MallocExtension::Register(new TCMallocImplementation);
    }
#endif
  }
}

可以看到，TCMalloc初始化的方式是调用tc_malloc()申请一字节内存并随后调用tc_free()将其释放。至于为什么在InitTSD前后各申请释放一次，不太清楚，猜测是为了测试在TSD（Thread Specific Data，详见后文）初始化之前也能正常工作。

初始化内容

那么TCMalloc在初始化时都执行了哪些操作呢？这里先简单列一下，后续讨论TCMalloc的实现细节时再逐一详细讨论：

初始化SizeMap（Size Class）
初始化各种Allocator
初始化CentralCache
创建PageHeap

总之一句话，创建TCMalloc自身的一些元数据，比如划分小对象的大小等等。

TCMalloc的内存分配算法概览

TCMalloc的官方介绍中将内存分配称为Object Allocation，本文也沿用这种叫法，并将object翻译为对象，可以将其理解为具有一定大小的内存。

按照所分配内存的大小，TCMalloc将内存分配分为三类：

小对象分配，(0, 256KB]
中对象分配，(256KB, 1MB]
大对象分配，(1MB, +∞)

简要介绍几个概念，Page，Span，PageHeap：

与操作系统管理内存的方式类似，TCMalloc将整个虚拟内存空间划分为n个同等大小的Page，每个page默认8KB。又将连续的n个page称为一个Span。

TCMalloc定义了PageHeap类来处理向OS申请内存相关的操作，并提供了一层缓存。可以认为，PageHeap就是整个可供应用程序动态分配的内存的抽象。

PageHeap以span为单位向系统申请内存，申请到的span可能只有一个page，也可能包含n个page。可能会被划分为一系列的小对象，供小对象分配使用，也可能当做一整块当做中对象或大对象分配。

小对象分配

Size Class

对于256KB以内的小对象分配，TCMalloc按大小划分了85个类别（官方介绍中说是88个左右，但我个人实际测试是85个，不包括0字节大小），称为Size Class，每个size class都对应一个大小，比如8字节，16字节，32字节。应用程序申请内存时，TCMalloc会首先将所申请的内存大小向上取整到size class的大小，比如1~8字节之间的内存申请都会分配8字节，9~16字节之间都会分配16字节，以此类推。因此这里会产生内部碎片。TCMalloc将这里的内部碎片控制在12.5%以内，具体的做法在讨论size class的实现细节时再详细分析。

ThreadCache

对于每个线程，TCMalloc都为其保存了一份单独的缓存，称之为ThreadCache，这也是TCMalloc名字的由来（Thread-Caching Malloc）。每个ThreadCache中对于每个size class都有一个单独的FreeList，缓存了n个还未被应用程序使用的空闲对象。

小对象的分配直接从ThreadCache的FreeList中返回一个空闲对象，相应的，小对象的回收也是将其重新放回ThreadCache中对应的FreeList中。

由于每线程一个ThreadCache，因此从ThreadCache中取用或回收内存是不需要加锁的，速度很快。

为了方便统计数据，各线程的ThreadCache连接成一个双向链表。ThreadCache的结构示大致如下：

CentralCache

那么ThreadCache中的空闲对象从何而来呢？答案是CentralCache——一个所有线程公用的缓存。

与ThreadCache类似，CentralCache中对于每个size class也都有一个单独的链表来缓存空闲对象，称之为CentralFreeList，供各线程的ThreadCache从中取用空闲对象。

由于是所有线程公用的，因此从CentralCache中取用或回收对象，是需要加锁的。为了平摊锁操作的开销，ThreadCache一般从CentralCache中一次性取用或回收多个空闲对象。

CentralCache在TCMalloc中并不是一个类，只是一个逻辑上的概念，其本质是CentralFreeList类型的数组。后文会详细讨论CentralCache的内部结构，现在暂且认为CentralCache的简化结构如下：

PageHeap

CentralCache中的空闲对象又是从何而来呢？答案是之前提到的PageHeap——TCMalloc对可动态分配的内存的抽象。

当CentralCache中的空闲对象不够用时，CentralCache会向PageHeap申请一块内存（可能来自PageHeap的缓存，也可能向系统申请新的内存），并将其拆分成一系列空闲对象，添加到对应size class的CentralFreeList中。

PageHeap内部根据内存块（span）的大小采取了两种不同的缓存策略。128个page以内的span，每个大小都用一个链表来缓存，超过128个page的span，存储于一个有序set（std::set）。讨论TCMalloc的实现细节时再具体分析，现在可以认为PageHeap的简化结构如下：

内存回收

上面说的都是内存分配，内存回收的情况是怎样的？

应用程序调用free()或delete一个小对象时，仅仅是将其插入到ThreadCache中其size class对应的FreeList中而已，不需要加锁，因此速度也是非常快的。

只有当满足一定的条件时，ThreadCache中的空闲对象才会重新放回CentralCache中，以供其他线程取用。同样的，当满足一定条件时，CentralCache中的空闲对象也会还给PageHeap，PageHeap再还给系统。

内存在这些组件之间的移动会在后文详细讨论，现在先忽略这些细节。

小结

总结一下，小对象分配流程大致如下：

将要分配的内存大小映射到对应的size class。
查看ThreadCache中该size class对应的FreeList。
如果FreeList非空，则移除FreeList的第一个空闲对象并将其返回，分配结束。
如果FreeList是空的：
- 从CentralCache中size class对应的CentralFreeList获取一堆空闲对象。
  - 如果CentralFreeList也是空的，则：
    - 向PageHeap申请一个span。
    - 拆分成size class对应大小的空闲对象，放入CentralFreeList中。
- 将这堆对象放置到ThreadCache中size class对应的FreeList中（第一个对象除外）。
- 返回从CentralCache获取的第一个对象，分配结束。

中对象分配

超过256KB但不超过1MB（128个page）的内存分配被认为是中对象分配，采取了与小对象不同的分配策略。

首先，TCMalloc会将应用程序所要申请的内存大小向上取整到整数个page（因此，这里会产生1B~8KB的内部碎片）。之后的操作表面上非常简单，向PageHeap申请一个指定page数量的span并返回其起始地址即可：

Span* span = Static::pageheap()->New(num_pages);
result = (PREDICT_FALSE(span == NULL) ? NULL : SpanToMallocResult(span));
return result;

问题在于，PageHeap是如何管理这些span的？即PageHeap::New()是如何实现的。

前文说到，PageHeap提供了一层缓存，因此PageHeap::New()并非每次都向系统申请内存，也可能直接从缓存中分配。

对128个page以内的span和超过128个page的span，PageHeap采取的缓存策略不一样。为了描述方便，以下将128个page以内的span称为小span，大于128个page的span称为大span。

先来看小span是如何管理的，大span的管理放在大对象分配一节介绍。

PageHeap中有128个小span的链表，分别对应1~128个page的span：

假设要分配一块内存，其大小经过向上取整之后对应k个page，因此需要从PageHeap取一个大小为k个page的span，过程如下：

从k个page的span链表开始，到128个page的span链表，按顺序找到第一个非空链表。
取出这个非空链表中的一个span，假设有n个page，将这个span拆分成两个span：
- 一个span大小为k个page，作为分配结果返回。
- 另一个span大小为n - k个page，重新插入到n - k个page的span链表中。
如果找不到非空链表，则将这次分配看做是大对象分配，分配过程详见下文。

大对象分配

超过1MB（128个page）的内存分配被认为是大对象分配，与中对象分配类似，也是先将所要分配的内存大小向上取整到整数个page，假设是k个page，然后向PageHeap申请一个k个page大小的span。

对于中对象的分配，如果上述的span链表无法满足，也会被当做是大对象来处理。也就是说，TCMalloc在源码层面其实并没有区分中对象和大对象，只是对于不同大小的span的缓存方式不一样罢了。

大对象分配用到的span都是超过128个page的span，其缓存方式不是链表，而是一个按span大小排序的有序set（std::set），以便按大小进行搜索。

假设要分配一块超过1MB的内存，其大小经过向上取整之后对应k个page（k>128），或者是要分配一块1MB以内的内存，但无法由中对象分配逻辑来满足，此时k <= 128。不管哪种情况，都是要从PageHeap的span set中取一个大小为k个page的span，其过程如下：

搜索set，找到不小于k个page的最小的span（best-fit），假设该span有n个page。
将这个span拆分为两个span：
- 一个span大小为k个page，作为结果返回。
- 另一个span大小为n - k个page，如果n - k > 128，则将其插入到大span的set中，否则，将其插入到对应的小span链表中。
如果找不到合适的span，则使用sbrk或mmap向系统申请新的内存以生成新的span，并重新执行中对象或大对象的分配算法。

小结

以上讨论忽略了很多实现上的细节，比如PageHeap对span的管理还区分了normal状态的span和returned状态的span，接下来会详细分析这些细节。

在此之前，画张图概括下TCMalloc的管理内存的策略：

可以看到，不超过256KB的小对象分配，在应用程序和内存之间其实有三层缓存：PageHeap、CentralCache、ThreadCache。而中对象和大对象分配，则只有PageHeap一层缓存。

TCMalloc的实现细节

算法概览一节涉及到了很多概念，比如Page，Span，Size Class，PageHeap，ThreadCache等，但只是粗略的一提，本节将详细讨论这些概念所涉及的实现细节。

Page

Page是TCMalloc管理内存的基本单位（这里的page要区分于操作系统管理虚拟内存的page），page的默认大小为8KB，可在configure时通过选项调整为32KB或64KB。

./configure <other flags> --with-tcmalloc-pagesize=32 (or 64)

page越大，TCMalloc的速度相对越快，但其占用的内存也会越高。简单说，就是空间换时间的道理。默认的page大小通过减少内存碎片来最小化内存使用，但跟踪这些page会花费更多的时间。使用更大的page则会带来更多的内存碎片，但速度上会有所提升。官方文档给出的数据是在某些google应用上有3%~5%的速度提升。

PageID

TCMalloc并非只将堆内存看做是一个个的page，而是将整个虚拟内存空间都看做是page的集合。从内存地址0x0开始，每个page对应一个递增的PageID，如下图（以32位系统为例）：

对于任意内存地址ptr，都可通过简单的移位操作来计算其所在page的PageID：

static const size_t kPageShift  = 13; // page大小：1 << 13 = 8KB
const PageID p = reinterpret_cast<uintptr_t>(ptr) >> kPageShift;

即，ptr所属page的PageID为ptr / page_size。

Span

一个或多个连续的Page组成一个Span（a contiguous run of pages）。TCMalloc以Span为单位向系统申请内存。

如图，第一个span包含2个page，第二个和第四个span包含3个page，第三个span包含5个page。

一个span记录了起始page的PageID（start），以及所包含page的数量（length）。

一个span要么被拆分成多个相同size class的小对象用于小对象分配，要么作为一个整体用于中对象或大对象分配。当作用作小对象分配时，span的sizeclass成员变量记录了其对应的size class。

span中还包含两个Span类型的指针（prev, next），用于将多个span以链表的形式存储。

span的三种状态

一个span处于以下三种状态中的一种：

IN_USE
ON_NORMAL_FREELIST
ON_RETURNED_FREELIST

IN_USE比较好理解，正在使用中的意思，要么被拆分成小对象分配给CentralCache或者ThreadCache了，要么已经分配给应用程序了。因为span是由PageHeap来管理的，因此即使只是分配给了CentralCache，还没有被应用程序所申请，在PageHeap看来，也是IN_USE了。

ON_NORMAL_FREELIST和ON_RETURNED_FREELIST都可以认为是空闲状态，区别在于，ON_RETURNED_FREELIST是指span对应的内存已经被PageHeap释放给系统了（在Linux中，对于MAP_PRIVATE|MAP_ANONYMOUS的内存使用madvise来实现）。需要注意的是，即使归还给系统，其虚拟内存地址依然是可访问的，只是对这些内存的修改丢失了而已，在下一次访问时会导致page fault以用0来重新初始化。

空闲对象链表

被拆分成多个小对象的span还包含了一个记录空闲对象的链表objects，由CentralFreeList来维护。

对于新创建的span，将其对应的内存按size class的大小均分成若干小对象，在每一个小对象的起始位置处存储下一个小对象的地址，首首相连：

但当span中的小对象经过一系列申请和回收之后，其顺序就不确定了：

可以看到，有些小对象已经不再空闲对象链表objects中了，链表中的元素顺序也已经被打乱。

空闲对象链表中的元素乱序没什么影响，因为只有当一个span的所有小对象都被释放之后，CentralFreeList才会将其还给PageHeap。

PageMap

PageMap之前没有提到过，它主要用于解决这么一个问题：给定一个page，如何确定这个page属于哪个span？

即，PageMap缓存了PageID到Span的对应关系。

32位系统、x86-64、arm64使用两级PageMap，以32位系统为例：

在root_数组中包含512个指向Leaf的指针，每个Leaf又是1024个void*的数组，数组索引为PageID，数组元素为page所属Span的指针。一共$2^{19}$个数组元素，对应32位系统的$2^{19}$个page。

使用两级map可以减少TCMalloc元数据的内存占用，因为初始只会给第一层（即root_数组）分配内存（2KB），第二层只有在实际用到时才会实际分配内存。而如果初始就给$2^{19}$个page都分配内存的话，则会占用$2^{19} * 4 bytes = 2MB$的内存。

Size Class

TCMalloc将每个小对象的大小（1B~256KB）分为85个类别（官方介绍中说是88个左右，但我个人实际测试是85个，不包括0字节大小），称之为Size Class，每个size class一个编号，从0开始递增（实际编号为0的size class是对应0字节，是没有实际意义的）。

举个例子，896字节对应编号为30的size class，下一个size class 31大小为1024字节，那么897字节到1024字节之间所有的分配都会向上舍入到1024字节。

SizeMap::Init()实现了对size class的划分，规则如下：

划分跨度

16字节以内，每8字节划分一个size class。
- 满足这种情况的size class只有两个：8字节、16字节。
16~128字节，每16字节划分一个size class。
- 满足这种情况的size class有7个：32, 48, 64, 80, 96, 112, 128字节。
128B~256KB，按照每次步进(size / 8)字节的长度划分，并且步长需要向下对齐到2的整数次幂，比如：
- 144字节：128 + 128 / 8 = 128 + 16 = 144
- 160字节：144 + 144 / 8 = 144 + 18 = 144 + 16 = 160
- 176字节：160 + 160 / 8 = 160 + 20 = 160 + 16 = 176
- 以此类推

一次移动多个空闲对象

ThreadCache会从CentralCache中获取空闲对象，也会将超出限制的空闲对象放回CentralCache。ThreadCache和CentralCache之间的对象移动是批量进行的，即一次移动多个空闲对象。CentralCache由于是所有线程公用，因此对其进行操作时需要加锁，一次移动多个对象可以均摊锁操作的开销，提升效率。

那么一次批量移动多少呢？每次移动64KB大小的内存，即因size class而异，但至少2个，至多32个（可通过环境变量TCMALLOC_TRANSFER_NUM_OBJ调整）。

移动数量的计算也是在size class初始化的过程中计算得出的。

一次申请多个page

对于每个size class，TCMalloc向系统申请内存时一次性申请n个page（一个span），然后均分成多个小对象进行缓存，以此来均摊系统调用的开销。

不同的size class对应的page数量是不同的，如何决定n的大小呢？从1个page开始递增，一直到均分成若干小对象后所剩的空间小于span总大小的1/8为止，因此，浪费的内存被控制在12.5%以内。这是TCMalloc减少内部碎片的一种措施。

另外，所分配的page数量还需满足一次移动多个空闲对象的数量要求（源码中的注释是这样说的，不过实际代码是满足1/4即可，原因不明）。

合并操作

在上述规则之上，还有一个合并操作：TCMalloc会将相同page数量，相同对象数量的相邻的size class合并为一个size class。比如：

第30个size class的对象大小是832字节，page数量为1个，因此包含8192 / 832 = 9个小对象。

第31个size class对应的page数量（1个）和对象数量（9个）跟第30个size class完全一样，因此第30个size class和第31个size class合并，所以第30个size class对应的对象大小为896字节。

下一个size class对应的对象大小为1024字节，page数量为1个，因此对象数量是8个，跟第30个size class的对象数量不一样，无法合并。

最终，第30个size class对应的对象大小为896字节。

记录映射关系

由以上划分规则可以看到，一个size class对应：

一个对象大小
一个申请page的数量
一个批量移动对象的数量

TCMalloc将size class与这些信息的映射关系分别记录在三个以size class的编号为索引的数组中（class_to_size_，num_objects_to_move_， class_to_pages_）。

还有一项非常重要的映射关系：小对象大小到size class编号的映射。TCMalloc将其记录在一个一维数组class_array_中。

256KB以内都是小对象，而size class的编号用一个字节就可以表示，因此存储小对象大小对应的size class编号需要256K个unsigned char，即256KB的内存。但由于size class之间是有间隔的（1024字节以内间隔至少8字节，1024以上间隔至少128字节），因此可以通过简单的计算对class_array_的索引进行压缩，以减少内存占用。

给定大小s，其对应的class_array_索引计算方式如下：

// s <= 1024
static inline size_t SmallSizeClass(size_t s) {
  return (static_cast<uint32_t>(s) + 7) >> 3;
}

// s > 1024
static inline size_t LargeSizeClass(size_t s) {
  return (static_cast<uint32_t>(s) + 127 + (120 << 7)) >> 7;
}

当s = 256KB时，计算结果即为class_array_的最大索引2169，因此数组的大小为2170字节。

计算任意内存地址对应的对象大小

当应用程序调用free()或delete释放内存时，需要有一种方式获取所要释放的内存地址对应的内存大小。结合前文所述的各种映射关系，在TCMalloc中按照以下顺序计算任意内存地址对应的对象大小：

计算给定地址计所在的PageID（ptr >> 13）
从PageMap中查询该page所在的span
span中记录了size class编号
根据size class编号从class_to_size_数组中查询对应的对象大小

这样做的好处是：不需要在内存块的头部记录内存大小，减少内存的浪费。

小结

size class的实现中有很多省空间省时间的做法：

省空间
控制划分跨度的最大值（8KB），减少内部碎片
控制一次申请page的数量，减少内部碎片
通过计算和一系列元数据记录内存地址到内存大小的映射关系，避免在实际分配的内存块中记录内存大小，减少内存浪费
两级PageMap或三级PageMap
压缩class_array_
省时间
一次申请多个page
一次移动多个空闲对象

PageHeap

前面介绍的都是TCMalloc如何对内存进行划分，接下来看TCMalloc如何管理如此划分后的内存，这是PageHeap的主要职责。

TCMalloc源码中对PageHeap的注释：

// -------------------------------------------------------------------------
// Page-level allocator
//  * Eager coalescing
//
// Heap for page-level allocation.  We allow allocating and freeing a
// contiguous runs of pages (called a "span").
// -------------------------------------------------------------------------

空闲Span管理器

如前所述，128page以内的span称为小span，128page以上的span称为大span。PageHeap对于这两种span采取了不同的管理策略。小span用链表，而且每个大小的span都用一个单独的链表来管理。大span用std::set。

前文没有提到的是，从另一个维度来看，PageHeap是分开管理ON_NORMAL_FREELIST和ON_RETURNED_FREELIST状态的span的。因此，每个小span对应两个链表，所有大span对应两个set。

// We segregate spans of a given size into two circular linked
// lists: one for normal spans, and one for spans whose memory
// has been returned to the system.
struct SpanList {
  Span        normal;
  Span        returned;
};

// Array mapping from span length to a doubly linked list of free spans
//
// NOTE: index 'i' stores spans of length 'i + 1'.
SpanList free_[kMaxPages];    // 128

typedef std::set<SpanPtrWithLength, SpanBestFitLess, STLPageHeapAllocator<SpanPtrWithLength, void> > SpanSet;

// Sets of spans with length > kMaxPages.
//
// Rather than using a linked list, we use sets here for efficient
// best-fit search.
SpanSet large_normal_;
SpanSet large_returned_;

因此，实际的PageHeap是这样的：

Heap段的使用限制

可以通过FLAGS_tcmalloc_heap_limit_mb对进程heap段的内存使用量进行限制，默认值0表示不做限制。如果开启了限制并且对heap段内存的使用量接近这个限制时，TCMalloc会更积极的将空闲内存释放给系统，进而会引发更多的软分页错误（minor page fault）。

为了简化讨论，后文均假设没有对heap段的内存使用做任何限制。

创建Span

// Allocate a run of "n" pages.  Returns zero if out of memory.
// Caller should not pass "n == 0" -- instead, n should have
// been rounded up already.
Span* New(Length n);

创建span的过程其实就是分配中对象和大对象的过程，假设要创建k个page大小的span（以下简称大小为k的span），过程如下：

搜索空闲span

Span* SearchFreeAndLargeLists(Length n);

1. 搜索空闲span链表，按照以下顺序，找出第一个不小于k的span：

从大小为k的span的链表开始依次搜索
对于某个大小的span，先搜normal链表，再搜returned链表

2. 如果span链表中没找到合适的span，则搜索存储大span的set：

从大小为k的span开始搜索
同样先搜normal再搜returned
优先使用长度最小并且起始地址最小的span（best-fit）

3. 如果通过以上两步找到了一个大小为m的span，则将其拆成两个span：

大小为m - k的span重新根据大小和状态放回链表或set中
大小为k的span作为结果返回，创建span结束

4. 如果没搜到合适的span，则继续后面的步骤：向系统申请内存。

小插曲：释放所有空闲内存

ReleaseAtLeastNPages(static_cast<Length>(0x7fffffff));

当没有可用的空闲span时，需要向系统申请新的内存，但在此之前，还有一次避免向系统申请新内存的机会：释放所有空闲内存。向系统申请的内存每达到128MB，且空闲内存超过从系统申请的总内存的1/4，就需要将所有的空闲内存释放。

因为TCMalloc将normal和returned的内存分开管理，而这两种内存不会合并在一起。因此，可能有一段连续的空闲内存符合要求（k个page大小），但因为它既有normal的部分，又有returned的部分，因此前面的搜索规则搜不到它。而释放所有内存可以将normal的内存也变为returned的，然后就可以合并了（合并规则详细后文合并span）。

之所以控制在每128MB一次的频率，是为了避免高频小量申请内存的程序遭受太多的minor page fault。

释放完毕后，会按照前面的搜索规则再次尝试搜索空闲span，如果还搜不到，才继续后续的步骤。

向系统申请内存

bool GrowHeap(Length n);

找不到合适的空闲span，就只能向系统申请新的内存了。

TCMalloc以sbrk()和mmap()两种方式向系统申请内存，所申请内存的大小和位置均按page对齐，优先使用sbrk()，申请失败则会尝试使用mmap()（64位系统Debug模式优先使用mmap，原因详见InitSystemAllocators()注释）。

TCMalloc向系统申请应用程序所使用的内存时，每次至少尝试申请1MB（kMinSystemAlloc），申请TCMalloc自身元数据所使用的内存时，每次至少申请8MB（kMetadataAllocChunkSize）。这样做有两点好处：

减少外部内存碎片（减少所申请内存与TCMalloc元数据所占内存的交替）
均摊系统调用的开销，提升性能

另外，当从系统申请的总内存超过128MB时就为PageMap一次性申请一大块内存，保证可以存储所有page和span的对应关系。这一举措可以减少TCMalloc的元数据将内存分块而导致的外部碎片。从源码中可以发现，仅在32位系统下才会这样做，可能是因为64位系统内存的理论上限太大，不太现实。

// bool PageHeap::GrowHeap(Length n);
if (old_system_bytes < kPageMapBigAllocationThreshold
    && stats_.system_bytes >= kPageMapBigAllocationThreshold) {
  pagemap_.PreallocateMoreMemory();
}

sbrk

先来看如何使用sbrk()从Heap段申请内存，下图展示了SbrkSysAllocator::Alloc()的执行流程，为了说明外部碎片的产生，并覆盖到SbrkSysAllocator::Alloc()的大部分流程，假设page大小为8KB，所申请的内存大小为16KB：

假设在申请内存之前，pb（program break，可以认为是堆内存的上边界）指向红色箭头所示位置，即没有在page的边界处。
第一次sbrk申请16KB内存，因此pb移至绿色箭头所示位置。
由于需要对申请的内存按page对齐，因此需要第二次sbrk，pb指向蓝色箭头所示位置，page的边界处。
最终，返回的内存地址为黑色箭头所示位置，黑色和蓝色箭头之间刚好16KB。

可以看出，红色箭头和黑色箭头之间的内存就无法被使用了，产生了外部碎片。

mmap

如果使用sbrk申请内存失败，TCMalloc会尝试使用mmap来分配。同样，为了覆盖MmapSysAllocator::Alloc()的大部分情况，下图假设系统的page为4KB，TCMalloc的page为16KB，申请的内存大小为32KB：

假设在申请内存之前，mmap段的边界位于红色箭头所示位置。
第一次mmap，会在32KB的基础上，多申请(对齐大小 - 系统page大小) = 16 -4 = 12KB的内存。此时mmap的边界位于绿色箭头所示位置。
然后通过两次munmap将所申请内存的两侧边界分别对齐到TCMalloc的page边界。
最终申请到的内存为两个蓝色箭头之间的部分，返回左侧蓝色箭头所指示的内存地址。

如果申请内存成功，则创建一个新的span并立即删除，可将其放入空闲span的链表或set中，然后继续后面的步骤。

最后的搜索

最后，重新搜索一次空闲span，如果还找不到合适的空闲span，那就认为是创建失败了。

至此，创建span的操作结束。

删除Span

// Delete the span "[p, p+n-1]".
// REQUIRES: span was returned by earlier call to New() and
//           has not yet been deleted.
void Delete(Span* span);

当span所拆分成的小对象全部被应用程序释放变为空闲对象，或者作为中对象或大对象使用的span被应用程序释放时，需要将span删除。不过并不是真正的删除，而是放到空闲span的链表或set中。

删除的操作非常简单，但可能会触发合并span的操作，以及释放内存到系统的操作。

合并Span

当span被delete时，会尝试向前向后合并一个span。

合并规则如下：

只有在虚拟内存空间上连续的span才可以被合并。
只有同是normal状态的span或同是returned状态的span才可以被合并。

上图中，被删除的span的前一个span是normal状态，因此可以与之合并，而后一个span是returned状态，无法与之合并。合并操作之后如下图：

还有一个值得注意的开关：aggressive_decommit_，开启后TCMalloc会积极的释放内存给系统，默认是关闭状态，可通过以下方式更改：

MallocExtension::instance()->SetNumericProperty("tcmalloc.aggressive_memory_decommit", value)

当开启了aggressive_decommit_后，删除normal状态的span时会尝试将其释放给系统，释放成功则状态变为returned。

在合并时，如果被删除的span此时是returned状态，则会将与其相邻的normal状态的span也释放给系统，然后再尝试合并。

因此，上面的例子中，被删除的span和其前一个span都会被更改为returned状态，合并之后如下，即三个span被合并成为一个span：

释放span

Length ReleaseAtLeastNPages(Length num_pages);

在delete一个span时还会以一定的频率触发释放span的内存给系统的操作（ReleaseAtLeastNPages()）。释放的频率可以通过环境变量TCMALLOC_RELEASE_RATE来修改。默认值为1，表示每删除1000个page就尝试释放至少1个page，2表示每删除500个page尝试释放至少1个page，依次类推，10表示每删除100个page尝试释放至少1个page。0表示永远不释放，值越大表示释放的越快，合理的取值区间为[0, 10]。

释放规则：

从小到大循环，按顺序释放空闲span，直到释放的page数量满足需求。
多次调用会从上一次循环结束的位置继续循环，而不会重新从头（1 page）开始。
释放的过程中能合并span就合并span
可能释放少于num_pages，没那么多free的span了。
可能释放多于num_pages，还差一点就够num_pages了，但刚好碰到一个很大的span。

释放方式：

如果系统支持，通过madvise(MADV_DONTNEED)释放span对应的内存。因此，即使释放成功，对应的虚拟内存地址空间仍然可访问，但内存的内容会丢失，在下次访问时会导致minor page fault以用0来重新初始化。

ThreadCache

TCMalloc分配小对象的速度是非常快的，这得益于其对每个线程都有一份单独的cache，即ThreadCache。

ThreadCache其实就是一组FreeList而已。对于每个size class，在ThreadCache中都有一个FreeList，缓存了一组空闲对象，应用程序申请256KB以内的小内存时，优先返回FreeList中的一个空闲对象。因为每个线程每个size class都有单独的FreeList，因此这个过程是不需要加锁的，速度非常快。

如果FreeList为空，TCMalloc才会从size class对应的CentralFreeList中获取一组空闲对象放入ThreadCache的FreeList中，并将其中一个对象返回。从CentralFreeList中获取空闲对象需要加锁的。

回顾下ThreadCache的结构：

各个线程的ThreadCache互相连接成为一个双向链表，主要目的是为了方便统计信息。

每线程Cache

那么每个线程一个ThreadCache是如何实现的呢？

这依赖于两种技术：Thread Local Storage（TLS)，和Thread Specific Data（TSD）。两者的功能基本是一样的，都是提供每线程存储。TLS用起来更方便，读取数据更快，但在线程销毁时TLS无法执行清理操作，而TSD可以，因此TCMalloc使用TSD为每个线程提供一个ThreadCache，如果TLS可用，则同时使用TLS保存一份拷贝以加速数据的访问。

TLS和TSD的具体细节可参考《The Linux Programming Interface》相关章节（31.3，31.4），本文不再展开讨论。

详细可参考源码中ThreadCache::CreateCacheIfNecessary()函数和threadlocal_data_变量相关代码。

何时创建ThreadCache

当某线程第一次申请分配内存时，TCMalloc为该线程创建其专属的ThreadCache（ThreadCache::GetCache() -> ThreadCache::CreateCacheIfNecessary()）。

何时销毁ThreadCache

在TCMalloc初始化TSD时，会调用Pthreads API中的pthread_key_create()创建ThreadCache对应的key，并且指定了销毁ThreadCache的函数ThreadCache::DestroyThreadCache()。因此，当一个线程销毁时，其对应的ThreadCache会由该函数销毁。

ThreadCache的大小

TCMalloc定义了一些变量来建议ThreadCache的大小。注意，是建议，而非强制。也就是说，实际的大小可能会超过这些值。

所有线程的ThreadCache的总大小限制（overall_thread_cache_size_）默认为32MB（kDefaultOverallThreadCacheSize），取值范围512KB~1GB，可以通过环境变量TCMalloc_MAX_TOTAL_THREAD_CACHE_BYTES或以下方式来进行调整：

MallocExtension::instance()->SetNumericProperty("TCMalloc.max_total_thread_cache_bytes", value);

每个线程的ThreadCache的大小限制默认为4MB（kMaxThreadCacheSize）。调整ThreadCache总大小时，会修改每个ThreadCache的大小限制到512KB~4MB之间的相应值。

慢启动算法：FreeList的长度控制

控制ThreadCache中各个FreeList中元素的数量是很重要的：

太小：不够用，需要经常去CentralCache获取空闲对象，带锁操作
太大：太多对象在空闲列表中闲置，浪费内存

不仅是内存分配，对于内存释放来说控制FreeList的长度也很重要：

太小：需要经常将空闲对象移至CentralCache，带锁操作
太大：太多对象在空闲列表中闲置，浪费内存

并且，有些线程的分配和释放是不对称的，比如生产者线程和消费者线程，这也是需要考虑的一个点。

类似TCP的拥塞控制算法，TCMalloc采用了慢启动（slow start）的方式来控制FreeList的长度，其效果如下：

FreeList被使用的越频繁，最大长度就越大。
如果FreeList更多的用于释放而不是分配，则其最大长度将仅会增长到某一个点，以有效的将整个空闲对象链表一次性移动到CentralCache中。

分配内存时的慢启动代码如下（FetchFromCentralCache）：

const int batch_size = Static::sizemap()->num_objects_to_move(cl);

// Increase max length slowly up to batch_size.  After that,
// increase by batch_size in one shot so that the length is a
// multiple of batch_size.
if (list->max_length() < batch_size) {
  list->set_max_length(list->max_length() + 1);
} else { 
  // Don't let the list get too long.  In 32 bit builds, the length
  // is represented by a 16 bit int, so we need to watch out for
  // integer overflow.
  int new_length = min<int>(list->max_length() + batch_size,
                            kMaxDynamicFreeListLength);
  // The list's max_length must always be a multiple of batch_size,
  // and kMaxDynamicFreeListLength is not necessarily a multiple
  // of batch_size.
  new_length -= new_length % batch_size;
  ASSERT(new_length % batch_size == 0);
  list->set_max_length(new_length);
}

max_length即为FreeList的最大长度，初始值为1。batch_size是size class一节提到的一次性移动空闲对象的数量，其值因size class而异。

可以看到，只要max_length没有超过batch_size，每当FreeList中没有元素需要从CentralCache获取空闲对象时（即FetchFromCentralCache），max_length就加1。

一旦max_length达到batch_size，接下来每次FetchFromCentralCache就会导致max_length增加batch_size。

但并不会无限制的增加，最大到kMaxDynamicFreeListLength（8192），以避免从FreeList向CentralCache移动对象时，因为对象过多而过长的占用锁。

再来看内存回收时的情况，每次释放小对象，都会检查FreeList的当前长度是否超过max_length：

if (PREDICT_FALSE(length > list->max_length())) {
  ListTooLong(list, cl);
  return;
}

如果超长，则执行以下逻辑：

void ThreadCache::ListTooLong(FreeList* list, uint32 cl) {
  size_ += list->object_size();

  const int batch_size = Static::sizemap()->num_objects_to_move(cl);
  ReleaseToCentralCache(list, cl, batch_size);

  // If the list is too long, we need to transfer some number of
  // objects to the central cache.  Ideally, we would transfer
  // num_objects_to_move, so the code below tries to make max_length
  // converge on num_objects_to_move.

  if (list->max_length() < batch_size) {
    // Slow start the max_length so we don't overreserve.
    list->set_max_length(list->max_length() + 1);
  } else if (list->max_length() > batch_size) {
    // If we consistently go over max_length, shrink max_length.  If we don't
    // shrink it, some amount of memory will always stay in this freelist.
    list->set_length_overages(list->length_overages() + 1);
    if (list->length_overages() > kMaxOverages) {
      ASSERT(list->max_length() > batch_size);
      list->set_max_length(list->max_length() - batch_size);
      list->set_length_overages(0);
    }
  }

  if (PREDICT_FALSE(size_ > max_size_)) {
    Scavenge();
  }
}

与内存分配的情况类似，只要max_length还没有达到batch_size，每当FreeList的长度超过max_length，max_length的值就加1。

当max_length达到或超过batch_size后，并不会立即调整max_length，而是累计超过3次（kMaxOverages）后，才会将max_length减少batch_size。

垃圾回收

TODO：本节还没写完，请先参阅官方介绍Garbage Collection of Thread Caches一节。。

从ThreadCache中回收垃圾对象，将未使用的对象返回到CentralFreeList，可以控制缓存的大小。

不同线程对缓存大小的需求是不一样的，因此不能统一对待：有些线程需要大的缓存，有些线程需要小的缓存即可，甚至有些线程不需要缓存。

当一个ThreadCache大小超过其max_size_时，触发垃圾回收：

if (PREDICT_FALSE(size_ > max_size_)){
  Scavenge();
}

只有当应用程序释放内存时（ThreadCache::Deallocate()）才会触发垃圾回收，遍历ThreadCache中所有的FreeList，将FreeList中的一些对象移至对应的CentralFreeList中。

具体移动多少对象由低水位标记L（lowater_，每个FreeList一个）来决定。L记录自上次垃圾收集以来，FreeList的最小长度。

CentralCache

CentralCache是逻辑上的概念，其本质是CentralFreeListPadded类型（CentralFreeList的子类，用于64字节对齐）的数组，每个size class对应数组中的一个元素。

ATTRIBUTE_HIDDEN static CentralFreeListPadded central_cache_[kClassSizesMax];

由于各线程公用一个CentralCache，因此，使用CentralCache时需要加锁。

以下讨论都是针对某一个size class的。

CentralFreeList中缓存了一系列小对象，供各线程的ThreadCache取用，各线程也会将多余的空闲小对象还给CentralFreeList，另外CentralFreeList还负责从PageHeap申请span以分割成小对象，以及将不再使用的span还给PageHeap。

管理span

CentralFreeList真正管理的是span，而小对象是包含在span中的空闲对象链表中的。CentralFreeList的empty_链表保存了已经没有空闲对象可用的span，nonempty_链表保存了还有空闲对象可用的span：

CentralFreeList↔ PageHeap

从PageHeap获取span

当ThreadCache从CentralFreeList取用空闲对象（RemoveRange），但CentralFreeList的空闲对象数量不够时，CentralFreeList调用Populate()从PageHeap申请一个span拆分成若干小对象，首首连接记录在span的objects指针中，即每个小对象的起始位置处，记录了下一个小对象的地址。此时的span如下图：

可以看到，此时span包含的对象按顺序连接在一起。

新申请的span被放入CentralFreeList的nonempty_链表头部。

将span还给PageHeap

CentralFreeList维护span的成员变量refcount，用来记录ThreadCache从中获取了多少对象。

当ThreadCache将不再使用的对象归还给CentralCache以致refcount减为0，即span中所有对象都空闲时，则CentralCache将这个span还给PageHeap。截取CentralFreeList::ReleaseToSpans()部分代码如下：

span->refcount--;
if (span->refcount == 0) {
  Event(span, '#', 0);
  counter_ -= ((span->length<<kPageShift) /
               Static::sizemap()->ByteSizeForClass(span->sizeclass));
  tcmalloc::DLL_Remove(span);
  --num_spans_;

  // Release central list lock while operating on pageheap
  lock_.Unlock();
  {
    SpinLockHolder h(Static::pageheap_lock());
    Static::pageheap()->Delete(span);
  }
  lock_.Lock();
}

CentralFreeList↔ThreadCache

CentralFreeList和ThreadCache之间的对象移动是批量进行的：

// Insert the specified range into the central freelist.  N is the number of
// elements in the range.  RemoveRange() is the opposite operation.
void InsertRange(void *start, void *end, int N);

// Returns the actual number of fetched elements and sets *start and *end.
int RemoveRange(void **start, void **end, int N);

start和end指定小对象链表的范围，N指定小对象的数量。批量移动小对象可以均摊锁操作的开销。

ThreadCache取用小对象

当ThreadCache中某个size class没有空闲对象可用时，需要从CentralFreeList获取N个对象，那么N的值是多少呢？从ThreadCache::FetchFromCentralCache()中可以找到答案：

const int batch_size = Static::sizemap()->num_objects_to_move(cl);
const int num_to_move = min<int>(list->max_length(), batch_size);
void *start, *end;
int fetch_count = Static::central_cache()[cl].RemoveRange(&start, &end, num_to_move);

移动数量N为max_length和batch_size的最小值（两者的具体涵义参见ThreadCache慢启动一节）。

假设只考虑内存分配的情况，一开始移动1个，然后是2个、3个，以此类推，同时max_length每次也加1，直到达到batch_size后，每次移动batch_size个对象。

CentralFreeList和ThreadCache之间的对象移动有个优化措施，因为大部分情况都是每次移动batch_size个对象，为了减少链表操作，提升效率，CentralFreeList将移动的batch_size个对象的链表的首尾指针缓存在了TCEntry中。因此后续只要需要移动batch_size个对象，只需要操作链表的首尾即可。

// Here we reserve space for TCEntry cache slots.  Space is preallocated
// for the largest possible number of entries than any one size class may
// accumulate.  Not all size classes are allowed to accumulate
// kMaxNumTransferEntries, so there is some wasted space for those size
// classes.
TCEntry tc_slots_[kMaxNumTransferEntries];