Memory Leaks

On the way home tonight I came up with a method of memory leak detection. The problem with memory leak detection, is if you have objects still active, your list of unallocated memory can be quite big, and if its a small leak, it can take a long time to track down. So as well as storing the filename and line number, I thought, why not store the “this” pointer for objects.

Now when allocation happens again on the same line number and filename, if there is an allocation for the current “this” object matching these, then allocation is happening again on the same object.

There is a problem with this however, loops that allocate will flag as reallocation without deallocation. These can be ignored though if care is taken with the objects that are doing this.

Athena: Memory Management (Part 3)

The final entry for my Athena: Memory Management (Part 1 and Part 2), this entry will cover my code for merging unallocated blocks into a single block and splitting memory blocks into smaller blocks.

For merging unallocated blocks, I iterate through each unallocated block, and if the next block is not out of memory pool range and is unallocated, then the current memory header has its size and the size of its header added to it. By continuing after this, we repeat the same process for the merged block incase there is more free memory after it.

//
//
void MemoryHeap::MergeFreeBlocks()
{
	unsigned char * pCurrentMemory = static_cast<unsigned char *>( m_memoryPool );
 
	for( unsigned int byteIdx = 0; byteIdx < kMemoryPoolSize; )
	{
		BasicMemoryHeader * pCurrentHeader = reinterpret_cast<BasicMemoryHeader *>( &pCurrentMemory[byteIdx] );
 
		if( pCurrentHeader->usage == kBlockUsage_UnAllocated )
		{
			const unsigned int kNextHeaderOffset = byteIdx + sizeof( BasicMemoryHeader ) + pCurrentHeader;
			BasicMemoryHeader * pNextHeader = reinterpret_cast<BasicMemoryHeader *>( &pCurrentMemory[kNextHeaderOffset] );
 
			if( kNextHeaderOffset < kMemoryPoolSize && pNextHeader->usage == kBlockUsage_UnAllocated )
			{
				pCurrentHeader->size += sizeof( BasicMemoryHeader ) + pNextHeader->size;
				continue;
			}
		}
 
		byteIdx += sizeof( BasicMemoryHeader ) + pCurrentHeader->size;
	}
}

 

When splitting a memory block, first I check to see if there is enough space left over from what I’m allocating for a new header and 16 bytes worth of memory. The 16 bytes is arbitrary, any value is acceptable as long as it is greater than 0. If there isn’t enough space left over, the function exits without splitting the memory block.

However if there is, the next memory header is setup using the space that is left over after subtracting the new memory header size and the space required for the original memory block. The original memory block size is then set to the require memory block size.

//
//
void MemoryHeap::SplitMemoryBlock( BasicMemoryHeader * inBlockHeader, const unsigned int inSize )
{
	const unsigned int kRequiredForSplit = sizeof( BasicMemoryHeader ) + 16;
 
	//
	// Don't Split if it is the correct size
	if( inBlockHeader->size < ( inSize + kRequiredForSplit ) )
	{
		return;
	}
 
	//
	// Setup New Header from Split
	unsigned char * nextHeaderPointer = reinterpret_cast<unsigned char *>( inBlockHeader ) + sizeof( BasicMemoryHeader ) + inSize;
	BasicMemoryHeader * nextHeader = reinterpret_cast<BasicMemoryHeader *>( nextHeaderPointer );
	nextHeader->size = inBlockHeader->size - inSize - sizeof( BasicMemoryHeader );
	nextHeader->usage = kBlockUsage_UnAllocated;
 
	//
	// Set old header size to input size
	inBlockHeader->size = inSize;
}

 

Finally for when I run out of memory, I output a message to the debug console window, cause an assertion, and if the code attempts to continue, it will cause the application to exit immediately with a code 1.

//
//
void MemoryHeap::OutOfMemory() const
{
	printf( "Memory Heap has run out of memory.\n" );
	assert( 0 );
	exit( 1 );
}

 

Well thats my basic memory heap for the moment. It still has lots of work since it isn’t perfect, one flaw with this memory heap is that it doesn’t support aligned allocations and reallocation.

Athena: Memory Management (Part 2)

Following on from my previous entry, Athena: Memory Manager (Part 1), this will show my code for allocation and freeing of memory.

