0x00 概念
堆其实就是程序虚拟地址空间的一块连续的线性区域,它由低地址向高地址方向增长。一般称管理堆的那部分程序为堆管理器。
当程序运行过程中, 动态申请内存时, 并不会直接在内核中申请下来需求的内存, 而是会在第一次申请内存时申请一块很大的内存空间, 这个内存空间中的所有数据,全部用于当程序下一次申请空间时更快的给予内存, 这一大块空间就是堆,由堆管理器来管理。
目前 Linux 标准发行版中使用的堆分配器是 glibc 中的堆分配器:ptmalloc2。ptmalloc2 主要是通过 malloc/free 函数来分配和释放内存块。
需要注意的是,在内存分配与使用的过程中,Linux 有这样的一个基本内存管理思想,只有当真正访问一个地址的时候,系统才会建立虚拟页面与物理页面的映射关系。 所以虽然操作系统已经给程序分配了很大的一块内存,但是这块内存其实只是虚拟内存。只有当用户使用到相应的内存时,系统才会真正分配物理页面给用户使用。
0x01 结构
malloc_chunk
程序申请下来的内存成为chunk, 在ptmalloc中使用malloc_chunk结构体表示。
无论一个 chunk 的大小如何,处于分配状态还是释放状态,它们都使用一个统一的结构。在 glibc 的malloc.c中,malloc_chunk结构体的定义如下:
struct malloc_chunk {
INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */
INTERNAL_SIZE_T size; /* Size in bytes, including overhead. */
struct malloc_chunk *fd; /* double links -- used only if free. */
struct malloc_chunk *bk;
/* Only used for large blocks: pointer to next larger size. */
struct malloc_chunk *fd_nextsize; /* double links -- used only if free. */
struct malloc_chunk *bk_nextsize;
};
chunk的结构:
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of previous chunk, if unallocated (P clear) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of chunk, in bytes |A|M|P|
mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| User data starts here... .
. .
. (malloc_usable_size() bytes) .
next . |
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| (size of chunk, but used for application data) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of next chunk, in bytes |A|0|1|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
这里 prev_size 和 size 统称为chunk头。
- prev_size:如果该 chunk 的物理相邻的前一地址 chunk(两个指针的地址差值为前一 chunk 大小)是空闲的话,那该字段记录的是前一个 chunk 的大小 (包括 chunk 头)。否则,该字段可以用来存储物理相邻的前一个 chunk 的数据。这里的前一 chunk 指的是较低地址的 chunk 。
- size:该 chunk 的大小,大小必须是 2 * SIZE_SZ 的整数倍。如果申请的内存大小不是 2 * SIZE_SZ 的整数倍,会被转换满足大小的最小的 2 * SIZE_SZ 的倍数。32 位系统中,SIZE_SZ 是 4;64 位系统中,SIZE_SZ 是 8。 此时size的低三位将不会被改变,于是低三位可以分别用来表示不同的含义:
- NON_MAIN_ARENA,记录当前 chunk 是否不属于主线程,1 表示不属于,0 表示属于。
- IS_MAPPED,记录当前 chunk 是否是由 mmap 分配的。
- PREV_INUSE,记录前一个 chunk 块是否被分配。一般来说,堆中第一个被分配的内存块的 size 字段的 P 位都会被设置为 1,以便于防止访问前面的非法内存。当一个 chunk 的 size 的 P 位为 0 时,我们能通过 prev_size 字段来获取上一个 chunk 的大小以及地址。这也方便进行空闲 chunk 之间的合并。
- fd,bk。 chunk 处于分配状态时,从 fd 字段开始是用户的数据。chunk 空闲时,会被添加到对应的空闲管理链表中,其字段的含义如下
- fd 指向下一个(非物理相邻)空闲的 chunk
- bk 指向上一个(非物理相邻)空闲的 chunk
- 通过 fd 和 bk 可以将空闲的 chunk 块加入到空闲的 chunk 块链表进行统一管理
- fd_nextsize, bk_nextsize,也是只有 chunk 空闲的时候才使用,不过其用于较大的 chunk(large chunk)。
- fd_nextsize 指向前一个与当前 chunk 大小不同的第一个空闲块,不包含 bin 的头指针。
- bk_nextsize 指向后一个与当前 chunk 大小不同的第一个空闲块,不包含 bin 的头指针。
- 一般空闲的 large chunk 在 fd 的遍历顺序中,按照由大到小的顺序排列。这样做可以避免在寻找合适 chunk 时挨个遍历。
bins
bin是一种记录free chunk的链表数据结构,用户释放的chunk并不会马上归还系统,ptmalloc会统一管理空闲的chunk, 当用户再次申请,会首先从bins中选择是否存在合适的chunk。
系统针对不同大小的free chunk,将bin分为了4类:
- 1) Fast bin;
- 2) Unsorted bin;
- 3) Small bin;
- 4) Large bin。
然后在每一类bins中都会使用链表来连接其中的chunk。
其中的small bins, large bins, unsorted bins都维护在一个大数组中,而fast bins则独立在外,用于存放一些比较小的chunk。
bins[]数组,用于记录除fastbins之外的所有bins。事实上,一共有126个bins,分别是:
- bin 1 为unsorted bin;
-
bin 2 到 63 为small bin;
-
bin 64 到 126 为large bin。
malloc_state是管理arena的核心结构,包含堆堆状态信息、bins链表等。
malloc_state的结构如下:
struct malloc_state {
/* Serialize access. */
__libc_lock_define(, mutex);
/* Flags (formerly in max_fast). */
int flags;
/* Fastbins */
mfastbinptr fastbinsY[ NFASTBINS ];
/* Base of the topmost chunk -- not otherwise kept in a bin */
mchunkptr top;
/* The remainder from the most recent split of a small request */
mchunkptr last_remainder;
/* Normal bins packed as described above */
mchunkptr bins[ NBINS * 2 - 2 ];
/* Bitmap of bins */
unsigned int binmap[ BINMAPSIZE ];
/* Linked list */
struct malloc_state *next;
/* Linked list for free arenas. Access to this field is serialized
by free_list_lock in arena.c. */
struct malloc_state *next_free;
/* Number of threads attached to this arena. 0 if the arena is on
the free list. Access to this field is serialized by
free_list_lock in arena.c. */
INTERNAL_SIZE_T attached_threads;
/* Memory allocated from the system in this arena. */
INTERNAL_SIZE_T system_mem;
INTERNAL_SIZE_T max_system_mem;
};
fastbins
fastbinsY[]
是一个数组,记录了所有的fastbins。
Fast bins主要是用于提高小内存的分配效率,默认情况下,对于SIZE_SZ为4B的平台,小于64B 的chunk分配请求,对于SIZE_SZ为8B 的平台,小于128B的chunk分配请求,首先会查找fastbins中是否有所需大小的chunk存在(精确匹配),如果存在,就直接返回。
Fast bins可以看着是small bins的一小部分cache,默认情况下, fastbins 只 cache了smallbins 的前7个大小的空闲chunk,也就是说,对于SIZE_SZ为4B的平台, fast bins有7个chunk空闲链表(bin),每个bin的chunk大小依次为16B,24B,32B,40B,48B,56B,64B;对于SIZE_SZ为8B的平台,fast bins有7个chunk空闲链表(bin),每个 bin的chunk 大小依次为32B,48B,64B,80B,96B,112B,128B。
以64为系统为例,分配的内存大小与chunk大小和 fastbins的对应关系如下表所示:
Fastbin | Holds chunk size | Read chunk size |
---|---|---|
0 | 0-0x10 | 0x20 |
1 | 0x11-0x20 | 0x30 |
2 | 0x21-0x30 | 0x40 |
3 | 0x31-0x40 | 0x50 |
4 | 0x41-0x50 | 0x60 |
5 | 0x51-0x60 | 0x70 |
6 | 0x61-0x70 | 0x80 |
unsorted bin
unsorted bin 可以视为空闲 chunk 回归其所属 bin 之前的缓冲区。
- 当一个较大的 chunk 被分割成两半后,如果剩下的部分大于 MINSIZE,就会被放到 unsorted bin 中。
-
释放一个不属于 fast bin 的 chunk,并且该 chunk 不和 top chunk 紧邻时,该 chunk 会被首先放到 unsorted bin 中。
Small Bin
small bins 中每个 chunk 的大小与其所在的 bin 的 index 的关系为:chunk_size = 2 * SIZE_SZ *index
下标 | SIZE_SZ=4(32 位) | SIZE_SZ=8(64 位) |
---|---|---|
2 | 16 | 32 |
3 | 24 | 48 |
4 | 32 | 64 |
5 | 40 | 80 |
x | 24x | 28x |
63 | 504 | 1008 |
small bins 中一共有 62 个循环双向链表,每个链表中存储的 chunk 大小都一致。可以将small bins理解为一个大数组,每个位置对应着每一类大小的chunk的链表。比如对于 32 位系统来说,下标 2 对应着大小为均为 16 字节的chunk的双向链表。每个链表都有链表头结点,这样可以方便对于链表内部结点的管理。此外,small bins 中每个 bin 对应的链表采用 FIFO 的规则,所以同一个链表中先被释放的 chunk 会先被分配出去。
Large Bin
large bins 中一共包括 63 个 bin,每个 bin 中的 chunk 的大小不一致,而是处于一定区间范围内。此外,这 63 个 bin 被分成了 6 组,每组 bin 中的 chunk 大小之间的公差一致,具体如下:
组 | 数量 | 公差 |
---|---|---|
1 | 32 | 64B |
2 | 16 | 512B |
3 | 8 | 4096B |
4 | 4 | 32768B |
5 | 2 | 262144B |
6 | 1 | 不限制 |
这里以32位平台为例,第一个large bin 的起始 chunk 大小为 512 字节,位于第一组,所以该 bin 可以存储的 chunk 的大小范围为 [512,512+64)
,满足关系 chunk_size = 512 + 64 * index
。
而第二组largebin的起始chunk大小为第一组bin的结束chunk大小,满足关系 chunk_size = 512 + 64 * 32 + 512 * index
。
0x02 实例
示例源码:
#include <stdio.h>
#include <stdlib.h>
int main()
{
char *a1 = malloc(0x10);
char *a2 = malloc(0x10);
char *a3 = malloc(0x10);
char *a4 = malloc(0x10);
free(a1);
free(a2);
free(a3);
free(a4);
}
打开gdb调试,在main函数处下断点,运行至第一个malloc函数结束处,使用heap指令:
可以看见已经为程序分配了一块起始地址为0x602000,大小为0x21的空间,注意这里是0x21,而不是我们源码中所写的0x10,这是因为申请得到的空间大小除了用户申请的大小外,还要加上chunk头的大小,也就是0x10,而且此时该chunk的PREV_INUSE位为1,大小就为 0x10 + 0x10 + 0x1 = 0x21
。
将四个malloc函数全部运行,再次查看程序的heap,四个大小为0x21的chunk依次排列:
接着运行至第一个free函数结束,可以看见第一个chunk已经free掉了,fd指向了0x00,也就是NULL。需要特别注意的是,fastbin 范围的 chunk 的 inuse 始终被置为 1。因此它们不会和其它被释放的 chunk 合并。因此chunk的size仍为0x21。
然后查看fastbins,可以看见0x20处有了第一个值,也就是刚才free掉的chunk的地址
接着将四个free函数运行完,可以看见四个chunk的已经free掉了,然后fd也分别指向了上一个free掉的chunk的地址,fastbins的0x20处就有了刚才free掉的四个chunk的地址。
我们为了印证malloc_chunk结构体中fd所说的指向下一个(非物理相邻)空闲的 chunk,将示例源码修改一下,将free(a2);
与free(a3);
交换一下位置,让a3先于a2被free掉,然后运行至四个free函数结束,查看一下heap和fastbins,可以看到Addr为0x602020的chunk,也就是a2对应的chunk的fd指向了0x602040,也就是a3对应的chunk的地址,而a3对应的chunk的fd指向了0x602000,也就是a0对应的chunk的地址,释放顺序为:a1、a3、a2、a4,于是这里的指向就变为了:a4 —▸ a2 —▸ a3 —▸ a1
,fastbins的0x20处的内容也是:0x602060 —▸ 0x602020 —▸ 0x602040 —▸ 0x602000
。此时顺序就不是刚才一样物理相邻了,而是变成了与其释放顺序有关。
此时我们将a2申请的空间修改为0x100,然后运行至 free(a2);
处,查看bins,可以发现此时a2的chunk,也就是0x602020地址对应的chunk没有在fastbins中,而是在unsortedbin中。
Comments | NOTHING