Glibc的堆实现

发布于 18 天前  49 次阅读


Glibc的堆实现

在这篇文章中,我们将会介绍Linux操作系统中堆(glibc)的具体实现。本文基本覆盖了glibc 2.30中所有关于堆的操作,然而由于笔者尚未开始对堆利用的学习,在漏洞利用方面的描述不多。当然对于经典的漏洞,笔者或许会略有提及,但这不是本文的目的所在。撰写本文的目的是更深刻的理解源代码中渗透出的计算机思想,为计算机底层开发和日后堆利用的学习打下基础。

注一:由于源代码实现的复杂性和笔者有限的知识,我们在本文中假设只有一个主线程在对堆进行操作,因此只考虑main_arena的情况。对关于线程安全有关的内容,笔者以后会慢慢补充。

注二:文中绝大部分内容来自glibc中的注释和笔者个人的理解。目前尚无对其他资料的引用,若有引用,来源将会在文末放出。

注三:glibc实现堆的源代码中包含大量的交叉引用,笔者无法保证文章中靠前的内容一定不包含未介绍的内容。在这种情况下,推荐善用目录。

堆在哪里?

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

struct mm_struct        *mm;

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

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系统调用的一个封装。其源码如下;

/* 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函数被进行了进一步的封装,代码如下:

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

    return result;
}
MORECORE

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

/* 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
#ifndef MORECORE_CONTIGUOUS
#define MORECORE_CONTIGUOUS 1
#endif

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

基本结构:malloc_chunk

/*
  -----------------------  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域中同时包含了表示该块是否被使用的标志位。

一个被分配的内存块可能具有如下形式:

    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of previous chunk, if unallocated (P clear)  |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of chunk, in bytes                     |A|M|P|
      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             User data starts here...                          .
            .                                                               .
            .             (malloc_usable_size() bytes)                      .
            .                                                               |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             (size of chunk, but used for application data)    |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of next chunk, in bytes                |A|0|1|
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

其中chunk指向的是malloc的代码实现中常常会用到的块的开头,而实际上用户得到的是mem
指向的地址。nextchunk是连续内存中下一个块的开头。

内存块的起始边界总是以偶数字对齐,因此用户得到的mem指针也总是以偶数字对齐(至少是
双字对齐)

空闲块总是被存储在双向循环链表中,它看起来像这样:

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

P标志位(PREV_INUSE)位于块的size域的最低位(由于size总是以双字对齐,因此有未被使用的低位),它标志着上一个块是否被使用。当该位为0时(即上一个块未被使用)size域之前的一个字(prev_size)代表上一个块(是一个空闲块)的大小,以此我们能找到上一个块的开头。最初分配的一个块的P标志位总是为1,以避免我们访问到不存在或者不被当前进程拥有的地址。在任何P标志位为1的块中,你都不能试图获取前一个块的大小,这种操作是无效的,甚至可能引起错误。

A标志位(NON_MAIN_ARENA)用于指示一个块是否在由变量main_arena所描述的最初的主要内存分配区域中。在多线程的环境下,每个线程都有独立的内存分配区域(区域的数量有上限,超过上限会导致分配区域不再接受新线程)。其他线程的分配区域中的块将会把A标志位置位。为了找到这样的一个块从属的分配区域,我们使用heap_for_ptr宏来进行一次掩码操作:

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

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

/* 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_READ|PROT_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

#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

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

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

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

MIN_CHUNK_SIZE

glibc/malloc/malloc.c

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

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

/* 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
/*
   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))

操作malloc_chunk的宏

常量定义
/* 当前一个相邻的块被使用时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)
有关操作

操作很杂,就不再细分了,建议函数中用到的时候再回来看(语句的下方是相应的注释)

#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域(包括标志位),(仅当块空闲时)
链表操作
#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

/* offset 2 to use otherwise unindexable first 2 bins */
#define fastbin_index(sz) \
    ((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)

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

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

glibc/malloc/malloc.c

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

#ifndef M_MXFAST
#define M_MXFAST            1
#endif

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

DEFAULT_MXFAST

glibc/malloc/malloc.c

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

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

set_max_fast

glibc/malloc/malloc.c

/* 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))

拆解:

(
    ((s) == 0)
    ?
    SMALLBIN_WIDTH
    // 最小值,使fastbin无法使用
    :
    (
        (s + SIZE_SZ) & ~MALLOC_ALIGN_MASK
        // 保证对齐,与request2size宏的操作类似
    )
)

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

NFASTBINS

glibc/malloc/malloc.c

#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

/*
static void
malloc_init_state (mstate av)
*/

set_max_fast (DEFAULT_MXFAST);

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

/*
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中堆块的大小大致按照对数分布。

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
/* 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))

拆解:

(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。

                       +-----------------+ This is what we get
                       |
                       |        +--------+ We want this bin
                       |        |
               +---+-------+---+v--+---+
               |   |   |   |   |   |   |
               |   |   |   |   |   |   |
               |   |   |   |   |   |   |
               |   |   |   |   |   |   |
               |fd |bk |fd |bk |fd |bk |
               |   |   |   |   |   |   |
               |   |   |   |   |   |   |
               |   |   |   |   |   |   |
               |   |   |   |   |   |   |
               +-+-+-+-+---+---+---+---+
                 |   |
A bin's header<--+---+
next_bin
/* analog of ++bin */
#define next_bin(b)  ((mbinptr) ((char *) (b) + (sizeof (mchunkptr) << 1)))

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

(
    (mbinptr)
    (
        (char *)
        (b)
        +
        (
            sizeof (mchunkptr) << 1
            // 两个指针大小
        )
        // 加上后相当于在bins中前进了一个bin
    )
)
// 最终得到的是索引为b + 1的bin的指针
first & last
#define first(b)     ((b)->fd)
#define last(b)      ((b)->bk)

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

NBINS & NSMALLBINS
#define NBINS             128
#define NSMALLBINS         64

解释:分别是bins的总数(不包括fastbins)以及small bins的总数

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

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

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

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

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

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

smallbin_index
#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的等差数列

(
    (
        SMALLBIN_WIDTH == 16
        ?
        (
            ((unsigned) (sz)) >> 4
        )
        :
        (
            ((unsigned) (sz)) >> 3)
    ) + SMALLBIN_CORRECTION)
largebin_index_32
#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)

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

(
    (
        (((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
#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
// 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
#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
#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的大小时,它不会被包含在内。

#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.)

/* 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有关
/* 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
#define idx2block(i)     ((i) >> BINMAPSHIFT)

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

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

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

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

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

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

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

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

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

与tcache有关的宏

glibc/malloc/malloc.c

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

解释:tcache bin的默认个数

xsize2tidx
# 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开始是因为这个大小是用户申请的大小)

/* 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
/* 本宏仅仅被用来初始化tunable对象(在一个malloc_par的初始化中)和下面的这个宏 */
# define tidx2usize(idx)        (((size_t) idx) * MALLOC_ALIGNMENT + MINSIZE - SIZE_SZ)

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

MAX_TCACHE_SIZE
# define MAX_TCACHE_SIZE        tidx2usize (TCACHE_MAX_BINS-1)

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

TCACHE_FILL_COUNT
# define TCACHE_FILL_COUNT 7

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

与arena有关的宏

arena_get
/* 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
#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)后边没有分号,这意味着我们可以放心的在使用宏时添加分号以符合我们的直觉,而不必担心宏展开后分号重复。

常用typedef

typedef struct malloc_chunk *mfastbinptr;
typedef struct malloc_chunk* mchunkptr;
typedef struct malloc_chunk *mbinptr;
typedef struct malloc_state *mstate;

常用函数之间的关系

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

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

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函数主要影响的结构体(这两个函数我们都会有详细解释)

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

/* 我们将这个结构放在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

/* 这样的结构在每个线程的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;

全局变量

__malloc_hook

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

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

__malloc_initialized

glibc/malloc/arena.c

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

解释:指示malloc是否已经被初始化

glibc/include/malloc.h

#define __malloc_initialized __libc_malloc_initialized

解释:glic中的一个别名

与arena相关

main_arena
static struct malloc_state main_arena =
{
    .mutex = _LIBC_LOCK_INITIALIZER,
    // 初始化锁,为0
    .next = &main_arena,
    .attached_threads = 1
};

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

thread_arena
static __thread mstate thread_arena attribute_tls_model_ie;

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

Arena free list有关
/* 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_

/* 这是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有关

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函数的一个别名,对该函数的分析有利于我们复习之前提到的宏。

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

/* 检查请求的大小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

/*
  初始化一个 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段

#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

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_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

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

detach_arena

/* 当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

/* 从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

/* Create a new heap.  size is automatically rounded up to a multiple
   of the page size. */

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

  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 = ALIGN_UP (size, pagesize);

  /* A memory region aligned to a multiple of HEAP_MAX_SIZE is needed.
     No swap space needs to be reserved for the following large
     mapping (on Linux, this is the case for all non-writable mappings
     anyway). */
  p2 = MAP_FAILED;
  if (aligned_heap_area)
    {
      p2 = (char *) MMAP (aligned_heap_area, HEAP_MAX_SIZE, PROT_NONE,
                          MAP_NORESERVE);
      aligned_heap_area = NULL;
      if (p2 != MAP_FAILED && ((unsigned long) p2 & (HEAP_MAX_SIZE - 1)))
        {
          __munmap (p2, HEAP_MAX_SIZE);
          p2 = MAP_FAILED;
        }
    }
  if (p2 == MAP_FAILED)
    {
      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);
        }
      else
        {
          /* Try to take the chance that an allocation of only HEAP_MAX_SIZE
             is already aligned. */
          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->mprotect_size = size;
  LIBC_PROBE (memory_heap_new, 2, h, h->size);
  return h;
}

_int_new_arena

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)
    {
      /* Maybe size is too large to fit in a single heap.  So, just try
         to create a minimally-sized arena and let _int_malloc() attempt
         to deal with the large request via mmap_chunk().  */
      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);
  a->attached_threads = 1;
  /*a->next = NULL;*/
  a->system_mem = a->max_system_mem = h->size;

  /* Set up the top chunk, with proper alignment. */
  ptr = (char *) (a + 1);
  misalign = (unsigned long) chunk2mem (ptr) & MALLOC_ALIGN_MASK;
  if (misalign > 0)
    ptr += MALLOC_ALIGNMENT - misalign;
  top (a) = (mchunkptr) ptr;
  set_head (top (a), (((char *) h + h->size) - ptr) | PREV_INUSE);

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

arena_get2

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);
    }
  return a;
}

tcache_init

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

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

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

}