//
//
void * MemoryHeap::Allocate( const unsigned int inSize )
{
	//
	//
	unsigned char * pCurrentMemory = static_cast<unsigned char *>( m_memoryPool );
 
	for( unsigned int byteIdx = 0; byteIdx < kMemoryPoolSize; )
	{
		//
		//
		BasicMemoryHeader * pCurrentHeader = reinterpret_cast<BasicMemoryHeader *>( &pCurrentMemory[byteIdx] );
 
		if( pCurrentHeader->usage == kBlockUsage_UnAllocated && pCurrentHeader->size >= inSize )
		{
			//
			//
			SplitMemoryBlock( pCurrentHeader, inSize );
 
			//
			//
			pCurrentHeader->usage = kBlockUsage_Allocated;
			return pCurrentMemory + sizeof( BasicMemoryHeader );
		}
 
		byteIdx += sizeof( BasicMemoryHeader ) + pCurrentHeader->size;
	}
 
	//
	// No adequate memory block found, must be out of memory.
	OutOfMemory();
	return 0;
}

 

Unlike the memory allocation function, the free function just takes the pointer we are passing in and subtracts the size of the header from it. Since the actual block of memory is offset by the header size from the header, by going backwards we can get instant access to the header.

//
//
void MemoryHeap::Free( void * inPointer )
{
	//
	//
	unsigned char * memoryBlockOffset = static_cast<unsigned char *>( inPointer );
 
	//
	//
	BasicMemoryHeader * pBlockHeader = reinterpret_cast<BasicMemoryHeader *>( memoryBlockOffset - sizeof( BasicMemoryHeader ) );
	pBlockHeader->usage = kBlockUsage_UnAllocated;
 
	//
	//
	MergeFreeBlocks();
}

 

Thats all for now, the next entry will finish off my basic memory heap class.

Athena: Memory Management (Part 1)

After reading Object-Orientated Game Development, I came up with some ideas for managing memory pools. Basically it works like this, after first allocating a pool of memory of size X, the first header size is subtracted from this.

So a basic memory header would be the following code. It stores the size of the memory block following it and whether that memory block has been allocated. The size of this memory header is 8 bytes, 4 bytes for the size and 4 bytes for the usage. I will probably expand this later by adding memory guards, and maybe a pointer to the next free block to improve lookup times.

#ifndef BASICMEMORYHEADER_H_INCLUDED
#define BASICMEMORYHEADER_H_INCLUDED
 
//
//
enum BlockUsage
{
	kBlockUsage_UnAllocated,
	kBlockUsage_Allocated
};
 
//
//
struct BasicMemoryHeader
{
	BasicMemoryHeader()
		:
		usage( kBlockUsage_UnAllocated ),
		size( 0 )
	{
	}
 
	BlockUsage usage;
	unsigned int size;
}
 
#endif

 

Now for the heap object, it will contain my pool of memory. If I use 100,008 bytes, after the first 8 bytes of our pool are used for the first header, I will have 100,000 bytes available for allocation. I have the two main functions, ‘Alloc()‘ for allocating memory, and ‘Free()‘ for releasing allocated memory.

My other three functions are used when allocating and freeing memory. After I have freed a memory block, I’ll make a call to ‘MergeFreeBlocks()’, which will iterate through all memory blocks and merge two blocks together that are next to each other in memory.

When allocating memory, when I find a suitably sized memory block, I’ll make a call to ‘SplitMemoryBlock()‘, passing to it the memory block I found, and the amount of blocks I need allocated from it, if there is more than enough memory, at the end of my allocation size, a new memory header with the remainder of memory, while the original will be updated to my usage request.

If when allocating there is not enough memory, I’ll make a call to ‘OutOfMemory()‘.

#ifndef MEMORYHEAP_H_INCLUDED
#define MEMORYHEAP_H_INCLUDED
 
//
//
#include "BasicMemoryHeader.h"
 
//
//
class MemoryHeap
{
	//
	// Attributes
	private:
		const unsigned int kMemoryPoolSize;
		void * m_memoryPool = 0;
 
	//
	// Functions
	public:
		//
		//
		MemoryHeap();
 
		//
		//
		~MemoryHeap();
 
		//
		//
		void * Allocate( const unsigned int inSize );
 
		//
		//
		void Free( void * inPointer );
 
	private:
		//
		//
		void MergeFreeBlocks();
 
		//
		//
		void SplitMemoryBlock( BasicMemoryHeader * inBlockHeader, const unsigned int inUsageSize );
 
		//
		//
		void OutOfMemory() const;
}
 
#endif

 

This is my basic setup for memory heap after it has been created and destroyed.

I wanted to check to see if any memory hasn’t been deallocated when the destructor is called, so I iterate through all memory blocks to checked to see if they are allocated. If they are allocated, I make an assert happen.

//
//
#include "MemoryHeap.h"
 
//
//
MemoryHeap::MemoryHeap()
	:
	kMemoryPoolSize( 100008 )
{
	//
	// Allocated Memory Pool
	m_memoryPool = malloc( kMemoryPoolSize );
 
	//
	// Setup First Memory Header
	BasicMemoryHeader * firstMemoryHeader = static_cast<BasicMemoryHeader *>( m_memoryPool );
	firstMemoryHeader.size = kMemoryPoolSize - sizeof( BasicMemoryHeader );
}
 
