自己实现内存分配

很早之前,我们就在讨论自己实现内存分配的必要性,既然系统已经实现了内存内存分配,我们为何要多此一举?我们是否可以认为系统的内存分配是高效的?很自然的观点,自己实现内存分配没有系统的高效,我到现在依然保持这样的观点(对于成熟的系统)。我们找了很多理由来说明它的不必要性,却又找了很多理由来说明它的必要性。先看下历史缘由吧(即使在现在依然在进行中):
BREW系统中无法使用高级的C++,自然包括异常(ADS1.2编译器),这样,如果一个很深很深的函数中,某个地方内存分配失败,为了确保程序的正常运行,必须进行检查,告诉用户内存不够了,而我们又不能使用try…catch机制,只能在每个内存分配之后进行检查。这是一种让人烦恼的情况,必须进行解决。

BREW程序在测试的时候,测试员会尽可能的使用各种手段在运行中减少内存,你不想让测试员成天在你耳边说:嗨,你的程序在内存减到xxx的时候又崩溃了。
某些情况下,我们需要把相关联的内存分到一起,但又不想失去程序的可读性,也不想提高读程序的难度。
BREW程序中,在程序启动的时候,我们可以大致知道我们需要多少的空余内存,我们可以进行内存检测,但在运行中间,我们并不太能知道我们已经使用了多少内存(考虑内存碎片的影响)。
这些时候,我们就会说,自己实现一个内存分配器吧,这些问题就可以解决了。但如果下一个项目比较简单,或者是原创的话,又会说,那种情况并不多,还是算了吧。我也是在反复再三之后,终于决定实现它。当使用它之后,发现它很有必要,至少省了某些东西。
上面说了很多废话,先看代码,再说讲解。一切都在代码中:
CMemoryManger.h:

       #ifndef _H_MEMORYMANGER
#define _H_MEMORYMANGER
#include "AEEStdlib.h"
#include "define.h"

struct MEM_STRUCT
{
    MEM_STRUCT* prev; 
    MEM_STRUCT* next; 
};

class CMemoryManger
{
public:
    CMemoryManger();
    ~CMemoryManger();
    void Init();
    void Destroy();
    void setMemoryBlockNum( int asize );
    void setMemorySize( int ablock, int asize );
    void* MemoryAlloc( int ablock, size_t asize );
    bool MemoryFree( void* abuf );
    void ClearBlock( int ablock );
    void FreeBlock( int ablock );
    byte** m_mem; 
    byte** m_memend; 
    byte** m_memindex; 
    int m_blocknum; 
    MEM_STRUCT** start; 
    MEM_STRUCT** end;
};

CMemoryManger.cpp

#include "MemoryManger.h"
#include "AEEStdlib.h"
#include "MemoryAlloc.h"

void CMemoryManger::Init()
{
    m_mem = NULL;
    m_memend = NULL;
    m_memindex = NULL;
    m_blocknum = 0;
    start = NULL;
    end = NULL;
}

void CMemoryManger::Destroy()
{
    for( int i = 0; i < m_blocknum; i++ )
    {
		FreeBlock( i );
    }
	delete[] start;
	delete[] end;
    delete[] m_mem;
    delete[] m_memindex;
    delete[] m_memend;
    m_blocknum = 0;
    m_mem = NULL;
    m_memend = NULL;
    m_memindex = NULL;
    start = NULL;
    end = NULL;
}

CMemoryManger::CMemoryManger()
{
    m_mem = NULL;
    m_memend = NULL;
    m_memindex = NULL;
    start = NULL;
    end = NULL;
    m_blocknum = 0;
}


CMemoryManger::~CMemoryManger()
{
    for( int i = 0; i < m_blocknum; i++ )
    {
		FreeBlock( i );
		// delete[] m_mem[i];
		//m_mem[i] = NULL;
		//m_memend[i] = NULL;
		//m_memindex[i] = NULL;
		//start[i] = NULL;
		//end[i] = NULL;
    }
	delete[] start;
	delete[] end;
    delete[] m_mem;
    delete[] m_memindex;
    delete[] m_memend;

    m_blocknum = 0;
    m_mem = NULL;
    m_memend = NULL;
    m_memindex = NULL;
    start = NULL;
    end = NULL;
}


