Kindly hosted by

Specific Memory Manager

Welcome to the Memory Manager tutorial. I wrote this tutorial to make life easier for myself (and others!) when I've been struck
with the problem of memory allocation/deallocation of differently sized memory blocks in the global memory manager. So, I've thought,
wouldn't it be better that each structure, or even a class will have their own memory manager? Since most structures we are usually dealing with
that invlove a lot of allocation/deallocation is vertices, we are going to write memory managers for them.

To begin with something, let's take a look at a basic memory manager that we are going to use:

#define __FUNCTION__ "??"

#include "DoubleList.h"
#include "Logger.h"

#include <time.h>
#include <malloc.h>
#include <memory.h>

#define	Memory_Allocation_Unknown			0
#define Memory_Allocation_New				1
#define Memory_Allocation_NewArray			2
#define Memory_Allocation_Malloc			3
#define	Memory_Deallocation_Delete			4
#define	Memory_Deallocation_DeleteArray			5
#define Memory_Deallocation_Free			6

#define Memory_BlockStatus_Free				0
#define Memory_BlockStatus_Cache			1
#define Memory_BlockStatus_Used				2

struct tMemoryBlock
{
	size_t		m_szActualSize;
	size_t		m_szReportedSize;
	void		*m_pActualAddress;
	void		*m_pReportedAddress;
	unsigned int	m_uiAllocationType;
	unsigned int	m_uiAllocationNumber;
	unsigned int	m_uiBlockStatus;
	
	char m_strFilename[32];
	char m_strFunction[32];
	unsigned int m_uiLine;

	tMemoryBlock()
	{
		m_szActualSize = m_szReportedSize = 0;
		m_pActualAddress = m_pReportedAddress = NULL;
		m_uiAllocationType = Memory_Allocation_Unknown;
		m_uiAllocationNumber = 0;
		m_uiBlockStatus = Memory_BlockStatus_Free;
	};

	~tMemoryBlock()
	{

	};
};

class CMemoryManager
{

public:
	CMemoryManager();
	virtual ~CMemoryManager();

	void *Allocate(size_t bytes, int alloc_type);
	void Deallocate(void *ptr, int dealloc_type);

	void DumpMemoryReport(const char *filename = NULL);
	void DumpLeaksReport(const char *filename = NULL);
	
	void FreeAll();

	void SetOwner(const char *file, unsigned int line, const char* func);

	unsigned int GetNextUID();
	
	void EnableGC();
	bool GetGC();
	void DisableGC();

private:
	
	tMemoryBlock *FindBlockByAddr(void *ptr);
	
	void FillBlock(tMemoryBlock *block, unsigned long pattern);

	bool ValidateMemoryBlock(tMemoryBlock *block);
	bool ValidateAllBlocks();

	size_t CalculateActualSize(const size_t reportedSize);
	void *CalculateReportedAddress(void *actualAddress);

	unsigned int	m_uiTotalReportedMemory;
	unsigned int	m_uiTotalActualMemory;
	unsigned int	m_uiPeakReportedMemory;
	unsigned int	m_uiPeakActualMemory;
	unsigned int	m_uiAccumulatedReportedMemory;
	unsigned int	m_uiAccumulatedActualMemory;
	unsigned int	m_uiAccumulatedAllocUnitCount;
	unsigned int	m_uiPeakAllocUnitCount;

	unsigned int m_uiLine;
	char m_strFilename[255];
	char m_strFunction[255];

	CLogger m_Logger;

	// If you declare this variable to be true, it will do the following:
	// 1. Will not free the avaliable memory, but instead move it to unused pool
	// 2. Will free that unused memory at the end (in destructor)
	// 3. Pull out unused memory of same size instead of allocating new chunk using malloc()
	bool m_bUseGC;
	unsigned int m_uiLastUID;
	
	CDoubleList <tMemoryBlock *> m_lstUnusedMemory;
	CDoubleList <tMemoryBlock *> m_lstUsedMemory;

protected:
	void *GetPtr(unsigned int index, bool used = true);
};

As you might say, this class closely resembles the one that is being done by Fluid Studios. Well, they are definately done a excellent job,
so I took their code as a base. Don't worry - the software (code) is 100% free. So, moving on, let's take a look at the most important function
in this class:

