malloc 函数分析 glibc2.23

malloc 函数详解

本篇主要是参考了glibc 2.23的源码

首先我们来看看malloc函数的执行流程。

strong_alias (__libc_malloc, __malloc)
strong_alias (__libc_malloc, malloc)


定义了malloc的是__libc_malloc的别名，__malloc也是__libc_malloc的别名。也就是说我们调用的malloc函数，实际上调用的是__libc_malloc函数。

void *__libc_malloc(size_t bytes)
{
.......
arena_get(ar_ptr, bytes);
victim = _int_malloc(ar_ptr, bytes);
.......
}


__libc_malloc函数又调用了_int_malloc函数，实际上真正分配内存的函数是_int_malloc函数。好了现在我们大致了解了malloc的流程。我们来细致的分析一波。

首先当然是分析__libc_malloc函数喽。

void *__libc_malloc(size_t bytes)//bytes：用户申请分配的空间
{ mstate ar_ptr;
void *victim; /*
# define atomic_forced_read(x)
({ __typeof (x) __x; __asm ("" : "=r" (__x) : "0" (x)); __x; })
__typeof是原始函数的返回类型，后面是一段汇编代码，”0”是零，即%0，引用时不可以加 %，
只能input引用output，这里就是原子读，将__malloc_hook的地址放入任意寄存器(r)再取出
__malloc_hook一开始初始化为malloc_hook_ini，__libc_malloc接下来就是调用
malloc_hook_ini进行初始化。分配完了回调__libc_malloc函数进行分配内存
static void * malloc_hook_ini (size_t sz, const void *caller)
{
__malloc_hook = NULL;
ptmalloc_init ();//初始化的主要函数
return __libc_malloc (sz);
}
*/ //把全局变量__malloc_hook赋给了hook，如果hook不为空，则执行hook。
void *(*hook)(size_t, const void *) = atomic_forced_read(__malloc_hook);
if (__builtin_expect(hook != NULL, 0))
return (*hook)(bytes, RETURN_ADDRESS(0)); //如果我们没有自定义堆分配函数，默认ptmalloc来完成
//获取当前的arena,如果是主线程则获得的是main_arena
arena_get(ar_ptr, bytes); //调用_int_malloc，真正实现内存分配的函数
victim = _int_malloc(ar_ptr, bytes); //如果_int_malloc 分配失败，并且我们之前能够找到一个可用arena，可以用另一个arena重试。
if (!victim && ar_ptr != NULL) {
LIBC_PROBE(memory_malloc_retry, 1, bytes);
ar_ptr = arena_get_retry(ar_ptr, bytes);
victim = _int_malloc(ar_ptr, bytes);
}//释放mutex引用的互斥锁对象，因为ptmalloc支持多线程
if (ar_ptr != NULL)
(void) mutex_unlock(&ar_ptr->mutex);/*
#define arena_for_chunk(ptr) \
(chunk_non_main_arena (ptr) ? heap_for_ptr (ptr)->ar_ptr : &main_arena) 过以下检测需要满足的要求，只需满足一条即可
1. victim 为 0
2. IS_MMAPPED 为 1
3. NON_MAIN_ARENA 为 0
*/
assert(!victim || chunk_is_mmapped(mem2chunk(victim)) || ar_ptr == arena_for_chunk(mem2chunk(victim))); return victim;
}


上面一起看的不清楚，没关系，我们接下来逐条分块分析

__libc_malloc函数执行流程:

1. 把全局变量__malloc_hook赋给了hook，然后对hook是否为NULL进行判断，如果不为空，则执行hook,如果为空，则跳到下一步。(一般我们劫持__malloc_hook就是在这里执行的)

   /*
# define atomic_forced_read(x)
({ __typeof (x) __x; __asm ("" : "=r" (__x) : "0" (x)); __x; }) static void * malloc_hook_ini (size_t sz, const void *caller)
{
__malloc_hook = NULL;
ptmalloc_init ();//初始化的主要函数
return __libc_malloc (sz);
}
*///将全局变量__malloc_hook赋给了局部变量hook，第一次调用malloc时__malloc_hook的值为malloc_hook_ini，之后我们执行hook函数，也就是malloc_hook_ini
void *(*hook)(size_t, const void *) = atomic_forced_read(__malloc_hook);
if (__builtin_expect(hook != NULL, 0))
return (*hook)(bytes, RETURN_ADDRESS(0));


2. 获取arena，然后调用_int_malloc分配内存

   //获取当前的arena,如果是主线程则获得的是main_arena
arena_get(ar_ptr, bytes);//调用_int_malloc，真正实现申请内存的函数
victim = _int_malloc(ar_ptr, bytes);


3. 第二步分配失败，尝试其他的arena,使用_int_malloc分配内存

   //如果第2步中_int_malloc分配失败，且能够找到一个可用arena的情况下，才可以用另一个arena重试。
