updated:

Glibc的堆实现

Glibc的堆实现

在这篇文章中，我们将会介绍Linux操作系统中堆（glibc）的具体实现。本文基本覆盖了glibc 2.30中所有关于堆的操作，然而由于笔者尚未开始对堆利用的学习，在漏洞利用方面的描述不多。当然对于经典的漏洞，笔者或许会略有提及，但这不是本文的目的所在。撰写本文的目的是更深刻的理解源代码中渗透出的计算机思想，为计算机底层开发和日后堆利用的学习打下基础。 注一：由于源代码实现的复杂性和笔者有限的知识，我们在本文中假设只有一个主线程在对堆进行操作，因此只考虑main_arena的情况。对关于线程安全有关的内容，笔者以后会慢慢补充。 注二：文中绝大部分内容来自glibc中的注释和笔者个人的理解。目前尚无对其他资料的引用，若有引用，来源将会在文末放出。 注三：glibc实现堆的源代码中包含大量的交叉引用，笔者无法保证文章中靠前的内容一定不包含未介绍的内容。在这种情况下，推荐善用目录。

堆在哪里？

谈到堆，绕不开的第一道坎是虚拟地址空间中堆的位置。在Linux操作系统中，有一个程序描述符的概念，它是一个定义在linux/include/linux/sched.h中，名为task_struct的结构体。它描述了一个进程的几乎所有信息，在这里我们仅仅关注下面的一个成员：

1
struct mm_struct    *mm;

该成员为当前进程的内存空间描述符，再来看结构体mm_struct，它的原型在linux/include/linux/mm_types.h中，下面是该结构体原型的一部分：

1
2
3
4
spinlock_t arg_lock; /* protect the below fields */
unsigned long start_code, end_code, start_data, end_data;
unsigned long start_brk, brk, start_stack;
unsigned long arg_start, arg_end, env_start, env_end;

在这里，我们不仅看到了老朋友code，data，stack segment，还看到了我们在寻找的brk和start_brk指针。在一个程序的运行过程中，brk始终指向堆的顶部，而start_brk指向堆的底部。对brk的改变需要通过系统调用brk（读作break）来实现.

基本函数与结构

基本函数

sbrk函数

该函数是glibc对brk系统调用的一个封装。其源码如下； 我们可以看到，sbrk仅仅接受一个增量作为参数，而在sbrk的内部，其调用brk函数的参数仅仅是一个地址，这其中还使用了一个外部变量__curbrk。从这一点看来，sbrk和我们印象中的空间分配函数都不太一样。实际上，经过查找资料我们发现brk的作用实际上是设置一个叫做program break的东西的值，所谓的program break指的是elf在装载后data segment后第一个未初始化的字节的位置（一般可以认为是data segment的结尾）因此sbrk函数所做的实际上是通过增加data segment的大小来为程序分配可用空间。（在现代的linux系统中，为了安全起见，program break的初始位置可能经过了一定的随机化，因此通过堆地址泄露出ELF装载地址的方法可能不可行）。

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
/* Defined in brk.c.  */
extern void *__curbrk;
extern int __brk (void *addr);

/* Extend the process's data space by INCREMENT.
   If INCREMENT is negative, shrink data space by - INCREMENT.
   Return start of new space allocated, or -1 for errors.  */
void *
__sbrk (intptr_t increment)
{
  void *oldbrk;

  /* If this is not part of the dynamic library or the library is used
     via dynamic loading in a statically linked program update
     __curbrk from the kernel's brk value.  That way two separate
     instances of __brk and __sbrk can share the heap, returning
     interleaved pieces of it.  */
  if (__curbrk == NULL  __libc_multiple_libcs)  // 当前没有brk
    if (__brk (0) < 0)    /* Initialize the break.  */
      return (void *) -1;  // 初始化失败

  if (increment == 0)  // 提高效率
    return __curbrk;

  oldbrk = __curbrk;
  if (increment > 0
      ? ((uintptr_t) oldbrk + (uintptr_t) increment < (uintptr_t) oldbrk)
      : ((uintptr_t) oldbrk < (uintptr_t) -increment))  //整形溢出检查（妙）
    {
      __set_errno (ENOMEM);
      return (void *) -1;
    }

  if (__brk (oldbrk + increment) < 0)  // 关键部分，改变brk指针
    return (void *) -1;

  return oldbrk;
}
libc_hidden_def (__sbrk)
weak_alias (__sbrk, sbrk)  // 定义弱符号sbrk

__default_morecore

函数源码

glibc/malloc/morecore.c 实际上在malloc的实现中，sbrk函数被进行了进一步的封装，代码如下：

1
2
3
4
5
6
7
8
9
10
11
/* 将数据空间变化INCREMENT个byte，函数返回新空间的起始位置
当INCREMENT为负数时缩减空间。返回NULL代表出现错误。*/
void *
__default_morecore (ptrdiff_t increment)
{
    void *result = (void *) __sbrk (increment);
    if (result == (void *) -1)
        return NULL;

    return result;
}
MORECORE

与该函数相关的宏定义如下：

1
2
3
4
5
/* Definition for getting more memory from the OS.  */
#define MORECORE         (*__morecore)
#define MORECORE_FAILURE 0
void * __default_morecore (ptrdiff_t);
void *(*__morecore)(ptrdiff_t) = __default_morecore;

可以看到，宏MORECORE代表了向操作系统申请空间的函数。MORECORE_FAILURE则是发生错误时的返回值。 其实这个宏的值也可以更改为sbrk，只是此时的错误返回值变成-1 你甚至可以自己实现一个合适的函数来满足MORECORE宏的要求。

MORECORE_CONTIGUOUS
1
2
3
#ifndef MORECORE_CONTIGUOUS
#define MORECORE_CONTIGUOUS 1
#endif

如果MORECORE_CONTIGUOUS为真，那么我们可以利用对MORECORE使用正的参数的连续调用总是会返回连续的增长的地址的特点。（对于Unix的sbrk函数来说，这是正确的。）即使这个常量没有被定义，当返回地址是连续的时，malloc依然允许分配跨越通过不同sbrk调用得到的区域的块。然而对该常量的定义可以开启一些更强的连续性检查以及更高的空间利用率。

基本结构：malloc_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
/*
  -----------------------  Chunk representations -----------------------
*/

/*
  该结构体的定义或许有些误导人（但它绝对是准确而且必须的）
  它为我们打开了一扇使用已知的偏移和基地址一窥内存中必要数据域的窗口。
  详情查看下面的解释。
*/

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

下面是源代码中对该结构体的详细注释： malloc_chunk的详情： 我们使用一种被称为“边界标记”的方式来维护内存片。块的大小被同时存储在这个块的头部和脚部（size域），这大大加快了将碎片化的块合并为大块的速度。size域中同时包含了表示该块是否被使用的标志位。 一个被分配的内存块可能具有如下形式：

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                     AMP
      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                         User data starts here...                          .
            .                                                               .
            .             (malloc_usable_size() bytes)                      .
            .                                                               
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                         (size of chunk, but used for application data)    
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                         Size of next chunk, in bytes                A01
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

