2 //--------------------------------------------------------------------//
3 //--- DHAT: a Dynamic Heap Analysis Tool dh_main.c ---//
4 //--------------------------------------------------------------------//
7 This file is part of DHAT, a Valgrind tool for profiling the
8 heap usage of programs.
10 Copyright (C) 2010-2018 Mozilla Foundation
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.
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.
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
27 The GNU General Public License is contained in the file COPYING.
30 /* Contributed by Julian Seward <jseward@acm.org> */
33 #include "pub_tool_basics.h"
34 #include "pub_tool_clientstate.h"
35 #include "pub_tool_libcbase.h"
36 #include "pub_tool_libcassert.h"
37 #include "pub_tool_libcfile.h"
38 #include "pub_tool_libcprint.h"
39 #include "pub_tool_libcproc.h"
40 #include "pub_tool_machine.h" // VG_(fnptr_to_fnentry)
41 #include "pub_tool_mallocfree.h"
42 #include "pub_tool_options.h"
43 #include "pub_tool_replacemalloc.h"
44 #include "pub_tool_tooliface.h"
45 #include "pub_tool_wordfm.h"
47 #define HISTOGRAM_SIZE_LIMIT 1024
49 //------------------------------------------------------------//
51 //------------------------------------------------------------//
53 // Values for the entire run.
54 static ULong g_total_blocks
= 0;
55 static ULong g_total_bytes
= 0;
58 static ULong g_curr_blocks
= 0;
59 static ULong g_curr_bytes
= 0;
60 static ULong g_curr_instrs
= 0; // incremented from generated code
62 // Values at the global max, i.e. when g_curr_bytes peaks.
63 static ULong g_max_blocks
= 0;
64 static ULong g_max_bytes
= 0;
65 static ULong g_max_instrs
= 0;
67 // Values for the entire run. Computed at the end.
68 static ULong g_reads_bytes
= 0;
69 static ULong g_writes_bytes
= 0;
71 //------------------------------------------------------------//
72 //--- an Interval Tree of live blocks ---//
73 //------------------------------------------------------------//
75 /* Tracks information about live blocks. */
80 ExeContext
* ap
; /* allocation ec */
81 ULong allocd_at
; /* instruction number */
84 /* Approx histogram, one byte per payload byte. Counts latch up
85 therefore at 0xFFFF. Can be NULL if the block is resized or if
86 the block is larger than HISTOGRAM_SIZE_LIMIT. */
87 UShort
* histoW
; /* [0 .. req_szB-1] */
91 /* May not contain zero-sized blocks. May not contain
92 overlapping blocks. */
93 static WordFM
* interval_tree
= NULL
; /* WordFM* Block* void */
95 /* Here's the comparison function. Since the tree is required
96 to contain non-zero sized, non-overlapping blocks, it's good
97 enough to consider any overlap as a match. */
98 static Word
interval_tree_Cmp ( UWord k1
, UWord k2
)
100 Block
* b1
= (Block
*)k1
;
101 Block
* b2
= (Block
*)k2
;
102 tl_assert(b1
->req_szB
> 0);
103 tl_assert(b2
->req_szB
> 0);
104 if (b1
->payload
+ b1
->req_szB
<= b2
->payload
) return -1;
105 if (b2
->payload
+ b2
->req_szB
<= b1
->payload
) return 1;
109 // 2-entry cache for find_Block_containing
110 static Block
* fbc_cache0
= NULL
;
111 static Block
* fbc_cache1
= NULL
;
113 static UWord stats__n_fBc_cached
= 0;
114 static UWord stats__n_fBc_uncached
= 0;
115 static UWord stats__n_fBc_notfound
= 0;
117 static Block
* find_Block_containing ( Addr a
)
119 if (LIKELY(fbc_cache0
120 && fbc_cache0
->payload
<= a
121 && a
< fbc_cache0
->payload
+ fbc_cache0
->req_szB
)) {
123 stats__n_fBc_cached
++;
126 if (LIKELY(fbc_cache1
127 && fbc_cache1
->payload
<= a
128 && a
< fbc_cache1
->payload
+ fbc_cache1
->req_szB
)) {
129 // found at 1; swap 0 and 1
130 Block
* tmp
= fbc_cache0
;
131 fbc_cache0
= fbc_cache1
;
133 stats__n_fBc_cached
++;
141 Bool found
= VG_(lookupFM
)( interval_tree
,
142 &foundkey
, &foundval
, (UWord
)&fake
);
144 stats__n_fBc_notfound
++;
147 tl_assert(foundval
== 0); // we don't store vals in the interval tree
148 tl_assert(foundkey
!= 1);
149 Block
* res
= (Block
*)foundkey
;
150 tl_assert(res
!= &fake
);
151 // put at the top position
152 fbc_cache1
= fbc_cache0
;
154 stats__n_fBc_uncached
++;
158 // delete a block; asserts if not found. (viz, 'a' must be
159 // known to be present.)
160 static void delete_Block_starting_at ( Addr a
)
165 Bool found
= VG_(delFromFM
)( interval_tree
,
166 NULL
, NULL
, (Addr
)&fake
);
168 fbc_cache0
= fbc_cache1
= NULL
;
172 //------------------------------------------------------------//
173 //--- a FM of allocation points (APs) ---//
174 //------------------------------------------------------------//
178 // The allocation point that we're summarising stats for.
181 // Total number of blocks and bytes allocated by this AP.
185 // The current number of blocks and bytes live for this AP.
189 // Values at the AP max, i.e. when this AP's curr_bytes peaks.
190 ULong max_blocks
; // Blocks at the AP max.
191 ULong max_bytes
; // The AP max, measured in bytes.
193 // Values at the global max.
194 ULong at_tgmax_blocks
;
195 ULong at_tgmax_bytes
;
197 // Total lifetimes of all blocks allocated by this AP. Includes blocks
198 // explicitly freed and blocks implicitly freed at termination.
199 ULong total_lifetimes_instrs
;
201 // Number of blocks freed by this AP. (Only used in assertions.)
204 // Total number of reads and writes in all blocks allocated
209 /* Histogram information. We maintain a histogram aggregated for
210 all retiring Blocks allocated by this AP, but only if:
211 - this AP has only ever allocated objects of one size
212 - that size is <= HISTOGRAM_SIZE_LIMIT
213 What we need therefore is a mechanism to see if this AP
214 has only ever allocated blocks of one size.
217 Unknown because no retirement yet
218 Exactly xsize all retiring blocks are of this size
219 Mixed multiple different sizes seen
221 enum { Unknown
=999, Exactly
, Mixed
} xsize_tag
;
223 UInt
* histo
; /* [0 .. xsize-1] */
227 /* maps ExeContext*'s to APInfo*'s. Note that the keys must match the
228 .ap field in the values. */
229 static WordFM
* apinfo
= NULL
; /* WordFM* ExeContext* APInfo* */
232 // Are we at peak memory? If so, update at_tgmax_blocks and at_tgmax_bytes in
233 // all APInfos. Note that this is moderately expensive so we avoid calling it
234 // on every allocation.
235 static void check_for_peak(void)
237 if (g_curr_bytes
== g_max_bytes
) {
238 // It's a peak. (If there are multiple equal peaks we record the latest
241 VG_(initIterFM
)(apinfo
);
242 while (VG_(nextIterFM
)(apinfo
, &keyW
, &valW
)) {
243 APInfo
* api
= (APInfo
*)valW
;
244 tl_assert(api
&& api
->ap
== (ExeContext
*)keyW
);
245 api
->at_tgmax_blocks
= api
->curr_blocks
;
246 api
->at_tgmax_bytes
= api
->curr_bytes
;
248 VG_(doneIterFM
)(apinfo
);
252 /* 'bk' is being introduced (has just been allocated). Find the
253 relevant APInfo entry for it, or create one, based on the block's
254 allocation EC. Then, update the APInfo to the extent that we
255 actually can, to reflect the allocation. */
256 static void intro_Block ( Block
* bk
)
264 Bool found
= VG_(lookupFM
)( apinfo
,
265 &keyW
, &valW
, (UWord
)bk
->ap
);
268 tl_assert(keyW
== (UWord
)bk
->ap
);
270 api
= VG_(malloc
)( "dh.intro_Block.1", sizeof(APInfo
) );
271 VG_(memset
)(api
, 0, sizeof(*api
));
273 Bool present
= VG_(addToFM
)( apinfo
,
274 (UWord
)bk
->ap
, (UWord
)api
);
277 tl_assert(api
->freed_blocks
== 0);
278 api
->xsize_tag
= Unknown
;
280 if (0) VG_(printf
)("api %p --> Unknown\n", api
);
283 tl_assert(api
->ap
== bk
->ap
);
285 // Update global stats first.
288 g_total_bytes
+= bk
->req_szB
;
291 g_curr_bytes
+= bk
->req_szB
;
292 if (g_curr_bytes
> g_max_bytes
) {
293 g_max_blocks
= g_curr_blocks
;
294 g_max_bytes
= g_curr_bytes
;
295 g_max_instrs
= g_curr_instrs
;
298 // Now update APInfo stats.
301 api
->total_bytes
+= bk
->req_szB
;
304 api
->curr_bytes
+= bk
->req_szB
;
305 if (api
->curr_bytes
> api
->max_bytes
) {
306 api
->max_blocks
= api
->curr_blocks
;
307 api
->max_bytes
= api
->curr_bytes
;
311 /* 'bk' is retiring (being freed). Find the relevant APInfo entry for
312 it, which must already exist. Then, fold info from 'bk' into that
313 entry. 'because_freed' is True if the block is retiring because
314 the client has freed it. If it is False then the block is retiring
315 because the program has finished, in which case we want to skip the
316 updates of the total blocks live etc for this AP, but still fold in
317 the access counts and histo data that have so far accumulated for
319 static void retire_Block ( Block
* bk
, Bool because_freed
)
327 Bool found
= VG_(lookupFM
)( apinfo
,
328 &keyW
, &valW
, (UWord
)bk
->ap
);
332 tl_assert(api
->ap
== bk
->ap
);
334 // update stats following this free.
336 VG_(printf
)("ec %p api->c_by_l %llu bk->rszB %llu\n",
337 bk
->ap
, api
->curr_bytes
, (ULong
)bk
->req_szB
);
340 // Total bytes is coming down from a possible peak.
343 // Then update global stats.
344 tl_assert(g_curr_blocks
>= 1);
345 tl_assert(g_curr_bytes
>= bk
->req_szB
);
347 g_curr_bytes
-= bk
->req_szB
;
349 // Then update APInfo stats.
350 tl_assert(api
->curr_blocks
>= 1);
351 tl_assert(api
->curr_bytes
>= bk
->req_szB
);
353 api
->curr_bytes
-= bk
->req_szB
;
358 tl_assert(bk
->allocd_at
<= g_curr_instrs
);
359 api
->total_lifetimes_instrs
+= (g_curr_instrs
- bk
->allocd_at
);
362 api
->reads_bytes
+= bk
->reads_bytes
;
363 api
->writes_bytes
+= bk
->writes_bytes
;
364 g_reads_bytes
+= bk
->reads_bytes
;
365 g_writes_bytes
+= bk
->writes_bytes
;
367 // histo stuff. First, do state transitions for xsize/xsize_tag.
368 switch (api
->xsize_tag
) {
371 tl_assert(api
->xsize
== 0);
372 tl_assert(api
->freed_blocks
== 1 || api
->freed_blocks
== 0);
373 tl_assert(!api
->histo
);
374 api
->xsize_tag
= Exactly
;
375 api
->xsize
= bk
->req_szB
;
376 if (0) VG_(printf
)("api %p --> Exactly(%lu)\n", api
, api
->xsize
);
377 // and allocate the histo
379 api
->histo
= VG_(malloc
)("dh.retire_Block.1",
380 api
->xsize
* sizeof(UInt
));
381 VG_(memset
)(api
->histo
, 0, api
->xsize
* sizeof(UInt
));
386 //tl_assert(api->freed_blocks > 1);
387 if (bk
->req_szB
!= api
->xsize
) {
388 if (0) VG_(printf
)("api %p --> Mixed(%lu -> %lu)\n",
389 api
, api
->xsize
, bk
->req_szB
);
390 api
->xsize_tag
= Mixed
;
392 // deallocate the histo, if any
394 VG_(free
)(api
->histo
);
401 //tl_assert(api->freed_blocks > 1);
408 // See if we can fold the histo data from this block into
409 // the data for the AP
410 if (api
->xsize_tag
== Exactly
&& api
->histo
&& bk
->histoW
) {
411 tl_assert(api
->xsize
== bk
->req_szB
);
413 for (i
= 0; i
< api
->xsize
; i
++) {
414 // FIXME: do something better in case of overflow of api->histo[..]
415 // Right now, at least don't let it overflow/wrap around
416 if (api
->histo
[i
] <= 0xFFFE0000)
417 api
->histo
[i
] += (UInt
)bk
->histoW
[i
];
419 if (0) VG_(printf
)("fold in, AP = %p\n", api
);
424 VG_(printf
)("block retiring, histo %lu: ", bk
->req_szB
);
426 for (i
= 0; i
< bk
->req_szB
; i
++)
427 VG_(printf
)("%u ", (UInt
)bk
->histoB
[i
]);
430 VG_(printf
)("block retiring, no histo %lu\n", bk
->req_szB
);
435 /* This handles block resizing. When a block with AP 'ec' has a
436 size change of 'delta', call here to update the APInfo. */
437 static void resize_Block(ExeContext
* ec
, SizeT old_req_szB
, SizeT new_req_szB
)
439 Long delta
= (Long
)new_req_szB
- (Long
)old_req_szB
;
443 Bool found
= VG_(lookupFM
)( apinfo
,
444 &keyW
, &valW
, (UWord
)ec
);
448 tl_assert(api
->ap
== ec
);
451 tl_assert(api
->curr_bytes
>= -delta
);
452 tl_assert(g_curr_bytes
>= -delta
);
455 // Total bytes might be coming down from a possible peak.
459 // Note: we treat realloc() like malloc() + free() for total counts, i.e. we
460 // increment total_blocks by 1 and increment total_bytes by new_req_szB.
462 // A reasonable alternative would be to leave total_blocks unchanged and
463 // increment total_bytes by delta (but only if delta is positive). But then
464 // calls to realloc wouldn't be counted towards the total_blocks count,
465 // which is undesirable.
467 // Update global stats first.
470 g_total_bytes
+= new_req_szB
;
472 g_curr_blocks
+= 0; // unchanged
473 g_curr_bytes
+= delta
;
474 if (g_curr_bytes
> g_max_bytes
) {
475 g_max_blocks
= g_curr_blocks
;
476 g_max_bytes
= g_curr_bytes
;
477 g_max_instrs
= g_curr_instrs
;
480 // Now update APInfo stats.
483 api
->total_bytes
+= new_req_szB
;
485 api
->curr_blocks
+= 0; // unchanged
486 api
->curr_bytes
+= delta
;
487 if (api
->curr_bytes
> api
->max_bytes
) {
488 api
->max_blocks
= api
->curr_blocks
;
489 api
->max_bytes
= api
->curr_bytes
;
494 //------------------------------------------------------------//
495 //--- update both Block and APInfos after {m,re}alloc/free ---//
496 //------------------------------------------------------------//
499 void* new_block ( ThreadId tid
, void* p
, SizeT req_szB
, SizeT req_alignB
,
502 tl_assert(p
== NULL
); // don't handle custom allocators right now
503 SizeT actual_szB
/*, slop_szB*/;
505 if ((SSizeT
)req_szB
< 0) return NULL
;
508 req_szB
= 1; /* can't allow zero-sized blocks in the interval tree */
510 // Allocate and zero if necessary
512 p
= VG_(cli_malloc
)( req_alignB
, req_szB
);
516 if (is_zeroed
) VG_(memset
)(p
, 0, req_szB
);
517 actual_szB
= VG_(cli_malloc_usable_size
)(p
);
518 tl_assert(actual_szB
>= req_szB
);
519 /* slop_szB = actual_szB - req_szB; */
524 // Make new Block, add to interval_tree.
525 Block
* bk
= VG_(malloc
)("dh.new_block.1", sizeof(Block
));
526 bk
->payload
= (Addr
)p
;
527 bk
->req_szB
= req_szB
;
528 bk
->ap
= VG_(record_ExeContext
)(tid
, 0/*first word delta*/);
529 bk
->allocd_at
= g_curr_instrs
;
531 bk
->writes_bytes
= 0;
532 // set up histogram array, if the block isn't too large
534 if (req_szB
<= HISTOGRAM_SIZE_LIMIT
) {
535 bk
->histoW
= VG_(malloc
)("dh.new_block.2", req_szB
* sizeof(UShort
));
536 VG_(memset
)(bk
->histoW
, 0, req_szB
* sizeof(UShort
));
539 Bool present
= VG_(addToFM
)( interval_tree
, (UWord
)bk
, (UWord
)0/*no val*/);
541 fbc_cache0
= fbc_cache1
= NULL
;
545 if (0) VG_(printf
)("ALLOC %lu -> %p\n", req_szB
, p
);
551 void die_block ( void* p
, Bool custom_free
)
553 tl_assert(!custom_free
); // at least for now
555 Block
* bk
= find_Block_containing( (Addr
)p
);
558 return; // bogus free
561 tl_assert(bk
->req_szB
> 0);
562 // assert the block finder is behaving sanely
563 tl_assert(bk
->payload
<= (Addr
)p
);
564 tl_assert( (Addr
)p
< bk
->payload
+ bk
->req_szB
);
566 if (bk
->payload
!= (Addr
)p
) {
567 return; // bogus free
570 if (0) VG_(printf
)(" FREE %p %llu\n",
571 p
, g_curr_instrs
- bk
->allocd_at
);
573 retire_Block(bk
, True
/*because_freed*/);
575 VG_(cli_free
)( (void*)bk
->payload
);
576 delete_Block_starting_at( bk
->payload
);
578 VG_(free
)( bk
->histoW
);
586 void* renew_block ( ThreadId tid
, void* p_old
, SizeT new_req_szB
)
588 if (0) VG_(printf
)("REALL %p %lu\n", p_old
, new_req_szB
);
591 tl_assert(new_req_szB
> 0); // map 0 to 1
593 // Find the old block.
594 Block
* bk
= find_Block_containing( (Addr
)p_old
);
596 return NULL
; // bogus realloc
599 tl_assert(bk
->req_szB
> 0);
600 // assert the block finder is behaving sanely
601 tl_assert(bk
->payload
<= (Addr
)p_old
);
602 tl_assert( (Addr
)p_old
< bk
->payload
+ bk
->req_szB
);
604 if (bk
->payload
!= (Addr
)p_old
) {
605 return NULL
; // bogus realloc
608 // Keeping the histogram alive in any meaningful way across
609 // block resizing is too darn complicated. Just throw it away.
611 VG_(free
)(bk
->histoW
);
615 // Actually do the allocation, if necessary.
616 if (new_req_szB
<= bk
->req_szB
) {
618 // New size is smaller or same; block not moved.
619 resize_Block(bk
->ap
, bk
->req_szB
, new_req_szB
);
620 bk
->req_szB
= new_req_szB
;
625 // New size is bigger; make new block, copy shared contents, free old.
626 p_new
= VG_(cli_malloc
)(VG_(clo_alignment
), new_req_szB
);
628 // Nb: if realloc fails, NULL is returned but the old block is not
629 // touched. What an awful function.
632 tl_assert(p_new
!= p_old
);
634 VG_(memcpy
)(p_new
, p_old
, bk
->req_szB
);
635 VG_(cli_free
)(p_old
);
637 // Since the block has moved, we need to re-insert it into the
638 // interval tree at the new place. Do this by removing
640 delete_Block_starting_at( (Addr
)p_old
);
641 // now 'bk' is no longer in the tree, but the Block itself
644 // Update the metadata.
645 resize_Block(bk
->ap
, bk
->req_szB
, new_req_szB
);
646 bk
->payload
= (Addr
)p_new
;
647 bk
->req_szB
= new_req_szB
;
651 = VG_(addToFM
)( interval_tree
, (UWord
)bk
, (UWord
)0/*no val*/);
653 fbc_cache0
= fbc_cache1
= NULL
;
662 //------------------------------------------------------------//
663 //--- malloc() et al replacement wrappers ---//
664 //------------------------------------------------------------//
666 static void* dh_malloc ( ThreadId tid
, SizeT szB
)
668 return new_block( tid
, NULL
, szB
, VG_(clo_alignment
), /*is_zeroed*/False
);
671 static void* dh___builtin_new ( ThreadId tid
, SizeT szB
)
673 return new_block( tid
, NULL
, szB
, VG_(clo_alignment
), /*is_zeroed*/False
);
676 static void* dh___builtin_vec_new ( ThreadId tid
, SizeT szB
)
678 return new_block( tid
, NULL
, szB
, VG_(clo_alignment
), /*is_zeroed*/False
);
681 static void* dh_calloc ( ThreadId tid
, SizeT m
, SizeT szB
)
683 return new_block( tid
, NULL
, m
*szB
, VG_(clo_alignment
), /*is_zeroed*/True
);
686 static void *dh_memalign ( ThreadId tid
, SizeT alignB
, SizeT szB
)
688 return new_block( tid
, NULL
, szB
, alignB
, False
);
691 static void dh_free ( ThreadId tid
__attribute__((unused
)), void* p
)
693 die_block( p
, /*custom_free*/False
);
696 static void dh___builtin_delete ( ThreadId tid
, void* p
)
698 die_block( p
, /*custom_free*/False
);
701 static void dh___builtin_vec_delete ( ThreadId tid
, void* p
)
703 die_block( p
, /*custom_free*/False
);
706 static void* dh_realloc ( ThreadId tid
, void* p_old
, SizeT new_szB
)
709 return dh_malloc(tid
, new_szB
);
715 return renew_block(tid
, p_old
, new_szB
);
718 static SizeT
dh_malloc_usable_size ( ThreadId tid
, void* p
)
720 Block
* bk
= find_Block_containing( (Addr
)p
);
721 return bk
? bk
->req_szB
: 0;
725 //------------------------------------------------------------//
726 //--- memory references ---//
727 //------------------------------------------------------------//
730 void inc_histo_for_block ( Block
* bk
, Addr addr
, UWord szB
)
732 UWord i
, offMin
, offMax1
;
733 offMin
= addr
- bk
->payload
;
734 tl_assert(offMin
< bk
->req_szB
);
735 offMax1
= offMin
+ szB
;
736 if (offMax1
> bk
->req_szB
)
737 offMax1
= bk
->req_szB
;
738 //VG_(printf)("%lu %lu (size of block %lu)\n", offMin, offMax1, bk->req_szB);
739 for (i
= offMin
; i
< offMax1
; i
++) {
740 UShort n
= bk
->histoW
[i
];
747 void dh_handle_write ( Addr addr
, UWord szB
)
749 Block
* bk
= find_Block_containing(addr
);
751 bk
->writes_bytes
+= szB
;
753 inc_histo_for_block(bk
, addr
, szB
);
758 void dh_handle_read ( Addr addr
, UWord szB
)
760 Block
* bk
= find_Block_containing(addr
);
762 bk
->reads_bytes
+= szB
;
764 inc_histo_for_block(bk
, addr
, szB
);
769 // Handle reads and writes by syscalls (read == kernel
770 // reads user space, write == kernel writes user space).
771 // Assumes no such read or write spans a heap block
772 // boundary and so we can treat it just as one giant
775 void dh_handle_noninsn_read ( CorePart part
, ThreadId tid
, const HChar
* s
,
776 Addr base
, SizeT size
)
780 dh_handle_read(base
, size
);
782 case Vg_CoreSysCallArgInMem
:
784 case Vg_CoreTranslate
:
792 void dh_handle_noninsn_write ( CorePart part
, ThreadId tid
,
793 Addr base
, SizeT size
)
797 dh_handle_write(base
, size
);
807 //------------------------------------------------------------//
808 //--- Instrumentation ---//
809 //------------------------------------------------------------//
811 #define binop(_op, _arg1, _arg2) IRExpr_Binop((_op),(_arg1),(_arg2))
812 #define mkexpr(_tmp) IRExpr_RdTmp((_tmp))
813 #define mkU32(_n) IRExpr_Const(IRConst_U32(_n))
814 #define mkU64(_n) IRExpr_Const(IRConst_U64(_n))
815 #define assign(_t, _e) IRStmt_WrTmp((_t), (_e))
818 void add_counter_update(IRSB
* sbOut
, Int n
)
820 #if defined(VG_BIGENDIAN)
822 #elif defined(VG_LITTLEENDIAN)
825 # error "Unknown endianness"
827 // Add code to increment 'g_curr_instrs' by 'n', like this:
828 // WrTmp(t1, Load64(&g_curr_instrs))
829 // WrTmp(t2, Add64(RdTmp(t1), Const(n)))
830 // Store(&g_curr_instrs, t2)
831 IRTemp t1
= newIRTemp(sbOut
->tyenv
, Ity_I64
);
832 IRTemp t2
= newIRTemp(sbOut
->tyenv
, Ity_I64
);
833 IRExpr
* counter_addr
= mkIRExpr_HWord( (HWord
)&g_curr_instrs
);
835 IRStmt
* st1
= assign(t1
, IRExpr_Load(END
, Ity_I64
, counter_addr
));
836 IRStmt
* st2
= assign(t2
, binop(Iop_Add64
, mkexpr(t1
), mkU64(n
)));
837 IRStmt
* st3
= IRStmt_Store(END
, counter_addr
, mkexpr(t2
));
839 addStmtToIRSB( sbOut
, st1
);
840 addStmtToIRSB( sbOut
, st2
);
841 addStmtToIRSB( sbOut
, st3
);
845 void addMemEvent(IRSB
* sbOut
, Bool isWrite
, Int szB
, IRExpr
* addr
,
848 IRType tyAddr
= Ity_INVALID
;
849 const HChar
* hName
= NULL
;
851 IRExpr
** argv
= NULL
;
854 const Int THRESH
= 4096 * 4; // somewhat arbitrary
855 const Int rz_szB
= VG_STACK_REDZONE_SZB
;
857 tyAddr
= typeOfIRExpr( sbOut
->tyenv
, addr
);
858 tl_assert(tyAddr
== Ity_I32
|| tyAddr
== Ity_I64
);
861 hName
= "dh_handle_write";
862 hAddr
= &dh_handle_write
;
864 hName
= "dh_handle_read";
865 hAddr
= &dh_handle_read
;
868 argv
= mkIRExprVec_2( addr
, mkIRExpr_HWord(szB
) );
870 /* Add the helper. */
874 di
= unsafeIRDirty_0_N( 2/*regparms*/,
875 hName
, VG_(fnptr_to_fnentry
)( hAddr
),
878 /* Generate the guard condition: "(addr - (SP - RZ)) >u N", for
879 some arbitrary N. If that fails then addr is in the range (SP -
880 RZ .. SP + N - RZ). If N is smallish (a page?) then we can say
881 addr is within a page of SP and so can't possibly be a heap
882 access, and so can be skipped. */
883 IRTemp sp
= newIRTemp(sbOut
->tyenv
, tyAddr
);
884 addStmtToIRSB( sbOut
, assign(sp
, IRExpr_Get(goff_sp
, tyAddr
)));
886 IRTemp sp_minus_rz
= newIRTemp(sbOut
->tyenv
, tyAddr
);
891 ? binop(Iop_Sub32
, mkexpr(sp
), mkU32(rz_szB
))
892 : binop(Iop_Sub64
, mkexpr(sp
), mkU64(rz_szB
)))
895 IRTemp diff
= newIRTemp(sbOut
->tyenv
, tyAddr
);
900 ? binop(Iop_Sub32
, addr
, mkexpr(sp_minus_rz
))
901 : binop(Iop_Sub64
, addr
, mkexpr(sp_minus_rz
)))
904 IRTemp guard
= newIRTemp(sbOut
->tyenv
, Ity_I1
);
909 ? binop(Iop_CmpLT32U
, mkU32(THRESH
), mkexpr(diff
))
910 : binop(Iop_CmpLT64U
, mkU64(THRESH
), mkexpr(diff
)))
912 di
->guard
= mkexpr(guard
);
914 addStmtToIRSB( sbOut
, IRStmt_Dirty(di
) );
918 IRSB
* dh_instrument ( VgCallbackClosure
* closure
,
920 const VexGuestLayout
* layout
,
921 const VexGuestExtents
* vge
,
922 const VexArchInfo
* archinfo_host
,
923 IRType gWordTy
, IRType hWordTy
)
927 IRTypeEnv
* tyenv
= sbIn
->tyenv
;
929 const Int goff_sp
= layout
->offset_SP
;
931 // We increment the instruction count in two places:
932 // - just before any Ist_Exit statements;
933 // - just before the IRSB's end.
934 // In the former case, we zero 'n' and then continue instrumenting.
936 sbOut
= deepCopyIRSBExceptStmts(sbIn
);
938 // Copy verbatim any IR preamble preceding the first IMark
940 while (i
< sbIn
->stmts_used
&& sbIn
->stmts
[i
]->tag
!= Ist_IMark
) {
941 addStmtToIRSB( sbOut
, sbIn
->stmts
[i
] );
945 for (/*use current i*/; i
< sbIn
->stmts_used
; i
++) {
946 IRStmt
* st
= sbIn
->stmts
[i
];
948 if (!st
|| st
->tag
== Ist_NoOp
) continue;
959 // Add an increment before the Exit statement, then reset 'n'.
960 add_counter_update(sbOut
, n
);
967 IRExpr
* data
= st
->Ist
.WrTmp
.data
;
968 if (data
->tag
== Iex_Load
) {
969 IRExpr
* aexpr
= data
->Iex
.Load
.addr
;
970 // Note also, endianness info is ignored. I guess
971 // that's not interesting.
972 addMemEvent( sbOut
, False
/*!isWrite*/,
973 sizeofIRType(data
->Iex
.Load
.ty
),
980 IRExpr
* data
= st
->Ist
.Store
.data
;
981 IRExpr
* aexpr
= st
->Ist
.Store
.addr
;
982 addMemEvent( sbOut
, True
/*isWrite*/,
983 sizeofIRType(typeOfIRExpr(tyenv
, data
)),
990 IRDirty
* d
= st
->Ist
.Dirty
.details
;
991 if (d
->mFx
!= Ifx_None
) {
992 /* This dirty helper accesses memory. Collect the details. */
993 tl_assert(d
->mAddr
!= NULL
);
994 tl_assert(d
->mSize
!= 0);
996 // Large (eg. 28B, 108B, 512B on x86) data-sized
997 // instructions will be done inaccurately, but they're
998 // very rare and this avoids errors from hitting more
999 // than two cache lines in the simulation.
1000 if (d
->mFx
== Ifx_Read
|| d
->mFx
== Ifx_Modify
)
1001 addMemEvent( sbOut
, False
/*!isWrite*/,
1002 dataSize
, d
->mAddr
, goff_sp
);
1003 if (d
->mFx
== Ifx_Write
|| d
->mFx
== Ifx_Modify
)
1004 addMemEvent( sbOut
, True
/*isWrite*/,
1005 dataSize
, d
->mAddr
, goff_sp
);
1007 tl_assert(d
->mAddr
== NULL
);
1008 tl_assert(d
->mSize
== 0);
1014 /* We treat it as a read and a write of the location. I
1015 think that is the same behaviour as it was before IRCAS
1016 was introduced, since prior to that point, the Vex
1017 front ends would translate a lock-prefixed instruction
1018 into a (normal) read followed by a (normal) write. */
1020 IRCAS
* cas
= st
->Ist
.CAS
.details
;
1021 tl_assert(cas
->addr
!= NULL
);
1022 tl_assert(cas
->dataLo
!= NULL
);
1023 dataSize
= sizeofIRType(typeOfIRExpr(tyenv
, cas
->dataLo
));
1024 if (cas
->dataHi
!= NULL
)
1025 dataSize
*= 2; /* since it's a doubleword-CAS */
1026 addMemEvent( sbOut
, False
/*!isWrite*/,
1027 dataSize
, cas
->addr
, goff_sp
);
1028 addMemEvent( sbOut
, True
/*isWrite*/,
1029 dataSize
, cas
->addr
, goff_sp
);
1035 if (st
->Ist
.LLSC
.storedata
== NULL
) {
1037 dataTy
= typeOfIRTemp(tyenv
, st
->Ist
.LLSC
.result
);
1038 addMemEvent( sbOut
, False
/*!isWrite*/,
1039 sizeofIRType(dataTy
),
1040 st
->Ist
.LLSC
.addr
, goff_sp
);
1043 dataTy
= typeOfIRExpr(tyenv
, st
->Ist
.LLSC
.storedata
);
1044 addMemEvent( sbOut
, True
/*isWrite*/,
1045 sizeofIRType(dataTy
),
1046 st
->Ist
.LLSC
.addr
, goff_sp
);
1055 addStmtToIRSB( sbOut
, st
);
1059 // Add an increment before the SB end.
1060 add_counter_update(sbOut
, n
);
1072 //------------------------------------------------------------//
1073 //--- Command line args ---//
1074 //------------------------------------------------------------//
1076 static const HChar
* clo_dhat_out_file
= "dhat.out.%p";
1078 static Bool
dh_process_cmd_line_option(const HChar
* arg
)
1080 if VG_STR_CLO(arg
, "--dhat-out-file", clo_dhat_out_file
) {}
1083 return VG_(replacement_malloc_process_cmd_line_option
)(arg
);
1088 static void dh_print_usage(void)
1091 " --dhat-out-file=<file> output file name [dhat.out.%%p]\n"
1095 static void dh_print_debug_usage(void)
1103 //------------------------------------------------------------//
1104 //--- Finalisation ---//
1105 //------------------------------------------------------------//
1107 // File format notes.
1109 // - The files are JSON, because it's a widely-used format and saves us having
1110 // to write a parser in dh_view.js.
1112 // - We use a comma-first style for the generated JSON. Comma-first style
1113 // moves the special case for arrays/objects from the last item to the
1114 // first. This helps in cases where you can't easily tell in advance the
1115 // size of arrays/objects, such as iterating over a WordFM (because
1116 // VG_(sizeFM) is O(n) rather than O(1)), and iterating over stack frames
1117 // using VG_(apply_ExeContext) in combination with an InlIpCursor.
1119 // - We use short field names and minimal whitespace to minimize file sizes.
1123 #define FP(format, args...) ({ VG_(fprintf)(fp, format, ##args); })
1125 // The frame table holds unique frames.
1126 static WordFM
* frame_tbl
= NULL
;
1127 static UWord next_frame_n
= 0;
1129 static Word
frame_cmp(UWord a
, UWord b
)
1131 return VG_(strcmp
)((const HChar
*)a
, (const HChar
*)b
);
1134 static HChar
hex_digit_to_ascii_char(UChar d
)
1137 return (d
< 10) ? ('0' + d
) : ('a' + (d
- 10));
1140 // For JSON, we must escape double quote, backslash, and 0x00..0x1f.
1142 // Returns the original string if no escaping was required. Returns a pointer
1143 // to a static buffer if escaping was required. Therefore, the return value is
1144 // only valid until the next call to this function.
1145 static const HChar
* json_escape(const HChar
* s
)
1147 static HChar
* buf
= NULL
;
1148 static SizeT bufcap
= 0;
1150 // Do we need any escaping?
1155 if (c
== '"' || c
== '\\') {
1157 } else if (c
<= 0x1f) {
1165 // No escaping needed.
1169 // Escaping needed. (The +1 is for the NUL terminator.) Enlarge buf if
1171 SizeT newcap
= len
+ extra
+ 1;
1172 if (bufcap
< newcap
) {
1173 buf
= VG_(realloc
)("dh.json", buf
, newcap
);
1184 } else if (c
== '\\') {
1187 } else if (c
<= 0x1f) {
1192 *q
++ = hex_digit_to_ascii_char((c
& 0x00f0) >> 4);
1193 *q
++ = hex_digit_to_ascii_char(c
& 0x000f);
1204 static void write_APInfo_frame(UInt n
, DiEpoch ep
, Addr ip
, void* opaque
)
1206 Bool
* is_first
= (Bool
*)opaque
;
1207 InlIPCursor
* iipc
= VG_(new_IIPC
)(ep
, ip
);
1210 const HChar
* buf
= VG_(describe_IP
)(ep
, ip
, iipc
);
1212 // Skip entries in vg_replace_malloc.c (e.g. `malloc`, `calloc`,
1213 // `realloc`, `operator new`) because they're boring and clog up the
1215 if (VG_(strstr
)(buf
, "vg_replace_malloc.c")) {
1219 // If this description has been seen before, get its number. Otherwise,
1220 // give it a new number and put it in the table.
1221 UWord keyW
= 0, valW
= 0;
1223 Bool found
= VG_(lookupFM
)(frame_tbl
, &keyW
, &valW
, (UWord
)buf
);
1225 //const HChar* str = (const HChar*)keyW;
1226 //tl_assert(0 == VG_(strcmp)(buf, str));
1229 // `buf` is a static buffer, we must copy it.
1230 const HChar
* str
= VG_(strdup
)("dh.frame_tbl.3", buf
);
1231 frame_n
= next_frame_n
++;
1232 Bool present
= VG_(addToFM
)(frame_tbl
, (UWord
)str
, frame_n
);
1233 tl_assert(!present
);
1236 FP("%c%lu", *is_first
? '[' : ',', frame_n
);
1239 } while (VG_(next_IIPC
)(iipc
));
1241 VG_(delete_IIPC
)(iipc
);
1244 static void write_APInfo(APInfo
* api
, Bool is_first
)
1246 tl_assert(api
->total_blocks
>= api
->max_blocks
);
1247 tl_assert(api
->total_bytes
>= api
->max_bytes
);
1249 FP(" %c{\"tb\":%llu,\"tbk\":%llu,\"tli\":%llu\n",
1250 is_first
? '[' : ',',
1251 api
->total_bytes
, api
->total_blocks
, api
->total_lifetimes_instrs
);
1252 FP(" ,\"mb\":%llu,\"mbk\":%llu\n",
1253 api
->max_bytes
, api
->max_blocks
);
1254 FP(" ,\"gb\":%llu,\"gbk\":%llu\n",
1255 api
->at_tgmax_bytes
, api
->at_tgmax_blocks
);
1256 FP(" ,\"fb\":%llu,\"fbk\":%llu\n",
1257 api
->curr_bytes
, api
->curr_blocks
);
1258 FP(" ,\"rb\":%llu,\"wb\":%llu\n",
1259 api
->reads_bytes
, api
->writes_bytes
);
1261 if (api
->histo
&& api
->xsize_tag
== Exactly
) {
1264 // Simple run-length encoding: when N entries in a row have the same
1265 // value M, we print "-N,M". If there is just one in a row, we just
1266 // print "M". This reduces file size significantly.
1269 for (UWord i
= 0; i
< api
->xsize
; i
++) {
1270 UShort h
= api
->histo
[i
];
1272 // Continue current run.
1275 // End of run; print it.
1278 } else if (reps
> 1) {
1279 FP("-%d,%u,", reps
, repval
);
1285 // Print the final run.
1288 } else if (reps
> 1) {
1289 FP("-%d,%u", reps
, repval
);
1296 Bool is_first_frame
= True
;
1297 VG_(apply_ExeContext
)(write_APInfo_frame
, &is_first_frame
, api
->ap
);
1303 static void write_APInfos(void)
1309 VG_(initIterFM
)(apinfo
);
1310 Bool is_first
= True
;
1311 while (VG_(nextIterFM
)(apinfo
, &keyW
, &valW
)) {
1312 APInfo
* api
= (APInfo
*)valW
;
1313 tl_assert(api
&& api
->ap
== (ExeContext
*)keyW
);
1314 write_APInfo(api
, is_first
);
1317 VG_(doneIterFM
)(apinfo
);
1320 // We didn't print any elements. This happens if apinfo is empty.
1327 static void dh_fini(Int exit_status
)
1329 // This function does lots of allocations that it doesn't bother to free,
1330 // because execution is almost over anyway.
1332 // Total bytes might be at a possible peak.
1335 // Before printing statistics, we must harvest various stats (such as
1336 // lifetimes and accesses) for all the blocks that are still alive.
1338 VG_(initIterFM
)( interval_tree
);
1339 while (VG_(nextIterFM
)( interval_tree
, &keyW
, &valW
)) {
1340 Block
* bk
= (Block
*)keyW
;
1341 tl_assert(valW
== 0);
1343 retire_Block(bk
, False
/*!because_freed*/);
1345 VG_(doneIterFM
)( interval_tree
);
1348 if (VG_(clo_stats
)) {
1349 VG_(dmsg
)(" dhat: find_Block_containing:\n");
1350 VG_(dmsg
)(" found: %'lu (%'lu cached + %'lu uncached)\n",
1351 stats__n_fBc_cached
+ stats__n_fBc_uncached
,
1352 stats__n_fBc_cached
,
1353 stats__n_fBc_uncached
);
1354 VG_(dmsg
)(" notfound: %'lu\n", stats__n_fBc_notfound
);
1358 // Create the frame table, and insert the special "[root]" node at index 0.
1359 frame_tbl
= VG_(newFM
)(VG_(malloc
),
1363 const HChar
* root
= VG_(strdup
)("dh.frame_tbl.2", "[root]");
1364 Bool present
= VG_(addToFM
)(frame_tbl
, (UWord
)root
, 0);
1365 tl_assert(!present
);
1368 // Setup output filename. Nb: it's important to do this now, i.e. as late
1369 // as possible. If we do it at start-up and the program forks and the
1370 // output file format string contains a %p (pid) specifier, both the parent
1371 // and child will incorrectly write to the same file; this happened in
1373 HChar
* dhat_out_file
=
1374 VG_(expand_file_name
)("--dhat-out-file", clo_dhat_out_file
);
1376 fp
= VG_(fopen
)(dhat_out_file
, VKI_O_CREAT
|VKI_O_TRUNC
|VKI_O_WRONLY
,
1377 VKI_S_IRUSR
|VKI_S_IWUSR
);
1379 VG_(umsg
)("error: can't open DHAT output file '%s'\n", dhat_out_file
);
1383 // Write to data file.
1384 FP("{\"dhatFileVersion\":1\n");
1387 const HChar
* exe
= VG_(args_the_exename
);
1388 FP(",\"cmd\":\"%s", json_escape(exe
));
1389 for (Word i
= 0; i
< VG_(sizeXA
)(VG_(args_for_client
)); i
++) {
1390 const HChar
* arg
= *(HChar
**)VG_(indexXA
)(VG_(args_for_client
), i
);
1391 FP(" %s", json_escape(arg
));
1396 FP(",\"pid\":%d\n", VG_(getpid
)());
1399 FP(",\"mi\":%llu,\"ei\":%llu\n", g_max_instrs
, g_curr_instrs
);
1407 // The frame table maps strings to numbers. We want to print it ordered by
1408 // numbers. So we create an array and fill it in from the frame table, then
1410 UWord n_frames
= next_frame_n
;
1411 const HChar
** frames
=
1412 VG_(malloc
)("dh.frames", n_frames
* sizeof(const HChar
*));
1413 VG_(initIterFM
)(frame_tbl
);
1414 while (VG_(nextIterFM
)(frame_tbl
, &keyW
, &valW
)) {
1415 const HChar
* str
= (const HChar
*)keyW
;
1419 VG_(doneIterFM
)(frame_tbl
);
1421 for (UWord i
= 0; i
< n_frames
; i
++) {
1422 FP(" %c\"%s\"\n", i
== 0 ? '[' : ',', json_escape(frames
[i
]));
1431 if (VG_(clo_verbosity
) == 0) {
1435 // Print brief global stats.
1436 VG_(umsg
)("Total: %'llu bytes in %'llu blocks\n",
1437 g_total_bytes
, g_total_blocks
);
1438 VG_(umsg
)("At t-gmax: %'llu bytes in %'llu blocks\n",
1439 g_max_bytes
, g_max_blocks
);
1440 VG_(umsg
)("At t-end: %'llu bytes in %'llu blocks\n",
1441 g_curr_bytes
, g_curr_blocks
);
1442 VG_(umsg
)("Reads: %'llu bytes\n", g_reads_bytes
);
1443 VG_(umsg
)("Writes: %'llu bytes\n", g_writes_bytes
);
1445 // Print a how-to-view-the-profile hint.
1447 VG_(umsg
)("To view the resulting profile, open\n");
1448 VG_(umsg
)(" file://%s/%s\n", VG_(libdir
), "dh_view.html");
1449 VG_(umsg
)("in a web browser, click on \"Load...\" "
1450 "and then select the file\n");
1451 VG_(umsg
)(" %s\n", dhat_out_file
);
1452 VG_(umsg
)("Scroll to the end the displayed page to see a short\n");
1453 VG_(umsg
)("explanation of some of the abbreviations used in the page.\n");
1456 //------------------------------------------------------------//
1457 //--- Initialisation ---//
1458 //------------------------------------------------------------//
1460 static void dh_post_clo_init(void)
1464 static void dh_pre_clo_init(void)
1466 VG_(details_name
) ("DHAT");
1467 VG_(details_version
) (NULL
);
1468 VG_(details_description
) ("a dynamic heap analysis tool");
1469 VG_(details_copyright_author
)(
1470 "Copyright (C) 2010-2018, and GNU GPL'd, by Mozilla Foundation");
1471 VG_(details_bug_reports_to
) (VG_BUGS_TO
);
1474 VG_(basic_tool_funcs
) (dh_post_clo_init
,
1479 VG_(needs_libc_freeres
)();
1480 VG_(needs_cxx_freeres
)();
1481 VG_(needs_command_line_options
)(dh_process_cmd_line_option
,
1483 dh_print_debug_usage
);
1484 //zz VG_(needs_client_requests) (dh_handle_client_request);
1485 //zz VG_(needs_sanity_checks) (dh_cheap_sanity_check,
1486 //zz dh_expensive_sanity_check);
1487 VG_(needs_malloc_replacement
) (dh_malloc
,
1489 dh___builtin_vec_new
,
1493 dh___builtin_delete
,
1494 dh___builtin_vec_delete
,
1496 dh_malloc_usable_size
,
1499 VG_(track_pre_mem_read
) ( dh_handle_noninsn_read
);
1500 //VG_(track_pre_mem_read_asciiz) ( check_mem_is_defined_asciiz );
1501 VG_(track_post_mem_write
) ( dh_handle_noninsn_write
);
1503 tl_assert(!interval_tree
);
1504 tl_assert(!fbc_cache0
);
1505 tl_assert(!fbc_cache1
);
1507 interval_tree
= VG_(newFM
)( VG_(malloc
),
1508 "dh.interval_tree.1",
1510 interval_tree_Cmp
);
1512 apinfo
= VG_(newFM
)( VG_(malloc
),
1515 NULL
/*unboxedcmp*/ );
1518 VG_DETERMINE_INTERFACE_VERSION(dh_pre_clo_init
)
1520 //--------------------------------------------------------------------//
1521 //--- end dh_main.c ---//
1522 //--------------------------------------------------------------------//