首页
论坛
课程
招聘
[原创] heap related data structure && ptmalloc2
2020-3-7 11:22 3424

[原创] heap related data structure && ptmalloc2

2020-3-7 11:22
3424

复习堆的时候发现自己对于堆结构,空间申请与释放,函数调用掌握的还是不够透彻,所以再重新复习一遍堆的数据结构 o3o 也发现了一些以前搞错了很多,害...
本文只捡练了一些(以32位系统为例,64位基本都是对应size*2)

0x01 malloc_chunk的基本结构

(使用中/未被free)

 

(空闲chunk/free之后)

  1. size字段的低三个比特位对chunk的大小没有影响,他们从高到底分别表示:
    • NONMAINARENA,记录当前 chunk 是否不属于主线程(main_arena),1 表示不属于,0 表示属于。
    • ID_MAPPED,记录当前 chunk 是否是由 mmap 分配的。(chunk空闲时,M不存在)
    • PREV_INUSE,记录前一个chunk是否被分配。1表示被分配,0表示没有。堆的第一个chunk所记录的prev_inuse位默认为1
  2. fd_nextsize bk_nextsize在chunk空闲时才使用,(Large bin中特有)暂不讲解。
  3. 一般情况下,物理相邻的两个空闲chunk会被合并为一个chunk,堆管理器会通过prev_size字段及size字段合并两个物理相邻的空闲chunk。

0x02 chunk的复用

空闲时,一个chunk至少需要4个size_t(4B)大小的空间(prev_size, size, fd, bk)共16B,且chunk的大小要对齐到8B。
当一个chunk处于使用状态时,它的下一个chunk的prev_size无效,该prev_size域被当前chunk使用。(可以理解为,当chunk在使用时,在二进制文件中执行,而不归共享库管理,下一个chunk的prev_size域直接分配给当前chunk,可以使内存空间高效利用,也省去重新分配空间的麻烦)
一个使用中的chunk的大小in_use_size = (用户申请大小 + 8 - 4) align to 8B
+8是存储prev_size和size
-4是“借”了下一个chunk的prev_size
最终分配的chunk_size = max(in_use_size, 16)

0x03 Bin

一.概述

  • 用户释放掉的 chunk 不会马上归还给系统,ptmalloc 会统一管理 heap 和 mmap 映射区域中的空闲的 chunk。当用户再一次请求分配内存时,ptmalloc 分配器会试图在空闲的 chunk 中挑选一块合适的给用户。这样可以避免频繁的系统调用,降低内存分配的开销。
  • ptmalloc将相似大小的chunk用双向链表链接,此链表称为bin。ptmalloc一共维护了128个bin,并使用一个数组来存储这些bin
  • free掉一个chunk时根据chunk大小加入到对应的bin中。


bin[128]中0和127不使用

二.分类

1. fast bins

不大于max_fast(64B)的chunk被释放后,首先会被放到fastbins中,fastbins中的chunk不改变它的Prev_inuse标志,也就无法被合并。
当用户需要的chunk大小 < max_fast时,ptmalloc会首先判断fastbin中相应的bin中是否有对应大小的空闲块(这里比较的是无符号整数),如果有,直接从fastbin头结点开始取chunk。free之后如果再次malloc相同size,会申请到同一块内存。如果没有才会查找bins中的空闲chunk。
在某个特定的时候,ptmalloc会遍历fastbins中的chunk,将相邻的空闲chunk进行合并,并将合并后的chunk加入unsorted bin中,然后再将unsortedbin中的chunk加入bins。

 

fast bin为单链表。采用LIFO(Last In First Out)。fastbins cache了 small bins的前7个大小的空闲chunk,对于 SIZE_SZ 为 4B 的平台【16B,24B,32B,40B,48B,56B,64B】;对 于 SIZE_SZ 为 8B 的平台【32B,48B,64B,80B,96B,112B,128B】

 

当每次释放的 chunk 与该 chunk 相邻的空闲 chunk 合并后的大小大于 64k 时,就认为内存碎片可能比较多了,就需要 把 fast bins 中的所有 chunk 都进行合并,以减少内存碎片对系统的影响

2. unsorted bins