if (!victim && ar_ptr != NULL) {
LIBC_PROBE(memory_malloc_retry, 1, bytes);
ar_ptr = arena_get_retry(ar_ptr, bytes);
victim = _int_malloc(ar_ptr, bytes);
}


4. 释放互斥锁，检查分配到的内存，返回分配得到的chunk

   /*
#define chunk_is_mmapped(p) ((p)->size & IS_MMAPPED)
#define arena_for_chunk(ptr) \
(chunk_non_main_arena (ptr) ? heap_for_ptr (ptr)->ar_ptr : &main_arena)
*///释放mutex引用的互斥锁对象，因为ptmalloc支持多线程
if (ar_ptr != NULL)
(void) mutex_unlock(&ar_ptr->mutex);/*
#define arena_for_chunk(ptr) \
(chunk_non_main_arena (ptr) ? heap_for_ptr (ptr)->ar_ptr : &main_arena) 过以下检测需要满足的要求，只需满足一条即可
1. victim 为 0
2. IS_MMAPPED 为 1
3. NON_MAIN_ARENA 为 0
*/
assert(!victim || chunk_is_mmapped(mem2chunk(victim)) || ar_ptr == arena_for_chunk(mem2chunk(victim)));//返回得到的chunk
return victim;


我们再来看看_int_malloc函数

static void * _int_malloc(mstate av, size_t bytes)
{
//变量声明
{ *** } checked_request2size(bytes, nb); //如果需要分配的内存大小nb落在fastbin的范围内
if ((unsigned long) (nb) <= (unsigned long) (get_max_fast())) {
......
} //如果fastbin中没有找到合适的chunk，且要申请的大小在smallbin的范围
//#define in_smallbin_range(sz) ((unsigned long) (sz) < 64*(2*size_t))
if (in_smallbin_range(nb)) {
......
}
else{ //如果不在small bin 的范围，也就是说在large bin 的范围
idx = largebin_index(nb);//获取对应大小largebin的索引 if (have_fastchunks(av))
malloc_consolidate(av);
} /*
下面的源代码实现从 last remainder chunk，large bins 和 top chunk 中分配所需的 chunk，
这里包含了多个多层循环，在这些循环中，主要工作是分配前两步都未分配成功的 small bin chunk，
large bin chunk 和 large chunk。最外层的循环用于重新尝试分配 small bin chunk，因
为如果在前一步分配 small bin chunk 不成功，并没有调用 malloc_consolidate()函数合并
fast bins 中的 chunk，将空闲 chunk 加入 unsorted bin 中，如果第一尝试从
last remainder chunk，top chunk 中分配 small bin chunk 都失败以后，如果 fast bins
中存在空闲 chunk，会调用malloc_consolidate()函数，那么在 usorted bin 中就可能存在合适
的 small bin chunk 供分配，所以需要再次尝试。
*/ for (;;) {
/*
如果unsorted bins不为空，遍历unsorted bin中的每个chunk,没有匹配成功，
那么将该chunk放入对应的bin中
*/
while ((victim = unsorted_chunks(av)->bk) != unsorted_chunks(av)) {
.....
} //如果unsorted bin中也找不到合适的chunk，且在large bin的范围，继续在largebin中找
if (!in_smallbin_range(nb)) {
..........
} /*
如果通过上面的方式从最合适的 small bin 或 large bin 中都没有分配到需要的 chunk，则
查看比当前 bin 的 index 大的 small bin 或 large bin 是否有空闲 chunk 可利用来分
配所需的 chunk。
*/
{ ...... } //如果以上都无法满足我们要申请的chunk的要求，最后使用top_chunk //如果top chunk 满足我们要申请的chunk大小要求（top chunk 的size > 我们要申请的chunk + 最小chunk的size ）
if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE)) {
........
} //如果top chunk 空间不够，且fastbin中是否有空闲chunk
//则触发malloc_consolidate函数合并fastbin中能合并chunk，然后加入到unsorted bin 中
//接着返回for循环开始,从unsorted bin 中继续查找
else if (have_fastchunks(av)) {
*******
}
//如果top chunk 空间不够，且fastbin中没有空闲chunk，就通过sysmalloc从操作系统分配内存。
else
{
..............
}
}
}


我们总结一下 _int_malloc 响应用户内存分配要求的具体步骤：

1. 将用户的请求大小转换为实际需要分配的 chunk 空间大小。

2. 判断所需分配 chunk 的大小是否满足 chunk_size <= max_fast (max_fast 默认为 64B)，

   如果是的话，尝试在 fast bins 中取一个所需大小的 chunk 分配给用户。如果可以找到，则分

   配结束，否则跳到下一步。

3. 判断所需大小是否处在 small bins 中，如果chunk 大小处在 small bins 中，转到下一步，否则跳到第5步。

