malloc 源码分析

渗透技巧 1年前 (2023) admin
353 0 0


 作者:Ally Switch


01 前言

本篇将基于 glibc.2.31 源码,分析 malloc在源码中的具体实现。主要参考博客园上的一篇基于 glibc2.31的源码分析,以及看雪上一篇基于 glibc2.23 的源码分析。分析过程按照执行的先后顺序来。


02 源码调试

1. 按照官网的方式下载安装;

2. 网速慢,可下载 zip 包后,解压到指定目录下,然后配置~/.gdbinit文件即可;

3. 要进行源码调试,需在官网下载对应版本的源码,然后在~/.gdbinit中配置源码所在路径,我这里只配置常用的源码;

malloc 源码分析


4. 配置完后,用 gdb 调试程序,start 启动后会在程序入口断下,单步(si指令)到库函数例如 malloc 中,就可以看到源码了,如下图所示;

5. 我这里直接在 vscode 的 terminal 中调试,没用 ubuntu 自带的 terminal,这样方便查看源码。尽管已经是源码调试,但 terminal 中只能看到源码片段,并不完整,所以还是需要有源码进行辅助。

malloc 源码分析



03

__libc_malloc 主流程

1. 首先编写一个会使用到 malloc / free 的简单程序;

malloc 源码分析


2. 用 pwndbg 结合源码进行单步调试,si单步到 malloc 中,进入下图所示的状态;

malloc 源码分析


a)DISASM:反汇编窗口显示经过 .plt 表中的 stub 代码后,跳转到了 malloc 函数真正开始的地方;

b)SOURCE:源码窗口,可以看到目前位于 __libc_malloc() 函数的开始处;

c)BACKTRACE:调用栈窗口显示,此时进入了 malloc 函数中执行。


综上,可以分析得出,在程序进入 malloc 函数后,最先执行的函数 __libc_malloc()。


3. 接下来,开始分析 __libc_malloc(),这里会先分析主体流程,涉及到的其它函数与宏,会先简要概括,并在后文根据情况适当展开,我们先来看第一部分:

malloc 源码分析


a)mstate 类型对应的结构体是 malloc_state,其作用相当于 Arena Header

b)判断是否存在 __malloc_hook,若存在则调用该 hook 函数并返回。值得注意的是,在 2.34 版本中,malloc_hook 同其它大部分的 hook 都被删除了

c)atomic_forced_read(x)这个宏的作用相当于 *ptr,只不过是原子操作


d)若开启了 tcache 机制(默认开启),则:

§  调用 checked_request2size() 判断申请的空间大小是否超过边界。若未超过边界,则根据申请的大小计算出需要分配的 chunk 大小,该值保存在传入的 tbytes 参数中

§  调用csize2tidx()根据 tbytes 中指定的 chunk 大小找到对应的 tcache bin 下标

§  若 tcache 还未创建,则通过宏MAYBE_INIT_TCACHE调用tcache_init()来初始化 tcache


§  接下来进行 3 项判断,若都满足,则调用tcache_get()返回对应大小的 chunk:

(1)先前计算出的下标是否在 tcache bins 范围内(这里的 mp_ 对应的结构体是 malloc_par)

(2)tcache 是否存在

(3)下标所对应的 tcache bin 中是否仍有空闲的 tcache chunk


4.接下来分析libc_malloc()的第二部分:

malloc 源码分析


a)首先处理单线程的情况:

§  调用_int_malloc()函数分配内存,该函数是内存分配的最核心函数,后面会对其进行分析:

(1)main_arena:由于是单线程,所以只有一个主分配区。其为 malloc_state 结构体,在第一次申请时可能值为 NULL,在_int_malloc()内部会对其进行初始化;

(2)bytes:也就是申请的字节数了,注意这里的 bytes 是外层在 malloc 中传入的申请的字节数,尚未转换成需要申请的 chunk 大小。

§  如果执行成功的话,就会返回一个指向内存的指针。本质上,这个指针指向分配的 chunk 中存放数据的首地址,也就是 chunkaddr + 2 * SIZE_SZ 的位置。


b)然后是多线程的情况:

§  首先调用arena_get()获取分配区;

§  然后通过_int_malloc()从该分配区中拿到分配给咱的内存地址;

§  如果成功获取分配区,但是分配内存失败,可能是 mmap 区域的内存耗尽等多种原因。所里会调用arena_get_retry()更换分配区,然后再调用_int_malloc从新的分配区上进行分配;

§  前面两次无论是否分配成功,只要获取到了分配区,这里就会将线程锁释放。这个锁是在获取空闲分配区时加上的。在前面两次试图获取或者更换分配区时,会在不同情况下进行上锁,这个后面会讨论;

§  最后将指向分配内存的指针返回给用户;


5. 至此,__libc_malloc()的主体流程分析完毕。



04

__libc_malloc 辅助函数

这部分会对在分析__libc_malloc()时见到的几个关键的”函数 / 宏”展开分析,部分函数也在_int_malloc()中被调用。


4-1 checked_request2size

