内存管理：malloc主分配过程_int_malloc
一、概述
前文介绍了malloc初始化，本文来看malloc的具体分配过程，主要通过_int_malloc这个函数，这里面始终贯穿着各种bin和special chunk，这些概念在前文malloc的bin和特殊chunk都已经详细介绍过，本文只专注看代码的主要脉络，_int_malloc这个函数很长，我画了一个流程图：
图1：_int_malloc flow
后面我按照流程图把_int_malloc这个函数分成若干部分，从代码实现的角度逐个来看
二、CAS操作
在malloc的实现中，需要频繁的插入和删除各个bin中的chunk，很多地方用到了CAS操作，因为用的比较多，这里先简单介绍一下
CAS是compare and swap的缩写，它是原子操作的一种，可用于在多线程编程中实现不被打断的数据交换操作，从而避免多线程同时改写某一数据时由于执行顺序不确定性以及中断的不可预知性产生的数据不一致问题，该操作通过将内存中的值与指定数据进行比较，当数值一样时将内存中的数据替换为新的值。
CAS需要有3个操作数：内存地址V，旧的预期值A，即将要更新的目标值B，CAS指令执行时，当且仅当内存地址V的值与预期值A相等时，将内存地址V的值修改为B，否则就什么都不做，整个比较并替换的操作是一个原子操作，下面举一个例子：
#define REMOVE_FB(fb, victim, pp) \ do { \ victim = pp; \ if (victim == NULL) \ break; \ pp = REVEAL_PTR(victim->fd); \ } while ((pp = catomic_compare_and_exchange_val_acq \ (fb, pp, victim)) != victim);上面这段代码是用来从fast bin中删除一个chunk，我们这里只关注catomic_compare_and_exchange_val_acq(fb, pp, victim)这个函数调用，其中fb是表头，pp新的节点，victim是老的节点，需要把老节点删掉，把新节点接上，这个调用就是通过CAS操作保证thread-safe的，以x86平台为例，一直往下追，最底层的实现如下：
#define __arch_c_compare_and_exchange_val_32_acq(mem, newval, oldval) \({ \__typeof(*mem) ret; \__asm __volatile('cmpl $0, %%' SEG_REG ':%P5\n\t' \'je 0f\n\t' \'lock\n' \'0:\tcmpxchgl %2, %1' \: '=a'(ret), '=m'(*mem) \: BR_CONSTRAINT(newval), 'm'(*mem), '0'(oldval), \'i'(offsetof(tcbhead_t, multiple_threads))); \ret; \})
这是一段x86的内联汇编，GCC的内联汇编语法大家可以自行查阅相关资料，这里只关注lock和cmpxchgl这两个指令，lock确保对内存的read/write操作原子执行，cmpxchgl用来比较并交换操作数，所以归根结底，CAS操作还是通过硬件指令的支持才能实现原子操作。
但是CAS操作存在ABA等问题，这里不再细说，大家可以自行查相关资料。
三、从fast bin分配
在_int_malloc的开始，先看申请的内存大小nb是否符合fast bin的限制，符合的话，首先进入fast bin的分配代码：
if (nb <= get_max_fast()) { idx = fastbin_index(nb); mfastbinptr *fb = &fastbin(av, idx); mchunkptr pp; if ((victim = *fb) != NULL) { REMOVE_FB(fb, pp, victim); void *p = chunk2mem(victim); alloc_perturb(p, bytes); return p; }}会根据nb得到fast bin的index，再根据index，得到指向所在bin的head指针fb，如果这个bin非空，则取第一个chunk，使用前面介绍的REMOVE_FB将其从所在bin删除，并将取到的chunk返回
四、从small bin分配
不符合fast bin分配条件的话，会继续看是否符合small bin的分配条件，这部分的代码如下：
if (in_smallbin_range(nb)) {idx = smallbin_index(nb);bin = bin_at(av, idx);if ((victim = last(bin)) != bin) {bck = victim->bk;set_inuse_bit_at_offset(victim, nb);bin->bk = bck;bck->fd = bin;if (av != &main_arena)set_non_main_arena(victim);check_malloced_chunk(av, victim, nb);void *p = chunk2mem(victim);alloc_perturb(p, bytes);return p;}}
这里的处理过程和fast bin类似，也是根据nb定位到所在的bin，所在bin非空的话，就分配成功，返回得到的chunk，并且从所在bin中删除，和fast bin的最大不同之处在于这里操作的是双向链表
五、merge fast bin into unsorted bin
在fast bin和small bin都分配失败之后，会把fast bin中的chunk进行一次整理合并，然后将合并后的chunk放入unsorted bin中，这是通过malloc_consolidate这个函数完成的：
static void malloc_consolidate(mstate av) { // 因为这里会release所有的fast bin，所以先把相应flag disable atomic_store_relaxed (&av->have_fastchunks, false); unsorted_bin = unsorted_chunks(av); maxfb = &fastbin(av, NFASTBINS - 1); fb = &fastbin (av, 0); // 两层循环 // 1. 外层循环遍历所有fast bin // 2. 内层循环遍历bin中所有chunk do { p = atomic_exchange_acq (fb, NULL); if (p != 0) { do { // 内层循环主要做了下面几件事，代码太长，略了 // 1. 如果当前chunk的前一个chunk是free状态，进行合并 // 2. 如果当前chunk的后一个chunk是free状态，进行合并 // 3. 如果合并后的chunk不和top chunk挨着， // 将合并后的chunk插入到unsorted bin中 // 4. 如果合并后的chunk和top chunk挨着， // 重新设置top chunk的起始位置 } while ((p = nextp) != 0); } } while (fb++ != maxfb);}具体的步骤我写在上面代码的注释中了，这样更方便理解
六、尝试从unsorted bin中分配
这部分代码已经进入_int_malloc中最后那个最大的for循环了，这部分的工作在for循环的刚开始，如下所示：
for (;;) {// for循环的第一部分代码int iters = 0;while((victim = unsorted_chunks(av)->bk) != unsorted_chunks(av)) {bck = victim->bk;size = chunksize(victim);mchunkptr next = chunk_at_offset(victim, size);// 符合这四个条件的话，从last remainder chunk分配if (in_smallbin_range(nb)&& bck == unsorted_chunks(av)&& victim == av->last_remainder&& size > (nb + MINSIZE)) {// 。。。return p;}// 。。。// 正好遇到请求大小的chunk，分配成功if (size == nb) {// 。。。return p;}// 当前chunk属于small bin的范围，将其放回small binif (in_smallbin_range(size)) {// 。。。} else { // 当前chunk属于large bin的范围，将其放回large bin// 。。。}// 从unsorted bin中删除当前chunk// 。。。// 判断最大循环次数if (++iters >= 10000)break;}}
七、尝试从large bin中分配
这是_int_malloc中最后那个大for循环的第二部分代码，在从unsorted bin分配失败之后，准备从large bin分配：
for (;;) { // for循环的第二部分代码 // 判断nb的大小，符合条件的话从large bin分配 if (!in_smallbin_range(nb)) { bin = bin_at(av, idx);
// 判断前面得到的bin是否为空 // 不为空的话最大的chunk size是否大于等于请求大小nb victim = first(bin); if (victim != bin && chunksize_nomask(victim) >= nb) { // 1. 用best fit算法找到最合适大小的chunk // 2. 对这个chunk进行split，一部分返回给用户， // 剩余部分赋值给malloc_state中的remainder， // 同时插入到unsorted bin当中 return p; } } // 在请求大小nb所在的bin分配失败，继续从后面的bin来分配， // 在查找后面bin的过程中，会用到binmap来加快查找速度 ++idx; bin = bin_at(av, idx); block = idx2block(idx); map = av->binmap[block]; bit = idx2bit(idx);
for (;;) { // 如果后面没有找到合适的bin，就跳到use_top使用top chunk来分配 // 如果后面找到了合适的bin，那么： // 1. 用best fit算法找到最合适大小的chunk // 2. 对这个chunk进行split，一部分返回给用户， // 剩余部分赋值给malloc_state中的remainder， // 同时插入到unsorted bin当中 }}
八、尝试从top chunk中分配
这是_int_malloc中最后那个大for循环的第三部分代码，在从large bin分配失败之后，准备从top chunk分配：
for (;;) {// for循环的第三部分代码// 前面都分配失败，从top chunk分配use_top:victim = av->top;size = chunksize(victim);if (size >= (nb + MINSIZE)) {// top chunk的大小如果满足要求，分配成功// 剩余的部分成为新的top chunk，同时也会成为remainderremainder_size = size - nb;remainder = chunk_at_offset(victim, nb);av->top = remainder;set_head(victim, ...);set_head(remainder, remainder_size | PREV_INUSE);void *p = chunk2mem(victim);return p;} else if (av->have_fastchunks) {// 如果fast bin flag被设置，// 再重新release fast bin的内容到unsorted bin中，// 并且重新得到请求大小所在bin的indexmalloc_consolidate(av);if (in_smallbin_range(nb))idx = smallbin_index(nb);elseidx = largebin_index(nb);} else {// 如果top chunk也不满足请求大小，// 就使用系统调用增加top chunk，或者再开辟出一块heapvoid *p = sysmalloc(nb, av);return p;}}
九、小结
到现在为止基本把malloc从算法、数据结构、代码各个方面都讲了一遍，其中最难讲的是代码部分，因为文章只能线性的展示代码的内容，但是程序的执行有循环和分支跳转，用文字很难完美的描绘代码的实际执行过程，如果大家需要了解更多的执行细节，可以进一步细致的看源代码的实现。