glibc2.23的堆源码学习

源码学习"/>

glibc2.23的堆源码学习

学pwn的路，光看别人写的总结，不看源码，永远不明白背后的道理，所以还是来看一看glibc的源码，浅浅学习一下，在此做个记录，欢迎各位师傅纠错和提意见建议,时间紧张，每次写一点点，定期更新。

参考网站：malloc.c - malloc/malloc.c - Glibc source code (glibc-2.23) - Bootlin

源码加部分介绍足足5000行代码，量对于我这种萌新来说还是很大的

上来前200行都是介绍，这里面例举了malloc.c里面的主要函数，之前学数据结构的时候也就学了个malloc()和free()，这次主要是需要看啥函数源码，就分析啥函数源码

这次主要研究malloc、free函数的源码以及calloc、realloc、valloc的用法

然后咱先看看chunk的结构(malloc生成的)：

/*This struct declaration is misleading (but accurate and necessary).It declares a "view" into memory allowing access to necessaryfields at known offsets from a given base. See explanation below.
*/struct malloc_chunk {INTERNAL_SIZE_T      prev_size;  /* Size of previous chunk (if free).  */INTERNAL_SIZE_T      size;       /* Size in bytes, including overhead. */struct malloc_chunk* fd;         /* double links -- used only if free. */struct malloc_chunk* bk;/* Only used for large blocks: pointer to next larger size.  */struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */struct malloc_chunk* bk_nextsize;
};

 源码里有两个图比较形象的描述了一个chunk的状态：

1.malloc的状态：

2.free后的状态：

光看这里对于一个初学者很是懵逼，大家可以写一个简单的c语言的malloc代码，然后用gdb调试看一下heap，多操作慢慢也就能理解背后的原理

size of chunk里有一个M、P标志位，

M表示的是IS_MAPPED用于表示当前堆块是否是通过mmap分配的

P表示PREV_INUSE用于表示上一个chunk是否处于使用状态（1为使用，0为未使用）

还有A标志位（图里没有）表示NON_MAIN_ARENA用于表示是否是主分配区

上面三个标志位除了P，一般都是0，所以我们经常在分配的heap里面看到我们要的堆块size比原来大1就是因为P标志位置1。

在源码中找到了相关定义：

可以看到三个标志位从高到低分别是A/M/P

然后介绍一下malloc函数：

先看源码里的介绍：

/*malloc(size_t n)Returns a pointer to a newly allocated chunk of at least n bytes, or nullif no space is available. Additionally, on failure, errno isset to ENOMEM on ANSI C systems.If n is zero, malloc returns a minumum-sized chunk. (The minimumsize is 16 bytes on most 32bit systems, and 24 or 32 bytes on 64bitsystems.)  On most systems, size_t is an unsigned type, so callswith negative arguments are interpreted as requests for huge amountsof space, which will often fail. The maximum supported value of ndiffers across systems, but is in all cases less than the maximumrepresentable value of a size_t.
*/

放英文可能好理解一点，中文翻译出来容易翻译错误

简而言之，就是申请一个malloc空间，会有一个最小的申请大小（在64位下，比如malloc（1）会返回一个0x10大小的chunk），也有一个大小的对齐（比如malloc（0x20）会返回一个0x30大小的chunk）

来看一下_int_malloc函数：
 