1. 首先来看checked_requeset2size();

malloc 源码分析


a)首先判断申请的内存大小是否超过了边界 PTRDIFF_MAX,这个在 64 位系统上是 0x7fffffffffffffff;

b)如果符合要求,就调用request2size()这个宏,根据申请申请大小 req,计算出需要分配的 chunk 大小返回给 sz,并返回 true。


2. 然后进入request2size(),这里涉及到的宏均已经列出,其中 SIZE_SZ,根据系统位数变化,64 位对应 8 字节,32 位对应 4 字节。我们默认环境是 64 位的,所以都以 8 字节进行计算;

malloc 源码分析


a)MALLOC_ALIGNMENT 是 2 个 SIZE_SZ 的大小,就是 0x10 字节;

b)MALLOC_ALIGN_MASK 就是 15 字节,也就是 0xF;

c)MIN_CHUNK_SIZE 是从 malloc_chunk 结构体开头,到 fd_nextsize 这个字段之前的大小,也就是 4个 SIZE_SZ,共 32 字节,即 0x20;

d)MINSIZE 算出来也是 0x20 字节。

malloc 源码分析


e)最后计算出 request2size() 的两种情况:

§  当申请的内存少于 25(0x19) 字节时,分配一个 0x20 大小的 chunk 块。这个值可以根据 malloc_chunk 结构体推算出,因为 fd & bk 这俩字段仅在 free_chunk 中有效,否则用于存放数据,并且当 chunk 被使用时,下一个 chunk 的 prev_size 字段也可以用于存放当前 chunk 的数据,这 3 个字段加起来就是 24 字节,因此,当申请的空间小于 25 字节时,一个最小 chunk (0x20)即可满足需求;

§  当大于等于 25(0x19) 字节时,就会计算出一个按照 0x10 对其的值,作为至少需要分配的 chunk 大小,具体算法参考下面的计算过程。


malloc 源码分析


4-2 csize2tidx

malloc 源码分析


a)这里的参数 x,正是前request2size()这个宏计算出的实际需要分配的 chunk 大小;

b)MALLOC_ALIGNMENT 是 2 个 SIZE_SZ 的大小,就是 0x10 字节;

c)MINSIZE 前面也算出来是 0x20 字节;

e)下面进行一个简单的演算,假设 x 的值为 0x30 字节。

malloc 源码分析


此时得到的 idx 值为 1,我们知道 idx 是从 0 开始的,最小的 tcache bin chunk 大小是 0x20 字节。因此可以得出chunksize = 0x20 + idx * 0x10,这个 chunksize 就是需要分配的 chunk 大小,这样就会好理解很多。


4-3 MAYBE_INIT_TCACHE

malloc 源码分析


a)先看 3006 行,这里

MAYBE_INIT_TCACHE宏内部调用了tcache_init();

b)回到 2972 行,我们来看tcache_init()的内部实现;

§  首先计算出 tcache_perthread_struct 结构的大小,然后为其分配空间;

§  分配空间的过程和__libc_malloc()中类似,为了防止套娃这里只分析最外层的函数;

§  调用arena_get()获取分配区,然后通过_int_malloc()从该分配区分配内存;

§  如果分配区存在但没分配到,那就调用arena_get_retry()换个分配区再分配;

§  分配完成后调用__libc_lock_unlock释放分配区,这是因为在获取分配区或者更换分配区时会进行上锁操作;

§  最后将申请到的内存赋给 

tcache_perthread_struct 结构,再调用memset()将内容初始化为0。


4-4 tcache_get

方才在__libc_malloc()中提到,如果满足一定条件,则通过tcache_get()获取到一个 chunk,传入的参数是经过宏csize2tidx算出来的所在 tcache bin 的 idx,下面来看这个函数:

malloc 源码分析


a)先根据 idx 找到对应的 tcache bin 的第一个 tcache_entry,也就是这条 bin 上的第一个 chunk 块;

b)将这条 tcache bin 上的第一个 tcache_entry 修改为当前 tcache_entry 的下一个 tcache_entry,相当于将原先第一个 tcache_entry 给取出来(这玩意本质上就是 malloc_chunk,用到的字段不同,参考前一篇介绍的内容);

c)修改此 tcache_bin 对应 tcache_counts 中表示该链上 chunk 数量的值,执行减 1 操作;

d)将取出的 chunk 的 key 字段置为 NULL,表示已经从 tcache 上取出;最后将其返回。


4-5 chunk_is_mmapped

malloc 源码分析


这个宏就是判断当前这个 chunk 是否通过mmap()申请的,这部分在前一篇介绍 malloc_chunk 时有提到,在 chunksize 的低 3 位保存了当前 chunk 的一些属性,其中下标为1的位(10b)就是用于判断 IS_MAPPED 的 M 位。


4-6 chunk2mem / mem2chunk

这俩宏功能互补,所以放在一起说。

malloc 源码分析


a)chunk2mem传入的是 chunk 的实际首地址,所以需要加上 prev_size 和 chunksize 两个字段的大小后,才能指向开始存储数据的位置。一般调用这个宏是将分配好的 chunk 转换为可以返回给用户的地址;

