jemalloctcmalloc,tcmalloc内存池

最近学习了tcmalloc的结构。 这是go中使用的内存分配机制。 本文以tcmalloc为参考，加入一些自己的理解。

tcmallocvsptmalloc (glibc 2.3 malloc )对于小内存，TCmalloc通过提供线程级内存分配来减少线程之间的争用。 ptmalloc2也提供线程级分配，但其内存分配给一个线程后，无法重新分配给另一个线程。 这会浪费很大的资源。 对于大容量内存，tcmalloc也采用了精细高效的分配策略。

在2.8 GHz P4环境下，tcmalloc执行小存储器malloc/free的时间约为50ns，小于ptmalloc2的300ns。

另外，关于空间利用，tcmalloc多余的空间很少，n个8字节对象占有的总空间约为8N*1.01，而ptmalloc2用4字节管理各个对象，因此空间利用率很小。

小内存分配和回收线程维护着用于小内存分配的cache。 如果需要请求内存，请先从线程cache分配，如果不够，则从Central Heap的central free lists分配。 另外，tcmalloc执行定期的垃圾回收，回收线程cache内的过剩内存并放入central free lists。

tcmalloc大约有88种大小的内存块(size-class )，小于1个块的大小会产生碎片性的浪费，但由于tcmalloc并不完全按2的指数倍分配，因此浪费的空间并不是那么大例如，如果内存块大小为8、16、32、48、64、80，而请求区域为70，则分配块大小为80即可，而无需分配128来浪费较大的碎片。 所有空闲块(class )都在单链表中维护，因此在使用时，只需直接从对应的链表中取出即可。

大致的分配策略如下

根据申请的大小，找到相应的块大小size-class。 如上图所示，如果在线程高速缓存链表中查找相应块大小的可用内存块的链表不为空，则返回。 线程内部没有冲突，所以不需要锁定。 如果链表为空

在central free lists中找到与size-class相对应的链表空闲块后，其结构与图线程缓存中的链表相匹配。 从central free lists自由链表中找到的空闲块放在线程高速缓存链表中，并从线程高速缓存链表返回到central free lists中相应的链表中

分配页面，将该页面划分为所需的多个size-class块，并将块放置在central free lists的空闲链表中。 将central free lists的空闲链表的一部分空闲块移动到线程缓存的链表中并从线程缓存的链表中返回，多级分配的优点是第一级是线程内部资源，锁定优先权是性能

线程的内部链表应该有多长？ 如果小的话，就会从Central free list继续申请，如果引起竞争的大的话就会浪费。 分配策略采用慢启动增长的方式，防止了大量分配申请导致的系统抖动。 伪代码如下。

starteachfreelistmax _ length at1.allocationiffreelistempty { fetch min (max _ length，num _ objects _ to _ move ) from }超过}else{//num_objects_to_move时max_length =num_objects_to_move； } deallocationiflengthmax _ length {/don ' ttrytoreleasenum _ objects _ to _ moveifwedon ' thavethatmany.release mini num _ objects _ to _ move (objectststocestoced ) h长度//slove继续增长} else if max _ length num _ objects _ to _ move {/ifweconsistentlygoovermax _ length，shrink max _ th ifoverageskmaxoverages { max _ length-=num _ objects _ to _ move； overages=0； }

  中内存指的是大小为256KB到1MB的大小，将会分配多个页，Central Heap以8k为一个页。Central Heap有一个包含128个链表的heap，链表大小从1个页到128个页。那么，如果申请的空间需要多少个page则从heap对应项中的链表中取出一个，如果该链表为空，则从下一个链表寻找（将会导致重新划分，比如需要4个页，但是4 pages链表为空，则从5pages中拿一个，但是5pages应该拆分为2部分，一个为4page，一个为1page）。如果都不满足需求，则视为“大内存”分配。
  注意，中内存不是从线程缓存中分配，而是直接在CentralHeap。

  大内存指的是大于1MB的块，这个将会从红黑树中进行分配。tcmalloc维护了一个红黑树用于标记不同的span，如果需要则从树种找到一个满足条件的最小的span进行分配。这可能导致span进行重新划分，一部分用于分配申请的大小，另外多出的部分可能重新放入到红黑树，也可能放入全局Centeral Heap的center free-lists（上图所示）。如果红黑树中找不到满足的span，则从系统中进行申请（tcmalloc采用sbrk和mmap）

  span对象负责管理连续的多个页，比如下图，a，b，c，d是4个span，管理不同大小的连续页。
  所有span组成一个span lists，span内部划分给多个对象使用，参加下图，图来自图解 TCMalloc
  一个span可能被分配或者释放。如果释放了，挂入到page heap的链表中。如果申请了，可能作为大内存被分配，也可能被划分后进行分配，比如划分为多个小内存。如果被划分成小内存，则内部会记录各个size-class的分配情况。
  同样还是上面第一个图，可以用一个数组记录各个页分别属于哪个span。但是这样对空间消耗比较大，每一块内存都需要一个数组元素表示，tcmalloc用基数radix tree（前缀树/字典树trie tree的一种压缩优化）记录映射情况，这样可以对前缀相同部分进行压缩。如果是32位系统，则树高2层，根节点包含了32项，叶子节点包含2^14项，则对32位系统来说，可以记录2^19个页（2^19 * 8k=2^32）。如下图所示，采用基数而不是前缀树的原因是为了空间压缩，如果是前缀树，则需要2^32 * 2 - 1=2^33-1个结点，就算结点内只有一个值和一个指针，存储这么多指针也需要浪费很多的空间。下图是手绘的radix tree示意图。
  对于64位系统，则树高3层。

  当一个对象被释放后，通过计算页号，再通过radix tree得知所在的span，span可以知道是否为小内存，如果是的话还知道size-class（span内部维护该信息）。当然，在开始的时候说过，如果是小内存，释放会挂入线程内部的缓存链表，知道链表大小超过了阈值则会回收到central free lists。当然central free lists也可能发生回收，属于一个span的内存全部空闲后，将会触发回收。
  如果是大内存，则通过span获取页跨度，假设为[p,q]，那么寻找p-1和q+1所在的span是否为空，如果都为空，则进行合并后放入page heap（上面提到的红黑树）。

  上面我们提过，我们在central free lists中保存了不同size-class小内存用于二次分配。每个central free lists由二级结构组成，第一级是span，第二级是span内空闲空间组成的链表，保存小内存地址。如果线程内部小内存不够用，就从这里进行分配。如果线程内部小内存过多就行回收，也挂入这里的链表。如果一个span内的内存全都回收后，该span也将进行回收，放入到全局的page heap中。

  在开始讲小内存的伪代码中已经介绍过垃圾回收的机制。当线程缓存超过max_size以后，将会触发回收。垃圾回收只有在对象释放的时候才会发生。用户可以通过控制tcmalloc_max_total_thread_cache_bytes来控制num_objects_to_move的大小。每次垃圾回收，线程将尝试将自己的max_size变大。如果回收时max_size小于tcmalloc_max_total_thread_cache_bytes，那么max_size将会直接增长；反之，则会促使从别的线程中偷取max_size。
此处存在一个疑问：这种机制将会导致max_size超过tcmalloc_max_total_thread_cache_bytes，和上面伪代码中的收缩机制有什么区别？什么时候用收缩，什么时候从别的线程进行偷取？

转载请注明链接：http://vinllen.com/tcmallocqian-xi/

https://gperftools.github.io/gperftools/tcmalloc.html
https://github.com/gperftools/gperftools/blob/master/src/tcmalloc.cc
https://zhuanlan.zhihu.com/p/29216091