4. 根据所需分配的 chunk 的大小，找到具体所在的某个 small bin，从该 bin 的尾部摘取一个恰好满足大小的 chunk，若成功，则分配结束，否则，转到第6步。

5. chunk 大小不处在 small bins 中，遍历 fast bins 中的 chunk，将相邻的 chunk 进行合并， 并链接到 unsorted bin 中。转到下一步。

6. 到了这一步，说明需要分配的是一块大的内存，或者 fastbin和small bins 中找不到合适的 chunk。于是遍历 unsorted bin 中的 chunk，如果 unsorted bin 只 有一个 chunk，并且这个 chunk 在上次分配时被分割过，并且所需分配的 chunk 大小属于 small bins，并且 chunk 的大小大于等于需要分配的大小，这种情况下就直 接将该 chunk 进行切割，分配结束，或者,如果size刚好则直接返回，否则将根据 chunk 的空间大小将其放入 small bins 或是 large bins 中，遍历完成后，转入下一步。

7. 到了这一步，说明需要分配的是一块大的内存，或者 fastbin，small bins 和 unsorted bin 中都找不到合适的 chunk。如果需要分配的是一块大的内存，则跳到下一步，否则跳到第9步

8. 从 large bins 中按照“smallest-first，best-fit”原则，找一个合适的 chunk，从 中划分一块所需大小的 chunk，并将剩下的部分放入 unsorted bin中 。若操作成功，则 分配结束，否则跳到下一步。

9. 如果通过上面的方式从最合适的fastbin,small bin 或 large bin 中都没有分配到需要的 chunk，则 查看比当前 最合适bin 的 index 大的 small bin 或 large bin 是否有空闲 chunk 可利用，来分割得到所需的 chunk，并将剩下的部分放入 unsorted bin中。若操作成功，则 分配结束，否则跳到下一步。

10. 如果以上都无法满足我们要申请的chunk的要求，那么就需要操作 top chunk 来 进行分配了。判断 top chunk 大小是否满足所需 chunk 的大小，如果是，则从 top chunk 中分出一块来。否则转到下一步。

11. 到了这一步，说明 top chunk 也不能满足分配要求。如果fastbin中有空闲chunk则触发malloc_consolidate函数合并fastbin中能合并chunk，然后加入到unsorted bin中，如果是与top_chunk相邻的chunk则直接与top_chunk合并。若操作成功，则 跳转到 6 ，否则转到下一步

12. 到了这一步，说明，top chunk 也不能满足分配要求，且fastbin中也没有空闲chunk。通过sysmalloc从操作系统分配内存。

_int_malloc函数执行流程:

1. 用户输入的size转换为实际要申请的size,不足最小chunk的返回最小chunk的大小

   /*
SIZE_SZ 在64位上是8，在32位是4
#define MALLOC_ALIGNMENT (2 *SIZE_SZ)
#define MALLOC_ALIGN_MASK (MALLOC_ALIGNMENT - 1) #最小的chunk(MIN_CHUNK_SIZE)在32位上为0x10,64位为0x20
#define MIN_CHUNK_SIZE (offsetof(struct malloc_chunk, fd_nextsize)) #MINSIZE在32位上为0x10,64位为0x20
#define MINSIZE \
(unsigned long)(((MIN_CHUNK_SIZE+MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)) //把用户输入的size转换为实际要申请的size,不足最小chunk的返回最小chunk的大小
#define request2size(req) \
(((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE) ? MINSIZE : ((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK) //检查请求是否太大，checked_request2size 陷阱(返回0)
#define REQUEST_OUT_OF_RANGE(req)
((unsigned long) (req) >= (unsigned long) (INTERNAL_SIZE_T) (-2 * MINSIZE)) #define checked_request2size(req, sz)
if (REQUEST_OUT_OF_RANGE (req)) {
__set_errno (ENOMEM);
return 0;
}
(sz) = request2size (req);
*/
/*
checked_request2size()函数将需要分配的内存大小 bytes 转换为需要分配的 chunk 大小 nb。
Ptmalloc 内部分配都是以 chunk 为单位，根据 chunk 的大小，决定如何获得满足条件的 chunk。
*/
checked_request2size(bytes, nb);


2. 获取arena,如果是主线程这返回main_arena

   //传入的参数av是在上面__libc_malloc中调用arena_get获得的分配去指针，如果为null，就表示没有分配区可用，这时候就直接调用sysmalloc通过mmap获取chunk。
if (__glibc_unlikely(av == NULL)) {
void *p = sysmalloc(nb, av);
if (p != NULL)
alloc_perturb(p, bytes);//将p的mem部分全部设置为byte ,默认什么也不做
return p;
}