b)mem2chunk传入的是返回给用户的地址,即经过 chunk2mem 处理后的结果,其指向 malloc_chunk 中位于开始存储数据的位置,减去 2 个 SIZE_SZ 大小后,即可指向 chunk 实际开始的位置。


4-7 arena_for_chunk

这部分涉及的宏定义还是挺多的。

malloc 源码分析


a)这个宏传入的参数是经过mem2chunk得到的 chunk 地址,用来获取 chunk 所在的分配区(arena);

b)首先会调用chunk_main_arena这个宏,判断是否设置了 NON_MAIN_ARENA 位,这个值若未设置,就可以直接判断出是 main_arena(主分配区);

c)否则,先计算 HEAP_MAX_SIZE – 1 取反后的值,将其与 chunk 所在地址进行与操作,从而得到 chunk 所在堆的 heap_info 地址(这么做是因为每次申请的堆的起始地址是与 HEAP_MAX_SIZE 对齐的,因此这样可以取到堆的起始地址,从而拿到堆的 heap_info);

d)这里再回顾一下前一篇中总结的概念:一个堆对应一个 heap_info,一个 thread_arena(非主分配区) 对应一个 malloc_state,一个 thread_arena 中包含多个堆

e)拿到 heap_info 的地址后,就可以根据 ar_ptr 字段得到堆所在的分配区的地址了。


4-8 arena_get

这里涉及到的函数比较多,分开来讲。

malloc 源码分析


·   arena_get:

a)直接从 thread_arena 获取分配区(主分配区的获取不使用arena_get());

b)将获取到的分配区和申请内存大小作为参数传入 arean_lock()。


·   arena_lock:

a)判断是否成功获取分配区,若成功获取,则调用__libc_lock_lock对分配区上锁;

b)若获取失败,则调用arena_get2()重新获取分配区。


·   arena_get2:

a)这个函数就干了一件事,调用get_free_list()获取分配区,如果获取成功则将分配区返回,这里get_free_list()返回的是 malloc_state 结构体。


·   get_free_list:

a)想要弄明白这个函数,需要回顾下前一篇中介绍 malloc_state 的部分;

b)这里的 replaced_arena 是给下面要分析的arena_get_retry()用的,调用arena_get()时这个值通常为 NULL;

c)先获取 free_list 上的第一个空闲分配区(free_arena),这是一个串着所有空闲分配区的链表,然后将其从 free_list 上摘下来;

d)摘下来后,修改分配区的 attached_threads 的值为1,表明该分配区附加到当前线程;如果是通过arena_get_retry调用的,则还会将线程与原先的分配区(replaced_arena)进行 detach 操作;最后将新获取的分配区返回。


4-9 arena_get_retry

malloc 源码分析


对于非主分配区来说,如果分配区没空间了,可以考虑试着从主分配区分出来一点;否则,试着通过sbrk()进行分配区扩展;如果还不行的话,就试试其它空闲的分配区。这里最终调用回到了arena_get2()上面,前面刚分析过,就不再赘述了。


05

_int_malloc 主流程

5-1 初始校验

malloc 源码分析


·   _int_malloc()接收两个参数,分配区和需要分配的大小,然后从分配区中分配满足需求大小的 chunk;

·  变量中需要注意,mchunkptr 与 mbinptr 类型均是 malloc_chunk 结构体,其余参考注释即可;


·   进入函数后最先会遇到两处校验:

a)checked_request2size()前面分析过了,这里主要是判断申请的内存大小是否超过了边界,若未超过,则会计算出至少需要分配的 chunksize,将值保存到 nb 中,然后进入下一个判断;

b)接下来会判断 av 也就是传入的分配区是否为空,通常不为空。但如果为空,说明前面arena_get()与arena_get_retry()都未能获取到分配区。此时就会调用sysmalloc()去请求一个 chunk,通过alloc_perturb()初始化后,将这个 chunk 返回。这里 perturb_byte 的值默认为 0;


·   这里需要补充一些宏的含义(此处来自xi@0ji233的文章)。

malloc 源码分析


5-2 Fast Bin 处理流程

1. 在 fast bin 处理的开始处有一个宏定义如下:

malloc 源码分析


这个宏主要是通过 lock-free 的技术实现单向链表删除第一个 node 的操作,暂时不必关注


2. 接下来进入 fast bin 的处理过程,源码的格式看着可能比较乱,这里分别框出来来看:

malloc 源码分析


a)首先,判断 nb(先前计算出的所需 chunk 大小)是否位于 fast bin 范围内,如果在范围内,就进入红框做进一步处理,否则直接跳过 fast bin 的处理逻辑;


o   红色方框:

§  先通过fastbin_index算出 idx,即所需的 chunk 位于哪条 bin 上;

§  调用fastbin获取对应 bin 的链表头,并将链表上的第一个 chunk 地址赋给 victim;

