堆内存管理介绍
dlmalloc – General purpose allocator
**ptmalloc2 – glibc**
jemalloc – FreeBSD and Firefox
tcmalloc – Google
libumem – Solaris本文主要学习介绍在linux glibc使用的ptmalloc2实现原理。
本来linux默认的是dlmalloc，但是由于其不支持多线程重新加载，所以后来被多线程的ptmalloc2代替了。当然在linux平台*malloc本质上都是通过brk和mmap实现的。关于这部分内容，一定要学习下面这篇文章：
鉴于篇幅，本文就不加以详细说明了，只是为了更方便对堆内存管理的理解，截取其中函数调用关系图：
图1-1 函数调用关系图
系统内存分布图：
图1-2 系统内存分布图
Arena介绍
Arena数量限制
在main thread和thread1有自己独立的arena，那么是不是无论多少线程，每个线程都有自己独立的arena呢？答案是否定的。事实上，arena是个跟系统中处理器核心个数有关的，如下表所示：
For 32 bit systems:
Number of arena = 2 * number of cores + 1.
For 64 bit systems:
Number of arena = 8 * number of cores + 1.
Arena数量限制
假设有如下情景：一台只含有一个处理器核心的PC机安装有32位操作系统，其上运行一个多线程应用程序，共含有4个线程—主线程和三个用户线程。显然线程个数大于系统能维护的最大arena个数（2*核心数+1=3），那么此时的glibc malloc就需要确保这4个线程能够正确共享这3个arena，那么它是如何实现的呢？
当主线程首次调用malloc的时候，glibc malloc会直接为它分配一个main arena，而不需要任何附加条件。
当用户线程1和用户线程2首次调用malloc的时候，glibc malloc会分别为每个用户线程创建一个新的thread arena。此时，各个线程与arena是一一对应的。但是，当用户线程3调用malloc的时候，就会出问题了。因为此时glibc malloc能维持的arena个数已经达到上限，无法再为线程3分配新的arena了，那么久需要重复使用分配好的3个arena中的一个(main arena，arena 1或者arena 2)。那么该选择哪个arena进行重复利用呢？
1）首先，gblic malloc循环遍历所有可用的arenas，在遍历的过程中，他会尝试lock该arena。如果成功lock(该arena 当对应的线程并未使用堆内存则表示可lock)，比如将main arena成功lock住，那么就将main arena返回给用户，即表示该arena被线程3共享使用。
2）而如果没能找到可用的arena，那么就将线程3的malloc操作阻塞，直到有可用的arena为止。
3）现在，如果线程3再次调用malloc的话，glibc malloc就会先尝试使用最近访问的arena（此时为main arena）。如果此时main arena可用的话，就直接使用，否则就将线程3阻塞，直到main arena再次可用为止。
这样线程3与主线程就共享main arena了。至于其他更复杂的情况，以此类推。
堆管理介绍
整体介绍
在glibc malloc中针对堆管理，主要涉及到以下3种数据结构：
heap_info
即Heap header，因为一个thread arena(注意：不包含main thread) 可以包含多个heaps，所以为了便于管理，就给每个heap分配一个heap header。那么在什么情况下一个thread arena会包含多个heaps呢。在当前heap不够用的时候，malloc会通过系统调用mmap申请新的堆空间，新的堆空间会被添加到当前thread arena中，便于管理。
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;
malloc_state
即Arena Header，每个thread只含有一个Arena Header。Area Header包含bins信息，top chunk以及最后一个remainder chunk等。
struct malloc_state
{
/* Serialize access. */
mutex_t mutex;
/* Flags (formerly in max_fast). */
int flags;
/* Fastbins */
mfastbinptr fastbinsY[NFASTBINS];
/* Base of the topmost chunk -- not otherwise kept in a bin */
mchunkptr top;
/* The remainder from the most recent split of a small request */
mchunkptr last_remainder;
/* Normal bins packed as described above */
mchunkptr bins[NBINS * 2 - 2];
/* Bitmap of bins */
unsigned int binmap[BINMAPSIZE];
/* Linked list */
struct malloc_state *next;
/* Linked list for free arenas. */
struct malloc_state *next_free;
/* Memory allocated from the system in this arena. */
INTERNAL_SIZE_T system_mem;
INTERNAL_SIZE_T max_system_mem;
};
malloc_chunk
即Chunk Header，一个header被分为多个chunk，至于每个chunk的大小，这里根据用户的请求决定的，也就是说用户调用malloc(size)传递的size参数“就是”chunk的大小（这里给“就是”加上引号，说明这种表示并不正确，但是为了方便立即就暂时这么描述了，详细说明见后文）。每个chunk都由一个结构体malloc_chunk表示：
struct malloc_chunk {
/* #define INTERNAL_SIZE_T size_t */
INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */
INTERNAL_SIZE_T size; /* Size in bytes, including overhead. */
struct malloc_chunk* fd; /* double links -- used only if free. 这两个指针只在free chunk中存在*/
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;
};可能有很多读者会疑惑：该结构体里面没有一个类似data的字段来表示用户申请到的堆内存空间啊？且该结构体明确含有2个size_t类型的成员，4个指针，这不是意味着malloc_chunk的大小是固定的了么？那它又如何能够根据用户的请求分配不同大小的内存呢？要想回答清楚这个问题，需要我们完全理解这个glibc malloc的堆内存管理机制，同时，本文的主要目的之一就是希冀清楚这个概念。
NOTE:
1，main thread不含有多个heaps所以也就不含有heap_info结构体。当需要更多堆空间的时候，就通过扩展sbrk的heap segment来获取更多的空间，直到它碰到内存mapping区域为止。
2，不同于thread arena，main arena的arena header并不是sbrk heap segment的一部分，而是一个全局变量！因此它属于lib.so的data segment。
heap segment与arena关系
首先，通过内存分布图解释清malloc_state与heap_info之间的组织关系。
下面是只有一个heap segment的main arena和thread arena的内存分布图：
下面是一个thread arena中含有多个heap segments的情况：
上图可以看出，thread arena只含有一个malloc_state（即arena header），却有两个heap_info(即heap header)。由于两个heap segment是通过mmap分配内存，两者heap segments是通过mmap分配的内存，两者在内存布局上并不相邻而是分属于不同的内存区间，所以为了便于管理，libc malloc将第二个heap_info结构体的prev成员指向第一个heap_info结构体的起始位置（即ar_ptr成员），而第一个heap_info结构体的ar_ptr成员指向了malloc_state，这样就构成一个单链表，方便以后管理。
对chunk的理解
在glibc malloc中将整个堆内存空间分成连续的，大小不一的chunk，即对于堆内存管理而言chunk就是最小操作单位。chunk总共分成4类：1）allocated chunk; 2)free chunk; 3)top chunk; 4)Last remainder chunk。从本质上来说，所有类型的chunk都是内存中一块连续的区域，只是通过该区域中特定位置的某些标识符加以区分。为了简便，我们先将这4类chunk简化为2类：allocate chunk以及free chunk，前者标识已经分配给用户使用的chunk，后者表示未使用的chunk。
隐式链表技术
前文说过，任何堆内存管理器都是以chunk为单位进行堆内存管理的，而这就需要一些数据结构来标志各个块的边界，以及区分已经分配块和空闲块。大多数堆内存管理都将这些边界信息作为chunk的一部分嵌入到chunk内部，典型的设计如下所示：
简单的allocated chunk格式：
简单的free chunk格式：
堆内存中要求每个chunk的大小必须为8的整数倍，因此chunk size的后3位是无效，为了充分利用内存，堆管理奖这3个bit比特位用作chunk的标志位，典型的就是将第0比特位用于标记该chunk是否已经被分配。这样的设计很巧妙，因为我们只要获取一个指向chunk size的指针，就能知道该chunk的大小，即确定了此chunk的边界，且利用chunk size的第0比特位还能知道chunk是否已经分配，这样就成功将各个chunk区分开来。注意在allocated chunk中的padding部分主要用于地址对齐的，即让整个chunk的大小为8个整数倍。
通过上面的设计，我们能将整个堆内存组织成一个连续的已分配或未分配chunk序列：
上面的这种结构就叫做隐式链表，该链表隐式地由每个chunk的size字段链接起来，在进行分配操作的时候，堆内存管理器可以通过遍历整个堆内存的chunk，分析每个chunk的size字段，进而找到合适的chunk。
问题：这种隐式链表效率其实相当低的，特别是在内存回收方面，它难以进行相邻多个free chunk的合并操作，我们知道，如果只对free chunk进行分割，而不进行合并的话，就会产生大量小的，无法继续使用的内存碎片，直至整个内存消耗殆尽。因此堆内存管理设计了带边界标记的chunk合并技术。
带边界标记的合并技术
试想如下场景：假设我们要释放的chunk为P，它紧邻的前一个chunk为FD，紧邻的后一个chunk为BK，且BK与FD都为free chunk。将P于BK合并在一起时很容易的。因为可以通过P的size字段轻松定位到BK的开始位置，进而获取BK的size等等，但是将P于FD合并却很难，我们必须从头遍历整个堆，找到FD，然后加以合并，这就是意味着每次进行chunk释放操作消耗的时间与堆的大小成线性关系。为了解决这个问题，Knuth提出了一种聪明而通用的技术——边界标记。
Knuth在每个chunk的最后添加开一个脚部（Footer），它就是该chunk头部（Header）的一个副本，我们称之为边界标记。
显然每个chunk的脚部都在其相邻的下一个chunk头部的前4个字节处。通过这个脚部，堆内存管理器就可以很容易地得到前一个chunk的起始位置和分配状态，进而进行合并了。
但是，边界标记同时带来一个问题：它要求每个块都包含一个头部和脚部，如果应用程序频繁地进行小内存的申请和释放操作的话（比如1，2字节），就会造成很大的性能消耗。同时，考虑到只有对free chunk进行合并的时候才需要脚部，也就是对于allocated chunk而言它并不需要脚部，因此我们可以对这个脚部加以优化——将前一个chunk的已分配/空闲标记位存储在当前chunk的size字段的第1，或2比特位上，这样如果我们通过当前chunk的size字段就知道前一个chunk为free chunk，那么久可以得出结论：当前chunk地址之前的4个字节为前一个free chunk的脚部，我们可以通过脚部获取前一个chunk的起始位置；如果当前chunk的size字段表明前一个chunk是allocated chunk的话，那么就可以得出另一个结论：前一个chunk没有脚部，即当前chunk地址之前的4个字节为前一个allocated chunk的payload或padding的最后部分。新的chunk格式图如下：
改进版的Knuth边界标记allocated chunk格式：
再进化——支持多线程
随着技术的发展，特别是堆内存管理器添加堆多线程的支持，前述的chunk格式已经难以满足需求，比如，我们需要标记位来标记当前chunk是否属于非主线程即thread arena，以及该chunk由mmap得来还是通过brk实现等等。但此时chunk只剩下一个比特位没有使用了，怎么办？这需要对chunk格式进行大手术！
首先思考：是否有必要同时保存当前chunk和前一个chunk的已分配/空闲标记位？答案是否定的，因为我们只需要保存前一个chunk的分配标记位就可以了，至于当前chunk的分配标记位，可以通过查
下一个
chunk的size字段得到。那么size字段中剩下的两个比特位就可以用于满足多线程的标记需求了：
多线程版本Knuth边界标记free chunk格式
这里的P,M,N的含义如下：
-
PREV_INUSE(P)
：表示前一个chunk是否为allocated。 -
IS_MMAPPED(M)
：表示当前chunk是否是通过mmap系统调用产生的。 -
NON_MAIN_ARENA(N)
：表示当前chunk是否是thread arena。
再进一步，发现没有必要保存chunk size的副本，也就是说Footer的作用并不大，但是如果前一个chunk是free的话，在合并的时候我们又需要知道前一个chunk的大小，怎么办？将Footer从尾部移到首部，同时其不再保存当前chunk的size，而是前一个free chunk的size不就行了。同样，为了提高内存利用率，如果前一个chunk是allocated chunk的话，这个Footer就作为allocated chunk的payload或padding的一部分，结果图如下：
当前glibc malloc free chunk格式
至此，glibc malloc堆内存管理器中使用的隐式链表技术介绍完毕了。现在我们再回头去看看malloc_chunk结构就很好理解了：该结构体通过每个chunk的pre_size和size构成了隐式链表，而后续的fd，bk等指针并不是作用于隐式链表的，而是用于后文会介绍的用于加速内存分配和释放效率的显示链表bin，并且这些指针跟prev_size一样只在free_chunk中存在。
Top Chunk
当一个chunk处于arena的最顶部(即最高内存地址处)的时候，就称之为top chunk。该chunk并不属于任何bin，而是在系统当前的所有free chunk都无法满足用户请求的内存大小的时候，将此chunk当做一个应急消防员，分配给用户使用。如果top chunk的大小比用户请求的要大的话，就将该top chunk分作两部分:1）用户请求的chunk；2）剩余的部分为新的top chunk。否则，就需要扩展heap或分配新的heap了——在main arena中通过sbrk扩展heap，而在thread arena中通过mmap分配新的heap。
Last Reminder Chunk
要想理解此chunk就必须先理解glibc malloc中的bin机制。如果你已经看了第二部分稳重，那么下面的原理就很好理解了，否则建议你先阅读第二部分文章。对于Last remainder chunk，我们主要有两个问题：1）它是怎么产生的；2）它的作用是什么？
先回答第一个问题。当用户请求一个small chunk，且该请求无法被small bin，unsorted bin满足的时候，就通过bin maps遍历合适的chunk，如果该chunk有剩余部分的话，就将剩余部分变成一个新的chunk加入到unsorted bin中，另外，再将该新的chunk变成新的last remainder chunk。
然后回答第二个问题。此类型的chunk用于提高连续malloc的效率，主要是提高内存分配的局部性。那么具体是怎么提高局部性的呢？举例说明。当用户请求一个small chunk，且该请求无法被small bin满足，那么就转而交由unsorted bin处理。同时，假设当前unsorted bin中只有一个chunk的话——就是last remainder chunk，那么就将chunk分成两部分：前者分配给用户，剩下的部分放到unsorted bin中，并成为新的last remainder chunk。这个就保证了连续malloc(small chunk)中，各个small chunk在内存分布中是相邻的，即提高内存分配的局部性。