static void *
_int_malloc (mstate av, size_t bytes)
{INTERNAL_SIZE_T nb;               /* normalized request size */unsigned int 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 */unsigned long remainder_size;     /* its size */unsigned int block;               /* bit map traverser */unsigned int bit;                 /* bit map traverser */unsigned int map;                 /* current word of binmap */mchunkptr fwd;                    /* misc temp for linking */mchunkptr bck;                    /* misc temp for linking */const char *errstr = NULL;/*Convert request size to internal form by adding SIZE_SZ bytesoverhead plus possibly more to obtain necessary alignment and/orto obtain a size of at least MINSIZE, the smallest allocatablesize. Also, checked_request2size traps (returning 0) request sizesthat are so large that they wrap around zero when padded andaligned.*/checked_request2size (bytes, nb);/* There are no usable arenas.  Fall back to sysmalloc to get a chunk frommmap.  */if (__glibc_unlikely (av == NULL)){void *p = sysmalloc (nb, av);if (p != NULL)alloc_perturb (p, bytes);return p;}/*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 wecan try it without checking, which saves some time on this fast path.*/if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ())){idx = fastbin_index (nb);mfastbinptr *fb = &fastbin (av, idx);mchunkptr pp = *fb;do{victim = pp;if (victim == NULL)break;}while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim))!= victim);if (victim != 0){if (__builtin_expect (fastbin_index (chunksize (victim)) != idx, 0)){errstr = "malloc(): memory corruption (fast)";errout:malloc_printerr (check_action, errstr, chunk2mem (victim), av);return NULL;}check_remalloced_chunk (av, victim, nb);void *p = chunk2mem (victim);alloc_perturb (p, bytes);return p;}}/*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 areprocessed to find best fit. But for small ones, fits are exactanyway, so we can check now, which is faster.)*/if (in_smallbin_range (nb)){idx = smallbin_index (nb);bin = bin_at (av, idx);if ((victim = last (bin)) != bin){if (victim == 0) /* initialization check */malloc_consolidate (av);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;check_malloced_chunk (av, victim, nb);void *p = chunk2mem (victim);alloc_perturb (p, bytes);return p;}}}/*If this is a large request, consolidate fastbins before continuing.While it might look excessive to kill all fastbins beforeeven seeing if there is space available, this avoidsfragmentation problems normally associated with fastbins.Also, in practice, programs tend to have runs of either small orlarge requests, but less often mixtures, so consolidation is notinvoked all that often in most programs. And the programs thatit is called frequently in otherwise tend to fragment.*/else{idx = largebin_index (nb);if (have_fastchunks (av))malloc_consolidate (av);}/*Process recently freed or remaindered chunks, taking one only ifit is exact fit, or, if this a small request, the chunk is remainder fromthe most recent non-exact fit.  Place other traversed chunks inbins.  Note that this step is the only place in any routine wherechunks are placed in bins.The outer loop here is needed because we might not realize untilnear the end of malloc that we should have consolidated, so mustdo so and retry. This happens at most once, and only when we wouldotherwise need to expand memory to service a "small" request.*/for (;; ){int iters = 0;while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av)){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), av);size = chunksize (victim);/*If a small request, try to use last remainder if it is theonly chunk in unsorted bin.  This helps promote locality forruns of consecutive small requests. This is the onlyexception to best-fit, and applies only when there isno 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)){/* 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;}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;}/* remove from unsorted list */unsorted_chunks (av)->bk = bck;bck->fd = unsorted_chunks (av);/* 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);alloc_perturb (p, bytes);return p;}/* place chunk in bin */if (in_smallbin_range (size)){victim_index = smallbin_index (size);bck = bin_at (av, victim_index);fwd = bck->fd;}else{victim_index = largebin_index (size);bck = bin_at (av, victim_index);fwd = bck->fd;/* 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 ((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;}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);}if ((unsigned long) size == (unsigned long) fwd->size)/* Always insert in the second position.  */fwd = fwd->fd;else{victim->fd_nextsize = fwd;victim->bk_nextsize = fwd->bk_nextsize;fwd->bk_nextsize = victim;victim->bk_nextsize->fd_nextsize = victim;}bck = fwd->bk;}}elsevictim->fd_nextsize = victim->bk_nextsize = victim;}mark_bin (av, victim_index);victim->bk = bck;victim->fd = fwd;fwd->bk = victim;bck->fd = victim;#define MAX_ITERS       10000if (++iters >= MAX_ITERS)break;}/*If a large request, scan through the chunks of current bin insorted 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)){victim = victim->bk_nextsize;while (((unsigned long) (size = chunksize (victim)) <(unsigned long) (nb)))victim = victim->bk_nextsize;/* Avoid removing the first entry for a size so that the skiplist does not have to be rerouted.  */if (victim != last (bin) && victim->size == victim->fd->size)victim = victim->fd;remainder_size = size - nb;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;}/* Split */else{remainder = chunk_at_offset (victim, nb);/* We cannot assume the unsorted list is empty and thereforehave 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;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 largestbin. This search is strictly by best-fit; i.e., the smallest(with ties going to approximately the least recently used) chunkthat fits is selected.The bitmap avoids needing to check that most blocks are nonempty.The particular case of skipping all bins during warm-up phaseswhen 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 ((unsigned long) (size) >= (unsigned long) (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;}/* Split */else{remainder = chunk_at_offset (victim, nb);/* We cannot assume the unsorted list is empty and thereforehave to perform a complete insert here.  */bck = unsorted_chunks (av);fwd = bck->fd;if (__glibc_unlikely (fwd->bk != bck)){errstr = "malloc(): corrupted unsorted chunks 2";goto errout;}remainder->bk = bck;remainder->fd = fwd;bck->fd = remainder;fwd->bk = remainder;/* advertise as last remainder */if (in_smallbin_range (nb))av->last_remainder = remainder;if (!in_smallbin_range (remainder_size)){remainder->fd_nextsize = NULL;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;}}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-fitsearch rule.  In effect, av->top is treated as larger (and thusless well fitting) than any other available chunk since it canbe extended to be as large as necessary (up to systemlimitations).We require that av->top always exists (i.e., has size >=MINSIZE) after initialization, so if it would otherwise beexhausted by current request, it is replenished. (The mainreason for ensuring it exists is that we may need MINSIZE spaceto put in fenceposts in sysmalloc.)*/victim = av->top;size = chunksize (victim);if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE)){remainder_size = size - nb;remainder = chunk_at_offset (victim, nb);av->top = remainder;set_head (victim, nb | PREV_INUSE |(av != &main_arena ? NON_MAIN_ARENA : 0));set_head (remainder, remainder_size | PREV_INUSE);check_malloced_chunk (av, victim, nb);void *p = chunk2mem (victim);alloc_perturb (p, bytes);return p;}/* When we are using atomic ops to free fast chunks we can gethere for all block sizes.  */else if (have_fastchunks (av)){malloc_consolidate (av);/* restore original bin index */if (in_smallbin_range (nb))idx = smallbin_index (nb);elseidx = largebin_index (nb);}/*Otherwise, relay to handle system-dependent cases*/else{void *p = sysmalloc (nb, av);if (p != NULL)alloc_perturb (p, bytes);return p;}}
}