3. 如果我们申请的内存大小 小于global_max_fast，我们尝试在fastbin 中匹配相应的chunk，如果可以找到,则分配结束。否则转到下一步。

   /*
从 fast bins 中分配一个 chunk 相当简单，首先根 据所需 chunk 的大小获得该 chunk 所属 fast bin 的 index，根据该 index 获得所需 fast bin 的空 闲 chunk 链表的头指针，然后将头指针的下一个 chunk 作为空闲 chunk 链表的头部。为了加 快从 fast bins 中分配 chunk，处于 fast bins 中 chunk 的状态仍然保持为 inuse 状态，避免被 相邻的空闲 chunk 合并，从 fast bins 中分配 chunk，只需取出第一个 chunk，并调用 chunk2mem() 函数返回用户所需的内存块。
*///get_max_fast返回fastbin可以存储内存的最大值，它在ptmalloc的初始化函数malloc_init_state中定义。
//如果需要分配的内存大小nb落在fastbin的范围内,我么尝试从 fast bins 中 分配 chunk
if ((unsigned long) (nb) <= (unsigned long) (get_max_fast())) {
/*
#define fastbin_index(sz)
((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)
减2是根据fastbin存储的内存最小值计算的，32位为4，64位为8，假设SIZE_SZ=8，因此改写后
idx = (nb>>4)-2
*/
idx = fastbin_index(nb);//获得chunk大小nb对应的fastbin索引。
//获得索引idx后，就通过fastbin取出空闲chunk链表指针
//#define fastbin(ar_ptr, idx) ((ar_ptr)->fastbinsY[idx])
mfastbinptr *fb = &fastbin(av, idx);//通过fastbin取出空闲chunk链表头指针
mchunkptr pp = *fb;//获取对应大小的fatbin的链表中的第一个空闲的chunk
do {
victim = pp;
if (victim == NULL)
break;
} while ((pp = catomic_compare_and_exchange_val_acq(fb, victim->fd, victim)) != victim);
//catomic_compare_and_exchange_val_rel 功能是 如果*fb等于victim，则将*fb存储为victim->fd，返回victim；
//其作用是从刚刚得到的空闲chunk链表指针中取出第一个空闲的chunk(victim)，并将链表头设置为该空闲chunk的下一个chunk(victim->fd) if (victim != 0) {
//由取出的chunk的size计算出来的idx要等于bin的idx
//就是检查拿到的chunk的size是否符合该fastbin的大小（这也是fast bin 的唯一检查）
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;
}
//# define check_remalloced_chunk(A, P, N)
check_remalloced_chunk(av, victim, nb); //什么也没实现
void *p = chunk2mem(victim); //把chunk的指针转换成mem的指针 /*
static void alloc_perturb (char *p, size_t n)
{
if (__glibc_unlikely (perturb_byte))
memset (p, perturb_byte ^ 0xff, n);
}
*/
alloc_perturb(p, bytes);//将p的mem部分全部设置为perturb_byte ,默认什么也不做
return p;
}
}

4. 判断所需大小是否处在 small bins 中,即判断 chunk_size < 64*(2*size_t) 是否成立。根据所需分配的 chunk 的大小,找到具体所在的某个 small bin,从该 bin 的尾部摘取一个恰好满足大小的 chunk。若成功,则分配结束。否则转到下一步。

   /*
如果分配的 chunk 属于 small bin，首先查找 chunk 所对应 small bins 数组的 index，然后 根据 index 获得某个 small bin 的空闲 chunk 双向循环链表表头，然后将最后一个 chunk 赋值 给 victim，如果 victim 与表头相同，表示该链表为空，不能从 small bin 的空闲 chunk 链表中 分配，这里不处理，等后面的步骤来处理。如果 victim 与表头不同，有两种情况，如果 victim 为 0，表示 small bin 还没有初始化为双向循环链表，调用 malloc_consolidate()函数将 fast bins 中的 chunk 合并，初始化small bin。否则，将 victim 从 small bin 的双向循环链表中取出，设置 victim chunk 的 inuse 标志，该标志处于 victim chunk 的物理相邻下一个 chunk 的 size 字段的第一个 bit。从 small bin 中取出一个 chunk 也可以用 unlink()宏函数，只是这里没有使用。接着判断当前分配区是否为非主分配区，如果是，将 victim chunk 的 size 字段中的表示 非主分配区的标志 bit 清零，最后调用 chunk2mem()函数获得 chunk 的实际可用的内存指针， 将该内存指针返回给应用层。到此从 small bins 中分配 chunk 的工作完成了，但我们看到， 当对应的 small bin 中没有空闲 chunk，或是对应的 small bin 还没有初始化完成，并没有获取 到 chunk，这两种情况都需要后面的步骤来处理。
*/if (in_smallbin_range(nb))
{
/*
#define smallbin_index(sz) (
(SMALLBIN_WIDTH == 16 ? (((unsigned) (sz)) >> 4) : (((unsigned) (sz)) >> 3))
)
如果是64位,size>>4就是smallbin_index,32位则是size>>3
*/
idx = smallbin_index(nb); /*
#define bin_at(m, i) (mbinptr) (((char *) &((m)->bins[((i) - 1) * 2])) - 0x10)
*/
//获得索引idx后，就通过idx获取对应的small bin链表表头指针
bin = bin_at(av, idx); //从bin的的尾部取出一个chunk作为victim，如果 victim 与表头相同，表示该链表为空
//这里就是检查bin是否为空的
if ((victim = last(bin)) != bin) {
//victim为0表示smallbin还未初始化
if (victim == 0) /* initialization check */
malloc_consolidate(av); //调用malloc_consolidate进行初始化操作
else {
bck = victim->bk;//获得vitcm的后一个chunk //检查victim的上一个chunk的fd是否等于victim
//这里也是small bin 的唯一安全检查
if (__glibc_unlikely(bck->fd != victim)) {
errstr = "malloc(): smallbin double linked list corrupted";
goto errout;
} /*
#define set_inuse_bit_at_offset(p, s) \
(((mchunkptr) (((char *) (p)) + (s)))->size |= PREV_INUSE)
*/
//设置victim物理相邻的下一个chunk的prev_inuse位
set_inuse_bit_at_offset(victim, nb);
bin->bk = bck;
bck->fd = bin; if (av != &main_arena)
victim->size |= NON_MAIN_ARENA; //如果不是主线程则设置NON_MAIN_ARENA位 check_malloced_chunk(av, victim, nb);//默认不做任何操作
void *p = chunk2mem(victim);//将chunk指针转化为mem指针
alloc_perturb(p, bytes);//将p的mem部分全部设置为perturb_byte ,默认什么也不做
return p;
}
}
}