§  判断 vicitim 是否存在,若不存在,说明这条 bin 上已经没有多余的 chunk 了,又因为 fast bin 中是大小严格匹配的,如果大小符合的 chunk 不存在,也不会去寻找其它的 bin,就会直接跳过 fast bin 剩余的处理逻辑。


o   橙色方框:

§  进入橙色方框,说明 chunk 存在。这里只做了一件事,就是将这个 chunk 从 bin 上摘下来;由于 fast bin 是先进后出单链表,具体手法就是令当前 bin 的指针指向最后一个 chunk 的前一个。其中REMOVE_FB这个宏对应的是多线程的处理。


o   蓝色方框:

§  这部分主要是两个 check,第一个 check 是用 vicitim 再算一遍,判断其是否属于它原先所在的 bin;

§  第二个 check 是对一些标志位的 check。


o   粉色方框:

§  这里是仅在开启了 tcache 的情况下才会发生的操作,当然 glibc2.31 版本中 tcache 是默认开启的;

§  首先根据申请的 chunk 的大小,计算出当前 fast bin 对应的 tcache bin 是哪一个;

§  如果当前 fast bin 不为空,且 tcache bin 仍有多余空间(少于 7 个 chunk),就会将 fast bin 中的 chunk 移动到 tcache bin 中,这个操作放在一个循环里,每轮都会判断一次 fast bin 是否还有 chunk 以及 tcache bin 是否还有空间。从 fast bin 摘下来的操作和前面橙色方框中的一样;放入 tcache bin 中则是用的 tcache_put。


o   绿色方框:

§  粉色方框是不影响整体逻辑的部分,这里可以直接跟着蓝色方框来看;

§  拿到 vicitim 后,调用chunk2mem将指针指向 chunk 存储数据的开始地址;

§  再调用alloc_perturb()对这块内存初始化,然后返回给用户。


5-3 Small Bin 处理流程

1. 如果 fast bin 中没有合适的 chunk,且所需 chunk 的大小位于 small bin 范围内,那么就会进入 small bin 的处理流程。small bin 与 fast bin 的处理流程大体看着类似,但是细节有所不同:

malloc 源码分析



a)首先是判断申请的 chunksize 范围是否在 small bin 的范围内,不在就跳过这段处理逻辑,在的话就;

§  先调用smallbin_index算出 chunk 所在的 idx 是多少;

§  再调用bin_at得到 idx 在 bins 中对应的那个 bin 的链表头。这里简单回顾一下,bins 是一个数组,数组中包含了 unsorted bin、small bin 以及 large bin 中各个 bin 的链表头,这些 bin 都是双链表


b)然后判断这个链表头的后一个元素是否还是它自己(注意这里在判断的同时,也进行了赋值操作,此时该链表若至少存在 1 个 chunk,那么 vicitim 指向的就是这个 chunk 的地址),如果是,说明这个 bin 已经空了,就跳过 small bin 的处理逻辑,因为 small bin 和 fast bin 一样也是严格匹配的,一旦大小不符合,就会跳过这段处理逻辑:

§  否则,获取 vicitim 的下一个 chunk,victim 是刚刚在进行判断链表是否为空时,取到的第一个 chunk,并判断这个 chunk 与 victim 之间的双链表是否完整,从而防止一些堆利用;

§  然后,通过set_inuse_bit_at_offset将 victim 之后(进程虚拟内存中紧挨着 victim 地址的 chunk)的一个 chunk 的 prev_inuse 设置为 1,表示 victim 这个 chunk 正在被使用。fast bin 处理过程中是没有这个操作的,因为 fast bin 中的 chunk 默认都设置了 prev_inuse 的值,从而防止 chunk 之间的前后合并;

§  设置完以后是一个常规的链表操作,将 victim 从双链表上摘下来;

§  然后再判断一下用来分配这个 chunk 的分配区是否为主分配区,若是,则设置相应字段的值;

§  接着调用check_malloced_chunk进行一些字段的检查。


2. 接下来是针对 tcache 情况的一些处理以及将 chunk 返回给用户,这部分和 fast bin 处理过程也很像,简单来看下:

malloc 源码分析


a)tcache 处理的部分和 fast bin 中 tcache 处理的部分基本上一样,就是在对应大小(刚刚分配的 chunk 的大小)的 small bin 不为空且 tcache bin 还有额外空间时,通过循环将 small bin 中的 chunk 塞到 tcache bin 中;且每次循环判断一次 small bin 是否为空,以及 tcache bin 是否满了。这里仅说下不同点:

§  small bin 中的 chunk 放入 tcache bin 中时需要设置 prev_inuse;fast bin 中的 chunk 默认是设置了的;

§  small bin 断链进行的是双链表操作;fast bin 是单链表操作;

§  small bin 需要判断是否为主分配区,并设置相应字段;fast bin 没有;


b)最后和 fast bin 一样,将分配的好的 chunk 初始化后返回给用户。



5-4 Unsorted Bin 处理流程

1. 如果在 small bin 或者 fast bin 处理流程中找到了合适大小的 chunk,那么程序就返回了。如果执行到这里,说明 chunk 大小位于 large bin 中或者在 small bin 和 fast bin 中没有找到所需大小的块,接下来就沿着这个思路结合源码继续分析;

