2 /*--------------------------------------------------------------------*/
3 /*--- The leak checker. mc_leakcheck.c ---*/
4 /*--------------------------------------------------------------------*/
7 This file is part of MemCheck, a heavyweight Valgrind tool for
8 detecting memory errors.
10 Copyright (C) 2000-2010 Julian Seward
13 This program is free software; you can redistribute it and/or
14 modify it under the terms of the GNU General Public License as
15 published by the Free Software Foundation; either version 2 of the
16 License, or (at your option) any later version.
18 This program is distributed in the hope that it will be useful, but
19 WITHOUT ANY WARRANTY; without even the implied warranty of
20 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
21 General Public License for more details.
23 You should have received a copy of the GNU General Public License
24 along with this program; if not, write to the Free Software
25 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
28 The GNU General Public License is contained in the file COPYING.
31 #include "pub_tool_basics.h"
32 #include "pub_tool_vki.h"
33 #include "pub_tool_aspacehl.h"
34 #include "pub_tool_aspacemgr.h"
35 #include "pub_tool_execontext.h"
36 #include "pub_tool_hashtable.h"
37 #include "pub_tool_libcbase.h"
38 #include "pub_tool_libcassert.h"
39 #include "pub_tool_libcprint.h"
40 #include "pub_tool_libcsignal.h"
41 #include "pub_tool_machine.h"
42 #include "pub_tool_mallocfree.h"
43 #include "pub_tool_options.h"
44 #include "pub_tool_oset.h"
45 #include "pub_tool_signals.h"
46 #include "pub_tool_libcsetjmp.h" // setjmp facilities
47 #include "pub_tool_tooliface.h" // Needed for mc_include.h
49 #include "mc_include.h"
51 /*------------------------------------------------------------*/
52 /*--- An overview of leak checking. ---*/
53 /*------------------------------------------------------------*/
55 // Leak-checking is a directed-graph traversal problem. The graph has
56 // two kinds of nodes:
58 // - GP registers of all threads;
59 // - valid, aligned, pointer-sized data words in valid client memory,
60 // including stacks, but excluding words within client heap-allocated
61 // blocks (they are excluded so that later on we can differentiate
62 // between heap blocks that are indirectly leaked vs. directly leaked).
63 // - heap-allocated blocks. A block is a mempool chunk or a malloc chunk
64 // that doesn't contain a mempool chunk. Nb: the terms "blocks" and
65 // "chunks" are used interchangeably below.
67 // There are two kinds of edges:
68 // - start-pointers, i.e. pointers to the start of a block;
69 // - interior-pointers, i.e. pointers to the interior of a block.
71 // We use "pointers" rather than "edges" below.
73 // Root set nodes only point to blocks. Blocks only point to blocks;
74 // a block can point to itself.
76 // The aim is to traverse the graph and determine the status of each block.
78 // There are 9 distinct cases. See memcheck/docs/mc-manual.xml for details.
79 // Presenting all nine categories to the user is probably too much.
80 // Currently we do this:
81 // - definitely lost: case 3
82 // - indirectly lost: case 4, 9
83 // - possibly lost: cases 5..8
84 // - still reachable: cases 1, 2
86 // It's far from clear that this is the best possible categorisation; it's
87 // accreted over time without any central guiding principle.
89 /*------------------------------------------------------------*/
90 /*--- XXX: Thoughts for improvement. ---*/
91 /*------------------------------------------------------------*/
93 // From the user's point of view:
94 // - If they aren't using interior-pointers, they just have to fix the
95 // directly lost blocks, and the indirectly lost ones will be fixed as
96 // part of that. Any possibly lost blocks will just be due to random
97 // pointer garbage and can be ignored.
99 // - If they are using interior-pointers, the fact that they currently are not
100 // being told which ones might be directly lost vs. indirectly lost makes
101 // it hard to know where to begin.
103 // All this makes me wonder if new option is warranted:
104 // --follow-interior-pointers. By default it would be off, the leak checker
105 // wouldn't follow interior-pointers and there would only be 3 categories:
108 // If turned on, then it would show 7 categories (R, DL, IL, DR/DL, IR/IL,
109 // IR/IL/DL, IL/DL). That output is harder to understand but it's your own
110 // damn fault for using interior-pointers...
114 // Also, why are two blank lines printed between each loss record?
119 // Also, --show-reachable is a bad name because it also turns on the showing
120 // of indirectly leaked blocks(!) It would be better named --show-all or
121 // --show-all-heap-blocks, because that's the end result.
125 // Also, the VALGRIND_LEAK_CHECK and VALGRIND_QUICK_LEAK_CHECK aren't great
126 // names. VALGRIND_FULL_LEAK_CHECK and VALGRIND_SUMMARY_LEAK_CHECK would be
131 // Also, VALGRIND_COUNT_LEAKS and VALGRIND_COUNT_LEAK_BLOCKS aren't great as
132 // they combine direct leaks and indirect leaks into one. New, more precise
133 // ones (they'll need new names) would be good. If more categories are
134 // used, as per the --follow-interior-pointers option, they should be
135 // updated accordingly. And they should use a struct to return the values.
139 // Also, for this case:
141 // (4) p4 BBB ---> AAA
143 // BBB is definitely directly lost. AAA is definitely indirectly lost.
144 // Here's the relevant loss records printed for a full check (each block is
147 // ==20397== 16 bytes in 1 blocks are indirectly lost in loss record 9 of 15
148 // ==20397== at 0x4C2694E: malloc (vg_replace_malloc.c:177)
149 // ==20397== by 0x400521: mk (leak-cases.c:49)
150 // ==20397== by 0x400578: main (leak-cases.c:72)
152 // ==20397== 32 (16 direct, 16 indirect) bytes in 1 blocks are definitely
153 // lost in loss record 14 of 15
154 // ==20397== at 0x4C2694E: malloc (vg_replace_malloc.c:177)
155 // ==20397== by 0x400521: mk (leak-cases.c:49)
156 // ==20397== by 0x400580: main (leak-cases.c:72)
158 // The first one is fine -- it describes AAA.
160 // The second one is for BBB. It's correct in that 16 bytes in 1 block are
161 // directly lost. It's also correct that 16 are indirectly lost as a result,
162 // but it means that AAA is being counted twice in the loss records. (It's
163 // not, thankfully, counted twice in the summary counts). Argh.
165 // This would be less confusing for the second one:
167 // ==20397== 16 bytes in 1 blocks are definitely lost in loss record 14
168 // of 15 (and 16 bytes in 1 block are indirectly lost as a result; they
169 // are mentioned elsewhere (if --show-reachable=yes is given!))
170 // ==20397== at 0x4C2694E: malloc (vg_replace_malloc.c:177)
171 // ==20397== by 0x400521: mk (leak-cases.c:49)
172 // ==20397== by 0x400580: main (leak-cases.c:72)
174 // But ideally we'd present the loss record for the directly lost block and
175 // then the resultant indirectly lost blocks and make it clear the
176 // dependence. Double argh.
178 /*------------------------------------------------------------*/
179 /*--- The actual algorithm. ---*/
180 /*------------------------------------------------------------*/
182 // - Find all the blocks (a.k.a. chunks) to check. Mempool chunks require
183 // some special treatment because they can be within malloc'd blocks.
184 // - Scan every word in the root set (GP registers and valid
185 // non-heap memory words).
186 // - First, we skip if it doesn't point to valid memory.
187 // - Then, we see if it points to the start or interior of a block. If
188 // so, we push the block onto the mark stack and mark it as having been
190 // - Then, we process the mark stack, repeating the scanning for each block;
191 // this can push more blocks onto the mark stack. We repeat until the
192 // mark stack is empty. Each block is marked as definitely or possibly
193 // reachable, depending on whether interior-pointers were required to
195 // - At this point we know for every block if it's reachable or not.
196 // - We then push each unreached block onto the mark stack, using the block
197 // number as the "clique" number.
198 // - We process the mark stack again, this time grouping blocks into cliques
199 // in order to facilitate the directly/indirectly lost categorisation.
200 // - We group blocks by their ExeContexts and categorisation, and print them
201 // if --leak-check=full. We also print summary numbers.
203 // A note on "cliques":
204 // - A directly lost block is one with no pointers to it. An indirectly
205 // lost block is one that is pointed to by a directly or indirectly lost
207 // - Each directly lost block has zero or more indirectly lost blocks
208 // hanging off it. All these blocks together form a "clique". The
209 // directly lost block is called the "clique leader". The clique number
210 // is the number (in lc_chunks[]) of the clique leader.
211 // - Actually, a directly lost block may be pointed to if it's part of a
212 // cycle. In that case, there may be more than one choice for the clique
213 // leader, and the choice is arbitrary. Eg. if you have A-->B and B-->A
214 // either A or B could be the clique leader.
215 // - Cliques cannot overlap, and will be truncated to avoid this. Eg. if we
216 // have A-->C and B-->C, the two cliques will be {A,C} and {B}, or {A} and
217 // {B,C} (again the choice is arbitrary). This is because we don't want
218 // to count a block as indirectly lost more than once.
220 // A note on 'is_prior_definite':
221 // - This is a boolean used in various places that indicates if the chain
222 // up to the prior node (prior to the one being considered) is definite.
223 // - In the clique == -1 case:
224 // - if True it means that the prior node is a root-set node, or that the
225 // prior node is a block which is reachable from the root-set via
227 // - if False it means that the prior node is a block that is only
228 // reachable from the root-set via a path including at least one
230 // - In the clique != -1 case, currently it's always True because we treat
231 // start-pointers and interior-pointers the same for direct/indirect leak
232 // checking. If we added a PossibleIndirectLeak state then this would
236 // Define to debug the memory-leak-detector.
237 #define VG_DEBUG_LEAKCHECK 0
238 #define VG_DEBUG_CLIQUE 0
241 /*------------------------------------------------------------*/
242 /*--- Getting the initial chunks, and searching them. ---*/
243 /*------------------------------------------------------------*/
245 // Compare the MC_Chunks by 'data' (i.e. the address of the block).
246 static Int compare_MC_Chunks(void* n1, void* n2)
248 MC_Chunk* mc1 = *(MC_Chunk**)n1;
249 MC_Chunk* mc2 = *(MC_Chunk**)n2;
250 if (mc1->data < mc2->data) return -1;
251 if (mc1->data > mc2->data) return 1;
255 #if VG_DEBUG_LEAKCHECK
256 // Used to sanity-check the fast binary-search mechanism.
258 Int find_chunk_for_OLD ( Addr ptr,
265 PROF_EVENT(70, "find_chunk_for_OLD");
266 for (i = 0; i < n_chunks; i++) {
267 PROF_EVENT(71, "find_chunk_for_OLD(loop)");
268 a_lo = chunks[i]->data;
269 a_hi = ((Addr)chunks[i]->data) + chunks[i]->szB;
270 if (a_lo <= ptr && ptr < a_hi)
277 // Find the i such that ptr points at or inside the block described by
278 // chunks[i]. Return -1 if none found. This assumes that chunks[]
279 // has been sorted on the 'data' field.
281 Int find_chunk_for ( Addr ptr,
285 Addr a_mid_lo, a_mid_hi;
286 Int lo, mid, hi, retVal;
287 // VG_(printf)("find chunk for %p = ", ptr);
292 // Invariant: current unsearched space is from lo to hi, inclusive.
293 if (lo > hi) break; // not found
296 a_mid_lo = chunks[mid]->data;
297 a_mid_hi = chunks[mid]->data + chunks[mid]->szB;
298 // Extent of block 'mid' is [a_mid_lo .. a_mid_hi).
299 // Special-case zero-sized blocks - treat them as if they had
300 // size 1. Not doing so causes them to not cover any address
301 // range at all and so will never be identified as the target of
302 // any pointer, which causes them to be incorrectly reported as
303 // definitely leaked.
304 if (chunks[mid]->szB == 0)
307 if (ptr < a_mid_lo) {
311 if (ptr >= a_mid_hi) {
315 tl_assert(ptr >= a_mid_lo && ptr < a_mid_hi);
320 # if VG_DEBUG_LEAKCHECK
321 tl_assert(retVal == find_chunk_for_OLD ( ptr, chunks, n_chunks ));
323 // VG_(printf)("%d\n", retVal);
329 find_active_chunks(UInt* pn_chunks)
331 // Our goal is to construct a set of chunks that includes every
332 // mempool chunk, and every malloc region that *doesn't* contain a
335 MC_Chunk **mallocs, **chunks, *mc;
336 UInt n_mallocs, n_chunks, m, s;
337 Bool *malloc_chunk_holds_a_pool_chunk;
339 // First we collect all the malloc chunks into an array and sort it.
340 // We do this because we want to query the chunks by interior
341 // pointers, requiring binary search.
342 mallocs = (MC_Chunk**) VG_(HT_to_array)( MC_(malloc_list), &n_mallocs );
343 if (n_mallocs == 0) {
344 tl_assert(mallocs == NULL);
348 VG_(ssort)(mallocs, n_mallocs, sizeof(VgHashNode*), compare_MC_Chunks);
350 // Then we build an array containing a Bool for each malloc chunk,
351 // indicating whether it contains any mempools.
352 malloc_chunk_holds_a_pool_chunk = VG_(calloc)( "mc.fas.1",
353 n_mallocs, sizeof(Bool) );
354 n_chunks = n_mallocs;
356 // Then we loop over the mempool tables. For each chunk in each
357 // pool, we set the entry in the Bool array corresponding to the
358 // malloc chunk containing the mempool chunk.
359 VG_(HT_ResetIter)(MC_(mempool_list));
360 while ( (mp = VG_(HT_Next)(MC_(mempool_list))) ) {
361 VG_(HT_ResetIter)(mp->chunks);
362 while ( (mc = VG_(HT_Next)(mp->chunks)) ) {
364 // We'll need to record this chunk.
367 // Possibly invalidate the malloc holding the beginning of this chunk.
368 m = find_chunk_for(mc->data, mallocs, n_mallocs);
369 if (m != -1 && malloc_chunk_holds_a_pool_chunk[m] == False) {
370 tl_assert(n_chunks > 0);
372 malloc_chunk_holds_a_pool_chunk[m] = True;
375 // Possibly invalidate the malloc holding the end of this chunk.
377 m = find_chunk_for(mc->data + (mc->szB - 1), mallocs, n_mallocs);
378 if (m != -1 && malloc_chunk_holds_a_pool_chunk[m] == False) {
379 tl_assert(n_chunks > 0);
381 malloc_chunk_holds_a_pool_chunk[m] = True;
386 tl_assert(n_chunks > 0);
388 // Create final chunk array.
389 chunks = VG_(malloc)("mc.fas.2", sizeof(VgHashNode*) * (n_chunks));
392 // Copy the mempool chunks and the non-marked malloc chunks into a
393 // combined array of chunks.
394 VG_(HT_ResetIter)(MC_(mempool_list));
395 while ( (mp = VG_(HT_Next)(MC_(mempool_list))) ) {
396 VG_(HT_ResetIter)(mp->chunks);
397 while ( (mc = VG_(HT_Next)(mp->chunks)) ) {
398 tl_assert(s < n_chunks);
402 for (m = 0; m < n_mallocs; ++m) {
403 if (!malloc_chunk_holds_a_pool_chunk[m]) {
404 tl_assert(s < n_chunks);
405 chunks[s++] = mallocs[m];
408 tl_assert(s == n_chunks);
412 VG_(free)(malloc_chunk_holds_a_pool_chunk);
414 *pn_chunks = n_chunks;
419 /*------------------------------------------------------------*/
420 /*--- The leak detector proper. ---*/
421 /*------------------------------------------------------------*/
423 // Holds extra info about each block during leak checking.
426 UInt state:2; // Reachedness.
427 UInt pending:1; // Scan pending.
428 SizeT indirect_szB : (sizeof(SizeT)*8)-3; // If Unreached, how many bytes
429 // are unreachable from here.
433 // An array holding pointers to every chunk we're checking. Sorted by address.
434 static MC_Chunk** lc_chunks;
435 // How many chunks we're dealing with.
436 static Int lc_n_chunks;
438 // This has the same number of entries as lc_chunks, and each entry
439 // in lc_chunks corresponds with the entry here (ie. lc_chunks[i] and
440 // lc_extras[i] describe the same block).
441 static LC_Extra* lc_extras;
443 // Records chunks that are currently being processed. Each element in the
444 // stack is an index into lc_chunks and lc_extras. Its size is
445 // 'lc_n_chunks' because in the worst case that's how many chunks could be
446 // pushed onto it (actually I think the maximum is lc_n_chunks-1 but let's
448 static Int* lc_markstack;
449 // The index of the top element of the stack; -1 if the stack is empty, 0 if
450 // the stack has one element, 1 if it has two, etc.
451 static Int lc_markstack_top;
453 // Keeps track of how many bytes of memory we've scanned, for printing.
454 // (Nb: We don't keep track of how many register bytes we've scanned.)
455 static SizeT lc_scanned_szB;
458 SizeT MC_(bytes_leaked) = 0;
459 SizeT MC_(bytes_indirect) = 0;
460 SizeT MC_(bytes_dubious) = 0;
461 SizeT MC_(bytes_reachable) = 0;
462 SizeT MC_(bytes_suppressed) = 0;
464 SizeT MC_(blocks_leaked) = 0;
465 SizeT MC_(blocks_indirect) = 0;
466 SizeT MC_(blocks_dubious) = 0;
467 SizeT MC_(blocks_reachable) = 0;
468 SizeT MC_(blocks_suppressed) = 0;
471 // Determines if a pointer is to a chunk. Returns the chunk number et al
472 // via call-by-reference.
474 lc_is_a_chunk_ptr(Addr ptr, Int* pch_no, MC_Chunk** pch, LC_Extra** pex)
481 if (!VG_(am_is_valid_for_client)(ptr, 1, VKI_PROT_READ)) {
484 ch_no = find_chunk_for(ptr, lc_chunks, lc_n_chunks);
485 tl_assert(ch_no >= -1 && ch_no < lc_n_chunks);
490 // Ok, we've found a pointer to a chunk. Get the MC_Chunk and its
492 ch = lc_chunks[ch_no];
493 ex = &(lc_extras[ch_no]);
495 tl_assert(ptr >= ch->data);
496 tl_assert(ptr < ch->data + ch->szB + (ch->szB==0 ? 1 : 0));
498 if (VG_DEBUG_LEAKCHECK)
499 VG_(printf)("ptr=%#lx -> block %d\n", ptr, ch_no);
510 // Push a chunk (well, just its index) onto the mark stack.
511 static void lc_push(Int ch_no, MC_Chunk* ch)
513 if (!lc_extras[ch_no].pending) {
515 VG_(printf)("pushing %#lx-%#lx\n", ch->data, ch->data + ch->szB);
518 tl_assert(lc_markstack_top < lc_n_chunks);
519 lc_markstack[lc_markstack_top] = ch_no;
520 tl_assert(!lc_extras[ch_no].pending);
521 lc_extras[ch_no].pending = True;
525 // Return the index of the chunk on the top of the mark stack, or -1 if
527 static Bool lc_pop(Int* ret)
529 if (-1 == lc_markstack_top) {
532 tl_assert(0 <= lc_markstack_top && lc_markstack_top < lc_n_chunks);
533 *ret = lc_markstack[lc_markstack_top];
535 tl_assert(lc_extras[*ret].pending);
536 lc_extras[*ret].pending = False;
542 // If 'ptr' is pointing to a heap-allocated block which hasn't been seen
543 // before, push it onto the mark stack.
545 lc_push_without_clique_if_a_chunk_ptr(Addr ptr, Bool is_prior_definite)
551 if ( ! lc_is_a_chunk_ptr(ptr, &ch_no, &ch, &ex) )
554 // Possibly upgrade the state, ie. one of:
555 // - Unreached --> Possible
556 // - Unreached --> Reachable
557 // - Possible --> Reachable
558 if (ptr == ch->data && is_prior_definite && ex->state != Reachable) {
559 // 'ptr' points to the start of the block, and the prior node is
560 // definite, which means that this block is definitely reachable.
561 ex->state = Reachable;
563 // State has changed to Reachable so (re)scan the block to make
564 // sure any blocks it points to are correctly marked.
567 } else if (ex->state == Unreached) {
568 // Either 'ptr' is a interior-pointer, or the prior node isn't definite,
569 // which means that we can only mark this block as possibly reachable.
570 ex->state = Possible;
572 // State has changed to Possible so (re)scan the block to make
573 // sure any blocks it points to are correctly marked.
579 lc_push_if_a_chunk_ptr_register(Addr ptr)
581 lc_push_without_clique_if_a_chunk_ptr(ptr, /*is_prior_definite*/True);
584 // If ptr is pointing to a heap-allocated block which hasn't been seen
585 // before, push it onto the mark stack. Clique is the index of the
588 lc_push_with_clique_if_a_chunk_ptr(Addr ptr, Int clique)
594 tl_assert(0 <= clique && clique < lc_n_chunks);
596 if ( ! lc_is_a_chunk_ptr(ptr, &ch_no, &ch, &ex) )
599 // If it's not Unreached, it's already been handled so ignore it.
600 // If ch_no==clique, it's the clique leader, which means this is a cyclic
601 // structure; again ignore it because it's already been handled.
602 if (ex->state == Unreached && ch_no != clique) {
603 // Note that, unlike reachable blocks, we currently don't distinguish
604 // between start-pointers and interior-pointers here. We probably
606 ex->state = IndirectLeak;
609 // Add the block to the clique, and add its size to the
610 // clique-leader's indirect size. Also, if the new block was
611 // itself a clique leader, it isn't any more, so add its
612 // indirect_szB to the new clique leader.
613 if (VG_DEBUG_CLIQUE) {
614 if (ex->indirect_szB > 0)
615 VG_(printf)(" clique %d joining clique %d adding %lu+%lu\n",
616 ch_no, clique, (SizeT)ch->szB, (SizeT)ex->indirect_szB);
618 VG_(printf)(" block %d joining clique %d adding %lu\n",
619 ch_no, clique, (SizeT)ch->szB);
622 lc_extras[clique].indirect_szB += ch->szB;
623 lc_extras[clique].indirect_szB += ex->indirect_szB;
624 ex->indirect_szB = 0; // Shouldn't matter.
629 lc_push_if_a_chunk_ptr(Addr ptr, Int clique, Bool is_prior_definite)
632 lc_push_without_clique_if_a_chunk_ptr(ptr, is_prior_definite);
634 lc_push_with_clique_if_a_chunk_ptr(ptr, clique);
638 static VG_MINIMAL_JMP_BUF(memscan_jmpbuf);
641 void scan_all_valid_memory_catcher ( Int sigNo, Addr addr )
644 VG_(printf)("OUCH! sig=%d addr=%#lx\n", sigNo, addr);
645 if (sigNo == VKI_SIGSEGV || sigNo == VKI_SIGBUS)
646 VG_MINIMAL_LONGJMP(memscan_jmpbuf);
649 // Scan a block of memory between [start, start+len). This range may
650 // be bogus, inaccessable, or otherwise strange; we deal with it. For each
651 // valid aligned word we assume it's a pointer to a chunk a push the chunk
652 // onto the mark stack if so.
654 lc_scan_memory(Addr start, SizeT len, Bool is_prior_definite, Int clique)
656 Addr ptr = VG_ROUNDUP(start, sizeof(Addr));
657 Addr end = VG_ROUNDDN(start+len, sizeof(Addr));
658 vki_sigset_t sigmask;
660 if (VG_DEBUG_LEAKCHECK)
661 VG_(printf)("scan %#lx-%#lx (%lu)\n", start, end, len);
663 VG_(sigprocmask)(VKI_SIG_SETMASK, NULL, &sigmask);
664 VG_(set_fault_catcher)(scan_all_valid_memory_catcher);
666 // We might be in the middle of a page. Do a cheap check to see if
667 // it's valid; if not, skip onto the next page.
668 if (!VG_(am_is_valid_for_client)(ptr, sizeof(Addr), VKI_PROT_READ))
669 ptr = VG_PGROUNDUP(ptr+1); // First page is bad - skip it.
674 // Skip invalid chunks.
675 if ( ! MC_(is_within_valid_secondary)(ptr) ) {
676 ptr = VG_ROUNDUP(ptr+1, SM_SIZE);
680 // Look to see if this page seems reasonable.
681 if ((ptr % VKI_PAGE_SIZE) == 0) {
682 if (!VG_(am_is_valid_for_client)(ptr, sizeof(Addr), VKI_PROT_READ)) {
683 ptr += VKI_PAGE_SIZE; // Bad page - skip it.
688 if (VG_MINIMAL_SETJMP(memscan_jmpbuf) == 0) {
689 if ( MC_(is_valid_aligned_word)(ptr) ) {
690 lc_scanned_szB += sizeof(Addr);
692 // If we get here, the scanned word is in valid memory. Now
693 // let's see if its contents point to a chunk.
694 lc_push_if_a_chunk_ptr(addr, clique, is_prior_definite);
695 } else if (0 && VG_DEBUG_LEAKCHECK) {
696 VG_(printf)("%#lx not valid\n", ptr);
700 // We need to restore the signal mask, because we were
701 // longjmped out of a signal handler.
702 VG_(sigprocmask)(VKI_SIG_SETMASK, &sigmask, NULL);
704 ptr = VG_PGROUNDUP(ptr+1); // Bad page - skip it.
708 VG_(sigprocmask)(VKI_SIG_SETMASK, &sigmask, NULL);
709 VG_(set_fault_catcher)(NULL);
713 // Process the mark stack until empty.
714 static void lc_process_markstack(Int clique)
716 Int top = -1; // shut gcc up
717 Bool is_prior_definite;
719 while (lc_pop(&top)) {
720 tl_assert(top >= 0 && top < lc_n_chunks);
722 // See comment about 'is_prior_definite' at the top to understand this.
723 is_prior_definite = ( Possible != lc_extras[top].state );
725 lc_scan_memory(lc_chunks[top]->data, lc_chunks[top]->szB,
726 is_prior_definite, clique);
730 static Word cmp_LossRecordKey_LossRecord(const void* key, const void* elem)
732 LossRecordKey* a = (LossRecordKey*)key;
733 LossRecordKey* b = &(((LossRecord*)elem)->key);
735 // Compare on states first because that's fast.
736 if (a->state < b->state) return -1;
737 if (a->state > b->state) return 1;
738 // Ok, the states are equal. Now compare the locations, which is slower.
739 if (VG_(eq_ExeContext)(
740 MC_(clo_leak_resolution), a->allocated_at, b->allocated_at))
742 // Different locations. Ordering is arbitrary, just use the ec pointer.
743 if (a->allocated_at < b->allocated_at) return -1;
744 if (a->allocated_at > b->allocated_at) return 1;
745 VG_(tool_panic)("bad LossRecord comparison");
748 static Int cmp_LossRecords(void* va, void* vb)
750 LossRecord* lr_a = *(LossRecord**)va;
751 LossRecord* lr_b = *(LossRecord**)vb;
752 SizeT total_szB_a = lr_a->szB + lr_a->indirect_szB;
753 SizeT total_szB_b = lr_b->szB + lr_b->indirect_szB;
755 // First compare by sizes.
756 if (total_szB_a < total_szB_b) return -1;
757 if (total_szB_a > total_szB_b) return 1;
758 // If size are equal, compare by states.
759 if (lr_a->key.state < lr_b->key.state) return -1;
760 if (lr_a->key.state > lr_b->key.state) return 1;
761 // If they're still equal here, it doesn't matter that much, but we keep
762 // comparing other things so that regtests are as deterministic as
763 // possible. So: compare num_blocks.
764 if (lr_a->num_blocks < lr_b->num_blocks) return -1;
765 if (lr_a->num_blocks > lr_b->num_blocks) return 1;
766 // Finally, compare ExeContext addresses... older ones are likely to have
768 if (lr_a->key.allocated_at < lr_b->key.allocated_at) return -1;
769 if (lr_a->key.allocated_at > lr_b->key.allocated_at) return 1;
773 static void print_results(ThreadId tid, Bool is_full_check)
775 Int i, n_lossrecords;
777 LossRecord** lr_array;
781 // Create the lr_table, which holds the loss records.
783 VG_(OSetGen_Create)(offsetof(LossRecord, key),
784 cmp_LossRecordKey_LossRecord,
785 VG_(malloc), "mc.pr.1",
788 // Convert the chunks into loss records, merging them where appropriate.
789 for (i = 0; i < lc_n_chunks; i++) {
790 MC_Chunk* ch = lc_chunks[i];
791 LC_Extra* ex = &(lc_extras)[i];
794 lrkey.state = ex->state;
795 lrkey.allocated_at = ch->where;
797 old_lr = VG_(OSetGen_Lookup)(lr_table, &lrkey);
799 // We found an existing loss record matching this chunk. Update the
800 // loss record's details in-situ. This is safe because we don't
801 // change the elements used as the OSet key.
802 old_lr->szB += ch->szB;
803 old_lr->indirect_szB += ex->indirect_szB;
804 old_lr->num_blocks++;
806 // No existing loss record matches this chunk. Create a new loss
807 // record, initialise it from the chunk, and insert it into lr_table.
808 lr = VG_(OSetGen_AllocNode)(lr_table, sizeof(LossRecord));
811 lr->indirect_szB = ex->indirect_szB;
813 VG_(OSetGen_Insert)(lr_table, lr);
816 n_lossrecords = VG_(OSetGen_Size)(lr_table);
818 // Create an array of pointers to the loss records.
819 lr_array = VG_(malloc)("mc.pr.2", n_lossrecords * sizeof(LossRecord*));
821 VG_(OSetGen_ResetIter)(lr_table);
822 while ( (lr = VG_(OSetGen_Next)(lr_table)) ) {
825 tl_assert(i == n_lossrecords);
827 // Sort the array by loss record sizes.
828 VG_(ssort)(lr_array, n_lossrecords, sizeof(LossRecord*),
832 MC_(blocks_leaked) = MC_(bytes_leaked) = 0;
833 MC_(blocks_indirect) = MC_(bytes_indirect) = 0;
834 MC_(blocks_dubious) = MC_(bytes_dubious) = 0;
835 MC_(blocks_reachable) = MC_(bytes_reachable) = 0;
836 MC_(blocks_suppressed) = MC_(bytes_suppressed) = 0;
838 // Print the loss records (in size order) and collect summary stats.
839 for (i = 0; i < n_lossrecords; i++) {
840 Bool count_as_error, print_record;
841 // Rules for printing:
842 // - We don't show suppressed loss records ever (and that's controlled
843 // within the error manager).
844 // - We show non-suppressed loss records that are not "reachable" if
846 // - We show all non-suppressed loss records if --leak-check=yes and
847 // --show-reachable=yes.
849 // Nb: here "reachable" means Reachable *or* IndirectLeak; note that
850 // this is different to "still reachable" used elsewhere because it
851 // includes indirectly lost blocks!
854 print_record = is_full_check &&
855 ( MC_(clo_show_reachable) ||
856 Unreached == lr->key.state ||
857 ( MC_(clo_show_possibly_lost) &&
858 Possible == lr->key.state ) );
859 // We don't count a leaks as errors with --leak-check=summary.
860 // Otherwise you can get high error counts with few or no error
861 // messages, which can be confusing. Also, you could argue that
862 // indirect leaks should be counted as errors, but it seems better to
863 // make the counting criteria similar to the printing criteria. So we
865 count_as_error = is_full_check &&
866 ( Unreached == lr->key.state ||
867 Possible == lr->key.state );
869 MC_(record_leak_error) ( tid, i+1, n_lossrecords, lr, print_record,
873 MC_(blocks_suppressed) += lr->num_blocks;
874 MC_(bytes_suppressed) += lr->szB;
876 } else if (Unreached == lr->key.state) {
877 MC_(blocks_leaked) += lr->num_blocks;
878 MC_(bytes_leaked) += lr->szB;
880 } else if (IndirectLeak == lr->key.state) {
881 MC_(blocks_indirect) += lr->num_blocks;
882 MC_(bytes_indirect) += lr->szB;
884 } else if (Possible == lr->key.state) {
885 MC_(blocks_dubious) += lr->num_blocks;
886 MC_(bytes_dubious) += lr->szB;
888 } else if (Reachable == lr->key.state) {
889 MC_(blocks_reachable) += lr->num_blocks;
890 MC_(bytes_reachable) += lr->szB;
893 VG_(tool_panic)("unknown loss mode");
897 if (VG_(clo_verbosity) > 0 && !VG_(clo_xml)) {
898 VG_(umsg)("LEAK SUMMARY:\n");
899 VG_(umsg)(" definitely lost: %'lu bytes in %'lu blocks\n",
900 MC_(bytes_leaked), MC_(blocks_leaked) );
901 VG_(umsg)(" indirectly lost: %'lu bytes in %'lu blocks\n",
902 MC_(bytes_indirect), MC_(blocks_indirect) );
903 VG_(umsg)(" possibly lost: %'lu bytes in %'lu blocks\n",
904 MC_(bytes_dubious), MC_(blocks_dubious) );
905 VG_(umsg)(" still reachable: %'lu bytes in %'lu blocks\n",
906 MC_(bytes_reachable), MC_(blocks_reachable) );
907 VG_(umsg)(" suppressed: %'lu bytes in %'lu blocks\n",
908 MC_(bytes_suppressed), MC_(blocks_suppressed) );
909 if (!is_full_check &&
910 (MC_(blocks_leaked) + MC_(blocks_indirect) +
911 MC_(blocks_dubious) + MC_(blocks_reachable)) > 0) {
912 VG_(umsg)("Rerun with --leak-check=full to see details "
913 "of leaked memory\n");
916 MC_(blocks_reachable) > 0 && !MC_(clo_show_reachable))
918 VG_(umsg)("Reachable blocks (those to which a pointer "
919 "was found) are not shown.\n");
920 VG_(umsg)("To see them, rerun with: --leak-check=full "
921 "--show-reachable=yes\n");
927 /*------------------------------------------------------------*/
928 /*--- Top-level entry point. ---*/
929 /*------------------------------------------------------------*/
931 void MC_(detect_memory_leaks) ( ThreadId tid, LeakCheckMode mode )
935 tl_assert(mode != LC_Off);
937 // Get the chunks, stop if there were none.
938 lc_chunks = find_active_chunks(&lc_n_chunks);
939 if (lc_n_chunks == 0) {
940 tl_assert(lc_chunks == NULL);
941 if (VG_(clo_verbosity) >= 1 && !VG_(clo_xml)) {
942 VG_(umsg)("All heap blocks were freed -- no leaks are possible\n");
948 // Sort the array so blocks are in ascending order in memory.
949 VG_(ssort)(lc_chunks, lc_n_chunks, sizeof(VgHashNode*), compare_MC_Chunks);
951 // Sanity check -- make sure they're in order.
952 for (i = 0; i < lc_n_chunks-1; i++) {
953 tl_assert( lc_chunks[i]->data <= lc_chunks[i+1]->data);
956 // Sanity check -- make sure they don't overlap. The one exception is that
957 // we allow a MALLOCLIKE block to sit entirely within a malloc() block.
958 // This is for bug 100628. If this occurs, we ignore the malloc() block
959 // for leak-checking purposes. This is a hack and probably should be done
960 // better, but at least it's consistent with mempools (which are treated
961 // like this in find_active_chunks). Mempools have a separate VgHashTable
962 // for mempool chunks, but if custom-allocated blocks are put in a separate
963 // table from normal heap blocks it makes free-mismatch checking more
966 // If this check fails, it probably means that the application
967 // has done something stupid with VALGRIND_MALLOCLIKE_BLOCK client
968 // requests, eg. has made overlapping requests (which are
969 // nonsensical), or used VALGRIND_MALLOCLIKE_BLOCK for stack locations;
970 // again nonsensical.
972 for (i = 0; i < lc_n_chunks-1; i++) {
973 MC_Chunk* ch1 = lc_chunks[i];
974 MC_Chunk* ch2 = lc_chunks[i+1];
976 Addr start1 = ch1->data;
977 Addr start2 = ch2->data;
978 Addr end1 = ch1->data + ch1->szB - 1;
979 Addr end2 = ch2->data + ch2->szB - 1;
980 Bool isCustom1 = ch1->allockind == MC_AllocCustom;
981 Bool isCustom2 = ch2->allockind == MC_AllocCustom;
984 // Normal case - no overlap.
986 // We used to allow exact duplicates, I'm not sure why. --njn
987 //} else if (start1 == start2 && end1 == end2) {
988 // Degenerate case: exact duplicates.
990 } else if (start1 >= start2 && end1 <= end2 && isCustom1 && !isCustom2) {
991 // Block i is MALLOCLIKE and entirely within block i+1.
993 for (j = i+1; j < lc_n_chunks-1; j++) {
994 lc_chunks[j] = lc_chunks[j+1];
998 } else if (start2 >= start1 && end2 <= end1 && isCustom2 && !isCustom1) {
999 // Block i+1 is MALLOCLIKE and entirely within block i.
1001 for (j = i; j < lc_n_chunks-1; j++) {
1002 lc_chunks[j] = lc_chunks[j+1];
1007 VG_(umsg)("Block 0x%lx..0x%lx overlaps with block 0x%lx..0x%lx",
1008 start1, end1, start2, end2);
1009 VG_(umsg)("This is usually caused by using VALGRIND_MALLOCLIKE_BLOCK");
1010 VG_(umsg)("in an inappropriate way.");
1015 // Initialise lc_extras.
1016 lc_extras = VG_(malloc)( "mc.dml.2", lc_n_chunks * sizeof(LC_Extra) );
1017 for (i = 0; i < lc_n_chunks; i++) {
1018 lc_extras[i].state = Unreached;
1019 lc_extras[i].pending = False;
1020 lc_extras[i].indirect_szB = 0;
1023 // Initialise lc_markstack.
1024 lc_markstack = VG_(malloc)( "mc.dml.2", lc_n_chunks * sizeof(Int) );
1025 for (i = 0; i < lc_n_chunks; i++) {
1026 lc_markstack[i] = -1;
1028 lc_markstack_top = -1;
1031 if (VG_(clo_verbosity) > 1 && !VG_(clo_xml)) {
1032 VG_(umsg)( "Searching for pointers to %'d not-freed blocks\n",
1036 // Scan the memory root-set, pushing onto the mark stack any blocks
1040 Addr* seg_starts = VG_(get_segment_starts)( &n_seg_starts );
1042 tl_assert(seg_starts && n_seg_starts > 0);
1046 // VG_(am_show_nsegments)( 0, "leakcheck");
1047 for (i = 0; i < n_seg_starts; i++) {
1049 NSegment const* seg = VG_(am_find_nsegment)( seg_starts[i] );
1052 if (seg->kind != SkFileC && seg->kind != SkAnonC) continue;
1053 if (!(seg->hasR && seg->hasW)) continue;
1054 if (seg->isCH) continue;
1056 // Don't poke around in device segments as this may cause
1057 // hangs. Exclude /dev/zero just in case someone allocated
1058 // memory by explicitly mapping /dev/zero.
1059 if (seg->kind == SkFileC
1060 && (VKI_S_ISCHR(seg->mode) || VKI_S_ISBLK(seg->mode))) {
1061 HChar* dev_name = VG_(am_get_filename)( (NSegment*)seg );
1062 if (dev_name && 0 == VG_(strcmp)(dev_name, "/dev/zero")) {
1063 // Don't skip /dev/zero.
1065 // Skip this device mapping.
1071 VG_(printf)("ACCEPT %2d %#lx %#lx\n", i, seg->start, seg->end);
1073 // Scan the segment. We use -1 for the clique number, because this
1075 seg_size = seg->end - seg->start + 1;
1076 if (VG_(clo_verbosity) > 2) {
1077 VG_(message)(Vg_DebugMsg,
1078 " Scanning root segment: %#lx..%#lx (%lu)\n",
1079 seg->start, seg->end, seg_size);
1081 lc_scan_memory(seg->start, seg_size, /*is_prior_definite*/True, -1);
1085 // Scan GP registers for chunk pointers.
1086 VG_(apply_to_GP_regs)(lc_push_if_a_chunk_ptr_register);
1088 // Process the pushed blocks. After this, every block that is reachable
1089 // from the root-set has been traced.
1090 lc_process_markstack(/*clique*/-1);
1092 if (VG_(clo_verbosity) > 1 && !VG_(clo_xml)) {
1093 VG_(umsg)("Checked %'lu bytes\n", lc_scanned_szB);
1097 // Trace all the leaked blocks to determine which are directly leaked and
1098 // which are indirectly leaked. For each Unreached block, push it onto
1099 // the mark stack, and find all the as-yet-Unreached blocks reachable
1100 // from it. These form a clique and are marked IndirectLeak, and their
1101 // size is added to the clique leader's indirect size. If one of the
1102 // found blocks was itself a clique leader (from a previous clique), then
1103 // the cliques are merged.
1104 for (i = 0; i < lc_n_chunks; i++) {
1105 MC_Chunk* ch = lc_chunks[i];
1106 LC_Extra* ex = &(lc_extras[i]);
1108 if (VG_DEBUG_CLIQUE)
1109 VG_(printf)("cliques: %d at %#lx -> Loss state %d\n",
1110 i, ch->data, ex->state);
1112 tl_assert(lc_markstack_top == -1);
1114 if (ex->state == Unreached) {
1115 if (VG_DEBUG_CLIQUE)
1116 VG_(printf)("%d: gathering clique %#lx\n", i, ch->data);
1118 // Push this Unreached block onto the stack and process it.
1120 lc_process_markstack(i);
1122 tl_assert(lc_markstack_top == -1);
1123 tl_assert(ex->state == Unreached);
1127 print_results( tid, ( mode == LC_Full ? True : False ) );
1129 VG_(free) ( lc_chunks );
1130 VG_(free) ( lc_extras );
1131 VG_(free) ( lc_markstack );
1134 /*--------------------------------------------------------------------*/
1136 /*--------------------------------------------------------------------*/