Glibc-堆管理学习笔记

发表于 | 分类于

关于glibc堆内存管理，已经有很多文章进行了深入的剖析，这里我记录一下自己学习过程中的一些总结。

Arena结构

glibc是基于ptmalloc2的堆内存管理器，通过arena结构来支持多线程堆内存管理。每一个线程的堆内存状态都由arena结构来纪录，这是一个malloc_state类型的结构体。

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
struct malloc_state
{
  /* Serialize access.  */
  __libc_lock_define (, mutex);

  /* Flags (formerly in max_fast).  */
  int flags;

  /* Fastbins */
  mfastbinptr fastbinsY[NFASTBINS]; //10

  /* 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;
};

一般主要关注malloc_state结构体当中的三个元素：

fastbinsY，保存fast bin的空闲堆块
top，top chunk
bins，保存small bin，unsorted bin，large bin的空闲堆块

上面三个关键元素在下面进行详细的解释。

对于主线程的堆内存管理，它的状态由全局变量main_arena来保存。需要注意的是，并不是有多少线程系统就分配多少arena，arena的个数与系统的核心数相关。当存在多于arena个数的线程应用时，多个线程之间共享使用arena。
至于为什么会提出arena结构，因为早期的堆内存管理是不支持多线程应用的，多个线程之间存在共享使用堆数据结构带来的性能开销问题，比如当前线程要使用堆，必须等待前一个线程释放相关的堆结构。
引入arena结构之后，每一个线程都拥有自己独立的堆结构。

brk与mmap系统调用

主线程与非主线程的堆，在内存分配方面有些许不同，主要体现在系统调用上。
对于main arena而言，通过brk系统调用来分配或者扩展堆内存。当第一次调用malloc的时候，程序会被分配一个初始的132KB的堆内存，如果后续的使用超过了这个大小，则通过调用brk来扩展当前的堆大小。
对于thread arena而言，通过mmap来分配或者扩展堆内存，类似与main arena。
关于这两个系统调用，这篇文章有详细说明Syscalls used by malloc。

glibc的堆内存管理

glibc是通过chunk来进行堆内存的管理的，这里的chunk就是一个个大小固定的内存单元，最开始系统给程序只有一个top chunk，大小为132kb。
当程序需要获取一块内存时，便通过在top chunk上分割一部分来返回给用户程序，剩余的部分作为新的top chunk。
当程序释放之前申请的内存时，为了提高程序的性能，引入了bin结构，来保存释放的内存块，以方便程序下次的内存申请。
这里主要有三个bin结构：
fast bin，small bin以及large bin。下面将一个个介绍这三个bin结构。

堆块chunk

首先需要了解一下chunk的结构。
在glibc源码中，是通过malloc_chunk这个结构体来定义chunk的：

1
2
3
4
5
6
7
8
9
10
11
12
struct malloc_chunk {

  INTERNAL_SIZE_T      mchunk_prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      mchunk_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的详细描述：

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
   malloc_chunk details:

    (The following includes lightly edited explanations by Colin Plumb.)

    Chunks of memory are maintained using a `boundary tag' method as
    described in e.g., Knuth or Standish.  (See the paper by Paul
    Wilson ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a
    survey of such techniques.)  Sizes of free chunks are stored both
    in the front of each chunk and at the end.  This makes
    consolidating fragmented chunks into bigger chunks very fast.  The
    size fields also hold bits representing whether chunks are free or
    in use.

    An allocated chunk looks like this:


    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)                      .
	    .                                                               |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             (size of chunk, but used for application data)    |
	    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             Size of next chunk, in bytes                |A|0|1|
	    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

    Where "chunk" is the front of the chunk for the purpose of most of
    the malloc code, but "mem" is the pointer that is returned to the
    user.  "Nextchunk" is the beginning of the next contiguous chunk.

    Chunks always begin on even word boundaries, so the mem portion
    (which is returned to the user) is also on an even word boundary, and
    thus at least double-word aligned.

    Free chunks are stored in circular doubly-linked lists, and look like this:

    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             Size of previous chunk, if unallocated (P clear)  |
	    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    `head:' |             Size of chunk, in bytes                     |A|0|P|
      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             Forward pointer to next chunk in list             |
	    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             Back pointer to previous chunk in list            |
	    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             Unused space (may be 0 bytes long)                .
	    .                                                               .
	    .                                                               |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    `foot:' |             Size of chunk, in bytes                           |
	    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             Size of next chunk, in bytes                |A|0|0|
	    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

    The P (PREV_INUSE) bit, stored in the unused low-order bit of the
    chunk size (which is always a multiple of two words), is an in-use
    bit for the *previous* chunk.  If that bit is *clear*, then the
    word before the current chunk size contains the previous chunk
    size, and can be used to find the front of the previous chunk.
    The very first chunk allocated always has this bit set,
    preventing access to non-existent (or non-owned) memory. If
    prev_inuse is set for any given chunk, then you CANNOT determine
    the size of the previous chunk, and might even get a memory
    addressing fault when trying to do so.

    The A (NON_MAIN_ARENA) bit is cleared for chunks on the initial,
    main arena, described by the main_arena variable.  When additional
    threads are spawned, each thread receives its own arena (up to a
    configurable limit, after which arenas are reused for multiple
    threads), and the chunks in these arenas have the A bit set.  To
    find the arena for a chunk on such a non-main arena, heap_for_ptr
    performs a bit mask operation and indirection through the ar_ptr
    member of the per-heap header heap_info (see arena.c).

    Note that the `foot' of the current chunk is actually represented
    as the prev_size of the NEXT chunk. This makes it easier to
    deal with alignments etc but can be very confusing when trying
    to extend or adapt this code.

从上面文档说明可以看出，chunk分为allocated chunk和free chunk，这两个chunk虽然是同一个内存块，却具有不同的字段意义。
但是，他们的头部字段是相同的。chunk的头部字段分为prev_size和size字段，各占8字节，总共16字节。当用户申请一块内存时，返回给用户的指针指向的位置为mem处。

prev_size，只有当前一个chunk为free状态的时候，这个字段才有意义，表示前一个free chunk的大小。
size，表示chunk的大小，包括头部。

由于chunk的大小为16的倍数，也就是说size字段的后4个bit永远用不到，所以可以使用后三个bit来保存一些其他信息，从低字节开始依次为：P，M，A。

P，表示此块的上一块是否在使用当中，如果上一块处于free状态，则置0，此时，prev_size字段保存的值就是上一块的大小。
M，表示此块是否是由mmap分配，如果为0，表示是通过top chunk分割而来。
A，表示是否不属于main_arena，如果为0,表示此块是在主线程当中分配的。

free chunk

前面提到的bin结构，就是用来管理这些被释放的chunk的。为了方便管理，引入了fd和bk两个指针，指向处于同一个bin的前后两个free chunk。
这样，便形成了一个循环双链表，fastbin是例外，它是单链表。

allocated chunk

这里需要注意的是，glibc很好的利用了空间复用的策略，提高了内存的使用效率。

1：由于fd和bk字段只有在free chunk当中才有意义，所以在allocated chunk当中可以用来存储用户数据。
2：prev_size字段一样，只有当前一个chunk处于free状态时才有意义，所以，当前allocated chunk可以使用下一个chunk的prev_size字段来存储用户数据。

最小的chunk大小

需要保证最基本的prev_size，size，fd，bk的存储空间，所以chunk最小的尺寸为32字节。

chunk的内存对齐

为了方便内存管理，每当申请一块内存时，系统都会将申请的大小加上8字节，然后对齐到16字节的倍数。
这里为什么加上8字节？因为prev_size字段可以用于存储数据，所以本质上属于前一个chunk，这里只加上size字段的大小。

Fast bin

malloc_state结构体当中的fastbinY数组，保存的是大小从32字节到128字节的free chunk。

1：fast bin是一个单链表结构，每一个数组元素，都是一个单链表头。每一个单链表保存的chunk大小都相同，相邻的单链表保存的chunk尺寸间隔为16字节。这样算下来总共有7个fast bin，剩余的fastbinY元素没有使用。
2：属于fast bin尺寸范围的chunk被free之后，它下一块chunk的P位不置为0。
3：物理内存相邻的fast bin chunk不进行合并操作。

示例

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
48
49
50
51
//一个简单的堆管理程序
#include<stdio.h>
#include<stdlib.h>

void *array[10] = {NULL};

void create()
{
	int temp = 0;
	scanf("%d",&temp);
	getchar();
	void *ptr = malloc(temp);
	int i = 0;
	for(;i <= 9;i++)
	{
		if(array[i] == NULL)
		{
			array[i] = ptr;
			break;
		}
	}
}

void delete()
{
	int temp = 0;
	scanf("%d",&temp);
	getchar();
	free(array[temp]);
}

int main()
{
	int temp = 0;
	while(1)
	{
		scanf("%d",&temp);
		getchar();
		switch(temp)
		{
			case 1:
				create();
				break;
			case 2:
				delete();
				break;
			case 3:
				exit(0);
		}
	}
}

连续申请3个23字节大小的内存块，并依次释放，查看arena的状态。

三个chunk

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
0x55a28872b410 FASTBIN {
  mchunk_prev_size = 0, 
  mchunk_size = 33, 
  fd = 0x0, 
  bk = 0x0, 
  fd_nextsize = 0x0, 
  bk_nextsize = 0x21
}
0x55a28872b430 FASTBIN {
  mchunk_prev_size = 0, 
  mchunk_size = 33, 
  fd = 0x55a28872b410, 
  bk = 0x0, 
  fd_nextsize = 0x0, 
  bk_nextsize = 0x21
}
0x55a28872b450 FASTBIN {
  mchunk_prev_size = 0, 
  mchunk_size = 33, 
  fd = 0x55a28872b430, 
  bk = 0x0, 
  fd_nextsize = 0x0, 
  bk_nextsize = 0x20b91
}

pwndbg> x/20xg 0x55a28872b410
0x55a28872b410:	0x0000000000000000	0x0000000000000021
0x55a28872b420:	0x0000000000000000	0x0000000000000000
0x55a28872b430:	0x0000000000000000	0x0000000000000021
0x55a28872b440:	0x000055a28872b410	0x0000000000000000
0x55a28872b450:	0x0000000000000000	0x0000000000000021
0x55a28872b460:	0x000055a28872b430	0x0000000000000000

可以看出申请的23个字节，加上8字节，之后对齐到32字节。33是因为最后的P位为1，fast bin的chunk即使free之后，P位也不置为0。

bin的内容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
pwndbg> bins
fastbins
0x20: 0x55a28872b450 —▸ 0x55a28872b430 —▸ 0x55a28872b410 ◂— 0x0
0x30: 0x0
0x40: 0x0
0x50: 0x0
0x60: 0x0
0x70: 0x0
0x80: 0x0
unsortedbin
all: 0x0
smallbins
empty
largebins
empty

fastbin为单链表。

arena内容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
pwndbg> arena
{
  mutex = 0, 
  flags = 0, 
  fastbinsY = {0x55a28872b450, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0}, 
  top = 0x55a28872b470, 
  last_remainder = 0x0, 
  bins = {0x7fdf372a5b58 <main_arena+88>, ...}, 
  binmap = {0, 0, 0, 0}, 
  next = 0x7fdf372a5b00 <main_arena>, 
  next_free = 0x0, 
  attached_threads = 1, 
  system_mem = 135168, 
  max_system_mem = 135168
}

32字节的free chunk组成的链表，其头部存储到fastbinY数组的第一个元素中。
当再申请一个22字节(对齐之后的chunk大小也为32字节)大小的内存块时，会将链表头部元素取出来，并更新fastbinY数组第一个元素的内容为头部chunk的fd值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
pwndbg> arena
{
  mutex = 0, 
  flags = 0, 
  fastbinsY = {0x55a28872b430, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0}, 
  ...
}
pwndbg> bins
fastbins
0x20: 0x55a28872b430 —▸ 0x55a28872b410 ◂— 0x0
0x30: 0x0
0x40: 0x0
0x50: 0x0
0x60: 0x0
0x70: 0x0
0x80: 0x0
...

可以看出fastbin单链表的操作顺序是LIFO，后进先出。

Unsorted bin

Unsorted bin是一个循环双链表结构，保存的chunk大小不一，只有一个bin，就是malloc_state结构体当中的bins数组的bins[1]。
当free的chunk的size大于128字节的时候，首先会将chunk链接到unsorted bin当中，除非free的chunk和top chunk相连，这时会将free的chunk直接并入top chunk当中。

Small bin

small bin也是一个循环双链表结构。

保存的chunk大小从32字节到1008字节。
一共有62个bin，每一个bin保存的chunk尺寸都是一样的。相邻bin的chunk尺寸间隔16字节。
物理内存相邻的chunk会进行合并操作，主要通过unlink宏实现。

关于small bin双链表的头部和尾部在bins数组当中的存储，利用了伪chunk的技巧。

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
if (in_smallbin_range (nb))
    {
      idx = smallbin_index (nb);
      //定位bin的索引
      bin = bin_at (av, idx);
      //根据索引得到bin的一个元素，取地址，减去偏移，得到伪chunck的地址

      if ((victim = last (bin)) != bin) //循环链表尾节点
      //bins当中没有填充free chunck的时候，伪chunck的头部地址和fd，bk的值是一样的
        {
          if (victim == 0) /* initialization check */
            malloc_consolidate (av);
          else
            {
              bck = victim->bk;
              if (__glibc_unlikely (bck->fd != victim))
                {
                  errstr = "malloc(): smallbin double linked list corrupted";
                  goto errout;
                }
              set_inuse_bit_at_offset (victim, nb);
              bin->bk = bck;
              bck->fd = bin;

              if (av != &main_arena)
                set_non_main_arena (victim);
              check_malloced_chunk (av, victim, nb);
              void *p = chunk2mem (victim);
              alloc_perturb (p, bytes);
              return p;
            }
        }
    }

