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-2011 Julian Seward 11 jseward (at) 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_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 48 49 #include "mc_include.h" 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 // [bug 197930] 116 // 117 // ---- 118 // 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. 122 // 123 // ---- 124 // 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 127 // better. 128 // 129 // ---- 130 // 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. 136 // 137 // ---- 138 // 139 // Also, for this case: 140 // 141 // (4) p4 BBB ---> AAA 142 // 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 145 // 16 bytes): 146 // 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) 151 // 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) 157 // 158 // The first one is fine -- it describes AAA. 159 // 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. 164 // 165 // This would be less confusing for the second one: 166 // 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) 173 // 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. 177 178 /*------------------------------------------------------------*/ 179 /*--- The actual algorithm. ---*/ 180 /*------------------------------------------------------------*/ 181 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 189 // reached. 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 194 // reach it. 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. 202 // 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 206 // block. 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. 219 // 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 226 // start-pointers. 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 229 // interior-pointer. 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 233 // change. 234 235 236 // Define to debug the memory-leak-detector. 237 #define VG_DEBUG_LEAKCHECK 0 238 #define VG_DEBUG_CLIQUE 0 239 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). 246 static 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. 257 static 258 Int 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. 280 static 281 Int 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 328 static MC_Chunk** 329 find_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. 424 typedef 425 struct { 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. 430 } 431 LC_Extra; 432 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; 437 // chunks will be converted and merged in loss record, maintained in lr_table 438 // lr_table elements are kept from one leak_search to another to implement 439 // the "print new/changed leaks" client request 440 static OSet* lr_table; 441 442 // DeltaMode used the last time we called detect_memory_leaks. 443 // The recorded leak errors must be output using a logic based on this delta_mode. 444 // The below avoids replicating the delta_mode in each LossRecord. 445 LeakCheckDeltaMode MC_(detect_memory_leaks_last_delta_mode); 446 447 448 // This has the same number of entries as lc_chunks, and each entry 449 // in lc_chunks corresponds with the entry here (ie. lc_chunks[i] and 450 // lc_extras[i] describe the same block). 451 static LC_Extra* lc_extras; 452 453 // Records chunks that are currently being processed. Each element in the 454 // stack is an index into lc_chunks and lc_extras. Its size is 455 // 'lc_n_chunks' because in the worst case that's how many chunks could be 456 // pushed onto it (actually I think the maximum is lc_n_chunks-1 but let's 457 // be conservative). 458 static Int* lc_markstack; 459 // The index of the top element of the stack; -1 if the stack is empty, 0 if 460 // the stack has one element, 1 if it has two, etc. 461 static Int lc_markstack_top; 462 463 // Keeps track of how many bytes of memory we've scanned, for printing. 464 // (Nb: We don't keep track of how many register bytes we've scanned.) 465 static SizeT lc_scanned_szB; 466 467 468 SizeT MC_(bytes_leaked) = 0; 469 SizeT MC_(bytes_indirect) = 0; 470 SizeT MC_(bytes_dubious) = 0; 471 SizeT MC_(bytes_reachable) = 0; 472 SizeT MC_(bytes_suppressed) = 0; 473 474 SizeT MC_(blocks_leaked) = 0; 475 SizeT MC_(blocks_indirect) = 0; 476 SizeT MC_(blocks_dubious) = 0; 477 SizeT MC_(blocks_reachable) = 0; 478 SizeT MC_(blocks_suppressed) = 0; 479 480 481 // Determines if a pointer is to a chunk. Returns the chunk number et al 482 // via call-by-reference. 483 static Bool 484 lc_is_a_chunk_ptr(Addr ptr, Int* pch_no, MC_Chunk** pch, LC_Extra** pex) 485 { 486 Int ch_no; 487 MC_Chunk* ch; 488 LC_Extra* ex; 489 490 // Quick filter. 491 if (!VG_(am_is_valid_for_client)(ptr, 1, VKI_PROT_READ)) { 492 return False; 493 } else { 494 ch_no = find_chunk_for(ptr, lc_chunks, lc_n_chunks); 495 tl_assert(ch_no >= -1 && ch_no < lc_n_chunks); 496 497 if (ch_no == -1) { 498 return False; 499 } else { 500 // Ok, we've found a pointer to a chunk. Get the MC_Chunk and its 501 // LC_Extra. 502 ch = lc_chunks[ch_no]; 503 ex = &(lc_extras[ch_no]); 504 505 tl_assert(ptr >= ch->data); 506 tl_assert(ptr < ch->data + ch->szB + (ch->szB==0 ? 1 : 0)); 507 508 if (VG_DEBUG_LEAKCHECK) 509 VG_(printf)("ptr=%#lx -> block %d\n", ptr, ch_no); 510 511 *pch_no = ch_no; 512 *pch = ch; 513 *pex = ex; 514 515 return True; 516 } 517 } 518 } 519 520 // Push a chunk (well, just its index) onto the mark stack. 521 static void lc_push(Int ch_no, MC_Chunk* ch) 522 { 523 if (!lc_extras[ch_no].pending) { 524 if (0) { 525 VG_(printf)("pushing %#lx-%#lx\n", ch->data, ch->data + ch->szB); 526 } 527 lc_markstack_top++; 528 tl_assert(lc_markstack_top < lc_n_chunks); 529 lc_markstack[lc_markstack_top] = ch_no; 530 tl_assert(!lc_extras[ch_no].pending); 531 lc_extras[ch_no].pending = True; 532 } 533 } 534 535 // Return the index of the chunk on the top of the mark stack, or -1 if 536 // there isn't one. 537 static Bool lc_pop(Int* ret) 538 { 539 if (-1 == lc_markstack_top) { 540 return False; 541 } else { 542 tl_assert(0 <= lc_markstack_top && lc_markstack_top < lc_n_chunks); 543 *ret = lc_markstack[lc_markstack_top]; 544 lc_markstack_top--; 545 tl_assert(lc_extras[*ret].pending); 546 lc_extras[*ret].pending = False; 547 return True; 548 } 549 } 550 551 // Partial fix for https://bugs.kde.org/show_bug.cgi?id=280271 552 // Only used in valgrind-variant now. 553 static Bool vv_lc_is_start_pointer(Addr ptr, MC_Chunk* chunk) 554 { 555 // Pointers to the start of the chunk are indeed start-pointers 556 if (ptr == chunk->data) 557 return True; 558 559 // Below are a few heuristics to reduce the number of false positive 560 // "possibly lost" reports on C++ types by treating some interior-pointers 561 // as start-pointers (inspired by the Dr. Memory article at CGO2011). 562 563 // Shortcut: heuristics assume 'ptr' is word-aligned. 564 if (ptr != VG_ROUNDUP(ptr, sizeof(Addr))) 565 return False; 566 567 if (ptr == chunk->data + sizeof(Addr)) { 568 // Pointer to a new[]-allocated buffer? 569 SizeT sz_from_header = *(SizeT*)chunk->data, 570 expected_sz = chunk->szB - sizeof(Addr); 571 if (sz_from_header > 0 && sz_from_header <= expected_sz && 572 expected_sz % sz_from_header == 0) 573 return True; 574 } 575 576 if (ptr == chunk->data + 3*sizeof(Addr)) { 577 // Pointer to std::string internals? 578 SizeT assumed_len = *(SizeT*)chunk->data, 579 assumed_capacity = *((SizeT*)chunk->data + 1); 580 if (assumed_len <= assumed_capacity) { 581 // std::string 582 if (chunk->szB - 3*sizeof(SizeT) == assumed_capacity + 1) 583 return True; 584 585 // std::basic_string<unsigned short> a.k.a. string16 586 if (chunk->szB - 3*sizeof(SizeT) == 2*(assumed_capacity + 1)) 587 return True; 588 589 // std::basic_string<wchar_t> on Linux 590 if (chunk->szB - 3*sizeof(SizeT) == 4*(assumed_capacity + 1)) 591 return True; 592 } 593 } 594 595 if (ptr == chunk->data + 2*sizeof(Addr)) { 596 // Pointer to a nss_ZAlloc-allocated buffer? 597 // It adds a header like this: 'struct { void *ptr; uint32 size };' 598 SizeT sz_from_header = *(UInt*)(chunk->data + sizeof(Addr)), 599 expected_sz = chunk->szB - 2*sizeof(Addr); 600 tl_assert(sizeof(UInt) == 4); 601 if (sz_from_header == expected_sz) 602 return True; 603 } 604 605 return False; 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. 610 static void 611 lc_push_without_clique_if_a_chunk_ptr(Addr ptr, Bool is_prior_definite) 612 { 613 Int ch_no; 614 MC_Chunk* ch; 615 LC_Extra* ex; 616 617 if ( ! lc_is_a_chunk_ptr(ptr, &ch_no, &ch, &ex) ) 618 return; 619 620 // Possibly upgrade the state, ie. one of: 621 // - Unreached --> Possible 622 // - Unreached --> Reachable 623 // - Possible --> Reachable 624 if (vv_lc_is_start_pointer(ptr, ch) && 625 is_prior_definite && ex->state != Reachable) { 626 // 'ptr' points to the start of the block, and the prior node is 627 // definite, which means that this block is definitely reachable. 628 ex->state = Reachable; 629 630 // State has changed to Reachable so (re)scan the block to make 631 // sure any blocks it points to are correctly marked. 632 lc_push(ch_no, ch); 633 634 } else if (ex->state == Unreached) { 635 // Either 'ptr' is a interior-pointer, or the prior node isn't definite, 636 // which means that we can only mark this block as possibly reachable. 637 ex->state = Possible; 638 639 // State has changed to Possible so (re)scan the block to make 640 // sure any blocks it points to are correctly marked. 641 lc_push(ch_no, ch); 642 } 643 } 644 645 static void 646 lc_push_if_a_chunk_ptr_register(Addr ptr) 647 { 648 lc_push_without_clique_if_a_chunk_ptr(ptr, /*is_prior_definite*/True); 649 } 650 651 // If ptr is pointing to a heap-allocated block which hasn't been seen 652 // before, push it onto the mark stack. Clique is the index of the 653 // clique leader. 654 static void 655 lc_push_with_clique_if_a_chunk_ptr(Addr ptr, Int clique) 656 { 657 Int ch_no; 658 MC_Chunk* ch; 659 LC_Extra* ex; 660 661 tl_assert(0 <= clique && clique < lc_n_chunks); 662 663 if ( ! lc_is_a_chunk_ptr(ptr, &ch_no, &ch, &ex) ) 664 return; 665 666 // If it's not Unreached, it's already been handled so ignore it. 667 // If ch_no==clique, it's the clique leader, which means this is a cyclic 668 // structure; again ignore it because it's already been handled. 669 if (ex->state == Unreached && ch_no != clique) { 670 // Note that, unlike reachable blocks, we currently don't distinguish 671 // between start-pointers and interior-pointers here. We probably 672 // should, though. 673 ex->state = IndirectLeak; 674 lc_push(ch_no, ch); 675 676 // Add the block to the clique, and add its size to the 677 // clique-leader's indirect size. Also, if the new block was 678 // itself a clique leader, it isn't any more, so add its 679 // indirect_szB to the new clique leader. 680 if (VG_DEBUG_CLIQUE) { 681 if (ex->indirect_szB > 0) 682 VG_(printf)(" clique %d joining clique %d adding %lu+%lu\n", 683 ch_no, clique, (unsigned long)ch->szB, 684 (unsigned long)ex->indirect_szB); 685 else 686 VG_(printf)(" block %d joining clique %d adding %lu\n", 687 ch_no, clique, (unsigned long)ch->szB); 688 } 689 690 lc_extras[clique].indirect_szB += ch->szB; 691 lc_extras[clique].indirect_szB += ex->indirect_szB; 692 ex->indirect_szB = 0; // Shouldn't matter. 693 } 694 } 695 696 static void 697 lc_push_if_a_chunk_ptr(Addr ptr, Int clique, Bool is_prior_definite) 698 { 699 if (-1 == clique) 700 lc_push_without_clique_if_a_chunk_ptr(ptr, is_prior_definite); 701 else 702 lc_push_with_clique_if_a_chunk_ptr(ptr, clique); 703 } 704 705 706 static VG_MINIMAL_JMP_BUF(memscan_jmpbuf); 707 708 static 709 void scan_all_valid_memory_catcher ( Int sigNo, Addr addr ) 710 { 711 if (0) 712 VG_(printf)("OUCH! sig=%d addr=%#lx\n", sigNo, addr); 713 if (sigNo == VKI_SIGSEGV || sigNo == VKI_SIGBUS) 714 VG_MINIMAL_LONGJMP(memscan_jmpbuf); 715 } 716 717 // Scan a block of memory between [start, start+len). This range may 718 // be bogus, inaccessable, or otherwise strange; we deal with it. For each 719 // valid aligned word we assume it's a pointer to a chunk a push the chunk 720 // onto the mark stack if so. 721 static void 722 lc_scan_memory(Addr start, SizeT len, Bool is_prior_definite, Int clique) 723 { 724 Addr ptr = VG_ROUNDUP(start, sizeof(Addr)); 725 Addr end = VG_ROUNDDN(start+len, sizeof(Addr)); 726 vki_sigset_t sigmask; 727 728 if (VG_DEBUG_LEAKCHECK) 729 VG_(printf)("scan %#lx-%#lx (%lu)\n", start, end, len); 730 731 VG_(sigprocmask)(VKI_SIG_SETMASK, NULL, &sigmask); 732 VG_(set_fault_catcher)(scan_all_valid_memory_catcher); 733 734 // We might be in the middle of a page. Do a cheap check to see if 735 // it's valid; if not, skip onto the next page. 736 if (!VG_(am_is_valid_for_client)(ptr, sizeof(Addr), VKI_PROT_READ)) 737 ptr = VG_PGROUNDUP(ptr+1); // First page is bad - skip it. 738 739 while (ptr < end) { 740 Addr addr; 741 742 // Skip invalid chunks. 743 if ( ! MC_(is_within_valid_secondary)(ptr) ) { 744 ptr = VG_ROUNDUP(ptr+1, SM_SIZE); 745 continue; 746 } 747 748 // Look to see if this page seems reasonable. 749 if ((ptr % VKI_PAGE_SIZE) == 0) { 750 if (!VG_(am_is_valid_for_client)(ptr, sizeof(Addr), VKI_PROT_READ)) { 751 ptr += VKI_PAGE_SIZE; // Bad page - skip it. 752 continue; 753 } 754 } 755 756 if (VG_MINIMAL_SETJMP(memscan_jmpbuf) == 0) { 757 if ( MC_(is_valid_aligned_word)(ptr) ) { 758 lc_scanned_szB += sizeof(Addr); 759 addr = *(Addr *)ptr; 760 // If we get here, the scanned word is in valid memory. Now 761 // let's see if its contents point to a chunk. 762 lc_push_if_a_chunk_ptr(addr, clique, is_prior_definite); 763 } else if (0 && VG_DEBUG_LEAKCHECK) { 764 VG_(printf)("%#lx not valid\n", ptr); 765 } 766 ptr += sizeof(Addr); 767 } else { 768 // We need to restore the signal mask, because we were 769 // longjmped out of a signal handler. 770 VG_(sigprocmask)(VKI_SIG_SETMASK, &sigmask, NULL); 771 772 ptr = VG_PGROUNDUP(ptr+1); // Bad page - skip it. 773 } 774 } 775 776 VG_(sigprocmask)(VKI_SIG_SETMASK, &sigmask, NULL); 777 VG_(set_fault_catcher)(NULL); 778 } 779 780 781 // Process the mark stack until empty. 782 static void lc_process_markstack(Int clique) 783 { 784 Int top = -1; // shut gcc up 785 Bool is_prior_definite; 786 787 while (lc_pop(&top)) { 788 tl_assert(top >= 0 && top < lc_n_chunks); 789 790 // See comment about 'is_prior_definite' at the top to understand this. 791 is_prior_definite = ( Possible != lc_extras[top].state ); 792 793 lc_scan_memory(lc_chunks[top]->data, lc_chunks[top]->szB, 794 is_prior_definite, clique); 795 } 796 } 797 798 static Word cmp_LossRecordKey_LossRecord(const void* key, const void* elem) 799 { 800 LossRecordKey* a = (LossRecordKey*)key; 801 LossRecordKey* b = &(((LossRecord*)elem)->key); 802 803 // Compare on states first because that's fast. 804 if (a->state < b->state) return -1; 805 if (a->state > b->state) return 1; 806 // Ok, the states are equal. Now compare the locations, which is slower. 807 if (VG_(eq_ExeContext)( 808 MC_(clo_leak_resolution), a->allocated_at, b->allocated_at)) 809 return 0; 810 // Different locations. Ordering is arbitrary, just use the ec pointer. 811 if (a->allocated_at < b->allocated_at) return -1; 812 if (a->allocated_at > b->allocated_at) return 1; 813 VG_(tool_panic)("bad LossRecord comparison"); 814 } 815 816 static Int cmp_LossRecords(void* va, void* vb) 817 { 818 LossRecord* lr_a = *(LossRecord**)va; 819 LossRecord* lr_b = *(LossRecord**)vb; 820 SizeT total_szB_a = lr_a->szB + lr_a->indirect_szB; 821 SizeT total_szB_b = lr_b->szB + lr_b->indirect_szB; 822 823 // First compare by sizes. 824 if (total_szB_a < total_szB_b) return -1; 825 if (total_szB_a > total_szB_b) return 1; 826 // If size are equal, compare by states. 827 if (lr_a->key.state < lr_b->key.state) return -1; 828 if (lr_a->key.state > lr_b->key.state) return 1; 829 // If they're still equal here, it doesn't matter that much, but we keep 830 // comparing other things so that regtests are as deterministic as 831 // possible. So: compare num_blocks. 832 if (lr_a->num_blocks < lr_b->num_blocks) return -1; 833 if (lr_a->num_blocks > lr_b->num_blocks) return 1; 834 // Finally, compare ExeContext addresses... older ones are likely to have 835 // lower addresses. 836 if (lr_a->key.allocated_at < lr_b->key.allocated_at) return -1; 837 if (lr_a->key.allocated_at > lr_b->key.allocated_at) return 1; 838 return 0; 839 } 840 841 static void print_results(ThreadId tid, LeakCheckParams lcp) 842 { 843 Int i, n_lossrecords; 844 LossRecord** lr_array; 845 LossRecord* lr; 846 Bool is_suppressed; 847 SizeT old_bytes_leaked = MC_(bytes_leaked); /* to report delta in summary */ 848 SizeT old_bytes_indirect = MC_(bytes_indirect); 849 SizeT old_bytes_dubious = MC_(bytes_dubious); 850 SizeT old_bytes_reachable = MC_(bytes_reachable); 851 SizeT old_bytes_suppressed = MC_(bytes_suppressed); 852 SizeT old_blocks_leaked = MC_(blocks_leaked); 853 SizeT old_blocks_indirect = MC_(blocks_indirect); 854 SizeT old_blocks_dubious = MC_(blocks_dubious); 855 SizeT old_blocks_reachable = MC_(blocks_reachable); 856 SizeT old_blocks_suppressed = MC_(blocks_suppressed); 857 858 if (lr_table == NULL) 859 // Create the lr_table, which holds the loss records. 860 // If the lr_table already exists, it means it contains 861 // loss_records from the previous leak search. The old_* 862 // values in these records are used to implement the 863 // leak check delta mode 864 lr_table = 865 VG_(OSetGen_Create)(offsetof(LossRecord, key), 866 cmp_LossRecordKey_LossRecord, 867 VG_(malloc), "mc.pr.1", 868 VG_(free)); 869 870 871 // Convert the chunks into loss records, merging them where appropriate. 872 for (i = 0; i < lc_n_chunks; i++) { 873 MC_Chunk* ch = lc_chunks[i]; 874 LC_Extra* ex = &(lc_extras)[i]; 875 LossRecord* old_lr; 876 LossRecordKey lrkey; 877 lrkey.state = ex->state; 878 lrkey.allocated_at = ch->where; 879 880 old_lr = VG_(OSetGen_Lookup)(lr_table, &lrkey); 881 if (old_lr) { 882 // We found an existing loss record matching this chunk. Update the 883 // loss record's details in-situ. This is safe because we don't 884 // change the elements used as the OSet key. 885 old_lr->szB += ch->szB; 886 old_lr->indirect_szB += ex->indirect_szB; 887 old_lr->num_blocks++; 888 } else { 889 // No existing loss record matches this chunk. Create a new loss 890 // record, initialise it from the chunk, and insert it into lr_table. 891 lr = VG_(OSetGen_AllocNode)(lr_table, sizeof(LossRecord)); 892 lr->key = lrkey; 893 lr->szB = ch->szB; 894 lr->indirect_szB = ex->indirect_szB; 895 lr->num_blocks = 1; 896 lr->old_szB = 0; 897 lr->old_indirect_szB = 0; 898 lr->old_num_blocks = 0; 899 VG_(OSetGen_Insert)(lr_table, lr); 900 } 901 } 902 n_lossrecords = VG_(OSetGen_Size)(lr_table); 903 904 // Create an array of pointers to the loss records. 905 lr_array = VG_(malloc)("mc.pr.2", n_lossrecords * sizeof(LossRecord*)); 906 i = 0; 907 VG_(OSetGen_ResetIter)(lr_table); 908 while ( (lr = VG_(OSetGen_Next)(lr_table)) ) { 909 lr_array[i++] = lr; 910 } 911 tl_assert(i == n_lossrecords); 912 913 // Sort the array by loss record sizes. 914 VG_(ssort)(lr_array, n_lossrecords, sizeof(LossRecord*), 915 cmp_LossRecords); 916 917 // Zero totals. 918 MC_(blocks_leaked) = MC_(bytes_leaked) = 0; 919 MC_(blocks_indirect) = MC_(bytes_indirect) = 0; 920 MC_(blocks_dubious) = MC_(bytes_dubious) = 0; 921 MC_(blocks_reachable) = MC_(bytes_reachable) = 0; 922 MC_(blocks_suppressed) = MC_(bytes_suppressed) = 0; 923 924 // Print the loss records (in size order) and collect summary stats. 925 for (i = 0; i < n_lossrecords; i++) { 926 Bool count_as_error, print_record, delta_considered; 927 // Rules for printing: 928 // - We don't show suppressed loss records ever (and that's controlled 929 // within the error manager). 930 // - We show non-suppressed loss records that are not "reachable" if 931 // --leak-check=yes. 932 // - We show all non-suppressed loss records if --leak-check=yes and 933 // --show-reachable=yes. 934 // 935 // Nb: here "reachable" means Reachable *or* IndirectLeak; note that 936 // this is different to "still reachable" used elsewhere because it 937 // includes indirectly lost blocks! 938 // 939 lr = lr_array[i]; 940 switch (lcp.deltamode) { 941 case LCD_Any: 942 delta_considered = lr->num_blocks > 0; 943 break; 944 case LCD_Increased: 945 delta_considered 946 = lr_array[i]->szB > lr_array[i]->old_szB 947 || lr_array[i]->indirect_szB > lr_array[i]->old_indirect_szB 948 || lr->num_blocks > lr->old_num_blocks; 949 break; 950 case LCD_Changed: 951 delta_considered = lr_array[i]->szB != lr_array[i]->old_szB 952 || lr_array[i]->indirect_szB != lr_array[i]->old_indirect_szB 953 || lr->num_blocks != lr->old_num_blocks; 954 break; 955 default: 956 tl_assert(0); 957 } 958 959 print_record = lcp.mode == LC_Full && delta_considered && 960 ( lcp.show_reachable || 961 Unreached == lr->key.state || 962 ( lcp.show_possibly_lost && 963 Possible == lr->key.state ) ); 964 // We don't count a leaks as errors with lcp.mode==LC_Summary. 965 // Otherwise you can get high error counts with few or no error 966 // messages, which can be confusing. Also, you could argue that 967 // indirect leaks should be counted as errors, but it seems better to 968 // make the counting criteria similar to the printing criteria. So we 969 // don't count them. 970 count_as_error = lcp.mode == LC_Full && delta_considered && 971 ( Unreached == lr->key.state || 972 Possible == lr->key.state ); 973 if ((Reachable == lr->key.state && !MC_(clo_show_reachable)) || 974 (Possible == lr->key.state && !MC_(clo_show_possibly_lost))) 975 is_suppressed = False; 976 else 977 is_suppressed = MC_(record_leak_error)(tid, i+1, n_lossrecords, lr, 978 print_record, count_as_error); 979 980 if (is_suppressed) { 981 MC_(blocks_suppressed) += lr->num_blocks; 982 MC_(bytes_suppressed) += lr->szB; 983 984 } else if (Unreached == lr->key.state) { 985 MC_(blocks_leaked) += lr->num_blocks; 986 MC_(bytes_leaked) += lr->szB; 987 988 } else if (IndirectLeak == lr->key.state) { 989 MC_(blocks_indirect) += lr->num_blocks; 990 MC_(bytes_indirect) += lr->szB; 991 992 } else if (Possible == lr->key.state) { 993 MC_(blocks_dubious) += lr->num_blocks; 994 MC_(bytes_dubious) += lr->szB; 995 996 } else if (Reachable == lr->key.state) { 997 MC_(blocks_reachable) += lr->num_blocks; 998 MC_(bytes_reachable) += lr->szB; 999 1000 } else { 1001 VG_(tool_panic)("unknown loss mode"); 1002 } 1003 } 1004 1005 for (i = 0; i < n_lossrecords; i++) 1006 { 1007 if (lr->num_blocks == 0) 1008 // remove from lr_table the old loss_records with 0 bytes found 1009 VG_(OSetGen_Remove) (lr_table, &lr_array[i]->key); 1010 else 1011 { 1012 // move the leak sizes to old_* and zero the current sizes 1013 // for next leak search 1014 lr_array[i]->old_szB = lr_array[i]->szB; 1015 lr_array[i]->old_indirect_szB = lr_array[i]->indirect_szB; 1016 lr_array[i]->old_num_blocks = lr_array[i]->num_blocks; 1017 lr_array[i]->szB = 0; 1018 lr_array[i]->indirect_szB = 0; 1019 lr_array[i]->num_blocks = 0; 1020 } 1021 } 1022 VG_(free)(lr_array); 1023 1024 if (VG_(clo_verbosity) > 0 && !VG_(clo_xml)) { 1025 char d_bytes[20]; 1026 char d_blocks[20]; 1027 1028 VG_(umsg)("LEAK SUMMARY:\n"); 1029 VG_(umsg)(" definitely lost: %'lu%s bytes in %'lu%s blocks\n", 1030 MC_(bytes_leaked), 1031 MC_(snprintf_delta) (d_bytes, 20, MC_(bytes_leaked), old_bytes_leaked, lcp.deltamode), 1032 MC_(blocks_leaked), 1033 MC_(snprintf_delta) (d_blocks, 20, MC_(blocks_leaked), old_blocks_leaked, lcp.deltamode)); 1034 VG_(umsg)(" indirectly lost: %'lu%s bytes in %'lu%s blocks\n", 1035 MC_(bytes_indirect), 1036 MC_(snprintf_delta) (d_bytes, 20, MC_(bytes_indirect), old_bytes_indirect, lcp.deltamode), 1037 MC_(blocks_indirect), 1038 MC_(snprintf_delta) (d_blocks, 20, MC_(blocks_indirect), old_blocks_indirect, lcp.deltamode) ); 1039 VG_(umsg)(" possibly lost: %'lu%s bytes in %'lu%s blocks\n", 1040 MC_(bytes_dubious), 1041 MC_(snprintf_delta) (d_bytes, 20, MC_(bytes_dubious), old_bytes_dubious, lcp.deltamode), 1042 MC_(blocks_dubious), 1043 MC_(snprintf_delta) (d_blocks, 20, MC_(blocks_dubious), old_blocks_dubious, lcp.deltamode) ); 1044 VG_(umsg)(" still reachable: %'lu%s bytes in %'lu%s blocks\n", 1045 MC_(bytes_reachable), 1046 MC_(snprintf_delta) (d_bytes, 20, MC_(bytes_reachable), old_bytes_reachable, lcp.deltamode), 1047 MC_(blocks_reachable), 1048 MC_(snprintf_delta) (d_blocks, 20, MC_(blocks_reachable), old_blocks_reachable, lcp.deltamode) ); 1049 VG_(umsg)(" suppressed: %'lu%s bytes in %'lu%s blocks\n", 1050 MC_(bytes_suppressed), 1051 MC_(snprintf_delta) (d_bytes, 20, MC_(bytes_suppressed), old_bytes_suppressed, lcp.deltamode), 1052 MC_(blocks_suppressed), 1053 MC_(snprintf_delta) (d_blocks, 20, MC_(blocks_suppressed), old_blocks_suppressed, lcp.deltamode) ); 1054 if (lcp.mode != LC_Full && 1055 (MC_(blocks_leaked) + MC_(blocks_indirect) + 1056 MC_(blocks_dubious) + MC_(blocks_reachable)) > 0) { 1057 if (lcp.requested_by_monitor_command) 1058 VG_(umsg)("To see details of leaked memory, give 'full' arg to leak_check\n"); 1059 else 1060 VG_(umsg)("Rerun with --leak-check=full to see details " 1061 "of leaked memory\n"); 1062 } 1063 if (lcp.mode == LC_Full && 1064 MC_(blocks_reachable) > 0 && !lcp.show_reachable) 1065 { 1066 VG_(umsg)("Reachable blocks (those to which a pointer " 1067 "was found) are not shown.\n"); 1068 if (lcp.requested_by_monitor_command) 1069 VG_(umsg)("To see them, add 'reachable any' args to leak_check\n"); 1070 else 1071 VG_(umsg)("To see them, rerun with: --leak-check=full " 1072 "--show-reachable=yes\n"); 1073 } 1074 VG_(umsg)("\n"); 1075 } 1076 } 1077 1078 /*------------------------------------------------------------*/ 1079 /*--- Top-level entry point. ---*/ 1080 /*------------------------------------------------------------*/ 1081 1082 void MC_(detect_memory_leaks) ( ThreadId tid, LeakCheckParams lcp) 1083 { 1084 Int i, j; 1085 1086 tl_assert(lcp.mode != LC_Off); 1087 1088 MC_(detect_memory_leaks_last_delta_mode) = lcp.deltamode; 1089 1090 // Get the chunks, stop if there were none. 1091 lc_chunks = find_active_chunks(&lc_n_chunks); 1092 if (lc_n_chunks == 0) { 1093 tl_assert(lc_chunks == NULL); 1094 if (lr_table != NULL) { 1095 // forget the previous recorded LossRecords as next leak search will in any case 1096 // just create new leaks. 1097 // Maybe it would be better to rather call print_result ? 1098 // (at least when leak decrease are requested) 1099 // This will then output all LossRecords with a size decreasing to 0 1100 VG_(OSetGen_Destroy) (lr_table); 1101 } 1102 if (VG_(clo_verbosity) >= 1 && !VG_(clo_xml)) { 1103 VG_(umsg)("All heap blocks were freed -- no leaks are possible\n"); 1104 VG_(umsg)("\n"); 1105 } 1106 return; 1107 } 1108 1109 // Sort the array so blocks are in ascending order in memory. 1110 VG_(ssort)(lc_chunks, lc_n_chunks, sizeof(VgHashNode*), compare_MC_Chunks); 1111 1112 // Sanity check -- make sure they're in order. 1113 for (i = 0; i < lc_n_chunks-1; i++) { 1114 tl_assert( lc_chunks[i]->data <= lc_chunks[i+1]->data); 1115 } 1116 1117 // Sanity check -- make sure they don't overlap. The one exception is that 1118 // we allow a MALLOCLIKE block to sit entirely within a malloc() block. 1119 // This is for bug 100628. If this occurs, we ignore the malloc() block 1120 // for leak-checking purposes. This is a hack and probably should be done 1121 // better, but at least it's consistent with mempools (which are treated 1122 // like this in find_active_chunks). Mempools have a separate VgHashTable 1123 // for mempool chunks, but if custom-allocated blocks are put in a separate 1124 // table from normal heap blocks it makes free-mismatch checking more 1125 // difficult. 1126 // 1127 // If this check fails, it probably means that the application 1128 // has done something stupid with VALGRIND_MALLOCLIKE_BLOCK client 1129 // requests, eg. has made overlapping requests (which are 1130 // nonsensical), or used VALGRIND_MALLOCLIKE_BLOCK for stack locations; 1131 // again nonsensical. 1132 // 1133 for (i = 0; i < lc_n_chunks-1; i++) { 1134 MC_Chunk* ch1 = lc_chunks[i]; 1135 MC_Chunk* ch2 = lc_chunks[i+1]; 1136 1137 Addr start1 = ch1->data; 1138 Addr start2 = ch2->data; 1139 Addr end1 = ch1->data + ch1->szB - 1; 1140 Addr end2 = ch2->data + ch2->szB - 1; 1141 Bool isCustom1 = ch1->allockind == MC_AllocCustom; 1142 Bool isCustom2 = ch2->allockind == MC_AllocCustom; 1143 1144 if (end1 < start2) { 1145 // Normal case - no overlap. 1146 1147 // We used to allow exact duplicates, I'm not sure why. --njn 1148 //} else if (start1 == start2 && end1 == end2) { 1149 // Degenerate case: exact duplicates. 1150 1151 } else if (start1 >= start2 && end1 <= end2 && isCustom1 && !isCustom2) { 1152 // Block i is MALLOCLIKE and entirely within block i+1. 1153 // Remove block i+1. 1154 for (j = i+1; j < lc_n_chunks-1; j++) { 1155 lc_chunks[j] = lc_chunks[j+1]; 1156 } 1157 lc_n_chunks--; 1158 1159 } else if (start2 >= start1 && end2 <= end1 && isCustom2 && !isCustom1) { 1160 // Block i+1 is MALLOCLIKE and entirely within block i. 1161 // Remove block i. 1162 for (j = i; j < lc_n_chunks-1; j++) { 1163 lc_chunks[j] = lc_chunks[j+1]; 1164 } 1165 lc_n_chunks--; 1166 1167 } else { 1168 VG_(umsg)("Block 0x%lx..0x%lx overlaps with block 0x%lx..0x%lx", 1169 start1, end1, start2, end2); 1170 VG_(umsg)("This is usually caused by using VALGRIND_MALLOCLIKE_BLOCK"); 1171 VG_(umsg)("in an inappropriate way."); 1172 tl_assert (0); 1173 } 1174 } 1175 1176 // Initialise lc_extras. 1177 lc_extras = VG_(malloc)( "mc.dml.2", lc_n_chunks * sizeof(LC_Extra) ); 1178 for (i = 0; i < lc_n_chunks; i++) { 1179 lc_extras[i].state = Unreached; 1180 lc_extras[i].pending = False; 1181 lc_extras[i].indirect_szB = 0; 1182 } 1183 1184 // Initialise lc_markstack. 1185 lc_markstack = VG_(malloc)( "mc.dml.2", lc_n_chunks * sizeof(Int) ); 1186 for (i = 0; i < lc_n_chunks; i++) { 1187 lc_markstack[i] = -1; 1188 } 1189 lc_markstack_top = -1; 1190 1191 // Verbosity. 1192 if (VG_(clo_verbosity) > 1 && !VG_(clo_xml)) { 1193 VG_(umsg)( "Searching for pointers to %'d not-freed blocks\n", 1194 lc_n_chunks ); 1195 } 1196 1197 // Scan the memory root-set, pushing onto the mark stack any blocks 1198 // pointed to. 1199 { 1200 Int n_seg_starts; 1201 Addr* seg_starts = VG_(get_segment_starts)( &n_seg_starts ); 1202 1203 tl_assert(seg_starts && n_seg_starts > 0); 1204 1205 lc_scanned_szB = 0; 1206 1207 // VG_(am_show_nsegments)( 0, "leakcheck"); 1208 for (i = 0; i < n_seg_starts; i++) { 1209 SizeT seg_size; 1210 NSegment const* seg = VG_(am_find_nsegment)( seg_starts[i] ); 1211 tl_assert(seg); 1212 1213 if (seg->kind != SkFileC && seg->kind != SkAnonC) continue; 1214 if (!(seg->hasR && seg->hasW)) continue; 1215 if (seg->isCH) continue; 1216 1217 // Don't poke around in device segments as this may cause 1218 // hangs. Exclude /dev/zero just in case someone allocated 1219 // memory by explicitly mapping /dev/zero. 1220 if (seg->kind == SkFileC 1221 && (VKI_S_ISCHR(seg->mode) || VKI_S_ISBLK(seg->mode))) { 1222 HChar* dev_name = VG_(am_get_filename)( (NSegment*)seg ); 1223 if (dev_name && 0 == VG_(strcmp)(dev_name, "/dev/zero")) { 1224 // Don't skip /dev/zero. 1225 } else { 1226 // Skip this device mapping. 1227 continue; 1228 } 1229 } 1230 1231 if (0) 1232 VG_(printf)("ACCEPT %2d %#lx %#lx\n", i, seg->start, seg->end); 1233 1234 // Scan the segment. We use -1 for the clique number, because this 1235 // is a root-set. 1236 seg_size = seg->end - seg->start + 1; 1237 if (VG_(clo_verbosity) > 2) { 1238 VG_(message)(Vg_DebugMsg, 1239 " Scanning root segment: %#lx..%#lx (%lu)\n", 1240 seg->start, seg->end, seg_size); 1241 } 1242 lc_scan_memory(seg->start, seg_size, /*is_prior_definite*/True, -1); 1243 } 1244 } 1245 1246 // Scan GP registers for chunk pointers. 1247 VG_(apply_to_GP_regs)(lc_push_if_a_chunk_ptr_register); 1248 1249 // Process the pushed blocks. After this, every block that is reachable 1250 // from the root-set has been traced. 1251 lc_process_markstack(/*clique*/-1); 1252 1253 if (VG_(clo_verbosity) > 1 && !VG_(clo_xml)) { 1254 VG_(umsg)("Checked %'lu bytes\n", lc_scanned_szB); 1255 VG_(umsg)( "\n" ); 1256 } 1257 1258 // Trace all the leaked blocks to determine which are directly leaked and 1259 // which are indirectly leaked. For each Unreached block, push it onto 1260 // the mark stack, and find all the as-yet-Unreached blocks reachable 1261 // from it. These form a clique and are marked IndirectLeak, and their 1262 // size is added to the clique leader's indirect size. If one of the 1263 // found blocks was itself a clique leader (from a previous clique), then 1264 // the cliques are merged. 1265 for (i = 0; i < lc_n_chunks; i++) { 1266 MC_Chunk* ch = lc_chunks[i]; 1267 LC_Extra* ex = &(lc_extras[i]); 1268 1269 if (VG_DEBUG_CLIQUE) 1270 VG_(printf)("cliques: %d at %#lx -> Loss state %d\n", 1271 i, ch->data, ex->state); 1272 1273 tl_assert(lc_markstack_top == -1); 1274 1275 if (ex->state == Unreached) { 1276 if (VG_DEBUG_CLIQUE) 1277 VG_(printf)("%d: gathering clique %#lx\n", i, ch->data); 1278 1279 // Push this Unreached block onto the stack and process it. 1280 lc_push(i, ch); 1281 lc_process_markstack(i); 1282 1283 tl_assert(lc_markstack_top == -1); 1284 tl_assert(ex->state == Unreached); 1285 } 1286 } 1287 1288 print_results( tid, lcp); 1289 1290 VG_(free) ( lc_chunks ); 1291 VG_(free) ( lc_extras ); 1292 VG_(free) ( lc_markstack ); 1293 } 1294 1295 /*--------------------------------------------------------------------*/ 1296 /*--- end ---*/ 1297 /*--------------------------------------------------------------------*/ 1298