malloc 源码剖析.docx

内容摘要：这个函数应该是所有使用C/C+的人最熟悉的malloc调用的实现,c语言标准库提供的malloc函数.如果你使用linux, douglea malloc已经默认作为glibc的malloc,新的版本可能用的是ptmalloc(dlmalloc的多线程版本),如果你用的bsd4.2及以前系统libc用的kingsley的malloc; BSD(包括freebsd,netbsd,openbsd)4.2以后版本libc用的是PHKmalloc;如果你用的windows系统用的是microsoft的分配器算法;不过其他各个系统很容易使用doug lea malloc替换现有malloc函数.本文以dlmalloc2.7.0版本为基础，先以伪代码的形式介绍sYSTRIm函数的主要流程。其中一些次要情节已略！/*如果你使用linux, douglea malloc已经默认作为glibc的malloc,新的版本可能用的是ptmalloc(dlmalloc的多线程版本)如果你用的bsd4.2及以前系统libc用的kingsley的malloc;BSD(包括freebsd,netbsd,openbsd)4.2以后版本libc用的是PHKmalloc;如果你用的windows系统用的是microsoft的分配器算法;不过其他各个系统很容易使用doug lea malloc替换现有的malloc*/c语言标准库提供的malloc函数；请注意malloc的几个return出口;void* mALLOc(size_t bytes) /04bytes-nb=16;4bytes-nb=bytes+2个4字节头，然后对其到8bytes checked_request2size(bytes, nb); /如果在fastbin中有可用的块直接从fastbin中分配 if (unsigned long)(nb) max_fast) fb = &(av-fastbins(fastbin_index(nb); if ( (victim = *fb) != 0) /静态变量成员fastbin初始化为0 *fb = victim-fd; check_remalloced_chunk(victim, nb); return chunk2mem(victim); /如果是first_chunk-chunk-chunk-.-last_chunk | / -| */ /按上图将victim从链表中删除,设置victim的下一块的pbit=inuse /将victim块返回给应用 return chunk2mem(victim); else /512bytes,先释放fastbin中的块 idx = largebin_index(nb); if (have_fastchunks(av) /初始化的时候静态变量0，这个条件成立， malloc_consolidate(av); /合并fastbin中的chunk,放入unsorted_bin /这里是唯一将chunks放入bin的地方 /处理最近被释放或剩余的chunks，如果上次小请求没有完全匹配 /分割出小chunk就会发生 /最外面的for(;)需要，因为我们无法知道在malloc结束前有合并操作 /因此需要多尝试一次，最多多循环一次 for(;) /* unsorted chunks，所有的从一个chunk中分割出来的剩余chunk首先放到 unsorted chunks链表中，下次malloc调用中有一次被再次使用的机会。 作为一个队列维护。 当free或malloc_consolidate函数中 将剩余chunk放入unsorted chunks链表， 而在malloc函数中被分配或放入其他 正常bin中。 */ /循环unsorted中每一块，与插入顺序相反，从后面开始匹配查找 while ( (victim = unsorted_chunks(av)-bk) != unsorted_chunks(av) bck = victim-bk;/victim:unsorteds last chunk;bck:unsorteds last-two chunk size = chunksize(victim); if (in_smallbin_range(nb) /last_remainder /并且这一块是上一次分割剩下的 & (unsigned long)(size) (unsigned long)(nb + MINSIZE) /剩余的chunk必须大于MINSIZE /分割nb出去，剩余的继续放在reminder和unsorted中 return chunk2mem(victim); /unsorted_bin中多于一块chunk,或者剩余一块但不是上一次分割剩余的 /或者剩余的一块大小太小，继续向下 /把最后一块从unsorted freelist中删除 unsorted_chunks(av)-bk = bck; bck-fd = unsorted_chunks(av); /如果正好完全匹配，则return if (size = nb) set_inuse_bit_at_offset(victim, size); check_malloced_chunk(victim, nb); return chunk2mem(victim); /不是完全匹配就从unsorted_bin移到normal_bin中 if(in_smallbin_range(size) else/注意large-bin中的内存块是有序的,FIFO /end while /对于size) = (unsigned long)(nb) /从后往前找，找到第一个满足请求的 while (unsigned long)(size = chunksize(victim) bk; /如果剩余的大小MINSIZE不进行分割,直接将该块返回给应用 if (remainder_size map说明这个32位中bit后面的bin都是空 /*bit=0?啥意思,index%32=0 index-bit 32 -1 20 1 -2 21 2 -4 22 . 31 - 231 */ if (bit map | bit = 0) /bit怎么会是0? /从下一个32开始 do if (+block = BINMAPSIZE) /* out of bins */ goto use_top; /所有bin都找完了还没找到,跳到下面use_top while ( (map = av-binmapblock) = 0); bin = bin_at(av, (block BINMAPSHIFT); bit = 1;/从第一位开始 /. /如果找到一块满足的，将该块进行分割 /如果剩余的大小MINSIZE不进行分割,直接将该块返回给应用 if (remainder_size = (unsigned long)(nb + MINSIZE) return chunk2mem(victim); /上面入口处如果请求512bytes会触发合并fastbin /在这里:如果fastbins无法满足,smallbins也无法满足, /而后合并fastbins放入unsorted_bins, /对于大块再到unsorted_bins找,如果没有精确匹配放入normal_bin /然后再到normal_bins找best-fit /如果还没找到，扩展top /由此可知，如果请求smallsize，则不会触发上述合并fastbins， /然后会触发到unsorted_bins查找，只有一块上次剩余的小块才会 /被分配，或者精确匹配，否则放入normal_bins /然后不管larger或small都到normal_bins中查找 /所以在这里对fastbins合并再尝试一次 else if (have_fastchunks(av) assert(in_smallbin_range(nb); malloc_consolidate(av); idx = smallbin_index(nb); /* restore original bin index */ else /top也没法满足，向OS扩展内存 return sYSMALLOc(nb, av); /最外层的for(;) /endsYSMALLOc函数用于合并fastbin中的空闲内存块，是doug lea malloc(dlmalloc)重要的函数之一。本文以dlmalloc2.7.0版本为基础，先以伪代码的形式介绍sYSMALLOc函数的主要流程。 / 当malloc无法满足nb bytes大小请求时，调用sysmalloc向OS获取更多内存，因此av-top将被扩展static Void_t* sYSMALLOc(INTERNAL_SIZE_T nb, mstate av)#if HAVE_MMAP /如果定义此宏,默认是定义了的,doug lea为windows也实现了一个模拟版本 /如果请求的大小nb达到了mmap分配阀值,并且通过mmap申请的内存块个数没有达到参数设置的上限 if (unsigned long)(nb) = (unsigned long)(av-mmap_threshold) &(av-n_mmaps n_mmaps_max) /调整分配大小,多分配8+4个字节,并按pagesize对齐 size = (nb + SIZE_SZ + MALLOC_ALIGN_MASK + pagemask) & pagemask; /调用mmap获得内存 mm = (char*)(MMAP(0, size, PROT_READ|PROT_WRITE, MAP_PRIVATE); if(mm)/如果mmap分配成功 return chunk2mem(p);/将mmap获得内存返回给应用 /mmap如果失败,继续向下 #endif /*没有mmap可用,或mmap不成功,或size每到达mapp阀值,则需要调整top*/ /将原来由top内存块信息记录下来 old_top = av-top; old_size = chunksize(old_top); old_end = (char*)(chunk_at_offset(old_top, old_size); /调整请求的size size = nb + av-top_pad + MINSIZ; /*如果空间连续,先减去已经存在的top空间,再向操作系统申请*/ if (contiguous(av) size -= old_size; /调用sbrk向OS要求扩展heap空间 brk = (char*)(MORECORE(size); /如果有mmap继续尝试通过mmap分配空间#if HAVE_MMAP if (brk = (char*)(MORECORE_FAILURE) /不能和原来的brk分配空间连续了,单独分配,把之前的size修正 if (contiguous(av) size = (size + old_size + pagemask) & pagemask; /调用mmap申请空间 brk = (char*)(MMAP(0, size, PROT_READ|PROT_WRITE, MAP_PRIVATE); /mmap申请成功 if (brk != (char*)(MORECORE_FAILURE) snd_brk = brk + size;/记录申请得到的内存块尾部地址 /因为通过mmap扩展空间了,记录标记为top不再是连续的了 set_noncontiguous(av); #endif /如果是通过brk扩展内存成功的,则扩展top空间 if (brk = old_end & snd_brk = (char*)(MORECORE_FAILURE) set_head(old_top, (size + old_size) | PREV_INUSE); else/否则,即通过mmap(brk备份)分配成功的内存;或调用malloc之间有其他人调用了brk /这时候需要调整top相关信息 front_misalign = 0; end_misalign = 0; correction = 0; aligned_brk = brk; if (contiguous(av) /调用malloc之间有其他人调用了brk /brk内存头部按8bytes对齐 front_misalign = (INTERNAL_SIZE_T)chunk2mem(brk) & MALLOC_ALIGN_MASK; /将原来top剩余的size,算到新的brk扩展的空间内,多申请这么大 correction += old_size; /brk内存尾部按pagesize对齐 end_misalign = (INTERNAL_SIZE_T)(brk + size + correction); /计算因为头部对齐,和尾部对齐需要的额外空间大小 correction += (end_misalign + pagemask) & pagemask) - end_misalign; /多向操作系统申请因为对齐需要的内存 snd_brk = (char*)(MORECORE(correction); else /mmap分配的内存 /通过mmap扩展的内存,snd_brk指向mmap内存快的尾部 /通过mmap分配的不连续,在mmap请求前就已经按页对齐,所以这里不需要再调整对齐了 if (snd_brk = (char*)(MORECORE_FAILURE) snd_brk = (char*)(MORECORE(0); /av-top指向新扩展的头部,设置top-size /av-top可能是原有top的扩展(连续)(这种情况不进这个分支) /也可能是原来的top-size移过去,新的一块brk空间,与原来的不连续 /还有可能是来自一块mmap的空间头部 av-top = (mchunkptr)aligned_brk; set_head(av-top, (snd_brk - aligned_brk + correction) | PREV_INUSE); av-sbrked_mem += correction; /*如果不是第一次调用sysmalloc,程序走到这里说明通过mmap扩展,或中间有插入的brk 因此需要在原来的top后面插入边界,放上上面的top中合并操作合并了非自己管理的内存*/ if (old_size != 0) /!=0说明不是第一次执行到这里 /插入边界标志块 chunk_at_offset(old_top, old_size)-size = SIZE_SZ|PREV_INUSE; /插入边界标志块 chunk_at_offset(old_top, old_size + SIZE_SZ)-size = SIZE_SZ|PREV_INUSE; /如果老的top空间还比较大,将其释放 if (old_size = MINSIZE) fREe(chunk2mem(old_top); p = av-top; size = chunksize(p); /从top分配一块nb大小的内存快满足应用需要 remainder_size = size - nb; remainder = chunk_at_offset(p, nb); av-top = remainder; set_head(p, nb | PREV_INUSE);/最顶部着一块的p-bit肯定要设为inuse set_head(remainder, remainder_size | PREV_INUSE); return chunk2mem(p);consolidate_fastbin函数用于合并fastbin中的空闲内存块，是doug lea malloc(dlmalloc)重要的函数之一。本文以dlmalloc2.7.0版本为基础，先以伪代码的形式介绍consolidate_fastbin函数的主要流程。void dlmalloc_consolidate