原文：https://www.yuque.com/hxfqg9/bin/nvrgrs

什么是堆

在程序运行过程中，堆可以提供动态分配的内存，允许程序申请未知的内存。堆其实就是程序虚拟地址空间的一块连续线性区域，它由低地址往高地址增长。我们称管理堆的那部分程序为：堆管理器
堆管理器位于程序与内核之间，主要做：
1、响应用户申请内存的请求
2、管理用户所释放的内存
目前 Linux 标准发行版中使用的堆分配器是 glibc 的堆分配器：ptmalloc2，主要通过 mallo/free 来分配和释放内存块
不同的线程维护不同的堆称为：per thread arena
主线程创建的堆称为：main arena

glibc 的堆管理实现：
arena 指的是堆内存区域本身，并不是结构；主线程的 main arena 通过 sbrk 创建；其他线程的 arena 通过 mmap 创建
malloc_state 管理 arena 的核心结构，包含堆的状态信息、bins 链表等；main arena 对应的 malloc state 结构存储在 glibc 全局变量中；其他线程 arena 对应的 malloc_state 存储在 arena 本身中
bins 用来管理空闲内存块，通常用链表的结构来进行组织
chunks 内存块结构
在内存分配与使用中只有当真正去访问一个地址的时候，系统才会建立虚拟页面与物理内存的映射关系

Arena 头部结构：malloc_state 存储了 arena 的状态，其中的 bins[] 用于管理空闲块的 bins

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

主要关心这么几个：
mfastbinptr fastbinsY[NFASTBINS]，保存了 fastbins 各个链表的数组的头，大小为10 记录的是fast bin链
mchunkptr top，指向了 top chunk
mchunkptr bins[NBINS * 2 - 2]，大小为129。记录的是unsorted bin（1）、small bin（2~63）、large bin链（64~126）

chunk的结构

我们称由 malloc 申请的内存为 chunk，这块内存在 ptmalloc 中被称为 malloc_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;
};

prev_size：如果前一个 chunk 是空闲的话，记录物理相邻前一个 chunk 的大小；否则存储前一个的数据
size：该 chunk 的大小，必须是 2*SIZE_SZ 的整数倍，后三位分别是：

• NON_MAIN_ARENA（A）：表示该 chunk 属于主分配区（1）或者非主分配区（0）
• IS_MAPPED（M）：记录当前 chunk 是否是由 mmap 分配的，M 为 1 表示该 chunk 是从 mmap 映射区域分配的，否则是从 heap 区域分配的
• PREV_INUSE（P）：记录前一个 chunk 块是否被分配。一般来说，堆中第一个被分配的内存块的 size 字段的 P 位都会被设置为 1，以便于防止访问前面的非法内存。当一个 chunk 的 size 的 P 位为 0 时，我们能通过 prev_size 字段来获取上一个 chunk 的大小以及地址。这也方便进行空闲 chunk 之间的合并。

fd、bk：chunk 处于分配时从 fd 字段开始就是用户数据了，chunk 空闲时 会被添加到对应的空闲管理链表中

• fd：指向下一个（非物理相邻）空闲的 chunk
• bk：指向上一个（非物理相邻）空闲的 chunk
• 通过 fd 和 bk 可以将空闲的 chunk 块加入到空闲的 chunk 块链表进行统一管理

fd_nextsize， bk_nextsize，也是只有 chunk 空闲的时候才使用，不过其用于较大的 chunk（large chunk）

• fd_nextsize：指向前一个与当前 chunk 大小不同的第一个空闲块，不包含 bin 的头指针。
• bk_nextsize：指向后一个与当前 chunk 大小不同的第一个空闲块，不包含 bin 的头指针。

一般空闲的 large chunk 在 fd 的遍历顺序中，按照由大到小的顺序排列。这样做可以避免在寻找合适 chunk 时挨个遍历。

使用中的 chunk 结构

