sewardj | cb2288b | 2007-12-02 02:08:17 +0000 | [diff] [blame^] | 1 | |
sewardj | 99a2ceb | 2007-11-09 12:30:36 +0000 | [diff] [blame] | 2 | Title |
| 3 | ===== |
sewardj | cb2288b | 2007-12-02 02:08:17 +0000 | [diff] [blame^] | 4 | |
sewardj | 99a2ceb | 2007-11-09 12:30:36 +0000 | [diff] [blame] | 5 | Omega - A Valgrind tool for instant memory leak detection. |
sewardj | cb2288b | 2007-12-02 02:08:17 +0000 | [diff] [blame^] | 6 | |
| 7 | Designed by Bryan "Brain Murders" Meredith with grateful thanks to the |
| 8 | Valgrind team for making their tool and techniques available under the |
| 9 | GPL and my employer Apertio (www.apertio.com) for allowing the use of |
| 10 | their time, equipment for 64bit testing and providing moral support. |
sewardj | 99a2ceb | 2007-11-09 12:30:36 +0000 | [diff] [blame] | 11 | |
| 12 | Synopsis |
| 13 | ======== |
sewardj | cb2288b | 2007-12-02 02:08:17 +0000 | [diff] [blame^] | 14 | |
| 15 | Whilst Valgrind's MemCheck tool can currently detect and report that a |
| 16 | memory leak has occurred, the debugging output only shows where the |
| 17 | memory that has leaked was allocated. There are no clues as to where |
| 18 | the last reference to the allocated block was lost. Omega uses a |
| 19 | modified version of MemCheck's "definedness" ('V' bit tracking) |
| 20 | technique in order to help track pointers to allocated memory, |
| 21 | outputting debugging information when the final (hence Omega) pointer |
| 22 | to an allocated block is over-written or lost through a call to free() |
| 23 | or the stack unwinding. |
sewardj | 99a2ceb | 2007-11-09 12:30:36 +0000 | [diff] [blame] | 24 | |
| 25 | How it Works |
| 26 | ============ |
sewardj | 99a2ceb | 2007-11-09 12:30:36 +0000 | [diff] [blame] | 27 | |
sewardj | cb2288b | 2007-12-02 02:08:17 +0000 | [diff] [blame^] | 28 | The main task in tracking leaks is when a checking whenever a value is |
| 29 | written into memory or a register. This can result in the creation of |
| 30 | a new reference to an allocated block, the destruction of a current |
| 31 | reference to an allocated block or both. If we determine that either |
| 32 | the register to be written or the memory location to be written |
| 33 | contains a pointer that we are tracking, we update our tracking system |
| 34 | and report if we are losing the last pointer to a block. |
| 35 | |
| 36 | Because checking every single write to memory causes a huge overhead, |
| 37 | we make a couple of assumptions about what constitutes a pointer in |
| 38 | order to reduce hash table lookups of the internal data. In order to |
| 39 | optimise checking for pointers during free() and stack unwinding, we |
| 40 | maintain a set of PBits (Pointer Bits) that allow us to quickly check |
| 41 | a range of addresses for pointers that will be lost. |
sewardj | 99a2ceb | 2007-11-09 12:30:36 +0000 | [diff] [blame] | 42 | |
| 43 | A Simple Example |
| 44 | ---------------- |
sewardj | 99a2ceb | 2007-11-09 12:30:36 +0000 | [diff] [blame] | 45 | |
sewardj | cb2288b | 2007-12-02 02:08:17 +0000 | [diff] [blame^] | 46 | The program under test calls malloc (or one of the other heap |
| 47 | allocation functions). We generate an internal record to track the |
| 48 | address and size of the new block. |
sewardj | 99a2ceb | 2007-11-09 12:30:36 +0000 | [diff] [blame] | 49 | |
sewardj | cb2288b | 2007-12-02 02:08:17 +0000 | [diff] [blame^] | 50 | At each time we write to memory or a register is loaded, we check to |
| 51 | see if we have a tracked pointer record for the location about to be |
| 52 | written. If so, we remove this record and decrement the reference |
| 53 | count for the block that it pointed to, generating an alarm if this |
| 54 | was the last reference. We check if the value that we are writing |
| 55 | matches the address of an allocated block. If we get a match, we add a |
| 56 | tracked pointer record for the written address and increment the |
| 57 | reference count. To speed things up, the internal records are stored |
| 58 | in hash tables. |
| 59 | |
| 60 | When we call free (or one of the other heap de-allocation functions), |
| 61 | we do cleanup processing on our internal record. There are two key |
| 62 | activities that must be performed at this point. |
sewardj | 99a2ceb | 2007-11-09 12:30:36 +0000 | [diff] [blame] | 63 | |
| 64 | 1) Clear and deallocate any hanging pointers. |
sewardj | cb2288b | 2007-12-02 02:08:17 +0000 | [diff] [blame^] | 65 | |
| 66 | 2) Recursively remove references to any pointers that are within the |
| 67 | memory area that we are about to free. |
sewardj | 99a2ceb | 2007-11-09 12:30:36 +0000 | [diff] [blame] | 68 | |
| 69 | As an option, during stage 1 we could report on the hanging pointers. |
| 70 | |
sewardj | cb2288b | 2007-12-02 02:08:17 +0000 | [diff] [blame^] | 71 | Note that stack unwinding also performs stage 2 to ensure that we |
| 72 | don't leak through automatic variables going out of scope. |
sewardj | 99a2ceb | 2007-11-09 12:30:36 +0000 | [diff] [blame] | 73 | |
| 74 | 'P' bit Propagation |
| 75 | ------------------- |
sewardj | cb2288b | 2007-12-02 02:08:17 +0000 | [diff] [blame^] | 76 | |
| 77 | Each time we see an address of a memory block being written into an |
| 78 | address or register, in addition to setting up the tracked pointer |
| 79 | record, we also set a PBit to show that there is a tracked record for |
| 80 | the address. By using PBit lookups and caching the PBit nodes between |
| 81 | lookups (along with a dedicated PBit node for registers) we can get a |
| 82 | significant performance gain. The time when PBits really come into |
| 83 | their own is when we need to clear all of the tracked pointer records |
| 84 | from a range of memory ie. invalidating the stack, calling |
| 85 | free(). Using the PBit mechanism, we can check upto 64K in one |
| 86 | go. This can be a huge gain as many structures do not hold nested |
| 87 | pointers to allocated memory. |
sewardj | 99a2ceb | 2007-11-09 12:30:36 +0000 | [diff] [blame] | 88 | |
| 89 | Stuff that I really want to add |
| 90 | =============================== |
sewardj | cb2288b | 2007-12-02 02:08:17 +0000 | [diff] [blame^] | 91 | |
| 92 | Client Calls - This would allow us to track client based memory pool |
| 93 | implementations, MALLOC_LIKE_BLOCK() etc. |
| 94 | |
| 95 | Summary Report - I want some feedback on what the output of the Omega |
| 96 | should be so watch this space. |
| 97 | |
| 98 | Suppression Support - I don't know how much this is needed but it |
| 99 | would probably be worthwhile. |
sewardj | 99a2ceb | 2007-11-09 12:30:36 +0000 | [diff] [blame] | 100 | |
| 101 | What We Can Detect |
| 102 | ================== |
sewardj | cb2288b | 2007-12-02 02:08:17 +0000 | [diff] [blame^] | 103 | |
sewardj | 99a2ceb | 2007-11-09 12:30:36 +0000 | [diff] [blame] | 104 | Using the above techniques, we can track the following leaks: |
| 105 | |
| 106 | Simple over-write of a tracked pointer. |
sewardj | 99a2ceb | 2007-11-09 12:30:36 +0000 | [diff] [blame] | 107 | |
sewardj | cb2288b | 2007-12-02 02:08:17 +0000 | [diff] [blame^] | 108 | lastP = blah; |
| 109 | |
| 110 | Tracked pointer being modified (we wont raise a leak report on this - |
| 111 | we will track the offset within the block - see "Shadowing"). |
| 112 | |
| 113 | lastP++; |
sewardj | 99a2ceb | 2007-11-09 12:30:36 +0000 | [diff] [blame] | 114 | |
| 115 | Automatic variable going out of scope. |
sewardj | cb2288b | 2007-12-02 02:08:17 +0000 | [diff] [blame^] | 116 | |
| 117 | { |
| 118 | void *lastP = malloc(64); |
| 119 | return; |
| 120 | } |
sewardj | 99a2ceb | 2007-11-09 12:30:36 +0000 | [diff] [blame] | 121 | |
| 122 | Tracked pointer within allocated block being returned to OS. |
sewardj | 99a2ceb | 2007-11-09 12:30:36 +0000 | [diff] [blame] | 123 | |
sewardj | cb2288b | 2007-12-02 02:08:17 +0000 | [diff] [blame^] | 124 | { |
| 125 | void *arrayP = malloc(10 * sizeof(void *)); |
| 126 | arrayP[1] = malloc(64); |
| 127 | free(arrayP); |
| 128 | } |
sewardj | 99a2ceb | 2007-11-09 12:30:36 +0000 | [diff] [blame] | 129 | |
| 130 | Shadowing |
| 131 | ========= |
sewardj | 99a2ceb | 2007-11-09 12:30:36 +0000 | [diff] [blame] | 132 | |
sewardj | cb2288b | 2007-12-02 02:08:17 +0000 | [diff] [blame^] | 133 | This helps to solve the problem of where a program does its own memory |
| 134 | management of the kind: |
sewardj | 99a2ceb | 2007-11-09 12:30:36 +0000 | [diff] [blame] | 135 | |
sewardj | cb2288b | 2007-12-02 02:08:17 +0000 | [diff] [blame^] | 136 | 1 secret *foo = malloc(sizeof(bar) + sizeof(secret) + alignment_correction); |
| 137 | 2 foo->secret_stuff = magic_key; |
| 138 | 3 etc. |
| 139 | 4 foo++; |
| 140 | 5 return (bar*)foo; |
sewardj | 99a2ceb | 2007-11-09 12:30:36 +0000 | [diff] [blame] | 141 | |
sewardj | cb2288b | 2007-12-02 02:08:17 +0000 | [diff] [blame^] | 142 | If the pointer to foo is shadowed at some internal offset to the block |
| 143 | start, we create a shadow record and link it to the main block so that |
| 144 | we can track references to either. Without this we do a leak alert at |
| 145 | line 4 instead which is undesireable. There can only be one shadow to |
| 146 | a block unless we really need more and someone wants to code it and |
| 147 | send me a patch. |
sewardj | 99a2ceb | 2007-11-09 12:30:36 +0000 | [diff] [blame] | 148 | |
| 149 | What We Don't Detect |
| 150 | -------------------- |
sewardj | 99a2ceb | 2007-11-09 12:30:36 +0000 | [diff] [blame] | 151 | |
sewardj | cb2288b | 2007-12-02 02:08:17 +0000 | [diff] [blame^] | 152 | Actually, we do pretty well here but there are a couple of things you |
| 153 | need to know about. |
sewardj | 99a2ceb | 2007-11-09 12:30:36 +0000 | [diff] [blame] | 154 | |
sewardj | cb2288b | 2007-12-02 02:08:17 +0000 | [diff] [blame^] | 155 | 1) We track pointers in registers. Therefore, whilst the final code |
| 156 | reference (on the stack say) may be lost, the pointer can (and |
| 157 | does) live on within a register until the register is |
| 158 | overwritten. The best way to help prevent this from making late |
| 159 | reports is to compile with -O0. On x86, this makes quite a |
| 160 | difference, especially to non-trivial functions. |
| 161 | |
| 162 | 2) Some code is a little naughty when it comes to memory blocks that |
| 163 | have been returned to the OS. Memcheck reports these read accesses |
| 164 | to free()ed blocks as illegal reads. Omega also reports them as it |
| 165 | gets annoyed when it has just reported a block as leaked only for a |
| 166 | pointer to appear from "no-where". (Calling free() on a block does |
| 167 | not erase the contents of the block so even though Omega removes |
| 168 | all tracked pointer records for addresses within the block, the |
| 169 | pointers themselves still exist. Once one of these pointers is |
| 170 | read, Omega tracks it being loaded into a register at which point, |
| 171 | it complains and resumes tracking the "leaked" block.) |
sewardj | 99a2ceb | 2007-11-09 12:30:36 +0000 | [diff] [blame] | 172 | |
| 173 | What Next? |
| 174 | ========== |
sewardj | cb2288b | 2007-12-02 02:08:17 +0000 | [diff] [blame^] | 175 | |
sewardj | 99a2ceb | 2007-11-09 12:30:36 +0000 | [diff] [blame] | 176 | Feedback!!! |
| 177 | |
sewardj | cb2288b | 2007-12-02 02:08:17 +0000 | [diff] [blame^] | 178 | The core of the tool is done and working. Now I need feedback from |
| 179 | anyone out there that is interested in using it so I can make the |
| 180 | output as usefull as it can be. |
sewardj | 99a2ceb | 2007-11-09 12:30:36 +0000 | [diff] [blame] | 181 | |
sewardj | cb2288b | 2007-12-02 02:08:17 +0000 | [diff] [blame^] | 182 | If anyone is interested in helping me out on this, send your |
| 183 | patches. I hope to get this accepted into Valgrind so it can get some |
| 184 | serious attention but I dont know if that will happen so I will try to |
| 185 | maintain a patch against svn or a tar of the whole thing if that gets |
| 186 | too troublesome. |
sewardj | 99a2ceb | 2007-11-09 12:30:36 +0000 | [diff] [blame] | 187 | |
sewardj | cb2288b | 2007-12-02 02:08:17 +0000 | [diff] [blame^] | 188 | Bryan "Brain Murders" Meredith. The current maintainer of Omega is |
| 189 | Rich Coe <richard.coe@med.ge.com>. Please send all email regarding |
| 190 | Omega to Rich. |