malloc函数的用法，malloc内存分配原理-励北网

3.2.5 malloc的实现

有了上面的代码，我们可以利用它们整合成一个简单但初步可用的malloc。注意首先我们要定义个block链表的头first_block，初始化为NULL；另外，我们需要剩余空间至少有BLOCK_SIZE + 8才执行分裂操作。

由于我们希望malloc分配的数据区是按8字节对齐，所以在size不为8的倍数时，我们需要将size调整为大于size的最小的8的倍数：

size_talign8(size_ts){if(s&0x7==0)returns;return((s>>3)+1)<<3;}

#defineBLOCK_SIZE24void*first_block=NULL;/*otherfunctions...*/void*malloc(size_tsize){t_blockb,last;size_ts;/*对齐地址*/s=align8(size);if(first_block){/*查找合适的block*/last=first_block;b=find_block(&last,s);if(b){/*如果可以，则分裂*/if((b->size-s)>=(BLOCK_SIZE+8))split_block(b,s);b->free=0;}else{/*没有合适的block，开辟一个新的*/b=extend_heap(last,s);if(!b)returnNULL;}}else{b=extend_heap(NULL,s);if(!b)returnNULL;first_block=b;}returnb->data;}

3.2.6 calloc的实现

有了malloc，实现calloc只要两步：

malloc一段内存
将数据区内容置为0

由于我们的数据区是按8字节对齐的，所以为了提高效率，我们可以每8字节一组置0，而不是一个一个字节设置。我们可以通过新建一个size_t指针，将内存区域强制看做size_t类型来实现。

void*calloc(size_tnumber,size_tsize){size_t*new;size_ts8,i;new=malloc(number*size);if(new){s8=align8(number*size)>>3;for(i=0;i<s8;i++)new[i]=0;}returnnew;}

3.2.7 free的实现

free的实现并不像看上去那么简单，这里我们要解决两个关键问题：

如何验证所传入的地址是有效地址，即确实是通过malloc方式分配的数据区首地址
如何解决碎片问题

首先我们要保证传入free的地址是有效的，这个有效包括两方面：

地址应该在之前malloc所分配的区域内，即在first_block和当前break指针范围内
这个地址确实是之前通过我们自己的malloc分配的

第一个问题比较好解决，只要进行地址比较就可以了，关键是第二个问题。

这里有两种解决方案：一是在结构体内埋一个magic number字段，free之前通过相对偏移检查特定位置的值是否为我们设置的magic number，另一种方法是在结构体内增加一个magic pointer，这个指针指向数据区的第一个字节（也就是在合法时free时传入的地址），我们在free前检查magic pointer是否指向参数所指地址。这里我们采用第二种方案：

首先我们在结构体中增加magic pointer（同时要修改BLOCK_SIZE）：

typedefstructs_block*t_block;structs_block{size_tsize;/*数据区大小*/t_blocknext;/*指向下个块的指针*/intfree;/*是否是空闲块*/intpadding;/*填充4字节，保证meta块长度为8的倍数*/void*ptr;/*Magicpointer，指向data*/chardata[1]/*这是一个虚拟字段，表示数据块的第一个字节，长度不应计入meta*/};

然后我们定义检查地址合法性的函数：

