malloc实现的方式有哪些？这篇文章运用了实例代码展示，代码非常详细，可供感兴趣的小伙伴们参考借鉴，希望对大家有所帮助。

方式1：K&R malloc

又叫做first-fit规则, 即查找第一个可用的匹配块。与之相对应的是查找第一个最符合（best-fit）的可用块。
K&R malloc的实现来自书籍 the C programming language by Kernighan and Ritchie (K&R) Section 8.7

维持的free list是一个环。 第一个元素是base。

#defineNALLOC1024/*minimum#unitstorequest*/structheader{structheader*ptr;size_tsize;};typedefstructheaderHeader;staticHeaderbase;staticHeader*freep=NULL;内存分配

指定分配的内存大小为sizeof(Header)的倍数，且一定大于nbytes。nunits就是这个倍数。

循环free list。 找到第一个符合即大于等于nbytes的块。
— 如果刚好合适，则链表删除此块并返回此块。
— 如果大于，则截断此元素
— 如果没有找到合适的块，则调用moreheap新分配一个。

/*malloc:general-purposestorageallocator*/void*kr_malloc(size_tnbytes){Header*p,*prevp;unsignednunits;nunits=(nbytes+sizeof(Header)-1)/sizeof(Header)+1;//base作为第一个元素。if((prevp=freep)==NULL){/*nofreelistyet*/base.ptr=freep=prevp=&base;base.size=0;}for(p=prevp->ptr;;prevp=p,p=p->ptr){if(p->size>=nunits){/*bigenough*/if(p->size==nunits)/*exactly*/prevp->ptr=p->ptr;else{/*allocatetailend*/p->size-=nunits;p+=p->size;p->size=nunits;}freep=prevp;return(void*)(p+1);}if(p==freep){/*wrappedaroundfreelist*/if((p=(Header*)moreheap(nunits))==NULL){returnNULL;/*noneleft*/}}}}sbrk

sbrk是unix增加内存的操作系统调用。
wiki的解释是：

Thebrkandsbrkcallsdynamicallychangetheamountofspaceallocatedforthedatasegmentofthecallingprocess.Thechangeismadebyresettingtheprogrambreakoftheprocess,whichdeterminesthemaximumspacethatcanbeallocated.Theprogrambreakistheaddressofthefirstlocationbeyondthecurrentendofthedataregion.Theamountofavailablespaceincreasesasthebreakvalueincreases.Theavailablespaceisinitializedtoavalueofzero,unlessthebreakisloweredandthenincreased,asitmayreusethesamepagesinsomeunspecifiedway.Thebreakvaluecanbeautomaticallyroundeduptoasizeappropriateforthememorymanagementarchitecture.[4]Uponsuccessfulcompletion,thebrksubroutinereturnsavalueof0,andthesbrksubroutinereturnsthepriorvalueoftheprogrambreak(iftheavailablespaceisincreasedthenthispriorvaluealsopointstothestartofthenewarea).Ifeithersubroutineisunsuccessful,avalueof−1isreturnedandtheerrnoglobalvariableissettoindicatetheerror.

由于这里是增加内存，sbrk成功时会返回新增加区域的开始地址，如果失败则会返回-1。
新生成一个块之后，调用free函数将其加入到freelist当中。
注意这里的up+1 是什么意思。其代表的是新分配的区域的开头。以为新分配的区域之前有Header大小，用于标识大小和下一个区域。

staticHeader*moreheap(size_tnu){char*cp;Header*up;if(nu<NALLOC)nu=NALLOC;cp=sbrk(nu*sizeof(Header));if(cp==(char*)-1)returnNULL;up=(Header*)cp;up->size=nu;kr_free((void*)(up+1));returnfreep;}free

ap是要释放的区域，其前面还有Header大小。bp 指向了块的开头。

遍历free list，找到要插入的中间区域。

如果前后的区域正好是连在一起的，则进行合并。

/*free:putblockapinfreelist*/voidkr_free(void*ap){Header*bp,*p;if(ap==NULL)return;bp=(Header*)ap-1;/*pointtoblockheader*/for(p=freep;!(bp>p&&bp<p->ptr);p=p->ptr)if(p>=p->ptr&&(bp>p||bp<p->ptr))break;/*freedblockatstartorendofarena*/if(bp+bp->sizfe==p->ptr){/*jointouppernbr*/bp->size+=p->ptr->size;bp->ptr=p->ptr->ptr;}else{bp->ptr=p->ptr;}if(p+p->size==bp){/*jointolowernbr*/p->size+=bp->size;p->ptr=bp->ptr;}else{p->ptr=bp;}freep=p;}方式2：Region-based allocator, a special-purpose allocator.

malloc 与free 快速

内存开销低

内存碎片严重

不通用，用于特定应用程序。

structregion{void*start;void*cur;void*end;};typedefstructregionRegion;staticRegionrg_base;Region*rg_create(size_tnbytes){rg_base.start=sbrk(nbytes);rg_base.cur=rg_base.start;rg_base.end=rg_base.start+nbytes;return&rg_base;}void*rg_malloc(Region*r,size_tnbytes){assert(r->cur+nbytes<=r->end);void*p=r->cur;r->cur+=nbytes;returnp;}//freeallmemoryinregionresettingcurtostartvoidrg_free(Region*r){r->cur=r->start;}方式3：Buddy allocator

我觉得wiki的解释挺好的：
wiki解析
提示：

对于2^k 大小的空间，我们可以将其分割为大小为2^0, 2^1, 2^2, … 2^k的多种可能。

malloc(17) 会分配 32 bytes，因此其会一定程度上浪费空间。

数据结构带来的格外内存开销

malloc 和free快速。

下面介绍一种代码实现。

基本参数

ROUNDUP(n,sz) 求出要分配n哥字节时，希望分配的实际内存是大于等于n 并且是sz的倍数。

#defineLEAF_SIZE16//Thesmallestallocationsize(inbytes)#defineNSIZES15//Numberofentriesinbd_sizesarray#defineMAXSIZE(NSIZES-1)//Largestindexinbd_sizesarray#defineBLK_SIZE(k)((1L<<(k))*LEAF_SIZE)//Sizeinbytesforsizek#defineHEAP_SIZEBLK_SIZE(MAXSIZE)#defineNBLK(k)(1<<(MAXSIZE-k))//Numberofblockatsizek#defineROUNDUP(n,sz)(((((n)-1)/(sz))+1)*(sz))//Rounduptothenextmultipleofsz

NBLK求出在第k位置有多少块。

每一个大小k维护一个sz_info,sz_info中都有一个free list, alloc 是一个char数组用于记录块是否分配。split 是一个char数组用于块是否割裂。
这里要注意，使用的是bit数组来记录。 char有8位，如第n位代表的是当前k大小的第5个区块。

//Theallocatorhassz_infoforeachsizek.Eachsz_infohasafree//list,anarrayalloctokeeptrackwhichblockshavebeen//allocated,andansplitarraytotokeeptrackwhichblockshave//beensplit.Thearraysareoftypechar(whichis1byte),butthe//allocatoruses1bitperblock(thus,onecharrecordstheinfoof//8blocks).structsz_info{structbd_listfree;char*alloc;char*split;};typedefstructsz_infoSz_info;

每一个级别的双链表 for free list

//Adouble-linkedlistforthefreelistofeachlevelstructbd_list{structbd_list*next;structbd_list*prev;};bit数组操作

//Return1ifbitatpositionindexinarrayissetto1intbit_isset(char*array,intindex){charb=array[index/8];charm=(1<<(index%8));return(b&m)==m;}//Setbitatpositionindexinarrayto1voidbit_set(char*array,intindex){charb=array[index/8];charm=(1<<(index%8));array[index/8]=(b|m);}//Clearbitatpositionindexinarrayvoidbit_clear(char*array,intindex){charb=array[index/8];charm=(1<<(index%8));array[index/8]=(b&~m);}初始化

首先调用mmap分配一个非常大的区域。此大小为2 ^ MAXSIZE * 16,16为分配的最小块。

//Allocatememoryfortheheapmanagedbytheallocator,andallocate//memoryforthedatastructuresoftheallocator.voidbd_init(){bd_base=mmap(NULL,HEAP_SIZE,PROT_READ|PROT_WRITE,MAP_PRIVATE|MAP_ANONYMOUS,-1,0);if(bd_base==MAP_FAILED){fprintf(stderr,"couldn'tmapheap;%s\n",strerror(errno));assert(bd_base);}//printf("bd:heapsize%d\n",HEAP_SIZE);for(intk=0;k<NSIZES;k++){lst_init(&bd_sizes[k].free);intsz=sizeof(char)*ROUNDUP(NBLK(k),8)/8;bd_sizes[k].alloc=malloc(sz);memset(bd_sizes[k].alloc,0,sz);}for(intk=1;k<NSIZES;k++){intsz=sizeof(char)*ROUNDUP(NBLK(k),8)/8;bd_sizes[k].split=malloc(sz);memset(bd_sizes[k].split,0,sz);}lst_push(&bd_sizes[MAXSIZE].free,bd_base);}找到第一个k， 使得2^k >= n

//Whatisthefirstksuchthat2^k>=n?intfirstk(size_tn){intk=0;size_tsize=LEAF_SIZE;while(size<n){k++;size*=2;}returnk;}查找位置p ， 如果以2^k 大小为区块，那么其位于第几个区块。

//Computetheblockindexforaddresspatsizekintblk_index(intk,char*p){intn=p-(char*)bd_base;returnn/BLK_SIZE(k);}将k大小，序号为bi的区块的首地址计算出来

//Convertablockindexatsizekbackintoanaddressvoid*addr(intk,intbi){intn=bi*BLK_SIZE(k);return(char*)bd_base+n;}malloc

找到一个大小k，块2^k是大于等于要分配的大小。
如果db_size[k].free 不为空，说明当前有大小为k的空闲空间。
如果没有找到，则让k+1，继续找到更大的空间有无空闲。

如果找到，则lst_pop(&bd_sizes[k].free)获取第一个块。 blk_index(k, p)获取以k为衡量指标，p位于的第n个块。 并通过bit_set将bd_sizes[k].alloc 在第n号位置设置为1。
如果找到的k是比较大的空间，这时候需要对此空间进行分割，一分为2。 一直到找到一个比较符合的空间。

void*bd_malloc(size_tnbytes){intfk,k;assert(bd_base!=NULL);//Findafreeblock>=nbytes,startingwithsmallestkpossiblefk=firstk(nbytes);for(k=fk;k<NSIZES;k++){if(!lst_empty(&bd_sizes[k].free))break;}if(k>=NSIZES)//Nofreeblocks?returnNULL;//Foundone;popitandpotentiallysplitit.char*p=lst_pop(&bd_sizes[k].free);bit_set(bd_sizes[k].alloc,blk_index(k,p));for(;k>fk;k--){//第2半的空间char*q=p+BLK_SIZE(k-1);//对于大小k来说，其在位置p处是分割的。bit_set(bd_sizes[k].split,blk_index(k,p));//对于大小k-1来说，其在位置p处是分配的。bit_set(bd_sizes[k-1].alloc,blk_index(k-1,p));//对于大小k-1来说，其在位置q处是空闲的。lst_push(&bd_sizes[k-1].free,q);}//printf("malloc:%psizeclass%d\n",p,fk);returnp;}free

当要free位置p时，size找到第一个k，当k+1在p位置是分割的，则返回k。这时候说明在k处区域是可以合并的。这是一种优化。
// Find the size of the block that p points to. int size(char *p) { for (int k = 0; k < NSIZES; k++) { if(bit_isset(bd_sizes[k+1].split, blk_index(k+1, p))) { return k; } } return 0; }

voidbd_free(void*p){void*q;intk;for(k=size(p);k<MAXSIZE;k++){intbi=blk_index(k,p);bit_clear(bd_sizes[k].alloc,bi);intbuddy=(bi%2==0)?bi+1:bi-1;if(bit_isset(bd_sizes[k].alloc,buddy)){break;}//budyisfree;mergewithbuddyq=addr(k,buddy);lst_remove(q);if(buddy%2==0){p=q;}bit_clear(bd_sizes[k+1].split,blk_index(k+1,p));}//放入freelist当中。//printf("free%p@%d\n",p,k);lst_push(&bd_sizes[k].free,p);}环形双链表的基本操作

//Implementationoflists:double-linkedandcircular.Double-linked//makesremovefast.Circularsimplifiescode,becausedon'thaveto//checkforemptylistininsertandremove.voidlst_init(Bd_list*lst){lst->next=lst;lst->prev=lst;}intlst_empty(Bd_list*lst){returnlst->next==lst;}voidlst_remove(Bd_list*e){e->prev->next=e->next;e->next->prev=e->prev;}void*lst_pop(Bd_list*lst){assert(lst->next!=lst);Bd_list*p=lst->next;lst_remove(p);return(void*)p;}voidlst_push(Bd_list*lst,void*p){Bd_list*e=(Bd_list*)p;e->next=lst->next;e->prev=lst;lst->next->prev=p;lst->next=e;}voidlst_print(Bd_list*lst){for(Bd_list*p=lst->next;p!=lst;p=p->next){printf("%p",p);}printf("\n");}其他顺序分配方式

*dlmalloc*slaballocator

以上就是malloc实现的几种方式的详细介绍内容了，看完之后是否有所收获呢？如果想了解更多相关内容，欢迎关注亿速云行业资讯！