其中chunk指向的是malloc的代码实现中常常会用到的块的开头，而实际上用户得到的是mem 指向的地址。nextchunk是连续内存中下一个块的开头。 内存块的起始边界总是以偶数字对齐，因此用户得到的mem指针也总是以偶数字对齐（至少是 双字对齐） 空闲块总是被存储在双向循环链表中，它看起来像这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                         Size of previous chunk, if unallocated (P clear)  
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    `head:'              Size of chunk, in bytes                     A0P
      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                A00
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

P标志位（PREV_INUSE）位于块的size域的最低位（由于size总是以双字对齐，因此有未被使用的低位），它标志着上一个块是否被使用。当该位为0时（即上一个块未被使用）size域之前的一个字（prev_size）代表上一个块（是一个空闲块）的大小，以此我们能找到上一个块的开头。最初分配的一个块的P标志位总是为1，以避免我们访问到不存在或者不被当前进程拥有的地址。在任何P标志位为1的块中，你都不能试图获取前一个块的大小，这种操作是无效的，甚至可能引起错误。 A标志位（NON_MAIN_ARENA）用于指示一个块是否在由变量main_arena所描述的最初的主要内存分配区域中。在多线程的环境下，每个线程都有独立的内存分配区域（区域的数量有上限，超过上限会导致分配区域不再接受新线程）。其他线程的分配区域中的块将会把A标志位置位。为了找到这样的一个块从属的分配区域，我们使用heap_for_ptr宏来进行一次掩码操作：

1
2
#define heap_for_ptr(ptr) \
  ((heap_info *) ((unsigned long) (ptr) & ~(HEAP_MAX_SIZE - 1)))

然后间接通过得到的heap_info结构体来获取其ar_ptr成员，该成员指向当前的arena

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* A heap is a single contiguous memory region holding (coalesceable)
     malloc_chunks.  It is allocated with mmap() and always starts at an
     address aligned to HEAP_MAX_SIZE.  */

  typedef struct _heap_info
  {
    mstate ar_ptr; /* Arena for this heap. */
    struct _heap_info *prev; /* Previous heap. */
    size_t size;   /* Current size in bytes. */
    size_t mprotect_size; /* Size in bytes that has been mprotected
                             PROT_READPROT_WRITE.  */
    /* Make sure the following data is properly aligned, particularly
       that sizeof (heap_info) + 2 * SIZE_SZ is a multiple of
       MALLOC_ALIGNMENT. */
    char pad[-6 * SIZE_SZ & MALLOC_ALIGN_MASK];
  } heap_info;

注意当前块的脚部指下一个块的prev_size部分，_（放到当前块里面说，就是当前块的size）_这简化了对齐等操作，然而同时让扩展或变更处理这部分的代码变得困难。 下面是上面所说的三种例外情况

  1. “top”这个特殊的块并没有脚部的size域_（其实这是下一个块的prev_size部分，在源代码中，这里似乎没有严格的分界），因为其后不存在一个块需要查找到它（注意我们在堆的理论基础中说过，这一操作仅仅在合并时需要）_。在初始化后，top块需要一直存在，如果它的大小小于变量MINSIZE指定的大小，它将会被重新填满。

  2. 通过mmap直接分配，M标志位被置位的块。由于它们是逐个分配的，每个块都必须包含自己的脚部。我们会忽略一个M标志位被置位的块的其他标志位，因为它既不属于某个arena，也不会在内存中与某个空闲块相邻。The M bit is also used for chunks which originally came from a dumped heap via malloc_set_state in hooks.c.*（没看懂什么意思=-=）

  3. 在块分配器看来，fastbins中的块被看作是已经分配的块。他们仅仅会在malloc_consolidate函数中与他们的相邻块大量合并。

以上便是glibc 2.29中malloc_chunk结构体下方的注释，如果你仔细思考过，会发现该结构与我们上一篇文章 堆的理论基础 中提出的模型几乎完全一致。 读到这里，我们再回头看一下之前提到的边界标记的含义，谁是边界？是谁的边界？我们可不可以这样说：malloc_chunk是用户有效数据，以及填充之间的边界。你可能已经发现，malloc_chunk中并没有指定一个用于存放用户数据的data成员。实际上在内存中，堆块的布局像是下面的结构：

我们可以看到，每一个黄色区域（有效载荷或者空闲块的无效数据）的两端都被蓝色的malloc_chunk包围（当然，已分配的块的malloc_chunk的一部分也是有效载荷），因此我们完全可以考虑换一种角度去理解：堆便是由特定结构的边界分割的一块内存。 当然，我们现在也不能百分百搞懂有一些要点的意思，不要着急，下面我们会分析更详细的实现。

辅助信息

常用宏

我们使用宏来屏蔽平台之间的差异，下面是源代码中使用到的一些宏: 注意： - 一般来说，一个小标题对应一个宏。如果多个宏名称相似，功能相似，我们将会把它们合并到一个小标题中。对于名称相似的宏，名称中不同的部分使用xxx来代替，对于功能相似的宏，小标题会指示其功能。 - 在这里我们并没有列出所有的宏，有一些宏使用次数极少，而且是很好的self documented的，我们仅仅在使用到该宏的代码的注释中进行解释。

与对齐有关的宏

对齐是glibc内存管理中不可或缺的一部分，对应的宏数量也很可观。

SIZE_SZ

glibc/malloc/malloc-internal.h

1
2
3
4
5
6
#ifndef INTERNAL_SIZE_T
# define INTERNAL_SIZE_T size_t
#endif

/* The corresponding word size.  */
#define SIZE_SZ (sizeof (INTERNAL_SIZE_T))

解释：这是用于屏蔽平台差异的核心，SIZE_SZ被用来表示一个平台上的字长（32位一般是4byte，64位一般是8byte）。

MALLOC_ALIGNMENT

glibc/sysdeps/generic/malloc-alignment.h

1
2
3
4
5
/* MALLOC_ALIGNMENT是一个由malloc分配的块的最小对齐单位。它必须是2的倍数，且至少为
  SIZE_SZ倍。即使是在只需要很小的块的平台上这也是必须的。这个值当然可以更大，然而这里的
  代码和数据结构都以8byte的对齐作为假设进行了优化*/
#define MALLOC_ALIGNMENT (2 * SIZE_SZ < __alignof__ (long double) \
                          ? __alignof__ (long double) : 2 * SIZE_SZ)

解释：见注释，在64位下，这个值一般是16，32位下是8

MALLOC_ALIGN_MASK

glibc/malloc/malloc-internal.h

1
2
/* The corresponding bit mask value.  */
#define MALLOC_ALIGN_MASK (MALLOC_ALIGNMENT - 1)

解释：如我们以16byte对齐，那么对应的掩码便是0b1111。8byte对齐对应0b111

MIN_CHUNK_SIZE

glibc/malloc/malloc.c

1
2
/* The smallest possible chunk */
#define MIN_CHUNK_SIZE        (offsetof(struct malloc_chunk, fd_nextsize))

解释：最小的可能块大小被定义为了fd_nextsize与malloc_chunk结构体起始位置的偏移，经过简单的计算，我们发现这意味着一个最小的块大小为4个字（64位下是0x20个字节，32位下是0x10个字节）。（注意此时我们没有考虑对齐的问题）

MINSIZE

glibc/malloc/malloc.c

1
2
3
4
/* The smallest size we can malloc is an aligned minimal chunk */

#define MINSIZE  \
  (unsigned long)(((MIN_CHUNK_SIZE+MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK))

解释：考虑对齐时的最小块大小。与运算将会把得到的大小的低位清零。加法是为了保证最小块大小大于可能的最小块大小（即“多一点点也要进位”的思路）。按上面的例子（64位），有：(0x20 + 0xF) & ~0xF = 0x20。但如果把0x20换成0x21，计算就变成了（0x21 + 0xF) & ~0xF = 0x30。

request2size

glibc/malloc/malloc.c

1
2
3
4
5
6
/* pad request bytes into a usable size -- internal version */

#define request2size(req)                                         \
  (((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE)  ?             \
   MINSIZE :                                                      \
   ((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)

解释：将用户请求的大小变更为符合内存对齐标准的大小，算法同上。（这里是如何解决堆块复用的问题的？）

REQUEST_OUT_OF_RANGE
1
2
3
4
5
6
7
8
9
/*
   Check if a request is so large that it would wrap around zero when
   padded and aligned. To simplify some other code, the bound is made
   low enough so that adding MINSIZE will also not wrap around zero.
 */

#define REQUEST_OUT_OF_RANGE(req)                                 \
  ((unsigned long) (req) >=                                      \                
   (unsigned long) (INTERNAL_SIZE_T) (-2 * MINSIZE))
ALIGN_UP && ALIGN_DOWN
1
2
3
4
5
/* 将数值按size向下对齐  */
#define ALIGN_DOWN(base, size)  ((base) & -((__typeof__ (base)) (size)))

/* 将数值按size向上对齐  */
#define ALIGN_UP(base, size)  ALIGN_DOWN ((base) + (size) - 1, (size))

操作malloc_chunk的宏

常量定义
1
2
3
4
5
6
7
8
9
10
11
/* 当前一个相邻的块被使用时malloc_chunk的size域会与该值进行或运算 */
#define PREV_INUSE 0x1
#define IS_MMAPPED 0x2
#define NON_MAIN_ARENA 0x4
/*
   提取块大小时需要掩盖的几个位

   注意：对于一些本不应该接触到mmap产生的块的宏来讲，IS_MMAPPED标志位是不被掩盖的
   因此当人为的错误使得当这些宏意外访问这些块时，程序可以及时崩溃并产生有用的core dump
 */
#define SIZE_BITS (PREV_INUSE  IS_MMAPPED  NON_MAIN_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
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
#define chunksize_nomask(p)         ((p)->mchunk_size)
/* 直接提取size域，包括标志位  */

#define chunksize(p) (chunksize_nomask (p) & ~(SIZE_BITS))
/* 提取除去标志位之后的size域，即真正的总大小 */

#define prev_inuse(p)       ((p)->mchunk_size & PREV_INUSE)
/* 通过与运算提取PREV_INUSE位 */

#define chunk_is_mmapped(p) ((p)->mchunk_size & IS_MMAPPED)
/* 这个值仅当把块分配给用户时被立即设置 */
#define chunk_main_arena(p) (((p)->mchunk_size & NON_MAIN_ARENA) == 0)
/* 检查一个块是否来自main_arena */
#define set_non_main_arena(p) ((p)->mchunk_size = NON_MAIN_ARENA)
/* 标志一个块不在main_arena中  */

#define prev_size(p) ((p)->mchunk_prev_size)
/* P的前一个块的size域，仅当前一个块是空闲块时有效  */
#define set_prev_size(p, sz) ((p)->mchunk_prev_size = (sz))
/* 设置前一个块的size域，仅当前一个块是空闲块时有效  */

#define chunk_at_offset(p, s)  ((mchunkptr) (((char *) (p)) + (s)))
/* 将位于p + s处的数据视为一个malloc_chunk，并将对应的指针返回 */

#define inuse(p)                                                              \
  (
    (
        ((mchunkptr) 
            (((char *) (p)) + chunksize (p))
            // 跳过当前块，来到下一个块
        )->mchunk_size
        ) & PREV_INUSE
        // 取出下一个块的PREV_INUSE
    )
/* 获取p的inuse位，也就是p指向的块的下一个相邻块的prev_inuse位 */

#define set_inuse(p)                                                              
  ((mchunkptr) (((char *) (p)) + chunksize (p)))->mchunk_size = PREV_INUSE
#define clear_inuse(p)                                                              
  ((mchunkptr) (((char *) (p)) + chunksize (p)))->mchunk_size &= ~(PREV_INUSE)
// 设置p处块的inuse位（下一个块的PREV_INUSE）


/* check/set/clear inuse bits in known places */
#define inuse_bit_at_offset(p, s)                                              \
(
    (
        (mchunkptr) 
        (
            ((char *) (p))
            +
            (s)
            // 这是一个偏移量
        )
    )->mchunk_size & PREV_INUSE
)
#define set_inuse_bit_at_offset(p, s)                                              
  (((mchunkptr) (((char *) (p)) + (s)))->mchunk_size = PREV_INUSE)
#define clear_inuse_bit_at_offset(p, s)                                              
  (((mchunkptr) (((char *) (p)) + (s)))->mchunk_size &= ~(PREV_INUSE))
// 检查，设置或者提取未知位置处块的inuse位，这一组宏的作用以后会提到

#define set_head_size(p, s)  
（(p)->mchunk_size = 
    (
        (
            (p)->mchunk_size & SIZE_BITS
            // 实际size置0，保留标志位
        )  (s)
        // 设置size
    )
 )
// 在不影响use bit的前提下修改块头的size域
#define set_head(p, s)       ((p)->mchunk_size = (s))
// 直接设置size域（包括标志位）
#define set_foot(p, s)       (((mchunkptr) ((char *) (p) + (s)))->mchunk_prev_size = (s))
// 设置块的脚部的size域（包括标志位），（仅当块空闲时）

/* 在chunk header与用户区域的指针之间相互转换 */
#define chunk2mem(p)   ((void*)((char*)(p) + 2*SIZE_SZ))
#define mem2chunk(mem) ((mchunkptr)((char*)(mem) - 2*SIZE_SZ))
链表操作
1
2
3
4
5
#define next_chunk(p) ((mchunkptr) (((char *) (p)) + chunksize (p)))
/* 获取指向下一个chunk首部的指针 */

#define prev_chunk(p) ((mchunkptr) (((char *) (p)) - prev_size (p)))
/* 获取指向上一个chunk首部的指针（仅当prev_inuse未置位时有效 */

与fastbin有关的宏

源代码中的注释

Fastbins是一个用于容纳最近释放的小块的单链表数组。使用单链表是因为链表中的内存块并不会被移出（由于其分配策略），因此使用双向链表是不必要的，而且单链表的速度也足以胜任（甚至更快）。 同时，不同于其他通常的bins，由于对这些暂存的小块的使用并不十分受顺序的影响，fastbins使用更快的LIFO分配策略_（不需要对单链表进行遍历，只需要从头部插入或取出）_ fastbins中的块总是保持它们的inuse标志位（即下一个块的prev_inuse位）被置位，这样可以保证它们不会与相邻的空闲块合并_（否则就失去了意义）_。malloc_consolidate函数将会释放所有位于fastbins中的chunk并将它们与其他空闲块合并。

fastbin_index

glibc/malloc/malloc.c

1
2
3
4
/* offset 2 to use otherwise unindexable first 2 bins */
/* 注意这里的sz是包含chunk结构的堆块大小 */
#define fastbin_index(sz) \
  ((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)

解释：最终的减二是为了使用原本无法索引到的前两个bin（由于对齐的缘故）。其中sz是一个堆块的总大小，在64位下，这个大小是32，即2 << 5（因此我们需要减2）。因此根据上面的算式，fastbins中bin中chunk的总大小范围如下（64位）：

1
2
3
4
index 0     32 (0x20)
index 1     48 (0x30)
index 2     54 (0x40)
etc
MAX_FAST_SIZE

glibc/malloc/malloc.c

1
2
/* The maximum fastbin request size we support */
#define MAX_FAST_SIZE     (80 * SIZE_SZ / 4)

解释：定义了我们glibc支持的的fastbin的最大大小，在Linux amd64下，这个值是160，即0xA0。在i386下，这个值是80，即0x50。注意这并不一定是提供给用户的接口所允许的最大fastbin大小。

M_MXFAST

glibc/malloc/malloc.c

1
2
3
#ifndef M_MXFAST
#define M_MXFAST            1
#endif

解释：该常量被mallopt使用，是一个param_number，与fastbin的最大大小没有直接联系，我们将在下面介绍mallopt函数时一并提到。

DEFAULT_MXFAST

glibc/malloc/malloc.c

1
2
3
#ifndef DEFAULT_MXFAST
#define DEFAULT_MXFAST     (64 * SIZE_SZ / 4)
#endif

解释：这个值才是真正的fastbin的默认最大值。i386下是64byte，amd64下是128byte，详情参见下面的“特别注意”

set_max_fast

glibc/malloc/malloc.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* fasbins中内存块的最大值  */
static INTERNAL_SIZE_T global_max_fast;

/*
   设置global_max_fast的值
   当s为0时设置一个很小的值使得fasbin不可能存在.
   先决条件：main_arena中没有已经存在的fastbin chunk。
   因为do_check_malloc_state ()函数将会对此条件进行检查，我们在改变global_max_fast
   的值之前需要先调用malloc_consolidate ()函数将fastbin清空。注意对于其他的arena来说
   ，减小global_max_fast的值会导致fastbin的入口点被泄露。
 */

#define set_max_fast(s) \
  global_max_fast = (((s) == 0) ? SMALLBIN_WIDTH : ((s + SIZE_SZ) & ~MALLOC_ALIGN_MASK))

拆解：

1
2
3
4
5
6
7
8
9
10
11
(
    ((s) == 0)
    ?
    SMALLBIN_WIDTH
    // 最小值，使fastbin无法使用
    :
    (
        (s + SIZE_SZ) & ~MALLOC_ALIGN_MASK
        // 保证对齐，与request2size宏的操作类似
    )
)

解释：上面提到的“很小的值”指的是MALLOC_ALIGNMENT，这是一个malloc分配的堆块的最小对齐单位，一般任何一个有效的块都要比这个值大，因此fastbin相当于不存在了。

NFASTBINS

glibc/malloc/malloc.c

1
#define NFASTBINS  (fastbin_index (request2size (MAX_FAST_SIZE)) + 1)

解释：这个宏指定了我们fastbin中链表的总数，在Linux AMD64下，计算如下：

((0xA0 + 0x8 + 0b1111) \& (\sim0b1111) >> 4) - 2 + 1 = 10

在i386下，计算如下：

((0x50 + 0x4 + 0b111) \& (\sim0b111) >> 3) - 2 + 1 = 10

fastbin的最大大小

到底是谁规定了fastbin的最大大小？实际上这个值是global_max_fast，那么这个值又是由谁设置的呢？我们看到set_max_fast宏是一个设置这个值的一个较安全的封装。因此我们查找对set_max_fast宏的交叉引用，找到了下面两处代码： glibc/malloc/malloc.c

1
2
3
4
5
6
/*
static void
malloc_init_state (mstate av)
*/

set_max_fast (DEFAULT_MXFAST);

解释：该函数是arena初始化时会调用的函数。在这里，我们将global_max_fast设置为了DEFAULT_MXFAST。因此，DEFAULT_MXFAST是默认的fastbin的大小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
int
__libc_mallopt (int param_number, int value)
*/
 /* We must consolidate main arena before changing max_fast
   (see definition of set_max_fast).  */
malloc_consolidate (av);
//注意这里调用malloc_consolidate对fastbin进行了清空

switch (param_number)
  {
  case M_MXFAST:
  // 正如我们前面说的，M_MXFAST只是一个param_number，不太重要
    if (value >= 0 && value <= MAX_FAST_SIZE)
    // 注意这句话真正体现出了谁才是fastbin真正的最大值（the maximum value we support）
      {
        LIBC_PROBE (memory_mallopt_mxfast, 2, value, get_max_fast ());  
        // 不必在意，我也不知道这个宏在做什么=-=
        set_max_fast (value);
        // 将global_max_fast设置成我们给定的值
      }
    else
      res = 0;
      break;

解释：mallopt函数是一个面向用户的函数，如我们可以使用mallopt(M_MXFAST, 0)来停止使用fastbin。后面我们会对这个函数进行完整的分析。

与Bins有关的宏

glibc/malloc/malloc.c

源代码中的注释
综述

所有（Bins）的内部状态都保存在将在下面定义的malloc_state结构体的一个（静态）实例中。除此之外不应当有其他的静态变量（保存这些状态），除了下面这两个变量。

  • 当 USE_MALLOC_LOCK 被定义时, 有上面声明的 mALLOC_MUTEx
  • 如果不支持MAP_ANONYMOUS, mmap使用的一个伪文件描述符（dummy file descriptor）

注意有许多用于最小化记录（状态信息）所需要的空间的技巧。其结果是我们需要大概1K byte多一点的空间来存放这些信息（在一个字是4byte的机器上）。 之前我们提到过代码和数据结构有针对8byte对齐的平台的优化，一个字是4byte时刚好是8byte对齐。

Bins的概念

Bins是一个用于存放空闲链表的数组。每个链表都是双向的。这些链表大致是按照log尺度来放置的_（如64，32，16，8在log尺度上是等距的）。这些链表一共有128个，这初看可能有点过多，但实践已经验证了它的正确性。 大多数链表中空闲块的大小可能与我们使用malloc通常会申请的堆块大小不同，但它们常常是堆中的碎片和合并后的堆块的大小。以正因此，我们可以更快捷的进行查找。 我们维护着这样一个不变的事实：任何一个被合并后的堆块从物理上不与另一个相邻（即空闲块不相邻）。因此链表中的每个块要么是与已分配的块相邻。要么是位于可用的堆空间的尽头。 bins的链表中的块是按照大小来组织顺序的，链表的末端近似是距上次使用时间最久的块。对于small bins来说，顺序不是必须的，因为small bins的链表中的每个块大小相等（还记得我们的堆的理论基础吗？这属于基于大小类的简单分离存储策略）。然而对于较大的块的分类来说，顺序可以加快最佳适配的速度。These lists are just sequential. Keeping them in order almost never requires enough traversal to warrant using fancier ordered data structures.（完全不会翻译=-=）_ 在链接在一起的同等大小的块中，最近释放的块被排在最前面，而分配的块则会从链表的尾部取。即FIFO的分配顺序_（可以理解为一个链队），这样可以保证每个块具有同等的机会和相邻的空闲块合并，从而达成空闲块尽可能大，碎片尽可能少的目的。（可否添加更详细的解释？）_ 为了简化对双向链表的操作，每个bin的头部可以被当作malloc_chunk类型的数据使用。这避免了头部带来的特殊情况。但为了节省空间并增强局部性，我们仅仅为bins的头部分配fd与bk指针，然后使用一些tricks来把它们作为malloc_chunk的元素来看待。（记住这一点，下面有大用处） 你可能会问，哪里增强局部性了？下面是笔者的一点看法：假设我们使用amd64平台，那么一个完整的malloc_chunk的大小是48个字节。回顾我们学习的有关cache的知识，一个cache行可能是64字节或者32字节，这并不是48的倍数。这意味着当我们使用交替使用相邻的两块bin的头部的数据时，这些数据并不能很好的被放置到cache line中，在最坏的情况下甚至可能发生抖动。而当头部仅仅为两个指针，即16byte时，我们访问一个bin的头部之后可以保证与其相邻的4个bin的头部信息都完整的缓存到了cache中。这大大提升了访问局部数据的速度 （太妙了）

Bins的索引

大小在512byte以下的堆块所在的bin都只有一种大小的堆块，块的大小都为8的整数倍_（此处可能是历史遗留？64位按照16字节对齐。也无伤大雅）_。 更大的bins中堆块的大小大致按照对数分布。

1
2
3
4
5
6
7
64 bins of size       8
32 bins of size      64
16 bins of size     512
 8 bins of size    4096
 4 bins of size   32768
 2 bins of size  262144
 1 bin  of size what's left

为了速度，bin_index中的数字其实要稍大一点。但这没什么影响。（需要更详细的解释） bins中的块最大在1MB左右，因为我们假设更大的块是通过mmap来分配的。 索引为0的bin不存在，索引为1的bin是无序的链表。if that would be a valid chunk size the small bins are bumped up one._（不会翻译=-=）_

bin_at
1
2
3
4
/* addressing -- note that bin_at(0) does not exist */
#define bin_at(m, i) \
  (mbinptr) (((char *) &((m)->bins[((i) - 1) * 2]))                              \
             - offsetof (struct malloc_chunk, fd))

拆解：

1
2
3
4
5
6
7
8
9
10
11
(mbinptr) (
  (
    (char *) &
    (
      (m)->bins[((i) - 1) * 2]
      // 查找对应的头部，* 2是因为每个头部包含两个指针，注意i从1开始
      // 即前面说过的，第0个bin不存在
    )
  ) - offsetof (struct malloc_chunk, fd))
  // 减去一个偏移，将fd指针放到正确的位置上
  // 制造出一种“这里有一个完整的malloc_chunk的假象

解释：m是一个malloc_state实例，mbinptr是malloc_chunk结构体的一个别名。这是一个glibc用来节省空间和增强局部性的小trick。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
                       +-----------------+ This is what we get
                       
                               +--------+ We want this bin
                               
               +---+-------+---+v--+---+
                                 
                                 
                                 
                                 
               fd bk fd bk fd bk 
                                 
                                 
                                 
                                 
               +-+-+-+-+---+---+---+---+
                    
A bin's header<--+---+
next_bin
1
2
/* analog of ++bin */
#define next_bin(b)  ((mbinptr) ((char *) (b) + (sizeof (mchunkptr) << 1)))

解释：获取指向第b + 1个bin的指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
(
  (mbinptr)
  (
    (char *)
    (b)
    +
    (
      sizeof (mchunkptr) << 1
      // 两个指针大小
    )
    // 加上后相当于在bins中前进了一个bin
  )
)
// 最终得到的是索引为b + 1的bin的指针
first & last
1
2
#define first(b)     ((b)->fd)
#define last(b)      ((b)->bk)

解释：用于表示bin内部方向的备忘用宏

NBINS & NSMALLBINS
1
2
#define NBINS             128
#define NSMALLBINS         64

解释：分别是bins的总数（不包括fastbins）以及small bins的总数

SMALLBIN_xxx
1
2
#define SMALLBIN_WIDTH    MALLOC_ALIGNMENT
#define SMALLBIN_CORRECTION (MALLOC_ALIGNMENT > 2 * SIZE_SZ)

解释：smallbin的宽度就是一个块的最小对齐单位，SMALLBIN_CORRECTION指示当前对齐是否正确。

MIN_LARGE_SIZE
1
#define MIN_LARGE_SIZE    ((NSMALLBINS - SMALLBIN_CORRECTION) * SMALLBIN_WIDTH)

解释：定义了small bins中最大的s块大小

in_smallbin_range
1
2
#define in_smallbin_range(sz)  \
  ((unsigned long) (sz) < (unsigned long) MIN_LARGE_SIZE)

解释：通过将给定的大小与small bins中最大的块大小比较，得到该块是否位于small bins中

smallbin_index
1
2
3
#define smallbin_index(sz) \
  ((SMALLBIN_WIDTH == 16 ? (((unsigned) (sz)) >> 4) : (((unsigned) (sz)) >> 3))\
   + SMALLBIN_CORRECTION)

解释：通过一个给定的块大小判断这个块应该在small bins中的哪个bin里，注意这体现出的事实是：一般情况下，small bins中的bin的块大小在i386环境下成首项为8，公差为8的等差数列；在amd64环境下成首项为16，公差为16的等差数列

1
2
3
4
5
6
7
8
9
10
11
(
  (
    SMALLBIN_WIDTH == 16
    ?
    (
      ((unsigned) (sz)) >> 4
    )
    :
    (
      ((unsigned) (sz)) >> 3)
  ) + SMALLBIN_CORRECTION)
largebin_index_32
1
2
3
4
5
6
7
#define largebin_index_32(sz)                                                \
  (((((unsigned long) (sz)) >> 6) <= 38) ?  56 + (((unsigned long) (sz)) >> 6) :\
   ((((unsigned long) (sz)) >> 9) <= 20) ?  91 + (((unsigned long) (sz)) >> 9) :\
   ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
   ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
   ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
   126)

解释：此处拆解一个。下面类似的看看就好

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
(
  (
    (((unsigned long) (sz)) >> 6) <= 38
  ) ?  56 + (((unsigned long) (sz)) >> 6)
  :
  (
    (((unsigned long) (sz)) >> 9) <= 20
  ) ?  91 + (((unsigned long) (sz)) >> 9)
  :
   (
     (((unsigned long) (sz)) >> 12) <= 10
   ) ? 110 + (((unsigned long) (sz)) >> 12)
  :
   (
     (((unsigned long) (sz)) >> 15) <= 4
   ) ? 119 + (((unsigned long) (sz)) >> 15)
  :
   (
     (((unsigned long) (sz)) >> 18) <= 2)
  ? 124 + (((unsigned long) (sz)) >> 18)
  :
   126
)

基本就是判断给定的一个一个块大小落到了哪个bin中

largebin_index_32_big
1
2
3
4
5
6
7
#define largebin_index_32_big(sz)                                            \
  (((((unsigned long) (sz)) >> 6) <= 45) ?  49 + (((unsigned long) (sz)) >> 6) :\
   ((((unsigned long) (sz)) >> 9) <= 20) ?  91 + (((unsigned long) (sz)) >> 9) :\
   ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
   ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
   ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
   126)

同上

largebin_index_64
1
2
3
4
5
6
7
8
9
10
// XXX It remains to be seen whether it is good to keep the widths of
// XXX the buckets the same or whether it should be scaled by a factor
// XXX of two as well.
#define largebin_index_64(sz)                                                \
  (((((unsigned long) (sz)) >> 6) <= 48) ?  48 + (((unsigned long) (sz)) >> 6) :\
   ((((unsigned long) (sz)) >> 9) <= 20) ?  91 + (((unsigned long) (sz)) >> 9) :\
   ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\
   ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\
   ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\
   126)

同上

largebin_index
1
2
3
4
#define largebin_index(sz) \
  (SIZE_SZ == 8 ? largebin_index_64 (sz)                                     \
   : MALLOC_ALIGNMENT == 16 ? largebin_index_32_big (sz)                     \
   : largebin_index_32 (sz))

解释：对上面三个宏的二次封装，我们可以看到三种模式：64位，32位，32位大模式

bin_index
1
2
#define bin_index(sz) \
  ((in_smallbin_range (sz)) ? smallbin_index (sz) : largebin_index (sz))

解释：对上面宏的高度封装，通过一个给定的块大小获取其所在的bin的索引。注意这里面始终没有提到unsorted bin

与unsorted bin有关的宏

unsorted_chunks

所有分割块得到的剩余部分以及释放的块会被首先放到unsorted bin中。在malloc给了它们一次被使用的机会后，它们将会被放到一般的bins中。因此基本上unsorted bin扮演着一个队列的角色，堆块在被分割或者被释放时会放入unsorted bin；在malloc时又会被使用或者被放到正常的bins中_（后一种情况大概指的是大小不符合条件）_ 位于unsorted bin中的堆块的NON_MAIN_ARENA标志位从来不会被置位，因此在比较arena的大小时，它不会被包含在内。

1
#define unsorted_chunks(M)          (bin_at (M, 1))

解释，通过计算这个宏，我们会发现我们实际上找到的是bins数组中索引为0的项。但我们前面已经说过索引为0的bin不存在。这里的一点不一致性实际是因为bins只有127项，上面说的不存在的bin压根没有被包含在数组中。

与top有关的宏

initial_top

最上面的那个空闲块（位于可访问的内存的尽头，即top）是被特殊对待的。它从来不被任何bin包含在内，只有当没有其他空闲块可用时，它才会派上用场。同时当top非常大时会被归还给操作系统（见M_TRIM_THRESHOLD）。 Because top initially points to its own bin with initial zero size, thus forcing extension on the first malloc request, we avoid having any special code in malloc to check whether it even exists yet. But we still need to do so when getting memory from system, so we make initial_top treat the bin as a legal but unusable chunk during the interval between initialization and the first call to sysmalloc. (This is somewhat delicate, since it relies on the 2 preceding words to be zero during this interval as well.)

1
2
/* Conveniently, the unsorted bin can be used as dummy top on first call */
#define initial_top(M)              (unsorted_chunks (M))

在第一次调用sysmalloc时，unsorted bin可以作为一个伪top chunk使用。

与binmap有关的宏

源代码中的注释

为了补偿由于bins的巨大数目（128个）所产生的时间开销，我们使用一种一级索引结构来进行对bin之间的搜索。这种结构被称为binmap，它是一种记录bins中的bin是否为空的位向量。如此一来，我们便可以在遍历bin时跳过空bin。当一个bin变成空bin时，binmap并不会立刻清空。当我们下一次调用malloc，对bin遍历时才会清空那些被注意到为空的bin所对应的位。

BINMAPSIZE有关
1
2
3
4
/* Conservatively use 32 bits per map word, even if on 64bit system */
#define BINMAPSHIFT      5
#define BITSPERMAP       (1U << BINMAPSHIFT)
#define BINMAPSIZE       (NBINS / BITSPERMAP)

解释：其实binmap是由一系列的特定类型数据拼起来的，每个map中对应32个bin，总共需要\(128 / 32 = 4\)个map。也就是说对应着内存中的128个二进制位，每个位对应一个bin。

idx2block
1
#define idx2block(i)     ((i) >> BINMAPSHIFT)

解释：相当于整形除法，通过一个bin的索引来找到这个bin在binmap中的哪个map上

idx2bit
1
#define idx2bit(i)       ((1U << ((i) & ((1U << BINMAPSHIFT) - 1))))

解释：取第i位为1，其余位都为0的掩码。用于从已经获取到的map中提取出相应位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
(
  (1U << 
   (
     (i) & 
     (
       (1U << BINMAPSHIFT) - 1
       // 获得一个掩码0x11111
     )
     // 进行与运算，只取i的后5位，相当于进行了一次验证，保证i的范围为0到31
   )
  )
  // 假设i是7，那么进行运算：
  // 1 << (0b111 & 0b11111) = 1 << 0b111 = 0b10000000
)
mark_bin
1
#define mark_bin(m, i)    ((m)->binmap[idx2block (i)] = idx2bit (i))

解释：利用掩码操作将binmap的对应map的对应位使用或置为1

unmark_bin
1
#define unmark_bin(m, i)  ((m)->binmap[idx2block (i)] &= ~(idx2bit (i)))

解释：同上，但使用与结合掩码按位取反置为0

get_binmap
1
#define get_binmap(m, i)  ((m)->binmap[idx2block (i)] & idx2bit (i))

解释：获取i对应的bin记录在binmap中的状态，依然是类似的位操作

与tcache有关的宏

glibc/malloc/malloc.c

TCACHE_MAX_BINS
1
2
3
4
#if USE_TCACHE
/* 我们想要64个tcache bin。但我们可以使用tunables的技术来改变这个值
 * tunables是一种glibc使用的可以通过设置环境变量来改变代码行为的技术 */
# define TCACHE_MAX_BINS                64

解释：tcache bin的默认个数

xsize2tidx
1
2
3
4
5
6
7
8
# define csize2tidx(x) 
(
    ((x) - MINSIZE + MALLOC_ALIGNMENT - 1)
    / MALLOC_ALIGNMENT
)
// 当x是chunksize()的返回值时使用这个宏（因为x一定是对齐的）
# define usize2tidx(x) csize2tidx (request2size (x))
// 当x是用户提供的值时使用这个宏（x不一定对齐）

解释：该宏用以通过给定的大小计算相应块所在的bin。下面的表格显示了tcache bins中每个bin中chunk的大小范围（注：大小从0开始是因为这个大小是用户申请的大小）

1
2
3
4
5
6
7
8
/* With rounding and alignment, the bins are...
   idx 0   bytes 0..24 (64-bit) or 0..12 (32-bit)
   idx 1   bytes 25..40 or 13..20
   idx 2   bytes 41..56 or 21..28
   etc.  */

/* This is another arbitrary limit, which tunables can change.  Each
   tcache bin will hold at most this number of chunks.  */

如果你足够细心，按照上面的宏进行了计算，你会发现一种严重的不一致现象。如用户申请了24个字节的chunk，那么对齐后size域应当是0x30。使用csize2tidx宏计算时，我们得到\(idx = (0x30 - 17) / 16 = 1.938 = 1\) （强制类型转换舍去小数部分）。这显然是不正确的，而出现这个结果的源头是malloc分配堆块时采用的一种被称为“堆块复用”的策略。 我们知道，当当前堆块不空闲时，与其相邻的下一个堆块的prev_size域是没有意义的，因此这8个字节完全可以被用来当作有效载荷。这一做法是稳定有效的，因为下一个堆块的prev_size域被使用，与当前堆块非空闲这两个事实是相互佐证的，因此我们可以放心使用。（注意当前堆块的size域没有算进额外的8的字节）。因此64位下对一个chunksize为a的块，其总的可用空间为\(a - 16 + 8 = a - 8\)个字节。 现在回到之前的问题，对于一个用户申请为24个字节的chunk，其size域实际上是0x20。因此正确的计算方法是\(idx = (0x20 - 17) / 16 = 15 / 16 = 0\)，完美吻合。同样的，对于一个申请为56个字节的chunk，其size域实际上是0x40，idx为\(idx = (0x40 - 17) / 16 = 2.938 = 2\)。

tidx2usize
1
2
/* 本宏仅仅被用来初始化tunable对象（在一个malloc_par的初始化中）和下面的这个宏 */
# define tidx2usize(idx)        (((size_t) idx) * MALLOC_ALIGNMENT + MINSIZE - SIZE_SZ)

解释：idx是bin的索引，最终得到的是位于此处的bin中最大的chunk大小。

MAX_TCACHE_SIZE
1
# define MAX_TCACHE_SIZE        tidx2usize (TCACHE_MAX_BINS-1)

解释：得到tcache的最后一个bins中最大chunk的大小，也就是整个tcache中最大chunk的大小。这个值仅仅被使用了一次。

TCACHE_FILL_COUNT
1
# define TCACHE_FILL_COUNT 7

解释：是tcache中每个bin的最大chunk个数

与arena有关的宏

arena_get
1
2
3
4
5
6
7
8
9
10
11
/* arena_get()用于获取一个arena并锁上相应的互斥锁。
 * 首先，尝试本线程上一次成功加锁的arena（该情况比较常见，为了速度，我们使用宏来处理）
 * 如果尝试失败，那么遍历由arena组成的循环链表，如果没有合适的arena，那就创建一个新的
 * 在后一种情况中，size仅仅起到提醒新arena中需要立即使用到的空间的大小的作用 */

#define arena_get(ptr, size) do { \
      ptr = thread_arena;
      // 获取上一次操作过的arena                                                      
      arena_lock (ptr, size);     
      // 检查arena，合适则加锁，否则寻找一个新的arena                                                 
  } while (0)
arena_lock
1
2
3
4
5
6
7
8
#define arena_lock(ptr, size) do                                          \
      if (ptr)                                                                      
        __libc_lock_lock (ptr->mutex);     
        // 若ptr有效。则arena有效，加锁即可                                         
      else                                                                      
        ptr = arena_get2 ((size), NULL);
        // 否则就另寻新arena                                      
  } while (0)

解释：这两个宏牵扯到的东西有亿点多，后面会加以解释。 令：do {...} while(0)这种写法很奇怪，但其实这是一种把包含多语句的宏以函数形式使用的trick。注意while(0)后边没有分号，这意味着我们可以放心的在使用宏时添加分号以符合我们的直觉，而不必担心宏展开后分号重复。

heap_for_ptr
1
2
#define heap_for_ptr(ptr) \
  ((heap_info *) ((unsigned long) (ptr) & ~(HEAP_MAX_SIZE - 1)))

由于heap（非main_arena）的起始地址是以HEAP_MAX_SIZE对齐的, 而且heap的最大大小也是HEAP_MAX_SIZE, 因此对heap中任何一个地址作此运算均可得到存储在heap首部的heap info结构的地址。

arena_for_chunk
1
2
#define arena_for_chunk(ptr) \
  (chunk_main_arena (ptr) ? &main_arena : heap_for_ptr (ptr)->ar_ptr)
delete_heap
1
2
3
4
5
6
#define delete_heap(heap) \
  do {                        \
      if ((char *) (heap) + HEAP_MAX_SIZE == aligned_heap_area)          \
        aligned_heap_area = NULL;                \
      __munmap ((char *) (heap), HEAP_MAX_SIZE);            \
    } while (0)

删除一块堆区（非main_arena，因此它是通过mmap函数分配的）

常用typedef

1
2
3
4
typedef struct malloc_chunk *mfastbinptr;
typedef struct malloc_chunk* mchunkptr;
typedef struct malloc_chunk *mbinptr;
typedef struct malloc_state *mstate;

常用函数之间的关系

在glibc中的malloc.c的最后，程序定义了一系列别名，将这些列举出来将会有利于我们的分析：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
weak_alias (__malloc_info, malloc_info)

strong_alias (__libc_calloc, __calloc) weak_alias (__libc_calloc, calloc)
strong_alias (__libc_free, __free) strong_alias (__libc_free, free)
strong_alias (__libc_malloc, __malloc) strong_alias (__libc_malloc, malloc)
strong_alias (__libc_memalign, __memalign)
weak_alias (__libc_memalign, memalign)
strong_alias (__libc_realloc, __realloc) strong_alias (__libc_realloc, realloc)
strong_alias (__libc_valloc, __valloc) weak_alias (__libc_valloc, valloc)
strong_alias (__libc_pvalloc, __pvalloc) weak_alias (__libc_pvalloc, pvalloc)
strong_alias (__libc_mallinfo, __mallinfo)
weak_alias (__libc_mallinfo, mallinfo)
strong_alias (__libc_mallopt, __mallopt) weak_alias (__libc_mallopt, mallopt)

weak_alias (__malloc_stats, malloc_stats)
weak_alias (__malloc_usable_size, malloc_usable_size)
weak_alias (__malloc_trim, malloc_trim)

必要的结构体

malloc_state

glibc/malloc/malloc.c

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
struct malloc_state
{
  /* Serialize access.  */
  __libc_lock_define (, mutex);
  // 加锁，这里应该是定义了一个int类型的变量，该变量为arena的串行访问提供支持
  // 不确定，源代码在
  // https://sites.uclouvain.be/SystInfo/usr/include/bits/libc-lock.h.html

  /* Flags (以前位于global_max_fast变量中).  */
  int flags;

  /*当fastbin中包含最近插入的空闲块时置位*/
  /* 这本应是一个布尔值，但并非所有的平台都支持对布尔值的原子操作（保证线程安全） */
  int have_fastchunks;

  /* 这是一个链表数组，数组中的每一个成员都指向一个链表的首节点 
  根据我们上面的计算，该数组一般有10个元素*/
  mfastbinptr fastbinsY[NFASTBINS];

  /* 指向top chunk */
  mchunkptr top;

  /* 对最近分割的小块的备忘录 */
  mchunkptr last_remainder;

  /* 上面提到过的一般的bins */
  /* 你可能会很疑惑，这里为什么分配的内存数是NBINS的二倍，但你仔细看这个定义：
   * malloc_chunk *bins[NBINS * 2 - 2];
   * 你会发现，这是一个指针数组，数组中的每一项都是一个指针
   * 其中每一个指针都可以指向一个malloc_chunk结构
   * 还记得我们前面提到过的节省空间的小trick吗？这便是其中之一
   * 答案在宏bin_at中 */
   mchunkptr bins[NBINS * 2 - 2];

  /* 定义用于加速遍历bins的binmap */
  unsigned int binmap[BINMAPSIZE];

  /* 链表 */
  struct malloc_state *next;

  /* 空闲arena的链表，使用arena.c的free_list_lock变量来保证对该域的串行访问 */
  /* 串行即线程按顺序依次访问 */
  struct malloc_state *next_free;

  /* 使用该arena的线程数，当该arena位于空闲链表中时置为0，相当于一个引用计数器
     使用arena.c的free_list_lock函数来保证对该域的串行访问.  */
  /* INTERNAL_SIZE_T一般是size_t，可自定义，详情在
      glibc/malloc/malloc-internal.h*/
  INTERNAL_SIZE_T attached_threads;

  /* 系统为该arena分配的内存大小 */
  INTERNAL_SIZE_T system_mem;
  INTERNAL_SIZE_T max_system_mem;
};

malloc_state结构体的实例被用来指示一个arena，即内存分配区，该结构体中包含了malloc工作所需要的大部分信息。

malloc_par

该结构体的全称猜测是malloc_parameters，即与malloc有关的参数，这也是mallopt函数主要影响的结构体（这两个函数我们都会有详细解释）

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
struct malloc_par
{
  /* Tunable parameters */
  // 我们可以使用环境变量来影响这些变量
  unsigned long trim_threshold;
  /* 直译为修剪的门槛，即top chunk的最大值，top chunk的大小大于这个值会被修剪。这一过程
   * 由malloc_trim函数在调用free函数时完成（注意并非所有情况都如此，下面将会提到）这一
   * 修剪的特性主要在长生命周期的程序中有用，因为在某些操作系统中，使用sbrk来缩小堆是一件
   * 很耗费时间的事。因此这个值要足够大，这样你才能获得更好的性能。
   * 
   * trim和mmap是两种可以向操作系统归还存储空间的方法，因此对于长生命周期的程序来说，恰当的
   * 权衡trim_threshold和下面将提到的mmap_threshold的值有助于将一个长期使用的程序的资源
   * 占用最小化。
   * 
   * （...这里有一些关于性能的建议，不再翻译）
   * 
   * 实际上，trim_threshold仅仅是一种保护手段，用于防止程序占用大量不需要空间。因为对sbrk，
   * mmap，munmap的频繁调用会导致程序的性能下降。
   * 
   * 对trim的设置会受关于fastbin的设置（MXFAST）的影响：除非我们将TRIM_FASTBINS设置为1，
   * 否则释放任何大小小于MXFAST的块都不会造成trim。这有助于提升一些大量使用小堆块的程序的性能。
   */


  INTERNAL_SIZE_T top_pad;
  // 是调用sbrk函数时在原有请求大小上添加的一个值，是一个填充

  INTERNAL_SIZE_T mmap_threshold;
  /* 是mmap的门槛，注意门槛的意义是使用mmap进行分配的块至少有这么大，但并不代表大小大于该值
   * 的块都要使用mmap。实际上，如果有足够大的freed space，那么我们不会使用mmap。
   * 使用mmap来分配较大的块有一种隔离的效果，即mmap分配的块不会被直接重复利用。
   * 这样做有下面三点好处：
   * 
   * 1. 使用mmap分配的空间总是能被相互独立的归还给操作系统，这样可以保证一个长寿命周期的程序
   *    系统层面的内存需求尽可能小。
   * 2. 正常分配的块空闲后有可能会“锁住”，即被两个使用中的块夹在中间，导致其无法通过
   *    malloc_trim函数归还给操作系统。而使用mmap分配的空间就不会出现这种情况
   * 3. 对于一些内存地址空间不连续的操作系统，mmap可以申请到sbrk申请不到的空间。
   * 
   * 相应的，它也有下面三个缺点：
   * 
   * 1. 一般分配方式的优先也同时是mmap的弱点，使用mmap获取的块不能被合并，变更大小，也不能
   *    重复利用
   * 2. mmap所需要的页对齐可能会造成更多的浪费
   * 3. 不同平台上mmap的实现可能会导致malloc的性能再不同的平台上有差距，并且可能造成某些限制
   *    mmap的速度一般比一般的分配方式更慢。
   * 该值的默认值是一个源于经验的值，它可以再大多数系统上很好的工作。
   * 这里还有一些细节，即该值可以是动态的。在这里暂不赘述。
   */

  INTERNAL_SIZE_T arena_test;
  INTERNAL_SIZE_T arena_max;

  /* mmap支持 */
  int n_mmaps;
  int n_mmaps_max;
  // 指定了同一时间最大使用mmap的请求数（即同一时间有多少个mmap块存在）
  int max_n_mmaps;
  /* 在用户显式的设置 trim_threshold，top_pad，mmap_threshold，max_n_mmaps
  这几个变量之前，它们的值是动态的。对这些变量的显式设置会导致no_dyn_threshold被置位*/
  int no_dyn_threshold;

  /* Statistics */
  INTERNAL_SIZE_T mmapped_mem;
  INTERNAL_SIZE_T max_mmapped_mem;

  /* 由MORECORE或者sbrk的到的首个地址 */
  char *sbrk_base;

#if USE_TCACHE
  size_t tcache_bins;
   /* 决定tcache bin的个数  */
  size_t tcache_max_bytes;
  /* 决定每个bin中chunk的最大个数  */
  size_t tcache_count;

  size_t tcache_unsorted_limit;
  /* 这个值与malloc的具体实现有关，我们后面会提到  */
#endif
};

tcache_entry

1
2
3
4
5
6
7
8
9
/* 我们将这个结构放在per-thread cache的用户数据区域 */
typedef struct tcache_entry
{
  struct tcache_entry *next;
  // bin的entry（即链表头）
  struct tcache_perthread_struct *key;
  // 这个元素被用来检测double free漏洞
} tcache_entry;

tcache_perthread_struct

1
2
3
4
5
6
7
8
9
10
11
/* 这样的结构在每个线程的arena中都有一个，它包含着每个线程都需要的缓存内容
 * （也就是"tcache_perthread_struct"名字的含义）
 * 在这里，压缩存储空间变得不是那么必要。注意COUNTS和ENTRIES的数量都是有富余的
 * 由于性能上的原因，我们不会每次都数数bin有多少个（也就是一次分配到位）*/
typedef struct tcache_perthread_struct
{
  char counts[TCACHE_MAX_BINS];
  // 每个bin中的块个数
  tcache_entry *entries[TCACHE_MAX_BINS];
  // 每个bin的entry
} tcache_perthread_struct;

heap_info

1
2
3
4
5
6
7
8
9
10
typedef struct _heap_info
{
  mstate ar_ptr; /* 指向此堆的arena结构体 */
  struct _heap_info *prev; /* 将多个heap作为链表管理 */
  size_t size;   /* 当前堆的大小 */
  size_t mprotect_size; /* 已经被mprotect置为可读写的区域的大小（初始和size相同）  */
  /* 确保接下来在堆区放置的数据是正确对齐了的，即 sizeof (heap_info) + 2 * SIZE_SZ 是MALLOC_ALIGNMENT
   * 的倍数 */
  char pad[-6 * SIZE_SZ & MALLOC_ALIGN_MASK];
} heap_info;

全局变量

__malloc_hook

1
2
void *weak_variable (*__malloc_hook)
(size_t __size, const void *) = malloc_hook_ini;

解释：这个值存放在data section，泄露libc基地址后可以通过任意地址写漏洞修改改值，从而造成任意地址执行。

__malloc_initialized

glibc/malloc/arena.c

1
2
/* Already initialized? */
int __malloc_initialized = -1;

解释：指示malloc是否已经被初始化 glibc/include/malloc.h

1
#define __malloc_initialized __libc_malloc_initialized

解释：glic中的一个别名

main_arena

1
2
3
4
5
6
7
static struct malloc_state main_arena =
{
  .mutex = _LIBC_LOCK_INITIALIZER,
  // 初始化锁，为0
  .next = &main_arena,
  .attached_threads = 1
};

main_arena 是一个malloc_state实例。即主线程使用的arena。

thread_arena

1
static __thread mstate thread_arena attribute_tls_model_ie;

根据别处的注释，大致可以推断该值总是最近一次加互斥锁的arena的值（不确定）。即线程最近操作过的arena。这里不敢深挖，水太深=-=，还涉及到tls的几种模式

Arena free list有关

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/* arena的空闲链表。free_list_lock同步化了下面对free_list变量，以及malloc_state
 * 结构中next_free和attached_threads两个成员的访问。同时这是线程访问这些数据唯一需要
 * 获取的锁。*/

__libc_lock_define_initialized (static, free_list_lock);
// 定义了一个针对free_list指针的互斥锁并初始化（为0）
static size_t narenas = 1;
// arena的个数，即free_list中节点的个数
static mstate free_list;
// 存放已经被释放的arena

/* list_lock prevents concurrent writes to the next member of struct
   malloc_state objects.

   Read access to the next member is supposed to synchronize with the
   atomic_write_barrier and the write to the next member in
   _int_new_arena.  This suffers from data races; see the FIXME
   comments in _int_new_arena and reused_arena.

   list_lock also prevents concurrent forks.  At the time list_lock is
   acquired, no arena lock must have been acquired, but it is
   permitted to acquire arena locks subsequently, while list_lock is
   acquired.  */
__libc_lock_define_initialized (static, list_lock);

解释：这里我们遇到了一个新名词：synchronizes access，即同步访问。上面我们又提到过Serialize access，即串行访问。这两个名词有什么区别呢？ 串行访问指任务的执行方式，即的是同一时间只能有一个线程对资源进行访问，也即一个任务完成后另一个线程才能对资源进行访问。 同步访问指能否开启新的线程，即当一个线程在访问资源时，该线程必须阻塞以等待资源访问完成才能够进行其他操作。 这里注释的作者应该表达的是同一个意思。

mp_

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
/* 这是malloc_par结构体的唯一实例  */

static struct malloc_par mp_ =
{
  .top_pad = DEFAULT_TOP_PAD,
  // 该值默认为0
  .n_mmaps_max = DEFAULT_MMAP_MAX,
  // 该值默认为65536，即同时最多有65536个mmap的块
  .mmap_threshold = DEFAULT_MMAP_THRESHOLD,
  // 默认为128 * 1024，可能动态变化
  .trim_threshold = DEFAULT_TRIM_THRESHOLD,
  // 默认的top chunk最大大小
#define NARENAS_FROM_NCORES(n) ((n) * (sizeof (long) == 4 ? 2 : 8))
  // 确定最大的arena个数，详细解释在这里：https://zhuanlan.zhihu.com/p/24909781
  .arena_test = NARENAS_FROM_NCORES (1)
  // arena有8个
#if USE_TCACHE
  ,
  .tcache_count = TCACHE_FILL_COUNT,
  // tcache中每个bin中的最大chunk数，默认为7
  .tcache_bins = TCACHE_MAX_BINS,
  // tcache中bin的个数，默认为64
  .tcache_max_bytes = tidx2usize (TCACHE_MAX_BINS-1),
  // tcache中最大chunk的大小，具体计算前面有详解
  .tcache_unsorted_limit = 0 /* No limit.  */
  // 以后再说。。
#endif
};

与tcache有关

1
2
static __thread bool tcache_shutting_down = false;
static __thread tcache_perthread_struct *tcache = NULL;

解释：__thread是实现thread local storage（线程局部存储）的一种方法。被该关键字修饰的变量在每一个线程中都有一个实例。也就很好的解决了线程冲突的问题。 tcache_shutting_down在函数tcache_thread_shutdown被调用（从hook调用）时置为true。 tcache则指向一个tcache_perthread_struct实例，即存放tcache bins的counts和entries的地方

mallopt函数

该函数控制流相对简单，它是__libc_mallopt函数的一个别名，对该函数的分析有利于我们复习之前提到的宏。

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
int
__libc_mallopt (int param_number, int value)
{
  mstate av = &main_arena;
  int res = 1;

  if (__malloc_initialized < 0)
    ptmalloc_init ();
    // 我们将会在下面对malloc函数的分析中讲解这里的意思
    // 大致实现了检测当前arena是否被初始化，若没有，则初始化之

  __libc_lock_lock (av->mutex);
  // 加互斥锁，防竞态，保证对该变量的串行访问

  LIBC_PROBE (memory_mallopt, 2, param_number, value);
  // 不清楚是什么意思=-=

  /* 我们必须首先调用malloc_consolidate函数以保证fastbin为空
     (见宏set_max_fast处的说明).  */
  malloc_consolidate (av);
  // 我们将会在介绍malloc函数之后介绍该函数

  switch (param_number)
    {
    case M_MXFAST:
      if (value >= 0 && value <= MAX_FAST_SIZE)
        {
          LIBC_PROBE (memory_mallopt_mxfast, 2, value, get_max_fast ());
          set_max_fast (value);
        }
      else
        res = 0;
      break;
      // 见辅助信息 -> 常用宏 -> 与fastbin有关的宏 -> fastbin的最大大小
    // 下面的do_set系列函数的源码我们不再赘述，它们的功能可以用一句话来概括：
    // 将mp_结构体的相应项设置为指定的值
    case M_TRIM_THRESHOLD:
      do_set_trim_threshold (value);
      break;
      // 设置top块被修剪的临界值

    case M_TOP_PAD:
      do_set_top_pad (value);
      break;
      // 设置sbrk申请空间时的填充（额外空间）

    case M_MMAP_THRESHOLD:
      res = do_set_mmap_threshold (value);
      break;

    case M_MMAP_MAX:
      do_set_mmaps_max (value);
      break;
      // 注意上面两个不仅设置了相应的值，还将no_dyn_threshold置位

    case M_CHECK_ACTION:
      do_set_mallopt_check (value);
      break;
      // 什么也没有做，可能是用来检查mallopt函数本身的

    case M_PERTURB:
      do_set_perturb_byte (value);
      break;
      // 是关于程序测试的。作用不详

    case M_ARENA_TEST:
      if (value > 0)
        do_set_arena_test (value);
      break;
      // 作用不详

    case M_ARENA_MAX:
      if (value > 0)
        do_set_arena_max (value);
      break;
      // 作用不详
    }
  __libc_lock_unlock (av->mutex);
  // 解互斥锁
  return res;
}
libc_hidden_def (__libc_mallopt)

malloc函数

辅助函数

checked_request2size

1
2
3
4
5
6
7
8
9
/* 检查请求的大小req在pading之后是否还能保证小于PTRDIFF_T，若不满足则返回false，若满足则返回padding后的值 */
static inline bool
checked_request2size (size_t req, size_t *sz) __nonnull (1)
{
  if (__glibc_unlikely (req > PTRDIFF_MAX))
    return false;
  *sz = request2size (req);
  return true;
}

malloc_init_state

glibc/malloc/malloc.c

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
/*
  初始化一个 malloc_state 结构体.
  它在ptmalloc_init ()或_int_new_arena ()函数中被调用，协助创建一个新的arena
 */
// av是一个malloc_state类型结构体
static void
malloc_init_state (mstate av)
{
  int i;
  mbinptr bin;
  /* 用于指示一个bin */

  /* 为一般的bins建立循环链接结构 */
  for (i = 1; i < NBINS; ++i)
  {
      bin = bin_at (av, i);
      bin->fd = bin->bk = bin;  // 双向循环链接
  }
  // 注意这时bins中的指针还没有指向真正有效的地址，现在它们指向data段的bin本身的地址

#if MORECORE_CONTIGUOUS
  if (av != &main_arena)
#endif
  set_noncontiguous (av);
  // 进行关于MORECORE返回的内存的连续性的设置，与性能有关
  // 影响malloc_state的flags域，确切来说，是第二位的NONCONTIGUOUS_BIT
  if (av == &main_arena)
    set_max_fast (DEFAULT_MXFAST);
  // 将fastbin最大大小设置为默认值
  atomic_store_relaxed (&av->have_fastchunks, false);
  // 防止多线程竞争，结果是将have_fastchunks置为0
  // have_fastchunks当fastbin中包含最近插入的空闲块时置位

  av->top = initial_top (av);
  // 宏展开的结果是bin_at (av, 1)，top初始位于unsorted bins的开头
}

ptmalloc_init

glibc/malloc/arena.c

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
static void
ptmalloc_init (void)
{
  if (__malloc_initialized >= 0)
    return;
  /* 在函数的末尾，我们将该变量置为1。代表已经初始化过了 */

  __malloc_initialized = 0;

#ifdef SHARED
  /* In case this libc copy is in a non-default namespace, never use brk.
     Likewise if dlopened from statically linked program.  */
  Dl_info di;
  struct link_map *l;

  if (_dl_open_hook != NULL
       (_dl_addr (ptmalloc_init, &di, &l, NULL) != 0
          && l->l_ns != LM_ID_BASE))
    __morecore = __failing_morecore;
#endif
// 我们不关心这一部分

  thread_arena = &main_arena; 
  /* 即将被初始化的arena，这一部分很有意思，首先我们需要注意：由于__malloc_initialized是一个共享的全集变量。
   * 在一个进程的生命周期中，ptmalloc_init一般只会调用一次（从它的名字便可以看出，该函数是用来对ptmalloc进行
   * 一个overall的初始化的）。因此进程保有的第一个arena便是这里的main_arena，这个arena是特别的，因为它是
   * 唯一一个把信息保存在data段的arena，同时也是唯一一个使用MORECORE（__brk）来向操作系统申请空间的arena。
   * 相关的调用链：
   * __libc_malloc->tcache_init->_int_malloc->sysmalloc->MORECORE->__brk
   *
   * 在后面的代码中（确切来说，是new_heap这个函数）我们会发现，其他线程的arena所占据的空间是由mmap分配的
   * 并且arena相关的信息就存放在mmap出的区域的头部（包括表示堆区信息的结构体heap_info与记录chunks信息的
   * malloc_state）
   * 相关的调用链：
   * __libc_malloc->tcache_init->arena_get->arena_get2->_int_new_arena->new_heap->mmap
   */

  malloc_init_state (&main_arena);
  /* 初始化arena */

#if HAVE_TUNABLES
  TUNABLE_GET (check, int32_t, TUNABLE_CALLBACK (set_mallopt_check));
  TUNABLE_GET (top_pad, size_t, TUNABLE_CALLBACK (set_top_pad));
  TUNABLE_GET (perturb, int32_t, TUNABLE_CALLBACK (set_perturb_byte));
  TUNABLE_GET (mmap_threshold, size_t, TUNABLE_CALLBACK (set_mmap_threshold));
  TUNABLE_GET (trim_threshold, size_t, TUNABLE_CALLBACK (set_trim_threshold));
  TUNABLE_GET (mmap_max, int32_t, TUNABLE_CALLBACK (set_mmaps_max));
  TUNABLE_GET (arena_max, size_t, TUNABLE_CALLBACK (set_arena_max));
  TUNABLE_GET (arena_test, size_t, TUNABLE_CALLBACK (set_arena_test));
#if USE_TCACHE
  TUNABLE_GET (tcache_max, size_t, TUNABLE_CALLBACK (set_tcache_max));
  TUNABLE_GET (tcache_count, size_t, TUNABLE_CALLBACK (set_tcache_count));
  TUNABLE_GET (tcache_unsorted_limit, size_t,
               TUNABLE_CALLBACK (set_tcache_unsorted_limit));
#endif
// 这里使用了一种被称为tunables的技术，glibc使用这种技术来保证开发者可以按照他们的需求来修改（alter）动态链接库。
// 这意味着我们可以通过设置环境变量来影响malloc的行为。
// 详情参见 https://www.gnu.org/software/libc/manual/html_node/Tunables.html
// 实际上下面的几个判断语句就是对这一功能的部分实现

#else
  const char *s = NULL;
  if (__glibc_likely (_environ != NULL))
    {
      char **runp = _environ;
      char *envline;

      while (__builtin_expect ((envline = next_env_entry (&runp)) != NULL,
                               0))
        {
          size_t len = strcspn (envline, "=");

          if (envline[len] != '=')
            /* This is a "MALLOC_" variable at the end of the string
               without a '=' character.  Ignore it since otherwise we
               will access invalid memory below.  */
            continue;

          switch (len)
            {
            case 6:
              if (memcmp (envline, "CHECK_", 6) == 0)
                s = &envline[7];
              break;
              // 添加对调试的支持
            case 8:
              if (!__builtin_expect (__libc_enable_secure, 0))
                {
                  if (memcmp (envline, "TOP_PAD_", 8) == 0)
                    __libc_mallopt (M_TOP_PAD, atoi (&envline[9]));
                  else if (memcmp (envline, "PERTURB_", 8) == 0)
                    __libc_mallopt (M_PERTURB, atoi (&envline[9]));
                }
              break;
            case 9:
              if (!__builtin_expect (__libc_enable_secure, 0))
                {
                  if (memcmp (envline, "MMAP_MAX_", 9) == 0)
                    __libc_mallopt (M_MMAP_MAX, atoi (&envline[10]));
                  else if (memcmp (envline, "ARENA_MAX", 9) == 0)
                    __libc_mallopt (M_ARENA_MAX, atoi (&envline[10]));
                }
              break;
            case 10:
              if (!__builtin_expect (__libc_enable_secure, 0))
                {
                  if (memcmp (envline, "ARENA_TEST", 10) == 0)
                    __libc_mallopt (M_ARENA_TEST, atoi (&envline[11]));
                }
              break;
            case 15:
              if (!__builtin_expect (__libc_enable_secure, 0))
                {
                  if (memcmp (envline, "TRIM_THRESHOLD_", 15) == 0)
                    __libc_mallopt (M_TRIM_THRESHOLD, atoi (&envline[16]));
                  else if (memcmp (envline, "MMAP_THRESHOLD_", 15) == 0)
                    __libc_mallopt (M_MMAP_THRESHOLD, atoi (&envline[16]));
                }
              break;
            default:
              break;
            }
        }
    }
    // 上面的一坨代码都是为了这个页面里所描述的功能，不再赘述，详情参见mallopt的分析
    // https://www.gnu.org/software/libc/manual/html_node/Memory-Allocation-Tunables.html#Memory-Allocation-Tunables 
    // 有意思的是case的分类依据居然是变量名的长度=-=

  if (s && s[0] != '\0' && s[0] != '0')
    __malloc_check_init ();
    // 回顾上面的代码，我们通过CHECK_来声明我们要调试libc，该函数用于将各个钩子函数设置为
    // 相应的用于检查的函数，从而开启对debug的支持，其源代码如下：
    /* Activate a standard set of debugging hooks.
    void
    __malloc_check_init (void)
    {
      using_malloc_checking = 1;
      __malloc_hook = malloc_check;
      __free_hook = free_check;
      __realloc_hook = realloc_check;
      __memalign_hook = memalign_check;
    }
    */
    // 这是我们第一次看到hook函数，即钩子函数，该函数可以捕获对某一函数的调用，将传递给该函数
    // 的信息进行加工或者提取再传入。
#endif

#if HAVE_MALLOC_INIT_HOOK
  void (*hook) (void) = atomic_forced_read (__malloc_initialize_hook);
  if (hook != NULL)
    (*hook)();
#endif
// 此处是为了向后兼容，此处不讨论其用途
  __malloc_initialized = 1;
  // 初始化完毕
}

malloc_hook_ini

glibc/malloc/hooks.c

1
2
3
4
5
6
7
8
9
10
static void *
malloc_hook_ini (size_t sz, const void *caller)
{
  __malloc_hook = NULL;
  // 该函数仅调用一遍，判断部分在__libc_malloc中
  ptmalloc_init ();
  // 初始化
  return __libc_malloc (sz);
  // 初始化完毕，再来一次，这次玩真的了
}

detach_arena

1
2
3
4
5
6
7
8
9
10
11
/* 当replaced_arena不为空时，将其从当前线程脱离。该函数只能在free_list_lock被获取的情况下掉用 */
static void
detach_arena (mstate replaced_arena)
{
  if (replaced_arena != NULL)
    {
      assert (replaced_arena->attached_threads > 0);
      --replaced_arena->attached_threads;
      // 引用计数减一
    }
}

get_free_list

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
/* 从free_list中摘出一个arena并附加到x  */
static mstate
get_free_list (void)
{
  mstate replaced_arena = thread_arena;
  // 当前线程的arena
  mstate result = free_list;
  // free_list是arena list的头指针
  if (result != NULL)
    {
      __libc_lock_lock (free_list_lock);
      result = free_list;
      // 这里在对free_list加锁之后重新获取了一遍free_list，防止竞争引起的更改
      if (result != NULL)
        {
          free_list = result->next_free;

          /* 保证获取到的arena没有附加到任何线程上 */
          assert (result->attached_threads == 0);
          result->attached_threads = 1;

          detach_arena (replaced_arena);
          // 当前线程有正在使用的arena时，将其从当前线程脱离
        }
      __libc_lock_unlock (free_list_lock);
      // 释放锁

      // 再次判断，防止竞态
      if (result != NULL)
        {
          LIBC_PROBE (memory_arena_reuse_free_list, 1, result);
          /* 查找这条语句的作者着实费了一番功夫，该语句与Linux上的一个被成为Systemtap的工具息息相关
           * 该语句可以视为开发者内嵌在glibc中的探针，我们可以通过systamtap这一工具来探测这些探针被
           * 触发时的参数等情况（这样的操作最初是为了让人们更加了解内核的运行机制）。详情参见
           * https://developers.redhat.com/blog/2014/10/02/understanding-malloc-behavior-using-systemtap-userspace-probes/
           * https://developers.redhat.com/blog/2015/01/06/malloc-systemtap-probes-an-example/
           */
          __libc_lock_lock (result->mutex);
          // 对该arena加锁
          thread_arena = result;
          // 附加到当前进程
        }
    }

  return result;
}

new_heap

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
static char *aligned_heap_area;
// 该变量与下面的函数息息相关，因此将其单列出来

/* 创建一块新的堆区，其大小在size参数的基础上与pagesize对齐 */

static heap_info *
new_heap (size_t size, size_t top_pad)
{
  size_t pagesize = GLRO (dl_pagesize);
  // 获取pagesize
  char *p1, *p2;
  unsigned long ul;
  heap_info *h;

  // HEAP_MIN_SIZE为堆的最小大小，默认为32 * 1024，在编译时确定
  if (size + top_pad < HEAP_MIN_SIZE)
    size = HEAP_MIN_SIZE;
  else if (size + top_pad <= HEAP_MAX_SIZE)
    size += top_pad;
  else if (size > HEAP_MAX_SIZE)
    return 0;
  else
    size = HEAP_MAX_SIZE;
  // 如果size未达到 HEAP_MAX_SIZE但size+toppad达到，size将会取HEAP_MAX_SIZE
  size = ALIGN_UP (size, pagesize);
  // 将size按pagesize向上对齐

  /* 我们需要一块和HEAP_MAX_SIZE对齐的堆区，因此首先要在内存中找到这样一个地址：
   * 1. 和HEAP_MAX_SIZE对齐
   * 2. 从该地址开始，有足够的空间放下我们的堆（在最坏的情况下，我们需要HEAP_MAX_SIZE这么大的空间
   * 为了确保这一点，开发者采取了一种类似于试水的措施：先分配HEAP_MAX_SIZE * 2大小的空间
   * 这样可以保证在前HEAP_MAX_SIZE大小的空间中一定有一个地址满足上述的条件。然后使用munmap函数将
   * 不需要的部分裁剪掉即可。
   */
  p2 = MAP_FAILED;
  if (aligned_heap_area)
    // 初始情况下aligned_heap_area为0，因此不会进入该块
    {
      /* 当aligned_heap_area不为0时，说明我们尝试分配过堆，而且aligned_heap_area必定是和HEAP_MAX_SIZE
       * 对齐的，该地址之后很有可能存在HEAP_MAX_SIZE大小的空闲空间。在这里我们进行尝试，实在是不行的话
       *（mmap失败）就重新进行复杂一点的过量分配再裁剪的操作。
       */

      p2 = (char *) MMAP (aligned_heap_area, HEAP_MAX_SIZE, PROT_NONE,
                          MAP_NORESERVE);
      aligned_heap_area = NULL;
      // aligned_heap_area的有效值用过一次就不能再用了
      if (p2 != MAP_FAILED && ((unsigned long) p2 & (HEAP_MAX_SIZE - 1)))
        {
          __munmap (p2, HEAP_MAX_SIZE);
          p2 = MAP_FAILED;
        }
    }
  if (p2 == MAP_FAILED)
    // 第一次调用new_heap时，由于上一个if块的处理逻辑，程序将执行该块
    {
      p1 = (char *) MMAP (0, HEAP_MAX_SIZE << 1, PROT_NONE, MAP_NORESERVE);
      // 申请最大堆大小两倍的内存页
      if (p1 != MAP_FAILED)
        {
          p2 = (char *) (((unsigned long) p1 + (HEAP_MAX_SIZE - 1))
                         & ~(HEAP_MAX_SIZE - 1));
          ul = p2 - p1;
          if (ul)
            __munmap (p1, ul);
          else
            aligned_heap_area = p2 + HEAP_MAX_SIZE;
          __munmap (p2 + HEAP_MAX_SIZE, HEAP_MAX_SIZE - ul);
        }
    /* 经过该if块中的操作后，内存中与之相关的一部分如图所示：
     * +-------------+-------+-------------+-------+
     * -------------                    -------
     * -------------                    -------
     * -------------                    -------
     * -------------                    -------
     * +-------------+-------+-------------+-------+
     * ^             ^                     ^
     * +--->  ul <---+                     
     * +             +                     +
     * p1            p2             p2 + HEAP_MAX_SIZE (aka.aligned_heap_area)
     * 阴影部分为被裁减掉的块，中间的空白部分是我们最终得到的内存区域
     */
      else
        {
          /* 由于上一次分配HEAP_MAX_SIZE二倍大小的内存失败了，我们来尝试一下只分配HEAP_MAX_SIZE大小的内存
           * （万一分配出来刚好就是对齐的就赚了）如果还是不行就return 0，表示失败
           */
          p2 = (char *) MMAP (0, HEAP_MAX_SIZE, PROT_NONE, MAP_NORESERVE);
          if (p2 == MAP_FAILED)
            return 0;

          if ((unsigned long) p2 & (HEAP_MAX_SIZE - 1))
            {
              __munmap (p2, HEAP_MAX_SIZE);
              return 0;
            }
        }
    }
  if (__mprotect (p2, size, PROT_READ  PROT_WRITE) != 0)
    // 修改分配到的堆区的权限
    // 这里需要注意：上面我们
    {
      __munmap (p2, HEAP_MAX_SIZE);
      return 0;
    }
  h = (heap_info *) p2;
  h->size = size;
  // 实际上h指向的总是一块大小为HEAP_MAX_SIZE的内存，只是结构体的size域说明了它的大小
  // 而且超出size之后的内存没有rw权限（由上面的mprotect决定
  h->mprotect_size = size;
  LIBC_PROBE (memory_heap_new, 2, h, h->size);
  return h;
}

_int_new_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
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
static mstate
_int_new_arena (size_t size)
{
  mstate a;
  heap_info *h;
  char *ptr;
  unsigned long misalign;

  h = new_heap (size + (sizeof (*h) + sizeof (*a) + MALLOC_ALIGNMENT),
                mp_.top_pad);
  /* 申请一个新的堆区 */

  if (!h)
    {
      /* 或许我们申请的大小有点过于大了（如比HEAP_MAX_SIZE还要大），因此我们只需尝试分配一个最小大小的arena，后续只需要通过
       * int_malloc()函数尝试使用mmap_chunk()来扩大heap的大小 */
      h = new_heap (sizeof (*h) + sizeof (*a) + MALLOC_ALIGNMENT, mp_.top_pad);
      if (!h)
        return 0;
    }
  a = h->ar_ptr = (mstate) (h + 1);
  malloc_init_state (a);
  // 初始化bins和top chunk，但并没有初始化fastbin中chunk的最大值
  a->attached_threads = 1;
  /*a->next = NULL;*/
  a->system_mem = a->max_system_mem = h->size;
  // 该arena中从系统分配到的内存大小

  /* 经过上述操作后，我们的arena的大致结构如下所示：
   *       +-----------+
   *                  
   *                  v
   *     +-++--+--+--+-+----------------------+-----
   *                                    
   *                                    
   *                                    
   *                                    
   *                                    
   *     ++-++-++-++-+++-----------+----------+-----
   *      ^  ^  ^  ^  ^            ^
   *                          
   *      +    +    +            +
   * ar_ptr   size pad       arena structure
   *         +     +           (malloc state)
   *        prev  mprotect_size
   */

  /* Set up the top chunk, with proper alignment. */
  ptr = (char *) (a + 1);
  // 此时ptr指向malloc state后的可用区域
  misalign = (unsigned long) chunk2mem (ptr) & MALLOC_ALIGN_MASK;
  if (misalign > 0)
    ptr += MALLOC_ALIGNMENT - misalign;
  // 将ptr指针与MALLOC_ALIGNMENT对齐，此时ptr应当指向unsortedbin，但这里首先将其作为top chunk使用
  top (a) = (mchunkptr) ptr; 
  set_head (top (a), (((char *) h + h->size) - ptr)  PREV_INUSE);
  // 设置top chunk的size为heap中ptr以后部分的size，并将其PREV_INUSE位置为1

  // 下面的工作可以分为两步
  // 1. 将本arena按照头插法插入到以main_arena为首的arena链表中
  // 2. 设置本线程的thread_arena
  LIBC_PROBE (memory_arena_new, 2, a, size);
  mstate replaced_arena = thread_arena;
  thread_arena = a;
  __libc_lock_init (a->mutex);

  __libc_lock_lock (list_lock);

  /* Add the new arena to the global list.  */
  a->next = main_arena.next;
  /* FIXME: The barrier is an attempt to synchronize with read access
     in reused_arena, which does not acquire list_lock while
     traversing the list.  */
  atomic_write_barrier ();
  /* 这是一个写屏障，展开后的形式是asm volatile ("" : : : "memory")
   * 作用是保证程序编译是屏障两侧操作的有序性，否则有可能出现main_arena.next先被赋值为a，
   * 但a的next域并未指向原main_arena.next的情况，导致另外一个线程的reuse_arena在遍历
   * 该循环链表时出现segmentation fault。*/
  main_arena.next = a;

  __libc_lock_unlock (list_lock);

  __libc_lock_lock (free_list_lock);
  detach_arena (replaced_arena);
  __libc_lock_unlock (free_list_lock);

  /* Lock this arena.  NB: Another thread may have been attached to
     this arena because the arena is now accessible from the
     main_arena.next list and could have been picked by reused_arena.
     This can only happen for the last arena created (before the arena
     limit is reached).  At this point, some arena has to be attached
     to two threads.  We could acquire the arena lock before list_lock
     to make it less likely that reused_arena picks this new arena,
     but this could result in a deadlock with
     __malloc_fork_lock_parent.  */

  __libc_lock_lock (a->mutex);

  return a;
}

reuse_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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/* 获取一个可以被重复利用用来分配内存的arena并将其上锁，避免分配到avoid_arena，因为我们
 * 尝试过在那里分配空间而且失败了 */
static mstate
reused_arena (mstate avoid_arena)
{
  mstate result;
  /* FIXME: Access to next_to_use suffers from data races.  */
  static mstate next_to_use;
  if (next_to_use == NULL)
    next_to_use = &main_arena;

  /* Iterate over all arenas (including those linked from
     free_list).  */
  result = next_to_use;
  do
    {
      if (!__libc_lock_trylock (result->mutex))
        goto out;

      /* FIXME: This is a data race, see _int_new_arena.  */
      result = result->next;
    }
  while (result != next_to_use);

  /* Avoid AVOID_ARENA as we have already failed to allocate memory
     in that arena and it is currently locked.   */
  if (result == avoid_arena)
    result = result->next;

  /* No arena available without contention.  Wait for the next in line.  */
  LIBC_PROBE (memory_arena_reuse_wait, 3, &result->mutex, result, avoid_arena);
  __libc_lock_lock (result->mutex);

out:
  /* Attach the arena to the current thread.  */
  {
    /* Update the arena thread attachment counters.   */
    mstate replaced_arena = thread_arena;
    __libc_lock_lock (free_list_lock);
    detach_arena (replaced_arena);

    /* We may have picked up an arena on the free list.  We need to
       preserve the invariant that no arena on the free list has a
       positive attached_threads counter (otherwise,
       arena_thread_freeres cannot use the counter to determine if the
       arena needs to be put on the free list).  We unconditionally
       remove the selected arena from the free list.  The caller of
       reused_arena checked the free list and observed it to be empty,
       so the list is very short.  */
    remove_from_free_list (result);

    ++result->attached_threads;

    __libc_lock_unlock (free_list_lock);
  }

  LIBC_PROBE (memory_arena_reuse, 2, result, avoid_arena);
  thread_arena = result;
  next_to_use = result->next;

  return result;
}

arena_get2

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
static mstate
arena_get2 (size_t size, mstate avoid_arena)
{
  mstate a;
  // 指向一个malloc_state实例，用于指示arena

  static size_t narenas_limit;

  a = get_free_list ();
  // 意思是从arena的空闲链表中取出一个arena
  if (a == NULL)
  // 如果没有现成的arena，就造一个
    {
      if (narenas_limit == 0)
        {
          if (mp_.arena_max != 0)
            // 该变量属于tunable选项，默认情况下为0，用于限制一个进程中arena的数量
            narenas_limit = mp_.arena_max;
          else if (narenas > mp_.arena_test)
            // narenas是进程中arena的总数
            // arena_test在没有设置arena_max的情况下有效，只有当arena的数量超过这个值时
            // glibc才会检验arena的数量是否达到最大值
            {
              int n = __get_nprocs ();

              if (n >= 1)
                narenas_limit = NARENAS_FROM_NCORES (n);
              else
                /* We have no information about the system.  Assume two
                   cores.  */
                narenas_limit = NARENAS_FROM_NCORES (2);
            }
            // 这里是根据CPU核数来确定arena的数目
        }
        /* 上面这个if语句可以看出开发者为了提高性能做出的努力。首先，查询CPU核心数从而获得最大
         * arena数量的信息需要一定的时间开销，正常情况下，arena max和arena test都没有被设置
         * 这时每次申请新的arena都要进行一次查询操作，因此我们可以通过设置arena test来进一步
         * 压榨程序的性能（即arena的数量没有达到这个值时，我们可以保证有足够的arena）。同时
         * 假设我们设置了arena max，那么arena的最大数量就人为的确定下来了，我们也就不再需要进行
         * 查询，设置arena test的优势也就不存在了。*/
    repeat:;
      size_t n = narenas;

      if (__glibc_unlikely (n <= narenas_limit - 1))
      // 开发者这里是假设大部分程序使用了多线程？
      // 因此arena大概率不够用？
        {
        // 如果narenas与n相等，则将n+1赋值给narenas，并返回0；否则返回1
          if (catomic_compare_and_exchange_bool_acq (&narenas, n + 1, n))
            goto repeat;
        /* 这里似乎是一个非常巧妙的保护措施，将上面的两个if语句分别标记为1和2
         * 任何narenas的值在2之前被其他线程的修改都会在2处会检测出不一致。
         * 从而回到1之前重新检测是否达到limit
         * 又因为2处校验操作的原子性（看起来这个原子性对多核cpu也适用，具体信息需要更多资料支撑）
         * 我们可以保证不会有两个线程同时执行2处的操作。这便保证了线程的安全性。
         */
          a = _int_new_arena (size);
        // 经过上面的两次校验，我们可以确定能执行到这个位置的线程不会引起arena数量超出限制了
          if (__glibc_unlikely (a == NULL))
            catomic_decrement (&narenas);
        }
      else
        a = reused_arena (avoid_arena);
        // 尝试重复利用一个arena，并避免使用avoid_arena，因为这里假设我们在avoid_arena分配内存时失败过
        // 这意味着它可能已经被锁上了
    }
  return a;
}

tcache_init

作用为初始化tcache bins，tcache的全称大概是thread cache，它和多线程密切相关

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
static void
tcache_init(void)
{
  mstate ar_ptr;
  // 指向一个malloc_state实例，注意这种实例通常用来指示一个arena
  void *victim = 0;
  const size_t bytes = sizeof (tcache_perthread_struct);
  // tcache_perthread_struct用于存放用于tcache的辅助数据
  // bytes是其大小


  if (tcache_shutting_down)
    return;
  // 判断是否tcache已经被释放，其中tcache_shutting_down是一个bool值

  arena_get (ar_ptr, bytes);
  /* 当主线程第一次调用tcache_init时，由于arena_get会将thread_arena赋值给ar_ptr
   * 并检测检测thread_arena是否为空。而在ptmalloc_init函数中我们已经将thread_arena
   * 置为main_arena，因此ar_ptr最终会被置为main_arena。注意直到这时main_arena
   * 仍然没有得到真正可用的一块区域（即在地址空间中，heap这一区域尚且不存在）。接下来的
   * _int_malloc函数将会调用sysmalloc函数，进而通过sbrk真正的初始化main_arena。*/

  victim = _int_malloc (ar_ptr, bytes);
  if (!victim && ar_ptr != NULL)
    {
      ar_ptr = arena_get_retry (ar_ptr, bytes);
      victim = _int_malloc (ar_ptr, bytes);
    }


  if (ar_ptr != NULL)
    __libc_lock_unlock (ar_ptr->mutex);

  /* In a low memory situation, we may not be able to allocate memory
     - in which case, we just keep trying later.  However, we
     typically do this very early, so either there is sufficient
     memory, or there isn't enough memory to do non-trivial
     allocations anyway.  */
  if (victim)
    {
      tcache = (tcache_perthread_struct *) victim;
      memset (tcache, 0, sizeof (tcache_perthread_struct));
    }

}

tcache_put

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* 该函数假设idx在tcache中存在而且对应的链表没有满.  */
static __always_inline void
tcache_put (mchunkptr chunk, size_t tc_idx)
{
  tcache_entry *e = (tcache_entry *) chunk2mem (chunk);
  // 该entry指向该chunk的用户可控内容，而不是chunk的internal header

  /* 将key赋值为全局变量tcache的值，方便我们在_int_free函数中检测是否发生了double free 
   * （类似于一个难以伪造的标签）*/
  e->key = tcache;

  e->next = tcache->entries[tc_idx];
  tcache->entries[tc_idx] = e;
  // 使用头插法将chunk加入链表
  ++(tcache->counts[tc_idx]);
}

grow_heap

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
static int
grow_heap (heap_info *h, long diff)
{
  size_t pagesize = GLRO (dl_pagesize);
  long new_size;

  diff = ALIGN_UP (diff, pagesize);
  new_size = (long) h->size + diff;
  if ((unsigned long) new_size > (unsigned long) HEAP_MAX_SIZE)
    return -1;

  if ((unsigned long) new_size > h->mprotect_size)
    {
      if (__mprotect ((char *) h + h->mprotect_size,
                      (unsigned long) new_size - h->mprotect_size,
                      PROT_READ  PROT_WRITE) != 0)
        return -2;

      h->mprotect_size = new_size;
    }

  h->size = new_size;
  LIBC_PROBE (memory_heap_more, 2, h, h->size);
  return 0;
}
/* 该函数做的事情很简单，在new_heap函数中，我们在利用mmap为heap分配空间时，一次性分配了HEAP_MAX_SIZE
 * 大小的空间，而仅仅将前size大小的空间使用mprotect函数改变了权限，因此我们在增长heap中可用空间的大小时
 * 只需把剩下的空间的前diff（假设有效）大小的空间也使用mprotect函数修改为rw权限即可 */

主要函数

sysmalloc

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
/* sysmalloc被用于向操作系统请求更多的内存。该函数假设av->top没有大于nb的空间, 因此它将会尝试
 * 扩展或者是替换掉top */

static void *
sysmalloc (INTERNAL_SIZE_T nb, mstate av)
{
  mchunkptr old_top;              /* incoming value of av->top */
  INTERNAL_SIZE_T old_size;       /* its size */
  char *old_end;                  /* its end address */

  long size;                      /* arg to first MORECORE or mmap call */
  char *brk;                      /* return value from MORECORE */

  long correction;                /* arg to 2nd MORECORE call */
  char *snd_brk;                  /* 2nd return val */

  INTERNAL_SIZE_T front_misalign; /* unusable bytes at front of new space */
  INTERNAL_SIZE_T end_misalign;   /* partial page left at end of new space */
  char *aligned_brk;              /* aligned offset into brk */

  mchunkptr p;                    /* the allocated/returned chunk */
  mchunkptr remainder;            /* remainder from allocation */
  unsigned long remainder_size;   /* its size */


  size_t pagesize = GLRO (dl_pagesize);
  bool tried_mmap = false;


  /* 如果mmap可用且请求的大小大于mmap threshold, 而且再次mmap不会超过mmap块数目限制
   * 我们就直接mmap一块对应大小的内存并返回 */

  if (av == NULL
       ((unsigned long) (nb) >= (unsigned long) (mp_.mmap_threshold)
    && (mp_.n_mmaps < mp_.n_mmaps_max)))
    {
      char *mm;           /* mmap的返回值 */

    try_mmap:
      /* 对于mmap的块, 我们需要先将nb加上SIZE_SZ再向上取整到与页对齐, 因为后面没有堆块可复用了 */
      if (MALLOC_ALIGNMENT == 2 * SIZE_SZ)
        size = ALIGN_UP (nb + SIZE_SZ, pagesize);
      else
        size = ALIGN_UP (nb + SIZE_SZ + MALLOC_ALIGN_MASK, pagesize);
      tried_mmap = true;

      /* 判断size, 防止溢出 */
      if ((unsigned long) (size) > (unsigned long) (nb))
        {
          mm = (char *) (MMAP (0, size, PROT_READ  PROT_WRITE, 0));

          if (mm != MAP_FAILED)
            {
              /*
                 The offset to the start of the mmapped region is stored
                 in the prev_size field of the chunk. This allows us to adjust
                 returned start address to meet alignment requirements here
                 and in memalign(), and still be able to compute proper
                 address argument for later munmap in free() and realloc().
               */

              if (MALLOC_ALIGNMENT == 2 * SIZE_SZ)
                {
                  /* 检测对齐是否正确  */
                  assert (((INTERNAL_SIZE_T) chunk2mem (mm) & MALLOC_ALIGN_MASK) == 0);
                  front_misalign = 0;
                }
              else
                front_misalign = (INTERNAL_SIZE_T) chunk2mem (mm) & MALLOC_ALIGN_MASK;
              if (front_misalign > 0)
                {
                  correction = MALLOC_ALIGNMENT - front_misalign;
                  p = (mchunkptr) (mm + correction);
      set_prev_size (p, correction);
                  set_head (p, (size - correction)  IS_MMAPPED);
                }
              else
                {
                  p = (mchunkptr) mm;
                  set_prev_size (p, 0);
                  set_head (p, size  IS_MMAPPED);
                }

              /* update statistics */

              int new = atomic_exchange_and_add (&mp_.n_mmaps, 1) + 1;
              atomic_max (&mp_.max_n_mmaps, new);

              unsigned long sum;
              sum = atomic_exchange_and_add (&mp_.mmapped_mem, size) + size;
              atomic_max (&mp_.max_mmapped_mem, sum);

              check_chunk (av, p);

              return chunk2mem (p);
            }
        }
    }

  /* 没有可用的arena且(可能的)mmap失败了  */
  if (av == NULL)
    return 0;

  /* 记录原本top chunk的相关信息 */

  old_top = av->top;
  old_size = chunksize (old_top);
  old_end = (char *) (chunk_at_offset (old_top, old_size));

  brk = snd_brk = (char *) (MORECORE_FAILURE);

  /* 如果这不是我们第一次deal with这个arena, 那么我们要求old_size和prev_inuse
   * 都是正常的(prev_inuse被置为, 即arena被使用过) */

  assert ((old_top == initial_top (av) && old_size == 0) 
          ((unsigned long) (old_size) >= MINSIZE &&
           prev_inuse (old_top) &&
           ((unsigned long) old_end & (pagesize - 1)) == 0));

  /* 到这里为止av一定是一个有效值, 正常情况下old_size一定小于我们申请的size(否则不会进入sysmalloc函数)
   * 主线程对sysmalloc的第一次调用比较特殊, 此时av是main_arena, 而正如我们所知, main arena此时并没有
   * 对应的内存中的分配区. 在malloc_init_state函数中, bins被初始化为对应的等效chunk(详情参见源码)
   * 而top被赋值为bins[1], 此时其实际上指向top本身的地址, 此处的malloc_chunk结构体的mchunk_size成员
   * 为last_remainder, 初始值为0 */
  assert ((unsigned long) (old_size) < (unsigned long) (nb + MINSIZE));


  if (av != &main_arena)
    {
      heap_info *old_heap, *heap;
      size_t old_heap_size;

      /* 首先尝试扩展当前的heap */
      old_heap = heap_for_ptr (old_top);
      old_heap_size = old_heap->size;
      if ((long) (MINSIZE + nb - old_size) > 0
          && grow_heap (old_heap, MINSIZE + nb - old_size) == 0)
        {
          av->system_mem += old_heap->size - old_heap_size;
          // 加上空间的增量
          set_head (old_top, (((char *) old_heap + old_heap->size) - (char *) old_top)
                     PREV_INUSE);
          // 设置top chunk的size项
        }
      else if ((heap = new_heap (nb + (MINSIZE + sizeof (*heap)), mp_.top_pad)))
        {
          /* Use a newly allocated heap.  */
          heap->ar_ptr = av;
          heap->prev = old_heap;
          av->system_mem += heap->size;
          /* Set up the new top.  */
          top (av) = chunk_at_offset (heap, sizeof (*heap));
          set_head (top (av), (heap->size - sizeof (*heap))  PREV_INUSE);

          /* Setup fencepost and free the old top chunk with a multiple of
             MALLOC_ALIGNMENT in size. */
          /* The fencepost takes at least MINSIZE bytes, because it might
             become the top chunk again later.  Note that a footer is set
             up, too, although the chunk is marked in use. */
          old_size = (old_size - MINSIZE) & ~MALLOC_ALIGN_MASK;
          set_head (chunk_at_offset (old_top, old_size + 2 * SIZE_SZ), 0  PREV_INUSE);
          if (old_size >= MINSIZE)
            {
              set_head (chunk_at_offset (old_top, old_size), (2 * SIZE_SZ)  PREV_INUSE);
              set_foot (chunk_at_offset (old_top, old_size), (2 * SIZE_SZ));
              set_head (old_top, old_size  PREV_INUSE  NON_MAIN_ARENA);
              _int_free (av, old_top, 1);
            }
          else
            {
              set_head (old_top, (old_size + 2 * SIZE_SZ)  PREV_INUSE);
              set_foot (old_top, (old_size + 2 * SIZE_SZ));
            }
        }
      else if (!tried_mmap)
        /* We can at least try to use to mmap memory.  */
        goto try_mmap;
    }
  else     /* av == main_arena */
  /* 下面这一段需要我们重点关注，它是main_arena初始化工作的尾声，在这一部分结束后
   * 我们的进程地址空间中才真正出现了可以用来分配内存的main_arena */

    { /* Request enough space for nb + pad + overhead */
      size = nb + mp_.top_pad + MINSIZE;

      /* 如果brk分配空间是连续的，这就意味着我们可以善加利用已有的空间。如果我们获得分配的
       * 空间之后发现得到的空间并不连续，可以把old_size再加回来。 */
      if (contiguous (av))
        size -= old_size;

      size = ALIGN_UP (size, pagesize);

      /* 避免因为size过大而溢出 */
      if (size > 0)
        {
          brk = (char *) (MORECORE (size));
          /* 在这里我们进行了系统调用brk，通过改变program break来进行堆空间的申请以及改动
           * 注意到这个位置我们的初始化工作还没有结束，我们需要保证heap的结尾地址也是以page size
           * 对齐的，*/
          LIBC_PROBE (memory_sbrk_more, 2, brk, size);
        }

      if (brk != (char *) (MORECORE_FAILURE))
        {
          /* 下次可以尝试改写__after_morecore_hook来劫持控制流  */
          void (*hook) (void) = atomic_forced_read (__after_morecore_hook);
          if (__builtin_expect (hook != NULL, 0))
            (*hook)();
        }
      else
        {
        /* 如果mmap可用，那么在MORECORE失败时我们可以将mmap作为备用。当操作系统的内存空间中
         * 无法扩展到连续的内存中，而其他地方又存在足够的空间时mmap将会很有用。由于这时mmap出
         * 的空间相比较那些独立的arena来说是相对特殊的，因此我们这里不受mmap max count和
         * mmap threshold的约束 */

          /* mmap分配的空间是不连续的，因此原来top chunk里面可用的空间无法重复利用了 */
          if (contiguous (av))
            size = ALIGN_UP (size + old_size, pagesize);

          /* 申请稍大的空间（默认1024x1024），原因未知 */
          if ((unsigned long) (size) < (unsigned long) (MMAP_AS_MORECORE_SIZE))
            size = MMAP_AS_MORECORE_SIZE;

          /* 检查溢出 */
          if ((unsigned long) (size) > (unsigned long) (nb))
            {
              char *mbrk = (char *) (MMAP (0, size, PROT_READ  PROT_WRITE, 0));

              if (mbrk != MAP_FAILED)
                {
                  brk = mbrk;
                  snd_brk = brk + size;

                  /* 我们的arena现在已经无法连续的扩展了。 */
                  set_noncontiguous (av);
                }
            }
        }

      if (brk != (char *) (MORECORE_FAILURE))
        {
          if (mp_.sbrk_base == 0)
            mp_.sbrk_base = brk;
          av->system_mem += size;

          /* brk保持old_end，同时snd_brk保持初始值，这意味着我们的sbrk调用成功，因此只需
           * 更新原本top chunk的size即可，一个特殊情况是程序第一次调用sbrk，这时heap还未
           * 初始化，因此brk不等于old_end */

          if (brk == old_end && snd_brk == (char *) (MORECORE_FAILURE))
              set_head (old_top, (size + old_size)  PREV_INUSE);

          else if (contiguous (av) && old_size && brk < old_end)
              /* 发生异常，我们空间被别的进程动了，因此赶快报错  */
              malloc_printerr ("break adjusted to free malloc space");

          /*
           * 如果我们正处于heap初始化的过程中或者使用了mmap分配空间导致内存不连续，那么
              我们就要找出内存的结尾在哪里（snd_brk)
           * 我们必须保证malloc出来的所有chunk都以MALLOC_ALIGNMENT大小对齐

           * If there was an intervening foreign sbrk, we need to adjust sbrk
              request size to account for fact that we will not be able to
              combine new space with existing space in old_top.

            * 几乎所有的操作系统都会一次性分配一个页，在这种情况下我们申请的空间也应当以页对齐
              因此我们考虑分配足够多的空间，使空间的结尾地址也以页对齐。这使得我们未来的调用
              分配的空间也按页对齐 */

          else
            {
              front_misalign = 0;
              end_misalign = 0;
              correction = 0;
              aligned_brk = brk;

              /* handle contiguous cases */
              if (contiguous (av))
                {
                  /* Count foreign sbrk as system_mem.  */
                  if (old_size)
                    av->system_mem += brk - old_end;

                  /* Guarantee alignment of first new chunk made from this space */

                  front_misalign = (INTERNAL_SIZE_T) chunk2mem (brk) & MALLOC_ALIGN_MASK;
                  if (front_misalign > 0)
                    {
                      /*
                         为brk分配的空间的头部添加一个修正，使其按页对齐
                       */

                      correction = MALLOC_ALIGNMENT - front_misalign;
                      aligned_brk += correction;
                    }

                  /*
                     由于经过上面的判断，brk与old_end不相等，这意味着我们分配的空间与（可能存在的）
                     原本的空间不相邻，因此无法与原本的空间合并。这意味着我们需要再分配一次空间，添加上
                     我们之前忽略掉的old_size，同时考虑对齐问题。
                   */

                  correction += old_size;

                  end_misalign = (INTERNAL_SIZE_T) (brk + size + correction);
                  correction += (ALIGN_UP (end_misalign, pagesize)) - end_misalign;

                  assert (correction >= 0);
                  snd_brk = (char *) (MORECORE (correction));

                  if (snd_brk == (char *) (MORECORE_FAILURE))
                    {
                      correction = 0;
                      snd_brk = (char *) (MORECORE (0));
                    }
                  else
                    {
                      /* Call the `morecore' hook if necessary.  */
                      void (*hook) (void) = atomic_forced_read (__after_morecore_hook);
                      if (__builtin_expect (hook != NULL, 0))
                        (*hook)();
                    }
                }

              /* 处理获得的内存不连续的情形 */
              else
                {
                  if (MALLOC_ALIGNMENT == 2 * SIZE_SZ)
                    assert (((unsigned long) chunk2mem (brk) & MALLOC_ALIGN_MASK) == 0);
                  else
                    {
                      front_misalign = (INTERNAL_SIZE_T) chunk2mem (brk) & MALLOC_ALIGN_MASK;
                      if (front_misalign > 0)
                        {
                          aligned_brk += MALLOC_ALIGNMENT - front_misalign;
                        }
                    }

                  if (snd_brk == (char *) (MORECORE_FAILURE))
                    {
                      snd_brk = (char *) (MORECORE (0));
                    }
                }

              /* 根据第二次sbrk的结果来调整top的位置以及size */
              if (snd_brk != (char *) (MORECORE_FAILURE))
                {
                  av->top = (mchunkptr) aligned_brk;
                  set_head (av->top, (snd_brk - aligned_brk + correction)  PREV_INUSE);
                  av->system_mem += correction;

                  /*
                     用于处理不连续的内存的情形，我们通过人工设置两个极小的使用中的块来避免与top chunk
                     进行的合并，以免合并到不属于我们的内存。
                   */

                  if (old_size != 0)
                    {
                      /*
                         缩减以前的top chunk来为即将插入的块留下空间
                       */
                      old_size = (old_size - 4 * SIZE_SZ) & ~MALLOC_ALIGN_MASK;
                      set_head (old_top, old_size  PREV_INUSE);

                      set_head (chunk_at_offset (old_top, old_size), (2 * SIZE_SZ)  PREV_INUSE);
                      set_head (chunk_at_offset (old_top, old_size + 2 * SIZE_SZ), (2 * SIZE_SZ)  PREV_INUSE);

                      /* 如果可能的话，将这个已经废掉的top chunk废掉 */
                      if (old_size >= MINSIZE)
                        {
                          _int_free (av, old_top, 1);
                        }
                    }
                }
            }
        }
    } /* if (av !=  &main_arena) */

  if ((unsigned long) av->system_mem > (unsigned long) (av->max_system_mem))
    av->max_system_mem = av->system_mem;
  check_malloc_state (av);

  /* 分配的最终阶段 */
  p = av->top;
  size = chunksize (p);
  // p为top chunk，而size为top chunk的大小

  /* 如果上面任何一条扩大top的路径成功，我们都将会进入if */
  if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE))
    {
    /* 在这里，我们简单的切割top chunk，切下来的的大小为nb的块作为返回值，而remainder作为新的top chunk */
      remainder_size = size - nb;
      remainder = chunk_at_offset (p, nb);
      av->top = remainder;
      set_head (p, nb  PREV_INUSE  (av != &main_arena ? NON_MAIN_ARENA : 0));
      set_head (remainder, remainder_size  PREV_INUSE);
      check_malloced_chunk (av, p, nb);
      return chunk2mem (p);
    }

  /* 扩大top失败时我们就会来到这里 */
  __set_errno (ENOMEM);
  return 0;
}