5. 如果我们申请的chunk的大小不在small bin的范围，也就是说我们申请的chunk的大小在large bin的范围,如果fastbin中存在chunk，我们在这一步会遍历fastbin，可以合并的块合并，然后加入到unsorted bin中,如果与topchunk相邻则直接合并到top chunk（注意这里是把fastbin中的所有块清空）

   /*
所需 chunk 不属于 small bins，那么就一定属于 large bins，首先根据 chunk 的大小获得 对应的 large bin 的 index，接着判断当前分配区的 fast bins 中是否包含 chunk，如果存在，调用 malloc_consolidate()函数合并 fast bins 中的 chunk，并将这些空闲 chunk 加入 unsorted bin 中。
*/else{
idx = largebin_index(nb);//获取对应大小largebin的索引
/*
#define FASTCHUNKS_BIT (1U)
#define have_fastchunks(M) (((M)->flags & FASTCHUNKS_BIT) == 0) 如果申请的是large bin 范围的chunk，那么会先把fastbin中能合并的chunk进行合并，
然后加入到unsorted bin中,如果与topchunk相邻则直接合并到top chunk
（注意这里是把fastbin中的所有块清空）
*/ if (have_fastchunks(av))
malloc_consolidate(av);
}


6. 接着我们遍历unsorted bin,寻找合适的chunk，如果不合适，则加入small bins或者large bins。当遍历到最后一个chunk时，即之前没有大小正好合适的chunk，如果最后一个chunk的大小大于（请求的size+最小chunk的size），则分割它，返回我们要的chunk,分割剩余的chunk还留在unsorted bin中。

   //#define unsorted_chunks(M) (bin_at (M, 1))
