heap note
堆
本篇文章摘自华庭大佬的Glibc 内存管理一书，只是插入了一些记录
什么是堆
在程序运行过程中，堆可以提供动态分配的内存，允许程序申请大小未知的内存。堆其实就是程序虚拟地址空间的一块连续的线性区域，它由低地址向高地址方向增长。我们一般称管理堆的那部分程序为堆管理器。
堆管理器处于用户程序与内核中间，主要做以下工作
- 响应用户的申请内存请求，向操作系统申请内存，然后将其返回给用户程序。同时，为了保持内存管理的高效性，内核一般都会预先分配很大的一块连续的内存，然后让堆管理器通过某种算法管理这块内存。只有当出现了堆空间不足的情况，堆管理器才会再次与操作系统进行交互。
- 管理用户所释放的内存。一般来说，用户释放的内存并不是直接返还给操作系统的，而是由堆管理器进行管理。这些释放的内存可以来响应用户新申请的内存的请求。
Linux 中早期的堆分配与回收由 Doug Lea 实现，但它在并行处理多个线程时，会共享进程的堆内存空间。因此，为了安全性，一个线程使用堆时，会进行加锁。然而，与此同时，加锁会导致其它线程无法使用堆，降低了内存分配和回收的高效性。同时，如果在多线程使用时，没能正确控制，也可能影响内存分配和回收的正确性。Wolfram Gloger 在 Doug Lea 的基础上进行改进使其可以支持多线程，这个堆分配器就是 ptmalloc 。在 glibc-2.3.x. 之后，glibc 中集成了 ptmalloc2。
目前 Linux 标准发行版中使用的堆分配器是 glibc 中的堆分配器：ptmalloc2。ptmalloc2 主要是通过 malloc/free 函数来分配和释放内存块。
需要注意的是，在内存分配与使用的过程中，Linux 有这样的一个基本内存管理思想，只有当真正访问一个地址的时候，系统才会建立虚拟页面与物理页面的映射关系。 所以虽然操作系统已经给程序分配了很大的一块内存，但是这块内存其实只是虚拟内存。只有当用户使用到相应的内存时，系统才会真正分配物理页面给用户使用。
堆的基本操作
这里我们主要介绍
- 基本的堆操作，包括堆的分配，回收，堆分配背后的系统调用
- 介绍堆目前的多线程支持。
malloc
在 glibc 的 malloc.c 中，malloc 的说明如下
1 | /* |
可以看出，malloc 函数返回对应大小字节的内存块的指针。此外，该函数还对一些异常情况进行了处理
- 当 n=0 时，返回当前系统允许的堆的最小内存块。
- 当 n 为负数时，由于在大多数系统上，size_t 是无符号数（这一点非常重要），所以程序就会申请很大的内存空间，但通常来说都会失败，因为系统没有那么多的内存可以分配。
free
在 glibc 的 malloc.c 中，free 的说明如下
1 | /* |
可以看出，free 函数会释放由 p 所指向的内存块。这个内存块有可能是通过 malloc 函数得到的，也有可能是通过相关的函数 realloc 得到的。
此外，该函数也同样对异常情况进行了处理
- 当 p 为空指针时，函数不执行任何操作。
- 当 p 已经被释放之后，再次释放会出现乱七八糟的效果，这其实就是
double free。 - 除了被禁用 (mallopt) 的情况下，当释放很大的内存空间时，程序会将这些内存空间还给系统，以便于减小程序所使用的内存空间。
内存分配背后的系统调用
在前面提到的函数中，无论是 malloc 函数还是 free 函数，我们动态申请和释放内存时，都经常会使用，但是它们并不是真正与系统交互的函数。这些函数背后的系统调用主要是 (s)brk 函数以及 mmap, munmap 函数。
如下图所示，我们主要考虑对堆进行申请内存块的操作。
(s)brk
对于堆的操作，操作系统提供了 brk 函数，glibc 库提供了 sbrk 函数，我们可以通过增加 brk 的大小来向操作系统申请内存。
初始时，堆的起始地址 start_brk 以及堆的当前末尾 brk 指向同一地址。根据是否开启 ASLR，两者的具体位置会有所不同
- 不开启 ASLR 保护时，start_brk 以及 brk 会指向 data/bss 段的结尾。
- 开启 ASLR 保护时，start_brk 以及 brk 也会指向同一位置，只是这个位置是在 data/bss 段结尾后的随机偏移处。
具体效果如下图（这个图片与网上流传的基本一致，这里是因为要画一张大图，所以自己单独画了下）所示
例子
1 | /* sbrk and brk example */ |
需要注意的是，在每一次执行完操作后，都执行了 getchar() 函数，这是为了我们方便我们查看程序真正的映射。
在第一次调用 brk 之前
从下面的输出可以看出，并没有出现堆。因此
- start_brk = brk = end_data = 0x804b000
1 | sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/syscalls$ ./sbrk |
第一次增加 brk 后
从下面的输出可以看出，已经出现了堆段
- start_brk = end_data = 0x804b000
- brk = 0x804c000
1 | sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/syscalls$ ./sbrk |
其中，关于堆的那一行
- 0x0804b000 是相应堆的起始地址
- rw-p 表明堆具有可读可写权限，并且属于隐私数据。
- 00000000 表明文件偏移，由于这部分内容并不是从文件中映射得到的，所以为 0。
- 00:00 是主从 (Major/mirror) 的设备号，这部分内容也不是从文件中映射得到的，所以也都为 0。
- 0 表示着 Inode 号。由于这部分内容并不是从文件中映射得到的，所以为 0。
mmap
malloc 会使用 mmap 来创建独立的匿名映射段。匿名映射的目的主要是可以申请以 0 填充的内存，并且这块内存仅被调用进程所使用。
例子
1 | /* Private anonymous mapping example using mmap syscall */ |
在执行 mmap 之前
我们可以从下面的输出看到，目前只有. so 文件的 mmap 段。
1 | sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/syscalls$ cat /proc/6067/maps |
mmap 后
从下面的输出可以看出，我们申请的内存与已经存在的内存段结合在了一起构成了 b7e00000 到 b7e21000 的 mmap 段。
1 | sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/syscalls$ cat /proc/6067/maps |
munmap
从下面的输出，我们可以看到我们原来申请的内存段已经没有了，内存段又恢复了原来的样子了。
1 | sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/syscalls$ cat /proc/6067/maps |
多线程支持
在原来的 dlmalloc 实现中，当两个线程同时要申请内存时，只有一个线程可以进入临界区申请内存，而另外一个线程则必须等待直到临界区中不再有线程。这是因为所有的线程共享一个堆。在 glibc 的 ptmalloc 实现中，比较好的一点就是支持了多线程的快速访问。在新的实现中，所有的线程共享多个堆。
这里给出一个例子。
pthread_create 是一个函数，用于在 POSIX 线程库中创建一个新的线程。
函数原型如下：
1 | int pthread_create(pthread_t *thread, const pthread_attr_t *attr, |
参数说明：
thread：指向pthread_t类型的指针，用于存储新创建线程的标识符。attr：指向pthread_attr_t类型的指针，用于指定线程的属性。可以传递NULL，表示使用默认属性。start_routine：指向线程函数的指针，该函数是线程的入口点，线程将从该函数开始执行。arg：传递给线程函数start_routine的参数。
返回值：
- 如果成功创建线程，则返回 0，表示成功。
- 如果创建线程失败，则返回一个非零的错误码，表示失败的原因。
pthread_create 函数用于创建一个新的线程，并在指定的线程函数 start_routine 中执行。新线程的执行将从 start_routine 函数开始，该函数接受一个 void* 类型的参数 arg。线程函数可以执行任意操作，包括计算、I/O 操作、同步等。
使用 pthread_create 创建的线程在执行完毕后，可以通过调用 pthread_join 函数来等待线程的结束，并获取线程的返回值。此外，还可以使用其他线程相关的函数来管理和操作线程，例如 pthread_detach、pthread_cancel 等。
需要注意的是，pthread_create 函数是 POSIX 标准中定义的线程创建函数，在不同的操作系统和编译器中可能有所差异。在使用时，应仔细阅读相关文档并遵循相应的使用规范。
pthread_join 是一个函数，用于等待指定的线程结束，并获取线程的返回值。
函数原型如下：
1 | int pthread_join(pthread_t thread, void **retval); |
参数说明：
thread：要等待的线程标识符，通常由pthread_create返回。retval：指向void*类型指针的指针，用于存储线程的返回值。
返回值：
- 如果成功等待线程结束，则返回 0，表示成功。
- 如果等待线程失败，则返回一个非零的错误码，表示失败的原因。
pthread_join 函数用于等待指定的线程结束。当调用该函数时，当前线程将被阻塞，直到被等待的线程执行完毕。在线程结束后，可以通过 retval 参数获取线程的返回值，该返回值是线程函数 start_routine 的返回值。
需要注意的是，如果线程被成功等待并成功获取返回值，那么线程的资源将被释放，不再占用系统资源。但是，如果不关心线程的返回值，可以将 retval 参数设置为 NULL。
1 | /* Per thread arena example. */ |
第一次申请之前， 没有任何任何堆段。
1 | sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread |
第一次申请后， 从下面的输出可以看出，堆段被建立了，并且它就紧邻着数据段，这说明 malloc 的背后是用 brk 函数来实现的。同时，需要注意的是，我们虽然只是申请了 1000 个字节，但是我们却得到了 0x0806c000-0x0804b000=0x21000 个字节的堆。这说明虽然程序可能只是向操作系统申请很小的内存，但是为了方便，操作系统会把很大的内存分配给程序。这样的话，就避免了多次内核态与用户态的切换，提高了程序的效率。我们称这一块连续的内存区域为 arena。此外，我们称由主线程申请的内存为 main_arena。后续的申请的内存会一直从这个 arena 中获取，直到空间不足。当 arena 空间不足时，它可以通过增加 brk 的方式来增加堆的空间。类似地，arena 也可以通过减小 brk 来缩小自己的空间。
1 | sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread |
在主线程释放内存后，我们从下面的输出可以看出，其对应的 arena 并没有进行回收，而是交由 glibc 来进行管理。当后面程序再次申请内存时，在 glibc 中管理的内存充足的情况下，glibc 就会根据堆分配的算法来给程序分配相应的内存。
1 | sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread |
在第一个线程 malloc 之前，我们可以看到并没有出现与线程 1 相关的堆，但是出现了与线程 1 相关的栈。
1 | sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread |
第一个线程 malloc 后， 我们可以从下面输出看出线程 1 的堆段被建立了。而且它所在的位置为内存映射段区域，同样大小也是 132KB(b7500000-b7521000)。因此这表明该线程申请的堆时，背后对应的函数为 mmap 函数。同时，我们可以看出实际真的分配给程序的内存为 1M(b7500000-b7600000)。而且，只有 132KB 的部分具有可读可写权限，这一块连续的区域成为 thread arena。
注意：
当用户请求的内存大于 128KB 时，并且没有任何 arena 有足够的空间时，那么系统就会执行 mmap 函数来分配相应的内存空间。这与这个请求来自于主线程还是从线程无关。
1 | sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread |
在第一个线程释放内存后， 我们可以从下面的输出看到，这样释放内存同样不会把内存重新给系统。
1 | sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread |
glibc内存管理篇
5. 源代码分析
5.1 边界标记法
1 | struct malloc_chunk { |
prev_size:如果前一个 chunk 是空闲的，该域表示前一个 chunk 的大小，如果前一个 chunk 不空闲，该域无意义。
size：当前 chunk 的大小，并且记录了当前 chunk 和前一个 chunk 的一些属性，包括前一个 chunk 是否在使用中，当前 chunk 是否是通过 mmap 获得的内存，当前 chunk 是否属于 非主分配区。
fd 和 bk：指针 fd 和 bk 只有当该 chunk 块空闲时才存在，其作用是用于将对应的空闲 chunk 块加入到空闲 chunk 块链表中统一管理，如果该 chunk 块被分配给应用程序使用，那 么这两个指针也就没有用（该 chunk 块已经从空闲链中拆出）了，所以也当作应用程序的使用空间，而不至于浪费。 fd指向低地址，bk指向高地址
fd_nextsize 和 bk_nextsize:当当前的 chunk 存在于 large bins 中时，large bins 中的空闲 chunk 是按照大小排序的，但同一个大小的 chunk 可能有多个，增加了这两个字段可以加快遍历空闲 chunk，并查找满足需要的空闲 chunk，fd_nextsize 指向下一个比当前 chunk 大小 大的第一个空闲 chunk，bk_nextszie 指向前一个比当前 chunk 大小小的第一个空闲 chunk。 如果该 chunk 块被分配给应用程序使用，那么这两个指针也就没有用（该 chunk 块已经从 size 链中拆出）了，所以也当作应用程序的使用空间，而不至于浪费。
一个已分配的块的结构如下所示：
1 | chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
在这里，”chunk”在大多数malloc代码中表示块的前部，而”mem”是返回给调用者的指针。块的前部包含了前一个块的大小（如果该块已分配），以及当前块的大小（以字节为单位）。”M”和”P”是用于表示块的状态（分配或空闲）的位标志。”mem”指针指向的位置是用户数据的起始位置。下一个块的位置由”nextchunk”指针表示，并且包含了下一个块的大小信息。
空闲块以循环双向链表的形式存储，结构如下所示：
1 | chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
在这里，空闲块的结构与已分配块的结构类似，但有一些差别。空闲块的前部包含了前一个块的大小。head:标记表示这是一个空闲块的头部。在mem指针指向的位置，存储了块的大小信息和状态标志（P表示空闲）。空闲块还包含了指向链表中下一个块和前一个块的指针，形成了循环双向链表的结构。链表的头部指针指向第一个空闲块。空闲块的尾部有一个foot:标记，标识块的大小。
P（PREV_INUSE）位存储在chunk大小的未使用的低位上（chunk大小总是二字倍数），它是用于标记前一个chunk是否在使用的一个位。如果该位被清除，则当前chunk大小之前的字包含了前一个chunk的大小，并且可以用来找到上一个chunk的开头。第一次分配的chunk总是设置了这个位，这样可以防止访问不存在的（或不属于自己的）内存。如果任何给定的chunk的prev_inuse被设置，则你无法确定前一个chunk的大小，甚至在尝试这样做时可能会遇到内存寻址错误。
值得注意的是，当前chunk的foot实际上表示为下一个chunk的prev_size。这样做可以更容易地处理对齐等问题，但在尝试扩展或适应这段代码时可能会非常困惑。
所有这些都有两个异常情况：
- 特殊的chunk
顶端（top）并不使用它的后续大小字段，因为没有紧接着的下一个chunk需要依赖它的索引。在初始化后，顶端chunk强制被设置为一直存在。如果它变得小于MINSIZE字节，则会被重新填充。 - 通过mmap分配的chunks，在其大小字段中设置了第二低位的M（IS_MMAPPED）位。因为它们是单独一个一个分配的，每一个都必须包含自己的后续大小字段。
1 | /* conversion from malloc headers to user pointers, and back */ |
对于已经分配的 chunk，通过 chunk2mem 宏根据 chunk 地址获得返回给用户的内存地址，反过来通过 mem2chunk 宏根据 mem 地址得到 chunk 地址，chunk 的地址是按 2 * SIZE_SZ 对齐的，而 chunk 结构体的前两个域刚好也是 2*SIZE_SZ 大小，所以，mem 地址也是 2 * SIZE_SZ 对齐的。宏 aligned_OK 和misaligned_chunk(p)用于校验地址是否是按 2 * SIZE_SZ 对齐的。 MIN_CHUNK_SIZE 定义了最小的 chunk 的大小，32 位平台上位 16 字节，64 位平台为 24 字节或是 32 字节。MINSIZE 定义了最小的分配的内存大小，是对 MIN_CHUNK_SIZE 进行了 2*SIZE_SZ 对齐，地址对齐后与 MIN_CHUNK_SIZE 的大小仍然是一样的。
1 | /* |
这几个宏用于将用户请求的分配大小转换成内部需要分配的 chunk 大小，这里需要注意 的在转换时不但考虑的地址对齐，还额外加上了 SIZE_SZ，这意味着 ptmalloc 分配内存需要 一个额外的overhead，为SIZE_SZ字节，通过chunk的空间复用，我们很容易得出这个overhead 为 SIZE_SZ。
wiki: 当一个 chunk 处于已分配状态时，它的物理相邻的下一个 chunk 的 prev_size 字段必然是无效的，故而这个字段就可以被当前这个 chunk 使用。这就是 ptmalloc 中 chunk 间的复用。具体流程如下
- 首先，利用 REQUEST_OUT_OF_RANGE 判断是否可以分配用户请求的字节大小的 chunk。
- 其次，需要注意的是用户请求的字节是用来存储数据的，即 chunk header 后面的部分。与此同时，由于 chunk 间复用，所以可以使用下一个 chunk 的 prev_size 字段。因此，这里只需要再添加 SIZE_SZ 大小即可以完全存储内容。
- 由于系统中所允许的申请的 chunk 最小是 MINSIZE，所以与其进行比较。如果不满足最低要求，那么就需要直接分配 MINSIZE 字节。
- 如果大于的话，因为系统中申请的 chunk 需要 2 * SIZE_SZ 对齐，所以这里需要加上 MALLOC_ALIGN_MASK 以便于对齐。
以 Linux X86_64 平台为例，假设 SIZE_SZ 为 8 字节，空闲时，一个 chunk 中至少要 4 个 size_t（8B）大小的空间，用来存储 prev_size，size，fd 和 bk，也就是 MINSIZE（32B），chunk 的大小要对齐到 2 * SIZE_SZ（16B）。当一个 chunk 处于使用状态时，它的下一个 chunk 的 prev_size 域肯定是无效的。所以实际上，这个空间也可以被当前 chunk 使用。这听起来有点 不可思议，但确实是合理空间复用的例子。故而实际上，一个使用中的 chunk 的大小的计算公式应该是：in_use_size = (用户请求大小+ 16 - 8 ) align to 8B，这里加 16 是因为需要存储 prev_size 和 size，但又因为向下一个 chunk“借”了 8B，所以要减去 8，每分配一个 chunk 的 overhead 为 8B，即 SIZE_SZ 的大小。最后，因为空闲的 chunk 和使用中的 chunk 使用的是同一块空间。所以肯定要取其中最大者作为实际的分配空间。即**最终的分配空间 chunk_size = max(in_use_size, 32)**。这就是当用户请求内存分配时，ptmalloc 实际需要分配的内存大小。
注意：如果 chunk 是由 mmap ()直接分配的，则该 chunk 不会有前一个 chunk 和后一个 chunk，所有本 chunk 没有下一个 chunk 的 prev_size 的空间可以“借”，所以对于直接 mmap() 分配内存的 overhead 为 2 * SIZE_SZ,因为每个mmap()分配的内存块都有一个额外的头部和尾部，用于管理和维护内存的相关信息。
对于使用mmap()直接分配的内存块，其内存布局通常是独立的，与其他内存块没有前后关系。因此，这些内存块不会有前一个块或后一个块，也就无法利用前一个块的prev_size字段来存储额外的信息。
1 | /* 当前一个相邻的内存块正在使用时，将 size 字段与 PREV_INUSE 进行按位或操作 */ |
解释：
PREV_INUSE（0x1）：用于表示前一个相邻内存块是否正在使用的标志位。当前一个内存块处于使用状态时，将该标志位设置为1。prev_inuse(p)：用于提取给定内存块（p）的前一个内存块的使用状态。通过与PREV_INUSE进行按位与操作，可以获取前一个内存块的使用状态。IS_MMAPPED（0x2）：用于表示内存块是否是通过mmap()函数获得的标志位。当内存块是通过mmap()函数分配的时，将该标志位设置为1。chunk_is_mmapped(p)：用于检查给定内存块（p）是否是通过mmap()函数分配的内存块。通过与IS_MMAPPED进行按位与操作，可以判断内存块是否是通过mmap()函数分配的。NON_MAIN_ARENA（0x4）：用于表示内存块是否来自非主要堆区（non-main arena）的标志位。非主要堆区是glibc中用于管理多个堆的机制，当内存块来自非主要堆区时，将该标志位设置为1。chunk_non_main_arena(p)：用于检查给定内存块（p）是否来自非主要堆区。通过与NON_MAIN_ARENA进行按位与操作，可以判断内存块是否来自非主要堆区。
chunk 在分割时总是以地址对齐（默认是 8 字节，可以自由设置，但是 8 字节是最小值 并且设置的值必须是 2 为底的幂函数值，即是 alignment = 2^n，n 为整数且 n>=3）的方式来 进行的，所以用 chunk->size 来存储本 chunk 块大小字节数的话，其末 3bit 位总是 0，因此 这三位可以用来存储其它信息，比如：
以第 0 位作为 P 状态位，标记前一chunk 块是否在使用中，为 1 表示使用，为 0 表示空闲。
以第 1 位作为 M 状态位，标记本 chunk 块是否是使用 mmap()直接从进程的 mmap 映射区域分配的，为 1 表示是，为 0 表示否。
以第 2 位作为 A 状态位，标记本 chunk 是否属于非主分配区，为 1 表示是，为 0 表示 否。
1 | /* |
1 | /* |
这些宏的作用如下：
SIZE_BITS：用于屏蔽提取大小时不需要的位。其中包括PREV_INUSE、IS_MMAPPED和NON_MAIN_ARENA。这些位用于标记内存块的状态和属性。chunksize(p)：用于获取给定内存块（p）的大小。通过将内存块的 size 字段与SIZE_BITS进行按位与操作，可以得到实际的内存块大小，忽略了使用位。next_chunk(p)：用于获取给定内存块（p）的下一个物理malloc_chunk的指针。通过将内存块的地址加上内存块的大小（忽略了使用位），可以得到下一个物理内存块的地址。prev_chunk(p)：用于获取给定内存块（p）的前一个物理malloc_chunk的指针。通过将内存块的地址减去前一个内存块的prev_size字段的值，可以得到前一个物理内存块的地址。chunk_at_offset(p, s)：将给定内存块（p）的地址加上偏移量s，将结果视为一个块的指针。这个宏用于在指定偏移量处处理内存块。
prev_size 字段虽然在当前 chunk 块结构体内，记录的却是前一个邻接 chunk 块的信息， 这样做的好处就是我们通过本块 chunk 结构体就可以直接获取到前一 chunk 块的信息，从而 方便做进一步的处理操作。相对的，当前 chunk 块的 foot 信息就存在于下一个邻接 chunk 块的结构体内。字段 prev_size 记录的什么信息呢？有两种情况：
1）如果前一个邻接 chunk 块空闲，那么当前 chunk 块结构体内的 prev_size 字段记录的 是前一个邻接 chunk 块的大小。这就是由当前 chunk 指针获得前一个空闲 chunk 地址的依据。 宏 prev_chunk(p)就是依赖这个假设实现的。
2）如果前一个邻接 chunk 在使用中，则当前 chunk 的 prev_size 的空间被前一个 chunk 借用中，其中的值是前一个 chunk 的内存内容，对当前 chunk 没有任何意义。
字段 size 记录了本 chunk 的大小，无论下一个 chunk 是空闲状态或是被使用状态，都可以通过本 chunk 的地址加上本 chunk 的大小，得到下一个 chunk 的地址，由于 size 的低 3 个 bit 记录了控制信息，需要屏蔽掉这些控制信息，取出实际的 size 在进行计算下一个 chunk 地址，这是 next_chunk(p)的实现原理。
浅浅理解：标志位是不占用内存大小的，实际size包含例如pre_size之类的管理信息
宏 chunksize(p)用于获得 chunk 的实际大小，需要屏蔽掉 size 中的控制信息。
宏 chunk_at_offset(p, s)将 p+s 的地址强制看作一个 chunk。
注意：按照边界标记法，可以有多个连续的并且正在被使用中的 chunk 块，但是不会有 多个连续的空闲 chunk 块，因为连续的多个空闲 chunk 块一定会合并成一个大的空闲 chunk 块。
补充：合并空闲块的目标通常是为了提高内存利用率和减少内存碎片化
1 | /* 提取 p 的 inuse 位 */ |
inuse(p)宏用于提取给定内存块p的 inuse 位。通过对p进行位运算和指针偏移，获取下一个内存块的起始位置，并从其size字段中提取出 PREV_INUSE 位的值，以确定p是否被标记为已使用。set_inuse(p)宏用于将给定内存块p标记为已使用，而不影响其他属性。通过对p进行位运算和指针偏移，获取下一个内存块的起始位置，并将其size字段中的 PREV_INUSE 位置为 1，表示该内存块已被使用。clear_inuse(p)宏用于将给定内存块p标记为未使用，而不影响其他属性。通过对p进行位运算和指针偏移，获取下一个内存块的起始位置，并将其size字段中的 PREV_INUSE 位清零，表示该内存块未被使用。
上面的这一组宏用于 check/set/clear 当前 chunk 使用标志位，当前 chunk 的使用标志位存储在下一个 chunk 的 size 的第 0 bit（P 状态位），所以首先要获得下一个 chunk 的地址， 然后 check/set/clear 下一个 chunk 的 size 域的第 0 bit。
1 | /* check/set/clear inuse bits in known places */ |
上面的三个宏用于 check/set/clear 指定 chunk 的 size 域中的使用标志位。
1 | /* Set size at head, without disturbing its use bit */ |
宏 set_head_size(p, s)用于设置当前 chunk p 的 size 域并保留 size 域的控制信息。宏 set_head(p, s) 用于设置当前 chunk p 的 size 域并忽略已有的 size 域控制信息。宏 set_foot(p, s)用于设置当前 chunk p 的下一个 chunk 的 prev_size 为 s，s 为当前 chunk 的 size，只有当 chunk p 为空闲时才能使用这个宏，当前 chunk 的 foot 的内存空间存在于下一个 chunk，即下一个 chunk 的 prev_size。
5.2 分箱式内存管理
对于空闲的 chunk，ptmalloc 采用分箱式内存管理方式，根据空闲 chunk 的大小和处于的状态将其放在四个不同的 bin 中，这四个空闲 chunk 的容器包括 fast bins，unsorted bin， small bins 和 large bins。Fast bins 是小内存块的高速缓存，当一些大小小于 64 字节的 chunk 被回收时，首先会放入 fast bins 中，在分配小内存时，首先会查看 fast bins 中是否有合适的 内存块，如果存在，则直接返回 fast bins 中的内存块，以加快分配速度。Usorted bin 只有一个，回收的 chunk 块必须先放到 unsorted bin 中，分配内存时会查看 unsorted bin 中是否有合适的 chunk，如果找到满足条件的 chunk，则直接返回给用户，否则将 unsorted bin 的所有 chunk 放入 small bins 或是 large bins 中。Small bins 用于存放固定大小的 chunk，共 64 个 bin，最小的 chunk 大小为 16 字节或 32 字节，每个 bin 的大小相差 8 字节或是 16 字节，当 分配小内存块时，采用精确匹配的方式从 small bins 中查找合适的 chunk。Large bins 用于存 储大于等于 512B 或 1024B 的空闲 chunk，这些 chunk 使用双向链表的形式按大小顺序排序， 分配内存时按最近匹配方式从 large bins 中分配 chunk。
问题小结
问题：为什么bin数组在遍历的时候会往前跨两个地址，并且将bin元素强转成chunk指针类型？
解答：因为chunk指针指向chunk，如果直接使用bin数组的fd和bk来寻址，那么链表会断掉，因为类型不符合
太强了！！ 强转很重要！！！！
bin 通用的宏如下：
1 | typedef struct malloc_chunk *mbinptr; |
5.2.1 Small bins
ptmalloc使用small bins管理空闲小chunk，每个small bin中的chunk的大小与bin的index 有如下关系： Chunk_size=2 * SIZE_SZ * index
在 SIZE_SZ 为 4B 的平台上，small bins 中的 chunk 大小是以 8B 为公差的等差数列，最大 的 chunk 大小为 504B，最小的 chunk 大小为 16B，所以实际共 62 个 bin。分别为 16B、24B、 32B，„„，504B。在 SIZE_SZ 为 8B 的平台上，small bins 中的 chunk 大小是以 16B 为公差的等差数列，最大的 chunk 大小为 1008B，最小的 chunk 大小为 32B，所以实际共 62 个 bin。 分别为 32B、48B、64B，…… ，1008B。
ptmalloc 维护了 62 个双向环形链表（每个链表都具有链表头节点，加头节点的最大作用就是便于对链表内节点的统一处理，即简化编程），每一个链表内的各空闲 chunk 的大小一致，因此当应用程序需要分配某个字节大小的内存空间时直接在对应的链表内取就可以了， 这样既可以很好的满足应用程序的内存空间申请请求而又不会出现太多的内存碎片。我们可 以用如下图来表示在 SIZE_SZ 为 4B 的平台上 ptmalloc 对 512B 字节以下的空闲 chunk 组织方 式（所谓的分箱机制）
5.2.2 Large bins
在 SIZE_SZ 为 4B 的平台上，大于等于 512B 的空闲 chunk，或者，在 SIZE_SZ 为 8B 的平 台上，大小大于等于 1024B 的空闲 chunk，由 sorted bins 管理。Large bins 一共包括 63 个 bin， 每个 bin 中的 chunk 大小不是一个固定公差的等差数列，而是分成 6 组 bin，每组 bin 是一个 固定公差的等差数列，每组的 bin 数量依次为 32、16、8、4、2、1，公差依次为 64B、512B、 4096B、32768B、262144B 等。
以 SIZE_SZ 为 4B 的平台为例，第一个 large bin 的起始 chunk 大小为 512B，共 32 个 bin， 公差为 64B，等差数列满足如下关系：
Chunk_size=512 + 64 * index
第二个 large bin 的起始 chunk 大小为第一组 bin 的结束 chunk 大小，满足如下关系：
Chunk_size=512 + 64 * 32 + 512 * index
同理，我们可计算出每个 bin 的起始 chunk 大小和结束 chunk 大小。这些 bin 都是很有规律的，其实 small bins 也是满足类似规律，small bins 可以看着是公差为 8 的等差数列，一 共有 64 个 bin（第 0 和 1bin 不存在），所以我们可以将 small bins 和 large bins 存放在同一个包含 128 个 chunk 的数组上，数组的前一部分位 small bins，后一部分为 large bins，每个 bin 的 index 为 chunk 数组的下标，于是，我们可以根据数组下标计算出该 bin 的 chunk 大小（small bins）或是 chunk 大小范围（large bins），也可以根据需要分配内存块大小计算出所需 chunk 所属 bin 的 index，ptmalloc 使用了一组宏巧妙的实现了这种计算。
1 |
|
注意：如果对于用户要分配的内存大小 size， 必须先使用 checked_request2size(req, sz)计算出 chunk 的大小，再使用 bin_index(sz)计算出 chunk 所属的 bin index。
对于 SIZE_SZ 为 4B 的平台，bin[0]和 bin[1]是不存在的，因为最小的 chunk 为 16B，small bins 一共 62 个，large bins 一共 63 个，加起来一共 125 个 bin。而 NBINS 定义为 128，其实 bin[0]和 bin[127]都不存在，bin[1]为 unsorted bin 的 chunk 链表头。
1 | typedef struct malloc_chunk* mbinptr; |
宏 bin_at(m, i)通过 bin index 获得 bin 的链表头，chunk 中的 fb 和 bk 用于将空闲 chunk 链入链表中，而对于每个 bin 的链表头，只需要这两个域就可以了，prev_size 和 size 对链表都来说都没有意义，浪费空间，ptmalloc 为了节约这点内存空间，增大 cpu 高速缓存的命中率，在 bins 数组中只为每个 bin 预留了两个指针的内存空间用于存放 bin 的链表头的 fb 和 bk 指针。
从 bin_at(m, i)的定义可以看出，bin[0]不存在，以 SIZE_SZ 为 4B 的平台为例，bin[1]的前 4B 存储的是指针 fb，后 4B 存储的是指针 bk，而 bin_at 返回的是 malloc_chunk 的指针，由 于 fb 在 malloc_chunk 的偏移地址为 offsetof (struct malloc_chunk, fd))=8，所以用 fb 的地址减去 8 就得到 malloc_chunk 的地址。但切记，对 bin 的链表头的 chunk，一定不能修改 prev_size 和 size 域，这两个域是与其他 bin 的链表头的 fb 和 bk 内存复用的。
宏 next_bin(b)用于获得下一个 bin 的地址，根据前面的分析，我们知道只需要将当前 bin 的地址向后移动两个指针的长度就得到下一个 bin 的链表头地址。
每个 bin 使用双向循环链表管理空闲 chunk，bin 的链表头的指针 fb 指向第一个可用的 chunk，指针 bk 指向最后一个可用的 chunk。宏 first(b)用于获得 bin 的第一个可用 chunk， 宏 last(b)用于获得 bin 的最后一个可用的 chunk，这两个宏便于遍历 bin，而跳过 bin 的链表头。
宏 unlink(P, BK, FD)用于将 chunk 从所在的空闲链表中取出来，注意 large bins 中的空闲 chunk 可能处于两个双向循环链表中，unlink 时需要从两个链表中都删除。(还有一个由fdnextsize,bknextsize组成的链表，因为large bin十分特殊，大小可能不相同)
注意：bins是声明在malloc_state的指针数组，长度为254，2个元素构成一个bin，bin数组元素指向的是所对应管理的chunk
5.2.3 Unsorted bin
Unsorted bin 可以看作是 small bins 和 large bins 的 cache(缓存)，只有一个 unsorted bin，以双向链表管理空闲 chunk，空闲 chunk 不排序，所有的 chunk 在回收时都要先放到 unsorted bin 中，分配时，如果在 unsorted bin 中没有合适的 chunk，就会把 unsorted bin 中的所有 chunk 分别加入到所属的 bin 中，然后再在 bin 中分配合适的 chunk。Bins 数组中的元素 bin[1]用于 存储 unsorted bin 的 chunk 链表头。
1 | /* |
1 | /* |
上面的宏的定义比较明显，把 bin[1]设置为 unsorted bin 的 chunk 链表头，对 top chunk 的初始化，也暂时把 top chunk 初始化为 unsort chunk，仅仅是初始化一个值而已，这个 chunk 的内容肯定不能用于 top chunk 来分配内存，主要原因是 top chunk 不属于任何 bin，但 ptmalloc 中的一些 check 代码，可能需要 top chunk 属于一个合法的 bin。
5.2.4 Fast bins
Fast bins 主要是用于提高小内存的分配效率，默认情况下，对于 SIZE_SZ 为 4B 的平台， 小于 64B 的 chunk 分配请求，对于 SIZE_SZ 为 8B 的平台，小于 128B 的 chunk 分配请求， 首先会查找 fast bins 中是否有所需大小的 chunk 存在（精确匹配），如果存在，就直接返回。
Fast bins 可以看着是 small bins 的一小部分 cache，默认情况下，fast bins 只 cache 了 small bins 的前 7 个大小的空闲 chunk，也就是说，对于 SIZE_SZ 为 4B 的平台，fast bins 有 7 个 chunk 空闲链表（bin），每个 bin 的 chunk 大小依次为 16B，24B，32B，40B，48B，56B，64B；对于 SIZE_SZ 为 8B 的平台，fast bins 有 7 个 chunk 空闲链表（bin），每个 bin 的 chunk 大小依 次为 32B，48B，64B，80B，96B，112B，128B。以 32 为系统为例，分配的内存大小与 chunk 大小和 fast bins 的对应关系如下表所示：
Fast bins 可以看着是 LIFO 的栈，使用单向链表实现。
1 | /* |
1 | /* |
根据 fast bin 的 index，获得 fast bin 的地址。
1 | /* offset 2 to use otherwise unindexable first 2 bins */ |
宏 fastbin_index(sz)用于获得 fast bin 在 fast bins 数组中的 index，由于 bin[0]和 bin[1]中 的chunk不存在，所以需要减2，对于SIZE_SZ为4B的平台，将sz除以8减2得到fast bin index， 对于 SIZE_SZ 为 8B 的平台，将 sz 除以 16 减去 2 得到 fast bin index。
1 | /* The maximum fastbin request size we support */ |
根据 SIZE_SZ 的不同大小，定义 MAX_FAST_SIZE 为 80B 或是 160B，fast bins 数组的大小 NFASTBINS 为 10，FASTBIN_CONSOLIDATION_THRESHOLD 为 64k，当每次释放的 chunk 与该 chunk 相邻的空闲 chunk 合并后的大小大于 64k 时，就认为内存碎片可能比较多了，就需要 把 fast bins 中的所有 chunk 都进行合并，以减少内存碎片对系统的影响。
1 |
|
上面的宏 DEFAULT_MXFAST 定义了默认的 fast bins 中最大的 chunk 大小，对于 SIZE_SZ 为 4B 的平台，最大 chunk 为 64B，对于 SIZE_SZ 为 8B 的平台，最大 chunk 为 128B。ptmalloc 默认情况下调用 set_max_fast(s)将全局变量 global_max_fast 设置为 DEFAULT_MXFAST，也就 是设置 fast bins 中 chunk 的最大值，get_max_fast()用于获得这个全局变量 global_max_fast 的值。
5.3 核心结构体分析
每个分配区是 struct malloc_state 的一个实例，ptmalloc 使用 malloc_state 来管理分配区， 而参数管理使用 struct malloc_par，全局拥有一个唯一的 malloc_par 实例。
5.3.1 malloc_state
1 | struct malloc_state |
Mutex 用于串行化访问分配区，当有多个线程访问同一个分配区时，第一个获得这个 mutex 的线程将使用该分配区分配内存，分配完成后，释放该分配区的 mutex，以便其它线程使用该分配区。
Flags 记录了分配区的一些标志，bit0 用于标识分配区是否包含至少一个 fast bin chunk， bit1 用于标识分配区是否能返回连续的虚拟地址空间。
1 | /* |
该注释解释了在 max_fast 中持有的 FASTCHUNKS_BIT 表示可能存在一些 fastbin 块的含义。当将块插入任何 fastbin中时，会将该标志位设置为 true，并且只有在 malloc_consolidate 函数中才会清除该标志位。为了确保在启动时 have_fastchunks 为 true（因为静态变量会被零填充），真值被取反，简化了初始化检查。
1 |
上面的宏用于设置或是置位 flags 中 fast chunk 的标志位 bit0，如果 bit0 为 0，表示分配区中有 fast chunk，如果为 1 表示没有 fast chunk，初始化完成后的 malloc_state 实例中，flags 值为 0，表示该分配区中有 fast chunk，但实际上没有，试图从 fast bins 中分配 chunk 都会返回 NULL，在第一次调用函数 malloc_consolidate()对 fast bins 进行 chunk 合并时，如果 max_fast 大于 0，会调用 clear_fastchunks 宏，标志该分配区中已经没有 fast chunk，因为函数 malloc_consolidate()会合并所有的 fast bins 中的 chunk。clear_fastchunks 宏只会在函数 malloc_consolidate()中调用。当有 fast chunk 加入 fast bins 时，就是调用 set_fastchunks 宏标 46 识分配区的 fast bins 中存在 fast chunk。
1 | /* |
该注释解释了 NONCONTIGUOUS_BIT 的含义。**NONCONTIGUOUS_BIT 表示 MORECORE 函数不返回连续的内存区域。在正常情况下，如果连续的 MORECORE 调用返回的内存区域是相邻的，那么在合并内存块时可以利用这种连续性。**
初始情况下，**NONCONTIGUOUS_BIT 的值来自 MORECORE_CONTIGUOUS，但如果在后续的内存分配中使用了 mmap 作为 sbrk 的替代方式，那么 NONCONTIGUOUS_BIT 的值会动态地进行更改。**
1 |
Flags 的 bit1 如果为 0，表示 MORCORE 返回连续虚拟地址空间，bit1 为 1，表示 MORCORE 返回非连续虚拟地址空间，对于主分配区，MORECORE 其实为 sbr()，默认返回连续虚拟地 址空间，对于非主分配区，使用 mmap()分配大块虚拟内存，然后进行切分来模拟主分配区的行为，而默认情况下 mmap 映射区域是不保证虚拟地址空间连续的，所以非主分配区默认分配非连续虚拟地址空间。
Malloc_state 中声明了几个对锁的统计变量，默认没有定义 THREAD_STATS，所以不会对锁的争用情况做统计。
fastbinsY 拥有 10（NFASTBINS）个元素的数组，用于存放每个 fast chunk 链表头指针， 所以 fast bins 最多包含 10 个 fast chunk 的单向链表。
top 是一个 chunk 指针，指向分配区的 top chunk。
last_remainder 是一个 chunk 指针，分配区上次分配 small chunk 时，从一个 chunk 中分裂出一个 small chunk 返回给用户，分裂后的剩余部分形成一个 chunk，last_remainder 就是指向的这个 chunk。
bins 用于存储 unstored bin，small bins 和 large bins 的 chunk 链表头，small bins 一共 62 个，large bins 一共 63 个，加起来一共 125 个 bin。而 NBINS 定义为 128，其实 bin[0]和 bin[127] 都不存在，bin[1]为 unsorted bin 的 chunk 链表头，所以实际只有 126bins。Bins 数组能存放 了 254（NBINS * 2 – 2）个 mchunkptr 指针，而我们实现需要存储 chunk 的实例，一般情况下， chunk 实例的大小为 6 个 mchunkptr 大小，这 254 个指针的大小怎么能存下 126 个 chunk 呢？ 这里使用了一个技巧，如果按照我们的常规想法，也许会申请 126 个 malloc_chunk 结构体指针元素的数组，然后再给链表申请一个头节点（即 126 个），再让每个指针元素正确指向而形成 126 个具有头节点的链表。事实上，对于 malloc_chunk 类型的链表“头节点”，其内的 prev_size 和 size 字段是没有任何实际作用的，fd_nextsize 和 bk_nextsize 字段只有 large bins 中的空闲 chunk 才会用到，而对于 large bins 的空闲 chunk 链表头不需要这两个字段，因此 这四个字段所占空间如果不合理使用的话那就是白白的浪费。我们再来看一看 128 个 malloc_chunk 结构体指针元素的数组占了多少内存空间呢？假设 SIZE_SZ 的大小为 8B，则指针的大小也为 8B，结果为 126 * 2 * 8=2016 字节。而 126 个 malloc_chunk 类型的链表“头节点” 需要多少内存呢？126 * 6 * 8=6048，真的是 6048B 么？不是，刚才不是说了，prev_size，size， fd_nextsize 和 bk_nextsize 这四个字段是没有任何实际作用的，因此完全可以被重用（覆盖）， 47 因此实际需要内存为 12628=2016。Bins 指针数组的大小为，（128 * 2 - 2） 8=2032* , 2032 大 于 2016（事实上最后 16 个字节都被浪费掉了），那么这 254 个 malloc_chunk结构体指针元素数组所占内存空间就可以存储这 126 个头节点了。
binmap 字段是一个 int 数组，ptmalloc 用一个 bit 来标识该 bit 对应的 bin 中是否包含空 闲 chunk。
1 | /* |
binmap 一共 128bit，16 字节，4 个 int 大小，binmap 按 int 分成 4 个 block，每个 block 有 32 个 bit，根据 bin indx 可以使用宏 idx2block 计算出该 bin 在 binmap 对应的 bit 属于哪个 block。idx2bit 宏取第 i 位为 1，其它位都为 0 的掩码，举个例子：idx2bit(3) 为 “0000 1000” （只显示 8 位）。mark_bin 设置第 i 个 bin 在 binmap 中对应的 bit 位为 1；unmark_bin 设置 第 i 个 bin 在 binmap 中对应的 bit 位为 0；get_binmap 获取第 i 个 bin 在 binmap 中对应的 bit。
next 字段用于将分配区以单向链表链接起来。
next_free 字段空闲的分配区链接在单向链表中，只有在定义了 PER_THREAD 的情况下才 定义该字段。
system_mem 字段记录了当前分配区已经分配的内存大小。
max_system_mem 记录了当前分配区最大能分配的内存大小。
堆相关数据结构(大部分与上述重复)
！！！一些关于堆的约束，后面详细考虑！！！
1 | /* |
Top Chunk
glibc 中对于 top chunk 的描述如下
1 | /* |
程序第一次进行 malloc 的时候，heap 会被分为两块，一块给用户，剩下的那块就是 top chunk。其实，所谓的 top chunk 就是处于当前堆的物理地址最高的 chunk。这个 chunk 不属于任何一个 bin，它的作用在于当所有的 bin 都无法满足用户请求的大小时，如果其大小不小于指定的大小，就进行分配，并将剩下的部分作为新的 top chunk。否则，就对 heap 进行扩展后再进行分配。在 main arena 中通过 sbrk 扩展 heap，而在 thread arena 中通过 mmap 分配新的 heap。
需要注意的是，top chunk 的 prev_inuse 比特位始终为 1，否则其前面的 chunk 就会被合并到 top chunk 中。
初始情况下，我们可以将 unsorted chunk 作为 top chunk。
last remainder
在用户使用 malloc 请求分配内存时，ptmalloc2 找到的 chunk 可能并不和申请的内存大小一致，这时候就将分割之后的剩余部分称之为 last remainder chunk ，unsort bin 也会存这一块。top chunk 分割剩下的部分不会作为 last remainder.
宏观结构
arena
在我们之前介绍的例子中，无论是主线程还是新创建的线程，在第一次申请内存时，都会有独立的 arena。那么会不会每个线程都有独立的 arena 呢？下面我们就具体介绍。
arena 数量
对于不同系统，arena 数量的约束如下
1 | For 32 bit systems: |
显然，不是每一个线程都会有对应的 arena。至于为什么 64 位系统，要那么设置，我也没有想明白。此外，因为每个系统的核数是有限的，当线程数大于核数的二倍（超线程技术）时，就必然有线程处于等待状态，所以没有必要为每个线程分配一个 arena。
arena 分配规则(来自于不知名博客，不确定其完全正确性)
Ptmalloc2通过几种数据结构来进行管理，主要有arena,heap,chunk三种层级。arena和heap都是对chunk的一种组织方式，方便之后的分配，arena又是对heap的组织，arene是堆管理器。
arena: 有一个main_arena，是由主线程创建的，thread_arena则为各线程创建的，当arena满了之后就不再创建而是与其他arena共享一个arena，方法为依次给各个arena上锁（查看是否有其他线程正在使用该arena），如果上锁成功（没有其他线程正在使用），则使用该arena，之后一直使用这个arena，如果无法使用则阻塞等待。heap的等级就比arena要低一些了，一个arena可以有多个heap，也是存储了堆相关的信息。chunk为分配给用户的内存的一个单位，每当我们分配一段内存的时候其实就是分配得到了一个chunk，我们就可以在chunk当中进行一定的操作了。不过为了进行动态分配，chunk本身也有一些数据（元数据），是用来指示其分配等等的数据。glibc的malloc源码中涉及三种最重要数据结构：Arena、Heap、Chunk ，分别对应结构体malloc_state、heap_info、malloc_chunk 。每个数据结构都有对应的结构体实现,如图:
- Thread - Arena ： 一个Arena对应多个线程Thread。即每个线程都有一个Arena，但是**有可能多个线程共用一个Arena(同一时间只能一对一)**。每个Arena都包含一个malloc_state结构体，保存bins, top chunk, Last reminder chunk等信息。
- Arena - Heap：一个Arena可能拥有多个heap。Arena开始的时候只有一个heap，但是当这个heap的空间用尽时，就需要获取新的heap。(也可以理解为subheap子堆)
- Heap - Chunk：一个Heap根据用户的请求会划分为多个chunk，每个chunk拥有自己的header - malloc_chunk。
区别
与 thread 不同的是，main_arena 并不在申请的 heap 中，而是一个全局变量，在 libc.so 的数据段。
heap_info
程序刚开始执行时，每个线程是没有 heap 区域的。当其申请内存时，就需要一个结构来记录对应的信息，而 heap_info 的作用就是这个。而且当该 heap 的资源被使用完后，就必须得再次申请内存了。此外，一般申请的 heap 是不连续的，因此需要记录不同 heap 之间的链接结构。
该数据结构是专门为从 Memory Mapping Segment 处申请的内存准备的，即为非主线程准备的。
主线程可以通过 sbrk() 函数扩展 program break location 获得（直到触及 Memory Mapping Segment），只有一个 heap，没有 heap_info 数据结构。
heap_info 的主要结构如下
1 |
|
1 |
|
该结构主要是描述堆的基本信息，包括
- 堆对应的 arena 的地址
- 由于一个线程申请一个堆之后，可能会使用完，之后就必须得再次申请。因此，一个线程可能会有多个堆。prev 即记录了上一个 heap_info 的地址。这里可以看到每个堆的 heap_info 是通过单向链表进行链接的。
- size 表示当前堆的大小
- 最后一部分确保对齐
pad 里负数的缘由是什么呢？
pad 是为了确保分配的空间是按照 MALLOC_ALIGN_MASK+1 (记为 MALLOC_ALIGN_MASK_1) 对齐的。在 pad 之前该结构体一共有 6 个 SIZE_SZ 大小的成员, 为了确保 MALLOC_ALIGN_MASK_1 字节对齐, 可能需要进行 pad，不妨假设该结构体的最终大小为 MALLOC_ALIGN_MASK_1*x，其中 x 为自然数，那么需要 pad 的空间为 MALLOC_ALIGN_MASK_1 * x - 6 * SIZE_SZ = (MALLOC_ALIGN_MASK_1 * x - 6 * SIZE_SZ) % MALLOC_ALIGN_MASK_1 = 0 - 6 * SIZE_SZ % MALLOC_ALIGN_MASK_1=-6 * SIZE_SZ % MALLOC_ALIGN_MASK_1 = -6 * SIZE_SZ & MALLOC_ALIGN_MASK。
看起来该结构应该是相当重要的，但是如果如果我们仔细看完整个 malloc 的实现的话，就会发现它出现的频率并不高。
malloc_state
该结构用于管理堆，记录每个 arena 当前申请的内存的具体状态，比如说是否有空闲 chunk，有什么大小的空闲 chunk 等等。无论是 thread arena 还是 main arena，它们都只有一个 malloc state 结构。由于 thread 的 arena 可能有多个，malloc state 结构会在最新申请的 arena 中。
注意，main arena 的 malloc_state 并不是 heap segment 的一部分，而是一个全局变量，存储在 libc.so 的数据段。
其结构如下
1 | struct malloc_state |
- _libc_lock_define(, mutex);
- 该变量用于控制程序串行访问同一个分配区，当一个线程获取了分配区之后，其它线程要想访问该分配区，就必须等待该线程分配完成后才能够使用。
- flags
- flags 记录了分配区的一些标志，比如 bit0 记录了分配区是否有 fast bin chunk ，bit1 标识分配区是否能返回连续的虚拟地址空间。具体如下
1 | /* |
1 | /* |
- fastbinsY[NFASTBINS]
- 存放每个 fast chunk 链表头部的指针
- top
- 指向分配区的 top chunk
- last_reminder
- 最新的 chunk 分割之后剩下的那部分
- bins
- 用于存储 unstored bin，small bins 和 large bins 的 chunk 链表。
- binmap
- ptmalloc 用一个 bit 来标识某一个 bin 中是否包含空闲 chunk 。
malloc_par
！！待补充！！
基础操作
unlink
unlink 用来将一个双向链表（只存储空闲的 chunk）中的一个元素取出来，可能在以下地方使用
- malloc
- 从恰好大小合适的 large bin 中获取 chunk。
- 这里需要注意的是 fastbin 与 small bin 就没有使用 unlink，这就是为什么漏洞会经常出现在它们这里的原因。
- 依次遍历处理 unsorted bin 时也没有使用 unlink 。
- 从比请求的 chunk 所在的 bin 大的 bin 中取 chunk。
- 从恰好大小合适的 large bin 中获取 chunk。
- free
- 后向合并，合并物理相邻低地址空闲 chunk。
- 前向合并，合并物理相邻高地址空闲 chunk（除了 top chunk）。
- malloc_consolidate
- 后向合并，合并物理相邻低地址空闲 chunk。
- 前向合并，合并物理相邻高地址空闲 chunk（除了 top chunk）。
- realloc
- 前向扩展，合并物理相邻高地址空闲 chunk（除了 top chunk）。
由于 unlink 使用非常频繁，所以 unlink 被实现为了一个宏，如下
1 | /* Take a chunk off a bin list */ |
这里我们以 small bin 的 unlink 为例子介绍一下。对于 large bin 的 unlink，与其类似，只是多了一个 nextsize 的处理。
可以看出， P 最后的 fd 和 bk 指针并没有发生变化，但是当我们去遍历整个双向链表时，已经遍历不到对应的链表了。这一点没有变化还是很有用处的，因为我们有时候可以使用这个方法来泄漏地址
- libc 地址
- P 位于双向链表头部，bk 泄漏
- P 位于双向链表尾部，fd 泄漏
- 双向链表只包含一个空闲 chunk 时，P 位于双向链表中，fd 和 bk 均可以泄漏
- 泄漏堆地址，双向链表包含多个空闲 chunk
- P 位于双向链表头部，fd 泄漏
- P 位于双向链表中，fd 和 bk 均可以泄漏
- P 位于双向链表尾部，bk 泄漏
注意
- 这里的头部指的是 bin 的 fd 指向的 chunk，即双向链表中最新加入的 chunk。
- 这里的尾部指的是 bin 的 bk 指向的 chunk，即双向链表中最先加入的 chunk。
同时，无论是对于 fd，bk 还是 fd_nextsize ，bk_nextsize，程序都会检测 fd 和 bk 是否满足对应的要求。
1 | // fd bk |
看起来似乎很正常。我们以 fd 和 bk 为例，P 的 forward chunk 的 bk 很自然是 P ，同样 P 的 backward chunk 的 fd 也很自然是 P 。如果没有做相应的检查的话，我们可以修改 P 的 fd 与 bk，从而可以很容易地达到任意地址写的效果。关于更加详细的例子，可以参见利用部分的 unlink 。
注意：堆的第一个 chunk 所记录的 prev_inuse 位默认为 1。
malloc_printerr
在 glibc malloc 时检测到错误的时候，会调用 malloc_printerr 函数。
1 | static void malloc_printerr(const char *str) { |
主要会调用 __libc_message 来执行abort 函数，如下
1 | if ((action & do_abort)) { |
在abort 函数里，在 glibc 还是 2.23 版本时，会 fflush stream。
1 | /* Flush all streams. We cannot close them now because the user |
堆初始化
堆初始化是在用户第一次申请内存时执行 malloc_consolidate 再执行 malloc_init_state 实现的。这里不做过多讲解。可以参见 malloc_state 相关函数。
申请内存块
__libc_malloc
一般我们会使用 malloc 函数来申请内存块，可是当仔细看 glibc 的源码实现时，其实并没有 malloc 函数。其实该函数真正调用的是 __libc_malloc 函数。为什么不直接写个 malloc 函数呢，因为有时候我们可能需要不同的名称。此外，__libc_malloc 函数只是用来简单封装 _int_malloc 函数。_int_malloc 才是申请内存块的核心。下面我们来仔细分析一下具体的实现。
该函数会首先检查是否有内存分配函数的钩子函数（__malloc_hook），这个主要用于用户自定义的堆分配函数，方便用户快速修改堆分配函数并进行测试。这里需要注意的是，用户申请的字节一旦进入申请内存函数中就变成了无符号整数。
1 | // wapper for int_malloc |
接着会寻找一个 arena 来试图分配内存。
1 | arena_get(ar_ptr, bytes); |
然后调用 _int_malloc 函数去申请对应的内存。
1 | victim = _int_malloc(ar_ptr, bytes); |
如果分配失败的话，ptmalloc 会尝试再去寻找一个可用的 arena，并分配内存。
1 | /* Retry with another arena only if we were able to find a usable arena before. */ |
如果申请到了 arena，那么在退出之前还得解锁。
1 | if (ar_ptr != NULL) __libc_lock_unlock(ar_ptr->mutex); |
判断目前的状态是否满足以下条件
- 要么没有申请到内存
- 要么是 mmap 的内存
- 要么申请到的内存必须在其所分配的 arena 中
1 | assert(!victim || chunk_is_mmapped(mem2chunk(victim)) ||ar_ptr == arena_for_chunk(mem2chunk(victim))); //断言语句，假则中断程序，确保在特定情况下，victim指针的状态与堆管理器的状态相符合 |
最后返回内存。
1 | return victim; |
_int_malloc
_int_malloc 是内存分配的核心函数，其核心思路有如下
- 它根据用户申请的内存块大小以及相应大小 chunk 通常使用的频度（fastbin chunk, small chunk, large chunk），依次实现了不同的分配方法。
- 它由小到大依次检查不同的 bin 中是否有相应的空闲块可以满足用户请求的内存。
- 当所有的空闲 chunk 都无法满足时，它会考虑 top chunk。
- 当 top chunk 也无法满足时，堆分配器才会进行内存块申请。
1 | 在进入该函数后，函数立马定义了一系列自己需要的变量，并将用户申请的内存大小转换为内部的 chunk 大小。 |
1 | static void *_int_malloc(mstate av, size_t bytes) { |
arena
1 | /* There are no usable arenas. Fall back to sysmalloc to get a chunk from mmap. */ |
fast bin
如果申请的 chunk 的大小位于 fastbin 范围内，需要注意的是这里比较的是无符号整数。此外，是从 fastbin 的头结点开始取 chunk。
1 | /* |
small bin
如果获取的内存块的范围处于 small bin 的范围，那么执行如下流程
1 | /* |
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 进行合并，以便减少堆中的碎片。
1 | /* |
bk是前驱节点，fd是后继节点，别记错了咩
大循环 - 遍历 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。
1 | /* |
unsorted bin 遍历
先考虑 unsorted bin，再考虑 last remainder(是最近一次非精确匹配的剩余块) ，但是对于 small bin chunk 的请求会有所例外。
注意 unsorted bin 的遍历顺序为 bk。
1 | // 如果 unsorted bin 不为空 |
SMALL REQUEST
如果用户的请求为 small bin chunk，那么我们首先考虑 last remainder，如果 last remainder 是 unsorted bin 中的唯一一块的话， 并且 last remainder 的大小分割后还可以作为一个 chunk ，为什么没有等号？
1 | /* |
初始取出
1 | /* remove from unsorted list */ |
EXACT FIT
如果从 unsorted bin 中取出来的 chunk 大小正好合适，就直接使用。这里应该已经把合并后恰好合适的 chunk 给分配出去了。
1 | /* Take now instead of binning if exact fit */ |
PLACE CHUNK IN SMALL BIN
把取出来的 chunk 放到对应的 small bin 中。
1 | /* place chunk in bin */ |
PLACE CHUNK IN LARGE BIN
把取出来的 chunk 放到对应的 large bin 中。
1 | } else { |
最终取出
1 | // 放到对应的 bin 中，构成 bck<-->victim<-->fwd。 |
WHILE 迭代次数
while 最多迭代 10000 次后退出。
1 | // #define MAX_ITERS 10000 |
large chunk
注： 或许会很奇怪，为什么这里没有先去看 small chunk 是否满足新需求了呢？这是因为 small bin 在循环之前已经判断过了，这里如果有的话，就是合并后的才出现 chunk。但是在大循环外，large chunk 只是单纯地找到其索引，所以觉得在这里直接先判断是合理的，而且也为了下面可以再去找较大的 chunk。
如果请求的 chunk 在 large chunk 范围内，就在对应的 bin 中从小到大进行扫描，找到第一个合适的。
1 | /* |
寻找较大 chunk
如果走到了这里，那说明对于用户所需的 chunk，不能直接从其对应的合适的 bin 中获取 chunk，所以我们需要来查找比当前 bin 更大的 fast bin ， small bin 或者 large bin。
1 | /* |
找到一个合适的 MAP
1 | /* Skip rest of block if there are no more set bits in this block. |
找到合适的 BIN
1 | /* Advance to bin with set bit. There must be one. */ |
简单检查 CHUNK
1 | /* Inspect the bin. It is likely to be non-empty */ |
真正取出 CHUNK
1 | else { |
使用 top chunk
如果所有的 bin 中的 chunk 都没有办法直接满足要求（即不合并），或者说都没有空闲的 chunk。那么我们就只能使用 top chunk 了。
1 | use_top: |
堆内存不够
如果堆内存不够，我们就需要使用 sysmalloc 来申请内存了。
1 | /* |
_libc_calloc
calloc 也是 libc 中的一种申请内存块的函数。在 libc中的封装为 _libc_calloc，具体介绍如下
1 | /* |
sysmalloc
正如该函数头的注释所言，该函数用于当前堆内存不足时，需要向系统申请更多的内存。
1 | /* |
基本定义
1 | static void *sysmalloc(INTERNAL_SIZE_T nb, mstate av) { |
1 | static void *sysmalloc(INTERNAL_SIZE_T nb, mstate av) { |
我们可以主要关注一下 pagesize，其
1 |
|
所以，pagesize=4096=0x1000。
考虑 mmap
正如开头注释所言如果满足如下任何一种条件
- 没有分配堆。
- 申请的内存大于
mp_.mmap_threshold，并且 mmap 的数量小于最大值，就可以尝试使用 mmap。
默认情况下，临界值为
1 | static struct malloc_par mp_ = { |
DEFAULT_MMAP_THRESHOLD 为 128*1024 字节，即 128 K。
1 |
|
下面为这部分代码，目前不是我们关心的重点，可以暂时跳过。
1 | /* |
mmap 失败或者未分配堆
1 | /* There are no usable arenas and mmap also failed. */ |
如果是这两种情况中的任何一种，其实就可以退出了。。
记录旧堆信息
1 | /* Record incoming configuration of top */ |
检查旧堆信息 1
1 | /* |
这个检查要求满足其中任何一个条件
old_top == initial_top(av) && old_size == 0，即如果是第一次的话，堆的大小需要是 0。- 新的堆，那么
(unsigned long)(old_size) >= MINSIZE && prev_inuse(old_top)，堆的大小应该不小于MINSIZE，并且前一个堆块应该处于使用中。((unsigned long)old_end & (pagesize - 1)) == 0)，堆的结束地址应该是页对齐的，由于页对齐的大小默认是 0x1000，所以低 12 个比特需要为 0。
检查旧堆信息 2
1 | /* Precondition: not enough current space to satisfy nb request */ |
根据 malloc 中的定义
1 | static void *_int_malloc(mstate av, size_t bytes) { |
nb 应该是已经加上 chunk 头部的字节，为什么还要加上 MINSIZE呢？这是因为 top chunk 的大小应该至少预留 MINSIZE 空间，以便于合并。
tcache(gblic>=2.26)
tcache 是 glibc 2.26 (ubuntu 17.10) 之后引入的一种技术（see commit），目的是提升堆管理的性能。但提升性能的同时舍弃了很多安全检查，也因此有了很多新的利用方式。
主要参考了 glibc 源码，angelboy 的 slide 以及 tukan.farm，链接都放在最后了。
相关结构体
tcache 引入了两个新的结构体，tcache_entry 和 tcache_perthread_struct。
这其实和 fastbin 很像，但又不一样。
tcache_entry
1 | /* We overlay this structure on the user-data portion of a chunk when |
tcache_entry 用于链接空闲的 chunk 结构体，其中的 next 指针指向下一个大小相同的 chunk。
需要注意的是这里的 next 指向 chunk 的 user data，而 fastbin 的 fd 指向 chunk 开头的地址。
而且，tcache_entry 会复用空闲 chunk 的 user data 部分。
tcache_perthread_struct
1 | /* There is one of these for each thread, which contains the |
每个 thread 都会维护一个 tcache_perthread_struct，它是整个 tcache 的管理结构，一共有 TCACHE_MAX_BINS 个计数器和 TCACHE_MAX_BINS项 tcache_entry，其中
tcache_entry用单向链表的方式链接了相同大小的处于空闲状态（free 后）的 chunk，这一点上和 fastbin 很像。counts记录了tcache_entry链上空闲 chunk 的数目，每条链上最多可以有 7 个 chunk。（为了在tcache中保持较小的内存开销和更好的性能，可能在不同libc上有不同的限制，例如较早版本有的4或者8）
用图表示大概是：（next指针存在fd区域）
基本工作方式
- 第一次 malloc 时，会先 malloc 一块内存用来存放
tcache_perthread_struct。 - free 内存，且 size 小于 small bin size 时
- tcache 之前会放到 fastbin 或者 unsorted bin 中
- tcache 后：
- 先放到对应的 tcache 中，直到 tcache 被填满（默认是 7 个）
- tcache 被填满之后，再次 free 的内存和之前一样被放到 fastbin 或者 unsorted bin 中
- tcache 中的 chunk 不会合并（不取消 inuse bit）
- malloc 内存，且 size 在 tcache 范围内
- 先从 tcache 取 chunk，直到 tcache 为空
- tcache 为空后，从 bin 中找
- tcache 为空时，如果
fastbin/smallbin/unsorted bin中有 size 符合的 chunk，会先把fastbin/smallbin/unsorted bin中的 chunk 放到 tcache 中，直到填满。之后再从 tcache 中取；因此 chunk 在 bin 中和 tcache 中的顺序会反过来
Tcache的相关知识
在32位系统中，bin会存放12-512字节的chunk，在64位系统中bin会存放24-1032字节的chunk。也就是说符合这些大小的chunk被释放后不会先加入fastbin，而是会先放入TcacheBin中。**(和fastbin的存储大小差不多一致)**
TcacheBin以单链表构成
什么时候用到Tcache：
free：在释放chunk的时候，如果chunk符合Tcachebin的大小，并且该bin还没有被装满(没有七个)，则会优先放入TcacheBin中
malloc：
- 当我们使用malloc的时候，返回一个chunk，并且该chunk是从fastbin中返回的，那么该chunk所对应下标的所有chunk都会被放入TcacheBin(当然，前提是Tcachebin没有被装满)，而且由于fastbin和Tcachebin都是先进后出，所以就会导致chunk在移动完以后chunk的顺序和fastbin中的顺序相反。
- smallbin中的也一样，返回的一个chunk属于smallbin，那么smallbin中对应的chunk就会全部放入Tcachebin(前提是没有装满)
- 当出现堆块的合并等其它情况的时候，每一个符合条件的chunk都会优先放入TcacheBin中，而不是直接返回(除非Tcache已满)。寻找结束后Tcache会返回其中一个
比较重要的一点，当我们调用malloc的时候，其实是先调用libc_malloc然后调用int_malloc，但是如果我们请求的大小在Tcachebin中有符合的chunk那么就会在libc_malloc中返回该chunk，而不会调用int_malloc
我们在处理chunk的过程中，如果在Tcache中的chunk已满，那么会直接返回最后一个chunk；binning code 结束后，如果没有直接返回（如上），那么如果有至少一个符合要求的 chunk 被找到，则返回最后一个。
tcache 中的 chunk 不会被合并，无论是相邻 chunk，还是 chunk 和 top chunk。因为这些 chunk 会被标记为 inuse。
源码分析
接下来从源码的角度分析一下 tcache。
__libc_malloc
第一次 malloc 时，会进入到 MAYBE_INIT_TCACHE ()
1 | void * |
__tcache_init()
附:arena是一块连续的内存区域(包括Heap Arena[Small bin and Large bin]和Thread-specific Arena[Fast bin and Tcache])
其中 **MAYBE_INIT_TCACHE () 在 tcache 为空（即第一次 malloc）时调用了 tcache_init()**，直接查看 tcache_init()
1 | tcache_init(void) |
tcache_init() 成功返回后，tcache_perthread_struct 就被成功建立了。
申请内存
接下来将进入申请内存的步骤
1 | // 从 tcache list 中获取内存 |
在 tcache->entries 不为空时，将进入 tcache_get() 的流程获取 chunk，否则与 tcache 机制前的流程类似，这里主要分析第一种 tcache_get()。这里也可以看出 tcache 的优先级很高，比 fastbin 还要高（ fastbin 的申请在没进入 tcache 的流程中）。
tcache_get()
看一下 tcache_get()
1 | /* Caller must ensure that we know tc_idx is valid and there's |
tcache_get() 就是获得 chunk 的过程了。可以看出这个过程还是很简单的，从 tcache->entries[tc_idx] 中获得第一个 chunk，tcache->counts 减一，几乎没有任何保护。
__libc_free()
看完申请，再看看有 tcache 时的释放
1 | void |
__libc_free() 没有太多变化，**MAYBE_INIT_TCACHE () 在 tcache 不为空失去了作用**。
_int_free()
跟进 `_int_free()
1 | static void |
判断 tc_idx 合法，tcache->counts[tc_idx] 在 7 个以内时，就进入 tcache_put()，传递的两个参数是要释放的 chunk 和该 chunk 对应的 size 在 tcache 中的下标。
tcache_put()
1 | /* Caller must ensure that we know tc_idx is valid and there's room |
tcache_puts() 完成了把释放的 chunk 插入到 tcache->entries[tc_idx] 链表头部的操作，也几乎没有任何保护。并且 没有把 p 位置零。(P位是指前一个内存是否分配)