tcmalloc浅析

  1. 云栖社区>
  2. 博客列表>
  3. 正文

tcmalloc浅析

七伤 2016-02-19 15:11:56 浏览9848 评论0

摘要: 最近因debug需要,阅读了一下慕名已久的tcmalloc,略记一些自己的理解。 一图胜千言: 总体结构 在tcmalloc内存管理的体系之中,一共有三个层次:ThreadCache、CentralCache、PageHeap,如上图所示。

最近因debug需要,阅读了一下慕名已久的tcmalloc,略记一些自己的理解。
一图胜千言:
_2014_05_21_10_17_40

总体结构

在tcmalloc内存管理的体系之中,一共有三个层次:ThreadCache、CentralCache、PageHeap,如上图所示。
分配内存和释放内存的时候都是按从前到后的顺序,在各个层次中去进行尝试。基本思想是:前面的层次分配内存失败,则从下一层分配一批补充上来;前面的层次释放了过多的内存,则回收一批到下一层次。
这几个层次从前到后,主要有这么几方面的变化:

  1. 线程私有性:ThreadCache,顾名思义,是每个线程一份的。理想情况下,每个线程的内存需求都在自己的ThreadCache里面完成,线程之间不需要竞争,非常高效。而CentralCache和PageHeap则是全局的;
  2. 内存分配粒度:在tcmalloc里面,有两种粒度的内存,object和span。span是连续page的内存,而object则是由span切成的小块。object的尺寸被预设了一些规格(class),比如16字节、32字节、等等,同一个span切出来的object都是相同的规格。object不大于256K,超大的内存将直接分配span来使用。ThreadCache和CentralCache都是管理object,而PageHeap管理的是span。

ThreadCache

比较简单,最主要的逻辑是维护一组FreeList,针对每一种class的object;

CentralCache

里面有多个CentralFreeList,针对每一种class的object。
CentralFreeList并不像ThreadCache那样直接维护object的链表,而是维护span的链表,每个span下面再挂一个由这个span切分出来的object的链。这样做便于在span内的object是否都已经free的情况下,将span整体回收给PageHeap(span.refcount_记录了被分配出去的object个数)。但是这样一来,每个回收回来的object都需要寻找自己所属的span,然后才能挂进freelist,过程会比较耗时。
所以CentralFreeList里面还搞了一个cache(tc_slots_),回收回来的一批object先往cache里面塞,塞不下了再回收进span的objects链。分配object给ThreadCache时也是先尝试在cache里面拿,没了再去span里面分配。
多少个object算做是一批?这都是预定义好的(称作batch_size,比如32个),不同的class可能有不同的值。ThreadCache向CentralCache分配和回收object时,都尽量以batch_size为一个批次。而为了cache的简单高效,如果批次个数不等于batch_size,则会绕过cache。
另外,CentralFreeList里的span链表其实是有两个:nonempty_和empty_,根据span的objects链是否有空闲,放入对应链表。这样就避免了在分配时去判断span是否为空,只需要在由空变非空、或者由非空变空时移动一下span。

PageHeap

维护了两个很重要的东西:page到span的映射关系,和空闲span的伙伴系统。

当应用free()一个地址的时候,怎么知道该把它对应的object放回哪里去呢?tcmalloc里面并没有针对object的控制结构,要解决这个问题,page到span的映射关系至关重要。地址值经过地址对齐,很容易知道它属于哪一个page。再通过page到span的映射关系就能知道object应该放到哪里。span.sizeclass记录了span被切分成的object属于哪一个class,那么属于这个span的object在free时就应该放到ThreadCache对应class的FreeList上面去;如果object需要放回CentralCache,直接把它挂到对应span的objects链表上即可。

page到span的映射关系通过radix tree来实现,逻辑上可以把它理解为一个大数组,以page的值作为偏移,就能访问到page所对应的节点。这个节点上面其实就是一个指针,指向这个page所对应的span(注意,可能有多个page指向同一个span,因为span的尺寸可能不止一个page)。
为减少查询radix tree的开销,PageHeap还维护了一个最近最常使用的若干个page到class(span.sizeclass)的对应关系cache。为了保持cache的效率,cache只提供64K个固定坑位,旧的对应关系会被新来的对应关系替换掉。

空闲span的伙伴系统为上层提供span的分配与回收。当需要的span没有空闲时,可以把更大尺寸的span拆小(如果大的span都没有了,则需要重新找kernel分配);当span回收时,又需要判断相邻的span是否空闲,以便将它们组合。判断相邻span还是要用到radix tree,radix tree就像一个大数组,很容易取到当前span前后相邻的span。
span的尺寸有从1个page到255个page的所有规格,所以span总是可以按任意尺寸进行拆分和组合(当然是page粒度的)。大于255个page的span单独归为一类,不作细分。

