堆基础01：ptmalloc2初探

前言

• 本篇第一部分会介绍堆分配涉及到的系统调用，这部分比较简单，通过实验即可理解；第二部分介绍 ptmalloc 分配器的起源与大致的分配策略；第三部分则是堆管理涉及到的数据结构，从而为下一篇源码分析做好准备
• 本篇内容均基于 64 位下的 Ubuntu 系统，所以描述的每个基本内存块（例如栈中的一个单元，寄存器默认的存储大小，一个指针的大小）都是 8 字节，而不是 4 字节
• 本篇内容基于pukrquq与xi@0ji233两位师傅发表在看雪的文章，此篇也是我正式开始堆学习的第一篇，目前计划第二篇为 glibc2.31 部分源码的分析，第三篇则以howtoheap上的练习为主，更全面的去了解堆。再之后，根据先前的学习，将部分内容总结经验，再在看雪发一篇文章
• 本篇数据结构的截图部分，均以 glibc2.31 版本的源码为依据，但部分来自网上的图片，可能是经典的 glibc2.23 或更早的版本，但不影响学习

调试工具

pwndbg和peda是比较常用的gdb插件，两者各有优势，可惜并不兼容：

• pwndbg在调试堆的数据结构时很方便，常用命令可以参考这里
• peda在查找字符串等功能时方便，常用命令可以参考这里

安装不困难（pwndbg可能需要依次安装psutil、pyelftools、capstone、pycparser），下载后，只需在home目录下的.gdbinit中写入

bash

source ~/peda/peda.py
# 或者
source ~/pwndbg/gdbinit.py

由于这类辅助用的gdb插件都不兼容，所以在使用某一款插件时需注释掉其它插件。如果结合源码调试的话，可配合 pwndbg 使用，并在.gdbinit写入源码路径，可参考这里

进程堆管理

Linux提供了两种堆空间分配的方式，一个是brk系统调用，另一个是mmap系统调用。

上图为经典的Linux进程内存布局，从中可以看出：

• .bss段之上，向上扩展的一块内存是由brk系统调用分配的堆空间
• stack空间之下，向下扩展的一块包含文件映射和匿名映射的内存，是由mmap系统调用分配的堆空间

brk/sbrk

Linux手册中，对于brk与sbrk的描述如下：

brk() and sbrk() change the location of the program break, which defines the end of the process’s data segment (i.e., the program break is the first location after the end of the uninitialized data segment). Increasing the program break has the effect of allocating memory to the process; decreasing the break deallocates memory

这里结合上面那张Linux进程内存布局图，会很好理解，在ASLR开启前后会有细微差别，具体如下：

• ASLR 关闭时，两者指向 data/bss 段的末尾，也就是 end_data
• ASLR 开启时，两者指向 data/bss 段的末尾加上一段随机 brk 偏移

关于这两个调用的用法，参考手册就行：

c

#include 

int brk(void *addr);
void *sbrk(intptr_t increment);

brk() sets the end of the data segment to the value specified by addr, when that value is reasonable, the system has enough memory, and the process does not exceed its maximum data size

sbrk() increments the program’s data space by increment bytes. Calling sbrk() with an increment of 0 can be used to find the current location of the program break. （这里是因为sbrk()返回值为执行该调用前的program break，即previous program break）

下面用例子加深一下印象：

c

#include 
#include 

void main() {

	void *curr_brk, *tmp_brk, *pre_brk;

	printf("Current Process PID: %d\n", getpid());


	tmp_brk = curr_brk = sbrk(0);
	printf("After Initialize: %p\n", curr_brk);
	getchar();

	brk(curr_brk+4096);
	curr_brk = sbrk(0);
	printf("After Brk: %p\n", curr_brk);
	getchar();


	pre_brk = sbrk(4096);
	curr_brk = sbrk(0);	
	printf("Before Sbrk: %p\n", pre_brk);
	printf("After Sbrk: %p\n", curr_brk);
	getchar();

	brk(tmp_brk);
	curr_brk = sbrk(0);
	printf("After Restore: %p\n", curr_brk);
	getchar();
}

编译，运行程序，然后观察/proc/PID/maps中进行内存布局的情况，下图展示了第一次执行brk()前后的进程堆的变化，sbrk()的情况也差不多，这里不再贴图展示。

mmap/munmap

这部分手册描述的内容比较多，先来看函数原型：

c

#include 

void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);
int munmap(void *addr, size_t length);