一个已经分配的 chunk 的样子如下。我们称前两个字段称为 chunk header，后面的部分称为 user data。每次 malloc 申请得到的内存指针，其实指向 user data 的起始处
chunk 指针指向一个 chunk 的开始，一个 chunk 中包含了用户请求的内存区域和相关的控制信息，图中 mem 指针才是真正返回给用户的内存指针。

空闲中的 chunk 结构

当 chunk 空闲时，其 M 状态不存在，只有 A P 原本是数据区的地方存储四个指针
指针 fd 指向前一个空闲的 chunk，而 bk 指向后一个空闲的 chunk，plmalloc 通过这两个指针将大小相近的 chunk 连成一个双向链表。
对于 large bin 中的空闲 chunk，还有两个指针 fd_nextsize 和 bk_nextsize，这两个指针用于加快 large bin 中查找最近匹配的空闲 chunk 。不同的 chunk 链表又是通过 bins 或者 fastbins 来组织
一般情况下，物理相邻的两个空闲 chunk 会被合并为一个 chunk 。堆管理器会通过 prev_size 字段以及 size 字段合并两个物理相邻的空闲 chunk 块
如果前一个 chunk 处于使用状态，那么不需要去通过链表串起来，所以当前 chunk 也就不需要 prev_size，当申请的内存大小对 2*size_t 取余之后比 size_t 小于等于的话就可以用它的下一个 chunk 的 prev_size
比如：64位下 malloc(0x45)，那 0x45 mod 0x10 还差 0x5，那他就可以用后面一个 chunk 的 prev_size，最后加上 chunk header 大小是 0x50
还是 64 位下，如果大小是 0x49 的话取余之后还差 0x5，那就没法用了，只能多申请一块，最后加上 chunk header 用了 0x60

内存对齐

直接整理个表格

bin

bin链表中指向的是 chunk header
ptmalloc 采用分箱式方法对空闲的 chunk 进行管理。首先，它会根据空闲的 chunk 的大小以及使用状态将 chunk 初步分为 4 类：
fast bins，用于管理较小的 chunk，在之前说的那个 fastbinY 数组里面
small bins，用于管理中等大小的 chunk
large bins，用于管理较大的 chunk
unsorted bin，用于存放未整理的 chunk
bin 对应的数据结构

#define NBINS 128
/* Normal bins packed as described above */
mchunkptr bins[ NBINS * 2 - 2 ];

fastbin

单向链表后进先出，同时 p 位被保留防止合并，同一大小的 chunk 会在同一条链上，不同大小的 chunk 在不同的链上
不同平台大小不同，列一个索引，当 malloc 的大小在这个范围内的时候会首先去 fastbin 中找

unsortedbin

双向循环链表，先进先出，存放所有不满足 fastbin，未被整理的 chunk

malloc 的时候在其他 bin 没找到合适的就会遍历 unsortedbin 同时根据大小放到对应的 bin 里

smallbin

双向链表，先进先出

释放的时候会检查相邻的是不是 free 的，如果是进行合并然后放到 unsortedbin

largebin

双向链表，先进先出

需要根据 fd_nextsize 和 bk_nextsize 指针从大到小排序

tcache

libc2.26 及以后有，先进后出，最大为0x410

每个 tcache bin 最多只能有 7 个，prev_inuse 不会置零，也就是不会进行合并，七个填满之后就跟之前一样了

指针直接指向 chunk 的 userdata 部分

malloc_consolidate功能

1. 首先判断当前 malloc_state 结构体中的 fastbin 是否为空，如果为空就说明整个 malloc_state 都没有完成初始化，需要对malloc_state 进行初始化。
2. malloc_state 的初始化操作由函数 malloc_init_state(av) 完成，该函数先初始化除 fastbins 之外的所有的bins，再初始化 fastbins，清空 fastbins

consolidate情景

1、当去 malloc 一个大于 smallbin 的 chunk 时

