本篇主要参考了https://xz.aliyun.com/t/10650?page=1
对其中的知识点进行了理解和重新排序，便于对其更好的理解
0x00 堆的数据结构，申请与释放
堆和栈都是一种数据结构，在内存中线性分布储存数据，栈由高地址向低地址伸展，堆由低地址向高地址伸展。堆的位置一般都在bss段的高地址处。
在程序运行过程中，堆可以提供动态分配的内存，允许程序申请大小未知的内存。堆其实就是程序虚拟地址空间的一块连续的线性区域，它由低地址向高地址方向增长。我们一般称管理堆的那部分程序为堆管理器。
目前 Linux 标准发行版中使用的堆分配器是 glibc 中的堆分配器：ptmalloc2。ptmalloc2 主要是通过 malloc/free 函数来分配和释放内存块。
在真正了解堆之前，需要以下基础知识：
0x01 arena
arena包含一片或者数片连续的内存，对快将会从这片区域中划分给用户。主线程的arena被称为main_arena，它包含start_brk 和 brk之间的这片连续内存。一般把start_brk 和 brk之间这片连续的内存称为堆。
主线程arena只有堆，子线程的arena可以有数片连续的内存。如果主线程的堆大小不够分的话，就要通过brk函数调用来扩展，但是子线程分配的映射段大小是固定的，不可以扩展的，所以子线程分配处理的一段映射段不够用的话就需要再次使用mmap函数来分配新的内存。
0x02 bin & chunk
chunk
chunk是glibc管理内存的基本单位，整个堆在初始化后会被当成一个free chunk，称为top chunk，每次用户请求内存时，如果bins中没有合适的chunk，malloc就会从top chunk中进行划分，如果top chunk的大小不够，就调用brk函数扩展堆的大小，然后从新生成的top chunk中进行划分。用户释放内存时，glibc会先根据情况将释放的chunk与其他相邻的free chunk合并，然后加入合适的bin中。
chunk的数据结构如下
struct malloc_chunk{
INTERNAL_SIZE_T mchunk_prev_size; 记录被释放的相邻chunk的大小。
INTERNAL_SIZE_T mchunk_size; 记录当前chunk的大小，chunk的大小都是8字节对齐
struct malloc_chunk *fd;
struct malloc_chunk *bk;
struct malloc_chunk *fd_nextsize;
struct malloc_chunk *bk_nextsize;
}
根据chunk的结构可知，最小的chunk为0x20（x86下为0x10）。
首先在x64下，一个地址的内存大小就为0x8，那么一个最小的chunk，用pre size记录上一个chunk大小，用size记录自己的大小，size下面是一个fd，再下面是data，所以如果要最小的话，一共是4个0x8，那么就是0x20的大小。
那么同理，在x86下，一个地址的内存大小为0x4，所以就是上述的一半，既最小的堆在x86中就是0x10的大小。
bin
管理arena中空闲chunk的结构，以数组的形式存在，在数组元素为相应大小的chunk链表的链表头存在于arena的malloc_state中
保管用户暂时不需要的内存空间，当用户需要重新申请内存的时候，就不需要向操作系统要新的内存空间了，如果回收站中有正好满足你需求的空间，就把那份空间分配给你就可以了。
根据chunk的大小，将bin如下进行分类
-
Fast bin（单向链表）
Fast bin分类的chunk的大小为32-128字节(0x80)字节，如果chunk在被释放时发现其大小满足这个要求，则将该chunk放入Fast Bin。一个最新被加入的Fast Bin的chunk，其fd指针指向上一次加入的Fast Bin的chunk的pre size。
-
Small bin（双向链表）
Small bin保存大小为32-1024（0x400）字节的chunk，每个放入其中的chunk为双链表结构，不同大小的chunk储存在对应的链接中。由于是双链表结构，所以他的速度比fast bin慢一些。
-
Large bin（双向链表）
大于1024字节的chunk使用Large Bin进行管理。相同大小的Large Bin使用fd和bk指针连接，不同大小的Large bin通过fd_nextsize和bk_nextsize按大小排序连接。
-
Unsorted Bin（双向链表）
Unsorted Bin相当于Ptmalloc2堆管理器的垃圾桶。chunk被释放后，会先加入Unsorted Bin中，等待下次分配使用。在堆管理器的Unsorted Bin不为空的时候，用户申请非Fast Bin大小内存会先从Unsorted Bin中查找，如果找到符合该申请的chunk(等于或者大于)，则直接分配或者分割该chunk。
0x03 malloc
在glibc的malloc中，有以下说明：
malloc 函数返回对应大小字节的内存块的指针。
当 n=0 时，返回当前系统允许的堆的最小内存块
当 n 为负数时，由于在大多数系统上，size_t 是无符号数（这一点非常重要），所以程序就会申请很大的内存空间，但通常来说都会失败，因为系统没有那么多的内存可以分配。
malloc --> __libc_malloc --> _int_malloc
__libc_malloc(size)
用户申请的字节一旦进入申请内存函数中就变成了 无符号整数。
寻找钩子hook ----》 寻找arena ----》 调用_int_malloc分配内存 -+--》成功，返回内存
↑ |
| ↓
+-----分配失败，再寻找一个arena
_int_malloc()
--------------------------------------------------------------------------------
将size转化为对应的chunk大小 ----》 fastbin ----》 遍历（后进先出），检查大小是否符合 ----》 符合则计算索引 ----》 chunk转换为内存返回
根据大小选择bin ----》 smallbin ----》获取索引、指针 ----》 检查该bin是否为空 ----》 不为空 ----》将链表中最后一个chunk分配（先进先出）
| +----》 初始化
+---》 该bin为空
----》 不在fastbin和smallbin中 ----》 malloc_consolidate()：处理fastbin ----》 可以合并的合并，然后放 unsorted bin ----》大循环
----------------------------------------------------------------------------------
大循环 ----》 遍历unsorted bin ----》 FIFO寻找大小刚好合适的bin ----》若有，bin转为内存后返回
循环10000次 ----》若没有，则将当前的unsorted bin按照大小放至对应的small或large中
----》 遍历large bin ----》对应的 bin 中从小(链表尾部)到大（头部）进行扫描 ----》 找到第一个合适的返回
----》 若大小合适的bin都不存在，则在map中找更大的bin遍历 ----》 找到，返回内存
----》 找不到，使用top chunk ----》 满足，分割后返回
----》 不满足，使用 sysmalloc 来申请内存
------------------------------------------------------------------------------------
//从 fastbin 的头结点开始取 chunk（LIFO）
0x04 _libc_malloc
一般我们会使用 malloc 函数来申请内存块，可是当仔细看 glibc 的源码实现时，其实并没有 malloc 函数。其实该函数真正调用的是 **libc_malloc 函数。为什么不直接写个 malloc 函数呢，因为有时候我们可能需要不同的名称。此外，**libc_malloc 函数只是用来简单封装 _int_malloc 函数。_int_malloc 才是申请内存块的核心。下面我们来仔细分析一下具体的实现。
该函数会首先检查是否有内存分配函数的钩子函数（__malloc_hook），这个主要用于用户自定义的堆分配函数，方便用户快速修改堆分配函数并进行测试。这里需要注意的是，用户申请的字节一旦进入申请内存函数中就变成了无符号整数。
// wapper for int_malloc
void *__libc_malloc(size_t bytes) {
mstate ar_ptr;
void * victim;
// 检查是否有内存分配钩子，如果有，调用钩子并返回.
void *(*hook)(size_t, const void *) = atomic_forced_read(__malloc_hook);
if (__builtin_expect(hook != NULL, 0))
return (*hook)(bytes, RETURN_ADDRESS(0));
接着会寻找一个arena来试图分配内存
arena_get(ar_ptr, bytes);
然后调用 _int_malloc 函数去申请对应的内存。
victim = _int_malloc(ar_ptr, bytes);
如果分配失败的话，ptmalloc 会尝试再去寻找一个可用的arena，并分配内存。
/* Retry with another arena only if we were able to find a usable arena before */
if (!victim && ar-ptr != NULL)
{
LIBC_PROBE(memory_malloc_retry, 1, bytes);
ar_ptr = arena_get_retry(ar_ptr, bytes);
victim = _int_malloc(ac_ptr, bytes);
}
如果申请到了arena，那么在退出之前还得解锁。
if (ar_ptr != NULL) __libc_lock_unlock(ar_ptr->mutex);
判断目前的状态是否满足以下条件
- 要么没有申请到内存
- 要么是 mmap 的内存
- 要么申请到的内存必须在其所分配的 arena 中
0x05 _int_malloc
_int_malloc 是内存分配的核心函数，其核心思路有如下
- 它根据用户申请的内存块大小以及相应大小 chunk 通常使用的频度（fastbin chunk, small chunk, large chunk），依次实现了不同的分配方法。
- 它由小到大依次检查不同的 bin 中是否有相应的空闲块可以满足用户请求的内存。
- 当所有的空闲 chunk 都无法满足时，它会考虑 top chunk。
- 当 top chunk 也无法满足时，堆分配器才会进行内存块申请。
在进入该函数后，函数立马定义了一系列自己需要的变量，并将用户申请的内存大小转换为内部的 chunk 大小。
- fast bin
如果申请的 chunk 的大小位于 fastbin 范围内，需要注意的是这里比较的是无符号整数。此外，是从 fastbin 的头结点开始取 chunk。
- large bin
当 fast bin、small bin 中的 chunk 都不能满足用户请求 chunk 大小时，就会考虑是不是 large bin。但是，其实在 large bin 中并没有直接去扫描对应 bin 中的 chunk，而是先利用 malloc_consolidate（参见 malloc_state 相关函数） 函数处理 fast bin 中的 chunk，将有可能能够合并的 chunk 先进行合并后放到 unsorted bin 中，不能够合并的就直接放到 unsorted bin 中，然后再在下面的大循环中进行相应的处理。为什么不直接从相应的 bin 中取出 large chunk 呢？这是 ptmalloc 的机制，它会在分配 large chunk 之前对堆中碎片 chunk 进行合并，以便减少堆中的碎片。
- unsorted bin 大循环 - 遍历
如果程序执行到了这里，那么说明 与 chunk 大小正好一致的 bin (fast bin， small bin) 中没有 chunk 可以直接满足需求 ，但是 large chunk 则是在这个大循环中处理。
在接下来的这个循环中，主要做了以下的操作
- 按照 FIFO 的方式逐个将 unsorted bin 中的 chunk 取出来
- 如果是 small request，则考虑是不是恰好满足，是的话，直接返回。
- 如果不是的话，放到对应的 bin 中。
- 尝试从 large bin 中分配用户所需的内存
该部分是一个大循环，这是为了尝试重新分配 small bin chunk，这是因为我们虽然会首先使用 large bin，top chunk 来尝试满足用户的请求，但是如果没有满足的话，由于我们在上面没有分配成功 small bin，我们并没有对 fast bin 中的 chunk 进行合并，所以这里会进行 fast bin chunk 的合并，进而使用一个大循环来尝试再次分配 small bin chunk。
- 使用 top chunk
如果所有的 bin 中的 chunk 都没有办法直接满足要求（即不合并），或者说都没有空闲的 chunk。那么我们就只能使用 top chunk 了。
0x06 free
在glibc中的free，有以下说明：
- free 函数会释放由 p 所指向的内存块。这个内存块有可能是通过 malloc 函数得到的，也有可能是通过相关的函数 realloc 得到的。
- 当 p 为空指针时，函数不执行任何操作。
- 当 p 已经被释放之后，再次释放会出现乱七八糟的效果，这其实就是
double free。 - 除了被禁用 (mallopt) 的情况下，当释放很大的内存空间时，程序会将这些内存空间还给系统，以便于减小程序所使用的内存空间。
free --> __libc_free --> _int_free
_int_free()
检查 ----》是否fastbin ----》是fastbin，放至fastbin链表表头
+---》是否mmap分配 ----》 是，munmap_chunk()
+---》 否，合并chunk ----》 向低地址合并 ----》想高地址合并 ----》 下一个是否是top chunk ----》 是，合并到top chunk
0x10 示例（brk、sbrk）
0x11 brk & sbrk
对于堆的操作，操作系统提供了 brk 函数，glibc 库提供了 sbrk 函数，我们可以通过增加 brk的大小来向操作系统申请内存。
初始时，堆的起始地址 start_brk以及堆的当前末尾 brk指向同一地址。根据是否开启 ASLR，两者的具体位置会有所不同
- 不开启 ASLR 保护时，start_brk 以及 brk 会指向 data/bss 段的结尾。
- 开启 ASLR 保护时，start_brk 以及 brk 也会指向同一位置，只是这个位置是在 data/bss 段结尾后的随机偏移处。
0x12 example
/* sbrk and brk example*/
#include<stdio.h>
#include<unistd.h>
#include<sys/types.h>
int main()
{
void *curr_brk, *tmp_brk = NULL; //创立空指针
printf("Welcome to sbrk example:%d\n",getpid()); //读取heap,pid
/* sbrk(0) gives current program break location */
tmp_brk = curr_brk = sbrk(0); //通过sbrk空指针赋值
printf("Program Break Location1:%p\n", curr_brk);
getchar();
/* brk(addr) increments/decrements program break location */
brk(curr_brk+4096);
curr_brk = sbrk(0);
printf("Program Break Location2:%p\n" ,curr_brk);
getchar();
brk(tmp_brk);
curr_brk = sbrk(0);
printf("Program Break Location3:%p\n", curr_brk);
getchar();
return 0;
}
首先运行程序，根据pid查看对应的maps。
在第一次调用brk函数之前，从下面的输出中可以看出当前堆的情况。
start_brk = end_data = 0x01161000
brk = 0x01182000
在第一次调用brk函数之后可以看到brk增加了。
brk = 0x01183000
其中，关于堆的那一行
- 0x01161000 是相应堆的起始地址
- rw-p 表明堆具有可读可写权限，并且属于隐私数据。
- 00000000 表明文件偏移，由于这部分内容并不是从文件中映射得到的，所以为 0。
- 00:00 是主从 (Major/mirror) 的设备号，这部分内容也不是从文件中映射得到的，所以也都为 0。
- 0 表示着 Inode 号。由于这部分内容并不是从文件中映射得到的，所以为 0。
但是看到这里我产生了疑问，代码中并没有说明申请多大的空间，只是调用了sbrk()函数，却每次都分配了0x21000（132kb）的空间。
在源码中添加一些东西，使用malloc申请1kb和1000kb的空间，再来分析空间结构。
/* sbrk and brk example*/
#include<stdio.h>
#include<unistd.h>
#include<sys/types.h>
#include<stdlib.h>
int main()
{
void *curr_brk, *tmp_brk = NULL; //创立空指针
printf("Welcome to sbrk example:%d\n",getpid()); //读取heap,pid
/* sbrk(0) gives current program break location */
tmp_brk = curr_brk = sbrk(0); //通过sbrk空指针赋值
void *addr = malloc(1024); //申请空间
printf("malloc addr is:%p\n", addr);
printf("Program Break Location1:%p\n", curr_brk);
getchar();
free(addr);
/* brk(addr) increments/decrements program break location */
brk(curr_brk+4096);
curr_brk = sbrk(0);
printf("Program Break Location2:%p\n" ,curr_brk);
getchar();
brk(tmp_brk);
curr_brk = sbrk(0);
addr = malloc(1024 * 1000);
printf("malloc addr is:%p\n", addr);
printf("Program Break Location3:%p\n", curr_brk);
getchar();
free(addr);
return 0;
}
第一次运行效果还是一样的，可以看到我们申请的空间是在初始化的空间内的。
但是第二次申请了1000kb的空间的时候，则是在初始空间以外的地方申请的，大小为1004kb。
这说明虽然程序向OS申请了小的内存，但是OS会把大的内存分给程序。这样的话避免了多次内核态与用户态的切换，提高了效率。我们称这一连续的内存为arena。此外，我们称由主线程申请的为main_arena。后续的申请内存会从这个arena中获取，直到空间不足。当arena大小不足时，可通过增加brk的方式增加arena的空间。类似的，arena可通过减少brk缩小它的空间。
当用户请求的内存小于初始化堆空间大小时（128k），会在main_arena中分配空间给用户；当用户请求的内存大于128kb，并且没有任何arena满足要求时，系统会调用mmap函数分配相应的内存空间。这与请求来自主进程还是线程无关。