首页 > C/C++ > 理解glibc的堆管理策略
2017
10-29

理解glibc的堆管理策略

历史沿革

常常用到的堆管理策略主要有以下几种

  • dlmalloc – General purpose allocator
  • ptmalloc2 – glibc
  • jemalloc – FreeBSD and Firefox
  • tcmalloc – Google
  • libumem – Solaris

ptmalloc2最初由dlmalloc修改而来,后来ptmalloc2加入了多线程机制的支持,从此与dlmalloc渐渐区分开来,现在是linux的默认内存管理策略。 dlmalloc为多个线程维护一个堆,多个线程调用malloc时只能依次执行。ptmalloc为每个线程分配一个arena,在各个线程专属的arena中进行堆管理,因此可以同时处理多个线程的malloc调用,该机制称为Per Thread Arena

实现细节

调用的系统函数

brk:改变程序退出的节点地址所在,一般情况下,程序退出节点位于数据段末尾后内存,但是堆管理过程需要在数据段后附加新数据(堆),因此调用系统函数brk()增加内存空间
mmap:与brk直接粗暴的改变程序退出节点不同,mmap用来添加新的映射到其余的内存地址中,堆管理在映射到的内存地址中进行
malloc()

调用malloc后,会根据情况调用brk和mmap两个系统函数创建堆
brk:当主线程调用malloc(),且请求的内存大小较小时(<128KB),使用brk分配堆 直接在数据段之后请求一段内存负责堆管理,返回的内存比请求的内存更大,以用于后续的需求
mmap:当普通线程调用malloc()时,调用mmap()系统函数将线程的arena分配到映射的内存空间中

堆会维护一个freelist(glibc里面称为bin)来对堆中未被使用的内存地址进行记录,如果在同一个arena中请求堆,先检查bin中是否有free的堆地址,如果堆不够用时,才会向内核请求增加arena的内存大小

理解glibc的堆管理策略 - 第1张  | 刘建广学习笔记

free()

调用free()函数并不会将malloc()分配的内存释放掉,仅仅是将free的内存地址加入bin,在下一次malloc的时候可以使用

堆结构

堆结构分为三层:arena、heap、chunk 这里绘制了一副图表明堆,类似的这样的图网上还有很多

arena

arena的个数有上限,通常为CPU核心的个数2(32位系统)8(64位系统),如果超过了这一上限,则内核可能将多个线程的堆映射到一个arena
一个arena可以维护多个堆,但是只维护一个malloc_state(即Arena Header)
理解glibc的堆管理策略 - 第2张  | 刘建广学习笔记
只有一个堆的内存地址
当当前堆内存地址空间不足时,调用mmap()在内存空间中映射一个新的堆出来,映射出来后的结果如下
理解glibc的堆管理策略 - 第3张  | 刘建广学习笔记


heap

如果一个arena维护了多个堆,每个堆需要维护一个heap_info(即Heap Header)。但main arena是例外,因为他不需要调用mmap,只需要往后增加内存大小就可以,他只用维护一个堆就好
main heap
chunk

chunk是堆中分出的数据块,每个chunk是一个连续的内存地址,用来存放比如数组等程序运行时的数据 chunk分为四种类型
Allocated chunk
Free chunk
Top chunk
Last Remainder chunk

1. allocated chunk

被分配了的在使用中的chunk
理解glibc的堆管理策略 - 第4张  | 刘建广学习笔记
image.png
prev chunk:记录上一个chunk的大小,将chunk想象成一个单链表,prev chunk就是chunk上的上一个数据单元,不同的chunk间是不连续的
chunk size:记录当前chunk的大小,其中,包含三比特的符号位
N:置0表示该chunk属于main arena
P:置1表示prev chunk在使用中(没有被free掉)
M:置1表示该chunk是调用mmap而产生的(即被映射到了其他的内存空间中)

2. free chunk

记录在bin中未被使用的chunk。两个chunk不能是地址连续的,否则会被合并掉 除了allocated chunk中记录的数据外,free chunk还记录了一些指针指向bin中记录的上一个/下一个free chunk的地址
bin

bin即freelist,维护一个记录freechunk地址的列表,根据free chunk的大小不同分为4种chunk
Fast bin
Small bin
Large bin
Unsorted bin(还没有排序过大小的chunk,排序后分为上述三类)
bins数组用于记录Small bin、Large bin、Unsorted bin。fastbinsY记录fast bin,共包含10个bin。bins数组包含共126个bin,第1个bin记录unsorted chunks,Bin 2-63是Small bin,Bin 64-126是Large bin
fast bins:
单链表FILO(first in last out),每个freechunk维护一个fd指针指向bin中记录的下一个fast chunk的地址
每个bins记录的chunk大小一致,第0个bin记录8字节的chunk,第一个记录16字节,第二个记录24字节,此后递增
fast chunks可以是内存地址上连续的,这是chunk中的一个例外
理解glibc的堆管理策略 - 第5张  | 刘建广学习笔记

unsorted bins:
当small 和large chunk被free后,chunk会被加入到unsorted bins
双链表,在调用malloc()时会首先检查是否有unsorted chunk,然后根据size决定将他分类或者合并
small bins:
双链表FIFO(first in first out)
与fast bins类似,以8个字节为单位分类bin。smallchunk的尺寸大小为120~512字节
free时,先检查前/后一个chunk是否是free的,如果是,则合并,之后加入到unsorted中
large bins:
类似于一个网状的链表,有多个指针,除了指向list中的下/上一个指针,还会指向按照size排序比他大/小一点的其他chunk
不同的bin维护不同size范围的large chunk,但是同一个bin中记录的chunk size不一定相等
调用malloc时,找到size相等或者最相近的那个large chunk,再将其分为两部分,一部分叫做:used chunk,另外一部分叫做remaining chunk,归入unsorted bin重新分配
调用free过程与small chunk类似
理解glibc的堆管理策略 - 第6张  | 刘建广学习笔记

3. Top Chunk

堆中最高地址处的chunk,不属于任何bin,当最大的chunk都不能满足用户的需求时,调用此处chunk,如果还不够,则调用系统函数增加top chunk

4. Last Remainder Chunk

unsorted bin中存放的最后一个没有被使用的chunk

最后编辑:
作者:liujg
真实-不弄虚,不做假,做自己,不违心; 踏实-不浮躁,不盲从,不急功,不近利; 实学-不投机,不取巧,勤于学,精于业。