t_blockget_block(void*p){char*tmp;tmp=p;return(p=tmp-=BLOCK_SIZE);}intvalid_addr(void*p){if(first_block){if(p>first_block&&p

当多次malloc和free后，整个内存池可能会产生很多碎片block，这些block很小，经常无法使用，甚至出现许多碎片连在一起，虽然总体能满足某此malloc要求，但是由于分割成了多个小block而无法fit，这就是碎片问题。

一个简单的解决方式时当free某个block时，如果发现它相邻的block也是free的，则将block和相邻block合并。为了满足这个实现，需要将s_block改为双向链表。修改后的block结构如下：

typedefstructs_block*t_block;structs_block{size_tsize;/*数据区大小*/t_blockprev;/*指向上个块的指针*/t_blocknext;/*指向下个块的指针*/intfree;/*是否是空闲块*/intpadding;/*填充4字节，保证meta块长度为8的倍数*/void*ptr;/*Magicpointer，指向data*/chardata[1]/*这是一个虚拟字段，表示数据块的第一个字节，长度不应计入meta*/};

合并方法如下：

t_blockfusion(t_blockb){if(b->next&&b->next->free){b->size+=BLOCK_SIZE+b->next->size;b->next=b->next->next;if(b->next)b->next->prev=b;}returnb;}

有了上述方法，free的实现思路就比较清晰了：首先检查参数地址的合法性，如果不合法则不做任何事；否则，将此block的free标为1，并且在可以的情况下与后面的block进行合并。

如果当前是最后一个block，则回退break指针释放进程内存，如果当前block是最后一个block，则回退break指针并设置first_block为NULL。实现如下：

voidfree(void*p){t_blockb;if(valid_addr(p)){b=get_block(p);b->free=1;if(b->prev&&b->prev->free)b=fusion(b->prev);if(b->next)fusion(b);else{if(b->prev)b->prev->prev=NULL;elsefirst_block=NULL;brk(b);}}}3.2.8 realloc的实现

为了实现realloc，我们首先要实现一个内存复制方法。如同calloc一样，为了效率，我们以8字节为单位进行复制：

voidcopy_block(t_blocksrc,t_blockdst){size_t*sdata,*ddata;size_ti;sdata=src->ptr;ddata=dst->ptr;for(i=0;(i*8)

然后我们开始实现realloc。一个简单（但是低效）的方法是malloc一段内存，然后将数据复制过去。但是我们可以做的更高效，具体可以考虑以下几个方面：

如果当前block的数据区大于等于realloc所要求的size，则不做任何操作
如果新的size变小了，考虑split
如果当前block的数据区不能满足size，但是其后继block是free的，并且合并后可以满足，则考虑做合并

下面是realloc的实现：

void*realloc(void*p,size_tsize){size_ts;t_blockb,new;void*newp;if(!p)/*根据标准库文档，当p传入NULL时，相当于调用malloc*/returnmalloc(size);if(valid_addr(p)){s=align8(size);b=get_block(p);if(b->size>=s){if(b->size-s>=(BLOCK_SIZE+8))split_block(b,s);}else{/*看是否可进行合并*/if(b->next&&b->next->free&&(b->size+BLOCK_SIZE+b->next->size)>=s){fusion(b);if(b->size-s>=(BLOCK_SIZE+8))split_block(b,s);}else{/*新malloc*/newp=malloc(s);if(!newp)returnNULL;new=get_block(newp);

copy_block(b,new);free(p);return(newp);}}return(p);}returnNULL;}

3.3 遗留问题和优化

以上是一个较为简陋，但是初步可用的malloc实现。还有很多遗留的可能优化点，例如：

同时兼容32位和64位系统
在分配较大快内存时，考虑使用mmap而非sbrk，这通常更高效
可以考虑维护多个链表而非单个，每个链表中的block大小均为一个范围内，例如8字节链表、16字节链表、24-32字节链表等等。此时可以根据size到对应链表中做分配，可以有效减少碎片，并提高查询block的速度
可以考虑链表中只存放free的block，而不存放已分配的block，可以减少查找block的次数，提高效率

还有很多可能的优化，这里不一一赘述。下面附上一些参考文献，有兴趣的同学可以更深入研究。

4 其它参考

这篇文章大量参考了A malloc Tutorial^[7]，其中一些图片和代码直接引用了文中的内容，这里特别指出
Computer Systems: A Programmer's Perspective, 2/E^[8]一书有许多值得参考的地方
关于Linux的虚拟内存模型，Anatomy of a Program in Memory^[9]是很好的参考资料，另外作者还有一篇How the Kernel Manages Your Memory^[10]对于Linux内核中虚拟内存管理的部分有很好的讲解
对于真实世界的malloc实现，可以参考glibc的实现^[11]
本文写作过程中大量参考了维基百科^[12]，再次感谢这个伟大的网站，并且呼吁大家在手头允许的情况下可以适当捐助维基百科，帮助这个造福人类的系统运行下去