18cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 28cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd/*--------------------------------------------------------------------*/ 38cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd/*--- The leak checker. mc_leakcheck.c ---*/ 48cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd/*--------------------------------------------------------------------*/ 58cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 68cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd/* 78cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd This file is part of MemCheck, a heavyweight Valgrind tool for 88cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd detecting memory errors. 98cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 108cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd Copyright (C) 2000-2013 Julian Seward 118cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd jseward@acm.org 128cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 138cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd This program is free software; you can redistribute it and/or 148cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd modify it under the terms of the GNU General Public License as 158cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd published by the Free Software Foundation; either version 2 of the 168cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd License, or (at your option) any later version. 178cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 188cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd This program is distributed in the hope that it will be useful, but 198cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd WITHOUT ANY WARRANTY; without even the implied warranty of 208cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 218cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd General Public License for more details. 228cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 238cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd You should have received a copy of the GNU General Public License 248cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd along with this program; if not, write to the Free Software 258cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 268cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 02111-1307, USA. 278cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 288cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd The GNU General Public License is contained in the file COPYING. 298cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd*/ 308cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 318cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#include "pub_tool_basics.h" 328cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#include "pub_tool_vki.h" 338cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#include "pub_tool_aspacehl.h" 348cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#include "pub_tool_aspacemgr.h" 358cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#include "pub_tool_execontext.h" 368cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#include "pub_tool_hashtable.h" 378cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#include "pub_tool_libcbase.h" 388cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#include "pub_tool_libcassert.h" 398cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#include "pub_tool_libcprint.h" 408cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#include "pub_tool_libcsignal.h" 418cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#include "pub_tool_machine.h" 428cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#include "pub_tool_mallocfree.h" 438cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#include "pub_tool_options.h" 448cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#include "pub_tool_oset.h" 458cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#include "pub_tool_poolalloc.h" 468cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#include "pub_tool_signals.h" // Needed for mc_include.h 478cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#include "pub_tool_libcsetjmp.h" // setjmp facilities 488cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#include "pub_tool_tooliface.h" // Needed for mc_include.h 498cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 508cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#include "mc_include.h" 518cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 528cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd/*------------------------------------------------------------*/ 538cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd/*--- An overview of leak checking. ---*/ 548cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd/*------------------------------------------------------------*/ 558cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 568cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// Leak-checking is a directed-graph traversal problem. The graph has 578cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// two kinds of nodes: 588cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// - root-set nodes: 598cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// - GP registers of all threads; 608cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// - valid, aligned, pointer-sized data words in valid client memory, 618cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// including stacks, but excluding words within client heap-allocated 628cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// blocks (they are excluded so that later on we can differentiate 638cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// between heap blocks that are indirectly leaked vs. directly leaked). 648cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// - heap-allocated blocks. A block is a mempool chunk or a malloc chunk 658cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// that doesn't contain a mempool chunk. Nb: the terms "blocks" and 668cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// "chunks" are used interchangeably below. 678cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// 688cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// There are two kinds of edges: 698cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// - start-pointers, i.e. pointers to the start of a block; 708cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// - interior-pointers, i.e. pointers to the interior of a block. 718cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// 728cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// We use "pointers" rather than "edges" below. 738cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// 748cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// Root set nodes only point to blocks. Blocks only point to blocks; 758cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// a block can point to itself. 768cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// 778cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// The aim is to traverse the graph and determine the status of each block. 788cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// 798cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// There are 9 distinct cases. See memcheck/docs/mc-manual.xml for details. 808cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// Presenting all nine categories to the user is probably too much. 818cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// Currently we do this: 828cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// - definitely lost: case 3 838cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// - indirectly lost: case 4, 9 848cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// - possibly lost: cases 5..8 858cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// - still reachable: cases 1, 2 868cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// 878cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// It's far from clear that this is the best possible categorisation; it's 888cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// accreted over time without any central guiding principle. 898cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 908cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd/*------------------------------------------------------------*/ 918cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd/*--- XXX: Thoughts for improvement. ---*/ 928cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd/*------------------------------------------------------------*/ 938cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 948cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// From the user's point of view: 958cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// - If they aren't using interior-pointers, they just have to fix the 968cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// directly lost blocks, and the indirectly lost ones will be fixed as 978cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// part of that. Any possibly lost blocks will just be due to random 988cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// pointer garbage and can be ignored. 998cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// 1008cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// - If they are using interior-pointers, the fact that they currently are not 1018cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// being told which ones might be directly lost vs. indirectly lost makes 1028cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// it hard to know where to begin. 1038cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// 1048cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// All this makes me wonder if new option is warranted: 1058cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// --follow-interior-pointers. By default it would be off, the leak checker 1068cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// wouldn't follow interior-pointers and there would only be 3 categories: 1078cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// R, DL, IL. 1088cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// 1098cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// If turned on, then it would show 7 categories (R, DL, IL, DR/DL, IR/IL, 1108cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// IR/IL/DL, IL/DL). That output is harder to understand but it's your own 1118cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// damn fault for using interior-pointers... 1128cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// 1138cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// ---- 1148cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// 1158cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// Also, why are two blank lines printed between each loss record? 1168cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// [bug 197930] 1178cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// 1188cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// ---- 1198cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// 1208cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// Also, --show-reachable is a bad name because it also turns on the showing 1218cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// of indirectly leaked blocks(!) It would be better named --show-all or 1228cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// --show-all-heap-blocks, because that's the end result. 1238cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// We now have the option --show-leak-kinds=... which allows to specify =all. 1248cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// 1258cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// ---- 1268cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// 1278cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// Also, the VALGRIND_LEAK_CHECK and VALGRIND_QUICK_LEAK_CHECK aren't great 1288cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// names. VALGRIND_FULL_LEAK_CHECK and VALGRIND_SUMMARY_LEAK_CHECK would be 1298cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// better. 1308cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// 1318cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// ---- 1328cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// 1338cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// Also, VALGRIND_COUNT_LEAKS and VALGRIND_COUNT_LEAK_BLOCKS aren't great as 1348cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// they combine direct leaks and indirect leaks into one. New, more precise 1358cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// ones (they'll need new names) would be good. If more categories are 1368cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// used, as per the --follow-interior-pointers option, they should be 1378cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// updated accordingly. And they should use a struct to return the values. 1388cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// 1398cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// ---- 1408cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// 1418cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// Also, for this case: 1428cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// 1438cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// (4) p4 BBB ---> AAA 1448cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// 1458cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// BBB is definitely directly lost. AAA is definitely indirectly lost. 1468cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// Here's the relevant loss records printed for a full check (each block is 1478cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// 16 bytes): 1488cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// 1498cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// ==20397== 16 bytes in 1 blocks are indirectly lost in loss record 9 of 15 1508cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// ==20397== at 0x4C2694E: malloc (vg_replace_malloc.c:177) 1518cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// ==20397== by 0x400521: mk (leak-cases.c:49) 1528cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// ==20397== by 0x400578: main (leak-cases.c:72) 1538cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// 1548cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// ==20397== 32 (16 direct, 16 indirect) bytes in 1 blocks are definitely 1558cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// lost in loss record 14 of 15 1568cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// ==20397== at 0x4C2694E: malloc (vg_replace_malloc.c:177) 157// ==20397== by 0x400521: mk (leak-cases.c:49) 158// ==20397== by 0x400580: main (leak-cases.c:72) 159// 160// The first one is fine -- it describes AAA. 161// 162// The second one is for BBB. It's correct in that 16 bytes in 1 block are 163// directly lost. It's also correct that 16 are indirectly lost as a result, 164// but it means that AAA is being counted twice in the loss records. (It's 165// not, thankfully, counted twice in the summary counts). Argh. 166// 167// This would be less confusing for the second one: 168// 169// ==20397== 16 bytes in 1 blocks are definitely lost in loss record 14 170// of 15 (and 16 bytes in 1 block are indirectly lost as a result; they 171// are mentioned elsewhere (if --show-reachable=yes or indirect is given 172// in --show-leak-kinds=... !)) 173// ==20397== at 0x4C2694E: malloc (vg_replace_malloc.c:177) 174// ==20397== by 0x400521: mk (leak-cases.c:49) 175// ==20397== by 0x400580: main (leak-cases.c:72) 176// 177// But ideally we'd present the loss record for the directly lost block and 178// then the resultant indirectly lost blocks and make it clear the 179// dependence. Double argh. 180 181/*------------------------------------------------------------*/ 182/*--- The actual algorithm. ---*/ 183/*------------------------------------------------------------*/ 184 185// - Find all the blocks (a.k.a. chunks) to check. Mempool chunks require 186// some special treatment because they can be within malloc'd blocks. 187// - Scan every word in the root set (GP registers and valid 188// non-heap memory words). 189// - First, we skip if it doesn't point to valid memory. 190// - Then, we see if it points to the start or interior of a block. If 191// so, we push the block onto the mark stack and mark it as having been 192// reached. 193// - Then, we process the mark stack, repeating the scanning for each block; 194// this can push more blocks onto the mark stack. We repeat until the 195// mark stack is empty. Each block is marked as definitely or possibly 196// reachable, depending on whether interior-pointers were required to 197// reach it. 198// - At this point we know for every block if it's reachable or not. 199// - We then push each unreached block onto the mark stack, using the block 200// number as the "clique" number. 201// - We process the mark stack again, this time grouping blocks into cliques 202// in order to facilitate the directly/indirectly lost categorisation. 203// - We group blocks by their ExeContexts and categorisation, and print them 204// if --leak-check=full. We also print summary numbers. 205// 206// A note on "cliques": 207// - A directly lost block is one with no pointers to it. An indirectly 208// lost block is one that is pointed to by a directly or indirectly lost 209// block. 210// - Each directly lost block has zero or more indirectly lost blocks 211// hanging off it. All these blocks together form a "clique". The 212// directly lost block is called the "clique leader". The clique number 213// is the number (in lc_chunks[]) of the clique leader. 214// - Actually, a directly lost block may be pointed to if it's part of a 215// cycle. In that case, there may be more than one choice for the clique 216// leader, and the choice is arbitrary. Eg. if you have A-->B and B-->A 217// either A or B could be the clique leader. 218// - Cliques cannot overlap, and will be truncated to avoid this. Eg. if we 219// have A-->C and B-->C, the two cliques will be {A,C} and {B}, or {A} and 220// {B,C} (again the choice is arbitrary). This is because we don't want 221// to count a block as indirectly lost more than once. 222// 223// A note on 'is_prior_definite': 224// - This is a boolean used in various places that indicates if the chain 225// up to the prior node (prior to the one being considered) is definite. 226// - In the clique == -1 case: 227// - if True it means that the prior node is a root-set node, or that the 228// prior node is a block which is reachable from the root-set via 229// start-pointers. 230// - if False it means that the prior node is a block that is only 231// reachable from the root-set via a path including at least one 232// interior-pointer. 233// - In the clique != -1 case, currently it's always True because we treat 234// start-pointers and interior-pointers the same for direct/indirect leak 235// checking. If we added a PossibleIndirectLeak state then this would 236// change. 237 238 239// Define to debug the memory-leak-detector. 240#define VG_DEBUG_LEAKCHECK 0 241#define VG_DEBUG_CLIQUE 0 242 243 244/*------------------------------------------------------------*/ 245/*--- Getting the initial chunks, and searching them. ---*/ 246/*------------------------------------------------------------*/ 247 248// Compare the MC_Chunks by 'data' (i.e. the address of the block). 249static Int compare_MC_Chunks(const void* n1, const void* n2) 250{ 251 const MC_Chunk* mc1 = *(const MC_Chunk *const *)n1; 252 const MC_Chunk* mc2 = *(const MC_Chunk *const *)n2; 253 if (mc1->data < mc2->data) return -1; 254 if (mc1->data > mc2->data) return 1; 255 return 0; 256} 257 258#if VG_DEBUG_LEAKCHECK 259// Used to sanity-check the fast binary-search mechanism. 260static 261Int find_chunk_for_OLD ( Addr ptr, 262 MC_Chunk** chunks, 263 Int n_chunks ) 264 265{ 266 Int i; 267 Addr a_lo, a_hi; 268 PROF_EVENT(70, "find_chunk_for_OLD"); 269 for (i = 0; i < n_chunks; i++) { 270 PROF_EVENT(71, "find_chunk_for_OLD(loop)"); 271 a_lo = chunks[i]->data; 272 a_hi = ((Addr)chunks[i]->data) + chunks[i]->szB; 273 if (a_lo <= ptr && ptr < a_hi) 274 return i; 275 } 276 return -1; 277} 278#endif 279 280// Find the i such that ptr points at or inside the block described by 281// chunks[i]. Return -1 if none found. This assumes that chunks[] 282// has been sorted on the 'data' field. 283static 284Int find_chunk_for ( Addr ptr, 285 MC_Chunk** chunks, 286 Int n_chunks ) 287{ 288 Addr a_mid_lo, a_mid_hi; 289 Int lo, mid, hi, retVal; 290 // VG_(printf)("find chunk for %p = ", ptr); 291 retVal = -1; 292 lo = 0; 293 hi = n_chunks-1; 294 while (True) { 295 // Invariant: current unsearched space is from lo to hi, inclusive. 296 if (lo > hi) break; // not found 297 298 mid = (lo + hi) / 2; 299 a_mid_lo = chunks[mid]->data; 300 a_mid_hi = chunks[mid]->data + chunks[mid]->szB; 301 // Extent of block 'mid' is [a_mid_lo .. a_mid_hi). 302 // Special-case zero-sized blocks - treat them as if they had 303 // size 1. Not doing so causes them to not cover any address 304 // range at all and so will never be identified as the target of 305 // any pointer, which causes them to be incorrectly reported as 306 // definitely leaked. 307 if (chunks[mid]->szB == 0) 308 a_mid_hi++; 309 310 if (ptr < a_mid_lo) { 311 hi = mid-1; 312 continue; 313 } 314 if (ptr >= a_mid_hi) { 315 lo = mid+1; 316 continue; 317 } 318 tl_assert(ptr >= a_mid_lo && ptr < a_mid_hi); 319 retVal = mid; 320 break; 321 } 322 323# if VG_DEBUG_LEAKCHECK 324 tl_assert(retVal == find_chunk_for_OLD ( ptr, chunks, n_chunks )); 325# endif 326 // VG_(printf)("%d\n", retVal); 327 return retVal; 328} 329 330 331static MC_Chunk** 332find_active_chunks(Int* pn_chunks) 333{ 334 // Our goal is to construct a set of chunks that includes every 335 // mempool chunk, and every malloc region that *doesn't* contain a 336 // mempool chunk. 337 MC_Mempool *mp; 338 MC_Chunk **mallocs, **chunks, *mc; 339 UInt n_mallocs, n_chunks, m, s; 340 Bool *malloc_chunk_holds_a_pool_chunk; 341 342 // First we collect all the malloc chunks into an array and sort it. 343 // We do this because we want to query the chunks by interior 344 // pointers, requiring binary search. 345 mallocs = (MC_Chunk**) VG_(HT_to_array)( MC_(malloc_list), &n_mallocs ); 346 if (n_mallocs == 0) { 347 tl_assert(mallocs == NULL); 348 *pn_chunks = 0; 349 return NULL; 350 } 351 VG_(ssort)(mallocs, n_mallocs, sizeof(VgHashNode*), compare_MC_Chunks); 352 353 // Then we build an array containing a Bool for each malloc chunk, 354 // indicating whether it contains any mempools. 355 malloc_chunk_holds_a_pool_chunk = VG_(calloc)( "mc.fas.1", 356 n_mallocs, sizeof(Bool) ); 357 n_chunks = n_mallocs; 358 359 // Then we loop over the mempool tables. For each chunk in each 360 // pool, we set the entry in the Bool array corresponding to the 361 // malloc chunk containing the mempool chunk. 362 VG_(HT_ResetIter)(MC_(mempool_list)); 363 while ( (mp = VG_(HT_Next)(MC_(mempool_list))) ) { 364 VG_(HT_ResetIter)(mp->chunks); 365 while ( (mc = VG_(HT_Next)(mp->chunks)) ) { 366 367 // We'll need to record this chunk. 368 n_chunks++; 369 370 // Possibly invalidate the malloc holding the beginning of this chunk. 371 m = find_chunk_for(mc->data, mallocs, n_mallocs); 372 if (m != -1 && malloc_chunk_holds_a_pool_chunk[m] == False) { 373 tl_assert(n_chunks > 0); 374 n_chunks--; 375 malloc_chunk_holds_a_pool_chunk[m] = True; 376 } 377 378 // Possibly invalidate the malloc holding the end of this chunk. 379 if (mc->szB > 1) { 380 m = find_chunk_for(mc->data + (mc->szB - 1), mallocs, n_mallocs); 381 if (m != -1 && malloc_chunk_holds_a_pool_chunk[m] == False) { 382 tl_assert(n_chunks > 0); 383 n_chunks--; 384 malloc_chunk_holds_a_pool_chunk[m] = True; 385 } 386 } 387 } 388 } 389 tl_assert(n_chunks > 0); 390 391 // Create final chunk array. 392 chunks = VG_(malloc)("mc.fas.2", sizeof(VgHashNode*) * (n_chunks)); 393 s = 0; 394 395 // Copy the mempool chunks and the non-marked malloc chunks into a 396 // combined array of chunks. 397 VG_(HT_ResetIter)(MC_(mempool_list)); 398 while ( (mp = VG_(HT_Next)(MC_(mempool_list))) ) { 399 VG_(HT_ResetIter)(mp->chunks); 400 while ( (mc = VG_(HT_Next)(mp->chunks)) ) { 401 tl_assert(s < n_chunks); 402 chunks[s++] = mc; 403 } 404 } 405 for (m = 0; m < n_mallocs; ++m) { 406 if (!malloc_chunk_holds_a_pool_chunk[m]) { 407 tl_assert(s < n_chunks); 408 chunks[s++] = mallocs[m]; 409 } 410 } 411 tl_assert(s == n_chunks); 412 413 // Free temporaries. 414 VG_(free)(mallocs); 415 VG_(free)(malloc_chunk_holds_a_pool_chunk); 416 417 *pn_chunks = n_chunks; 418 419 return chunks; 420} 421 422/*------------------------------------------------------------*/ 423/*--- The leak detector proper. ---*/ 424/*------------------------------------------------------------*/ 425 426// Holds extra info about each block during leak checking. 427typedef 428 struct { 429 UInt state:2; // Reachedness. 430 UInt pending:1; // Scan pending. 431 UInt heuristic: (sizeof(UInt)*8)-3; 432 // Heuristic with which this block was considered reachable. 433 // LchNone if state != Reachable or no heuristic needed to 434 // consider it reachable. 435 436 union { 437 SizeT indirect_szB; 438 // If Unreached, how many bytes are unreachable from here. 439 SizeT clique; 440 // if IndirectLeak, clique leader to which it belongs. 441 } IorC; 442 } 443 LC_Extra; 444 445// An array holding pointers to every chunk we're checking. Sorted by address. 446// lc_chunks is initialised during leak search. It is kept after leak search 447// to support printing the list of blocks belonging to a loss record. 448// lc_chunk array can only be used validly till the next "free" operation 449// (as a free operation potentially destroys one or more chunks). 450// To detect lc_chunk is valid, we store the nr of frees operations done 451// when lc_chunk was build : lc_chunks (and lc_extras) stays valid as 452// long as no free operations has been done since lc_chunks building. 453static MC_Chunk** lc_chunks; 454// How many chunks we're dealing with. 455static Int lc_n_chunks; 456static SizeT lc_chunks_n_frees_marker; 457// This has the same number of entries as lc_chunks, and each entry 458// in lc_chunks corresponds with the entry here (ie. lc_chunks[i] and 459// lc_extras[i] describe the same block). 460static LC_Extra* lc_extras; 461 462// chunks will be converted and merged in loss record, maintained in lr_table 463// lr_table elements are kept from one leak_search to another to implement 464// the "print new/changed leaks" client request 465static OSet* lr_table; 466// Array of sorted loss record (produced during last leak search). 467static LossRecord** lr_array; 468 469// Value of the heuristics parameter used in the current (or last) leak check. 470static UInt detect_memory_leaks_last_heuristics; 471 472// DeltaMode used the last time we called detect_memory_leaks. 473// The recorded leak errors are output using a logic based on this delta_mode. 474// The below avoids replicating the delta_mode in each LossRecord. 475LeakCheckDeltaMode MC_(detect_memory_leaks_last_delta_mode); 476 477// Each leak search run increments the below generation counter. 478// A used suppression during a leak search will contain this 479// generation number. 480UInt MC_(leak_search_gen); 481 482// Records chunks that are currently being processed. Each element in the 483// stack is an index into lc_chunks and lc_extras. Its size is 484// 'lc_n_chunks' because in the worst case that's how many chunks could be 485// pushed onto it (actually I think the maximum is lc_n_chunks-1 but let's 486// be conservative). 487static Int* lc_markstack; 488// The index of the top element of the stack; -1 if the stack is empty, 0 if 489// the stack has one element, 1 if it has two, etc. 490static Int lc_markstack_top; 491 492// Keeps track of how many bytes of memory we've scanned, for printing. 493// (Nb: We don't keep track of how many register bytes we've scanned.) 494static SizeT lc_scanned_szB; 495// Keeps track of how many bytes we have not scanned due to read errors that 496// caused a signal such as SIGSEGV. 497static SizeT lc_sig_skipped_szB; 498 499 500SizeT MC_(bytes_leaked) = 0; 501SizeT MC_(bytes_indirect) = 0; 502SizeT MC_(bytes_dubious) = 0; 503SizeT MC_(bytes_reachable) = 0; 504SizeT MC_(bytes_suppressed) = 0; 505 506SizeT MC_(blocks_leaked) = 0; 507SizeT MC_(blocks_indirect) = 0; 508SizeT MC_(blocks_dubious) = 0; 509SizeT MC_(blocks_reachable) = 0; 510SizeT MC_(blocks_suppressed) = 0; 511 512// Subset of MC_(bytes_reachable) and MC_(blocks_reachable) which 513// are considered reachable due to the corresponding heuristic. 514static SizeT MC_(bytes_heuristically_reachable)[N_LEAK_CHECK_HEURISTICS] 515 = {0,0,0,0}; 516static SizeT MC_(blocks_heuristically_reachable)[N_LEAK_CHECK_HEURISTICS] 517 = {0,0,0,0}; 518 519// Determines if a pointer is to a chunk. Returns the chunk number et al 520// via call-by-reference. 521static Bool 522lc_is_a_chunk_ptr(Addr ptr, Int* pch_no, MC_Chunk** pch, LC_Extra** pex) 523{ 524 Int ch_no; 525 MC_Chunk* ch; 526 LC_Extra* ex; 527 528 // Quick filter. Note: implemented with am, not with get_vabits2 529 // as ptr might be random data pointing anywhere. On 64 bit 530 // platforms, getting va bits for random data can be quite costly 531 // due to the secondary map. 532 if (!VG_(am_is_valid_for_client)(ptr, 1, VKI_PROT_READ)) { 533 return False; 534 } else { 535 ch_no = find_chunk_for(ptr, lc_chunks, lc_n_chunks); 536 tl_assert(ch_no >= -1 && ch_no < lc_n_chunks); 537 538 if (ch_no == -1) { 539 return False; 540 } else { 541 // Ok, we've found a pointer to a chunk. Get the MC_Chunk and its 542 // LC_Extra. 543 ch = lc_chunks[ch_no]; 544 ex = &(lc_extras[ch_no]); 545 546 tl_assert(ptr >= ch->data); 547 tl_assert(ptr < ch->data + ch->szB + (ch->szB==0 ? 1 : 0)); 548 549 if (VG_DEBUG_LEAKCHECK) 550 VG_(printf)("ptr=%#lx -> block %d\n", ptr, ch_no); 551 552 *pch_no = ch_no; 553 *pch = ch; 554 *pex = ex; 555 556 return True; 557 } 558 } 559} 560 561// Push a chunk (well, just its index) onto the mark stack. 562static void lc_push(Int ch_no, MC_Chunk* ch) 563{ 564 if (!lc_extras[ch_no].pending) { 565 if (0) { 566 VG_(printf)("pushing %#lx-%#lx\n", ch->data, ch->data + ch->szB); 567 } 568 lc_markstack_top++; 569 tl_assert(lc_markstack_top < lc_n_chunks); 570 lc_markstack[lc_markstack_top] = ch_no; 571 tl_assert(!lc_extras[ch_no].pending); 572 lc_extras[ch_no].pending = True; 573 } 574} 575 576// Return the index of the chunk on the top of the mark stack, or -1 if 577// there isn't one. 578static Bool lc_pop(Int* ret) 579{ 580 if (-1 == lc_markstack_top) { 581 return False; 582 } else { 583 tl_assert(0 <= lc_markstack_top && lc_markstack_top < lc_n_chunks); 584 *ret = lc_markstack[lc_markstack_top]; 585 lc_markstack_top--; 586 tl_assert(lc_extras[*ret].pending); 587 lc_extras[*ret].pending = False; 588 return True; 589 } 590} 591 592static const HChar* pp_heuristic(LeakCheckHeuristic h) 593{ 594 switch(h) { 595 case LchNone: return "none"; 596 case LchStdString: return "stdstring"; 597 case LchNewArray: return "newarray"; 598 case LchMultipleInheritance: return "multipleinheritance"; 599 default: return "???invalid heuristic???"; 600 } 601} 602 603// True if ptr looks like the address of a vtable, i.e. if ptr 604// points to an array of pointers to functions. 605// It is assumed the only caller of this function is heuristic_reachedness 606// which must check that ptr is aligned and above page 0. 607// Checking that ptr is above page 0 is an optimisation : it is assumed 608// that no vtable is located in the page 0. So, all small integer values 609// encountered during the scan will not incur the cost of calling this 610// function. 611static Bool aligned_ptr_above_page0_is_vtable_addr(Addr ptr) 612{ 613 // ??? If performance problem: 614 // ??? maybe implement a cache (array indexed by ptr % primenr) 615 // ??? of "I am a vtable ptr" ??? 616 617 // ??? Maybe the debug info could (efficiently?) be used to detect vtables ? 618 619 // We consider ptr as a vtable ptr if it points to a table 620 // where we find only NULL pointers or pointers pointing at an 621 // executable region. We must find at least 2 non NULL pointers 622 // before considering ptr as a vtable pointer. 623 // We scan a maximum of VTABLE_MAX_CHECK words for these 2 non NULL 624 // pointers. 625#define VTABLE_MAX_CHECK 20 626 627 NSegment const *seg; 628 UInt nr_fn_ptrs = 0; 629 Addr scan; 630 Addr scan_max; 631 632 // First verify ptr points inside a client mapped file section. 633 // ??? is a vtable always in a file mapped readable section ? 634 seg = VG_(am_find_nsegment) (ptr); 635 if (seg == NULL 636 || seg->kind != SkFileC 637 || !seg->hasR) 638 return False; 639 640 // Check potential function pointers, up to a maximum of VTABLE_MAX_CHECK. 641 scan_max = ptr + VTABLE_MAX_CHECK*sizeof(Addr); 642 // If ptr is near the end of seg, avoid scan_max exceeding the end of seg: 643 if (scan_max > seg->end - sizeof(Addr)) 644 scan_max = seg->end - sizeof(Addr); 645 for (scan = ptr; scan <= scan_max; scan+=sizeof(Addr)) { 646 Addr pot_fn = *((Addr *)scan); 647 if (pot_fn == 0) 648 continue; // NULL fn pointer. Seems it can happen in vtable. 649 seg = VG_(am_find_nsegment) (pot_fn); 650#if defined(VGA_ppc64) 651 // ppc64 use a thunk table. So, we have one more level of indirection 652 // to follow. 653 if (seg == NULL 654 || seg->kind != SkFileC 655 || !seg->hasR 656 || !seg->hasW) 657 return False; // ptr to nowhere, or not a ptr to thunks. 658 pot_fn = *((Addr *)pot_fn); 659 if (pot_fn == 0) 660 continue; // NULL fn pointer. Seems it can happen in vtable. 661 seg = VG_(am_find_nsegment) (pot_fn); 662#endif 663 if (seg == NULL 664 || seg->kind != SkFileC 665 || !seg->hasT) 666 return False; // ptr to nowhere, or not a fn ptr. 667 nr_fn_ptrs++; 668 if (nr_fn_ptrs == 2) 669 return True; 670 } 671 672 return False; 673} 674 675// If ch is heuristically reachable via an heuristic member of heur_set, 676// returns this heuristic. 677// If ch cannot be considered reachable using one of these heuristics, 678// return LchNone. 679// This should only be called when ptr is an interior ptr to ch. 680// The StdString/NewArray/MultipleInheritance heuristics are directly 681// inspired from DrMemory: 682// see http://www.burningcutlery.com/derek/docs/drmem-CGO11.pdf [section VI,C] 683// and bug 280271. 684static LeakCheckHeuristic heuristic_reachedness (Addr ptr, 685 MC_Chunk *ch, LC_Extra *ex, 686 UInt heur_set) 687{ 688 if (HiS(LchStdString, heur_set)) { 689 // Detects inner pointers to Std::String for layout being 690 // length capacity refcount char_array[] \0 691 // where ptr points to the beginning of the char_array. 692 // Note: we check definedness for length and capacity but 693 // not for refcount, as refcount size might be smaller than 694 // a SizeT, giving a uninitialised hole in the first 3 SizeT. 695 if ( ptr == ch->data + 3 * sizeof(SizeT) 696 && MC_(is_valid_aligned_word)(ch->data + sizeof(SizeT))) { 697 const SizeT capacity = *((SizeT*)(ch->data + sizeof(SizeT))); 698 if (3 * sizeof(SizeT) + capacity + 1 == ch->szB 699 && MC_(is_valid_aligned_word)(ch->data)) { 700 const SizeT length = *((SizeT*)ch->data); 701 if (length <= capacity) { 702 // ??? could check there is no null byte from ptr to ptr+length-1 703 // ??? and that there is a null byte at ptr+length. 704 // ??? 705 // ??? could check that ch->allockind is MC_AllocNew ??? 706 // ??? probably not a good idea, as I guess stdstring 707 // ??? allocator can be done via custom allocator 708 // ??? or even a call to malloc ???? 709 return LchStdString; 710 } 711 } 712 } 713 } 714 715 if (HiS(LchNewArray, heur_set)) { 716 // Detects inner pointers at second word of new[] array, following 717 // a plausible nr of elements. 718 // Such inner pointers are used for arrays of elements 719 // having a destructor, as the delete[] of the array must know 720 // how many elements to destroy. 721 // 722 // We have a strange/wrong case for 'ptr = new MyClass[0];' : 723 // For such a case, the returned ptr points just outside the 724 // allocated chunk. This chunk is then seen as a definite 725 // leak by Valgrind, as it is not considered an interior pointer. 726 // It is the c++ equivalent of bug 99923 (malloc(0) wrongly considered 727 // as definitely leaked). See the trick in find_chunk_for handling 728 // 0-sized block. This trick does not work for 'new MyClass[0]' 729 // because a chunk "word-sized" is allocated to store the (0) nr 730 // of elements. 731 if ( ptr == ch->data + sizeof(SizeT) 732 && MC_(is_valid_aligned_word)(ch->data)) { 733 const SizeT nr_elts = *((SizeT*)ch->data); 734 if (nr_elts > 0 && (ch->szB - sizeof(SizeT)) % nr_elts == 0) { 735 // ??? could check that ch->allockind is MC_AllocNewVec ??? 736 return LchNewArray; 737 } 738 } 739 } 740 741 if (HiS(LchMultipleInheritance, heur_set)) { 742 // Detect inner pointer used for multiple inheritance. 743 // Assumption is that the vtable pointers are before the object. 744 if (VG_IS_WORD_ALIGNED(ptr) 745 && MC_(is_valid_aligned_word)(ptr)) { 746 Addr first_addr; 747 Addr inner_addr; 748 749 // Avoid the call to is_vtable_addr when the addr is not 750 // aligned or points in the page0, as it is unlikely 751 // a vtable is located in this page. This last optimisation 752 // avoids to call aligned_ptr_above_page0_is_vtable_addr 753 // for all small integers. 754 // Note: we could possibly also avoid calling this function 755 // for small negative integers, as no vtable should be located 756 // in the last page. 757 inner_addr = *((Addr*)ptr); 758 if (VG_IS_WORD_ALIGNED(inner_addr) 759 && inner_addr >= (Addr)VKI_PAGE_SIZE 760 && MC_(is_valid_aligned_word)(ch->data)) { 761 first_addr = *((Addr*)ch->data); 762 if (VG_IS_WORD_ALIGNED(first_addr) 763 && first_addr >= (Addr)VKI_PAGE_SIZE 764 && aligned_ptr_above_page0_is_vtable_addr(inner_addr) 765 && aligned_ptr_above_page0_is_vtable_addr(first_addr)) { 766 // ??? could check that ch->allockind is MC_AllocNew ??? 767 return LchMultipleInheritance; 768 } 769 } 770 } 771 } 772 773 return LchNone; 774} 775 776 777// If 'ptr' is pointing to a heap-allocated block which hasn't been seen 778// before, push it onto the mark stack. 779static void 780lc_push_without_clique_if_a_chunk_ptr(Addr ptr, Bool is_prior_definite) 781{ 782 Int ch_no; 783 MC_Chunk* ch; 784 LC_Extra* ex; 785 Reachedness ch_via_ptr; // Is ch reachable via ptr, and how ? 786 787 if ( ! lc_is_a_chunk_ptr(ptr, &ch_no, &ch, &ex) ) 788 return; 789 790 if (ex->state == Reachable) { 791 if (ex->heuristic && ptr == ch->data) 792 // If block was considered reachable via an heuristic, and it is now 793 // directly reachable via ptr, clear the heuristic field. 794 ex->heuristic = LchNone; 795 return; 796 } 797 798 // Possibly upgrade the state, ie. one of: 799 // - Unreached --> Possible 800 // - Unreached --> Reachable 801 // - Possible --> Reachable 802 803 if (ptr == ch->data) 804 ch_via_ptr = Reachable; 805 else if (detect_memory_leaks_last_heuristics) { 806 ex->heuristic 807 = heuristic_reachedness (ptr, ch, ex, 808 detect_memory_leaks_last_heuristics); 809 if (ex->heuristic) 810 ch_via_ptr = Reachable; 811 else 812 ch_via_ptr = Possible; 813 } else 814 ch_via_ptr = Possible; 815 816 if (ch_via_ptr == Reachable && is_prior_definite) { 817 // 'ptr' points to the start of the block or is to be considered as 818 // pointing to the start of the block, and the prior node is 819 // definite, which means that this block is definitely reachable. 820 ex->state = Reachable; 821 822 // State has changed to Reachable so (re)scan the block to make 823 // sure any blocks it points to are correctly marked. 824 lc_push(ch_no, ch); 825 826 } else if (ex->state == Unreached) { 827 // Either 'ptr' is a interior-pointer, or the prior node isn't definite, 828 // which means that we can only mark this block as possibly reachable. 829 ex->state = Possible; 830 831 // State has changed to Possible so (re)scan the block to make 832 // sure any blocks it points to are correctly marked. 833 lc_push(ch_no, ch); 834 } 835} 836 837static void 838lc_push_if_a_chunk_ptr_register(ThreadId tid, const HChar* regname, Addr ptr) 839{ 840 lc_push_without_clique_if_a_chunk_ptr(ptr, /*is_prior_definite*/True); 841} 842 843// If ptr is pointing to a heap-allocated block which hasn't been seen 844// before, push it onto the mark stack. Clique is the index of the 845// clique leader. 846static void 847lc_push_with_clique_if_a_chunk_ptr(Addr ptr, Int clique, Int cur_clique) 848{ 849 Int ch_no; 850 MC_Chunk* ch; 851 LC_Extra* ex; 852 853 tl_assert(0 <= clique && clique < lc_n_chunks); 854 855 if ( ! lc_is_a_chunk_ptr(ptr, &ch_no, &ch, &ex) ) 856 return; 857 858 // If it's not Unreached, it's already been handled so ignore it. 859 // If ch_no==clique, it's the clique leader, which means this is a cyclic 860 // structure; again ignore it because it's already been handled. 861 if (ex->state == Unreached && ch_no != clique) { 862 // Note that, unlike reachable blocks, we currently don't distinguish 863 // between start-pointers and interior-pointers here. We probably 864 // should, though. 865 lc_push(ch_no, ch); 866 867 // Add the block to the clique, and add its size to the 868 // clique-leader's indirect size. Also, if the new block was 869 // itself a clique leader, it isn't any more, so add its 870 // indirect_szB to the new clique leader. 871 if (VG_DEBUG_CLIQUE) { 872 if (ex->IorC.indirect_szB > 0) 873 VG_(printf)(" clique %d joining clique %d adding %lu+%lu\n", 874 ch_no, clique, (unsigned long)ch->szB, 875 (unsigned long)ex->IorC.indirect_szB); 876 else 877 VG_(printf)(" block %d joining clique %d adding %lu\n", 878 ch_no, clique, (unsigned long)ch->szB); 879 } 880 881 lc_extras[clique].IorC.indirect_szB += ch->szB; 882 lc_extras[clique].IorC.indirect_szB += ex->IorC.indirect_szB; 883 ex->state = IndirectLeak; 884 ex->IorC.clique = (SizeT) cur_clique; 885 } 886} 887 888static void 889lc_push_if_a_chunk_ptr(Addr ptr, 890 Int clique, Int cur_clique, Bool is_prior_definite) 891{ 892 if (-1 == clique) 893 lc_push_without_clique_if_a_chunk_ptr(ptr, is_prior_definite); 894 else 895 lc_push_with_clique_if_a_chunk_ptr(ptr, clique, cur_clique); 896} 897 898 899static VG_MINIMAL_JMP_BUF(memscan_jmpbuf); 900static volatile Addr bad_scanned_addr; 901 902static 903void scan_all_valid_memory_catcher ( Int sigNo, Addr addr ) 904{ 905 if (0) 906 VG_(printf)("OUCH! sig=%d addr=%#lx\n", sigNo, addr); 907 if (sigNo == VKI_SIGSEGV || sigNo == VKI_SIGBUS) { 908 bad_scanned_addr = addr; 909 VG_MINIMAL_LONGJMP(memscan_jmpbuf); 910 } 911} 912 913// lc_scan_memory has 2 modes: 914// 915// 1. Leak check mode (searched == 0). 916// ----------------------------------- 917// Scan a block of memory between [start, start+len). This range may 918// be bogus, inaccessable, or otherwise strange; we deal with it. For each 919// valid aligned word we assume it's a pointer to a chunk a push the chunk 920// onto the mark stack if so. 921// clique is the "highest level clique" in which indirectly leaked blocks have 922// to be collected. cur_clique is the current "lower" level clique through which 923// the memory to be scanned has been found. 924// Example: in the below tree if A is leaked, the top level clique will 925// be A, while lower level cliques will be B and C. 926/* 927 A 928 / \ 929 B C 930 / \ / \ 931 D E F G 932*/ 933// Proper handling of top and lowest level clique allows block_list of a loss 934// record to describe the hierarchy of indirectly leaked blocks. 935// 936// 2. Search ptr mode (searched != 0). 937// ----------------------------------- 938// In this mode, searches for pointers to a specific address range 939// In such a case, lc_scan_memory just scans [start..start+len[ for pointers 940// to searched and outputs the places where searched is found. 941// It does not recursively scans the found memory. 942static void 943lc_scan_memory(Addr start, SizeT len, Bool is_prior_definite, 944 Int clique, Int cur_clique, 945 Addr searched, SizeT szB) 946{ 947 /* memory scan is based on the assumption that valid pointers are aligned 948 on a multiple of sizeof(Addr). So, we can (and must) skip the begin and 949 end portions of the block if they are not aligned on sizeof(Addr): 950 These cannot be a valid pointer, and calls to MC_(is_valid_aligned_word) 951 will assert for a non aligned address. */ 952#if defined(VGA_s390x) 953 // Define ptr as volatile, as on this platform, the value of ptr 954 // is read in code executed via a longjmp. 955 volatile 956#endif 957 Addr ptr = VG_ROUNDUP(start, sizeof(Addr)); 958 const Addr end = VG_ROUNDDN(start+len, sizeof(Addr)); 959 vki_sigset_t sigmask; 960 961 if (VG_DEBUG_LEAKCHECK) 962 VG_(printf)("scan %#lx-%#lx (%lu)\n", start, end, len); 963 964 VG_(sigprocmask)(VKI_SIG_SETMASK, NULL, &sigmask); 965 VG_(set_fault_catcher)(scan_all_valid_memory_catcher); 966 967 /* Optimisation: the loop below will check for each begin 968 of SM chunk if the chunk is fully unaddressable. The idea is to 969 skip efficiently such fully unaddressable SM chunks. 970 So, we preferrably start the loop on a chunk boundary. 971 If the chunk is not fully unaddressable, we might be in 972 an unaddressable page. Again, the idea is to skip efficiently 973 such unaddressable page : this is the "else" part. 974 We use an "else" so that two consecutive fully unaddressable 975 SM chunks will be skipped efficiently: first one is skipped 976 by this piece of code. The next SM chunk will be skipped inside 977 the loop. */ 978 if ( ! MC_(is_within_valid_secondary)(ptr) ) { 979 // Skip an invalid SM chunk till the beginning of the next SM Chunk. 980 ptr = VG_ROUNDUP(ptr+1, SM_SIZE); 981 } else if (!VG_(am_is_valid_for_client)(ptr, sizeof(Addr), VKI_PROT_READ)) { 982 // else we are in a (at least partially) valid SM chunk. 983 // We might be in the middle of an unreadable page. 984 // Do a cheap check to see if it's valid; 985 // if not, skip onto the next page. 986 ptr = VG_PGROUNDUP(ptr+1); // First page is bad - skip it. 987 } 988 /* The above optimisation and below loop is based on some relationships 989 between VKI_PAGE_SIZE, SM_SIZE and sizeof(Addr) which are asserted in 990 MC_(detect_memory_leaks). */ 991 992 // During scan, we check with aspacemgr that each page is readable and 993 // belongs to client. 994 // We still protect against SIGSEGV and SIGBUS e.g. in case aspacemgr is 995 // desynchronised with the real page mappings. 996 // Such a desynchronisation could happen due to an aspacemgr bug. 997 // Note that if the application is using mprotect(NONE), then 998 // a page can be unreadable but have addressable and defined 999 // VA bits (see mc_main.c function mc_new_mem_mprotect). 1000 if (VG_MINIMAL_SETJMP(memscan_jmpbuf) != 0) { 1001 // Catch read error ... 1002 // We need to restore the signal mask, because we were 1003 // longjmped out of a signal handler. 1004 VG_(sigprocmask)(VKI_SIG_SETMASK, &sigmask, NULL); 1005# if defined(VGA_s390x) 1006 // For a SIGSEGV, s390 delivers the page address of the bad address. 1007 // For a SIGBUS, old s390 kernels deliver a NULL address. 1008 // bad_scanned_addr can thus not be used. 1009 // So, on this platform, we always skip a full page from ptr. 1010 // The below implies to mark ptr as volatile, as we read the value 1011 // after a longjmp to here. 1012 lc_sig_skipped_szB += VKI_PAGE_SIZE; 1013 ptr = ptr + VKI_PAGE_SIZE; // Unaddressable, - skip it. 1014# else 1015 // On other platforms, just skip one Addr. 1016 lc_sig_skipped_szB += sizeof(Addr); 1017 tl_assert(bad_scanned_addr >= VG_ROUNDUP(start, sizeof(Addr))); 1018 tl_assert(bad_scanned_addr < VG_ROUNDDN(start+len, sizeof(Addr))); 1019 ptr = bad_scanned_addr + sizeof(Addr); // Unaddressable, - skip it. 1020#endif 1021 } 1022 while (ptr < end) { 1023 Addr addr; 1024 1025 // Skip invalid chunks. 1026 if (UNLIKELY((ptr % SM_SIZE) == 0)) { 1027 if (! MC_(is_within_valid_secondary)(ptr) ) { 1028 ptr = VG_ROUNDUP(ptr+1, SM_SIZE); 1029 continue; 1030 } 1031 } 1032 1033 // Look to see if this page seems reasonable. 1034 if (UNLIKELY((ptr % VKI_PAGE_SIZE) == 0)) { 1035 if (!VG_(am_is_valid_for_client)(ptr, sizeof(Addr), VKI_PROT_READ)) { 1036 ptr += VKI_PAGE_SIZE; // Bad page - skip it. 1037 continue; 1038 } 1039 } 1040 1041 if ( MC_(is_valid_aligned_word)(ptr) ) { 1042 lc_scanned_szB += sizeof(Addr); 1043 // If the below read fails, we will longjmp to the loop begin. 1044 addr = *(Addr *)ptr; 1045 // If we get here, the scanned word is in valid memory. Now 1046 // let's see if its contents point to a chunk. 1047 if (UNLIKELY(searched)) { 1048 if (addr >= searched && addr < searched + szB) { 1049 if (addr == searched) { 1050 VG_(umsg)("*%#lx points at %#lx\n", ptr, searched); 1051 MC_(pp_describe_addr) (ptr); 1052 } else { 1053 Int ch_no; 1054 MC_Chunk *ch; 1055 LC_Extra *ex; 1056 VG_(umsg)("*%#lx interior points at %lu bytes inside %#lx\n", 1057 ptr, (long unsigned) addr - searched, searched); 1058 MC_(pp_describe_addr) (ptr); 1059 if (lc_is_a_chunk_ptr(addr, &ch_no, &ch, &ex) ) { 1060 Int h; 1061 for (h = LchStdString; h <= LchMultipleInheritance; h++) { 1062 if (heuristic_reachedness(addr, ch, ex, H2S(h)) == h) { 1063 VG_(umsg)("block at %#lx considered reachable " 1064 "by ptr %#lx using %s heuristic\n", 1065 ch->data, addr, pp_heuristic(h)); 1066 } 1067 } 1068 // Verify the loop above has properly scanned all 1069 // heuristics. If the below fails, it probably means the 1070 // LeakCheckHeuristic enum is not in sync anymore with the 1071 // above loop and/or with N_LEAK_CHECK_HEURISTICS. 1072 tl_assert (h == N_LEAK_CHECK_HEURISTICS); 1073 } 1074 } 1075 } 1076 } else { 1077 lc_push_if_a_chunk_ptr(addr, clique, cur_clique, is_prior_definite); 1078 } 1079 } else if (0 && VG_DEBUG_LEAKCHECK) { 1080 VG_(printf)("%#lx not valid\n", ptr); 1081 } 1082 ptr += sizeof(Addr); 1083 } 1084 1085 VG_(sigprocmask)(VKI_SIG_SETMASK, &sigmask, NULL); 1086 VG_(set_fault_catcher)(NULL); 1087} 1088 1089 1090// Process the mark stack until empty. 1091static void lc_process_markstack(Int clique) 1092{ 1093 Int top = -1; // shut gcc up 1094 Bool is_prior_definite; 1095 1096 while (lc_pop(&top)) { 1097 tl_assert(top >= 0 && top < lc_n_chunks); 1098 1099 // See comment about 'is_prior_definite' at the top to understand this. 1100 is_prior_definite = ( Possible != lc_extras[top].state ); 1101 1102 lc_scan_memory(lc_chunks[top]->data, lc_chunks[top]->szB, 1103 is_prior_definite, clique, (clique == -1 ? -1 : top), 1104 /*searched*/ 0, 0); 1105 } 1106} 1107 1108static Word cmp_LossRecordKey_LossRecord(const void* key, const void* elem) 1109{ 1110 const LossRecordKey* a = key; 1111 const LossRecordKey* b = &(((const LossRecord*)elem)->key); 1112 1113 // Compare on states first because that's fast. 1114 if (a->state < b->state) return -1; 1115 if (a->state > b->state) return 1; 1116 // Ok, the states are equal. Now compare the locations, which is slower. 1117 if (VG_(eq_ExeContext)( 1118 MC_(clo_leak_resolution), a->allocated_at, b->allocated_at)) 1119 return 0; 1120 // Different locations. Ordering is arbitrary, just use the ec pointer. 1121 if (a->allocated_at < b->allocated_at) return -1; 1122 if (a->allocated_at > b->allocated_at) return 1; 1123 VG_(tool_panic)("bad LossRecord comparison"); 1124} 1125 1126static Int cmp_LossRecords(const void* va, const void* vb) 1127{ 1128 const LossRecord* lr_a = *(const LossRecord *const *)va; 1129 const LossRecord* lr_b = *(const LossRecord *const *)vb; 1130 SizeT total_szB_a = lr_a->szB + lr_a->indirect_szB; 1131 SizeT total_szB_b = lr_b->szB + lr_b->indirect_szB; 1132 1133 // First compare by sizes. 1134 if (total_szB_a < total_szB_b) return -1; 1135 if (total_szB_a > total_szB_b) return 1; 1136 // If size are equal, compare by states. 1137 if (lr_a->key.state < lr_b->key.state) return -1; 1138 if (lr_a->key.state > lr_b->key.state) return 1; 1139 // If they're still equal here, it doesn't matter that much, but we keep 1140 // comparing other things so that regtests are as deterministic as 1141 // possible. So: compare num_blocks. 1142 if (lr_a->num_blocks < lr_b->num_blocks) return -1; 1143 if (lr_a->num_blocks > lr_b->num_blocks) return 1; 1144 // Finally, compare ExeContext addresses... older ones are likely to have 1145 // lower addresses. 1146 if (lr_a->key.allocated_at < lr_b->key.allocated_at) return -1; 1147 if (lr_a->key.allocated_at > lr_b->key.allocated_at) return 1; 1148 return 0; 1149} 1150 1151// allocates or reallocates lr_array, and set its elements to the loss records 1152// contains in lr_table. 1153static Int get_lr_array_from_lr_table(void) { 1154 Int i, n_lossrecords; 1155 LossRecord* lr; 1156 1157 n_lossrecords = VG_(OSetGen_Size)(lr_table); 1158 1159 // (re-)create the array of pointers to the loss records. 1160 // lr_array is kept to allow producing the block list from gdbserver. 1161 if (lr_array != NULL) 1162 VG_(free)(lr_array); 1163 lr_array = VG_(malloc)("mc.pr.2", n_lossrecords * sizeof(LossRecord*)); 1164 i = 0; 1165 VG_(OSetGen_ResetIter)(lr_table); 1166 while ( (lr = VG_(OSetGen_Next)(lr_table)) ) { 1167 lr_array[i++] = lr; 1168 } 1169 tl_assert(i == n_lossrecords); 1170 return n_lossrecords; 1171} 1172 1173 1174static void get_printing_rules(LeakCheckParams* lcp, 1175 LossRecord* lr, 1176 Bool* count_as_error, 1177 Bool* print_record) 1178{ 1179 // Rules for printing: 1180 // - We don't show suppressed loss records ever (and that's controlled 1181 // within the error manager). 1182 // - We show non-suppressed loss records that are specified in 1183 // --show-leak-kinds=... if --leak-check=yes. 1184 1185 Bool delta_considered; 1186 1187 switch (lcp->deltamode) { 1188 case LCD_Any: 1189 delta_considered = lr->num_blocks > 0; 1190 break; 1191 case LCD_Increased: 1192 delta_considered 1193 = lr->szB > lr->old_szB 1194 || lr->indirect_szB > lr->old_indirect_szB 1195 || lr->num_blocks > lr->old_num_blocks; 1196 break; 1197 case LCD_Changed: 1198 delta_considered = lr->szB != lr->old_szB 1199 || lr->indirect_szB != lr->old_indirect_szB 1200 || lr->num_blocks != lr->old_num_blocks; 1201 break; 1202 default: 1203 tl_assert(0); 1204 } 1205 1206 *print_record = lcp->mode == LC_Full && delta_considered 1207 && RiS(lr->key.state,lcp->show_leak_kinds); 1208 // We don't count a leaks as errors with lcp->mode==LC_Summary. 1209 // Otherwise you can get high error counts with few or no error 1210 // messages, which can be confusing. Otherwise, we count as errors 1211 // the leak kinds requested by --errors-for-leak-kinds=... 1212 *count_as_error = lcp->mode == LC_Full && delta_considered 1213 && RiS(lr->key.state,lcp->errors_for_leak_kinds); 1214} 1215 1216static void print_results(ThreadId tid, LeakCheckParams* lcp) 1217{ 1218 Int i, n_lossrecords, start_lr_output_scan; 1219 LossRecord* lr; 1220 Bool is_suppressed; 1221 /* old_* variables are used to report delta in summary. */ 1222 SizeT old_bytes_leaked = MC_(bytes_leaked); 1223 SizeT old_bytes_indirect = MC_(bytes_indirect); 1224 SizeT old_bytes_dubious = MC_(bytes_dubious); 1225 SizeT old_bytes_reachable = MC_(bytes_reachable); 1226 SizeT old_bytes_suppressed = MC_(bytes_suppressed); 1227 SizeT old_blocks_leaked = MC_(blocks_leaked); 1228 SizeT old_blocks_indirect = MC_(blocks_indirect); 1229 SizeT old_blocks_dubious = MC_(blocks_dubious); 1230 SizeT old_blocks_reachable = MC_(blocks_reachable); 1231 SizeT old_blocks_suppressed = MC_(blocks_suppressed); 1232 1233 SizeT old_bytes_heuristically_reachable[N_LEAK_CHECK_HEURISTICS]; 1234 SizeT old_blocks_heuristically_reachable[N_LEAK_CHECK_HEURISTICS]; 1235 1236 for (i = 0; i < N_LEAK_CHECK_HEURISTICS; i++) { 1237 old_bytes_heuristically_reachable[i] 1238 = MC_(bytes_heuristically_reachable)[i]; 1239 MC_(bytes_heuristically_reachable)[i] = 0; 1240 old_blocks_heuristically_reachable[i] 1241 = MC_(blocks_heuristically_reachable)[i]; 1242 MC_(blocks_heuristically_reachable)[i] = 0; 1243 } 1244 1245 if (lr_table == NULL) 1246 // Create the lr_table, which holds the loss records. 1247 // If the lr_table already exists, it means it contains 1248 // loss_records from the previous leak search. The old_* 1249 // values in these records are used to implement the 1250 // leak check delta mode 1251 lr_table = 1252 VG_(OSetGen_Create)(offsetof(LossRecord, key), 1253 cmp_LossRecordKey_LossRecord, 1254 VG_(malloc), "mc.pr.1", 1255 VG_(free)); 1256 1257 // If we have loss records from a previous search, reset values to have 1258 // proper printing of the deltas between previous search and this search. 1259 n_lossrecords = get_lr_array_from_lr_table(); 1260 for (i = 0; i < n_lossrecords; i++) { 1261 if (lr_array[i]->num_blocks == 0) { 1262 // remove from lr_table the old loss_records with 0 bytes found 1263 VG_(OSetGen_Remove) (lr_table, &lr_array[i]->key); 1264 VG_(OSetGen_FreeNode)(lr_table, lr_array[i]); 1265 } else { 1266 // move the leak sizes to old_* and zero the current sizes 1267 // for next leak search 1268 lr_array[i]->old_szB = lr_array[i]->szB; 1269 lr_array[i]->old_indirect_szB = lr_array[i]->indirect_szB; 1270 lr_array[i]->old_num_blocks = lr_array[i]->num_blocks; 1271 lr_array[i]->szB = 0; 1272 lr_array[i]->indirect_szB = 0; 1273 lr_array[i]->num_blocks = 0; 1274 } 1275 } 1276 // lr_array now contains "invalid" loss records => free it. 1277 // lr_array will be re-created below with the kept and new loss records. 1278 VG_(free) (lr_array); 1279 lr_array = NULL; 1280 1281 // Convert the chunks into loss records, merging them where appropriate. 1282 for (i = 0; i < lc_n_chunks; i++) { 1283 MC_Chunk* ch = lc_chunks[i]; 1284 LC_Extra* ex = &(lc_extras)[i]; 1285 LossRecord* old_lr; 1286 LossRecordKey lrkey; 1287 lrkey.state = ex->state; 1288 lrkey.allocated_at = MC_(allocated_at)(ch); 1289 1290 if (ex->heuristic) { 1291 MC_(bytes_heuristically_reachable)[ex->heuristic] += ch->szB; 1292 MC_(blocks_heuristically_reachable)[ex->heuristic]++; 1293 if (VG_DEBUG_LEAKCHECK) 1294 VG_(printf)("heuristic %s %#lx len %lu\n", 1295 pp_heuristic(ex->heuristic), 1296 ch->data, (unsigned long)ch->szB); 1297 } 1298 1299 old_lr = VG_(OSetGen_Lookup)(lr_table, &lrkey); 1300 if (old_lr) { 1301 // We found an existing loss record matching this chunk. Update the 1302 // loss record's details in-situ. This is safe because we don't 1303 // change the elements used as the OSet key. 1304 old_lr->szB += ch->szB; 1305 if (ex->state == Unreached) 1306 old_lr->indirect_szB += ex->IorC.indirect_szB; 1307 old_lr->num_blocks++; 1308 } else { 1309 // No existing loss record matches this chunk. Create a new loss 1310 // record, initialise it from the chunk, and insert it into lr_table. 1311 lr = VG_(OSetGen_AllocNode)(lr_table, sizeof(LossRecord)); 1312 lr->key = lrkey; 1313 lr->szB = ch->szB; 1314 if (ex->state == Unreached) 1315 lr->indirect_szB = ex->IorC.indirect_szB; 1316 else 1317 lr->indirect_szB = 0; 1318 lr->num_blocks = 1; 1319 lr->old_szB = 0; 1320 lr->old_indirect_szB = 0; 1321 lr->old_num_blocks = 0; 1322 VG_(OSetGen_Insert)(lr_table, lr); 1323 } 1324 } 1325 1326 // (re-)create the array of pointers to the (new) loss records. 1327 n_lossrecords = get_lr_array_from_lr_table (); 1328 tl_assert(VG_(OSetGen_Size)(lr_table) == n_lossrecords); 1329 1330 // Sort the array by loss record sizes. 1331 VG_(ssort)(lr_array, n_lossrecords, sizeof(LossRecord*), 1332 cmp_LossRecords); 1333 1334 // Zero totals. 1335 MC_(blocks_leaked) = MC_(bytes_leaked) = 0; 1336 MC_(blocks_indirect) = MC_(bytes_indirect) = 0; 1337 MC_(blocks_dubious) = MC_(bytes_dubious) = 0; 1338 MC_(blocks_reachable) = MC_(bytes_reachable) = 0; 1339 MC_(blocks_suppressed) = MC_(bytes_suppressed) = 0; 1340 1341 // If there is a maximum nr of loss records we can output, then first 1342 // compute from where the output scan has to start. 1343 // By default, start from the first loss record. Compute a higher 1344 // value if there is a maximum to respect. We need to print the last 1345 // records, as the one with the biggest sizes are more interesting. 1346 start_lr_output_scan = 0; 1347 if (lcp->mode == LC_Full && lcp->max_loss_records_output < n_lossrecords) { 1348 Int nr_printable_records = 0; 1349 for (i = n_lossrecords - 1; i >= 0 && start_lr_output_scan == 0; i--) { 1350 Bool count_as_error, print_record; 1351 lr = lr_array[i]; 1352 get_printing_rules (lcp, lr, &count_as_error, &print_record); 1353 // Do not use get_printing_rules results for is_suppressed, as we 1354 // only want to check if the record would be suppressed. 1355 is_suppressed = 1356 MC_(record_leak_error) ( tid, i+1, n_lossrecords, lr, 1357 False /* print_record */, 1358 False /* count_as_error */); 1359 if (print_record && !is_suppressed) { 1360 nr_printable_records++; 1361 if (nr_printable_records == lcp->max_loss_records_output) 1362 start_lr_output_scan = i; 1363 } 1364 } 1365 } 1366 1367 // Print the loss records (in size order) and collect summary stats. 1368 for (i = start_lr_output_scan; i < n_lossrecords; i++) { 1369 Bool count_as_error, print_record; 1370 lr = lr_array[i]; 1371 get_printing_rules(lcp, lr, &count_as_error, &print_record); 1372 is_suppressed = 1373 MC_(record_leak_error) ( tid, i+1, n_lossrecords, lr, print_record, 1374 count_as_error ); 1375 1376 if (is_suppressed) { 1377 MC_(blocks_suppressed) += lr->num_blocks; 1378 MC_(bytes_suppressed) += lr->szB; 1379 1380 } else if (Unreached == lr->key.state) { 1381 MC_(blocks_leaked) += lr->num_blocks; 1382 MC_(bytes_leaked) += lr->szB; 1383 1384 } else if (IndirectLeak == lr->key.state) { 1385 MC_(blocks_indirect) += lr->num_blocks; 1386 MC_(bytes_indirect) += lr->szB; 1387 1388 } else if (Possible == lr->key.state) { 1389 MC_(blocks_dubious) += lr->num_blocks; 1390 MC_(bytes_dubious) += lr->szB; 1391 1392 } else if (Reachable == lr->key.state) { 1393 MC_(blocks_reachable) += lr->num_blocks; 1394 MC_(bytes_reachable) += lr->szB; 1395 1396 } else { 1397 VG_(tool_panic)("unknown loss mode"); 1398 } 1399 } 1400 1401 if (VG_(clo_verbosity) > 0 && !VG_(clo_xml)) { 1402 HChar d_bytes[20]; 1403 HChar d_blocks[20]; 1404# define DBY(new,old) \ 1405 MC_(snprintf_delta) (d_bytes, 20, (new), (old), lcp->deltamode) 1406# define DBL(new,old) \ 1407 MC_(snprintf_delta) (d_blocks, 20, (new), (old), lcp->deltamode) 1408 1409 VG_(umsg)("LEAK SUMMARY:\n"); 1410 VG_(umsg)(" definitely lost: %'lu%s bytes in %'lu%s blocks\n", 1411 MC_(bytes_leaked), 1412 DBY (MC_(bytes_leaked), old_bytes_leaked), 1413 MC_(blocks_leaked), 1414 DBL (MC_(blocks_leaked), old_blocks_leaked)); 1415 VG_(umsg)(" indirectly lost: %'lu%s bytes in %'lu%s blocks\n", 1416 MC_(bytes_indirect), 1417 DBY (MC_(bytes_indirect), old_bytes_indirect), 1418 MC_(blocks_indirect), 1419 DBL (MC_(blocks_indirect), old_blocks_indirect)); 1420 VG_(umsg)(" possibly lost: %'lu%s bytes in %'lu%s blocks\n", 1421 MC_(bytes_dubious), 1422 DBY (MC_(bytes_dubious), old_bytes_dubious), 1423 MC_(blocks_dubious), 1424 DBL (MC_(blocks_dubious), old_blocks_dubious)); 1425 VG_(umsg)(" still reachable: %'lu%s bytes in %'lu%s blocks\n", 1426 MC_(bytes_reachable), 1427 DBY (MC_(bytes_reachable), old_bytes_reachable), 1428 MC_(blocks_reachable), 1429 DBL (MC_(blocks_reachable), old_blocks_reachable)); 1430 for (i = 0; i < N_LEAK_CHECK_HEURISTICS; i++) 1431 if (old_blocks_heuristically_reachable[i] > 0 1432 || MC_(blocks_heuristically_reachable)[i] > 0) { 1433 VG_(umsg)(" of which " 1434 "reachable via heuristic:\n"); 1435 break; 1436 } 1437 for (i = 0; i < N_LEAK_CHECK_HEURISTICS; i++) 1438 if (old_blocks_heuristically_reachable[i] > 0 1439 || MC_(blocks_heuristically_reachable)[i] > 0) 1440 VG_(umsg)(" %19s: " 1441 "%'lu%s bytes in %'lu%s blocks\n", 1442 pp_heuristic(i), 1443 MC_(bytes_heuristically_reachable)[i], 1444 DBY (MC_(bytes_heuristically_reachable)[i], 1445 old_bytes_heuristically_reachable[i]), 1446 MC_(blocks_heuristically_reachable)[i], 1447 DBL (MC_(blocks_heuristically_reachable)[i], 1448 old_blocks_heuristically_reachable[i])); 1449 VG_(umsg)(" suppressed: %'lu%s bytes in %'lu%s blocks\n", 1450 MC_(bytes_suppressed), 1451 DBY (MC_(bytes_suppressed), old_bytes_suppressed), 1452 MC_(blocks_suppressed), 1453 DBL (MC_(blocks_suppressed), old_blocks_suppressed)); 1454 if (lcp->mode != LC_Full && 1455 (MC_(blocks_leaked) + MC_(blocks_indirect) + 1456 MC_(blocks_dubious) + MC_(blocks_reachable)) > 0) { 1457 if (lcp->requested_by_monitor_command) 1458 VG_(umsg)("To see details of leaked memory, " 1459 "give 'full' arg to leak_check\n"); 1460 else 1461 VG_(umsg)("Rerun with --leak-check=full to see details " 1462 "of leaked memory\n"); 1463 } 1464 if (lcp->mode == LC_Full && 1465 MC_(blocks_reachable) > 0 && !RiS(Reachable,lcp->show_leak_kinds)) { 1466 VG_(umsg)("Reachable blocks (those to which a pointer " 1467 "was found) are not shown.\n"); 1468 if (lcp->requested_by_monitor_command) 1469 VG_(umsg)("To see them, add 'reachable any' args to leak_check\n"); 1470 else 1471 VG_(umsg)("To see them, rerun with: --leak-check=full " 1472 "--show-leak-kinds=all\n"); 1473 } 1474 VG_(umsg)("\n"); 1475 #undef DBL 1476 #undef DBY 1477 } 1478} 1479 1480// print recursively all indirectly leaked blocks collected in clique. 1481static void print_clique (Int clique, UInt level) 1482{ 1483 Int ind; 1484 Int i, n_lossrecords;; 1485 1486 n_lossrecords = VG_(OSetGen_Size)(lr_table); 1487 1488 for (ind = 0; ind < lc_n_chunks; ind++) { 1489 LC_Extra* ind_ex = &(lc_extras)[ind]; 1490 if (ind_ex->state == IndirectLeak 1491 && ind_ex->IorC.clique == (SizeT) clique) { 1492 MC_Chunk* ind_ch = lc_chunks[ind]; 1493 LossRecord* ind_lr; 1494 LossRecordKey ind_lrkey; 1495 Int lr_i; 1496 ind_lrkey.state = ind_ex->state; 1497 ind_lrkey.allocated_at = MC_(allocated_at)(ind_ch); 1498 ind_lr = VG_(OSetGen_Lookup)(lr_table, &ind_lrkey); 1499 for (lr_i = 0; lr_i < n_lossrecords; lr_i++) 1500 if (ind_lr == lr_array[lr_i]) 1501 break; 1502 for (i = 0; i < level; i++) 1503 VG_(umsg)(" "); 1504 VG_(umsg)("%p[%lu] indirect loss record %d\n", 1505 (void *)ind_ch->data, (unsigned long)ind_ch->szB, 1506 lr_i+1); // lr_i+1 for user numbering. 1507 if (lr_i >= n_lossrecords) 1508 VG_(umsg) 1509 ("error: no indirect loss record found for %p[%lu]?????\n", 1510 (void *)ind_ch->data, (unsigned long)ind_ch->szB); 1511 print_clique(ind, level+1); 1512 } 1513 } 1514 } 1515 1516Bool MC_(print_block_list) ( UInt loss_record_nr) 1517{ 1518 Int i, n_lossrecords; 1519 LossRecord* lr; 1520 1521 if (lr_table == NULL || lc_chunks == NULL || lc_extras == NULL) { 1522 VG_(umsg)("Can't print block list : no valid leak search result\n"); 1523 return False; 1524 } 1525 1526 if (lc_chunks_n_frees_marker != MC_(get_cmalloc_n_frees)()) { 1527 VG_(umsg)("Can't print obsolete block list : redo a leak search first\n"); 1528 return False; 1529 } 1530 1531 n_lossrecords = VG_(OSetGen_Size)(lr_table); 1532 if (loss_record_nr >= n_lossrecords) 1533 return False; // Invalid loss record nr. 1534 1535 tl_assert (lr_array); 1536 lr = lr_array[loss_record_nr]; 1537 1538 // (re-)print the loss record details. 1539 // (+1 on loss_record_nr as user numbering for loss records starts at 1). 1540 MC_(pp_LossRecord)(loss_record_nr+1, n_lossrecords, lr); 1541 1542 // Match the chunks with loss records. 1543 for (i = 0; i < lc_n_chunks; i++) { 1544 MC_Chunk* ch = lc_chunks[i]; 1545 LC_Extra* ex = &(lc_extras)[i]; 1546 LossRecord* old_lr; 1547 LossRecordKey lrkey; 1548 lrkey.state = ex->state; 1549 lrkey.allocated_at = MC_(allocated_at)(ch); 1550 1551 old_lr = VG_(OSetGen_Lookup)(lr_table, &lrkey); 1552 if (old_lr) { 1553 // We found an existing loss record matching this chunk. 1554 // If this is the loss record we are looking for, output the pointer. 1555 if (old_lr == lr_array[loss_record_nr]) { 1556 VG_(umsg)("%p[%lu]\n", 1557 (void *)ch->data, (unsigned long) ch->szB); 1558 if (ex->state != Reachable) { 1559 // We can print the clique in all states, except Reachable. 1560 // In Unreached state, lc_chunk[i] is the clique leader. 1561 // In IndirectLeak, lc_chunk[i] might have been a clique leader 1562 // which was later collected in another clique. 1563 // For Possible, lc_chunk[i] might be the top of a clique 1564 // or an intermediate clique. 1565 print_clique(i, 1); 1566 } 1567 } 1568 } else { 1569 // No existing loss record matches this chunk ??? 1570 VG_(umsg)("error: no loss record found for %p[%lu]?????\n", 1571 (void *)ch->data, (unsigned long) ch->szB); 1572 } 1573 } 1574 return True; 1575} 1576 1577// If searched = 0, scan memory root set, pushing onto the mark stack the blocks 1578// encountered. 1579// Otherwise (searched != 0), scan the memory root set searching for ptr 1580// pointing inside [searched, searched+szB[. 1581static void scan_memory_root_set(Addr searched, SizeT szB) 1582{ 1583 Int i; 1584 Int n_seg_starts; 1585 Addr* seg_starts = VG_(get_segment_starts)( &n_seg_starts ); 1586 1587 tl_assert(seg_starts && n_seg_starts > 0); 1588 1589 lc_scanned_szB = 0; 1590 lc_sig_skipped_szB = 0; 1591 1592 // VG_(am_show_nsegments)( 0, "leakcheck"); 1593 for (i = 0; i < n_seg_starts; i++) { 1594 SizeT seg_size; 1595 NSegment const* seg = VG_(am_find_nsegment)( seg_starts[i] ); 1596 tl_assert(seg); 1597 1598 if (seg->kind != SkFileC && seg->kind != SkAnonC) continue; 1599 if (!(seg->hasR && seg->hasW)) continue; 1600 if (seg->isCH) continue; 1601 1602 // Don't poke around in device segments as this may cause 1603 // hangs. Exclude /dev/zero just in case someone allocated 1604 // memory by explicitly mapping /dev/zero. 1605 if (seg->kind == SkFileC 1606 && (VKI_S_ISCHR(seg->mode) || VKI_S_ISBLK(seg->mode))) { 1607 HChar* dev_name = VG_(am_get_filename)( seg ); 1608 if (dev_name && 0 == VG_(strcmp)(dev_name, "/dev/zero")) { 1609 // Don't skip /dev/zero. 1610 } else { 1611 // Skip this device mapping. 1612 continue; 1613 } 1614 } 1615 1616 if (0) 1617 VG_(printf)("ACCEPT %2d %#lx %#lx\n", i, seg->start, seg->end); 1618 1619 // Scan the segment. We use -1 for the clique number, because this 1620 // is a root-set. 1621 seg_size = seg->end - seg->start + 1; 1622 if (VG_(clo_verbosity) > 2) { 1623 VG_(message)(Vg_DebugMsg, 1624 " Scanning root segment: %#lx..%#lx (%lu)\n", 1625 seg->start, seg->end, seg_size); 1626 } 1627 lc_scan_memory(seg->start, seg_size, /*is_prior_definite*/True, 1628 /*clique*/-1, /*cur_clique*/-1, 1629 searched, szB); 1630 } 1631 VG_(free)(seg_starts); 1632} 1633 1634/*------------------------------------------------------------*/ 1635/*--- Top-level entry point. ---*/ 1636/*------------------------------------------------------------*/ 1637 1638void MC_(detect_memory_leaks) ( ThreadId tid, LeakCheckParams* lcp) 1639{ 1640 Int i, j; 1641 1642 tl_assert(lcp->mode != LC_Off); 1643 1644 // Verify some assertions which are used in lc_scan_memory. 1645 tl_assert((VKI_PAGE_SIZE % sizeof(Addr)) == 0); 1646 tl_assert((SM_SIZE % sizeof(Addr)) == 0); 1647 // Above two assertions are critical, while below assertion 1648 // ensures that the optimisation in the loop is done in the 1649 // correct order : the loop checks for (big) SM chunk skipping 1650 // before checking for (smaller) page skipping. 1651 tl_assert((SM_SIZE % VKI_PAGE_SIZE) == 0); 1652 1653 MC_(leak_search_gen)++; 1654 MC_(detect_memory_leaks_last_delta_mode) = lcp->deltamode; 1655 detect_memory_leaks_last_heuristics = lcp->heuristics; 1656 1657 // Get the chunks, stop if there were none. 1658 if (lc_chunks) { 1659 VG_(free)(lc_chunks); 1660 lc_chunks = NULL; 1661 } 1662 lc_chunks = find_active_chunks(&lc_n_chunks); 1663 lc_chunks_n_frees_marker = MC_(get_cmalloc_n_frees)(); 1664 if (lc_n_chunks == 0) { 1665 tl_assert(lc_chunks == NULL); 1666 if (lr_table != NULL) { 1667 // forget the previous recorded LossRecords as next leak search 1668 // can in any case just create new leaks. 1669 // Maybe it would be better to rather call print_result ? 1670 // (at least when leak decreases are requested) 1671 // This will then output all LossRecords with a size decreasing to 0 1672 VG_(OSetGen_Destroy) (lr_table); 1673 lr_table = NULL; 1674 } 1675 if (VG_(clo_verbosity) >= 1 && !VG_(clo_xml)) { 1676 VG_(umsg)("All heap blocks were freed -- no leaks are possible\n"); 1677 VG_(umsg)("\n"); 1678 } 1679 return; 1680 } 1681 1682 // Sort the array so blocks are in ascending order in memory. 1683 VG_(ssort)(lc_chunks, lc_n_chunks, sizeof(VgHashNode*), compare_MC_Chunks); 1684 1685 // Sanity check -- make sure they're in order. 1686 for (i = 0; i < lc_n_chunks-1; i++) { 1687 tl_assert( lc_chunks[i]->data <= lc_chunks[i+1]->data); 1688 } 1689 1690 // Sanity check -- make sure they don't overlap. The one exception is that 1691 // we allow a MALLOCLIKE block to sit entirely within a malloc() block. 1692 // This is for bug 100628. If this occurs, we ignore the malloc() block 1693 // for leak-checking purposes. This is a hack and probably should be done 1694 // better, but at least it's consistent with mempools (which are treated 1695 // like this in find_active_chunks). Mempools have a separate VgHashTable 1696 // for mempool chunks, but if custom-allocated blocks are put in a separate 1697 // table from normal heap blocks it makes free-mismatch checking more 1698 // difficult. 1699 // 1700 // If this check fails, it probably means that the application 1701 // has done something stupid with VALGRIND_MALLOCLIKE_BLOCK client 1702 // requests, eg. has made overlapping requests (which are 1703 // nonsensical), or used VALGRIND_MALLOCLIKE_BLOCK for stack locations; 1704 // again nonsensical. 1705 // 1706 for (i = 0; i < lc_n_chunks-1; i++) { 1707 MC_Chunk* ch1 = lc_chunks[i]; 1708 MC_Chunk* ch2 = lc_chunks[i+1]; 1709 1710 Addr start1 = ch1->data; 1711 Addr start2 = ch2->data; 1712 Addr end1 = ch1->data + ch1->szB - 1; 1713 Addr end2 = ch2->data + ch2->szB - 1; 1714 Bool isCustom1 = ch1->allockind == MC_AllocCustom; 1715 Bool isCustom2 = ch2->allockind == MC_AllocCustom; 1716 1717 if (end1 < start2) { 1718 // Normal case - no overlap. 1719 1720 // We used to allow exact duplicates, I'm not sure why. --njn 1721 //} else if (start1 == start2 && end1 == end2) { 1722 // Degenerate case: exact duplicates. 1723 1724 } else if (start1 >= start2 && end1 <= end2 && isCustom1 && !isCustom2) { 1725 // Block i is MALLOCLIKE and entirely within block i+1. 1726 // Remove block i+1. 1727 for (j = i+1; j < lc_n_chunks-1; j++) { 1728 lc_chunks[j] = lc_chunks[j+1]; 1729 } 1730 lc_n_chunks--; 1731 1732 } else if (start2 >= start1 && end2 <= end1 && isCustom2 && !isCustom1) { 1733 // Block i+1 is MALLOCLIKE and entirely within block i. 1734 // Remove block i. 1735 for (j = i; j < lc_n_chunks-1; j++) { 1736 lc_chunks[j] = lc_chunks[j+1]; 1737 } 1738 lc_n_chunks--; 1739 1740 } else { 1741 VG_(umsg)("Block 0x%lx..0x%lx overlaps with block 0x%lx..0x%lx\n", 1742 start1, end1, start2, end2); 1743 VG_(umsg)("Blocks allocation contexts:\n"), 1744 VG_(pp_ExeContext)( MC_(allocated_at)(ch1)); 1745 VG_(umsg)("\n"), 1746 VG_(pp_ExeContext)( MC_(allocated_at)(ch2)); 1747 VG_(umsg)("This is usually caused by using VALGRIND_MALLOCLIKE_BLOCK"); 1748 VG_(umsg)("in an inappropriate way.\n"); 1749 tl_assert (0); 1750 } 1751 } 1752 1753 // Initialise lc_extras. 1754 if (lc_extras) { 1755 VG_(free)(lc_extras); 1756 lc_extras = NULL; 1757 } 1758 lc_extras = VG_(malloc)( "mc.dml.2", lc_n_chunks * sizeof(LC_Extra) ); 1759 for (i = 0; i < lc_n_chunks; i++) { 1760 lc_extras[i].state = Unreached; 1761 lc_extras[i].pending = False; 1762 lc_extras[i].heuristic = LchNone; 1763 lc_extras[i].IorC.indirect_szB = 0; 1764 } 1765 1766 // Initialise lc_markstack. 1767 lc_markstack = VG_(malloc)( "mc.dml.2", lc_n_chunks * sizeof(Int) ); 1768 for (i = 0; i < lc_n_chunks; i++) { 1769 lc_markstack[i] = -1; 1770 } 1771 lc_markstack_top = -1; 1772 1773 // Verbosity. 1774 if (VG_(clo_verbosity) > 1 && !VG_(clo_xml)) { 1775 VG_(umsg)( "Searching for pointers to %'d not-freed blocks\n", 1776 lc_n_chunks ); 1777 } 1778 1779 // Scan the memory root-set, pushing onto the mark stack any blocks 1780 // pointed to. 1781 scan_memory_root_set(/*searched*/0, 0); 1782 1783 // Scan GP registers for chunk pointers. 1784 VG_(apply_to_GP_regs)(lc_push_if_a_chunk_ptr_register); 1785 1786 // Process the pushed blocks. After this, every block that is reachable 1787 // from the root-set has been traced. 1788 lc_process_markstack(/*clique*/-1); 1789 1790 if (VG_(clo_verbosity) > 1 && !VG_(clo_xml)) { 1791 VG_(umsg)("Checked %'lu bytes\n", lc_scanned_szB); 1792 if (lc_sig_skipped_szB > 0) 1793 VG_(umsg)("Skipped %'lu bytes due to read errors\n", 1794 lc_sig_skipped_szB); 1795 VG_(umsg)( "\n" ); 1796 } 1797 1798 // Trace all the leaked blocks to determine which are directly leaked and 1799 // which are indirectly leaked. For each Unreached block, push it onto 1800 // the mark stack, and find all the as-yet-Unreached blocks reachable 1801 // from it. These form a clique and are marked IndirectLeak, and their 1802 // size is added to the clique leader's indirect size. If one of the 1803 // found blocks was itself a clique leader (from a previous clique), then 1804 // the cliques are merged. 1805 for (i = 0; i < lc_n_chunks; i++) { 1806 MC_Chunk* ch = lc_chunks[i]; 1807 LC_Extra* ex = &(lc_extras[i]); 1808 1809 if (VG_DEBUG_CLIQUE) 1810 VG_(printf)("cliques: %d at %#lx -> Loss state %d\n", 1811 i, ch->data, ex->state); 1812 1813 tl_assert(lc_markstack_top == -1); 1814 1815 if (ex->state == Unreached) { 1816 if (VG_DEBUG_CLIQUE) 1817 VG_(printf)("%d: gathering clique %#lx\n", i, ch->data); 1818 1819 // Push this Unreached block onto the stack and process it. 1820 lc_push(i, ch); 1821 lc_process_markstack(/*clique*/i); 1822 1823 tl_assert(lc_markstack_top == -1); 1824 tl_assert(ex->state == Unreached); 1825 } 1826 } 1827 1828 print_results( tid, lcp); 1829 1830 VG_(free) ( lc_markstack ); 1831 lc_markstack = NULL; 1832 // lc_chunks, lc_extras, lr_array and lr_table are kept (needed if user 1833 // calls MC_(print_block_list)). lr_table also used for delta leak reporting 1834 // between this leak search and the next leak search. 1835} 1836 1837static Addr searched_wpa; 1838static SizeT searched_szB; 1839static void 1840search_address_in_GP_reg(ThreadId tid, const HChar* regname, Addr addr_in_reg) 1841{ 1842 if (addr_in_reg >= searched_wpa 1843 && addr_in_reg < searched_wpa + searched_szB) { 1844 if (addr_in_reg == searched_wpa) 1845 VG_(umsg) 1846 ("tid %d register %s pointing at %#lx\n", 1847 tid, regname, searched_wpa); 1848 else 1849 VG_(umsg) 1850 ("tid %d register %s interior pointing %lu bytes inside %#lx\n", 1851 tid, regname, (long unsigned) addr_in_reg - searched_wpa, 1852 searched_wpa); 1853 } 1854} 1855 1856void MC_(who_points_at) ( Addr address, SizeT szB) 1857{ 1858 MC_Chunk** chunks; 1859 Int n_chunks; 1860 Int i; 1861 1862 if (szB == 1) 1863 VG_(umsg) ("Searching for pointers to %#lx\n", address); 1864 else 1865 VG_(umsg) ("Searching for pointers pointing in %lu bytes from %#lx\n", 1866 szB, address); 1867 1868 chunks = find_active_chunks(&n_chunks); 1869 1870 // Scan memory root-set, searching for ptr pointing in address[szB] 1871 scan_memory_root_set(address, szB); 1872 1873 // Scan active malloc-ed chunks 1874 for (i = 0; i < n_chunks; i++) { 1875 lc_scan_memory(chunks[i]->data, chunks[i]->szB, 1876 /*is_prior_definite*/True, 1877 /*clique*/-1, /*cur_clique*/-1, 1878 address, szB); 1879 } 1880 VG_(free) ( chunks ); 1881 1882 // Scan GP registers for pointers to address range. 1883 searched_wpa = address; 1884 searched_szB = szB; 1885 VG_(apply_to_GP_regs)(search_address_in_GP_reg); 1886 1887} 1888 1889/*--------------------------------------------------------------------*/ 1890/*--- end ---*/ 1891/*--------------------------------------------------------------------*/ 1892 1893