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

0x01 malloc_chunk的基本结构

（使用中/未被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。

0x02 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)

0x03 Bin

一．概述

• 用户释放掉的 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）为例：

[招生]科锐逆向工程师培训(2025年3月11日实地，远程教学同时开班, 第52期)！