1.背景：
因为最近想复习一下PWN针对于heap的知识，发现很多地方都看不太懂了，所以回过头来继续再分析一下这个glibc2.23中，针对于patmalloc的malloc源码部分。
在阅读本文章前，请各位准备好一份在线源码，因为本篇文章属于是一镜到底形式的分析，并未做任何的分割。其中可能还需要对其中遇到的一些arena和chunk的结构体并未做说明，这个后续在做补充吧。
2.环境准备：
系统：Ubuntu 16.04
调试器: Pwndbg
gcc版本：5.4.0
2.1编译带源码信息的glibc：
这里主要参考网上文章https://gist.github.com/stefan1wan/5e4b3973aae578ac39f94d30a5555f19中的步骤。编译有问题的直接看在线文档也可以：https://elixir.bootlin.com/glibc/glibc-2.23/source/malloc/malloc.c
2.2下载glibc源码文件
glibc2.23源码：http://ftp.gnu.org/gnu/glibc/glibc-2.23.tar.gz
2.3编译64位的glibc源码：
tar -zxvf glibc-2.23.tar.gz
cd glibc-2.23
mkdir build_x64 \
cd build_x64 \
mkdir glibc_x64 \
CFLAGS="-g -g3 -ggdb -gdwarf-4 -Og -Wno-error" \
CXXFLAGS="-g -g3 -ggdb -gdwarf-4 -Og" \
../configure --prefix=/home/g0fl1er/Desktop/glibc-2.23/build_x64/glibc_x64
make -j4
make install
2.4编译32位的glibc源码：
tar -zxvf glibc-2.23.tar.gz
cd glibc-2.23
mkdir build_x32
cd build_x32
mkdir glibc_x32
CC="gcc -m32 -Wno-error=attributes" \
CXX="g++ -m32" \
CFLAGS="-g -g3 -ggdb -gdwarf-4 -Og -Wno-error" \
CXXFLAGS="-g -g3 -ggdb -gdwarf-4 -Og" \
../configure --prefix=/home/g0fl1er/Desktop/glibc-2.23/build_x32/glibc_x32/ --host=i686-linux-gnu
make -j4
make install
完成后就可以在各个glibc的文件夹下看到
2.5Patchelf替换：
这里直接替换我们刚才装好的
patchelf --set-interpreter /home/admin/Desktop/glibc-2.23/build_x64/glib64/lib/ld-linux-x86-64.so.2 --set-rpath /home/admin/Desktop/glibc-2.23/build_x64/glib64/lib/ 1
检查之后发现没有错误
3.malloc
源码：
#include <stdlib.h>
#include <stdio.h>
void main()
{
char *a = (char *)malloc(20);
}
编译：
gcc 1.c -o 1
3.1开始分析：
gdb -q 1
b main
r
一直ni走到call malloc这句话的地方，然后ni进入到他的那个函数内部
一路ni，走过这个dl_resolve的过程，直接到他的malloc的开始，也就是到__libc_malloc这个函数这里。
首先可以看到malloc的入口会进入到__libc_malloc函数进行，接着会调用atomic_forced_read函数对__malloc_hook变量的值进行读取
此时的__malloc_hook是有值的,并且读取到的值是malloc_hook_ini
接着会判断__malloc_hook是否为空，如果不为空，则会将__malloc_hook的值当做函数名称进行执行。这也就是为什么发生任意地址写的时候，为什么要修改__malloc_hook这个地址的值的原因了。
这里第一次在调用malloc的时候malloc_hook的值为malloc_hook_ini，所以这里会调用malloc_hook_ini函数。
进入到malloc_hook_ini这个函数内部可以看到具体的内容，首先会将__malloc_hook的值设置为空，避免下次调用malloc时，会造成重复调用。接着会调用ptmalloc_init()函数，这个函数是用于初始化ptmalloc的，最后返回到malloc函数的__libc_malloc入口处，并且将这次malloc的size作为参数，相当于再次调用malloc函数。
初始化完毕ptmalloc后，将回到malloc入口函数继续执行一遍上述的内容，因为这里经过了第一次的__malloc_hook_ini函数的清空_malloc_hook的值，所以不会再调用。
继续向下走，会进入到arena_get函数。
这个函数的会对arena进行加锁操作，既线程互斥锁mutex，以防止后续存在多个线程同时malloc时产生冲突。arena_get函数还会检测arena对象是否为空并且flags标志的第四个bit是否不为空，如果有一个不满足，则从系统中获取一个arena用于后续的heap的申请使用。
当前线程获取到了带锁的arena以后，将执行最核心的_int_malloc函数，其中参数1为刚才上锁的arena，参数2为申请的size大小，这里的ar_ptr其实就是main_arnea，意味着接下来的chunk分配的对象都是main_arena的。
进入到_int_malloc可以看到实现，首先会调用checked_request2size来对malloc的size进行校验。
这里看一下checked_request2size的源码可以看到具体的实现，发现主要采用了宏定义的方式，所以调试是看不到具体的执行过程的，只会显示具体的值。
该函数会调用REQUEST_OUT_OF_RANGE函数对申请的size做校验以后，如果不通过则会返回为0，反之则调用request2size函数对该申请的size进行对齐操作。
#define checked_request2size(req, sz)
if (REQUEST_OUT_OF_RANGE (req)) {
__set_errno (ENOMEM);
return 0;
}
(sz) = request2size (req);
进入到REQUEST_OUT_OF_RANGE宏，可以看到具体的定义，主要就是校验申请的size是否大于等于-2*MINSIZE，因为是无符号的，所以不存在负数，会进行转换，具体转换的值可以看汇编拿到,可以看到是-0x41，进行unsigned int类型转换后是0xffffffffffffffbf。 这里放一下所用的变量的值：
所以这部分就相当于是判断申请的size是否大于等于0xffffffffffffffbf大小。
#define REQUEST_OUT_OF_RANGE(req)
((unsigned long) (req) >=
(unsigned long) (INTERNAL_SIZE_T) (-2 * MINSIZE))
如果申请的size没有超过最大范围，则会进行size的对齐操作，调用request2size宏实现。
这里看一下request2size宏的实现为：
#define request2size(req) \
(((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE) ? \
MINSIZE : \
((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)
整体相当于是对size做了对齐操作，计算公式如下：
real_size = (req+8+15)&0xfffffffffffffff0
在获取到了对齐的size之后，该函数会将对齐的size给到名为nb的参数2变量。
之后会开始判断arena是否为空，既进入到int_malloc函数前如果没有通过arena_get函数获取到，则通过sysmalloc函数申请对齐后size大小的空间，然后判断申请到的空间如果不为空，则调用alloc_perturb函数对该空间的数据进行填充size大小的00数据。
if (__glibc_unlikely (av == NULL))
{
void *p = sysmalloc (nb, av);
if (p != NULL)
alloc_perturb (p, bytes);
return p;
}
进入到alloc_perturb函数可以看到具体的实现，主要就是调用memset将p指向的地址空间设置n大小的00数据。
alloc_perturb (char *p, size_t n)
{
if (__glibc_unlikely (perturb_byte))
memset (p, perturb_byte ^ 0xff, n);
}
因为上述内容一般不太会进入到该流程，所以这里调试器直接就跳过了，直接开始进行下一步对nb(对齐后的size)进行判断是否小于等于get_max_fast函数的返回值。
这里进入到get_max_fast函数可以看到也是一个宏定义，其中指向了global_max_fast这个变量
#define get_max_fast() global_max_fast
这里查看这个global_max_fast变量的值,得到的结果是0，所以在第一开始，所申请的size并不会比get_max_fast获取到的值大。
这里的话，先不进行下面的流程，直接开始假设申请的size没有比get_fast_max函数获取到的值大的流程，因为get_fast_max的值是下面初始化的。
if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
{
idx = fastbin_index (nb);
mfastbinptr *fb = &fastbin (av, idx);
mchunkptr pp = *fb;
do
{
victim = pp;
if (victim == NULL)
break;
}
while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim))
!= victim);
if (victim != 0)
{
if (__builtin_expect (fastbin_index (chunksize (victim)) != idx, 0))
{
errstr = "malloc(): memory corruption (fast)";
errout:
malloc_printerr (check_action, errstr, chunk2mem (victim), av);
return NULL;
}
check_remalloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
}
}
当我们所申请的size对齐以后得到的size没有比get_max_fast函数的返回值值大的时候 ，则会进入到该函数体中，这里get_max_fast函数的返回值如果初始化过后是128，既我们所申请的size如果没有超过128字节，会先进入到fastbin这里。
首先会调用fastbin_index函数，从fastbin队列中找到适合我们申请的size大小的对应fastbin中的下标idx。
idx = fastbin_index (nb);
进入到fastbin_index函数可以看到具体的实现，主要计算公式：idx = (size >> 4) - 2
#define fastbin_index(sz) \
((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)
然后将调用fastbin函数，从arena的结构体中的fastbin数组中取出idx下标对应的chunk单向链表。
mfastbinptr *fb = &fastbin (av, idx);
mchunkptr pp = *fb;
最后将pp指针指向该chunk单向链表的表头，进行循环查找，catomic_compare_and_exchange_val_acq函数的作用是对fb和victim的值进行判断，假如一样，就将victim->fd指向的下一个chunk返回给pp，然后pp跟上一个victim进行比较，如果不一样就进行判断是否为空，如果不为空就继续循环下一个，直到循环到该chunk链表的末尾。
此段循环主要的作用是依次循环该chunk链表中的每一个，直到最后，并且来判断是否为空链表。
do
{
victim = pp;
if (victim == NULL)
break;
}
while ((pp = catomic_compare_and_exchange_val_acq(fb, victim->fd, victim))
!= victim);
如果链表非空，则开始检查链表最后一个 chunk 的属性是否符合要求。首先通过反向查找用 chunksize 函数获取该 chunk 的大小，然后根据这个大小使用 fastbin_index 函数查找该 chunk 的索引 idx，并检查这个 idx 是否与之前获取的 idx 相同，如果不相同则报错。
总结一下，这里就是对获取的chunk做了个合规检查。
if (victim != 0)
{
if (__builtin_expect (fastbin_index (chunksize (victim)) != idx, 0))
{
errstr = "malloc(): memory corruption (fast)";
errout:
malloc_printerr (check_action, errstr, chunk2mem (victim), av);
return NULL;
}
当校验其chunk的size没有问题后，会调用check_remalloced_chunk函数去对该chunk的size等属性再次进行校验，该校验流程可以进入到check_remalloced_chunk函数中看到。
进入到check_remalloced_chunk函数可以看到具体的实现，主要该函数会调用ç函数实现。
# define check_remalloced_chunk(A, P, N) do_check_remalloced_chunk (A, P, N)
进入到check_remalloced_chunk函数可以看到具体实现，首先该函数会获取校验chunk的真实size，去掉其中的mmap和inuse的标志位。
INTERNAL_SIZE_T sz = p->size & ~(PREV_INUSE | NON_MAIN_ARENA);
之后会校验该chunk的分配arena是否正确，假如是main_arena分配的，那av就必须是main_arena，反之一样。
if (!chunk_is_mmapped (p))
{
assert (av == arena_for_chunk (p));
if (chunk_non_main_arena (p))
assert (av != &main_arena);
else
assert (av == &main_arena);
}
校验完毕了arena后，会调用do_check_inuse_chunk函数开始校验chunk的结构是否合规。
进入到do_check_inuse_chunk函数可以看到，首先会创建一个名为next的chunk指针，然后会调用do_check_chunk函数来检查传入的chunk。
mchunkptr next;
do_check_chunk (av, p);
进入到do_check_chunk函数可以看到其具体实现，首先会对调用chunsize函数获取该chunk的大小，其次就是获取一些固定的值，比如可申请内存空间的最大地址和最小地址，其中最大的大小就是top_chunk加上其size，即是最大的地址，而最小地址则是最大地址减去system_mem，就是最小地址。
unsigned long sz = chunksize (p);
/* min and max possible addresses assuming contiguous allocation */
char *max_address = (char *) (av->top) + chunksize (av->top);
char *min_address = max_address - av->system_mem;
完成了size的获取和可分配的最大最小地址的初始化以后，将会调用is_mmapped函数来对该chunk进行校验，判断其是否是由main_arena分配的chunk，如果不是则进入下面的判断中继续。
if (!chunk_is_mmapped (p))
chunk_is_mmapped函数的实现流程其实很简单，就是判断一下chunk的size块的第二个bit的mmap标志位。
假如是main_arena分配的，则该标志位的值为0，反之则是mmap分配的，则该标志位的值为1。
#define chunk_is_mmapped(p) ((p)->size & IS_MMAPPED)
这里先分析main_arena分配的chunk，首先会对判断该chunk是否是top_chunk，如果不是，则调用contiguous函数对arena的flags的第二个bit做校验，判断是否为0，如果是0，就必须要求该chunk的size大于可申请的内存大小的最小size。最后假设p是top_chunk，则会要求其大小必须要大于最小大小，并且其上一个chunk块必须是在使用中。
if (!chunk_is_mmapped (p))
{
/* Has legal address ... */
if (p != av->top)
{
if (contiguous (av))
{
assert (((char *) p) >= min_address);
assert (((char *) p + sz) <= ((char *) (av->top)));
}
}
else
{
/* top size is always at least MINSIZE */
assert ((unsigned long) (sz) >= MINSIZE);
/* top predecessor always marked inuse */
assert (prev_inuse (p));
}
分析完毕main_arena分配的chunk的逻辑以后，该分析这个chunk是mmap分配的逻辑。首先会调用contiguous函数来对arena的分配模式进行校验，如果不是连续模式就返回0，并且top_chunk不是unsorted_bin中的chunk，则校验其chunk的地址是否在可分配的最大最小的地址范围内。
最后会调用assert函数，要求该chunk的size对齐页和内存。
if (!chunk_is_mmapped (p))
{
//...........
//...........
//...........
}
else
{
/* address is outside main heap */
if (contiguous (av) && av->top != initial_top (av))
{
assert (((char *) p) < min_address || ((char *) p) >= max_address);
}
/* chunk is page-aligned */
assert (((p->prev_size + sz) & (GLRO (dl_pagesize) - 1)) == 0);
/* mem is aligned */
assert (aligned_OK (chunk2mem (p)));
}
总结一下，其实假如我们的chunk是main_arena分配的，以上的这个do_check_chunk函数其实只是校验了一下chunk的size是否处在可分配的最大和最小的size范围内。
完成了do_check_chunk的校验以后，将继续do_check_inuse_chunk函数的剩余部分。
调用chunk_is_mmapped函数校验一下chunk是否是由mmap校验，如果是mmap分配的chunk，就退出校验。
if (chunk_is_mmapped (p))
return; /* mmapped chunks have no next/prev */
如果是main_arena分配的chunk，则调用inuse()函数来获取当前的chunk是否是在使用中，assert函数则要求该chunk必须是在使用中，既Inuse位的值为1。
assert (inuse (p));
进入到inuse()函数可以看到具体宏定义的实现，主要就是通过访问当前chunk的下一个chunk的prev_inuse位是否为1来判断当前的chunk是否在使用中。
#define inuse(p) \
((((mchunkptr) (((char *) (p)) + ((p)->size & ~SIZE_BITS)))->size) & PREV_INUSE)
之后调用next_chunk()函数来获取当前chunk的下一个chunk
next = next_chunk (p);
调用prev_inuse()函数，获取当前chunk的上一个chunk是否在使用当中，如果上一个chunk是free状态(未使用)的，则利用上一个chunk来对当前chunk进行校验。并且调用do_check_free_chunk**函数来再次检查上一个chunk是否是free**状态(未使用)。
if(!prev_inuse(p)) //如果上一个chunk是free状态的
{
/* Note that we cannot even look at prev unless it is not inuse */
mchunkptr prv = prev_chunk(p);
assert(next_chunk(prv) == p);
do_check_free_chunk(av, prv);
}
进入到do_check_free_chunk函数可以看到具体的实现，会先获取chunk的size，然后利用该size获取下一个chunk，接着调用do_check_chunk函数检查该chunk的size和arena的大小是否合规(这里上面分析过do_check_chunk函数了,就不分析了)。之后调用assert函数来校验当前p的inuse位和mmap位是否为0，assert函数要求chunk必须是main_arena分配并且必须是free的。
/* Chunk must claim to be free ... */
assert (!inuse (p));
assert (!chunk_is_mmapped (p));
最后就是调用一系列的合规检测。
首先会校验当前chunk的size是否大于等于MIN_SIZE。
如果大于等于，assert函数则会要求：
1 chunk中的size和user_data的地址必须是对齐的
2 上一个chunk必须是在使用状态
3 下一个chunk的prev_size必须和当前chunk的size一样
4 下一个chunk必须是在使用状态或者下一个chunk是top_chunk
5 上一个chunk和下一个chunk的fd和bk指针必须指向的是当前chunk
如果小于,则要求size必须等于SIZE_SZ。
if ((unsigned long) (sz) >= MINSIZE)
{
assert ((sz & MALLOC_ALIGN_MASK) == 0);
assert (aligned_OK (chunk2mem (p)));
/* ... matching footer field */
assert (next->prev_size == sz);
/* ... and is fully consolidated */
assert (prev_inuse (p));
assert (next == av->top || inuse (next));
/* ... and has minimally sane links */
assert (p->fd->bk == p);
assert (p->bk->fd == p);
}
else /* markers are always of size SIZE_SZ */
assert (sz == SIZE_SZ);
完成了上述的do_check_free_chunk函数分析后。回到这do_check_inuse_chunk函数中对上一个chunk的状态和size再次做了校验。
接着do_check_inuse_chunk函数剩余部分，该函数会对当前chunk的下一个chunk进行校验，判断是否为top_chunk，如果是top_chunk，则会调用assert函数对下一个chunk进行一些强制性要求：
1 要求当前chunk必须是在使用
2 下一个chunk的size必须大于等于MIN_SIZE
如果下一个chunk不是top_chunk，则会判断其是否是free的，如果下一个chunk是free状态的，则会调用do_check_free_chunk函数对下一个chunk的free状态再次检查。
if (next == av->top)
{
assert (prev_inuse (next));
assert (chunksize (next) >= MINSIZE);
}
else if (!inuse (next))
do_check_free_chunk (av, next);
在完成了对当前chunk的使用状态的检测后，将继续回到do_check_remalloced_chunk函数，对剩下的部分进行分析。
剩下的部分都是利用assert函数对该chunk的size进行一系列的合规要求：
1 要求size必须对齐
2 size必须要大于MIN_SIZE
3 user_data必须要对齐
4 当前chunk的大小必须和我们申请的大小一样
/* Legal size ... */
assert ((sz & MALLOC_ALIGN_MASK) == 0);
assert ((unsigned long) (sz) >= MINSIZE);
/* ... and alignment */
assert (aligned_OK (chunk2mem (p)));
/* chunk is less than MINSIZE more than request */
assert ((long) (sz) - (long) (s) >= 0);
assert ((long) (sz) - (long) (s + MINSIZE) < 0);
结束了do_check_remalloced_chunk函数的检测后，如果一切校验都满足，则会退出do_check_remalloced_chunk函数，返回到_int_malloc的剩余部分。
校验通过后，将会调用chunk2mem函数，来获取chunk的user_data部分的首地址，然后调用alloc_perturb函数填充用户区数据，最后返回给用户。
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
以上就是对fast_bin部分的分析。
接下来，假设我们申请的大小超过了fast_bin的大小，则将进入到small_bin的判断。
if (in_smallbin_range (nb))
首先会调用in_samllbin_range()函数来对对齐后的size进行校验，如果符合samll_bin的范围则进入查找合适的块。这里因为in_small_bin_range()是宏定义的函数，所以看不到调试的具体内容，所以这里直接静态分析。
分析后主要就是判断size是否小于MIN_LARGE_SIZE的大小，而MIN_LARGE_SIZE大小为((NSMALLBINS - SMALLBIN_CORRECTION) * SMALLBIN_WIDTH)，因为本次环境是64位的程序，所以MIN_LARGE_SIZE**大小为0x400(1024) Byte。**
#define NBINS 128
#define NSMALLBINS 64
#define SMALLBIN_WIDTH MALLOC_ALIGNMENT
#define SMALLBIN_CORRECTION (MALLOC_ALIGNMENT > 2 * SIZE_SZ)
#define MIN_LARGE_SIZE ((NSMALLBINS - SMALLBIN_CORRECTION) * SMALLBIN_WIDTH)
#define in_smallbin_range(sz) \
((unsigned long) (sz) < (unsigned long) MIN_LARGE_SIZE)
既当我们申请的size < 1024 的时候，就会进入到small_bin中进行分配。
假设我们所申请的大小符合small_bin的大小，首先会调用smallbin_index函数去获取size对应small_bin中的idx下标。之后调用bin_at函数来根据其下标，到arena的结构体中取出对应的chunk。
idx = smallbin_index (nb);
bin = bin_at (av, idx);
进入到smallbin_index函数可以看到其计算下标的方式为small_bin_idx = size >> 4。此时这里所用到的标志的值为：
| 变量 |
值 |
| INTERNAL_SIZE_T |
0x8 |
| MINSIZE |
0x20 |
| SIZE_SZ |
0x8 |
| MALLOC_ALIGN_MASK |
0xf |
| MALLOC_ALIGNMENT |
0x10 |
#define smallbin_index(sz) \
((SMALLBIN_WIDTH == 16 ? (((unsigned) (sz)) >> 4) : (((unsigned) (sz)) >> 3))\
+ SMALLBIN_CORRECTION)
进入到bin_at函数可以看到是如何根据idx从arena中取出对应chunk的。从源代码分析，可以很清晰的知道，chunk的指针是通过arena的bin[(idx-1)*2]-chunk结构体中fd指针的偏移得来的。chunk结构体中,fd指针的偏移是0x10。
计算公式如下:
chunk_ptr = arena->bin[(idx -1) * 2] - 16
#define bin_at(m, i) \
(mbinptr) (((char *) &((m)->bins[((i) - 1) * 2])) \
- offsetof (struct malloc_chunk, fd))
这里因为small_bin的fd和bk指针都有作用，一个fd和bk指针占2*SIZE_T，故这里下标需要需要乘2，最后返回的是该chunk的fd指针(当然这里说法不一，具体左右还需自己调试理解。)
这里我们算一下假设我们的申请的size处在最小MIN_SIZE(0x20)到MIN_LARGE_SIZE(0x400)之间，下标一共有：
buf = set()
for idx in range(0x20,0x400):
buf.add(((idx>>4) -1) * 2)
print len(buf)
因此，可以知道，small_bin中一共用着62个下标的数据块。
接着会调用last函数取出该idx下标对应的chunk链表的最后一个chunk，来判断是否跟头链表是否一样。如果不一样，则证明该chunk链表不为空，否则证明当前下标的chunk链表为空。
if ((victim = last (bin)) != bin)
如果当前下标链表不为空，则会对最后一个chunk进行校验，如果最后一个chunk为0，则意味着bin中数据没有初始化，将会调用malloc_consolidate函数对当前的arena进行初始化，否则就将当前的chunk的上一个chunk的地址给到bck这个指针，然后利用该bck指向的上一个chunk的fd指针来对当前chunk进行校验是否一致。
如果一致，就将调用set_inuse_bit_at_offset函数将通过当前chunk加size偏移来获取下一个chunk，然后将下一个chunk的prev_inuse位设置为1，意味着当前chunk已被使用。
最后将当前这个chunk从bin的双向链表中移除，然后校验arena是否是main_arena，如果不是就需要设置该chunk的size位置的mmap的标志位为1。
if ((victim = last (bin)) != bin)
{
if (victim == 0) /* initialization check */
malloc_consolidate (av);
else
{
bck = victim->bk;
if (__glibc_unlikely (bck->fd != victim))
{
errstr = "malloc(): smallbin double linked list corrupted";
goto errout;
}
set_inuse_bit_at_offset (victim, nb);
bin->bk = bck;
bck->fd = bin;
if (av != &main_arena)
victim->size |= NON_MAIN_ARENA;
check_malloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
}
}
调用check_malloced_chunk函数校验当前chunk的size和用户申请的size(nb变量)是否一致，这里校验跟上面do_check_remalloced_chunk函数几乎一样，唯独最后多了一个要求当前chunk的上一个chunk必须为使用状态。
static void
do_check_malloced_chunk (mstate av, mchunkptr p, INTERNAL_SIZE_T s)
{
/* same as recycled case ... */
do_check_remalloced_chunk (av, p, s);
/*
... plus, must obey implementation invariant that prev_inuse is
always true of any allocated chunk; i.e., that each allocated
chunk borders either a previously allocated and still in-use
chunk, or the base of its memory arena. This is ensured
by making all allocations from the `lowest' part of any found
chunk. This does not necessarily hold however for chunks
recycled via fastbins.
*/
assert (prev_inuse (p));
}
完成了校验之后，就比较常规的执行chunk2mem获取user_data的地址，alloc_perturb函数负责将user_data区域的值设置为00字节，最后将获取到的user_data的地址返回给用户。
以上是small_bin的过程。但是这里没有提到malloc_consolidate函数，所以放到这里继续分析。
进入到malloc_consolidate函数可以看到具体的实现逻辑，首先该函数会先校验get_max_fast()**函数的返回值是否为0，如果是0的话，就将调用malloc_init_state函数和check_malloc_state函数对arena进行初始化操作。**
if (get_max_fast () != 0) {
//这里先省略不做分析
//......
}
else {
malloc_init_state(av);
check_malloc_state(av);
}
进入到malloc_init_state函数可以看到具体的实现逻辑，首先，会初始化从bin[1]到bin[127]中的所有chunk链表，将表头的fd和bk指针都指向自己。
int i;
mbinptr bin;
/* Establish circular links for normal bins */
for (i = 1; i < NBINS; ++i)
{
bin = bin_at (av, i);
bin->fd = bin->bk = bin;
}
接着开始判断当前的arena，如果不是main_arena就调用set_noncontiguous**函数，将arena的flags**的第二个bit设置为1.
#if MORECORE_CONTIGUOUS
if (av != &main_arena)
#endif
set_noncontiguous (av);
如果arena是main_arena，就调用set_max_fast()函数,参数为DEFAULT_MXFAST，设置get_max_fast()函数的返回值为128 (64位)。
if (av == &main_arena)
set_max_fast (DEFAULT_MXFAST);
这里进入到set_max_fast()函数可以看到实现逻辑，其中s = DEFAULT_MXFAST，DEFAULT_MXFAST = 128 (64位)。
经过计算，这里global_max_fast=128，所以下次再次触发get_fast_max()函数，得到的返回值将会是128，不再是0了。
#define set_max_fast(s) \
global_max_fast = (((s) == 0) \
? SMALLBIN_WIDTH : ((s + SIZE_SZ) & ~MALLOC_ALIGN_MASK))
在完成了上述内容后，会将当前arnea的flags的第1个bit位设置为1，最后把调用initial_top函数将当前arena的bin[0]-0x10位置的chunk传给arena的top，意味着先将bin[0]-0x10位置的chunk当做top_chunk。
av->flags |= FASTCHUNKS_BIT;
av->top = initial_top (av);
完成以上内容后，将继续调用check_malloc_state()函数，对当前的arena的内容进行检查等，arena的初始化这里就不分析了，接下来继续分析上述当get_max_fast()函数不为0的逻辑。
当get_max_fast**函数不为0时，会先调用clear_fastchunks函数，将arena中flags第一个bit的值设置为1，既清空fastbin中的chunk**。
接着调用unsorted_chunks()函数，将**bin[0]-0x10位置的chunk给到unsorted_bin，之后获取第一个和最后一个fastbin**数组的chunk链表
if (get_max_fast () != 0) {
clear_fastchunks(av);
unsorted_bin = unsorted_chunks(av);
/*
Remove each chunk from fast bin and consolidate it, placing it
then in unsorted bin. Among other reasons for doing this,
placing in unsorted bin avoids needing to calculate actual bins
until malloc is sure that chunks aren't immediately going to be
reused anyway.
*/
maxfb = &fastbin (av, NFASTBINS - 1);
fb = &fastbin (av, 0);
接下来是一个非常大的do_while的循环体，主要目的是为了实现fastbin的合并到unsorted_bin的过程。
首先会调用atomic_exchange_acq()函数获取一下fastbin中下标为0位置的chunk链表给到p
p = atomic_exchange_acq (fb, 0);
然后判断p是否为空，如果p不为空，则意味着当前chunk链表不为空，将执行第二个do_while循环，开始循环该链表中的每一个chunk
if (p != 0) {
do {
check_inuse_chunk(av, p);
nextp = p->fd;
/* Slightly streamlined version of consolidation code in free() */
size = p->size & ~(PREV_INUSE|NON_MAIN_ARENA);
nextchunk = chunk_at_offset(p, size);
nextsize = chunksize(nextchunk);
if (!prev_inuse(p)) {
prevsize = p->prev_size;
size += prevsize;
p = chunk_at_offset(p, -((long) prevsize));
unlink(av, p, bck, fwd);
}
if (nextchunk != av->top) {
nextinuse = inuse_bit_at_offset(nextchunk, nextsize);
if (!nextinuse) {
size += nextsize;
unlink(av, nextchunk, bck, fwd);
} else
clear_inuse_bit_at_offset(nextchunk, 0);
first_unsorted = unsorted_bin->fd;
unsorted_bin->fd = p;
first_unsorted->bk = p;
if (!in_smallbin_range (size)) {
p->fd_nextsize = NULL;
p->bk_nextsize = NULL;
}
set_head(p, size | PREV_INUSE);
p->bk = unsorted_bin;
p->fd = first_unsorted;
set_foot(p, size);
}
else {
size += nextsize;
set_head(p, size | PREV_INUSE);
av->top = p;
}
} while ( (p = nextp) != 0);
首先会调用check_inuse_chunk函数对该chunk链表中的chunk进行校验，要求当前chunk的下一个chunk的prev_inuse位的值必须为1(这里因为fastbin中的chunk在free的时候，默认不会清空**inuse**位的值，所以这里不是代表该chunk是在使用中)
check_inuse_chunk(av, p);
接着会获取该chunk的真实的size大小，然后利用该size获取当前chunk的下一个chunk的地址和size
size = p->size & ~(PREV_INUSE|NON_MAIN_ARENA);
nextchunk = chunk_at_offset(p, size);
nextsize = chunksize(nextchunk);
这里会校验一下，该chunk的前一个chunk是否是free的，如果当前chunk的上一个chunk是free状态的，那么就会对上一个free状态的chunk进行合并操作。
首先会获取free状态的chunk的大小，将其合并到当前chunk的size中，然后调用chunk_at_offset函数获取上一个chunk的地址，最后调用unlink函数将上一个chunk移除。
if (!prev_inuse(p)) {
prevsize = p->prev_size;
size += prevsize;
p = chunk_at_offset(p, -((long) prevsize));
unlink(av, p, bck, fwd);
}
进入到unlink函数可以看到具体的实现过程，其实该函数的主要目的就是将当前的chunk从small_bin和large_bin的两个双向链表中移除。
首先会获取移除chunk的fd和bk指针，然后利用fd指针和bk指针的值来对当前的chunk**做校验，确保p的fd和bk指针没有被修改，如果被修改了就会报"**corrupted double-linked list"错误。
/* Take a chunk off a bin list */
#define unlink(AV, P, BK, FD) { \
FD = P->fd; \
BK = P->bk; \
if (__builtin_expect (FD->bk != P || BK->fd != P, 0)) \
malloc_printerr (check_action, "corrupted double-linked list", P, AV); \
如果校验通过后，将会设置fd和bk指针的值，将当前的Chunk移除链表。接下来还需要考虑如何移除第二条双向链表，fd_nextsize和bk_nextsize的情况。
FD->bk = BK;
BK->fd = FD;
首先会判断要移除的chunk是否符合small_bin的范围，并且chunk的fd_nextsize指针位置不为空，如果满足这两个条件，则会认为该chunk是large_bin中的chunk，因为small_bin中保存的chunk不存在使用fd_nextsize和bk_nextsize的情况)。
if (!in_smallbin_range (P->size) \
&& __builtin_expect (P->fd_nextsize != NULL, 0))
如果校验通过，则利用该chunk的fd_nextsize和bk_nextsize指针来进行校验自身，判断其fd_nextsize和bk_nextsize是否被修改。
if (!in_smallbin_range (P->size) \
&& __builtin_expect (P->fd_nextsize != NULL, 0)) { \
if (__builtin_expect (P->fd_nextsize->bk_nextsize != P, 0) \
|| __builtin_expect (P->bk_nextsize->fd_nextsize != P, 0)) \
malloc_printerr (check_action, \
"corrupted double-linked list (not small)", \
P, AV);
这里补充一下fd_nextsize和bk_nextsize的知识，fd_nextsize**指向的是比自身小的下一个size，bk_nextsize指向的是比自身大的第一个size，然后当chunk大小相同时，则会在同一个chunk的双向链表中，而这个双向链表只有头chunk有fd_nextsize和bk_nextsize，这里的fd_nextsize和bk_nextsize是指向比自身chunk大和小的第一个chunk。这里随便放一张large_bin的结构图(size是随便编的,主要参考结构)：**
如果fd_nextsize和bk_nextsize指针并未被修改，则开始判断要移除的chunk的下一个chunk的fd_nextsize指针是否为NULL，如果为NULL则代表要判断移除chunk的size和下一个chunk的size一样，处在同一个双向链表中，这时就要接着判断移除chunk的fd_nextsize是否指向自身，如果指向自身则代表，该large_bin的chunk链表中只有这一个size的chunk双向链表，想要移除该chunk，只需要将fd_nextsize和bk_nextsize指向它的下一个chunk自身即可。
if (FD->fd_nextsize == NULL) { \
if (P->fd_nextsize == P) \
FD->fd_nextsize = FD->bk_nextsize = FD; \
else { \
....... \
} \
} else { \
........ \
}
}
如果说将要移除的chunk的fd_nextsize并没有指向自身，则代表该large_bin中，还有其他的size的chunk双向链表，需要将当前chunk的fd_nextsize和bk_nextsize都指向下一个size的chunk链表，然后同理再将下一个size的chunk双向链表的表头的fd_nextsize和bk_nextsize也指向移除chunk的下一个chunk。
if (FD->fd_nextsize == NULL) { \
if (P->fd_nextsize == P) \
.......... \
else { \
FD->fd_nextsize = P->fd_nextsize; \
FD->bk_nextsize = P->bk_nextsize; \
P->fd_nextsize->bk_nextsize = FD; \
P->bk_nextsize->fd_nextsize = FD; \
} \
} else { \
........ \
........ \
} \
}
如果下一个chunk的fd_nextsize指针不为空，则代表移除的chunk和下一个chunk的size不一样，就正常进行该size的chunk的双向链表的移除操作即可。
if (FD->fd_nextsize == NULL) { \
if (P->fd_nextsize == P) \
........ \
else { \
........ \
} \
} else { \
P->fd_nextsize->bk_nextsize = P->bk_nextsize; \
P->bk_nextsize->fd_nextsize = P->fd_nextsize; \
} \
}
以上便是unlink的过程。
完成了对应的unlink函数以后，将继续回到malloc_consolidate函数，当上一个chunk如果是free状态的，就会执行对该空闲chunk执行unlink操作，将其从对应的bin中的双向链表中移除。
if (!prev_inuse(p)) {
prevsize = p->prev_size;
size += prevsize;
p = chunk_at_offset(p, -((long) prevsize));
unlink(av, p, bck, fwd);
}
接着会判断，下一个chunk是否是top_chunk，如果不是，则调用inuse_bit_at_offset函数，结合下一个chunk的size，来获取下一个chunk的使用状态。
if (nextchunk != av->top) {
nextinuse = inuse_bit_at_offset(nextchunk, nextsize);
inuse_bit_at_offset函数的宏定义如下：
主要就就是chunk+chunk_size来获取下一个chunk的位置，然后通过&prev_inuse来获取prev_inuse位的状态来得知当前chunk的状态。
#define inuse_bit_at_offset(p, s) \
(((mchunkptr) (((char *) (p)) + (s)))->size & PREV_INUSE)
如果判断下一个chunk也是free状态的话，也是一样，将其大小合并到size，然后调用unlink函数将其从对应的bin的双向链表中移除。
如果下一个chunk是使用状态，则调用clear_inuse_bit_at_offset函数，将其prev_inuse位设置为0，既将当前chunk**设置为free状态。**
if (!nextinuse) {
size += nextsize;
unlink(av, nextchunk, bck, fwd);
} else
clear_inuse_bit_at_offset(nextchunk, 0);
完成了上述对上一个chunk和下一个chunk的状态的校验后，会发现，如果上下两个相邻的chunk如果是free状态的，那么就会合并，并且将其移出对应的bin的双向链表。
接下来会获取Unsorted_bin的第一个chunk，然后将当前Chunk接入到Unsorbin中。
first_unsorted = unsorted_bin->fd;
unsorted_bin->fd = p;
first_unsorted->bk = p;
之后判断合并以后的size是否大于等于0x400，如果大于small_bin的范围，则将fd_nextsize和bk_nextsize指向为NULL。
if (!in_smallbin_range (size)) {
p->fd_nextsize = NULL;
p->bk_nextsize = NULL;
}
调用set_head函数，将当前chunk的size的prev_inuse位设置为1，然后再调用set_foot函数，将当前chunk的下一个chunk的prev_size的位置设置为该chunk的size，最后把fd和bk指向到unsorted_bin中，既完成合并unsorted_bin的最终操作。
set_head(p, size | PREV_INUSE);
p->bk = unsorted_bin;
p->fd = first_unsorted;
set_foot(p, size);
如果下一个chunk是top_chunk，就将下一个chunk的size合并到当前chunk的size中，然后将该size的prev_inuse位设置为1，再把该size设置为当前chunk的size，最后将arena中的top_chunk设置为当前chunk，既将当前chunk合并到top_chunk。
if (nextchunk != av->top) {
//......
//......
//......
}
else {
size += nextsize;
set_head(p, size | PREV_INUSE);
av->top = p;
}
完成了fastbin中chunk的合并以后，将继续循环当前chunk链表中的其他的chunk，进行合并。
do {
//........
} while ( (p = nextp) != 0);
如果当前chunk链表遍历完毕以后，将继续循环fastbin中下一个idx的chunk链表，直到fastbin中最大的idx对应的chunk链表。
do {
//.......
//.......
do {
//........
} while ( (p = nextp) != 0);
} while (fb++ != maxfb);
完成了上述内容后，就该回到_int_malloc**函数**。
以上就是small_bin中的内容分析，接下来，如果size的大小，超过了small_bin的范围，则调用largebin_index函数根据用户申请的size来找到对应的idx，然再调用have_fastchunks函数，判断arena中的fast_bin是否存在空闲chunk，如果存在，就调用malloc_consolidate函数，对arena中fast_bin中的free的chunk进行合并。
if (in_smallbin_range (nb))
{
//......
//.......
}
else
{
idx = largebin_index (nb);
if (have_fastchunks (av))
malloc_consolidate (av);
}
进入到largebin_index函数可以看到具体的宏定义实现，主要计算过程如下：
1 当 ((sz) >> 6) <= 48**：**
-
如果 sz 右移 6 位后，结果小于等于 48，则 sz 在 0x100（256）到 0x1800（6144）字节之间。
-
idx计算：48 + ((sz) >> 6)。
2 当 ((sz) >> 9) <= 20**：**
-
如果 sz 右移 9 位后，结果小于等于 20，则 sz 在 0x1800（6144）到 0x4000（16384）字节之间。
-
idx计算：91 + ((sz) >> 9)。
3 当 ((sz) >> 12) <= 10**：**
-
如果 sz 右移 12 位后，结果小于等于 10，则 sz 在 0x4000（16384）到 0xA000（40960）字节之间。
-
idx计算：110 + ((sz) >> 12)。
4 当 ((sz) >> 15) <= 4**：**
-
如果 sz 右移 15 位后，结果小于等于 4，则 sz 在 0xA000（40960）到 0x28000（163840）字节之间。
-
idx计算：119 + ((sz) >> 15)。
5 当 ((sz) >> 18) <= 2**：**
-
如果 sz 右移 18 位后，结果小于等于 2，则 sz 在 0x28000（163840）到 0x100000（1048576）字节之间。
-
idx计算：124 + ((sz) >> 18)。
6 否则：
-
如果 sz 超过 1 MB（即 sz >> 18 大于 2），索引固定为 126。
其中size超过了0x400的chunk ，就会开始在large_bin的范围内开始找了。
#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)
获取了large_bin的idx以后，会调用have_fastchunks函数，进入have_fastchunks函数可以看到具体实现，主要就是取arena->flags的最低位bit是否为0来判断fast_bin是否为空。
#define have_fastchunks(M) (((M)->flags & FASTCHUNKS_BIT) == 0)
如果为空则调用malloc_consolidate函数进行合并，这里合并的过程上面已经分析过了。这里继续下面的代码分析，这里先补充一下unsorted_bin的结构图：
接下来是一个非常的大的循环，根据用户申请的size从各个bin中寻找适合的chunk进行分配。
for (;; )
{
//......
//......
//.....
//.....
}
首先会将idx变量设置为0，然后开启第二段while循环，主要是在unsorted_bin中进行chunk的分配操作，最大循环次数是10000。
主要循环方式是从尾到头进行循环。
首先调用unsorted_chunks函数，获取unsorted_bin中最后一个chunk，并且跟unsorted_bin中的第一个chunk进行比较，如果一样就停止循环，其中victim是跟unsorted_bin的first_chunk循环比较的每一个chunk。
int iters = 0;
while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
{
#define MAX_ITERS 10000
if (++iters >= MAX_ITERS)
break;
}
进入到循环体内部，首先会将当前循环chunk的上一个chunk，将其保存到bck中。然后将开始校验该chunk的size是否合规，如果不合规将报“malloc(): memory corruption”错误。
通过了size的合规检测，将调用checksize函数获取当前循环chunk的size，将其保存到size变量中。
while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
{
bck = victim->bk; //获取最后一个unsorted_bin中的chunk
if (__builtin_expect (victim->size <= 2 * SIZE_SZ, 0)
|| __builtin_expect (victim->size > av->system_mem, 0))
malloc_printerr (check_action, "malloc(): memory corruption",
chunk2mem (victim), av);
size = chunksize (victim);
//......
//.......
}
之后就是一个多条件判断：
1 调用in_smallbin_range函数，判断当前用户申请的size是否在small_bin的范围内
2 调用unsorted_chunks函数获取unsorted_bin中的first_chunk**，判断当前chunk的上一个chunk是否是unsorted_bin的**first_chunk
3 判断当前chunk是否是arena中的remainder分割的剩余chunk，既remainder_chunk。
4 判断当前chunk的size是否大于用户申请的size+MINSZIE,判断当前chunk的size是否可以满足用户申请的size
只有满足了上述四个条件，nb(用户申请的size) < 0x400、上一个chunk是unsorted_bin的first_chunk、当前chunk是remainder_chunk并且size大小满足用户所申请的size大小，就将当前的chunk进行分割，分为用户申请的size大小和reamin_size大小两部分。
首先会先计算当前chunk的size减去用户所申请的size还剩下多少size，将其保存到remainder_size变量中，之后调用chunk_at_offset函数获取remainder_chunk的地址，然后将这个remainder_chunk当做新的unsorted_bin。
remainder_size = size - nb;
remainder = chunk_at_offset (victim, nb);
unsorted_chunks (av)->bk = unsorted_chunks (av)->fd = remainder;
av->last_remainder = remainder;
remainder->bk = remainder->fd = unsorted_chunks (av);
之后会再次调用in_samll_bin函数判断分割后剩余的remainder_size是否在small_bin的范围内，如果剩余的remainder_size大于等于0x400，则代表其在large_bin的范围内，将remainder_chunk的fd_nextsize和bk_nextsize的指针置空。
if (!in_smallbin_range (remainder_size))
{
remainder->fd_nextsize = NULL;
remainder->bk_nextsize = NULL;
}
之后就是调用set_head和set_food函数将用户所申请大小的chunk和剩余的remainder_chunk的size部分进行设置，将对应的prev_inuse位和mmap位设置为对应的值，最后将remainder_chunk的next_chunk的prev_size也设置为remainder_size。
set_head (victim, nb | PREV_INUSE |
(av != &main_arena ? NON_MAIN_ARENA : 0));
set_head (remainder, remainder_size | PREV_INUSE);
set_foot (remainder, remainder_size);
设置完chunk的状态的内容后，就将用户所申请的chunk返回给用户，这部分内容就前面都有类似，就不再叙述了。
check_malloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
假如上述条件判断结束后，并没有找到合适的chunk，继续执行。
将当前的chunk移出unsorted_bin的chunk链表中
/* remove from unsorted list */
unsorted_chunks (av)->bk = bck;
bck->fd = unsorted_chunks (av);
判断当前循环的chunk的size是否和用户所申请的一致，如果size一致则调用set_inuse_bit_at_offset函数设置一下chunk的size部分的内容，然后直接将当前chunk返回给用户。
if (size == nb)
{
set_inuse_bit_at_offset (victim, size);
if (av != &main_arena)
victim->size |= NON_MAIN_ARENA;
check_malloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
}
假如上述判断并没有成立，则继续执行。
首先会调用in_smallbin_range函数判断当前chunk的size是否处在small_bin范围内，如果在就调用smallbin_index函数根据当前chunk的size获取small_bin中的idx，然后再调用bin_at函数获取arena->bin中对应idx的chunk链表的头指针，保存到bck变量中，然后将头指针指向的第一个chunk保存到fwd变量中。
if (in_smallbin_range (size))
{
victim_index = smallbin_index (size);
bck = bin_at (av, victim_index);
fwd = bck->fd;
}
如果当前chunk的size并未在small_bin范围中，而是在large_bin中，那么同理先调用largebin_index函数根据当前chunk的size获取large_bin中的idx，然后再调用bin_at函数获取arena->bin中对应idx的chunk链表的头指针，保存到bck变量中，然后将头指针指向的第一个chunk保存到fwd变量中。
if (in_smallbin_range (size))
{
//.....
//......
}
else
{
victim_index = largebin_index (size);
bck = bin_at (av, victim_index);
fwd = bck->fd;
接下来，会进行多种条件的判断，首先，会利用获取到的bck和fwd进行判断。
如果chunk的链表头指针bck**和第一个chunk的fwd指针不相等，则认为当前bin[idx]对应chunk链表中有chunk，不为空。然后会将当前chunk的size的prev_inuse位设置为1。完成上述内容后，会调用assert函数**对该chunk链表的最后一个chunk的size进行校验，要求其必须为main_arena分配的chunk。
if (fwd != bck)
{
/* Or with inuse bit to speed comparisons */
size |= PREV_INUSE;
/* if smaller than smallest, bypass loop below */
assert ((bck->bk->size & NON_MAIN_ARENA) == 0);
接着会判断当前循环的chunk的size是否比large_bin的对应idx的chunk链表的最后一个chunk的size还小。
如果当前chunk的size比large_bin中idx的chunk链表的最后一个chunk的size还小，那么就会把当前循环的chunk接入到large_bin中idx的chunk链表的末尾。
if ((unsigned long) (size) < (unsigned long) (bck->bk->size)) //bck->bk是该idx的chunk链表中最后一个chunk
{
fwd = bck;
bck = bck->bk;
victim->fd_nextsize = fwd->fd;
victim->bk_nextsize = fwd->fd->bk_nextsize;
fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim;
}
否则会先调用assert函数要求该chunk链表中的第一个chunk必须是main_arena分配的chunk，然后开始利用fd_nextsize指针，循环遍历当前chunk链表中每一个不同size的chunk**，之后调用assert函数，又一次对chunk的arena进行校验，必须是main_arena分配的chunk，该循环直到找到比当前chunk的size大于等于的第一个chunk为止。**
if ((unsigned long) (size) < (unsigned long) (bck->bk->size)) //bck->bk是该idx的chunk链表中最后一个chunk
{
//.....
//.........
//............
}
else
{
assert ((fwd->size & NON_MAIN_ARENA) == 0);
while ((unsigned long) size < fwd->size)
{
fwd = fwd->fd_nextsize;
assert ((fwd->size & NON_MAIN_ARENA) == 0);
}
//........
}
这里如果找到以后，会先判断，假如找到的large_bin中的chunk大小跟当前chunk的size一样，则说明两个chunk相同，直接将当前fwd的位置放到fwd的下边。
if ((unsigned long) size == (unsigned long) fwd->size)
/* Always insert in the second position. */
fwd = fwd->fd;
else{
//........
//........
}
如果不一样的话，就需要利用fd_nextsize和bk_nextsize指针，将当前chunk接入的位置放到fwd的右边，一会儿便于插入使用。
如果chunk的链表头指针bck**和第一个chunk的fwd指针相等，则代表该chunk的链表为空，那么就直接将当前chunk的fd_nextsize和bk_nextsize**指针全都指向自身。
/* maintain large bins in sorted order */
if (fwd != bck)
{
//........
//........
}
else
victim->fd_nextsize = victim->bk_nextsize = victim;
完成了上述samll_bin和large_bin中的fwd和bck的获取后，将开始调用mark_bin函数，先获取small_bin或large_bin中当前chunk的size对应的idx，然后将bin_map中对应idx位置的bit位设置为1，最后利用头插法，将上面找了半天的当前chunk的插入位置，插入当前循环的chunk。
mark_bin (av, victim_index);
victim->bk = bck; //采用头插法，插入到chunk链表中。
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;
这里进入到mark_bin可看到具体的实现，首先利用idx2block获取idx处于binmap中的具体索引，然后利用与运算，将binmap对应idx未知的值设为1.
#define mark_bin(m, i) ((m)->binmap[idx2block (i)] |= idx2bit (i))
这里可以进入到idx2block可以看到具体的实现，这里BINMAPSHIFT = 5，相当于是将当前的idx右移5位，相当于是除以32，以此来得到当前idx在binmap的第几个block中。
#define idx2block(i) ((i) >> BINMAPSHIFT)
得到了第几个Block以后，利用idx2bit函数，才知道Block中idx具体对应的bit位数，然后将其设置为1。
#define idx2bit(i) ((1U << ((i) & ((1U << BINMAPSHIFT) - 1))))
以上就是mark_bin函数的完整设置过程。
最后会对这次的循环设置一个次数，最多在unsorted_bin中寻找10000次，以防止死循环。
#define MAX_ITERS 10000
if (++iters >= MAX_ITERS)
break;
}
以上就是在unsorted_bin中寻找合适chunk的全部过程了，归根结底，unsorted_bin中如果找到了chunk，就直接分配，找不到就将chunk插入到small_bin或者large_bin中。
假如刚才没有成功在这个unsorted_bin中取到合适的chunk，那么就开始调用in_smallbin_range函数对用户申请的size进行校验，假如用户申请的size没有在small_bin中，那么就从large_bin中去找。
if (!in_smallbin_range(nb))
{
//.......
//.......
}
进入到这个判断内部可以看到，因为前面已经取过当前size在large_bin的idx了，所以这里直接用bin_at函数，直接在bin中取对应idx的chunk链表。然后调用first函数获取该chunk链表的第一个chunk，来跟头chunk进行比较，如果不一样，则代表当前chunk链表不为空，并且第一个chunk的size是否大于等于用户申请的大小，如果一切成立才继续执行判断内的代码，否则就跳出larget_bin的查找。
if (!in_smallbin_range(nb))
{
//.......
//.......
if ((victim = first(bin)) != bin && (unsigned long)(victim->size) >= (unsigned long)(nb))
{
//......
}
}
因为在large_bin中，chunk链表的第一个chunk一般是size最大的chunk，然后一直由大到小排列。这里假如用户所申请的size刚好满足，并且large_bin中的chunk不为空。
开始执行循环，从大到小去找第一个大于等于用户所申请size大小的chunk。
victim = victim->bk_nextsize;
while (((unsigned long) (size = chunksize(victim)) < (unsigned long) (nb)))
victim = victim->bk_nextsize;
开始判断，找到之后的chunk是否和用户申请的size一样，并且判断当前chunk是否是最后一个chunk，如果size一样的，并且当前chunk不是最后一个chunk，直接操作fd指针，将当前chunk的fd指针指向的chunk给到victim
if (victim != last(bin) && victim->size == victim->fd->size)
victim = victim->fd;
接下来就是将找到的比用户申请的size大于等于的第一个chunk的size进行分割，计算剩余size，然后将其从large_bin的chunk双向链表中移除。
/* remove from unsorted list */
unsorted_chunks (av)->bk = bck;
bck->fd = unsorted_chunks (av);
接着判断剩余size，是否小于MIN_SIZE，如果小于MIN_SIZE，则调用set_inuse_bit_at_offset函数，将该chunk的next_chunk的prev_inuse位设置为1，代表将当前的chunk的状态修改为使用状态。最后判断一下mmap的状态，如果是main_arena分配的chunk则将size中mmap位标志设置为0，反之则为1。
if (remainder_size < MINSIZE)
{
set_inuse_bit_at_offset(victim, size);
if (av != &main_arena)
victim->size |= NON_MAIN_ARENA;
}
如果剩余大小比MIN_SIZE大，则将其remainder_chunk接入到unsort_bin中，然后将当前chunk的size设置为用户所申请的大小，返回给用户，和上面unsorted_bin的分割的操作一样，就不再重复分析了。
if (remainder_size < MINSIZE)
{
//......
//......
}
/* Split */
else
{
remainder = chunk_at_offset(victim, nb);
/* We cannot assume the unsorted list is empty and therefore
have to perform a complete insert here. */
bck = unsorted_chunks(av);
fwd = bck->fd;
if (__glibc_unlikely(fwd->bk != bck))
{
errstr = "malloc(): corrupted unsorted chunks";
goto errout;
}
remainder->bk = bck;
remainder->fd = fwd;
bck->fd = remainder;
fwd->bk = remainder;
if (!in_smallbin_range(remainder_size))
{
remainder->fd_nextsize = NULL;
remainder->bk_nextsize = NULL;
}
set_head(victim, nb | PREV_INUSE |
(av != &main_arena ? NON_MAIN_ARENA : 0));
set_head(remainder, remainder_size | PREV_INUSE);
set_foot(remainder, remainder_size);
}
check_malloced_chunk(av, victim, nb);
void *p = chunk2mem(victim);
alloc_perturb(p, bytes);
return p;
}
假如上述在fast_bin、small_bin、unsorted_bin和large_bin中都没有找到合适的chunk，那么就在所有arena->bin中寻找空闲的chunk。
这里遍历所有的arena->bin主要就是通过bin_map实现，这里上面说过了bin_map的原理了，就不再叙述了。
++idx;
bin = bin_at(av, idx);
block = idx2block(idx);
map = av->binmap[block];
bit = idx2bit(idx);
for (;; )
{
/* Skip rest of block if there are no more set bits in this block. */
if (bit > map || bit == 0)
{
do
{
if (++block >= BINMAPSIZE) /* out of bins */
goto use_top;
}
while ((map = av->binmap[block]) == 0);
bin = bin_at(av, (block << BINMAPSHIFT));
bit = 1;
}
/* Advance to bin with set bit. There must be one. */
while ((bit & map) == 0)
{
bin = next_bin(bin);
bit <<= 1;
assert(bit != 0);
}
/* Inspect the bin. It is likely to be non-empty */
victim = last(bin);
/* If a false alarm (empty bin), clear the bit. */
if (victim == bin)
{
av->binmap[block] = map &= ~bit; /* Write through */
bin = next_bin(bin);
bit <<= 1;
}
else
{
size = chunksize(victim);
/* We know the first chunk in this bin is big enough to use. */
assert((unsigned long) (size) >= (unsigned long) (nb));
remainder_size = size - nb;
/* unlink */
unlink(av, victim, bck, fwd);
/* Exhaust */
if (remainder_size < MINSIZE)
{
set_inuse_bit_at_offset(victim, size);
if (av != &main_arena)
victim->size |= NON_MAIN_ARENA;
}
/* Split */
else
{
remainder = chunk_at_offset(victim, nb);
/* We cannot assume the unsorted list is empty and therefore
have to perform a complete insert here. */
bck = unsorted_chunks(av);
fwd = bck->fd;
if (__glibc_unlikely(fwd->bk != bck))
{
errstr = "malloc(): corrupted unsorted chunks 2";
goto errout;
}
remainder->bk = bck;
remainder->fd = fwd;
bck->fd = remainder;
fwd->bk = remainder;
/* advertise as last remainder */
if (in_smallbin_range(nb))
av->last_remainder = remainder;
if (!in_smallbin_range(remainder_size))
{
remainder->fd_nextsize = NULL;
remainder->bk_nextsize = NULL;
}
set_head(victim, nb | PREV_INUSE |
(av != &main_arena ? NON_MAIN_ARENA : 0));
set_head(remainder, remainder_size | PREV_INUSE);
set_foot(remainder, remainder_size);
}
check_malloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb(p, bytes);
return p;
}
}
假如寻遍bin_map中也没找到能够分配的chunk，那么就直接从top_chunk中直接进行分割。
use_top:
victim = av->top;
size = chunksize (victim);
if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE))
{
remainder_size = size - nb;
remainder = chunk_at_offset (victim, nb);
av->top = remainder;
set_head (victim, nb | PREV_INUSE |
(av != &main_arena ? NON_MAIN_ARENA : 0));
set_head (remainder, remainder_size | PREV_INUSE);
check_malloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
}
如果说，用户申请的size比较大，top_chunk也不够分配了，这时候就会调用sysmalloc函数直接从系统中进行分割。
if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE))
{
//......
}
/* When we are using atomic ops to free fast chunks we can get
here for all block sizes. */
else if (have_fastchunks (av))
{
//......
}
/*
Otherwise, relay to handle system-dependent cases
*/
else
{
void *p = sysmalloc (nb, av);
if (p != NULL)
alloc_perturb (p, bytes);
return p;
}
以上便是所有malloc函数申请背后的逻辑分析了。!
发表于 2024-12-11 15:45
