堆的基础知识
1、堆在程序和libc中间
2、申请chunk末尾的大小：>9 <=8
例：0x69-x78
申请的为同一个chunk为0x80
最小的chunk为0x20
3、teahce bin >2.27
teahce的管理结构在系统的前0x290
在0x290中前0x40个代表chunk的个数(默认上限为7个)，两个字 节为一个计数单位
4、堆申请顺序：teachce bin -> fast bin -> unsort bin ->small bin-> large bin
chunk
chunk的结构剖析
prev_size:若前一个物理相邻的chunk是free chunk，则表示其大小，否则用于存储前一个chunk的数据。
size：占据一字长的低3bite以后的地址用于表示当前chunk的大小（整个chunk的大小，包括chunk头）。
A falg：NON_MIAN_ARENA:记录当前的chunk是不属于主线程，1表示不属于，0表示属于。
M flag：IN_MAPPED:记录当前的chunk是否是由mmap分配的。
P flag：PREV_INUES:记录前一个chunk是否被分配，一般来说，堆中第一个被分配的内存块的size字段的P位都会被设置成1，以便于防止访问前面的非法内存，当一个chunk的size的P位为0时，我们能通过prev_size字段来获取上一个chunk的大小以及地址。这也方便进行空闲chunk之间的合并。
fd pointer：在bin中指向下一个（非物理相邻）空闲的chunk。
bk pointer：在bin中指向上一个（非物理相邻）空闲的chunk。
fd_nextsize:在large bin中指向前一个与当前chunk大小不同的的第一个空闲块，不包含bin的头指针。
bk_nextsize:在large bin中指向后一个与当前chunk大小不同的的第一个空闲块，不包含bin的头指针。
malloced chunk
chenk
已被分配且填写了相应数据的chunk
free chunk
被释放掉的malloced chunk成为free chunk
fd：指向后一个空闲的chunk
bk：指向前一个空闲的chunk
fd_nextsize和bk_nextsize：用于加快在large bin中查找最近匹配的空闲chunk
Unused：未被使用的区域
TOP chunk
arena中从未被使用过的内存区域
last remainder chunk
malloc分割原chunk后剩余的部分
堆的大小对齐
堆的大小（size）：
堆的大小必须是2SIZE_SZ的整数倍，如歌申请的内存的大小不是2SIZE_SZ的整数倍，会被转成满足大小的最小的2*SIZE_SZ的倍数；
在32位系统中，SIZE_SZ=4,在64位系统中，SIZE_SZ=8；也就是32位系统堆的大小位8的倍数，64位系统堆的大小为16的倍数，8对应的2进制为1000，所以不管size如何变换对应的低3位固定为0；为了不浪费这3个比特位，他们从高到低分别被用来表示：
chunk的微观结构
P它表示前一个块是否在使用中，P 为 0 则表示前一个 chunk 为空闲，这时 chunk 的第一个域 prev_size 才有效，prev_size 表示前一个 chunk 的 size，程序可以使用这个 值来找到前一个 chunk 的开始地址。当 P 为 1 时，表示前一个 chunk 正在使用中，prev_size 15无效，程序也就不可以得到前一个chunk的大小。不能对前一个chunk进行任何操作。ptmalloc 分配的第一个块总是将 P 设为 1，以防止程序引用到不存在的区域。 Chunk 的第二个域的倒数第二个位为 M，他表示当前 chunk 是从哪个内存区域获得的虚 拟内存。M 为 1 表示该 chunk 是从 mmap 映射区域分配的，否则是从 heap 区域分配的。 Chunk 的第二个域倒数第三个位为 A，表示该 chunk 属于主分配区或者非主分配区，如 果属于非主分配区，将该位置为 1，否则置为 0。
bin
概念:管理arena中空闲的chunk结构，以数组的形式存在，数组元素为相应大小的chunk链表的链表头，存在于arena的malloc_state中
fast bin
不大于 max_fast （默认值为 64B）的 chunk 被释放后，首先会被放到 fast bins 中，fast bins 中的 chunk 并不改变它的使用标志 P。这样也就无法将它们合并，当需要给用 户分配的 chunk 小于或等于 max_fast 时，ptmalloc 首先会在 fast bins 中查找相应的空闲块， 然后才会去查找bins中的空闲chunk。在某个特定的时候，ptmalloc会遍历fast bins中的chunk，将相邻的空闲chunk 进行合并，并将合并后的 chunk 加入 unsorted bin 中，然后再将 usorted bin 里的 chunk 加入 bins 中。
unsorted bin
unsorted bin 的队列使用 bins 数组的第一个（bins[1]），如果被用户释放的 chunk 大于 max_fast， 或者 fast bins 中的空闲 chunk 合并后，这些 chunk 首先会被放到 unsorted bin 队列中，在进 行 malloc 操作的时候，如果在 fast bins 中没有找到合适的 chunk，则 ptmalloc 会先在 unsorted bin 中查找合适的空闲 chunk，然后才查找 bins。如果 unsorted bin 不能满足分配要求。malloc 便会将 unsorted bin 中的 chunk 加入 bins 中。然后再从 bins 中继续进行查找和分配过程。从 这个过程可以看出来，unsorted bin 可以看做是 bins 的一个缓冲区，增加它只是为了加快分配的速度。
samll bin
数组：bins[2]......bins[63]
同一个samll bin中的chunk具有相同的大小
两个相邻的samll bin中的chunk大小相差8bytes
62个循环双向链表
FIFO
管理16、24、32、40...、504Btytes的free chunks（32位下）
每个链表中存储的chunk大小都一致
large bin
数组：bins[64]......bins[126]
63个循环双向链表
FIFO
管理大于504Bytes的free chunks（32位下）
mmaped bins
当需要分配的 chunk 足够大，而且 fast bins 和 bins 都不能满足要求，甚至 top chunk 本身也不能满足分配需求时，ptmalloc 会使用 mmap 来直接使用内存映射来将页映射到进程空间。这样分配的 chunk 在被 free 时将直接解除映射，于是就将内存归还给了操作系统，再 次对这样的内存区的引用将导致 segmentation fault 错误。这样的 chunk 也不会包含在任何 bin 中。
last remainder
Last remainder 是另外一种特殊的 chunk，就像 top chunk 和 mmaped chunk 一样，不会 在任何 bins中找到这种 chunk。当需要分配一个 small chunk，但在 small bins 中找不到合适的 chunk，如果 last remainder chunk 的大小大于所需的 small chunk 大小，last remainder chunk被分裂成两个 chunk，其中一个 chunk 返回给用户，另一个 chunk 变成新的 last remainder chuk。
teahce bin
出现于libc.2.27之后
tcache相对于其余四种bin，是出现的最晚的，在libc2-26中才加入，但现在的题目一般都基于更新版本的libc，tcache肯定是必不可少的一环，而且是最开始的那一环，所以这里先对tcache机制进行一个总结。Tcache全名为Thread Local Caching，它为每个线程创建一个缓存，里面包含了一些小堆块。无须对arena上锁既可以使用，所以采用这种机制后分配算法有不错的性能提升。每个线程默认使用64个单链表结构的bins，每个bins最多存放7个chunk，64位机器16字节递增，从0x20到0x410，也就是说位于以上大小的chunk释放后都会先行存入到tcache bin中。对于每个tcache bin单链表，它和fast bin一样都是先进后出，而且prev_inuse标记位都不会被清除，所以tcache bin中的chunk不会被合并，即使和Top chunk相邻。另外tcache机制出现后，每次产生堆都会先产生一个0x250大小的堆块，该堆块位于堆的开头，用于记录64个bins的地址（这些地址指向用户数据部分）以及每个bins中chunk数量。在这个0x250大小的堆块中，前0x40个字节用于记录每个bins中chunk数量，每个字节对应一条tcache bin链的数量，从0x20开始到0x410结束，刚好64条链，然后剩下的每8字节记录一条tcache bin链的开头地址，也是从0x20开始到0x410结束。还有一点值得注意的是，tcache bin中的fd指针是指向malloc返回的地址，也就是用户数据部分，而不是像fast bin单链表那样fd指针指向chunk头。
malloc
1、它根据用户申请的内存大小以及相应大小chunk通常使用的频度（fastbin chunk ，samll chunk，large chunk），依次实现了不同的分配方法/
2、它由大到小依次检查不同的bin中是否有相应的空闲块可以满足用户请求的内存
3、当所有的空闲的chunk都无法满足时，它会考虑top chunk
4、当top chunk 也无法满足时，堆分配器才会进行内存堆申请
free
1、它将用户暂且不用的chunk回收给堆管理器，适当的时候还会归还给操作系统
2、它依据chunk大小来优先试图将free chunk链入tcache或者是fsat bin。不满足则链入usorted bin中
3、在条件满足时free函数遍历usorted bin并将其中的物理相邻的free chunk合并，将相应大小的chunk分类放入small bin或large bin中。
4、除了tache chunk与fast bin chunk，其它的 chunk在free时会与其物理相邻的free chunk合并
ptmalloc的响应用户内存分配
1、获取分配区的锁，为了防止多个线程同时访问同一个分配区，在进行分配之前需要取得分配区域的锁。线程会查看私有实例中是否有一个已经存在的分配区，如果有，就尝试对该分配区进行加锁，如果加锁成功。使用该分配区分配内存，否则，该线程就要去搜索分配区循环链接表试图获取一个空闲的（没有加锁的）的分配区，会把该分配区加入到全分配区循环链接表和线程私有实例中并进项加锁，然后使用该分配区进行分配操作，开辟一个新的分配区一定为非主分配区。因为主分配区是从父进行继承过来的，开辟非主分配区时会调用mma()创建一个sub-heap，并设置好top chunk
2、会将用户的请求大小转换为实际需要分配的chunk空间大小
3、判断所需分配的chunk的大小是否满足chunk_size<max_fast（max_fast默认为64B）,如果是的话就进行下一步，否者跳转到（5）
4、所需分配的chunk满足（4）的条件，就在fast_bins中选取一个所需大小的chunk给用户。如果找到了，则分配结束，否则进行下一步
5、判断所需大小是否除以samll_bins中，就是判断chunk_size<512B
是否成立，如果成立chunk的大小处在samll_bins只中，进行下一步，否则跳转到（6）
6、根据所需分配的chunk的大小，找到具体所需要的某个samll_bin，从该bin的尾部取一块恰好满足大小的chunk，如果成功，则分配结束。否则进行下一步
7、进行到这说明需要分配的一块大的内存，或者是在samll_bins中找不到合适的chunk，于是，ptmalloc首先会去遍历fsat bins中的chunk，会将相邻的chunk进行合并，并链接到unsorted bin中，然后遍历unsorted bin中的chunk，如果unsorted bin中只有一个chunk，并且这个chunk在上次分配时被使用过，并且所需分配的chunk大小属于samll_bins,并且chunk的大小大于等于所需分配的chunk大小，这种情况下直接将该chunk进行切割，分配结束，否则将根据chunk的空间大小将其放入samll_bins或者large bins中，遍历完成后，进入下一步
8、到这里，说明需要分配的是一块大的内存。或者说是在fast bins和unsorted bin中找不到大小合适的chunk，并且fast bins和unsorted bin中所有的chunk都已经被清楚干净了，从large bins中按照“samll-fast,best-fast”原则，找到一个合适的chunk，从中划分出一个所需求的chunk，并将剩下的一部分链接回到bins中，若操作成功，则分配结束。否则进行下一步
9、如果搜索fast bins和bins都没有找到合适大小chunk，就需要用到top chunk进行分配了，会判断top chunk大小是否满足所需要chunk的大小，如果是则从top chunk中分出一块来，否则进行下一步
10、到这里，说明top chunk都无法满足需要分配的要求。这时候有两个选择，如果是主分配区，调用sbrk()，增肌top chunk的大小；如果是非主分配区，调用mmap()来分配一个新的sub-heap，来增加top chunk的大小；或直接使用mmap()来直接分配，在这么方法中，需要依靠chunk的大小来决定使用那种方法。判断所需分配的chunk大小是否大于等于mmap分配阈值，如果是的话，进行下一步。调用mmap分配，否则到（12），增加top chunk的大小
11、使用mmap系统调用为程序的内存空间映射一个chunk_size align 4KB大小的空间，然后将内存指返回给用户。
12、判断是否为第一次调用malloc，若是主分配区，则需要进行一次初始化工作，分配一块大小为（chunk_size+128KB）align 4KB大小的空间作为初始heap，若已经初始化过了，分主分配区则在top chunk中切割出一个chunk，使之满足分配需求，并将指针返回给用户
总结一下：根据用户请求分配的内存的大小，ptmalloc 有可能会在两个地方为用户 分配内存空间。在第一次分配内存时，一般情况下只存在一个主分配区，但也有可能从 父进程那里继承来了多个非主分配区，在这里主要讨论主分配区的情况，brk 值等于 start_brk，所以实际上 heap 大小为 0，top chunk 大小也是 0。这时，如果不增加 heap 大小，就不能满足任何分配要求。所以，若用户的请求的内存大小小于 mmap 分配阈值， 则 ptmalloc 会初始 heap。然后在 heap 中分配空间给用户，以后的分配就基于这个 heap 进行。若第一次用户的请求就大于 mmap 分配阈值，则 ptmalloc 直接使用 mmap()分配 一块内存给用户，而 heap 也就没有被初始化，直到用户第一次请求小于 mmap 分配阈 值的内存分配。第一次以后的分配就比较复杂了，简单说来，ptmalloc 首先会查找 fast bins， 如果不能找到匹配的 chunk，则查找 small bins。若还是不行，合并 fast bins，把 chunk 加入 unsorted bin，在 unsorted bin 中查找，若还是不行，把 unsorted bin 中的 chunk 全 加入 large bins 中，并查找 large bins。在 fast bins 和 small bins 中的查找都需要精确匹配， 而在 large bins 中查找时，则遵循“smallest-first，best-fit”的原则，不需要精确匹配。 若以上方法都失败了，则 ptmalloc 会考虑使用 top chunk。若 top chunk 也不能满足分配 要求。而且所需 chunk 大小大于 mmap 分配阈值，则使用 mmap 进行分配。否则增加 heap，增大 top chunk。以满足分配要求。
精简：
用户第一次请求小于 mmap 分配阈 值的内存分配。第一次以后的分配就比较复杂了，简单说来，ptmalloc 首先会查找 fast bins， 如果不能找到匹配的 chunk，则查找 small bins。若还是不行，合并 fast bins，把 chunk 加入 unsorted bin，在 unsorted bin 中查找，若还是不行，把 unsorted bin 中的 chunk 全 加入 large bins 中，并查找 large bins。在 fast bins 和 small bins 中的查找都需要精确匹配， 而在 large bins 中查找时，则遵循“smallest-first，best-fit”的原则，不需要精确匹配。 若以上方法都失败了，则 ptmalloc 会考虑使用 top chunk。若 top chunk 也不能满足分配 要求。而且所需 chunk 大小大于 mmap 分配阈值，则使用 mmap 进行分配。否则增加 heap，增大 top chunk。以满足分配要求。
free内存回收概述
4、判断chunk的大小和所处的位置，若chunk_size<=max_fast,
并且chunk并不位于heap的顶部，也就是说并不与top chunk相邻，则转到下一步，否者跳转到（6）
（因为与top chunk相邻的小chunk也和top chunk进行合并，所以这里不仅需要判断大小，还需要判断相邻情况）
5、将chunk放入fast bins中，chunk放入到fast bins中时，并不修改该chunk的使用状态位P，也不与相邻的chunk进行合并。只是放进去，而已。这一步做完之后释放便结束了，程序从free()函数中返回。
6、判断前一个chunk是否处于使用中，如果前一个也是空闲块，则合并，并转到下一步.
7、判断当前释放chunk的下一块是否为top chunk，如果是转到（9），否则转到下一步
8、判断下一个chunk是否处在使用中，如何下一个chunk也空闲的，则合并，并将合并后的chunk放到unsorted bin中。注意，这里再在合并的过程中，要更新chunk的大小，并跳转到（10）
9、如果执行到这一步，说明释放了一个与top chunk相邻的chunk，则无论它有多大，都将它与top chunk合并，并且更新top chunk的大小等信息，转下一步
10、判断合并后的 chunk 的大小是否大于 FASTBIN_CONSOLIDATION_THRESHOLD（默认 64KB），如果是的话，则会触发进行 fast bins 的合并操作，fast bins 中的 chunk 将被 遍历，并与相邻的空闲 chunk 进行合并，合并后的 chunk 会被放到 unsorted bin 中。 fast bins 将变为空，操作完成之后转下一步
11、判断 top chunk 的大小是否大于 mmap 收缩阈值（默认为 128KB），如果是的话，对 于主分配区，则会试图归还 top chunk 中的一部分给操作系统。但是最先分配的 128KB 空间是不会归还的，ptmalloc 会一直管理这部分内存，用于响应用户的分配 请求；如果为非主分配区，会进行 sub-heap 收缩，将 top chunk 的一部分返回给操 作系统，如果 top chunk 为整个 sub-heap，会把整个 sub-heap 还回给操作系统。做完这一步之后，释放结束，从 free() 函数退出。可以看出，收缩堆的条件是当前 free 的 chunk 大小加上前后能合并 chunk 的大小大于 64k，并且要 top chunk 的大 小要达到 mmap 收缩阈值，才有可能收缩堆。