//如果unsorted bins不为空，从尾到头遍历unsorted bin中的每个chunk
while ((victim = unsorted_chunks(av)->bk) != unsorted_chunks(av))
{
bck = victim->bk;//取出unsorted的尾部的chunk
/*
检查当前遍历的 chunk 是否合法，chunk 的大小不能小于等于 2 * SIZE_SZ，
也不能超过 该分配区总的内存分配量。然后获取 chunk 的大小并赋值给 size。
这里的检查似乎有点小问 题，直接使用了 victim->size，但 victim->size
中包含了相关的标志位信息，使用 chunksize(victim) 才比较合理，但在
unsorted bin 中的空闲 chunk 的所有标志位都清零了，所以这里直接
victim->size 没有问题。
*/
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);//获取victim的size/*
如果要申请的大小在smallbin范围 且 unsorted chunks 只有一个chunk，且
victim是last_remainder 且 victim的size大于请求的chunk的大小nb加上
(MINSIZE)最小chunk的size,那么就切割remainder,然后返回victim。 last_remainder 是一个 chunk 指针，分配区上次分配 small chunk 时，
从一个 chunk 中分 裂出一个 small chunk 返回给用户，分裂后的剩余部分
形成一个 chunk，last_remainder 就是 指向的这个 chunk。
*/
if (in_smallbin_range(nb) &&
bck == unsorted_chunks(av) &&
victim == av->last_remainder &&
(unsigned long) (size) > (unsigned long) (nb + MINSIZE)) { //分割remainder
remainder_size = size - nb;//计算分割后剩下的size
remainder = chunk_at_offset(victim, nb);//获取remainder的地址
//把remainder加入unsorted bin中
unsorted_chunks(av)->bk = unsorted_chunks(av)->fd = remainder;
av->last_remainder = remainder; // 设置last_remainder为remainder
remainder->bk = remainder->fd = unsorted_chunks(av);
//如果是remainder在large bin的范围，则把fd_nextsize,fd_nextsize清零
if (!in_smallbin_range(remainder_size)) {
remainder->fd_nextsize = NULL;
remainder->fd_nextsize = NULL;
}
//设置victim的size
set_head(victim, nb | PREV_INUSE |
(av != &main_arena ? NON_MAIN_ARENA : 0));
//设置remainder的size
set_head(remainder, remainder_size | PREV_INUSE);
//设置remainder的物理相邻的下一个chunk的prev_size
set_foot(remainder, remainder_size); check_malloced_chunk(av, victim, nb);//默认不做任何操作
void *p = chunk2mem(victim);//将chunk指针转化为mem指针
alloc_perturb(p, bytes);//将p的mem部分全部设置为bytes ,默认什么也不做
return p;
} //把victim从unsorted bin 中移除
unsorted_chunks(av)->bk = bck;
bck->fd = unsorted_chunks(av); //如果 victim 的size 与申请的size相等，那么就返回其。
if (size == nb) {
//设置victim物理相邻的下一个chunk的prev_inuse位
set_inuse_bit_at_offset(victim, size);
//如果av不是main_arena 也就是说如果不是主进程,设置NON_MAIN_ARENA位
if (av != &main_arena)
victim->size |= NON_MAIN_ARENA; check_malloced_chunk(av, victim, nb); // 默认不做任何操作
void *p = chunk2mem(victim);//把chunk转换为mem指针
alloc_perturb(p, bytes);//将p的mem部分全部设置为bytes ,默认什么也不做
return p;
} //如果上一步取出的chunk没有匹配成功，那么将该chunk放入对应的bin中
//如果在smallbin的范围,则放到对应多small bin中
if (in_smallbin_range(size))
{
victim_index = smallbin_index(size);//获取size对应的smallbin的index
bck = bin_at(av, victim_index);//bck指向size对应的smallbin的链表头
//fwd指向size对应的smallbin的链表中的新加入的chunk(small bin使用头插法)
fwd = bck->fd;
}
else//如果不再smallbin的范围，也就是说在large bin 的范围
{
victim_index = largebin_index(size);//获取size对应的large bin的index
bck = bin_at(av, victim_index);//bck指向size对应的large bin的链表头
fwd = bck->fd;//fwd指向size对应的large bin的链表中的新加入的chunk //如果large bin 非空，在largbin进行按顺序插入
if (fwd != bck) {
/* Or with inuse bit to speed comparisons */
size |= PREV_INUSE;
assert((bck->bk->size & NON_MAIN_ARENA) == 0);
/*
large bin中的chunk是按从大到小排列的，如果size < large bin
的最后一个chunk，说明size是这个large bin中的最小的，我们把它
加入到此large bin尾部。
*/
if ((unsigned long) (size) < (unsigned long) (bck->bk->size)) { fwd = bck;
bck = bck->bk; /*
large bin 中size最小的chunk的fd_nextsize会指向size最大的
那个chunk，也就是首部的chunk。同样，large bin 中size最大的
chunk的bk_nextsize会指向size最小的那个chunk。
victim的bk_nextsize指向large bin原来最小的chunk，它的
bk_nextsize指向最大的那个chunk。那么原来的最小的就成了第二小的了。
把它fd_nextsize和bk_nextsize都修正。
*/
victim->fd_nextsize = fwd->fd;
victim->bk_nextsize = fwd->fd->bk_nextsize;
//最大size的chunk的bk_nextsize，和原来最小chunk的bk_nextsize都指向victim
fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim;
}
else //如果victim不是large bin 中最小的chunk
{
//检查NON_MAIN_ARENA位是否为0
assert((fwd->size & NON_MAIN_ARENA) == 0);
//从大到小（从头到尾）找到合适的位置
while ((unsigned long) size < fwd->size) {
fwd = fwd->fd_nextsize;
assert((fwd->size & NON_MAIN_ARENA) == 0);
}
//如果size刚好相等，就直接加入到其后面省的改fd_nextsize和bk_nextsize了
if ((unsigned long) size == (unsigned long) fwd->size)
fwd = fwd->fd;
else
{
//size不相等，即size>fwd->size，把victim加入到纵向链表中
victim->fd_nextsize = fwd;
victim->bk_nextsize = fwd->bk_nextsize;
fwd->bk_nextsize = victim;
victim->bk_nextsize->fd_nextsize = victim;
}
bck = fwd->bk;
}
}
else //如果large bin 为空，将victim加入到纵向列表
victim->fd_nextsize = victim->bk_nextsize = victim;
} //#define mark_bin(m, i) ((m)->binmap[idx2block (i)] |= idx2bit (i))
mark_bin(av, victim_index); //把victim加入到的bin的表示为非空
//把victim加入到large bin的链表中
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;
}


