Building a simple C memory leak detector is not too difficult. I did it in a previous post in less than 200 lines. But once you add features, it becomes a lot more complicated.
What features am I talking about?
1) Allow use in programs with more than 1 source file.
2) Make fast enough to use in reasonably large programs.
3) C++ support (track allocations made with new and delete).
4) Detect use of mismatched allocation/deallocation (e.g. new and free).
5) Detect simple buffer overflows (writing off the end of an array).
6) Be generally helpful (errors should be handled gracefully).
7) Test everything well.
And of course it goes without saying that I wanted to keep it portable, and as simple as possible.
1) Allow use in programs with more than 1 source file.
The problem here is that doing everything in one header file is no longer possible. Since each source file must include the header file, each source would get a separate copy of the memory leak table. So the leak-detection code must be split into a header file and source file, and the source file must be compiled and linked in to the program. This makes the whole process much less seamless than adding a single #include to the user’s code, but unfortunately there’s not really a better alternative.
2) Make fast enough to use in reasonably large programs.
Conceptually, this is simple. We to store our memory entries in a data structure that allows fast unordered lookup, insertion and deletion of key value pairs. A hash table is the perfect choice. Since C doesn’t have a built-in one, I wrote a simple one myself – basically a large array of linked lists.
The only difficult here is that unlike a simple array, we can’t simply realloc to enlarge the table. There are clever ways to rehash, but performance-wise, it isn’t really worth it. I chose to simply to create a new table, remove each entry from the old one, and insert it into the new one.
The net result is pretty good. In a program with 800k memory allocations, the penalty of my leak detection machinery on a 2GHZ machine is still less than 1 second.
3) C++ support.
Memory allocation in C++ is done via the new and delete operators. Because they are operators, using simple macros to override them like in C with malloc/free so as to include where each allocation/deallocation occurred doesn’t work.
In C I could simply do:
#define malloc(n) mymalloc(n, __FILE__, __LINE__)
That doesn’t work in C++. The best I could come up with was to override the operators directly, and use a fairly nasty macro, plus global variables, to track where the allocations are coming from. Something along the lines of:
int _line;
char *_file;
#define new (_file=__FILE__, _line=__LINE__) && 0 ? NULL : new
#define delete _leaker_file=__FILE__, _line=__LINE__, delete
void *operator new(int size)
{
// do stuff
ptr = mymalloc(size);
_Leaker_Insert(ptr, _file, _line);
return ptr;
}
void operator delete(void *ptr)
{
_Leaker_Remove(ptr, _file, _line);
}
4) Detect use of mismatched allocation/deallocation.
This isn’t terribly difficult. Each allocation record now has a field for the type of allocation used to create it. When a deallocation function is called, we check that this type is compatible with the function that was just called.
5) Detect simple buffer overflows.
This is also not to difficult. We pad each allocation with a few extra bytes, initialized to some special string. Then when we deallocate, we check that the padding hasn’t changed. Of course, the special string should be unlikely to be something we would actually write to memory. I chose some unprintable ASCII values in a 4-byte string. Note that while this detects whether there was an overflow once the deallocation occurs, it doesn’t tell us where overflow was. Technically writing off the front of an array could also be checked this way, but it’s a relatively uncommon error, so I didn’t bother implementing that checking.
6) Be generally helpful.
Basically, this means writing informative error messages. Harder than it looks, particular since the intended audience is people who are new(ish) to this sort of thing.
7) Test everything well.
This, believe it or not, was the hardest (and most time-consuming) part of the process. As my compilers instructor says, to test something well, you have to have coverage and correctness. That means the tests have to exercise every possible code-path, and every possible feature, preferably in as many combinations as possible.
I wound up writing about 100 tests, as well as running the code in several real-world-ish programs. I’m sure there are still some bugs, but hopefully the basic functionality is pretty solid. I even uncovered a small but real compiler bug in the current version of the Clang compiler.