而bin_at是一个宏，它的定义是这样的：

1
2
3
#define bin_at(m, i) \
  (mbinptr) (((char *) &((m)->bins[((i) - 1) * 2]))			      \
             - offsetof (struct malloc_chunk, fd))

offsetof宏就是取得fd在malloc_chunk结构体当中的偏移。
当对malloc_state进行初始化的时候，也使用了伪chunk进行初始化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
static void
malloc_init_state (mstate av)
{
  int i;
  mbinptr bin;

  /* Establish circular links for normal bins */
  for (i = 1; i < NBINS; ++i)
    {
      bin = bin_at (av, i);//定位伪chunk
      bin->fd = bin->bk = bin;//利用伪chunk对bins数组进行初始化
    }

#if MORECORE_CONTIGUOUS
  if (av != &main_arena)
#endif
  set_noncontiguous (av);
  if (av == &main_arena)
    set_max_fast (DEFAULT_MXFAST);
  av->flags |= FASTCHUNKS_BIT;

  av->top = initial_top (av);
}

当small bin为空的时候，数组bins的内容

1
2
3
4
5
6
7
8
9
10
11
pwndbg> x/20xg 0x7fdf372a5b68
0x7fdf372a5b68 <main_arena+104>:	0x00007fdf372a5b58	0x00007fdf372a5b58
0x7fdf372a5b78 <main_arena+120>:	0x00007fdf372a5b68	0x00007fdf372a5b68
0x7fdf372a5b88 <main_arena+136>:	0x00007fdf372a5b78	0x00007fdf372a5b78
0x7fdf372a5b98 <main_arena+152>:	0x00007fdf372a5b88	0x00007fdf372a5b88
0x7fdf372a5ba8 <main_arena+168>:	0x00007fdf372a5b98	0x00007fdf372a5b98
0x7fdf372a5bb8 <main_arena+184>:	0x00007fdf372a5ba8	0x00007fdf372a5ba8
0x7fdf372a5bc8 <main_arena+200>:	0x00007fdf372a5bb8	0x00007fdf372a5bb8
0x7fdf372a5bd8 <main_arena+216>:	0x00007fdf372a5bc8	0x00007fdf372a5bc8
0x7fdf372a5be8 <main_arena+232>:	0x00007fdf372a5bd8	0x00007fdf372a5bd8
0x7fdf372a5bf8 <main_arena+248>:	0x00007fdf372a5be8	0x00007fdf372a5be8

