参考：
内容整理自网络和自己的认知，旨在学习交流，请勿用于商业用途。主要本来想把这个系列纳入linux内存管理的，但发现其实malloc并不属于linux内核范畴，内核并没有实现对堆的管理，平常我们调用的malloc来自glibc库编译出来的libc.so，所以便把malloc独立成一个系列了。
另外malloc涉及的内容比较多，也足以写成一个系列了。讲的是malloc的底层实现机制，也可以说是堆的管理机制。这其实也是网络安全中堆漏洞攻击的一项技术，不过我的初衷仅仅是为了更好的使用malloc，而非用来进行黑客攻击。有太多的技术细节没有精力去一一整理，暂时先这样吧，后面有空再完善。
目录 接口介绍 历史 背景知识 设计思路 管理方式 内存块chunk chunk技术分析 隐式链表技术 带边界标记的合并技术 chunk的分类 堆 Arena bin 1、small bin 2、fastbin 3、large bin 4、Unsorted Bin malloc流程 free流程 mallopt函数调整malloc行为或者参数(待完善) malloc提供的回调注册机制 通过程序观察malloc机制 多线程malloc调用观察
接口介绍 大家经常使用的malloc，有多人真正理解其背后的机制。且不说其背后的机制，正确使用其接口对于很多人来说都是个问题。
#include <stdlib.h> void *malloc (size_t size) void free (void *ptr) void *calloc (size_t nmemb, size_t size) void *realloc (void *ptr, size_t size)
malloc分配size字节的内存，并返回指向被分配内存的指针，该块内存未经初始化。如果size=0，可能返回NULL，也可能返回一个唯一的指针值，可以成功传递给free。实际上在内存足够时，malloc(0)返回的是最小malloc_chunk。
free释放ptr所指向的内存空间，ptr必须是返回自malloc(), calloc(), or realloc()的调用，否则，会发生一些未定义的行为，重复调用free也是。
calloc分配nmemb*size字节的内存，并返回指向被分配内存的指针。就是用于分配nmemb个元素大小为size的数组场合。该块内存被初始化为0。size=0同malloc。
realloc改变ptr所指向的内存块的大小为size，[内存起点,min(oldsize，newsize))的内容不会被更改。如果newsize > oldsize，新增的内存未经初始化。如果ptr = NULL，等价于malloc(size)；如size = 0，ptr != NULL，等价于free(ptr);除非ptr = NULL，ptr必须是返回自malloc(), calloc(), or realloc()的调用。
历史 This is a version (aka ptmalloc2) of malloc/free/realloc written by Doug Lea and adapted to multiple threads/arenas by Wolfram Gloger.into glibc in all parts of the code. Do not look for much commonality with the ptmalloc2 version.-20011215 on :2.7 .0 Sun Mar 11 14 :14 :06 2001 Doug Lea (dl at gee)Linux早期的堆分配与回收由Doug Lea实现，但它在并行处理多个线程时，会共享进程的堆内存空间。因此，为了安全性，一个线程使用堆时，会进行加锁。然而，与此同时，加锁会导致其它线程无法使用堆，降低了内存分配与回收的高效性。同时，如果在多线程使用时，没能正确控制，也可能引起内存分配和回收的正确性。
Wolfram Gloger在Doug Lea的基础上进行改进使其可以支持多线程，这个堆分配器就是ptmalloc，其官网：http://www./en/。在glibc-2.3.x之后，glibc中继承了ptmalloc2。
目前Linux标准发行版中使用的堆分配器是glibc中的堆分配器：ptmalloc2。ptmalloc2主要是通过malloc/free函数来分配和释放内存块。
背景知识 进程的虚拟内存布局如下：
设计思路 管理方式 malloc以chunk来标记一个内存块，chunk 中的头一个字是记录前一个 chunk 的大小，第二个字是记录当前 chunk 的大小和一些标志位，从第三个字开始是要分配给应用程序的内存。所以通过内存地址可以找到 chunk ，通过 chunk 也可以找到内存地址。还可以找到相邻的下一个 chunk ，和相邻的前一个 chunk 。怎么找我们下面会说。
chunk以队列的形式进行组织，根据种类的不同，由 3 种队列记录 ，只有空闲 chunk 才会出现在队列中，分配出去的 chunk 不会出现在队列中。如果chunk是空闲的它会挂到其中一个队列中，它是通过内存复用的方式，使用空闲 chunk 的第 3 个字和第 4 个字当作它的前链和后链（变长块是第 5 个字和第 6 个字），省的再分配空间给它。
第一种队列是 bins ， bins 有 125 个队列，前 62 个队列是定长的，一个队列存放的chunk大小相同，相邻队列之间chunk的大小相差8，叫small bins；后面的 63 个队列是不定长的，就是在一个范围长度的都分配在一个队列中，叫large bins。large bins每个队列中的 chunk 都是从小到大排列的。
第二种队列是 unsorted 队列（只有一个队列），（是一个缓冲）所有 free 下来的chunk如果大小不满足fastbin队列，会进入该队列。
第三种队列是 fastbins ，有 10 个定长队列，所有 free 下来的并且长度是小于 80 的 chunk 就会进入这种队列中，相当于一个缓冲池。进入此队列的 chunk 在 free 的时候并不修改使用位，目的是为了避免被相邻的块合并掉。
有人写代码，一个十几字节的结构体也用了malloc，单纯一个内部使用的结构体，就完全没必要调用malloc了，使用局部变量或者静态定义就可以了。使用malloc还得多浪费8/16字节的头，还得增加malloc的调用开销。
还有我们经常要分配一定数目的结构体缓存，分配连续空间的结构体缓存比一个个单独分配的要好。原因很简单，不仅可以节省malloc调用开销，还可以减少malloc chunk自身维护的8/16字节头。
这侧面反映出如果我们知道原理，就知道写出来的代码是好还是坏，知道怎么优化。
接下来我们会介绍一些关键数据结构。
内存块chunk chunk用于标记一块内存块，
struct malloc_chunk {/* Size of previous chunk (if free). */ /* 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 ;
每个成员都是8字节（64位系统中），或者4字节（32位系统中）。
mchunk_prev_size、mchunk_size fd、bk 当前chunk处于分配状态时：
fd_nextsize、bk_nextsize 也是只有chunk空闲的时候才使用，不过其用于较大的chunk（large chunk）
fd_nextsize：指向前一个与当前 chunk 大小不同的第一个空闲块，不包含bin的头指针。
bk_nextsize：指向后一个与当前 chunk 大小不同的第一个空闲块，不包含 bin 的头指针。
关于该结构体的内存复用，我们再解释下：
在分配出去给用户使用的时候，这个头有部分字段就不需要了，只保留前面8个字节，剩下的作为用户的数据部分。也就是说返回给用户的地址为malloc_chunk指针 + 8。也就是说前后向指针fd、bk只有当该chunk块未分配给用户时才存在，用于将该chunk加入到空闲chunk链表中统一管理；而如果该chunk被分配给应用程序使用，那么这两个指针也就没有用了（该chunk块已从空闲链表中移出），所以这两个指针占据的空间也被当作应用程序的使用空间，而不至于浪费。所以我们会看到下面两个图：
分配出去的chunk：
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+| Size of previous chunk, if unallocated (P clear) | | Size of chunk, in bytes | A|M| P| User data starts here... .| (size of chunk, but used for application data) | Size of next chunk, in bytes |A| 0 |1| mem的位置就是返回给用户使用的内存起始位置，前面8字节头是用于管理该内存块。
未分配出去的chunk以双向循环链表的形式进行组织：
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+of previous chunk, if unallocated (P clear) |' | Size of chunk, in bytes |A|0|P| to next chunk in list |to previous chunk in list |0 bytes long ) .' | Size of chunk, in bytes | of next chunk, in bytes |A|0 |0 |
mchunk_size字段不单单用于描述当前chunk的大小，末三位还被征用于描述一些信息：
A =0，表示该chunk在main arena分配。
M =1，表示该chunk通过mmap分配，此时其他位都失效。
P 该位叫PREV_INUSE位，置1是表示前一个chunk已经分配出去。=0时，也就是说前一个chunk是空闲的，mchunk_prev_size才表示前一个chunk的大小。为何如此？这里算是malloc设计上的第二处内存复用。应用程序申请n字节的空间，理论上malloc要分配8 + n字节的空间，这8字节是chunk管理头开销。为了节省内存，malloc分配的chunk大小只有4 + n，还缺4字节，就把下一个chunk的prev_size这个字段利用起来，这样该字段自然就不可用了。所以注释里这么说：
If prev_inuse is set for any given chunk , then you CANNOT determine the size of the previous chunk , and might even get a memory addressing fault when trying to do so.第一个chunk的P位总是置1，因为它前面没有chunk了。
为何mchunk_size表示chunk大小，低三位还能用于存储信息？因为在分配内存时，chunk的对齐单位是8Byte，这样size的低3位就都是0，那么就可以作为其他用途了。
实际上低三位被置位之后，我们想获取chunk的大小时虽不能直接用mchunk_size，但只要屏蔽掉它的低三位就是chunk的大小了：
#define SIZE_BITS (PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA) /* Get size, ignoring use bits */ #define chunksize(p) (chunksize_nomask (p) & ~(SIZE_BITS)) /* Like chunksize, but do not mask SIZE_BITS. */ #define chunksize_nomask(p) ((p)->mchunk_size)
基于这样的设计，我们可以通过当前chunk找到前一个chunk，也能找到下一个chunk。
/* Size of the chunk below P. Only valid if !prev_inuse (P). */ #define prev_size(p) ((p)->mchunk_prev_size) /* Ptr to previous physical malloc_chunk. Only valid if !prev_inuse (P). */ #define prev_chunk(p) ((mchunkptr) (((char *) (p)) - prev_size (p))) /* Ptr to next physical malloc_chunk. */ #define next_chunk(p) ((mchunkptr) (((char *) (p)) + chunksize (p)))
我们也可以得到chunk指针和用户内存指针的转换关系：
/* conversion from malloc headers to user pointers, and back */ #define chunk2mem(p) ((void*)((char*)(p) + 2*SIZE_SZ)) #define mem2chunk(mem) ((mchunkptr)((char*)(mem) - 2*SIZE_SZ)) /* The corresponding word size. */ #define SIZE_SZ (sizeof (INTERNAL_SIZE_T)) 每个平台的size_t大小可能不一样，所以这里通过sizeof来获取。
有许多chunk处理相关的宏，在此不一一贴出。比如我们想要知道当前chunk是否被使用，即它的inuse位是否置位。由于一个chunk的unuse信息存在下一个chunk的chunk_size里，所以我们可以根据偏移关系获取下一个chunk，再获取inuse信息。置位、清除chunk的inuse信息也是如此。
chunk技术分析 待补充。
隐式链表技术 带边界标记的合并技术 chunk的分类 按照认知顺序，不应该先讲chunk的分类，因为你们还有很多概念不知道。所以可以先跳过该小节，回头再来看。
glibc给我们申请的chunk主要分为以下几类：
allocated chunk
free chunk
top chunk
Last remainder chunk
为了简便，我们将4个种类的chunk划分为2个种类的chunk，这两个种类的chunk才是我们平常口头上所使用到的：
allocated chunk：当前chunk是被应用层用户所使用的。free chunk：当前chunk是空闲的，没有被应用层用户所使用。Top Chunk：
概念：当一个chunk处于一个arena的最顶部(即最高内存地址处)的时候，就称之为top chunk。
作用：该chunk并不属于任何bin，而是在系统当前的所有free chunk(无论那种bin)都无法满足用户请求的内存大小的时候，将此chunk当做一个应急消防员，分配给用户使用。
分配的规则：如果top chunk的大小比用户请求的大小要大的话，就将该top chunk分作两部分：1）用户请求的chunk；2）剩余的部分成为新的top chunk。否则，就需要扩展heap或分配新的heap了——在main arena中通过sbrk扩展heap，而在thread arena中通过mmap分配新的heap。
Last Remainder Chunk：
堆 这里的堆的概念有别于我们说的进程的堆，但又有关联，我们进程的堆正是由这么若干个堆组成。
typedef struct _heap_info /* 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 /* Make sure the following data is properly aligned, particularly char pad[-6 * SIZE_SZ & MALLOC_ALIGN_MASK];
可以看到堆也是以链表的形式组织。
待补充。
Arena arena这个概念不好解释，为啥叫arena这么个名字着实不解，其中文意思是圆形运动场所，竞争舞台，竞技场。它是位于堆之上的管理结构，用于管理堆，而堆是管理chunk的结构，这么说大家应该明白了，它是最顶层的管理结构。
malloc_state即Arena的管理结构，或者说是Arena Header。每个thread只含有一个Arena Header。Arena Header包含bins、fastbinsY的信息、top chunk以及最后一个remainder chunk等。arena同样是以链表的形式组织。
每个程序中arena的数量是有限制的，所以过多的线程也不会产生过多的arena，arena的数目限制如下：
32 位系统中：Number of arena = 2 * number of cores - 1. 64 位系统中：Number of arena= 8 * number of cores - 1 应用程序也可以通过调用mallopt(M_ARENA_MAX,value)函数来设置arnea的最大值。
关于arnea的限制逻辑在arena_get2这个arena获取函数里实现。
...static size_t narenas_limit;/* Nothing immediately available, so generate a new arena. */ if (narenas_limit == 0 )if (mp_.arena_max != 0 )//mp_.arena_max是mallopt(M_ARENA_MAX,value)设置的值 else if (narenas > mp_.arena_test)//mp_.arena_test是malloc定义的初始值1，narenas记录系统当前的arnea数目 int n = __get_nprocs ();if (n >= 1 )else /* We have no information about the system. Assume two 2 );
可以看到arenas_limit是个static变量，只会初始化一次，所以要想mallopt(M_ARENA_MAX,value)设置的值生效，要尽早调用。在系统第二次调用arena_get2这个函数后，再来设置M_ARENA_MAX就没用了，因为narenas_limit已经初始化了。个人觉得这样算是设计缺陷。
从上面的公式可以知道，当线程数量超出系统可以提供的arena数量时，就需要一些在概念上类似于在Linux的中锁的机制来实现线程对不同arnea的共享，这在reused_arena里实现。下面进行举例：
演示案例：
第一步：glibc malloc静态定义了一个主竞技场，当主线程首次调用malloc的时候，使用主竞技场。
第二步：当用户线程1和用户线程2首次调用malloc的时候，glibc malloc会分别为每个用户线程创建一个新的线程竞技场。此时，各个线程与arena是一一对应的。
第三步：当用户线程3调用malloc的时候，就出现问题了。因为此时glibc malloc能维护的arena个数已经达到上限，无法再为线程3分配新的arena了，那么就需要重复使用已经分配好的3个竞技场中的一个（主竞技场，竞技场1或者竞技场2）。
此时glibc malloc会做以下操作：
首先，glibc malloc循环遍历（因为是第一次，就从主竞技场开始遍历）所有可用的竞技场，在遍历的过程中，它会尝试锁该竞技场。如果成功锁（该竞技场当前对应的线程并未使用堆内存则表示可锁），那么该竞技场就可以被线程3所使用。
前面提到的主竞技场采用静态定义形式，所以它是位于data段的：
static struct malloc_state main_arena =1 看下我们说了这么久的arena长啥样。
struct malloc_state /* Serialize access. */ /* Flags (formerly in max_fast). */ int flags;/* Set if the fastbin chunks contain recently inserted free blocks. */ /* Note this is a bool but not all targets support atomics on booleans. */ int have_fastchunks;/* Fastbins */ /* Base of the topmost chunk -- not otherwise kept in a bin */ /* The remainder from the most recent split of a small request */ /* Normal bins packed as described above */ 2 - 2 ];/* Bitmap of bins */ unsigned int binmap[BINMAPSIZE];/* Linked list */ struct malloc_state *next ;/* Linked list for free arenas. Access to this field is serialized struct malloc_state *next_free ;/* Number of threads attached to this arena. 0 if the arena is on /* Memory allocated from the system in this arena. */
Main_arena与堆的宏观结构图 Thead_arena与堆的宏观结构图 当一个线程只有一个堆段时： 可以看到该图被分为3部分：
heap_info：表示该堆段的信息，并且该结构体的ar_ptr成员指针指向于该堆段所属的thread arena。
malloc_state：该堆段的竞技场并且top成员指向于最顶端的malloc_chunk
chunk块：就是该堆段所存储的区域
当一个线程含有多个堆段时： 先说什么时候会包含多个堆。就是在之前预分配给该次arena的堆的空间用尽时，会给该次arena创建新的堆。这一点和主arnea略有不同，主arena在其堆的空间用尽时，选择调用sbrk扩大空间；而次arnea的堆空间是用mmap分配的，没法扩充，而且新分配的堆和原来的堆在空间上也不是连续的。
这里头有许多重要的成员，细节我们会在后面介绍。
成员介绍：
last_remainder：当次arena中产生last_remainder时，此成员被初始化，并且指向arnea中的last_remainder
fastbinsY数组：存储的是该领域管理的fastbins
bins数组：存储的是该领域管理的smallbins，unsortedbin，largebins的头结点的两个指针域，
binmap数组：这是一个位图，用于标识bins数组哪些bin链中有块，提高查找效率。
bin 若干个同类的chunk通过链表组织在一起，叫做bin，本质是队列。只有未分配出去的chunk才会由bin来管理。分配出去的chunk会从bin的链表移除，另外chunk的链表域也会被作为用户程序的内存。
代码里有以下几类bin：
Fast bin
Unsorted bin
Small bin
Large bin
bin作为在chunk之上，arnea之下的中间层管理结构，自然由arena管理。
typedef struct malloc_chunk * mchunkptr ;typedef struct malloc_chunk *mfastbinptr ;struct malloc_state /*other member*/ /* Fastbins */ /* Normal bins packed as described above */ 2 - 2 ];/*other member*/ 可以看到有两种类型的bin：
1、small bin /* Normal bins packed as described above */
由于两两一租，所以该数组表示NBINS - 1 条双向链表。NBINS大小为128，第一条链表，用于unsorted bin，2-63用于small bin，64-126用于large bin，只有中间127-1-64=62条链表用于small bin。对于small bin，每一条链表存相同等级大小的chunk。
small bin的chunk大小在512字节以内，
#define in_smallbin_range(sz) \ long ) (sz) < (unsigned long ) MIN_LARGE_SIZE)#define NSMALLBINS 64 #define SMALLBIN_WIDTH MALLOC_ALIGNMENT #define SMALLBIN_CORRECTION (MALLOC_ALIGNMENT > 2 * SIZE_SZ) #define MIN_LARGE_SIZE ((NSMALLBINS - SMALLBIN_CORRECTION) * SMALLBIN_WIDTH)
malloc对分配的内存有对齐要求，在64位系统上是16字节对齐，在8位系统上是8字节对齐，根源在于size_t这个类型的大小不同。
#define MALLOC_ALIGNMENT (2 * SIZE_SZ < __alignof__ (long double) \ long double ) : 2 * SIZE_SZ)MIN_LARGE_SIZE这个宏指定了small bin和large bin的大小分界，不管是在32位系统还是64位系统，它都是512字节，SMALLBIN_CORRECTION用于校正64位系统使计算结果和32位系统一致。
smallbin_index宏用于计算size对应的bins数组中的索引：
#define smallbin_index(sz) \ 16 ? (((unsigned ) (sz)) >> 4 ) : (((unsigned ) (sz)) >> 3 ))\
对于32位系统，每一级大小是：8,16,24，…，512SIZE_SZ index。
bin_at这个宏用于获取头结点，出于节省内存的目的，在设计上十分巧妙。这是malloc的第三处内存复用，也是最经典的内存复用。没有为头结点分配空间，只为头结点的前后向指针分配空间，省去了分配头结点的内存。
/* addressing -- note that bin_at(0) does not exist */ #define bin_at(m, i) \ char *)&((m)->bins[((i) - 1 ) * 2 ])) \struct malloc_chunk, fd))small bin的唯一来源：在malloc函数里，如果fastbin、small bin都没有满足的chunk可用，会遍历unsorted bin查找大小刚好等于请求大小的chunk，如果不等，将其插入到small或者large bin。这也是large bin的唯一来源。
2、fastbin 设计用途或者说设计初衷：这也是fastbins chunk的唯一来源。
缺点：增加内存碎片化，增加程序内存整体占用。
MAX_FAST_SIZE定义了fastbin所能支持的最大分配大小。这个值最大是80，提高这个值会加剧碎片化，并且对于提升内存分配速度并无较大好处。将其设置为0，等于关闭fastbin，这导致malloc算法接近于纯粹fifo算法。
fastbin默认最大chunk是64字节，这个值可以通过mallopt函数设置，然而malloc不会任由用户限制，限制了其最大值为前面说的80。
不会对free chunk进行合并：鉴于设计fast bin的初衷就是进行快速的小内存分配和释放，因此系统将属于fast bin的chunk的PREV_INUSE位总是设置为1，这样即使当fast bin中有某个chunk同一个free chunk相邻的时候，系统也不会进行自动合并操作，而是保留两者。虽然这样做可能会造成额外的碎片化问题，但瑕不掩瑜。
我们一般熟悉的堆都是双链表的chunk，但是对于大小为(16 Bytes~ 64 Bytes)的堆块来说则是使用fastbin来进行管理的。
fastbin的chunk结构与常规的chunk有点不一样，使用的是单链表。
通过这幅图可以看出，原本是双链表（fd和bd）的位置现变成了单链表（fd），即bd被省去了。
而fastbin就是依靠单链表来组织的，堆管理结构始终维护一个指向最后一个chunk的指针(即保存的是链表尾)。这个指针决定了下一次要分配的chunk地址。未被使用的chunk被链入单链表中，单链表的第一个chunk成员的fd值为NULL。
其中最上面的是指向单链表最后chunk块的指针，chunk3因为是第一个chunk所以fd=0。
fastbin是一个简单的索引宏：
typedef struct malloc_chunk *mfastbinptr ;#define fastbin(ar_ptr, idx) ((ar_ptr)->fastbinsY[idx])
这个宏实现将大小转换为数组索引，
/* offset 2 to use otherwise unindexable first 2 bins */ #define fastbin_index(sz) \ int ) (sz)) >> (SIZE_SZ == 8 ? 4 : 3 )) - 2 )在32位系统上SIZE_SZ等于4，从这个转换关系我们可以明白，数组的每一等级大小是：
fastbin数组的大小是个宏NFASTBINS，取决于我们需要的最大等级大小是多少。
#define NFASTBINS (fastbin_index (request2size (MAX_FAST_SIZE)) + 1)
/* The maximum fastbin request size we support */ #define MAX_FAST_SIZE (80 * SIZE_SZ / 4) #define NFASTBINS (fastbin_index (request2size (MAX_FAST_SIZE)) + 1) request2size将大小向上MALLOC_ALIGN_MASK对齐，
#define request2size(req) \
在这里fastbin最大等级大小是88，代入之后可以推断出fastbin数组的大小是10。
fastbinY数组成员类型为chunk指针，我们似乎懂了，每个成员是一条链表，存储相应等级大小的chunk。这里的陷进是这个指针的链表尾，而非链表头。因此，fast bin中无论是添加还是移除fast chunk，都是对“链表尾”进行操作，而不会对某个中间的fast chunk进行操作。
fastbinY数组里的单条链表示意如下：
在malloc分配时，如果fastbin、small bin都没有合适的chunk，会调用malloc_consolidate对全部fastbin进行清理。清理的时候，会先判断它前面的chunk是否空闲，空闲的话合并。再判断该chunk的一下个chunk是top chunk，则将其合并到top chunk；如果不是，则判断这下一个chunk是空闲，空闲的话一并合并再插入unsorted
3、large bin 概念：大于等于512字节的chunk称之为large chunk，large bin就是用于管理这些largechunk的。
我们看下32位机，对齐大小8的情况large bin各个链表的chunk大小范围。
#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 )large bin按大小范围分成了六组：
第二组：[2496 - 10752)
第三组：[10752- 40960)
第四组：[40960 - 163840)
第五组：[163840 - 786432)
第六组：[786432,]
我们来看下large bin链表的结构，相比small bin链表会稍微复杂一些。
4、Unsorted Bin 何时使用：当释放较小或较大的chunk的时候，如果不满足fastbin大小，系统就将这些chunk添加到unsorted bin中。当然，如果释放的chunk的下一个chunk是top chunk，则会和top chunk合并成为新的top chunk，而不会插入到unsorted bin。
目的：这主要是为了让“glibc malloc机制”能够有第二次机会重新利用最近释放的chunk(第一次机会就是fast bin机制)。利用unsorted bin，可以加快内存的分配和释放操作，因为整个操作都不再需要花费额外的时间去查找合适的bin了
malloc流程 函数的分配堆内存的主要执行流程：
④在largebin中寻找可用的chunk来使用
关于malloc主体函数分析细节参考：https://blog.csdn.net/qq_41453285/article/details/99005759。
free流程 0、free(0)直接返回
if (mem == 0 ) /* free(0) has no effect */ return ;
1、将地址转为chunk
#define mem2chunk(mem) ((mchunkptr)((char*)(mem) - 2 * SIZE_SZ)) 即回退2 * SIZE_SZ字节。
2、通过mmap分配的chunk
INTERNAL_SIZE_T size = chunksize(p);uintptr_t mem = (uintptr_t )chunk2mem(p);uintptr_t block = (uintptr_t )p - prev_size(p);size_t total_size = prev_size(p) + size;/* If munmap failed the process virtual memory address space is in a char *)block, total_size);
但是在释放之前，如果用户没有设置过mmap分配阈值，会动态更新mmap分配阈值为此次释放的chunk的大小。也就是会所默认情况下mmap分配阈值是动态变化的。
3、通过sbrk分配的chunk:
1、chunk的size在fastbin范围内，插入到fastbin对应等级链表的头部（LIFO）。
2、大小不满足fastbin，且非mmap映射
top chunk的前一个chunk一定是被使用的，为啥？可以思考下top chunk的来源。
mallopt函数调整malloc行为或者参数(待完善) Tuning options that are also dynamically changeable via mallopt:for 32bit), 128 (for 64bit)switch (param_number)case M_MXFAST://fastbin最大大小 value );break ;case M_TRIM_THRESHOLD:// value );break ;case M_TOP_PAD:value );break ;case M_MMAP_THRESHOLD://mmap调用阈值 value );break ;case M_MMAP_MAX://mmap映射最大次数 value );break ;case M_CHECK_ACTION:value );break ;case M_PERTURB://malloc或者free之后填充的值 value );break ;case M_ARENA_TEST:if (value > 0 )value );break ;case M_ARENA_MAX://arena最大个数 if (value > 0 )value );break ;
malloc提供的回调注册机制 通过在malloc、free之前或者之后打印调试信息或者其他统计操作，可以帮助定位内存泄露问题。我们通常通过修改malloc来实现这一目的。
static int malloc_check = 0 ;void * MemMalloc (int ilen) if (0 == malloc_check )return malloc (ilen);else void *addr = malloc (ilen);//打印信息，或者统计操作 return addr;2、
malloc提供了一组钩子，让用户有途径修改malloc/free/remalloc等接口的实现。所谓的钩子就是回调函数指针。
/* Hooks for debugging and user-defined versions. */ extern void (*__MALLOC_HOOK_VOLATILE __free_hook) (void *__ptr,const void *) extern void *(*__MALLOC_HOOK_VOLATILE __malloc_hook)(size_t __size,const void *)extern void *(*__MALLOC_HOOK_VOLATILE __realloc_hook)(void *__ptr,size_t __size,const void *)extern void *(*__MALLOC_HOOK_VOLATILE __memalign_hook)(size_t __alignment,size_t __size,const void *)extern void (*__MALLOC_HOOK_VOLATILE __after_morecore_hook) (void )
看下malloc函数的开头就知道__malloc_hook钩子的作用了。
void *size_t bytes)//变量定义和assert参数检查 void *(*hook) (size_t , const void *)//钩子是全局函数指针，考虑到多线程多进程，访问时要加锁 if (__builtin_expect(hook != NULL , 0 ))//如果钩子非空，则调用钩子并返回 return (*hook)(bytes, RETURN_ADDRESS(0 ));__free_hook钩子的作用也是一样的，不贴代码了。
通常不会有人闲的蛋疼，自己去实现整个malloc。但是我们有这种需求：想在malloc里加点打印信息。我们可以把__malloc__hook钩子修改成自己的函数，这样子调用malloc时就会调用我们修改后的函数。然而我们没有能力去实现整个malloc，我们在做完自己的事后，重新调用原来的malloc。在重新调用原来的malloc之前，需要把钩子还原回去，不然等下malloc又调用了我们修改的函数。等原来的malloc执行完毕，我们还得把钩子改成我们修改的函数，这样下次malloc时又会进到我们修改后的函数。
我们来演示下通过malloc提供的__malloc_hook、__free_hook钩子在malloc、free加点打印信息。
#include <stdio.h> #include <malloc.h> //加锁解锁暂时省了 #define THREAD_LOCK #define THREAD_UNLOCK static void (*old_free) (void *ptr, const void *caller) static void *(*old_malloc)(size_t size, const void *caller);static void my_free (void *ptr, const void *caller) static void *my_malloc (size_t size, const void *caller) static void hook_back () static void hook_init () static void hook_restore () static void my_free (void *ptr, const void *caller) //要加锁，考虑多线程的话 //这里必须，不然会死循环 printf ('free address: %x\n' , ptr);free (ptr);//重新初始化钩子 return ;static void *my_malloc (size_t size, const void *caller) //要加锁，考虑多线程的话 void *p = NULL ;//这里必须，不然会死循环 malloc (size);printf ('%s-%s-%d:malloc start=%p,size=%d,\n' , __FILE__,__FUNCTION__,__LINE__,p,size);//打印文件名，函数，行号，方便定位问题 //重新初始化钩子 return p;void *(*__MALLOC_HOOK_VOLATILE __malloc_hook) (size_t size, const void *caller) = my_malloc;int main (int argc, char **argv) void *p = malloc (16 );if (p != NULL )free (p);//恢复正常 malloc (24 );if (p != NULL )free (p);return 0 ;
运行结果
root@AI-Machine: /home/hongjh/2019_ project# ./a.out 54 :malloc start=0xb7c00470 ,size=16 ,address: 只有第一次malloc会打印调试信息，调试信息包括分配位置文件名、函数、行号、分配大小、地址，方便定位问题。
通过程序观察malloc机制 #include <malloc.h> #include <unistd.h> struct malloc_chunk {unsigned int mchunk_prev_size; /* Size of previous chunk (if free). */ unsigned int 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 ;typedef struct malloc_chunk * mchunkptr ;#define SIZE_SZ sizeof(unsigned int) #define mem2chunk(mem) ((mchunkptr)((char*)(mem) - 2 * SIZE_SZ)) /* size field is or'ed with PREV_INUSE when previous adjacent chunk in use */ #define PREV_INUSE 0x1 #define prev_inuse(p) ((p)->mchunk_size & PREV_INUSE) /* size field is or'ed with IS_MMAPPED if the chunk was obtained with mmap() */ #define IS_MMAPPED 0x2 /* check for mmap()'ed chunk */ #define chunk_is_mmapped(p) ((p)->mchunk_size & IS_MMAPPED) /* size field is or'ed with NON_MAIN_ARENA if the chunk was obtained #define NON_MAIN_ARENA 0x4 /* Check for chunk from main arena. */ #define chunk_main_arena(p) (((p)->mchunk_size & NON_MAIN_ARENA) == 0) #define SIZE_BITS (PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA) /* Get size, ignoring use bits */ #define chunksize(p) (chunksize_nomask(p) & ~(SIZE_BITS)) /* Like chunksize, but do not mask SIZE_BITS. */ #define chunksize_nomask(p) ((p)->mchunk_size) /* Ptr to next physical malloc_chunk. */ #define next_chunk(p) ((mchunkptr) (((char *) (p)) + ((p)->mchunk_size & ~SIZE_BITS))) //malloc(nbytes)实际分配的大小等于 nbytes+sizeof(size_t)，再对结果向上2*size_t对齐，在32位系统里就是加4，然后8字节对齐。 //nbytes=0时，要满足malloc chunk头的最低开销8字节，8+4再8字节对齐就是16. //nbytes=132,132 + 4,8字节对齐就是136。 int main () void *pret;char *pmem1,*pmem2,*pmem3;0 );printf ('heap start = %p\n' ,pret);char *)malloc (132 );//malloc(0)实际分配的大小是16 printf ('pmem1:%p\n' ,pmem1);printf ('pchunk1 info:\n\tprev_size=%d,size=%d,prev_inuse=%d,arena=%d\n' ,pchunk1->mchunk_prev_size,chunksize(pchunk1),prev_inuse(pchunk1),chunk_main_arena(pchunk1) );0 );printf ('after malloc 132,brk = %p\n' ,pret);printf ('-------------------------\n' );//pchunk1的下一个chunk即topchunk printf ('topchunk info:\n\tprev_size=%d,size=%d,prev_inuse=%d,arena=%d\n' ,topchunk->mchunk_prev_size,chunksize(topchunk),prev_inuse(topchunk),chunk_main_arena(topchunk) );printf ('-------------------------\n' );char *)malloc (132 );printf ('pmem2:%p\n' ,pmem2);printf ('pchunk2 info:\n\tprev_size=%d,size=%d,prev_inuse=%d,arena=%d\n' ,pchunk2->mchunk_prev_size,chunksize(pchunk2),prev_inuse(pchunk2),chunk_main_arena(pchunk2) );0 );printf ('after malloc 132,brk = %p\n' ,pret);printf ('-------------------------\n' );//pchunk2的下一个chunk即topchunk printf ('topchunk info:\n\tprev_size=%d,size=%d,prev_inuse=%d,arena=%d\n' ,topchunk->mchunk_prev_size,chunksize(topchunk),prev_inuse(topchunk),chunk_main_arena(topchunk) );printf ('-------------------------\n' );free (pmem2);//free之后会将chunk2合并到topchunk，所以pmem2所在的chunk2成为新的topchunk //留意chunksize的打印结果，必然会增加136 printf ('topchunk info after free chunk2:\n\tprev_size=%d,size=%d,prev_inuse=%d,arena=%d\n' ,pchunk2->mchunk_prev_size,chunksize(pchunk2),prev_inuse(pchunk2),chunk_main_arena(pchunk2) );printf ('-------------------------\n' );//释放chunk1，继续合并到top chunk free (pmem1);printf ('topchunk info after free chunk1:\n\tprev_size=%d,size=%d,prev_inuse=%d,arena=%d\n' ,pchunk1->mchunk_prev_size,chunksize(pchunk1),prev_inuse(pchunk1),chunk_main_arena(pchunk1) );printf ('-------------------------\n' );//分配一块较大的内存，观察其起始地址，明显和前面的不连续，因为它是在mmap区分配的，而非堆区 malloc (137 *1024 );//4K向上对齐，实际分配了140K，试了136K，也是分140K。 printf ('pmem1:%p\n' ,pmem1);printf ('pchunk1 info:\n\tprev_size=%d,size=%d,prev_inuse=%d,arena=%d\n' ,pchunk1->mchunk_prev_size,chunksize(pchunk1),prev_inuse(pchunk1),chunk_main_arena(pchunk1) );0 );printf ('after malloc 137k,brk = %p\n' ,pret);//brk无变化 printf ('-------------------------\n' );//pchunk1的下一个chunk即topchunk printf ('topchunk info:\n\tprev_size=%d,size=%d,prev_inuse=%d,arena=%d\n' ,topchunk->mchunk_prev_size,chunksize(topchunk),prev_inuse(topchunk),chunk_main_arena(topchunk) );printf ('-------------------------\n' );//暂停执行 free (pmem1);//验证mmap阈值的动态调整，释放之后mmap的阈值更新为140 malloc (137 *1024 );printf ('pmem1:%p\n' ,pmem1);printf ('pchunk1 info:\n\tprev_size=%d,size=%d,prev_inuse=%d,arena=%d\n' ,pchunk1->mchunk_prev_size,chunksize(pchunk1),prev_inuse(pchunk1),chunk_main_arena(pchunk1) );0 );printf ('after malloc 137k,brk = %p\n' ,pret);//brk发生变化 printf ('-------------------------\n' );while (1 );//定住可以看进程的内存映射 return 0 ;
运行结果：
/mnt/nfs # ./a.out start = 0x22000 0x22410 0 ,size =136 ,prev_inuse=1 ,arena=1 after malloc 132 ,brk = 0x43000 ------------------------- 0 ,size =134000 ,prev_inuse=1 ,arena=1 ------------------------- 0x22498 0 ,size =136 ,prev_inuse=1 ,arena=1 after malloc 132 ,brk = 0x43000 ------------------------- 0 ,size =133864 ,prev_inuse=1 ,arena=1 ------------------------- after free chunk2:0 ,size =134000 ,prev_inuse=1 ,arena=1 ------------------------- after free chunk1:0 ,size =134136 ,prev_inuse=1 ,arena=1 ------------------------- 0xb6e36008 0 ,size =143360 ,prev_inuse=0 ,arena=1 after malloc 137 K,brk = 0x43000 ------------------------- 1179403647 ,size =65792 ,prev_inuse=1 ,arena=1 ------------------------- 0x22410 0 ,size =140296 ,prev_inuse=1 ,arena=1 after malloc 132 ,brk = 0x65000 ------------------------- 看下a.out进程的内存映射：
~ # cat /proc/13528/maps --p 00000000 00:10 666275 /mnt/nfs/a.out ---p 0012e000 1f:08 727 /lib/libc-2.24.so --p 0012e000 1f:08 727 /lib/libc-2.24.so --p 00020000 1f:08 765 /lib/ld-2.24.so --p 00000000 00:00 0 [vvar] # /mnt/nfs # ./a.out
在heap下面多了一个区间，大小正好是140K。
b6de0000-b6e03000 rw-p 00000000 00:00 0 我们申请137K内存的返回地址是pmem1:0xb6de0008，刚好相差了8字节偏移，联想到了malloc需要占用8字节的管理头，是不是焕然大悟。
由于我们用getchar暂停了程序的执行，按下回车程序继续执行，我们观察下进程内存空间的变化：
~ # cat /proc/18608/maps --p 00000000 00:10 666275 /mnt/nfs/a.out ---p 0012e000 1f:08 727 /lib/libc-2.24.so --p 0012e000 1f:08 727 /lib/libc-2.24.so --p 00020000 1f:08 765 /lib/ld-2.24.so --p 00000000 00:00 0 [vvar]
发生堆的空间进行了扩展了，印证了
多线程malloc调用观察 /* Per thread arena example. */ #include <stdio.h> #include <stdlib.h> #include <pthread.h> #include <unistd.h> #include <sys/types.h> void * threadFunc (void * arg) printf ('Before malloc in thread 1\n' );char * addr = (char *) malloc (1000 );printf ('After malloc and before free in thread 1\n' );free (addr);printf ('After free in thread 1\n' );int main () pthread_t t1;void * s;int ret;char * addr;printf ('Welcome to per thread arena example::%d\n' ,getpid());printf ('Before malloc in main thread\n' );char *) malloc (1000 );printf ('After malloc and before free in main thread\n' );free (addr);printf ('After free in main thread\n' );NULL , threadFunc, NULL );if (ret)printf ('Thread creation error\n' );return -1 ;if (ret)printf ('Thread join error\n' );return -1 ;return 0 ;下面我们依次分析其各个阶段的堆内存分布状况。
Before malloc in main thread:
在程序调用malloc之前程序进程中是没有heap segment的，并且在创建在创建线程前，也是没有线程堆栈的。
After malloc in main thread:
在主线程中调用malloc之后，就会发现系统给程序分配了堆栈，且这个堆栈刚好在数据段之上：
这就说明它是通过brk系统调用实现的。并且，还可以看出虽然我们只申请了1000字节的数据，但是系统却分配了132KB大小的堆，这是为什么呢？原来这132KB的堆空间叫做arena，此时因为是主线程分配的，所以叫做main arena(每个arena中含有多个chunk，这些chunk以链表的形式加以组织)。由于132KB比1000字节大很多，所以主线程后续再声请堆空间的话，就会先从这132KB的剩余部分中申请，直到用完或不够用的时候，再通过增加program break location的方式来增加main arena的大小。同理，当main arena中有过多空闲内存的时候，也会通过减小program break location的方式来缩小main arena的大小。
After free in main thread:
在主线程调用free之后：从内存布局可以看出程序的堆空间并没有被释放掉，原来调用free函数释放已经分配了的空间并非直接“返还”给系统，而是由glibc 的malloc库函数加以管理。它会将释放的chunk添加到main arenas的bin(这是一种用于存储同类型free chunk的双链表数据结构，后问会加以详细介绍)中。在这里，记录空闲空间的freelist数据结构称之为bins。之后当用户再次调用malloc申请堆空间的时候，glibc malloc会先尝试从bins中找到一个满足要求的chunk，如果没有才会向操作系统申请新的堆空间。如下图所示：
Before malloc in thread1:
在thread1调用malloc之前：从输出结果可以看出thread1中并没有heap segment，但是此时thread1自己的栈空间已经分配完毕了：
After malloc in thread1:
在thread1调用malloc之后：从输出结果可以看出thread1的heap segment已经分配完毕了，同时从这个区域的起始地址可以看出，它并不是通过brk分配的，而是通过mmap分配，因为它的区域为b7500000-b7600000共1MB，并不是同程序的data segment相邻。同时，我们还能看出在这1MB中，根据内存属性分为了2部分：0xb7500000-0xb7520000共132KB大小的空间是可读可写属性；后面的是不可读写属性。原来，这里只有可读写的132KB空间才是thread1的堆空间，即thread1 arena。
在thread1调用free之后：同main thread。
关于源码分析请看这些文章，我就不写了，因为太浪费时间了。
每天进步一点点…
图:二进制人生公众号 
