Memory leaks are a common occurrence in C programs, particularly for novice programmers.  Because memory allocation and deallocation is left to the programmers, it’s not difficult to lose track of what was allocated where, and forget to deallocate it once it is no longer in use.  The is particularly true for more complex data structures which may have dynamically allocated blocks of memory that reference other dynamically allocated blocks of memory.

There are a fair number of tools to deal with this, like valgrind.  Still, building a simple detector is a relatively straightforward exercise, and can often reveal interesting things.

The basic idea is to track allocations and deallocations with a table.  Each time a block of memory is allocated, you add the starting address of the block to your table.  Each time a block is deallocated, you check your table and remove the entry for that address.  If at the end of your program, the table is not empty, you know you have a leak.

Of course, once you know that you have a leak, it’s nice to be able to find where in your program you did the allocation that got leaked.  Here, it pays to use the right data structure.  If in addition to the address, each entry in your table stores where the allocation occured, then when you do your final check to see what was leaked, you can not only print the address of the leaked blocks, but where they were created.

Happily, the C preprocessor allows one to rather seamlessly do most of this.  First, you create your own custom allocator and deallocator functions which are responsibly for managing the allocation table, and calling the real memory management functions (e.g. myMalloc calls malloc, myFree calls free and so forth).  Next, you use the C preprocessor to override the standard memory functions with your version via macros.  You can also use the preprocessor to insert the line number and filenames of into your allocators (e.g. #define malloc(x) myMalloc(x, __FILE__, __LINE__)  ).  What’s neat about this method is that the preprocessor will expand each call prior to compilation, and so the correct filename and line end up being automagically inserted as arguments to the call to your function.

In practice, once you have the table set up, you can do more sophisticated checking too, such as telling users when the deallocate something that wasn’t allocated, or when they use the wrong deallocation function in C++.

Next time: a working example.