复习堆的时候发现自己对于堆结构，空间申请与释放，函数调用掌握的还是不够透彻，所以再重新复习一遍堆的数据结构 o3o 也发现了一些以前搞错了很多，害...
本文只捡练了一些（以32位系统为例,64位基本都是对应size*2）

（使用中/未被free）

（空闲chunk/free之后）

1. size字段的低三个比特位对chunk的大小没有影响，他们从高到底分别表示：
   • NONMAINARENA，记录当前 chunk 是否不属于主线程（main_arena），1 表示不属于，0 表示属于。
   • ID_MAPPED，记录当前 chunk 是否是由 mmap 分配的。（chunk空闲时，M不存在）
   • PREV_INUSE，记录前一个chunk是否被分配。1表示被分配，0表示没有。堆的第一个chunk所记录的prev_inuse位默认为1
2. fd_nextsize bk_nextsize在chunk空闲时才使用，（Large bin中特有）暂不讲解。
3. 一般情况下，物理相邻的两个空闲chunk会被合并为一个chunk，堆管理器会通过prev_size字段及size字段合并两个物理相邻的空闲chunk。

空闲时，一个chunk至少需要4个size_t（4B）大小的空间（prev_size, size, fd, bk）共16B，且chunk的大小要对齐到8B。
当一个chunk处于使用状态时，它的下一个chunk的prev_size无效，该prev_size域被当前chunk使用。（可以理解为，当chunk在使用时，在二进制文件中执行，而不归共享库管理，下一个chunk的prev_size域直接分配给当前chunk，可以使内存空间高效利用，也省去重新分配空间的麻烦）
一个使用中的chunk的大小in_use_size = (用户申请大小 + 8 - 4) align to 8B
+8是存储prev_size和size
-4是“借”了下一个chunk的prev_size
最终分配的chunk_size = max(in_use_size, 16)

一．概述

• 用户释放掉的 chunk 不会马上归还给系统，ptmalloc 会统一管理 heap 和 mmap 映射区域中的空闲的 chunk。当用户再一次请求分配内存时，ptmalloc 分配器会试图在空闲的 chunk 中挑选一块合适的给用户。这样可以避免频繁的系统调用，降低内存分配的开销。
• ptmalloc将相似大小的chunk用双向链表链接，此链表称为bin。ptmalloc一共维护了128个bin，并使用一个数组来存储这些bin
• free掉一个chunk时根据chunk大小加入到对应的bin中。

bin[128]中0和127不使用

二．分类

1. fast bins

不大于max_fast（64B）的chunk被释放后，首先会被放到fastbins中，fastbins中的chunk不改变它的Prev_inuse标志，也就无法被合并。
当用户需要的chunk大小 < max_fast时，ptmalloc会首先判断fastbin中相应的bin中是否有对应大小的空闲块（这里比较的是无符号整数），如果有，直接从fastbin头结点开始取chunk。free之后如果再次malloc相同size，会申请到同一块内存。如果没有才会查找bins中的空闲chunk。
在某个特定的时候，ptmalloc会遍历fastbins中的chunk，将相邻的空闲chunk进行合并，并将合并后的chunk加入unsorted bin中，然后再将unsortedbin中的chunk加入bins。

fast bin为单链表。采用LIFO（Last In First Out）。fastbins cache了 small bins的前7个大小的空闲chunk，对于 SIZE_SZ 为 4B 的平台【16B，24B，32B，40B，48B，56B，64B】；对 于 SIZE_SZ 为 8B 的平台【32B，48B，64B，80B，96B，112B，128B】

当每次释放的 chunk 与该 chunk 相邻的空闲 chunk 合并后的大小大于 64k 时，就认为内存碎片可能比较多了，就需要 把 fast bins 中的所有 chunk 都进行合并，以减少内存碎片对系统的影响

2. unsorted bins

如果被用户释放的chunk > max_fast（64B），或者fastbins中的空闲chunk合并后，这些chunk首先会被放入unsorted bin
malloc时如果fastbin中没有合适的chunk，就会在unsorted bin中查找合适的。如果unsorted bin中没有合适的chunk，就将unsorted bin中的chunk放到所属的bin中再分配。
可以把unsorted bins理解为缓冲区。

unsorted bin为bin[1]，其中的chunk没有排序，大小不限制，双链表，成环。采用FIFO。

3. small bins

small bin为索引2到63，大小为（2 SIZE_SZ ndx）（即 size < 512B），双链表，成环。采用FIFO。
实际共62个bin，同一个small bin 链表中的 chunk 的大小相同。两个相邻索引的 small bin 链表中的 chunk 大小32 位相差 8 字节【16B, 24B, 32B, ..., 504B】，64 位相差 16 字节【32B, 48B, 64B, ..., 1008B】
分配时采用精确匹配。

4. large bins

large bin为索引64到126，大小为[512,512+64)（即 size >= 512B）。
一共包括63个bin，每个 bin 中的 chunk 的大小不一致，而是处于一定区间范围内。此外，这 63 个 bin 被分成了 6 组，每组 bin 中的 chunk 大小之间的公差一致。
以32位平台（SIZE_SZ = 4B）为例：

large bins 中的每一个 bin 都包含一定范围内的 chunk，其中的 chunk 按 fd 指针的顺序从大到小排列。相同大小的 chunk 同样按照最近使用顺序排列。
分配时采用最近匹配。

——上述这些 bin 的排布都会遵循一个原则：任意两个物理相邻的空闲 chunk 不能在一起。

需要注意的是，并不是所有的 chunk 被释放后就立即被放到 bin 中。ptmalloc 为了提高分配的速度，会把一些小的 chunk先放到 fast bins 的容器内。而且，fastbin 容器中的 chunk 的使用标记总是被置位的，所以不满足上面的原则。

