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 /* Variable-length array. The size is 'n_ips'; at
85 least 1, at most VG_DEEPEST_BACKTRACE. [0] is the current IP,
86 [1] is its caller, [2] is the caller of [1], etc. */
87 UInt n_ips;
88 Addr ips[0];
89 };
90
91
92 /* This is the dynamically expanding hash table. */
93 static ExeContext** ec_htab; /* array [ec_htab_size] of ExeContext* */
94 static SizeT ec_htab_size; /* one of the values in ec_primes */
95 static SizeT ec_htab_size_idx; /* 0 .. N_EC_PRIMES-1 */
96
97 /* ECU serial number */
98 static UInt ec_next_ecu = 4; /* We must never issue zero */
99
100 static ExeContext* null_ExeContext;
101
102 /* Stats only: the number of times the system was searched to locate a
103 context. */
104 static ULong ec_searchreqs;
105
106 /* Stats only: the number of full context comparisons done. */
107 static ULong ec_searchcmps;
108
109 /* Stats only: total number of stored contexts. */
110 static ULong ec_totstored;
111
112 /* Number of 2, 4 and (fast) full cmps done. */
113 static ULong ec_cmp2s;
114 static ULong ec_cmp4s;
115 static ULong ec_cmpAlls;
116
117
118 /*------------------------------------------------------------*/
119 /*--- Exported functions. ---*/
120 /*------------------------------------------------------------*/
121
122 static ExeContext* record_ExeContext_wrk2 ( const Addr* ips, UInt n_ips );
123
124 /* Initialise this subsystem. */
init_ExeContext_storage(void)125 static void init_ExeContext_storage ( void )
126 {
127 Int i;
128 static Bool init_done = False;
129 if (LIKELY(init_done))
130 return;
131 ec_searchreqs = 0;
132 ec_searchcmps = 0;
133 ec_totstored = 0;
134 ec_cmp2s = 0;
135 ec_cmp4s = 0;
136 ec_cmpAlls = 0;
137
138 ec_htab_size_idx = 0;
139 ec_htab_size = ec_primes[ec_htab_size_idx];
140 ec_htab = VG_(malloc)("execontext.iEs1",
141 sizeof(ExeContext*) * ec_htab_size);
142 for (i = 0; i < ec_htab_size; i++)
143 ec_htab[i] = NULL;
144
145 {
146 Addr ips[1];
147 ips[0] = 0;
148 null_ExeContext = record_ExeContext_wrk2(ips, 1);
149 // null execontext must be the first one created and get ecu 4.
150 vg_assert(null_ExeContext->ecu == 4);
151 }
152
153 init_done = True;
154 }
155
156
157 /* Print stats. */
VG_(print_ExeContext_stats)158 void VG_(print_ExeContext_stats) ( Bool with_stacktraces )
159 {
160 Int i;
161 ULong total_n_ips;
162 ExeContext* ec;
163
164 init_ExeContext_storage();
165
166 if (with_stacktraces) {
167 VG_(message)(Vg_DebugMsg, " exectx: Printing contexts stacktraces\n");
168 for (i = 0; i < ec_htab_size; i++) {
169 for (ec = ec_htab[i]; ec; ec = ec->chain) {
170 VG_(message)(Vg_DebugMsg, " exectx: stacktrace ecu %u n_ips %u\n",
171 ec->ecu, ec->n_ips);
172 VG_(pp_StackTrace)( ec->ips, ec->n_ips );
173 }
174 }
175 VG_(message)(Vg_DebugMsg,
176 " exectx: Printed %'llu contexts stacktraces\n",
177 ec_totstored);
178 }
179
180 total_n_ips = 0;
181 for (i = 0; i < ec_htab_size; i++) {
182 for (ec = ec_htab[i]; ec; ec = ec->chain)
183 total_n_ips += ec->n_ips;
184 }
185 VG_(message)(Vg_DebugMsg,
186 " exectx: %'lu lists, %'llu contexts (avg %3.2f per list)"
187 " (avg %3.2f IP per context)\n",
188 ec_htab_size, ec_totstored, (Double)ec_totstored / (Double)ec_htab_size,
189 (Double)total_n_ips / (Double)ec_totstored
190 );
191 VG_(message)(Vg_DebugMsg,
192 " exectx: %'llu searches, %'llu full compares (%'llu per 1000)\n",
193 ec_searchreqs, ec_searchcmps,
194 ec_searchreqs == 0
195 ? 0ULL
196 : ( (ec_searchcmps * 1000ULL) / ec_searchreqs )
197 );
198 VG_(message)(Vg_DebugMsg,
199 " exectx: %'llu cmp2, %'llu cmp4, %'llu cmpAll\n",
200 ec_cmp2s, ec_cmp4s, ec_cmpAlls
201 );
202 }
203
204
205 /* Print an ExeContext. */
VG_(pp_ExeContext)206 void VG_(pp_ExeContext) ( ExeContext* ec )
207 {
208 VG_(pp_StackTrace)( ec->ips, ec->n_ips );
209 }
210
211
212 /* Compare two ExeContexts. Number of callers considered depends on res. */
VG_(eq_ExeContext)213 Bool VG_(eq_ExeContext) ( VgRes res, const ExeContext* e1,
214 const ExeContext* e2 )
215 {
216 Int i;
217
218 if (e1 == NULL || e2 == NULL)
219 return False;
220
221 // Must be at least one address in each trace.
222 vg_assert(e1->n_ips >= 1 && e2->n_ips >= 1);
223
224 switch (res) {
225 case Vg_LowRes:
226 /* Just compare the top two callers. */
227 ec_cmp2s++;
228 for (i = 0; i < 2; i++) {
229 if ( (e1->n_ips <= i) && (e2->n_ips <= i)) return True;
230 if ( (e1->n_ips <= i) && !(e2->n_ips <= i)) return False;
231 if (!(e1->n_ips <= i) && (e2->n_ips <= i)) return False;
232 if (e1->ips[i] != e2->ips[i]) return False;
233 }
234 return True;
235
236 case Vg_MedRes:
237 /* Just compare the top four callers. */
238 ec_cmp4s++;
239 for (i = 0; i < 4; i++) {
240 if ( (e1->n_ips <= i) && (e2->n_ips <= i)) return True;
241 if ( (e1->n_ips <= i) && !(e2->n_ips <= i)) return False;
242 if (!(e1->n_ips <= i) && (e2->n_ips <= i)) return False;
243 if (e1->ips[i] != e2->ips[i]) return False;
244 }
245 return True;
246
247 case Vg_HighRes:
248 ec_cmpAlls++;
249 /* Compare them all -- just do pointer comparison. */
250 if (e1 != e2) return False;
251 return True;
252
253 default:
254 VG_(core_panic)("VG_(eq_ExeContext): unrecognised VgRes");
255 }
256 }
257
258 /* VG_(record_ExeContext) is the head honcho here. Take a snapshot of
259 the client's stack. Search our collection of ExeContexts to see if
260 we already have it, and if not, allocate a new one. Either way,
261 return a pointer to the context. If there is a matching context we
262 guarantee to not allocate a new one. Thus we never store
263 duplicates, and so exact equality can be quickly done as equality
264 on the returned ExeContext* values themselves. Inspired by Hugs's
265 Text type.
266
267 Also checks whether the hash table needs expanding, and expands it
268 if so. */
269
ROLW(UWord w,Int n)270 static inline UWord ROLW ( UWord w, Int n )
271 {
272 Int bpw = 8 * sizeof(UWord);
273 w = (w << n) | (w >> (bpw-n));
274 return w;
275 }
276
calc_hash(const Addr * ips,UInt n_ips,UWord htab_sz)277 static UWord calc_hash ( const Addr* ips, UInt n_ips, UWord htab_sz )
278 {
279 UInt i;
280 UWord hash = 0;
281 vg_assert(htab_sz > 0);
282 for (i = 0; i < n_ips; i++) {
283 hash ^= ips[i];
284 hash = ROLW(hash, 19);
285 }
286 return hash % htab_sz;
287 }
288
resize_ec_htab(void)289 static void resize_ec_htab ( void )
290 {
291 SizeT i;
292 SizeT new_size;
293 ExeContext** new_ec_htab;
294
295 vg_assert(ec_htab_size_idx >= 0 && ec_htab_size_idx < N_EC_PRIMES);
296 if (ec_htab_size_idx == N_EC_PRIMES-1)
297 return; /* out of primes - can't resize further */
298
299 new_size = ec_primes[ec_htab_size_idx + 1];
300 new_ec_htab = VG_(malloc)("execontext.reh1",
301 sizeof(ExeContext*) * new_size);
302
303 VG_(debugLog)(
304 1, "execontext",
305 "resizing htab from size %lu to %lu (idx %lu) Total#ECs=%llu\n",
306 ec_htab_size, new_size, ec_htab_size_idx + 1, ec_totstored);
307
308 for (i = 0; i < new_size; i++)
309 new_ec_htab[i] = NULL;
310
311 for (i = 0; i < ec_htab_size; i++) {
312 ExeContext* cur = ec_htab[i];
313 while (cur) {
314 ExeContext* next = cur->chain;
315 UWord hash = calc_hash(cur->ips, cur->n_ips, new_size);
316 vg_assert(hash < new_size);
317 cur->chain = new_ec_htab[hash];
318 new_ec_htab[hash] = cur;
319 cur = next;
320 }
321 }
322
323 VG_(free)(ec_htab);
324 ec_htab = new_ec_htab;
325 ec_htab_size = new_size;
326 ec_htab_size_idx++;
327 }
328
329 /* Used by the outer as a marker to separate the frames of the inner valgrind
330 from the frames of the inner guest frames. */
_______VVVVVVVV_appended_inner_guest_stack_VVVVVVVV_______(void)331 static void _______VVVVVVVV_appended_inner_guest_stack_VVVVVVVV_______ (void)
332 {
333 }
334
335 /* Do the first part of getting a stack trace: actually unwind the
336 stack, and hand the results off to the duplicate-trace-finder
337 (_wrk2). */
record_ExeContext_wrk(ThreadId tid,Word first_ip_delta,Bool first_ip_only)338 static ExeContext* record_ExeContext_wrk ( ThreadId tid, Word first_ip_delta,
339 Bool first_ip_only )
340 {
341 Addr ips[VG_(clo_backtrace_size)];
342 UInt n_ips;
343
344 init_ExeContext_storage();
345
346 vg_assert(sizeof(void*) == sizeof(UWord));
347 vg_assert(sizeof(void*) == sizeof(Addr));
348
349 vg_assert(VG_(is_valid_tid)(tid));
350
351 if (first_ip_only) {
352 n_ips = 1;
353 ips[0] = VG_(get_IP)(tid) + first_ip_delta;
354 } else {
355 n_ips = VG_(get_StackTrace)( tid, ips, VG_(clo_backtrace_size),
356 NULL/*array to dump SP values in*/,
357 NULL/*array to dump FP values in*/,
358 first_ip_delta );
359 if (VG_(inner_threads) != NULL
360 && n_ips + 1 < VG_(clo_backtrace_size)) {
361 /* An inner V has informed us (the outer) of its thread array.
362 Append the inner guest stack trace, if we still have some
363 room in the ips array for the separator and (some) inner
364 guest IPs. */
365 UInt inner_tid;
366
367 for (inner_tid = 1; inner_tid < VG_N_THREADS; inner_tid++) {
368 if (VG_(threads)[tid].os_state.lwpid
369 == VG_(inner_threads)[inner_tid].os_state.lwpid) {
370 ThreadState* save_outer_vg_threads = VG_(threads);
371 UInt n_ips_inner_guest;
372
373 /* Append the separator + the inner guest stack trace. */
374 ips[n_ips] = (Addr)
375 _______VVVVVVVV_appended_inner_guest_stack_VVVVVVVV_______;
376 n_ips++;
377 VG_(threads) = VG_(inner_threads);
378 n_ips_inner_guest
379 = VG_(get_StackTrace)( inner_tid,
380 ips + n_ips,
381 VG_(clo_backtrace_size) - n_ips,
382 NULL/*array to dump SP values in*/,
383 NULL/*array to dump FP values in*/,
384 first_ip_delta );
385 n_ips += n_ips_inner_guest;
386 VG_(threads) = save_outer_vg_threads;
387 break;
388 }
389 }
390 }
391 }
392
393 return record_ExeContext_wrk2 ( ips, n_ips );
394 }
395
396 /* Do the second part of getting a stack trace: ips[0 .. n_ips-1]
397 holds a proposed trace. Find or allocate a suitable ExeContext.
398 Note that callers must have done init_ExeContext_storage() before
399 getting to this point. */
record_ExeContext_wrk2(const Addr * ips,UInt n_ips)400 static ExeContext* record_ExeContext_wrk2 ( const Addr* ips, UInt n_ips )
401 {
402 Int i;
403 Bool same;
404 UWord hash;
405 ExeContext* new_ec;
406 ExeContext* list;
407 ExeContext *prev2, *prev;
408
409 static UInt ctr = 0;
410
411 vg_assert(n_ips >= 1 && n_ips <= VG_(clo_backtrace_size));
412
413 /* Now figure out if we've seen this one before. First hash it so
414 as to determine the list number. */
415 hash = calc_hash( ips, n_ips, ec_htab_size );
416
417 /* And (the expensive bit) look a for matching entry in the list. */
418
419 ec_searchreqs++;
420
421 prev2 = NULL;
422 prev = NULL;
423 list = ec_htab[hash];
424
425 while (True) {
426 if (list == NULL) break;
427 ec_searchcmps++;
428 same = list->n_ips == n_ips;
429 for (i = 0; i < n_ips && same ; i++) {
430 same = list->ips[i] == ips[i];
431 }
432 if (same) break;
433 prev2 = prev;
434 prev = list;
435 list = list->chain;
436 }
437
438 if (list != NULL) {
439 /* Yay! We found it. Once every 8 searches, move it one step
440 closer to the start of the list to make future searches
441 cheaper. */
442 if (0 == ((ctr++) & 7)) {
443 if (prev2 != NULL && prev != NULL) {
444 /* Found at 3rd or later position in the chain. */
445 vg_assert(prev2->chain == prev);
446 vg_assert(prev->chain == list);
447 prev2->chain = list;
448 prev->chain = list->chain;
449 list->chain = prev;
450 }
451 else if (prev2 == NULL && prev != NULL) {
452 /* Found at 2nd position in the chain. */
453 vg_assert(ec_htab[hash] == prev);
454 vg_assert(prev->chain == list);
455 prev->chain = list->chain;
456 list->chain = prev;
457 ec_htab[hash] = list;
458 }
459 }
460 return list;
461 }
462
463 /* Bummer. We have to allocate a new context record. */
464 ec_totstored++;
465
466 new_ec = VG_(perm_malloc)( sizeof(struct _ExeContext)
467 + n_ips * sizeof(Addr),
468 vg_alignof(struct _ExeContext));
469
470 for (i = 0; i < n_ips; i++)
471 new_ec->ips[i] = ips[i];
472
473 vg_assert(VG_(is_plausible_ECU)(ec_next_ecu));
474 new_ec->ecu = ec_next_ecu;
475 ec_next_ecu += 4;
476 if (ec_next_ecu == 0) {
477 /* Urr. Now we're hosed; we emitted 2^30 ExeContexts already
478 and have run out of numbers. Not sure what to do. */
479 VG_(core_panic)("m_execontext: more than 2^30 ExeContexts created");
480 }
481
482 new_ec->n_ips = n_ips;
483 new_ec->chain = ec_htab[hash];
484 ec_htab[hash] = new_ec;
485
486 /* Resize the hash table, maybe? */
487 if ( ((ULong)ec_totstored) > ((ULong)ec_htab_size) ) {
488 vg_assert(ec_htab_size_idx >= 0 && ec_htab_size_idx < N_EC_PRIMES);
489 if (ec_htab_size_idx < N_EC_PRIMES-1)
490 resize_ec_htab();
491 }
492
493 return new_ec;
494 }
495
VG_(record_ExeContext)496 ExeContext* VG_(record_ExeContext)( ThreadId tid, Word first_ip_delta ) {
497 return record_ExeContext_wrk( tid, first_ip_delta,
498 False/*!first_ip_only*/ );
499 }
500
VG_(record_depth_1_ExeContext)501 ExeContext* VG_(record_depth_1_ExeContext)( ThreadId tid, Word first_ip_delta )
502 {
503 return record_ExeContext_wrk( tid, first_ip_delta,
504 True/*first_ip_only*/ );
505 }
506
VG_(make_depth_1_ExeContext_from_Addr)507 ExeContext* VG_(make_depth_1_ExeContext_from_Addr)( Addr a ) {
508 init_ExeContext_storage();
509 return record_ExeContext_wrk2( &a, 1 );
510 }
511
VG_(get_ExeContext_StackTrace)512 StackTrace VG_(get_ExeContext_StackTrace) ( ExeContext* e ) {
513 return e->ips;
514 }
515
VG_(get_ECU_from_ExeContext)516 UInt VG_(get_ECU_from_ExeContext)( const ExeContext* e ) {
517 vg_assert(VG_(is_plausible_ECU)(e->ecu));
518 return e->ecu;
519 }
520
VG_(get_ExeContext_n_ips)521 Int VG_(get_ExeContext_n_ips)( const ExeContext* e ) {
522 vg_assert(e->n_ips >= 1);
523 return e->n_ips;
524 }
525
VG_(get_ExeContext_from_ECU)526 ExeContext* VG_(get_ExeContext_from_ECU)( UInt ecu )
527 {
528 UWord i;
529 ExeContext* ec;
530 vg_assert(VG_(is_plausible_ECU)(ecu));
531 vg_assert(ec_htab_size > 0);
532 for (i = 0; i < ec_htab_size; i++) {
533 for (ec = ec_htab[i]; ec; ec = ec->chain) {
534 if (ec->ecu == ecu)
535 return ec;
536 }
537 }
538 return NULL;
539 }
540
VG_(make_ExeContext_from_StackTrace)541 ExeContext* VG_(make_ExeContext_from_StackTrace)( const Addr* ips, UInt n_ips )
542 {
543 init_ExeContext_storage();
544 return record_ExeContext_wrk2(ips, n_ips);
545 }
546
VG_(null_ExeContext)547 ExeContext* VG_(null_ExeContext) (void)
548 {
549 init_ExeContext_storage();
550 return null_ExeContext;
551 }
552
553 /*--------------------------------------------------------------------*/
554 /*--- end m_execontext.c ---*/
555 /*--------------------------------------------------------------------*/
556