Memory Manager: Part #1

Table of Contents

• What do we need it for?
• Code (The)
• More Code
• And.. Even more code

Welcome to the tutorial about the memory managing, the most fearsome tutorial in
the whole history of programming.... (add scary pictures & thingies here).
No, I'm kidding. By the end of this tutorial, you will be looking back and saying:
"Gee, how have I lived without it? It's so easy!"

What do we need it for?

Well, as any tutorial written here, you will need 2 basic classes that you will use
in conjunction in this project. They are... The List class and a Logger class!
Haha, tricked ya! You can probably use your own list and logger classes, but hey,
its up to you if you want to replace all relevant code in the project.

OK, so what do we need to write the memory manager for

1. Debugging purposes
2. Memory savings
3. To have something to write in our spare time!

Well, now we know what we need it for, let's see some code.

Code (The)

Well, here is our beloved memory manager:

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(bool unused = true);

	void SetOwner(const char *file, unsigned int line, const char* func);
	
	void EnableGC();
	bool GetGC();
	void DisableGC();

private:

	unsigned int GetNextUID();
        	
	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()
	// A good idea here is to limit the unused memory blocks to some fixed number and DO NOT
	// move memory unallocated into it, so that we don't run into problem on
	// spending more time looking for a pointer with similar size than unallocating the pointer.
	bool m_bUseGC;
	unsigned int m_uiLastUID;
	
	CDoubleList <tMemoryBlock *> m_lstUnusedMemory;
	CDoubleList <tMemoryBlock *> m_lstUsedMemory;

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

};

Yep, its pretty big. Let's see what each thing here is for:

1. The main functions, Allocate & Deallocate deal with... You right, allocation and
   deallocation of memory. They accept the type of allocation and the size of it, and then
   deal with 'em in the way I'll describe later.
2. The Dump* functions are here for the the debug purposes
3. The FreeAll function frees all allocated (and unallocated) memory
4. The SetOwner function shouldn't be used by public, but it sets the debugging information,
   like the file, line and function of where the pointer was allocated at.
5. And the Enable/Disable GC functions obviously enable/disable the use of GC (Garbage Collector)
   within our memory manager (the garbage in our case is the unallocated memory)

OK, so far so good for public declarations. Now lets see what our protected/private functions do:

1. FillBlock function fills the block' memory with a pattern corresponding to current memory block state (used, unused, etc)
2. ValidateMemoryBlock, um.. validates the, um.. 'validity' of a memory block by checking it's patterns.

Ok, thats it for functions, lets see our member variables declarations:

1. All those m_ui* variables are the statistical variables that track how much memory we accumulated, allocated, etc.
2. The m_Logger variable is a local logger that we are going to use to write to.. well, logging file.
3. m_bUseGC boolean variable is an important one. It tracks whether or not the user wants to use GC.
4. And finally, the m_lstUnusedMemory & m_lstUsedMemory are the lists holding the pointers to memory blocks that are,
   obviously, allocated ( in m_lstUsedMemory) and unallocated - or freed ( in m_lstUnusedMemory).

By the way, here is our tMemoryBlock structure, in case you wanted to know:

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()
	{

	};
};

In it, as you may see, some attributes exist. I'm not going to explain which and what for, because their names
are pretty self explanatory.
Well, so far so good. Of course, the hardest part in ANY code is the IMPLEMENTATION, not prototyping. So, let's see our implementation.

More Code

We will start with the hardest part - Allocate and Deallocate functions:

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)
			{
				#ifdef MMGR_DEBUG_MODE
					CGlobalLogger::GetSingleton().Write("Using pre-existing allocation at 0x%x\n", memory_block->m_pActualAddress);
				#endif
				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;
}

As you may see, the general logic here is: "Let's see if we have an already allocated memory block,
and if we have one, lets use it instead of allocating a new one by using CPU-expensive malloc() function. Otherwise,
allocate a new memory using malloc()."
That is its basic functionality in one sentence. Do you need more? Well, take a look closer, and you will see
all you need to see...

Yes, that was the Allocate. Now, to Deallocate.

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)
			{
				#ifdef MMGR_DEBUG_MODE
					CGlobalLogger::GetSingleton().Write("Saving pointer for further use: 0x%x\n", dealloc_block->m_pActualAddress);
				#endif
				m_lstUnusedMemory.push_back(m_lstUsedMemory.remove(dealloc_block));
			}
			else
			{
				free(dealloc_block->m_pActualAddress);
				delete m_lstUsedMemory.remove(dealloc_block);
				dealloc_block = NULL;
			}
		}
	}
}

Here, we firstly find the block that contains the memory pointer we need. Then, we validate it,
to make sure it's still uncorrupted. But then, if the m_bUseGC is set to true, we DO NOT deallocate
this memory pointer, but instead put it into GC pool for future use. Easy? Cool.

Well, we got so far. Now, lets see how we can employ all we have got and make something useful out of it.
Right now, our manager can only track basic data types - integers, floats, characters, etc. We will go into detail
on how to track other data types in our next tutorial.
OK, to have a global memory manager that will do all of the above (look after basic types), we have to do the
following thing:

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

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

"Is that it?" you may ask. Pretty much, yes. The only thing left to do is to declare a static variable somewhere in the
main file so we can actually use it:

static CGlobalLogger g_Logger("MemoryLog.txt");

Or you can instantiate it by creating a pointer to it (e.g CGobalLogger *pLogger = new CGlobalLogger("MemoryLog.txt"))

Well, that's about it.
Since you cannot call any member functions in the singleton' destructor, you must call FreeAll() at the end of the program.
Play around with it, modify it to your will (don't forget to pass on credits!) and see what else cool it can do.

Next tutorial we will go into specific memory managers, the ones that you can use to track custom data types.
Cyas soon!