每两个数组元素为一个bin。可以看出每一个bin的内容都为其本身的地址减去16，也就是减去了fd的偏移。以main_arena+104这个bin为例，这是一个unsorted bin，它对应的伪chunk头在0x00007fdf372a5b58地址处，而unsorted bin的内容就是伪chunk的fd和bk值。
对于small bin和large bin而言也一样，在组成循环双链表的时候，这个伪chunk会作为头部节点。

Large bin

large bin保存的是从1024字节开始的大块chunk，也是双链表结构，共有63个bin。
但是和前面相比不同的是，每一个bin保存的chunk大小不一致。

总结

上面说道，当free一个128字节以上的chunk时，首先会将chunk放入unsorted bin当中，那么，何时才会将free的chunk放入对应的bin当中呢？
当下一次申请内存时，unsorted bin当中的chunk不能满足要求时，会将unsorted bin当中的free chunk放入对应的bin，这是glibc当中唯一的一处将free chunk放入small bin和large bin当中代码。
small bin保存的free chunk范围包括了fast bin的范围，这么做没有矛盾吗？
fast bin的提出是为了更快的分配内存，但是也会带来内存碎片率增高的负面影响，当一个应用对内存碎片率要求较高时，可以通过关闭fast bin来实现，这时，small bin就代替fast bin来管理较小的内存块。

参考链接

Understanding glibc malloc
Linux堆内存管理深入分析(上)
Linux堆内存管理深入分析(下)