void CMemoryManger::setMemoryBlockNum( int asize )
{
    if( asize <= 0 || m_blocknum == asize )
        return;
    if( m_blocknum != 0 )
    {
        if( m_blocknum < asize )
        {
            int bsize = m_blocknum;
            byte** temp = m_mem;
            int i = 0;
            m_blocknum = asize;
            m_mem = new  byte*[m_blocknum];
            for( i = 0; i < bsize; i++ )
                m_mem[i] = temp[i];
            delete[] temp;
            temp = NULL;
            temp = m_memend;
            m_memend = new  byte*[m_blocknum];
            for( i = 0; i < bsize; i++ )
                m_memend[i] = temp[i];
            delete[] temp;
            temp = NULL;
            temp = m_memindex;
            m_memindex = new  byte*[m_blocknum];
            for( i = 0; i < bsize; i++ )
                m_memindex[i] = temp[i];
            delete[] temp;
            MEM_STRUCT** t = start;
            start = new  MEM_STRUCT*[m_blocknum];
            for( i = 0; i < bsize; i++ )
                start[i] = t[i];
            for( i = bsize; i < m_blocknum; i++ )
                start[i] = NULL;
            delete[] t;
            t = end;
            end = new  MEM_STRUCT*[m_blocknum];
            for( i = 0; i < bsize; i++ )
                end[i] = t[i];
            for( i = bsize; i < m_blocknum; i++ )
                end[i] = NULL;
            delete[] t;
            for( i = bsize; i < m_blocknum; i++ )
                m_mem[i] = NULL;
            for( i = bsize; i < m_blocknum; i++ )
                m_memend[i] = NULL;
            for( i = bsize; i < m_blocknum; i++ )
                m_memindex[i] = NULL;
        }
        else
            if( asize < m_blocknum )
            {
                int i = asize;
                int bsize = m_blocknum;
                for( i = asize; i < m_blocknum; i++ )
                {    
                    ClearBlock( i );
                    FreeBlock( i );
                }
                byte** temp = m_mem;
                m_blocknum = asize;
                m_mem = new byte*[m_blocknum];
                for( i = 0; i < m_blocknum; i++ )
                    m_mem[i] = temp[i];
                delete[] temp;
                temp = NULL;
                temp = m_memend;
                m_memend = new  byte*[m_blocknum];
                for( i = 0; i < m_blocknum; i++ )
                    m_memend[i] = temp[i];
                delete[] temp;
                temp = NULL;
                temp = m_memindex;
                m_memindex = new  byte*[m_blocknum];
                for( i = 0; i < m_blocknum; i++ )
                    m_memindex[i] = temp[i];
                delete[] temp;
                temp = NULL;
                MEM_STRUCT** t = start;
                start = new  MEM_STRUCT*[m_blocknum];
                for( i = 0; i < m_blocknum; i++ )
                    start[i] = t[i];
                delete[] t;
                t = end;
                end = new  MEM_STRUCT*[m_blocknum];
                for( i = 0; i < m_blocknum; i++ )
                    end[i] = t[i];
                delete[] t;
            }
    }
    else
    {
        m_blocknum = asize;
        m_mem = new  byte*[m_blocknum];
        m_memend = new  byte*[m_blocknum];
        m_memindex = new  byte*[m_blocknum];
        start = new MEM_STRUCT*[m_blocknum];
        end = new  MEM_STRUCT*[m_blocknum];
        for( int i = 0; i < m_blocknum; i++ )
        {
            m_mem[i] = NULL;
            m_memend[i] = NULL;
            m_memindex[i] = NULL;
            start[i] = NULL;
            end[i] = NULL;
        }
    }
}

void CMemoryManger::setMemorySize( int ablock, int asize )
{
    if( ablock < 0 || ablock >= m_blocknum )
        return;
    if( m_mem[ablock] )
        delete[] m_mem[ablock];
    m_mem[ablock] = NULL;
    m_memend[ablock] = NULL;
    m_memindex[ablock] = NULL;
    m_mem[ablock] = new byte[asize];
    m_memend[ablock] = m_mem[ablock] + asize;
    m_memindex[ablock] = m_mem[ablock]+8;
    start[ablock] = ( MEM_STRUCT* )( m_mem[ablock] );
    end[ablock] = ( MEM_STRUCT* )( m_memend[ablock] - sizeof( MEM_STRUCT ) );
    start[ablock]->prev = NULL;
    start[ablock]->next = end[ablock];
    end[ablock]->prev = start[ablock];
    end[ablock]->next = NULL;
    
}

