文章连接 ： 《堆的相关数据结构》
参考：
1.ctf.wiki : 堆相关数据结构 - CTF Wiki
2.星盟pwn佬 : 0011.哔哩哔哩-【个人向】CTF pwn 入门-P11[高清版]_哔哩哔哩_bilibili
- malloc_chunk
- 概念：
通过malloc申请的内存称为chunk，也可以将chunk称作堆的一个单位(自己随意理解)。
free掉的chunk将会被加入到相应的空闲管理列表中，简称为XX bin,大致分为四类，unsorted bin，small bin，fast bin，large bin。
下面介绍malloc_chunk的统一结构。具体表现根据是否被释放会有所不同。
主要结构：
struct malloc_chunk {
INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */
INTERNAL_SIZE_T size; /* Size in bytes, including overhead. */
// 由于 chunk 的大小必为8的整数倍，故 size的值的莫3bits必为0
// 为了不浪费这3bits，设计者为他们赋予了特殊作用
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;
};chunk_header : 前两个字段为chunk头，即为prev_szie和size
user_data : 除去chunk_header即为数据区，每次malloc申请的chunk其实指向user_data的起始部 分.
对每一部分进行解释：
- prev_size: 记录该chunk物理相邻的上一个free_chunk(较低地址)的大小,若上一个chunk被利用了，那么prev_size就可以用来存储上一个chunk的数据,即称为prev_size的复用。
- size： 代表本chunk的大小，其中需要注意chunk的大小必须是 2*SIZE_SZ 的整数倍，不满足的也会被转化为其的整数倍。其中SIZE_SZ代表最小内存单元，32位系统是4，64位系统是8。特别注意该字段的低三比特位对chunk大小没有影响。
原因：拿64位举例，由于size遵循着分配的原则，即0x10字节的整数倍，也可以说至少要是8字节的整数倍，那么也就说明了低三比特位一定为0，若为100，则会出现一个4出来，不满足分配规则，那着三比特位就该浪费掉吗？其实不然。
作用：
低三比特位从高到低位A,M,P。
-
-
- A：ARENA-> 记录当前chunk是否在主线程，1->不属于,0->属于1.
- M：mmap-> 记录当前chunk是否由mmap分配
- P： prev_inuse->记录前一个chunk是否被分配。1->被分配，0->没有被分配。P为0时可以通过prev_size获得前一个chunk的大小和地址。便于空闲chunk合并
-
以上二者如下图：
当chunk被free后,就会多出 fd，bk，fd_nextsize， bk_nextsize
- fd,bk: 指针类型。chunk空闲时，通过fd,bk指针连接成逻辑链表。从fd开始就是数据了。
-
- fd: forword,即指向下一个free_chunk->chunk_header的地址
- bk: backword,即指向上一个free_chunk->chunk_header的地址
- fd_nextsize， bk_nextsize：large bin中具有该部分.
-
- fd_nextsize 指向前一个与当前 chunk 大小不同的第一个空闲块，不包含 bin 的头指针。
- bk_nextsize 指向后一个与当前 chunk 大小不同的第一个空闲块，不包含 bin 的头指针。
- 一般空闲的 large chunk 在 fd 的遍历顺序中，按照由大到小的顺序排列。这样做可以避免在寻找合适 chunk 时挨个遍历。
补充知识：
- chunk header 和 user data图示：
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
header | Size of previous chunk, if unallocated (P clear) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of chunk, in bytes |A|M|P|
mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| User data starts here... .
. .
. (malloc_usable_size() bytes) .
next . |
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| (size of chunk, but used for application data) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of next chunk, in bytes |A|0|1|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- free chunk的合并
图中是small bin(unsorted bin)中chunk的合并，当下一个free chunk的p->0，即两个物理相邻的chunk都是free chunk,那么这两个free chunk会被合并。
- chunk -> size的大小
我们已经知道size代表的是该chunk的大小，这里阐述size跟malloc(参数) 其中参数的关系。
举例：64位操作系统，malloc(0x100):
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
void *ptr = malloc(0x100);
free(ptr);
}通过gdb调试，发现此时的chunk size 为0x111
为什么呢？ 其实malloc(参数),该参数代表的是数据内容，没有包括prev_size和size这两个控制字段，加上这两个控制字段，那么size就是0x100+0x10=0x110,那还有个1是哪来的，size的低三比特位中的p记录的是物理相邻上一个chunk是否被利用，gdb图中发现确实被利用了，所以该chunk_size中的P记为1，如图：
上述内容也可以印证malloc返回的指针指向user_data的起始地址。
- bin
前面也提到过bin，，用户释放掉的 chunk 不会马上归还给系统,ptmalloc会统一管理这些空闲的chunk,这些空闲的chunk会被"丢到"bin中，也就是空闲的chunk管理仓库，根据空闲的 chunk 的大小以及使用状态将 chunk 初步分为 4 类：fast bins，small bins，large bins，unsorted bin。在每类 bin 的内部仍然会有多个互不相关的链表(双向链表)来保存不同大小的 chunk。
bin的实现其实是一个数组。
注：下面只介绍四种bin中chunk的结构，关于bin更复杂的内容可以看开头参考的ctf.wiki。
- Fast Bin
（1）产生缘由：一些较小的chunk被free之后，chunk_size低三比特位中P=0，该chunk会与相邻的free_chunk合并，那么在下次malloc申请合适大小chunk的时候，便会对合并的free_chunk进行分割，分割出相应大小的chunk,那么像这样的每次分割就不fast了，因此啊，fast bin就产生了，如图可以发现该chunk_size中P=1，这是不会改变的，为的就是防止该chunk被free后与相邻free_chunk合并。
chunk_size范围：既然是fast,那么它的chunk是有大小限制的，只有在这个范围内的chunk被free后才会进入到fastbin，64位情况下，chunk_size的范围是0x20-0x80(包括chunk_header)，32位对半砍就是。该范围可以gdb调试，步过到malloc之后，然后输入fastbin，就会出现范围。
由于本人是ubuntu20.04,其是glibc2.31,版本过高，先free掉的chunk储存在新的bin结构：tcachebins
关于这个可以参考：关于如何理解Glibc堆管理器(Ⅶ——Tcache Bins!!)_tcachebins-CSDN博客
但是一般的题目还是不会用到这个新的bins。
（2）分配原则：采取LIFO策略，先进先出，即先释放的chunk将会被更早的分配。当malloc的chunk的大小 <= fastbin的max，那么ptmalloc就会先在fastbin找有没有合适的free_chunk,有的话就给malloc，没有的话就从其他bin中找。
释放chunk的时候，ptmaolloc会先将一些小的chunk放入fastbin中。
（3）异于其他：bin中是单向链表，因为"缺少"bk指针（并不是缺少，而是不会用到，因为fastbin中的chunk还可能会被分到small bin中去）
以下三种bin(s)都是双向链表，大概如下：
2.Unsorted Bin
(1)特点：位于bin数组下标1的位置，bins[1]。unsorted bin只有一项，其内容就是字面意思，没有分类的bin。chunk大小没有要求。
（2）来源：释放的chunk的size大于fastbin，并且该chunk不与top chunk紧邻，那么该chunk就会放到unsorted bin中。
3.small Bin
- bins[2] -- bins[63]
- 62个循环双向链表，每一个链表中的chunk大小都是一致的。32位系统下，bin[2]储存16字节的chunk，bin[3]储存24字节......504bytes , chunk_size = 2 * SIZE_SZ * bin_index。
- FIFO（队列形式）
注：可以发现small bin和fast bin对于chunk_size是有重合的
4.Large Bin
- bin[64] -- bin[126]
- 63个循环双向链表，每一个bin中chunk大小不一致，处于一定范围内。(详情见参考)
- 管理大于504bytes(user_data)的free_chunks(32位),第一个larbin的起始chunk_size=512字节
- FIFO（队列形式）
- Top Chunk
- 内容：当程序第一次malloc的时候，heap会被分为两部分，一部分给用户，另外一部分就是top chunk，其地址处于当前堆的最高物理地址。
- 本质上是free_chunk,会和上面的free_chunk合并
- 该chunk不被放入bin中当用户区域的bin满足不了用户申请的大小，并且chunk大小合适，才会从这部分分配chunk,剩下没被分配的重新作为top chunk。若是top chunk也不满足用户所申请的内存大小，就会扩展heap。
- Last_remainder_chunk
用户在malloc申请分配内存的时候，ptmalloc找到的chunk会按照fastbin -> unsorted bin -> small bins -> Large bins顺序去寻找free_chunk，只要size大小大于等于所申请的，就会将这段chunk给用户，而此时给的chunk可能和比申请的大，那么ptmalloc会将这部分chunk分割，只会给用户合适的chunk，那么剩下的部分就被称为last remainder chunk。
注：top chunk 分割剩下的部分不会作为 last remainder 。上面提到了，就是新的top chunk
实操理解：
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
void *ptr = malloc(0x20);
free(ptr);
}gdb调试图：
如图是可以看到Top chunk的size，并且它的物理地址确实位于当前堆的最高物理地址。可以分析这三个chunk_size之和（不包括P位的1），刚好就是所分配的heap大小。
- malloc_state
该结构是用来管理堆的，记录每个arena当前申请的内存的具体状态。每个arena都只有一个malloc_state结构。
注：main arena 的 malloc_state 并不是 heap segment 的一部分，而是一个全局变量，存储在 libc.so 的数据段。
struct malloc_state {
/* Serialize access. */
__libc_lock_define(, mutex);
/* Flags (formerly in max_fast). */
int flags;
/* Fastbins */
mfastbinptr fastbinsY[ NFASTBINS ];
// fastbin就储存在其中
/* 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 ];
// 该bins中储存的上面说的三种bin
/* Bitmap of bins, help to speed up the process of determinating if a given bin is definitely empty.*/
unsigned int binmap[ BINMAPSIZE ];
/* Linked list, points to the next arena */
struct malloc_state *next;
/* Linked list for free arenas. Access to this field is serialized
by free_list_lock in arena.c. */
struct malloc_state *next_free;
/* Number of threads attached to this arena. 0 if the arena is on
the free list. Access to this field is serialized by
free_list_lock in arena.c. */
INTERNAL_SIZE_T attached_threads;
/* Memory allocated from the system in this arena. */
INTERNAL_SIZE_T system_mem;
INTERNAL_SIZE_T max_system_mem;
};解释：
- fastbinsY[ NFASTBINS ]：
-
- 存放每个 fast chunk链表头部的指针
- top
-
- 指向Top chunk
- last_reminder
-
- 最新的 chunk 分割之后剩下的那部分
- bins[ NBINS * 2 - 2 ]
-
- 用于储存unsorted bin,small bins和Large bins的chunk链表
- binmap[ BINMAPSIZE ]
-
- ptmalloc用一个 bit 来标识某一个 bin 中是否包含空闲 chunk 。