本篇主要参考了https://xz.aliyun.com/t/10650?page=1
对其中的知识点进行了理解和重新排序,便于对其更好的理解
0x00 堆的数据结构,申请与释放
堆和栈都是一种数据结构,在内存中线性分布储存数据,栈由高地址向低地址伸展,堆由低地址向高地址伸展。堆的位置一般都在bss段的高地址处。
在程序运行过程中,堆可以提供动态分配的内存,允许程序申请大小未知的内存。堆其实就是程序虚拟地址空间的一块连续的线性区域,它由低地址向高地址方向增长。我们一般称管理堆的那部分程序为堆管理器。
目前 Linux 标准发行版中使用的堆分配器是 glibc 中的堆分配器:ptmalloc2。ptmalloc2 主要是通过 malloc/free 函数来分配和释放内存块。
在真正了解堆之前,需要以下基础知识:
0x01 arena
arena包含一片或者数片连续的内存,对快将会从这片区域中划分给用户。主线程的arena被称为main_arena,它包含start_brk 和 brk之间的这片连续内存。一般把start_brk 和 brk之间这片连续的内存称为堆。
主线程arena只有堆,子线程的arena可以有数片连续的内存。如果主线程的堆大小不够分的话,就要通过brk函数调用来扩展,但是子线程分配的映射段大小是固定的,不可以扩展的,所以子线程分配处理的一段映射段不够用的话就需要再次使用mmap函数来分配新的内存。
0x02 bin & chunk
chunk
chunk是glibc管理内存的基本单位,整个堆在初始化后会被当成一个free chunk,称为top chunk,每次用户请求内存时,如果bins中没有合适的chunk,malloc就会从top chunk中进行划分,如果top chunk的大小不够,就调用brk函数扩展堆的大小,然后从新生成的top chunk中进行划分。用户释放内存时,glibc会先根据情况将释放的chunk与其他相邻的free chunk合并,然后加入合适的bin中。
chunk的数据结构如下
struct malloc_chunk{
INTERNAL_SIZE_T mchunk_prev_size; 记录被释放的相邻chunk的大小。
INTERNAL_SIZE_T mchunk_size; 记录当前chunk的大小,chunk的大小都是8字节对齐
struct malloc_chunk *fd;
struct malloc_chunk *bk;
struct malloc_chunk *fd_nextsize;
struct malloc_chunk *bk_nextsize;
}
根据chunk的结构可知,最小的chunk为0x20(x86下为0x10)。
首先在x64下,一个地址的内存大小就为0x8,那么一个最小的chunk,用pre size记录上一个chunk大小,用size记录自己的大小,size下面是一个fd,再下面是data,所以如果要最小的话,一共是4个0x8,那么就是0x20的大小。
那么同理,在x86下,一个地址的内存大小为0x4,所以就是上述的一半,既最小的堆在x86中就是0x10的大小。
bin
管理arena中空闲chunk的结构,以数组的形式存在,在数组元素为相应大小的chunk链表的链表头存在于arena的malloc_state中
保管用户暂时不需要的内存空间,当用户需要重新申请内存的时候,就不需要向操作系统要新的内存空间了,如果回收站中有正好满足你需求的空间,就把那份空间分配给你就可以了。
根据chunk的大小,将bin如下进行分类
-
Fast bin(单向链表)
Fast bin分类的chunk的大小为32-128字节(0x80)字节,如果chunk在被释放时发现其大小满足这个要求,则将该chunk放入Fast Bin。一个最新被加入的Fast Bin的chunk,其fd指针指向上一次加入的Fast Bin的chunk的pre size。
-
Small bin(双向链表)
Small bin保存大小为32-1024(0x400)字节的chunk,每个放入其中的chunk为双链表结构,不同大小的chunk储存在对应的链接中。由于是双链表结构,所以他的速度比fast bin慢一些。
-
Large bin(双向链表)
大于1024字节的chunk使用Large Bin进行管理。相同大小的Large Bin使用fd和bk指针连接,不同大小的Large bin通过fd_nextsize和bk_nextsize按大小排序连接。
-
Unsorted Bin(双向链表)
Unsorted Bin相当于Ptmalloc2堆管理器的垃圾桶。chunk被释放后,会先加入Unsorted Bin中,等待下次分配使用。在堆管理器的Unsorted Bin不为空的时候,用户申请非Fast Bin大小内存会先从Unsorted Bin中查找,如果找到符合该申请的chunk(等于或者大于),则直接分配或者分割该chunk。
0x03 malloc
在glibc的malloc中,有以下说明:
malloc 函数返回对应大小字节的内存块的指针。
当 n=0 时,返回当前系统允许的堆的最小内存块
当 n 为负数时,由于在大多数系统上,size_t 是无符号数(这一点非常重要),所以程序就会申请很大的内存空间,但通常来说都会失败,因为系统没有那么多的内存可以分配。
malloc --> __libc_malloc --> _int_malloc
__libc_malloc(size)
用户申请的字节一旦进入申请内存函数中就变成了 无符号整数。
寻找钩子hook ----》 寻找arena ----》 调用_int_malloc分配内存 -+--》成功,返回内存
↑ |
| ↓
+-----分配失败,再寻找一个arena
_int_malloc()
--------------------------------------------------------------------------------
将size转化为对应的chunk大小 ----》 fastbin ----》 遍历(后进先出),检查大小是否符合 ----》 符合则计算索引 ----》 chunk转换为内存返回
根据大小选择bin ----》 smallbin ----》获取索引、指针 ----》 检查该bin是否为空 ----》 不为空 ----》将链表中最后一个chunk分配(先进先出)
| +----》 初始化
+---》 该bin为空
----》 不在fastbin和smallbin中 ----》 malloc_consolidate():处理fastbin ----》 可以合并的合并,然后放 unsorted bin ----》大循环
----------------------------------------------------------------------------------
大循环 ----》 遍历unsorted bin ----》 FIFO寻找大小刚好合适的bin ----》若有,bin转为内存后返回
循环10000次 ----》若没有,则将当前的unsorted bin按照大小放至对应的small或large中
----》 遍历large bin ----》对应的 bin 中从小(链表尾部)到大(头部)进行扫描 ----》 找到第一个合适的返回
----》 若大小合适的bin都不存在,则在map中找更大的bin遍历 ----》 找到,返回内存
----》 找不到,使用top chunk ----》 满足,分割后返回
----》 不满足,使用 sysmalloc 来申请内存
------------------------------------------------------------------------------------
//从 fastbin 的头结点开始取 chunk(LIFO)
0x04 _libc_malloc
一般我们会使用 malloc 函数来申请内存块,可是当仔细看 glibc 的源码实现时,其实并没有 malloc 函数。其实该函数真正调用的是 **libc_malloc 函数。为什么不直接写个 malloc 函数呢,因为有时候我们可能需要不同的名称。此外,**libc_malloc 函数只是用来简单封装 _int_malloc 函数。_int_malloc 才是申请内存块的核心。下面我们来仔细分析一下具体的实现。
该函数会首先检查是否有内存分配函数的钩子函数(__malloc_hook),这个主要用于用户自定义的堆分配函数,方便用户快速修改堆分配函数并进行测试。这里需要注意的是,用户申请的字节一旦进入申请内存函数中就变成了无符号整数。
// wapper for int_malloc
void *__libc_malloc(size_t bytes) {
mstate ar_ptr;
void * victim;
// 检查是否有内存分配钩子,如果有,调用钩子并返回.
void *(*hook)(size_t, const void *) = atomic_forced_read(__malloc_hook);
if (__builtin_expect(hook != NULL, 0))
return (*hook)(bytes, RETURN_ADDRESS(0));
接着会寻找一个arena来试图分配内存
arena_get(ar_ptr, bytes);
然后调用 _int_malloc 函数去申请对应的内存。
victim = _int_malloc(ar_ptr, bytes);
如果分配失败的话,ptmalloc 会尝试再去寻找一个可用的arena,并分配内存。
/* Retry with another arena only if we were able to find a usable arena before */
if (!victim && ar-ptr != NULL)
{
LIBC_PROBE(memory_malloc_retry, 1, bytes);
ar_ptr = arena_get_retry(ar_ptr, bytes);
victim = _int_malloc(ac_ptr, bytes);
}
如果申请到了arena,那么在退出之前还得解锁。
if (ar_ptr != NULL) __libc_lock_unlock(ar_ptr->mutex);
判断目前的状态是否满足以下条件
- 要么没有申请到内存
- 要么是 mmap 的内存
- 要么申请到的内存必须在其所分配的 arena 中
0x05 _int_malloc
_int_malloc 是内存分配的核心函数,其核心思路有如下
- 它根据用户申请的内存块大小以及相应大小 chunk 通常使用的频度(fastbin chunk, small chunk, large chunk),依次实现了不同的分配方法。
- 它由小到大依次检查不同的 bin 中是否有相应的空闲块可以满足用户请求的内存。
- 当所有的空闲 chunk 都无法满足时,它会考虑 top chunk。
- 当 top chunk 也无法满足时,堆分配器才会进行内存块申请。
在进入该函数后,函数立马定义了一系列自己需要的变量,并将用户申请的内存大小转换为内部的 chunk 大小。
- fast bin
如果申请的 chunk 的大小位于 fastbin 范围内,需要注意的是这里比较的是无符号整数。此外,是从 fastbin 的头结点开始取 chunk。
- large bin
当 fast bin、small bin 中的 chunk 都不能满足用户请求 chunk 大小时,就会考虑是不是 large bin。但是,其实在 large bin 中并没有直接去扫描对应 bin 中的 chunk,而是先利用 malloc_consolidate(参见 malloc_state 相关函数) 函数处理 fast bin 中的 chunk,将有可能能够合并的 chunk 先进行合并后放到 unsorted bin 中,不能够合并的就直接放到 unsorted bin 中,然后再在下面的大循环中进行相应的处理。为什么不直接从相应的 bin 中取出 large chunk 呢?这是 ptmalloc 的机制,它会在分配 large chunk 之前对堆中碎片 chunk 进行合并,以便减少堆中的碎片。
- unsorted bin 大循环 - 遍历
如果程序执行到了这里,那么说明 与 chunk 大小正好一致的 bin (fast bin, small bin) 中没有 chunk 可以直接满足需求 ,但是 large chunk 则是在这个大循环中处理。
在接下来的这个循环中,主要做了以下的操作
- 按照 FIFO 的方式逐个将 unsorted bin 中的 chunk 取出来
- 如果是 small request,则考虑是不是恰好满足,是的话,直接返回。
- 如果不是的话,放到对应的 bin 中。
- 尝试从 large bin 中分配用户所需的内存
该部分是一个大循环,这是为了尝试重新分配 small bin chunk,这是因为我们虽然会首先使用 large bin,top chunk 来尝试满足用户的请求,但是如果没有满足的话,由于我们在上面没有分配成功 small bin,我们并没有对 fast bin 中的 chunk 进行合并,所以这里会进行 fast bin chunk 的合并,进而使用一个大循环来尝试再次分配 small bin chunk。
- 使用 top chunk
如果所有的 bin 中的 chunk 都没有办法直接满足要求(即不合并),或者说都没有空闲的 chunk。那么我们就只能使用 top chunk 了。
0x06 free
在glibc中的free,有以下说明:
- free 函数会释放由 p 所指向的内存块。这个内存块有可能是通过 malloc 函数得到的,也有可能是通过相关的函数 realloc 得到的。
- 当 p 为空指针时,函数不执行任何操作。
- 当 p 已经被释放之后,再次释放会出现乱七八糟的效果,这其实就是
double free
。 - 除了被禁用 (mallopt) 的情况下,当释放很大的内存空间时,程序会将这些内存空间还给系统,以便于减小程序所使用的内存空间。
free --> __libc_free --> _int_free
_int_free()
检查 ----》是否fastbin ----》是fastbin,放至fastbin链表表头
+---》是否mmap分配 ----》 是,munmap_chunk()
+---》 否,合并chunk ----》 向低地址合并 ----》想高地址合并 ----》 下一个是否是top chunk ----》 是,合并到top chunk
0x10 示例(brk、sbrk)
0x11 brk & sbrk
对于堆的操作,操作系统提供了 brk 函数,glibc 库提供了 sbrk 函数,我们可以通过增加 brk的大小来向操作系统申请内存。
初始时,堆的起始地址 start_brk以及堆的当前末尾 brk指向同一地址。根据是否开启 ASLR,两者的具体位置会有所不同
- 不开启 ASLR 保护时,start_brk 以及 brk 会指向 data/bss 段的结尾。
- 开启 ASLR 保护时,start_brk 以及 brk 也会指向同一位置,只是这个位置是在 data/bss 段结尾后的随机偏移处。
0x12 example
/* sbrk and brk example*/
#include<stdio.h>
#include<unistd.h>
#include<sys/types.h>
int main()
{
void *curr_brk, *tmp_brk = NULL; //创立空指针
printf("Welcome to sbrk example:%d\n",getpid()); //读取heap,pid
/* sbrk(0) gives current program break location */
tmp_brk = curr_brk = sbrk(0); //通过sbrk空指针赋值
printf("Program Break Location1:%p\n", curr_brk);
getchar();
/* brk(addr) increments/decrements program break location */
brk(curr_brk+4096);
curr_brk = sbrk(0);
printf("Program Break Location2:%p\n" ,curr_brk);
getchar();
brk(tmp_brk);
curr_brk = sbrk(0);
printf("Program Break Location3:%p\n", curr_brk);
getchar();
return 0;
}
首先运行程序,根据pid查看对应的maps。
在第一次调用brk函数之前,从下面的输出中可以看出当前堆的情况。
start_brk = end_data = 0x01161000
brk = 0x01182000
在第一次调用brk函数之后可以看到brk增加了。
brk = 0x01183000
其中,关于堆的那一行
- 0x01161000 是相应堆的起始地址
- rw-p 表明堆具有可读可写权限,并且属于隐私数据。
- 00000000 表明文件偏移,由于这部分内容并不是从文件中映射得到的,所以为 0。
- 00:00 是主从 (Major/mirror) 的设备号,这部分内容也不是从文件中映射得到的,所以也都为 0。
- 0 表示着 Inode 号。由于这部分内容并不是从文件中映射得到的,所以为 0。
但是看到这里我产生了疑问,代码中并没有说明申请多大的空间,只是调用了sbrk()
函数,却每次都分配了0x21000(132kb)的空间。
在源码中添加一些东西,使用malloc申请1kb和1000kb的空间,再来分析空间结构。
/* sbrk and brk example*/
#include<stdio.h>
#include<unistd.h>
#include<sys/types.h>
#include<stdlib.h>
int main()
{
void *curr_brk, *tmp_brk = NULL; //创立空指针
printf("Welcome to sbrk example:%d\n",getpid()); //读取heap,pid
/* sbrk(0) gives current program break location */
tmp_brk = curr_brk = sbrk(0); //通过sbrk空指针赋值
void *addr = malloc(1024); //申请空间
printf("malloc addr is:%p\n", addr);
printf("Program Break Location1:%p\n", curr_brk);
getchar();
free(addr);
/* brk(addr) increments/decrements program break location */
brk(curr_brk+4096);
curr_brk = sbrk(0);
printf("Program Break Location2:%p\n" ,curr_brk);
getchar();
brk(tmp_brk);
curr_brk = sbrk(0);
addr = malloc(1024 * 1000);
printf("malloc addr is:%p\n", addr);
printf("Program Break Location3:%p\n", curr_brk);
getchar();
free(addr);
return 0;
}
第一次运行效果还是一样的,可以看到我们申请的空间是在初始化的空间内的。
但是第二次申请了1000kb的空间的时候,则是在初始空间以外的地方申请的,大小为1004kb。
这说明虽然程序向OS申请了小的内存,但是OS会把大的内存分给程序。这样的话避免了多次内核态与用户态的切换,提高了效率。我们称这一连续的内存为arena。此外,我们称由主线程申请的为main_arena。后续的申请内存会从这个arena中获取,直到空间不足。当arena大小不足时,可通过增加brk的方式增加arena的空间。类似的,arena可通过减少brk缩小它的空间。
当用户请求的内存小于初始化堆空间大小时(128k),会在main_arena中分配空间给用户;当用户请求的内存大于128kb,并且没有任何arena满足要求时,系统会调用mmap函数分配相应的内存空间。这与请求来自主进程还是线程无关。