TCMalloc

基础知识

Go语言的内存分配器主要是基于Tcmalloc内存分配器实现的。所以我们想搞懂Go语言的内存分配原理前，必须先了解Tcmalloc内存分配器

内存的线性分配

线性分配大致就是需要使用多少分配多少，“用到哪了标识到哪”如下图

线性分配有个问题：“已经分配的内存被释放了，我们如何再次分配？”。大家会想到用链表LinkedList，是的没错，但是内存管理中一般使用的是FreeList。

什么是FreeList

FreeList本质上还是个LinkedList和LinkedList的区别

• FreeList没有Next属性，所以不是用Next存放下一个节点的指针的值。
• FreeList相当于使用了Value的前8字节（其实就是整块内存的前8字节）存放下一个节点的指针。
• 分配出去的节点，节点整块内存空间可以被复写（指针的值可以被覆盖掉）

结论FreeList里一个节点最小为8字节

虚拟内存

这里直说结论哈，我们的进程是运行在虚拟内存上的，图示如下：

• 对于我们的进程而言，可使用的内存是连续的
• 安全，防止了进程直接对物理内存的操作(如果进程可以直接操作物理内存，那么存在某个进程篡改其他进程数据的可能)
• 虚拟内存和物理内存是通过MMU(Memory Manage Unit)映射的(感兴趣的可以研究下)

所以，以下文章我们说的内存都是虚拟内存。

TcMalloc

TCMalloc全程ThreadCacheAllo，是google开源的一个内存分配器，基于数据结构FreeList实现，并引入了线程级别的缓存，性能更加优异。

基本概念

page

操作系统是按Page管理内存的，本文中1Page为8KB

span和SpanList

一个Span是由N个Page构成的，且

• N的范围为1-正无穷
• 构成这个Span的N个Page在内存空间上必须是连续的

从图中可以看出，有：

• 1个Page构成的8KB的Span
• 2个连续Page构成的16KB的Span
• 3个连续Page构成的24KB的Span

除此之外，Span和Span之间可以构成双向链表我们称之为SpanList，内存管理器中通常将持有相同数量的Page和Span构成一个双向链表，如下图所示（N个持有1Page的Span构成的SpanList）

class Span : public SpanList::Elem {
 public:

  // 略...

  // 把span拆解成object的方法
  // object的概念看下文
  void BuildFreelist(size_t size, size_t count);

  
  // 略...

  union {
    // object构成的freelist
    // object的概念看下文
    ObjIdx cache_[kCacheSize];
    
    // 略...
  };

  PageId first_page_;  // 当前span是从哪个page开始的
  Length num_pages_;   // 当前page持有的page数量

  // 略...
};

Object和SizeClass的概念

一个Span会被按照某个大小拆封为N个Object，同时这N个Object构成FreeList

我们持有的1Page的Span为例，Span、Page、Object关系图如下

看完上面的图示，问题来了：

上图怎么知道拆分Span为一个个24字节大小的Object，这个规则是怎么知道的呢？

答案：依赖代码维护的映射列表。

我们以Google开源的TCMalloc源码(commit:9d274df)为例来看一下这个映射列表 https://github.com/google/tcmalloc/tree/master/tcmalloc

代码位置：tcmalloc/tcmalloc/size_classes.cc
代码示例(摘取一部分)：

const SizeClassInfo SizeMap::kSizeClasses[SizeMap::kSizeClassesCount] = {
    // 这里的每一行 称之为SizeClass
    // <bytes>, <pages>, <batch size>    <fixed>
    // Object大小列，一次申请的page数，一次移动的objects数(内存申请或回收)
    {        0,       0,           0},  // +Inf%
    // 所以也知道为啥最小8字节了吧？
    // Object会构成FreeList
    // FreeList的节点要存指针
    // 指针为8字节
    {        8,       1,          32},  // 0.59%
    {       16,       1,          32},  // 0.59%
    {       24,       1,          32},  // 0.68%
    {       32,       1,          32},  // 0.59%
    {       40,       1,          32},  // 0.98%
    {       48,       1,          32},  // 0.98%
    // ...略...
    {    98304,      12,           2},  // 0.05%
    {   114688,      14,           2},  // 0.04%
    {   131072,      16,           2},  // 0.04%
    {   147456,      18,           2},  // 0.03%
    {   163840,      20,           2},  // 0.03%
    {   180224,      22,           2},  // 0.03%
    {   204800,      25,           2},  // 0.02%
    {   229376,      28,           2},  // 0.02%
    {   262144,      32,           2},  // 0.02%
};

