Omega
An Instant Leak Detector Tool
for Valgrind
Omega addresses what I perceive to be one of the few shortfalls of the excellent Valgrind Memcheck Tool - where Memcheck reports the location that a leaked block was allocated, Omega also shows where it was leaked. As the author is acutely aware, as the complexity of a state machine increases, the ease of locating leaked memory blocks diminishes greatly. Locating and fixing these leaks can be tedious and extremely time consuming.
Omega works by tracking pointers to allocated blocks. A leak occurs when the last pointer is destroyed, either by being overwritten or going out of scope. As this last pointer loss is what causes the leak, the name Omega (last letter of the Greek alphabet + loads of symbolism for the end of "stuff" that you can google for if you are interested) seemed appropriate.
Omega is available as a "difference" file to the Valgrind Subversion trunk. It is maintained outside of the main Valgrind tool but you can get the current (RC 1) patch from here. If you downloaded previous beta patches, you are advised to upgrade.
Once you have downloaded the latest Omega patch, you need to obtain a copy of the Valgrind source. Instructions for doing that are here. Assuming that you have checked out the Valgrind source into the directory 'valgrind', you can apply the Omega patch like this:
$> cd valgrind $> gunzip -c /path_to/omega_patch_name.patch.gz | patch -p0
You can now follow the rest of the instructions here to build and install Valgrind.
For the absolute best results, your program should be compiled with "-O0 -g". Omega has been tuned to look for certain things. Unfortunately, the optimisations made by the compiler greatly diminishes what can be detected accurately, if at all. A particular problem is that optimisation tends to inline functions, thus giving Omega no way to detect scope related issues as the function exits. If you are running optimised code, there are likely to be a lot of false positives reported and not all of them will be rescinded. The final summary report will also be of poor quality by comparison. The "-g" option is essential as without it, Omega will not be able to accurately report line numbers for you. Finally, use Memcheck. It really is a great tool for finding all sorts of problems so it's highly recommended that you clean up until you just have memory leaks left.
Omega normally tracks all allocations but if you want to target a particular area, you can use the Valgrind MALLOCLIKE_BLOCK user request call instead. However, note that you still need to compile with "-O0 -g" for quality results. See the Valgrind manual for how to make use of MALLOCLIKE_BLOCK and FREELIKE_BLOCK.
Lets say you have something along the lines of this:
1 secret *foo = (secret *)malloc(sizeof(bar) + sizeof(secret) + alignment_correction); 2 foo->secret_stuff = magic_key; 3 etc. 4 foo++; 5 return (bar*)foo;
Internally, Omega uses shadow blocks to track references within an allocated block. Thus, when you increase "foo" on line 4, Omega creates a shadow block that ties back to the main block allocated at line 1 instead of raising a leak report. In theory, you could have a number of shadow blocks per allocated block but this is explicitly prevented for now as it makes some of the checking overly complex. Alternatively, use the MALLOCLIKE_BLOCK macro as this is the very situation it was designed to support.
Omega has a few runtime options that you can use but normally, you can just run it like this:
$> valgrind --tool=omega <programname>
OK. Let's run Memcheck and Omega on a small test program so you can see what to expect.
01 #include <stdlib.h>
02
03 static void func1(void)
04 {
05 char *pointer = 0;
06
07 pointer = malloc(64);
08
09 return;
10 } /* Leak report here */
11
12 int main(int argc, char *argv[])
13 {
14 func1();
15
16 return 0;
17 }
18 Save that (without the line numbers) as scope2.c then compile it like this:
$> gcc -g -O0 scope2.c -o scope $> gcc -g -O2 scope2.c -o scope_opti
We have made optimised and non-optimised versions so that you can see the differences in output. Looking at the program, it's quite obvious that we have a memory leak as "pointer" in "func1()" goes out of scope at line 10 and that is the only pointer to the block of 64 bytes that are allocated at line 7. Yes, this is a simple example (you can find the source for this and other test programs in "omega/tests") but it demonstrates the point and the principles scale up.
Lets run Memcheck first:
$> valgrind --tool=memcheck --leak-check=full ./scope ==13293== Memcheck, a memory error detector. ==13293== Copyright (C) 2002-2005, and GNU GPL'd, by Julian Seward et al. ==13293== Using LibVEX rev 1419, a library for dynamic binary translation. ==13293== Copyright (C) 2004-2005, and GNU GPL'd, by OpenWorks LLP. ==13293== Using valgrind-3.2.0.SVN, a dynamic binary instrumentation framework. ==13293== Copyright (C) 2000-2005, and GNU GPL'd, by Julian Seward et al. ==13293== For more details, rerun with: -v ==13293== ==13293== ==13293== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 11 from 1) ==13293== malloc/free: in use at exit: 64 bytes in 1 blocks. ==13293== malloc/free: 1 allocs, 0 frees, 64 bytes allocated. ==13293== For counts of detected errors, rerun with: -v ==13293== searching for pointers to 1 not-freed blocks. ==13293== checked 56,168 bytes. ==13293== ==13293== 64 bytes in 1 blocks are definitely lost in loss record 1 of 1 ==13293== at 0x401B51E: malloc (vg_replace_malloc.c:149) ==13293== by 0x8048372: func1 (scope2.c:7) ==13293== by 0x804838F: main (scope2.c:14) ==13293== ==13293== LEAK SUMMARY: ==13293== definitely lost: 64 bytes in 1 blocks. ==13293== possibly lost: 0 bytes in 0 blocks. ==13293== still reachable: 0 bytes in 0 blocks. ==13293== suppressed: 0 bytes in 0 blocks. ==13293== Reachable blocks (those to which a pointer was found) are not shown. ==13293== To see them, rerun with: --show-reachable=yes
As expected, Memcheck identifies that the block allocated at line 7 has leaked. Whilst with this trivial example, its obvious where the leak occurred, tracking down memory leaks can be a really tedious and time consuming exercise. So, lets try Omega to see if it can help us out:
$> valgrind --tool=omega ./scope ==13297== Omega-beta2, An instant memory leak detector. ==13297== Copyright (C) 2006, and GNU GPL'd, by Bryan Meredith. ==13297== Using LibVEX rev 1419, a library for dynamic binary translation. ==13297== Copyright (C) 2004-2005, and GNU GPL'd, by OpenWorks LLP. ==13297== Using valgrind-3.2.0.SVN, a dynamic binary instrumentation framework. ==13297== Copyright (C) 2000-2005, and GNU GPL'd, by Julian Seward et al. ==13297== For more details, rerun with: -v ==13297== ==13297== ==13297== ==13297== ==13297== Omega Leak Summary ==13297== ================== ==13297== Loss Record 1: Leaked 64 (0x40) bytes in 1 block ==13297== at 0x8048379: func1 (scope2.c:10) ==13297== by 0x804838F: main (scope2.c:14) ==13297== Block allocated ==13297== at 0x401AE7E: malloc (vg_replace_malloc.c:149) ==13297== by 0x8048372: func1 (scope2.c:7) ==13297== by 0x804838F: main (scope2.c:14) ==13297==
See the difference? Omega not only shows that the block allocated at line 7 leaked, it shows you that it leaked at line 10. Lets try again with the optimised version to show why compiling with "-O0 -g" is such a good idea.
$> valgrind --tool=omega ./scope_opti ==22234== Omega-beta5, An instant memory leak detector. ==22234== Copyright (C) 2006, and GNU GPL'd, by Bryan Meredith. ==22234== Using LibVEX rev 1419, a library for dynamic binary translation. ==22234== Copyright (C) 2004-2006, and GNU GPL'd, by OpenWorks LLP. ==22234== Using valgrind-3.3.0.SVN, a dynamic binary instrumentation framework. ==22234== Copyright (C) 2000-2006, and GNU GPL'd, by Julian Seward et al. ==22234== For more details, rerun with: -v ==22234== ==22234== ==22234== ==22234== ==22234== Omega Leak Summary ==22234== ================== ==22234== Loss Record 1: Leaked 64 (0x40) bytes in 1 block ==22234== at 0x4A20187: malloc (vg_replace_malloc.c:149) ==22234== by 0x4B3F153: (below main) (in /lib64/libc-2.4.so) ==22234== Block allocated ==22234== at 0x4A20159: malloc (vg_replace_malloc.c:149) ==22234== by 0x40050D: main (scope2.c:7) ==22234==
Look at the difference this time. Leaked where??? Has it gone mad?
The compiler has in-lined "func1". As a result of this and other optimisations (“pointer” doesn't exist any more for instance), the resulting output is about as useless as it possibly could be. So, “-O0 -g” is most definitely your friend.
The first option of particular use is "--only-malloclike". This switches Omega from automatically tracking all allocated blocks to only tracking blocks that are marked with the MALLOCLIKE_BLOCK() macro. If Memcheck is reporting a leak from a particular block, you could alter your source to mark the block and where the block is free()d. This is of particular use if you have your own custom allocators and want to check if the "lumps" passed out to your callers are being returned without having the noise from the rest of your program.
The "--instant-reports" option can be a mixed blessing. On the one hand, Omega will show you what it sees as it happens. On the other hand, you will possibly see some false positives being generated and rescinded which can be a little intimidating and can also generate a LOT of output.
If you have allocated a block (block B) and place a pointer to it into another allocated block (block A), the "--show-indirect" option could be useful to you. If the only remaining pointer to block B is the pointer in block A and block A leaked, Omega will not report that block B has also leaked during –instant-reports. Using the "--show-indirect" option will make Omega follow the entire chain, reporting all leaks as appropriate. Note that leaked blocks will still show in the leak summary regardless of this option.
A circular reference is when one block holds a pointer to another block and vice-versa. Although each block has a valid pointer to it, because there are no pointers external to the blocks, the memory is effectively lost. With this option, as Omega exits, it will scan all of the blocks that have not been reported as leaking and checks that they have an external reference. A long chain of blocks with an external reference to the first block is fine. A long chain of blocks with an external reference to the last item is not. I would welcome comments on how this information could best be reported to the user. Give it a go and let me know your thoughts.
The changes in RC1 have made Omega significantly slower than Memcheck. The actual amount varies massively depending upon the program but generally, it is now worse. Now that it looks like the functionality is correct, performance will be addressed. I will put some figures in here when I have optimised what I can so you will have a good idea whether to order a take-out or go for the sit down...
At work, we are migrating some software from one architecture to another. Moving software around can be fraught, even when properly planned. Having used Memcheck to get all of the memory leaks out of it a couple of releases ago, I longed for a tool that would show me where the leaks actually were but without having to change the source or mess around linking in other libraries.
Here it is.
Omega is NOT perfect (nearly. but not quite). I hope that it will get even better but it is usable NOW. It currently supports x86 and x86_64. I would welcome assistance to make this work on PPC32 and PPC64 but I have no hardware to test or build on so I would need patches rather than just helpful advice.
It is worth giving it a try – several of my colleagues at work have used Omega on x86_64 and were amazed at how much time and effort it saved them. I use it at work and whilst I am not amazed at how much time and effort it saves me (this was my aim from the start) I have to smile to myself when it just spits out the leak locations.
Beta 03 onwards has a wrapper around main so I can tell when the program has finished and hence should stop tracking. This might cause an issue with threads – I will hopefully be making this more robust before we get to 1.0 (which hopefully won't be too far away - sorry folks but I am on my own here so I work on this when I can).
Beta 04 introduces some function wrapping around memcpy, memmove and memset to reduce the chances of losing tracked pointers. It also has a fix for a false positive that I found and as a result of the fix, now has much more robust detection for functions returning values. Finally, it fixes a problem that shipped with the circular reference tracking in beta03.
Beta 04b fixes a typo in the wrapper around main().
Beta 05 aggregates the circular references together into common contexts, giving a repeat count and leak amount for that context. It also broke the debugger attach (you can try it but you probably wont like it). On the positive side, it gives much more accurate leak reports in some cases, having finally closed off some edge cases with functions that return values. A reported bug with realloc() on x86 (not x86-64) was also fixed. The next release is likely to be a release candidate unless you find me some juicy bugs to chomp on.
RC 01 removes the need to patch VEX in order to work. It also closes off some false positive cases (seeing a “Welcome back to the block” message while using –instant-reports should hopefully be very rare now). Whilst this patch is pretty well on the money, some of the changes have resulted in a performance hit and there remains at least one edge case that you might be able to trip (I'd like to know if you can trip it with a trivial example please). The rest of the release candidates will examine what can be sped back up without compromising the output. Please – go forth and find leaks! (and report bugs :D)
I am more than happy to receive your comments, criticisms, bug reports and especially patches (although I make no promises to accept them). Any success stories would also be nice to hear about. Please post onto the valgrind mailing lists so we can build a searchable index of issues and solutions to share.
I am Bryan "Brain Murders" Meredith and you will find me on the valgrind-users and valgrind-developers mailing lists.
Omega is Copyright (c) 2006 Bryan "Brain Murders" Meredith and is released under the GNU GPL(v2).