并不是所有的chunk都按照上面的方式组织。以下是三种特殊的chunk，他们不属于任何bins。

top chunk

对于非主分配区预先从mmap分配一块较大的sub-heap，heap 会被分为两块，一块给用户，剩下的那块就是 top chunk。其实，所谓的 top chunk 就是处于当前堆的物理地址最高的 chunk。【因为内存是按地址从底向高进行分配的】
这个 chunk 不属于任何一个 bin，它的作用在于当所有的 bin 都无法满足用户请求的大小时，如果其大小不小于指定的大小，就进行分配，并将剩下的部分作为新的 top chunk。否则，就重新分配一个sub-heap，并将top chunk迁移到新的sub-heap上再分配。
top chunk分配内存会使top chunk减小。如果回收的chunk恰好与top chunk相邻，那么合并成新top chunk使top chunk变大。
如果free时回收的内存大于某个阈值，且top chunk大小也超过的收缩阈值，ptmalloc就会收缩sub-heap。如果top chunk包含了整个sub-heap，ptmalloc会调用munmap把整个sub-heap返回操作系统。

主分配区是唯一能够映射进程heap区域的分配区（有点难理解。。。）在 main arena 中通过 sbrk 扩展收缩 heap，ptmalloc会预先分配一块较大的空闲内存（heap）
主分配区的top chunk第一次malloc时会分配一块(chunk_size + 128KB) align 4KB大小的空间作为初始heap，用户从top chunk分配内存时，可直接取出一块给用户。如果top chunk中没有空闲内存，ptmalloc会调用sbrk()将进程heap边界brk上移，然后修改top chunk大小。回收时，回收的内存恰好与top chunk相邻则合成新top chunk。
如果free时回收的内存大于某个阈值，且top chunk大小也超过的收缩阈值，会收缩内存，但至少保留一个页大小的空闲内存，从而把内存归还操作系统。

mmaped chunk（略）

chunk足够大时，以上的都不能满足分配需求时，ptmalloc会使用mmap直接使用内存映射来将页映射到进程空间。这样分配的chunk在被free时将直接接触映射，将内存归还给操作系统，若再次对这样的内存引用将导致segmentation fault。

last remainder chunk（略）

需要分配一个small chunk，但small bins中找不到合适的chunk，如果last remainder chunk的大小 > 所需的small chunk大小，就将它分裂成两个chunk，其中一个chunk返回用户，另一个变成新的last remainder chunk。

内存分配：_int_malloc

根据size

• 获取分配区的锁（略，想了解看源码分析）
• 将用户请求的大小转换为实际需要分配的chunk_size
• fastbin range：chunk_size <= max_fast，从fast bin中查找是否有合适的chunk。
  • 找到，分配结束。
  • 未找到 ⬇
• small bin range：chunk_size < 512B，先从small bin查找（small bin按照size排好，查找更快）按照size从对应具体的small bin的尾部找到恰好满足大小的chunk。
  • 找到，分配结束。
  • 未找到 ⬇
• ptmalloc首先遍历fast bins中的chunk，将相邻chunk合并，并链接到unsorted bin。
• 遍历unsorted bin。
  • 如果unsorted bin只有一个chunk，并且该chunk在上次分配时被使用，所需分配的chunk大小属于small bins，且该chunk大小 >= 需要分配的大小，直接切割，分配结束。（丢，好绕）
  • 否则，根据chunk大小放入small bins或large bins中。⬇
• large bin range：从large bin 中查找满足条件且最小的chunk。
  • 有则切分，剩下的部分链接回bins中，剩余的放入unsorted bin//这是ptmalloc机制，他在分配large chunk时会先对堆中的碎片chunk进行合并，以便减少堆中的碎片
  • 未找到 ⬇
• 从top chunk切割
  • 满足，分配结束
  • 不满足 ⬇
• 当topchunk也无法满足时，如果是主分配区，调用sbrk()增加top chunk大小。如果是非主分配区，调用mmap()
  【mmap的具体分配方法 略】

内存回收：free

• 1. 获取分配区锁
• 1. 检测传入free的指针是否为0
  • 是，直接return
  • 否，⬇
• 1. 是否是mmap分配
  • 是，释放mmap的chunk
  • 否，⬇
• 1. size是否属于fast bin且chunk并不位于heap顶部，也就是不与top chunk相邻
  • 是，插入fast bin，return
  • 否，⬇
• 1. 查看前一个chunk是否free
  • 是，合并，⬇
• 1. 查看下一个chunk是否为top chunk
  • 是，合并，更新top chunk大小，⬇
  • 否，->7
• 1. 查看下一个chunk是否free
  • 是，合并
• 1. 判断合并后的 chunk 的大小是否大于 FASTBIN_CONSOLIDATION_THRESHOLD（默认 64KB）
  • 是，触发进行 fast bins 的合并操作，fast bins 中的 chunk 将被 遍历，并与相邻的空闲 chunk 进行合并，合并后的 chunk 会被放到 unsorted bin 中。 fast bins 将变为空，⬇
• 1. 判断 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 收缩阈值，才有可能收缩堆

arena的个数是跟系统中处理器核心个数相关

For 32 bit systems:
     Number of arena = 2 * number of cores.
For 64 bit systems:
     Number of arena = 8 * number of cores.

main_arena

main_arena表示主分配区，任何进程有且仅有一个全局的主分配区

参考：CTF-wiki堆，glibc内存管理ptmalloc2源码分析

2020安全开发者峰会（2020 SDC）议题征集 中国.北京 7月！

最后于 2020-3-7 11:28 被plkk编辑 ，原因：