开个堆系列，先声明一下，本人堆学的不是太好，如果有错误，烦请各位师傅指出，谢谢！

一、main_arena总概

1.arena:堆内存本身

(1)主线程的main_arena:由sbrk函数创建。

①最开始调用sbrk函数创建大小为(128 KB + chunk_size) align 4KB 的空间作为 heap

②当不够用时，用sbrk或者mmap增加heap大小。

(2)其它线程的per thread arena:由mmap创建。

①最开始调用 mmap 映射一块大小为HEAP_MAX_SIZE（32 位系统上默认为 1MB，64 位系统上默认为 64MB）的空间作为 sub-heap。

②当不够用时，会调用 mmap 映射一块新的 sub-heap，也就是增加 top chunk 的大小，每次 heap 增加的值都会对齐到4KB。

2.malloc_state:管理arena的一个结构，包括堆状态信息，bins链表等等

(1)main_arena对应的malloc_state存储在glibc的全局变量中

(如果可以泄露malloc_state结构体的地址，那么就可以泄露glibc的地址)

(2)per thread arena对应的malloc_state存储在各自本身的arena

3.bins:用链表结构管理空闲的chunk块，通过free释放进入的chunk块(垃圾桶)

4.chunks:一般意义上的堆内存块

#注释头

struct malloc_state{
mutex_t mutex;//(相当于多线程的互斥锁)
int flags;//(记录分配器的一些标志，bit0 用于标识分配区是否包含至少一个 fast bin chunk，bit1 用于标识分配区是否能返回连续的虚拟地址空间。)
mfastbinptr fastbinsY[NFASTBINS];//(一个数组，里面的元素是各个不同大小的fastbins的首地址)
mchunkptr top;//(top chunk的首地址)
mchunkptr last_remainder;//(某些情况下切割剩下来的堆块)
mchunkptr bins[NBINS*2-2];
.......................................................
unsigned int binmap[BINMAPSIZE];//(以bit为单位的数组，共128bit，16个字节，4个int，由于bin的数量为128，对于这里面的128bit，为0表该bin没用有空闲块，为1表有空闲块。通过四个int的大小可以找出不同index的bin中是否有空闲块。这个在某些时候会用到。)
......//后面还有，不太重要
}

▲内存中的堆情况：

全局变量glibc:main_arena = struct malloc_state:

低地址------------------------------------------------------------- ------------------>高地址

由sbrk创建的main_arena

(1)可以把bin也当作一个chunk，不同Bins管理结构不同，有单向链表管理和双向链表管理。

(2)top里的bk保存Topchunk的首地址。

(bk和fd只用于Bins链表中，allocated_chunk中是属于用户可以使用的内容)

二、chunk结构：

1.在使用中的allocated_chunk和未被使用的free_chunk：

(1)allocated_chunk：

(2)free_chunk:

2.prev_size：8字节，保存前一个chunk的大小，在allocatedchunk中属于用户数据，参考上述的图片，free_chunk的下一个chunk的pre_size位为该free_chunk的size。

3.size:8字节，保存当前chunk大小。(free和allocated都有用)一个chunk的size以0x10递增，以0x20为最小chunk。

(1)malloc(0x01)：会有0x20这么大，实际用户可用数据就是0x18。size=0x21

(2)malloc(0x01-0x18)：仍然0x20这么大，实际用户可用数据就是0x18。size=0x21

(3)malloc(0x18)：会有0x30这么大，实际用户可用数据是0x28。size=0x31

所以size这个8字节内存的最低4位都不会被用到，所以malloc管理机制给最低的3位搞了个特殊形式标志位，A,M,P，分别代表不同内容。

①A:NON_MAIN_ARENA，代表是否属于非main_arena，1表是，0表否。就是线程的不同。

#注释头

#define chunk_non_main_arena(p) ((p)->size & NON_MAIN_ARENA)

②M:IS_MMAPPED，代表当前chunk是否是mmap出来的。

#注释头

#define chunk_is_mmapped(p) ((p)->size & IS_MMAPPED)

③P:PREV_INUSE，代表前一个chunk是否正在被使用，处于allocated还是free。

#注释头

#define prev_inuse(p) ((p)->size & PREV_INUSE)

(标志位为1都代表是，0都代表否)

三、bins结构：

1.fastbins:放在struct malloc_state中的mfastbinptr fastbinsY[NFASTBINS]数组中。

(1)归类方式：只使用fd位

①bin的index为1，bins[0],bins[1]组成一个bin。

②规定大小的chunk归到一类，但个数有限，不同版本不同，同时也可以设置其范围：