__int_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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
static void *
_int_malloc (mstate av, size_t bytes)
{
  INTERNAL_SIZE_T nb;               /* normalized request size */
  unsigned int idx;                 /* associated bin index */
  mbinptr bin;                      /* associated bin */

  mchunkptr victim;                 /* inspected/selected chunk */
  INTERNAL_SIZE_T size;             /* its size */
  int victim_index;                 /* its bin index */

  mchunkptr remainder;              /* remainder from a split */
  unsigned long remainder_size;     /* its size */

  unsigned int block;               /* bit map traverser */
  unsigned int bit;                 /* bit map traverser */
  unsigned int map;                 /* current word of binmap */

  mchunkptr fwd;                    /* misc temp for linking */
  mchunkptr bck;                    /* misc temp for linking */

#if USE_TCACHE
  size_t tcache_unsorted_count;      /* count of unsorted chunks processed */
#endif

  if (!checked_request2size (bytes, &nb))
    {
      __set_errno (ENOMEM);
      return NULL;
    }
  // nb为对齐后的实际堆块大小

  /* arena不存在，就使用sysmalloc创建一块新的arena，尚不明确这个if条件什么时候会满足  */
  if (__glibc_unlikely (av == NULL))
    {
      void *p = sysmalloc (nb, av);
      if (p != NULL)
  alloc_perturb (p, bytes);
      return p;
    }

  /* 如果我们请求的大小输入fastbin，那么我们将首先检测相应的bin中有没有可用的块
   * 注意下面的代码即使是在av没有被初始化的情况下依然可用，因此我们不需要进行特地的检查 */

#define REMOVE_FB(fb, victim, pp)      \
  do              \
    {              \
      victim = pp;          \
      if (victim == NULL)        \
  break;            \
    }              \
  while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim)) \
   != victim);
  // 如果fb与victim相等，就将victim->fd赋值给fb，并返回victim
  // 这里实际上是从以fb起始的链表中移除pp

  if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
    {
      idx = fastbin_index (nb);
      mfastbinptr *fb = &fastbin (av, idx);
      // 由堆块的大小得到相应fastbin的索引，同时从fastbins数组中取出相应的链表
      mchunkptr pp;
      victim = *fb;

      if (victim != NULL)
        // 如果链表不为空
        {
          // 将victim从链表中移除，注意这里是直接将链表的首个块取出
          if (SINGLE_THREAD_P)
              *fb = victim->fd;
          else
              REMOVE_FB (fb, pp, victim);
          // 在多线程情况下，我们需要考虑到线程安全的问题
          if (__glibc_likely (victim != NULL))
            // 多线程防止竞态
            {
              size_t victim_idx = fastbin_index (chunksize (victim));
              if (__builtin_expect (victim_idx != idx, 0))
                  malloc_printerr ("malloc(): memory corruption (fast)");
              // 一个简单的安全性检查，避免chunk的size被恶意改写
              check_remalloced_chunk (av, victim, nb);
              // 正常情况下，这个语句是空的，除非你编译glibc时声明开启debug支持
#if USE_TCACHE
              /* 如果这个bin中还有一个块，那么为了提高速度，我们将它放到tcachebin中  */
              size_t tc_idx = csize2tidx (nb);
              if (tcache && tc_idx < mp_.tcache_bins)
                /* 前提是tcache已经初始化而且nb大小的chunk在tcachebin中，在tcache_init
                 * 函数的结尾，我们看到tcache指向了arena开头的一块大小为 sizeof(tcache_perthread_struct)
                 * 的内存，并且这一块内存被memset函数初始化为0. */
                {
                  mchunkptr tc_victim;

                  /* 在tcache没有占满的情况下将这个fastbin中的所有剩下的chunk转移到tcache中 */
                  while (tcache->counts[tc_idx] < mp_.tcache_count
                           && (tc_victim = *fb) != NULL)
                    {
                      if (SINGLE_THREAD_P)
                          *fb = tc_victim->fd;
                      else
                        {
                          REMOVE_FB (fb, pp, tc_victim);
                          if (__glibc_unlikely (tc_victim == NULL))
                              break;
                        }
                      tcache_put (tc_victim, tc_idx);
                      // 将victim放到相应idx的tcache中
                    }
                }
#endif
              void *p = chunk2mem (victim);
              alloc_perturb (p, bytes);
              /* 正常情况下这个函数可以忽略，该函数的作用是将已分配的内存以某个值填充（perturb_byte）
               * 根据https://stackoverflow.com/questions/8134537/perturb-byte-in-int-malloc-in-glibc
               * 的描述，其作用仅仅是方便调试时直观的看到哪些内存被分配了，哪些内存被释放了。默认情况下
               * perturb_byte的值为0 */
              return p;
            }
        }
    }

   /*
      程序执行到这个位置，说明tcache bin和fastbin中都没有剩余的块或者请求的大小超过了两者的最大大小
      进入smallbin搜索的条件是块足够小（64位默认是0x400以下）。
      关于不首先进入unsortedbin搜索到原因：由于smallbins结构采用的是简单分离适配，我们只需判断对应的
      bin进行首次适配即可，对于这种稍小的请求来说速度非常快。而unsortedbin采用的是最佳适配，我们需要遍历
      整个链表，因此速度较慢。
   */

  if (in_smallbin_range (nb))
    {
      idx = smallbin_index (nb);
      bin = bin_at (av, idx);

      // 还记得malloc_state_init函数吗，在这个函数中，我们将bins中的每一项都初始化为了相应的等效chunk的地址
      if ((victim = last (bin)) != bin)
        {
          bck = victim->bk;
          // 一个安全性检测，这要求本chunk与下一个chunk之间的连接是双向的
          if (__glibc_unlikely (bck->fd != victim))
              malloc_printerr ("malloc(): smallbin double linked list corrupted");
          set_inuse_bit_at_offset (victim, nb);
          // 宏展开后为 (((mchunkptr) (((char *) (victim)) + (nb)))->mchunk_size = 0x1)
          // 注意smallbin中为0x400以下所有的对齐的chunk都预留了位置
          bin->bk = bck;
          bck->fd = bin;
          // 从双向链表中删除victim块

          if (av != &main_arena)
              set_non_main_arena (victim);
          check_malloced_chunk (av, victim, nb);
#if USE_TCACHE
          /* 将余下的块缓存到tcache中，这一点和上面fastbin中的操作几乎相同  */
          size_t tc_idx = csize2tidx (nb);
          if (tcache && tc_idx < mp_.tcache_bins)
            // 同上
            {
              mchunkptr tc_victim;

              /* 同上  */
              while (tcache->counts[tc_idx] < mp_.tcache_count
                       && (tc_victim = last (bin)) != bin)
                {
                  if (tc_victim != 0)
                    {
                      bck = tc_victim->bk;
                      set_inuse_bit_at_offset (tc_victim, nb);
                      // tcache与fastbins中块的一个特点就是下一个毗邻块的prev inuse保持置位状态
                      if (av != &main_arena)
                          set_non_main_arena (tc_victim);
                      bin->bk = bck;
                      bck->fd = bin;
                      //由于tcache是一个perthread的结构，我们不需要原子操作

                      tcache_put (tc_victim, tc_idx);
                    }
                }
            }
#endif
          void *p = chunk2mem (victim);
          alloc_perturb (p, bytes);
        // 同上
          return p;
        }
    }

  else
    /* 执行到这里这意味请求的size已经进入了largebin的范围，在进行下一步的处理之前，
     * 我们需要先进行consolidate以清空fastbin，在consolidate的过程中，fastbin中的
     * chunk与相邻的空闲块合并并被加入到unsorted bin中，以此来减轻内存碎片化 */
    {
      idx = largebin_index (nb);
      if (atomic_load_relaxed (&av->have_fastchunks))
          malloc_consolidate (av);
    }

  /* 利用最佳适配原则从最近释放的块和remainder中取出一个块。例外情况是if this a small request, 
   * the chunk is remainder from the most recent non-exact fit.
   * 将遍历过的chunk依照大小放在bins中。注意这是唯一一个chunk可以被放到bins里面的机会 。*/

