memory pool implementation

[tomtetlaw]

I'm trying to make a memory pool, I've got everything sorted out except for one thing: the allocation. I have no idea how to return a segment of the data in the pool. I have it like this byte *m_pData; . How would I be able to return a segment of that when it's initialized like m_pData = new byte[ size ]; Here is my code:

#define POOL_DEFAULT_SIZE 262144 //256k

CMemPool::CMemPool( void )
{
	Init( POOL_DEFAULT_SIZE );
}
	
CMemPool::CMemPool( int size )
{
	Init( size );
}

CMemPool::~CMemPool( void )
{
	Destroy( );
}

void CMemPool::Init( int size )
{
	m_pData = new byte[ size ];
	m_nMaxSize = size;
	m_nCurSize = 0;
}

void *CMemPool::Alloc( int size )
{
        // this is what i can't figure out
}

void CMemPool::Free( void *mem )
{
	if( !mem )
		return;

	memset( mem, 0, sizeof( mem ) );
	mem = NULL;
}

void CMemPool::Clear( void )
{
	memset( m_pData, 0, m_nMaxSize );
}

void CMemPool::Destroy( void )
{
	delete m_pData;
}

[tomtetlaw]

I think I did it right:

void *CMemPool::Alloc( int size )
{
	if( m_nCurSize + size > m_nMaxSize )
		return NULL;

	byte *ret = m_pData + m_nCurSize;
	m_nCurSize += size;

	return ret;
}

void CMemPool::Free( void *mem )
{
	if( !mem )
		return;

	m_nCurSize -= sizeof( mem );
	Q_memset( mem, 0, sizeof( mem ) );
	mem = NULL;
}

This seems to be working, but I could be wrong, does this look wrong or weird to anyone?

[thelamb]

It goes wrong in free.
sizeof( mem ) will be the size of a void*, not the size that was previously requested in Alloc.

Also.. be careful with pointer arithmetic:

char* pChar = 0;
pChar++; // pChar will be 1
int* pInt = 0;
pInt++;  // pInt will be 4!

So increasing a pointer, increases it by the size of the type it points to.

In your case it goes wrong, but if you ever decide to change the type of m_pData... be careful.

[tomtetlaw]

So how do I find out the proper size of what is passed to Free() ?

[thelamb]

You have to do some bookkeeping yourself, to keep track of the size.

For instance, a map that maps the pointer to the size

map<byte*,int> m_blockSize;

When you allocate, you add the pointer and the size to this map.. and when you free you search for the pointer, and get the matching size (if the pointer passed to free is not in the map, it's an invalid call to free).

There are other ways, but I think this is quite straight forward.

[mrnutty]

How about just using templates?

[tomtetlaw]

Okay, that worked. I have tried to make it fill the empty hole left by freeing the data, from what I can tell, it works, but when I try to delete m_pData, I get this runtime error:

Debug Error!

Program: ...tudio 2008\Projects\Quarantine_2010\Debug\Quarantine_2010.exe

HEAP CORRUPTION DETECTED: after normal block (#123) at 0x00430068
CRT detected that the application wrote to memory after the end of heap buffer.

(Press Retry to debug the application)

This is what my Alloc and Free functions look like:

void *CMemPool::Alloc( int size )
{
	if( m_nCurSize + size > m_nMaxSize )
		return NULL;

	byte *ret = m_pData + m_nCurSize;
	m_nCurSize += size;

	m_Sizes[ret] = size;

	return ret;
}

void CMemPool::Free( void *mem )
{
	if( !mem )
		return;

	m_pData;
	int size = m_Sizes[( byte * )mem];

	m_nCurSize -= size;
	Q_memset( mem, 0, size - 1 );

	byte *start = ( byte * )mem;
	byte *end = ( byte * )mem + ( size );
	memmove( start, end, m_nMaxSize - IndexOfByte( *end ) );

	mem = NULL;
}

This is what IndexOfByte looks like:

int CMemPool::IndexOfByte( byte b )
{
	for( int i = 0; i < m_nMaxSize; i++ )
		if( m_pData[i] == b )
			return i;
}

m_Sizes is std::map< byte *, int >

[thelamb]

Why do you do the memmove in Free? You move whatever is after end, to start.
That makes little sense...
Let's say I allocate 10 bytes, and after that 20.
So I get two pointers from you, p10 and p20.

Now I Free p10, so you move everything that was after p10 to the start of p10.
What if I use my p20 now? It's pointing to something totally different.

Welcome to fragmentation ;)

[tomtetlaw]

It makes perfect sense to me. Those are the start and end addresses of the to-be-free'd memory, so I'm moving it back so there isn't an empty space inbetween two parts of the buffer.

[thelamb]

Exactly - the intention of the move is fine(eliminating holes), but there can be allocated memory after what you're freeing right? So you will move this allocated memory to another address, but the person who allocated it will have no idea that you moved it - and just keeps on using it.

In my example the user of p20 assumes that he has 20 bytes, starting from the p20 pointer. But because p10 was free'ed, you moved the allocated 20 bytes back 10 bytes. So if now p20 writes 20 bytes, he will start writing in the middle of his 20-byte block and write 10 bytes past the end.

[ -10-  |     -20-     ]  <-- before
^p10     ^p20

[     -20-     ]          <-- after Free( p10 )
         ^p20

Ok the scaling is not perfect, but hopefully you got the idea ;)

[tomtetlaw]

But that's okay as p20 would still have the same value right? If not, how would I fix it?

[thelamb]

The whole point that it's not ok is because p20 has the same value...

How is the 'picture' not clear? p20 is pointing to the middle of the allocated 20 bytes, while at the beginning it was pointing to the start.

This is not easy to fix - allocating variable sized blocks from a fixed size (continuous) buffer is inherent to this problem... you need to re-think the allocation strategy.

There are many possible ways, best thing is to find a book on operating systems and reading the memory section - there is a lot of discussion about this stuff.

[tomtetlaw]

Ohhh now I understand. I guess for the time being I will have to live with fragmentation, untill I look up what you said, thanks for your help. :)