INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */ INTERNAL_SIZE_T 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; };
large
bin中挂着的chunk是按照大小排序的,一个chunk逻辑上相连的chunk可能大小相同,也可能不同,fd_nextsize,bk_nextsize就指向第一个大小不同的chunk
这样说比较抽象,具体见后面的largebin结构
空间复用
分配时状态
1 2 3 4 5 6 7 8 9 10 11 12 13 14
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Size of previous chunk, ifunallocated(P clear) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Size of chunk, in bytes |A|M|P| mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | User data starts here... . . . . (malloc_usable_size() bytes) . next . | chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | (size of chunk, but used for application data) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Size of next chunk, in bytes |A|0|1| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
空闲时状态
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Size of previous chunk | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ `head:' | Size of chunk, in bytes |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 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
宏定义
指针转换
1 2 3
/* conversion from malloc headers to user pointers, and back */ #define chunk2mem(p) ((void *) ((char *) (p) + 2 * SIZE_SZ)) #define mem2chunk(mem) ((mchunkptr)((char *) (mem) -2 * SIZE_SZ))
mem就是数据区,chunk就是malloc_chunk的基地址,两者的关系在图上表示
1 2 3 4 5 6 7 8 9 10 11 12 13 14
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Size of previous chunk, ifunallocated(P clear) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Size of chunk, in bytes |A|M|P| mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | User data starts here... . . . . (malloc_usable_size() bytes) . next . | chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | (size of chunk, but used for application data) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Size of next chunk, in bytes |A|0|1| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
/* Check if a request is so large that it would wrap around zero when padded and aligned. To simplify some other code, the bound is made low enough so that adding MINSIZE will also not wrap around zero. */
/* size field is or'ed with NON_MAIN_ARENA if the chunk was obtained from a non-main arena. This is only set immediately before handing the chunk to the user, if necessary. */ #define NON_MAIN_ARENA 0x4
/* Check for chunk from main arena. */ #define chunk_main_arena(p) (((p)->mchunk_size & NON_MAIN_ARENA) == 0)
/* Mark a chunk as not being on the main arena. */ #define set_non_main_arena(p) ((p)->mchunk_size |= NON_MAIN_ARENA)
/* Bits to mask off when extracting size Note: IS_MMAPPED is intentionally not masked off from size field in macros for which mmapped chunks should never be seen. This should cause helpful core dumps to occur if it is tried by accident by people extending or adapting this malloc. */ #define SIZE_BITS (PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
获取本chunk size
1 2 3 4 5
/* Get size, ignoring use bits */ #define chunksize(p) (chunksize_nomask(p) & ~(SIZE_BITS))
/* Like chunksize, but do not mask SIZE_BITS. */ #define chunksize_nomask(p) ((p)->mchunk_size)
/* Set size at head, without disturbing its use bit */ // SIZE_BITS = 7 #define set_head_size(p, s) \ ((p)->mchunk_size = (((p)->mchunk_size & SIZE_BITS) | (s)))
/* Set size/use field */ #define set_head(p, s) ((p)->mchunk_size = (s))
/* Set size at footer (only when chunk is not in use) */ #define set_foot(p, s) \ (((mchunkptr)((char *) (p) + (s)))->mchunk_prev_size = (s))
这里set_foot干了啥?
p是chunk指针,s是该chunk的大小,p+s就指向了本chunk的结尾,
也就是下一个chunk的基地址,也就是下一个chunk的prev_size成员,
于是p+s强转为一个malloc_chunk类型指针,
然后取其第一个成员也就是prev_size,写上本chunk的大小
指定偏移处认为是一个chunk
1 2
/* Treat space at ptr + offset as a chunk */ #define chunk_at_offset(p, s) ((mchunkptr)(((char *) (p)) + (s)))
实际上largebins和smallbins可以看成一个整体,前64个桶子是smallbins 前64个桶子相邻两个桶子之间大小差8字节 然后32个桶子相邻两个桶子之间大小差64字节 然后16个桶子相邻两个桶子之间大小差512字节 ... 64 bins of size 8 32 bins of size 64 16 bins of size 512 8 bins of size 4096 4 bins of size 32768 2 bins of size 262144 1 bin of size what's left
victim = _int_malloc (ar_ptr, bytes);//int_malloc函数是实际进行内存分配的函数 /* Retry with another arena only if we were able to find a usable arena before. */ 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);//重新获取分配区之后再次尝试切割堆块给victim }
if (ar_ptr != NULL)//解锁,因为int_malloc中会对分配区上锁,解锁后方便其他线程分配内存 (void) mutex_unlock (&ar_ptr->mutex);
INTERNAL_SIZE_T nb; /* normalized request size *///本变量是用户希望大小size的计算值,也就是实际的堆块大小 unsignedint idx; /* associated bin index *///本变量用于记录nb大小的堆块属于的桶子下标 mbinptr bin; /* associated bin */;//桶子头指针
mchunkptr victim; /* inspected/selected chunk *///命中堆块 INTERNAL_SIZE_T size; /* its size *///victim命中堆块本来的大小 int victim_index; /* its bin index *///victim_index命中堆块属于的桶子下标
mchunkptr remainder; /* remainder from a split *///切割一个大块,剩下的部分被称为remainder unsignedlong remainder_size; /* its size *///剩余部分的大小
unsignedint block; /* bit map traverser *///binmap下标,用于记录一个桶子属于四个block之一的哪一个 unsignedint bit; /* bit map traverser *///用于记录一共桶子属于其block中的哪一位 unsignedintmap; /* current word of binmap *///binmap[map],作为binmap的下标,有0,1,2,3四个取值
mchunkptr fwd; /* misc temp for linking *///取桶子头之后一般会让bck指向之前的第一个堆块,fwd指向桶子头,然后头插 mchunkptr bck; /* misc temp for linking */
/* There are no usable arenas. Fall back to sysmalloc to get a chunk from mmap. */ if (__glibc_unlikely (av == NULL)) { void *p = sysmalloc (nb, av); if (p != NULL) alloc_perturb (p, bytes); return p; }
staticvoidmalloc_consolidate(mstate av) { mfastbinptr *fb; /* current fastbin being consolidated */ mfastbinptr *maxfb; /* last fastbin (for loop control) */ mchunkptr p; /* current chunk being consolidated */ mchunkptr nextp; /* next chunk to consolidate */ mchunkptr unsorted_bin; /* bin header */ mchunkptr first_unsorted; /* chunk to link to */
/* These have same use as in free() */ mchunkptr nextchunk; INTERNAL_SIZE_T size; INTERNAL_SIZE_T nextsize; INTERNAL_SIZE_T prevsize; int nextinuse; mchunkptr bck; mchunkptr fwd;
/* If max_fast is 0, we know that av hasn't yet been initialized, in which case do so below */
if (get_max_fast() != 0)//如果max_faxt值为空,则说明堆还没有初始化 { clear_fastchunks(av);
unsorted_bin = unsorted_chunks(av);
/* Remove each chunk from fast bin and consolidate it, placing it then in unsorted bin. Among other reasons for doing this, placing in unsorted bin avoids needing to calculate actual bins until malloc is sure that chunks aren't immediately going to be reused anyway. */
maxfb = &fastbin(av, NFASTBINS - 1); fb = &fastbin(av, 0); do { p = atomic_exchange_acq(fb, 0); // p=fb,fb++ if (p != 0) { do { // 释放快桶子p上挂着的所有堆块 check_inuse_chunk(av, p); nextp = p->fd; // 先取后继
/* Slightly streamlined version of consolidation code in free() */ size = p->size & ~(PREV_INUSE | NON_MAIN_ARENA); // 撤销flag nextchunk = chunk_at_offset(p, size); // 物理上相邻的下一个堆块 nextsize = chunksize(nextchunk);
if (!prev_inuse(p))//向前合并 { prevsize = p->prev_size; size += prevsize; p = chunk_at_offset(p, -((long)prevsize));//取物理上前一个相邻的堆块基址,作为合并堆块的基址 unlink(av, p, bck, fwd); }
if (nextchunk != av->top)//如果后面和topchunk相邻则和topchunk合并,否则尝试向后合并 { nextinuse = inuse_bit_at_offset(nextchunk, nextsize);
/* 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) { /* 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); if ((unsignedlong)(size) < (unsignedlong)(bck->bk->size)) { fwd = bck; bck = bck->bk;
if (!in_smallbin_range(nb))//如果是一个largebin的请求 { 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)) {//first(bin)=bin->fd,可以看出bin->fd应该是该桶子中最大的一个堆块,然后顺着fd指针越来越小 //如果最大的堆块都不满足nb的需求,显然再往后找更小的无意义,因此首先需要判断最大的堆块是否能满足要求, //当这个前提条件满足时,再向后找最佳适配的堆块 victim = victim->bk_nextsize;//bk_nextsize是下一个比当前victim小的堆块,victim->bk可能和victim一样大,但是victim->bk_nextsize要么是桶子头,要么一定比当前堆块小 while (((unsignedlong)(size = chunksize(victim)) < (unsignedlong)(nb))) victim = victim->bk_nextsize;//从小开始遍历直到第一个大于等于nb大小的堆块
/* 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;//避免移除跳表的最开始一个导致变更指针,首先尝试寻找该大小的堆块是否有第二块,如果有则放过跳表头 remainder_size = size - nb;//victim块比较抠,只分配nb大小左右,多余的不给 unlink(av, victim, bck, fwd);
/* Exhaust */ if (remainder_size < MINSIZE)//如果发现victim分割后的剩余部分都是下脚料就不抠了 { set_inuse_bit_at_offset(victim, size); if (av != &main_arena) victim->size |= NON_MAIN_ARENA; } /* Split */ else//否则victim剩余部分放到unsortedbin { remainder = chunk_at_offset(victim, nb);//取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 (__glibc_unlikely(fwd->bk != bck)) { 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;//如果剩余大小还是largebin大小,则此时预先将指针清零 remainder->bk_nextsize = NULL; } 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); alloc_perturb(p, bytes); return p; } }
/* 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); //首先查binmap,看看下一个桶子是否确实有空闲堆块 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)//如果bit>map只可能是map=0,也就是当前block是空的 { do { if (++block >= BINMAPSIZE) /* out of bins */ goto use_top;//如果发现block遍历了4个block,全是空的,也就是largebin空了,直接使用top_chunk分配 } while ((map = av->binmap[block]) == 0);//跳过所有空的largebin
bin = bin_at(av, (block << BINMAPSHIFT)); bit = 1; }
/* Advance to bin with set bit. There must be one. */ while ((bit & map) == 0)//尝试找一个map对应block中有堆块的桶子 { bin = next_bin(bin); bit <<= 1;//左移也就是往largebin更大的方向找 assert(bit != 0); }//退出循环时,bin对应的桶子中一定有堆块
/* 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)//检查是否该bin中至少有一个堆块,这是因为map是懒修改的 {//也就是说,map中标记有的不一定有,但是map中标记没有的一定没有 av->binmap[block] = map &= ~bit; /* Write through */ //本桶子中确实没有,但也不是没有功劳,起码可以修改map,下一次查找一定不会查本桶子 bin = next_bin(bin); bit <<= 1;//继续向更大的largebin桶子寻找 }
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); }
/* Little security check which won't hurt performance: the allocator never wrapps around at the end of the address space. Therefore we can exclude some size values which might appear here by accident or by "design" from some intruder. */ if (__builtin_expect((uintptr_t)p > (uintptr_t)-size, 0) || __builtin_expect(misaligned_chunk(p), 0)) { errstr = "free(): invalid pointer"; errout: if (!have_lock && locked) (void)mutex_unlock(&av->mutex); malloc_printerr(check_action, errstr, chunk2mem(p), av); return; } /* We know that each chunk is at least MINSIZE bytes in size or a multiple of MALLOC_ALIGNMENT. */ if (__glibc_unlikely(size < MINSIZE || !aligned_OK(size))) { errstr = "free(): invalid size"; goto errout; }
if ((unsignedlong)(size) <= (unsignedlong)(get_max_fast())//如果释放堆块大小落在fastbin范围内
#if TRIM_FASTBINS /* If TRIM_FASTBINS set, don't place chunks bordering top into fastbins */ && (chunk_at_offset(p, size) != av->top)//检查后面是否和topchunk相邻,(如果相邻需要合并,不会进入fastbin) #endif ) {
if (__builtin_expect(chunk_at_offset(p, size)->size <= 2 * SIZE_SZ, 0) || __builtin_expect(chunksize(chunk_at_offset(p, size)) >= av->system_mem, 0)) {//首先检查堆块大小是否比最小大小要大,并且是不是可以分配的范围内 /* We might not have a lock at this point and concurrent modifications of system_mem might have let to a false positive. Redo the test after getting the lock. */ if (have_lock || ({c assert(locked == 0); mutex_lock(&av->mutex); locked = 1; chunk_at_offset(p, size)->size <= 2 * SIZE_SZ || chunksize(chunk_at_offset(p, size)) >= av->system_mem; })) { errstr = "free(): invalid next size (fast)"; goto errout; } if (!have_lock) { (void)mutex_unlock(&av->mutex); locked = 0; } } //已获得锁 free_perturb(chunk2mem(p), size - 2 * SIZE_SZ);//堆块的mem数据区清零
/* Atomically link P to its fastbin: P->FD = *FB; *FB = P; */ mchunkptr old = *fb, old2;//old指向fastbin对应桶子的第一个堆块 unsignedint old_idx = ~0u; do { /* Check that the top of the bin is not the record we are going to add (i.e., double free). */ if (__builtin_expect(old == p, 0))//检查p是否已经被刚刚释放过一次 { errstr = "double free or corruption (fasttop)"; goto errout; } /* Check that size of fastbin chunk at the top is the same as size of the chunk that we are adding. We can dereference OLD only if we have the lock, otherwise it might have already been deallocated. See use of OLD_IDX below for the actual check. */ if (have_lock && old != NULL) old_idx = fastbin_index(chunksize(old)); p->fd = old2 = old;//把p挂到fastbin上(头插法),fastbin[idx]->p->old->... } while ((old = catomic_compare_and_exchange_val_rel(fb, p, old2)) != old2);
/* Lightweight tests: check whether the block is already the top block. */ if (__glibc_unlikely(p == av->top))//p不能是topchunk { errstr = "double free or corruption (top)"; goto errout; } /* Or whether the next chunk is beyond the boundaries of the arena. */ if (__builtin_expect(contiguous(av) && (char *)nextchunk >= ((char *)av->top + chunksize(av->top)), 0)) {//如果下一个堆块溢出到topchunk内部了 errstr = "double free or corruption (out)"; goto errout; } /* Or whether the block is actually not marked used. */ if (__glibc_unlikely(!prev_inuse(nextchunk))) {//如果物理上的后块没有记录本块的释放状态 errstr = "double free or corruption (!prev)"; goto errout; }
/* Place the chunk in unsorted chunk list. Chunks are not placed into regular bins until after they have been given one chance to be used in malloc. */
/* If freeing a large space, consolidate possibly-surrounding chunks. Then, if the total unused topmost memory exceeds trim threshold, ask malloc_trim to reduce top. Unless max_fast is 0, we don't know if there are fastbins bordering top, so we cannot tell for sure whether threshold has been reached unless fastbins are consolidated. But we don't want to consolidate on each free. As a compromise, consolidation is performed if FASTBIN_CONSOLIDATION_THRESHOLD is reached. */
if ((unsignedlong)(size) >= FASTBIN_CONSOLIDATION_THRESHOLD) {//如果size大于fastbin合并阈值65536 if (have_fastchunks(av)) malloc_consolidate(av);//清空fastbin,该合并合并,放到unsortedbin或者topchunk
if (av == &main_arena)//如果是主分配区 { #ifndef MORECORE_CANNOT_TRIM if ((unsignedlong)(chunksize(av->top)) >= (unsignedlong)(mp_.trim_threshold))//如果topchunk太大了就得修剪一下 systrim(mp_.top_pad, av); #endif } else//否则就是非主分配区的辅助堆 { /* Always try heap_trim(), even if the top chunk is not large, because the corresponding heap might go away. */ heap_info *heap = heap_for_ptr(top(av));
