tcmalloc原理剖析(基于gperftools-2.1)

Posted by gao-xiao-long on November 25, 2017

本文偏重于剖析tcmalloc的整体结构(基于gperftools-2.1),为了不过于繁琐,不过多涉及内部实现细节。

介绍

tcmalloc是google开发的一个专门为高并发场景优化的内存分配器,全称为”thread cache malloc”。按照官网的介绍,tcmalloc相比于glibc2.3的malloc(底层实现为ptmalloc2)主要有以下优点:

  1. 快速:一台2.8GHz的P4机器上,执行一次malloc及free大约需要300纳秒;而tcmalloc的版本同样的操作大约只需要50纳秒。
  2. 空间占用小:相比ptmalloc2,tcmalloc对小对象占用空间进行了优化。例如:分配N个8字节对象只需要占用8N*1.01字节的空间。即,只需要多使用1%的空间。而ptmalloc2中每个对象都需要使用一个4字节的头信息,最后占用的字节可能达到8N*8。
  3. 不容易出现内存暴涨

使用方法

通过以下两种方法可以将默认的malloc-allocation替换为tcmalloc。

  1. 通过指定-ltcmalloc链接器标示将tcmalloc接入应用中
  2. 通过LD_PRELOAD指定:LD_PRELOAD=”/usr/lib/libtcmalloc.so”

替换原理

glibc中的memory-allocation方法均被为声明为弱符号,只需要在tcmalloc中将其重新定义即可。 具体的重新定义代码在src/libc_override*.h中(不同平台实现不同),下面是Linux平台下部分memory-allocation函数的重新定义实现:

void* operator new(size_t size)                  { return tc_new(size);       }
void operator delete(void* p) __THROW            { tc_delete(p);              }
void* operator new[](size_t size)                { return tc_newarray(size);  }
void operator delete[](void* p) __THROW          { tc_deletearray(p);         }
extern "C" {
  void* malloc(size_t s) __THROW                 { return tc_malloc(s);       }
  void  free(void* p) __THROW                    { tc_free(p);                }
  void* realloc(void* p, size_t s) __THROW       { return tc_realloc(p, s);   }
  void* calloc(size_t n, size_t s) __THROW       { return tc_calloc(n, s);    }
  void  cfree(void* p) __THROW                   { tc_cfree(p);               }
}  // extern "C"

整体结构

结构图 上图展示了tcmalloc的整体结构, tcmalloc主要由三个组件组成:ThreadCache、CentralFreeList及PageHeap。 其中:

  • ThreadCache: 线程缓存,它是一个TSL(线程本地存储)对象,尺寸小于256K的小内存申请均由ThreadCache进行分配;通过ThreadCache分配过程中不需要任何锁,可以极大的提高分配速度
  • PageHeap: 中央堆分配器,被所有线程共享(分配时需要全局锁定),负责与操作系统的直接交互(申请及释放内存),并且大尺寸的内存申请直接通过PageHeap进行分配
  • CentralFreeList:作为PageHeap与ThreadCache的中间人,负责
    1. 将PageHeap中的内存切分为小块,在恰当时机分配给ThreadCache。
    2. 获取从ThreadCache中回收的内存并在恰当的时机将部分内存归还给PageHeap

下面详细剖析下内部结构。

核心思想:Segregated Free List(离散式空闲列表)

tcmalloc的动态内存分配核心思想为离散式空闲列表算法,即如下图所示: 结构图 tcmalloc定义了86个size class,每个size class都维护了一个可分配的的空闲列表(空闲列表中的每一项称为一个object,同一个class的空闲列表中每个object大小相同)。在申请小内存时(小于256K),tcmalloc会根据申请大小映射到某个class中。比如,申请0到8个字节的大小时,会被映射到class1中,分配8个字节大小;申请9到16字节大小时,会被映射到class2中,分配16个字节大小….以此类推。 tcmalloc通过SizeMap类维护了具体的映射关系,部分映射关系如下: 结构图 说明:

  • num_objects_to_move用来定义ThreadCache在内存不足时从CentralFreeList一次获取多少个object
  • class_to_pages用来定义CentralFreeList在内存不足时每次从PageHeap获取多少个页
  • 当申请的内存大小大于256K时,不再通过SizeMap预定义分配内存,而是通过PageHeap直接分配大内存。

