tcmalloc学习记录
周末有时间学习一下tcmalloc用以自己记录。
引用学习自：https://wallenwang.com/2018/11/tcmalloc/
TCMalloc是什么？
TCMalloc全称Thread-Caching Malloc，即线程缓存的malloc，实现了高效的多线程内存管理，用于替代系统的内存分配相关的函数（malloc、free，new，new[]等）。
TCMalloc的内存分配算法概览
按照所分配内存的大小，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。可能会被划分为一系列的小对象，供小对象分配使用，也可能当做一整块当做中对象或大对象分配。
重点说一下小对象的分配：
对于256KB以内的小对象分配，TCMalloc按大小划分了85个类别（官方介绍中说是88个左右，但我个人实际测试是85个，不包括0字节大小），称为Size Class，每个size class都对应一个大小，比如8字节，16字节，32字节。
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获取的第一个对象，分配结束。
总结下来：tcmalloc的使用如下
申请内存
- 根据申请空间的大小从当前线程的可用内存块里面找（每个进程维护一组链表，每个链表代表一定大小的可用空间）
- 若没有找到，则到central list里面查找
- 若step 2的central list也没有找到，则计算分配size个字节需要分配多少page(page默认大小为8k，不同系统可能不同)
- 根据pagemap查找page对应的可用的span列表，若果找到了，则直接返回span，central list会将该span切割成合适的大小放入对应的列表中，然后交给thread cache
- 若step 4没有找到可用的span，则向OS直接申请，然后步骤同step 4
释放内存：
- 释放某个object
- 找到该object所在的span
- 若该span中所有object都被释放，则释放该span到对应的可用列表，在释放的过程中，尝试将该span跟左右spans merge成更大的span
- 若当前thread cache的free 空间大于指定预置，归还部分空间给central list
- central list也会试图通过释放可用span列表的最后几个span来将不用的空间归还给OS
TCMalloc的管理内存的策略概图：
不超过256KB的小对象分配，在应用程序和内存之间其实有三层缓存：PageHeap、CentralCache、ThreadCache。而中对象和大对象分配，则只有PageHeap一层缓存。