#if USE_TCACHE
  INTERNAL_SIZE_T tcache_nb = 0;
  size_t tc_idx = csize2tidx (nb);
  if (tcache && tc_idx < mp_.tcache_bins)
    tcache_nb = nb;
  int return_cached = 0;
  // 如果对应的块大小位于tcache范围内，将tcache nb赋值为nb

  tcache_unsorted_count = 0;
#endif

  for (;; )
    {
      int iters = 0;
      while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
        // victim永远指向unsorted bin中的第一个chunk
        {
          bck = victim->bk;
          size = chunksize (victim);
          mchunkptr next = chunk_at_offset (victim, size);

           /* 检测如下几点
           * 1. 本块与毗邻的下一块的size是否正确
           * 2. 本块的size与毗邻的下一块的prev size域是否吻合
           * 3. 本块是否与双向链表中的下一个块形成双向连接
           * 4. 毗邻的下一块的prev inuse位是否被置位
           */
          if (__glibc_unlikely (size <= 2 * SIZE_SZ)
               __glibc_unlikely (size > av->system_mem))
            malloc_printerr ("malloc(): invalid size (unsorted)");
          if (__glibc_unlikely (chunksize_nomask (next) < 2 * SIZE_SZ)
               __glibc_unlikely (chunksize_nomask (next) > av->system_mem))
            malloc_printerr ("malloc(): invalid next size (unsorted)");
          if (__glibc_unlikely ((prev_size (next) & ~(SIZE_BITS)) != size))
            malloc_printerr ("malloc(): mismatching next->prev_size (unsorted)");
          if (__glibc_unlikely (bck->fd != victim)
               __glibc_unlikely (victim->fd != unsorted_chunks (av)))
            malloc_printerr ("malloc(): unsorted double linked list corrupted");
          if (__glibc_unlikely (prev_inuse (next)))
            malloc_printerr ("malloc(): invalid next->prev_inuse (unsorted)");

           /*
              如果request在small bin的范围内而且unsorted bin中只有一个chunk，那么我们
              直接使用last remainder。last remainder是一种特别的chunk，它是由某一个大块
              分割后余下的部分。在连续的small request的情况下，这一策略有助于增强程序的局部性。
              同时这时最佳适配原则的唯一特例。
           */
          if (in_smallbin_range (nb) &&
              // 此request在small bin范围内
              bck == unsorted_chunks (av) &&
              // victim是unsorted bin中的唯一chunk
              victim == av->last_remainder &&
              // victim是last remainder
              (unsigned long) (size) > (unsigned long) (nb + MINSIZE))
              // victim的大小足够request使用
            {
              /* 分割并重新附加remainder */
              remainder_size = size - nb;
              /* 获取剩余的size */
              remainder = chunk_at_offset (victim, nb);
              /* 获取分割后的新的remainder */
              unsorted_chunks (av)->bk = unsorted_chunks (av)->fd = remainder;
              /* 再次形成双链表（part 1） */
              av->last_remainder = remainder;
              /* 设置新的last_remainder */
              remainder->bk = remainder->fd = unsorted_chunks (av);
              /* 再次形成双链表（part 2） */
              if (!in_smallbin_range (remainder_size))
                /* 如果该chunk属于一个large chunk，那么我们将其fd_nextsize与bk_nextsize设为NULL */
                {
                  remainder->fd_nextsize = NULL;
                  remainder->bk_nextsize = NULL;
                }

              set_head (victim, nb  PREV_INUSE 
                        (av != &main_arena ? NON_MAIN_ARENA : 0));
              set_head (remainder, remainder_size  PREV_INUSE);
              set_foot (remainder, remainder_size);
              /* 设置victim和remainder的header，以及remainder的下一个毗邻块的prev size */

              check_malloced_chunk (av, victim, nb);
              void *p = chunk2mem (victim);
              /* p指向用户可见的内存 */
              alloc_perturb (p, bytes);
              return p;
            }

          /* 控制流走向此处说明last remainder不存在或者不满足要求（并非unsorted bin中的唯一块或者大小不足 */
          if (__glibc_unlikely (bck->fd != victim))
            malloc_printerr ("malloc(): corrupted unsorted chunks 3");
          /* 检测双链是否完整 */
          unsorted_chunks (av)->bk = bck;
          bck->fd = unsorted_chunks (av);

          /* 
            将victim从双链表中移除以进行下一步操作
            注意这里不论该victim是否大小合适，我们都会将其从链表中移除 
            如果victim大小刚好合适，这时又分为两种情况
            1. 本块大小恰好在tcache范围内且对应链未满，那么我们将其优先放入tcache中并进行下一次循环
            2. 否则我们将本块直接返回

            如果victim大小与我们请求的大小不同，那么我们将其放到对应的bin中
          */

          if (size == nb)
            {
              set_inuse_bit_at_offset (victim, size);
              if (av != &main_arena)
                  set_non_main_arena (victim);
#if USE_TCACHE
              /* 优先装满tcache，只有当tcache满时我们才会直接将块返回，之后我们也有可能用到这个装入tcache的块  */
              if (tcache_nb && tcache->counts[tc_idx] < mp_.tcache_count)
                {
                  tcache_put (victim, tc_idx);
                  return_cached = 1;
                  continue;
                }
              else
                {
#endif
                  check_malloced_chunk (av, victim, nb);
                  void *p = chunk2mem (victim);
                  alloc_perturb (p, bytes);
                  return p;
#if USE_TCACHE
                }
#endif
            }

          /* 将chunk放到对应的bin中 */

          if (in_smallbin_range (size))
            {
              victim_index = smallbin_index (size);
              bck = bin_at (av, victim_index);
              fwd = bck->fd;
              /* 如果victim是一个small chunk，那么我们要做的事很简单：将其纳入由fd和bk组成的双链表中即可 */
            }
          else
            {
              /* 如果victim是一个large chunk，那么情况比较复杂，我们不仅要将victim加入链中，
                 还要保证链表中的chunk以size按从小到大顺序排序 */
              victim_index = largebin_index (size);
              bck = bin_at (av, victim_index);
              fwd = bck->fd;

              if (fwd != bck)
                /* 保证该bin非空 */
                {
                  size = PREV_INUSE;
                  /* malloc_consolidate保证了所有bins中的chunk不会与其他的空chunk相邻，为了加快速度
                     我们先使size的SIZE_BITS与bins中的chunk保持一致 */
                  assert (chunk_main_arena (bck->bk));
                  /* 我们之前说过，unsorted bin中chunk的NON_MAIN_ARENA位从来不会被置位 */
                  if ((unsigned long) (size) < (unsigned long) chunksize_nomask (bck->bk))
                    // 如果这个块足够小，那么只需将其以头插法插入到链表首即可
                    {
                      fwd = bck;
                      bck = bck->bk;
                      // 这一步相当于是fwd和bck互换，现在fwd指向链表的头节点

                      victim->fd_nextsize = fwd->fd;
                      victim->bk_nextsize = fwd->fd->bk_nextsize;
                      fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim;
                      /* 现在victim是该bin中size最小的chunk，将其按头插法加入nextsize构成的双向循环链表中即可 */
                    }
                  else
                    /* 这一部分类似于一个插入排序 */
                    {
                      assert (chunk_main_arena (fwd));
                      while ((unsigned long) size < chunksize_nomask (fwd))
                        /* 遍历查找到合适的位置 */
                        {
                          fwd = fwd->fd_nextsize;
                          assert (chunk_main_arena (fwd));
                        }

                      if ((unsigned long) size == (unsigned long) chunksize_nomask (fwd))
                        /* 对于size相等的情形，总是插入到第一个size相等的块之后，这带来的结果是只有
                           一系列size相等的块中的第一个块的nextsize域被设置，从而使得我们在遍历时可以跳过
                           size相等的块，而这正是nextsize链表的作用 */
                        fwd = fwd->fd;
                      else
                        /* 如果该size是独一无二的，那么将其插入到nextsize链表中 */ 
                        {
                          victim->fd_nextsize = fwd;
                          victim->bk_nextsize = fwd->bk_nextsize;
                          if (__glibc_unlikely (fwd->bk_nextsize->fd_nextsize != fwd))
                            malloc_printerr ("malloc(): largebin double linked list corrupted (nextsize)");
                          fwd->bk_nextsize = victim;
                          victim->bk_nextsize->fd_nextsize = victim;
                        }
                      bck = fwd->bk;
                      if (bck->fd != fwd)
                        malloc_printerr ("malloc(): largebin double linked list corrupted (bk)");
                    }
                }
              else
                // 链表为空的情形
                victim->fd_nextsize = victim->bk_nextsize = victim;
            }

          mark_bin (av, victim_index);
          // 在binmap中标记该bin不为空
          victim->bk = bck;
          victim->fd = fwd;
          fwd->bk = victim;
          bck->fd = victim;

#if USE_TCACHE
          /* 遍历次数达到限制，如果此时tcache中有被存入的块，直接将其取出并返回 */
          ++tcache_unsorted_count;
          if (return_cached
              && mp_.tcache_unsorted_limit > 0
              && tcache_unsorted_count > mp_.tcache_unsorted_limit)
            {
              return tcache_get (tc_idx);
            }
#endif

#define MAX_ITERS       10000
        /* 另一个硬性的遍历次数限制，达到限制直接break */
          if (++iters >= MAX_ITERS)
            break;
        }
    /* 
       我们遍历unsorted bin的循环到此结束了，首先回顾该循环的结束条件：
       1. last remainder存在而且是unsorted bin中唯一的块且大小足够（函数返回）
       2. unsorted bin中的所有块被遍历完毕（继续下一步）
       3. 循环次数达到tcache_unsorted_count的限制而且tcache中存在被缓存的块（函数返回）
       4. 循环次数达到MAX_ITERS限制（继续下一步）
       5. 有一个恰好适配的块而且对应的tcache被填满（函数返回）
       6. 有一个恰好适配的块而且size不在tcache的范围内（函数返回）

       再回顾该循环所做的事：
       1. 在使用last remainder的情况下，将其分割，并将余下的部分作为新的last remainder
       2. 将遇到的size与请求的size相同的块缓存到tcache中
       3. 将其他遇到的块放到相应的bin中
     */

#if USE_TCACHE
      /* 如果我们找到的合适的块都被放到了tcache中，那么取出一个并返回  */
      if (return_cached)
        {
          return tcache_get (tc_idx);
        }
#endif

      /* 如果我们遇到的是一个large request，那么使用nextsize构成的链表遍历对应的bin，
         尝试找出合适的大小最小的块 */

      if (!in_smallbin_range (nb))
        {
          bin = bin_at (av, idx);

          /* 如果链表为空或者是最大的块也没有请求的size大，那么我们直接跳过遍历 */
          if ((victim = first (bin)) != bin
        && (unsigned long) chunksize_nomask (victim)
          >= (unsigned long) (nb))
            {
              victim = victim->bk_nextsize;
              while (((unsigned long) (size = chunksize (victim)) <
                      (unsigned long) (nb)))
                victim = victim->bk_nextsize;

              /* 避免移除带有nextsize信息的那个块  */
              if (victim != last (bin)
      && chunksize_nomask (victim)
        == chunksize_nomask (victim->fd))
                victim = victim->fd;

              remainder_size = size - nb;
              // 切割一个large chunk，余下的部分就变成了remainder
              unlink_chunk (av, victim);

              /* 如果remainder的预计大小不足以构成一个chunk，那么不再分割 */
              if (remainder_size < MINSIZE)
                {
                  set_inuse_bit_at_offset (victim, size);
                  if (av != &main_arena)
                      set_non_main_arena (victim);
                }
              /* 进行分割 */
              else
                {
                  remainder = chunk_at_offset (victim, nb);
                  /* 我们不知道此时unsorted bin是否是空的，因此我们需要进行一次完整的插入操作 */
                  bck = unsorted_chunks (av);
                  fwd = bck->fd;
                  if (__glibc_unlikely (fwd->bk != bck))
                      malloc_printerr ("malloc(): corrupted unsorted chunks");
                  remainder->bk = bck;
                  remainder->fd = fwd;
                  bck->fd = remainder;
                  fwd->bk = remainder;
                  if (!in_smallbin_range (remainder_size))
                    {
                      remainder->fd_nextsize = NULL;
                      remainder->bk_nextsize = NULL;
                    }
                  set_head (victim, nb  PREV_INUSE  (av != &main_arena ? NON_MAIN_ARENA : 0));
                  set_head (remainder, remainder_size  PREV_INUSE);
                  set_foot (remainder, remainder_size);
                }
              check_malloced_chunk (av, victim, nb);
              void *p = chunk2mem (victim);
              alloc_perturb (p, bytes);
              return p;
              // 该if判断只要进入，就必然能找到一块合适的chunk，函数必然返回
            }
        }

      /* 
         如果控制流到达这个位置，说明这几种可能的情况：
         1. tcache中没有合适的块
         2. fastbins中没有合适的块
         3. small bins中没有合适的块
         4. unsorted bin中找不到合适的块（不存在或者循环达到限制）
         5. large bins中没有合适的块

         到这一步你可能会以为已经无路可走了，然而我们需要注意：tcache，fastbin，smallbin
         都是简单分离存储，unsorted bin和large bin是分离存储。因此这时我们可以考虑放宽我们
         对于分配到的chunk的要求，仅仅要求其大小大于request size，同时又尽可能的小即可，
         而不必恰好与request size相等。因此我们可以遍历每一个bin，从中找出符合要求的chunk
         并对其进行切割，将余下的部分放入last remainder。
         我们可以通过binmap来跳过空的bin，从而加速这一过程。
      */

      ++idx;
      // 准备查找存放更大chunk的bin
      bin = bin_at (av, idx);
      block = idx2block (idx);
      // block为该idx对应的bin对应的binmap位置
      map = av->binmap[block];
      bit = idx2bit (idx);

      for (;; )
        {
          /* 若本block的余下部分都没有有效的bin，那么跳过整个block  */
          if (bit > map  bit == 0)
            {
              do
                {
                  if (++block >= BINMAPSIZE) /* out of bins */
                    goto use_top;
                }
              while ((map = av->binmap[block]) == 0);

              bin = bin_at (av, (block << BINMAPSHIFT));
              bit = 1;
            }
          // 通过上面这个if语句，我们可以确定现在这个bin所在的block中必然有一个bin是有效的

          /* 我们使用这个循环来找到那个有效的bin */
          while ((bit & map) == 0)
            {
              bin = next_bin (bin);
              bit <<= 1;
              assert (bit != 0);
            }

          /* 检查这个bin，它有可能是空的（我们之前说过，当一个bin为空时，它对应的binmap项并不会立即被clear） */
          victim = last (bin);
          /* 注意这里的last体现了先进先出原则，bins实际上可以看作是由双向循环链表模拟的队列 */

          /*  如果这个bin是空的，那么将其对应的binmap项clear，然后进入下一次for循环 */
          if (victim == bin)
            {
              av->binmap[block] = map &= ~bit;
              bin = next_bin (bin);
              bit <<= 1;
            }

          else
            {
              size = chunksize (victim);

              /*  该bin中的第一个chunk一定是可用的 */
              assert ((unsigned long) (size) >= (unsigned long) (nb));

              remainder_size = size - nb;
              // 准备设置last remainder

              /* 将该bin从双链表中摘除 */
              unlink_chunk (av, victim);

              /* 若切割后留下的内存不足以构成一个块，那么不再进行切割 */
              if (remainder_size < MINSIZE)
                {
                  set_inuse_bit_at_offset (victim, size);
                  if (av != &main_arena)
                      set_non_main_arena (victim);
                }

              /* 进行切割 */
              else
                {
                  remainder = chunk_at_offset (victim, nb);

                  /* 我们不能假设unsorted bin是空的，因此我们需要进行一次完整的插入操作  */
                  bck = unsorted_chunks (av);
                  fwd = bck->fd;
                  if (__glibc_unlikely (fwd->bk != bck))
                      malloc_printerr ("malloc(): corrupted unsorted chunks 2");
                  remainder->bk = bck;
                  remainder->fd = fwd;
                  bck->fd = remainder;
                  fwd->bk = remainder;

                  /* 相比较于上一次分割large bin的操作，我们这里设置了last remainder */
                  if (in_smallbin_range (nb))
                    av->last_remainder = remainder;
                  if (!in_smallbin_range (remainder_size))
                    {
                      remainder->fd_nextsize = NULL;
                      remainder->bk_nextsize = NULL;
                    }
                  set_head (victim, nb  PREV_INUSE 
                            (av != &main_arena ? NON_MAIN_ARENA : 0));
                  set_head (remainder, remainder_size  PREV_INUSE);
                  set_foot (remainder, remainder_size);
                }
              check_malloced_chunk (av, victim, nb);
              void *p = chunk2mem (victim);
              alloc_perturb (p, bytes);
              return p;
            }
        }

    use_top:

      /* 
         程序执行到这里还是没返回，我们差不多没招了，这意味着现有的bin里面完全没有大小大于
         request size的块，因此我们只好切割top chunk，要是连top chunk都没有，那说明
         我们的堆区不够大了，需要通过sysmalloc函数要求操作系统扩大堆的大小 */

      victim = av->top;
      size = chunksize (victim);

      if (__glibc_unlikely (size > av->system_mem))
        malloc_printerr ("malloc(): corrupted top size");

      if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE))
        {
          remainder_size = size - nb;
          remainder = chunk_at_offset (victim, nb);
          av->top = remainder;
          set_head (victim, nb  PREV_INUSE 
                    (av != &main_arena ? NON_MAIN_ARENA : 0));
          set_head (remainder, remainder_size  PREV_INUSE);

          check_malloced_chunk (av, victim, nb);
          void *p = chunk2mem (victim);
          alloc_perturb (p, bytes);
          return p;
        }
      else if (atomic_load_relaxed (&av->have_fastchunks))
        // 如果在我们进行上面的一大坨操作时fastbin中又有了新的chunk，那么我们将其合并到unsorted bin中再来一遍
        {
          malloc_consolidate (av);
          /* 恢复原本的idx */
          if (in_smallbin_range (nb))
            idx = smallbin_index (nb);
          else
            idx = largebin_index (nb);
        }
      else
        {
        // 实在没办法，向操作系统请求更多的内存
        // 一个很特殊的情况是第一次malloc时，MAYBE_INIT_TCACHE将会调用_int_malloc
        // 这一次调用会直奔该块，开辟堆空间
          void *p = sysmalloc (nb, av);
          if (p != NULL)
            alloc_perturb (p, bytes);
          return p;
        }
    }
}

