tcmalloc
https://mp.weixin.qq.com/s/PtGrZEkKarXuFAe_S3-8sQ
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。
从git仓库clone版本的gperftools的安装依赖autoconf、automake、libtool，以Debian为例：
apt install autoconf automake libtool
生成configure等一系列文件
$ ./autogen.sh
生成Makefile
$ ./configure
编译
$ make
安装
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
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/https://wallenwang.com/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）参考资料：
http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dui0803d/pge1446568291678.html
http://zhaohongjian000.is-programmer.com/posts/29660.html
https://www.cnblogs.com/catch/p/3619379.html
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的大小，比如18字节之间的内存申请都会分配8字节，916字节之间都会分配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的结构示大致如下：
tcmalloc-ThreadCache
CentralCache
那么ThreadCache中的空闲对象从何而来呢？答案是CentralCache——一个所有线程公用的缓存。
与ThreadCache类似，CentralCache中对于每个size class也都有一个单独的链表来缓存空闲对象，称之为CentralFreeList，供各线程的ThreadCache从中取用空闲对象。
由于是所有线程公用的，因此从CentralCache中取用或回收对象，是需要加锁的。为了平摊锁操作的开销，ThreadCache一般从CentralCache中一次性取用或回收多个空闲对象。
CentralCache在TCMalloc中并不是一个类，只是一个逻辑上的概念，其本质是CentralFreeList类型的数组。后文会详细讨论CentralCache的内部结构，现在暂且认为CentralCache的简化结构如下：
tcmalloc-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的简化结构如下：
tcmalloc-PageHeap
内存回收
上面说的都是内存分配，内存回收的情况是怎样的？
应用程序调用free()或delete一个小对象时，仅仅是将其插入到ThreadCache中其size class对应的FreeList中而已，不需要加锁，因此速度也是非常快的。
只有当满足一定的条件时，ThreadCache中的空闲对象才会重新放回CentralCache中，以供其他线程取用。同样的，当满足一定条件时，CentralCache中的空闲对象也会还给PageHeap，PageHeap再还给系统。
内存在这些组件之间的移动会在后文详细讨论，现在先忽略这些细节。
小结
总结一下，小对象分配流程大致如下：
将要分配的内存大小映射到对应的size class。
查看ThreadCache中该size class对应的FreeList。
如果FreeList非空，则移除FreeList的第一个空闲对象并将其返回，分配结束。
如果FreeList是空的：
如果CentralFreeList也是空的，则：
向PageHeap申请一个span。
拆分成size class对应大小的空闲对象，放入CentralFreeList中。
从CentralCache中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：
tcmalloc-SpanList
假设要分配一块内存，其大小经过向上取整之后对应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的管理内存的策略：
tcmalloc-Overview
可以看到，不超过256KB的小对象分配，在应用程序和内存之间其实有三层缓存：PageHeap、CentralCache、ThreadCache。而中对象和大对象分配，则只有PageHeap一层缓存。
TCMalloc的实现细节
算法概览一节涉及到了很多概念，比如Page，Span，Size Class，PageHeap，ThreadCache等，但只是粗略的一提，本节将详细讨论这些概念所涉及的实现细节。
Page
Page是TCMalloc管理内存的基本单位（这里的page要区分于操作系统管理虚拟内存的page），page的默认大小为8KB，可在configure时通过选项调整为32KB或64KB。
./configure
page越大，TCMalloc的速度相对越快，但其占用的内存也会越高。简单说，就是空间换时间的道理。默认的page大小通过减少内存碎片来最小化内存使用，但跟踪这些page会花费更多的时间。使用更大的page则会带来更多的内存碎片，但速度上会有所提升。官方文档给出的数据是在某些google应用上有3%~5%的速度提升。
PageID
TCMalloc并非只将堆内存看做是一个个的page，而是将整个虚拟内存空间都看做是page的集合。从内存地址0x0开始，每个page对应一个递增的PageID，如下图（以32位系统为例）：
tcmalloc-Page
对于任意内存地址ptr，都可通过简单的移位操作来计算其所在page的PageID：
static const size_t kPageShift = 13; // page大小：1 « 13 = 8KB
const PageID p = reinterpret_cast
即，ptr所属page的PageID为ptr / page_size。
Span
一个或多个连续的Page组成一个Span（a contiguous run of pages）。TCMalloc以Span为单位向系统申请内存。
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的大小均分成若干小对象，在每一个小对象的起始位置处存储下一个小对象的地址，首首相连：
tcmalloc-FreshSpan
但当span中的小对象经过一系列申请和回收之后，其顺序就不确定了：
tcmalloc-UsedSpan
可以看到，有些小对象已经不再空闲对象链表objects中了，链表中的元素顺序也已经被打乱。
空闲对象链表中的元素乱序没什么影响，因为只有当一个span的所有小对象都被释放之后，CentralFreeList才会将其还给PageHeap。
PageMap
PageMap之前没有提到过，它主要用于解决这么一个问题：给定一个page，如何确定这个page属于哪个span？
即，PageMap缓存了PageID到Span的对应关系。
32位系统、x86-64、arm64使用两级PageMap，以32位系统为例：
tcmalloc-PageMap
在root_数组中包含512个指向Leaf的指针，每个Leaf又是1024个void*的数组，数组索引为PageID，数组元素为page所属Span的指针。一共个数组元素，对应32位系统的个page。
使用两级map可以减少TCMalloc元数据的内存占用，因为初始只会给第一层（即root_数组）分配内存（2KB），第二层只有在实际用到时才会实际分配内存。而如果初始就给个page都分配内存的话，则会占用的内存。
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。比如：
size_merge
第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
}
// s > 1024
static inline size_t LargeSizeClass(size_t s) {
return (static_cast
}
当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是这样的：
tcmalloc-PageHeap2
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);
搜索空闲span链表，按照以下顺序，找出第一个不小于k的span：
从大小为k的span的链表开始依次搜索
对于某个大小的span，先搜normal链表，再搜returned链表
如果span链表中没找到合适的span，则搜索存储大span的set：
从大小为k的span开始搜索
同样先搜normal再搜returned
优先使用长度最小并且起始地址最小的span（best-fit）
如果通过以上两步找到了一个大小为m的span，则将其拆成两个span：
大小为m - k的span重新根据大小和状态放回链表或set中
大小为k的span作为结果返回，创建span结束
如果没搜到合适的span，则继续后面的步骤：向系统申请内存。
小插曲：释放所有空闲内存
ReleaseAtLeastNPages(static_cast
当没有可用的空闲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：
tcmalloc-SbrkAlloc
假设在申请内存之前，pb（program break，可以认为是堆内存的上边界）指向红色箭头所示位置，即没有在page的边界处。
第一次sbrk申请16KB内存，因此pb移至绿色箭头所示位置。
由于需要对申请的内存按page对齐，因此需要第二次sbrk，pb指向蓝色箭头所示位置，page的边界处。
最终，返回的内存地址为黑色箭头所示位置，黑色和蓝色箭头之间刚好16KB。
可以看出，红色箭头和黑色箭头之间的内存就无法被使用了，产生了外部碎片。
mmap
如果使用sbrk申请内存失败，TCMalloc会尝试使用mmap来分配。同样，为了覆盖MmapSysAllocator::Alloc()的大部分情况，下图假设系统的page为4KB，TCMalloc的page为16KB，申请的内存大小为32KB：
tcmalloc-MmapAlloc
假设在申请内存之前，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才可以被合并。
tcmalloc-SpanMerge1
上图中，被删除的span的前一个span是normal状态，因此可以与之合并，而后一个span是returned状态，无法与之合并。合并操作之后如下图：
tcmalloc-SpanMerge2
还有一个值得注意的开关：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：
tcmalloc-SpanMerge3
释放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的结构：
tcmalloc-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
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：
tcmalloc-CentralFreeList
CentralFreeList↔ PageHeap
从PageHeap获取span
当ThreadCache从CentralFreeList取用空闲对象（RemoveRange），但CentralFreeList的空闲对象数量不够时，CentralFreeList调用Populate()从PageHeap申请一个span拆分成若干小对象，首首连接记录在span的objects指针中，即每个小对象的起始位置处，记录了下一个小对象的地址。此时的span如下图：
tcmalloc-FreshSpan
可以看到，此时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
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];
ThreadCache归还小对象
当ThreadCache中的空闲对象过多时（ThreadCache::ListTooLong()），会将一部分空闲对象放回CentralFreeList（ThreadCache::ReleaseToCentralCache()）。如何判断空闲对象过多请参考ThreadCache慢启动一节。
线程销毁也会将其ThreadCache中所有的空闲对象都放回CentralFreeList。
如果ThreadCache缓存的内存大小超过其允许的最大值，会触发GC操作（ThreadCache::Scavenge()），在其中也会将部分小对象归还给CentralFreeList，具体请参考ThreadCache垃圾回收一节。
系统的物理内存是有限的，而对内存的需求是变化的, 程序的动态性越强，内存管理就越重要，选择合适的内存管理算法会带来明显的性能提升。
比如nginx， 它在每个连接accept后会malloc一块内存，作为整个连接生命周期内的内存池。 当HTTP请求到达的时候，又会malloc一块当前请求阶段的内存池, 因此对malloc的分配速度有一定的依赖关系。(而apache的内存池是有父子关系的，请求阶段的内存池会和连接阶段的使用相同的分配器，如果连接内存池释放则请求阶段的子内存池也会自动释放)。
目标
内存管理可以分为三个层次，自底向上分别是：
操作系统内核的内存管理
glibc层使用系统调用维护的内存管理算法
应用程序从glibc动态分配内存后，根据应用程序本身的程序特性进行优化， 比如使用引用计数std::shared_ptr，apache的内存池方式等等。
当然应用程序也可以直接使用系统调用从内核分配内存，自己根据程序特性来维护内存，但是会大大增加开发成本。
本文主要介绍了glibc malloc的实现，及其替代品
一个优秀的通用内存分配器应具有以下特性:
额外的空间损耗尽量少
分配速度尽可能快
尽量避免内存碎片
缓存本地化友好
通用性，兼容性，可移植性，易调试
现状
目前大部分服务端程序使用glibc提供的malloc/free系列函数，而glibc使用的ptmalloc2在性能上远远弱后于google的tcmalloc和facebook的jemalloc。 而且后两者只需要使用LD_PRELOAD环境变量启动程序即可，甚至并不需要重新编译。
glibc ptmalloc2
ptmalloc2即是我们当前使用的glibc malloc版本。
ptmalloc原理
系统调用接口
上图是 x86_64 下 Linux 进程的默认地址空间, 对 heap 的操作, 操作系统提供了brk()系统调用，设置了Heap的上边界； 对 mmap 映射区域的操作,操作系 统 供了 mmap()和 munmap()函数。
因为系统调用的代价很高，不可能每次申请内存都从内核分配空间，尤其是对于小内存分配。 而且因为mmap的区域容易被munmap释放，所以一般大内存采用mmap()，小内存使用brk()。
多线程支持
Ptmalloc2有一个主分配区(main arena)， 有多个非主分配区。 非主分配区只能使用mmap向操作系统批发申请HEAP_MAX_SIZE（64位系统为64MB）大小的虚拟内存。 当某个线程调用malloc的时候，会先查看线程私有变量中是否已经存在一个分配区，如果存在则尝试加锁，如果加锁失败则遍历arena链表试图获取一个没加锁的arena， 如果依然获取不到则创建一个新的非主分配区。
free()的时候也要获取锁。分配小块内存容易产生碎片，ptmalloc在整理合并的时候也要对arena做加锁操作。在线程多的时候，锁的开销就会增大。
ptmalloc内存管理
用户请求分配的内存在ptmalloc中使用chunk表示， 每个chunk至少需要8个字节额外的开销。 用户free掉的内存不会马上归还操作系统，ptmalloc会统一管理heap和mmap区域的空闲chunk，避免了频繁的系统调用。
ptmalloc 将相似大小的 chunk 用双向链表链接起来, 这样的一个链表被称为一个 bin。Ptmalloc 一共 维护了 128 个 bin,并使用一个数组来存储这些 bin(如下图所示)。
数组中的第一个为 unsorted bin, 数组中从 2 开始编号的前 64 个 bin 称为 small bins, 同一个small bin中的chunk具有相同的大小。small bins后面的bin被称作large bins。
当free一个chunk并放入bin的时候， ptmalloc 还会检查它前后的 chunk 是否也是空闲的, 如果是的话,ptmalloc会首先把它们合并为一个大的 chunk, 然后将合并后的 chunk 放到 unstored bin 中。 另外ptmalloc 为了提高分配的速度,会把一些小的(不大于64B) chunk先放到一个叫做 fast bins 的容器内。
在fast bins和bins都不能满足需求后，ptmalloc会设法在一个叫做top chunk的空间分配内存。 对于非主分配区会预先通过mmap分配一大块内存作为top chunk， 当bins和fast bins都不能满足分配需要的时候, ptmalloc会设法在top chunk中分出一块内存给用户, 如果top chunk本身不够大, 分配程序会重新mmap分配一块内存chunk, 并将 top chunk 迁移到新的chunk上，并用单链表链接起来。如果free()的chunk恰好 与 top chunk 相邻,那么这两个 chunk 就会合并成新的 top chunk，如果top chunk大小大于某个阈值才还给操作系统。主分配区类似，不过通过sbrk()分配和调整top chunk的大小，只有heap顶部连续内存空闲超过阈值的时候才能回收内存。
需要分配的 chunk 足够大,而且 fast bins 和 bins 都不能满足要求,甚至 top chunk 本身也不能满足分配需求时,ptmalloc 会使用 mmap 来直接使用内存映射来将页映射到进程空间。
ptmalloc分配流程
ptmalloc的缺陷
后分配的内存先释放,因为 ptmalloc 收缩内存是从 top chunk 开始,如果与 top chunk 相邻的 chunk 不能释放, top chunk 以下的 chunk 都无法释放。
多线程锁开销大， 需要避免多线程频繁分配释放。
内存从thread的areana中分配， 内存不能从一个arena移动到另一个arena， 就是说如果多线程使用内存不均衡，容易导致内存的浪费。 比如说线程1使用了300M内存，完成任务后glibc没有释放给操作系统，线程2开始创建了一个新的arena， 但是线程1的300M却不能用了。
每个chunk至少8字节的开销很大
不定期分配长生命周期的内存容易造成内存碎片，不利于回收。 64位系统最好分配32M以上内存，这是使用mmap的阈值。
tcmalloc
tcmalloc是Google开源的一个内存管理库， 作为glibc malloc的替代品。目前已经在chrome、safari等知名软件中运用。
根据官方测试报告，ptmalloc在一台2.8GHz的P4机器上（对于小对象）执行一次malloc及free大约需要300纳秒。而TCMalloc的版本同样的操作大约只需要50纳秒。
小对象分配
tcmalloc为每个线程分配了一个线程本地ThreadCache，小内存从ThreadCache分配，此外还有个中央堆（CentralCache），ThreadCache不够用的时候，会从CentralCache中获取空间放到ThreadCache中。
小对象（<=32K）从ThreadCache分配，大对象从CentralCache分配。大对象分配的空间都是4k页面对齐的，多个pages也能切割成多个小对象划分到ThreadCache中。
小对象有将近170个不同的大小分类(class)，每个class有个该大小内存块的FreeList单链表，分配的时候先找到best fit的class，然后无锁的获取该链表首元素返回。如果链表中无空间了，则到CentralCache中划分几个页面并切割成该class的大小，放入链表中。
CentralCache分配管理
大对象(>32K)先4k对齐后，从CentralCache中分配。 CentralCache维护的PageHeap如下图所示， 数组中第256个元素是所有大于255个页面都挂到该链表中。
当best fit的页面链表中没有空闲空间时，则一直往更大的页面空间则，如果所有256个链表遍历后依然没有成功分配。 则使用sbrk, mmap, /dev/mem从系统中分配。
tcmalloc PageHeap管理的连续的页面被称为span.
如果span未分配， 则span是PageHeap中的一个链表元素
如果span已经分配，它可能是返回给应用程序的大对象， 或者已经被切割成多小对象，该小对象的size-class会被记录在span中
在32位系统中，使用一个中央数组(central array)映射了页面和span对应关系， 数组索引号是页面号，数组元素是页面所在的span。 在64位系统中，使用一个3-level radix tree记录了该映射关系。
回收
当一个object free的时候，会根据地址对齐计算所在的页面号，然后通过central array找到对应的span。
如果是小对象，span会告诉我们他的size class，然后把该对象插入当前线程的ThreadCache中。如果此时ThreadCache超过一个预算的值（默认2MB），则会使用垃圾回收机制把未使用的object从ThreadCache移动到CentralCache的central free lists中。
如果是大对象，span会告诉我们对象锁在的页面号范围。 假设这个范围是[p,q]， 先查找页面p-1和q+1所在的span，如果这些临近的span也是free的，则合并到[p,q]所在的span， 然后把这个span回收到PageHeap中。
CentralCache的central free lists类似ThreadCache的FreeList，不过它增加了一级结构，先根据size-class关联到spans的集合， 然后是对应span的object链表。如果span的链表中所有object已经free， 则span回收到PageHeap中。
tcmalloc的改进
ThreadCache会阶段性的回收内存到CentralCache里。 解决了ptmalloc2中arena之间不能迁移的问题。
Tcmalloc占用更少的额外空间。例如，分配N个8字节对象可能要使用大约8N * 1.01字节的空间。即，多用百分之一的空间。Ptmalloc2使用最少8字节描述一个chunk。
更快。小对象几乎无锁， >32KB的对象从CentralCache中分配使用自旋锁。 并且>32KB对象都是页面对齐分配，多线程的时候应尽量避免频繁分配，否则也会造成自旋锁的竞争和页面对齐造成的浪费。
性能对比
官方测试
测试环境是2.4GHz dual Xeon，开启超线程，redhat9，glibc-2.3.2, 每个线程测试100万个操作。
上图中可以看到尤其是对于小内存的分配， tcmalloc有非常明显性能优势。
上图可以看到随着线程数的增加，tcmalloc性能上也有明显的优势，并且相对平稳。
github mysql优化
github使用tcmalloc后，mysql性能提升30%
Jemalloc
jemalloc是facebook推出的， 最早的时候是freebsd的libc malloc实现。 目前在firefox、facebook服务器各种组件中大量使用。
jemalloc原理
与tcmalloc类似，每个线程同样在<32KB的时候无锁使用线程本地cache。
Jemalloc在64bits系统上使用下面的size-class分类：
Small: [8], [16, 32, 48, …, 128], [192, 256, 320, …, 512], [768, 1024, 1280, …, 3840]
Large: [4 KiB, 8 KiB, 12 KiB, …, 4072 KiB]
Huge: [4 MiB, 8 MiB, 12 MiB, …]
small/large对象查找metadata需要常量时间， huge对象通过全局红黑树在对数时间内查找。
虚拟内存被逻辑上分割成chunks（默认是4MB，1024个4k页），应用线程通过round-robin算法在第一次malloc的时候分配arena， 每个arena都是相互独立的，维护自己的chunks， chunk切割pages到small/large对象。free()的内存总是返回到所属的arena中，而不管是哪个线程调用free()。
上图可以看到每个arena管理的arena chunk结构， 开始的header主要是维护了一个page map（1024个页面关联的对象状态）， header下方就是它的页面空间。 Small对象被分到一起， metadata信息存放在起始位置。 large chunk相互独立，它的metadata信息存放在chunk header map中。
通过arena分配的时候需要对arena bin（每个small size-class一个，细粒度）加锁，或arena本身加锁。
并且线程cache对象也会通过垃圾回收指数退让算法返回到arena中。
jemalloc的优化
Jmalloc小对象也根据size-class，但是它使用了低地址优先的策略，来降低内存碎片化。
Jemalloc大概需要2%的额外开销。（tcmalloc 1%， ptmalloc最少8B）
Jemalloc和tcmalloc类似的线程本地缓存，避免锁的竞争
相对未使用的页面，优先使用dirty page，提升缓存命中。
性能对比
官方测试
上图是服务器吞吐量分别用6个malloc实现的对比数据，可以看到tcmalloc和jemalloc最好(facebook在2011年的测试结果，tcmalloc这里版本较旧)。
4.3.2 mysql优化
测试环境：2x Intel E5/2.2Ghz with 8 real cores per socket，16 real cores， 开启hyper-threading， 总共32个vcpu。 16个table，每个5M row。
OLTP_RO测试包含5个select查询：select_ranges, select_order_ranges, select_distinct_ranges, select_sum_ranges,
可以看到在多核心或者多线程的场景下， jemalloc和tcmalloc带来的tps增加非常明显。
参考资料
glibc内存管理ptmalloc源代码分析
Inside jemalloc
tcmalloc浅析
tcmalloc官方文档
Scalable memory allocation using jemalloc
mysql-performance-impact-of-memory-allocators-part-2
ptmalloc,tcmalloc和jemalloc内存分配策略研究
Tick Tock, malloc Needs a Clock
总结
在多线程环境使用tcmalloc和jemalloc效果非常明显。
当线程数量固定，不会频繁创建退出的时候， 可以使用jemalloc；反之使用tcmalloc可能是更好的选择。
