经典文章阅读:Understanding glibc malloc

对经典文章Understanding glibc malloc的阅读笔记&夹带自己理解的翻译

[toc]

原文链接

内存的管理方式有许多种,例如:

1
2
3
4
5
6
- dlmalloc – General purpose allocator
- ptmalloc2 – glibc
- jemalloc – FreeBSD and Firefox
- tcmalloc – Google
- libumem – Solaris

本文将只对glibc malloc进行讲解,其他的内存管理方式将留到以后进行讲解。让我们开始吧!(本文讲解的内存管理方式基于此处

发展历史

实际上,ptmalloc2是由dlmalloc的源代码fork而来的,并在dlmalloc的基础上添加了线程的支持,最终2006年发布。这之后,ptmalloc2这一内存管理方式被集成到了glibc中,这之后glibc开始自己对malloc内存管理方式进行修改。因此,目前ptmalloc2内存管理方式和glibcmalloc实现已经有着不小的差距了。

系统调用

如此所示malloc内部有两种系统调用,即brkmmap

线程

linux的早期版本,dlmalloc才是其默认的内存管理方式,但由于ptmalloc2添加的线程支持,这之后ptmalloc2才成为了linux的默认内存管理方式。线程能够改善内存分配的性能,也就是说,线程的支持能够改善应用程序的性能。在dlmalloc中,当两个线程同时调用malloc的时候,只有一个线程能够进入临界区修改数据,但这个时候操作系统中的空闲内存又是所有线程共享的。因此,内存分配问题在多线程的应用程序中占用了大量时间,造成程序的应用性能下降。在ptmalloc2中,当两个线程同时调用malloc的时候,内存将可以被立即分配,因为每个线程都维护了一个独立的heap,这些heap的空闲内存也是独立的。这个用于为每个线程维护独立的heap和空闲内存的东西就叫做线程arena。在ptmalloc2中,这个“空闲内存”也就是bin

Example

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
46
47
/* 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之前:

我们的程序会输出程序进程对应的pid。我们可以访问linux下的/proc/[pid]/maps来查看其内存空间的分配。在下面的输出中,我们可以看到,目前是没有任何heap被创建的,而由于thread1还没有被创建,因此输出中可以看到也没有线程的栈空间出现。

1
2
3
4
5
6
7
8
9
10
11
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread 
Welcome to per thread arena example::6501
Before malloc in main thread
...
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ cat /proc/6501/maps
08048000-08049000 r-xp 00000000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread
08049000-0804a000 r--p 00000000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804a000-0804b000 rw-p 00001000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread
b7e05000-b7e07000 rw-p 00000000 00:00 0
...
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$

主线程调用malloc之后

此时,我们从下面的输出中可以看到,heap段已经被创建了,且其范围为0x0804b000-0x0806c000,即大小为132kb。这说明这里的堆内存是由brk系统调用来创建的(不懂的可以看上面系统调用那里提到的那篇文章)。注意,用户只申请了1000bytes的内存空间,但操作系统仍然创建了132kb的堆内存。这一段连续的内存区域就叫做arena。以后的内存申请都会使用该区域,直到该区域的内存被分配完为止。有的师傅可能会想,那假如这个arena的内存分配完了的时候怎么办呢?此时,arena可以再通过中断的方式来增加内存。类似地,若top chunk处的空闲内存过大,arena也可以通过这种方式来缩小。

top chunkarena中顶部的一个chunk,我们接下来还会进行详细的讲解)

1
2
3
4
5
6
7
8
9
10
11
12
13
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread 
Welcome to per thread arena example::6501
Before malloc in main thread
After malloc and before free in main thread
...
sploitfun@sploitfun-VirtualBox:~/lsploits/hof/ptmalloc.ppt/mthread$ cat /proc/6501/maps
08048000-08049000 r-xp 00000000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread
08049000-0804a000 r--p 00000000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804a000-0804b000 rw-p 00001000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804b000-0806c000 rw-p 00000000 00:00 0 [heap]
b7e05000-b7e07000 rw-p 00000000 00:00 0
...
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$

主线程调用free之后:

在下面的输出中,我们可以看到,即使用户刚刚申请的内存已经被释放了,刚刚通过brk系统调用获得的132kb的内存并没有被立即释放。此时,刚刚释放的1000bytes的内存空间被释放给了glibc中叫做bin的地方(可以理解为Windows系统中的回收站)。我们前面提到,每个线程都拥有自己的arena,因此我们刚刚释放的1000bytes实际上是放入了main arenabin中。接下来,若用户需要申请内存,那么glibc将不会从arena中给用户一块新的内存,而是从bin中取出一块内存来给用户使用。只有bins中不含有空闲的内存块时,glibc才会从arena中给用户分配内存。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread 
Welcome to per thread arena example::6501
Before malloc in main thread
After malloc and before free in main thread
After free in main thread
...
sploitfun@sploitfun-VirtualBox:~/lsploits/hof/ptmalloc.ppt/mthread$ cat /proc/6501/maps
08048000-08049000 r-xp 00000000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread
08049000-0804a000 r--p 00000000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804a000-0804b000 rw-p 00001000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804b000-0806c000 rw-p 00000000 00:00 0 [heap]
b7e05000-b7e07000 rw-p 00000000 00:00 0
...
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$

thread1调用malloc之前:

观察代码,我们创建了一个子线程,并且让它执行代码中的threadFunc函数。在子线程刚刚创建,还没有调用malloc的时候,我们查看它的内存空间如下。可以看到,thread1heap空间目前还没有创建,但它的栈空间已经创建好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread 
Welcome to per thread arena example::6501
Before malloc in main thread
After malloc and before free in main thread
After free in main thread
Before malloc in thread 1
...
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ cat /proc/6501/maps
08048000-08049000 r-xp 00000000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread
08049000-0804a000 r--p 00000000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804a000-0804b000 rw-p 00001000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804b000-0806c000 rw-p 00000000 00:00 0 [heap]
b7604000-b7605000 ---p 00000000 00:00 0
b7605000-b7e07000 rw-p 00000000 00:00 0 [stack:6594]
...
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$

therad1调用malloc之后:

从下面的输出中我们可以看到,thread1heap空间已经创建好了,且其位于内存的映射区域,即0xb7500000-0xb7521000处,大小也为132kb。这说明这一段内存是通过mmap系统调用来生成的(记得前文说过main arena是通过brk系统调用来生成的吗)。这里同样的,尽管用户只申请了1000bytes,但是操作系统仍然分配了1MB(0xb7500000-b75600000)的内存空间。在这1MB的内存空间中,只有132KB的内存空间有读写权限,这个部分就是thread arena

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread 
Welcome to per thread arena example::6501
Before malloc in main thread
After malloc and before free in main thread
After free in main thread
Before malloc in thread 1
After malloc and before free in thread 1
...
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ cat /proc/6501/maps
08048000-08049000 r-xp 00000000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread
08049000-0804a000 r--p 00000000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804a000-0804b000 rw-p 00001000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804b000-0806c000 rw-p 00000000 00:00 0 [heap]
b7500000-b7521000 rw-p 00000000 00:00 0
b7521000-b7600000 ---p 00000000 00:00 0
b7604000-b7605000 ---p 00000000 00:00 0
b7605000-b7e07000 rw-p 00000000 00:00 0 [stack:6594]
...
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$

thread1调用free后

thread1调用free后,我们可以看到这段free掉的1000bytes内存空间同样没有还给操作系统。事实上,这段内存空间被释放给了thread arenas bin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread 
Welcome to per thread arena example::6501
Before malloc in main thread
After malloc and before free in main thread
After free in main thread
Before malloc in thread 1
After malloc and before free in thread 1
After free in thread 1
...
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ cat /proc/6501/maps
08048000-08049000 r-xp 00000000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread
08049000-0804a000 r--p 00000000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804a000-0804b000 rw-p 00001000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804b000-0806c000 rw-p 00000000 00:00 0 [heap]
b7500000-b7521000 rw-p 00000000 00:00 0
b7521000-b7600000 ---p 00000000 00:00 0
b7604000-b7605000 ---p 00000000 00:00 0
b7605000-b7e07000 rw-p 00000000 00:00 0 [stack:6594]
...
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$

Areana

Arena的数量

在上面的例子中,主线程包含了一个主arena,而thread1包含了一个thread arena。那么是否一个线程一定和一个arena一一对应呢?答案是否定的。举个例子,一个程序可以有非常多的线程,甚至多于操作系统拥有的cpu的核心数量,那么这种情况下给每个线程都分配一个arena非常浪费。因此,一个应用程序的子线程arena的数量限制与系统中的cpu核心数相关,如下所示:

1
2
3
4
对于32位系统:
arena数目 = 2 * cpu核心数
对于64位系统:
arena数目 = 8 * cpu核心数

注意,主线程一定有自己的main arena,因此总的arena数量要在此基础上+1

Arena调度策略

上面我们讲述了arena的数量限制。那么,一个很自然的问题就出现了:对于没有分配到arena的线程,如何进行内存管理呢?这就要引出arena的调度策略了。

假设我们现在有一个32位应用程序,它一共含有3个子线程,且只有1cpu核心。那么,此时线程的数量是3+1=4个线程,而arena的最大个数是1(cpu核心数) * 2 (32位系统) = 2个。在这种情况下,glibc为了让每个线程都能在工作的时候分配到arena,会采用调度策略。假设线程间的malloc顺序如下:

  • 主线程第一次调用malloc时,直接使用main arena,没有竞争。
  • thread1thread2第一次调用malloc的时候,都会为他们分配一个thread arena,没有任何的竞争。此时线程和arena之间也是一对一的关系。
  • 接下来,thread3也调用了malloc。由于arena数量已经达到最大值,无法再给thread3分配一个arena,因此此时glibc将会让thread3尝试重用这几个arenamain arena, arena1, arena2):
  • 重用过程:
    • 循环遍历来寻找可用的arena,直到找到一个可用的arena为止。
    • 若找到了一个可用的arena,则尝试将它锁定,并将这个arena返回给线程使用、
    • 若没有找到可用的arena,那么thread3将会被阻塞,直到有一个可用的arena为止。
  • thread3第二次调用malloc1的时候,thread3将会尝试使用最后一次使用的arena。假设上一次thread3使用了main arena,那么thread3将会尝试使用main arena。若main arena此时可用,那么thread3将会直接尝试使用main arena。若main arena此时不可用,那么thread3将会被阻塞,直到main arena可用为止。如此一来,main arena就在主线程和thread3之间实现了共享。

heap

glibc的源代码中,主要有以下三种数据结构:

1
2
heap_info
这是heap的header。一个arena可以含有多个heap,而每个heap都有一个header。为什么需要这么多个heap?事实上,在刚开始的时候每个thread arena只有一个heap,但在这个heap的空间用完的时候,会使用mmap来申请更多的heap(与之前的heap并不是连续的空间)。
1
2
malloc_state
这是arena的header。一个arena可以有多个heap,但是这些heap都由这一个arena管理,因此他们归属于同一个arena header。arena header中有多种信息,包括bins、top chunk、last remainder chunk...
1
2
malloc_chunk
这是chunk的header。一个heap会基于用户请求分成很多个chunk。每一个chunk都有自己的header,即malloc_chunk。

注意:

  • main arena没有多个heap段,也因此没有heap_info结构。当main arena的内存空间不够时,sbrk的堆结构将会被扩展(且是扩展了一段连续区域),直到遇到内存映射段为止。
  • thread arena不同,main arenaarena header并不是sbrk堆段的一部分,它实际上是一个全局变量,并且被保存在libc中。数据段也是同样的。

main arenathread arena的示意图如下:

只有一个heap的情况:

image-20230710100156754

thread arena中含有多个heap的情况:

image-20230710100313034

chunk

chunk是进行内存管理的基本单元,heap中的chunk可能有如下形式:

  • Allocated chunk(正在被使用)
  • Free chunk(空闲)
  • Top chunk
  • Last Remainder chunk

其中,前面两种表示chunk的状态,而后面两种表示两种特殊的chunk

Allocated chunk的结构如图所示:(每一行是一个数据,在32位下为4byte,64位下为8byte

image-20230710100603017

prev_size:实际上是最上面的数据。它不取决于当前chunk的状态,而是取决于与之相连的上一个chunk的状态。若上一个chunk的状态是free的,那么这个数据将会存放上一个chunk的大小,即prev_size;若上一个chunk的状态是allocated,那么这个数据空间将会作为上一个chunk额外可以存放的一点数据。

size:这是图中的第二行数据。可以看到,它包含chunk sizeN/M/P三个数据位。这里是把本行的最后三个bit用作数据位(因为size最后三个bit本来肯定为0,因此这三个bit可以用来表示信息)。

其中:

  • N表示NON_MAIN_ARENA。表示当前的chunk是属于main arena的还是属于thread arena的。若属于thread arena,那么N=1

  • M表示IS_MMAPED。若当前chunk是由mmap创建的,那么M=1

  • P表示PREV_INUSE。若前一个chunk的状态是free,那么该标志位为0,若为allocated,那么该标志位为1

Free Chunk的结构如图所示:

image-20230710182624916

prev_size:当chunk的状态为free的时候,上一个chunk若也为free状态,那么两个chunk会被合并,因此不存在这种情况。因此,上一个chunk的状态此时一定为allocatedprev_size一定存放的是上一个chunk的数据。

size:和allocated状态的size位是一样的。

fd:前向指针,指向同一个bin中的下一个chunk。注意,不是指向物理内存相连的下一个chunk

bk:后向指针,指向同一个bin中的上一个chunk。同上,不一定指向物理内存相连的下一个chunk

bins

bins是维护被free掉的chunk的数据结构。基于chunk大小的不同,bins可以被分为如下形式:

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

bin在操作系统中由以下数据结构进行管理:

fastbinsY: 管理fastbin

bins: 管理unsortedbinsmall binlarge binbins是个数组,长度为126,并且对应关系如下:

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

Fast bin

  • 一共有10fastbin。每一个fastbin都是单链表,因为fastbinchunk的存取操作都不会发生在链表的中间。由于fastbin是为了时间局部性原则,因此是后进先出(LIFO),存取操作都发生在链表头。

  • 在一个单链表内,chunk的大小都是相同的。不同的单链表之间的大小差是根据系统的位数决定的,在32位下,差为8,在64位下的差则为16。例如在32位下,fastbin0的大小为16bytes,那么fastbin1的大小为24bytes

  • malloc初始化期间,最大的fastbin size被设置为64bytes,因此默认情况下16bytes-4byteschunk被分类为fastbin chunk

  • fastbin不会合并。其他的bins中,两个相邻的空闲块可能会发生合并,但是fastbin是不会的,尽管这可能会产生内存碎片。这是因为这样做可以使得free的速度更快,fastbin就是为了操作系统能够更快地利用这些刚释放的chunk而设计的。

  • fastbin的范围是由一个叫做global_max_fast的变量决定的,而这个变量在第一次malloc请求的时候还是空的。因此,当第一次使用malloc申请内存的时候,即使申请的内存大小属于fastbin,也会交给small bin来处理。

image-20230716232409024

Unsorted bin

当大小属于small bin或者large binchunk被释放的时候,chunk也不会直接添加到对应的bin里面去,而是先被添加到unsorted bin,类似于fast bin,这样有利于时间局部性,因此略微加快了内存分配的速度,因为没有寻找合适的bin这个过程的时间。

  • 一共有1unsorted binunsorted bin包含一个循环双向链表。如图所示。
  • chunk的大小:没有限制,任何一个大小的chunk都可以被添加到unsorted bin

image-20230716232356352

Small bin

低于512bytes(0x200)chunk被称为small chunksmall bin的分配速度比large bin略快,但是比fastbin更慢。

  • 一共有62small bin。每一个small bin都是一个双向循环链表,因此在small bin中的chunk都是通过unlink的方式进行解链的。添加到small binchunk将会被添加到链表头,但是删除操作会发生在链表尾(FIFO)。
  • 不同small bin之间的差值和fastbin是一样的。在同一个small bin中,chunk的大小是一样的,因此他们在循环链表中的顺序是置入small bin的顺序,不会发生别的排序。
  • 合并:在small bin中,若有两个相邻的chunk都是free的,那么他们会发生合并,成为一个空闲的chunk。合并操作减少了外部碎片,但是同时也减慢了free的速度。
  • malloc时:初始状态下small bin都为空,因此用户即使访问了一个属于small binchunk也是由unsorted bin来处理。在第一次调用malloc时,small binlarge bin都将被初始化,并且它们的bin都会指向自身,表示它们是空的。若small bin不为空,那么会取出对应small bin中的最后一个chunk给用户。
  • free时:会检查相邻的上一个或者下一个chunk是否是free的,如果是,那么则会发生合并,并且将合并后的chunk添加到unsorted bin中。

Large bin

大于或等于512bytes(0x200)chunk被称为large chunk,管理空闲的large chunk的数据结构叫做Large bin

  • 一共有63largebin。每一个large bin都是双链表,因为在链表头、链表尾以及任意位置都可能添加或者删除数据。

  • small bin不同,在large bin中的chunk并不是同一个大小,因此在largebin中的chunk是按照降序排列的:最大的chunk在链表头,而最小的chunk在链表尾部。

  • 在这63largebin中,前32largebin的最大chunk和最小的chunk之差为64bytes。例如第一个largebin的大小为512bytes-568bytes,而第二个largebin的大小就为576bytes-632bytes

    接下来的16largebin相差512bytes

    接下来的8largebin相差4096bytes

    接下来的4largebin相差32768bytes

    接下来的2largebin相差262144bytes

    最后的1largebin包含其他所有的大小。

  • 合并:两个相邻的freechunk会被合并为一个chunk

  • malloc时:未初始化时,与small bin过程相同。

    初始化完成后,若用户请求的chunk大小要小于large bin中最大的chunk,那么largebin会进行遍历来找到大小相等或者接近的chunk。找到之后,这个chunk会被进行切割成两个部分:第一个部分返回给用户,第二部分作为Remainder chunk添加到unsorted bin

    若用户请求的chunk大小要大于large bin中最大的chunk,那么largebin则需要寻找一个更大的largebin。但此时若直接遍历查看往后的largebin是否有满足条件的largebin太慢了,因此有一个叫做binmaps的东西用来记录哪些largebin为空,并以此找到下一个不为空的largebin来重复以上的遍历方法。一旦找到了,同上。若没有找到,那么会使用top chunk来分配合适的内存。

  • free操作:和small bin相同。

Top Chunk

Top Chunk是在一个arena的顶端部分的chunk,它不属于任意的binTop chunk的作用是在所有bin中都没有空闲的chunk时来处理用户的malloc请求。

top chunk大小要大于用户请求大小,那么top chunk会被分为以下两个部分:

  • 用户请求,返回给用户
  • Remainder chunkRemainder chunk会成为新的top chunk

top chunk大小要小于用户请求大小,那么top chunk会通过sbrk(main arena)或者mmap(thread arena)的系统调用方式来进行扩展,取决于是main arena还是thread arena

Last Remainder Chunk

Last Remainder Chunk是一个在Unsorted bin中的特殊chunk。它会有两个地方产生作用:

  • 用户请求的size输入small bin,但small bin中对应的bin为空,而略大于这个chunk对应的值的small bin非空,那么就从这个small bin上面取出一个chunk,分为两部分,一部分给用户,而另一部分形成Last Remainder Chunk返回到Unsortedbin中。这也就是产生。

  • 若处理用户的请求时,fastbinsmallbin均分配失败,那么会尝试从unsorted bin中分配。如果满足以下条件:

    • 申请的sizesmall bin范围内
    • unsortedbin仅有一个free chunk
    • 且为last remainder chunk
    • 正好满足用户请求的size

    那么,就将last remainder chunk分成两部分,一部分返回用户而另一部分作为新的last remainder chunk插入到unsorted bin中。

last remainder chunk主要是利用了内存分配的局部性来提高连续malloc的效率(试想有一连串的small request)。

至此,Understanding glibc malloc这篇文章的个人翻译也就结束了,希望能通过这篇文章为起点,学习到glibc的更多知识^ ^。


经典文章阅读:Understanding glibc malloc
http://example.com/2023/09/23/system/Heap/understanding_glibc_malloc/
作者
Ltfall
发布于
2023年9月23日
许可协议