glibc的堆管理实现

arena

指的是堆内存区域本身,并非结构

主线程的main arena通过sbrk创建

其他线程arena通过mmap创建

malloc_state

管理arena的核心结构,包括堆的状态信息,bins链表等

main arena对应的malloc_state结构存储在glibc的全局变量中

其他线程的arena对应的malloc_state存储在arena本身

bins

用来管理空闲内存块,通常使用链表结构来进行组织

chunks

内存块的结构

chunks

用户请求的空间.

prev_size / prev_data：

• 如果前一个chunk是allocated chunk(P=1)，则此字段属于前一个chunk可用的data部分

• 如果前一个chunk是free chunk(P=0)，则此字段表示前一个chunk的size(prev_size)

标志位（size字段的低3bit）

• N：NON_MAIN_ARENA flag，表示chunk是否属于主线程

• M：IS_MMAPPED flag，表示是否由mmap分配

• P：PREV_INUSE flag，前一个chunk是否处于使用状态

如果当前chunk已经被free到bin中，

• fd：指向bin中后一个空闲块的指针

• bk：指向bin中前一个空闲块的指针

（后一个和前一个均不一定是物理相邻的）

如果当前chunk已经被free到large bin（后面马上会提到）中，

• fd_nextsize：指向large bin中后一个与自己大小不同的chunk的指针

• bk_nextsize：指向large bin中前一个与自己大小不同的chunk的指针

大小对齐

在glibc中，对齐由malloc.c中的request2size宏实现。可以简单将该操作理解为下表中的映射，即：实际size = 请求的size+8后对应的下一个0x10对齐的值

这里应该还考虑了下一个chunk的复用,那万一复用不了呢?

free chunk

allocated chunk

下一个chunk的prev_size也可以被用来存放数据,因为只有前一个chunk是free的时候这个字段才有意义

案例

顺便学一下怎么调试源码

指定libc版本编译 https://blog.csdn.net/mo4776/article/details/119837501

-Wl,–dynamic-linker=/动态连接器的路径/ld-linux-x86-64.so.2

https://blog.csdn.net/bandaoyu/article/details/121476940

gcc -Wl,-rpath=’/my/lib’,-dynamic-linker=’/my/lib/ld-linux.so.2’

gcc -Wl,-rpath=/home/ubuntu/glibc-all-in-one/libs/2.23-0ubuntu3_amd64//,–dynamic-linker=/home/ubuntu/glibc-all-in-one/libs/2.23-0ubuntu3_amd64/ld-linux-x86-64.so.2 1.c

各种bin

fast bin、tcache bin按照LIFO(last in first out)单链表组织，采用头插法

unsorted bin、small bin按照FIFO(first in first out)双链表组织，采用头插法

large bin按照双链表组织，插入节点时会保证size从大到小排序

https://blog.51cto.com/u_15076233/3914352

有两种结构来管理,一种是fastbin的,另外一种是其他三种bin的

/* Fastbins */ 用来管理小的chunk

mfastbinptr fastbinsY[NFASTBINS];

/* Normal bins packed as described above */

mchunkptr bins[NBINS * 2 - 2];

• bins：能够存放所有size范围的free chunk，共127个链表节点项，每个链表长度不限。

• bin[0]为unsorted bin 存放未整理的chunk

• bin[2] ~ bin[63]为small bin 管理中等大小的chunk

• bin[64] ~ bin[127]为large bin 存放较大的chunk

fastbin

将小chunk单独管理(0x20 - 0x80,以0x10为单位,共7个),fd指向它前面那一个 (64位)

使用顺序: 先进后出 ,或者说,后进,先出, 头插!

靠近fastbinY[]的是头部

释放的时候并不会把p标志置为0

https://kiprey.github.io/2020/04/heap-3-bins/

堆命令: vis fastbin

how2heap 2.23 fastbin的例子https://github.com/shellphish/how2heap/blob/master/glibc_2.23/fastbin_dup.c

分配完三个0x8大小的堆块后的堆布局,这里有几个细节需要注意.

1.对齐问题,因为要进行16字节对齐,所以哪怕是分配了8字节,也会给一个16字节的空间,头部是16字节,所以一共32字节

Malloc(16)也是这样的,malloc(24呢) 也是一样的, 是因为会复用下一个chunk的prev_size吗? 那不复用不就不够了

这个size是包含了头部的

