Frank__Library / 内存池 / TCMalloc源码学习(一)

分享

   

TCMalloc源码学习(一)

2016-08-11  Frank__Li...

打算一边学习tcmalloc的源码一边写总结文章。先从转述TCMalloc的一篇官方文档开始(TCMalloc : Thread-Caching Malloc)。

 

为什么用TCMalloc

TCMalloc比glibc 2.3 的malloc(是一个单独的库叫做ptmalloc2)和其他测试过的malloc都要快。TCMalloc致力于减少多线程对锁的竞争,在获取小的内存对象时候基本上不需要锁,在获取大的内存对象时候,TCMalloc使用了细粒度的高效率的spinlocks。ptmalloc2当然也有做减少线程间对锁进行竞争的努力,它每一个线程都有一个areans,彼此互不关联,这样显然有个问题就是一个线程释放的内存另外一个线程无法使用,只能新申请内存,如此下去,内存只会暴涨了。TCMalloc另一个优点是非常高效的空间利用率,例如在分配N个8 bytes的objects内存的时候,大约最多只会有8N *0.01 bytes(其实是8N / 7),后面源码分析会解释)的overhead,相比之下ptmalloc则是每一个object用了4bytes头,overhead总共达到了N*4 bytes。

 

用法(略)

原理概述

overview

TCMalloc给每一个线程也分配一个线程本地的cache。然后小对象的分配都是从这个cache中获取。而线程本地的cache又是按需从所有线程共享的一个central heap中获取的。周期的垃圾回收可以把部分内存从线程本地的cache挪回central heap,达到内存分配在多个线程中按需调度的目的。

TCMalloc对待大的内存(文章说大于32K,但其实看代码应该是大于256K的内存)的分配是直接从central heap中使用页层级的分配器(一页内存就是按照 4K 对齐的内存区域)分配的,也就是一个大的对象地址总是按页对齐横跨多个页。

在central heap中内存也是按页向系统请求分配的,而这些页内存通常会被裁剪成许多小对象,例如一页4K的内存能够被裁减成32个大小为128字节的objects。

 

小对象的分配

每一个小对象对应了一个大约有60项的map中的一项。每一项代表了包含这个size的内存,程序中用了一个链表把该size的可用的object串起来,总的来说这个map就是线程本地cahche。map中的表项按照尺寸划分的,对于前面小一点的size是每8个字节增加一项,大一点的就是16字节,具体的哪一个size对应哪一项,程序中有注释如下:

// 
// Examples: 
//   Size       Expression                      Index 
//   ------------------------------------------------------- 
//   0          (0 + 7) / 8                     0 
//   1          (1 + 7) / 8                     1 
//   ... 
//   1024       (1024 + 7) / 8                  128 
//   1025       (1025 + 127 + (120<<7)) / 128   129 
//   ... 
//   32768      (32768 + 127 + (120<<7)) / 128  376

 

线程本地的cache每一个size对应的Index中放置的是一个linklist,叫做free list,把可用的object内存串起来了。

threadheap 

 

分配小对象的过程是:(1)找到要分配的size对应cache表中的那一项;(2)在线程本地的cache中即size对应的free list中寻找可用内存;(2)假如free list不是空的就取出第一个object返回,这个过程不需要锁;

假如free list是空的,则进行以下步骤:(1)从对应size项的central free list中(这个是所有线程共享的)提取一些对象内存;(2)提取到的一些对象内存放到对应的线程本地free list项中;(3)从新提取的一些对象中获取一个对象作为返回值。

假如central free list中可用内存也是空的,则(1)从central page allocator中分配出一些页内存;(2)把这些页内存划分成一个一个object内存;(3)把这些新的objects挂在对应的central free list上;(4)参照之前,从其中移动一些内存到线程本地free list中。

 

大对象的分配

大的内存分配是按页直接从central heap page获取的。central heap page也是一个free list数组,第n项代表数个n页内存串起来的链表。

pageheap

      • 分配k pages的内存就直接从数组的第k项的free list找可用内存,如果是空的就从下一项找,一直等到找到再返回,如果这样还是找不到,就要找系统去申请内存了(sbrk,mmap,。。。)。假如在一个大于k的free list中找到了空闲内存,多出来的内存要再插到数组合适的位置中去。
    • Spans

      一个 Span 对象代表一些连续页内存,具体来说就是它在central heap page中是某一个free list中的节点,也是central free list某一个free list中的节点。在后者中,他还会把自己代表的页内存划分成对应size的一个一个objects,并用链表方式串起来,并等待线程本地cache去获取。

      TCMalloc还有一个所有线程共享的数据结构就是一个map(文中叫做 central array),记录某一个页内存的页号具体对应哪一个span:

      Image

      一个32位的系统共有4GB的虚拟地址空间,总共对应2^20 4K页,所以这个map最多占用4M的内存,看起来还可以接受。但是在64位的系统上就不行了,所以64位系统我们使用radix tree来代替数组实现这样的map。

       

    • 内存释放

      当释放一个内存对象的时候,我们算出他所在页的页号,然后在central array中找到该页号对应的Span,Span可以获取对应的sizeclass,然后可以知道是小内存对象还是大内存对象。假如是小块内存对象,把其插入线程本地的合适的free list中,假如线程本地cache超过了一个指定的大小(默认是2MB),垃圾收集器这时候会启动起来把没有在使用的objects从线程本地cache挪动到central free lists中。

      假如是大块的内存对象,Span同时可以获取这个object占据的连续页内存,比如是占据了 [p,q]页,我们也会判断第p-1,q+1页,假如他们是空闲的,可以和[p,q]页合并,然后插入到central page heap的合适free list中。

 

管理小内存对象的Central Free Lists

Central Free Lists是一个Free list的链表数组,代表着每一个szie类别当前可用的内存,free list的每一个节点是Span,Span内部则又是一些objects构成的链表。

内存在线程本地的Cache和Central Free List之间的移动是以这些object为单位的,从Central Free list申请内存,会从中移动适量个数的object到线程本地Cache,线程本地Cache返还内存时,也会把这些objects放到Central Free list原来所在的Span中去。

当Span每分配出一个object就增加一个引用计数,每被返还一个object就释放一个引用计数,在返还时如果引用技术为0,即没有地方在引用这个Span了,这时就会把Span所占用的页直接释放回heap page。

 

线程本地Cache的垃圾回收

前面也已经提过,当一个线程本地的Cache其超过2MB后会被垃圾回收的。垃圾回收的这个阈值也会随着线程个数的增加而降低,因为这样可以减少应用程序对内存过度的使用。

垃圾回收时决定在一个free list中回收多少个内存对象是由每个size对应的free list的低水位线 L 控制的。L 记录了上次垃圾回收时这个free list的最小长度,每次回收 L/2 个内存对象。这种使用历史记录作为对未来预测的算法有比较好的效果,使得不同size的内存对象可以比较快速的在各个线程中交换使用。

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息,谨防诈骗。如发现有害或侵权内容,请点击一键举报。

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多
    喜欢该文的人也喜欢 更多

    ×
    ×

    ¥.00

    微信或支付宝扫码支付:

    开通即同意《个图VIP服务协议》

    全部>>