函数主体

下面我们来分析__libc_malloc函数的源码:

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)

结合上面分析的内容,我们可以分析得出在程序中我们第一次调用malloc时实际上调用了两次__libc_malloc,其中第一次调用的流程如下图所示:
malloc初始化

malloc_consolidate函数

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

函数源码

/*
  ------------------------- malloc_consolidate -------------------------

  malloc_consolidate is a specialized version of free() that tears
  down chunks held in fastbins.  Free itself cannot be used for this
  purpose since, among other things, it might place chunks back onto
  fastbins.  So, instead, we need to use a minor variant of the same
  code.
*/

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

  /*
    Remove each chunk from fast bin and consolidate it, placing it
    then in unsorted bin. Among other reasons for doing this,
    placing in unsorted bin avoids needing to calculate actual bins
    until malloc is sure that chunks aren't immediately going to be
    reused anyway.
  */

  maxfb = &fastbin (av, NFASTBINS - 1);
  fb = &fastbin (av, 0);
  do {
    p = atomic_exchange_acq (fb, NULL);
    if (p != 0) {
      do {
        {
          unsigned int idx = fastbin_index (chunksize (p));
          if ((&fastbin (av, idx)) != fb)
            malloc_printerr ("malloc_consolidate(): invalid chunk size");
        }

        check_inuse_chunk(av, p);
        nextp = p->fd;

        /* Slightly streamlined version of consolidation code in free() */
        size = chunksize (p);
        nextchunk = chunk_at_offset(p, size);
        nextsize = chunksize(nextchunk);

        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 in fastbins");
          unlink_chunk (av, p);
        }

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

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

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

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

      } while ( (p = nextp) != 0);

    }
  } while (fb++ != maxfb);
}

参考文献

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/


Sinon想要一个npy