• mmap()用于在进程的虚拟地址空间中创建一个新的映射，并将文件或设备映射到这块内存中
  • addr：指定映射的起始地址，若该参数为NULL时，则由操作系统自己决定mapping的起始地址
  • length：指定映射的大小，该值必须大于0
  • prot：描述这段映射的内存保护属性，且不能与打开文件时设置的访问模式相冲突
  • flags：这个字段指定了mapping的一些行为属性，例如是否修改原本被映射的文件，对于映射到同一块区域的其它进程是否可见等等。其中，当设置了MAP_ANONYMOUS属性后，这块地址空间将不会映射到任何文件，其内容将会被初始化为0，我们称这块空间为匿名（Anonymous）空间，匿名空间可以用来作为堆空间。此时，fd参数将会被忽略，offset参数应设置为0
  • fd：指向将被映射到内存中的文件对象
  • offset：被映射内容在文件中的起始偏移，该值必须是页（4KB）的整数倍
• munmap则用于删除指定地址范围内的映射

下面看例子：

c

#include 
#include 
#include 

void main() {

	void *curr_brk;

	printf("Current Process PID: %d\n", getpid());
	printf("After Initialized:\n");
	getchar();

	char *addr;
	addr = mmap(NULL, (size_t)4096, PROT_READ | PROT_WRITE, \
		 MAP_PRIVATE | MAP_ANONYMOUS, 0, 0);
	printf("Mmap Finished: %p\n", addr);
	getchar();

	munmap(addr, (size_t)4096);
	printf("Unmap Finished\n");
	getchar();
}

编译运行，再观察进程内存布局，可以发现mmap()申请的堆位于ld-2.31.so之间，这个链接文件也是通过mmap映射到进程的虚拟地址空间中的。结合前面的进程内存布局，就能看的很明白了

ptmalloc2分配策略

为什么需要堆分配器

前面介绍了用于管理堆的系统调用，由于现代操作系统都是按页进行管理，一页就是4KB/4096B，所以通过brk()或mmap()申请内存时都是一页一页的去申请，如果我只需要几个字节的内存，却跟操作系统申请了一整页的内存，那就显得很浪费了；并且，如果每次分配内存都走系统调用，也会增加操作系统的负担，因此，诞生了堆分配器，通过实现 malloc 与 free 辅助操作系统进行堆的管理。

早期 Linux 中的 malloc 版本是由 Doug Lea 实现的，这个时候的堆分配器也叫做 dlmalloc，dlmalloc 存在的问题是不支持多线程；后来 Wolfram Gloger 基于 dlmalloc 进行改进，实现了支持多线程的 ptmalloc 堆分配器，并随着时间发展形成了 ptmalloc2，也就是现在常用的堆分配器。

多线程实现

为了支持多线程并行处理时对于内存的并发请求操作，malloc 的实现中把全局用户堆（heap）划分成很多子堆（sub-heap）。这些子堆是按照循环单链表的形式组织起来的。每一个子堆利用互斥锁（mutex）使线程对于该子堆的访问互斥。当某一线程需要调用 malloc 分配内存空间时，该线程搜索循环链表试图获得一个没有加锁的子堆。如果所有的子堆都已经加锁，那么 malloc 会开辟一块新的子堆，对于新开辟的子堆默认情况下是不加锁的，因此线程不需要阻塞就可以获得一个新的子堆并进行分配操作。在回收 free 操作中，线程同样试图获得待回收块所在子堆的锁，如果该子堆正在被别的线程使用，则需要等待直到其他线程释放该子堆的互斥锁之后才可以进行回收操作。

结构体概述

ptmalloc2 在进行分配的时候一定会根据实际选择一个最优策略，例如调用malloc(1)，我们认为分给它1字节就好了，然而现实没有那么理想。如果程序向这个1字节的内存块里面写入数据，那么我怎么判断这个只包含1字节的内存块是否正在被使用呢？这个内存块的分界线又是如何界定的呢？所以分割内存块的时候不可避免地要在内存块中额外开出一部分区域用于管理。

ptmalloc2在源码中定义了一个结构体 malloc_chunk 来描述这些内存块，所以内存块也简称 chunk。这个结构体包含了当前 chunk 的大小，前一个 chunk 的大小，前向和后向指针，以及一些标志位。当前 chunk 的大小，以及前一个 chunk 的大小，反映了当前 chunk 在堆中的位置情况，可以通过当前 chunk 地址 + 当前 chunk 的大小，得到后一个 chunk 的位置，用当前 chunk 地址 - 前一个 chunk 的大小，就可以得到前一个 chunk 的位置，这个操作，在对当前 chunk 进行 free 时会用到，因为会在 free 时根据标志位判断要被 free 的 chunk 在堆中位置前后的 chunk 是否是空闲的，如果空闲，那会先进行合并操作，再进行 free。