伙伴系统的freelist其实是有两个链,normal和returned,以区别活跃跟不活跃的内存。PageHeap并不会将内存释放给kernel,因为它们之间的交互都是针对一批连续page的,要想回收到整批的page,可能性很小。在PageHeap里面,多余的内存会放到returned里面去,跟normal做一下隔离。这样一来,normal的内存总是优先被使用,kernel倾向于一直保留它们。而returned的内存则不常被使用,kernel在内存不够的时候会优先将它们swap掉。
其实不用returned也能完成这样的事情,因为normal是个链表,每次分配回收总是作用在链表头上,那么链表内的span本身就按从热到冷的顺序排序了。链表尾部的span如果长期不被使用,不管是否移动到returned链,kernel都会倾向于将它们swap掉。不过,span进入returned时,tcmalloc还附加了一个操作,madvise(MADV_DONTNEED),试图告诉kernel这个内存已经不用了(kernel具体会怎么做,那就是另外一回事了)。
所以,在伙伴系统中分配span时,会有三个过程:优先在normal链中分配、尝试未果则在returned链中分配、还搞不定就向kernel去申请新的内存。

在PageHeap里面,还有一个PageHeapAllocator,专门用于分配各种控制结构的内存,比如span、ThreadCache、等。可见,在tcmalloc里面控制结构与object是分离的。而object自身并不需要额外的控制结构,当它被分配时,它的所有内存空间都服务于使用者;而当它空闲时,它的第一个8Byte空间被当作链表指针,链在各种freelist里面。

分配回收过程

再通过malloc和free两个过程把上述逻辑串起来看一看:

alloc

  1. 根据分配size,判断是小块内存还是大块内存(256K为界);
  2. 小块内存:
    1. 通过size得到对应的class;
    2. 先尝试在ThreadCache.list_[class]的FreeList里面分配,分配成功则直接返回;
    3. 尝试在CentralCache里面分配batch_size个object,其中一个用于返回,其他的都加进ThreadCache.list_[class];
    4. 拿到class对应的CentralFreeList;
    5. 尝试在CentralFreeList.tc_slots_[]里面分配(CentralFreeList.used_slots_是空闲slot游标);
    6. 尝试在CentralFreeList.nonempty_里面分配,尽量分配batch_size个object。但最后只要分配了多于一个object,即可返回;
    7. 如果CentralFreeList.nonempty_为空,则要向PageHeap去申请一个span。对应的class申请的span应该包含多少个连续page,这个也是预设好的。拿到span之后将其拆分成N个object,然后返回前面所需要的object;
      1. PageHeap先从伙伴系统对应npages的span链表里面查找空闲的span(优先查normal链、然后returned链),有则直接返回;
      2. 在更大npages的span里面查找空闲的span(优先查normal链、然后returned链),有则将其拆小,并返回所需要的span;
      3. 向kernel申请若干个page的内存(可能大于npage),返回所需要的span,其他的span放回伙伴系统;
  3. 大块内存:
    1. 直接向PageHeap去申请一个刚好大于等于请求size的span。申请过程与小块内存走到这一步时的过程一致;

free

  1. 通过释放的ptr,在PageHeap维护的映射关系中,找到对应span的class(先尝试在cache里面找,没有再查radix tree,然后插入cache。cache里面自动淘汰老的项)。class为0代表ptr指向的是大块内存;
  2. 小块内存:
    1. 将ptr指向的内存释放到ThreadCache.list_[class]里面;
    2. 如果ThreadCache.list_[class]长度超过阈值(FreeList.length_>=FreeList.max_length_),或者ThreadCache的容量超过阈值(ThreadCache.size_>=ThreadCache.max_size_),则触发回收过程。两种情况分别针对class对应的FreeList,和ThreadCache下面的所有FreeList进行回收(具体的策略后续再讨论);
    3. object被回收到CentralCache里面class对应的CentralFreeList上。先尝试batch_size个object的整块回收,CentralFreeList会试图将其释放到自己的cache里面去(tc_slots_);
    4. 如果cache装满,或者凑不满batch_size个整数的object,则单个回收,回收进其对应的span.objects。这个回收过程不必拿着object在CentralFreeList的span链表中逐个去寻找自己对应的span,而是通过PageHeap中的对应关系直接找到span;
    5. 如果span下面的object都已经回收了(refcount_减为0),则进一步将其释放回PageHeap;
      1. 在radix tree中找到span之前和这后的span,如果它们空闲且也在normal链上,则进行合并;
      2. PageHeap将多余的span回收到其对应的returned链上,然后继续考虑span之间的合并(要求span都在returned链上)(具体策略后续再讨论);
  3. 大块内存:
    1. ptr对应的直接就是一个span,直接将其释放回PageHeap即可;

回收策略

tcmalloc的主要数据结构基本上就是这些了。上面讨论的时候,有一个细节一直没深入:每一个层次在空闲量达到一定阈值的时候,会向下做一次释放。那么这个阈值该怎么定呢?

CentralCache => PageHeap

span从CentralCache回收到PageHeap的过程比较简单,只要一个span里面的object都空闲了,就将它回收到PageHeap;

normal => returned

