Glibc内存管理--ptmalloc2源代码分析（二十七）
5.7.2.3 分配large bin chunk（一）
/* 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. */ else { idx = largebin_index(nb); if (have_fastchunks(av)) malloc_consolidate(av); }
?所需chunk不属于small bins，那么就一定属于largebins，首先根据chunk的大小获得对应的large bin的index，接着判断当前分配区的fast bins中是否包含chunk，如果存在，调用malloc_consolidate()函数合并fast bins中的chunk，并将这些空闲chunk加入unsorted bin中。
下面的源代码实现从last remainderchunk，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供分配，所以需要再次尝试。
/* 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(;;) { int iters = 0;while ( (victim = unsorted_chunks(av)->bk) != unsorted_chunks(av)) {反向遍历unsorted bin的双向循环链表，遍历结束的条件是循环链表中只剩下一个头结点。 bck = victim->bk; 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)); size = chunksize(victim);?检查当前遍历的chunk是否合法，chunk的大小不能小于等于2 *SIZE_SZ，也不能超过该分配区总的内存分配量。然后获取chunk的大小并赋值给size。这里的检查似乎有点小问题，直接使用了victim->size，但victim->size中包含了相关的标志位信息，使用chunksize(victim)才比较合理，但在unsorted bin中的空闲chunk的所有标志位都清零了，所以这里直接victim->size没有问题。
/* 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. */ if (in_smallbin_range(nb) && bck == unsorted_chunks(av) && victim == av->last_remainder && (unsigned long)(size) > (unsigned long)(nb + MINSIZE)) {?如果需要分配一个small binchunk，在5.7.2.2节中的small bins中没有匹配到合适的chunk，并且unsorted bin中只有一个chunk，并且这个chunk为last remainder chunk，并且这个chunk的大小大于所需chunk的大小加上MINSIZE，在满足这些条件的情况下，可以使用这个chunk切分出需要的small bin chunk。这是唯一的从unsorted bin中分配small bin chunk的情况，这种优化利于cpu的高速缓存命中。
/* split and reattach remainder */ 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); if (!in_smallbin_range(remainder_size)) { remainder->fd_nextsize = NULL; remainder->bk_nextsize = NULL; }从该chunk中切分出所需大小的chunk，计算切分后剩下chunk的大小，将剩下的chunk加入unsortedbin的链表中，并将剩下的chunk作为分配区的last remainder chunk，若剩下的chunk属于large bin chunk，将该chunk的fd_nextsize和bk_nextsize设置为NULL，因为这个chunk仅仅存在于unsorted bin中，并且unsorted bin中有且仅有这一个chunk。
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); if (__builtin_expect (perturb_byte, 0)) alloc_perturb (p, bytes); return p;
?设置分配出的chunk和last remainderchunk的相关信息，如chunk的size，状态标志位，对于last remainder chunk，需要调用set_foot宏，因为只有处于空闲状态的chunk的foot信息（prev_size）才是有效的，处于inuse状态的chunk的foot无效，该foot是返回给应用层的内存块的一部分。设置完成chunk的相关信息，调用chunk2mem()获得chunk中可用的内存指针，返回给应用层，退出。
} /* remove from unsorted list */ unsorted_chunks(av)->bk = bck; bck->fd = unsorted_chunks(av);将双向循环链表中的最后一个chunk移除。 /* Take now instead of binning if exact fit */ 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); if (__builtin_expect (perturb_byte, 0)) alloc_perturb (p, bytes); return p; }?如果当前遍历的chunk与所需的chunk大小一致，将当前chunk返回。首先设置当前chunk处于inuse状态，该标志位处于相邻的下一个chunk的size中，如果当前分配区不是主分配区，设置当前chunk的非主分配区标志位，最后调用chunk2mem()获得chunk中可用的内存指针，返回给应用层，退出。
/* place chunk in bin */ if (in_smallbin_range(size)) { victim_index = smallbin_index(size); bck = bin_at(av, victim_index); fwd = bck->fd;如果当前chunk属于small bins，获得当前chunk所属small bin的index，并将该small bin的链表表头赋值给bck，第一个chunk赋值给fwd，也就是当前的chunk会插入到bck和fwd之间，作为small bin链表的第一个chunk。 } else { victim_index = largebin_index(size); bck = bin_at(av, victim_index); fwd = bck->fd;如果当前chunk属于large bins，获得当前chunk所属large bin的index，并将该large bin的链表表头赋值给bck，第一个chunk赋值给fwd，也就是当前的chunk会插入到bck和fwd之间，作为large bin链表的第一个chunk。 /* maintain large bins in sorted order */ 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);?如果fwd不等于bck，意味着large bin中有空闲chunk存在，由于largebin中的空闲chunk是按照大小顺序排序的，需要将当前从unsorted bin中取出的chunk插入到large bin中合适的位置。将当前chunk的size的inuse标志bit置位，相当于加1，便于加快chunk大小的比较，找到合适的地方插入当前chunk。这里还做了一次检查，断言在large bin双向循环链表中的最后一个chunk的size字段中的非主分配区的标志bit没有置位，因为所有在large bin中的chunk都处于空闲状态，该标志位一定是清零的。
if ((unsigned long)(size) < (unsigned long)(bck->bk->size)) { 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;?如果当前chunk比large bin的最后一个chunk的大小还小，那么当前chunk就插入到large bin的链表的最后，作为最后一个chunk。可以看出largebin中的chunk是按照从大到小的顺序排序的，同时一个chunk存在于两个双向循环链表中，一个链表包含了large bin中所有的chunk，另一个链表为chunk size链表，该链表从每个相同大小的chunk的取出第一个chunk按照大小顺序链接在一起，便于一次跨域多个相同大小的chunk遍历下一个不同大小的chunk，这样可以加快在large bin链表中的遍历速度。
} 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); }正向遍历chunk size链表，直到找到第一个chunk大小小于等于当前chunk大小的chunk退出循环。 if ((unsigned long) size == (unsigned long) fwd->size) /* Always insert in the second position. */ fwd = fwd->fd;如果从large bin链表中找到了与当前chunk大小相同的chunk，则同一大小的chunk已经存在，那么chunk size链表中一定包含了fwd所指向的chunk，为了不修改chunk size链表，当前chunk只能插入fwd之后。 else { victim->fd_nextsize = fwd; victim->bk_nextsize = fwd->bk_nextsize; fwd->bk_nextsize = victim; victim->bk_nextsize->fd_nextsize = victim;如果chunk size链表中还没有包含当前chunk大小的chunk，也就是说当前chunk的大小大于fwd的大小，则将当前chunk作为该chunk size的代表加入chunk size链表，chunk size链表也是按照由大到小的顺序排序。 } bck = fwd->bk; } } else victim->fd_nextsize = victim->bk_nextsize = victim;如果large bin链表中没有chunk，直接将当前chunk加入chunk size链表。 } mark_bin(av, victim_index); victim->bk = bck; victim->fd = fwd; fwd->bk = victim; bck->fd = victim;上面的代码将当前chunk插入到large bin的空闲chunk链表中，并将large bin所对应binmap的相应bit置位。#define MAX_ITERS 10000 if (++iters >= MAX_ITERS) break;如果unsorted bin中的chunk超过了10000个，最多遍历10000个就退出，避免长时间处理unsorted bin影响内存分配的效率。 }当将unsorted bin中的空闲chunk加入到相应的small bins和large bins后，将使用最佳匹配法分配large bin chunk。源代码如下： /* 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 && (unsigned long)(victim->size) >= (unsigned long)(nb)) {如果所需分配的chunk为large bin chunk，查询对应的large bin链表，如果large bin链表为空，或者链表中最大的chunk也不能满足要求，则不能从large bin中分配。否则，遍历large bin链表，找到合适的chunk。 victim = victim->bk_nextsize; while (((unsigned long)(size = chunksize(victim)) < (unsigned long)(nb))) victim = victim->bk_nextsize;反向遍历chunk size链表，直到找到第一个大于等于所需chunk大小的chunk退出循环。 /* 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;?如果从large bin链表中选取的chunkvictim不是链表中的最后一个chunk，并且与victim大小相同的chunk不止一个，那么意味着victim为chunk size链表中的节点，为了不调整chunk size链表，需要避免将chunk size链表中的节点取出，所以取victim->fd节点对应的chunk作为候选chunk。由于large bin链表中的chunk也是按大小排序，同一大小的chunk有多个时，这些chunk必定排在一起，所以victim->fd节点对应的chunk的大小必定与victim的大小一样。
remainder_size = size - nb; unlink(victim, bck, fwd);计算将victim切分后剩余大小，并调用unlink()宏函数将victim从large bin链表中取出。 /* Exhaust */ if (remainder_size < MINSIZE) { set_inuse_bit_at_offset(victim, size); if (av != &main_arena) victim->size |= NON_MAIN_ARENA;?如果将victim切分后剩余大小小于MINSIZE，则将真个victim分配给应用层，这种情况下，实际分配的chunk比所需的chunk要大一些。以64位系统为例，remainder_size的可能大小为0和16，如果为0，表示victim的大小刚好等于所需chunk的大小，设置victim的inuse标志，inuse标志位于下一个相邻的chunk的size字段中。如果remainder_size为16，则这16字节就浪费掉了。如果当前分配区不是主分配区，将victim的size字段中的非主分配区标志置位。
} /* 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 (__builtin_expect (fwd->bk != bck, 0)) { 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; }从victim中切分出所需的chunk，剩余部分作为一个新的chunk加入到unsorted bin中。如果剩余部分chunk属于large bins，将剩余部分chunk的chunk size链表指针设置为NULL，因为unsorted bin中的chunk是不排序的，这两个指针无用，必须清零。 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);设置victim和remainder的状态，由于remainder为空闲chunk，所以需要设置该chunk的foot。 } check_malloced_chunk(av, victim, nb); void *p = chunk2mem(victim); if (__builtin_expect (perturb_byte, 0)) alloc_perturb (p, bytes); return p;从large bin中使用最佳匹配法找到了合适的chunk，调用chunk2mem()获得chunk中可用的内存指针，返回给应用层，退出。 } }?
?
?
?
?