malloc 源码分析


a)首先的一个 else 块,它对应前面的if (in_smallbin_range(nb)),因此,如果进入了 else 语句,那么说明所需 chunk 的大小位于 large bin 中,这里会做两件事:

§  通过宏largebin_index获取所需 chunk 在 large bin 中的 index,即所在的 bin 链;

§  判断 fast bin 是否存在(即是否已经初始化),若存在,则调用malloc_consolidate()将 fast bin 中的所有 chunk free 掉并与前后的块合并,然后存到 unsorted bin 中。


b)如果没有进入 else 语句,说明所需的大小位于 fast bin 或者 small bin 中,但是 fast bin 与 small bin 分配时要求大小严格匹配,因此没有找到合适的块,所以就会进入到 unsorted bin 是处理流程。并且对于 large bin 范围的申请,在 else 语句执行完后,也会执行到此处:

§  glibc2.31版本默认开启 tcache,因此会执行此处的代码;

§  调用csize2tidx获取所需 chunk 大小在 tcache bin 中的 idx,如果 nb 的大小位于 tcache 范围内(tcache 范围涵盖了 large bin 中的前面一小部分),则将其赋值给变量 tcache_nb。


2. 接下来进入一个大的 for 循环,该循环可以忽略,因为一直延续到__int_malloc结束,重点在于这个 while 循环;

malloc 源码分析


a)unsorted bin 是一个双链表,位于 bins 上的第一个;

b)迭代循环 unsorted bin 中的所有 chunk,变量 iters 跟踪迭代次数;

c)victim 表示当前 chunk,bck 为 unsorted bin 上 victim 的后一个 chunk,next 为堆上 victim 的后一个 chunk

d)chunksize用于获取 chunk 的大小,chunk_at_offset用于获取下一个 chunk 的地址;


e)接下来会进行一堆 check:

§  检查 victim 和 next 的 size 不能小于最小的 chunksize,也不能大于所属分配区已经分配的内存大小;

§  检查 next 的 prev_size 是否等于 victim 的 size;

§  检查 victim->bk->fd 是否等于 victim,保证双链表完整性;

§  检查 victim->fd 是否等于 unsorted_chunks(av) 这是因为在每轮循环开始有 victim = unsorted_chunks(av)->bk;

§  检查 victim 是否设置了 prev_inuse,因为进入 unsorted bin 中的 chunk 都已经清空了该值。


3. 经过一系列 check 后,是针对各类情况的处理

malloc 源码分析


a)如果同时满足以下 4 个条件,则会进入对应的处理:

§  所需 chunk 的大小的范围在 small bin 中

§  unsorted bin 中仅剩最后一个 chunk:

(1)bck = victim->bk; 

(2)victim = unsorted_chunks(av)->bk。

§  victim 是 last remainder chunk;

§  该 last remainder chunk 的 size 需大于所需 chunk 大小与

MINSIZE 之和。


b)具体是进行一次 chunk 切割的操作,把所需大小的 chunk 返回给用户,余下的部分作为 last remainder chunk 回到 unsorted bin 中,下面简单分析下这个过程:

§  计算出 remainder_size,然后通过chunk_at_offset拿到分割后 remainder 的地址(成为新的 last remainder chunk)

§  修改 unsorted bin 的头指针,将其指向 last remainder chunk 的位置;

§  如果 remainder 大小不在 small bin 范围内,就添加 fd_nextsize 与 bk_nextsize 指针;

§  设置 victim 与 remainder 的标志位;

§  将 victim 存储数据的地址(victim + 2*SIZE_SZ)返回给用户。


4. 若不满足前面的判断条件,或 reminder 不够分割了,则会继续走到这里;

malloc 源码分析


a)首先会 check 一下链表的完整性,校验成功后,会将当前的 chunk 也就是 victim 从 unsorted bin 上面摘下来,方便后续操作;

b)然后判断一下,如果 victim 的 size 刚好符合申请所需的 chunk 大小,那么先设置好标志位,然后:

§  如果开启了 tcache(glibc2.31中默认开启),并且victim size 对应的 tc_idx 所在 bin 中仍有空余位置(少于7个),那么就调用tcache_put()将 victim 放入到 tcache 中;

§  如果对应的这条 tcache bin 已经满了,那么就直接将其返回给用户。


5. 接下来这步是 unsorted bin 处理的核心,它会将 unsorted bin 中遍历的 chunk 根据 size 放入对应的 small bin 或者 large bin 中,这是唯一一次将 chunk 放入 small bin 或者 large bin 的过程;

malloc 源码分析



a)如果 vicitim 的 size 位于 small bin:

§  获取该 size 在 small bin 中的 index;

§  获取该 index 所在 bin 的头指针作为 bck;

§  获取头指针后的第一个 chunk 指针作为 fwd;

§  使用头插法将 victim 插入到 bck 与 fwd 之间的位置。


b)否则,即 victim 的 size 位于 large bin 时:

