2 /*--------------------------------------------------------------------*/
3 /*--- Store and compare stack backtraces m_execontext.c ---*/
4 /*--------------------------------------------------------------------*/
7 This file is part of Valgrind, a dynamic binary instrumentation
10 Copyright (C) 2000-2017 Julian Seward
13 This program is free software; you can redistribute it and/or
14 modify it under the terms of the GNU General Public License as
15 published by the Free Software Foundation; either version 2 of the
16 License, or (at your option) any later version.
18 This program is distributed in the hope that it will be useful, but
19 WITHOUT ANY WARRANTY; without even the implied warranty of
20 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
21 General Public License for more details.
23 You should have received a copy of the GNU General Public License
24 along with this program; if not, write to the Free Software
25 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
28 The GNU General Public License is contained in the file COPYING.
31 #include "pub_core_basics.h"
32 #include "pub_core_debuglog.h"
33 #include "pub_core_libcassert.h"
34 #include "pub_core_libcprint.h" // For VG_(message)()
35 #include "pub_core_mallocfree.h"
36 #include "pub_core_options.h"
37 #include "pub_core_stacktrace.h"
38 #include "pub_core_machine.h" // VG_(get_IP)
39 #include "pub_core_threadstate.h" // VG_(is_valid_tid)
40 #include "pub_core_execontext.h" // self
42 /*------------------------------------------------------------*/
43 /*--- Low-level ExeContext storage. ---*/
44 /*------------------------------------------------------------*/
46 /* Depending on VgRes, the first 2, 4 or all IP values are used in
47 comparisons to remove duplicate errors, and for comparing against
48 suppression specifications. If not used in comparison, the rest
49 are purely informational (but often important).
51 The contexts are stored in a traditional chained hash table, so as
52 to allow quick determination of whether a new context already
53 exists. The hash table starts small and expands dynamically, so as
54 to keep the load factor below 1.0.
56 The idea is only to ever store any one context once, so as to save
57 space and make exact comparisons faster. */
60 /* Primes for the hash table */
62 #define N_EC_PRIMES 18
64 static SizeT ec_primes
[N_EC_PRIMES
] = {
65 769UL, 1543UL, 3079UL, 6151UL,
66 12289UL, 24593UL, 49157UL, 98317UL,
67 196613UL, 393241UL, 786433UL, 1572869UL,
68 3145739UL, 6291469UL, 12582917UL, 25165843UL,
69 50331653UL, 100663319UL
73 /* Each element is present in a hash chain, and also contains a
74 variable length array of guest code addresses (the useful part). */
77 struct _ExeContext
* chain
;
78 /* A 32-bit unsigned integer that uniquely identifies this
79 ExeContext. Memcheck uses these for origin tracking. Values
80 must be nonzero (else Memcheck's origin tracking is hosed), must
81 be a multiple of four, and must be unique. Hence they start at
84 /* epoch in which the ExeContext can be symbolised. In other words, epoch
85 identifies the set of debug info to use to symbolise the Addr in ips
86 using e.g. VG_(get_filename), VG_(get_fnname), ...
87 Note 1: 2 ExeContexts are equal when their ips array are equal and
88 their epoch are equal.
89 Note 2: a freshly created ExeContext has a DiEpoch_INVALID epoch.
90 DiEpoch_INVALID is used as a special value to indicate that ExeContext
91 is valid in the current epoch. VG_(get_ExeContext_epoch) translates
92 this invalid value in the real current epoch.
93 When a debug info is archived, the set of ExeContext is scanned :
94 If an ExeContext with epoch == DiEpoch_INVALID has one or more
95 ips Addr corresponding to the just archived debug info, the ExeContext
96 epoch is changed to the last epoch identifying the set containing the
97 archived debug info. */
99 /* Variable-length array. The size is 'n_ips'; at
100 least 1, at most VG_DEEPEST_BACKTRACE. [0] is the current IP,
101 [1] is its caller, [2] is the caller of [1], etc. */
107 /* This is the dynamically expanding hash table. */
108 static ExeContext
** ec_htab
; /* array [ec_htab_size] of ExeContext* */
109 static SizeT ec_htab_size
; /* one of the values in ec_primes */
110 static SizeT ec_htab_size_idx
; /* 0 .. N_EC_PRIMES-1 */
112 /* ECU serial number */
113 static UInt ec_next_ecu
= 4; /* We must never issue zero */
115 static ExeContext
* null_ExeContext
;
117 /* Stats only: the number of times the system was searched to locate a
119 static ULong ec_searchreqs
;
121 /* Stats only: the number of full context comparisons done. */
122 static ULong ec_searchcmps
;
124 /* Stats only: total number of stored contexts. */
125 static ULong ec_totstored
;
127 /* Number of 2, 4 and (fast) full cmps done. */
128 static ULong ec_cmp2s
;
129 static ULong ec_cmp4s
;
130 static ULong ec_cmpAlls
;
133 /*------------------------------------------------------------*/
134 /*--- ExeContext functions. ---*/
135 /*------------------------------------------------------------*/
137 static ExeContext
* record_ExeContext_wrk2 ( const Addr
* ips
, UInt n_ips
);
139 /* Initialise this subsystem. */
140 static void init_ExeContext_storage ( void )
143 static Bool init_done
= False
;
144 if (LIKELY(init_done
))
153 ec_htab_size_idx
= 0;
154 ec_htab_size
= ec_primes
[ec_htab_size_idx
];
155 ec_htab
= VG_(malloc
)("execontext.iEs1",
156 sizeof(ExeContext
*) * ec_htab_size
);
157 for (i
= 0; i
< ec_htab_size
; i
++)
163 null_ExeContext
= record_ExeContext_wrk2(ips
, 1);
164 // null execontext must be the first one created and get ecu 4.
165 vg_assert(null_ExeContext
->ecu
== 4);
171 DiEpoch
VG_(get_ExeContext_epoch
)( const ExeContext
* e
)
173 if (is_DiEpoch_INVALID (e
->epoch
))
174 return VG_(current_DiEpoch
)();
180 void VG_(print_ExeContext_stats
) ( Bool with_stacktraces
)
186 init_ExeContext_storage();
188 if (with_stacktraces
) {
189 VG_(message
)(Vg_DebugMsg
, " exectx: Printing contexts stacktraces\n");
190 for (i
= 0; i
< ec_htab_size
; i
++) {
191 for (ec
= ec_htab
[i
]; ec
; ec
= ec
->chain
) {
192 VG_(message
)(Vg_DebugMsg
,
193 " exectx: stacktrace ecu %u epoch %u n_ips %u\n",
194 ec
->ecu
, ec
->epoch
.n
, ec
->n_ips
);
195 VG_(pp_StackTrace
)( VG_(get_ExeContext_epoch
)(ec
),
196 ec
->ips
, ec
->n_ips
);
199 VG_(message
)(Vg_DebugMsg
,
200 " exectx: Printed %'llu contexts stacktraces\n",
205 for (i
= 0; i
< ec_htab_size
; i
++) {
206 for (ec
= ec_htab
[i
]; ec
; ec
= ec
->chain
)
207 total_n_ips
+= ec
->n_ips
;
209 VG_(message
)(Vg_DebugMsg
,
210 " exectx: %'lu lists, %'llu contexts (avg %3.2f per list)"
211 " (avg %3.2f IP per context)\n",
212 ec_htab_size
, ec_totstored
, (Double
)ec_totstored
/ (Double
)ec_htab_size
,
213 (Double
)total_n_ips
/ (Double
)ec_totstored
215 VG_(message
)(Vg_DebugMsg
,
216 " exectx: %'llu searches, %'llu full compares (%'llu per 1000)\n",
217 ec_searchreqs
, ec_searchcmps
,
220 : ( (ec_searchcmps
* 1000ULL) / ec_searchreqs
)
222 VG_(message
)(Vg_DebugMsg
,
223 " exectx: %'llu cmp2, %'llu cmp4, %'llu cmpAll\n",
224 ec_cmp2s
, ec_cmp4s
, ec_cmpAlls
229 /* Print an ExeContext. */
230 void VG_(pp_ExeContext
) ( ExeContext
* ec
)
232 VG_(pp_StackTrace
)( VG_(get_ExeContext_epoch
)(ec
), ec
->ips
, ec
->n_ips
);
236 void VG_(archive_ExeContext_in_range
) (DiEpoch last_epoch
,
237 Addr text_avma
, SizeT length
)
241 ULong n_archived
= 0;
242 const Addr text_avma_end
= text_avma
+ length
- 1;
244 if (VG_(clo_verbosity
) > 1)
245 VG_(message
)(Vg_DebugMsg
, "Scanning and archiving ExeContexts ...\n");
246 for (i
= 0; i
< ec_htab_size
; i
++) {
247 for (ec
= ec_htab
[i
]; ec
; ec
= ec
->chain
) {
248 if (is_DiEpoch_INVALID (ec
->epoch
))
249 for (UInt j
= 0; j
< ec
->n_ips
; j
++) {
250 if (UNLIKELY(ec
->ips
[j
] >= text_avma
251 && ec
->ips
[j
] <= text_avma_end
)) {
252 ec
->epoch
= last_epoch
;
259 if (VG_(clo_verbosity
) > 1)
260 VG_(message
)(Vg_DebugMsg
,
261 "Scanned %'llu ExeContexts, archived %'llu ExeContexts\n",
262 ec_totstored
, n_archived
);
265 /* Compare two ExeContexts. Number of callers considered depends on res. */
266 Bool
VG_(eq_ExeContext
) ( VgRes res
, const ExeContext
* e1
,
267 const ExeContext
* e2
)
271 if (e1
== NULL
|| e2
== NULL
)
274 // Must be at least one address in each trace.
275 vg_assert(e1
->n_ips
>= 1 && e2
->n_ips
>= 1);
277 // Note: we compare the epoch in the case below, and not here
278 // to have the ec_cmp* stats correct.
282 /* Just compare the top two callers. */
284 for (i
= 0; i
< 2; i
++) {
285 if ( (e1
->n_ips
<= i
) && (e2
->n_ips
<= i
)) return True
;
286 if ( (e1
->n_ips
<= i
) && !(e2
->n_ips
<= i
)) return False
;
287 if (!(e1
->n_ips
<= i
) && (e2
->n_ips
<= i
)) return False
;
288 if (e1
->ips
[i
] != e2
->ips
[i
]) return False
;
290 return e1
->epoch
.n
== e2
->epoch
.n
;
293 /* Just compare the top four callers. */
295 for (i
= 0; i
< 4; i
++) {
296 if ( (e1
->n_ips
<= i
) && (e2
->n_ips
<= i
)) return True
;
297 if ( (e1
->n_ips
<= i
) && !(e2
->n_ips
<= i
)) return False
;
298 if (!(e1
->n_ips
<= i
) && (e2
->n_ips
<= i
)) return False
;
299 if (e1
->ips
[i
] != e2
->ips
[i
]) return False
;
301 return e1
->epoch
.n
== e2
->epoch
.n
;
305 /* Compare them all -- just do pointer comparison. */
306 if (e1
!= e2
) return False
;
310 VG_(core_panic
)("VG_(eq_ExeContext): unrecognised VgRes");
314 /* VG_(record_ExeContext) is the head honcho here. Take a snapshot of
315 the client's stack. Search our collection of ExeContexts to see if
316 we already have it, and if not, allocate a new one. Either way,
317 return a pointer to the context. If there is a matching context we
318 guarantee to not allocate a new one. Thus we never store
319 duplicates, and so exact equality can be quickly done as equality
320 on the returned ExeContext* values themselves. Inspired by Hugs's
323 Also checks whether the hash table needs expanding, and expands it
326 static inline UWord
ROLW ( UWord w
, Int n
)
328 Int bpw
= 8 * sizeof(UWord
);
329 w
= (w
<< n
) | (w
>> (bpw
-n
));
333 static UWord
calc_hash ( const Addr
* ips
, UInt n_ips
, UWord htab_sz
)
337 vg_assert(htab_sz
> 0);
338 for (i
= 0; i
< n_ips
; i
++) {
340 hash
= ROLW(hash
, 19);
342 return hash
% htab_sz
;
345 static void resize_ec_htab ( void )
349 ExeContext
** new_ec_htab
;
351 vg_assert(ec_htab_size_idx
>= 0 && ec_htab_size_idx
< N_EC_PRIMES
);
352 if (ec_htab_size_idx
== N_EC_PRIMES
-1)
353 return; /* out of primes - can't resize further */
355 new_size
= ec_primes
[ec_htab_size_idx
+ 1];
356 new_ec_htab
= VG_(malloc
)("execontext.reh1",
357 sizeof(ExeContext
*) * new_size
);
361 "resizing htab from size %lu to %lu (idx %lu) Total#ECs=%llu\n",
362 ec_htab_size
, new_size
, ec_htab_size_idx
+ 1, ec_totstored
);
364 for (i
= 0; i
< new_size
; i
++)
365 new_ec_htab
[i
] = NULL
;
367 for (i
= 0; i
< ec_htab_size
; i
++) {
368 ExeContext
* cur
= ec_htab
[i
];
370 ExeContext
* next
= cur
->chain
;
371 UWord hash
= calc_hash(cur
->ips
, cur
->n_ips
, new_size
);
372 vg_assert(hash
< new_size
);
373 cur
->chain
= new_ec_htab
[hash
];
374 new_ec_htab
[hash
] = cur
;
380 ec_htab
= new_ec_htab
;
381 ec_htab_size
= new_size
;
385 /* Used by the outer as a marker to separate the frames of the inner valgrind
386 from the frames of the inner guest frames. */
387 static void _______VVVVVVVV_appended_inner_guest_stack_VVVVVVVV_______ (void)
391 /* Do the first part of getting a stack trace: actually unwind the
392 stack, and hand the results off to the duplicate-trace-finder
394 static ExeContext
* record_ExeContext_wrk ( ThreadId tid
, Word first_ip_delta
,
397 Addr ips
[VG_(clo_backtrace_size
)];
400 init_ExeContext_storage();
402 vg_assert(sizeof(void*) == sizeof(UWord
));
403 vg_assert(sizeof(void*) == sizeof(Addr
));
405 vg_assert(VG_(is_valid_tid
)(tid
));
409 ips
[0] = VG_(get_IP
)(tid
) + first_ip_delta
;
411 n_ips
= VG_(get_StackTrace
)( tid
, ips
, VG_(clo_backtrace_size
),
412 NULL
/*array to dump SP values in*/,
413 NULL
/*array to dump FP values in*/,
415 if (VG_(inner_threads
) != NULL
416 && n_ips
+ 1 < VG_(clo_backtrace_size
)) {
417 /* An inner V has informed us (the outer) of its thread array.
418 Append the inner guest stack trace, if we still have some
419 room in the ips array for the separator and (some) inner
423 for (inner_tid
= 1; inner_tid
< VG_N_THREADS
; inner_tid
++) {
424 if (VG_(threads
)[tid
].os_state
.lwpid
425 == VG_(inner_threads
)[inner_tid
].os_state
.lwpid
) {
426 ThreadState
* save_outer_vg_threads
= VG_(threads
);
427 UInt n_ips_inner_guest
;
429 /* Append the separator + the inner guest stack trace. */
431 _______VVVVVVVV_appended_inner_guest_stack_VVVVVVVV_______
;
433 VG_(threads
) = VG_(inner_threads
);
435 = VG_(get_StackTrace
)( inner_tid
,
437 VG_(clo_backtrace_size
) - n_ips
,
438 NULL
/*array to dump SP values in*/,
439 NULL
/*array to dump FP values in*/,
441 n_ips
+= n_ips_inner_guest
;
442 VG_(threads
) = save_outer_vg_threads
;
449 return record_ExeContext_wrk2 ( ips
, n_ips
);
452 /* Do the second part of getting a stack trace: ips[0 .. n_ips-1]
453 holds a proposed trace. Find or allocate a suitable ExeContext.
454 Note that callers must have done init_ExeContext_storage() before
455 getting to this point. */
456 static ExeContext
* record_ExeContext_wrk2 ( const Addr
* ips
, UInt n_ips
)
463 ExeContext
*prev2
, *prev
;
467 vg_assert(n_ips
>= 1 && n_ips
<= VG_(clo_backtrace_size
));
469 /* Now figure out if we've seen this one before. First hash it so
470 as to determine the list number. */
471 hash
= calc_hash( ips
, n_ips
, ec_htab_size
);
473 /* And (the expensive bit) look a for matching entry in the list. */
479 list
= ec_htab
[hash
];
482 if (list
== NULL
) break;
484 same
= list
->n_ips
== n_ips
&& is_DiEpoch_INVALID (list
->epoch
);
485 for (i
= 0; i
< n_ips
&& same
; i
++) {
486 same
= list
->ips
[i
] == ips
[i
];
495 /* Yay! We found it. Once every 8 searches, move it one step
496 closer to the start of the list to make future searches
498 if (0 == ((ctr
++) & 7)) {
499 if (prev2
!= NULL
&& prev
!= NULL
) {
500 /* Found at 3rd or later position in the chain. */
501 vg_assert(prev2
->chain
== prev
);
502 vg_assert(prev
->chain
== list
);
504 prev
->chain
= list
->chain
;
507 else if (prev2
== NULL
&& prev
!= NULL
) {
508 /* Found at 2nd position in the chain. */
509 vg_assert(ec_htab
[hash
] == prev
);
510 vg_assert(prev
->chain
== list
);
511 prev
->chain
= list
->chain
;
513 ec_htab
[hash
] = list
;
519 /* Bummer. We have to allocate a new context record. */
522 new_ec
= VG_(perm_malloc
)( sizeof(struct _ExeContext
)
523 + n_ips
* sizeof(Addr
),
524 vg_alignof(struct _ExeContext
));
526 for (i
= 0; i
< n_ips
; i
++)
527 new_ec
->ips
[i
] = ips
[i
];
529 vg_assert(VG_(is_plausible_ECU
)(ec_next_ecu
));
530 new_ec
->ecu
= ec_next_ecu
;
532 if (ec_next_ecu
== 0) {
533 /* Urr. Now we're hosed; we emitted 2^30 ExeContexts already
534 and have run out of numbers. Not sure what to do. */
535 VG_(core_panic
)("m_execontext: more than 2^30 ExeContexts created");
538 new_ec
->n_ips
= n_ips
;
539 new_ec
->chain
= ec_htab
[hash
];
540 ec_htab
[hash
] = new_ec
;
542 /* Resize the hash table, maybe? */
543 if ( ((ULong
)ec_totstored
) > ((ULong
)ec_htab_size
) ) {
544 vg_assert(ec_htab_size_idx
>= 0 && ec_htab_size_idx
< N_EC_PRIMES
);
545 if (ec_htab_size_idx
< N_EC_PRIMES
-1)
552 ExeContext
* VG_(record_ExeContext
)( ThreadId tid
, Word first_ip_delta
) {
553 return record_ExeContext_wrk( tid
, first_ip_delta
,
554 False
/*!first_ip_only*/ );
557 ExeContext
* VG_(record_depth_1_ExeContext
)( ThreadId tid
, Word first_ip_delta
)
559 return record_ExeContext_wrk( tid
, first_ip_delta
,
560 True
/*first_ip_only*/ );
563 ExeContext
* VG_(make_depth_1_ExeContext_from_Addr
)( Addr a
) {
564 init_ExeContext_storage();
565 return record_ExeContext_wrk2( &a
, 1 );
568 StackTrace
VG_(get_ExeContext_StackTrace
) ( ExeContext
* e
) {
572 UInt
VG_(get_ECU_from_ExeContext
)( const ExeContext
* e
) {
573 vg_assert(VG_(is_plausible_ECU
)(e
->ecu
));
577 Int
VG_(get_ExeContext_n_ips
)( const ExeContext
* e
) {
578 vg_assert(e
->n_ips
>= 1);
582 ExeContext
* VG_(get_ExeContext_from_ECU
)( UInt ecu
)
586 vg_assert(VG_(is_plausible_ECU
)(ecu
));
587 vg_assert(ec_htab_size
> 0);
588 for (i
= 0; i
< ec_htab_size
; i
++) {
589 for (ec
= ec_htab
[i
]; ec
; ec
= ec
->chain
) {
597 ExeContext
* VG_(make_ExeContext_from_StackTrace
)( const Addr
* ips
, UInt n_ips
)
599 init_ExeContext_storage();
600 return record_ExeContext_wrk2(ips
, n_ips
);
603 ExeContext
* VG_(null_ExeContext
) (void)
605 init_ExeContext_storage();
606 return null_ExeContext
;
609 /*--------------------------------------------------------------------*/
610 /*--- end m_execontext.c ---*/
611 /*--------------------------------------------------------------------*/