BruceFan's Blog

Stay hungry, stay foolish

0%

深入理解glibc malloc

glibc中的内存分配是由ptmalloc2实现的,ptmalloc2是dlmalloc(General purpose allocator)的分支,并加入了线程支持。
System Calls malloc内部会调用brkmmap系统调用。
Threading ptmalloc2中,当两个线程同时调用malloc,内存会立即得到分配,因为每个线程有一个单独的堆段,因此free list数据结构中保存的这些堆也是分开的。这种为每个线程分配一个单独的堆和free list数据结构的行为称为per thread arena

例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/* Per thread arena example. */
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>
#include <sys/types.h>

void* threadFunc(void* arg) {
printf("Before malloc in thread 1\n");
getchar();
char* addr = (char*) malloc(1000);
printf("After malloc and before free in thread 1\n");
getchar();
free(addr);
printf("After free in thread 1\n");
getchar();
}

int main() {
pthread_t t1;
void* s;
int ret;
char* addr;

printf("Welcome to per thread arena example::%d\n",getpid());
printf("Before malloc in main thread\n");
getchar();
addr = (char*) malloc(1000);
printf("After malloc and before free in main thread\n");
getchar();
free(addr);
printf("After free in main thread\n");
getchar();
ret = pthread_create(&t1, NULL, threadFunc, NULL);
if (ret) {
printf("Thread creation error\n");
return -1;
}
ret = pthread_join(t1, &s);
if (ret) {
printf("Thread join error\n");
return -1;
}
return 0;
}

输出分析
主线程的malloc之前,没有堆段,也没有每个线程的栈,因为thread1还没有创建。

1
2
3
4
5
6
7
8
9
10
11
12
$ ./per_thread_arena
Welcome to per thread arena example::3437
Before malloc in main thread

# another terminal
$ cat /proc/3437/maps
...
08048000-08049000 r-xp 00000000 08:02 3680065 /home/fanrong/Computer/pwn/heap-overflow/sploitfun/per_thread_arena
08049000-0804a000 r--p 00000000 08:02 3680065 /home/fanrong/Computer/pwn/heap-overflow/sploitfun/per_thread_arena
0804a000-0804b000 rw-p 00001000 08:02 3680065 /home/fanrong/Computer/pwn/heap-overflow/sploitfun/per_thread_arena
f755a000-f755b000 rw-p 00000000 00:00 0
...

主线程的malloc之后,堆段创建,主线程的堆内存由brk系统调用创建。尽管用户请求了1000bytes,但却创建了132KB的堆内存。这个连续的堆内存称为arena,因为由主线程创建,所以叫它main arena。后续的分配请求会接着用这个arena直到用完空闲空间,它可以通过增加program break location来增长(并调整Top Chunk的大小)。当Top Chunk有大量的空闲空间时arena也可以缩小。

1
2
3
4
5
After malloc and before free in main thread
...
0986e000-0988f000 rw-p 00000000 00:00 0 [heap]
f7536000-f7537000 rw-p 00000000 00:00 0
...

主线程的free之后,分配的内存区域没有释放给操作系统,而是是释放给glibc malloc,glibc malloc把这个空闲的块加到main arena的bin(glibc malloc中,freelist数据结构称为bin)

1
2
3
4
After free in main thread
...
0986e000-0988f000 rw-p 00000000 00:00 0 [heap]
f7536000-f7537000 rw-p 00000000 00:00 0

thread1的malloc之前,thread1没有堆段,但是有栈了。

1
2
3
Before malloc in thread 1
...
f6d36000-f7537000 rw-p 00000000 00:00 0 [stack:3904]

thread1的malloc之后,thread1的堆(f6c00000-f6c21000大小为132KB)创建了,与主线程不同,它是由mmap创建,称为thread arena

用户请求的大小大于128KB时,内存分配由mmap系统调用完成(而不是sbrk),不管是请求是main arena发出的还是thread arena发出的。

1
2
3
4
5
6
After malloc and before free in thread 1
...
0986e000-0988f000 rw-p 00000000 00:00 0 [heap]
f6c00000-f6c21000 rw-p 00000000 00:00 0
f6c21000-f6d00000 ---p 00000000 00:00 0
f6d35000-f6d36000 ---p 00000000 00:00 0

thread1的free之后,分配的内存没有释放给操作系统,而是释放给glibc malloc,glibc malloc把这个空闲块加到thread arena的bin

1
2
3
4
5
6
After free in thread 1
...
0986e000-0988f000 rw-p 00000000 00:00 0 [heap]
f6c00000-f6c21000 rw-p 00000000 00:00 0
f6c21000-f6d00000 ---p 00000000 00:00 0
f6d35000-f6d36000 ---p 00000000 00:00 0

Arena
arena的数量由系统的核数量决定。

32位系统:
arena的数量 = 2 * 核的数量
64位系统:
arena的数量 = 8 * 核的数量

Multiple Arena
例如:一个多线程(主线程+3个用户线程)应用在一个单核的32位系统上运行,线程数>2*核数,因此glibc malloc需要确保multiple arena能被线程共享。

  • 主线程第一次调用malloc会创建main arena。
  • thread1和thread2第一次调用malloc,会分别为它们创建thread arena
  • thread3第一次调用malloc不会创建arena,会尝试reuse已存在的arena(main arena或arena1或arena2)
  • reuse:
    当循环可用的arena时,尝试lock arena
    如果lock成功,返回那个arena给用户
    如果没有空闲的arena,阻塞排队等待arena

Multiple Heaps
glibc malloc中有三种数据结构:
heap_infoHeap Header - 一个thread arena可以有multiple heaps,每个heap有自己的header。(每个thread arena一开始只有一个heap,当堆段空间用尽时,会有新的heap被mmap到这个arena中)
malloc_stateArena Header - 一个thread arena的multiple heaps只有一个arena header。Arena header包含着bins,top chunk,last remainder chunk等信息。
malloc_chunkChunk Header - 一个heap根据用户请求被分成多个chunk,每个chunk有自己的header。

Main arena没有multiple heaps,因此没有heap_info结构。当main arena空间用尽时,sbrk创建的堆段会被增长(连续空间),直到它撞到内存映射段。
和thread arena不同,main arena的arena header不是sbrk创建的堆段的一部分,它是一个全局变量,因此它在libc.so的数据段。

main arena和thread arena(单个堆段)

thread arena(多个堆段)

Chunk堆段中chunk的类型:

  • Allocated chunk
  • Free chunk
  • Top chunk
  • Last Remainder chunk

Allocated Chunk

prev_size如果前一个chunk被free,这个成员包含前一个chunk的大小,如果前一个chunk被分配,这个域包含前一个chunk的用户数据。
size这个成员包含当前chunk的大小,最后三个字节包含了标识位信息。

  • PREV_INUSE(P) - 前一个chunk被分配时,设置这一位。
  • IS_MMAPPED(M) - 当chunk是mmap创建的,设置这一位。
  • NON_MAIN_ARENA(N) - 当chunk属于一个thread arena时,设置这一位。

Free Chunk

prev_size没有两个free chunk是相连的,当两个chunk都是free的,它们会合并成一个free chunk,因此free chunk的前一个chunk一定是allocated chunk,这个域一定包含用户数据。
size包含这个free chunk的大小。
fd指向相同bin里的下一个chunk(而不是物理内存中的下一个chunk)。
bk指向相同bin里的前一个chunk(而不是物理内存中的前一个chunk)。
Bins是free list数据结构,它们被用来保存free chunk。基于chunk的大小分为:

  • Fast bin
  • Unsorted bin
  • Small bin
  • Large bin

用于保存bin的数据结构:
fastbinsY这个数组保存fast bin。
bins这个数组保存unsorted,small和large bin,总共有126个bin:

  • Bin 1 - Unsorted bin
  • Bin 2 to Bin 63 - Small bin
  • Bin 64 to Bin 126 - Large bin

Fast Bin 16~80bytes大小的chunk被称为fast chunk。保存fast chunk的bin叫做fast bin,fast bin在内存中分配和回收更快。

  • bin的数量 - 10
    每个fast bin包含一个free chunk的单向链表,单项链表的增加和删除都在链表头(LIFO)。
  • Chunk size - 以8字节区分
    例如,第一个fast bin(index 0)包含16字节chunk的binlist,第二个fast bin(index 1)包含24字节chunk的binlist …
    同一个fast bin的chunk一样大小。

  • 在malloc初始化阶段,fast bin最大64字节(而不是80),因此默认16~64字节的chunk是fast chunk。
  • 不合并 - 两个相连的free chunk不会合并成一个,这会产生更多碎片,但是free的速度提高了。

Unsorted Bin 当small或large chunk free以后,不会把它们加到期望的bin,而是加到unsorted bin。这种方法使glibc malloc能重用最近free的chunk,使内存的分配和回收加速(因为减少了查找合适bin的时间)。

  • bin的数量 - 1
    unsorted bin包含一个free chunk的循环双向链表。
  • Chunk size - 没有大小限制


Small Bin 小于512字节的chunk称为small chunk,保存small chunk的bin称为small bin。small bin的分配与回收比large bin快(没有fast bin快)。

  • bin数量 - 62
    small bin包含free chunk的循环双向链表,双向链表的增加在开头,删除在末尾(FIFO)。
  • Chunk Size - 以8字节区分
    例如,第一个small bin(Bin 2)保存一个16字节chunk的binlist,第二个smallbin(Bin 3)保存一个24字节chunk的binlist …
    同一个small bin里的chunk大小相同。
  • 合并 - 两个相邻的free chunk会合并成一个。合并减少了碎片,但使free速度减慢。

Large Bin 大小大于等于512的chunk称为large chunk。保存large chunk的bin称为large bin。

  • bin的数量 - 63
    large bin包含一个free chunk的循环双向链表。
    chunk的增加和删除可以在链表的任何位置。
  • 合并 - 两个相邻的free chunk会合并成一个。

Top Chunk
在arena顶部的chunk称为top chunk,它不属于任何bin。Top chunk会在所有bin都没有空闲区域的时候使用。Top chunk大于用户请求时分成两部分:

  • 用户chunk
  • Remainder chunk

Remainder chunk变成新的top,top chunk小于用户请求,会通过sbrk(main arena)或mmap(thread arena)系统调用增加。
Last Remainder Chunk 最近从small请求中分离出来的。
reference
https://sploitfun.wordpress.com/2015/02/10/understanding-glibc-malloc/