__libc_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
void *
__libc_malloc (size_t bytes)
{
  mstate ar_ptr;  // 一个指向malloc_state结构体的指针
  void *victim;

  _Static_assert (PTRDIFF_MAX <= SIZE_MAX / 2,
                  "PTRDIFF_MAX is not more than half of SIZE_MAX");
  /* 为了避免出现未定义的结果 */

  void *(*hook) (size_t, const void *)
    = atomic_forced_read (__malloc_hook);
  /* 将读操作变成原子操作，其实就是一个简单的赋值语句。初始时该值为malloc_hook_ini，初始
   * 化一次之后就变成空值了 */

  if (__builtin_expect (hook != NULL, 0))
    return (*hook)(bytes, RETURN_ADDRESS (0));
   /* 这里__builtin_expect很引人注意，这个指令是gcc提供的。如__builtin_expect (x, 0)
    * 的意思是告诉编译器x为0的几率很大，放到这里就是hook为NULL的几率很大（因为只初始化一次）
    * 从而使最终编译得到的指令性能提升。*/

#if USE_TCACHE
// 该常量定义在makefile中，在编译glibc时确定
  /* int_free also calls request2size, be careful to not pad twice.  */
  size_t tbytes;
  if (!checked_request2size (bytes, &tbytes))
    {
      __set_errno (ENOMEM);
      return NULL;
    }
  // tbyte是处理过的值，经过了padding，同时还检查了是否会发生溢出
  size_t tc_idx = csize2tidx (tbytes);
  // 由申请的大小确定请求的块在哪个tcache bin中，只是一个简单的计算。
  // 如果该块非常大，这里暂时不会处理

  MAYBE_INIT_TCACHE ();
  /* 该宏展开后为
   * # define MAYBE_INIT_TCACHE() \
   *     if (__glibc_unlikely (tcache == NULL)) \
   *      tcache_init();
   * 注意这里我们遇到了unlikely这种写法，这是GCC的一种黑魔法，意为括号内的条件不太可能成立
   * （这是显然的，因为在一个线程的生命周期中，我们可能仅仅需要对tcache初始化一次）
   * 就像上面的__builtin_expect一样，作用也相似。 */

  DIAG_PUSH_NEEDS_COMMENT;
  if (tc_idx < mp_.tcache_bins
      /*&& tc_idx < TCACHE_MAX_BINS*/ /* to appease gcc */
      && tcache
      && tcache->entries[tc_idx] != NULL)
    {
      return tcache_get (tc_idx);
    }
  DIAG_POP_NEEDS_COMMENT;
#endif

  if (SINGLE_THREAD_P)
    {
      victim = _int_malloc (&main_arena, bytes);
      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.  */
  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;
}
libc_hidden_def (__libc_malloc)

free函数

辅助函数

heap_trim

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
static int
heap_trim (heap_info *heap, size_t pad)
{
  mstate ar_ptr = heap->ar_ptr;
  unsigned long pagesz = GLRO (dl_pagesize);
  mchunkptr top_chunk = top (ar_ptr), p;
  heap_info *prev_heap;
  long new_size, top_size, top_area, extra, prev_size, misalign;

  /* Can this heap go away completely? */
  while (top_chunk == chunk_at_offset (heap, sizeof (*heap)))
    {
      prev_heap = heap->prev;
      prev_size = prev_heap->size - (MINSIZE - 2 * SIZE_SZ);
      p = chunk_at_offset (prev_heap, prev_size);
      /* fencepost must be properly aligned.  */
      misalign = ((long) p) & MALLOC_ALIGN_MASK;
      p = chunk_at_offset (prev_heap, prev_size - misalign);
      assert (chunksize_nomask (p) == (0  PREV_INUSE)); /* must be fencepost */
      p = prev_chunk (p);
      new_size = chunksize (p) + (MINSIZE - 2 * SIZE_SZ) + misalign;
      assert (new_size > 0 && new_size < (long) (2 * MINSIZE));
      if (!prev_inuse (p))
        new_size += prev_size (p);
      assert (new_size > 0 && new_size < HEAP_MAX_SIZE);
      if (new_size + (HEAP_MAX_SIZE - prev_heap->size) < pad + MINSIZE + pagesz)
        break;
      ar_ptr->system_mem -= heap->size;
      LIBC_PROBE (memory_heap_free, 2, heap, heap->size);
      delete_heap (heap);
      heap = prev_heap;
      if (!prev_inuse (p)) /* consolidate backward */
        {
          p = prev_chunk (p);
          unlink_chunk (ar_ptr, p);
        }
      assert (((unsigned long) ((char *) p + new_size) & (pagesz - 1)) == 0);
      assert (((char *) p + new_size) == ((char *) heap + heap->size));
      top (ar_ptr) = top_chunk = p;
      set_head (top_chunk, new_size  PREV_INUSE);
      /*check_chunk(ar_ptr, top_chunk);*/
    }

  /* Uses similar logic for per-thread arenas as the main arena with systrim
     and _int_free by preserving the top pad and rounding down to the nearest
     page.  */
  top_size = chunksize (top_chunk);
  if ((unsigned long)(top_size) <
      (unsigned long)(mp_.trim_threshold))
    return 0;

  top_area = top_size - MINSIZE - 1;
  if (top_area < 0  (size_t) top_area <= pad)
    return 0;

  /* Release in pagesize units and round down to the nearest page.  */
  extra = ALIGN_DOWN(top_area - pad, pagesz);
  if (extra == 0)
    return 0;

  /* Try to shrink. */
  if (shrink_heap (heap, extra) != 0)
    return 0;

  ar_ptr->system_mem -= extra;

  /* Success. Adjust top accordingly. */
  set_head (top_chunk, (top_size - extra)  PREV_INUSE);
  /*check_chunk(ar_ptr, top_chunk);*/
  return 1;
}

主要函数

_int_free

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
static void
_int_free (mstate av, mchunkptr p, int have_lock)
{
  INTERNAL_SIZE_T size;        /* its size */
  mfastbinptr *fb;             /* associated fastbin */
  mchunkptr nextchunk;         /* next contiguous chunk */
  INTERNAL_SIZE_T nextsize;    /* its size */
  int nextinuse;               /* true if nextchunk is used */
  INTERNAL_SIZE_T prevsize;    /* size of previous contiguous chunk */
  mchunkptr bck;               /* misc temp for linking */
  mchunkptr fwd;               /* misc temp for linking */

  size = chunksize (p);

  /* Little security check which won't hurt performance: the
     allocator never wrapps around at the end of the address space.
     Therefore we can exclude some size values which might appear
     here by accident or by "design" from some intruder.  */
  if (__builtin_expect ((uintptr_t) p > (uintptr_t) -size, 0)
       __builtin_expect (misaligned_chunk (p), 0))
    malloc_printerr ("free(): invalid pointer");
  /* We know that each chunk is at least MINSIZE bytes in size or a
     multiple of MALLOC_ALIGNMENT.  */
  if (__glibc_unlikely (size < MINSIZE  !aligned_OK (size)))
    malloc_printerr ("free(): invalid size");

  check_inuse_chunk(av, p);

#if USE_TCACHE
  {
    size_t tc_idx = csize2tidx (size);
    if (tcache != NULL && tc_idx < mp_.tcache_bins)
      {
  /* Check to see if it's already in the tcache.  */
  tcache_entry *e = (tcache_entry *) chunk2mem (p);

  /* This test succeeds on double free.  However, we don't 100%
     trust it (it also matches random payload data at a 1 in
     2^<size_t> chance), so verify it's not an unlikely
     coincidence before aborting.  */
  if (__glibc_unlikely (e->key == tcache))
    {
      tcache_entry *tmp;
      LIBC_PROBE (memory_tcache_double_free, 2, e, tc_idx);
      for (tmp = tcache->entries[tc_idx];
     tmp;
     tmp = tmp->next)
        if (tmp == e)
    malloc_printerr ("free(): double free detected in tcache 2");
      /* If we get here, it was a coincidence.  We've wasted a
         few cycles, but don't abort.  */
    }

  if (tcache->counts[tc_idx] < mp_.tcache_count)
    {
      tcache_put (p, tc_idx);
      return;
    }
      }
  }
#endif

  /*
    If eligible, place chunk on a fastbin so it can be found
    and used quickly in malloc.
  */

  if ((unsigned long)(size) <= (unsigned long)(get_max_fast ())

#if TRIM_FASTBINS
      /*
  If TRIM_FASTBINS set, don't place chunks
  bordering top into fastbins
      */
      && (chunk_at_offset(p, size) != av->top)
#endif
      ) {

    if (__builtin_expect (chunksize_nomask (chunk_at_offset (p, size))
        <= 2 * SIZE_SZ, 0)
   __builtin_expect (chunksize (chunk_at_offset (p, size))
           >= av->system_mem, 0))
      {
  bool fail = true;
  /* We might not have a lock at this point and concurrent modifications
     of system_mem might result in a false positive.  Redo the test after
     getting the lock.  */
  if (!have_lock)
    {
      __libc_lock_lock (av->mutex);
      fail = (chunksize_nomask (chunk_at_offset (p, size)) <= 2 * SIZE_SZ
         chunksize (chunk_at_offset (p, size)) >= av->system_mem);
      __libc_lock_unlock (av->mutex);
    }

  if (fail)
    malloc_printerr ("free(): invalid next size (fast)");
      }

    free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);

    atomic_store_relaxed (&av->have_fastchunks, true);
    unsigned int idx = fastbin_index(size);
    fb = &fastbin (av, idx);

    /* Atomically link P to its fastbin: P->FD = *FB; *FB = P;  */
    mchunkptr old = *fb, old2;

    if (SINGLE_THREAD_P)
      {
  /* Check that the top of the bin is not the record we are going to
     add (i.e., double free).  */
  if (__builtin_expect (old == p, 0))
    malloc_printerr ("double free or corruption (fasttop)");
  p->fd = old;
  *fb = p;
      }
    else
      do
  {
    /* Check that the top of the bin is not the record we are going to
       add (i.e., double free).  */
    if (__builtin_expect (old == p, 0))
      malloc_printerr ("double free or corruption (fasttop)");
    p->fd = old2 = old;
  }
      while ((old = catomic_compare_and_exchange_val_rel (fb, p, old2))
       != old2);

    /* Check that size of fastbin chunk at the top is the same as
       size of the chunk that we are adding.  We can dereference OLD
       only if we have the lock, otherwise it might have already been
       allocated again.  */
    if (have_lock && old != NULL
  && __builtin_expect (fastbin_index (chunksize (old)) != idx, 0))
      malloc_printerr ("invalid fastbin entry (free)");
  }

  /*
    Consolidate other non-mmapped chunks as they arrive.
  */

  else if (!chunk_is_mmapped(p)) {

    /* If we're single-threaded, don't lock the arena.  */
    if (SINGLE_THREAD_P)
      have_lock = true;

    if (!have_lock)
      __libc_lock_lock (av->mutex);

    nextchunk = chunk_at_offset(p, size);

    /* Lightweight tests: check whether the block is already the
       top block.  */
    if (__glibc_unlikely (p == av->top))
      malloc_printerr ("double free or corruption (top)");
    /* Or whether the next chunk is beyond the boundaries of the arena.  */
    if (__builtin_expect (contiguous (av)
        && (char *) nextchunk
        >= ((char *) av->top + chunksize(av->top)), 0))
  malloc_printerr ("double free or corruption (out)");
    /* Or whether the block is actually not marked used.  */
    if (__glibc_unlikely (!prev_inuse(nextchunk)))
      malloc_printerr ("double free or corruption (!prev)");

    nextsize = chunksize(nextchunk);
    if (__builtin_expect (chunksize_nomask (nextchunk) <= 2 * SIZE_SZ, 0)
   __builtin_expect (nextsize >= av->system_mem, 0))
      malloc_printerr ("free(): invalid next size (normal)");

    free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);

    /* consolidate backward */
    if (!prev_inuse(p)) {
      prevsize = prev_size (p);
      size += prevsize;
      p = chunk_at_offset(p, -((long) prevsize));
      if (__glibc_unlikely (chunksize(p) != prevsize))
        malloc_printerr ("corrupted size vs. prev_size while consolidating");
      unlink_chunk (av, p);
    }

    if (nextchunk != av->top) {
      /* get and clear inuse bit */
      nextinuse = inuse_bit_at_offset(nextchunk, nextsize);

      /* consolidate forward */
      if (!nextinuse) {
  unlink_chunk (av, nextchunk);
  size += nextsize;
      } else
  clear_inuse_bit_at_offset(nextchunk, 0);

      /*
  Place the chunk in unsorted chunk list. Chunks are
  not placed into regular bins until after they have
  been given one chance to be used in malloc.
      */

      bck = unsorted_chunks(av);
      fwd = bck->fd;
      if (__glibc_unlikely (fwd->bk != bck))
  malloc_printerr ("free(): corrupted unsorted chunks");
      p->fd = fwd;
      p->bk = bck;
      if (!in_smallbin_range(size))
  {
    p->fd_nextsize = NULL;
    p->bk_nextsize = NULL;
  }
      bck->fd = p;
      fwd->bk = p;

      set_head(p, size  PREV_INUSE);
      set_foot(p, size);

      check_free_chunk(av, p);
    }

    /*
      If the chunk borders the current high end of memory,
      consolidate into top
    */

    else {
      size += nextsize;
      set_head(p, size  PREV_INUSE);
      av->top = p;
      check_chunk(av, p);
    }

    /*
      If freeing a large space, consolidate possibly-surrounding
      chunks. Then, if the total unused topmost memory exceeds trim
      threshold, ask malloc_trim to reduce top.

      Unless max_fast is 0, we don't know if there are fastbins
      bordering top, so we cannot tell for sure whether threshold
      has been reached unless fastbins are consolidated.  But we
      don't want to consolidate on each free.  As a compromise,
      consolidation is performed if FASTBIN_CONSOLIDATION_THRESHOLD
      is reached.
    */

    if ((unsigned long)(size) >= FASTBIN_CONSOLIDATION_THRESHOLD) {
      if (atomic_load_relaxed (&av->have_fastchunks))
  malloc_consolidate(av);

      if (av == &main_arena) {
#ifndef MORECORE_CANNOT_TRIM
  if ((unsigned long)(chunksize(av->top)) >=
      (unsigned long)(mp_.trim_threshold))
    systrim(mp_.top_pad, av);
#endif
      } else {
  /* Always try heap_trim(), even if the top chunk is not
     large, because the corresponding heap might go away.  */
  heap_info *heap = heap_for_ptr(top(av));

  assert(heap->ar_ptr == av);
  heap_trim(heap, mp_.top_pad);
      }
    }

    if (!have_lock)
      __libc_lock_unlock (av->mutex);
  }
  /*
    If the chunk was allocated via mmap, release via munmap().
  */

  else {
    munmap_chunk (p);
  }
}

