堆基础入门

堆基础

内存分配后的系统调用主要是(s)brk与mmap、munmap函数。start_brk指向bss的末尾，brk()与sbrk()来移动program_break使得堆增长；当用户申请内存过大(大于128kb)，ptmalloc2会选择mmap函数创建匿名映射段供用户使用，并通过unmmap函数回收。

chunk

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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)                      .
next    .                                                               |
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |             (size of chunk, but used for application data)    |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |             Size of next chunk, in bytes                |A|0|1|
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

​ 对于已经分配的chunk,前两个字段称为chunk header,后面称为user data。每次 malloc 申请得到的内存指针，也就是指向 user data 的起始处。
​ 对于prev_size字段，分配时可被上一chunk复用，空闲时代表前一chunk的size。这里的前一chunk指较低地址的chunk。
​ 对于size字段，该字段的低三个比特位对chunk大小没有影响，从高到低依次为：A：记录当前 chunk 是否不属于主线程，1 表示不属于，0 表示属于；M：记录当前 chunk 是否是由 mmap 分配的；P：记录前一个 chunk 块是否被分配，堆中第一个chunk P位常设置为1。
​ 一般来讲，物理相邻的两个空闲 chunk 会被合并为一个 chunk 。堆管理器会通过 prev_size 字段以及 size 字段合并两个物理相邻的空闲 chunk块。

top chunk

​ 程序第一次进行 malloc 的时候，heap 会被分为两块，一块给用户，剩下的那块就是 top chunk。其实，所谓的 top chunk 就是处于当前堆的物理地址最高的 chunk。这个 chunk 不属于任何一个 bin，它的作用在于当所有的 bin 都无法满足用户请求的大小时，如果其大小不小于指定的大小，就进行分配，并将剩下的部分作为新的 top chunk。否则，就对 heap 进行扩展后再进行分配。在 main arena 中通过 sbrk 扩展 heap，而在 thread arena 中通过 mmap 分配新的 heap。需要注意的是，top chunk 的 prev_inuse 比特位始终为 1，否则其前面的 chunk 就会被合并到 top chunk 中。

remainder

​ 当用户申请的chunk较小时，会先将一个较大的chunk进行拆分，合适的部分交给用户，剩下的部分则加入unsorted bin中（称为remainder）。同时malloc_state中的last_remainder会记录最近拆分出的remainder。
​ 拆分chunk的一种情况是：fast bin与small bin中没有合适的chunk，同时unsorted bin中有且只有一个可拆得分的chunk,并且为last remainder。

bin

bin对应的数据结构在malloc_state中：

1
2
3
#define NBINS 128
/* Normal bins packed as described above */
mchunkptr bins[ NBINS * 2 - 2 ];

bins就是用于存储 unstored bin，small bins 和 large bins 的 chunk 链表。
一个bin对应两个bins,一共有126个bin:
bin1为unsorted bin;
bin2到bin63为small bin;
bin64到bin126为large bin;

fast bin

程序申请与释放的堆块往往比较小，所以glibc采用单链表且LIFO。
FastbinsY也是一个bin数组，一共NFASTBINS个fast bin.
为了加快速度，fast bin里的chunk不会合并。所以下一个chunk的inuse始终为1，使其始终为使用状态。

unsorted bin

使用双链表结构，FIFO。unsorted bin 可以视为空闲 chunk 回归其所属 bin 之前的缓冲区。其chunk大小可以不同，主要两个来源：
1.当一个较大的 chunk 被分割成两半后，如果剩下的部分大于 MINSIZE，就会被放到 unsorted bin 中。
2.释放一个不属于 fastbin 的 chunk，并且该 chunk 不和 top chunk 紧邻时，该 chunk 会被首先放到 unsorted bin 中。

small bin

32-1008字节与fastbin有重合的地方

large bin

分为6组，每组能容纳的成等差数列。双链表结构，按大小顺序排列。fd_nextsize与bk_nextsize分别都用来指向第一个与自己不同大小的chunk，为加快检索速度。

malloc_consolidate

由于fastbin中的chunk无法释放，导致相邻chunk无法与之合并，从而造成大量内存碎片，malloc_consolidate函数即用来解决这个问题，该函数可将fastbin中的chunk取出来，与相邻的free chunk合并后放入unsorted bin中或者形成新的top chunk。

malloc