§  获取该 size 在 large bin 中的 index;

§  获取该 index 所在 bin 的头指针作为 bck;

§  获取头指针后的第一个 chunk 指针作为 fwd,这里的第一个 chunk 可以理解为这条 bin 链上 size 最大的 chunk,因为 large bin 上每条 bin 里的 chunk 大小并不相同,可以参考下图chunk#1在这条 bin 链上的位置。当然这张图是针对 glibc2.23 版本的 large bin,在 glibc2.31 版本下 large bin 的排列与下图有所不同,稍微我们会说到。

malloc 源码分析


§  接下来会有一系列条件判断,以及对应的处理逻辑,这里我将不按照代码前后顺序去分析其逻辑,而是直接将不同条件及处理逻辑进行对应,这样也许更加清晰:

情形一:fwd == bck

此时 large bin 中不包含任何 chunk,victim 会将其 fd_nextsize 与 bk_nextsize 设置成自己,然后链入到 bin 上。此时 victim 的 fd 和 bk 都是 bin 链表头。


情形二:fwd != bck 且 victim_size < #n_size(bck->bk)

这个情形可以参考上图,#n_size 指的就是上图蓝色的那个 chunk,前面 bck 指向了链表头,bck->bk 就指向最后一个 chunk,它是目前 large bin 上 size 最小的 chunk。如果 victim 的 size 比最小的 chunk 还要小。那么就会让 vicitim 作为最后一个 chunk。

注意这里所说的最后一个 chunk,参考上图,large bin 的 bin 链中相同大小的 chunk 用 fd/bk 相连,不同大小的 chunk 用 fd_nextsize/bk_nextsize 相连。当前这种情况下,large bin 中还没有与 victim_size 相等的 chunk,且 vicitim_size 小于这条 bin 上的所有 chunk,因此被放在了最后一个的位置。

这里具体所作的操作是,将 fwd 设置为链表头,bck 设置为原先最小 chunk 中的某一个(当有多个大小相同 chunk 的情况下,这个 bck 是与链表头相连的那一个,即这些 chunk 中的最后一个,而不是链在 fd_nextsize/bk_nextsize 上面的那个,因为它是相同大小 chunk 链上的第一个。另外通过它是用 fwd->fd->bk_nextsize 来定位的,而不是fwd->bk 来定位,也可以判断出这一点),fd_nextsize 指向原先最大 chunk 中的第一个,bk_nextsize 指向原先最小 chunk 中的第一个。


情形三:fwd != bck 且 victim_size > fwd_size

large bin 不为空,且不包含 victim_size 的 chunk,victim_size 大于链表中最小 chunk 的 size。

这一步判断时,会通过循环,从前往后找(最大的 chunk 开始往最小的 chunk 找)直到 victim_size >= fwd_size(当前 chunk 的大小),这里是大于的情况,也就说,当前 large bin 中并没有与 victim_size 相同的 chunk 存在,这里的操作和情形二比较类似,区别是情形二是在链表尾进行操作,这里则是在链表中间进行操作。

具体会通过 fd_nextsize/bk_nextsize 将 victim 放到 fwd 与 fwd->bk_nextsize 之间,这样保持了不同大小之间的 chunk 链接。然后将 victim 串在 fwd 与 fwd->bk 之间。这里注意 fwd->bk_nextsize 与 fwd->bk 指向的可能是不同 chunk。如果 fwd->bk_nextsize 指向的 chunk 相同大小的仅有它一个,那么此时 fwd->bk 与 fwd->bk_nextsize 是相同的,否则,fwd->bk 指向的是 fwd->bk_nextsize 所在 chunk 大小相同的这个链表里最靠后的一个 chunk。通过 fwd->bk_nextsize->fd->fd->fd…这种形式来访问。


情形四:fwd != bck 且 victim_size == fwd_size

large bin 不为空,包含 victim_size 的 chunk。

此时通过遍历相同大小的第一个 chunk(通过 fd_nextsize/bk_nextsize 相连),找到后将其插入到 fwd->fd 与 fwd 之间的位置,每次都是如此,也就是说新来的相同大小的 chunk 永远是放在第二个位置,原先的将会依次递增,然后结束。这下就可以解释情形三了,如果已经存在相同大小的 chunk,则找到这个大小位于 fd_nextsize/bk_nextsize 链上的那个 chunk 作为 fwd,将 victim 链入到 fwd 与 fwd->fd 之间,也就是相同大小 chunk 链表的第二个位置;如果不存在相同大小的 chunk,找到比 victim_size 小的里面最大的一个位于 

fd_nextsize/bk_nextsize 链上的那个 chunk 作为 fwd,将 victim 链入到 fwd 与 fwd->bk 之间

fd_nextsize/bk_nextsize 那条链上的链入操作比较好理解,这里解释这么多主要是防止被上面一张图 large bin 的排布所误解,glibc2.31 这个版本的 large bin 构筑可以参考下图,图片来自pukrquq。

malloc 源码分析


