blob: 9377e5ef53200e70860f47a29b3e4cc8b7629b68 [file] [log] [blame]
njn734b8052007-11-01 04:40:37 +00001//--------------------------------------------------------------------*/
2//--- Massif: a heap profiling tool. ms_main.c ---*/
3//--------------------------------------------------------------------*/
nethercotec9f36922004-02-14 16:40:02 +00004
5/*
nethercote996901a2004-08-03 13:29:09 +00006 This file is part of Massif, a Valgrind tool for profiling memory
nethercotec9f36922004-02-14 16:40:02 +00007 usage of programs.
8
sewardj9ebd6e02007-01-08 06:01:59 +00009 Copyright (C) 2003-2007 Nicholas Nethercote
njn2bc10122005-05-08 02:10:27 +000010 njn@valgrind.org
nethercotec9f36922004-02-14 16:40:02 +000011
12 This program is free software; you can redistribute it and/or
13 modify it under the terms of the GNU General Public License as
14 published by the Free Software Foundation; either version 2 of the
15 License, or (at your option) any later version.
16
17 This program is distributed in the hope that it will be useful, but
18 WITHOUT ANY WARRANTY; without even the implied warranty of
19 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
20 General Public License for more details.
21
22 You should have received a copy of the GNU General Public License
23 along with this program; if not, write to the Free Software
24 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
25 02111-1307, USA.
26
27 The GNU General Public License is contained in the file COPYING.
28*/
29
njn734b8052007-11-01 04:40:37 +000030//---------------------------------------------------------------------------
31// XXX:
32//---------------------------------------------------------------------------
33// Todo -- critical for release:
njn62721e92007-11-11 22:15:58 +000034// - address/close all the bug reports below (after writing docs)
njn374a36d2007-11-23 01:41:32 +000035// - Get Josef to update the Callgrind --callgrind-out-file option.
njndf02bbc2007-11-02 21:44:02 +000036//
njn734b8052007-11-01 04:40:37 +000037// Todo -- nice, but less critical:
njnab23b612007-11-27 00:53:56 +000038// - do a graph-drawing test
njn734b8052007-11-01 04:40:37 +000039// - make file format more generic. Obstacles:
40// - unit prefixes are not generic
41// - preset column widths for stats are not generic
42// - preset column headers are not generic
43// - "Massif arguments:" line is not generic
44// - do snapshots on client requests
45// - (Michael Meeks): have an interactive way to request a dump
46// (callgrind_control-style)
47// - "profile now"
48// - "show me the extra allocations since the last snapshot"
49// - "start/stop logging" (eg. quickly skip boring bits)
50// - Add ability to draw multiple graphs, eg. heap-only, stack-only, total.
51// Give each graph a title. (try to do it generically!)
52// - allow truncation of long fnnames if the exact line number is
53// identified? [hmm, could make getting the name of alloc-fns more
54// difficult] [could dump full names to file, truncate in ms_print]
55// - make --show-below-main=no work
njn1a2741a2007-11-26 21:59:04 +000056// - Options like --alloc-fn='operator new(unsigned, std::nothrow_t const&)'
57// don't work in a .valgrindrc file or in $VALGRIND_OPTS.
58// m_commandline.c:add_args_from_string() needs to respect single quotes.
59//
njn734b8052007-11-01 04:40:37 +000060//
61// Performance:
62// - To run the benchmarks:
63//
64// perl perf/vg_perf --tools=massif --reps=3 perf/{heap,tinycc} massif
65// time valgrind --tool=massif --depth=100 konqueror
66//
67// The other benchmarks don't do much allocation, and so give similar speeds
68// to Nulgrind.
69//
70// Timing results on 'nevermore' (njn's machine) as of r7013:
71//
72// heap 0.53s ma:12.4s (23.5x, -----)
73// tinycc 0.46s ma: 4.9s (10.7x, -----)
74// many-xpts 0.08s ma: 2.0s (25.0x, -----)
75// konqueror 29.6s real 0:21.0s user
76//
njnab23b612007-11-27 00:53:56 +000077// [Introduction of --time-unit=i as the default slowed things down by
78// roughly 0--20%.]
79//
njn734b8052007-11-01 04:40:37 +000080// - get_XCon accounts for about 9% of konqueror startup time. Try
81// keeping XPt children sorted by 'ip' and use binary search in get_XCon.
82// Requires factoring out binary search code from various places into a
83// VG_(bsearch) function.
84//
85// Todo -- low priority:
njn734b8052007-11-01 04:40:37 +000086// - In each XPt, record both bytes and the number of allocations, and
87// possibly the global number of allocations.
88// - (Artur Wisz) add a feature to Massif to ignore any heap blocks larger
89// than a certain size! Because: "linux's malloc allows to set a
90// MMAP_THRESHOLD value, so we set it to 4096 - all blocks above that will
91// be handled directly by the kernel, and are guaranteed to be returned to
92// the system when freed. So we needed to profile only blocks below this
93// limit."
94//
95// Examine and fix bugs on bugzilla:
96// IGNORE:
97// 112163 nor MASSIF crashed with signal 7 (SIGBUS) after running 2 days
98// - weird, crashes in VEX, ignore
99// 82871 nor Massif output function names too short
100// - on .ps graph, now irrelevant, ignore
101// 129576 nor Massif loses track of memory, incorrect graphs
102// - dunno, hard to reproduce, ignore
103// 132132 nor massif --format=html output does not do html entity escaping
104// - only for HTML output, irrelevant, ignore
105// 132950 Heap alloc/usage summary
106// - doesn't seem that interesting or general
107//
108// FIXED/NOW IRRELEVANT:
109// 89061 cra Massif: ms_main.c:485 (get_XCon): Assertion `xpt->max_chi...
110// - relevant code now gone
111// 143062 cra massif crashes on app exit with signal 8 SIGFPE
112// - fixed
113// 95483 nor massif feature request: include peak allocation in report
114// - implemented in Massif2
115// 92615 nor Write output from Massif at crash
116// - this happens unless Massif2 itself crashes
117// 121629 add instruction-counting mode for timing
118// - time-unit=B is similar, plus I'm considering this above anyway
119// 142197 nor massif tool ignores --massif:alloc-fn parameters in .valg...
120// - fixed in trunk
121// 142491 nor Maximise use of alloc_fns array
122// - addressed, it's now an XArray and thus unlimited in size
123// 144453 (get_XCon): Assertion 'xpt->max_children != 0' failed.
124// - relevant code now gone
125//
126// POSSIBLY FIXED BY BETTER SANITY CHECKING, BUT HARD TO TELL:
127// 141631 Massif: percentages don't add up correctly
128// - better sanity-checking should help this greatly
129// 142706 massif numbers don't seem to add up
130// - better sanity-checking should help this greatly
131// 149504 Assertion hit on alloc_xpt->curr_space >= -space_delta
132// - better sanity-checking should help this greatly
133// 146456 (update_XCon): Assertion 'xpt->curr_space >= -space_delta' failed.
134// - better sanity-checking should help this greatly
135//
136// File format working notes:
137
138#if 0
139desc: --heap-admin=foo
140cmd: date
141time_unit: ms
142#-----------
143snapshot=0
144#-----------
145time=0
146mem_heap_B=0
147mem_heap_admin_B=0
148mem_stacks_B=0
149heap_tree=empty
150#-----------
151snapshot=1
152#-----------
153time=353
154mem_heap_B=5
155mem_heap_admin_B=0
156mem_stacks_B=0
157heap_tree=detailed
158n1: 5 (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
159 n1: 5 0x27F6E0: _nl_normalize_codeset (in /lib/libc-2.3.5.so)
160 n1: 5 0x279DE6: _nl_load_locale_from_archive (in /lib/libc-2.3.5.so)
161 n1: 5 0x278E97: _nl_find_locale (in /lib/libc-2.3.5.so)
162 n1: 5 0x278871: setlocale (in /lib/libc-2.3.5.so)
163 n1: 5 0x8049821: (within /bin/date)
164 n0: 5 0x26ED5E: (below main) (in /lib/libc-2.3.5.so)
165
166
167n_events: n time(ms) total(B) useful-heap(B) admin-heap(B) stacks(B)
168t_events: B
169n 0 0 0 0 0
170n 0 0 0 0 0
171t1: 5 <string...>
172 t1: 6 <string...>
173
174Ideas:
175- each snapshot specifies an x-axis value and one or more y-axis values.
176- can display the y-axis values separately if you like
177- can completely separate connection between snapshots and trees.
178
179Challenges:
180- how to specify and scale/abbreviate units on axes?
181- how to combine multiple values into the y-axis?
182
183--------------------------------------------------------------------------------Command: date
184Massif arguments: --heap-admin=foo
185ms_print arguments: massif.out
186--------------------------------------------------------------------------------
187 KB
1886.472^ :#
189 | :# :: . .
190 ...
191 | ::@ :@ :@ :@:::# :: : ::::
192 0 +-----------------------------------@---@---@-----@--@---#-------------->ms 0 713
193
194Number of snapshots: 50
195 Detailed snapshots: [2, 11, 13, 19, 25, 32 (peak)]
196-------------------------------------------------------------------------------- n time(ms) total(B) useful-heap(B) admin-heap(B) stacks(B)
197-------------------------------------------------------------------------------- 0 0 0 0 0 0
198 1 345 5 5 0 0
199 2 353 5 5 0 0
200100.00% (5B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
201->100.00% (5B) 0x27F6E0: _nl_normalize_codeset (in /lib/libc-2.3.5.so)
202#endif
203
204//---------------------------------------------------------------------------
nethercotec9f36922004-02-14 16:40:02 +0000205
njnc7561b92005-06-19 01:24:32 +0000206#include "pub_tool_basics.h"
sewardj4cfea4f2006-10-14 19:26:10 +0000207#include "pub_tool_vki.h"
sewardj45f4e7c2005-09-27 19:20:21 +0000208#include "pub_tool_aspacemgr.h"
njnea27e462005-05-31 02:38:09 +0000209#include "pub_tool_debuginfo.h"
njn81c00df2005-05-14 21:28:43 +0000210#include "pub_tool_hashtable.h"
njn97405b22005-06-02 03:39:33 +0000211#include "pub_tool_libcbase.h"
njn132bfcc2005-06-04 19:16:06 +0000212#include "pub_tool_libcassert.h"
njneb8896b2005-06-04 20:03:55 +0000213#include "pub_tool_libcfile.h"
njn36a20fa2005-06-03 03:08:39 +0000214#include "pub_tool_libcprint.h"
njnf39e9a32005-06-12 02:43:17 +0000215#include "pub_tool_libcproc.h"
njnb506bd82005-06-21 04:01:51 +0000216#include "pub_tool_machine.h"
njn717cde52005-05-10 02:47:21 +0000217#include "pub_tool_mallocfree.h"
njn20242342005-05-16 23:31:24 +0000218#include "pub_tool_options.h"
njn717cde52005-05-10 02:47:21 +0000219#include "pub_tool_replacemalloc.h"
njnd01fef72005-03-25 23:35:48 +0000220#include "pub_tool_stacktrace.h"
njn43b9a8a2005-05-10 04:37:01 +0000221#include "pub_tool_tooliface.h"
sewardj14c7cc52007-02-25 15:08:24 +0000222#include "pub_tool_xarray.h"
sewardj45f4e7c2005-09-27 19:20:21 +0000223#include "pub_tool_clientstate.h"
nethercotec9f36922004-02-14 16:40:02 +0000224
225#include "valgrind.h" // For {MALLOC,FREE}LIKE_BLOCK
226
njn734b8052007-11-01 04:40:37 +0000227//------------------------------------------------------------*/
228//--- Overview of operation ---*/
229//------------------------------------------------------------*/
nethercotec9f36922004-02-14 16:40:02 +0000230
njn734b8052007-11-01 04:40:37 +0000231// The size of the stacks and heap is tracked. The heap is tracked in a lot
232// of detail, enough to tell how many bytes each line of code is responsible
233// for, more or less. The main data structure is a tree representing the
234// call tree beneath all the allocation functions like malloc().
nethercotec9f36922004-02-14 16:40:02 +0000235//
njn734b8052007-11-01 04:40:37 +0000236// "Snapshots" are recordings of the memory usage. There are two basic
237// kinds:
238// - Normal: these record the current time, total memory size, total heap
239// size, heap admin size and stack size.
240// - Detailed: these record those things in a normal snapshot, plus a very
241// detailed XTree (see below) indicating how the heap is structured.
nethercotec9f36922004-02-14 16:40:02 +0000242//
njn734b8052007-11-01 04:40:37 +0000243// Snapshots are taken every so often. There are two storage classes of
244// snapshots:
245// - Temporary: Massif does a temporary snapshot every so often. The idea
246// is to always have a certain number of temporary snapshots around. So
247// we take them frequently to begin with, but decreasingly often as the
248// program continues to run. Also, we remove some old ones after a while.
249// Overall it's a kind of exponential decay thing. Most of these are
250// normal snapshots, a small fraction are detailed snapshots.
251// - Permanent: Massif takes a permanent (detailed) snapshot in some
252// circumstances. They are:
253// - Peak snapshot: When the memory usage peak is reached, it takes a
254// snapshot. It keeps this, unless the peak is subsequently exceeded,
255// in which case it will overwrite the peak snapshot.
256// - User-requested snapshots: These are done in response to client
257// requests. They are always kept.
nethercotec9f36922004-02-14 16:40:02 +0000258
njn734b8052007-11-01 04:40:37 +0000259// Used for printing things when clo_verbosity > 1.
260#define VERB(verb, format, args...) \
261 if (VG_(clo_verbosity) > verb) { \
262 VG_(message)(Vg_DebugMsg, "Massif: " format, ##args); \
nethercotec9f36922004-02-14 16:40:02 +0000263 }
nethercotec9f36922004-02-14 16:40:02 +0000264
nethercotec9f36922004-02-14 16:40:02 +0000265
nethercotec9f36922004-02-14 16:40:02 +0000266
njn734b8052007-11-01 04:40:37 +0000267//------------------------------------------------------------//
268//--- Statistics ---//
269//------------------------------------------------------------//
nethercotec9f36922004-02-14 16:40:02 +0000270
271// Konqueror startup, to give an idea of the numbers involved with a biggish
272// program, with default depth:
273//
274// depth=3 depth=40
275// - 310,000 allocations
276// - 300,000 frees
277// - 15,000 XPts 800,000 XPts
278// - 1,800 top-XPts
279
njn734b8052007-11-01 04:40:37 +0000280static UInt n_heap_allocs = 0;
281static UInt n_heap_reallocs = 0;
282static UInt n_heap_frees = 0;
283static UInt n_stack_allocs = 0;
284static UInt n_stack_frees = 0;
285static UInt n_xpts = 0;
286static UInt n_xpt_init_expansions = 0;
287static UInt n_xpt_later_expansions = 0;
288static UInt n_sxpt_allocs = 0;
289static UInt n_sxpt_frees = 0;
290static UInt n_skipped_snapshots = 0;
291static UInt n_real_snapshots = 0;
292static UInt n_detailed_snapshots = 0;
293static UInt n_peak_snapshots = 0;
294static UInt n_cullings = 0;
295static UInt n_XCon_redos = 0;
nethercotec9f36922004-02-14 16:40:02 +0000296
njn734b8052007-11-01 04:40:37 +0000297//------------------------------------------------------------//
298//--- Globals ---//
299//------------------------------------------------------------//
nethercotec9f36922004-02-14 16:40:02 +0000300
njn1a2741a2007-11-26 21:59:04 +0000301// Number of guest instructions executed so far. Only used with
302// --time-unit=i.
303static Long guest_instrs_executed = 0;
304
njn32397c02007-11-10 04:08:08 +0000305static SizeT heap_szB = 0; // Live heap size
306static SizeT heap_extra_szB = 0; // Live heap extra size -- slop + admin bytes
307static SizeT stacks_szB = 0; // Live stacks size
nethercotec9f36922004-02-14 16:40:02 +0000308
njn734b8052007-11-01 04:40:37 +0000309// This is the total size from the current peak snapshot, or 0 if no peak
310// snapshot has been taken yet.
311static SizeT peak_snapshot_total_szB = 0;
nethercotec9f36922004-02-14 16:40:02 +0000312
njn734b8052007-11-01 04:40:37 +0000313// Incremented every time memory is allocated/deallocated, by the
314// allocated/deallocated amount; includes heap, heap-admin and stack
315// memory. An alternative to milliseconds as a unit of program "time".
316static ULong total_allocs_deallocs_szB = 0;
nethercotec9f36922004-02-14 16:40:02 +0000317
njn734b8052007-11-01 04:40:37 +0000318// We don't start taking snapshots until the first basic block is executed,
319// rather than doing it in ms_post_clo_init (which is the obvious spot), for
320// two reasons.
321// - It lets us ignore stack events prior to that, because they're not
322// really proper ones and just would screw things up.
323// - Because there's still some core initialisation to do, and so there
324// would be an artificial time gap between the first and second snapshots.
325//
326static Bool have_started_executing_code = False;
nethercotec9f36922004-02-14 16:40:02 +0000327
njn734b8052007-11-01 04:40:37 +0000328//------------------------------------------------------------//
329//--- Alloc fns ---//
330//------------------------------------------------------------//
nethercotec9f36922004-02-14 16:40:02 +0000331
njn734b8052007-11-01 04:40:37 +0000332static XArray* alloc_fns;
nethercotec9f36922004-02-14 16:40:02 +0000333
njn734b8052007-11-01 04:40:37 +0000334static void init_alloc_fns(void)
335{
336 // Create the list, and add the default elements.
337 alloc_fns = VG_(newXA)(VG_(malloc), VG_(free), sizeof(Char*));
338 #define DO(x) { Char* s = x; VG_(addToXA)(alloc_fns, &s); }
nethercotec9f36922004-02-14 16:40:02 +0000339
njn734b8052007-11-01 04:40:37 +0000340 // Ordered according to (presumed) frequency.
341 // Nb: The C++ "operator new*" ones are overloadable. We include them
342 // always anyway, because even if they're overloaded, it would be a
343 // prodigiously stupid overloading that caused them to not allocate
344 // memory.
345 DO("malloc" );
346 DO("__builtin_new" );
347 DO("operator new(unsigned)" );
348 DO("operator new(unsigned long)" );
349 DO("__builtin_vec_new" );
350 DO("operator new[](unsigned)" );
351 DO("operator new[](unsigned long)" );
352 DO("calloc" );
353 DO("realloc" );
354 DO("memalign" );
355 DO("operator new(unsigned, std::nothrow_t const&)" );
356 DO("operator new[](unsigned, std::nothrow_t const&)" );
357 DO("operator new(unsigned long, std::nothrow_t const&)" );
358 DO("operator new[](unsigned long, std::nothrow_t const&)");
359}
nethercotec9f36922004-02-14 16:40:02 +0000360
njn734b8052007-11-01 04:40:37 +0000361static Bool is_alloc_fn(Char* fnname)
362{
363 Char** alloc_fn_ptr;
364 Int i;
365
366 // Nb: It's a linear search through the list, because we're comparing
367 // strings rather than pointers to strings.
368 // Nb: This gets called a lot. It was an OSet, but they're quite slow to
369 // iterate through so it wasn't a good choice.
370 for (i = 0; i < VG_(sizeXA)(alloc_fns); i++) {
371 alloc_fn_ptr = VG_(indexXA)(alloc_fns, i);
372 if (VG_STREQ(fnname, *alloc_fn_ptr))
373 return True;
nethercotec9f36922004-02-14 16:40:02 +0000374 }
njn734b8052007-11-01 04:40:37 +0000375 return False;
376}
nethercotec9f36922004-02-14 16:40:02 +0000377
njn734b8052007-11-01 04:40:37 +0000378
379//------------------------------------------------------------//
380//--- Command line args ---//
381//------------------------------------------------------------//
382
383#define MAX_DEPTH 200
384
njn1a2741a2007-11-26 21:59:04 +0000385typedef enum { TimeI, TimeMS, TimeB } TimeUnit;
njn734b8052007-11-01 04:40:37 +0000386
387static Char* TimeUnit_to_string(TimeUnit time_unit)
388{
389 switch (time_unit) {
njn1a2741a2007-11-26 21:59:04 +0000390 case TimeI: return "i";
njn734b8052007-11-01 04:40:37 +0000391 case TimeMS: return "ms";
392 case TimeB: return "B";
393 default: tl_assert2(0, "TimeUnit_to_string: unrecognised TimeUnit");
394 }
395}
396
397static Bool clo_heap = True;
njn429afb42007-11-02 04:12:48 +0000398 // clo_heap_admin is deliberately a word-sized type. At one point it was
399 // a UInt, but this caused problems on 64-bit machines when it was
400 // multiplied by a small negative number and then promoted to a
401 // word-sized type -- it ended up with a value of 4.2 billion. Sigh.
njn62721e92007-11-11 22:15:58 +0000402static SizeT clo_heap_admin = 8;
403static Bool clo_stacks = False;
404static UInt clo_depth = 30;
405static double clo_threshold = 1.0; // percentage
406static double clo_peak_inaccuracy = 1.0; // percentage
njn1a2741a2007-11-26 21:59:04 +0000407static UInt clo_time_unit = TimeI;
njn62721e92007-11-11 22:15:58 +0000408static UInt clo_detailed_freq = 10;
409static UInt clo_max_snapshots = 100;
njnf4c665f2007-11-20 07:55:40 +0000410static Char* clo_massif_out_file = "massif.out.%p";
njn734b8052007-11-01 04:40:37 +0000411
412static XArray* args_for_massif;
nethercotec9f36922004-02-14 16:40:02 +0000413
njn51d827b2005-05-09 01:02:08 +0000414static Bool ms_process_cmd_line_option(Char* arg)
nethercotec9f36922004-02-14 16:40:02 +0000415{
njn734b8052007-11-01 04:40:37 +0000416 // Remember the arg for later use.
417 VG_(addToXA)(args_for_massif, &arg);
nethercotec9f36922004-02-14 16:40:02 +0000418
njn734b8052007-11-01 04:40:37 +0000419 VG_BOOL_CLO(arg, "--heap", clo_heap)
420 else VG_BOOL_CLO(arg, "--stacks", clo_stacks)
421
njn734b8052007-11-01 04:40:37 +0000422 else VG_NUM_CLO(arg, "--heap-admin", clo_heap_admin)
423 else VG_NUM_CLO(arg, "--depth", clo_depth)
424
njn62721e92007-11-11 22:15:58 +0000425 else VG_DBL_CLO(arg, "--threshold", clo_threshold)
njn734b8052007-11-01 04:40:37 +0000426
njn62721e92007-11-11 22:15:58 +0000427 else VG_DBL_CLO(arg, "--peak-inaccuracy", clo_peak_inaccuracy)
njn734b8052007-11-01 04:40:37 +0000428
429 else VG_NUM_CLO(arg, "--detailed-freq", clo_detailed_freq)
430 else VG_NUM_CLO(arg, "--max-snapshots", clo_max_snapshots)
431
njn1a2741a2007-11-26 21:59:04 +0000432 else if (VG_CLO_STREQ(arg, "--time-unit=i")) clo_time_unit = TimeI;
njn734b8052007-11-01 04:40:37 +0000433 else if (VG_CLO_STREQ(arg, "--time-unit=ms")) clo_time_unit = TimeMS;
434 else if (VG_CLO_STREQ(arg, "--time-unit=B")) clo_time_unit = TimeB;
nethercotec9f36922004-02-14 16:40:02 +0000435
436 else if (VG_CLO_STREQN(11, arg, "--alloc-fn=")) {
njn734b8052007-11-01 04:40:37 +0000437 Char* alloc_fn = &arg[11];
438 VG_(addToXA)(alloc_fns, &alloc_fn);
nethercotec9f36922004-02-14 16:40:02 +0000439 }
440
njnf4c665f2007-11-20 07:55:40 +0000441 else if (VG_CLO_STREQN(14, arg, "--massif-out-file=")) {
442 clo_massif_out_file = &arg[18];
443 }
444
nethercotec9f36922004-02-14 16:40:02 +0000445 else
446 return VG_(replacement_malloc_process_cmd_line_option)(arg);
nethercote27fec902004-06-16 21:26:32 +0000447
nethercotec9f36922004-02-14 16:40:02 +0000448 return True;
449}
450
njn51d827b2005-05-09 01:02:08 +0000451static void ms_print_usage(void)
nethercotec9f36922004-02-14 16:40:02 +0000452{
njn734b8052007-11-01 04:40:37 +0000453 VG_(printf)(
nethercotec9f36922004-02-14 16:40:02 +0000454" --heap=no|yes profile heap blocks [yes]\n"
njn1a2741a2007-11-26 21:59:04 +0000455" --heap-admin=<number> average admin bytes per heap block;\n"
njn734b8052007-11-01 04:40:37 +0000456" ignored if --heap=no [8]\n"
457" --stacks=no|yes profile stack(s) [no]\n"
458" --depth=<number> depth of contexts [30]\n"
nethercotec9f36922004-02-14 16:40:02 +0000459" --alloc-fn=<name> specify <fn> as an alloc function [empty]\n"
njn62721e92007-11-11 22:15:58 +0000460" --threshold=<m.n> significance threshold, as a percentage [1.0]\n"
461" --peak-inaccuracy=<m.n> maximum peak inaccuracy, as a percentage [1.0]\n"
njn1a2741a2007-11-26 21:59:04 +0000462" --time-unit=i|ms|B time unit: instructions executed, milliseconds\n"
463" or heap bytes alloc'd/dealloc'd [i]\n"
njn734b8052007-11-01 04:40:37 +0000464" --detailed-freq=<N> every Nth snapshot should be detailed [10]\n"
465" --max-snapshots=<N> maximum number of snapshots recorded [100]\n"
njn374a36d2007-11-23 01:41:32 +0000466" --massif-out-file=<file> output file name [massif.out.%%p]\n"
nethercotec9f36922004-02-14 16:40:02 +0000467 );
468 VG_(replacement_malloc_print_usage)();
469}
470
njn51d827b2005-05-09 01:02:08 +0000471static void ms_print_debug_usage(void)
nethercotec9f36922004-02-14 16:40:02 +0000472{
473 VG_(replacement_malloc_print_debug_usage)();
474}
475
njn734b8052007-11-01 04:40:37 +0000476
477//------------------------------------------------------------//
478//--- XPts, XTrees and XCons ---//
479//------------------------------------------------------------//
480
481// An XPt represents an "execution point", ie. a code address. Each XPt is
482// part of a tree of XPts (an "execution tree", or "XTree"). The details of
483// the heap are represented by a single XTree.
484//
485// The root of the tree is 'alloc_xpt', which represents all allocation
486// functions, eg:
487// - malloc/calloc/realloc/memalign/new/new[];
488// - user-specified allocation functions (using --alloc-fn);
489// - custom allocation (MALLOCLIKE) points
490// It's a bit of a fake XPt (ie. its 'ip' is zero), and is only used because
491// it makes the code simpler.
492//
493// Any child of 'alloc_xpt' is called a "top-XPt". The XPts at the bottom
494// of an XTree (leaf nodes) are "bottom-XPTs".
495//
496// Each path from a top-XPt to a bottom-XPt through an XTree gives an
497// execution context ("XCon"), ie. a stack trace. (And sub-paths represent
498// stack sub-traces.) The number of XCons in an XTree is equal to the
499// number of bottom-XPTs in that XTree.
500//
501// alloc_xpt XTrees are bi-directional.
502// | ^
503// v |
504// > parent < Example: if child1() calls parent() and child2()
505// / | \ also calls parent(), and parent() calls malloc(),
506// | / \ | the XTree will look like this.
507// | v v |
508// child1 child2
509//
510// XTrees and XPts are mirrored by SXTrees and SXPts, where the 'S' is short
511// for "saved". When the XTree is duplicated for a snapshot, we duplicate
512// it as an SXTree, which is similar but omits some things it does not need,
513// and aggregates up insignificant nodes. This is important as an SXTree is
514// typically much smaller than an XTree.
515
516// XXX: make XPt and SXPt extensible arrays, to avoid having to do two
517// allocations per Pt.
518
519typedef struct _XPt XPt;
520struct _XPt {
521 Addr ip; // code address
522
523 // Bottom-XPts: space for the precise context.
524 // Other XPts: space of all the descendent bottom-XPts.
525 // Nb: this value goes up and down as the program executes.
526 SizeT szB;
527
528 XPt* parent; // pointer to parent XPt
529
530 // Children.
531 // n_children and max_children are 32-bit integers. 16-bit integers
532 // are too small -- a very big program might have more than 65536
533 // allocation points (ie. top-XPts) -- Konqueror starting up has 1800.
534 UInt n_children; // number of children
535 UInt max_children; // capacity of children array
536 XPt** children; // pointers to children XPts
537};
538
539typedef
540 enum {
541 SigSXPt,
542 InsigSXPt
543 }
544 SXPtTag;
545
546typedef struct _SXPt SXPt;
547struct _SXPt {
548 SXPtTag tag;
549 SizeT szB; // memory size for the node, be it Sig or Insig
550 union {
551 // An SXPt representing a single significant code location. Much like
552 // an XPt, minus the fields that aren't necessary.
553 struct {
554 Addr ip;
555 UInt n_children;
556 SXPt** children;
557 }
558 Sig;
559
560 // An SXPt representing one or more code locations, all below the
561 // significance threshold.
562 struct {
563 Int n_xpts; // number of aggregated XPts
564 }
565 Insig;
566 };
567};
nethercotec9f36922004-02-14 16:40:02 +0000568
569// Fake XPt representing all allocation functions like malloc(). Acts as
570// parent node to all top-XPts.
571static XPt* alloc_xpt;
572
573// Cheap allocation for blocks that never need to be freed. Saves about 10%
574// for Konqueror startup with --depth=40.
nethercote7ac7f7b2004-11-02 12:36:02 +0000575static void* perm_malloc(SizeT n_bytes)
nethercotec9f36922004-02-14 16:40:02 +0000576{
577 static Addr hp = 0; // current heap pointer
578 static Addr hp_lim = 0; // maximum usable byte in current block
579
580 #define SUPERBLOCK_SIZE (1 << 20) // 1 MB
581
582 if (hp + n_bytes > hp_lim) {
sewardj45f4e7c2005-09-27 19:20:21 +0000583 hp = (Addr)VG_(am_shadow_alloc)(SUPERBLOCK_SIZE);
584 if (hp == 0)
njn734b8052007-11-01 04:40:37 +0000585 VG_(out_of_memory_NORETURN)( "massif:perm_malloc",
sewardj45f4e7c2005-09-27 19:20:21 +0000586 SUPERBLOCK_SIZE);
nethercotec9f36922004-02-14 16:40:02 +0000587 hp_lim = hp + SUPERBLOCK_SIZE - 1;
588 }
589
590 hp += n_bytes;
591
592 return (void*)(hp - n_bytes);
593}
594
njn734b8052007-11-01 04:40:37 +0000595static XPt* new_XPt(Addr ip, XPt* parent)
nethercotec9f36922004-02-14 16:40:02 +0000596{
njn734b8052007-11-01 04:40:37 +0000597 // XPts are never freed, so we can use perm_malloc to allocate them.
598 // Note that we cannot use perm_malloc for the 'children' array, because
599 // that needs to be resizable.
600 XPt* xpt = perm_malloc(sizeof(XPt));
601 xpt->ip = ip;
602 xpt->szB = 0;
603 xpt->parent = parent;
nethercotec9f36922004-02-14 16:40:02 +0000604
njn734b8052007-11-01 04:40:37 +0000605 // We don't initially allocate any space for children. We let that
606 // happen on demand. Many XPts (ie. all the bottom-XPts) don't have any
607 // children anyway.
nethercotec9f36922004-02-14 16:40:02 +0000608 xpt->n_children = 0;
njn734b8052007-11-01 04:40:37 +0000609 xpt->max_children = 0;
610 xpt->children = NULL;
nethercotec9f36922004-02-14 16:40:02 +0000611
612 // Update statistics
613 n_xpts++;
614
615 return xpt;
616}
617
njn734b8052007-11-01 04:40:37 +0000618static void add_child_xpt(XPt* parent, XPt* child)
619{
620 // Expand 'children' if necessary.
621 tl_assert(parent->n_children <= parent->max_children);
622 if (parent->n_children == parent->max_children) {
623 if (parent->max_children == 0) {
624 parent->max_children = 4;
625 parent->children = VG_(malloc)( parent->max_children * sizeof(XPt*) );
626 n_xpt_init_expansions++;
627 } else {
628 parent->max_children *= 2; // Double size
629 parent->children = VG_(realloc)( parent->children,
630 parent->max_children * sizeof(XPt*) );
631 n_xpt_later_expansions++;
632 }
633 }
634
635 // Insert new child XPt in parent's children list.
636 parent->children[ parent->n_children++ ] = child;
637}
638
639// Reverse comparison for a reverse sort -- biggest to smallest.
640static Int SXPt_revcmp_szB(void* n1, void* n2)
641{
642 SXPt* sxpt1 = *(SXPt**)n1;
643 SXPt* sxpt2 = *(SXPt**)n2;
644 return ( sxpt1->szB < sxpt2->szB ? 1
645 : sxpt1->szB > sxpt2->szB ? -1
646 : 0);
647}
648
649//------------------------------------------------------------//
650//--- XTree Operations ---//
651//------------------------------------------------------------//
652
653// Duplicates an XTree as an SXTree.
654static SXPt* dup_XTree(XPt* xpt, SizeT total_szB)
655{
656 Int i, n_sig_children, n_insig_children, n_child_sxpts;
657 SizeT insig_children_szB, sig_child_threshold_szB;
658 SXPt* sxpt;
659
660 // Number of XPt children Action for SXPT
661 // ------------------ ---------------
662 // 0 sig, 0 insig alloc 0 children
663 // N sig, 0 insig alloc N children, dup all
664 // N sig, M insig alloc N+1, dup first N, aggregate remaining M
665 // 0 sig, M insig alloc 1, aggregate M
666
667 // Work out how big a child must be to be significant. If the current
668 // total_szB is zero, then we set it to 1, which means everything will be
669 // judged insignificant -- this is sensible, as there's no point showing
670 // any detail for this case. Unless they used --threshold=0, in which
671 // case we show them everything because that's what they asked for.
672 //
673 // Nb: We do this once now, rather than once per child, because if we do
674 // that the cost of all the divisions adds up to something significant.
675 if (total_szB == 0 && clo_threshold != 0) {
676 sig_child_threshold_szB = 1;
677 } else {
njn62721e92007-11-11 22:15:58 +0000678 sig_child_threshold_szB = (SizeT)((total_szB * clo_threshold) / 100);
njn734b8052007-11-01 04:40:37 +0000679 }
680
681 // How many children are significant? And do we need an aggregate SXPt?
682 n_sig_children = 0;
683 for (i = 0; i < xpt->n_children; i++) {
684 if (xpt->children[i]->szB >= sig_child_threshold_szB) {
685 n_sig_children++;
686 }
687 }
688 n_insig_children = xpt->n_children - n_sig_children;
689 n_child_sxpts = n_sig_children + ( n_insig_children > 0 ? 1 : 0 );
690
691 // Duplicate the XPt.
692 sxpt = VG_(malloc)(sizeof(SXPt));
693 n_sxpt_allocs++;
694 sxpt->tag = SigSXPt;
695 sxpt->szB = xpt->szB;
696 sxpt->Sig.ip = xpt->ip;
697 sxpt->Sig.n_children = n_child_sxpts;
698
699 // Create the SXPt's children.
700 if (n_child_sxpts > 0) {
701 Int j;
702 SizeT sig_children_szB = 0;
703 sxpt->Sig.children = VG_(malloc)(n_child_sxpts * sizeof(SXPt*));
704
705 // Duplicate the significant children.
706 j = 0;
707 for (i = 0; i < xpt->n_children; i++) {
708 if (xpt->children[i]->szB >= sig_child_threshold_szB) {
709 sxpt->Sig.children[j++] = dup_XTree(xpt->children[i], total_szB);
710 sig_children_szB += xpt->children[i]->szB;
711 }
712 }
713
714 // Create the SXPt for the insignificant children, if any, and put it
715 // in the last child entry.
716 insig_children_szB = sxpt->szB - sig_children_szB;
717 if (n_insig_children > 0) {
718 // Nb: We 'n_sxpt_allocs' here because creating an Insig SXPt
719 // doesn't involve a call to dup_XTree().
720 SXPt* insig_sxpt = VG_(malloc)(sizeof(SXPt));
721 n_sxpt_allocs++;
722 insig_sxpt->tag = InsigSXPt;
723 insig_sxpt->szB = insig_children_szB;
724 insig_sxpt->Insig.n_xpts = n_insig_children;
725 sxpt->Sig.children[n_sig_children] = insig_sxpt;
726 }
727 } else {
728 sxpt->Sig.children = NULL;
729 }
730
731 return sxpt;
732}
733
734static void free_SXTree(SXPt* sxpt)
735{
736 Int i;
737 tl_assert(sxpt != NULL);
738
739 switch (sxpt->tag) {
740 case SigSXPt:
741 // Free all children SXPts, then the children array.
742 for (i = 0; i < sxpt->Sig.n_children; i++) {
743 free_SXTree(sxpt->Sig.children[i]);
744 sxpt->Sig.children[i] = NULL;
745 }
746 VG_(free)(sxpt->Sig.children); sxpt->Sig.children = NULL;
747 break;
748
749 case InsigSXPt:
750 break;
751
752 default: tl_assert2(0, "free_SXTree: unknown SXPt tag");
753 }
754
755 // Free the SXPt itself.
756 VG_(free)(sxpt); sxpt = NULL;
757 n_sxpt_frees++;
758}
759
760// Sanity checking: we periodically check the heap XTree with
761// ms_expensive_sanity_check.
762static void sanity_check_XTree(XPt* xpt, XPt* parent)
nethercotec9f36922004-02-14 16:40:02 +0000763{
764 Int i;
765
njn734b8052007-11-01 04:40:37 +0000766 tl_assert(xpt != NULL);
767
768 // Check back-pointer.
769 tl_assert2(xpt->parent == parent,
770 "xpt->parent = %p, parent = %p\n", xpt->parent, parent);
771
772 // Check children counts look sane.
773 tl_assert(xpt->n_children <= xpt->max_children);
774
775 // Check the sum of any children szBs equals the XPt's szB. Check the
776 // children at the same time.
777 if (xpt->n_children > 0) {
778 SizeT children_sum_szB = 0;
779 for (i = 0; i < xpt->n_children; i++) {
780 sanity_check_XTree(xpt->children[i], xpt);
781 children_sum_szB += xpt->children[i]->szB;
nethercotec9f36922004-02-14 16:40:02 +0000782 }
njn734b8052007-11-01 04:40:37 +0000783 tl_assert(children_sum_szB == xpt->szB);
nethercotec9f36922004-02-14 16:40:02 +0000784 }
nethercotec9f36922004-02-14 16:40:02 +0000785}
786
njn734b8052007-11-01 04:40:37 +0000787// Sanity checking: we check SXTrees (which are in snapshots) after
788// snapshots are created, before they are deleted, and before they are
789// printed.
790static void sanity_check_SXTree(SXPt* sxpt)
nethercotec9f36922004-02-14 16:40:02 +0000791{
njn734b8052007-11-01 04:40:37 +0000792 Int i;
nethercotec9f36922004-02-14 16:40:02 +0000793
njn734b8052007-11-01 04:40:37 +0000794 tl_assert(sxpt != NULL);
nethercotec9f36922004-02-14 16:40:02 +0000795
njn734b8052007-11-01 04:40:37 +0000796 // Check the sum of any children szBs equals the SXPt's szB. Check the
797 // children at the same time.
798 switch (sxpt->tag) {
799 case SigSXPt: {
800 if (sxpt->Sig.n_children > 0) {
801 SizeT children_sum_szB = 0;
802 for (i = 0; i < sxpt->Sig.n_children; i++) {
803 sanity_check_SXTree(sxpt->Sig.children[i]);
804 children_sum_szB += sxpt->Sig.children[i]->szB;
805 }
806 tl_assert(children_sum_szB == sxpt->szB);
807 }
808 break;
809 }
810 case InsigSXPt:
811 break; // do nothing
812
813 default: tl_assert2(0, "sanity_check_SXTree: unknown SXPt tag");
814 }
815}
816
817
818//------------------------------------------------------------//
819//--- XCon Operations ---//
820//------------------------------------------------------------//
821
822// This is the limit on the number of removed alloc-fns that can be in a
823// single XCon.
824#define MAX_OVERESTIMATE 50
825#define MAX_IPS (MAX_DEPTH + MAX_OVERESTIMATE)
826
827// Get the stack trace for an XCon, filtering out uninteresting entries:
828// alloc-fns and entries above alloc-fns, and entries below main-or-below-main.
829// Eg: alloc-fn1 / alloc-fn2 / a / b / main / (below main) / c
830// becomes: a / b / main
831// Nb: it's possible to end up with an empty trace, eg. if 'main' is marked
832// as an alloc-fn. This is ok.
833static
834Int get_IPs( ThreadId tid, Bool is_custom_alloc, Addr ips[])
835{
836 #define BUF_LEN 1024
837 Char buf[BUF_LEN];
838 Int n_ips, i, n_alloc_fns_removed;
839 Int overestimate;
840 Bool redo;
841
842 // We ask for a few more IPs than clo_depth suggests we need. Then we
843 // remove every entry that is an alloc-fn. Depending on the
844 // circumstances, we may need to redo it all, asking for more IPs.
845 // Details:
846 // - If the original stack trace is smaller than asked-for, redo=False
847 // - Else if after filtering we have >= clo_depth IPs, redo=False
848 // - Else redo=True
849 // In other words, to redo, we'd have to get a stack trace as big as we
850 // asked for and remove more than 'overestimate' alloc-fns.
851
852 // Main loop.
853 redo = True; // Assume this to begin with.
854 for (overestimate = 3; redo; overestimate += 6) {
855 // This should never happen -- would require MAX_OVERESTIMATE
856 // alloc-fns to be removed from the stack trace.
857 if (overestimate > MAX_OVERESTIMATE)
858 VG_(tool_panic)("get_IPs: ips[] too small, inc. MAX_OVERESTIMATE?");
859
860 // Ask for more IPs than clo_depth suggests we need.
sewardj39f34232007-11-09 23:02:28 +0000861 n_ips = VG_(get_StackTrace)( tid, ips, clo_depth + overestimate,
862 0/*first_ip_delta*/ );
njn734b8052007-11-01 04:40:37 +0000863 tl_assert(n_ips > 0);
nethercotec9f36922004-02-14 16:40:02 +0000864
njn734b8052007-11-01 04:40:37 +0000865 // If the original stack trace is smaller than asked-for, redo=False.
866 if (n_ips < clo_depth + overestimate) { redo = False; }
nethercotec9f36922004-02-14 16:40:02 +0000867
njn734b8052007-11-01 04:40:37 +0000868 // If it's a non-custom block, we will always remove the first stack
869 // trace entry (which will be one of malloc, __builtin_new, etc).
870 n_alloc_fns_removed = ( is_custom_alloc ? 0 : 1 );
nethercotec9f36922004-02-14 16:40:02 +0000871
njn734b8052007-11-01 04:40:37 +0000872 // Filter out alloc fns. If it's a non-custom block, we remove the
873 // first entry (which will be one of malloc, __builtin_new, etc)
874 // without looking at it, because VG_(get_fnname) is expensive (it
875 // involves calls to VG_(malloc)/VG_(free)).
876 for (i = n_alloc_fns_removed; i < n_ips; i++) {
877 if (VG_(get_fnname)(ips[i], buf, BUF_LEN)) {
878 if (is_alloc_fn(buf)) {
879 n_alloc_fns_removed++;
880 } else {
881 break;
882 }
883 }
884 }
885 // Remove the alloc fns by shuffling the rest down over them.
886 n_ips -= n_alloc_fns_removed;
887 for (i = 0; i < n_ips; i++) {
888 ips[i] = ips[i + n_alloc_fns_removed];
889 }
nethercotec9f36922004-02-14 16:40:02 +0000890
njn734b8052007-11-01 04:40:37 +0000891 // If after filtering we have >= clo_depth IPs, redo=False
892 if (n_ips >= clo_depth) {
893 redo = False;
894 n_ips = clo_depth; // Ignore any IPs below --depth.
895 }
896
897 if (redo) {
898 n_XCon_redos++;
nethercotec9f36922004-02-14 16:40:02 +0000899 }
900 }
njn734b8052007-11-01 04:40:37 +0000901 return n_ips;
902}
nethercotec9f36922004-02-14 16:40:02 +0000903
njn734b8052007-11-01 04:40:37 +0000904// Gets an XCon and puts it in the tree. Returns the XCon's bottom-XPt.
905static XPt* get_XCon( ThreadId tid, Bool is_custom_alloc )
906{
907 Addr ips[MAX_IPS];
908 Int i;
909 XPt* xpt = alloc_xpt;
nethercotec9f36922004-02-14 16:40:02 +0000910
njn734b8052007-11-01 04:40:37 +0000911 // After this call, the IPs we want are in ips[0]..ips[n_ips-1].
912 Int n_ips = get_IPs(tid, is_custom_alloc, ips);
913
914 // Now do the search/insertion of the XCon.
915 for (i = 0; i < n_ips; i++) {
916 Addr ip = ips[i];
917 Int ch;
njnd01fef72005-03-25 23:35:48 +0000918 // Look for IP in xpt's children.
njn734b8052007-11-01 04:40:37 +0000919 // Linear search, ugh -- about 10% of time for konqueror startup tried
920 // caching last result, only hit about 4% for konqueror.
nethercotec9f36922004-02-14 16:40:02 +0000921 // Nb: this search hits about 98% of the time for konqueror
njn734b8052007-11-01 04:40:37 +0000922 for (ch = 0; True; ch++) {
923 if (ch == xpt->n_children) {
924 // IP not found in the children.
925 // Create and add new child XPt, then stop.
926 XPt* new_child_xpt = new_XPt(ip, xpt);
927 add_child_xpt(xpt, new_child_xpt);
928 xpt = new_child_xpt;
929 break;
nethercotec9f36922004-02-14 16:40:02 +0000930
njn734b8052007-11-01 04:40:37 +0000931 } else if (ip == xpt->children[ch]->ip) {
932 // Found the IP in the children, stop.
933 xpt = xpt->children[ch];
nethercotec9f36922004-02-14 16:40:02 +0000934 break;
935 }
nethercotec9f36922004-02-14 16:40:02 +0000936 }
nethercotec9f36922004-02-14 16:40:02 +0000937 }
njn734b8052007-11-01 04:40:37 +0000938 tl_assert(0 == xpt->n_children); // Must be bottom-XPt
939 return xpt;
nethercotec9f36922004-02-14 16:40:02 +0000940}
941
njn734b8052007-11-01 04:40:37 +0000942// Update 'szB' of every XPt in the XCon, by percolating upwards.
943static void update_XCon(XPt* xpt, SSizeT space_delta)
nethercotec9f36922004-02-14 16:40:02 +0000944{
njnca82cc02004-11-22 17:18:48 +0000945 tl_assert(True == clo_heap);
njnca82cc02004-11-22 17:18:48 +0000946 tl_assert(NULL != xpt);
947 tl_assert(0 == xpt->n_children); // must be bottom-XPt
nethercotec9f36922004-02-14 16:40:02 +0000948
njn734b8052007-11-01 04:40:37 +0000949 if (0 == space_delta)
950 return;
951
nethercotec9f36922004-02-14 16:40:02 +0000952 while (xpt != alloc_xpt) {
njn734b8052007-11-01 04:40:37 +0000953 if (space_delta < 0) tl_assert(xpt->szB >= -space_delta);
954 xpt->szB += space_delta;
nethercotec9f36922004-02-14 16:40:02 +0000955 xpt = xpt->parent;
njn734b8052007-11-01 04:40:37 +0000956 }
957 if (space_delta < 0) tl_assert(alloc_xpt->szB >= -space_delta);
958 alloc_xpt->szB += space_delta;
nethercotec9f36922004-02-14 16:40:02 +0000959}
960
961
njn734b8052007-11-01 04:40:37 +0000962//------------------------------------------------------------//
963//--- Snapshots ---//
964//------------------------------------------------------------//
965
966// Snapshots are done in a way so that we always have a reasonable number of
967// them. We start by taking them quickly. Once we hit our limit, we cull
968// some (eg. half), and start taking them more slowly. Once we hit the
969// limit again, we again cull and then take them even more slowly, and so
970// on.
971
njn1a2741a2007-11-26 21:59:04 +0000972// Time is measured either in i or ms or bytes, depending on the --time-unit
njn734b8052007-11-01 04:40:37 +0000973// option. It's a Long because it can exceed 32-bits reasonably easily, and
974// because we need to allow negative values to represent unset times.
975typedef Long Time;
976
977#define UNUSED_SNAPSHOT_TIME -333 // A conspicuous negative number.
978
979typedef
980 enum {
981 Normal = 77,
982 Peak,
983 Unused
984 }
985 SnapshotKind;
nethercotec9f36922004-02-14 16:40:02 +0000986
987typedef
988 struct {
njn734b8052007-11-01 04:40:37 +0000989 SnapshotKind kind;
990 Time time;
991 SizeT heap_szB;
njn32397c02007-11-10 04:08:08 +0000992 SizeT heap_extra_szB;// Heap slop + admin bytes.
njn734b8052007-11-01 04:40:37 +0000993 SizeT stacks_szB;
994 SXPt* alloc_sxpt; // Heap XTree root, if a detailed snapshot,
njn32397c02007-11-10 04:08:08 +0000995 } // otherwise NULL.
njn734b8052007-11-01 04:40:37 +0000996 Snapshot;
nethercotec9f36922004-02-14 16:40:02 +0000997
njn734b8052007-11-01 04:40:37 +0000998static UInt next_snapshot_i = 0; // Index of where next snapshot will go.
999static Snapshot* snapshots; // Array of snapshots.
1000
1001static Bool is_snapshot_in_use(Snapshot* snapshot)
nethercotec9f36922004-02-14 16:40:02 +00001002{
njn734b8052007-11-01 04:40:37 +00001003 if (Unused == snapshot->kind) {
1004 // If snapshot is unused, check all the fields are unset.
1005 tl_assert(snapshot->time == UNUSED_SNAPSHOT_TIME);
njn32397c02007-11-10 04:08:08 +00001006 tl_assert(snapshot->heap_extra_szB == 0);
njn734b8052007-11-01 04:40:37 +00001007 tl_assert(snapshot->heap_szB == 0);
1008 tl_assert(snapshot->stacks_szB == 0);
1009 tl_assert(snapshot->alloc_sxpt == NULL);
1010 return False;
nethercotec9f36922004-02-14 16:40:02 +00001011 } else {
njn734b8052007-11-01 04:40:37 +00001012 tl_assert(snapshot->time != UNUSED_SNAPSHOT_TIME);
1013 return True;
nethercotec9f36922004-02-14 16:40:02 +00001014 }
1015}
1016
njn734b8052007-11-01 04:40:37 +00001017static Bool is_detailed_snapshot(Snapshot* snapshot)
nethercotec9f36922004-02-14 16:40:02 +00001018{
njn734b8052007-11-01 04:40:37 +00001019 return (snapshot->alloc_sxpt ? True : False);
nethercotec9f36922004-02-14 16:40:02 +00001020}
1021
njn734b8052007-11-01 04:40:37 +00001022static Bool is_uncullable_snapshot(Snapshot* snapshot)
nethercotec9f36922004-02-14 16:40:02 +00001023{
njn734b8052007-11-01 04:40:37 +00001024 return &snapshots[0] == snapshot // First snapshot
1025 || &snapshots[next_snapshot_i-1] == snapshot // Last snapshot
1026 || snapshot->kind == Peak; // Peak snapshot
nethercotec9f36922004-02-14 16:40:02 +00001027}
1028
njn734b8052007-11-01 04:40:37 +00001029static void sanity_check_snapshot(Snapshot* snapshot)
nethercotec9f36922004-02-14 16:40:02 +00001030{
njn734b8052007-11-01 04:40:37 +00001031 if (snapshot->alloc_sxpt) {
1032 sanity_check_SXTree(snapshot->alloc_sxpt);
1033 }
nethercotec9f36922004-02-14 16:40:02 +00001034}
1035
njn734b8052007-11-01 04:40:37 +00001036// All the used entries should look used, all the unused ones should be clear.
1037static void sanity_check_snapshots_array(void)
1038{
1039 Int i;
1040 for (i = 0; i < next_snapshot_i; i++) {
1041 tl_assert( is_snapshot_in_use( & snapshots[i] ));
1042 }
1043 for ( ; i < clo_max_snapshots; i++) {
1044 tl_assert(!is_snapshot_in_use( & snapshots[i] ));
1045 }
1046}
nethercotec9f36922004-02-14 16:40:02 +00001047
njn734b8052007-11-01 04:40:37 +00001048// This zeroes all the fields in the snapshot, but does not free the heap
1049// XTree if present. It also does a sanity check unless asked not to; we
1050// can't sanity check at startup when clearing the initial snapshots because
1051// they're full of junk.
1052static void clear_snapshot(Snapshot* snapshot, Bool do_sanity_check)
1053{
1054 if (do_sanity_check) sanity_check_snapshot(snapshot);
1055 snapshot->kind = Unused;
1056 snapshot->time = UNUSED_SNAPSHOT_TIME;
njn32397c02007-11-10 04:08:08 +00001057 snapshot->heap_extra_szB = 0;
njn734b8052007-11-01 04:40:37 +00001058 snapshot->heap_szB = 0;
1059 snapshot->stacks_szB = 0;
1060 snapshot->alloc_sxpt = NULL;
1061}
1062
1063// This zeroes all the fields in the snapshot, and frees the heap XTree if
1064// present.
1065static void delete_snapshot(Snapshot* snapshot)
1066{
1067 // Nb: if there's an XTree, we free it after calling clear_snapshot,
1068 // because clear_snapshot does a sanity check which includes checking the
1069 // XTree.
1070 SXPt* tmp_sxpt = snapshot->alloc_sxpt;
1071 clear_snapshot(snapshot, /*do_sanity_check*/True);
1072 if (tmp_sxpt) {
1073 free_SXTree(tmp_sxpt);
1074 }
1075}
1076
1077static void VERB_snapshot(Int verbosity, Char* prefix, Int i)
1078{
1079 Snapshot* snapshot = &snapshots[i];
1080 Char* suffix;
1081 switch (snapshot->kind) {
1082 case Peak: suffix = "p"; break;
1083 case Normal: suffix = ( is_detailed_snapshot(snapshot) ? "d" : "." ); break;
1084 case Unused: suffix = "u"; break;
1085 default:
1086 tl_assert2(0, "VERB_snapshot: unknown snapshot kind: %d", snapshot->kind);
1087 }
njn32397c02007-11-10 04:08:08 +00001088 VERB(verbosity, "%s S%s%3d (t:%lld, hp:%ld, ex:%ld, st:%ld)",
njn734b8052007-11-01 04:40:37 +00001089 prefix, suffix, i,
1090 snapshot->time,
1091 snapshot->heap_szB,
njn32397c02007-11-10 04:08:08 +00001092 snapshot->heap_extra_szB,
njn734b8052007-11-01 04:40:37 +00001093 snapshot->stacks_szB
1094 );
1095}
1096
1097// Cull half the snapshots; we choose those that represent the smallest
1098// time-spans, because that gives us the most even distribution of snapshots
1099// over time. (It's possible to lose interesting spikes, however.)
1100//
1101// Algorithm for N snapshots: We find the snapshot representing the smallest
1102// timeframe, and remove it. We repeat this until (N/2) snapshots are gone.
1103// We have to do this one snapshot at a time, rather than finding the (N/2)
1104// smallest snapshots in one hit, because when a snapshot is removed, its
1105// neighbours immediately cover greater timespans. So it's O(N^2), but N is
1106// small, and it's not done very often.
1107//
1108// Once we're done, we return the new smallest interval between snapshots.
1109// That becomes our minimum time interval.
1110static UInt cull_snapshots(void)
1111{
1112 Int i, jp, j, jn, min_timespan_i;
1113 Int n_deleted = 0;
1114 Time min_timespan;
1115
1116 n_cullings++;
1117
1118 // Sets j to the index of the first not-yet-removed snapshot at or after i
1119 #define FIND_SNAPSHOT(i, j) \
1120 for (j = i; \
1121 j < clo_max_snapshots && !is_snapshot_in_use(&snapshots[j]); \
1122 j++) { }
1123
1124 VERB(2, "Culling...");
1125
1126 // First we remove enough snapshots by clearing them in-place. Once
1127 // that's done, we can slide the remaining ones down.
1128 for (i = 0; i < clo_max_snapshots/2; i++) {
1129 // Find the snapshot representing the smallest timespan. The timespan
1130 // for snapshot n = d(N-1,N)+d(N,N+1), where d(A,B) is the time between
1131 // snapshot A and B. We don't consider the first and last snapshots for
1132 // removal.
1133 Snapshot* min_snapshot;
1134 Int min_j;
1135
1136 // Initial triple: (prev, curr, next) == (jp, j, jn)
1137 // Initial min_timespan is the first one.
1138 jp = 0;
1139 FIND_SNAPSHOT(1, j);
1140 FIND_SNAPSHOT(j+1, jn);
1141 min_timespan = 0x7fffffffffffffffLL;
1142 min_j = -1;
1143 while (jn < clo_max_snapshots) {
1144 Time timespan = snapshots[jn].time - snapshots[jp].time;
1145 tl_assert(timespan >= 0);
1146 // Nb: We never cull the peak snapshot.
1147 if (Peak != snapshots[j].kind && timespan < min_timespan) {
1148 min_timespan = timespan;
1149 min_j = j;
1150 }
1151 // Move on to next triple
1152 jp = j;
1153 j = jn;
1154 FIND_SNAPSHOT(jn+1, jn);
1155 }
1156 // We've found the least important snapshot, now delete it. First
1157 // print it if necessary.
1158 tl_assert(-1 != min_j); // Check we found a minimum.
1159 min_snapshot = & snapshots[ min_j ];
1160 if (VG_(clo_verbosity) > 1) {
1161 Char buf[64];
1162 VG_(snprintf)(buf, 64, " %3d (t-span = %lld)", i, min_timespan);
1163 VERB_snapshot(2, buf, min_j);
1164 }
1165 delete_snapshot(min_snapshot);
1166 n_deleted++;
1167 }
1168
1169 // Slide down the remaining snapshots over the removed ones. First set i
1170 // to point to the first empty slot, and j to the first full slot after
1171 // i. Then slide everything down.
1172 for (i = 0; is_snapshot_in_use( &snapshots[i] ); i++) { }
1173 for (j = i; !is_snapshot_in_use( &snapshots[j] ); j++) { }
1174 for ( ; j < clo_max_snapshots; j++) {
1175 if (is_snapshot_in_use( &snapshots[j] )) {
1176 snapshots[i++] = snapshots[j];
1177 clear_snapshot(&snapshots[j], /*do_sanity_check*/True);
1178 }
1179 }
1180 next_snapshot_i = i;
1181
1182 // Check snapshots array looks ok after changes.
1183 sanity_check_snapshots_array();
1184
1185 // Find the minimum timespan remaining; that will be our new minimum
1186 // time interval. Note that above we were finding timespans by measuring
1187 // two intervals around a snapshot that was under consideration for
1188 // deletion. Here we only measure single intervals because all the
1189 // deletions have occurred.
1190 //
1191 // But we have to be careful -- some snapshots (eg. snapshot 0, and the
1192 // peak snapshot) are uncullable. If two uncullable snapshots end up
1193 // next to each other, they'll never be culled (assuming the peak doesn't
1194 // change), and the time gap between them will not change. However, the
1195 // time between the remaining cullable snapshots will grow ever larger.
1196 // This means that the min_timespan found will always be that between the
1197 // two uncullable snapshots, and it will be much smaller than it should
1198 // be. To avoid this problem, when computing the minimum timespan, we
1199 // ignore any timespans between two uncullable snapshots.
1200 tl_assert(next_snapshot_i > 1);
1201 min_timespan = 0x7fffffffffffffffLL;
1202 min_timespan_i = -1;
1203 for (i = 1; i < next_snapshot_i; i++) {
1204 if (is_uncullable_snapshot(&snapshots[i]) &&
1205 is_uncullable_snapshot(&snapshots[i-1]))
1206 {
1207 VERB(2, "(Ignoring interval %d--%d when computing minimum)", i-1, i);
1208 } else {
1209 Time timespan = snapshots[i].time - snapshots[i-1].time;
1210 tl_assert(timespan >= 0);
1211 if (timespan < min_timespan) {
1212 min_timespan = timespan;
1213 min_timespan_i = i;
1214 }
1215 }
1216 }
1217 tl_assert(-1 != min_timespan_i); // Check we found a minimum.
1218
1219 // Print remaining snapshots, if necessary.
1220 if (VG_(clo_verbosity) > 1) {
1221 VERB(2, "Finished culling (%3d of %3d deleted)",
1222 n_deleted, clo_max_snapshots);
1223 for (i = 0; i < next_snapshot_i; i++) {
1224 VERB_snapshot(2, " post-cull", i);
1225 }
1226 VERB(2, "New time interval = %lld (between snapshots %d and %d)",
1227 min_timespan, min_timespan_i-1, min_timespan_i);
1228 }
1229
1230 return min_timespan;
1231}
1232
1233static Time get_time(void)
1234{
1235 // Get current time, in whatever time unit we're using.
njn1a2741a2007-11-26 21:59:04 +00001236 if (clo_time_unit == TimeI) {
1237 return guest_instrs_executed;
1238 } else if (clo_time_unit == TimeMS) {
njn734b8052007-11-01 04:40:37 +00001239 // Some stuff happens between the millisecond timer being initialised
1240 // to zero and us taking our first snapshot. We determine that time
1241 // gap so we can subtract it from all subsequent times so that our
1242 // first snapshot is considered to be at t = 0ms. Unfortunately, a
1243 // bunch of symbols get read after the first snapshot is taken but
1244 // before the second one (which is triggered by the first allocation),
1245 // so when the time-unit is 'ms' we always have a big gap between the
1246 // first two snapshots. But at least users won't have to wonder why
1247 // the first snapshot isn't at t=0.
1248 static Bool is_first_get_time = True;
1249 static Time start_time_ms;
1250 if (is_first_get_time) {
1251 start_time_ms = VG_(read_millisecond_timer)();
1252 is_first_get_time = False;
1253 return 0;
1254 } else {
1255 return VG_(read_millisecond_timer)() - start_time_ms;
1256 }
1257 } else if (clo_time_unit == TimeB) {
1258 return total_allocs_deallocs_szB;
1259 } else {
1260 tl_assert2(0, "bad --time-unit value");
1261 }
1262}
1263
1264// Take a snapshot, and only that -- decisions on whether to take a
1265// snapshot, or what kind of snapshot, are made elsewhere.
1266static void
1267take_snapshot(Snapshot* snapshot, SnapshotKind kind, Time time,
1268 Bool is_detailed, Char* what)
1269{
1270 tl_assert(!is_snapshot_in_use(snapshot));
1271 tl_assert(have_started_executing_code);
1272
1273 // Heap and heap admin.
1274 if (clo_heap) {
1275 snapshot->heap_szB = heap_szB;
1276 if (is_detailed) {
njn32397c02007-11-10 04:08:08 +00001277 SizeT total_szB = heap_szB + heap_extra_szB + stacks_szB;
njn734b8052007-11-01 04:40:37 +00001278 snapshot->alloc_sxpt = dup_XTree(alloc_xpt, total_szB);
1279 tl_assert( alloc_xpt->szB == heap_szB);
1280 tl_assert(snapshot->alloc_sxpt->szB == heap_szB);
1281 }
njn32397c02007-11-10 04:08:08 +00001282 snapshot->heap_extra_szB = heap_extra_szB;
njn734b8052007-11-01 04:40:37 +00001283 }
1284
1285 // Stack(s).
1286 if (clo_stacks) {
1287 snapshot->stacks_szB = stacks_szB;
1288 }
1289
1290 // Rest of snapshot.
1291 snapshot->kind = kind;
1292 snapshot->time = time;
1293 sanity_check_snapshot(snapshot);
1294
1295 // Update stats.
1296 if (Peak == kind) n_peak_snapshots++;
1297 if (is_detailed) n_detailed_snapshots++;
1298 n_real_snapshots++;
1299}
1300
1301
1302// Take a snapshot, if it's time, or if we've hit a peak.
1303static void
1304maybe_take_snapshot(SnapshotKind kind, Char* what)
1305{
1306 // 'min_time_interval' is the minimum time interval between snapshots.
1307 // If we try to take a snapshot and less than this much time has passed,
1308 // we don't take it. It gets larger as the program runs longer. It's
1309 // initialised to zero so that we begin by taking snapshots as quickly as
1310 // possible.
1311 static Time min_time_interval = 0;
1312 // Zero allows startup snapshot.
1313 static Time earliest_possible_time_of_next_snapshot = 0;
1314 static Int n_snapshots_since_last_detailed = 0;
1315 static Int n_skipped_snapshots_since_last_snapshot = 0;
1316
1317 Snapshot* snapshot;
1318 Bool is_detailed;
1319 Time time = get_time();
1320
1321 switch (kind) {
1322 case Normal:
1323 // Only do a snapshot if it's time.
1324 if (time < earliest_possible_time_of_next_snapshot) {
1325 n_skipped_snapshots++;
1326 n_skipped_snapshots_since_last_snapshot++;
1327 return;
1328 }
1329 is_detailed = (clo_detailed_freq-1 == n_snapshots_since_last_detailed);
1330 break;
1331
1332 case Peak: {
1333 // Because we're about to do a deallocation, we're coming down from a
1334 // local peak. If it is (a) actually a global peak, and (b) a certain
1335 // amount bigger than the previous peak, then we take a peak snapshot.
1336 // By not taking a snapshot for every peak, we save a lot of effort --
1337 // because many peaks remain peak only for a short time.
njn32397c02007-11-10 04:08:08 +00001338 SizeT total_szB = heap_szB + heap_extra_szB + stacks_szB;
njn734b8052007-11-01 04:40:37 +00001339 SizeT excess_szB_for_new_peak =
njn62721e92007-11-11 22:15:58 +00001340 (SizeT)((peak_snapshot_total_szB * clo_peak_inaccuracy) / 100);
njn734b8052007-11-01 04:40:37 +00001341 if (total_szB <= peak_snapshot_total_szB + excess_szB_for_new_peak) {
1342 return;
1343 }
1344 is_detailed = True;
1345 break;
1346 }
1347
1348 default:
1349 tl_assert2(0, "maybe_take_snapshot: unrecognised snapshot kind");
1350 }
1351
1352 // Take the snapshot.
1353 snapshot = & snapshots[next_snapshot_i];
1354 take_snapshot(snapshot, kind, time, is_detailed, what);
1355
1356 // Record if it was detailed.
1357 if (is_detailed) {
1358 n_snapshots_since_last_detailed = 0;
1359 } else {
1360 n_snapshots_since_last_detailed++;
1361 }
1362
1363 // Update peak data, if it's a Peak snapshot.
1364 if (Peak == kind) {
1365 Int i, number_of_peaks_snapshots_found = 0;
1366
1367 // Sanity check the size, then update our recorded peak.
1368 SizeT snapshot_total_szB =
njn32397c02007-11-10 04:08:08 +00001369 snapshot->heap_szB + snapshot->heap_extra_szB + snapshot->stacks_szB;
njn734b8052007-11-01 04:40:37 +00001370 tl_assert2(snapshot_total_szB > peak_snapshot_total_szB,
1371 "%ld, %ld\n", snapshot_total_szB, peak_snapshot_total_szB);
1372 peak_snapshot_total_szB = snapshot_total_szB;
1373
1374 // Find the old peak snapshot, if it exists, and mark it as normal.
1375 for (i = 0; i < next_snapshot_i; i++) {
1376 if (Peak == snapshots[i].kind) {
1377 snapshots[i].kind = Normal;
1378 number_of_peaks_snapshots_found++;
1379 }
1380 }
1381 tl_assert(number_of_peaks_snapshots_found <= 1);
1382 }
1383
1384 // Finish up verbosity and stats stuff.
1385 if (n_skipped_snapshots_since_last_snapshot > 0) {
1386 VERB(2, " (skipped %d snapshot%s)",
1387 n_skipped_snapshots_since_last_snapshot,
1388 ( n_skipped_snapshots_since_last_snapshot == 1 ? "" : "s") );
1389 }
1390 VERB_snapshot(2, what, next_snapshot_i);
1391 n_skipped_snapshots_since_last_snapshot = 0;
1392
1393 // Cull the entries, if our snapshot table is full.
1394 next_snapshot_i++;
1395 if (clo_max_snapshots == next_snapshot_i) {
1396 min_time_interval = cull_snapshots();
1397 }
1398
1399 // Work out the earliest time when the next snapshot can happen.
1400 earliest_possible_time_of_next_snapshot = time + min_time_interval;
1401}
1402
1403
1404//------------------------------------------------------------//
1405//--- Sanity checking ---//
1406//------------------------------------------------------------//
1407
1408static Bool ms_cheap_sanity_check ( void )
1409{
1410 return True; // Nothing useful we can cheaply check.
1411}
1412
1413static Bool ms_expensive_sanity_check ( void )
1414{
1415 sanity_check_XTree(alloc_xpt, /*parent*/NULL);
1416 sanity_check_snapshots_array();
1417 return True;
1418}
1419
1420
1421//------------------------------------------------------------//
1422//--- Heap management ---//
1423//------------------------------------------------------------//
1424
1425// Metadata for heap blocks. Each one contains a pointer to a bottom-XPt,
1426// which is a foothold into the XCon at which it was allocated. From
1427// HP_Chunks, XPt 'space' fields are incremented (at allocation) and
1428// decremented (at deallocation).
1429//
1430// Nb: first two fields must match core's VgHashNode.
1431typedef
1432 struct _HP_Chunk {
1433 struct _HP_Chunk* next;
njn32397c02007-11-10 04:08:08 +00001434 Addr data; // Ptr to actual block
1435 SizeT req_szB; // Size requested
1436 SizeT slop_szB; // Extra bytes given above those requested
1437 XPt* where; // Where allocated; bottom-XPt
njn734b8052007-11-01 04:40:37 +00001438 }
1439 HP_Chunk;
1440
1441static VgHashTable malloc_list = NULL; // HP_Chunks
1442
1443static void update_alloc_stats(SSizeT szB_delta)
1444{
1445 // Update total_allocs_deallocs_szB.
1446 if (szB_delta < 0) szB_delta = -szB_delta;
1447 total_allocs_deallocs_szB += szB_delta;
1448}
1449
njn32397c02007-11-10 04:08:08 +00001450static void update_heap_stats(SSizeT heap_szB_delta, Int heap_extra_szB_delta)
njn734b8052007-11-01 04:40:37 +00001451{
njn32397c02007-11-10 04:08:08 +00001452 if (heap_szB_delta < 0)
1453 tl_assert(heap_szB >= -heap_szB_delta);
1454 if (heap_extra_szB_delta < 0)
1455 tl_assert(heap_extra_szB >= -heap_extra_szB_delta);
njn734b8052007-11-01 04:40:37 +00001456
njn32397c02007-11-10 04:08:08 +00001457 heap_extra_szB += heap_extra_szB_delta;
1458 heap_szB += heap_szB_delta;
1459
1460 update_alloc_stats(heap_szB_delta + heap_extra_szB_delta);
njn734b8052007-11-01 04:40:37 +00001461}
nethercotec9f36922004-02-14 16:40:02 +00001462
nethercote159dfef2004-09-13 13:27:30 +00001463static
njn32397c02007-11-10 04:08:08 +00001464void* new_block ( ThreadId tid, void* p, SizeT req_szB, SizeT req_alignB,
njn57735902004-11-25 18:04:54 +00001465 Bool is_zeroed )
nethercotec9f36922004-02-14 16:40:02 +00001466{
1467 HP_Chunk* hc;
njn734b8052007-11-01 04:40:37 +00001468 Bool is_custom_alloc = (NULL != p);
njn32397c02007-11-10 04:08:08 +00001469 SizeT actual_szB, slop_szB;
1470
1471 if (req_szB < 0) return NULL;
nethercotec9f36922004-02-14 16:40:02 +00001472
nethercote57e36b32004-07-10 14:56:28 +00001473 // Allocate and zero if necessary
1474 if (!p) {
njn32397c02007-11-10 04:08:08 +00001475 p = VG_(cli_malloc)( req_alignB, req_szB );
nethercote57e36b32004-07-10 14:56:28 +00001476 if (!p) {
nethercote57e36b32004-07-10 14:56:28 +00001477 return NULL;
1478 }
njn32397c02007-11-10 04:08:08 +00001479 if (is_zeroed) VG_(memset)(p, 0, req_szB);
1480 actual_szB = VG_(malloc_usable_size)(p);
1481 tl_assert(actual_szB >= req_szB);
1482 slop_szB = actual_szB - req_szB;
1483 } else {
1484 slop_szB = 0;
nethercote57e36b32004-07-10 14:56:28 +00001485 }
1486
njnf1c5def2005-08-11 02:17:07 +00001487 // Make new HP_Chunk node, add to malloc_list
njn32397c02007-11-10 04:08:08 +00001488 hc = VG_(malloc)(sizeof(HP_Chunk));
1489 hc->req_szB = req_szB;
1490 hc->slop_szB = slop_szB;
1491 hc->data = (Addr)p;
1492 hc->where = NULL;
njn246a9d22005-08-14 06:24:20 +00001493 VG_(HT_add_node)(malloc_list, hc);
nethercote57e36b32004-07-10 14:56:28 +00001494
njn734b8052007-11-01 04:40:37 +00001495 if (clo_heap) {
njn32397c02007-11-10 04:08:08 +00001496 VERB(3, "<<< new_mem_heap (%lu, %lu)", req_szB, slop_szB);
njn734b8052007-11-01 04:40:37 +00001497
1498 // Update statistics.
1499 n_heap_allocs++;
1500
1501 // Update heap stats.
njn32397c02007-11-10 04:08:08 +00001502 update_heap_stats(req_szB, clo_heap_admin + slop_szB);
njn734b8052007-11-01 04:40:37 +00001503
1504 // Update XTree.
1505 hc->where = get_XCon( tid, is_custom_alloc );
njn32397c02007-11-10 04:08:08 +00001506 update_XCon(hc->where, req_szB);
njn734b8052007-11-01 04:40:37 +00001507
1508 // Maybe take a snapshot.
1509 maybe_take_snapshot(Normal, " alloc");
1510
1511 VERB(3, ">>>");
1512 }
nethercotec9f36922004-02-14 16:40:02 +00001513
nethercotec9f36922004-02-14 16:40:02 +00001514 return p;
1515}
1516
1517static __inline__
1518void die_block ( void* p, Bool custom_free )
1519{
njnf1c5def2005-08-11 02:17:07 +00001520 HP_Chunk* hc;
nethercotec9f36922004-02-14 16:40:02 +00001521
njnf1c5def2005-08-11 02:17:07 +00001522 // Remove HP_Chunk from malloc_list
njn9a463242005-08-16 03:29:50 +00001523 hc = VG_(HT_remove)(malloc_list, (UWord)p);
njn734b8052007-11-01 04:40:37 +00001524 if (NULL == hc) {
njn5cc5d7e2005-08-11 02:09:25 +00001525 return; // must have been a bogus free()
njn734b8052007-11-01 04:40:37 +00001526 }
nethercotec9f36922004-02-14 16:40:02 +00001527
njn734b8052007-11-01 04:40:37 +00001528 if (clo_heap) {
1529 VERB(3, "<<< die_mem_heap");
nethercotec9f36922004-02-14 16:40:02 +00001530
njn734b8052007-11-01 04:40:37 +00001531 // Update statistics
1532 n_heap_frees++;
nethercote57e36b32004-07-10 14:56:28 +00001533
njn734b8052007-11-01 04:40:37 +00001534 // Maybe take a peak snapshot, since it's a deallocation.
1535 maybe_take_snapshot(Peak, "de-PEAK");
1536
1537 // Update heap stats.
njn32397c02007-11-10 04:08:08 +00001538 update_heap_stats(-hc->req_szB, -clo_heap_admin - hc->slop_szB);
njn734b8052007-11-01 04:40:37 +00001539
1540 // Update XTree.
njn32397c02007-11-10 04:08:08 +00001541 update_XCon(hc->where, -hc->req_szB);
njn734b8052007-11-01 04:40:37 +00001542
1543 // Maybe take a snapshot.
1544 maybe_take_snapshot(Normal, "dealloc");
1545
njn32397c02007-11-10 04:08:08 +00001546 VERB(3, ">>> (-%lu, -%lu)", hc->req_szB, hc->slop_szB);
njn734b8052007-11-01 04:40:37 +00001547 }
1548
1549 // Actually free the chunk, and the heap block (if necessary)
1550 VG_(free)( hc ); hc = NULL;
nethercotec9f36922004-02-14 16:40:02 +00001551 if (!custom_free)
1552 VG_(cli_free)( p );
nethercotec9f36922004-02-14 16:40:02 +00001553}
1554
njn734b8052007-11-01 04:40:37 +00001555static __inline__
njn32397c02007-11-10 04:08:08 +00001556void* renew_block ( ThreadId tid, void* p_old, SizeT new_req_szB )
nethercotec9f36922004-02-14 16:40:02 +00001557{
njn734b8052007-11-01 04:40:37 +00001558 HP_Chunk* hc;
1559 void* p_new;
njn32397c02007-11-10 04:08:08 +00001560 SizeT old_req_szB, old_slop_szB, new_slop_szB, new_actual_szB;
njn734b8052007-11-01 04:40:37 +00001561 XPt *old_where, *new_where;
1562
1563 // Remove the old block
1564 hc = VG_(HT_remove)(malloc_list, (UWord)p_old);
1565 if (hc == NULL) {
1566 return NULL; // must have been a bogus realloc()
1567 }
1568
njn32397c02007-11-10 04:08:08 +00001569 old_req_szB = hc->req_szB;
1570 old_slop_szB = hc->slop_szB;
njn734b8052007-11-01 04:40:37 +00001571
1572 if (clo_heap) {
njn32397c02007-11-10 04:08:08 +00001573 VERB(3, "<<< renew_mem_heap (%lu)", new_req_szB);
njn734b8052007-11-01 04:40:37 +00001574
1575 // Update statistics
1576 n_heap_reallocs++;
1577
1578 // Maybe take a peak snapshot, if it's (effectively) a deallocation.
njn32397c02007-11-10 04:08:08 +00001579 if (new_req_szB < old_req_szB) {
njn734b8052007-11-01 04:40:37 +00001580 maybe_take_snapshot(Peak, "re-PEAK");
1581 }
njn734b8052007-11-01 04:40:37 +00001582 }
1583
1584 // Actually do the allocation, if necessary.
njn32397c02007-11-10 04:08:08 +00001585 if (new_req_szB <= old_req_szB + old_slop_szB) {
1586 // New size is smaller or same; block not moved.
njn734b8052007-11-01 04:40:37 +00001587 p_new = p_old;
njn32397c02007-11-10 04:08:08 +00001588 new_slop_szB = old_slop_szB + (old_req_szB - new_req_szB);
njn734b8052007-11-01 04:40:37 +00001589
1590 } else {
njn32397c02007-11-10 04:08:08 +00001591 // New size is bigger; make new block, copy shared contents, free old.
1592 p_new = VG_(cli_malloc)(VG_(clo_alignment), new_req_szB);
1593 if (!p_new) {
1594 // Nb: if realloc fails, NULL is returned but the old block is not
1595 // touched. What an awful function.
1596 return NULL;
njn734b8052007-11-01 04:40:37 +00001597 }
njn32397c02007-11-10 04:08:08 +00001598 VG_(memcpy)(p_new, p_old, old_req_szB);
1599 VG_(cli_free)(p_old);
1600 new_actual_szB = VG_(malloc_usable_size)(p_new);
1601 tl_assert(new_actual_szB >= new_req_szB);
1602 new_slop_szB = new_actual_szB - new_req_szB;
njn734b8052007-11-01 04:40:37 +00001603 }
1604
1605 if (p_new) {
1606 // Update HP_Chunk.
njn32397c02007-11-10 04:08:08 +00001607 hc->data = (Addr)p_new;
1608 hc->req_szB = new_req_szB;
1609 hc->slop_szB = new_slop_szB;
1610 old_where = hc->where;
1611 hc->where = NULL;
njn734b8052007-11-01 04:40:37 +00001612
1613 // Update XTree.
1614 if (clo_heap) {
1615 new_where = get_XCon( tid, /*custom_malloc*/False);
1616 hc->where = new_where;
njn32397c02007-11-10 04:08:08 +00001617 update_XCon(old_where, -old_req_szB);
1618 update_XCon(new_where, new_req_szB);
njn734b8052007-11-01 04:40:37 +00001619 }
1620 }
1621
1622 // Now insert the new hc (with a possibly new 'data' field) into
1623 // malloc_list. If this realloc() did not increase the memory size, we
1624 // will have removed and then re-added hc unnecessarily. But that's ok
1625 // because shrinking a block with realloc() is (presumably) much rarer
1626 // than growing it, and this way simplifies the growing case.
1627 VG_(HT_add_node)(malloc_list, hc);
1628
njn734b8052007-11-01 04:40:37 +00001629 if (clo_heap) {
njn32397c02007-11-10 04:08:08 +00001630 // Update heap stats.
1631 update_heap_stats(new_req_szB - old_req_szB, new_slop_szB - old_slop_szB);
1632
1633 // Maybe take a snapshot.
njn734b8052007-11-01 04:40:37 +00001634 maybe_take_snapshot(Normal, "realloc");
1635
njn32397c02007-11-10 04:08:08 +00001636 VERB(3, ">>> (%ld, %ld)",
1637 new_req_szB - old_req_szB, new_slop_szB - old_slop_szB);
njn734b8052007-11-01 04:40:37 +00001638 }
1639
1640 return p_new;
nethercotec9f36922004-02-14 16:40:02 +00001641}
1642
njn734b8052007-11-01 04:40:37 +00001643
1644//------------------------------------------------------------//
1645//--- malloc() et al replacement wrappers ---//
1646//------------------------------------------------------------//
1647
1648static void* ms_malloc ( ThreadId tid, SizeT szB )
nethercotec9f36922004-02-14 16:40:02 +00001649{
njn734b8052007-11-01 04:40:37 +00001650 return new_block( tid, NULL, szB, VG_(clo_alignment), /*is_zeroed*/False );
nethercotec9f36922004-02-14 16:40:02 +00001651}
1652
njn734b8052007-11-01 04:40:37 +00001653static void* ms___builtin_new ( ThreadId tid, SizeT szB )
nethercotec9f36922004-02-14 16:40:02 +00001654{
njn734b8052007-11-01 04:40:37 +00001655 return new_block( tid, NULL, szB, VG_(clo_alignment), /*is_zeroed*/False );
nethercotec9f36922004-02-14 16:40:02 +00001656}
1657
njn734b8052007-11-01 04:40:37 +00001658static void* ms___builtin_vec_new ( ThreadId tid, SizeT szB )
fitzhardinge51f3ff12004-03-04 22:42:03 +00001659{
njn734b8052007-11-01 04:40:37 +00001660 return new_block( tid, NULL, szB, VG_(clo_alignment), /*is_zeroed*/False );
1661}
1662
1663static void* ms_calloc ( ThreadId tid, SizeT m, SizeT szB )
1664{
1665 return new_block( tid, NULL, m*szB, VG_(clo_alignment), /*is_zeroed*/True );
1666}
1667
1668static void *ms_memalign ( ThreadId tid, SizeT alignB, SizeT szB )
1669{
1670 return new_block( tid, NULL, szB, alignB, False );
fitzhardinge51f3ff12004-03-04 22:42:03 +00001671}
1672
njn51d827b2005-05-09 01:02:08 +00001673static void ms_free ( ThreadId tid, void* p )
nethercotec9f36922004-02-14 16:40:02 +00001674{
1675 die_block( p, /*custom_free*/False );
1676}
1677
njn51d827b2005-05-09 01:02:08 +00001678static void ms___builtin_delete ( ThreadId tid, void* p )
nethercotec9f36922004-02-14 16:40:02 +00001679{
1680 die_block( p, /*custom_free*/False);
1681}
1682
njn51d827b2005-05-09 01:02:08 +00001683static void ms___builtin_vec_delete ( ThreadId tid, void* p )
nethercotec9f36922004-02-14 16:40:02 +00001684{
1685 die_block( p, /*custom_free*/False );
1686}
1687
njn734b8052007-11-01 04:40:37 +00001688static void* ms_realloc ( ThreadId tid, void* p_old, SizeT new_szB )
nethercotec9f36922004-02-14 16:40:02 +00001689{
njn734b8052007-11-01 04:40:37 +00001690 return renew_block(tid, p_old, new_szB);
nethercotec9f36922004-02-14 16:40:02 +00001691}
1692
1693
njn734b8052007-11-01 04:40:37 +00001694//------------------------------------------------------------//
1695//--- Stacks ---//
1696//------------------------------------------------------------//
nethercotec9f36922004-02-14 16:40:02 +00001697
njn734b8052007-11-01 04:40:37 +00001698// We really want the inlining to occur...
1699#define INLINE inline __attribute__((always_inline))
nethercotec9f36922004-02-14 16:40:02 +00001700
njn734b8052007-11-01 04:40:37 +00001701static void update_stack_stats(SSizeT stack_szB_delta)
nethercotec9f36922004-02-14 16:40:02 +00001702{
njn734b8052007-11-01 04:40:37 +00001703 if (stack_szB_delta < 0) tl_assert(stacks_szB >= -stack_szB_delta);
1704 stacks_szB += stack_szB_delta;
nethercotec9f36922004-02-14 16:40:02 +00001705
njn734b8052007-11-01 04:40:37 +00001706 update_alloc_stats(stack_szB_delta);
nethercotec9f36922004-02-14 16:40:02 +00001707}
1708
njn734b8052007-11-01 04:40:37 +00001709static INLINE void new_mem_stack_2(Addr a, SizeT len, Char* what)
nethercotec9f36922004-02-14 16:40:02 +00001710{
njn734b8052007-11-01 04:40:37 +00001711 if (have_started_executing_code) {
1712 VERB(3, "<<< new_mem_stack (%ld)", len);
1713 n_stack_allocs++;
1714 update_stack_stats(len);
1715 maybe_take_snapshot(Normal, what);
1716 VERB(3, ">>>");
nethercotec9f36922004-02-14 16:40:02 +00001717 }
nethercotec9f36922004-02-14 16:40:02 +00001718}
1719
njn734b8052007-11-01 04:40:37 +00001720static INLINE void die_mem_stack_2(Addr a, SizeT len, Char* what)
nethercotec9f36922004-02-14 16:40:02 +00001721{
njn734b8052007-11-01 04:40:37 +00001722 if (have_started_executing_code) {
1723 VERB(3, "<<< die_mem_stack (%ld)", -len);
1724 n_stack_frees++;
1725 maybe_take_snapshot(Peak, "stkPEAK");
1726 update_stack_stats(-len);
1727 maybe_take_snapshot(Normal, what);
1728 VERB(3, ">>>");
nethercotec9f36922004-02-14 16:40:02 +00001729 }
nethercotec9f36922004-02-14 16:40:02 +00001730}
1731
njn734b8052007-11-01 04:40:37 +00001732static void new_mem_stack(Addr a, SizeT len)
nethercotec9f36922004-02-14 16:40:02 +00001733{
njn734b8052007-11-01 04:40:37 +00001734 new_mem_stack_2(a, len, "stk-new");
1735}
nethercotec9f36922004-02-14 16:40:02 +00001736
njn734b8052007-11-01 04:40:37 +00001737static void die_mem_stack(Addr a, SizeT len)
1738{
1739 die_mem_stack_2(a, len, "stk-die");
1740}
nethercotec9f36922004-02-14 16:40:02 +00001741
nethercote8b5f40c2004-11-02 13:29:50 +00001742static void new_mem_stack_signal(Addr a, SizeT len)
nethercotec9f36922004-02-14 16:40:02 +00001743{
njn734b8052007-11-01 04:40:37 +00001744 new_mem_stack_2(a, len, "sig-new");
nethercotec9f36922004-02-14 16:40:02 +00001745}
1746
nethercote8b5f40c2004-11-02 13:29:50 +00001747static void die_mem_stack_signal(Addr a, SizeT len)
nethercotec9f36922004-02-14 16:40:02 +00001748{
njn734b8052007-11-01 04:40:37 +00001749 die_mem_stack_2(a, len, "sig-die");
nethercotec9f36922004-02-14 16:40:02 +00001750}
1751
njn734b8052007-11-01 04:40:37 +00001752
1753//------------------------------------------------------------//
1754//--- Client Requests ---//
1755//------------------------------------------------------------//
nethercotec9f36922004-02-14 16:40:02 +00001756
njn51d827b2005-05-09 01:02:08 +00001757static Bool ms_handle_client_request ( ThreadId tid, UWord* argv, UWord* ret )
nethercotec9f36922004-02-14 16:40:02 +00001758{
1759 switch (argv[0]) {
1760 case VG_USERREQ__MALLOCLIKE_BLOCK: {
nethercote57e36b32004-07-10 14:56:28 +00001761 void* res;
njn734b8052007-11-01 04:40:37 +00001762 void* p = (void*)argv[1];
1763 SizeT szB = argv[2];
1764 res = new_block( tid, p, szB, /*alignB--ignored*/0, /*is_zeroed*/False );
njnca82cc02004-11-22 17:18:48 +00001765 tl_assert(res == p);
njn734b8052007-11-01 04:40:37 +00001766 *ret = 0;
nethercotec9f36922004-02-14 16:40:02 +00001767 return True;
1768 }
1769 case VG_USERREQ__FREELIKE_BLOCK: {
njn734b8052007-11-01 04:40:37 +00001770 void* p = (void*)argv[1];
nethercotec9f36922004-02-14 16:40:02 +00001771 die_block( p, /*custom_free*/True );
njn734b8052007-11-01 04:40:37 +00001772 *ret = 0;
nethercotec9f36922004-02-14 16:40:02 +00001773 return True;
1774 }
1775 default:
1776 *ret = 0;
1777 return False;
1778 }
1779}
1780
njn734b8052007-11-01 04:40:37 +00001781//------------------------------------------------------------//
1782//--- Instrumentation ---//
1783//------------------------------------------------------------//
nethercotec9f36922004-02-14 16:40:02 +00001784
njn1a2741a2007-11-26 21:59:04 +00001785static void add_counter_update(IRSB* sbOut, Int n)
1786{
1787 #if defined(VG_BIGENDIAN)
1788 # define END Iend_BE
1789 #elif defined(VG_LITTLEENDIAN)
1790 # define END Iend_LE
1791 #else
1792 # error "Unknown endianness"
1793 #endif
1794 // Add code to increment 'guest_instrs_executed' by 'n', like this:
1795 // WrTmp(t1, Load64(&guest_instrs_executed))
1796 // WrTmp(t2, Add64(RdTmp(t1), Const(n)))
1797 // Store(&guest_instrs_executed, t2)
1798 IRTemp t1 = newIRTemp(sbOut->tyenv, Ity_I64);
1799 IRTemp t2 = newIRTemp(sbOut->tyenv, Ity_I64);
1800 IRExpr* counter_addr = mkIRExpr_HWord( (HWord)&guest_instrs_executed );
1801
1802 IRStmt* st1 = IRStmt_WrTmp(t1, IRExpr_Load(END, Ity_I64, counter_addr));
1803 IRStmt* st2 =
1804 IRStmt_WrTmp(t2,
1805 IRExpr_Binop(Iop_Add64, IRExpr_RdTmp(t1),
1806 IRExpr_Const(IRConst_U64(n))));
1807 IRStmt* st3 = IRStmt_Store(END, counter_addr, IRExpr_RdTmp(t2));
1808
1809 addStmtToIRSB( sbOut, st1 );
1810 addStmtToIRSB( sbOut, st2 );
1811 addStmtToIRSB( sbOut, st3 );
1812}
1813
1814static IRSB* ms_instrument2( IRSB* sbIn )
1815{
1816 Int i, n = 0;
1817 IRSB* sbOut;
1818
1819 // We increment the instruction count in two places:
1820 // - just before any Ist_Exit statements;
1821 // - just before the IRSB's end.
1822 // In the former case, we zero 'n' and then continue instrumenting.
1823
1824 sbOut = deepCopyIRSBExceptStmts(sbIn);
1825
1826 for (i = 0; i < sbIn->stmts_used; i++) {
1827 IRStmt* st = sbIn->stmts[i];
1828
1829 if (!st || st->tag == Ist_NoOp) continue;
1830
1831 if (st->tag == Ist_IMark) {
1832 n++;
1833 } else if (st->tag == Ist_Exit) {
1834 if (n > 0) {
1835 // Add an increment before the Exit statement, then reset 'n'.
1836 add_counter_update(sbOut, n);
1837 n = 0;
1838 }
1839 }
1840 addStmtToIRSB( sbOut, st );
1841 }
1842
1843 if (n > 0) {
1844 // Add an increment before the SB end.
1845 add_counter_update(sbOut, n);
1846 }
1847 return sbOut;
1848}
1849
sewardj4ba057c2005-10-18 12:04:18 +00001850static
sewardj0b9d74a2006-12-24 02:24:11 +00001851IRSB* ms_instrument ( VgCallbackClosure* closure,
njn1a2741a2007-11-26 21:59:04 +00001852 IRSB* sbIn,
njn734b8052007-11-01 04:40:37 +00001853 VexGuestLayout* layout,
sewardj461df9c2006-01-17 02:06:39 +00001854 VexGuestExtents* vge,
sewardj4ba057c2005-10-18 12:04:18 +00001855 IRType gWordTy, IRType hWordTy )
nethercotec9f36922004-02-14 16:40:02 +00001856{
njn734b8052007-11-01 04:40:37 +00001857 if (! have_started_executing_code) {
1858 // Do an initial sample to guarantee that we have at least one.
1859 // We use 'maybe_take_snapshot' instead of 'take_snapshot' to ensure
1860 // 'maybe_take_snapshot's internal static variables are initialised.
1861 have_started_executing_code = True;
1862 maybe_take_snapshot(Normal, "startup");
1863 }
njn1a2741a2007-11-26 21:59:04 +00001864
1865 if (clo_time_unit == TimeI) { return ms_instrument2(sbIn); }
1866 else if (clo_time_unit == TimeMS) { return sbIn; }
1867 else if (clo_time_unit == TimeB) { return sbIn; }
1868 else { tl_assert2(0, "bad --time-unit value"); }
nethercotec9f36922004-02-14 16:40:02 +00001869}
1870
nethercotec9f36922004-02-14 16:40:02 +00001871
njn734b8052007-11-01 04:40:37 +00001872//------------------------------------------------------------//
1873//--- Writing snapshots ---//
1874//------------------------------------------------------------//
nethercotec9f36922004-02-14 16:40:02 +00001875
njn374a36d2007-11-23 01:41:32 +00001876// The output file name. Controlled by --massif-out-file.
1877static Char* massif_out_file = NULL;
1878
njn734b8052007-11-01 04:40:37 +00001879#define FP_BUF_SIZE 1024
1880Char FP_buf[FP_BUF_SIZE];
nethercotec9f36922004-02-14 16:40:02 +00001881
njn734b8052007-11-01 04:40:37 +00001882// XXX: implement f{,n}printf in m_libcprint.c eventually, and use it here.
1883// Then change Cachegrind to use it too.
1884#define FP(format, args...) ({ \
1885 VG_(snprintf)(FP_buf, FP_BUF_SIZE, format, ##args); \
1886 VG_(write)(fd, (void*)FP_buf, VG_(strlen)(FP_buf)); \
1887})
nethercotec9f36922004-02-14 16:40:02 +00001888
1889// Nb: uses a static buffer, each call trashes the last string returned.
njn734b8052007-11-01 04:40:37 +00001890static Char* make_perc(ULong x, ULong y)
nethercotec9f36922004-02-14 16:40:02 +00001891{
1892 static Char mbuf[32];
njn734b8052007-11-01 04:40:37 +00001893
1894// tl_assert(x <= y); XXX; put back in later...
1895
njn1a2741a2007-11-26 21:59:04 +00001896 // XXX: I'm not confident that VG_(percentify) works as it should...
njn734b8052007-11-01 04:40:37 +00001897 VG_(percentify)(x, y, 2, 6, mbuf);
1898 // XXX: this is bogus if the denominator was zero -- resulting string is
1899 // something like "0 --%")
1900 if (' ' == mbuf[0]) mbuf[0] = '0';
nethercotec9f36922004-02-14 16:40:02 +00001901 return mbuf;
1902}
1903
njn734b8052007-11-01 04:40:37 +00001904static void pp_snapshot_SXPt(Int fd, SXPt* sxpt, Int depth, Char* depth_str,
1905 Int depth_str_len,
1906 SizeT snapshot_heap_szB, SizeT snapshot_total_szB)
nethercotec9f36922004-02-14 16:40:02 +00001907{
njn734b8052007-11-01 04:40:37 +00001908 #define BUF_LEN 1024
1909 Int i, n_insig_children_sxpts;
1910 Char* perc;
1911 Char ip_desc_array[BUF_LEN];
1912 Char* ip_desc = ip_desc_array;
1913 SXPt* pred = NULL;
1914 SXPt* child = NULL;
nethercotec9f36922004-02-14 16:40:02 +00001915
njn734b8052007-11-01 04:40:37 +00001916 switch (sxpt->tag) {
1917 case SigSXPt:
1918 // Print the SXPt itself.
1919 if (sxpt->Sig.ip == 0) {
1920 ip_desc =
1921 "(heap allocation functions) malloc/new/new[], --alloc-fns, etc.";
1922 } else {
1923 // If it's main-or-below-main, we (if appropriate) ignore everything
1924 // below it by pretending it has no children.
1925 // XXX: get this properly. Also, don't hard-code "(below main)"
1926 // here -- look at the "(below main)"/"__libc_start_main" mess
1927 // (m_stacktrace.c and m_demangle.c).
1928 // [Nb: Josef wants --show-below-main to work for his fn entry/exit
1929 // tracing]
1930 Bool should_hide_below_main = /*!VG_(clo_show_below_main)*/True;
1931 if (should_hide_below_main &&
1932 VG_(get_fnname)(sxpt->Sig.ip, ip_desc, BUF_LEN) &&
1933 (VG_STREQ(ip_desc, "main") || VG_STREQ(ip_desc, "(below main)")))
1934 {
1935 sxpt->Sig.n_children = 0;
1936 }
1937 // We need the -1 to get the line number right, But I'm not sure why.
1938 ip_desc = VG_(describe_IP)(sxpt->Sig.ip-1, ip_desc, BUF_LEN);
1939 }
1940 perc = make_perc(sxpt->szB, snapshot_total_szB);
1941 FP("%sn%d: %lu %s\n",
1942 depth_str, sxpt->Sig.n_children, sxpt->szB, ip_desc);
nethercotec9f36922004-02-14 16:40:02 +00001943
njn734b8052007-11-01 04:40:37 +00001944 // Indent.
1945 tl_assert(depth+1 < depth_str_len-1); // -1 for end NUL char
1946 depth_str[depth+0] = ' ';
1947 depth_str[depth+1] = '\0';
1948
1949 // Sort SXPt's children by szB (reverse order: biggest to smallest).
1950 // Nb: we sort them here, rather than earlier (eg. in dup_XTree), for
1951 // two reasons. First, if we do it during dup_XTree, it can get
1952 // expensive (eg. 15% of execution time for konqueror
1953 // startup/shutdown). Second, this way we get the Insig SXPt (if one
1954 // is present) in its sorted position, not at the end.
1955 VG_(ssort)(sxpt->Sig.children, sxpt->Sig.n_children, sizeof(SXPt*),
1956 SXPt_revcmp_szB);
1957
1958 // Print the SXPt's children. They should already be in sorted order.
1959 n_insig_children_sxpts = 0;
1960 for (i = 0; i < sxpt->Sig.n_children; i++) {
1961 pred = child;
1962 child = sxpt->Sig.children[i];
1963
1964 if (InsigSXPt == child->tag)
1965 n_insig_children_sxpts++;
1966
1967 // Ok, print the child.
1968 pp_snapshot_SXPt(fd, child, depth+1, depth_str, depth_str_len,
1969 snapshot_heap_szB, snapshot_total_szB);
1970
1971 // Unindent.
1972 depth_str[depth+0] = '\0';
1973 depth_str[depth+1] = '\0';
1974 }
1975 // There should be 0 or 1 Insig children SXPts.
1976 tl_assert(n_insig_children_sxpts <= 1);
1977 break;
1978
1979 case InsigSXPt: {
1980 Char* s = ( sxpt->Insig.n_xpts == 1 ? "," : "s, all" );
1981 perc = make_perc(sxpt->szB, snapshot_total_szB);
1982 FP("%sn0: %lu in %d place%s below massif's threshold (%s)\n",
1983 depth_str, sxpt->szB, sxpt->Insig.n_xpts, s,
njn62721e92007-11-11 22:15:58 +00001984 make_perc((ULong)clo_threshold, 100));
njn734b8052007-11-01 04:40:37 +00001985 break;
1986 }
1987
1988 default:
1989 tl_assert2(0, "pp_snapshot_SXPt: unrecognised SXPt tag");
nethercotec9f36922004-02-14 16:40:02 +00001990 }
nethercotec9f36922004-02-14 16:40:02 +00001991}
1992
njn734b8052007-11-01 04:40:37 +00001993static void pp_snapshot(Int fd, Snapshot* snapshot, Int snapshot_n)
nethercotec9f36922004-02-14 16:40:02 +00001994{
njn734b8052007-11-01 04:40:37 +00001995 sanity_check_snapshot(snapshot);
nethercotec9f36922004-02-14 16:40:02 +00001996
njn734b8052007-11-01 04:40:37 +00001997 FP("#-----------\n");
1998 FP("snapshot=%d\n", snapshot_n);
1999 FP("#-----------\n");
2000 FP("time=%lld\n", snapshot->time);
2001 FP("mem_heap_B=%lu\n", snapshot->heap_szB);
njn32397c02007-11-10 04:08:08 +00002002 FP("mem_heap_extra_B=%lu\n", snapshot->heap_extra_szB);
njn734b8052007-11-01 04:40:37 +00002003 FP("mem_stacks_B=%lu\n", snapshot->stacks_szB);
2004
2005 if (is_detailed_snapshot(snapshot)) {
2006 // Detailed snapshot -- print heap tree.
2007 Int depth_str_len = clo_depth + 3;
2008 Char* depth_str = VG_(malloc)(sizeof(Char) * depth_str_len);
2009 SizeT snapshot_total_szB =
njn32397c02007-11-10 04:08:08 +00002010 snapshot->heap_szB + snapshot->heap_extra_szB + snapshot->stacks_szB;
njn734b8052007-11-01 04:40:37 +00002011 depth_str[0] = '\0'; // Initialise depth_str to "".
2012
2013 FP("heap_tree=%s\n", ( Peak == snapshot->kind ? "peak" : "detailed" ));
2014 pp_snapshot_SXPt(fd, snapshot->alloc_sxpt, 0, depth_str,
2015 depth_str_len, snapshot->heap_szB,
2016 snapshot_total_szB);
2017
2018 VG_(free)(depth_str);
2019
2020 } else {
2021 FP("heap_tree=empty\n");
nethercote43a15ce2004-08-30 19:15:12 +00002022 }
nethercotec9f36922004-02-14 16:40:02 +00002023}
2024
njn734b8052007-11-01 04:40:37 +00002025static void write_snapshots_to_file(void)
nethercotec9f36922004-02-14 16:40:02 +00002026{
njn734b8052007-11-01 04:40:37 +00002027 Int i, fd;
sewardj92645592005-07-23 09:18:34 +00002028 SysRes sres;
nethercotec9f36922004-02-14 16:40:02 +00002029
njn734b8052007-11-01 04:40:37 +00002030 sres = VG_(open)(massif_out_file, VKI_O_CREAT|VKI_O_TRUNC|VKI_O_WRONLY,
2031 VKI_S_IRUSR|VKI_S_IWUSR);
sewardj92645592005-07-23 09:18:34 +00002032 if (sres.isError) {
njn734b8052007-11-01 04:40:37 +00002033 // If the file can't be opened for whatever reason (conflict
2034 // between multiple cachegrinded processes?), give up now.
2035 VG_(message)(Vg_UserMsg,
2036 "error: can't open output file '%s'", massif_out_file );
2037 VG_(message)(Vg_UserMsg,
2038 " ... so profiling results will be missing.");
nethercotec9f36922004-02-14 16:40:02 +00002039 return;
sewardj92645592005-07-23 09:18:34 +00002040 } else {
sewardje8089302006-10-17 02:15:17 +00002041 fd = sres.res;
nethercotec9f36922004-02-14 16:40:02 +00002042 }
2043
njn734b8052007-11-01 04:40:37 +00002044 // Print massif-specific options that were used.
2045 // XXX: is it worth having a "desc:" line? Could just call it "options:"
2046 // -- this file format isn't as generic as Cachegrind's, so the
2047 // implied genericity of "desc:" is bogus.
2048 FP("desc:");
2049 for (i = 0; i < VG_(sizeXA)(args_for_massif); i++) {
2050 Char* arg = *(Char**)VG_(indexXA)(args_for_massif, i);
2051 FP(" %s", arg);
nethercotec9f36922004-02-14 16:40:02 +00002052 }
njn734b8052007-11-01 04:40:37 +00002053 if (0 == i) FP(" (none)");
2054 FP("\n");
nethercotec9f36922004-02-14 16:40:02 +00002055
njn734b8052007-11-01 04:40:37 +00002056 // Print "cmd:" line.
2057 FP("cmd: ");
sewardj45f4e7c2005-09-27 19:20:21 +00002058 if (VG_(args_the_exename)) {
njn734b8052007-11-01 04:40:37 +00002059 FP("%s", VG_(args_the_exename));
2060 for (i = 0; i < VG_(sizeXA)( VG_(args_for_client) ); i++) {
2061 HChar* arg = * (HChar**) VG_(indexXA)( VG_(args_for_client), i );
2062 if (arg)
2063 FP(" %s", arg);
2064 }
2065 } else {
2066 FP(" ???");
sewardj45f4e7c2005-09-27 19:20:21 +00002067 }
njn734b8052007-11-01 04:40:37 +00002068 FP("\n");
nethercotec9f36922004-02-14 16:40:02 +00002069
njn734b8052007-11-01 04:40:37 +00002070 FP("time_unit: %s\n", TimeUnit_to_string(clo_time_unit));
nethercotec9f36922004-02-14 16:40:02 +00002071
njn734b8052007-11-01 04:40:37 +00002072 for (i = 0; i < next_snapshot_i; i++) {
2073 Snapshot* snapshot = & snapshots[i];
2074 pp_snapshot(fd, snapshot, i); // Detailed snapshot!
nethercotec9f36922004-02-14 16:40:02 +00002075 }
2076}
2077
njn734b8052007-11-01 04:40:37 +00002078
2079//------------------------------------------------------------//
2080//--- Finalisation ---//
2081//------------------------------------------------------------//
2082
njn51d827b2005-05-09 01:02:08 +00002083static void ms_fini(Int exit_status)
nethercotec9f36922004-02-14 16:40:02 +00002084{
njn734b8052007-11-01 04:40:37 +00002085 // Output.
2086 write_snapshots_to_file();
nethercotec9f36922004-02-14 16:40:02 +00002087
njn734b8052007-11-01 04:40:37 +00002088 // Stats
2089 tl_assert(n_xpts > 0); // always have alloc_xpt
2090 VERB(1, "heap allocs: %u", n_heap_allocs);
2091 VERB(1, "heap reallocs: %u", n_heap_reallocs);
2092 VERB(1, "heap frees: %u", n_heap_frees);
2093 VERB(1, "stack allocs: %u", n_stack_allocs);
2094 VERB(1, "stack frees: %u", n_stack_frees);
2095 VERB(1, "XPts: %u", n_xpts);
2096 VERB(1, "top-XPts: %u (%d%%)",
2097 alloc_xpt->n_children,
2098 ( n_xpts ? alloc_xpt->n_children * 100 / n_xpts : 0));
njn55a30042007-11-10 04:18:39 +00002099 VERB(1, "XPt init expansions: %u", n_xpt_init_expansions);
2100 VERB(1, "XPt later expansions: %u", n_xpt_later_expansions);
njn734b8052007-11-01 04:40:37 +00002101 VERB(1, "SXPt allocs: %u", n_sxpt_allocs);
2102 VERB(1, "SXPt frees: %u", n_sxpt_frees);
2103 VERB(1, "skipped snapshots: %u", n_skipped_snapshots);
2104 VERB(1, "real snapshots: %u", n_real_snapshots);
2105 VERB(1, "detailed snapshots: %u", n_detailed_snapshots);
2106 VERB(1, "peak snapshots: %u", n_peak_snapshots);
2107 VERB(1, "cullings: %u", n_cullings);
njn55a30042007-11-10 04:18:39 +00002108 VERB(1, "XCon redos: %u", n_XCon_redos);
nethercotec9f36922004-02-14 16:40:02 +00002109}
2110
njn734b8052007-11-01 04:40:37 +00002111
2112//------------------------------------------------------------//
2113//--- Initialisation ---//
2114//------------------------------------------------------------//
njn51d827b2005-05-09 01:02:08 +00002115
2116static void ms_post_clo_init(void)
2117{
njn734b8052007-11-01 04:40:37 +00002118 Int i;
njn51d827b2005-05-09 01:02:08 +00002119
njn734b8052007-11-01 04:40:37 +00002120 // Check options.
2121 if (clo_heap_admin < 0 || clo_heap_admin > 1024) {
2122 VG_(message)(Vg_UserMsg, "--heap-admin must be between 0 and 1024");
2123 VG_(err_bad_option)("--heap-admin");
2124 }
2125 if (clo_depth < 1 || clo_depth > MAX_DEPTH) {
2126 VG_(message)(Vg_UserMsg, "--depth must be between 1 and %d", MAX_DEPTH);
2127 VG_(err_bad_option)("--depth");
2128 }
njn62721e92007-11-11 22:15:58 +00002129 if (clo_threshold < 0 || clo_threshold > 100) {
2130 VG_(message)(Vg_UserMsg, "--threshold must be between 0.0 and 100.0");
njn734b8052007-11-01 04:40:37 +00002131 VG_(err_bad_option)("--threshold");
2132 }
2133 if (clo_detailed_freq < 1 || clo_detailed_freq > 10000) {
2134 VG_(message)(Vg_UserMsg, "--detailed-freq must be between 1 and 10000");
2135 VG_(err_bad_option)("--detailed-freq");
2136 }
2137 if (clo_max_snapshots < 10 || clo_max_snapshots > 1000) {
2138 VG_(message)(Vg_UserMsg, "--max-snapshots must be between 10 and 1000");
2139 VG_(err_bad_option)("--max-snapshots");
2140 }
2141
2142 // If we have --heap=no, set --heap-admin to zero, just to make sure we
2143 // don't accidentally use a non-zero heap-admin size somewhere.
2144 if (!clo_heap) {
2145 clo_heap_admin = 0;
2146 }
2147
2148 // Print alloc-fns, if necessary.
2149 if (VG_(clo_verbosity) > 1) {
2150 VERB(1, "alloc-fns:");
2151 for (i = 0; i < VG_(sizeXA)(alloc_fns); i++) {
2152 Char** alloc_fn_ptr = VG_(indexXA)(alloc_fns, i);
2153 VERB(1, " %d: %s", i, *alloc_fn_ptr);
2154 }
2155 }
2156
2157 // Events to track.
2158 if (clo_stacks) {
2159 VG_(track_new_mem_stack) ( new_mem_stack );
2160 VG_(track_die_mem_stack) ( die_mem_stack );
2161 VG_(track_new_mem_stack_signal) ( new_mem_stack_signal );
2162 VG_(track_die_mem_stack_signal) ( die_mem_stack_signal );
2163 }
2164
2165 // Initialise snapshot array, and sanity-check it.
2166 snapshots = VG_(malloc)(sizeof(Snapshot) * clo_max_snapshots);
2167 // We don't want to do snapshot sanity checks here, because they're
2168 // currently uninitialised.
2169 for (i = 0; i < clo_max_snapshots; i++) {
2170 clear_snapshot( & snapshots[i], /*do_sanity_check*/False );
2171 }
2172 sanity_check_snapshots_array();
njnf4c665f2007-11-20 07:55:40 +00002173
2174 // Setup output filename.
njn3ed19712007-11-22 23:01:59 +00002175 massif_out_file =
2176 VG_(expand_file_name)("--massif-out-file", clo_massif_out_file);
njn51d827b2005-05-09 01:02:08 +00002177}
2178
tom151a6392005-11-11 12:30:36 +00002179static void ms_pre_clo_init(void)
njn734b8052007-11-01 04:40:37 +00002180{
njn51d827b2005-05-09 01:02:08 +00002181 VG_(details_name) ("Massif");
2182 VG_(details_version) (NULL);
njn1a2741a2007-11-26 21:59:04 +00002183 VG_(details_description) ("a heap profiler");
njn9a0cba42007-04-15 22:15:57 +00002184 VG_(details_copyright_author)(
njn734b8052007-11-01 04:40:37 +00002185 "Copyright (C) 2003-2007, and GNU GPL'd, by Nicholas Nethercote");
njn51d827b2005-05-09 01:02:08 +00002186 VG_(details_bug_reports_to) (VG_BUGS_TO);
2187
2188 // Basic functions
2189 VG_(basic_tool_funcs) (ms_post_clo_init,
2190 ms_instrument,
2191 ms_fini);
2192
2193 // Needs
2194 VG_(needs_libc_freeres)();
2195 VG_(needs_command_line_options)(ms_process_cmd_line_option,
2196 ms_print_usage,
2197 ms_print_debug_usage);
2198 VG_(needs_client_requests) (ms_handle_client_request);
njn734b8052007-11-01 04:40:37 +00002199 VG_(needs_sanity_checks) (ms_cheap_sanity_check,
2200 ms_expensive_sanity_check);
njnfc51f8d2005-06-21 03:20:17 +00002201 VG_(needs_malloc_replacement) (ms_malloc,
njn51d827b2005-05-09 01:02:08 +00002202 ms___builtin_new,
2203 ms___builtin_vec_new,
2204 ms_memalign,
2205 ms_calloc,
2206 ms_free,
2207 ms___builtin_delete,
2208 ms___builtin_vec_delete,
2209 ms_realloc,
2210 0 );
2211
njn51d827b2005-05-09 01:02:08 +00002212 // HP_Chunks
njn734b8052007-11-01 04:40:37 +00002213 malloc_list = VG_(HT_construct)( "Massif's malloc list" );
njn51d827b2005-05-09 01:02:08 +00002214
2215 // Dummy node at top of the context structure.
njn734b8052007-11-01 04:40:37 +00002216 alloc_xpt = new_XPt(/*ip*/0, /*parent*/NULL);
2217
2218 // Initialise alloc_fns.
2219 init_alloc_fns();
2220
2221 // Initialise args_for_massif.
2222 args_for_massif = VG_(newXA)(VG_(malloc), VG_(free), sizeof(HChar*));
njn51d827b2005-05-09 01:02:08 +00002223}
2224
sewardj45f4e7c2005-09-27 19:20:21 +00002225VG_DETERMINE_INTERFACE_VERSION(ms_pre_clo_init)
nethercotec9f36922004-02-14 16:40:02 +00002226
njn734b8052007-11-01 04:40:37 +00002227//--------------------------------------------------------------------//
2228//--- end ---//
2229//--------------------------------------------------------------------//