glibc的malloc源码中涉及三种数据结构:Arena、Heap、Chunk ,分别对应结构体malloc_state、heap_info、malloc_chunk。具体的对应关系如下图所示
需要注意的是,Main Arena只有一个heap,因此没有heap_info结构。当main arena用尽空间后,会扩展当前的heap空间。此外,Main Arean的Arena header并不是heap segment的一部分,而作为全局变量储存在libc.so的数据段中。
下图是只有一个heap时,主线程和线程的堆结构示意图,左图是Main Arena,右图是Threa Arena。堆是从低地址向高地址增长的,可以看到每一个malloc_chunk上面都跟着一个chunk。同时Main Arena没有heap_info和malloc_state的结构。
下图是存在多个heap的thread Arena的情况。可以看到每一个heap都一个heap header(heap_info),但是只有最初的heap拥有arena header
当线程申请内存时,就创建一个Arena。主线程有自己独立的Arena,叫做main arena,但不是每一个线程都有独立的Arena。
Arena的个数取决于cpu核的个数
For 32 bit systems: Number of arena = 2 * number of cores + main arena For 64 bit systems: Number of arena = 8 * number of cores + main arena
Q: 多线程时,Arena是怎样分配的呢?
A: 假设一个单核的cpu上运行着一个拥有4个线程(main thread + user thread )的32位程序。
- 当主线程第一次调用malloc时,将创建main arena;
- 当thread 1和thread 2第一次调用malloc时,它们将分别创建一个arena,即Arena-1 和 Arena-2;
- 当thread 3第一次调用malloc时,已经不能再创建新的arena,因此需要复用已存在的arena;
- 详细的复用规则参考源码 reused_arena
bins是用来索引空闲chunk的结构。根据chunk大小,可以分为四类不同的Bin。
数据结构中包含如下两类:
fastbinsY: 用来索引fast bin的数组;
typedef struct malloc_chunk *mfastbinptr; mfastbinptr fastbinsY[]; // Array of pointers to chunks
bins: 一个用来索引unsorted, small, large三种bins的数组。总长度为126
typedef struct malloc_chunk* mchunkptr; mchunkptr bins[]; // Array of pointers to chunks
Fastbin是“An array of lists holding recently freed small chunks”。
默认情况下(32 位系统为例), fastbin 中默认支持最大的 chunk 的数据空间大小为 64 字节。但是其可以支持的 chunk 的数据空间最大为 80 字节。
数量:包含10个bins。每个bin都是一个单链表(只使用fd指针),链表的入队出队都在表头进行,所以是LIFO。如下图所示
大小:每个bin都包含同样大小的chunk,fastbinsY[0]储存数据空间大小为0 bytes的chunk,fastbinsY[1]储存大小为8 bytes的chunk,以此类推,每次增加8个byte。
注意,chunk的数据空间是指用户可以利用来储存数据的空间,总是小于chunk的实际大小的。
在malloc
初始化时,最大的fast bin大小被设置为64byte,而不是80 bytes。
不合并:两个freed chunk可以相邻。与malloc_chunk学习时的说明有所冲突,主要是fast bin更注重分配的速度。
malloc(fast chunk):用户通过malloc请求的大小属于fast chunk的大小范围
Free(fast chunk):用户通过free释放的大小属于fast chunk的大小范围
当small chunk和large chunk被释放的时候,这些chunk并不会添加到对应的small bin或者large bin中,而是被添加到unsroted bin中。这是符合局部性原则的。
chunk大小小于512byte的属于small chunk,
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 |
n | 2 * 4 * n | 2 * 8 * n |
63 | 504 | 1008 |
合并:两个空闲的chunk相邻时要合并成一个空闲的chunk。
这里的相邻指的是在链表中相邻吗?还是在物理地址上相邻。
malloc(small chunk):
free(small chunk):
chunk大小大于512byte的属于large chunk,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 | 不限制 |
为了增加内存管理的效率,large bin中的链表采用降序排列。
在Arena的图中,可以看到靠近内存上边界的chunk叫做top chunk。Top chunk不属于任何bin。它的作用是满足bin中没有空闲的chunk时,用户申请内存空间的请求。
需要注意的是,top chunk 的 prev_inuse 比特位始终为 1,否则其前面的 chunk 就会被合并到 top chunk 中。
在用户使用 malloc 请求分配内存时,ptmalloc2 找到的 chunk 可能并不和申请的内存大小一致,这时候就将分割之后的剩余部分称之为 last remainder chunk ,unsort bin 也会存这一块。top chunk 分割剩下的部分不会作为 last remainder.
https://heap-exploitation.dhavalkapil.com
https://zhuanlan.zhihu.com/p/24753861
https://zhuanlan.zhihu.com/p/185826940
https://www.cnblogs.com/alisecurity/p/5520847.html
https://sploitfun.wordpress.com/2015/02/10/understanding-glibc-malloc/comment-page-1/