_libc_malloc()

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
84
85
86
void * __libc_malloc (size_t bytes)
{
  /* mstate类型对应的结构体是 malloc_state */
  mstate ar_ptr;
  void *victim;

  _Static_assert (PTRDIFF_MAX <= SIZE_MAX / 2,
                  "PTRDIFF_MAX is not more than half of SIZE_MAX");
  
  /* 如果存在__malloc_hook，则调用 hook 函数 */
  void *(*hook) (size_t, const void *)
    = atomic_forced_read (__malloc_hook);
  if (__builtin_expect (hook != NULL, 0))
    return (*hook)(bytes, RETURN_ADDRESS (0));

/* 使用 tcache 机制的情况  */
#if USE_TCACHE
  /* int_free also calls request2size, be careful to not pad twice.  */
  size_t tbytes;

  /* 判断请求分配字节的大小，在 64 位的情况下，bytes 不能大于 0x7fffffffffffffff；*/
  /* 在 32 位的情况下，bytes 不能超过 0x7fffffff。函数中也会调用 request2size 来 */ 
  /* 计算 bytes 数据需要分配的内存大小，当 bytes 数据的大小比最小 chunk 要还小时，*/
  /* 按最小 chunk 的大小分配；当 bytes 数据的大小比最小 chunk 大时，则分配满足内存 */
  /* 对齐要求的最小大小。将分配的大小赋值给 tbytes 返回。 */
  if (!checked_request2size (bytes, &tbytes))
    {
      __set_errno (ENOMEM);
      return NULL;
    }

  /* 计算 tbytes 大小所对应的 tcache 下标 */
  size_t tc_idx = csize2tidx (tbytes);
  
  /* 如果 tcache 还没有被创建，则调用 tcache_init() 初始化 tcache */
  MAYBE_INIT_TCACHE ();

  DIAG_PUSH_NEEDS_COMMENT;
  
  /* 这里的 mp_ 是 malloc_par 结构 */
  /* 判断 idx 是否在 tcache bins 的范围内 */
  /* 判断 tcache 是否存在 */
  /* 判断 idx 对应的 tcache bins 中是否有空闲 tcache chunk */
  if (tc_idx < mp_.tcache_bins
      && tcache
      && tcache->counts[tc_idx] > 0)
    {
      return tcache_get(tc_idx);  /* 获得对应大小的 chunk */
    }
  DIAG_POP_NEEDS_COMMENT;
#endif
  
  /* 没有启用多线程的情况 */
  if (SINGLE_THREAD_P)
    {
      victim = _int_malloc (&main_arena, bytes);  /* 调用 _int_malloc 函数分配内存 */
      /* 当前 chunk 是从 mmap 分配的或当前 chunk 是从主分配区分配的 */
      assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
	      &main_arena == arena_for_chunk (mem2chunk (victim)));  
      return victim;  /* 将成功分配的内存指针返回 */
    }

  /* 启用多线程的情况 */
  arena_get (ar_ptr, bytes); /* 获取分配区 */

  victim = _int_malloc (ar_ptr, bytes);  /* 同上 */
  /* Retry with another arena only if we were able to find a usable arena
     before.  */
  /* 如果成功获取分配区，但是分配内存失败，可能是 mmap 区域的内存耗尽等多种原因 */
  /* 不同的原因有不同的解决方法，比如更换分配区等等 */
  /* 所以这里重新进行了获取分配区和分配内存操作，确保内存分配成功 */
  if (!victim && ar_ptr != NULL)
    {
      LIBC_PROBE (memory_malloc_retry, 1, bytes);
      ar_ptr = arena_get_retry (ar_ptr, bytes);
      victim = _int_malloc (ar_ptr, bytes);
    }
  
  /* 这里是释放线程锁，不用管它 */
  if (ar_ptr != NULL)
    __libc_lock_unlock (ar_ptr->mutex);

  assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
          ar_ptr == arena_for_chunk (mem2chunk (victim)));
  return victim; 
}

_int_malloc()

​ _int_malloc()是内存分配的核心函数，为了以最快速度找到最合适的chunk，glibc根据申请堆块的大小和各个bin的状态安排了分配顺序和内存整理的时机，大致搜索顺序：
1）fast bin(大小完全一样)
2）small bin(大小完全一样)
3）unsorted bin(大小完全一样)
4）large bin(大小完全一样)
5）bins(寻找最小的能满足的)
6）top chunk(切出合适的chunl)
7）系统函数分配