7. 如果unsorted bin中也找不到合适的chunk，且在large bin的范围，继续在largebin中找

   //如果unsorted bin中也找不到合适的chunk，且在large bin的范围，继续在largebin中找
if (!in_smallbin_range(nb)) {
bin = bin_at(av, idx); //如果对应的 bin 不为空 且 其中最大的chunk也很比我们想要的nb大
if ((victim = first(bin)) != bin &&
(unsigned long) (victim->size) >= (unsigned long) (nb))
{
// 反向遍历nextsize链表（从小到大），找到第一个比size大的chunk
victim = victim->bk_nextsize;
while (((unsigned long) (size = chunksize(victim)) <
(unsigned long) (nb)))
victim = victim->bk_nextsize; /*
如果取出的chunk不是bin的最后一个chunk，同时该chunk有大小相同的chunk连接在一起
它就会取它前面的那个chunk即 chunk->fd ,因为大小相同的chunk只有一个会被串在
nextsize链上这可以避免额外的bk_nextsize和fd_nextsize的赋值
*/
if (victim != last(bin) && victim->size == victim->fd->size)
victim = victim->fd; remainder_size = size - nb;//计算切割后的大小
unlink(av, victim, bck, fwd); //通过unlink将chunk从链表移除 if (remainder_size < MINSIZE) {
//如果切割后的大小不足以作为一个chunk，那么就会将其标志位设为inuse
//如果不是main_arena,同时设置NO_main_arena标志位
set_inuse_bit_at_offset(victim, size);
if (av != &main_arena)
victim->size |= NON_MAIN_ARENA;
}
else {
//如果剩余的大小可以作为一个chunk
//获得剩余部分的地址，放入unsorted bin中
remainder = chunk_at_offset(victim, nb);
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;
//如果剩余部分的大小在largin bin的范围，则清空nextsize字段
if (!in_smallbin_range(remainder_size)) {
remainder->fd_nextsize = NULL;
remainder->bk_nextsize = NULL;
} //设置victim的size
set_head(victim, nb | PREV_INUSE |
(av != &main_arena ? NON_MAIN_ARENA : 0));
//设置remainder的size
set_head(remainder, remainder_size | PREV_INUSE);
//设置remainder的物理相邻的下一个chunk的prev_size
set_foot(remainder, remainder_size); }
check_malloced_chunk(av, victim, nb);//默认不做任何操作
void *p = chunk2mem(victim);//将chunk指针转化为mem指针
alloc_perturb(p, bytes);//将p的mem部分全部设置为bytes ,默认什么也不做
return p;
}
}


