本文主要是对于TCMalloc内存分配论文的学习， 英文论文Thread-Caching Malloc见地址：http://goog-perftools.sourceforge.net/doc/tcmalloc.html

Motivation

根据我已做的测试，TCMalloc比gclib2.3里面的malloc(ptmalloc2)和其余的mollocs速度更加的快。在2.8GHz的处理器上，针对小对象(小于32Kb)ptmalloc2做一次malloc/free的操作，需要大概300ns，而TCMalloc同样的操作需要大约50ns。由此可见TCMalloc的速度优势。

在多线程环境下，TCMalloc可以极大减少锁资源的争夺。针对small object，TCMalloc几乎就是lock free的。针对large object，TCMalloc采用高效的细粒度的自旋锁。

ptmalloc2也使用线程私有内存区域来减少锁的竞争，但是有一个很严重的问题，ptmalloc2线程私有的内存区域不能从一个线程私有内存区域移动到另外一个线程私有内存区域，这会造成很严重的内存浪费。例如，在一个谷歌应用程序中，第一阶段将为其数据结构分配大约300MB的内存。当第一阶段完成时，第二阶段将在相同的地址空间中启动。如果将第二个阶段分配到的内存区域与第一个阶段所使用的内存区域不同，那么第二阶段将不会重用第一个阶段之后剩下的任何内存，并将向地址空间添加另一个300MB。在其他应用程序中也发现了类似的内存爆炸问题。

Overview

TCMalloc为每个线程指定了一个thread local cache，小对象的内存分配直接走thread local cache。 根据需要，将对象从central data structures 移动到thread local cache，并且使用定期garbage collection将内存从thread local cache迁移回central data structures。

TCMalloc默认将size小于32KB的对象称作small object, 大于32KB的对象叫做large object。 针对large object，TCMalloc直接从central heap以 page-level 分配器分配large object。 page是一个以4KB对齐的内存区域，也就是说large object总是与page对齐的，并且占用完整的page number。

一组page可以被分割成一系列大小相同的小对象。比如一个4KB的page可以被分割成32个128byte的对象。

Small Object Allocation

每个待allocated small object的size会向上映射到大约170个可分配的大小类中的一个。比如，size在961 to 1024 bytes的object都会映射到1024 bytes size 的对象上。这些170个可分配的大小类的增长不是以2的次幂上升的，而是以8，16，32，48等梯度空间上升的，当size大于2kb时候上升梯度是256 bytes。

一个thread local cache一般情况下是如下图所见的数据结构，是一个包含每个size-class的空闲对象的单链表数组。

allocating small object pipeline:

1. 根据其大小映射到相应的size-class。
2. 在当前线程的thread lcoal cache寻找size-class对应的free list。
   1. 如果size-class对应的free list非空，我们从free list取出第一个对象并返回，当使用这种方式allocate时候，TCMalloc根本不会获得锁。这大大加快了分配速度。(lock free)
   2. 如果size-class对应的free list为空：
      1. 我们从这个size-class的central free list中获取一组对象(central free list由所有线程共享)。
      2. 将这组对象放在thread local free list中。
      3. 将新获取的对象之一返回到应用程序。
   3. 如果size-class对应的free list为空，且central free list也为空：
      1. 我们从central page allocator 分配a run of pages;
      2. 分割a run of pages成一组size-class的对象；
      3. 将分割的新对象放在central free list；
      4. 如前2.2所述，将central free list其中一些对象移动到thread local free list中。

Large Object Allocation

A large object是指size>32K的对象，large object分配时会向上对齐到page的大小4KB，也就是说large object对象分配时的大小一定是大于32KB且为4KB整数的大小。 large object的分配由central page heap处理。

central page heap也是一个free list array数组。对于数组索引i<256，第k项是由k个page为一个实体组成的free list。第256项是长度为>= 256个page的free list。见下图：

通过查询第k个free list是否为空来分配k个page的large object。如果free list为空，我们将查看下一个free list，以此类推，直到我们查看最后一个空闲列表。如果到最后一个free list也没找到合适的内存，我们将从system memory中获取内存(使用sbrk、mmap或通过映射/dev/mem的各个部分)。

如果分配k个page大小的object的由长度为大于k的free list来执行最后分配，则free list的其余部分将重新插入到页面堆中的适当空闲列表中。

根据前面的分析，我们直到现在已知的缓存已经有 thread-local cache、central free list(shared by thread)、central page heap。 也就是三级缓存。

Spans

TCMalloc管理的heap由一系列的page组成。一系列连续的page可以用一个span来表示，一个span既可以被allocate，也可以被free。

1）如果是free，那么span就是一个实体，这个实体在一个page链表的堆中。
2）如果是allocate，那么这个span要么是一个传递给app的large object，要么就是已经被分割成一系列小对象的一组page。如果拆分为small object，那么对象的size-class将记录在span中。

我们可以使用按页码索引的central array来查找page所属的span。如下图，span a占用2页，span b占用1页，span c占用5页，span d占用3页。

在64位机器上，我们使用3-level radix tree而不是数组来将页码映射到相应的span指针。

Deallocation(释放)

当我们释放一个对象的时候，我们计算这个对象的page number并在central array中查找到它，以找到这个对象相应的span对象。span告诉我们对象是否是small object，以及它的size-class是否是small。

1）如果释放的是一个small object，那么我们就将它插入到thread-local cache里面合适的free list。如果thread-local cache现在超过了预定的大小(默认为2MB)，我们将运行一次garbage collection，将未使用的对象从thread-local cache移动到central free list。

2）如果释放的是一个large object，那么span告诉我们对象所覆盖的页面范围。假设这个范围是[p,q]，我们还查找p-1和q+1页的span。如果这两个相邻的span的空间都是自由的，我们就把它们和[p,q]页的span结合起来一起释放。生成的最终的span被插入到central page heap中适当的free list。

Central Free Lists for Small Objects

如前所述，我们为每个size-class保留一个central free list。每个central free list都由两层数据结构组成:一组span 以及每个span的free object list。

通过从某个span的链表中删除第一个条目，可以从central free list中分配对象。(如果所有span都是空链表，那么首先从central page heap中分配适当大小的span。)

通过将对象添加到span包含的链表中，可以将其返回到central free list。如果链表长度现在等于span中小对象的总数，那么这个span现在是完全空闲的，并返回到central page heap。

Garbage Collection of Thread Caches

当线程缓存中所有对象的大小加起来超过2MB时，需要对其进行垃圾收集。随着线程数目的增多，垃圾收集的阈值是会自动减少的，因此在存在大量内存的时候，我们的程序不会浪费过量的内存。

我们遍历缓存中的所有空闲链表，从中移动一定数量的对象到对应的中央链表中。每个链表的低水位标记L决定了从空闲链中移出对象的数量。L记录了自从上一次垃圾收集操作之后本链表的最小长度。注意我们可以缩短链的长度，通过在前一次垃圾收集时移走L个对象，并且没有从中央链中获取其他对象。我们使用这个过去的记录来预测未来的情况，从线程缓存中移走L/2个对象到中央链表中。这个算法性能良好，如果一个线程停止使用某个特定大小的对象，该大小的所有对象将会很快的从线程缓存中迁移到中央空闲链中，以便被其他线程来使用。