malloc_chunk 是用来描述内存块的，ptmalloc2 在对这些内存块进行管理时，用到了一个 bin 的概念，bin 可以翻译成一个容器，在glibc2.31版本中，bin 包括 fast bins、unsorted bin、small bin、large bin 和 tcache bin。堆管理器会根据 chunk 的类型将其放入对应的 bin 中，为了方便管理，这些 bin 都是以链表的形式存在，malloc_chunk 中包含的前向和后向指针，就是用于这里的链表管理。

分配策略

ptmalloc2 会在第一次执行 malloc 的时候向操作系统申请 0x21000B（132KB），后续分配就不会向操作系统申请内存，而是会从这块132KB的堆里面进行分割小块，直到用完的时候才会再次申请内存。

接下来看具体的分配策略，首先根据申请的字节大小，系统选择一个合适的 chunksize 作为需要分配的 chunk 大小，这个 chunksize 会通过特定的宏操作计算得出，比方说，chunksize 至少为 0x20 字节，这个大小的 chunk 最多可以容纳 0x10 字节的数据，那么当申请的空间小于等于 0x10 字节时，ptmalloc2 就会分配一个大小为 0x20 字节的 chunk。这里解释下为什么 chunksize 至少为 0x20 字节，malloc_chunk 本身包含四个字段，prev_chunksize（8字节），chunksize（8字节），fwd（8字节）和 bck（8字节），其中 chunksize 描述的是整个 chunk 的大小，包含这4个字段和数据；另外，当 chunk 被使用时，fwd 和 bck 两个字段是不使用的，因为它们仅在链式管理时使用（当 chunk 放入 bin 中，也意味着这个 chunk 此时是空闲的，暂时不使用了），当 chunk 正在被使用时，这两个字段是用不到的，自然就可以用来存储数据了，也就是说，原本 malloc_chunk 结构体中两个用来存放指针的空间，可以用来存放数据，大小为 0x10 字节。

计算出需要分配多大的 chunk 以后，就会开始去不同的 bin 中查找符合条件的 chunk：

1. 首先是 tcache bin，这是在 glibc2.26 开始引入的缓存机制，默认开启。如果申请的 chunksize 不属于 large bin，并且 tcache bin 已经初始化了，并且 tcache bin 中有对应的大小的 chunk 块，那么就会直接从 tcache bin 中取出这个 chunk 拿去用。从 tcache bin 中取出 chunk 的操作是发生在调用_int_malloc()之前的，是最先发生的操作
2. 接下来会进入_int_malloc()，这是实现 malloc 的核心函数。进入后会先判断 chunksize 是否属于 fast bins，如果属于就去 fast bins 里面找，fast bins 的判断是严格匹配的，如果 chunksize 是 0x30 字节，那就在 fast bins 中找空闲的 0x30 字节的 chunk，不会说 0x40 字节的 chunk 好像还挺合适就拿了，不会
3. fast bins 没有找到合适的，则判断 chunksize 大小是否位于 small bin 的范围区间，如果符合，就会去 small bin 里面找，small bin 包含 62 条 bin 链，和 fast bins 类似，small bin 的每条 bin 链中的 chunk 大小是相同的，因此直接在对应 chunksize 的 bin 链中找就行，同样也是严格匹配 chunksize
4. 如果在申请的 chunksize 大小位于 large bin 范围区间（或者在 fast bins 和 small bin 中未能找到合适的 chunk），则会先将 fast bins 中的 chunk 合并，插入到 unsorted bin 中，接下来遍历 unsorted bin 中的所有 chunk，同时将遍历到的 chunk 从 unsorted bin 上摘下，看这个 chunk 的大小是否符合申请的 chunksize，如果符合，就将这个 chunk 返回给用户。否则，就根据这个 chunk 的 chunksize 将其放入 small bin 或者 large bin 中。其实这一步，主要是将 unsorted bin 中的 chunk 分配到 small bin 和 large bin 中
5. 这里还有一点很重要，在遍历 unsorted chunk 开始处有一个判断条件，会判断申请的是否为 small chunk（前面判断的 small bin 中的 chunk，这里判断是 unsorted bin 中属于 small bin 范围区间的的 chunk，即尚未分配到 small bin 中的一个 chunk），且 unsorted bin 中只有一个 chunk，且这个 chunk 为 last remainder chunk，且这个 chunk 满足所需的大小加上 0x20，如果满足这四个条件，则会尝试对这个 last remainder chunk 进行切割，参考下面（6）。切割后剩余的 chunk 仍然作为 last remainder chunk 存在
6. 接下来，开始在 large bin 中寻找合适的 chunk，由于 large bin 的每个 bin 中的 chunk 大小是不一定相同的，所以在查找时，会先试图找到一个匹配申请的 chunksize 的 chunk。若找不到，就选择一个略微大一些的 chunk，然后判断这个 chunk 分割出 chunksize 后余下的 remainder chunk 是否能达到最小的 chunksize（即 0x20字节），如果可以达到，那就先分割，把 chunksize 的部分返回给申请的程序。余下的 remainder chunk 则链入 unsorted bin 中，当发生完这个操作后，该 remainder chunk 是最近一次被分割后得到的 chunk，因此又称作 last remainder chunk（这里的 remainder chunk 在源码中并没有被设置为 last remainder chunk，具体有待考证）；如果 remainder chunk 达不到 0x20 字节，就不分割，把一整块返回给程序
7. 前面提到的 small bin、unsorted bin、large bin 都属于 bins 中的一个或一组链表，下文会分析到 bins 中各个 bin 的组织结构。
8. 如果说，在 large bin 中也没找到合适的 chunk，则会通过一个位图判断整个 bins 中是否包含符合申请 chunksize 要求的 bin 链，然后再在这个 bin 链上找是否有符合要求的 chunk，若有的话，则和 （6） 一样根据情况进行分割
9. 如果 bins 中也没有符合要求的 chunk，则会去 top chunk 进行分割。这个 top chunk 位于一开始申请的 0x21000 字节的高地址处，它不属于任何 bin。如果 top chunk 的大小满足用户所需求的 chunk 大小，那么就会分割一块返回给申请的程序，但是余下的 remainder chunk 不会链入 unsorted bin 中，仍以 top chunk 的形式存在着
10. 如果 top chunk 仍然不满足申请的 chunksize 需求，那么就会根据实际情况，通过sbrk()扩展 top chunk，或者调用mmap()分配新的堆