//
//
MemoryHeap::~MemoryHeap()
{
	const unsigned char * pCurrentMemory = static_cast<unsigned char *>( m_memoryPool );
 
	//
	//
	for( unsigned int byteIdx = 0; byteIdx < kMemoryPoolSize; )
	{
		const BasicMemoryHeader * pCurrentHeader = reinterpret_cast<BasicMemoryHeader *>( &pCurrentMemory[byteIdx] );
		assert( pCurrentHeader->usage == kBlockUsage_UnAllocated );
		byteIdx += sizeof( BasicMemoryHeader ) + pCurrentHeader->size;
	}
 
	//
	//
	free( m_memoryPool );
}

 

I don’t want to get this blog entry clogged up with code, so I’ll post the allocation and free code in the next entry, and the merge / split code in the entry after.

The Problem with Placement New

A few days ago I posted about a wonderous operator I had just found out about, known as Placement New. However after playing around with it a bit, I came by a slight problem with it.

To understand it, lets look at the class below.

#ifndef TEST_H_INCLUDED
#define TEST_H_INCLUDED
 
// --- [ includes ] -------------------------------------------
//
#include <stdlib.h>
 
// --- [ class ] ----------------------------------------------
//
class Test
{
	// Attributes
	//
	private:
		void * m_pData;
 
	// Functions
	//
	public:
		Test()
		{
			m_pData = malloc( 100 );
		}
 
		~Test()
		{
			free( m_pData );
		}
};
 
#endif

 

A very basic class, in it’s constructor it allocates 100 bytes of memory and then frees that 100 bytes in its destructor, so no memory leak as long as the destructor is called. Now lets see this in action with placement new.

// --- [ includes ] -------------------------------------------
//
#include "Test.h"
#include <new>
 
// --- [ prototypes ] -----------------------------------------
//
template<class T>
void CallDestructor( T* inObject );
 
template<class T>
void CallDestructor( T** inObject );
 
// --- [ entry point ] ----------------------------------------
//
void main()
{
	char buffer[2048];
 
	// Case 1: Single New
	{
		// Create Class
		Test * pClass = new ( buffer ) Test();
 
		// Call class destructor
		CallDestructor( pClass );
	}
 
	// Case 2: Single New Array of Pointers
	{
		// Create Pointer List
		Test ** pClassList = new ( buffer ) Test*[10];
 
		// Call destructor
		CallDestructor( pClassList );
	}
}
 
// --- [ functions ] ------------------------------------------
//
template<class T>
void CallDestructor( T* inObject )
{
	inObject->~T();
}
 
template<class T>
void CallDestructor( T** inObject )
{
	// Do nothing
}

 

Those both work fine, however the problem arises when you allocate an array of objects as below.

// --- [ includes ] -------------------------------------------
//
#include "Test.h"
#include <new>
 
// --- [ prototypes ] -----------------------------------------
//
template<class T>
void CallDestructor( T* inObject );
 
template<class T>
void CallDestructor( T** inObject );
 
// --- [ entry point ] ----------------------------------------
//
int main()
{
	char buffer[2048];
 
	// Case 1: Single New
	{
		// Create Class
		Test * pClass = new ( buffer ) Test();
 
		// Call class destructor
		CallDestructor( pClass );
	}
 
	// Case 2: Single New Array of Pointers
	{
		// Create Pointer List
		Test ** pClassList = new ( buffer ) Test*[10];
 
		// Call destructor
		CallDestructor( pClassList );
	}
 
	// Case 3: Multiple Object New in Array
	{
		// Create Array of Objects
		Test * pClassArray = new ( buffer ) Test[10];
 
		// Call destructor
		CallDestructor( pClassArray );
	}
 
	return 0;
}
 
// --- [ functions ] ------------------------------------------
//
template<class T>
void CallDestructor( T* inObject )
{
	inObject->~T();
}
 
template<class T>
void CallDestructor( T** inObject )
{
// Do nothing
}

 

If you debug through this code you’ll notice that case 1 and 2 still work, however when you get to case 3, the destructor is only called once, since it cannot tell the difference between an array and a single class that was allocated with new.

I can only think of three ways around this at the moment.

  1. Store the Number of Objects in this array and manually iterate through free them
  2. Override the placement new operator with my own that adds a header to the memory block that stores the number of elements so it can be retrieved to iterate through.
  3. Override the default delete operator, this way the delete operator can be used as you normally would to free objects created with new.

The last option seems to the best one, however overriding both default delete operators would mean I’d need my own memory management system, and override the default new operators as well.

Best get to work on that…