malloc_consolidate函数

虽然该函数是静态定义的，但由于其重要地位，我们仍然将花费一个小节的内容来对其进行解释。

辅助函数

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
/* 从Bins中的双向链表中摘下一个块（包括large， small，unsorted bins）  */
static void
unlink_chunk (mstate av, mchunkptr p)
{
  if (chunksize (p) != prev_size (next_chunk (p)))
    malloc_printerr ("corrupted size vs. prev_size");
  // 安全性检测

  mchunkptr fd = p->fd;
  mchunkptr bk = p->bk;
  // 分别获取该双向链表中本块的前驱节点和后继节点

  if (__builtin_expect (fd->bk != p  bk->fd != p, 0))
    malloc_printerr ("corrupted double-linked list");
  // 验证双向链表的双向性

  fd->bk = bk;
  bk->fd = fd;
  // 进行删除操作

  if (!in_smallbin_range (chunksize_nomask (p)) && p->fd_nextsize != NULL)
    // largebin中的节点不仅仅是通过fd bk连接起来，为了提高查找效率，它们还通过fd_nextsize以及bk_nextsize连接起来
    {
      if (p->fd_nextsize->bk_nextsize != p
           p->bk_nextsize->fd_nextsize != p)
          malloc_printerr ("corrupted double-linked list (not small)");
      // 检查双向链表的双向性

      if (fd->fd_nextsize == NULL)
        // 这说明我们要unlink的是一系列大小相同的chunk中的首个块（带有nextsize信息的那个）
        {
          if (p->fd_nextsize == p)
            // p与其自身成环的情形
              fd->fd_nextsize = fd->bk_nextsize = fd;
          else
            {
              fd->fd_nextsize = p->fd_nextsize;
              fd->bk_nextsize = p->bk_nextsize;
              p->fd_nextsize->bk_nextsize = fd;
              p->bk_nextsize->fd_nextsize = fd;
            }
        }
      else
        {
          p->fd_nextsize->bk_nextsize = p->bk_nextsize;
          p->bk_nextsize->fd_nextsize = p->fd_nextsize;
        }
    }
}