在PageHeap中,span从normal链表回收到returned链表的过程则略复杂一些:
考虑到这个过程是很偏避的一个逻辑,span是否移到returned链表对整体性能而言差别并不会太大,所以尽量lazy。基本思路是,每当PageHeap回收到N个page的span时(这个过程中可能伴随着相当数目的span分配),触发一次normal到returned的回收,只回收一个span。
这个N值初始化为1G内存的page数,每次回收span到returned链之后,可能还会增加N值,但是最大不超过4G。
触发回收的过程也比较简单,每次进来轮询伙伴系统中的一个normal链表,将链尾的span回收即可。
这里面没有判断normal链是否应该被回收,如果回收了不该回收的span,后续的分配过程会把span从returned链里面捞回来。否则span将长期呆在returned链里面。

ThreadCache => CentralCache

ThreadCache是tcmalloc的核心,它里面的FreeList长度控制还是比较复杂的。
前面提到过,FreeList长度超过限额和ThreadCache容量超过限额,这两种情况下会触发object回收。考虑到应用程序的多样性,这两个限额不能是定死的,必需得自适应:有些线程对内存的需求可能远多于其他一些线程、有些线程可能总是在分配内存而另一些线程则总是释放内存(生产者消费者)、等等。

先来看ThreadCache的容量限额,其思想是:为每一个ThreadCache初始化一个比较小的限额,然后每当ThreadCache由于cache超限而触发object到CentralCache的回收时,就增大该ThreadCache的限额。有限额增大,就应该有限额回收。tcmalloc预设了一个所有ThreadCache的总容量,当ThreadCache需要增大容量时,如果总容量尚有余额,则使用这些余额。否则需要增大的容量就从其他线程的ThreadCache里面去收刮(具体从收刮哪个线程的容量,简单采用了轮询的方式)。这样一来,只需要在ThreadCache内存回收时做一些简单的处理,就能实现ThreadCache的容量的自适应:内存需求大的线程总是收刮别人的容量,而内存需求低的线程则总是被收刮。当然,收刮与被收刮并不是无节制的,会有一个最大值最小值的限制,比如128字节~4M。
到达ThreadCache的容量限额时,会对它下面的每一个FreeList进行回收,回收的数目是该Freelist.lowator_的一半。什么是lowator_呢?就是该Freelist在ThreadCache超限的两次回收周期之间内,FreeList的最小长度。也就是说,在上一个周期中,FreeList里面有lowator_个object是从未被用到的。通过这一历史信息,可以预估在下一次回收到来时,可能也有lowator_个object可能不会被用到。不过保守一点,只回收lowator_的一半。
回收过程其实只是对每一个FreeList的保守回收,回收完成之后ThreadCache的容量可能还会继续高于限额,不过随着这次回收,ThreadCache的容量限额也会被抬高。

下一个问题是单个FreeList的限额,tcmalloc采用慢启动策略,每个FreeList初始时长度限额为1。在限额为1~batch_size之间时,为慢启动状态。此时,不管是alloc遇到空FreeList、还是free遇到长度超限,都给限额加1。这样做可以给不常用或者使用很规律的object确定一个合适的限额,而如果object的使用抖动较大的话,应该给它一个更大的buffer。
如果限额增加达到batch_size,则慢启动状态结束。此时,如果alloc遇到空FreeList,限额会按batch_size的整数倍进行扩展。而如果free超限,则限额将按照batch_size的整数倍进行缩减。
alloc遇到空FreeList(说明FreeList的限额达不到线程的分配需求),应该不断增加限额,这个好理解。那么free超限的情况下,为什么慢启动状态下要增加限额,非慢启动状态则要减少限额呢?如果free总是超限,说明线程对object的free要多于alloc,线程之间对该object的分配回收很可能是不对称的。那么作为专职回收的那个线程,没必要给他留大的限额,因为它的分配需求很少。而慢启动状态下超限还给限额做加1递增,一方面可以应对抖动,另一方面递增限额的目的是使之能够达到batch_size(如果free确实远多于alloc话),从而在回收object时可以按batch_size批量回收。
FreeList限额超限的处理比较简单,直接回收batch_size个object即可(不足batch_size个,则有多少回收多少)。可见,处于慢启动状态下的FreeList限额超限,将导致FreeList被清空。

用云栖社区APP,舒服~

【云栖快讯】诚邀你用自己的技术能力来用心回答每一个问题,通过回答传承技术知识、经验、心得,问答专家期待你加入!  详情请点击

网友评论

七伤
文章63篇 | 关注38
关注
一站式提供企业即时通讯、销售管理、协同办公。 查看详情
基于深度学习技术及阿里巴巴多年的海量数据支撑, 提供多样化的内容识别服务,能有效帮助用户降低... 查看详情
阿里云数据库内置的智能专家,提供云数据库问题诊断、性能优化、SQL分析、资源分析、优化报告等... 查看详情
为您提供简单高效、处理能力可弹性伸缩的计算服务,帮助您快速构建更稳定、安全的应用,提升运维效... 查看详情
阿里云9.10会员日

阿里云9.10会员日