登录后台

页面导航

本文编写于 447 天前,最后修改于 118 天前,其中某些信息可能已经过时。

Linux堆管理介绍

0x00前言

堆是程序虚拟地址空间中的一块连续的区域,由低地址向高地址增长。当前 Linux 使用的堆分配器被称为 ptmalloc2,在glibc中实现。我们首先要清楚:Linux平台申请内存空间本质上都是通过系统调用brk()函数和mmap()函数实现的。ptmalloc2是Linux的默认内存分配器,支持多线程,每一个线程维护一个单独的堆分段。
内存分布图:
clipboard(3).png

0x01arena(分配区)

简单来讲,arena就是内存管理器通过系统调用brk()函数和mmap()函数分配的一个堆区,按线程的类型可以分为2类:
main arena(主分配区):主线程建立的arena;
thread arena(非主分配区):子线程建立的arena;

main arena中的内存申请:

clipboard(6).png
主分配区第一次申请时,若请求的空间小于 mmap 分配阈值(mmap threshold,默认值为 128KB)时,主分配区会调用 sbrk()函数,一般分配的空间要比申请的大,这样可以减少后续的申请次数。后续申请会根据 arena 中剩余空间的大小决定是继续分配还是扩容,其中包含扩容部分的为 top chunk。这里需要注意分配阈值虽然具有默认值,但是会动态调整;

thread arena中的申请:

每个进程内部只有一个主分配区以及可能会有多个非主分配区(non-arena), 主分配区分配虚拟内存可以使用 sbrk 以及 mmap, 而非主分配区是同 sub-heap(子堆) 来管理内存。
clipboard(5).png
非主分配区第一次申请时会调用 mmap 映射一块大小为 HEAP_MAX_SIZE (32 位系统上默认为 1MB, 64 位系统上默认为 64MB)的空间作为 sub-heap,这些sub-heap通过链表链接起来。

0x02chunk

在内存空间中,glibc将整个堆空间分成了连续的、大小不一的chunk,即对于堆内存管理而言chunk就是最小的操作单位。chunk之间的连接方式可以看成链表,每一个chunk都可以看成一个结点,它们在物理内存上不连续,但是映射到虚拟内存上chunk与chunk之间就链接到了一起。
chunk只是一片内存区域,严格意义上来说可以分成allocated chunk和free chunk两类,top chunk和Last remainderchunk 只是比较特殊的chunk。

allocated chunk:

chunk在内存中的样子如下图:
clipboard.png

chunk指针指向的地址是chunk的开始,一个chunk包含chunk的的相关信息和用户的数据,mem指针是真正返回给用户的指针。chunk的第二个区域的最低一位是P,它是前一个chunk的状态标志符,P为0表示前一个chunk空闲,这时chunk的第一个区域prev_size才有效,它表示前一个chunk的大小。
prev_size 表示前一个 chunk 的 size, 程序可以使用这个值来找到前一个 chunk 的开始. 当 p 为 1 时, 表示前一个 chunk 正在使用中, prev_size 无效, 程序也就不可以得到前一个 chunk 的大小. 而不能对前一个 chunk 进行任何操作. ptmalloc 分配的第一个块总是将 p 设为 1 , 以防止程序引用到不存在的区域。
Chunk 的第二个域的倒数第二个位为 M,他表示当前 chunk 是从哪个内存区域获得的虚 拟内存。M 为 1 表示该 chunk 是从 mmap 映射区域分配的,否则是从 heap 区域分配的。 Chunk 的第二个域倒数第三个位为 A,表示该 chunk 属于主分配区或者非主分配区,如 果属于非主分配区,将该位置为 1,否则置为 0。

free chunk:

空闲 chunk 在内存中的结构如图所示:
clipboard(7).png
当chunk空闲时,只有AP状态,原本储存用户数据的区域储存了四个指针,会与两边的空闲chunk形成双向连链表的结构。其中fd指针指向后一块空闲的chunk,bk指针指向前一个空闲的chunk。

top chunk:在每个arena空闲内存的最高处一定会存在着一块空闲的chunk,这个chunk就是top chunk,该chunk不输于任何bin!!!分配内存时会先从fastbins,small bins,large bins中查找合适的chunk,如果都不能满足需要的时候,ptmalloc2会从top chunk中分配一个chunk返回给用户。

Last Remainder Chunk:当用户请求的是一个small chunk,且该请求无法被small bin、unsorted bin满足的时候,就通过binmaps遍历bin查找最合适的chunk,如果该chunk有剩余部分的话,就将该剩余部分变成一个新的chunk加入到unsorted bin中,另外,再将该新的chunk变成新的last remainder chunk。此类型的chunk用于提高连续malloc(small chunk)的效率,主要是提高内存分配的局部性。

