Chinaunix首页 | 论坛 | 博客
  • 博客访问: 15482745
  • 博文数量: 2005
  • 博客积分: 11986
  • 博客等级: 上将
  • 技术积分: 22535
  • 用 户 组: 普通用户
  • 注册时间: 2007-05-17 13:56
文章分类

全部博文(2005)

文章存档

2014年(2)

2013年(2)

2012年(16)

2011年(66)

2010年(368)

2009年(743)

2008年(491)

2007年(317)

分类: C/C++

2007-08-01 11:16:11

一种轻巧的“内存动态分配管理机制”

文章来源: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);
}

阅读(4723) | 评论(0) | 转发(2) |
给主人留下些什么吧!~~