staticvoid * _int_malloc (mstate av, size_t bytes) { INTERNAL_SIZE_T nb; /* normalized request size */ unsignedint idx; /* associated bin index */ mbinptr bin; /* associated bin */
mchunkptr victim; /* inspected/selected chunk */ INTERNAL_SIZE_T size; /* its size */ int victim_index; /* its bin index */
mchunkptr remainder; /* remainder from a split */ unsignedlong remainder_size; /* its size */
unsignedint block; /* bit map traverser */ unsignedint bit; /* bit map traverser */ unsignedintmap; /* current word of binmap */
mchunkptr fwd; /* misc temp for linking */ mchunkptr bck; /* misc temp for linking */
constchar *errstr = NULL; /* Convert request size to internal form by adding SIZE_SZ bytes overhead plus possibly more to obtain necessary alignment and/or to obtain a size of at least MINSIZE, the smallest allocatable size. Also, checked_request2size traps (returning 0) request sizes that are so large that they wrap around zero when padded and aligned. */
/* If the size qualifies as a fastbin, first check corresponding bin. This code is safe to execute even if av is not yet initialized, so we can try it without checking, which saves some time on this fast path. */
/* If a small request, check regular bin. Since these "smallbins" hold one size each, no searching within bins is necessary. (For a large request, we need to wait until unsorted chunks are processed to find best fit. But for small ones, fits are exact anyway, so we can check now, which is faster.) */
if (in_smallbin_range (nb)) {//判断所需的size是否属于smallbin idx = smallbin_index (nb); bin = bin_at (av, idx); //计算出对应的bin和idx if ((victim = last (bin)) != bin) {//获取 small bin 中的最后一个块（如果存在） if (victim == 0) /* initialization check */ malloc_consolidate (av);//整合fastbin中的chunk 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;//如果在非主 arena 中，设置块的标志 check_malloced_chunk (av, victim, nb);//正常检查堆块 void *p = chunk2mem (victim); alloc_perturb (p, bytes); return p; } } }
分配large bin chunk
如果所需的 chunk 不属于 small bins，首先会执行如下的代码段：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
/* If this is a large request, consolidate fastbins before continuing. While it might look excessive to kill all fastbins before even seeing if there is space available, this avoids fragmentation problems normally associated with fastbins. Also, in practice, programs tend to have runs of either small or large requests, but less often mixtures, so consolidation is not invoked all that often in most programs. And the programs that it is called frequently in otherwise tend to fragment. */
所需 chunk 不属于 small bins，那么就一定属于 large bins，首先根据 chunk 的大小获得对应的 large bin 的 index，接着判断当前分配区的 fast bins 中是否包含 chunk，如果存在，调用 malloc_consolidate()函数合并 fast bins 中的 chunk，并将这些空闲 chunk 加入 unsorted bin中。
下面的源代码实现从 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 供分配，所以需要再次尝试。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
/* Process recently freed or remaindered chunks, taking one only if it is exact fit, or, if this a small request, the chunk is remainder from the most recent non-exact fit. Place other traversed chunks in bins. Note that this step is the only place in any routine where chunks are placed in bins. The outer loop here is needed because we might not realize until near the end of malloc that we should have consolidated, so must do so and retry. This happens at most once, and only when we would otherwise need to expand memory to service a "small" request. */
for (;; )//遍历unsortedbin { int iters = 0; while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
/* If a small request, try to use last remainder if it is the only chunk in unsorted bin. This helps promote locality for runs of consecutive small requests. This is the only exception to best-fit, and applies only when there is no exact fit for a small chunk. */
如果需要分配一个 small bin chunk，在前面的 small bins 中没有匹配到合适的chunk，并且 unsorted bin 中只有一个 chunk，并且这个 chunk 为 last remainder chunk，并且这个 chunk 的大小大于所需 chunk 的大小加上 MINSIZE，在满足这些条件的情况下，可以使用这个chunk 切分出需要的small bin chunk。这是唯一的从unsorted bin 中分配small bin chunk的情况，这种优化利于 cpu 的高速缓存命中（这也表明了smallbin和fastbin中的chunk需要精准匹配）。
如果当前 chunk 属于 large bins，获得当前 chunk 所属 large bin 的 index，并将该 large bin的链表表头赋值给 bck，第一个 chunk 赋值给 fwd，也就是当前的 chunk 会插入到 bck 和 fwd之间，作为 large bin 链表的第一个 chunk
1 2 3 4 5 6 7
/* maintain large bins in sorted order */ if (fwd != bck)//这个就是判断largebin中有没有chunk { /* 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);
如果fwd 不等于 bck ，意味着large bin 中有空闲chunk 存在，由于large bin 中的空闲chunk是按照大小顺序排序的，需要将当前从 unsorted bin 中取出的 chunk 插入到 large bin 中合适的位置。将当前 chunk 的 size 的 inuse 标志 bit 置位，相当于加 1，便于加快 chunk 大小的比较，找到合适的地方插入当前 chunk。这里还做了一次检查，断言在 large bin 双向循环链表中的最后一个 chunk 的 size 字段中的非主分配区的标志 bit 没有置位，因为所有在 large bin中的 chunk 都处于空闲状态，该标志位一定是清零的。
如果当前chunk 比 large bin的最后一个chunk 的大小还小，那么当前 chunk 就插入到largebin 的链表的最后，作为最后一个 chunk。可以看出 large bin 中的 chunk 是按照从大到小的顺序排序的，同时一个 chunk 存在于两个双向循环链表中，一个链表包含了 large bin 中所有的chunk，另一个链表为chunk size 链表，该链表从每个相同大小的chunk 的取出第一个chunk按照大小顺序链接在一起，便于一次跨域多个相同大小的 chunk 遍历下一个不同大小的 chunk，这样可以加快在 large bin 链表中的遍历速度。
if ((unsignedlong) size == (unsignedlong) fwd->size) //判断当前操作的chunk的size是不是等于largebin中最大的size /* Always insert in the second position. */ fwd = fwd->fd;
#define MAX_ITERS 10000 if (++iters >= MAX_ITERS) break; }
/* If a large request, scan through the chunks of current bin in sorted order to find smallest that fits. Use the skip list for this. */
if (!in_smallbin_range (nb)) { bin = bin_at (av, idx);
/* skip scan if empty or largest chunk is too small */ if ((victim = first (bin)) != bin && (unsignedlong) (victim->size) >= (unsignedlong) (nb)) { victim = victim->bk_nextsize; while (((unsignedlong) (size = chunksize (victim)) < (unsignedlong) (nb))) victim = victim->bk_nextsize;
/* Avoid removing the first entry for a size so that the skip list does not have to be rerouted. */ if (victim != last (bin) && victim->size == victim->fd->size) victim = victim->fd;
/* Search for a chunk by scanning bins, starting with next largest bin. This search is strictly by best-fit; i.e., the smallest (with ties going to approximately the least recently used) chunk that fits is selected. The bitmap avoids needing to check that most blocks are nonempty. The particular case of skipping all bins during warm-up phases when no chunks have been returned yet is faster than it might look. */
++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 ((unsignedlong) (size) >= (unsignedlong) (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; }
use_top: /* If large enough, split off the chunk bordering the end of memory (held in av->top). Note that this is in accord with the best-fit search rule. In effect, av->top is treated as larger (and thus less well fitting) than any other available chunk since it can be extended to be as large as necessary (up to system limitations). We require that av->top always exists (i.e., has size >= MINSIZE) after initialization, so if it would otherwise be exhausted by current request, it is replenished. (The main reason for ensuring it exists is that we may need MINSIZE space to put in fenceposts in sysmalloc.) */
/* When we are using atomic ops to free fast chunks we can get here for all block sizes. */ elseif (have_fastchunks (av)) { malloc_consolidate (av); /* restore original bin index */ if (in_smallbin_range (nb)) idx = smallbin_index (nb); else idx = largebin_index (nb); }