void *CMemoryManager::Allocate(size_t bytes, int alloc_type)
{
	// Do a search if required of a similar allocation made before with same size
, but with block status marked either as BLOCK_MEMORY_FREE or BLOCK_MEMORY_READY_TO_BE_FREED
	// If there's such, ZeroMemory it, mark flag as USED, and return it
	// Otherwise, allocate memory for new block
	// Increase our allocation count
	tMemoryBlock *memory_block = NULL;
	bool no_free_blocks_in_gc = false;

	if(m_bUseGC)
	{
		memory_block = m_lstUnusedMemory.begin();
		m_lstUnusedMemory.set_ptr(memory_block);

		while(memory_block !=NULL)
		{
			if(memory_block->m_szReportedSize == bytes)
			{
				m_lstUsedMemory.push_back(m_lstUnusedMemory.remove(memory_block));
				break;
			}

			memory_block = m_lstUnusedMemory.next();
		}

		if(memory_block == NULL)
		{
			memory_block = (tMemoryBlock *)malloc(sizeof(tMemoryBlock));
			memset(memory_block, 0, sizeof(tMemoryBlock));
			no_free_blocks_in_gc = true;
		}
	}
	else
	{
		memory_block = (tMemoryBlock *)malloc(sizeof(tMemoryBlock));
		memset(memory_block, 0, sizeof(tMemoryBlock));
	}

	memory_block->m_szActualSize = CalculateActualSize(bytes);
	memory_block->m_pActualAddress = malloc(memory_block->m_szActualSize);
	memory_block->m_uiAllocationType = alloc_type;
	memory_block->m_pReportedAddress = CalculateReportedAddress(memory_block->m_pActualAddress);
	memory_block->m_szReportedSize = bytes;

	memory_block->m_uiLine = m_uiLine;
	strncpy(memory_block->m_strFilename, m_strFilename, 32);
	strncpy(memory_block->m_strFunction, m_strFunction, 32);
	
	// Account for the new allocatin unit in our stats
	m_uiTotalReportedMemory+= memory_block->m_szReportedSize;
	m_uiTotalActualMemory+= memory_block->m_szActualSize;
	
	if (m_uiTotalReportedMemory > m_uiPeakReportedMemory) 
		m_uiPeakReportedMemory = m_uiTotalReportedMemory;

	if (m_uiTotalActualMemory  > m_uiPeakActualMemory)
		m_uiPeakActualMemory   = m_uiTotalActualMemory;

	if (m_lstUsedMemory.size() > m_uiPeakAllocUnitCount)
		m_uiPeakAllocUnitCount = m_lstUsedMemory.size();

	m_uiAccumulatedReportedMemory+= memory_block->m_szReportedSize;
	m_uiAccumulatedActualMemory += memory_block->m_szActualSize;
	m_uiAccumulatedAllocUnitCount++;

	FillBlock(memory_block, unusedPattern);

	if(m_bUseGC && no_free_blocks_in_gc)
		m_lstUsedMemory.push_back(memory_block);

	return memory_block->m_pReportedAddress;
}

Well, let's disassemble it. This function accepts new and new[] allocations, as well as malloc. It also needs to know how much memory is
needed to be allocated (in bytes). So, once it has those 2 parameters passed to it, it does the following thing:

1. Searches through the list in hope to find a deallocated block that has same memory size as the one requested
   1. If it finds one, it zero's its memory, moves its node from unused list to used list and returns the pointer.
2. If it doesn't find one, it allocates a new block with requested memory size and puts the pointer in the used list.

Yup, that's what is happening in this function. Well, at the bottom of it it calculates the statistical values for overall memory allocation.

OK, next thing is the Deallocate() function:

void CMemoryManager::Deallocate(void *ptr, int dealloc_type)
{
	// ---------------------------------------------------------------------------------------------------------------------------------
	// Deallocate memory and track it
	// ---------------------------------------------------------------------------------------------------------------------------------
	tMemoryBlock *dealloc_block = FindBlockByAddr(ptr);
	if(dealloc_block == NULL)
		return;
		
	// If you hit this assert, then the allocation unit that is about to be deallocated is damaged. But you probably
	// already know that from a previous assert you should have seen in validateblock() :)
	if(ValidateMemoryBlock(dealloc_block))
	{
		if(dealloc_type != 0)
		{
			// Remove this allocation from our stats
			m_uiTotalReportedMemory -= dealloc_block->m_szReportedSize;
			m_uiTotalActualMemory   -= dealloc_block->m_szActualSize;
		
			if(m_bUseGC)
				m_lstUnusedMemory.push_back(m_lstUsedMemory.remove(dealloc_block));
			else
			{
				free(dealloc_block->m_pActualAddress);
				delete m_lstUsedMemory.remove(dealloc_block);
				dealloc_block = NULL;
			}
		}
	}
}

What's going on here? Simple. Firstly, the passed memory pointer is found in the used list, then that pointer is validated (see ValidateBlock()).
If it's all OK, it puts the block pointer to used block list. You might add in here some kind of cache, e.g if a list is full (your amount), then do not
add anymore to it.

Obviously, for our manager to perform allocation/deallocation, we need to override new, new[], delete, and delete[] global operators. Here they are:

void* __cdecl operator new(size_t reportedSize)
{
	if (reportedSize == 0)
		reportedSize = 1;

	for(;;)
	{
		// Try the allocation

		void	*ptr = CGlobalMemoryManager::GetSingleton().Allocate(reportedSize, Memory_Allocation_New);
		if (ptr)			
			return ptr;
	}
}

// ---------------------------------------------------------------------------------------------------------------------------------

