1
2 /*--------------------------------------------------------------------*/
3 /*--- Store and compare stack backtraces m_execontext.c ---*/
4 /*--------------------------------------------------------------------*/
5
6 /*
7 This file is part of Valgrind, a dynamic binary instrumentation
8 framework.
9
10 Copyright (C) 2000-2017 Julian Seward
11 jseward@acm.org
12
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.
17
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.
22
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
26 02111-1307, USA.
27
28 The GNU General Public License is contained in the file COPYING.
29 */
30
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
41
42 /*------------------------------------------------------------*/
43 /*--- Low-level ExeContext storage. ---*/
44 /*------------------------------------------------------------*/
45
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).
50
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.
55
56 The idea is only to ever store any one context once, so as to save
57 space and make exact comparisons faster. */
58
59
60 /* Primes for the hash table */
61
62 #define N_EC_PRIMES 18
63
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
70 };
71
72
73 /* Each element is present in a hash chain, and also contains a
74 variable length array of guest code addresses (the useful part). */
75
76 struct _ExeContext {
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
82 4. */
83 UInt ecu;
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. */
98 DiEpoch epoch;
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. */
102 UInt n_ips;
103 Addr ips[0];
104 };
105
106
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 */
111
112 /* ECU serial number */
113 static UInt ec_next_ecu = 4; /* We must never issue zero */
114
115 static ExeContext* null_ExeContext;
116
117 /* Stats only: the number of times the system was searched to locate a
118 context. */
119 static ULong ec_searchreqs;
120
121 /* Stats only: the number of full context comparisons done. */
122 static ULong ec_searchcmps;
123
124 /* Stats only: total number of stored contexts. */
125 static ULong ec_totstored;
126
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;
131
132
133 /*------------------------------------------------------------*/
134 /*--- ExeContext functions. ---*/
135 /*------------------------------------------------------------*/
136
137 static ExeContext* record_ExeContext_wrk2 ( const Addr* ips, UInt n_ips );
138
139 /* Initialise this subsystem. */
init_ExeContext_storage(void)140 static void init_ExeContext_storage ( void )
141 {
142 Int i;
143 static Bool init_done = False;
144 if (LIKELY(init_done))
145 return;
146 ec_searchreqs = 0;
147 ec_searchcmps = 0;
148 ec_totstored = 0;
149 ec_cmp2s = 0;
150 ec_cmp4s = 0;
151 ec_cmpAlls = 0;
152
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++)
158 ec_htab[i] = NULL;
159
160 {
161 Addr ips[1];
162 ips[0] = 0;
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);
166 }
167
168 init_done = True;
169 }
170
VG_(get_ExeContext_epoch)171 DiEpoch VG_(get_ExeContext_epoch)( const ExeContext* e )
172 {
173 if (is_DiEpoch_INVALID (e->epoch))
174 return VG_(current_DiEpoch)();
175 else
176 return e->epoch;
177 }
178
179 /* Print stats. */
VG_(print_ExeContext_stats)180 void VG_(print_ExeContext_stats) ( Bool with_stacktraces )
181 {
182 Int i;
183 ULong total_n_ips;
184 ExeContext* ec;
185
186 init_ExeContext_storage();
187
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 );
197 }
198 }
199 VG_(message)(Vg_DebugMsg,
200 " exectx: Printed %'llu contexts stacktraces\n",
201 ec_totstored);
202 }
203
204 total_n_ips = 0;
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;
208 }
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
214 );
215 VG_(message)(Vg_DebugMsg,
216 " exectx: %'llu searches, %'llu full compares (%'llu per 1000)\n",
217 ec_searchreqs, ec_searchcmps,
218 ec_searchreqs == 0
219 ? 0ULL
220 : ( (ec_searchcmps * 1000ULL) / ec_searchreqs )
221 );
222 VG_(message)(Vg_DebugMsg,
223 " exectx: %'llu cmp2, %'llu cmp4, %'llu cmpAll\n",
224 ec_cmp2s, ec_cmp4s, ec_cmpAlls
225 );
226 }
227
228 /* Print an ExeContext. */
VG_(pp_ExeContext)229 void VG_(pp_ExeContext) ( ExeContext* ec )
230 {
231 VG_(pp_StackTrace)( VG_(get_ExeContext_epoch)(ec), ec->ips, ec->n_ips );
232 }
233
VG_(apply_ExeContext)234 void VG_(apply_ExeContext)(
235 void(*action)(UInt n, DiEpoch ep, Addr ip, void* opaque),
236 void* opaque, ExeContext* ec)
237 {
238 VG_(apply_StackTrace)(action, opaque, VG_(get_ExeContext_epoch)(ec),
239 ec->ips, ec->n_ips);
240 }
241
VG_(archive_ExeContext_in_range)242 void VG_(archive_ExeContext_in_range) (DiEpoch last_epoch,
243 Addr text_avma, SizeT length )
244 {
245 Int i;
246 ExeContext* ec;
247 ULong n_archived = 0;
248 const Addr text_avma_end = text_avma + length - 1;
249
250 if (VG_(clo_verbosity) > 1)
251 VG_(message)(Vg_DebugMsg, "Scanning and archiving ExeContexts ...\n");
252 for (i = 0; i < ec_htab_size; i++) {
253 for (ec = ec_htab[i]; ec; ec = ec->chain) {
254 if (is_DiEpoch_INVALID (ec->epoch))
255 for (UInt j = 0; j < ec->n_ips; j++) {
256 if (UNLIKELY(ec->ips[j] >= text_avma
257 && ec->ips[j] <= text_avma_end)) {
258 ec->epoch = last_epoch;
259 n_archived++;
260 break;
261 }
262 }
263 }
264 }
265 if (VG_(clo_verbosity) > 1)
266 VG_(message)(Vg_DebugMsg,
267 "Scanned %'llu ExeContexts, archived %'llu ExeContexts\n",
268 ec_totstored, n_archived);
269 }
270
271 /* Compare two ExeContexts. Number of callers considered depends on res. */
VG_(eq_ExeContext)272 Bool VG_(eq_ExeContext) ( VgRes res, const ExeContext* e1,
273 const ExeContext* e2 )
274 {
275 Int i;
276
277 if (e1 == NULL || e2 == NULL)
278 return False;
279
280 // Must be at least one address in each trace.
281 vg_assert(e1->n_ips >= 1 && e2->n_ips >= 1);
282
283 // Note: we compare the epoch in the case below, and not here
284 // to have the ec_cmp* stats correct.
285
286 switch (res) {
287 case Vg_LowRes:
288 /* Just compare the top two callers. */
289 ec_cmp2s++;
290 for (i = 0; i < 2; i++) {
291 if ( (e1->n_ips <= i) && (e2->n_ips <= i)) return True;
292 if ( (e1->n_ips <= i) && !(e2->n_ips <= i)) return False;
293 if (!(e1->n_ips <= i) && (e2->n_ips <= i)) return False;
294 if (e1->ips[i] != e2->ips[i]) return False;
295 }
296 return e1->epoch.n == e2->epoch.n;
297
298 case Vg_MedRes:
299 /* Just compare the top four callers. */
300 ec_cmp4s++;
301 for (i = 0; i < 4; i++) {
302 if ( (e1->n_ips <= i) && (e2->n_ips <= i)) return True;
303 if ( (e1->n_ips <= i) && !(e2->n_ips <= i)) return False;
304 if (!(e1->n_ips <= i) && (e2->n_ips <= i)) return False;
305 if (e1->ips[i] != e2->ips[i]) return False;
306 }
307 return e1->epoch.n == e2->epoch.n;
308
309 case Vg_HighRes:
310 ec_cmpAlls++;
311 /* Compare them all -- just do pointer comparison. */
312 if (e1 != e2) return False;
313 return True;
314
315 default:
316 VG_(core_panic)("VG_(eq_ExeContext): unrecognised VgRes");
317 }
318 }
319
320 /* VG_(record_ExeContext) is the head honcho here. Take a snapshot of
321 the client's stack. Search our collection of ExeContexts to see if
322 we already have it, and if not, allocate a new one. Either way,
323 return a pointer to the context. If there is a matching context we
324 guarantee to not allocate a new one. Thus we never store
325 duplicates, and so exact equality can be quickly done as equality
326 on the returned ExeContext* values themselves. Inspired by Hugs's
327 Text type.
328
329 Also checks whether the hash table needs expanding, and expands it
330 if so. */
331
ROLW(UWord w,Int n)332 static inline UWord ROLW ( UWord w, Int n )
333 {
334 Int bpw = 8 * sizeof(UWord);
335 w = (w << n) | (w >> (bpw-n));
336 return w;
337 }
338
calc_hash(const Addr * ips,UInt n_ips,UWord htab_sz)339 static UWord calc_hash ( const Addr* ips, UInt n_ips, UWord htab_sz )
340 {
341 UInt i;
342 UWord hash = 0;
343 vg_assert(htab_sz > 0);
344 for (i = 0; i < n_ips; i++) {
345 hash ^= ips[i];
346 hash = ROLW(hash, 19);
347 }
348 return hash % htab_sz;
349 }
350
resize_ec_htab(void)351 static void resize_ec_htab ( void )
352 {
353 SizeT i;
354 SizeT new_size;
355 ExeContext** new_ec_htab;
356
357 vg_assert(ec_htab_size_idx >= 0 && ec_htab_size_idx < N_EC_PRIMES);
358 if (ec_htab_size_idx == N_EC_PRIMES-1)
359 return; /* out of primes - can't resize further */
360
361 new_size = ec_primes[ec_htab_size_idx + 1];
362 new_ec_htab = VG_(malloc)("execontext.reh1",
363 sizeof(ExeContext*) * new_size);
364
365 VG_(debugLog)(
366 1, "execontext",
367 "resizing htab from size %lu to %lu (idx %lu) Total#ECs=%llu\n",
368 ec_htab_size, new_size, ec_htab_size_idx + 1, ec_totstored);
369
370 for (i = 0; i < new_size; i++)
371 new_ec_htab[i] = NULL;
372
373 for (i = 0; i < ec_htab_size; i++) {
374 ExeContext* cur = ec_htab[i];
375 while (cur) {
376 ExeContext* next = cur->chain;
377 UWord hash = calc_hash(cur->ips, cur->n_ips, new_size);
378 vg_assert(hash < new_size);
379 cur->chain = new_ec_htab[hash];
380 new_ec_htab[hash] = cur;
381 cur = next;
382 }
383 }
384
385 VG_(free)(ec_htab);
386 ec_htab = new_ec_htab;
387 ec_htab_size = new_size;
388 ec_htab_size_idx++;
389 }
390
391 /* Used by the outer as a marker to separate the frames of the inner valgrind
392 from the frames of the inner guest frames. */
_______VVVVVVVV_appended_inner_guest_stack_VVVVVVVV_______(void)393 static void _______VVVVVVVV_appended_inner_guest_stack_VVVVVVVV_______ (void)
394 {
395 }
396
397 /* Do the first part of getting a stack trace: actually unwind the
398 stack, and hand the results off to the duplicate-trace-finder
399 (_wrk2). */
record_ExeContext_wrk(ThreadId tid,Word first_ip_delta,Bool first_ip_only)400 static ExeContext* record_ExeContext_wrk ( ThreadId tid, Word first_ip_delta,
401 Bool first_ip_only )
402 {
403 Addr ips[VG_(clo_backtrace_size)];
404 UInt n_ips;
405
406 init_ExeContext_storage();
407
408 vg_assert(sizeof(void*) == sizeof(UWord));
409 vg_assert(sizeof(void*) == sizeof(Addr));
410
411 vg_assert(VG_(is_valid_tid)(tid));
412
413 if (first_ip_only) {
414 n_ips = 1;
415 ips[0] = VG_(get_IP)(tid) + first_ip_delta;
416 } else {
417 n_ips = VG_(get_StackTrace)( tid, ips, VG_(clo_backtrace_size),
418 NULL/*array to dump SP values in*/,
419 NULL/*array to dump FP values in*/,
420 first_ip_delta );
421 if (VG_(inner_threads) != NULL
422 && n_ips + 1 < VG_(clo_backtrace_size)) {
423 /* An inner V has informed us (the outer) of its thread array.
424 Append the inner guest stack trace, if we still have some
425 room in the ips array for the separator and (some) inner
426 guest IPs. */
427 UInt inner_tid;
428
429 for (inner_tid = 1; inner_tid < VG_N_THREADS; inner_tid++) {
430 if (VG_(threads)[tid].os_state.lwpid
431 == VG_(inner_threads)[inner_tid].os_state.lwpid) {
432 ThreadState* save_outer_vg_threads = VG_(threads);
433 UInt n_ips_inner_guest;
434
435 /* Append the separator + the inner guest stack trace. */
436 ips[n_ips] = (Addr)
437 _______VVVVVVVV_appended_inner_guest_stack_VVVVVVVV_______;
438 n_ips++;
439 VG_(threads) = VG_(inner_threads);
440 n_ips_inner_guest
441 = VG_(get_StackTrace)( inner_tid,
442 ips + n_ips,
443 VG_(clo_backtrace_size) - n_ips,
444 NULL/*array to dump SP values in*/,
445 NULL/*array to dump FP values in*/,
446 first_ip_delta );
447 n_ips += n_ips_inner_guest;
448 VG_(threads) = save_outer_vg_threads;
449 break;
450 }
451 }
452 }
453 }
454
455 return record_ExeContext_wrk2 ( ips, n_ips );
456 }
457
458 /* Do the second part of getting a stack trace: ips[0 .. n_ips-1]
459 holds a proposed trace. Find or allocate a suitable ExeContext.
460 Note that callers must have done init_ExeContext_storage() before
461 getting to this point. */
record_ExeContext_wrk2(const Addr * ips,UInt n_ips)462 static ExeContext* record_ExeContext_wrk2 ( const Addr* ips, UInt n_ips )
463 {
464 Int i;
465 Bool same;
466 UWord hash;
467 ExeContext* new_ec;
468 ExeContext* list;
469 ExeContext *prev2, *prev;
470
471 static UInt ctr = 0;
472
473 vg_assert(n_ips >= 1 && n_ips <= VG_(clo_backtrace_size));
474
475 /* Now figure out if we've seen this one before. First hash it so
476 as to determine the list number. */
477 hash = calc_hash( ips, n_ips, ec_htab_size );
478
479 /* And (the expensive bit) look a for matching entry in the list. */
480
481 ec_searchreqs++;
482
483 prev2 = NULL;
484 prev = NULL;
485 list = ec_htab[hash];
486
487 while (True) {
488 if (list == NULL) break;
489 ec_searchcmps++;
490 same = list->n_ips == n_ips && is_DiEpoch_INVALID (list->epoch);
491 for (i = 0; i < n_ips && same ; i++) {
492 same = list->ips[i] == ips[i];
493 }
494 if (same) break;
495 prev2 = prev;
496 prev = list;
497 list = list->chain;
498 }
499
500 if (list != NULL) {
501 /* Yay! We found it. Once every 8 searches, move it one step
502 closer to the start of the list to make future searches
503 cheaper. */
504 if (0 == ((ctr++) & 7)) {
505 if (prev2 != NULL && prev != NULL) {
506 /* Found at 3rd or later position in the chain. */
507 vg_assert(prev2->chain == prev);
508 vg_assert(prev->chain == list);
509 prev2->chain = list;
510 prev->chain = list->chain;
511 list->chain = prev;
512 }
513 else if (prev2 == NULL && prev != NULL) {
514 /* Found at 2nd position in the chain. */
515 vg_assert(ec_htab[hash] == prev);
516 vg_assert(prev->chain == list);
517 prev->chain = list->chain;
518 list->chain = prev;
519 ec_htab[hash] = list;
520 }
521 }
522 return list;
523 }
524
525 /* Bummer. We have to allocate a new context record. */
526 ec_totstored++;
527
528 new_ec = VG_(perm_malloc)( sizeof(struct _ExeContext)
529 + n_ips * sizeof(Addr),
530 vg_alignof(struct _ExeContext));
531
532 for (i = 0; i < n_ips; i++)
533 new_ec->ips[i] = ips[i];
534
535 vg_assert(VG_(is_plausible_ECU)(ec_next_ecu));
536 new_ec->ecu = ec_next_ecu;
537 ec_next_ecu += 4;
538 if (ec_next_ecu == 0) {
539 /* Urr. Now we're hosed; we emitted 2^30 ExeContexts already
540 and have run out of numbers. Not sure what to do. */
541 VG_(core_panic)("m_execontext: more than 2^30 ExeContexts created");
542 }
543
544 new_ec->n_ips = n_ips;
545 new_ec->chain = ec_htab[hash];
546 new_ec->epoch = DiEpoch_INVALID();
547 ec_htab[hash] = new_ec;
548
549 /* Resize the hash table, maybe? */
550 if ( ((ULong)ec_totstored) > ((ULong)ec_htab_size) ) {
551 vg_assert(ec_htab_size_idx >= 0 && ec_htab_size_idx < N_EC_PRIMES);
552 if (ec_htab_size_idx < N_EC_PRIMES-1)
553 resize_ec_htab();
554 }
555
556 return new_ec;
557 }
558
VG_(record_ExeContext)559 ExeContext* VG_(record_ExeContext)( ThreadId tid, Word first_ip_delta ) {
560 return record_ExeContext_wrk( tid, first_ip_delta,
561 False/*!first_ip_only*/ );
562 }
563
VG_(record_depth_1_ExeContext)564 ExeContext* VG_(record_depth_1_ExeContext)( ThreadId tid, Word first_ip_delta )
565 {
566 return record_ExeContext_wrk( tid, first_ip_delta,
567 True/*first_ip_only*/ );
568 }
569
VG_(make_depth_1_ExeContext_from_Addr)570 ExeContext* VG_(make_depth_1_ExeContext_from_Addr)( Addr a ) {
571 init_ExeContext_storage();
572 return record_ExeContext_wrk2( &a, 1 );
573 }
574
VG_(get_ExeContext_StackTrace)575 StackTrace VG_(get_ExeContext_StackTrace) ( ExeContext* e ) {
576 return e->ips;
577 }
578
VG_(get_ECU_from_ExeContext)579 UInt VG_(get_ECU_from_ExeContext)( const ExeContext* e ) {
580 vg_assert(VG_(is_plausible_ECU)(e->ecu));
581 return e->ecu;
582 }
583
VG_(get_ExeContext_n_ips)584 Int VG_(get_ExeContext_n_ips)( const ExeContext* e ) {
585 vg_assert(e->n_ips >= 1);
586 return e->n_ips;
587 }
588
VG_(get_ExeContext_from_ECU)589 ExeContext* VG_(get_ExeContext_from_ECU)( UInt ecu )
590 {
591 UWord i;
592 ExeContext* ec;
593 vg_assert(VG_(is_plausible_ECU)(ecu));
594 vg_assert(ec_htab_size > 0);
595 for (i = 0; i < ec_htab_size; i++) {
596 for (ec = ec_htab[i]; ec; ec = ec->chain) {
597 if (ec->ecu == ecu)
598 return ec;
599 }
600 }
601 return NULL;
602 }
603
VG_(make_ExeContext_from_StackTrace)604 ExeContext* VG_(make_ExeContext_from_StackTrace)( const Addr* ips, UInt n_ips )
605 {
606 init_ExeContext_storage();
607 return record_ExeContext_wrk2(ips, n_ips);
608 }
609
VG_(null_ExeContext)610 ExeContext* VG_(null_ExeContext) (void)
611 {
612 init_ExeContext_storage();
613 return null_ExeContext;
614 }
615
616 /*--------------------------------------------------------------------*/
617 /*--- end m_execontext.c ---*/
618 /*--------------------------------------------------------------------*/
619