蓝色企业网站配色,seo搜索引擎实战详解,网站app 开发,网页设计基础知识点任何一个对C稍稍有了解的人都知道malloc、calloc、free。前面两个是用户态在堆上分配一段连续(虚拟地址)的内存空间#xff0c;然后可以通过free释放#xff0c;但是#xff0c;同时也会有很多人对其背后的实现机制不了解。这篇文章则是通过介绍这三个函数#xff0c;并简单…任何一个对C稍稍有了解的人都知道malloc、calloc、free。前面两个是用户态在堆上分配一段连续(虚拟地址)的内存空间然后可以通过free释放但是同时也会有很多人对其背后的实现机制不了解。这篇文章则是通过介绍这三个函数并简单的予以实现对比现有C的标准库实现(glibc等)相比并不是特别高效我们重在阐述背后的基本原理。一、C程序的存储空间布局图1text整个用户空间的最低地址部分存放的是指令(程序所编译成的可执行机器码)。可共享即使是频繁操作执行的程序在存储器中也只需有一个副本通常是只读的。initialized data(data)存放初始化过的全局变量包含了程序中需明确地赋初值的变量。uninitialized data(bss)存放的是未初始化过的全局变量在程序开始执行之前内核将此段中的数据初始化为0或者NULL。heap堆自低地址向高地址增长后面重点剖析stack栈自高地址向低地址增长自动变量以及每次函数调用时所需保存的信息都存放在此段中。二、Heap 内存模型一般来说malloc所申请的内存主要从heap区域分配的。linux内存管理从这里可以了解到linux下虚拟地址与物理地址。linux对堆的管理如下图2linux 内核维护一个break指针这个指针指向堆空间的某个地址。从堆起始地址(Heap’s Start)到break之间的地址空间为映射好的(虚拟地址与物理地址的映射通过MMU实现)可以供进程访问而从break往上是未映射的地址空间如果访问这段空间则程序会报错。所以如果Mapped Region 空间不够时会调整break指针扩大映射空间重新分配内存。三、调整breakbrk()和sbrk()最初break的位置正好位于bss端末尾之后看图1在break指针的位置升高时程序可以访问新分配区域内的任何内存地址而此时物理内存页尚未分配内存会在京城首次试图访问这些虚拟内存地址时自动分配新的物理内存页。linux通过brk和sbrk系统调用操作break指针int brk(void *addr);void *sbrk(intptr_t increment);brk() 将break指针设置为 addr 所指定的位置由于虚拟内存以页为单位进行分配addr实际会四舍五入到下一个内存也的边界处。由于brk是直接指定一个地址所以一旦这个值取得过低有可能导致不可预知的行为对照图1brk只能在指定的区域内调整break。sbrk() 将break指针在原有地址增加从参数 increment 传入的大小(linux中sbrk是基于brk基础上实现的一个库函数)用于声明increment 的intptr_t 类型属于整数数据类型。若调用成功sbrk() 返回前一个break 的地址换言之如果break 增加那么返回值是指向这块新分配内存起始位置的指针。sbrk(0) 将得到当前break指针的位置。系统对每一个进程所分配的资源不是无限的包括可映射的内存空间图2未映射内存的尾端有个rlimit表示当前进程可用的资源上限。三、malloc根据标准C库函数的定义malloc 具有如下模型void* malloc(size_t size);这个函数要实现的功能是在系统中分配一段连续的可用的内存具体有如下要求- malloc分配的内存大小至少为size参数所指定的字节数- malloc的返回值是一个指针指向一段可用内存的起始地址- 多次调用malloc所分配的地址不能有重叠部分除非该地址已经被释放掉- malloc应该尽快完成内存分配并返回(不能使用NP-hard的内存分配算法)- 实现malloc时应该同时实现内存大小调整和内存释放函数(calloc和free)- malloc分配失败时必须返回NULLmalloc 返回内存块所采用的字节对齐方式总是适宜于高效访问任何类型的C语言数据结构。四、初探实现malloc我们假定整个内存处于初始状态即break指针位于bss段的单位整个heap都是 Unmapped Region。(图2)基于此我们可以实现一个简单但毫无实际价值的malloc/*一个糟糕的仿制malloc*/#include #incldue void *malloc(size_t size){void *p;p sbrk(0);/*如果sbrk失败返回NULL*/if(sbrk(size) (void*)-1)return NULL;return p;}这个malloc就是从未映射区域直接划出一块但是malloc对这块已分配的内存缺乏记录不便于内存释放。五、正式实现malloc上面说到分配的内存没有记录一旦调用free释放free不知道它到底要释放多大的内存所以我们需要额外一个数据结构来记录这些信息。5.1、数据结构一个简单可行方案是将堆内存以块的形式组织起来每个块(block)由meta区和数据区组成meta去记录数据块的元信息(数据块大小、空闲标志位、指针等)数据区则是真实分配的内存区域并且数据区的第一个字节地址即为malloc返回的地址。可用如下结构体定义一个blocktypedef struct s_block *t_block;struct s_block{size_t size;//数据区大小t_block next;//指向下个块的指针int free;//是否是空闲块char data[1];//虚拟字段表示数据块的第一个字节长度不计入meta};图3那么用这个结构体来分配内存而不用malloc则是下面一番场景t_block b;b sbrk(0);sbrk(sizeof(struct s_block) size);b-size size;//size 为要分配的内存大小5.2、寻找合适的block我们从堆的起始地址开始查找第一个符合要求的block并返回block起始地址如果找不到就返回NULLt_block find_block(t_block *last, size_t size){t_block b base;while(b !(b-free b-size size)){*last b;b b-next;}return b;}这里base是一个全局变量维护整个堆的起始地址。另外这里在遍历时会更新一个last指针这个指针始终指向当前遍历的block如果找不到合适的block那么malloc将很容易的开辟新的block使用。5.3、开辟新的block如果现有block都不能满足需求则需要在链表最后开辟一个新的block。最简单的方式就是利用sbrk升高break位置然后对其初始化然后更新对应block指针将其add到链表最后。t_block extend_heap(t_block last, size_t size){t_block b;b sbrk(0);//定位到当前break位置if(sbrk(sizeof(struct s_block) size) (void*)-1)//调整break位置return NULL;b-size size;b-next NULL;if(last)//这个last是指向extend之前最后一个blocklast-next b;//新开辟的block挂载在链表中b-free 0;return b;}5.4、分裂block看前面 find_block() 的实现如果我们申请的 size 远小于查找到的 block。(这种情况是可能它是查到第一个满足条件(大小可用)的block)这样会导致较大内部碎片的产生。所以应该在剩余数据区足够大的情况下将其分裂成一个新的block图4//b是要分裂的blocksize是申请的内存大小//分裂后b成了分配后的blockvoid split_block(t_block b, size_t size){t_block new;//新的空闲block 要分裂的block - 申请分配出去的内存new b-data size;//将new定位到剩下的数据块区域//分裂的原block-分配出去的内存大小-block结构体本身大小new-size b-size - size - BLOCK_SIZE;new-next b-next;//链表插入new-free 1;//空闲标记可用b-size size;b-next new;//链表插入}看了上面一大串是不是跟伙伴算法很像。但是这里的分裂block函数得视情况调用如果申请的size block-size但是又不是小太多如果分裂block的话会导致分裂后剩余未分配出去的数据块过小无法满足其余需求很容易形成内存碎片。所以伙伴算法有更高效的处理(实际上伙伴算法也会产生内部碎片)。5.5、malloc 的实现铺垫做了那么多我们可以利用它们整合成一个简单可用的malloc。首先定义一个block链表的头指针初始化为NULL另外我们需要剩余空间至少有 BLOCK_SIZE 4 才执行分离操作。此外一开始我们讲到malloc对分配的内存大小也有要求是按4字节对齐所以申请的size不为4的倍数时我们需要将其调整为大于size的最小的4的倍数。#define align4(x) (((((x)-1)2)2)4)#define BLOCK_SIZE 12void *base NULL;void *malloc(size_t size){t_block b, last;size_t s;s align4(size);if(base){//first find a blocklast base;b find_block(last, s);if(b){//can we splitif((b-size - s) (BLOCK_SIZE 8))split_block(b, s);b-free 0;}else{//no fitting block, extend the heapb extend_heap(last, s);if(!b)return NULL;}}else{//first timeb extend_heap(NULL, s);if(!b)return NULL;base b;}return b-data;}实现思路很简单首先往链表中查找合适的block如果找到了看是否可以分裂如果可以就分裂如果没有找到合适的就开辟一个新的block如果是第一次分配即整个内存链表不存在则一开始就得新开辟一个block。六、calloc 的实现先看calloc的标准库语义函数 calloc() 用于给一组相同对象分配内存。void *calloc(size_t numitems, size_t size)参数numitems指定分配对象的数量size指定每个对象的大小。calloc 与之malloc 不同之处在于calloc 会将分配后的内存空间初始化而malloc 申请的是一块未初始化的内存。所以实现calloc只需两步malloc 一块内存将数据区内容初始化为0void *calloc(size_t numitems, size_t size){size_t *new;size_t s, i;new malloc(numitems * size);if(new){//因为申请的内存总是4的倍数所以这里我们以4字节为单位初始化s align4(numitems * size) 2;for(i 0; i s; i)new[i] 0;}return new;}七、free 的实现free 的实现并不像看上去那么简单需要解决两个关键问题如何验证所传入的地址是有效地址(malloc方式分配的)如何解决碎片问题7.1、先看如何解决碎片问题就是把相邻的空闲内存合并为大的(伙伴算法类似)//合并相邻空闲的内存块参数决定合并的是上一个还是下一个t_block fusion(t_block b){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;}return b;}再看如何验证所传入的地址是有效的位于heap内。一个解决方法是在block结构体中添加一个 ptr 指针用于指向数据块区域如果 b-ptr b-data则表示 b 极有可能是一个有效block。所以我们对block数据结构进行了扩展struct s_block{size_t size;//数据区大小t_block next;//指向下个块的指针int free;//是否是空闲块struct s_block *next;struct s_block *prev;void *ptr;char data[1];};7.2、根据给定地址得到对应的block//注意这个函数最后通过偏移量得到的block可能是有效的可能不是有效的t_block get_block(void *p){char *tmp;tmp p;return (p tmp - BLOCK_SIZE);}7.3、下面则验证是不是有效的blockint valid_addr(void *p){if(base){if(p base p sbrk(0))return (p (get_block(p))-ptr);//如果两个字段地址一样表示是一个有效block}return 0;}7.4、下面就实现free这里我们采用的合并策略是这样的先合并相邻的空闲内存块合并之后再检查是否还有空闲的相邻内存块如果有则继续合并直到最后该内存块是最大的连续内存块。另外对于break指针的调整(降低)必须保证在该释放的block与 Unmapped Region之间是空闲的没有被占。void free(void *p){t_block b;if(valid_addr(p))//地址的有效性验证{b get_block(p);//得到对应的blockb-free 1;//如果相邻的上一块内存是空闲的就合并,//合并之后的上一块还是空闲的就继续合并直到不能合并为止while(b-prev b-prev-free){b fusion(b-prev);}//同理去合并后面的空闲blockwhile(b-next)fusion(b);//内部会判断是否空闲//如果当前block是最后面的那个block此时可以调整break指针了if(NULL b-next){if(b-prev)//当前block前面还有占用的blockb-prev-next NULL;else//当前block就是整个heap仅存的base NULL;//则重置basebrk(b);//调整break指针到b地址位置}//否则不能调整break}}八、realloc的实现同样先看标准库中realloc的语义void *realloc(void *ptr, size_t size)ptr 是指向需要调整大小的内存块的指针参数 size 指定所需调整大小的期望值。realloc() 用来调整(通常是增加)一块内存的大小而此块内存应是之前由malloc函数分配的。若 realloc 增加了已分配内存块的大小则不会对额外分配的内存进行初始化。8.1、内存块复制看了realloc的语义我们首先得实现一个内存复制方法。如同calloc一样我们以4字节为单位进行复制void copy_block(t_block src, t_block dst){int *sdata, *dtata;size_t i;sdata src-ptr;ddata dst-ptr;for(i 0; i*4 src-size i*4 dst-size; i)ddata[i] sdata[i];}8.2、实现realloc为了更高效我们考虑以下几个方面如果当前block的数据区大于等于realloc要求的size则考虑能不能split然后直接返回如果新的size变小了考虑split如果当前block的数据区不能满足size但是其后继block是free并且合并后可以满足size则考虑合并然后再考虑能不能split如果以上都不行则调用malloc重新分配size大小内存然后内存复制void *realloc(void *p, size_t size){size_t s;t_block b, new;void *newp;if(!p)return malloc(size);if(valid_addr(p)){s align4(size);b get_block(p);//得到对应的blockif(b-size s)//如果size变小了考虑split{if(b-size - s (BLOCK_SIZE 4))split_block(b, s);}else//如果当前block的数据区不能满足size{//如果后继block是free的并且合并后大小满足size考虑合并if(b-next b-next-free (b-size BLOCK_SIZE b-next-size) s){fusion(b);//合并后满足size再看能不能splitif(b-size - s (BLOCK_SIZE 4))split_block(b, s);}else//以上都不满足则malloc新区域{newp malloc(s);if(!newp)return NULL;//内存复制new get_block(newp);copy_block(b, new);free(p);//释放oldreturn newp;}}return p;//当前block数据区大于size时}return NULL;}九、总结以上是一个比较简陋存在很大的优化空间但大致阐述了malloc的机制这也是本篇博文的目的。对于更好的优化读者可以参考linux内核伙伴算法、以及STL空间配置器。十、参考资料1、《Advanced Programming in the UNIX Environment》2、《The Linux Programming Interface》3、 A Malloc Tutorial