堆管理结构

分配区

前面提到，ptmalloc2 在实现多线程时，在 malloc 的实现中把全局用户堆（heap）划分成很多子堆（sub-heap），每一个子堆利用互斥锁使线程对于该子堆的访问互斥。这里 ptmalloc2 引入了分配区（arena）的概念，每个arena 本质上是完全不同的堆，他们独自管理自己的 chunk 和 bins。arena 分为 main_arena 和 thread_arena。malloc 内部通过brk()和mmap()系统调用来分配内存。每个进程只有一个 main_arena（称为主分配区），但是可以有多个 thread_arena（或者non_main_arena，非主分配区）。

• main_arena：
  1. 对应进程 heap 段，由brk()函数创建
  2. 分配区信息由 malloc_state 结构体存储
  3. main_arena 的 malloc_state 结构体存储在该进程链接的 libc.so 的数据段
  4. main arena 的大小可以扩展。
• thread_arena：
  1. 对应进程的 mmap 段，thread_arena 由mmap()函数创建
  2. 分配区信息由 malloc_state 和 heap_info 两个结构体存储
  3. thread_arena 的 malloc_state 和 heap_info 存放在堆块的头部
  4. thread_arena 的大小不可以扩展，用完之后需调用mmap()申请一个新的 thread_arena

heap_info

heap_info 这个结构相当于 Heap Header，它是堆的管理结构之一。前面提到了 main_arena 和 thread_arena，其中 main_arena 是不需要 heap_info 结构体的（因为它只有一个堆），所以这里只需要关注它在 thread_arena 中的作用就行了。在非主分配区中是可能包含多个堆的，原因在于 thread_arena 中的堆是通过mmap()调用申请的，因此不能通过brk()进行扩展，当空间不足时，只能够再次调用mmap()申请新的堆空间，heap_info 就是管理这些通过mmap()申请出来的堆空间的，包括第一次申请的在内，thread_arena 申请的每个堆空间，都会对应一个 heap_info 来描述并管理这个堆

• ar_ptr：这个字段指向堆所在的分配区（arena），是一个 malloc_state 结构体，一个堆只能对应一个分配区
• prev：将同一个分配区（arena）中，堆的 heap_info 结构，用单向链表链接起来。这里 prev 指向链表中前一个堆对应的 heap_info
• size：当前堆的大小
• mprotect_size：当前堆还没有被分配的内存大小
• pad：用于对齐的，不用关心

malloc_state

malloc_state 相当于 Arena Header，前面提到 thread_arena 中的每个堆都对应一个 heap_info，这些所有堆共有一个 malloc_state，它用来表示分配区，位于整个分配区的头部。总结一下就是每个 thread_arena 对应一个 malloc_state，thread_arena 中的每个堆对应一个 heap_info。当然，main_arena 也对应一个 malloc_state，但是存储在该进程链接的 libc.so 的数据段中

