为了更有效率地分配空闲的堆内存,ptmalloc2把空闲的chunk进行了分类,并用链表把不同类的chunk串起来就形成了bin。不同类的chunk组成的bin有不同的名字:fast bin, unsorted bin, small bin, large bin,这些bin的不同之处将在后面源码分析的部分说明。
/* This struct declaration is misleading (but accurate and necessary). It declares a "view" into memory allowing access to necessary fields at known offsets from a given base. See explanation below. */
structmalloc_chunk {
INTERNAL_SIZE_T mchunk_prev_size; /* Size of previous chunk (if free). */ INTERNAL_SIZE_T mchunk_size; /* Size in bytes, including overhead. */
structmalloc_chunk* fd;/* double links -- used only if free. */ structmalloc_chunk* bk;
/* Only used for large blocks: pointer to next larger size. */ structmalloc_chunk* fd_nextsize;/* double links -- used only if free. */ structmalloc_chunk* bk_nextsize; };
/* malloc_chunk details: (The following includes lightly edited explanations by Colin Plumb.) Chunks of memory are maintained using a `boundary tag' method as described in e.g., Knuth or Standish. (See the paper by Paul Wilson ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a survey of such techniques.) Sizes of free chunks are stored both in the front of each chunk and at the end. This makes consolidating fragmented chunks into bigger chunks very fast. The size fields also hold bits representing whether chunks are free or in use. An allocated chunk looks like this: chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Size of previous chunk, if unallocated (P clear) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Size of chunk, in bytes |A|M|P| mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | User data starts here... . . . . (malloc_usable_size() bytes) . . | nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | (size of chunk, but used for application data) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Size of next chunk, in bytes |A|0|1| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Where "chunk" is the front of the chunk for the purpose of most of the malloc code, but "mem" is the pointer that is returned to the user. "Nextchunk" is the beginning of the next contiguous chunk. Chunks always begin on even word boundaries, so the mem portion (which is returned to the user) is also on an even word boundary, and thus at least double-word aligned. Free chunks are stored in circular doubly-linked lists, and look like this: chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Size of previous chunk, if unallocated (P clear) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ `head:' | Size of chunk, in bytes |A|0|P| mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Forward pointer to next chunk in list | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Back pointer to previous chunk in list | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Unused space (may be 0 bytes long) . . . . | nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ `foot:' | Size of chunk, in bytes | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Size of next chunk, in bytes |A|0|0| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The P (PREV_INUSE) bit, stored in the unused low-order bit of the chunk size (which is always a multiple of two words), is an in-use bit for the *previous* chunk. If that bit is *clear*, then the word before the current chunk size contains the previous chunk size, and can be used to find the front of the previous chunk. The very first chunk allocated always has this bit set, preventing access to non-existent (or non-owned) memory. If prev_inuse is set for any given chunk, then you CANNOT determine the size of the previous chunk, and might even get a memory addressing fault when trying to do so. The A (NON_MAIN_ARENA) bit is cleared for chunks on the initial, main arena, described by the main_arena variable. When additional threads are spawned, each thread receives its own arena (up to a configurable limit, after which arenas are reused for multiple threads), and the chunks in these arenas have the A bit set. To find the arena for a chunk on such a non-main arena, heap_for_ptr performs a bit mask operation and indirection through the ar_ptr member of the per-heap header heap_info (see arena.c). Note that the `foot' of the current chunk is actually represented as the prev_size of the NEXT chunk. This makes it easier to deal with alignments etc but can be very confusing when trying to extend or adapt this code. The three exceptions to all this are: 1. The special chunk `top' doesn't bother using the trailing size field since there is no next contiguous chunk that would have to index off it. After initialization, `top' is forced to always exist. If it would become less than MINSIZE bytes long, it is replenished. 2. Chunks allocated via mmap, which have the second-lowest-order bit M (IS_MMAPPED) set in their size fields. Because they are allocated one-by-one, each must contain its own trailing size field. If the M bit is set, the other bits are ignored (because mmapped chunks are neither in an arena, nor adjacent to a freed chunk). The M bit is also used for chunks which originally came from a dumped heap via malloc_set_state in hooks.c. 3. Chunks in fastbins are treated as allocated chunks from the point of view of the chunk allocator. They are consolidated with their neighbors only in bulk, in malloc_consolidate. */
/* A heap is a single contiguous memory region holding (coalesceable) malloc_chunks. It is allocated with mmap() and always starts at an address aligned to HEAP_MAX_SIZE. */
typedefstruct _heap_info { mstate ar_ptr; /* Arena for this heap. */ struct _heap_info *prev;/* Previous heap. */ size_t size; /* Current size in bytes. */ size_t mprotect_size; /* Size in bytes that has been mprotected PROT_READ|PROT_WRITE. */ /* Make sure the following data is properly aligned, particularly that sizeof (heap_info) + 2 * SIZE_SZ is a multiple of MALLOC_ALIGNMENT. */ char pad[-6 * SIZE_SZ & MALLOC_ALIGN_MASK]; } heap_info;
/* Flags (formerly in max_fast). */ int flags;//表示arena是否存在fastbin或者内存是否连续等信息
/* Set if the fastbin chunks contain recently inserted free blocks. */ /* Note this is a bool but not all targets support atomics on booleans. */ int have_fastchunks;
/* Base of the topmost chunk -- not otherwise kept in a bin */ mchunkptr top;//指向top chunk
/* The remainder from the most recent split of a small request */ mchunkptr last_remainder;//指向last_remainder
/* Normal bins packed as described above */ mchunkptr bins[NBINS * 2 - 2];//存放除fastbin的所有bin
/* Bitmap of bins */ unsignedint binmap[BINMAPSIZE];
/* Linked list */ structmalloc_state *next;//指向下一个arena
/* Linked list for free arenas. Access to this field is serialized by free_list_lock in arena.c. */ structmalloc_state *next_free;//指向下一个空闲的arena
/* Number of threads attached to this arena. 0 if the arena is on the free list. Access to this field is serialized by free_list_lock in arena.c. */ INTERNAL_SIZE_T attached_threads;//使用本arena的线程的数量
/* Memory allocated from the system in this arena. */ //分配给本arena的内存范围 INTERNAL_SIZE_T system_mem; INTERNAL_SIZE_T max_system_mem; };
/* We overlay this structure on the user-data portion of a chunk when the chunk is stored in the per-thread cache. */ typedefstructtcache_entry { structtcache_entry *next; } tcache_entry;
/* There is one of these for each thread, which contains the per-thread cache (hence "tcache_perthread_struct"). Keeping overall size low is mildly important. Note that COUNTS and ENTRIES are redundant (we could have just counted the linked list each time), this is for performance reasons. */ typedefstructtcache_perthread_struct { char counts[TCACHE_MAX_BINS]; tcache_entry *entries[TCACHE_MAX_BINS]; } tcache_perthread_struct;
//寻找可用的arena并分配chunk arena_get(ar_ptr, bytes); victim = _int_malloc(ar_ptr, bytes); /* Retry with another arena only if we were able to find a usable arena before. */ //如果找到了可用的arena但chunk分配不成功则重新寻找和分配 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); }
if (ar_ptr != NULL) __libc_lock_unlock (ar_ptr->mutex);
/* In a low memory situation, we may not be able to allocate memory - in which case, we just keep trying later. However, we typically do this very early, so either there is sufficient memory, or there isn't enough memory to do non-trivial allocations anyway. */ if (victim) { tcache = (tcache_perthread_struct *) victim; memset (tcache, 0, sizeof (tcache_perthread_struct)); }
/* 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. */ //将申请的字节数bytes根据2*SIZE_SZ对齐转换成实际分配的字节数nb //并做了一些安全检查,确保不会溢出 checked_request2size (bytes, nb);
/* There are no usable arenas. Fall back to sysmalloc to get a chunk from mmap. */ //如果当前的arena不可用,就用调用sysmalloc向操作系统直接申请nb大小的内存返回 if (__glibc_unlikely (av == NULL)) { void *p = sysmalloc (nb, av); if (p != NULL) alloc_perturb (p, bytes); return p; } ... }
fast bin
fast bin存储在fastbinY数组中,一共有10个,每个fast bin都是一个单链表,只用fd将各个chunk串起来。每个单链表中的chunk大小是一样的,这样在找特定大小的chunk的时候就不用挨个找,只需要计算出对应链表的索引即可,提高了效率。如fastbinY[0]中存储的链表里都是16字节大小的chunk(以32位系统为例),之后每个链表增加8个字节,所以最后一个fast bin中存储的是88字节的chunk。另外,fast bin使用的是LIFO算法(即后入先出),这样刚被释放的chunk最先被分配,利用了局部性原理。
fast bin是除tcache外优先级最高的,如果fas tbin中有满足需求的chunk就不需要再到small bin和large bin中寻找。当在fast bin中找到需要的chunk后还将与该chunk大小相同的所有chunk放入tcache,目的就是利用局部性原理提高下一次内存分配的效率。
/* 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. */
#define REMOVE_FB(fb, victim, pp) \ do \ { \ victim = pp; \ if (victim == NULL) \ break; \ } while ((pp = catomic_compare_and_exchange_val_acq(fb, victim->fd, victim)) != victim); //判断实际分配的chunk大小是否满足fastbin的要求 //即小于等于MAX_FAST_SIZE(在32位中是80,在64位中是160) if ((unsignedlong)(nb) <= (unsignedlong)(get_max_fast())) { idx = fastbin_index(nb);//寻找在fastbin数组中对应的索引 mfastbinptr *fb = &fastbin(av, idx);//链表头指针 mchunkptr pp; victim = *fb;//将链表的第一个chunk作为victim取出,插入时也插入在链表头,即LIFO if (victim != NULL) { if (SINGLE_THREAD_P) *fb = victim->fd;//即将victim从链表中取出 else REMOVE_FB(fb, pp, victim);//也是将victim从链表中取出,fb指向下一个chunk //确保分配的chunk属于刚才找到的fastbin链表 if (__glibc_likely(victim != NULL)) { size_t victim_idx = fastbin_index(chunksize(victim)); if (__builtin_expect(victim_idx != idx, 0)) malloc_printerr("malloc(): memory corruption (fast)"); check_remalloced_chunk(av, victim, nb); //将大小为nb的chunk放到tcache里 #if USE_TCACHE /* While we're here, if we see other chunks of the same size, stash them in the tcache. */ size_t tc_idx = csize2tidx(nb); if (tcache && tc_idx < mp_.tcache_bins)//mp_.tcache_bins=64 { mchunkptr tc_victim;
/* While bin not empty and tcache not full, copy chunks. */ //当对应tcache链没有满并且要放入tcache的chunk(即刚才被拿出去的chunk的下一个chunk)不为空 while (tcache->counts[tc_idx] < mp_.tcache_count && (tc_victim = *fb) != NULL)//mp_.tcache_count=7,即tcache的链表最多7个chunk { //同上,从链表中取出tc_victim if (SINGLE_THREAD_P) *fb = tc_victim->fd; else { REMOVE_FB(fb, pp, tc_victim); if (__glibc_unlikely(tc_victim == NULL)) break; } tcache_put(tc_victim, tc_idx);//将取出的chunk放入对应的tcache链表 } } #endif //返回从fastbin中找到的chunk void *p = chunk2mem(victim); alloc_perturb(p, bytes); return p; } } }
small bin
small bin存储在bins数组中,下标为2到63,一共62个,和fast bin一样,每个small bin中的chunk都是相同的大小,下标为2的small bin中存储的是16个字节的chunk,之后一次增加8个字节,所以下标为63的small bin中存储的是504个字节的chunk(以32位系统为例)。与fast bin不同的是,small bin是一个双向循环链表,且采用FIFO(先进先出)算法。
/* 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.) */
//如果不是main_arena将NON_MAIN_ARENA位置1 if (av != &main_arena) set_non_main_arena(victim); check_malloced_chunk(av, victim, nb); #if USE_TCACHE //与fast bin中那部分相似,都是将所有大小为nb的chunk放入tcache中 //不同的是在本部分中chunk放入tcache之前将该chunk标记为使用中 //而fast bin的那部分没有 //说明tcache和fast bin中的chunk尽管空闲还是都被标记为使用中 //目的是防止相邻的chunk合并 /* While we're here, if we see other chunks of the same size, stash them in the tcache. */ size_t tc_idx = csize2tidx(nb); if (tcache && tc_idx < mp_.tcache_bins) { mchunkptr tc_victim;
/* While bin not empty and tcache not full, copy chunks over. */ while (tcache->counts[tc_idx] < mp_.tcache_count && (tc_victim = last(bin)) != bin) { if (tc_victim != 0) { bck = tc_victim->bk; set_inuse_bit_at_offset(tc_victim, nb); if (av != &main_arena) set_non_main_arena(tc_victim); bin->bk = bck; bck->fd = bin;
/* 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);//算出对应的large bin的索引 //合并 fast bin 到 unsorted bin if (atomic_load_relaxed(&av->have_fastchunks)) malloc_consolidate(av); }
/* 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. */ //tcache变量定义及初始化 #if USE_TCACHE INTERNAL_SIZE_T tcache_nb = 0; size_t tc_idx = csize2tidx(nb);//nb对应的tcache索引 if (tcache && tc_idx < mp_.tcache_bins) tcache_nb = nb; int return_cached = 0;//用于标记是否有合适大小chunk在下面的过程中被放入tcache
for (;;)//大循环 { int iters = 0; //unsorted bin非空 while ((victim = unsorted_chunks(av)->bk) != unsorted_chunks(av)) { bck = victim->bk;//倒数第二个chunk //victim的大小非法 if (__builtin_expect(chunksize_nomask(victim) <= 2 * SIZE_SZ, 0) || __builtin_expect(chunksize_nomask(victim) > av->system_mem, 0)) malloc_printerr("malloc(): memory corruption"); size = chunksize(victim);//victim的大小
/* 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. */
/* maintain large bins in sorted order */ if (fwd != bck)//如果large bin链表不为空 { /* Or with inuse bit to speed comparisons */ //将PREV_INUSE置1,加速比较 size |= PREV_INUSE; /* if smaller than smallest, bypass loop below */ //确保bck->bk在main arena中 assert(chunk_main_arena(bck->bk)); //如果victim比链表中的最后一个也就是最小的一个还小,就直接插入最后 if ((unsignedlong)(size) < (unsignedlong)chunksize_nomask(bck->bk)) { fwd = bck; bck = bck->bk;
//如果已经将足够多的chunk放入tcache就直接从tcache中找到chunk并返回 #if USE_TCACHE /* If we've processed as many chunks as we're allowed while filling the cache, return one of the cached ones. */ ++tcache_unsorted_count; if (return_cached && mp_.tcache_unsorted_limit > 0 && tcache_unsorted_count > mp_.tcache_unsorted_limit) { return tcache_get(tc_idx); } #endif
#define MAX_ITERS 10000 //wille循环最多10000次 if (++iters >= MAX_ITERS) break; } //while循环结束后判断是否有chunk被放进tcache,如果有就从tcache中取出chunk并返回 #if USE_TCACHE /* If all the small chunks we found ended up cached, return one now. */ if (return_cached) { return tcache_get(tc_idx); } #endif
/* 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);//idx在之前被赋值,idx = largebin_index(nb)
/* skip scan if empty or largest chunk is too small */ //如果large bin非空并且large bin中最大的chunk不小于nb if ((victim = first(bin)) != bin && (unsignedlong)chunksize_nomask(victim) >= (unsignedlong)(nb)) { victim = victim->bk_nextsize; //反向遍历链表,从最小的开始找,找到第一个不小于nb的chunk 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. */ //如果victim不是链表的最后一个,并且victim与之普通链上的下一个chunk大小相同 //就使用下一个chunk,因为该chunk不在nextsize链上,就不用改动nextsize指针 //注:前面找到的第一个不小于nb的chunk是在nextsize链上找到的,所以该chunk普通链上 //的下一个chunk是有可能与之大小相同的,正如前面所说,如果插入的时候大小相同就插在后面 if (victim != last(bin) && chunksize_nomask(victim) == chunksize_nomask(victim->fd)) 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. */
for (;;) { /* Skip rest of block if there are no more set bits in this block. */ //bit>map,即在当前block中大于等于(idx%32)位置上的bin都不可用 //另外按照bin的排列规则,索引越大的bin,chunk越大 //所以bit>map表示当前block中没有可用的bin if (bit > map || bit == 0) { //如果当前block不可用就找下一个block,直到binmap不等于0,即找到的block中有可用bin do { if (++block >= BINMAPSIZE) /* out of bins */ goto use_top;//如果超出了bin的范围,就使用top chunk } while ((map = av->binmap[block]) == 0);
//block左移5位即idx2block的逆过程,找到当前block的第一个bin bin = bin_at(av, (block << BINMAPSHIFT)); bit = 1;//表示当前使用的是第一个bin }
/* Advance to bin with set bit. There must be one. */ //(bit & map) == 0表示当前的bin不可用 while ((bit & map) == 0) { bin = next_bin(bin); bit <<= 1;//左移1位表示使用下一个chunk assert(bit != 0); }
/* Inspect the bin. It is likely to be non-empty */ //从最后一个也就是最小的一个chunk开始 victim = last(bin);
/* If a false alarm (empty bin), clear the bit. */ //如果bin是空的的话更新对应map中的bit值为0,并找下一个bin if (victim == bin) { av->binmap[block] = map &= ~bit; /* Write through */ bin = next_bin(bin); bit <<= 1; }
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. */ //如果top chunk不够,并且有fast bin就合并fast bin elseif (atomic_load_relaxed(&av->have_fastchunks)) { malloc_consolidate(av);//合并fast bin到top chunk /* restore original bin index */ //计算nb所属的bin if (in_smallbin_range(nb)) idx = smallbin_index(nb); else idx = largebin_index(nb); }