void* CMemoryManger::MemoryAlloc( int ablock, size_t asize )
{
    if( ablock < 0 || ablock >= m_blocknum )
    {
        DBGPRINTF( "CMemoryManger::MemoryAlloc ablock < 0 || ablock >= m_blocknum" );
        return NULL;
    }
    if( m_mem[ablock] == NULL )
    {
        DBGPRINTF( "CMemoryManger::MemoryAlloc m_mem[%d] == NULL", ablock );
        return NULL;
    }
    byte* temp = m_mem[ablock];
    int bsize = asize + 4 - ( asize % 4 );
    MEM_STRUCT* tstart = start[ablock];
    MEM_STRUCT* tend = end[ablock];
    for( ; ; )
    {
        if( tstart >= end[ablock] )
        {
            DBGPRINTF( "MemoryManger::MemoryAlloc m_mem[%d] too small", ablock );
            return NULL;
        }
        bool use = ( ( ( *( ( int* )( (byte*)tstart +  sizeof( MEM_STRUCT* ) ) ) ) & ( 1 < < 31 ) ) == 0 ) ? TRUE : FALSE;
        if( use )
        {
            int csize = (int)( ( byte* )( tstart->next ) - ( byte* ) tstart -  sizeof( MEM_STRUCT ) );
            if( csize < bsize + sizeof( MEM_STRUCT ) )
            {
                tstart = (MEM_STRUCT*)( (int)( tstart->next ) & ( 0xFFFFFFFF >> 1 ) );
                continue;
            }
            MEM_STRUCT* add = ( MEM_STRUCT* )( (byte*)( tstart ) + bsize + sizeof( MEM_STRUCT ) );
			if(add != tstart->next )
			{
            add->prev = tstart;
			//if( ( ( ( *( ( int* )( (byte*)(tstart->next) +  sizeof( MEM_STRUCT* ) ) ) ) & ( 1 < < 31 ) ) == 0 ) )
            add->next = tstart->next;
            tstart->next = add;
            add->next->prev = add;
			}
			uint32* p = (uint32*)( (byte*)tstart+ sizeof( MEM_STRUCT* ) );
            *p |= 1 < < 31;
			/*if(tstart == NULL || tstart->next == NULL || add->next == NULL )
			{
				int k = 10;
			}
			if(tstart->prev == tstart->next)
			{
				int k = 10;
			}*/
			MEMSET(( byte* ) ( tstart ) + sizeof( MEM_STRUCT ) , 0, bsize );
            return ( ( byte* ) ( tstart ) + sizeof( MEM_STRUCT ) );
        }
        else
        {
            tstart = (MEM_STRUCT*)( (int)( tstart->next ) & ( 0xFFFFFFFF >> 1 ) );
        }
    }
    return NULL;
}

bool CMemoryManger::MemoryFree( void* abuf )
{
    if( abuf == NULL )
        return TRUE;
    for( int i = 0; i < m_blocknum; i++ )
    {
        if( ( byte* ) abuf == m_mem[i] )
            return FALSE;
        else
        if( ( byte* )abuf > m_mem[i] && ( byte* ) abuf < m_memend[i] )
        {
			byte* temp = m_mem[i];
            MEM_STRUCT* tmem = ( MEM_STRUCT* )( (byte*)abuf - sizeof( MEM_STRUCT ) );
			uint32* p = (uint32*)( (byte*)tmem + sizeof( MEM_STRUCT* ));
            *p &=  ( 0xFFFFFFFF >> 1 );
			if( tmem->prev == NULL )
			{
				//*p &=  ( 0xFFFFFFFF >> 1 );
			}else
            if( ( *( ( int* )( (byte*)( tmem->prev )+ sizeof( MEM_STRUCT* ) ) ) & ( 1 < < 31 ) ) == 0 )
            {
                tmem->prev->next = tmem->next;
                tmem->next->prev = tmem->prev;
				MEM_STRUCT* clear = tmem;
                tmem = tmem->prev;
				//MEMSET( (byte*)(tmem )+ sizeof( MEM_STRUCT ), 0, (int)( (byte*)(tmem->next) - (byte*) tmem ) - sizeof(MEM_STRUCT ));
				clear->prev = NULL;
				clear->next = NULL;
				
            }
			if( tmem->next == NULL )
			{
			//	tmem->next = end[i];
			//	int k = 10;
			}else
            if( ( *( ( int* )( (byte*)(tmem->next )+ sizeof( MEM_STRUCT* ) ) ) & ( 1 < < 31 ) ) == 0 )
            {
				MEM_STRUCT* clear = tmem->next;
                tmem->next = tmem->next->next;
                tmem->next->prev = tmem;
				//MEMSET( (byte*)(tmem )+ sizeof( MEM_STRUCT ), 0, (int)( (byte*)(tmem->next) - (byte*) tmem )- sizeof(MEM_STRUCT ));
				//MEMSET( (byte*)(tmem->next->prev)+ sizeof( MEM_STRUCT ), 0, (byte*)(tmem->next->next));
				clear->prev = NULL;
				clear->next = NULL;
            }
			
			//*p &=  ( 0xFFFFFFFF >> 1 );
            return TRUE;
        }
    }
    
    return FALSE;
}