6. 这里是 unsorted bin 处理流程的第六步,在第四步时,如果从 unsorted bin 中摘下来的 chunk 刚好满足我们的需求,并且 tcache 仍然有多余的空间,那么 ptmalloc2 会先将这个 chunk 放到对应的 tcache bin 中,然后回到循环开头,直到下一个从 unsorted bin 中摘出来的 chunk 不满足需求(如果满足需求,同样会进入 tcache bin,若 tcache bin 已满,则直接返回给用户,不会执行到此处),那么再根据其 size 被分配到 small bin 或者 large bin 以后,就会执行到这里。

因为代码块不同,这里我们分为 3 个部分来看更为清晰些:

malloc 源码分析


o   红色方框:

首先前面在从 unsorted bin 中取出 chunk 时,若发现符合要求的则会放入 tcache bin 中,并将 return_cached 的值设置为 1,会用于此处的判断。此外,tcache_unsorted_count 会在每次执行到这里时都会自增1,说明此轮没有 chunk 进入 tcache bin,而是进入了 large bin/ small bin。如果执行到此处的次数超过了 tcache_unsorted_limit 的值(默认是 0),就会调用 tcache_get()从 tcache bin 中取出符合需求的 chunk 返回给用户。


o   绿色方框:

注意这部分有个大括号,闭合了前面的 while 循环,这里说的是,最多遍历 unsorted bin 一万次。不然一次产生了太多的 unsorted bin,然后我 malloc 一次,结果一直在这个循环里分配 unsorted bin 上面的 chunk,迟迟等不到分配的内存,所以这里会设定一个遍历的最大值。


o   蓝色方框:

最后,出了 while 循环,也就遍历完 unsorted bin 了,这时会判断一下在先前遍历时是否找到符合需求的 chunk,若找到了且被放入了 tcache bin 中,则 return_cached 会被设置,此时调用tcache_get()即可。至此,unsorted bin 的处理逻辑就全部结束了。若仍未找到合适的 chunk,则会继续往后执行。



5-5 Large Bin 处理流程

1. 在将 unsorted bin 中的 chunk 分配到 small bin 与 large bin 后,若所需的 chunk 大小位于 large bin 的范围区间,则会从这里开始处理;

malloc 源码分析


o   第一层校验

会判断所需的 chunk 大小 nb 是否位于 small bin 范围内,这里再判断一遍的原因是 bin_at这个宏是根据 size 获取在 bins 中的 idx 的,前一篇我们提到,bins 中包含了 unsorted bin,small bin 以及 large bin。这里又判断一次范围是否在 small bin 也是为了确保,bin_at 的结果会落在 large bin 在 bins 对应的 idx 范围内;


o   第二层校验

是确保 large bin 不为空,且 large bin 中最大的 chunk 要比所需的 chunk 要大。first宏用于获取 idx 所在 bin 中第一个 chunk,即当前 idx 中最大的 chunk;


o   接下来开始在 large bin 中寻找到最合适的那个 chunk,逻辑如下:

a)与插入 chunk 到 large bin 中不同,这里是从最小的 chunk 开始遍历,直到找到一个 chunk 大于等于所需的 chunk 大小;

b)这里有两处判断,第二处用来确保 victim 所在的相同大小的双链上至少有两个 chunk,这样我们方便把第二个 chunk,也就是 victim->fd 给分配出去。victim != last(bin)主要是判断 size 最小的那个双链是否有两个或更多 chunk,因为这个双链上最后一个 chunk 与 bin 链表头相连,若相等,则说明该链上就只有一个 chunk,所以这两个判断证明的事是一样的;


c)如果这条链上存在至少 2 个 chunk,那就取第 2 个,否则就用第 1 个。然后调用unlink_chunk()将这个 chunk 断链,并判断切去所需大小 nb 后,余下空间是否构成一个最小 chunk:

(1)若不能,则对这个 chunk 设置并检查相应的标志位后,返回给用户;

(2)若能,则会切割出 nb 大小的部分,余下的部分作为 reminder 链入到 unsorted bin 中并根据大小决定是否设置 bk_nextsize / fd_nextsize,并对 reminder 与分割出的部分分别设置标志位,将分割出的部分返回给用户。此处分割剩下的 reminder,并没有被设置为该分配区的 last reminder chunk。分析到这里为止,仅在 unsorted bin 处理逻辑中的一次分割会设置 last reminder chunk,这点需要注意。


2. 如果在前面找到的 large bin 中未发现符合要求的 chunk,就会来到这一步。这部分代码看着不复杂,但是理解起来也不是非常容易,咱们来逐条分析:

malloc 源码分析


a)++idx:在前一个 bins[idx] 所表示的 large bin 中没有找到合适的块,那么就增加 idx 的值,去 bins[idx++] 去找是否有符合的块。当然,理论上 bins[idx++] 中只要存在 chunk,就一定可以满足需求;

b)bin_at:这个宏之前已经多次出现,就是拿到这个 idx 在 bins 对应的链表的头节点,这个头节点是一个 malloc_chunk 结构体,通过头节点的 fd/bk 指针可以访问这个 bin 上的第一个块(对应 large bin 中最大的块)与最后一块(对应 large bin 中最小的块);


