exp-omega/docs/omega_introduction.txt

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 and my employer Apertio (www.apertio.com) for allowing the use of
their time, equipment for 64bit testing and providing moral support.

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 main task in tracking leaks is when a checking whenever a value is
written into memory or 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 causes a huge overhead,
we make a couple of assumptions about what constitutes a pointer in
order to reduce hash table lookups of the internal data. In order to
optimise checking for pointers during free() and stack unwinding, we
maintain a set of PBits (Pointer Bits) that allow us to quickly check
a range of addresses for pointers that will be lost.

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.

At each time we write to memory or a register is loaded, we check to
see if we have a tracked pointer record for the location about to be
written. If so, we remove this record and decrement the reference
count for the block that it pointed to, generating an alarm if this
was the last reference. We check if the value that we are writing
matches the address of an allocated block. If we get a match, we add a
tracked pointer record for the written address and increment the
reference count. To speed things up, the internal records are stored
in hash tables.

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) Clear and deallocate any hanging pointers.

2) Recursively remove references to any pointers that are within the
   memory area that we are about to free.

As an option, during stage 1 we could report on the hanging pointers.

Note that stack unwinding also performs stage 2 to ensure that we
don't leak through automatic variables going out of scope.

'P' bit Propagation
-------------------

Each time we see an address of a memory block being written into an
address or register, in addition to setting up the tracked pointer
record, we also set a PBit to show that there is a tracked record for
the address. By using PBit lookups and caching the PBit nodes between
lookups (along with a dedicated PBit node for registers) we can get a
significant performance gain. The time when PBits really come into
their own is when we need to clear all of the tracked pointer records
from a range of memory ie. invalidating the stack, calling
free(). Using the PBit mechanism, we can check upto 64K in one
go. This can be a huge gain as many structures do not hold nested
pointers to allocated memory.

Stuff that I really want to add
===============================

Client Calls - This would allow us to track client based memory pool
implementations, MALLOC_LIKE_BLOCK() etc.

Summary Report - I want some feedback on what the output of the Omega
should be so watch this space.

Suppression Support - I don't know how much this is needed but it
would probably be worthwhile.

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 (we wont raise a leak report on this -
we will track the offset within the block - see "Shadowing").

  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);
  }

Shadowing
=========

This helps to solve the problem of where a program does its own memory
management of the kind:

  1  secret *foo = malloc(sizeof(bar) + sizeof(secret) + alignment_correction);
  2  foo->secret_stuff = magic_key;
  3      etc.
  4  foo++;
  5  return (bar*)foo;

If the pointer to foo is shadowed at some internal offset to the block
start, we create a shadow record and link it to the main block so that
we can track references to either. Without this we do a leak alert at
line 4 instead which is undesireable. There can only be one shadow to
a block unless we really need more and someone wants to code it and
send me a patch.

What We Don't Detect
--------------------

Actually, we do pretty well here but there are a couple of things you
need to know about.

1) We track pointers in registers. Therefore, whilst the final code
   reference (on the stack say) may be lost, the pointer can (and
   does) live on within a register until the register is
   overwritten. The best way to help prevent this from making late
   reports is to compile with -O0. On x86, this makes quite a
   difference, especially to non-trivial functions.

2) Some code is a little naughty when it comes to memory blocks that
   have been returned to the OS. Memcheck reports these read accesses
   to free()ed blocks as illegal reads. Omega also reports them as it
   gets annoyed when it has just reported a block as leaked only for a
   pointer to appear from "no-where". (Calling free() on a block does
   not erase the contents of the block so even though Omega removes
   all tracked pointer records for addresses within the block, the
   pointers themselves still exist. Once one of these pointers is
   read, Omega tracks it being loaded into a register at which point,
   it complains and resumes tracking the "leaked" block.)

What Next?
==========

Feedback!!!

The core of the tool is done and working. Now I need feedback from
anyone out there that is interested in using it so I can make the
output as usefull as it can be.

If anyone is interested in helping me out on this, send your
patches. I hope to get this accepted into Valgrind so it can get some
serious attention but I dont know if that will happen so I will try to
maintain a patch against svn or a tar of the whole thing if that gets
too troublesome.

Bryan "Brain Murders" Meredith.  The current maintainer of Omega is
Rich Coe <richard.coe@med.ge.com>.  Please send all email regarding
Omega to Rich.