Hexo
0%

TCMalloc的内存分配算法概览

Posted on

TCMalloc的内存分配算法概览

转载自https://zhuanlan.zhihu.com/p/51432385 仅作学习使用

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的结构示大致如下：

img

CentralCache

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

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

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

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

img

PageHeap

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

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

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

img

内存回收

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

应用程序调用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并返回其起始地址即可：

1
2
3
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：

img

假设要分配一块内存，其大小经过向上取整之后对应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的管理内存的策略：

img

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