如果被用户释放的chunk > max_fast(64B),或者fastbins中的空闲chunk合并后,这些chunk首先会被放入unsorted bin
malloc时如果fastbin中没有合适的chunk,就会在unsorted bin中查找合适的。如果unsorted bin中没有合适的chunk,就将unsorted bin中的chunk放到所属的bin中再分配。
可以把unsorted bins理解为缓冲区。

 

unsorted bin为bin[1],其中的chunk没有排序,大小不限制,双链表,成环。采用FIFO。

3. small bins

small bin为索引2到63,大小为(2 SIZE_SZ ndx)(即 size < 512B),双链表,成环。采用FIFO。
实际共62个bin,同一个small bin 链表中的 chunk 的大小相同。两个相邻索引的 small bin 链表中的 chunk 大小32 位相差 8 字节【16B, 24B, 32B, ..., 504B】,64 位相差 16 字节【32B, 48B, 64B, ..., 1008B】
分配时采用精确匹配。

4. large bins

large bin为索引64到126,大小为[512,512+64)(即 size >= 512B)。
一共包括63个bin,每个 bin 中的 chunk 的大小不一致,而是处于一定区间范围内。此外,这 63 个 bin 被分成了 6 组,每组 bin 中的 chunk 大小之间的公差一致。
以32位平台(SIZE_SZ = 4B)为例:

数量 公差
1 32 64B
2 16 512B
3 8 4096B
4 4 32768B
5 2 262144B
6 1 不限制
 

large bins 中的每一个 bin 都包含一定范围内的 chunk,其中的 chunk 按 fd 指针的顺序从大到小排列。相同大小的 chunk 同样按照最近使用顺序排列。
分配时采用最近匹配。


 

——上述这些 bin 的排布都会遵循一个原则:任意两个物理相邻的空闲 chunk 不能在一起

 

需要注意的是,并不是所有的 chunk 被释放后就立即被放到 bin 中。ptmalloc 为了提高分配的速度,会把一些小的 chunk放到 fast bins 的容器内。而且,fastbin 容器中的 chunk 的使用标记总是被置位的,所以不满足上面的原则。

0x04 三种特殊的chunk

并不是所有的chunk都按照上面的方式组织。以下是三种特殊的chunk,他们不属于任何bins。

top chunk

对于非主分配区预先从mmap分配一块较大的sub-heap,heap 会被分为两块,一块给用户,剩下的那块就是 top chunk。其实,所谓的 top chunk 就是处于当前堆的物理地址最的 chunk。【因为内存是按地址从底向高进行分配的】
这个 chunk 不属于任何一个 bin,它的作用在于当所有的 bin 都无法满足用户请求的大小时,如果其大小不小于指定的大小,就进行分配,并将剩下的部分作为新的 top chunk。否则,就重新分配一个sub-heap,并将top chunk迁移到新的sub-heap上再分配。
top chunk分配内存会使top chunk减小。如果回收的chunk恰好与top chunk相邻,那么合并成新top chunk使top chunk变大。
如果free时回收的内存大于某个阈值,且top chunk大小也超过的收缩阈值,ptmalloc就会收缩sub-heap。如果top chunk包含了整个sub-heap,ptmalloc会调用munmap把整个sub-heap返回操作系统。

 

主分配区是唯一能够映射进程heap区域的分配区(有点难理解。。。)在 main arena 中通过 sbrk 扩展收缩 heap,ptmalloc会预先分配一块较大的空闲内存(heap)
主分配区的top chunk第一次malloc时会分配一块(chunk_size + 128KB) align 4KB大小的空间作为初始heap,用户从top chunk分配内存时,可直接取出一块给用户。如果top chunk中没有空闲内存,ptmalloc会调用sbrk()将进程heap边界brk上移,然后修改top chunk大小。回收时,回收的内存恰好与top chunk相邻则合成新top chunk。
如果free时回收的内存大于某个阈值,且top chunk大小也超过的收缩阈值,会收缩内存,但至少保留一个页大小的空闲内存,从而把内存归还操作系统。

mmaped chunk(略)

chunk足够大时,以上的都不能满足分配需求时,ptmalloc会使用mmap直接使用内存映射来将页映射到进程空间。这样分配的chunk在被free时将直接接触映射,将内存归还给操作系统,若再次对这样的内存引用将导致segmentation fault。

last remainder chunk(略)

需要分配一个small chunk,但small bins中找不到合适的chunk,如果last remainder chunk的大小 > 所需的small chunk大小,就将它分裂成两个chunk,其中一个chunk返回用户,另一个变成新的last remainder chunk。