void* __cdecl operator new[](unsigned int reportedSize)
{
	if (reportedSize == 0)
		reportedSize = 1;

	// ANSI says: loop continuously because the error handler could possibly free up some memory
	for(;;)
	{
		// Try the allocation

		void	*ptr = CGlobalMemoryManager::GetSingleton().Allocate(reportedSize, Memory_Allocation_NewArray);
		if (ptr)
			return ptr;
	}
	
}

void* __cdecl operator new(size_t reportedSize, const char *sourceFile, int sourceLine)
{
	if (reportedSize == 0)
		reportedSize = 1;

	// ANSI says: loop continuously because the error handler could possibly free up some memory
	for(;;)
	{
		// Try the allocation

		void	*ptr = CGlobalMemoryManager::GetSingleton().Allocate(reportedSize, Memory_Allocation_New);
		if (ptr)
			return ptr;
	}
}

// ---------------------------------------------------------------------------------------------------------------------------------

void* __cdecl operator new[](size_t reportedSize, const char *sourceFile, int sourceLine)
{
	if (reportedSize == 0)
		reportedSize = 1;

	// ANSI says: loop continuously because the error handler could possibly free up some memory
	for(;;)
	{
		// Try the allocation

		void	*ptr = CGlobalMemoryManager::GetSingleton().Allocate(reportedSize, Memory_Allocation_NewArray);
		if (ptr)
			return ptr;
	}
}

void __cdecl operator delete(void *reportedAddress)
{
	if (reportedAddress) 
		CGlobalMemoryManager::GetSingleton().Deallocate(reportedAddress, Memory_Deallocation_Delete);
}

// ---------------------------------------------------------------------------------------------------------------------------------

As you see, they call the global memory manager, that is simply this:

class CGlobalMemoryManager : public CMemoryManager, public CSingleton<CGlobalMemoryManager>
{
public:

	CGlobalMemoryManager(){};
	virtual ~CGlobalMemoryManager() {};
};

Well,you probably are gonig to say - "That's easy! I can write that thing myself in an hour!" - Great, I say. Way to go. If you need it, please do it, or if you don't,
take this one!
OK, strayed off-topic, we're finally coming to the Specific Memory Manager. Hey! But what's about this memory manager for simple types (int, float, etc)?
Can't we use it to aid us? Of course we can! That's what that whole thing is about - code reusability. So, to actually have a specific memory manager, all we
have to do is to add new, new[], delete and delete[] operators to the structure/class we are gonig to use with that manager! Here's an example.

Let's take a Geometry Manager that will manage geometry for us. It looks like this:

class CGeometryEngine : public CMemoryManager, public CSingleton<CGeometryEngine>
{
public:
	CGeometryEngine(void);
	virtual ~CGeometryEngine(void);

	CGeometry *GetEntry(unsigned int index, eGeometryType type = Geometry_Unknown);

	int GetNextID()	// MODIFY!
	{	
		m_iLastID++;
		return m_iLastID; 
	};

private:
	int m_iLastID;
};

And, the Geometry class:

#undef new
#undef delete

class CGeometry
{
public:
	// Constructor / Destructor
	CGeometry(eGeometryType type = Geometry_Unknown);
	CGeometry(eGeometryType geom_type, void *pvdata, unsigned int prim_count, size_t prim_size);
	virtual ~CGeometry();

	void SetData(void *data, unsigned int primitive_count, unsigned int primitive_size);
	void *GetData();
	
	int GetID();
	eGeometryType GetType();

	unsigned int GetPrimCount();
	unsigned int GetPrimSize();

	void* operator new (size_t size); //implicitly declared as a member function
	void operator delete(void *p); //implicitly declared as a member function

private:

	int m_iUID;
	void *m_pvData;	// Already a vertex/texcoord/etc list, hence a buffer
	unsigned int m_uiPrimitiveCount; // E.g a number of vertices or triangles, etc
	size_t m_uiPrimitiveSize;	// E.g a sizeof(CVector3) etc number

protected:
	eGeometryType m_eGeomType;
};

As you may notice, we MUST use #undef's to say that we are going to use NOT the global new/delete operators, but those that are specified within the class.
Also, we have overriden the new/delete operators for the Geometry class (don't worry about the array allocation/deallocation yet). They look like this:

oid* CGeometry::operator new (size_t  size) throw (const char *)
{
	if(CGeometryEngine::GetSingletonPtr() !=NULL)
		return CGeometryEngine::GetSingleton().Allocate(size, Memory_Allocation_New);

	return NULL;
}

void CGeometry::operator delete (void *p)
{
	if(CGeometryEngine::GetSingletonPtr() !=NULL)
		CGeometryEngine::GetSingleton().Deallocate(p, Memory_Deallocation_Delete);
}

Way to go! Heaps easy! Work is done.
Take your time to look at my elegant approach. You may notice that I no more need the add/remove functions for the geometry manager, since those
are replaced by Allocate/Deallocate and they really do their work well with double buffering (used and unused lists).

If you got any questions, please take your time and e-mail me. I will be glad to answer any questions, related and not, to this and other tutorials.