Title ===== Omega - A Valgrind tool for instant memory leak detection. Designed by Bryan "Brain Murders" Meredith with grateful thanks to the Valgrind team for making their tool and techniques available under the GPL. Synopsis ======== Whilst Valgrind's MemCheck tool can currently detect and report that a memory leak has occurred, the debugging output only shows where the memory that has leaked was allocated. There are no clues as to where the last reference to the allocated block was lost. Omega uses a modified version of MemCheck's "definedness" ('V' bit tracking) technique in order to help track pointers to allocated memory, outputting debugging information when the final (hence Omega) pointer to an allocated block is over-written or lost through a call to free() or the stack unwinding. How it Works ============ The critical point in tracking leaking pointers is when a value is written into memory from a register. This can result in the creation of a new reference to an allocated block, the destruction of a current reference to an allocated block or both. If we determine that either the register to be written or the memory location to be written contains a pointer that we are tracking, we update our tracking system and report if we are losing the last pointer to a block. Because checking every single write to memory is going to cause a huge overhead, we use a modified version of MemCheck's 'V' bit tracking to give us a simple "are we dealing with a tracked pointer" check before we go on to more heavyweight processing. A Simple Example ---------------- The program under test calls malloc (or one of the other heap allocation functions). We generate an internal record to track the address and size of the new block and set the 'V' bits of the shadow register to indicate 'valid (0)'. Note that as with MemCheck, the default state of all shadow memory is 'invalid (1)'. Immediately before the register is written out to memory, we create a new temporary register that contains the result of a bitwise AND between the 'V' bits of the register and the memory location to be written. We now call a helper function passing this register. If the results of the AND is '0', we know that there is a state change that we have to track and so process accordingly, adding and/or deleting new back references in the internal record and generating user diagnostic as required. When we call free (or one of the other heap de-allocation functions), we do cleanup processing on our internal record. There are two key activities that must be performed at this point. 1) Set 'V' bits to any hanging pointers to 'invalid'. 2) Recursively remove references to any pointers that are within the memory area that we are about to free. As an option, during part 1 we could report on the hanging pointers. Note that stack unwinding would also perform part 2 to ensure that we don't leak through automatic variables going out of scope. 'V' bit Propagation ------------------- Unlike MemCheck, we only have one size of data to track - namely sizeof(void *). Another key difference is that we need the pointer to be unmolested for it to be of interest to us. The upshot of these two properties are that in the first version of Omega, not only can we further limit our checks to transfers of the appropriate width and alignment but any operation that changes the value during propagation causes the 'V' bits to be set to 'invalid', thus saving us from performing the expensive lookups and processing. As a later feature addition, it should be possible through some mechanism (possibly the suppression functionality) to indicate that a pointer at some positive offset to the allocated memory address should also be tracked. This would be of benefit to those that implement their own memory management. Optimisation ------------ As part of the tracking process, we also hold a sparse bitmap in nodes that cover an area of memory 64kB in size. Each bit within a bitmap node represents an aligned pointer in memory. The point of this second reference is to assist in the detection of tracked references within the stack and allocated memory blocks. Due to the compressed nature of the information, we can check if an area of memory is free of tracked pointers 32 possible pointers at a time. What We Can Detect ================== Using the above techniques, we can track the following leaks: Simple over-write of a tracked pointer. lastP = blah; Tracked pointer being modified. lastP++; Automatic variable going out of scope. { void *lastP = malloc(64); return; } Tracked pointer within allocated block being returned to OS. { void *arrayP = malloc(10 * sizeof(void *)); arrayP[1] = malloc(64); free(arrayP); } What We Don't Detect -------------------- This never results in the tracked pointer being saved into memory. It should be possible to add some state tracking to check if an allocated block has references when the stack unwinds but this sort of thing is usually either deliberate or easily fixed after a run through MemCheck. { new CFred(); return; } What Next? ========== I have to code it ;P I have produced this in order to obtain feedback as soon as possible on what will be a very useful tool both to my company and hopefully others. Any and all feedback gratefully received. I understand that some parts have probably been oversimplified and testing of the first implementation will reveal some shortcomings. The main thing is that the principle of using the 'V' bits to track pointers to allocated blocks is sound - implementation of the internal data structures for the allocated blocks, the reverse lookups and handling can be optimised over time as required and thus is not detailed here. This is not to say that I don't have a solution, it's just that it is one of many possible so not as interesting. Bryan "Brain Murders" Meredith Feel free to email me about this at omega@brainmurders.eclipse.co.uk so I can sort the incoming mail.