-
Notifications
You must be signed in to change notification settings - Fork 0
/
ms_main.c
executable file
·2628 lines (2274 loc) · 91.7 KB
/
ms_main.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
//--------------------------------------------------------------------*/
//--- Massif: a heap profiling tool. ms_main.c ---*/
//--------------------------------------------------------------------*/
/*
This file is part of Massif, a Valgrind tool for profiling memory
usage of programs.
Copyright (C) 2003-2013 Nicholas Nethercote
This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License as
published by the Free Software Foundation; either version 2 of the
License, or (at your option) any later version.
This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
02111-1307, USA.
The GNU General Public License is contained in the file COPYING.
*/
//---------------------------------------------------------------------------
// XXX:
//---------------------------------------------------------------------------
// Todo -- nice, but less critical:
// - do a graph-drawing test
// - make file format more generic. Obstacles:
// - unit prefixes are not generic
// - preset column widths for stats are not generic
// - preset column headers are not generic
// - "Massif arguments:" line is not generic
// - do snapshots on client requests
// - (Michael Meeks): have an interactive way to request a dump
// (callgrind_control-style)
// - "profile now"
// - "show me the extra allocations since the last snapshot"
// - "start/stop logging" (eg. quickly skip boring bits)
// - Add ability to draw multiple graphs, eg. heap-only, stack-only, total.
// Give each graph a title. (try to do it generically!)
// - allow truncation of long fnnames if the exact line number is
// identified? [hmm, could make getting the name of alloc-fns more
// difficult] [could dump full names to file, truncate in ms_print]
// - make --show-below-main=no work
// - Options like --alloc-fn='operator new(unsigned, std::nothrow_t const&)'
// don't work in a .valgrindrc file or in $VALGRIND_OPTS.
// m_commandline.c:add_args_from_string() needs to respect single quotes.
// - With --stack=yes, want to add a stack trace for detailed snapshots so
// it's clear where/why the peak is occurring. (Mattieu Castet) Also,
// possibly useful even with --stack=no? (Andi Yin)
//
// Performance:
// - To run the benchmarks:
//
// perl perf/vg_perf --tools=massif --reps=3 perf/{heap,tinycc} massif
// time valgrind --tool=massif --depth=100 konqueror
//
// The other benchmarks don't do much allocation, and so give similar speeds
// to Nulgrind.
//
// Timing results on 'nevermore' (njn's machine) as of r7013:
//
// heap 0.53s ma:12.4s (23.5x, -----)
// tinycc 0.46s ma: 4.9s (10.7x, -----)
// many-xpts 0.08s ma: 2.0s (25.0x, -----)
// konqueror 29.6s real 0:21.0s user
//
// [Introduction of --time-unit=i as the default slowed things down by
// roughly 0--20%.]
//
// - get_XCon accounts for about 9% of konqueror startup time. Try
// keeping XPt children sorted by 'ip' and use binary search in get_XCon.
// Requires factoring out binary search code from various places into a
// VG_(bsearch) function.
//
// Todo -- low priority:
// - In each XPt, record both bytes and the number of allocations, and
// possibly the global number of allocations.
// - (Andy Lin) Give a stack trace on detailed snapshots?
// - (Artur Wisz) add a feature to Massif to ignore any heap blocks larger
// than a certain size! Because: "linux's malloc allows to set a
// MMAP_THRESHOLD value, so we set it to 4096 - all blocks above that will
// be handled directly by the kernel, and are guaranteed to be returned to
// the system when freed. So we needed to profile only blocks below this
// limit."
//
// File format working notes:
#if 0
desc: --heap-admin=foo
cmd: date
time_unit: ms
#-----------
snapshot=0
#-----------
time=0
mem_heap_B=0
mem_heap_admin_B=0
mem_stacks_B=0
heap_tree=empty
#-----------
snapshot=1
#-----------
time=353
mem_heap_B=5
mem_heap_admin_B=0
mem_stacks_B=0
heap_tree=detailed
n1: 5 (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
n1: 5 0x27F6E0: _nl_normalize_codeset (in /lib/libc-2.3.5.so)
n1: 5 0x279DE6: _nl_load_locale_from_archive (in /lib/libc-2.3.5.so)
n1: 5 0x278E97: _nl_find_locale (in /lib/libc-2.3.5.so)
n1: 5 0x278871: setlocale (in /lib/libc-2.3.5.so)
n1: 5 0x8049821: (within /bin/date)
n0: 5 0x26ED5E: (below main) (in /lib/libc-2.3.5.so)
n_events: n time(ms) total(B) useful-heap(B) admin-heap(B) stacks(B)
t_events: B
n 0 0 0 0 0
n 0 0 0 0 0
t1: 5 <string...>
t1: 6 <string...>
Ideas:
- each snapshot specifies an x-axis value and one or more y-axis values.
- can display the y-axis values separately if you like
- can completely separate connection between snapshots and trees.
Challenges:
- how to specify and scale/abbreviate units on axes?
- how to combine multiple values into the y-axis?
--------------------------------------------------------------------------------Command: date
Massif arguments: --heap-admin=foo
ms_print arguments: massif.out
--------------------------------------------------------------------------------
KB
6.472^ :#
| :# :: . .
...
| ::@ :@ :@ :@:::# :: : ::::
0 +-----------------------------------@---@---@-----@--@---#-------------->ms 0 713
Number of snapshots: 50
Detailed snapshots: [2, 11, 13, 19, 25, 32 (peak)]
-------------------------------------------------------------------------------- n time(ms) total(B) useful-heap(B) admin-heap(B) stacks(B)
-------------------------------------------------------------------------------- 0 0 0 0 0 0
1 345 5 5 0 0
2 353 5 5 0 0
100.00% (5B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->100.00% (5B) 0x27F6E0: _nl_normalize_codeset (in /lib/libc-2.3.5.so)
#endif
//---------------------------------------------------------------------------
#include "pub_tool_basics.h"
#include "pub_tool_vki.h"
#include "pub_tool_aspacemgr.h"
#include "pub_tool_debuginfo.h"
#include "pub_tool_hashtable.h"
#include "pub_tool_libcbase.h"
#include "pub_tool_libcassert.h"
#include "pub_tool_libcfile.h"
#include "pub_tool_libcprint.h"
#include "pub_tool_libcproc.h"
#include "pub_tool_machine.h"
#include "pub_tool_mallocfree.h"
#include "pub_tool_options.h"
#include "pub_tool_replacemalloc.h"
#include "pub_tool_stacktrace.h"
#include "pub_tool_threadstate.h"
#include "pub_tool_tooliface.h"
#include "pub_tool_xarray.h"
#include "pub_tool_clientstate.h"
#include "pub_tool_gdbserver.h"
#include "pub_tool_clreq.h" // For {MALLOC,FREE}LIKE_BLOCK
//------------------------------------------------------------*/
//--- Overview of operation ---*/
//------------------------------------------------------------*/
// The size of the stacks and heap is tracked. The heap is tracked in a lot
// of detail, enough to tell how many bytes each line of code is responsible
// for, more or less. The main data structure is a tree representing the
// call tree beneath all the allocation functions like malloc().
// (Alternatively, if --pages-as-heap=yes is specified, memory is tracked at
// the page level, and each page is treated much like a heap block. We use
// "heap" throughout below to cover this case because the concepts are all the
// same.)
//
// "Snapshots" are recordings of the memory usage. There are two basic
// kinds:
// - Normal: these record the current time, total memory size, total heap
// size, heap admin size and stack size.
// - Detailed: these record those things in a normal snapshot, plus a very
// detailed XTree (see below) indicating how the heap is structured.
//
// Snapshots are taken every so often. There are two storage classes of
// snapshots:
// - Temporary: Massif does a temporary snapshot every so often. The idea
// is to always have a certain number of temporary snapshots around. So
// we take them frequently to begin with, but decreasingly often as the
// program continues to run. Also, we remove some old ones after a while.
// Overall it's a kind of exponential decay thing. Most of these are
// normal snapshots, a small fraction are detailed snapshots.
// - Permanent: Massif takes a permanent (detailed) snapshot in some
// circumstances. They are:
// - Peak snapshot: When the memory usage peak is reached, it takes a
// snapshot. It keeps this, unless the peak is subsequently exceeded,
// in which case it will overwrite the peak snapshot.
// - User-requested snapshots: These are done in response to client
// requests. They are always kept.
// Used for printing things when clo_verbosity > 1.
#define VERB(verb, format, args...) \
if (VG_(clo_verbosity) > verb) { \
VG_(dmsg)("Massif: " format, ##args); \
}
// Used for printing stats when clo_stats == True.
#define STATS(format, args...) \
if (VG_(clo_stats)) { \
VG_(dmsg)("Massif: " format, ##args); \
}
//------------------------------------------------------------//
//--- Statistics ---//
//------------------------------------------------------------//
// Konqueror startup, to give an idea of the numbers involved with a biggish
// program, with default depth:
//
// depth=3 depth=40
// - 310,000 allocations
// - 300,000 frees
// - 15,000 XPts 800,000 XPts
// - 1,800 top-XPts
static UInt n_heap_allocs = 0;
static UInt n_heap_reallocs = 0;
static UInt n_heap_frees = 0;
static UInt n_ignored_heap_allocs = 0;
static UInt n_ignored_heap_frees = 0;
static UInt n_ignored_heap_reallocs = 0;
static UInt n_stack_allocs = 0;
static UInt n_stack_frees = 0;
static UInt n_xpts = 0;
static UInt n_xpt_init_expansions = 0;
static UInt n_xpt_later_expansions = 0;
static UInt n_sxpt_allocs = 0;
static UInt n_sxpt_frees = 0;
static UInt n_skipped_snapshots = 0;
static UInt n_real_snapshots = 0;
static UInt n_detailed_snapshots = 0;
static UInt n_peak_snapshots = 0;
static UInt n_cullings = 0;
static UInt n_XCon_redos = 0;
//------------------------------------------------------------//
//--- Globals ---//
//------------------------------------------------------------//
// Number of guest instructions executed so far. Only used with
// --time-unit=i.
static Long guest_instrs_executed = 0;
static SizeT heap_szB = 0; // Live heap size
static SizeT heap_extra_szB = 0; // Live heap extra size -- slop + admin bytes
static SizeT stacks_szB = 0; // Live stacks size
// This is the total size from the current peak snapshot, or 0 if no peak
// snapshot has been taken yet.
static SizeT peak_snapshot_total_szB = 0;
// Incremented every time memory is allocated/deallocated, by the
// allocated/deallocated amount; includes heap, heap-admin and stack
// memory. An alternative to milliseconds as a unit of program "time".
static ULong total_allocs_deallocs_szB = 0;
// When running with --heap=yes --pages-as-heap=no, we don't start taking
// snapshots until the first basic block is executed, rather than doing it in
// ms_post_clo_init (which is the obvious spot), for two reasons.
// - It lets us ignore stack events prior to that, because they're not
// really proper ones and just would screw things up.
// - Because there's still some core initialisation to do, and so there
// would be an artificial time gap between the first and second snapshots.
//
// When running with --heap=yes --pages-as-heap=yes, snapshots start much
// earlier due to new_mem_startup so this isn't relevant.
//
static Bool have_started_executing_code = False;
//------------------------------------------------------------//
//--- Alloc fns ---//
//------------------------------------------------------------//
static XArray* alloc_fns;
static XArray* ignore_fns;
static void init_alloc_fns(void)
{
// Create the list, and add the default elements.
alloc_fns = VG_(newXA)(VG_(malloc), "ms.main.iaf.1",
VG_(free), sizeof(HChar*));
#define DO(x) { const HChar* s = x; VG_(addToXA)(alloc_fns, &s); }
// Ordered roughly according to (presumed) frequency.
// Nb: The C++ "operator new*" ones are overloadable. We include them
// always anyway, because even if they're overloaded, it would be a
// prodigiously stupid overloading that caused them to not allocate
// memory.
//
// XXX: because we don't look at the first stack entry (unless it's a
// custom allocation) there's not much point to having all these alloc
// functions here -- they should never appear anywhere (I think?) other
// than the top stack entry. The only exceptions are those that in
// vg_replace_malloc.c are partly or fully implemented in terms of another
// alloc function: realloc (which uses malloc); valloc,
// malloc_zone_valloc, posix_memalign and memalign_common (which use
// memalign).
//
DO("malloc" );
DO("__builtin_new" );
DO("operator new(unsigned)" );
DO("operator new(unsigned long)" );
DO("__builtin_vec_new" );
DO("operator new[](unsigned)" );
DO("operator new[](unsigned long)" );
DO("calloc" );
DO("realloc" );
DO("memalign" );
DO("posix_memalign" );
DO("valloc" );
DO("operator new(unsigned, std::nothrow_t const&)" );
DO("operator new[](unsigned, std::nothrow_t const&)" );
DO("operator new(unsigned long, std::nothrow_t const&)" );
DO("operator new[](unsigned long, std::nothrow_t const&)");
#if defined(VGO_darwin)
DO("malloc_zone_malloc" );
DO("malloc_zone_calloc" );
DO("malloc_zone_realloc" );
DO("malloc_zone_memalign" );
DO("malloc_zone_valloc" );
#endif
}
static void init_ignore_fns(void)
{
// Create the (empty) list.
ignore_fns = VG_(newXA)(VG_(malloc), "ms.main.iif.1",
VG_(free), sizeof(HChar*));
}
// Determines if the named function is a member of the XArray.
static Bool is_member_fn(XArray* fns, const HChar* fnname)
{
HChar** fn_ptr;
Int i;
// Nb: It's a linear search through the list, because we're comparing
// strings rather than pointers to strings.
// Nb: This gets called a lot. It was an OSet, but they're quite slow to
// iterate through so it wasn't a good choice.
for (i = 0; i < VG_(sizeXA)(fns); i++) {
fn_ptr = VG_(indexXA)(fns, i);
if (VG_STREQ(fnname, *fn_ptr))
return True;
}
return False;
}
//------------------------------------------------------------//
//--- Command line args ---//
//------------------------------------------------------------//
#define MAX_DEPTH 200
typedef enum { TimeI, TimeMS, TimeB } TimeUnit;
static const HChar* TimeUnit_to_string(TimeUnit time_unit)
{
switch (time_unit) {
case TimeI: return "i";
case TimeMS: return "ms";
case TimeB: return "B";
default: tl_assert2(0, "TimeUnit_to_string: unrecognised TimeUnit");
}
}
static Bool clo_heap = True;
// clo_heap_admin is deliberately a word-sized type. At one point it was
// a UInt, but this caused problems on 64-bit machines when it was
// multiplied by a small negative number and then promoted to a
// word-sized type -- it ended up with a value of 4.2 billion. Sigh.
static SSizeT clo_heap_admin = 8;
static Bool clo_pages_as_heap = False;
static Bool clo_stacks = False;
static Int clo_depth = 30;
static double clo_threshold = 1.0; // percentage
static double clo_peak_inaccuracy = 1.0; // percentage
static Int clo_time_unit = TimeI;
static Int clo_detailed_freq = 10;
static Int clo_max_snapshots = 100;
static const HChar* clo_massif_out_file = "massif.out.%p";
static XArray* args_for_massif;
static Bool ms_process_cmd_line_option(const HChar* arg)
{
const HChar* tmp_str;
// Remember the arg for later use.
VG_(addToXA)(args_for_massif, &arg);
if VG_BOOL_CLO(arg, "--heap", clo_heap) {}
else if VG_BINT_CLO(arg, "--heap-admin", clo_heap_admin, 0, 1024) {}
else if VG_BOOL_CLO(arg, "--stacks", clo_stacks) {}
else if VG_BOOL_CLO(arg, "--pages-as-heap", clo_pages_as_heap) {}
else if VG_BINT_CLO(arg, "--depth", clo_depth, 1, MAX_DEPTH) {}
else if VG_STR_CLO(arg, "--alloc-fn", tmp_str) {
VG_(addToXA)(alloc_fns, &tmp_str);
}
else if VG_STR_CLO(arg, "--ignore-fn", tmp_str) {
VG_(addToXA)(ignore_fns, &tmp_str);
}
else if VG_DBL_CLO(arg, "--threshold", clo_threshold) {
if (clo_threshold < 0 || clo_threshold > 100) {
VG_(fmsg_bad_option)(arg,
"--threshold must be between 0.0 and 100.0\n");
}
}
else if VG_DBL_CLO(arg, "--peak-inaccuracy", clo_peak_inaccuracy) {}
else if VG_XACT_CLO(arg, "--time-unit=i", clo_time_unit, TimeI) {}
else if VG_XACT_CLO(arg, "--time-unit=ms", clo_time_unit, TimeMS) {}
else if VG_XACT_CLO(arg, "--time-unit=B", clo_time_unit, TimeB) {}
else if VG_BINT_CLO(arg, "--detailed-freq", clo_detailed_freq, 1, 1000000) {}
else if VG_BINT_CLO(arg, "--max-snapshots", clo_max_snapshots, 10, 1000) {}
else if VG_STR_CLO(arg, "--massif-out-file", clo_massif_out_file) {}
else
return VG_(replacement_malloc_process_cmd_line_option)(arg);
return True;
}
static void ms_print_usage(void)
{
VG_(printf)(
" --heap=no|yes profile heap blocks [yes]\n"
" --heap-admin=<size> average admin bytes per heap block;\n"
" ignored if --heap=no [8]\n"
" --stacks=no|yes profile stack(s) [no]\n"
" --pages-as-heap=no|yes profile memory at the page level [no]\n"
" --depth=<number> depth of contexts [30]\n"
" --alloc-fn=<name> specify <name> as an alloc function [empty]\n"
" --ignore-fn=<name> ignore heap allocations within <name> [empty]\n"
" --threshold=<m.n> significance threshold, as a percentage [1.0]\n"
" --peak-inaccuracy=<m.n> maximum peak inaccuracy, as a percentage [1.0]\n"
" --time-unit=i|ms|B time unit: instructions executed, milliseconds\n"
" or heap bytes alloc'd/dealloc'd [i]\n"
" --detailed-freq=<N> every Nth snapshot should be detailed [10]\n"
" --max-snapshots=<N> maximum number of snapshots recorded [100]\n"
" --massif-out-file=<file> output file name [massif.out.%%p]\n"
);
}
static void ms_print_debug_usage(void)
{
VG_(printf)(
" (none)\n"
);
}
//------------------------------------------------------------//
//--- XPts, XTrees and XCons ---//
//------------------------------------------------------------//
// An XPt represents an "execution point", ie. a code address. Each XPt is
// part of a tree of XPts (an "execution tree", or "XTree"). The details of
// the heap are represented by a single XTree.
//
// The root of the tree is 'alloc_xpt', which represents all allocation
// functions, eg:
// - malloc/calloc/realloc/memalign/new/new[];
// - user-specified allocation functions (using --alloc-fn);
// - custom allocation (MALLOCLIKE) points
// It's a bit of a fake XPt (ie. its 'ip' is zero), and is only used because
// it makes the code simpler.
//
// Any child of 'alloc_xpt' is called a "top-XPt". The XPts at the bottom
// of an XTree (leaf nodes) are "bottom-XPTs".
//
// Each path from a top-XPt to a bottom-XPt through an XTree gives an
// execution context ("XCon"), ie. a stack trace. (And sub-paths represent
// stack sub-traces.) The number of XCons in an XTree is equal to the
// number of bottom-XPTs in that XTree.
//
// alloc_xpt XTrees are bi-directional.
// | ^
// v |
// > parent < Example: if child1() calls parent() and child2()
// / | \ also calls parent(), and parent() calls malloc(),
// | / \ | the XTree will look like this.
// | v v |
// child1 child2
//
// (Note that malformed stack traces can lead to difficulties. See the
// comment at the bottom of get_XCon.)
//
// XTrees and XPts are mirrored by SXTrees and SXPts, where the 'S' is short
// for "saved". When the XTree is duplicated for a snapshot, we duplicate
// it as an SXTree, which is similar but omits some things it does not need,
// and aggregates up insignificant nodes. This is important as an SXTree is
// typically much smaller than an XTree.
// XXX: make XPt and SXPt extensible arrays, to avoid having to do two
// allocations per Pt.
typedef struct _XPt XPt;
struct _XPt {
Addr ip; // code address
// Bottom-XPts: space for the precise context.
// Other XPts: space of all the descendent bottom-XPts.
// Nb: this value goes up and down as the program executes.
SizeT szB;
XPt* parent; // pointer to parent XPt
// Children.
// n_children and max_children are 32-bit integers. 16-bit integers
// are too small -- a very big program might have more than 65536
// allocation points (ie. top-XPts) -- Konqueror starting up has 1800.
UInt n_children; // number of children
UInt max_children; // capacity of children array
XPt** children; // pointers to children XPts
};
typedef
enum {
SigSXPt,
InsigSXPt
}
SXPtTag;
typedef struct _SXPt SXPt;
struct _SXPt {
SXPtTag tag;
SizeT szB; // memory size for the node, be it Sig or Insig
union {
// An SXPt representing a single significant code location. Much like
// an XPt, minus the fields that aren't necessary.
struct {
Addr ip;
UInt n_children;
SXPt** children;
}
Sig;
// An SXPt representing one or more code locations, all below the
// significance threshold.
struct {
Int n_xpts; // number of aggregated XPts
}
Insig;
};
};
// Fake XPt representing all allocation functions like malloc(). Acts as
// parent node to all top-XPts.
static XPt* alloc_xpt;
static XPt* new_XPt(Addr ip, XPt* parent)
{
// XPts are never freed, so we can use VG_(perm_malloc) to allocate them.
// Note that we cannot use VG_(perm_malloc) for the 'children' array, because
// that needs to be resizable.
XPt* xpt = VG_(perm_malloc)(sizeof(XPt), vg_alignof(XPt));
xpt->ip = ip;
xpt->szB = 0;
xpt->parent = parent;
// We don't initially allocate any space for children. We let that
// happen on demand. Many XPts (ie. all the bottom-XPts) don't have any
// children anyway.
xpt->n_children = 0;
xpt->max_children = 0;
xpt->children = NULL;
// Update statistics
n_xpts++;
return xpt;
}
static void add_child_xpt(XPt* parent, XPt* child)
{
// Expand 'children' if necessary.
tl_assert(parent->n_children <= parent->max_children);
if (parent->n_children == parent->max_children) {
if (0 == parent->max_children) {
parent->max_children = 4;
parent->children = VG_(malloc)( "ms.main.acx.1",
parent->max_children * sizeof(XPt*) );
n_xpt_init_expansions++;
} else {
parent->max_children *= 2; // Double size
parent->children = VG_(realloc)( "ms.main.acx.2",
parent->children,
parent->max_children * sizeof(XPt*) );
n_xpt_later_expansions++;
}
}
// Insert new child XPt in parent's children list.
parent->children[ parent->n_children++ ] = child;
}
// Reverse comparison for a reverse sort -- biggest to smallest.
static Int SXPt_revcmp_szB(const void* n1, const void* n2)
{
const SXPt* sxpt1 = *(const SXPt *const *)n1;
const SXPt* sxpt2 = *(const SXPt *const *)n2;
return ( sxpt1->szB < sxpt2->szB ? 1
: sxpt1->szB > sxpt2->szB ? -1
: 0);
}
//------------------------------------------------------------//
//--- XTree Operations ---//
//------------------------------------------------------------//
// Duplicates an XTree as an SXTree.
static SXPt* dup_XTree(XPt* xpt, SizeT total_szB)
{
Int i, n_sig_children, n_insig_children, n_child_sxpts;
SizeT sig_child_threshold_szB;
SXPt* sxpt;
// Number of XPt children Action for SXPT
// ------------------ ---------------
// 0 sig, 0 insig alloc 0 children
// N sig, 0 insig alloc N children, dup all
// N sig, M insig alloc N+1, dup first N, aggregate remaining M
// 0 sig, M insig alloc 1, aggregate M
// Work out how big a child must be to be significant. If the current
// total_szB is zero, then we set it to 1, which means everything will be
// judged insignificant -- this is sensible, as there's no point showing
// any detail for this case. Unless they used --threshold=0, in which
// case we show them everything because that's what they asked for.
//
// Nb: We do this once now, rather than once per child, because if we do
// that the cost of all the divisions adds up to something significant.
if (0 == total_szB && 0 != clo_threshold) {
sig_child_threshold_szB = 1;
} else {
sig_child_threshold_szB = (SizeT)((total_szB * clo_threshold) / 100);
}
// How many children are significant? And do we need an aggregate SXPt?
n_sig_children = 0;
for (i = 0; i < xpt->n_children; i++) {
if (xpt->children[i]->szB >= sig_child_threshold_szB) {
n_sig_children++;
}
}
n_insig_children = xpt->n_children - n_sig_children;
n_child_sxpts = n_sig_children + ( n_insig_children > 0 ? 1 : 0 );
// Duplicate the XPt.
sxpt = VG_(malloc)("ms.main.dX.1", sizeof(SXPt));
n_sxpt_allocs++;
sxpt->tag = SigSXPt;
sxpt->szB = xpt->szB;
sxpt->Sig.ip = xpt->ip;
sxpt->Sig.n_children = n_child_sxpts;
// Create the SXPt's children.
if (n_child_sxpts > 0) {
Int j;
SizeT sig_children_szB = 0, insig_children_szB = 0;
sxpt->Sig.children = VG_(malloc)("ms.main.dX.2",
n_child_sxpts * sizeof(SXPt*));
// Duplicate the significant children. (Nb: sig_children_szB +
// insig_children_szB doesn't necessarily equal xpt->szB.)
j = 0;
for (i = 0; i < xpt->n_children; i++) {
if (xpt->children[i]->szB >= sig_child_threshold_szB) {
sxpt->Sig.children[j++] = dup_XTree(xpt->children[i], total_szB);
sig_children_szB += xpt->children[i]->szB;
} else {
insig_children_szB += xpt->children[i]->szB;
}
}
// Create the SXPt for the insignificant children, if any, and put it
// in the last child entry.
if (n_insig_children > 0) {
// Nb: We 'n_sxpt_allocs' here because creating an Insig SXPt
// doesn't involve a call to dup_XTree().
SXPt* insig_sxpt = VG_(malloc)("ms.main.dX.3", sizeof(SXPt));
n_sxpt_allocs++;
insig_sxpt->tag = InsigSXPt;
insig_sxpt->szB = insig_children_szB;
insig_sxpt->Insig.n_xpts = n_insig_children;
sxpt->Sig.children[n_sig_children] = insig_sxpt;
}
} else {
sxpt->Sig.children = NULL;
}
return sxpt;
}
static void free_SXTree(SXPt* sxpt)
{
Int i;
tl_assert(sxpt != NULL);
switch (sxpt->tag) {
case SigSXPt:
// Free all children SXPts, then the children array.
for (i = 0; i < sxpt->Sig.n_children; i++) {
free_SXTree(sxpt->Sig.children[i]);
sxpt->Sig.children[i] = NULL;
}
VG_(free)(sxpt->Sig.children); sxpt->Sig.children = NULL;
break;
case InsigSXPt:
break;
default: tl_assert2(0, "free_SXTree: unknown SXPt tag");
}
// Free the SXPt itself.
VG_(free)(sxpt); sxpt = NULL;
n_sxpt_frees++;
}
// Sanity checking: we periodically check the heap XTree with
// ms_expensive_sanity_check.
static void sanity_check_XTree(XPt* xpt, XPt* parent)
{
tl_assert(xpt != NULL);
// Check back-pointer.
tl_assert2(xpt->parent == parent,
"xpt->parent = %p, parent = %p\n", xpt->parent, parent);
// Check children counts look sane.
tl_assert(xpt->n_children <= xpt->max_children);
// Unfortunately, xpt's size is not necessarily equal to the sum of xpt's
// children's sizes. See comment at the bottom of get_XCon.
}
// Sanity checking: we check SXTrees (which are in snapshots) after
// snapshots are created, before they are deleted, and before they are
// printed.
static void sanity_check_SXTree(SXPt* sxpt)
{
Int i;
tl_assert(sxpt != NULL);
// Check the sum of any children szBs equals the SXPt's szB. Check the
// children at the same time.
switch (sxpt->tag) {
case SigSXPt: {
if (sxpt->Sig.n_children > 0) {
for (i = 0; i < sxpt->Sig.n_children; i++) {
sanity_check_SXTree(sxpt->Sig.children[i]);
}
}
break;
}
case InsigSXPt:
break; // do nothing
default: tl_assert2(0, "sanity_check_SXTree: unknown SXPt tag");
}
}
//------------------------------------------------------------//
//--- XCon Operations ---//
//------------------------------------------------------------//
// This is the limit on the number of removed alloc-fns that can be in a
// single XCon.
#define MAX_OVERESTIMATE 50
#define MAX_IPS (MAX_DEPTH + MAX_OVERESTIMATE)
// This is used for various buffers which can hold function names/IP
// description. Some C++ names can get really long so 1024 isn't big
// enough.
#define BUF_LEN 2048
// Determine if the given IP belongs to a function that should be ignored.
static Bool fn_should_be_ignored(Addr ip)
{
static HChar buf[BUF_LEN];
return
( VG_(get_fnname)(ip, buf, BUF_LEN) && is_member_fn(ignore_fns, buf)
? True : False );
}
// Get the stack trace for an XCon, filtering out uninteresting entries:
// alloc-fns and entries above alloc-fns, and entries below main-or-below-main.
// Eg: alloc-fn1 / alloc-fn2 / a / b / main / (below main) / c
// becomes: a / b / main
// Nb: it's possible to end up with an empty trace, eg. if 'main' is marked
// as an alloc-fn. This is ok.
static
Int get_IPs( ThreadId tid, Bool exclude_first_entry, Addr ips[])
{
static HChar buf[BUF_LEN];
Int n_ips, i, n_alloc_fns_removed;
Int overestimate;
Bool redo;
// We ask for a few more IPs than clo_depth suggests we need. Then we
// remove every entry that is an alloc-fn. Depending on the
// circumstances, we may need to redo it all, asking for more IPs.
// Details:
// - If the original stack trace is smaller than asked-for, redo=False
// - Else if after filtering we have >= clo_depth IPs, redo=False
// - Else redo=True
// In other words, to redo, we'd have to get a stack trace as big as we
// asked for and remove more than 'overestimate' alloc-fns.
// Main loop.
redo = True; // Assume this to begin with.
for (overestimate = 3; redo; overestimate += 6) {
// This should never happen -- would require MAX_OVERESTIMATE
// alloc-fns to be removed from the stack trace.
if (overestimate > MAX_OVERESTIMATE)
VG_(tool_panic)("get_IPs: ips[] too small, inc. MAX_OVERESTIMATE?");
// Ask for more IPs than clo_depth suggests we need.
n_ips = VG_(get_StackTrace)( tid, ips, clo_depth + overestimate,
NULL/*array to dump SP values in*/,
NULL/*array to dump FP values in*/,
0/*first_ip_delta*/ );
tl_assert(n_ips > 0);
// If the original stack trace is smaller than asked-for, redo=False.
if (n_ips < clo_depth + overestimate) { redo = False; }
// Filter out alloc fns. If requested, we automatically remove the
// first entry (which presumably will be something like malloc or
// __builtin_new that we're sure to filter out) without looking at it,
// because VG_(get_fnname) is expensive.
n_alloc_fns_removed = ( exclude_first_entry ? 1 : 0 );
for (i = n_alloc_fns_removed; i < n_ips; i++) {
if (VG_(get_fnname)(ips[i], buf, BUF_LEN)) {
if (is_member_fn(alloc_fns, buf)) {
n_alloc_fns_removed++;
} else {
break;
}
}
}
// Remove the alloc fns by shuffling the rest down over them.
n_ips -= n_alloc_fns_removed;
for (i = 0; i < n_ips; i++) {
ips[i] = ips[i + n_alloc_fns_removed];
}
// If after filtering we have >= clo_depth IPs, redo=False
if (n_ips >= clo_depth) {
redo = False;
n_ips = clo_depth; // Ignore any IPs below --depth.
}
if (redo) {
n_XCon_redos++;
}
}
return n_ips;
}
// Gets an XCon and puts it in the tree. Returns the XCon's bottom-XPt.
// Unless the allocation should be ignored, in which case we return NULL.
static XPt* get_XCon( ThreadId tid, Bool exclude_first_entry )
{
static Addr ips[MAX_IPS];
Int i;
XPt* xpt = alloc_xpt;
// After this call, the IPs we want are in ips[0]..ips[n_ips-1].
Int n_ips = get_IPs(tid, exclude_first_entry, ips);
// Should we ignore this allocation? (Nb: n_ips can be zero, eg. if
// 'main' is marked as an alloc-fn.)
if (n_ips > 0 && fn_should_be_ignored(ips[0])) {
return NULL;
}
// Now do the search/insertion of the XCon.
for (i = 0; i < n_ips; i++) {
Addr ip = ips[i];
Int ch;
// Look for IP in xpt's children.
// Linear search, ugh -- about 10% of time for konqueror startup tried
// caching last result, only hit about 4% for konqueror.
// Nb: this search hits about 98% of the time for konqueror
for (ch = 0; True; ch++) {
if (ch == xpt->n_children) {
// IP not found in the children.
// Create and add new child XPt, then stop.
XPt* new_child_xpt = new_XPt(ip, xpt);
add_child_xpt(xpt, new_child_xpt);
xpt = new_child_xpt;
break;
} else if (ip == xpt->children[ch]->ip) {
// Found the IP in the children, stop.
xpt = xpt->children[ch];
break;
}
}
}
// [Note: several comments refer to this comment. Do not delete it
// without updating them.]
//
// A complication... If all stack traces were well-formed, then the
// returned xpt would always be a bottom-XPt. As a consequence, an XPt's
// size would always be equal to the sum of its children's sizes, which
// is an excellent sanity check.
//
// Unfortunately, stack traces occasionally are malformed, ie. truncated.
// This allows a stack trace to be a sub-trace of another, eg. a/b/c is a
// sub-trace of a/b/c/d. So we can't assume this xpt is a bottom-XPt;
// nor can we do sanity check an XPt's size against its children's sizes.
// This is annoying, but must be dealt with. (Older versions of Massif
// had this assertion in, and it was reported to fail by real users a
// couple of times.) Even more annoyingly, I can't come up with a simple
// test case that exhibit such a malformed stack trace, so I can't
// regression test it. Sigh.
//
// However, we can print a warning, so that if it happens (unexpectedly)
// in existing regression tests we'll know. Also, it warns users that
// the output snapshots may not add up the way they might expect.
//
//tl_assert(0 == xpt->n_children); // Must be bottom-XPt
if (0 != xpt->n_children) {
static Int n_moans = 0;
if (n_moans < 3) {
VG_(umsg)(
"Warning: Malformed stack trace detected. In Massif's output,\n");
VG_(umsg)(
" the size of an entry's child entries may not sum up\n");
VG_(umsg)(
" to the entry's size as they normally do.\n");
n_moans++;
if (3 == n_moans)
VG_(umsg)(
" (And Massif now won't warn about this again.)\n");
}
}
return xpt;
}
// Update 'szB' of every XPt in the XCon, by percolating upwards.
static void update_XCon(XPt* xpt, SSizeT space_delta)
{
tl_assert(clo_heap);
tl_assert(NULL != xpt);
if (0 == space_delta)
return;
while (xpt != alloc_xpt) {
if (space_delta < 0) tl_assert(xpt->szB >= -space_delta);