• mutex：用于串行化访问分配区（arena），当有多个线程访问同一个分配区时，第一个获得这个 mutex 的线程将使用该分配区分配内存，分配完成后，释放该分配区的 mutex，以便其它线程使用该分配区
• flags：记录分配区的一些标志
• have_fastchunks：标志位，判断 fast bin 最近是否有插入空闲块
• fastbinsY：用来记录和管理 fast bin 的链表数组，每条都是单链表
• top：指向 top chunk
• last_remainder：指向 last remainder chunk
• bins：包括 unsorted bin、small bin 和 large bin，具体参考下文介绍 bins 时的图，其中 NBINS 定义为 128
• binmap：用于快速查找对应 index 的 bin 是否为空的一个位图
• next：指向下一个 arena，arena 之间通过单循环链表构成
• next_free：指向下一个空闲的 arena。这是一个链表（free_list），串着空闲的分配区（free_arena），访问这个链表上的空闲分配区，需要通过 free_list_lock 进行上锁
• attached_threads：附加到当前分配区的进程数。如果该值为 0，说明没有线程附加到该分配区，此时该分配区位于 free_list。这个 free_list 就是 next_free 指向的 free_list，它包含着还没有被线程附加的空闲分配区。对于多线程的程序，某个线程申请内存时，会试图从 thread_arena 中获取到分配区，在首次申请时，thread_arena 的尚未被初始化，值为 NULL。此时会进一步调用 get_free_list() 从 free_list 中找到一个尚未被附加的 free_arena 将其返回，同时将该 arena 从 free_list 上移除，并赋值给 thread_arena。这部分在分析__libc_malloc()时会再次提到
• system_mem：表示系统调用时申请的内存大小

malloc_chunk

malloc_chunk 相当于 Chunk Header，就是前面提到用来描述一个内存块的结构，chunk 在不同状态下，所使用的字段及含义也不相同，这里以定义时的结构入手进行简单的解析

• mchunk_prev_size：如果前一个（虚拟内存空间的具体位置上的前一个） chunk 是空闲的，则该字段表示前一个 chunk 的大小（通过当前 chunk 的地址，以及这个字段的值，就可以定位前一个 chunk 的地址，这样在 free 当前 chunk 时，发现前一个 chunk 也是空闲时，就会发生合并）。否则，该字段用于存储前一个 chunk 的数据，没错，当前一个 chunk 不空闲时，这个字段是不属于当前 chunk 的，而是作为前一个 chunk 的存储空间使用
• mchunk_size：表示当前 chunk 的大小，也记录了当前 chunk 和前一个 chunk 的一些属性
• fd & bk：这俩指针仅在当前 chunk 空闲时才存在，用于将 chunk 加入到对应的 bin 中进行统一的链式管理。若当前 chunk 正在被使用，则这两个指针的位置用于存放数据
• fd_nextsize & bk_nextsize：这俩指针仅在当前 chunk 空闲时，且位于 large bin 中时才存在。因为 large bin 中每条链上的 chunk 大小并不一定相同，这些大小不同的 chunk 就是用这俩指针进行链接，其中 fd_nextsize 指向 size 比自身小的里面最大的 chunk，bk_nextsize 指向 size 比自身大的里面最小的 chunk，大小相同的 chunk 则用指针 fd/bk 进行链接，这部分可以参考后面 large bin 的图示

关系

第一张图比较好看明白，即 main_arena 和 thread_arena（仅有一个堆的情况下）两个分配区中堆结构的大致情况。

这张图中的 thread_arena 包含了两个堆，此时两个堆通过 heap_info 关联，但仅有一个 malloc_state 结构，由于原先的堆空间不足了，最后的 top chunk 作为普通的 chunk 根据大小链入对应的 bin 中，新申请的堆的 top chunk 则作为新的 top chunk 存在，并由 malloc_state 中的 top 字段指向其位置。

malloc_par

这里补充一个结构体，malloc_par，虽然不是最核心的堆管理结果，但是在引入 tcache 后，它会记录一些 tcache 相关的信息，并在分配时会使用到该结构，并且对于一个进程全局拥有一个唯一的 malloc_par 实例，所以这里作简要介绍：

