最新个人博客shankusu.me
以下内容转载或参考或引用自
/zxx910509/article/details/62881131
一、malloc/free概述
malloc是在C语言中用于在程序运行时在堆中进行动态内存分配的库函数。free是进行内存释放的库函数。
1、函数原型
[cpp]view plaincopy#include<stdlib.h>void*malloc(size_tsize); [cpp]view plaincopyvoidfree(void*memblock);
2、返回值
成功时，返回所分配存储空间的起始地址；返回值类型为void*,在C语言中可以把void*直接付给具体的类型，但是在C++中必须进行强制类型转换
失败时(内存不足时)返回NULL
size为0时，返回的指针不是NULL；但是除了free，别的地方不要使用这个指针。
3、使用示例
[cpp]view plaincopy#include<stdlib.h>/*For_MAX_PATHdefinition*/#include<stdio.h>#include<malloc.h>voidmain(void){char*string;/*Allocatespaceforapathname*/string=malloc(_MAX_PATH);//InaC++file,explicitlycastmalloc'sreturn.Forexample,//string=(char*)malloc(_MAX_PATH);if(string==NULL)printf("Insufficientmemoryavailable\n");else{printf("Memoryspaceallocatedforpathname\n");free(string);printf("Memoryfreed\n");}}
二、malloc实际分配的内存大小
malloc实际分配的内存会大于我们需要的size。主要由两方面因素决定：
1、字节对齐。会对齐到机器最受限的类型（具体的实现因机器而异）。
2、“块头部信息”。每个空闲块都有“头部”控制信息，其中包含一个指向链表中下一个块的指针、当前块的大小和一个指向本身的指针。为了简化块对齐，所有块的大小都必须是头部大小的整数倍，且头部已正确对齐。
在VC平台下由_CrtMemBlockHeader结构体实现。
以下为《C程序设计语言》中给出的通过union进行的头部实现，其中假定机器的受限类型为long。
[cpp]view plaincopytypedeflongAlign;/*按照long类型的边界对齐*/unionheader/*块的头部*/{struct{unionheader*ptr;/*空闲块链表中的下一块*/unsignedsize;/*本块的大小*/}s;Alignx;/*强制块对齐*/};
说明：
（1）实际分配的内存块将多一个单元，用于头部本身。实际分配的块的大小被记录在头部的size字段中。
（2）size字段是必须的，因为malloc函数控制的块不一定是连续的，这样就不能通过指针算术运算计算其大小。
（3）malloc返回的是空闲块的首地址，而不是首地址。
三、malloc/free实现过程
1、空闲存储空间以空闲链表的方式组织（地址递增），每个块包含一个长度、一个指向下一块的指针以及一个指向自身存储空间的指针。（因为程序中的某些地方可能不通过malloc调用申请，因此malloc管理的空间不一定连续。）
2、当有申请请求时，malloc会扫描空闲链表，直到找到一个足够大的块为止（首次适应）(因此每次调用malloc时并不是花费了完全相同的时间）。
3、如果该块恰好与请求的大小相符，则将其从链表中移走并返回给用户。如果该块太大，则将其分为两部分，尾部的部分分给用户，剩下的部分留在空闲链表中（更改头部信息）。因此malloc分配的是一块连续的内存。
4、释放时，首先搜索空闲链表，找到可以插入被释放块的合适位置。如果与被释放块相邻的任一边是一个空闲块，则将这两个块合为一个更大的块，以减少内存碎片。
四、实现
以下为《C语言程序设计语言》中给出的一种实现方法
1、malloc的实现
[cpp]view plaincopytypedefunionheaderHeader;staticHeaderbase;/*从空链表开始*/staticHeader*freep=NULL;/*空闲链表的初始指针*/void*malloc(unsignednbytes){Header*p,*prevp;Header*morecore(unsigned);unsignednunits;nunits=(nbytes+sizeof(Header)-1)/sizeof(Header)+1;if((prevp=freep)==NULL)/*没有空闲链表*/{base.s.ptr=freep=prevp=&base;base.s.size=0;}for(p=prevp->s.ptr;;prevp=p,p=p->s.ptr){if(p->s.size>=nunits)/*足够大*/{if(p->s.size==nunits)/*正好*/prevp->s.ptr=p->s.ptr;else/*分配末尾部分*/{p->s.size-=nunits;p+=p->s.size;p->s.size=nunits;}freep=prevp;return(void*)(p+1);}if(p==freep)/*闭环的空闲链表*/if((p=morecore(nunits))==NULL)returnNULL;/*没有剩余的存储空间*/}}
说明：
（1）malloc实际分配的空间是Header大小的整数倍，并且多出一个Header空间用于放置Header
（2）式nunits = (nbytes+sizeof(Header)-1)/sizeof(Header) + 1中的减1是为了防止(nbytes+sizeof(Header))%sizeof(Header) == 0时，多分配了一个Header大小的空间
（3）第一次调用malloc函数时，freep为NULL，系统将创建一个退化的空闲链表，它只包含一个大小为0的块，且该块指向自己。任何时候，当请求空闲空间时，都将搜索空闲块链表。搜索从上一次找到空闲块的地方（freep）开始。该策略可以保证链表是均匀的。如果找到的块太大，则将其尾部返回给用户，这样，初始块的头部只需要修改size字段即可。
（4）任何时候，返回给用户的指针都指向块内的空闲存储空间，即比指向头部的指针大一个单元。
（5）sbrk不是系统调用，是C库函数。sbrk/brk是从堆中分配空间，本质是移动一个位置，向后移就是分配空间，向前移就是释放空间，sbrk用相对的整数值确定位置，如果这个整数是正数，会从当前位置向后移若干字节，如果为负数就向前若干字节。在任何情况下，返回值永远是移动之前的位置。在LINUX中sbrk(0)能返回比较精确的虚拟内存使用情况。链接：sbrk()/brk()--改变数据长度
（6）链接:brk()分配过程
2、morecore的实现
函数morecore用来向操作系统请求存储空间，其实现细节因系统的不同而不同。因为向系统请求存储空间是一个开销很大的操作，因此我们不希望每次调用malloc时都执行该操作，基于这个考虑，morecore函数请求至少NALLOC个单元。这个较大的块将根据需要分成较小的块。在设置完size字段后，morecore函数调用free函数把多余的存储空间插入到空闲区域中。
[cpp]view plaincopy#defineNALLOC1024/*最小申请单元数*/staticHeader*morecore(unsignednu){char*cp;Header*up;if(nu<NALLOC)nu=NALLOC;cp=sbrk(nu*sizeof(Header));if(cp==(char*)-1)/*没有空间*/returnNULL;up=(Header*)cp;up->s.size=nu;free((void*)(up+1));returnfreep;}
说明：
（1）没有存储空间时sbrk调用返回-1.因此需要将-1强制类型转换为char*类型，以便 与返回值进行比较。而且，强制类型转换使得函数不会受不同机器中指针表示的不同的影响。
3、free的实现
free函数从freep指向的地址开始，逐个扫描空闲链表，寻找可以插入空闲块的地方。该位置可能在链表的末尾或者两个空闲块之间。在任何一种情况下，如果被释放的块与另一空闲块相邻，则将这两个块合并。
[cpp]view plaincopyvoidfree(void*ap){Header*bp,*p;bp=(Header*)ap-1;/*指向块头*/for(p=freep;!(bp>p&&bp<p->s.ptr);p=p->s.ptr)if(p>=p->s.ptr&&(bp>p||bp<p->s.ptr))break;/*被释放的块在链表的开头或结尾*/if(bp+bp->s.size==p->s.ptr)/*与上一相邻块合并*/{bp->s.size+=p->s.ptr->s.size;bp->s.ptr=p->s.ptr->s.ptr;}elsebp->s.ptr=p->s.ptr;if(p+p->s.size==bp)/*与下一相邻块合并*/{p->s.size+=bp->s.size;p->s.ptr=bp->s.ptr;}elsep->s.ptr=bp;freep=p;}
五、注意事项
链接：malloc/free使用注意事项
参考文献：
1、《C程序设计语言》
2、《C和指针》
3、《C和C++安全编码》
4、链接：如何实现一个malloc
