一种轻巧的“内存动态分配管理机制”
文章来源:http://gliethttp.cublog.cn
(1)首先计算需要管理的内存区域一共有多少个sizeof(Header)内存动态管理组DMG,放入header->s.size中 (2)malloc分配的内存从最后DMG组开始 (3)本次分配的内存管理单元Header和数据一起分配,并位于此次分配出去的内存管理组DMG的第一组,数据紧跟其后 (4)一次分配最小数据空间sizeof(Header)=8字节,也就是说如果malloc(3),那实际分配的数据空间是8字节,容易有碎片 (5)动态增长DMG使用morecore(u32 nu);可以从当前os中再申请nu个DMG (6)刚刚使用free释放的内存空间,经过边界合并后,将其加入free链表,同时更改freep指向p (7)有一点需要注意:因为free链表空闲内存是从小地址->大地址顺序链接的,所以p >= p->s.ptr,说明p位于 内存最大地址处[最末尾],但此时p->s.ptr可能不是&base. //------------------------------------------------ //1.空闲链表结构体定义如下 typedef u32 Align; union header { struct { union header *ptr; u32 size; }s; Align x;//该x仅用于编译器对header结构体的4字节对齐 }; typedef union header Header; //------------------------------------------------ //2.malloc()内存动态分配管理函数 #include "malloc.h" char * __heap_start = (char *)(0x02000000 + 0x5800); char * __heap_end = (char *)(0x0203FFFF); static Header base; //未必是空闲链表开始,只是一个普通header元素,&base地址值未必最小 static Header *freep=NULL;//未初始化 int is_run = 0; void *malloc(u32 nbytes) {Header *p, *prevp; u32 nunits; //计算管理nbytes数据需要多少个DMG[gliethttp] nunits = (nbytes+sizeof(Header)-1)/sizeof(Header) + 1; prevp = freep; if(prevp == NULL) {//第一次运行,初始化之 base.s.ptr = freep = prevp = &base;//base.s.ptr指向其自身&base base.s.size=0;//无大小,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个DMG p->s.size -= nunits; p += p->s.size; //(char*)p+p->s.size*sizeof(Header),p指向管理nbytes个字节的DMG第一组 p->s.size = nunits; } freep = prevp; return (void *)(p+1);//返回紧跟DMG管理第一组后的数据区指针 } if(p == freep) {//从freep开始搜索了一圈,出现回环 p = morecore(nunits);//尝试从操作系统中再获取一些内存,不同os有不同的方式 if(p==NULL)return NULL;//实在是没有可用内存了,那么只能false } } } //------------------------------------------------ //3.free()内存释放函数 void free(void *ap) {Header *bp, *p; //(Header *)ap-1,读取控制当前ap内存的控制单元DMG第一组 bp = (Header *)ap-1; for(p=freep;!(bp > p && bp < p->s.ptr); p=p->s.ptr) { //p >= p->s.ptr表明数据回环了,此时p为管理的内存最大地址值[最末尾],p->s.ptr可能不是&base
//bp可能比最大的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后边的p->s.ptr合并 bp->s.size += p->s.ptr->s.size; bp->s.ptr = p->s.ptr->s.ptr; }else { bp->s.ptr = p->s.ptr;//将bp插到p->s.ptr前面 } if(p + p->s.size == bp) { //和bp前边的p合并 p->s.size += bp->s.size; p->s.ptr = bp->s.ptr; }else { p->s.ptr = bp;//将bp插到p后面 } freep = p; } //------------------------------------------------ //4.morecore()从当前os中获取更多内存的函数 Header *morecore(u32 nu) {char *cp; Header *up; if(is_run)return NULL; is_run = 1; //第一次调用 nu = (__heap_end - __heap_start)/sizeof(Header) - 1; cp = (char *)__heap_start; up = (Header *)cp; up->s.size = nu;//空闲内存 free((void *)(up+1));//释放紧接DMG第一组的内存空间 return freep; } //上面函数的原型是 #define NALLOC 1024 //一次至少向os申请NALLOC个DMG单元 static Header *morecore(unsigned nu) {char *cp, *sbrk(int); Header *up; if (nu < NALLOC) nu = NALLOC;//至少向os申请NALLOC个DMG单元 cp = sbrk(nu * sizeof(Header)); //通过unix的sbrk系统调用,在进程的末尾增加内存空间,能保证&base地址值最小 if (cp == (char *) -1) return NULL; up = (Header *) cp; up->s.size = nu; free((void *)(up+1));//将新增的空间添加到free空闲队列 return freep; } //------------------------------------------------ //5.init_malloc()初始化windows下使用的__heap_start和__heap_end void init_malloc() { //calloc分配内存,同时清0 __heap_start = (char *)calloc(0x400000, sizeof(char)); __heap_end = (char *)(__heap_start + 0x400000); }
|