• trim_threshold：top chunk 的收缩阈值
• top_pad：在分配内存时是否添加额外的 pad，默认设置为0
• mmap_threshold：mmap 分配阈值
• arena_test：当进程的分配区数量小于等于 arena_test 时，不会重用已有的分配区
• arena_max：当进程的分配区数量达到 arena_max 时，不会再创建新的分配区，只会重用已有的分配区
• n_mmaps：当前进程使用 mmap() 分配的内存块的个数
• n_mmaps_max & max_n_mmaps：mmap()函数分配的内存块的最大数量
• no_dyn_threshold：是否开启mmap()分配阈值动态调整机制，默认为0，即开启
• mmaped_mem & max_mmapped_mem：统计mmap()分配的内存大小，通常这两字段的值相等
• sbrk_base：堆的起始地址
• tcache_bins：tcache bin 的数量
• tcache_max_bytes：最大 tcache chunk 的大小
• tcache_count：每个 tcache bin 中 tcache chunk 的最大数量

Chunk

一个 chunk 可以是以下几种类型之一：

• 已分配的（Allocated chunk）
• 空闲的（Free chunk）
• Top chunk
• Last Remainder chunk

Allocated Chunk

这里唯一需要解释的就是 N、M、P 这三个标志位（这里能余下这 3 位是因为 chunk 大小按照 8 字节对齐）：

• N位：表示是否为 non_main_arena，若为1，则 chunk 属于 thread_arena
• M位：表示该 chunk 是否通过mmap()申请的，若为1，则是
• P位：表示 prev_inuse，若位1，说明前一个（虚拟内存空间的具体位置上的前一个）块正在被使用。即处于 Allocated 状态

Free Chunk

Free Chunk 多出了 fd & bk 这两个指针；若为 largin bin 中的 Free Chunk，则还会多出 fd_nextsize & bk_nextsize 这俩指针。

Top Chunk

一个 arena 顶部的 chunk 被称作 top chunk，它不属于任何 bin，其信息记录在 mstate 中（即 malloc_state 结构中）。当所有 bin 中都没有空闲可用的 chunk 时，便会切割 top chunk 来满足用户的内存申请。top chunk 在进行分配时也是通过切割，若空间足够，则会从 top chunk 上切割下程序申请大小的 chunk 返回给程序，余下部分，作为新的 top chunk 存在（这个新的 top chunk，在刚分割完时也被称作 last remainder chunk，但不会链入到 unsorted bin 中）。如果连 top chunk 都不够用，则会进行如下判断：

• 如果位于 main_arena 中，通过brk()/sbrk()扩张 top chunk 的边界
• 如果位于 non_main_arena（即 thread_arena），则调用mmap()分配新的堆空间，通过 heap_info 数据结构将多个堆串连在一起

markdown

注：Top Chunk 的 PREV_INUSE 位总是1

Last Remainder Chunk

Last Remainder Chunk 来源于最近一次的 split（切割） 操作。当程序申请的 mallocsize（这里用 mallocsize 表示程序申请的 chunk 大小） 落入 large bin 对应的范围区间时，若没有找到刚好合适的块，则会选择一个大于 mallocsize 的最小 chunk 进行分配。在分配该块时进行如下判断：

• 如果 chunksize - mallocsize >= 0x20，则分割出 mallocsize 大小的 chunk 返回给用户，余下的 chunk 将会链入 unsorted bin 中，这个余下的 chunk，就被称作 last remainder chunk，表示最近一次由于 split 操作从而进入 unsorted bin 的 chunk
• 如果 chunksize - mallocsize < 0x20，直接将 chunk 返回给申请的程序，此时不存在 last remainder chunk

之后当程序再次请求 small chunk 时，且 small chunk 中未能找到合适的 chunk 时，就会判断 last remainder chunk 是否为 unsorted bin 中的唯一块，如果是，那么 last remainder chunk 会被再次分割出 small chunk 返回给程序，余下的部分继续作为新的 last remainder chunk 存在。这样，当程序进行连续的小空间内存申请时，分配到的内存都是相邻的（last remainder chunk 周围） ，从而在 free 的时候就可能会与周围的空闲 small chunk 进行合并操作，达到了更好的局部性

Bin

bin 是用来管理 free chunk 的链表，根据功能与 chunksize 的不同，可以分为：

• Fast Bin
• Unsorted Bin
• Small Bin
• Large Bin
• Tcache Bin

Fast Bin

fast bin 顾名思义，当初设计时的定位为 bins 的高速缓冲区，主要用于提高小内存分配效率，放置在 fastbinsY 数组上。当用户释放/申请一块不大于 global_max_fast 的 chunk 时，会优先考虑在 fast bin 上存放或从 fast bin 中找到是否存在合适的 chunk。它具备以下特点：

