什么是堆

在程序运行过程中，堆可以提供动态分配的内存，允许程序申请未知的内存。堆其实就是程序虚拟地址空间的一块连续线性区域，它由低地址往高地址增长。我们称管理堆的那部分程序为：堆管理器

堆管理器位于程序与内核之间，主要做：
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 内存块结构

在内存分配与使用中只有当真正去访问一个地址的时候，系统才会建立虚拟页面与物理内存的映射关系

image.png

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

  1. struct malloc_state
  2. {
  3.   /* Serialize access.  */
  4.   mutex_t mutex;
  5.   /* Flags (formerly in max_fast).  */
  6.   int flags;
  7.   /* Fastbins */
  8.   mfastbinptr fastbinsY[NFASTBINS];
  9.   /* Base of the topmost chunk -- not otherwise kept in a bin */
  10.   mchunkptr top;
  11.   /* The remainder from the most recent split of a small request */
  12.   mchunkptr last_remainder;
  13.   /* Normal bins packed as described above */
  14.   mchunkptr bins[NBINS * 2 - 2];
  15.   /* Bitmap of bins */
  16.   unsigned int binmap[BINMAPSIZE];
  17.   /* Linked list */
  18.   struct malloc_state *next;
  19.   /* Linked list for free arenas.  */
  20.   struct malloc_state *next_free;
  21.   /* Memory allocated from the system in this arena.  */
  22.   INTERNAL_SIZE_T system_mem;
  23.   INTERNAL_SIZE_T max_system_mem;
  24. };

主要关心这么几个：
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 的大小如何，处于分配状态还是释放状态，它们都使用一个统一的结构。虽然它们使用了同一个数据结构，但是根据是否被释放，它们的表现形式会有所不同

  1. /*
  2.   This struct declaration is misleading (but accurate and necessary).
  3.   It declares a "view" into memory allowing access to necessary
  4.   fields at known offsets from a given base. See explanation below.
  5. */
  6. struct malloc_chunk {
  7.   INTERNAL_SIZE_T      prev_size;  /* Size of previous chunk (if free).  */
  8.   INTERNAL_SIZE_T      size;       /* Size in bytes, including overhead. */
  9.   struct malloc_chunk* fd;         /* double links -- used only if free. */
  10.   struct malloc_chunk* bk;
  12.   /* Only used for large blocks: pointer to next larger size.  */
  13.   struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
  14.   struct malloc_chunk* bk_nextsize;
  15. };

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 指针才是真正返回给用户的内存指针。

image.png
image.png

空闲中的 chunk 结构

image.png

当 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
image.png

内存对齐

直接整理个表格

机器类型 64位 32位
对齐位数 16 8
size_t 8 4

bin

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

bin 对应的数据结构

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

fastbin

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

fastbinsY[] x86（size_t=4） x64（size_t=8）
0 0x10 0x20
1 0x18 0x30
2 0x20 0x40
3 0x28 0x50
4 0x30 0x60
5 0x38 0x70
6 0x40 0x80

unsortedbin

双向循环链表，先进先出，存放所有不满足 fastbin，未被整理的 chunk
malloc 的时候在其他 bin 没找到合适的就会遍历 unsortedbin 同时根据大小放到对应的 bin 里

smallbin

双向链表，先进先出
释放的时候会检查相邻的是不是 free 的，如果是进行合并然后放到 unsortedbin
image.png

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）