获取拆分规则的过程(先找到行、再找到这行第一列的值)：
1. 先找到对应行(如何找到这个行？是不是有人有疑惑了，
想知道这个答案就需要了解`CentralFreeList`这个结构了，
下文我们会讲到。)
2. 找到第一列，这个数字就是object的大小

同时通过上面我们知道了：SizeMap::kSizeClasses的每一行元素我们称之为SizeClass(下文中我们直接就称之为SizeClass).

这个5个基本概念具体干什么用的呢？

答案：支撑了`Tcmalloc`的基本结构的实现。

基本结构

Tcmalloc主要由三部分构成

• PageHeap
• CentralFreeList
• ThreadCache

但是呢，实际上CentralFreeList是被TranferCacheManager管理的，所以Tcmalloc的基本结构应该为下图所示

接着ThreadCache其实是被线程持有的

这是为了减少线程之间的竞争，分配内存时减少锁的过程。

这也是为什么叫ThreadCache Alloc的原因

详细构成

PageHeap

主要负责管理不同规格的span，相同规格的Span构成SpanList

持有相同Page数目的Span叫做相同规格的Span

PageHeap对象里维护了一个数下free_类型是个数组，粗略看数组元素的类型是SpanList，同时free_这个数据的元素具有以下特性

• 索引值为1对应的SpanList，该SpanList的Span都持有1Pages；
• 索引值为2对应的SpanList，该SpanList的Span都持有2Pages；
• 以此类推，free_索引值为MaxNumber对应的SpanList，该SpanList的Span都持有MaxNumber Pages；
• MaxNumber的值由kMaxPages决定

class PageHeap final : public PageAllocatorInterface {
 public:

  // ...略

 private:
  // 持有两个Span构成的双向链表
  struct SpanListPair {
    // Span构成的双向链表 正常的
    SpanList normal; 
    // Span构成的双向链表 大概是 物理内存已经回收 但是虚拟内存还被持有(感兴趣可以研究)
    SpanList returned;
  };

  // ...略

  // kMaxPages.raw_num()这么多个，由上面SpanListPair类型构成的数组
  SpanListPair free_[kMaxPages.raw_num()] ABSL_GUARDED_BY(pageheap_lock);

  // ...略
};

结论

• free_数组元素的类型是SpanListPair
• SpanListPair里维护了俩个SpanList

根据这个结论我们修正下PageHeap结构图

又因为大于kMaxPages个Pages(大对象)的内存分配是从large_中分配的，代码如下：

class PageHeap final : public PageAllocatorInterface {
 public:

  // ...略

  //  大对象的内存从这里分配(length >= kMaxPages)
  SpanListPair large_ ABSL_GUARDED_BY(pageheap_lock);

  // ...略
};

所以我们再加上大对象的分配时的large_属性，得到PageHeap的结构图如下：

同时PageHeap核心的代码片段如下：

class PageHeap final : public PageAllocatorInterface {
 public:

  // ...略

 private:
  // 持有两个Span构成的双向链表
  struct SpanListPair {
    // Span构成的双向链表
    SpanList normal; 
    // Span构成的双向链表
    SpanList returned;
  };

  //  大对象的内存从这里分配(length >= kMaxPages)
  SpanListPair large_ ABSL_GUARDED_BY(pageheap_lock);

  // kMaxPages.raw_num()这么多个，由上面SpanListPair类型构成的数组
  SpanListPair free_[kMaxPages.raw_num()] ABSL_GUARDED_BY(pageheap_lock);

  // ...略
};

CentralFreeList和TransferCacheManager

CentralCache

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

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

我们可以称之为中央缓存，中央缓存被线程共享，从中央缓存CentralFreeList获取缓存需要加锁。

CentralFreeList里面有个属性size_class_，就是SizeClass的值，来自于映射表SizeMap这个数组的索引值。CentralfreeList里的span会做一件事情，按照size_class_值对应的规格拆解成Span为多个Object，同时这些Object构成FreeList

同时，sizeMap里的每个SizeClass都会对应一个CentralfreeList,所以最多一共会有N个CentralfreeList,N的值为kNumClass

class CentralFreeList {

  // ...略

 private:

  // 锁
  // 线程从此处获取内存 需要加锁 保证并发安全
  absl::base_internal::SpinLock lock_;

  // 对应上文提到的映射表SizeClassInfo中的某个索引值
  // 目的找到Span拆解为object时，object的大小等规则
  size_t size_class_;  
  // object的总数量
  size_t object_size_;
  // 一个Span持有的object的数量
  size_t objects_per_span_;
  // 一个Span持有的page的数量
  Length pages_per_span_;