小内存分配:ThreadCache

tcmalloc实现中,每个thread独立维护了各自的离散式空闲列表,它的核心结构如下:

class FreeList {
private:
 void*    list_;
 uint32_t length_;
 uint32_t lowater_;
 uint32_t max_length_;
};

class ThreadCache {
private:
     FreeList      list_[kNumClasses];    
};

ThreadCache中定义的list_变量即为size class的实现。这里啰嗦下,在实现free list时tcmalloc并没有使用next指针指向下一个位置。而是直接使用了void* list_。这里运用了一种技巧:将每个object的前8个字节存储下一个object地址,这样可以模拟链表实现(object分配给应用程序后前8个字节可以被应用程序覆盖)。 结构图

当通过ThreadCache分配小内存时:

  1. 通过SizeMap查找要分配的内存对应的size class及object size大小。
  2. 查看当前ThreadCache的free list是否为空,如果free list不为空,直接从列表中移除第一个object并返回,由于这个过程中需要获取任何锁,所以速度极快。
  3. 如果free list为空,从CentralFreeList中获取若干个object(具体object个数由慢启动算法决定,防止空间浪费)到ThreadCache对应的size class列表中,并取出其中一个object返回。
  4. 如果CentralFreeList中object也不够用,则CentralFreeList会向PageHeap申请一连串页面(由Span表示,每次申请class_to_pages个),并将申请的页面切割成一系列的object,之后再将部分object转移给ThreadCache。

Span是什么呢?object又是如何组织的呢?从PageHeap及CentralFreeList中找下答案吧。

大内存分配:PageHeap

前面讲过,PageHeap的职能之一是向操作系统申请内存,与大多数现代分配器一样,tcmalloc使用基于页的分配方式,即每次至少像系统申请1页空间。tcmalloc中定义的页大小为8K个字节(多数linux系统中一页大小为4K字节,也就是说tcmalloc中的一页对应linux中两页)。 虽然PageHeap是按页申请内存,但是它管理内存的基本单位为Span(跨度),Span对象代表了表示连续的页面。 如下图所示,分别有a,b,c,d四个Span;a占据了2个页面,b占据了1个页面,c占据了4个页面,d占据了3个页面。 结构图 下面是Span的定义


struct Span {
  PageID        start;          // Span描述的内存的起始地址
  Length        length;         // Span页面数量
  Span*         next;           // Span由双向链表组成,PageHeap和CentralFreeList中都用的到
  Span*         prev;           //
  void*         objects;        // Span会在CentralFreeList中拆分成由object组成的free list
  unsigned int  refcount : 16;  // Span的object被引用次数,当refcount=0时,表示此Span没有被使用
  unsigned int  sizeclass : 8;  // Span属于的size class
  unsigned int  location : 2;   // Span在的位置IN_USE?normal?returned?
  unsigned int  sample : 1;     // Sampled object?
  // What freelist the span is on: IN_USE if on none, or normal or returned
  enum { IN_USE, ON_NORMAL_FREELIST, ON_RETURNED_FREELIST };
};

PS: 上述定义中的objects、refcount、sizeclass属于CentralFreeList中管理的内容,可以先不关注。

以上是Span的概念,那么,PageHeap是如何组织Span的呢?

来看下PageHeap的主要结构及示意图:


PageMap pagemap_; // page id 到 Span的映射

struct SpanList {
   Span        normal;
   Span        returned;
};

SpanList large_;

SpanList free_[kMaxPages]; // kMaxPages = 128

结构图

从PageHeap的主要结构中看到:

  1. PageHeap通过free_数组保存了每个页大小对应的空闲Span双向链表。
  2. 大于kMaxPages页面,统一保存在large_中,不再按照页面数目区分。
  3. Span列表又分为了normal和returned两个部分,其中:
    • normal部分包含的Span,是页面明确映射到进程地址空间的Span。
    • returned部分包含的Span,是tcmalloc已经通过madvise归还给操作系统空间,调用madvise相当于取消了虚拟内存与物理内存的映射。 tcmalloc之所以还保留returned列表,是因为虽然通过madvise归还给了操作系统,但是操作系统有可能还没有收回这部分内存空间,可以直接利用,如果在操作系统回收前tcmalloc重新使用了这些页面,那么系统就不会再进行回收。并且,即使操作系统已经回收了这部分内存,重新使用这部分空间时内核会引发page fault并将其映射到一块全零的内存空间,不影响使用(代价是会影响性能)。