主要函数

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
/*
  ------------------------- malloc_consolidate -------------------------

  malloc_consolidate可以看作是free函数的一个特殊版本，它将清除fastbin中的块
  free函数本身做不到这一点，因此我们需要free函数的这个变种。
*/

static void malloc_consolidate(mstate av)
{
  mfastbinptr*    fb;                 /* current fastbin being consolidated */
  mfastbinptr*    maxfb;              /* last fastbin (for loop control) */
  mchunkptr       p;                  /* current chunk being consolidated */
  mchunkptr       nextp;              /* next chunk to consolidate */
  mchunkptr       unsorted_bin;       /* bin header */
  mchunkptr       first_unsorted;     /* chunk to link to */

  /* These have same use as in free() */
  mchunkptr       nextchunk;
  INTERNAL_SIZE_T size;
  INTERNAL_SIZE_T nextsize;
  INTERNAL_SIZE_T prevsize;
  int             nextinuse;

  atomic_store_relaxed (&av->have_fastchunks, false);

  unsorted_bin = unsorted_chunks(av);
  // 获取unsortedbin

  /*
    移除并合并fastbin中的每一个块并将其放到unsortedbin中。这样做的一个原因是在
    malloc确定这个块不会被再次使用之前，我们不需要对块所在的bin进行计算
  */

  maxfb = &fastbin (av, NFASTBINS - 1);
  // maxfb指向最后一个bin
  fb = &fastbin (av, 0);
  do {
    p = atomic_exchange_acq (fb, NULL);
    // 将NULL存入fb，并返回旧的fb的值，p初始指向该bin的链表首部
    if (p != 0) {
      do {
        {
          unsigned int idx = fastbin_index (chunksize (p));
          if ((&fastbin (av, idx)) != fb)
            malloc_printerr ("malloc_consolidate(): invalid chunk size");
          // 对chunk size进行安全性检查
        }

        check_inuse_chunk(av, p);
        nextp = p->fd;
        // 指向下一个堆块

        /* 相比较于free中的合并操作的代码稍微提高了效率 */
        size = chunksize (p);
        nextchunk = chunk_at_offset(p, size);
        nextsize = chunksize(nextchunk);
        // 获取物理上相邻的下一个块的大小

        if (!prev_inuse(p)) {
          // 如果与p物理相邻的前一个块是一个空闲块
          prevsize = prev_size (p);
          size += prevsize;
          // 更新size
          p = chunk_at_offset(p, -((long) prevsize));
          // 将p指向的块更新为p物理相邻的前一个块
          if (__glibc_unlikely (chunksize(p) != prevsize))
            malloc_printerr ("corrupted size vs. prev_size in fastbins");
          unlink_chunk (av, p);
          // 进行unink操作，即将p从其所在的双向链表中分离出来
        }

        if (nextchunk != av->top) {
          nextinuse = inuse_bit_at_offset(nextchunk, nextsize);

          if (!nextinuse) {
            size += nextsize;
            // 更新size
            unlink_chunk (av, nextchunk);
            // 将下一个块从bins中取出
          } else
            clear_inuse_bit_at_offset(nextchunk, 0);
            // 本块即将进入unsorted bin，因此下一个块的prev inuse位取消置位

          first_unsorted = unsorted_bin->fd;

          unsorted_bin->fd = p;
          first_unsorted->bk = p;

          if (!in_smallbin_range (size)) {
            p->fd_nextsize = NULL;
            p->bk_nextsize = NULL;
          }

          set_head(p, size  PREV_INUSE);
          p->bk = unsorted_bin;
          p->fd = first_unsorted;
          set_foot(p, size);
          // 将p使用尾插法加入到unsorted bin的双向循环链表中，同时设置p的size域以及下一个毗邻chunk的prev size域
        }

        else {
          size += nextsize;
          set_head(p, size  PREV_INUSE);
          av->top = p;
          // 如果空闲块与top chunk相邻，则将本块并入到top chunk（不再加入到unsortedbin）
        }

      } while ( (p = nextp) != 0);
      // 内层循环作用为遍历bin中的每一个chunk
    }
  } while (fb++ != maxfb);
  // 这里外层的循环作用为遍历每一个bin（链表）
}