void CMemoryManger::ClearBlock( int ablock )
{
    if( ablock < 0 || ablock > m_blocknum )
    {
        DBGPRINTF( "CMemoryManger::ClearBlock ablock < 0 || ablock > m_blocknum" );
        return;
    }
	if( m_mem[ablock] == NULL )
		return;
    MEMSET( m_mem[ablock], 0, m_memend[ablock] - m_mem[ablock] );
    start[ablock] = ( MEM_STRUCT* )( m_mem[ablock] );
    end[ablock] = ( MEM_STRUCT* )( m_memend[ablock] - sizeof( MEM_STRUCT ) );
    start[ablock]->prev = NULL;
    start[ablock]->next = end[ablock];
    end[ablock]->prev = start[ablock];
    end[ablock]->next = NULL;
}

void CMemoryManger::FreeBlock( int ablock )
{
    if( ablock < 0 || ablock > m_blocknum )
    {
        DBGPRINTF( "CMamoryManger::FreeBlock ablock < 0 || ablock > m_blocknum" );
        return;
    }
	if( m_mem[ablock] == NULL )
		return;
    delete[] m_mem[ablock];
    m_mem[ablock] = NULL;
    m_memend[ablock] = NULL;
    m_memindex[ablock] = NULL;
    start[ablock] = NULL;
    end[ablock] = NULL;
}
#endif

上面就是内存分配的全部代码。首先说明内存分配的数据结构MEM_STRUCT。
MEM_STRUCT事实上是一个双向链表,prev指向它的前一个节点,next指向它的后一个节点,两个中间的内容就是分配好的内存。类似这样:
_______________________
|prev|next| memory |
|____|____|____________|
next还有另外一个作用,就是指示当前这个memory块是否被分配,这是通过next指针值的最高位决定的,如果最高位被置为1,那么这块内存已经被使用,否则,这块内存没有被使用。这样以来,我们可以管理的内存就会减少了?是的,在我的环境下,虽然CPU是32位的,但手机中的内存并没有32位化,如果用户态程序需要占用如此大的内存,就要考虑是否有必要了。
CMemoryManger的几个函数,Init是初始化,Destroy是销毁,setMemoryBlockNum是设置要管理内存块的块数,setMemorySize是设置指定内存块的内存大小,MemoryAlloc是将内存在某块中分配指定大小的内存,MemoryFree则是释放它,ClearBlock则是清空指定内存块,把它初始化,FreeBlock则将内存块从内存中释放。
来模拟一次使用吧,我们首先调用Init函数,来初始化内存结构,然后调用setMemoryBlockNum,设置内存块为1(最简单的模式),调用setMemorySize设置内存块0(索引从0开始)的内存大小,这样一番操作之后,内存的状态类似这样:
start_____________________________________end__________________
| | | | | |
|prev=0|next=end| |prev=start |next=0 |
|______|________|_______________________|____________|_______|
包含了一个MEM_STRUCT结构,next指示紧接着它的内存没有使用(最高位没有置为1)。
接下来,我们分配一个内存,将会变成这样:
start______________p1______________________________end__________________
| | | | | | | | |
|prev=0|next=p1 |use |prev=start|next=end| |prev=start |next=0 |
|______|________|______|__________|________|_____|____________|_______|
start的next值为p1|(1<<31)。 如果这个时候调用MemoryFree删除p1的话,之用将start的next的值的最高位设置为0,然后设置next指向p1的next就可以了。这样以来,内存就恢复成初始化的时候的了。 可以看到一个好处是如果有两片连着的内存都不使用的话,内存管理器会自动的把这两个内存练成一片,变成一片更大的内存,这样就提高了内存使用率。 如果没有调用MemoryFree来删除p1,而是再次调用MemoryAlloc分配另外一个p2的话,只用从start开始查找,看哪一片的next的最高位为0,并且next指向的节点的值与当前的值相差够分配内存的话,就分配,否则就接着往后查找,如果找到了end,则说明内存不够用了,无法正确进行分配,则打印出一条信息。 如果使用系统分配的话,出现无法分配的话,则会进行内存整理,但我们仅仅属于用户态的程序,无法进行这一步,尽管如此,我们还是有了一个小小的碎片整理。 效率如何?我们关心的是效率,由于使用分块管理,我们可以将不太变化的内存(比如图像,地图数据)放入一个指定的内存块中,将经常变化的数据(临时分配的内存,比如字符串)放入另外一块内存,由于都是在已经分配好的内存中进行再分配,索引不会引起系统的内存碎片,由于将相关的内存放入到一起,而且使用链表(对于频繁而又数量不多的节点)来查找,效率可以认为是可以接受的,事实上,当我使用上面的代码在我的某个项目中的时候,比不使用它还要快上1-2祯(保守的说)。 好用不?非常好用,以后我会提到的,对于C++来说,仅仅重载而已(一个小提示)。 昨天晚上朋友来访,无法更新,所有拖到了今天,元旦的话,应该会正常一些吧。

发布者

rix

如果连自己都不爱自己,哪还有谁来爱你

  • 没有想到表格变成了那样,改天在emacs中学会了更好的画图方法再更新

  • :-),新年快乐~