看一下free函数的介绍：

/*free(void* p)Releases the chunk of memory pointed to by p, that had been previouslyallocated using malloc or a related routine such as realloc.It has no effect if p is null. It can have arbitrary (i.e., bad!)effects if p has already been freed.Unless disabled (using mallopt), freeing very large spaces willwhen possible, automatically trigger operations that giveback unused memory to the system, thus reducing program footprint.
*/

简要意思就是回收已经使用的空间，减少程序占用

free函数的源码：
 

static void
_int_free (mstate av, mchunkptr p, int have_lock)
{INTERNAL_SIZE_T size;        /* its size */mfastbinptr *fb;             /* associated fastbin */mchunkptr nextchunk;         /* next contiguous chunk */INTERNAL_SIZE_T nextsize;    /* its size */int nextinuse;               /* true if nextchunk is used */INTERNAL_SIZE_T prevsize;    /* size of previous contiguous chunk */mchunkptr bck;               /* misc temp for linking */mchunkptr fwd;               /* misc temp for linking */const char *errstr = NULL;int locked = 0;size = chunksize (p);/* Little security check which won't hurt performance: theallocator never wrapps around at the end of the address space.Therefore we can exclude some size values which might appearhere 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 amultiple of MALLOC_ALIGNMENT.  */if (__glibc_unlikely (size < MINSIZE || !aligned_OK (size))){errstr = "free(): invalid size";goto errout;}check_inuse_chunk(av, p);/*If eligible, place chunk on a fastbin so it can be foundand used quickly in malloc.*/if ((unsigned long)(size) <= (unsigned long)(get_max_fast ())#if TRIM_FASTBINS/*If TRIM_FASTBINS set, don't place chunksbordering top into fastbins*/&& (chunk_at_offset(p, size) != av->top)
#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 modificationsof system_mem might have let to a false positive.  Redo the testafter getting the lock.  */if (have_lock|| ({ 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);set_fastchunks(av);unsigned int idx = fastbin_index(size);fb = &fastbin (av, idx);/* Atomically link P to its fastbin: P->FD = *FB; *FB = P;  */mchunkptr old = *fb, old2;unsigned int 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)){errstr = "double free or corruption (fasttop)";goto errout;}/* Check that size of fastbin chunk at the top is the same assize of the chunk that we are adding.  We can dereference OLDonly if we have the lock, otherwise it might have already beendeallocated.  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;}while ((old = catomic_compare_and_exchange_val_rel (fb, p, old2)) != old2);if (have_lock && old != NULL && __builtin_expect (old_idx != idx, 0)){errstr = "invalid fastbin entry (free)";goto errout;}}/*Consolidate other non-mmapped chunks as they arrive.*/else if (!chunk_is_mmapped(p)) {if (! have_lock) {(void)mutex_lock(&av->mutex);locked = 1;}nextchunk = chunk_at_offset(p, size);/* Lightweight tests: check whether the block is already thetop block.  */if (__glibc_unlikely (p == av->top)){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)){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;}nextsize = chunksize(nextchunk);if (__builtin_expect (nextchunk->size <= 2 * SIZE_SZ, 0)|| __builtin_expect (nextsize >= av->system_mem, 0)){errstr = "free(): invalid next size (normal)";goto errout;}free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);/* consolidate backward */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) {/* get and clear inuse bit */nextinuse = inuse_bit_at_offset(nextchunk, nextsize);/* consolidate forward */if (!nextinuse) {unlink(av, nextchunk, bck, fwd);size += nextsize;} elseclear_inuse_bit_at_offset(nextchunk, 0);/*Place the chunk in unsorted chunk list. Chunks arenot placed into regular bins until after they havebeen given one chance to be used in malloc.*/bck = unsorted_chunks(av);fwd = bck->fd;if (__glibc_unlikely (fwd->bk != bck)){errstr = "free(): corrupted unsorted chunks";goto errout;}p->fd = fwd;p->bk = bck;if (!in_smallbin_range(size)){p->fd_nextsize = NULL;p->bk_nextsize = NULL;}bck->fd = p;fwd->bk = p;set_head(p, size | PREV_INUSE);set_foot(p, size);check_free_chunk(av, p);}/*If the chunk borders the current high end of memory,consolidate into top*/else {size += nextsize;set_head(p, size | PREV_INUSE);av->top = p;check_chunk(av, p);}/*If freeing a large space, consolidate possibly-surroundingchunks. Then, if the total unused topmost memory exceeds trimthreshold, ask malloc_trim to reduce top.Unless max_fast is 0, we don't know if there are fastbinsbordering top, so we cannot tell for sure whether thresholdhas been reached unless fastbins are consolidated.  But wedon't want to consolidate on each free.  As a compromise,consolidation is performed if FASTBIN_CONSOLIDATION_THRESHOLDis reached.*/if ((unsigned long)(size) >= FASTBIN_CONSOLIDATION_THRESHOLD) {if (have_fastchunks(av))malloc_consolidate(av);if (av == &main_arena) {
#ifndef MORECORE_CANNOT_TRIMif ((unsigned long)(chunksize(av->top)) >=(unsigned long)(mp_.trim_threshold))systrim(mp_.top_pad, av);
#endif} else {/* Always try heap_trim(), even if the top chunk is notlarge, because the corresponding heap might go away.  */heap_info *heap = heap_for_ptr(top(av));assert(heap->ar_ptr == av);heap_trim(heap, mp_.top_pad);}}if (! have_lock) {assert (locked);(void)mutex_unlock(&av->mutex);}}/*If the chunk was allocated via mmap, release via munmap().*/else {munmap_chunk (p);}
}

今天，先写到这里，源码还没写注释，有时间继续写。