很早之前,我们就在讨论自己实现内存分配的必要性,既然系统已经实现了内存内存分配,我们为何要多此一举?我们是否可以认为系统的内存分配是高效的?很自然的观点,自己实现内存分配没有系统的高效,我到现在依然保持这样的观点(对于成熟的系统)。我们找了很多理由来说明它的不必要性,却又找了很多理由来说明它的必要性。先看下历史缘由吧(即使在现在依然在进行中):
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++来说,仅仅重载而已(一个小提示)。
昨天晚上朋友来访,无法更新,所有拖到了今天,元旦的话,应该会正常一些吧。
没有想到表格变成了那样,改天在emacs中学会了更好的画图方法再更新
:-),新年快乐~