M_MXFAST即为其最大的参数，可以通过 mallopt()进行设置，但最大只能是80B。

(2)单向链表：

▲例子：a=malloc(0x10); b=malloc(0x10); c=malloc(0x10); d=malloc(0x10)

FastbinY,d,c,b,a

①free(a)之后：

#注释头

fastbinY[0x20]->a;       a.fd=0

②free(b)之后：

#注释头

fastbinY[0x20]->b;       b.fd=a       a.fd=0

③free(c)之后：

#注释头

fastbinY[0x20]->c;        c.fd=b       b.fd->a;    a.fd=0

④free(d)之后：

#注释头

fastbinY[0x20]->d;       d.fd=c       c.fd->b;     b.fd->a;    a.fd=0

(3)后进先出：

①m=malloc(0x10):          m->d

②n=malloc(0x10):           n->c

(4)不改变IN_USE位(p位):

如果某个chunk进入到fastbin中，那么该chunk的下一个chunk的IN_USE位还是为1，不会改变成0。

例子：a=malloc(0x10); b=malloc(0x10); c=malloc(0x10);

①free(a)之后:        b.p=1

②free(b)之后：     c.p=1;      b.p=1

p位不会变成0，如果该chunk进入到fastbins中。

可以进行free(0),free(1),free(0)，但是不能直接free(0)两次。

(5)除了malloc_consolidate函数会清空fastbins，其它的操作都不会减少fastbins中chunk的数量。

2.smallbins:放在bins[2]-bins[125]中，共计62组，是一个双向链表。最大chunk的大小不超过1024字节

(1)归类方式：

①相同大小的chunk归到一类：大小范围[0x20,0x3f0]，0x20、0x30、....0x3f0。每组bins中的chunk大小一定。

②每组bin中的chunk大小有如下关系：Chunk_size=2 * SIZE_SZ * index，index即为2-63，下图中64即为largebins的范围了。(SIZE_SZ在32，64位下分别位4，8。)

(2)双向链表：

▲例子：a=malloc(0x100); b=malloc(0x100); c=malloc(0x100)

①free(a)之后:          smallbin,a

#注释头

smallbin.bk->a;         a.bk->smallbin;      
samllbin.fd->a          a.fd->smallbin;

②free(b)之后:        smallbin,b,a

#注释头

smallbin.bk->a;       a.bk->b    b.bk->smallbin
smallbin.fd->b;       b.fd->a    a.fd->smallbin

③free(c)之后：     smallbin,c,b,a

#注释头

smallbin.bk->a;       a.bk->b    b.bk->c    c.bk->smallbin
smallbin.fd->c;       c.fd->b    b.fd->a    a.fd->smallbin

（fd,bk为bins[n]，bins[n+1]。fd和bk共同构成一个Binat。）

(3)先进先出：

①m=malloc(0x100):                m->a

②n=malloc(0x100):                 n->b

(4)当有空闲chunk相邻时，Chunk会被合并成一个大chunk，这里指的是物理上的地址相邻，不是链表中相邻。通过判断当前chunk的in_use位的值来判断前一个chunk是否处于Free，如果是，那么合并。再通过当前chunk首地址加上size取得下一个chunk首地址，再将下一个chunk首地址加上它自己的size，取得下下个chunk的首地址，然后判断下下个chunk的in_use位的值看是否下个chunk处于Free，如果处于Free，则合并。

3.largebins:放在bins[126]-bins[251]，共计63组，bin的index为64-126，最小chunk的大小不小于1024个字节。

(1)归类方式：范围归类，例如bins[126]-bins[127]中保存chunk范围在[0x400,0x440]。且chunk在一个bin中按照从大到小排序，便于检索。其它与smallbins基本一致。

①范围模式：由以下代码定义范围：

#注释头