将 fastbin 中的 chunk 都整理到 unsortedbin 中，遇到相邻的就合并了，与 topchunk 相邻的就与 topchunk 合并

判断 unsortedbin 中有没有能直接拿来用的，如果有就拿来用，没有就看看有没有能切割的，有的话就切出来拿来用产生 last remainder，同时把 unsortedbin 中的 chunk 整理到对应的 bins 中去，都没有的话就从 topchunk 中找

以下内容复制自：https://blog.csdn.net/sinat_19596835/article/details/81665095

分配过程：

1. ptmalloc在开始时，若请求的空间小于mmap分配阈值（mmap threshold，默认值为128KB）时，主分配区会调用sbrk()增加一块大小为 (128 KB + chunk-size) align 4KB的空间作为heap，若大于mmap分配阈值，则ptmalloc直接使用mmap()映射一块大小为chunk的内存作为heap。非主分配区会调用mmap映射一块大小为HEAP-MAX-SIZE（32位系统上默认为1MB，64位系统上默认为64MB）的空间作为sub-heap。当用户请求内存分配时，首先会在这个区域找一块合适的chunk给用户。当用户释放heap中的chunk时，ptmalloc又会使用fast bins和bins来组织空闲chunk。
2. 若brk!=brk-start，若用户申请内存，先判断所需分配chunk的大小是否满足chunk-size<=max-fast（max-fast默认为64B），如果是的话则转到下一步。
3. 首先尝试在fast bins中取一个所需大小的chunk分配给用户。如果可以找到，则分配结束。否则转到下一步。
4. 判断所需大小是否在small bins中，即判断chunk-size < 512B是否成立。如果chunk大小处在small bins中，则转下一步，否则转6步
5. 根据所需分配的chunk的大小，找到具体所在的某个small bin，从该bin的尾部摘取一个恰好满足大小的chunk。若成功，则分配结束，否则，转到下一步。
6. 到了这一步，说明需要分配的内存较大。ptmalloc首先遍历fast bins中的chunk，并将相邻的chunk进行合并，并链接到unsorted bin中，然后遍历unsorted bin中的chunk，如果unsorted bin只有一个chunk，并且这个chunk在上次分配过程中被使用过，并且所需分配的chunk大小属于small bins，并且chunk的大小大于等于需要分配的大小，这种情况下就直接将该chunk进行切割，分配结束，否则将根据chunk的空间大小将其放入small bins或是large bins中，遍历完成后，转入下一步
7. 到了这一步，说明需要分配的内存较大。或者small bins和unsorted bins中都找不到合适的chunk，并且fast bins和unsorted bins中所有的chunk都清除干净了。从large bins中按照“smallest-first，best-fit”原则，找一个合适的chunk，从中划分一块所需大小的chunk，并将剩下的部分链接回到bins中。若操作成功，则分配结束，否则转到下一步。
8. 如果搜索fast bins和bins都没有找到合适的chunk，那么就需要操作top chunk来进行分配了。判断top chunk大小是否满足所需chunk的大小，如果是，则从top chunk中分出一块来。否则转到下一步。
9. 到了这一步，说明top chunk也不能满足分配要求，所以，于是就有了两个选择: 如果是主分配区，调用sbrk()，增加top chunk大小；如果是非主分配区，调用mmap来分配一个新的sub-heap，增加top chunk大小；或者使用mmap()来直接分配。在这里，需要依靠chunk的大小来决定到底使用哪种方法。判断所需分配的chunk大小是否大于等于 mmap分配阈值，如果是的话，则转下一步，调用mmap分配，否则跳到第11步，增加top chunk 的大小。
10. 使用mmap系统调用为程序的内存空间映射一块chunk_size align 4kB大小的空间。 然后将内存指针返回给用户。
11. 判断是否为第一次调用malloc，若是主分配区，则需要进行一次初始化工作，分配一块大小为(chunk_size + 128KB) align 4KB大小的空间作为初始的heap。若已经初始化过了，主分配区则调用sbrk()增加heap空间，非主分配区则在top chunk中切割出一个chunk，使之满足分配需求，并将内存指针返回给用户。