0x03 bin

chunk是内存管理的最小操作单位,但tmalloc2总不能对每一块chunk都进行管理,就好像公司里老板不可能对每一位员工进行直接管理,老板会设立部门来将员工分类,这样会使整个公司高效的运转,linux的内存管理机制也是这样,由此出现了bin。
allocated chunk是用户正在使用的,它们之间通过链表链接,那么free chunk该怎么办?bin将它们归类链接到了一起。bin是一种记录free chunk的链表数据结构。系统针对不同大小的free chunk,将bin分为了4类: Fast bin 、Unsorted bin、Small bin 、Large bin。
clipboard(2).png
我刚开始把bin和bins搞混,这里说明下,bin是一种数据结构,bins是一个数组。

fast bin

在内存分配和释放过程中,fast bin是所有bin中操作速度最快的。介绍一些fast bin的特征:
1) fast bin的个数——10个
2)每个fast bin都是一个单链表(只使用fd指针)。为什么使用单链表呢?因为在fast bin中无论是添加还是移除fast chunk,都是对“链表尾”进行操作,而不会对某个中间的fast chunk进行操作。更具体点就是LIFO(后入先出)算法:添加操作(free内存)就是将新的fast chunk加入链表尾,删除操作(malloc内存)就是将链表尾部的fast chunk删除。需要注意的是,为了实现LIFO算法,fastbinsY数组中每个fastbin元素均指向了该链表的rear end(尾结点),而尾结点通过其fd指针指向前一个结点,依次类推,如图2-1所示。
.png)
3) chunk size:10个fast bin中所包含的fast chunk size是按照步进8字节排列的,即第一个fast bin中所有fast chunk size均为16字节,第二个fast bin中为24字节,依次类推。在进行malloc初始化的时候,最大的fast chunk size被设置为80字节(chunk unused size为64字节),因此默认情况下大小为16到80字节的chunk被分类到fast chunk。详情如图2-1所示。

4) 不会对free chunk进行合并操作。鉴于设计fast bin的初衷就是进行快速的小内存分配和释放,因此系统将属于fast bin的chunk的P(未使用标志位)总是设置为1,这样即使当fast bin中有某个chunk同一个free chunk相邻的时候,系统也不会进行自动合并操作,而是保留两者。虽然这样做可能会造成额外的碎片化问题,但瑕不掩瑜。
5) malloc(fast chunk)操作:即用户通过malloc请求的大小属于fast chunk的大小范围(注意:用户请求size加上16字节就是实际内存chunk size)。在初始化的时候fast bin支持的最大内存大小以及所有fast bin链表都是空的,所以当最开始使用malloc申请内存的时候,即使申请的内存大小属于fast chunk的内存大小(即16到80字节),它也不会交由fast bin来处理,而是向下传递交由small bin来处理,如果small bin也为空的话就交给unsorted bin处理:

unsorted bin:

unsorted bin临时存放未分类的chunk,这样做主要是为了让“glibc malloc机制”能够有第二次机会重新利用最近释放的chunk(第一次机会就是fast bin机制),利用unsorted bin,可以加快内存的分配和释放操作,因为整个操作都不再需要花费额外的时间去查找合适的bin了。
Unsorted bin的特性如下:
1、unsorted bin的个数: 1个。unsorted bin是一个由free chunks组成的循环双链表。
2、chunk size: 在unsorted bin中,对chunk的大小并没有限制,任何大小的chunk都可以归属到unsorted bin中。

Small bin

小于512字节的chunk称之为small chunk,small bin就是用于管理small chunk的。就内存的分配和释放速度而言,small bin比larger bin快,但比fast bin慢。
Small bin的特性如下:
1、small bin个数:62个。每个small bin也是一个由对应free chunk组成的循环双链表。同时Small bin采用FIFO(先入先出)算法:内存释放操作就将新释放的chunk添加到链表的front end(前端),分配操作就从链表的rear end(尾端)中获取chunk。
2、chunk size: 同一个small bin中所有chunk大小是不一样的,且第一个small bin中chunk大小为16字节,后续每个small bin中chunk的大小依次增加8字节,即最后一个small bin的chunk为16 + 62 * 8 = 512字节。
3、合并操作:相邻的free chunk需要进行合并操作,即合并成一个大的free chunk。具体操作见下文free(small chunk)介绍。
4、malloc(small chunk)操作:类似于fast bins,最初所有的small bin都是空的,因此在对这些small bin完成初始化之前,即使用户请求的内存大小属于small chunk也不会交由small bin进行处理,而是交由unsorted bin处理,如果unsorted bin也不能处理的话,glibc malloc就依次遍历后续的所有bins,找出第一个满足要求的bin,如果所有的bin都不满足的话,就转而使用top chunk,如果top chunk大小不够,那么就扩充top chunk,这样就一定能满足需求了。注意遍历后续bins以及之后的操作同样被large bin所使用,因此,将这部分内容放到large bin的malloc操作中加以介绍。
那么glibc malloc是如何初始化这些bins的呢?因为这些bin属于malloc_state结构体,所以在初始化malloc_state的时候就会对这些bin进行初始化,代码如下:
malloc_init_state (mstate av)
{
int i;
mbinptr bin;
/ Establish circular links for normal bins /
for (i = 1; i < NBINS; ++i)
{

  bin = bin_at (av, i);
  bin->fd = bin->bk = bin;

}
……
}