8. 如果通过上面的方式从最合适的 small bin 或 large bin 中都没有分配到需要的 chunk，则 查看比当前 bin 的 index 大的 small bin 或 large bin 是否有空闲 chunk 可利用来分配所需的 chunk。

   /*
获取下一个相邻 bin 的空闲 chunk 链表，并获取该 bin 对应 binmap 中的 bit 位的值。binmap 字段是一个 int 数组，ptmalloc 用一个 bit 来标识该 bit 对应的 bin 中是否包含空闲 chunk。Binmap 按 block 管理，每个 block 为一个 int，共 32 个 bit，可以表示 32 个 bin 中是否有空闲 chunk 存在。使用 binmap 可以加快查找 bin 是否包含空闲 chunk。这里只查询比所需 chunk 大的 bin 中是否有空闲 chunk 可用。
*/++idx;
bin = bin_at(av, idx);//获取当前bin的下一个bin
block = idx2block(idx);
map = av->binmap[block];//获取block
bit = idx2bit(idx);//获取block中对应的bit/*
Idx2bit()宏将 idx 指定的位设置为 1，其它位清零，map 表示一个 block(unsigned int) 值，如果bit 大于 map，意味着比bit对应的bin的size大的bin中无空闲chunk，如果 map 为 0，该 block 所对应的所有 bins 中都没有空闲 chunk， 于是遍历 binmap 的下一个 block，直到找到一个不为 0 的 block 或者遍历完所有的 block。 退出循环遍历后，设置 bin 指向 block 的第一个 bit 对应的 bin，并将 bit 置为 1，表示该 block 中 bit 1 对应的 bin，这个 bin 中如果有空闲 chunk，该 chunk 的大小一定满足要求。
*/for (;;)
{
/*
如果bit 大于 map，意味着比该bit对应的bin的size大的bin中无空闲chunk，如果 map 为
0，该 block 所对应的所有 bins 中都没有空闲 chunk 。接着在下一个block中寻找
*/
if (bit > map || bit == 0)
{
do {
//如果block超过了范围，说明比所需chunk大的bin中没有chunk，直接使用top_chunk
if (++block >= BINMAPSIZE) /* out of bins */
goto use_top;
//如果block为0,这表明block中的所有bit所对应的bin没有空闲chunk
} while ((map = av->binmap[block]) == 0); bin = bin_at(av, (block << BINMAPSHIFT));
bit = 1;
}/*
在一个block遍历对应的 bin，直到找到一个 bit 不为 0 退出遍历，则该 bit 对于的 bin 中有空闲 chunk 存在。
*/
while ((bit & map) == 0) {
bin = next_bin(bin);
bit <<= 1;
assert(bit != 0);
} //获取bin尾部的chunk
victim = last(bin); /*
如果 victim 与 bin 链表头指针相同，表示该 bin 中没有空闲 chunk，binmap 中的相应位
设置不准确，将 binmap 的相应 bit 位清零，获取当前 bin 下一个 bin，将 bit 移到下一个
bit 位，即乘以 2。
*/
if (victim == bin) {
av->binmap[block] = map &= ~bit; /* Write through */
bin = next_bin(bin);
bit <<= 1;
}
else
{
/*
当前 bin 中的最后一个 chunk 满足要求，获取该 chunk 的大小，计算切分出所需 chunk
后剩余部分的大小，然后将 victim 从 bin 的链表中取出。
*/
size = chunksize(victim); assert((unsigned long) (size) >= (unsigned long) (nb)); remainder_size = size - nb;//计算分割后的大小 unlink(av, victim, bck, fwd);//从bin中取出victim /*
如果剩余部分的大小小于 MINSIZE，将整个 chunk 分配给应用层，设置 victim 的状态为
inuse，如果当前分配区为非主分配区，设置 victim 的非主分配区标志位。
*/
if (remainder_size < MINSIZE) {
set_inuse_bit_at_offset(victim, size);
if (av != &main_arena)
victim->size |= NON_MAIN_ARENA;
}
else {
//如果剩余的大小可以作为一个chunk
//获得剩余部分的地址，放入unsorted bin中
remainder = chunk_at_offset(victim, nb);
bck = unsorted_chunks(av);
fwd = bck->fd;
//这里检查unsorted bin 中的链表头部是否合法
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; //设置last_remainder为刚刚分割剩余的remainder
if (in_smallbin_range(nb))
av->last_remainder = remainder; //如果剩余部分的大小在largin bin的范围，则清空nextsize字段
if (!in_smallbin_range(remainder_size)) {
remainder->fd_nextsize = NULL;
remainder->bk_nextsize = NULL;
} //设置victim的size
set_head(victim, nb | PREV_INUSE |
(av != &main_arena ? NON_MAIN_ARENA : 0));
//设置remainder的size
set_head(remainder, remainder_size | PREV_INUSE);
//设置remainder的物理相邻的下一个chunk的prev_size
set_foot(remainder, remainder_size);
} check_malloced_chunk(av, victim, nb);//默认不做任何操作
void *p = chunk2mem(victim);//将chunk指针转化为mem指针
alloc_perturb(p, bytes);//将p的mem部分全部设置为bytes ,默认什么也不做
return p;
}
}

9. 如果从所有的 bins 中都没有获得所需的 chunk，可能的情况为 bins 中没有空闲 chunk， 或者所需的 chunk 大小很大，下一步将尝试从 top chunk 中分配所需 chunk。

   use_top://如果以上都无法满足我们要申请的chunk的要求，最后使用top_chunk
victim = av->top; // victim 指向top chunk
size = chunksize(victim);//获取top chunk的size
//如果top chunk 满足我们要申请的chunk大小要求（top chunk 的size > 我们要申请的chunk + 最小chunk的size ），那么就分割它。
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;
}//如果top chunk 空间不够，且fastbin中有空闲chunk
//则触发malloc_consolidate函数合并fastbin中能合并chunk，然后加入到unsorted bin中，如果是与top_chunk相邻的chunk则直接与top_chunk合并，
//接着返回for循环开始,从unsorted bin 中继续查找
else if (have_fastchunks(av)) {
malloc_consolidate(av);
/* restore original bin index */
if (in_smallbin_range(nb))
idx = smallbin_index(nb);
else
idx = largebin_index(nb);
}
//如果top chunk 空间不够，且fastbin中没有空闲chunk，就通过sysmalloc从操作系统分配内存。
else {
void *p = sysmalloc(nb, av); //这里也是house of orange利用的地方
if (p != NULL)
alloc_perturb(p, bytes);//将p的mem部分全部设置为bytes ,默认什么也不做
return p;
}


至此，_int_malloc()函数的代码就分析完了，当还有几个关键函数没有分析，将在之后分析。