c)接下来 3 行相互之间有所关联,需要放在一起来看:

§  首先 block,map,bit 这三个变量都是 unsigned int 类型;

§  malloc_state 结构中有一个 binmap,它用来快速查找对应 index 所在的 bin 是否为空。这里通过 av->binmap 来访问;

§  binmap 是个数组,长度为 4,每个元素都是一个 32 位的整数,加起来刚好是 128 位,刚好对应 bins 中的每个 bin,这 128 位可以看作是下标,若该下标的值置0,则说明 bin 为空;

§  idx2block 这个宏的操作是将 idx 右移 5位,即将 idx 除 32,得到一个位于 0~3 范围内的值,从而找到该下标位于 binmap 中的第几个 32 位的整数上;

§  idx2bit 这个宏如下,作用是取到 idx 对应 large bin 的下标

    #define BINMAPSHIFT      5
    #define idx2bit(i)       ((1U << ((i) & ((1U << BINMAPSHIFT) – 1))))


3. 接下来会进入一个死循环,直到找到一个符合要求的 chunk;

malloc 源码分析


if 语句有两个条件(来自付师傅的笔记):

(1)bit > map:如果bit大于map说明在本block中,map中大于bit的位置都为0,表示对应的bin都为空,无需继续检查

(2)bit == 0:通过idx2bit转化为32位的数据中,应该是31个0和一个1组成的,所以bit!=0;且因为前面进行了++idx,所以不可能转变成对应第一个bin的unsorted bin


然后进入循环,判断当前 block 的值是否为 0,即这个 block 所表示的 32 个 bin 是否都是空的,如果是空的,就找下一个 block。如果全部都为空,就跳转到 use_top 中进行处理。如果不为空,那么找到下标对应的 bin 并将 bit 置 1。


a)while 循环里通过 bit 与 map 相与是否为 0 来判断这个 bin 是否为空。若为空,则通过next_bin来访问下一个 bin,这里的下一个可以理解为 bins[80] -> bins[81] 这种形式,同时 bit 也进行左移,即移动到这个 block 里面与表示这个 bin 所在位置的下标处;

b)此时这个 bin 应该不是空的,但还是要判断一下。通过 last 获取到 bin 中的第一个元素,判断是否与自身相等,若相等,则说明 bin 为空,那么将这个 bin 在 binmap 中对应的 bit 置零,然后继续查看下一个 bin。


4. 若不为空,那这个 bin 里面的 chunk 肯定是可以拿来用的,所以这里取的是最小的 chunk 作为 victim。接下来的操作就和 unsorted bin 里面满足 4 个条件的那个操作,以及前面在一开始就可以找到一个合适的 large bin chunk 时的操作是类似的。就是先切割,挂到 unsorted bin 中,返回给用户这么几个操作,这里就不多赘述了。唯一需要注意的是,若所需的 chunk 位于 small bin 的范围(有人可能问这都校验多少次了为什么还可能是 small bin 范围,那可能是因为 small bin 和 unsorted bin 中都没有 chunk,最后只能来 large bin 申请),那么这里分割后的 reminder 会被设置为 last remainder chunk。这是第二次设置 last remainder chunk 的地方。

malloc 源码分析


5-6 Top Chunk 处理流程

如果 large bin 也是空的或者满足不了需求怎么办,那么前面有一处 goto use_top,就会来到这里,试图分配 top chunk。

malloc 源码分析


a)先通过 av->top 获取到 top chunk,通过宏 chunksize 获取到 top chunk 的大小。然后先做一个判断,看这个 top chunk 的 size 是否超过了 av->system_mem(这个值表示系统调用时申请的内存大小)。这个判断在 unsorted bin 的处理流程开始处也进行过一次;


b)接下来,则根据 top chunk 的情况分类处理:

§  如果 top chunk 超过 nb(所需 chunk 大小) + MINSIZE,那么操作和前面 unsorted bin 与 large bin 分割类似。此处分割不会设置 last reminder chunk;

§  否则,如果存在 fastbin,那么先调用 malloc_consolidate() 将 fastbin 合并;再根据所需的 chunk 大小设置 idx 的值,然后回到死循环的开头(图中紫色大括号,对应 unsorted bin 处理流程的开始部分)再进行一轮判断;

§  若上面俩都没执行,那么调用 sysmalloc() 通过系统调用来进行内存分配,这部分可参考Pwnki的分析。





06


参考链接

1.     博客园:glibc2.31 malloc 与 free 源码分析

2.     看雪:malloc源码分析

3.     CSDN:glibc下malloc与free的实现原理(二):malloc函数的实现

4.     堆学习之 fastbin-attack

5.     看雪:how2heap深入浅出学习堆利用


原文始发于微信公众号(中孚安全技术研究):malloc 源码分析

版权声明:admin 发表于 2023年3月31日 下午5:21。
转载请注明:malloc 源码分析 | CTF导航

相关文章

暂无评论

您必须登录才能参与评论!
立即登录
暂无评论...