注意在malloc源码中,将bins数组中的第一个成员索引值设置为了1,而不是我们常用的0(在bin_at宏中,自动将i进行了减1处理…)。从上面代码可以看出在初始化的时候glibc malloc将所有bin的指针都指向了自己——这就代表这些bin都是空的。
过后,当再次调用malloc(small chunk)的时候,如果该chunk size对应的small bin不为空,就从该small bin链表中取得small chunk,否则就需要交给unsorted bin及之后的逻辑来处理了。
5、free(small chunk):当释放small chunk的时候,先检查该chunk相邻的chunk是否为free,如果是的话就进行合并操作:将这些chunks合并成新的chunk,然后将它们从small bin中移除,最后将新的chunk添加到unsorted bin中。

large bin

大于512字节的chunk称之为large chunk,large bin就是用于管理这些large chunk的。
Large bin的特性如下:
1、large bin的数量:63个。Large bin类似于small bin,只是需要注意两点:一是同一个large bin中每个chunk的大小可以不一样,但必须处于某个给定的范围(特例2) ;二是large chunk可以添加、删除在large bin的任何一个位置。
2、chunk size:在这63个large bins中,前32个large bin依次以64字节步长为间隔,即第一个large bin中chunk size为512~575字节,第二个large bin中chunk size为576 ~ 639字节。紧随其后的16个large bin依次以512字节步长为间隔;之后的8个bin以步长4096为间隔;再之后的4个bin以32768字节为间隔;之后的2个bin以262144字节为间隔;剩下的chunk就放在最后一个large bin中。鉴于同一个large bin中每个chunk的大小不一定相同,因此为了加快内存分配和释放的速度,就将同一个large bin中的所有chunk按照chunk size进行从大到小的排列:最大的chunk放在链表的front end,最小的chunk放在rear end。
3、合并操作:类似于small bin。
4、malloc(large chunk)操作:初始化完成之前的操作类似于small bin,这里主要讨论large bins初始化完成之后的操作。首先确定用户请求的大小属于哪一个large bin,然后判断该large bin中最大的chunk的size是否大于用户请求的size(只需要对比链表中front end的size即可)。如果大于,就从rear end开始遍历该large bin,找到第一个size相等或接近的chunk,分配给用户。如果该chunk大于用户请求的size的话,就将该chunk拆分为两个chunk:前者返回给用户,且size等同于用户请求的size;剩余的部分做为一个新的chunk添加到unsorted bin中。如果该large bin中最大的chunk的size小于用户请求的size的话,那么就依次查看后续的large bin中是否有满足需求的chunk,不过需要注意的是鉴于bin的个数较多(不同bin中的chunk极有可能在不同的内存页中),如果按照上一段中介绍的方法进行遍历的话(即遍历每个bin中的chunk),就可能会发生多次内存页中断操作,进而严重影响检索速度,所以glibc malloc设计了Binmap结构体来帮助提高bin-by-bin检索的速度。Binmap记录了各个bin中是否为空,通过bitmap可以避免检索一些空的bin。如果通过binmap找到了下一个非空的large bin的话,就按照上一段中的方法分配chunk,否则就使用top chunk来分配合适的内存。
5、Free(large chunk):类似于small chunk。

总结:
bin机制的引入是为了方便内存管理器管理内存碎片,最终的目的是为了提高堆内存分配和释放的效率,优化内存管理。
clipboard(1).png
参考资料:
《Glibc 内存管理 Ptmalloc2 源代码分析 》
Linux堆内存管理深入分析(上):https://www.cnblogs.com/alisecurity/p/5486458.html
Linux堆内存管理深入分析(下):https://www.cnblogs.com/alisecurity/p/5520847.html