18张图解密新时代内存分配器TCMalloc
source link: http://tigerb.cn/2021/01/31/go-base/tcmalloc/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
18张图解密新时代内存分配器TCMalloc
本系列基于64位平台、1Page=8KB
今天我们开始拉开《Go语言轻松系列》第二章「内存与垃圾回收」的序幕。
关于「内存与垃圾回收」章节,大体从如下三大部分展开:
- 知识预备:为后续的内容做一些知识储备,知识预备包括
- 指针的大小 点击此处查看本文
- Tcmalloc内存分配原理(本篇内容)
- Go内存设计与实现
- Go的垃圾回收原理
我们的主要目的是掌握Go语言的内存分配原理。但是呢,Go语言的内存分配主要是基于Tcmalloc内存分配器实现的。所以,我们想搞懂Go语言的内存分配原理前,必须先了解Tcmalloc内存分配器,以便于我们更好的理解Go语言的内存分配原理。
本文目录如下:
- 读前知识储备
- 内存的线性分配
- 什么是
FreeList
? - 什么是
TCMalloc
?
TCMalloc
中的五个基本概念Page
的概念Span
的概念SpanList
的概念
Object
的概念SizeClass
的概念
- 解密
Tcmalloc
的基本结构 PageHeap
、CentralFreeList
、ThreadCache
的详细构成- 解密
PageHeap
- 解密
CentralFreeList
和TransferCacheManager
的构成- 解密
CentralFreeList
- 解密
TransferCacheManager
- 解密
- 解密
ThreadCache
- 解密
- 解密
TCMalloc
基本结构的依赖关系
读前知识储备
本小节的内容如下:
- 内存的线性分配
- 什么是
FreeList
? - 什么是
TCMalloc
?
目的:辅助我们更好的理解内存分配原理。
内存的线性分配
线性分配大致就是需要使用多少分配多少,“用到哪了标识到哪”,如下图所示:
线性分配有个问题:“已经分配的内存被释放了,我们如何再次分配?”。大家会想到用链表LinkedList
,是的没错,但是内存管理中一般使用的是FreeList
。
什么是FreeList?
FreeList
本质上还是个LinkedList
,和LinkedList
的区别:
FreeList
没有Next
属性,所以不是用Next
属性存放下一个节点的指针的值。FreeList
“相当于使用了Value
的前8字节”(其实就是整块内存的前8字节)存放下一个节点的指针。- 分配出去的节点,节点整块内存空间可以被复写(指针的值可以被覆盖掉)
如下图所示:
结论:
FreeList
里一个节点最小为8字节
备注:因为要存指针,指针的大小为8字节,为什么?可以参考上篇文章《64位平台下,指针自身的大小为什么是8字节?》(http://tigerb.cn/2021/01/23/go-base/memory-pointer/)
这里直说结论哈,我们的进程是运行在虚拟内存上的,图示如下:
- 对于我们的进程而言,可使用的内存是连续的
- 安全,防止了进程直接对物理内存的操作(如果进程可以直接操作物理内存,那么存在某个进程篡改其他进程数据的可能)
- 虚拟内存和物理内存是通过MMU(Memory Manage Unit)映射的(感兴趣的可以研究下)
- 等等(感兴趣的可以研究下)
所以,以下文章我们所说的内存都是指虚拟内存。
什么是TCMalloc?
TCMalloc
全称Thread Cache Alloc
,是Google开源的一个内存分配器,基于数据结构FreeList
实现,并引入了线程级别的缓存,性能更加优异。
TCMalloc中的五个基本概念
本小节的内容如下:
Page
的概念Span
的概念SpanList
的概念
Object
的概念SizeClass
的概念
目的:
TCMalloc
各个主要部分是基于这些基本概念组成的.
Page的概念
操作系统是按Page
管理内存的,本文中1Page为8KB,如下图所示:
备注:操作系统为什么按`Page`管理内存?不在本文范围。
Span和SpanList的概念
一个Span
是由N个Page
构成的,且:
- N的范围为
1 ~ +∞
- 构成这个
Span
的N个Page
在内存空间上必须是连续的
如下图所示:
从图中可以看出,有:
- 1个
Page
构成的8KB的Span
- 2个连续
Page
构成的16KB的Span
- 3个连续
Page
构成的24KB的Span
除此之外,Span
和Span
之间可以构成双向链表我们称之为SpanList
,内存管理中通常将持有相同数量Page
的Span
构成一个双向链表,如下图所示(N个持有1Page的Span
构成的SpanList
):
我们再来看Span
的下代码,如下:
class Span : public SpanList::Elem {
public:
// 略...
// 把span拆解成object的方法
// object的概念看下文
void BuildFreelist(size_t size, size_t count);
// 略...
union {
// object构成的freelist
// object的概念看下文
ObjIdx cache_[kCacheSize];
// 略...
};
PageId first_page_; // 当前span是从哪个page开始的
Length num_pages_; // 当前page持有的page数量
// 略...
};
Object和SizeClass的概念
一个Span
会被按照某个大小拆分为N个Objects
,同时这N个Objects
构成一个FreeList
(如果忘了FreeList的概念可以再返回上文重新看看)。
我们以持有1Page
的Span
为例,Span
、Page
、Object
关系图示如下:
看完上面的图示,问题来了:
上图怎么知道拆分
Span
为一个个24字节大小的Object
,这个规则是怎么知道的呢?
答案:依赖代码维护的映射列表。
我们以Google开源的TCMalloc源码(commit:9d274df)为例来看一下这个映射列表 https://github.com/google/tcmalloc/tree/master/tcmalloc
代码位置:tcmalloc/tcmalloc/size_classes.cc
代码示例(摘取一部分):
const SizeClassInfo SizeMap::kSizeClasses[SizeMap::kSizeClassesCount] = {
// 这里的每一行 称之为SizeClass
// <bytes>, <pages>, <batch size> <fixed>
// Object大小列,一次申请的page数,一次移动的objects数(内存申请或回收)
{ 0, 0, 0}, // +Inf%
// 所以也知道为啥最小8字节了吧?
// Object会构成FreeList
// FreeList的节点要存指针
// 指针为8字节
{ 8, 1, 32}, // 0.59%
{ 16, 1, 32}, // 0.59%
{ 24, 1, 32}, // 0.68%
{ 32, 1, 32}, // 0.59%
{ 40, 1, 32}, // 0.98%
{ 48, 1, 32}, // 0.98%
// ...略...
{ 98304, 12, 2}, // 0.05%
{ 114688, 14, 2}, // 0.04%
{ 131072, 16, 2}, // 0.04%
{ 147456, 18, 2}, // 0.03%
{ 163840, 20, 2}, // 0.03%
{ 180224, 22, 2}, // 0.03%
{ 204800, 25, 2}, // 0.02%
{ 229376, 28, 2}, // 0.02%
{ 262144, 32, 2}, // 0.02%
};
获取拆分规则的过程(先找到行、再找到这行第一列的值):
1. 先找到对应行(如何找到这个行?是不是有人有疑惑了,
想知道这个答案就需要了解`CentralFreeList`这个结构了,
下文我们会讲到。)
2. 找到第一列,这个数字就是object的大小
同时通过上面我们知道了:SizeMap::kSizeClasses
的每一行元素我们称之为SizeClass(下文中我们直接就称之为SizeClass
).
这个5个基本概念具体干什么用的呢?
答案:支撑了`Tcmalloc`的基本结构的实现。
解密Tcmalloc的基本结构
Tcmalloc
主要由三部分构成:
PageHeap
CentralFreeList
ThreadCache
图示如下:
但是呢,实际上CentralFreeList
是被TransferCacheManager
管理的,所以Tcmalloc
的基本结构实际应该为下图所示:
接着,
ThreadCache
其实被线程持有,为什么呢?
答案:减少线程之间的竞争,分配内存时减少锁的过程。
这也是为什么叫`Thread Cache Alloc`的原因。
进一步得到简易的结构图:
解密PageHeap、CentralFreeList、ThreadCache的详细构成
本小节的内容如下:
- 解密
PageHeap
- 解密
CentralFreeList
和TransferCacheManager
的构成- 解密
CentralFreeList
- 解密
TransferCacheManager
- 解密
- 解密
ThreadCache
目的:详细了解
TCMalloc
各个组成部分的实现。
解密PageHeap
PageHeap
主要负责管理不同规格的Span
,相同规格的Span
构成SpanList
(可回顾上文SpanList
的概念)。
什么是相同规格的
Span
?
答:持有相同`Page`数目的`Span`。
PageHeap
对象里维护了一个属性free_
类型是个数组,粗略看数组元素的类型是SpanList
,同时free_
这个数据的元素具有以下特性:
- 索引值为1对应的
SpanList
,该SpanList
的Span
都持有1Pages; - 索引值为2对应的
SpanList
,该SpanList
的Span
都持有2Pages; - 以此类推,
free_
索引值为MaxNumber对应的SpanList
,该SpanList
的Span
都持有MaxNumber Pages; - MaxNumber的值由
kMaxPages
决定
图示如下:
但是呢,实际上从代码可知:数组元素的实际类型为SpanListPair
,代码如下
class PageHeap final : public PageAllocatorInterface {
public:
// ...略
private:
// 持有两个Span构成的双向链表
struct SpanListPair {
// Span构成的双向链表 正常的
SpanList normal;
// Span构成的双向链表 大概是 物理内存已经回收 但是虚拟内存还被持有(感兴趣可以研究)
SpanList returned;
};
// ...略
// kMaxPages.raw_num()这么多个,由上面SpanListPair类型构成的数组
SpanListPair free_[kMaxPages.raw_num()] ABSL_GUARDED_BY(pageheap_lock);
// ...略
};
free_
数组元素的类型是SpanListPair
SpanListPair
里维护了两个SpanList
根据这个结论我们修正下PageHeap
结构图,如下:
又因为大于kMaxPages个Pages(大对象)的内存分配是从large_
中分配的,代码如下:
class PageHeap final : public PageAllocatorInterface {
public:
// ...略
// 大对象的内存从这里分配(length >= kMaxPages)
SpanListPair large_ ABSL_GUARDED_BY(pageheap_lock);
// ...略
};
所以我们再加上大对象的分配时的large_
属性,得到PageHeap
的结构图如下:
同时PageHeap
核心的代码片段如下:
class PageHeap final : public PageAllocatorInterface {
public:
// ...略
private:
// 持有两个Span构成的双向链表
struct SpanListPair {
// Span构成的双向链表
SpanList normal;
// Span构成的双向链表
SpanList returned;
};
// 大对象的内存从这里分配(length >= kMaxPages)
SpanListPair large_ ABSL_GUARDED_BY(pageheap_lock);
// kMaxPages.raw_num()这么多个,由上面SpanListPair类型构成的数组
SpanListPair free_[kMaxPages.raw_num()] ABSL_GUARDED_BY(pageheap_lock);
// ...略
};
解密CentralFreeList和TransferCacheManager的构成
解密CentralFreeList
我们可以称之为中央缓存,中央缓存被线程共享,从中央缓存CentralFreeList
获取缓存需要加锁。
CentralFreeList
里面有个属性size_class_
,就是SizeClass
的值,来自于映射表SizeMap
这个数组的索引值。CentralFreeList
里的Span
会做一件事情,按照这个size_class_
值对应的规则拆解Span
为多个Object
,同时这些Object
构成FreeList
。
同时,SizeMap
里的每个SizeClass
都会对应一个CentralFreeList
,所以最多一共会有N个CentralFreeList
,N的值为kNumClasses
。关键代码如下:
class CentralFreeList {
// ...略
private:
// 锁
// 线程从此处获取内存 需要加锁 保证并发安全
absl::base_internal::SpinLock lock_;
// 对应上文提到的映射表SizeClassInfo中的某个索引值
// 目的找到Span拆解为object时,object的大小等规则
size_t size_class_;
// object的总数量
size_t object_size_;
// 一个Span持有的object的数量
size_t objects_per_span_;
// 一个Span持有的page的数量
Length pages_per_span_;
// ...略
如下图就展示了kNumClasses
个CentralFreeList
,其中我们以size_class_
的值为1
和3
为例来展示下CentralFreeList
的结构。
解密TransferCacheManager
因为有kNumClasses
个CentralFreeList
,这些CentralFreeList
在哪维护的呢?
答案:就是`TransferCacheManager`这个结构里的`freelist_`属性。
代码如下:
class TransferCacheManager {
// ...略
private:
// freelist_是个数组
// 元素的类型是上面的CentralFreeList
// 元素的数量与 映射表 SizeClassInfo对应
CentralFreeList freelist_[kNumClasses];
} ABSL_CACHELINE_ALIGNED;
解密ThreadCache的构成
我们可以称之为线程缓存,TCMalloc
内存分配器的核心所在。ThreadCache
被每个线程持有,分配内存时不用加锁,性能好。
ThreadCache
对象里维护了一个属性list_
类型是个数组,数组元素的类型是FreeList
,代码如下:
class ThreadCache {
// ...略
// list_是个数组
// 元素的类型是FreeList
// 元素的数量与 映射表 SizeClassInfo对应
FreeList list_[kNumClasses];
// ...略
};
同时FreeList
里的元素还具有以下特性:
- 索引值为1对应的
FreeList
,该FreeList
的Object
大小为8 Bytes; - 索引值为2对应的
FreeList
,该FreeList
的Object
大小为16 Bytes; - 以此类推,
free_
索引值为MaxNumber对应的FreeList
,该FreeList
的Object
大小为MaxNumber Bytes; - MaxNumber的值由
kNumClasses
决定
这个规则怎么来的?还是取决于映射列表,同样以Google开源的TCMalloc源码(commit:9d274df)为例,来看一下这个映射列表:
https://github.com/google/tcmalloc/tree/master/tcmalloc
代码位置:tcmalloc/tcmalloc/size_classes.cc
代码示例(摘取一部分):
const SizeClassInfo SizeMap::kSizeClasses[SizeMap::kSizeClassesCount] = {
// 这里的每一行 称之为SizeClass
// <bytes>, <pages>, <batch size> <fixed>
// Object大小列,一次申请的page数,一次移动的objects数(内存申请或回收)
{ 0, 0, 0}, // +Inf%
{ 8, 1, 32}, // 0.59%
{ 16, 1, 32}, // 0.59%
{ 24, 1, 32}, // 0.68%
{ 32, 1, 32}, // 0.59%
{ 40, 1, 32}, // 0.98%
{ 48, 1, 32}, // 0.98%
// ...略...
};
我们可以得到:
数组索引 FreeList里单个Object的大小 1 8 Bytes 2 16 Bytes 3 24 Bytes 4 32 Bytes 5 40 Bytes … … kNumClasses kNumClasses Bytes得到ThreadCache
结构图如下所示:
注意:图示中索引为3的FreeList的Span尾部会浪费掉8字节。
解密Tcmalloc基本结构的依赖关系
本小节的内容如下:
目的:了解
Tcmalloc
内存分配的大致过程。
我们把Tcmalloc
中分配的对象分为两类:
小对象的大小范围就来自于SizeMap
维护的映射表,也就是单个Object
的大小范围,我们还是以如下代码片段为例,可知单个Object
大小范围为:
8 Byte ~ 262144 Byte == 8 Byte ~ 256 KB
const SizeClassInfo SizeMap::kSizeClasses[SizeMap::kSizeClassesCount] = {类型 大小 来源 小对象 <= 256 KB
// 这里的每一行 称之为SizeClass
// <bytes>, <pages>, <batch size> <fixed>
// Object大小列,一次申请的page数,一次移动的objects数(内存申请或回收)
// ...略...
{ 8, 1, 32}, // 0.59%
// ...略...
{ 262144, 32, 2}, // 0.02%
};
ThreadCache
、CentralFreeList
非小对象
> 256 KB
PageHeap.free_
和PageHeap.large_
当给小对象分配内存时:ThreadCache
的内存不足时,从对应SizeClass
的CentralFreeList
获取,如果获取不到,CentralFreeList
再从PageHeap
里获取内存。
当给非小对象分配内存时:PageHeap.free_
和PageHeap.large_
里获取。
最后,我们以获取6
字节的小对象为例(SizeClass
的值为1
),看一下详细内存分配过程。
简单总结下,本篇文章我们可以获取到的知识点:
- 了解了
FreeList
- 知道了
TCMalloc
主要由ThreadCache
、CentralFreeList
、PageHeap
三部分组成Object
构成的FreeList
,被ThreadCache
维护Span
构成了SpanList
,被CentralFreeList
维护,同时Span
会被拆解成Object
- 当
ThreadCache
里的Object
没有时,从对应SizeClass
的CentralFreeList
里获取 - 小对象来自
ThreadCache
、CentralFreeList
- 非小对象来自
PageHeap
- 线程从
ThreadCache
获取内存不需要加锁
通过学习以上内容,再回过头学习Go语言的内存分配,应该会变得轻松明了,下次我们就来看看Go内存设计与实现。
参考:
1. tcmalloc源码(commit:9d274df) https://github.com/google/tcmalloc/tree/master/tcmalloc
2. 可利用空间表(Free List)https://songlee24.github.io/2015/04/08/free-list/
3. 图解 TCMalloc https://zhuanlan.zhihu.com/p/29216091
4. TCMalloc解密 https://wallenwang.com/2018/11/tcmalloc/
5. TCMalloc : Thread-Caching Malloc https://github.com/google/tcmalloc/blob/master/docs/design.md
6. TCMalloc : Thread-Caching Malloc https://gperftools.github.io/gperftools/tcmalloc.html
7. tcmalloc原理剖析(基于gperftools-2.1) http://gao-xiao-long.github.io/2017/11/25/tcmalloc/
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK