BruceFan's Blog

Stay hungry, stay foolish

0%

深入理解glibc malloc

发表于 Edited on

glibc中的内存分配是由ptmalloc2实现的，ptmalloc2是dlmalloc（General purpose allocator）的分支，并加入了线程支持。
System Calls malloc内部会调用brk或mmap系统调用。
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/