• fast bin 是单向链表（因为它不会从中间摘下一个 chunk 出来，添加与删除只发生在单链表的首尾之间），所以只用到了 malloc_chunk 结构的 fd 指针
• fast bin 中 chunk 的 prev_inuse 位设为1，即永远被视为在使用中，这意味着相邻空闲 chunk 不会合并或被切割。它的匹配规则也是定量匹配，这在前面介绍分配策略时有提到。虽然这么做导致外部碎片增多，但是 free 效率提升
• fast bin 采用先进后出（FILO）的原则，每个 bin 只存储大小相同的 chunk，最多包含 10 个，范围为 0x20 ~ 0xB0
• 初始化堆时会默认设置 global_max_fast 的值为 0x80，此时 fast bin 只包含 0x20 ~ 0x80 范围的 chunk，大于 0x80 的 chunk 在释放时会进入 unsorted bin。调用 mallopt 设置 fast bin 的最大值，则 fast bin 可以包含最大为 0xB0 的 chunk

结合下方示意图会更好理解

图二这里还出现了 bins，这部分在接下来的部分会介绍到

Bins

首先 bins 是一个数组，数组中包含了 unsorted bin、small bin 以及 large bin，并且 bins 里面的 bin 都是双链表（使用双向链表是因为有可能会从链表的中间取出一块chunk出来返还给用户）。下面先简单了解一下 bins 中包含的这 3 种 bin，接下来结合图示，介绍 bins 的大概结构以及不同 bin 的排列

• unsorted bin：
  1. 是 bins 的缓冲区，位于 bins 数组中的第一位
  2. 当用户释放的 chunk 大于 global_max_fast 或 fast bin 进行合并后得到的 chunk，都会放入 unsorted bin 中，因此，unsorted bin 中的 chunk 大小是不同的
  3. 当用户申请的 chunk 在 fast bin 与 small bin 中无法通过定量匹配找到时，会先去 unsorted bin 查找是否有合适的 chunk；若没有，则会将 unsorted bin 上的 chunk 放入 small bin 或 large bin 中，然后再去 large bin 中找
• small bin：
  1. 小于 0x400 字节（64位系统）的 chunk，在从 unsorted bin 中取下时会进入 small bin
  2. 位于 bins 数组的 2~63 位，共 62 条 small bin
  3. 与 fast bin 类似，small bin 中每条 bin 存储的 chunk 也是大小相同的；不同的是它会参与合并，因此不存在两个相邻的 free chunk，small bin 采用的策略是先进先出（FIFO）
  4. small bin 中每条 bin 之间的 chunk 大小相差 0x10 字节（64位系统）
  5. small bin 起始 bin 的 chunk 大小为 0x20 字节（64位系统）
• large bin：
  1. 大于0x200字节（32位系统）/ 0x400 字节（64位系统）的 chunk，在从 unsorted bin 中取下时会进入 large bin。换句话说，最小的 large bin 是最大的 small bin 所不能表示的大小
  2. 位于 bins 数组的 64~126 位，共 63 条 small bin
  3. large bin 中每条 bin 上的 chunk 大小不一定相同。大小相同的 chunk 用 fd/bk 链接，不相同的用 fd_nextsize/bk_nextsize 链接
  4. 每条 bin 之间 chunk 大小相差的字节也是变化的

接下来，我们结合图示，对上述概念进行巩固：

先看第一张图，这张图只是 bins 的一个简略版，不能代表 bins 中链表结构的实际情况，但是从总体上来看是符合实际的。我们这里只需要关注粉色那一栏就行：

1. bins 中包含了 126 个 bin，其中第 1 个是 unsorted bin，第 2—63 个是 small bin，第 64—126 个是 large bin
2. 由图可以看出，这 126 个 bin 的开头，都对应着一对指针 fd 与 bk，这俩指针将一条 bin 双向链接起来
3. 图中 bin1 为 unsorted bin，bin 上即存着属于 small bin 范围的 chunk，也存着属于 large bin 范围的 chunk（注意此图基于 32 位系统）
4. 图中 bin13 位于 small bin 区间，单条 bin 上的 chunk 相同
5. 图中 bin71 位于 large bin 区间，单条 bin 上的 chunk 不同

第二张图，看着更清晰些：

1. 图中 BINS[1] 对应 unsorted bin，但是通过bin_at()这个宏会发现，bin_at(1) 的位置其实指向 BINS[0]
2. 这其实是因为，尽管 bins 中的每条 bin 的开头仅需要 1 对指针即可，但是 bins 数组中的每个元素，仍然是一个 chunk
3. 这里回顾一下 malloc_state 结构中的 bins 字段，它的类型是 mchunkptr 数组，也就是 malloc_chunk 类型，这样就可以理解为什么上图会标出来整个 malloc_chunk 结构，因为 bins 数组的每个元素就是 malloc_chunk 类型
4. 由于 bin 头仅需要一对指针，prev_size 与 size 字段用不到，因此就可以忽略这两个字段的值，这样就可以让它们的位置与 fd/bk 的位置重叠，从而节省空间，这样，就形成了图一中，粉色那行的排布。每个 bin 的开头仅包含一对头指针