综上

内存分配:_int_malloc

根据size

  • 获取分配区的锁(略,想了解看源码分析)
  • 将用户请求的大小转换为实际需要分配的chunk_size
  • fastbin range:chunk_size <= max_fast,从fast bin中查找是否有合适的chunk。
    • 找到,分配结束。
    • 未找到 ⬇
  • small bin range:chunk_size < 512B,先从small bin查找(small bin按照size排好,查找更快)按照size从对应具体的small bin的尾部找到恰好满足大小的chunk。
    • 找到,分配结束。
    • 未找到 ⬇
  • ptmalloc首先遍历fast bins中的chunk,将相邻chunk合并,并链接到unsorted bin。
  • 遍历unsorted bin。
    • 如果unsorted bin只有一个chunk,并且该chunk在上次分配时被使用,所需分配的chunk大小属于small bins,且该chunk大小 >= 需要分配的大小,直接切割,分配结束。(丢,好绕)
    • 否则,根据chunk大小放入small bins或large bins中。⬇
  • large bin range:从large bin 中查找满足条件且最小的chunk。
    • 有则切分,剩下的部分链接回bins中,剩余的放入unsorted bin//这是ptmalloc机制,他在分配large chunk时会先对堆中的碎片chunk进行合并,以便减少堆中的碎片
    • 未找到 ⬇
  • 从top chunk切割
    • 满足,分配结束
    • 不满足 ⬇
  • 当topchunk也无法满足时,如果是主分配区,调用sbrk()增加top chunk大小。如果是非主分配区,调用mmap()
    【mmap的具体分配方法 略】

内存回收:free

    1. 获取分配区锁
    1. 检测传入free的指针是否为0
    • 是,直接return
    • 否,⬇
    1. 是否是mmap分配
    • 是,释放mmap的chunk
    • 否,⬇
    1. size是否属于fast bin且chunk并不位于heap顶部,也就是不与top chunk相邻
    • 是,插入fast bin,return
    • 否,⬇
    1. 查看前一个chunk是否free
    • 是,合并,⬇
    1. 查看下一个chunk是否为top chunk
    • 是,合并,更新top chunk大小,⬇
    • 否,->7
    1. 查看下一个chunk是否free
    • 是,合并
    1. 判断合并后的 chunk 的大小是否大于 FASTBIN_CONSOLIDATION_THRESHOLD(默认 64KB)
    • 是,触发进行 fast bins 的合并操作,fast bins 中的 chunk 将被 遍历,并与相邻的空闲 chunk 进行合并,合并后的 chunk 会被放到 unsorted bin 中。 fast bins 将变为空,⬇
    1. 判断 top chunk 的大小是否大于 mmap 收缩阈值(默认为 128KB)
    • 是,对 于主分配区,则会试图归还 top chunk 中的一部分给操作系统。但是最先分配的 128KB 空间是不会归还的,ptmalloc 会一直管理这部分内存,用于响应用户的分配 请求;如果为非主分配区,会进行 sub-heap 收缩,将 top chunk 的一部分返回给操 作系统,如果 top chunk 为整个 sub-heap,会把整个 sub-heap 还回给操作系统。

释放结束,从 free() 函数退出。可以看出,收缩堆的条件是当前 free 的 chunk 大小加上前后能合并 chunk 的大小大于 64k,并且要 top chunk 的大 小要达到 mmap 收缩阈值,才有可能收缩堆

分配区

arena的个数是跟系统中处理器核心个数相关

For 32 bit systems:
     Number of arena = 2 * number of cores.
For 64 bit systems:
     Number of arena = 8 * number of cores.

main_arena

main_arena表示主分配区,任何进程有且仅有一个全局的主分配区

参考:CTF-wiki堆glibc内存管理ptmalloc2源码分析


《0day安全 软件漏洞分析技术(第二版)》第三次再版印刷预售开始!

最后于 2020-3-7 11:28 被plkk编辑 ,原因:
收藏
点赞0
打赏
分享
最新回复 (1)
雪    币:
能力值: ( LV1,RANK:0 )
在线值:
发帖
回帖
粉丝
mb_kugwraep 活跃值 2020-3-7 16:08
2
0
厉害
游客
登录 | 注册 方可回帖
返回