附录

几个重要数据类型以及易混概念

  • 两个空间
    • main_arena结构体本身占据的空间——main_arena是malloc_state这一结构体在libc中的唯一静态实例，它被存放在elf文件的data section，随着elf文件被装载到内存中。
    • 作为主分配区的main arena，它一般是由brk系统调用向内核申请而来（少部分情况下是mmap），是通过扩展data segment得到的一块用户可支配的空间。
  • 三个结构
    • malloc_state中存放着bins以及top chunk的入口，它是我们访问分配区的渠道。
    • tcache_perthread_struct中存放着libc-2.27之后引进的一种特殊的缓存——tcache的入口，它在每一个分配区都有一个实例，存放在每一个分配区的前sizeof(tcache_perthread_struct)（0x280）个字节。
    • malloc_par中存放着一些配置信息，如tcache中bin的个数，top chunk的默认大小（0x20000）等。

ptmalloc初始化流程图

__libc_malloc

注：此处初始化仅仅到进程地址空间中出现主分配区为止

参考文献

https://stackoverflow.com/questions/257418/do-while-0-what-is-it-good-for https://code.woboq.org/userspace/glibc/malloc/arena.c.html https://code.woboq.org/userspace/glibc/sysdeps/nptl/libc-lockP.h.html https://www.cnblogs.com/crunchyou/archive/2013/02/20/2918207.html https://www.cnblogs.com/bbqzsl/p/6764287.html https://developers.redhat.com/blog/2014/10/02/understanding-malloc-behavior-using-systemtap-userspace-probes/ https://developers.redhat.com/blog/2015/01/06/malloc-systemtap-probes-an-example/ https://stackoverflow.com/questions/6338162/what-is-program-break-where-does-it-start-from-0x00 https://lwn.net/Articles/249172/

← Prev roarctf_2019_easy_pwn题解 | Woboq使用指南 Next →