Tuesday, September 18, 2012

Memory management 1/2

Hey guys!

As I promised before via Twitter, this post is about the memory management / tracking systems we use in our K15 EngineV2 (I hate that name...gotta change it soon).

Memory leak detection and memory tracking

Memory leaks...At least every serious C/C++ programmer has had several in his career. They are hard to track and solve sometimes. Sure, there are tools that help you with that such as Application Verifier from Microsoft or some other debug helper, but they are either ridiculously slow during run-time or hard to configure. 

I've decided to implement a very, very easy to program but nevertheless efficient memory leak detection system which also can be used to track memory usage of the engine at the same time.

Lets start off by creating a new struct to hold all those useful information that we want to track.

 struct MemoryBlock  
           MemoryBlock *Next;          /*Address to next memory block*/  
           MemoryBlock *Previous;     /*Address to previous memory block*/  
           const char *File;          /*File the allocation occurred*/  
           unsigned int Line;          /*Line at which the new call happened*/  
           unsigned int Size;          /*Size of the allocated memory*/  
           bool IsArray;               /*Was the memory allocated by new[]?*/  

The first two members (namely Next and Previous) are to keep track of each MemoryBlock in a linked list (we'll come to that later).

The next member File and Line are to keep track of where exactly the new call of the leaking memory occurred. That gives you a good idea of where to start looking for errors in your code.

Member Size is to keep track of how much memory has been allocated and with IsArray you can check whether or not the memory has been allocated via new[] or new.

The next step would be to overload global new, new[], delete and delete[]. This is easily done:

 void *operator new[](unsigned int iSize,const char* sFile,unsigned int iLineNumber);  
 void *operator new(unsigned int iSize,const char* sFile,unsigned int iLineNumber);  
 void operator delete[](void* pPointer);  
 void operator delete(void* pPointer);  

You may wonder where the parameter sFile and iLineNumber are getting filled in the new[] and new operators (iSize is getting filled automatically). For this purpose I created a simple macro that looks like this:

 #define K15_NEW new(__FILE__,__LINE__)  

Whenever you use K15_NEW instead of the normal new (or new[]) operator, the global new operators that we just declared are getting called (If you're unfamiliar with the __FILE__ and __LINE__ macros just look here).

What we do next is to declare a function that does all the dirty work for us (allocating memory, expand the linked list of MemoryBlock structs, counting the call to new and add the size of the new memory to an internal counter).

This would be the code of such a function:

 void *Allocate(unsigned int iSize,const char* sFile,unsigned int iLine,bool isArray)  
      //We need some more size for the MemoryBlock struct.  
      iSize += sizeof(MemoryBlock);  
      //Allocate memory.  
      char *pPointer = malloc(iSize);  
      //This function does fill the MemoryBlock struct and add it to the linked list.  
      //We need to shift the memory so that the memory we return is the memory the user wanted.  
      pPointer += sizeof(MemoryBlock);  
      return pPointer;  

 void ProtocolMemoryAllocation( void* pPointer,unsigned int iSize,const char* sFile,unsigned int iLineNumber,bool bArray )  
      MemoryBlock* pBlock = (MemoryBlock*)pPointer;  
      //Set all the flags  
      pBlock->IsArray = bArray;  
      pBlock->Size = iSize;  
      pBlock->File = sFile;  
      pBlock->Line = iLineNumber;  
      //Add block to linked list.  
      //Increase size of allocated memory (to keep track of the memory usage)  
      ms_iAllocatedMemory += iSize;  
      //Increment the counter that keeps track of new/delete calls.  

The same goes for deallocation:

 void Free( char *pPointer,bool bArray )  
      //Shift the pointer so that it points to the whole memory block that we allocated previously  
      //(including MemoryBlock).  
      pPointer -= sizeof(MemoryBlock);  
      //Delete the linkedlist entry and do decrease the new/delete counter.  
      //finally free the memory.  

 void ProtocolMemoryDeallocation( void* pPointer,bool bArray )  
       MemoryBlock *pBlock = (MemoryBlock*)pPointer;  
      //Does the memory gets freed with delete[] if it got allocated with new[]?  
       assert(bArray == pBlock->IsArray);  
      //Decrease the amount of currently allocated memory.  
       ms_iAllocatedMemory -= pBlock->Size;  
      //Decrement the new/delete counter.  
      //Remove the block from the linked list of MemoryBlock structs.  

The next thing we need to do to implement the memory tracker is to call the above implement functions by our overloaded new, new[], delete and delete[] operators. This is an easy task:

 void *operator new[](unsigned int iSize,const char* sFile,unsigned int sLineNumber)  
      return Allocate(iSize,sFile,sLineNumber,true);  
 void *operator new(unsigned int iSize,const char* sFile,unsigned int sLineNumber)  
      return Allocate(iSize,sFile,sLineNumber,false);  
 void operator delete[](void* pPointer)  
 void operator delete(void* pPointer)  

To add a little bit of leak detection, we could implement yet another function that iterates over the list of MemoryBlock structs (which should be empty if there's no leak in your application) and print the desired information into a log file or a message box. Call this function at the end of your application and you're good to go!

That's it...We now implemented a fully working and yet efficient memory tracking and leak detection tool.

The next post will be completely about memory management. I'll introduce two different approaches to  memory management (being a memory pool and a memory heap).

Verse network protocol

I recently watched this video of Eskil Steenberg, the creator of Love, talking about the tools he created for Love and the Verse network protocol he used to synchronize the 3D models between his tools.

I find that technology amazing! I just downloaded some papers describing the protocol (how it works, etc.) - maybe we can add this technology to our very own tools, allowing the 3D artists working with their favorite modelling tool (Blender for instance has native Verse support) while examining the results live in the editor of our engine.

I bet our 3D modeler at K15 Games will wet his pants if I tell him about that ;)