当调用Span* New(Length n) 申请内存时(n代表的是申请分配的页面数目):

  1. free_[kMaxPages]中大于等于n的free list会被遍历一遍,查找是否有合适大小的Span;如果有,则将此Span从free list中移除;如果Span大小比n大,tcmalloc则会将其Carve,将剩余的Span重新放到free_list中。比如,n = 3, 但是系统遍历时发现free_[3]对应的索引已经没有空闲Span了,但是在free_[4]中找到了空闲Span,这时候此Span会被切分成两份:一份对应3个页面,返回给调用方;一份对应1个页面,挂接到free_[1]中,供下次使用。
  2. 如果free_中的normal和returned链表中都找不到合适的Span,则从large_链表中查找大小最合适的Span,这时候需要遍历整个large_的normal和returned列表,时间复杂度为O(n)
  3. 如果large_中也没有可用Span,则通过tcmalloc_SystemAlloc()向操作系统申请,并返回指定大小Span。(每次都会尝试申请至少128页(kMinSystemAlloc),以便下次使用)

当调用Delete(Span* span)时:

  1. 将Span重新放入PageHeap的free list中(如果Span的左右邻居也是空闲的,则将它们从free list中去除,然后合并为同一个Span再挂接到free list)
  2. 检查是否需要释放内存给操作系统,如果需要,则释放。

另外PageHeap还定义了PageMap pagemap_,PageMap是一个radix tree数据结构,保存的是PageID到Span对象的映射,free内存时会用到此映射。

中间人:CentralFreeList

tcmalloc为每个size class设置设置了一个CentralFreeList(中央自由列表),ThreadCache之间共享这些CentralFreeList

  static CentralFreeListPadded central_cache_[kNumClasses];
  class CentralFreeList {
  private:
      SpinLock lock_;
      size_t size_class_;
      Span empty_;       
      Span nonempty_;
  };

结构图

作为中间人,CentralFreeList的功能之一就是从PageHeap中取出部分Span并按照预定大小(SizeMap中定义)将其拆分成大小固定的object供ThreadCache共享; CentralFreeList从PageHeap拿到一个Span后:

  1. 通过调用PageHeap::RegisterSizeClass()将Span中的location填充为”IN_USE”,并将sizeclass填充为指定的值
  2. 通过SizeMap获取size class对应的object大小,然后将Span切分,通过 void* objects保存为object的free list。
  3. 将Span挂接到nonempty_链表中。

每当ThreadCache从CentralFreeList获取object时:

  1. 从nonempty_链表中获取第一个Span,并从此Span种的objects链表中获取可用object返回,每分配一个object,Span的refcount + 1。
  2. 当Span无可用object时,将此Span从nonempty_链表摘除,挂接到empty_链表(object重新归还给此Span时会从新将其挂载到nonempty_链表)

当ThreadCache归还object给CentralFreeList时:

  1. 找到此object对应的Span,挂接到objects链表表头,如果Span在empty_链表,则重新挂接到nonempty_链表
  2. Span的refcount–。如果refcount变成了0,表示此Span所有的object都已经归还,将此Span从CentralFreeList的链表中摘掉,并将其退还给PageHeap。(pageheap->Delete(Span))

至此,tcmalloc的核心结构分析完成。

参考

1.tcmalloc 官方文档

2.Post-Mortem Heap Analysis: tcmalloc

3.内存分配器

4.各种内存动态分配算法总结

5.jemalloc在facebook的应用

6.jemalloc论文

7.tcmalloc源码分析

8.Anatomy of a Program in Memory

9.How the Kernel Manages Your Memory

10.ptmalloc介绍 GLibC Malloc for Exploiters: Leak It, Write It, Become a Wizard - Yannay Livneh

11.What Programmers Should Know About Memory Allocation


Custom Theme JavaScript