参考：cyberangel
与栈由高地址向地址值增长不同，堆由地址值向高地址增长，如图：
heap在函数调用malloc（brk增加）之后才会被分配
堆内存管理的两种系统调用：(s)brk和mmap
(s)brk通过改变程序间断点位置，从而改变数据段长度，来分配内存
mmap通过在堆和栈之间找的一段空闲内存分配，并初始化为0
当用户申请一段大于128kb的内存时选择mmap而不是(s)brk,
zhihu
同理，当空闲内存过多时(s)brk也会通过改变自己指向的地址以缩减空余内存
内存分配有以下特点：
1.具有长生命周期的大内存分配使用mmap
2.特别大的内存分配使用mmap
3.具有短生命周期的内存分配使用(s)brk
4.尽量只缓存临时使用的空闲小内存快，对大内存块或是长生命周期的大内存块在释放时都直接归还给操作系统
5.对空闲的小内存块只会在malloc和free的时候进行合并，free时空闲内存块可能放入内存池中，不一定归还给操作系统
6.收缩堆的条件时当前free的块大小加上前后能合并的chunk的大小大于64k，并且堆顶大小达到阈值，才有可能收缩堆，把堆最顶端的空闲内存返回给操作系统
主线程首次调用malloc分配的内存也叫做main arena，非主线程malloc时产生thread arena
如果main arena内存时通过mmap向系统分配的，free时会直接调用munmap将该内存归还给系统
而free调用之后不仅会清空堆块的user data，还会将指向该堆块的指针存储到main_arena中（或是fastbin，注意指针和地址区别开，地址存放的指针，64位指针8字节，一个 arena 顶部的 chunk 叫做 Top chunk，它不属于任何 bin。当所有 bin 中都没有空闲的可用 chunk 时，我们切割 Top chunk 来满足用户的内存申请。假设 Top chunk 当前大小为 N 字节，用户申请了 K 字节的内存，那么 Top chunk 将被切割为：
一个 K 字节的 chunk，分配给用户
一个 N-K 字节的 chunk，称为 Last Remainder chunk
后者成为新的 Top chunk。如果连 Top chunk 都不够用了，那么：
在 main_arena 中，用 brk() 扩张 Top chunk
在 non_main_arena 中，用 mmap() 分配新的堆
对于堆中最小内存管理单位，chunk来说，分为allocated chunk，free chunk，top chunk，Last remainder chunk四种chunk，但又可以分为allocated chunk和free chunk两种，无论一个 chunk 的大小如何，处于分配状态还是释放状态，它们都使用一个统一的结构
/*
This struct declaration is misleading (but accurate and necessary).
It declares a "view" into memory allowing access to necessary
fields at known offsets from a given base. See explanation below.
*/
struct malloc_chunk {
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. */
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;
};
- allocated chunk：
allocated chunck就是已经分配给用户的 chunk，其图示如下：
chunk：该 Allocated chunk 的起始地址；
mem：该 Allocated chunk 中用户可用区域的起始地址（= chunk + sizeof(malloc_chunk)）；
next_chunk：下一个 chunck（无论类型）的起始地址。
在图中，chunk 指针指向一个 chunk 的开始，一个 chunk 中包含了用户请求的内存区域和相关的控制信息。图中的 mem 指针才是真正返回给用户的内存指针。chunk 的第二个域的最低一位为 P，它表示前一个块是否在使用中，P 为 0 则表示前一个 chunk 为空闲，这时chunk 的第一个域 prev_size 才有效，prev_size 表示前一个 chunk 的 size，程序可以使用这个值来找到前一个 chunk 的开始地址。当 P 为 1 时，表示前一个 chunk 正在使用中，prev_size无效，程序也就不可以得到前一个chunk的大小。不能对前一个chunk进行任何操作。ptmalloc分配的第一个块总是将 P 设为 1，以防止程序引用到不存在的区域。
Chunk 的第二个域的倒数第二个位为 M，他表示当前 chunk 是从哪个内存区域获得的虚拟内存。M 为 1 表示该 chunk 是从 mmap 映射区域分配的，否则是从 heap 区域分配的。Chunk 的第二个域倒数第三个位为 A，表示该 chunk 属于主分配区或者非主分配区，如果属于非主分配区，将该位置为 1，否则置为 0。
- free chunk：
prev_size: 两个相邻 free chunk 会被合并成一个，因此该字段总是保存前一个 allocated chunk 的用户数据；
size: 该字段保存本 free chunk 的大小；
fd: Forward pointer —— 本字段指向同一 bin 中的下个 free chunk（free chunk 链表的前驱指针）；
bk: Backward pointer —— 本字段指向同一 bin 中的上个 free chunk（free chunk 链表的后继指针）。
当 chunk 空闲时，其 M 状态不存在，只有 AP 状态，原本是用户数据区的地方存储了四个指针，指针 fd 指向后一个空闲的 chunk，而 bk 指向前一个空闲的 chunk，ptmalloc 通过这两个指针将大小相近的 chunk 连成一个双向链表。对于 large bin 中的空闲 chunk，还有两个指针，fd_nextsize 和 bk_nextsize，这两个指针用于加快在 large bin 中查找最近匹配的空闲chunk。不同的 chunk 链表又是通过 bins 或者 fastbins 来组织的
- bin:
用户释放掉的 chunk 不会马上归还给系统，ptmalloc 会统一管理 heap 和 mmap 映射区域中的空闲的 chunk。当用户再一次请求分配内存时，ptmalloc 分配器会试图在空闲的 chunk 中挑选一块合适的给用户。这样可以避免频繁的系统调用，降低内存分配的开销。
ptmalloc 将相似大小的 chunk 用双向链表链接起来，这样的一个链表被称为一个 bin。Ptmalloc 一共 维护了 128 个 bin，并使用一个数组来存储这些 bin
fastbin:
共有10个fastbin
管理 16、24、32、40、48、56、64 Bytes 的 free chunks（32位下默认）
其中的 chunk 的 in_use 位（下一个物理相邻的 chunk 的 P 位）总为1
当用户申请一个小于等于64bytes的空间时会首先检查对应大小的fastbin中是否包含未被使用的chunk，如果存在则直接将其从fastbin中移除并返回；否则通过其他方式（剪切top chunk）得到一块符合大小要求的chunk并返回
small bin：
如果程序请求的内存范围不在 fast bin 的范围内，就会考虑 small bin。简单点说就是大于 80 Bytes 小于某一个值时，就会选择它。
unsorted bin：
当 fast bin、small bin 中的 chunk 都不能满足用户请求 chunk 大小时，堆管理器就会考虑使用 unsorted bin 。它会在分配 large chunk 之前对堆中碎片 chunk 进行合并，以便减少堆中的碎片。
unsorted bin 与 fast bin 不同，他使用双向链表对 chunk 进行连接
unsorted 的字面意思就是” 不可回收” 的意思，可以看作将不可回收的垃圾（不满足能够进行内存分配的堆块）都放到这个” 垃圾桶” 中。
large bin：
当 fast bin、small bin 中的 chunk 都不能满足用户请求 chunk 大小时，就会考虑是不是 large bin。但是，其实在 large bin 中并没有直接去扫描对应 bin 中的 chunk，而是先利用 malloc_consolidate（参见 malloc_state 相关函数） 函数处理 fast bin 中的 chunk，将有可能能够合并的 chunk 先进行合并后放到 unsorted bin 中，不能够合并的就直接放到 unsorted bin 中，然后在大循环中进行相应的处理。