释放过程

1. 判断传入的指针是否为0，如果为0，则什么都不做，直接return。否则转下一步。
2. 判断所需释放的chunk是否为mmaped chunk，如果是，则调用munmap()释放mmaped chunk，解除内存空间映射，该该空间不再有效，访问该区域会报错。如果开启了mmap分配阈值的动态调整机制，并且当前回收的chunk大小大于mmap分配阈值，将mmap分配阈值设置为该chunk的大小，将mmap收缩阈值设定为mmap分配阈值的2倍（？？没看懂为什么），释放完成，否则跳到下一步。
3. 判断chunk的大小和所处的位置，若chunk_size <= max_fast，并且chunk并不位于heap的顶部，也就是说并不与top chunk相邻，则转到下一步，否则跳到第5步。（因为与top chunk相邻的小chunk也和 top chunk进行合并，所以这里不仅需要判断大小，还需要判断相邻情况）
4. 将chunk放到fast bins中，chunk放入到fast bins中时，并不修改该chunk使用状态位P。也不与相邻的chunk进行合并。只是放进去，如此而已。这一步做完之后释放便结束了，程序从free()函数中返回。
5. 判断前一个chunk是否处在使用中，如果前一个块也是空闲块，则合并。并转下一步。
6. 判断当前释放chunk的下一个块是否为top chunk，如果是，则转第8步，否则转下一步。
7. 判断下一个chunk是否处在使用中，如果下一个chunk也是空闲的，则合并，并将合并后的chunk放到unsorted bin中。注意，这里在合并的过程中，要更新chunk的大小，以反映合并后的chunk的大小。并转到第9步。
8. 如果执行到这一步，说明释放了一个与top chunk相邻的chunk。则无论它有多大，都将它与top chunk合并，并更新top chunk的大小等信息。转下一步。
9. 判断合并后的chunk 的大小是否大于FASTBIN-CONSOLIDATION-THRESHOLD（默认64KB），如果是的话，则会触发进行fast bins的合并操作，fast bins中的chunk将被遍历，并与相邻的空闲chunk进行合并，合并后的chunk会被放到unsorted bin中。fast bins将变为空，操作完成之后转下一步。
10. 判断top chunk的大小是否大于mmap收缩阈值（默认为128KB），如果是的话，对于主分配区，则会试图归还top chunk中的一部分给操作系统。判断top chunk的大小是否大于mmap收缩阈值（默认为128KB），如果是的话，对于主分配区，则会试图归还top chunk中的一部分给操作系统。但是最先分配的128KB空间是不会归还的，ptmalloc 会一直管理这部分内存，用于响应用户的分配请求；如果为非主分配区，会进行sub-heap收缩，将top chunk的一部分返回给操作系统，如果top chunk为整个sub-heap，会把整个sub-heap还回给操作系统。做完这一步之后，释放结束，从 free() 函数退出。可以看出，收缩堆的条件是当前free的chunk大小加上前后能合并chunk的大小大于64k，并且要top chunk的大小要达到mmap收缩阈值，才有可能收缩堆。，ptmalloc 会一直管理这部分内存，用于响应用户的分配请求；如果为非主分配区，会进行sub-heap收缩，将top chunk的一部分返回给操作系统，如果top chunk为整个sub-heap，会把整个sub-heap还回给操作系统。做完这一步之后，释放结束，从 free() 函数退出。可以看出，收缩堆的条件是当前free的chunk大小加上前后能合并chunk的大小大于64k，并且要top chunk的大小要达到mmap收缩阈值，才有可能收缩堆。

呸呸呸，还是得 RTFSC（Read The Fucking Source Code）