#define largebin_index_64(sz)                                               
  (((((unsigned long) (sz)) >> 6) <= 48) ?  48 + (((unsigned long) (sz)) >> 6) :
   ((((unsigned long) (sz)) >> 9) <= 20) ?  91 + (((unsigned long) (sz)) >> 9) :
   ((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :
   ((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :
   ((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :
   126)

②范围具体实例：

#注释头

size                           index
[0x400 , 0x440)                64
[0x440 , 0x480)                65
[0x480 , 0x4C0)                66
[0x4C0 , 0x500)                67
[0x500 , 0x540)                68
等差 0x40      …
[0xC00 , 0xC40)                96
[0xC40 , 0xE00)                97
[0xE00 , 0x1000)               98
[0x1000 , 0x1200)              99
[0x1200 , 0x1400)              100
[0x1400 , 0x1600)              101
等差 0x200    …
[0x2800 , 0x2A00)              111
[0x2A00 , 0x3000)              112
[0x3000 , 0x4000)              113
[0x4000 , 0x5000)              114
等差 0x1000 …
[0x9000 , 0xA000)              119
[0xA000 , 0x10000)             120
[0x10000 , 0x18000)            121
[0x18000 , 0x20000)            122
[0x20000 , 0x28000)            123
[0x28000 , 0x40000)            124
[0x40000 , 0x80000)            125
[0x80000 , …. )                126

(2)双向链表，但是有两种排列方式：

①取用排列：

首先依据fd_nextsize，bk_nextsize两个指针大小找到适合的，然后按照正常的FIFO先进先出原则，通过fd,bk来排列。

②大小排列：

每个进入largebin的chunk

其chunk_addr+0x20处即为其fd_nextsize指针，chunk_addr+0x28处为其bk_nextsize指针。

然后通过fd_nextsize，bk_nextsize两个指针依据从大至小的顺序排列：

(这张图片我也忘记从哪里整的了...侵删)

其中size顺序为：D>C>B>A，但是释放顺序却不一定是这样的。设置这个的原因是当申请特定大小的堆块时，可以据此来快速查找，提升性能。

(3)特殊解链：

由于largebin中会存在fd_nextsize指针和bk_nextsize指针，所以通常的largebin_attack就是针对这个进行利用的。

借用星阑科技的一张图说明一切：

4.unsortedbins:bins[0]和bins[1]中，bins[0]为fd，bins[1]为bk，bin的index为1，双链表结构。

(1)归类方式：只有一个bin，存放所有不满足fastbin，未被整理的chunk。

(2)双向链表：

a=malloc(0x100); b=malloc(0x100); c=malloc(0x100)

①free(a)之后:          unsortedbin,a

#注释头

unsortedbin.bk->a;  a.bk->unsortedbin;
unsortedbin.fd->a;  a.fd->unsortedbin;

②free(b)之后:        unsortedbin,b,a

#注释头

unsortedbin.bk->a;  a.bk->b     b.bk->unsortedbin
unsortedbin.fd->b;  b.fd->a     a.fd->unsortedbin

③free(c)之后：     unsortedbin,c,b,a

#注释头

unsortedbin.bk->a;  a.bk->b     b.bk->c     c.bk->unsortedbin
unsortedbin.fd->c;  c.fd->b     b.fd->a     a.fd->unsortedbin

(3)先进先出：

①m=malloc(0x100):                m->a

②n=malloc(0x100):                 n->b

▲依据fd来遍历：

如果fd链顺序为A->B->C

那么解链顺序一定是先解C，再解B，再解A。

5、Tcache机制：从libc-2.26及以后都有:先进后出，最大为0x410

(1)结构：

①2.29以下，无key字段的tcache，结构大小为0x240，包括chunk头则占据0x250:

#注释头

typedef struct tcache_perthread_struct
{
  char counts[TCACHE_MAX_BINS];//0x40
  tcache_entry *entries[TCACHE_MAX_BINS];//0x40
} tcache_perthread_struct;

A.counts:是个数组，总共64个字节，对应tcache的64个bin，每个字节代表对应bin中存在chunk的个数，所以每个字节都会小于8，一般使用

#注释头

tc_idx = csize2tidx (size);
tcache->counts[tc_idx]

来访问索引对应bin的count。

从0x55555555b010至0x55555555b04f都是counts这个数组的范围。

▲由于使用tcache时，不会检查tcache->counts[tc_idx]的大小是否处在[0,7]的范围，所以如果我们可以将对应bin的count改成[0,7]之外的数，这样下回再free该bin对应大小的chunk时，就不会将该chunk置入tcache中，使得tcache不满也能不进入tcache。

B.entries：是个bin指针数组，共64个指针数组，每个指针8个字节，总计大小0x200字节，指针指向对应的bin中第一个chunk的首地址，这个首地址不是chunk头的首地址，而是对应数据的首地址。如果该bin为空，则该指针也为空。一般会使用tcache->entries[tc_idx] != NULL来判断是否为空。

②2.29及以上，在entry中增加了key字段，结构体大小为0x290，count由原来的一个字节变为两个字节

#注释头

typedef struct tcache_entry
{
  struct tcache_entry *next;
  /* This field exists to detect double frees.  */
  struct tcache_perthread_struct *key; /* 新增指针 */
} tcache_entry;

(2)类似于一个比较大的fastbins。总共64个bin。

(3)归类方式：

相同大小的chunk归到一类：大小范围[0x20,0x410]。每组bins中的chunk大小一定。且一组bin中最多只能有7个chunk，如果free某大小bin的chunk数量超过7，那么多余的chunk会按照没有tcache机制来free。

(4).单向链表：

▲例子：a=malloc(0x10); b=malloc(0x10); c=malloc(0x10); d=malloc(0x10)

FastbinY,d,c,b,a

①free(a)之后：tcachebins[0x20]->a;   a.fd=0

②free(b)之后：tcachebins[0x20]->b;   b.fd=a      a.fd=0

③free(c)之后：tcachebins[0x20]->c;    c.fd=b       b.fd->a;    a.fd=0

④free(d)之后：tcachebins[0x20]->d;   d.fd=c       c.fd->b;    b.fd->a;    a.fd=0

★但是这里的fd指向的是chunk内容地址，而不是其它的bins中的fd指向的是chunk头地址。

(5)后进先出，与fastbins类似。且tcache的优先级最高。

(6)特殊：

①当tcache某个bin被填满之后，再free相同大小的bin放到fastbin中或者smallbins中，之后连续申请7个该大小的chunk，那么tcache中的这个bin就会被清空。之后再申请该大小的chunk就会从fastbins或者smallbins中找，如果找到了，那么返回该chunk的同时，会将该大小的fastbin或者smallbin中所有的chunk都移动到对应大小的tcache的bin中，直至填满7个。(移动时仍旧遵循先进后出的原则，所以移动之后chunk顺序会发生颠倒)

②libc-2.26中存在tcache poisoning漏洞，即可以连续free(chunk)多次。

假如chunk0,chunk1，然后free(chunk0)两次，这样tcache bin中就是：

chunk0.fd ->chunk0，即chunk0->chunk0

那么第一次申请回chunk0，修改fd为fakechunk，tcache bin中就是：

chunk0.fd->fakechunk，即chunk0->fakechunk

之后再申请回chunk0，再申请一次就是fakechunk了，实现任意地址修改。

★这个漏洞在libc2.27中就被修复了。

③从tcache中申请Chunk的时候不会检查size位，不需要构造字节错误。

(7)2.31下新增stash机制：

在 Fastbins 处理过程中新增了一个 Stash 机制，每次从 Fastbins 取 Chunk 的时候会把剩下的 Chunk 全部依次放进对应的 tcache，直到 Fastbins 空或是 tcache 满。

(8)2.32下新增fd异或机制：

会将fd异或上某个值。这个具体看其他文章吧，我自己调试大多都是异或heap_base/0x1000，比较奇怪，具体题目具体分析。

6.Topchunk:不属于任何Bin，在arena中属于最高地址，没有其它空闲块时，topchunk就会被用于分配。

7.last_remainder:当请求small chunk大小内存时，如果发生分裂，则剩余的chunk保存为last_remainder，放入unsortedbin中。

四、没有tcache的malloc和free流程：

malloc流程：

★如果是多线程情况下，那么会先进行分配区的加锁，这里就可能存在条件竞争漏洞。

1.如果size在fastbins的范围内，则先在fastbins中查找，找到则结束，没找到就去unsortedbins中找。

2.如果size不在fastbins范围中，而在smallbins范围中，则查找smallbins（在2.23下如果发现smallbin链表未初始化，则会调用malloc_consolidate函数，但是实际情况在申请chunk之前都已经初始化过了，所以这个不怎么重要if (victim == 0) /* initialization check */  malloc_consolidate (av); 而且这个操作从2.27开始已经没有了，如果能够让smallbin不初始化，或者将main_arena+0x88设置为0），此时若smallbin找到结束，没找到去unsortedbins中找

3.如果size不在fastbins，smallbins范围中，那一定在largebins中，那么先调用malloc_consolidate函数将所有的fastbin中的chunk取出来，合并相邻的freechunk，放到unsortedbin中，或者与topchunk合并。再去largebins中找，找到结束，没找到就去unsortedbins中找。

4.unsortedbins中查找：

(1)如果unsortedbin中只有last_reaminder，且分配的size小于last_remainder，且要求的size范围为smallbin的范围，则分裂，将分裂之后的一个合适的chunk给用户，剩余的chunk变成新的last_remainder进入unsortedbin中。如果大于last_remainder，或者分配的size范围为largebin的范围，则将last_remainder整理至对应bin中，跳至第5步。

(2)如果unsortedbin中不只一个chunk，则先整理，遍历unsortedbins。如果遇到精确大小，直接返回给用户，接着整理完。如果一直没遇到过，则该过程中所有遇到的chunk都会被整理到对应的fastbins，smallbins，largebins中去。

5.unsortedbins中还是找不到，则：

(1)若当前size最开始判断是处于smallbins范围内，则再去smallbins找，这回不找精确大小，找最接近略大于size的一个固定大小的chunk给分裂，将符合size的chunk返回给用户，剩下的扔给unsortedbins，作为新的last_remainder。

(2)若当前size最开始判断处于largebins范围内，则去largebins中找，和步骤(1)类似。

(3)若当前size大于largebins中最大的chunk大小，那么就去topchunk来分割使用。

6.topchunk分割：

(1)topchunk空间够，则直接分割。

(2)topchunk空间不够，那么再调用malloc_consolidate函数进行整理一下，然后利用brk或者mmap进行再拓展。

①brk扩展：当申请的size小于128K时，使用该扩展。向高地址拓展新的topchunk，一般加0x21000，之后从新的topchunk再分配，旧的topchun进入unsortedbin中。

②mmap扩展：申请的size大于等于mmap分配阈值(最开始为128k)时，使用该扩展，但是这种扩展申请到的chunk，在释放时会调用munmap函数直接被返回给操作系统，而不会进入bins中。所以如果用指针再引用该chunk块时，就会造成segmentation fault错误。

▲当ptmalloc munmap chunk时，如果回收的chunk空间大小大于mmap分配阈值的当前值，并且小于DEFAULT_MMAP_THRESHOLD_MAX（32位系统默认为512KB，64位系统默认为32MB），ptmalloc会把mmap分配阈值调整为当前回收的chunk的大小，并将mmap收缩阈值（mmap trim threshold）设置为mmap分配阈值的2倍。这就是ptmalloc的对mmap分配阈值的动态调整机制，该机制是默认开启的，当然也可以用mallopt()关闭该机制

▲如果将 M_MMAP_MAX 设置为 0，ptmalloc 将不会使用 mmap 分配大块内存。

free流程：

★多线程情况下，free()函数同样首先需要获取分配区的锁，来保证线程安全。

1.首先判断该chunk是否为mmaped chunk，如果是，则调用 munmap()释放mmaped chunk，解除内存空间映射，该该空间不再有效。同时满足条件则调整mmap阈值。

2.如果size位于fastbins范围内，直接放到fastbins中。

(这里有点争议，在《glibc内存管理ptmalloc源代码分析.pdf》一书中，写到：

如果执行到这一步，说明释放了一个与top chunk相邻的chunk。则无论它有多大，都将它与top chunk合并，并更新top chunk的大小等信息。

但是实际测试，如果size位于fastbins范围内，则不管是否与topchunk相邻，都直接放到fastbin中，测试环境是libc2.23，内核版本是Linux version 5.10.13，也可能是某些参数的问题把，具体题目分析就好了。)

3.如果size不在fastbins范围内，则进行判断：

(1)先判断前一个chunk_before，如果chunk_before是free状态的，那么就将前一个chunk从其对应的bins中取出来(unlink)，然后合并这两个chunk和chunk_before。

由于还没有进入链表结构中，所以这里寻找chunk_before地址是通过当前地址减去当前chunk的presize内容，得到chunk_before的地址，从而获取其in_use位。

这也是presize唯一的用途，所以在堆溢出中，可以只要不进行free，presize可以任意修改。

(这里如果chunk_before是位于fastbins中则没办法合并，因为在fastbins中的in_use位不会被改变，永远是1，在判断时始终认为该chunk是处于allocated状态的)

(2)再判断后一个chunk，如果后一个chunk是free状态，那么如步骤(1)，合并，之后将合并和的chunk放入到unsortedbins中去。如果后一个chunk就是topchunk，那么直接将这个chunk和topchunk合并完事。

之后将合并之后的chunk进行判断，(这里也可能不发生合并，但依旧会进行判断)如果size大于FASTBIN_CONSOLIDATION_THRESHOLD(0x10000)，那么就调用malloc_consolidate函数进行整理fastbins，然后给到unsortedbins中，等待malloc时进行整理。

▲32位与64位区别，差不多其实，对于0x8和0x10的变化而已：

▲至于有tcache的malloc和free，在各个版本其实都差不太多，除开2.29和2.31、2.32三个版本的不同检查和机制，都是判断count和链表来着，具体结合题目会比较好。

[培训]《安卓高级研修班(网课)》月薪三万计划，掌握调试、分析还原ollvm、vmp的方法，定制art虚拟机自动化脱壳的方法