  // ...略

如下图就展示了kNumClasses个CentralFreeList，其中我们以size_class_的值为1和3为例来展示下CentralFreeList的结构。

TransferCacheManager

因为有KnumClasses个CentralFreeList，这些CentralFreeList在哪维护呢？

答案就是TransferCacheManager这个结构里的freelist_属性

代码如下

class TransferCacheManager {
  
  // ...略

 private:
  // freelist_是个数组
  // 元素的类型是上面的CentralFreeList
  // 元素的数量与 映射表 SizeClassInfo对应
  CentralFreeList freelist_[kNumClasses];
} ABSL_CACHELINE_ALIGNED;

ThreadCache构成

我们可以称之为线程缓存TCMalloc内存分配器的核心所在。ThreadCache被每个线程持有，分配内存时不用加锁，性能好

ThreadCache对象里面维护了一个数下list_类型是个数组，数组元素类型是FreeList，代码如下

class ThreadCache {
  // ...略

  // list_是个数组
  // 元素的类型是FreeList
  // 元素的数量与 映射表 SizeClassInfo对应
  FreeList list_[kNumClasses]; 

  // ...略
};

同时FreeList里的元素还具有以下特性：

• 索引值为1对应的FreeList，该FreeList的Object大小为8 Bytes；
• 索引值为2对应的FreeList，该FreeList的Object大小为16 Bytes；
• 以此类推，free_索引值为MaxNumber对应的FreeList，该FreeList的Object大小为MaxNumber Bytes；
• MaxNumber的值由kNumClasses决定

这个规则怎么来的？还是取决于映射列表，同样以Google开源的TCMalloc源码(commit:9d274df)为例，来看一下这个映射列表：

https://github.com/google/tcmalloc/tree/master/tcmalloc
​
代码位置：tcmalloc/tcmalloc/size_classes.cc
代码示例(摘取一部分)：
​
const SizeClassInfo SizeMap::kSizeClasses[SizeMap::kSizeClassesCount] = {
    // 这里的每一行 称之为SizeClass
    // <bytes>, <pages>, <batch size>    <fixed>
    // Object大小列，一次申请的page数，一次移动的objects数(内存申请或回收)
    {        0,       0,           0},  // +Inf%
    {        8,       1,          32},  // 0.59%
    {       16,       1,          32},  // 0.59%
    {       24,       1,          32},  // 0.68%
    {       32,       1,          32},  // 0.59%
    {       40,       1,          32},  // 0.98%
    {       48,       1,          32},  // 0.98%
    // ...略...
};

我们可以得到

我们可以得到：

得到ThreadCache结构图如下所示：

注意：图示中索引为3的FreeList的Span尾部会浪费掉8字节。

Tcmalloc的内存分配过程

我们把Tcmalloc中分配的对象分为俩类

• 小对象
• 非小对象

小对象的大小范围来自SizeMap维护的映射表，也就是单个Object的大小范围，我们还是以如下代码片段为例，可知单个Object大小范围为

8 Byte ~ 262144 Byte == 8 Byte ~ 256 KB

const SizeClassInfo SizeMap::kSizeClasses[SizeMap::kSizeClassesCount] = {
    // 这里的每一行 称之为SizeClass
    // <bytes>, <pages>, <batch size>    <fixed>
    // Object大小列，一次申请的page数，一次移动的objects数(内存申请或回收)
    // ...略...
    {        8,       1,          32},  // 0.59%
    // ...略...
    {   262144,      32,           2},  // 0.02%
};

当给小对象分配内存时，ThreadCache的内存不足时，从对应SizeClass的CentralFreeList获取，如果获取不到，CentralFreeList再从PageHeap里获取内存

最后我们以获取6字节的小对象为例（SizeClass的值为1）看一下详细内存分配过程 。

总结

• 了解了FreeList

• 知道了TCMalloc主要由ThreadCache、CentralFreeList、PageHeap三部分组成

  • Object构成的FreeList，被ThreadCache维护
  • Span构成了SpanList，被CentralFreeList维护，同时Span会被拆解成Object
  • 当ThreadCache里的Object没有时，从对应SizeClass的CentralFreeList里获取
  • 小对象来自ThreadCache、CentralFreeList
  • 非小对象来自PageHeap
• 线程从ThreadCache获取内存不需要加锁

转载自(4 封私信 / 81 条消息) tcmalloc总是比malloc好吗？ - 知乎 (zhihu.com)