|
一种轻巧的“内存动态分配管理机制”
文章来源: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);
}
|
