flipcode - How To Find Memory Leaks

How To Find Memory Leaks
by (23 May 2000)

Introduction

I was recently working on a rather large project, the largest I had ever been involved with. We didn't have a concrete design document on this project so ideas and implementations were constantly changing. This is a great flexibility from a design/creation standpoint, but from a programming perspective it ended up becoming a rather large mess. Deep into the project we realized that with release date approaching we should tackle the task of cleaning up the garbage code and stabilizing it for alpha testing. Being a small company however meant that programs like BoundsChecker© from NuMega were just not within our reach. So we had to improvise. We needed a drop in solution to our current code base (the code base was entirely C++). We didn't want a project specific fix however. We needed a simple solution that could easily be compiled into this project and any other. Then at the end of runtime it would generate a list of the un-freed memory blocks. Well, of course we found it, otherwise this article would not be. We'll be right back after these messages to bring you the solution!

We're back. Let me elaborate more on exactly what we needed in our "memory tracer". We first needed something that could be added to any existing code base. Code reuse is a very important consideration, especially to a company. It can potentially save hundreds of hours and thousands of dollars. Secondly, our solution had to be simple. We didn't have time nor the courage to wade through thousands of lines of code doing re-writes and fixes to accommodate our memory tracer. And finally, it had to be free.

So we took a look at our code. The first thing we noticed is that nearly all of our memory allocations were accomplished through the operator new and variants. And likewise the de-allocations were accomplished through delete and variants. Well, we could replace all occurrences of new and delete with proprietary functions that tracked our memory for us? No! Too many replacements! C++ allows you to override new and delete in your classes. That would be great news if it didn't mean adding these overrides to all our classes. Wait a minute... I can override the global new and delete operators!!! Now I can do whatever just before each memory allocation and de-allocation! This great news! Sort of. I had actually known about this in a roundabout way. You see, MFC also has this ability. It is exploited through some of the _Crt() functions. Now that we have our back door, all we need to do is to track the allocations and cross-reference them with the de-allocations at destruction time. What doesn't get referenced is a leak. Simple.

Lets get to the workings of it shall we. All my work and references are written using Visual C++. It should be trivial to convert to other vendors. The first thing to do is to override new and delete so that they will be overridden everywhere in the program. In stdafx.h, I add:


      #ifdef _DEBUG
      inline void * __cdecl operator new(unsigned int size, 
                                         const char *file, int line)
      {
      };

      inline void __cdecl operator delete(void *p)
      {
      };
      #endif

These are my overridden functions. And by encasing them with #ifdef/#endif quotes, I don't get sub-par code with Release builds. When you look at the code you'll notice that new has been overridden with three parameters. These are the size of the requested allocation as well as the file and line from the source file where the allocation takes place. This is necessary in finding where the leaks are. Otherwise they would take a lot of assembly digging to find. By adding this however, all our code base that calls new() still refers to the operator new function that accepts one parameter, and not our three parameter new function. In addition, we wouldn't want to recode all our new operator statements to include the __FILE__ and __LINE__ arguments. What we need to do is to automatically make the one-parameter new operator call a three-parameter new operator call. This can be accomplished with some macro trickery.


      #ifdef _DEBUG
      #define DEBUG_NEW new(__FILE__, __LINE__)
      #else
      #define DEBUG_NEW new
      #endif
      #define new DEBUG_NEW

Now all of our one-parameter new operator calls are three parameter new calls with the __FILE__ and __LINE__ automatically inserted by the pre-compiler. Now is time for the actual tracking. We should also add the memory routines to our overridden functions so that they at least do what the old new/delete operator functions did.


      #ifdef _DEBUG
      inline void * __cdecl operator new(unsigned int size,
                                         const char *file, int line)
      {
	      void *ptr = (void *)malloc(size);
	      AddTrack((DWORD)ptr, size, file, line);
	      return(ptr);
      };
      inline void __cdecl operator delete(void *p)
      {
	      RemoveTrack((DWORD)p);
	      free(p);
      };
      #endif

In addition to these, you may also need to override the new[] and delete[] operators as well. They are the same so I just left them out to save space.

Finally we need to supply some code the tracking functions AddTrack() and RemoveTrack(). I use the STL to maintain my linked list of allocations. You can use whatever. They two functions can contain any code you wish and then some. But I'll provide you with my version just in case you have coders block.


      typedef struct {
	      DWORD	address;
	      DWORD	size;
	      char	file[64];
	      DWORD	line;
      } ALLOC_INFO;

      typedef list<ALLOC_INFO*> AllocList;

      AllocList *allocList;

      void AddTrack(DWORD addr,  DWORD asize,  const char *fname, DWORD lnum)
      {
	      ALLOC_INFO *info;

	      if(!allocList) {
		      allocList = new(AllocList);
	      }

	      info = new(ALLOC_INFO);
	      info->address = addr;
	      strncpy(info->file, fname, 63);
	      info->line = lnum;
	      info->size = asize;
	      allocList->insert(allocList->begin(), info);
      };

      void RemoveTrack(DWORD addr)
      {
	      AllocList::iterator i;

	      if(!allocList)
		      return;
	      for(i = allocList->begin(); i != allocList->end(); i++)
	      {
		      if((*i)->address == addr)
		      {
			      allocList->remove((*i));
			      break;
		      }
	      }
      };

Now, at the very last moment before our program exits, allocList is a list of all memory allocations that have not been freed. But in order to see what and where they are, you need to dump the information stored within allocList. I use the output window in Visual C++ for this. You can format this information in any way but what I've provided just dumps the list of information. Note that using the debug output window of Visual C++ may result in some lines of text not getting outputted before it cuts off.


      void DumpUnfreed()
      {
	      AllocList::iterator i;
	      DWORD totalSize = 0;
	      char buf[1024];

	      if(!allocList)
		      return;

	      for(i = allocList->begin(); i != allocList->end(); i++) {
		      sprintf(buf, "%-50s:\t\tLINE %d,\t\tADDRESS %d\t%d unfreed\n",
			      (*i)->file, (*i)->line, (*i)->address, (*i)->size);
		      OutputDebugString(buf);
		      totalSize += (*i)->size;
	      }
	      sprintf(buf, "-----------------------------------------------------------\n");
	      OutputDebugString(buf);
	      sprintf(buf, "Total Unfreed: %d bytes\n", totalSize);
	      OutputDebugString(buf);
      };

There you have it. A bit of reusable code that you can use in all your projects to track all your memory leaks. I always add these functions to every project I start working on and I've used them to clean up projects already completed. It may not help make your game look the best, but it will hopefully help stabilize it. Take care everyone and send me any and all comments.