large bin 的每条 bin 上的 chunk 大小并不一定相同，对于它的整体排布可能不好理解，所以这里先根据上图来分析 large bin 的结构：

1. 由图，这里只展示了 large bin 中的其中一个 bin（共 63 个 bin）
2. 图中大小相同的 chunk 用同一种颜色表示，它们通过 fd & bk 指针形成一个双向循环链表。那么，对 large bin 中的任何一个 bin 来说，相同 size 的 chunk 用一条双向循环链表链接在一起
3. 对于一个 bin 来说，其中相同 size 的 chunk 已经用双向循环链表链接在一起了，此时，这些链表中的第一个 chunk，会通过 fd_nextsize & bk_nextsize 链接在一起，即不同 size 的 chunk 也用一条双向循环链表链接在一起，其中沿着 bk_nextsize，chunksize 递增，沿着 fd_nextsize，chunksize 递减
4. 因此 large bin 是一个二维双向链表

接下来看下这个 size 大小如何去看。这里引用了网上的一张图，链接在文末：

1. 图中表示的是 bins 中不同 bin 对应的 size
2. small bin 中每条 bin 上的 chunk 大小相同的，以 bin[4] 为例，在 32 位系统上，bin[4] 中每个 chunk 的大小为 32 字节，64 位则是 64 字节
3. 对于 large bin，以 bin[64] 为例，在 32 位系统上，bin[64] 中包含的 size 范围为 [512, 576)，左闭右开的一个区间。这意味着，若从 unsorted bin 中取下的 chunk 的 size 位于这个范围区间，就会被放进 bin[64] 中。64 位系统同理。
4. 看雪专家xi@0ji233也总结了一张表（仅针对 large bin），这里 copy 过来

Tcache Bin

Tcache 是从 glibc2.26 开始新增的缓存机制，用于优化线程锁竞争的问题，它为每个线程预留了一组 bin，这组 bin 不属于 bins，并具备以下特点：

1. tcache bin 中共包含 64 个 bin（定义在 TCACHE_MAX_BINS），每个 bin 中最多缓存 7 个 chunk
2. 64 位系统上以 0x10 字节递增（24 -> 1032），32位系统上以 0x8 字节递增（12 -> 516）
3. tcache 缓存的是非 large chunk
4. tcache bin 上的 chunk 的 prev_inuse 设为1，不会与相邻的空闲 chunk 合并，与 fast bin 类似
5. 当一个 chunk 被释放时，首先进入 tcache bin，而不是 fast bin，这样当该线程再次申请分配的时候，如果在其线程 tcache bin 上有空闲 chunk，就从 tcache bin 中取出，无需等待堆锁，从而实现加速分配。填满了这个大小的 tcache bin 后，再释放的 chunk 才会进入 fast bin
6. tcache bin 由 tcache_entry 和 tcache_perthread_struct 两个结构体管理

管理 tcache 的有两个结构，分开看：

• tcache entry：
  • next：位于 malloc_chunk 结构体 fd 指针的位置，指向 bin 中下一个 chunk 的地址（并非直接存储，会进行移位 & 异或，类似 AFL 定位一个基本块的手法）
  • key：位于 malloc_chunk 结构体 bk 指针的位置（tcache bin 是单链表，未使用 bk 指针），标记 chunk 已在 tcache 中，防止针对 tcache 的 double free 攻击
• tcache_perthread_struct：
  • counts：字节数组，TCACHE_MAX_BINS（64）个元素，每个成员用来统计对应下标的 bin 中有多少个 chunk
  • entries：指针数组，TCACHE_MAX_BINS（64）个元素，每个成员指向对应下标的 bin 的头节点，其为一个 tcache_entry 结构

结合这两张图会很好理解（第二张图来自看雪专家pukrquq）

参考链接

1. 网安：堆内存管理
2. 网安：glibcheap
3. ChinaUnix：linux内存管理之malloc
4. 看雪：malloc源码分析
5. 看雪：how2heap深入浅出学习堆利用
6. CSDN：glibc Tcache机制
7. CSDN：堆基础—-2 开始入微数据结构
8. taqini：glibc调试环境的搭建
9. 博客园：glibc2.31 malloc与free 源码分析
10. CSDN：ptmalloc源码分析 - 分配器状态机malloc_state（02）