[Valgrind-developers] Omega - An Instant Leak Detection Tool

[Bryan M. <om...@br...>]

Dear Valgrind Team,

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.

The above description can also be read here:
http://www.brainmurders.eclipse.co.uk/omega_introduction.txt

Thanks for your time and looking forward to any feedback that you might wish 
to give.

Bryan "Brain Murders" Meredith