那岂不是如果malloc24的话,正好的空间,malloc16的话,会多了8字节可用的空间

后进先出,后面进来的会被挂到头部,可以修改一下代码,释放abc看一下,c是0,b是1,a是2

unsorted bin

(除了fastbin外) 被释放的chunk以及把大的chunk分割出来的剩下的chunk,都会先放进这里,目的主要是能让malloc有二次利用最近释放的chunk的机会

unsorted bin只有一个,位于bin[1]中 ????

无序双向链表,FIFO, 链头插入chunk,链尾取出?? 不对吧对的,看图,左边是插入,右边是取出

unsorted bin 本身是什么呢? 在哪里?

释放的时候会合并? 什么情况下, 相邻的会合并,(还有其他条件吗?)

unsortedbin
all: 0x5555557591c0 —▸ 0x555555759000 —▸ 0x7ffff7dd1b78 (main_arena+88) ◂— 0x5555557591c0

unsortedbin
all: 0x555555759380 —▸ 0x5555557591c0 —▸ 0x555555759000 —▸ 0x7ffff7dd1b78 (main_arena+88) ◂— 0x555555759380

左右箭头应该是 fd和bk的意思( 左箭头是值的意思吧)

small bin

bin[2] ~ bin[63]为small bin, 管理大小为[0x20, 0x400]的 free chunk,(64位)

small bins 中每个 chunk 的大小与其所在的 bin 的 index 的关系为：chunk_size = 2 * SIZE_SZ *index，具体如下

16-504B 0x10-0x200

32-1008B 0x20-0x400

索引为2中chunk大小为0x20 - 0x30
索引为3里的chunk大小为0x30 - 0x40
......
索引为63里的chunk大小为0x3F0 - 0x400

large bin

bin[64] ~ bin[126]为large bin 存放较大的chunk

large bin 大体上分为6大组，其中每个大组里都有若干小组

large bins 中一共包括 63 个 bin，每个 bin 中的 chunk 的大小不一致，而是处于一定区间范围内。此外，这 63 个 bin 被分成了 6 组，每组 bin 中的 chunk 大小之间的公差一致，具体如下：

tcachebin

2.26开始

malloc和free流程

raw.githubusercontent.com/cloudburst/libheap/master/heap.png

malloc

malloc的具体实现可以查看malloc.c中_int_malloc函数，大致流程如下：

1.将大小按规则对齐，得到实际要分配的大小size

2.检查size是否符合tcache bin的大小。如果是，检查对应size的entry是否有free chunk。如果有，则分配返回

3.检查size是否符合fast bin的大小。如果是，检查对应size的entry是否有free chunk。如果有，则分配返回

4.循环遍历unsorted bin，寻找可用的free chunk

• 如果遍历到的free chunk size正好和所需size相等，则分配返回

• 如果遍历到的free chunk size和所需size不等，则将其从双链表中解链(unlink)，插入到对应大小的bins中

5.根据size，以best-fit的方式，找到相应的small bin或者large bin

• 对于small bin，如果size正好合适，那么unlink之后，直接将该chunk返回给用户；否则进行切割，剩下的部分重新插入到unsorted bin中。

• 对于large bin，由于一个bin通常对应几个size，那么根据fd_nextsize的顺序，以size从大到小的顺序遍历chunk，同样采取best-fit的方式寻找合适的chunk，后续行为与small bin类似。

6.使用top chunk，将top chunk进行切割：

• 如果top chunk size足够，则将切割下来的部分返回，剩下的部分继续作为top chunk

• 如果top chunk size不够，则需要通过sysmalloc申请更多的堆空间

free

free的具体实现可以查看malloc.c中_int_free函数，大致流程如下：

如果free chunk的size属于tcache范围内，且对应大小的tcache bin没有满，则插入到相应的

tcache bin中去

如果free chunk的size属于fast bin范围内，且对应大小的tcache bin满了，则插入到fastbin

中去

如果上述条件均不满足，则通过该chunk的prev_inuse标志位检查是否可以前后向合并：

• 如果可以合并，则将需要被合并的chunk先unlink下来，合并成一个更大的chunk后再插入到

unsorted bin中（或合并到top chunk里面）

• 如果不可以合并，则将该chunk直接插入到unsorted bin中

free chunk是mmap的chunk，那么调用munmap直接返回给系统

参考资料

ctf-wiki

datacon训练营