mc_leakcheck.c revision e10c7f87d8530adde17869136f9695986be29696
1 2/*--------------------------------------------------------------------*/ 3/*--- The leak checker. mc_leakcheck.c ---*/ 4/*--------------------------------------------------------------------*/ 5 6/* 7 This file is part of MemCheck, a heavyweight Valgrind tool for 8 detecting memory errors. 9 10 Copyright (C) 2000-2009 Julian Seward 11 jseward@acm.org 12 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. 17 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. 22 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 26 02111-1307, USA. 27 28 The GNU General Public License is contained in the file COPYING. 29*/ 30 31#include "pub_tool_basics.h" 32#include "pub_tool_vki.h" 33#include "pub_tool_aspacemgr.h" 34#include "pub_tool_execontext.h" 35#include "pub_tool_hashtable.h" 36#include "pub_tool_libcbase.h" 37#include "pub_tool_libcassert.h" 38#include "pub_tool_libcprint.h" 39#include "pub_tool_libcsignal.h" 40#include "pub_tool_machine.h" 41#include "pub_tool_mallocfree.h" 42#include "pub_tool_options.h" 43#include "pub_tool_oset.h" 44#include "pub_tool_signals.h" 45#include "pub_tool_tooliface.h" // Needed for mc_include.h 46 47#include "mc_include.h" 48 49#include <setjmp.h> // For jmp_buf 50 51/*------------------------------------------------------------*/ 52/*--- An overview of leak checking. ---*/ 53/*------------------------------------------------------------*/ 54 55// Leak-checking is a directed-graph traversal problem. The graph has 56// two kinds of nodes: 57// - root-set 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. 66// 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. 70// 71// We use "pointers" rather than "edges" below. 72// 73// Root set nodes only point to blocks. Blocks only point to blocks; 74// a block can point to itself. 75// 76// The aim is to traverse the graph and determine the status of each block. 77// 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 85// 86// It's far from clear that this is the best possible categorisation; it's 87// accreted over time without any central guiding principle. 88 89/*------------------------------------------------------------*/ 90/*--- XXX: Thoughts for improvement. ---*/ 91/*------------------------------------------------------------*/ 92 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. 98// 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. 102// 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: 106// R, DL, IL. 107// 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... 111// 112// ---- 113// 114// Also, why are two blank lines printed between each loss record? 115// 116// ---- 117// 118// Also, --show-reachable is a bad name because it also turns on the showing 119// of indirectly leaked blocks(!) It would be better named --show-all or 120// --show-all-heap-blocks, because that's the end result. 121// 122// ---- 123// 124// Also, the VALGRIND_LEAK_CHECK and VALGRIND_QUICK_LEAK_CHECK aren't great 125// names. VALGRIND_FULL_LEAK_CHECK and VALGRIND_SUMMARY_LEAK_CHECK would be 126// better. 127// 128// ---- 129// 130// Also, VALGRIND_COUNT_LEAKS and VALGRIND_COUNT_LEAK_BLOCKS aren't great as 131// they combine direct leaks and indirect leaks into one. New, more precise 132// ones (they'll need new names) would be good. If more categories are 133// used, as per the --follow-interior-pointers option, they should be 134// updated accordingly. And they should use a struct to return the values. 135// 136// ---- 137// 138// Also, for this case: 139// 140// (4) p4 BBB ---> AAA 141// 142// BBB is definitely directly lost. AAA is definitely indirectly lost. 143// Here's the relevant loss records printed for a full check (each block is 144// 16 bytes): 145// 146// ==20397== 16 bytes in 1 blocks are indirectly lost in loss record 9 of 15 147// ==20397== at 0x4C2694E: malloc (vg_replace_malloc.c:177) 148// ==20397== by 0x400521: mk (leak-cases.c:49) 149// ==20397== by 0x400578: main (leak-cases.c:72) 150// 151// ==20397== 32 (16 direct, 16 indirect) bytes in 1 blocks are definitely 152// lost in loss record 14 of 15 153// ==20397== at 0x4C2694E: malloc (vg_replace_malloc.c:177) 154// ==20397== by 0x400521: mk (leak-cases.c:49) 155// ==20397== by 0x400580: main (leak-cases.c:72) 156// 157// The first one is fine -- it describes AAA. 158// 159// The second one is for BBB. It's correct in that 16 bytes in 1 block are 160// directly lost. It's also correct that 16 are indirectly lost as a result, 161// but it means that AAA is being counted twice in the loss records. (It's 162// not, thankfully, counted twice in the summary counts). Argh. 163// 164// This would be less confusing for the second one: 165// 166// ==20397== 16 bytes in 1 blocks are definitely lost in loss record 14 167// of 15 (and 16 bytes in 1 block are indirectly lost as a result; they 168// are mentioned elsewhere (if --show-reachable=yes is given!)) 169// ==20397== at 0x4C2694E: malloc (vg_replace_malloc.c:177) 170// ==20397== by 0x400521: mk (leak-cases.c:49) 171// ==20397== by 0x400580: main (leak-cases.c:72) 172// 173// But ideally we'd present the loss record for the directly lost block and 174// then the resultant indirectly lost blocks and make it clear the 175// dependence. Double argh. 176 177/*------------------------------------------------------------*/ 178/*--- The actual algorithm. ---*/ 179/*------------------------------------------------------------*/ 180 181// - Find all the blocks (a.k.a. chunks) to check. Mempool chunks require 182// some special treatment because they can be within malloc'd blocks. 183// - Scan every word in the root set (GP registers and valid 184// non-heap memory words). 185// - First, we skip if it doesn't point to valid memory. 186// - Then, we see if it points to the start or interior of a block. If 187// so, we push the block onto the mark stack and mark it as having been 188// reached. 189// - Then, we process the mark stack, repeating the scanning for each block; 190// this can push more blocks onto the mark stack. We repeat until the 191// mark stack is empty. Each block is marked as definitely or possibly 192// reachable, depending on whether interior-pointers were required to 193// reach it. 194// - At this point we know for every block if it's reachable or not. 195// - We then push each unreached block onto the mark stack, using the block 196// number as the "clique" number. 197// - We process the mark stack again, this time grouping blocks into cliques 198// in order to facilitate the directly/indirectly lost categorisation. 199// - We group blocks by their ExeContexts and categorisation, and print them 200// if --leak-check=full. We also print summary numbers. 201// 202// A note on "cliques": 203// - A directly lost block is one with no pointers to it. An indirectly 204// lost block is one that is pointed to by a directly or indirectly lost 205// block. 206// - Each directly lost block has zero or more indirectly lost blocks 207// hanging off it. All these blocks together form a "clique". The 208// directly lost block is called the "clique leader". The clique number 209// is the number (in lc_chunks[]) of the clique leader. 210// - Actually, a directly lost block may be pointed to if it's part of a 211// cycle. In that case, there may be more than one choice for the clique 212// leader, and the choice is arbitrary. Eg. if you have A-->B and B-->A 213// either A or B could be the clique leader. 214// - Cliques cannot overlap, and will be truncated to avoid this. Eg. if we 215// have A-->C and B-->C, the two cliques will be {A,C} and {B}, or {A} and 216// {B,C} (again the choice is arbitrary). This is because we don't want 217// to count a block as indirectly lost more than once. 218// 219// A note on 'is_prior_definite': 220// - This is a boolean used in various places that indicates if the chain 221// up to the prior node (prior to the one being considered) is definite. 222// - In the clique == -1 case: 223// - if True it means that the prior node is a root-set node, or that the 224// prior node is a block which is reachable from the root-set via 225// start-pointers. 226// - if False it means that the prior node is a block that is only 227// reachable from the root-set via a path including at least one 228// interior-pointer. 229// - In the clique != -1 case, currently it's always True because we treat 230// start-pointers and interior-pointers the same for direct/indirect leak 231// checking. If we added a PossibleIndirectLeak state then this would 232// change. 233 234 235// Define to debug the memory-leak-detector. 236#define VG_DEBUG_LEAKCHECK 0 237#define VG_DEBUG_CLIQUE 0 238 239#define UMSG(args...) VG_(message)(Vg_UserMsg, ##args) 240 241/*------------------------------------------------------------*/ 242/*--- Getting the initial chunks, and searching them. ---*/ 243/*------------------------------------------------------------*/ 244 245// Compare the MC_Chunks by 'data' (i.e. the address of the block). 246static Int compare_MC_Chunks(void* n1, void* n2) 247{ 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; 252 return 0; 253} 254 255#if VG_DEBUG_LEAKCHECK 256// Used to sanity-check the fast binary-search mechanism. 257static 258Int find_chunk_for_OLD ( Addr ptr, 259 MC_Chunk** chunks, 260 Int n_chunks ) 261 262{ 263 Int i; 264 Addr a_lo, a_hi; 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) 271 return i; 272 } 273 return -1; 274} 275#endif 276 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. 280static 281Int find_chunk_for ( Addr ptr, 282 MC_Chunk** chunks, 283 Int n_chunks ) 284{ 285 Addr a_mid_lo, a_mid_hi; 286 Int lo, mid, hi, retVal; 287 // VG_(printf)("find chunk for %p = ", ptr); 288 retVal = -1; 289 lo = 0; 290 hi = n_chunks-1; 291 while (True) { 292 // Invariant: current unsearched space is from lo to hi, inclusive. 293 if (lo > hi) break; // not found 294 295 mid = (lo + hi) / 2; 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) 305 a_mid_hi++; 306 307 if (ptr < a_mid_lo) { 308 hi = mid-1; 309 continue; 310 } 311 if (ptr >= a_mid_hi) { 312 lo = mid+1; 313 continue; 314 } 315 tl_assert(ptr >= a_mid_lo && ptr < a_mid_hi); 316 retVal = mid; 317 break; 318 } 319 320# if VG_DEBUG_LEAKCHECK 321 tl_assert(retVal == find_chunk_for_OLD ( ptr, chunks, n_chunks )); 322# endif 323 // VG_(printf)("%d\n", retVal); 324 return retVal; 325} 326 327 328static MC_Chunk** 329find_active_chunks(UInt* pn_chunks) 330{ 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 333 // mempool chunk. 334 MC_Mempool *mp; 335 MC_Chunk **mallocs, **chunks, *mc; 336 UInt n_mallocs, n_chunks, m, s; 337 Bool *malloc_chunk_holds_a_pool_chunk; 338 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); 345 *pn_chunks = 0; 346 return NULL; 347 } 348 VG_(ssort)(mallocs, n_mallocs, sizeof(VgHashNode*), compare_MC_Chunks); 349 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; 355 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)) ) { 363 364 // We'll need to record this chunk. 365 n_chunks++; 366 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); 371 n_chunks--; 372 malloc_chunk_holds_a_pool_chunk[m] = True; 373 } 374 375 // Possibly invalidate the malloc holding the end of this chunk. 376 if (mc->szB > 1) { 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); 380 n_chunks--; 381 malloc_chunk_holds_a_pool_chunk[m] = True; 382 } 383 } 384 } 385 } 386 tl_assert(n_chunks > 0); 387 388 // Create final chunk array. 389 chunks = VG_(malloc)("mc.fas.2", sizeof(VgHashNode*) * (n_chunks)); 390 s = 0; 391 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); 399 chunks[s++] = mc; 400 } 401 } 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]; 406 } 407 } 408 tl_assert(s == n_chunks); 409 410 // Free temporaries. 411 VG_(free)(mallocs); 412 VG_(free)(malloc_chunk_holds_a_pool_chunk); 413 414 *pn_chunks = n_chunks; 415 416 return chunks; 417} 418 419/*------------------------------------------------------------*/ 420/*--- The leak detector proper. ---*/ 421/*------------------------------------------------------------*/ 422 423// Holds extra info about each block during leak checking. 424typedef 425 struct { 426 UInt state:2; // Reachedness. 427 SizeT indirect_szB : (sizeof(SizeT)*8)-2; // If Unreached, how many bytes 428 // are unreachable from here. 429 } 430 LC_Extra; 431 432// An array holding pointers to every chunk we're checking. Sorted by address. 433static MC_Chunk** lc_chunks; 434// How many chunks we're dealing with. 435static Int lc_n_chunks; 436 437// This has the same number of entries as lc_chunks, and each entry 438// in lc_chunks corresponds with the entry here (ie. lc_chunks[i] and 439// lc_extras[i] describe the same block). 440static LC_Extra* lc_extras; 441 442// Records chunks that are currently being processed. Each element in the 443// stack is an index into lc_chunks and lc_extras. Its size is 444// 'lc_n_chunks' because in the worst case that's how many chunks could be 445// pushed onto it (actually I think the maximum is lc_n_chunks-1 but let's 446// be conservative). 447static Int* lc_markstack; 448// The index of the top element of the stack; -1 if the stack is empty, 0 if 449// the stack has one element, 1 if it has two, etc. 450static Int lc_markstack_top; 451 452// Keeps track of how many bytes of memory we've scanned, for printing. 453// (Nb: We don't keep track of how many register bytes we've scanned.) 454static SizeT lc_scanned_szB; 455 456 457SizeT MC_(bytes_leaked) = 0; 458SizeT MC_(bytes_indirect) = 0; 459SizeT MC_(bytes_dubious) = 0; 460SizeT MC_(bytes_reachable) = 0; 461SizeT MC_(bytes_suppressed) = 0; 462 463SizeT MC_(blocks_leaked) = 0; 464SizeT MC_(blocks_indirect) = 0; 465SizeT MC_(blocks_dubious) = 0; 466SizeT MC_(blocks_reachable) = 0; 467SizeT MC_(blocks_suppressed) = 0; 468 469 470/* TODO: GIVE THIS A PROPER HOME 471 TODO: MERGE THIS WITH DUPLICATE IN m_main.c and coredump-elf.c. 472 Extract from aspacem a vector of the current segment start 473 addresses. The vector is dynamically allocated and should be freed 474 by the caller when done. REQUIRES m_mallocfree to be running. 475 Writes the number of addresses required into *n_acquired. */ 476 477static Addr* get_seg_starts ( /*OUT*/Int* n_acquired ) 478{ 479 Addr* starts; 480 Int n_starts, r = 0; 481 482 n_starts = 1; 483 while (True) { 484 starts = VG_(malloc)( "mc.gss.1", n_starts * sizeof(Addr) ); 485 if (starts == NULL) 486 break; 487 r = VG_(am_get_segment_starts)( starts, n_starts ); 488 if (r >= 0) 489 break; 490 VG_(free)(starts); 491 n_starts *= 2; 492 } 493 494 if (starts == NULL) { 495 *n_acquired = 0; 496 return NULL; 497 } 498 499 *n_acquired = r; 500 return starts; 501} 502 503 504// Determines if a pointer is to a chunk. Returns the chunk number et al 505// via call-by-reference. 506static Bool 507lc_is_a_chunk_ptr(Addr ptr, Int* pch_no, MC_Chunk** pch, LC_Extra** pex) 508{ 509 Int ch_no; 510 MC_Chunk* ch; 511 LC_Extra* ex; 512 513 // Quick filter. 514 if (!VG_(am_is_valid_for_client)(ptr, 1, VKI_PROT_READ)) { 515 return False; 516 } else { 517 ch_no = find_chunk_for(ptr, lc_chunks, lc_n_chunks); 518 tl_assert(ch_no >= -1 && ch_no < lc_n_chunks); 519 520 if (ch_no == -1) { 521 return False; 522 } else { 523 // Ok, we've found a pointer to a chunk. Get the MC_Chunk and its 524 // LC_Extra. 525 ch = lc_chunks[ch_no]; 526 ex = &(lc_extras[ch_no]); 527 528 tl_assert(ptr >= ch->data); 529 tl_assert(ptr < ch->data + ch->szB + (ch->szB==0 ? 1 : 0)); 530 531 if (VG_DEBUG_LEAKCHECK) 532 VG_(printf)("ptr=%#lx -> block %d\n", ptr, ch_no); 533 534 *pch_no = ch_no; 535 *pch = ch; 536 *pex = ex; 537 538 return True; 539 } 540 } 541} 542 543// Push a chunk (well, just its index) onto the mark stack. 544static void lc_push(Int ch_no, MC_Chunk* ch) 545{ 546 if (0) { 547 VG_(printf)("pushing %#lx-%#lx\n", ch->data, ch->data + ch->szB); 548 } 549 lc_markstack_top++; 550 tl_assert(lc_markstack_top < lc_n_chunks); 551 lc_markstack[lc_markstack_top] = ch_no; 552} 553 554// Return the index of the chunk on the top of the mark stack, or -1 if 555// there isn't one. 556static Bool lc_pop(Int* ret) 557{ 558 if (-1 == lc_markstack_top) { 559 return False; 560 } else { 561 tl_assert(0 <= lc_markstack_top && lc_markstack_top < lc_n_chunks); 562 *ret = lc_markstack[lc_markstack_top]; 563 lc_markstack_top--; 564 return True; 565 } 566} 567 568 569// If 'ptr' is pointing to a heap-allocated block which hasn't been seen 570// before, push it onto the mark stack. 571static void 572lc_push_without_clique_if_a_chunk_ptr(Addr ptr, Bool is_prior_definite) 573{ 574 Int ch_no; 575 MC_Chunk* ch; 576 LC_Extra* ex; 577 578 if ( ! lc_is_a_chunk_ptr(ptr, &ch_no, &ch, &ex) ) 579 return; 580 581 // Only push it if it hasn't been seen previously. 582 if (ex->state == Unreached) { 583 lc_push(ch_no, ch); 584 } 585 586 // Possibly upgrade the state, ie. one of: 587 // - Unreached --> Possible 588 // - Unreached --> Reachable 589 // - Possible --> Reachable 590 if (ptr == ch->data && is_prior_definite) { 591 // 'ptr' points to the start of the block, and the prior node is 592 // definite, which means that this block is definitely reachable. 593 ex->state = Reachable; 594 595 } else if (ex->state == Unreached) { 596 // Either 'ptr' is a interior-pointer, or the prior node isn't definite, 597 // which means that we can only mark this block as possibly reachable. 598 ex->state = Possible; 599 } 600} 601 602static void 603lc_push_if_a_chunk_ptr_register(Addr ptr) 604{ 605 lc_push_without_clique_if_a_chunk_ptr(ptr, /*is_prior_definite*/True); 606} 607 608// If ptr is pointing to a heap-allocated block which hasn't been seen 609// before, push it onto the mark stack. Clique is the index of the 610// clique leader. 611static void 612lc_push_with_clique_if_a_chunk_ptr(Addr ptr, Int clique) 613{ 614 Int ch_no; 615 MC_Chunk* ch; 616 LC_Extra* ex; 617 618 tl_assert(0 <= clique && clique < lc_n_chunks); 619 620 if ( ! lc_is_a_chunk_ptr(ptr, &ch_no, &ch, &ex) ) 621 return; 622 623 // If it's not Unreached, it's already been handled so ignore it. 624 // If ch_no==clique, it's the clique leader, which means this is a cyclic 625 // structure; again ignore it because it's already been handled. 626 if (ex->state == Unreached && ch_no != clique) { 627 // Note that, unlike reachable blocks, we currently don't distinguish 628 // between start-pointers and interior-pointers here. We probably 629 // should, though. 630 ex->state = IndirectLeak; 631 lc_push(ch_no, ch); 632 633 // Add the block to the clique, and add its size to the 634 // clique-leader's indirect size. Also, if the new block was 635 // itself a clique leader, it isn't any more, so add its 636 // indirect_szB to the new clique leader. 637 if (VG_DEBUG_CLIQUE) { 638 if (ex->indirect_szB > 0) 639 VG_(printf)(" clique %d joining clique %d adding %lu+%lu\n", 640 ch_no, clique, (SizeT)ch->szB, (SizeT)ex->indirect_szB); 641 else 642 VG_(printf)(" block %d joining clique %d adding %lu\n", 643 ch_no, clique, (SizeT)ch->szB); 644 } 645 646 lc_extras[clique].indirect_szB += ch->szB; 647 lc_extras[clique].indirect_szB += ex->indirect_szB; 648 ex->indirect_szB = 0; // Shouldn't matter. 649 } 650} 651 652static void 653lc_push_if_a_chunk_ptr(Addr ptr, Int clique, Bool is_prior_definite) 654{ 655 if (-1 == clique) 656 lc_push_without_clique_if_a_chunk_ptr(ptr, is_prior_definite); 657 else 658 lc_push_with_clique_if_a_chunk_ptr(ptr, clique); 659} 660 661 662static jmp_buf memscan_jmpbuf; 663 664static 665void scan_all_valid_memory_catcher ( Int sigNo, Addr addr ) 666{ 667 if (0) 668 VG_(printf)("OUCH! sig=%d addr=%#lx\n", sigNo, addr); 669 if (sigNo == VKI_SIGSEGV || sigNo == VKI_SIGBUS) 670 __builtin_longjmp(memscan_jmpbuf, 1); 671} 672 673// Scan a block of memory between [start, start+len). This range may 674// be bogus, inaccessable, or otherwise strange; we deal with it. For each 675// valid aligned word we assume it's a pointer to a chunk a push the chunk 676// onto the mark stack if so. 677static void 678lc_scan_memory(Addr start, SizeT len, Bool is_prior_definite, Int clique) 679{ 680 Addr ptr = VG_ROUNDUP(start, sizeof(Addr)); 681 Addr end = VG_ROUNDDN(start+len, sizeof(Addr)); 682 vki_sigset_t sigmask; 683 684 if (VG_DEBUG_LEAKCHECK) 685 VG_(printf)("scan %#lx-%#lx (%lu)\n", start, end, len); 686 687 VG_(sigprocmask)(VKI_SIG_SETMASK, NULL, &sigmask); 688 VG_(set_fault_catcher)(scan_all_valid_memory_catcher); 689 690 // We might be in the middle of a page. Do a cheap check to see if 691 // it's valid; if not, skip onto the next page. 692 if (!VG_(am_is_valid_for_client)(ptr, sizeof(Addr), VKI_PROT_READ)) 693 ptr = VG_PGROUNDUP(ptr+1); // First page is bad - skip it. 694 695 while (ptr < end) { 696 Addr addr; 697 698 // Skip invalid chunks. 699 if ( ! MC_(is_within_valid_secondary)(ptr) ) { 700 ptr = VG_ROUNDUP(ptr+1, SM_SIZE); 701 continue; 702 } 703 704 // Look to see if this page seems reasonable. 705 if ((ptr % VKI_PAGE_SIZE) == 0) { 706 if (!VG_(am_is_valid_for_client)(ptr, sizeof(Addr), VKI_PROT_READ)) { 707 ptr += VKI_PAGE_SIZE; // Bad page - skip it. 708 continue; 709 } 710 } 711 712 if (__builtin_setjmp(memscan_jmpbuf) == 0) { 713 if ( MC_(is_valid_aligned_word)(ptr) ) { 714 lc_scanned_szB += sizeof(Addr); 715 addr = *(Addr *)ptr; 716 // If we get here, the scanned word is in valid memory. Now 717 // let's see if its contents point to a chunk. 718 lc_push_if_a_chunk_ptr(addr, clique, is_prior_definite); 719 } else if (0 && VG_DEBUG_LEAKCHECK) { 720 VG_(printf)("%#lx not valid\n", ptr); 721 } 722 ptr += sizeof(Addr); 723 } else { 724 // We need to restore the signal mask, because we were 725 // longjmped out of a signal handler. 726 VG_(sigprocmask)(VKI_SIG_SETMASK, &sigmask, NULL); 727 728 ptr = VG_PGROUNDUP(ptr+1); // Bad page - skip it. 729 } 730 } 731 732 VG_(sigprocmask)(VKI_SIG_SETMASK, &sigmask, NULL); 733 VG_(set_fault_catcher)(NULL); 734} 735 736 737// Process the mark stack until empty. 738static void lc_process_markstack(Int clique) 739{ 740 Int top; 741 Bool is_prior_definite; 742 743 while (lc_pop(&top)) { 744 tl_assert(top >= 0 && top < lc_n_chunks); 745 746 // See comment about 'is_prior_definite' at the top to understand this. 747 is_prior_definite = ( Possible != lc_extras[top].state ); 748 749 lc_scan_memory(lc_chunks[top]->data, lc_chunks[top]->szB, 750 is_prior_definite, clique); 751 } 752} 753 754static Word cmp_LossRecordKey_LossRecord(const void* key, const void* elem) 755{ 756 LossRecordKey* a = (LossRecordKey*)key; 757 LossRecordKey* b = &(((LossRecord*)elem)->key); 758 759 // Compare on states first because that's fast. 760 if (a->state < b->state) return -1; 761 if (a->state > b->state) return 1; 762 // Ok, the states are equal. Now compare the locations, which is slower. 763 if (VG_(eq_ExeContext)( 764 MC_(clo_leak_resolution), a->allocated_at, b->allocated_at)) 765 return 0; 766 // Different locations. Ordering is arbitrary, just use the ec pointer. 767 if (a->allocated_at < b->allocated_at) return -1; 768 if (a->allocated_at > b->allocated_at) return 1; 769 VG_(tool_panic)("bad LossRecord comparison"); 770} 771 772static Int cmp_LossRecords(void* va, void* vb) 773{ 774 LossRecord* lr_a = *(LossRecord**)va; 775 LossRecord* lr_b = *(LossRecord**)vb; 776 SizeT total_szB_a = lr_a->szB + lr_a->indirect_szB; 777 SizeT total_szB_b = lr_b->szB + lr_b->indirect_szB; 778 779 // First compare by sizes. 780 if (total_szB_a < total_szB_b) return -1; 781 if (total_szB_a > total_szB_b) return 1; 782 // If size are equal, compare by states. 783 if (lr_a->key.state < lr_b->key.state) return -1; 784 if (lr_a->key.state > lr_b->key.state) return 1; 785 // If they're still equal here, it doesn't matter that much, but we keep 786 // comparing other things so that regtests are as deterministic as 787 // possible. So: compare num_blocks. 788 if (lr_a->num_blocks < lr_b->num_blocks) return -1; 789 if (lr_a->num_blocks > lr_b->num_blocks) return 1; 790 // Finally, compare ExeContext addresses... older ones are likely to have 791 // lower addresses. 792 if (lr_a->key.allocated_at < lr_b->key.allocated_at) return -1; 793 if (lr_a->key.allocated_at > lr_b->key.allocated_at) return 1; 794 return 0; 795} 796 797static void print_results(ThreadId tid, Bool is_full_check) 798{ 799 Int i, n_lossrecords; 800 OSet* lr_table; 801 LossRecord** lr_array; 802 LossRecord* lr; 803 Bool is_suppressed; 804 805 // Create the lr_table, which holds the loss records. 806 lr_table = 807 VG_(OSetGen_Create)(offsetof(LossRecord, key), 808 cmp_LossRecordKey_LossRecord, 809 VG_(malloc), "mc.pr.1", 810 VG_(free)); 811 812 // Convert the chunks into loss records, merging them where appropriate. 813 for (i = 0; i < lc_n_chunks; i++) { 814 MC_Chunk* ch = lc_chunks[i]; 815 LC_Extra* ex = &(lc_extras)[i]; 816 LossRecord* old_lr; 817 LossRecordKey lrkey; 818 lrkey.state = ex->state; 819 lrkey.allocated_at = ch->where; 820 821 old_lr = VG_(OSetGen_Lookup)(lr_table, &lrkey); 822 if (old_lr) { 823 // We found an existing loss record matching this chunk. Update the 824 // loss record's details in-situ. This is safe because we don't 825 // change the elements used as the OSet key. 826 old_lr->szB += ch->szB; 827 old_lr->indirect_szB += ex->indirect_szB; 828 old_lr->num_blocks++; 829 } else { 830 // No existing loss record matches this chunk. Create a new loss 831 // record, initialise it from the chunk, and insert it into lr_table. 832 lr = VG_(OSetGen_AllocNode)(lr_table, sizeof(LossRecord)); 833 lr->key = lrkey; 834 lr->szB = ch->szB; 835 lr->indirect_szB = ex->indirect_szB; 836 lr->num_blocks = 1; 837 VG_(OSetGen_Insert)(lr_table, lr); 838 } 839 } 840 n_lossrecords = VG_(OSetGen_Size)(lr_table); 841 842 // Create an array of pointers to the loss records. 843 lr_array = VG_(malloc)("mc.pr.2", n_lossrecords * sizeof(LossRecord*)); 844 i = 0; 845 VG_(OSetGen_ResetIter)(lr_table); 846 while ( (lr = VG_(OSetGen_Next)(lr_table)) ) { 847 lr_array[i++] = lr; 848 } 849 tl_assert(i == n_lossrecords); 850 851 // Sort the array by loss record sizes. 852 VG_(ssort)(lr_array, n_lossrecords, sizeof(LossRecord*), 853 cmp_LossRecords); 854 855 // Zero totals. 856 MC_(blocks_leaked) = MC_(bytes_leaked) = 0; 857 MC_(blocks_indirect) = MC_(bytes_indirect) = 0; 858 MC_(blocks_dubious) = MC_(bytes_dubious) = 0; 859 MC_(blocks_reachable) = MC_(bytes_reachable) = 0; 860 MC_(blocks_suppressed) = MC_(bytes_suppressed) = 0; 861 862 // Print the loss records (in size order) and collect summary stats. 863 for (i = 0; i < n_lossrecords; i++) { 864 Bool print_record; 865 // Rules for printing: 866 // - We don't show suppressed loss records ever (and that's controlled 867 // within the error manager). 868 // - We show non-suppressed loss records that are not "reachable" if 869 // --leak-check=yes. 870 // - We show all non-suppressed loss records if --leak-check=yes and 871 // --show-reachable=yes. 872 // 873 // Nb: here "reachable" means Reachable *or* IndirectLeak; note that 874 // this is different to "still reachable" used elsewhere because it 875 // includes indirectly lost blocks! 876 // 877 lr = lr_array[i]; 878 print_record = is_full_check && 879 ( MC_(clo_show_reachable) || 880 Unreached == lr->key.state || 881 Possible == lr->key.state ); 882 is_suppressed = 883 MC_(record_leak_error) ( tid, i+1, n_lossrecords, lr, print_record ); 884 885 if (is_suppressed) { 886 MC_(blocks_suppressed) += lr->num_blocks; 887 MC_(bytes_suppressed) += lr->szB; 888 889 } else if (Unreached == lr->key.state) { 890 MC_(blocks_leaked) += lr->num_blocks; 891 MC_(bytes_leaked) += lr->szB; 892 893 } else if (IndirectLeak == lr->key.state) { 894 MC_(blocks_indirect) += lr->num_blocks; 895 MC_(bytes_indirect) += lr->szB; 896 897 } else if (Possible == lr->key.state) { 898 MC_(blocks_dubious) += lr->num_blocks; 899 MC_(bytes_dubious) += lr->szB; 900 901 } else if (Reachable == lr->key.state) { 902 MC_(blocks_reachable) += lr->num_blocks; 903 MC_(bytes_reachable) += lr->szB; 904 905 } else { 906 VG_(tool_panic)("unknown loss mode"); 907 } 908 } 909 910 if (VG_(clo_verbosity) > 0 && !VG_(clo_xml)) { 911 UMSG(""); 912 UMSG("LEAK SUMMARY:"); 913 UMSG(" definitely lost: %'lu bytes in %'lu blocks.", 914 MC_(bytes_leaked), MC_(blocks_leaked) ); 915 UMSG(" indirectly lost: %'lu bytes in %'lu blocks.", 916 MC_(bytes_indirect), MC_(blocks_indirect) ); 917 UMSG(" possibly lost: %'lu bytes in %'lu blocks.", 918 MC_(bytes_dubious), MC_(blocks_dubious) ); 919 UMSG(" still reachable: %'lu bytes in %'lu blocks.", 920 MC_(bytes_reachable), MC_(blocks_reachable) ); 921 UMSG(" suppressed: %'lu bytes in %'lu blocks.", 922 MC_(bytes_suppressed), MC_(blocks_suppressed) ); 923 if (!is_full_check && 924 (MC_(blocks_leaked) + MC_(blocks_indirect) + 925 MC_(blocks_dubious) + MC_(blocks_reachable)) > 0) { 926 UMSG("Rerun with --leak-check=full to see details of leaked memory."); 927 } 928 if (is_full_check && 929 MC_(blocks_reachable) > 0 && !MC_(clo_show_reachable)) 930 { 931 UMSG("Reachable blocks (those to which a pointer was found) are not shown."); 932 UMSG("To see them, rerun with: --leak-check=full --show-reachable=yes"); 933 } 934 } 935} 936 937/*------------------------------------------------------------*/ 938/*--- Top-level entry point. ---*/ 939/*------------------------------------------------------------*/ 940 941void MC_(detect_memory_leaks) ( ThreadId tid, LeakCheckMode mode ) 942{ 943 Int i; 944 945 tl_assert(mode != LC_Off); 946 947 // Get the chunks, stop if there were none. 948 lc_chunks = find_active_chunks(&lc_n_chunks); 949 if (lc_n_chunks == 0) { 950 tl_assert(lc_chunks == NULL); 951 if (VG_(clo_verbosity) >= 1 && !VG_(clo_xml)) { 952 UMSG("All heap blocks were freed -- no leaks are possible."); 953 } 954 return; 955 } 956 957 // Sort the array so blocks are in ascending order in memory. 958 VG_(ssort)(lc_chunks, lc_n_chunks, sizeof(VgHashNode*), compare_MC_Chunks); 959 960 // Sanity check -- make sure they're in order. 961 for (i = 0; i < lc_n_chunks-1; i++) { 962 tl_assert( lc_chunks[i]->data <= lc_chunks[i+1]->data); 963 } 964 965 // Sanity check -- make sure they don't overlap. But do allow exact 966 // duplicates. If this assertion fails, it may mean that the application 967 // has done something stupid with VALGRIND_MALLOCLIKE_BLOCK client 968 // requests, specifically, has made overlapping requests (which are 969 // nonsensical). Another way to screw up is to use 970 // VALGRIND_MALLOCLIKE_BLOCK for stack locations; again nonsensical. 971 for (i = 0; i < lc_n_chunks-1; i++) { 972 MC_Chunk* ch1 = lc_chunks[i]; 973 MC_Chunk* ch2 = lc_chunks[i+1]; 974 Bool nonsense_overlap = ! ( 975 // Normal case - no overlap. 976 (ch1->data + ch1->szB <= ch2->data) || 977 // Degenerate case: exact duplicates. 978 (ch1->data == ch2->data && ch1->szB == ch2->szB) 979 ); 980 if (nonsense_overlap) { 981 UMSG("Block [0x%lx, 0x%lx) overlaps with block [0x%lx, 0x%lx)", 982 ch1->data, (ch1->data + ch1->szB), 983 ch2->data, (ch2->data + ch2->szB)); 984 } 985 tl_assert (!nonsense_overlap); 986 } 987 988 // Initialise lc_extras. 989 lc_extras = VG_(malloc)( "mc.dml.2", lc_n_chunks * sizeof(LC_Extra) ); 990 for (i = 0; i < lc_n_chunks; i++) { 991 lc_extras[i].state = Unreached; 992 lc_extras[i].indirect_szB = 0; 993 } 994 995 // Initialise lc_markstack. 996 lc_markstack = VG_(malloc)( "mc.dml.2", lc_n_chunks * sizeof(Int) ); 997 for (i = 0; i < lc_n_chunks; i++) { 998 lc_markstack[i] = -1; 999 } 1000 lc_markstack_top = -1; 1001 1002 // Verbosity. 1003 if (VG_(clo_verbosity) > 0 && !VG_(clo_xml)) 1004 UMSG( "searching for pointers to %'d not-freed blocks.", lc_n_chunks ); 1005 1006 // Scan the memory root-set, pushing onto the mark stack any blocks 1007 // pointed to. 1008 { 1009 Int n_seg_starts; 1010 Addr* seg_starts = get_seg_starts( &n_seg_starts ); 1011 1012 tl_assert(seg_starts && n_seg_starts > 0); 1013 1014 lc_scanned_szB = 0; 1015 1016 // VG_(am_show_nsegments)( 0, "leakcheck"); 1017 for (i = 0; i < n_seg_starts; i++) { 1018 SizeT seg_size; 1019 NSegment const* seg = VG_(am_find_nsegment)( seg_starts[i] ); 1020 tl_assert(seg); 1021 1022 if (seg->kind != SkFileC && seg->kind != SkAnonC) continue; 1023 if (!(seg->hasR && seg->hasW)) continue; 1024 if (seg->isCH) continue; 1025 1026 // Don't poke around in device segments as this may cause 1027 // hangs. Exclude /dev/zero just in case someone allocated 1028 // memory by explicitly mapping /dev/zero. 1029 if (seg->kind == SkFileC 1030 && (VKI_S_ISCHR(seg->mode) || VKI_S_ISBLK(seg->mode))) { 1031 HChar* dev_name = VG_(am_get_filename)( (NSegment*)seg ); 1032 if (dev_name && 0 == VG_(strcmp)(dev_name, "/dev/zero")) { 1033 // Don't skip /dev/zero. 1034 } else { 1035 // Skip this device mapping. 1036 continue; 1037 } 1038 } 1039 1040 if (0) 1041 VG_(printf)("ACCEPT %2d %#lx %#lx\n", i, seg->start, seg->end); 1042 1043 // Scan the segment. We use -1 for the clique number, because this 1044 // is a root-set. 1045 seg_size = seg->end - seg->start + 1; 1046 if (VG_(clo_verbosity) > 2) { 1047 VG_(message)(Vg_DebugMsg, 1048 " Scanning root segment: %#lx..%#lx (%lu)", 1049 seg->start, seg->end, seg_size); 1050 } 1051 lc_scan_memory(seg->start, seg_size, /*is_prior_definite*/True, -1); 1052 } 1053 } 1054 1055 // Scan GP registers for chunk pointers. 1056 VG_(apply_to_GP_regs)(lc_push_if_a_chunk_ptr_register); 1057 1058 // Process the pushed blocks. After this, every block that is reachable 1059 // from the root-set has been traced. 1060 lc_process_markstack(/*clique*/-1); 1061 1062 if (VG_(clo_verbosity) > 0 && !VG_(clo_xml)) 1063 UMSG("checked %'lu bytes.", lc_scanned_szB); 1064 1065 // Trace all the leaked blocks to determine which are directly leaked and 1066 // which are indirectly leaked. For each Unreached block, push it onto 1067 // the mark stack, and find all the as-yet-Unreached blocks reachable 1068 // from it. These form a clique and are marked IndirectLeak, and their 1069 // size is added to the clique leader's indirect size. If one of the 1070 // found blocks was itself a clique leader (from a previous clique), then 1071 // the cliques are merged. 1072 for (i = 0; i < lc_n_chunks; i++) { 1073 MC_Chunk* ch = lc_chunks[i]; 1074 LC_Extra* ex = &(lc_extras[i]); 1075 1076 if (VG_DEBUG_CLIQUE) 1077 VG_(printf)("cliques: %d at %#lx -> Loss state %d\n", 1078 i, ch->data, ex->state); 1079 1080 tl_assert(lc_markstack_top == -1); 1081 1082 if (ex->state == Unreached) { 1083 if (VG_DEBUG_CLIQUE) 1084 VG_(printf)("%d: gathering clique %#lx\n", i, ch->data); 1085 1086 // Push this Unreached block onto the stack and process it. 1087 lc_push(i, ch); 1088 lc_process_markstack(i); 1089 1090 tl_assert(lc_markstack_top == -1); 1091 tl_assert(ex->state == Unreached); 1092 } 1093 } 1094 1095 print_results( tid, ( mode == LC_Full ? True : False ) ); 1096 1097 VG_(free) ( lc_chunks ); 1098 VG_(free) ( lc_extras ); 1099 VG_(free) ( lc_markstack ); 1100} 1101 1102/*--------------------------------------------------------------------*/ 1103/*--- end ---*/ 1104/*--------------------------------------------------------------------*/ 1105 1106