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-2013 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_vki.h" // To keep pub_core_threadstate.h happy
40 #include "pub_core_libcsetjmp.h" // Ditto
41 #include "pub_core_threadstate.h" // VG_(is_valid_tid)
42 #include "pub_core_execontext.h" // self
43
44 /*------------------------------------------------------------*/
45 /*--- Low-level ExeContext storage. ---*/
46 /*------------------------------------------------------------*/
47
48 /* Depending on VgRes, the first 2, 4 or all IP values are used in
49 comparisons to remove duplicate errors, and for comparing against
50 suppression specifications. If not used in comparison, the rest
51 are purely informational (but often important).
52
53 The contexts are stored in a traditional chained hash table, so as
54 to allow quick determination of whether a new context already
55 exists. The hash table starts small and expands dynamically, so as
56 to keep the load factor below 1.0.
57
58 The idea is only to ever store any one context once, so as to save
59 space and make exact comparisons faster. */
60
61
62 /* Primes for the hash table */
63
64 #define N_EC_PRIMES 18
65
66 static SizeT ec_primes[N_EC_PRIMES] = {
67 769UL, 1543UL, 3079UL, 6151UL,
68 12289UL, 24593UL, 49157UL, 98317UL,
69 196613UL, 393241UL, 786433UL, 1572869UL,
70 3145739UL, 6291469UL, 12582917UL, 25165843UL,
71 50331653UL, 100663319UL
72 };
73
74
75 /* Each element is present in a hash chain, and also contains a
76 variable length array of guest code addresses (the useful part). */
77
78 struct _ExeContext {
79 struct _ExeContext* chain;
80 /* A 32-bit unsigned integer that uniquely identifies this
81 ExeContext. Memcheck uses these for origin tracking. Values
82 must be nonzero (else Memcheck's origin tracking is hosed), must
83 be a multiple of four, and must be unique. Hence they start at
84 4. */
85 UInt ecu;
86 /* Variable-length array. The size is 'n_ips'; at
87 least 1, at most VG_DEEPEST_BACKTRACE. [0] is the current IP,
88 [1] is its caller, [2] is the caller of [1], etc. */
89 UInt n_ips;
90 Addr ips[0];
91 };
92
93
94 /* This is the dynamically expanding hash table. */
95 static ExeContext** ec_htab; /* array [ec_htab_size] of ExeContext* */
96 static SizeT ec_htab_size; /* one of the values in ec_primes */
97 static SizeT ec_htab_size_idx; /* 0 .. N_EC_PRIMES-1 */
98
99 /* ECU serial number */
100 static UInt ec_next_ecu = 4; /* We must never issue zero */
101
102 static ExeContext* null_ExeContext;
103
104 /* Stats only: the number of times the system was searched to locate a
105 context. */
106 static ULong ec_searchreqs;
107
108 /* Stats only: the number of full context comparisons done. */
109 static ULong ec_searchcmps;
110
111 /* Stats only: total number of stored contexts. */
112 static ULong ec_totstored;
113
114 /* Number of 2, 4 and (fast) full cmps done. */
115 static ULong ec_cmp2s;
116 static ULong ec_cmp4s;
117 static ULong ec_cmpAlls;
118
119
120 /*------------------------------------------------------------*/
121 /*--- Exported functions. ---*/
122 /*------------------------------------------------------------*/
123
124 static ExeContext* record_ExeContext_wrk2 ( Addr* ips, UInt n_ips ); /*fwds*/
125
126 /* Initialise this subsystem. */
init_ExeContext_storage(void)127 static void init_ExeContext_storage ( void )
128 {
129 Int i;
130 static Bool init_done = False;
131 if (LIKELY(init_done))
132 return;
133 ec_searchreqs = 0;
134 ec_searchcmps = 0;
135 ec_totstored = 0;
136 ec_cmp2s = 0;
137 ec_cmp4s = 0;
138 ec_cmpAlls = 0;
139
140 ec_htab_size_idx = 0;
141 ec_htab_size = ec_primes[ec_htab_size_idx];
142 ec_htab = VG_(malloc)("execontext.iEs1",
143 sizeof(ExeContext*) * ec_htab_size);
144 for (i = 0; i < ec_htab_size; i++)
145 ec_htab[i] = NULL;
146
147 {
148 Addr ips[1];
149 ips[0] = 0;
150 null_ExeContext = record_ExeContext_wrk2(ips, 1);
151 // null execontext must be the first one created and get ecu 4.
152 vg_assert(null_ExeContext->ecu == 4);
153 }
154
155 init_done = True;
156 }
157
158
159 /* Print stats. */
VG_(print_ExeContext_stats)160 void VG_(print_ExeContext_stats) ( Bool with_stacktraces )
161 {
162 init_ExeContext_storage();
163
164 if (with_stacktraces) {
165 Int i;
166 ExeContext* ec;
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 VG_(message)(Vg_DebugMsg,
181 " exectx: %'lu lists, %'llu contexts (avg %'llu per list)\n",
182 ec_htab_size, ec_totstored, ec_totstored / (ULong)ec_htab_size
183 );
184 VG_(message)(Vg_DebugMsg,
185 " exectx: %'llu searches, %'llu full compares (%'llu per 1000)\n",
186 ec_searchreqs, ec_searchcmps,
187 ec_searchreqs == 0
188 ? 0ULL
189 : ( (ec_searchcmps * 1000ULL) / ec_searchreqs )
190 );
191 VG_(message)(Vg_DebugMsg,
192 " exectx: %'llu cmp2, %'llu cmp4, %'llu cmpAll\n",
193 ec_cmp2s, ec_cmp4s, ec_cmpAlls
194 );
195 }
196
197
198 /* Print an ExeContext. */
VG_(pp_ExeContext)199 void VG_(pp_ExeContext) ( ExeContext* ec )
200 {
201 VG_(pp_StackTrace)( ec->ips, ec->n_ips );
202 }
203
204
205 /* Compare two ExeContexts. Number of callers considered depends on res. */
VG_(eq_ExeContext)206 Bool VG_(eq_ExeContext) ( VgRes res, ExeContext* e1, ExeContext* e2 )
207 {
208 Int i;
209
210 if (e1 == NULL || e2 == NULL)
211 return False;
212
213 // Must be at least one address in each trace.
214 tl_assert(e1->n_ips >= 1 && e2->n_ips >= 1);
215
216 switch (res) {
217 case Vg_LowRes:
218 /* Just compare the top two callers. */
219 ec_cmp2s++;
220 for (i = 0; i < 2; i++) {
221 if ( (e1->n_ips <= i) && (e2->n_ips <= i)) return True;
222 if ( (e1->n_ips <= i) && !(e2->n_ips <= i)) return False;
223 if (!(e1->n_ips <= i) && (e2->n_ips <= i)) return False;
224 if (e1->ips[i] != e2->ips[i]) return False;
225 }
226 return True;
227
228 case Vg_MedRes:
229 /* Just compare the top four callers. */
230 ec_cmp4s++;
231 for (i = 0; i < 4; i++) {
232 if ( (e1->n_ips <= i) && (e2->n_ips <= i)) return True;
233 if ( (e1->n_ips <= i) && !(e2->n_ips <= i)) return False;
234 if (!(e1->n_ips <= i) && (e2->n_ips <= i)) return False;
235 if (e1->ips[i] != e2->ips[i]) return False;
236 }
237 return True;
238
239 case Vg_HighRes:
240 ec_cmpAlls++;
241 /* Compare them all -- just do pointer comparison. */
242 if (e1 != e2) return False;
243 return True;
244
245 default:
246 VG_(core_panic)("VG_(eq_ExeContext): unrecognised VgRes");
247 }
248 }
249
250 /* VG_(record_ExeContext) is the head honcho here. Take a snapshot of
251 the client's stack. Search our collection of ExeContexts to see if
252 we already have it, and if not, allocate a new one. Either way,
253 return a pointer to the context. If there is a matching context we
254 guarantee to not allocate a new one. Thus we never store
255 duplicates, and so exact equality can be quickly done as equality
256 on the returned ExeContext* values themselves. Inspired by Hugs's
257 Text type.
258
259 Also checks whether the hash table needs expanding, and expands it
260 if so. */
261
ROLW(UWord w,Int n)262 static inline UWord ROLW ( UWord w, Int n )
263 {
264 Int bpw = 8 * sizeof(UWord);
265 w = (w << n) | (w >> (bpw-n));
266 return w;
267 }
268
calc_hash(Addr * ips,UInt n_ips,UWord htab_sz)269 static UWord calc_hash ( Addr* ips, UInt n_ips, UWord htab_sz )
270 {
271 UInt i;
272 UWord hash = 0;
273 vg_assert(htab_sz > 0);
274 for (i = 0; i < n_ips; i++) {
275 hash ^= ips[i];
276 hash = ROLW(hash, 19);
277 }
278 return hash % htab_sz;
279 }
280
resize_ec_htab(void)281 static void resize_ec_htab ( void )
282 {
283 SizeT i;
284 SizeT new_size;
285 ExeContext** new_ec_htab;
286
287 vg_assert(ec_htab_size_idx >= 0 && ec_htab_size_idx < N_EC_PRIMES);
288 if (ec_htab_size_idx == N_EC_PRIMES-1)
289 return; /* out of primes - can't resize further */
290
291 new_size = ec_primes[ec_htab_size_idx + 1];
292 new_ec_htab = VG_(malloc)("execontext.reh1",
293 sizeof(ExeContext*) * new_size);
294
295 VG_(debugLog)(
296 1, "execontext",
297 "resizing htab from size %lu to %lu (idx %lu) Total#ECs=%llu\n",
298 ec_htab_size, new_size, ec_htab_size_idx + 1, ec_totstored);
299
300 for (i = 0; i < new_size; i++)
301 new_ec_htab[i] = NULL;
302
303 for (i = 0; i < ec_htab_size; i++) {
304 ExeContext* cur = ec_htab[i];
305 while (cur) {
306 ExeContext* next = cur->chain;
307 UWord hash = calc_hash(cur->ips, cur->n_ips, new_size);
308 vg_assert(hash < new_size);
309 cur->chain = new_ec_htab[hash];
310 new_ec_htab[hash] = cur;
311 cur = next;
312 }
313 }
314
315 VG_(free)(ec_htab);
316 ec_htab = new_ec_htab;
317 ec_htab_size = new_size;
318 ec_htab_size_idx++;
319 }
320
321 /* Do the first part of getting a stack trace: actually unwind the
322 stack, and hand the results off to the duplicate-trace-finder
323 (_wrk2). */
record_ExeContext_wrk(ThreadId tid,Word first_ip_delta,Bool first_ip_only)324 static ExeContext* record_ExeContext_wrk ( ThreadId tid, Word first_ip_delta,
325 Bool first_ip_only )
326 {
327 Addr ips[VG_(clo_backtrace_size)];
328 UInt n_ips;
329
330 init_ExeContext_storage();
331
332 vg_assert(sizeof(void*) == sizeof(UWord));
333 vg_assert(sizeof(void*) == sizeof(Addr));
334
335 vg_assert(VG_(is_valid_tid)(tid));
336
337 if (first_ip_only) {
338 n_ips = 1;
339 ips[0] = VG_(get_IP)(tid) + first_ip_delta;
340 } else {
341 n_ips = VG_(get_StackTrace)( tid, ips, VG_(clo_backtrace_size),
342 NULL/*array to dump SP values in*/,
343 NULL/*array to dump FP values in*/,
344 first_ip_delta );
345 }
346
347 return record_ExeContext_wrk2 ( ips, n_ips );
348 }
349
350 /* Do the second part of getting a stack trace: ips[0 .. n_ips-1]
351 holds a proposed trace. Find or allocate a suitable ExeContext.
352 Note that callers must have done init_ExeContext_storage() before
353 getting to this point. */
record_ExeContext_wrk2(Addr * ips,UInt n_ips)354 static ExeContext* record_ExeContext_wrk2 ( Addr* ips, UInt n_ips )
355 {
356 Int i;
357 Bool same;
358 UWord hash;
359 ExeContext* new_ec;
360 ExeContext* list;
361 ExeContext *prev2, *prev;
362
363 static UInt ctr = 0;
364
365 tl_assert(n_ips >= 1 && n_ips <= VG_(clo_backtrace_size));
366
367 /* Now figure out if we've seen this one before. First hash it so
368 as to determine the list number. */
369 hash = calc_hash( ips, n_ips, ec_htab_size );
370
371 /* And (the expensive bit) look a for matching entry in the list. */
372
373 ec_searchreqs++;
374
375 prev2 = NULL;
376 prev = NULL;
377 list = ec_htab[hash];
378
379 while (True) {
380 if (list == NULL) break;
381 ec_searchcmps++;
382 same = True;
383 for (i = 0; i < n_ips; i++) {
384 if (list->ips[i] != ips[i]) {
385 same = False;
386 break;
387 }
388 }
389 if (same) break;
390 prev2 = prev;
391 prev = list;
392 list = list->chain;
393 }
394
395 if (list != NULL) {
396 /* Yay! We found it. Once every 8 searches, move it one step
397 closer to the start of the list to make future searches
398 cheaper. */
399 if (0 == ((ctr++) & 7)) {
400 if (prev2 != NULL && prev != NULL) {
401 /* Found at 3rd or later position in the chain. */
402 vg_assert(prev2->chain == prev);
403 vg_assert(prev->chain == list);
404 prev2->chain = list;
405 prev->chain = list->chain;
406 list->chain = prev;
407 }
408 else if (prev2 == NULL && prev != NULL) {
409 /* Found at 2nd position in the chain. */
410 vg_assert(ec_htab[hash] == prev);
411 vg_assert(prev->chain == list);
412 prev->chain = list->chain;
413 list->chain = prev;
414 ec_htab[hash] = list;
415 }
416 }
417 return list;
418 }
419
420 /* Bummer. We have to allocate a new context record. */
421 ec_totstored++;
422
423 new_ec = VG_(perm_malloc)( sizeof(struct _ExeContext)
424 + n_ips * sizeof(Addr),
425 vg_alignof(struct _ExeContext));
426
427 for (i = 0; i < n_ips; i++)
428 new_ec->ips[i] = ips[i];
429
430 vg_assert(VG_(is_plausible_ECU)(ec_next_ecu));
431 new_ec->ecu = ec_next_ecu;
432 ec_next_ecu += 4;
433 if (ec_next_ecu == 0) {
434 /* Urr. Now we're hosed; we emitted 2^30 ExeContexts already
435 and have run out of numbers. Not sure what to do. */
436 VG_(core_panic)("m_execontext: more than 2^30 ExeContexts created");
437 }
438
439 new_ec->n_ips = n_ips;
440 new_ec->chain = ec_htab[hash];
441 ec_htab[hash] = new_ec;
442
443 /* Resize the hash table, maybe? */
444 if ( ((ULong)ec_totstored) > ((ULong)ec_htab_size) ) {
445 vg_assert(ec_htab_size_idx >= 0 && ec_htab_size_idx < N_EC_PRIMES);
446 if (ec_htab_size_idx < N_EC_PRIMES-1)
447 resize_ec_htab();
448 }
449
450 return new_ec;
451 }
452
VG_(record_ExeContext)453 ExeContext* VG_(record_ExeContext)( ThreadId tid, Word first_ip_delta ) {
454 return record_ExeContext_wrk( tid, first_ip_delta,
455 False/*!first_ip_only*/ );
456 }
457
VG_(record_depth_1_ExeContext)458 ExeContext* VG_(record_depth_1_ExeContext)( ThreadId tid, Word first_ip_delta )
459 {
460 return record_ExeContext_wrk( tid, first_ip_delta,
461 True/*first_ip_only*/ );
462 }
463
VG_(make_depth_1_ExeContext_from_Addr)464 ExeContext* VG_(make_depth_1_ExeContext_from_Addr)( Addr a ) {
465 init_ExeContext_storage();
466 return record_ExeContext_wrk2( &a, 1 );
467 }
468
VG_(get_ExeContext_StackTrace)469 StackTrace VG_(get_ExeContext_StackTrace) ( ExeContext* e ) {
470 return e->ips;
471 }
472
VG_(get_ECU_from_ExeContext)473 UInt VG_(get_ECU_from_ExeContext)( ExeContext* e ) {
474 vg_assert(VG_(is_plausible_ECU)(e->ecu));
475 return e->ecu;
476 }
477
VG_(get_ExeContext_n_ips)478 Int VG_(get_ExeContext_n_ips)( ExeContext* e ) {
479 vg_assert(e->n_ips >= 1);
480 return e->n_ips;
481 }
482
VG_(get_ExeContext_from_ECU)483 ExeContext* VG_(get_ExeContext_from_ECU)( UInt ecu )
484 {
485 UWord i;
486 ExeContext* ec;
487 vg_assert(VG_(is_plausible_ECU)(ecu));
488 vg_assert(ec_htab_size > 0);
489 for (i = 0; i < ec_htab_size; i++) {
490 for (ec = ec_htab[i]; ec; ec = ec->chain) {
491 if (ec->ecu == ecu)
492 return ec;
493 }
494 }
495 return NULL;
496 }
497
VG_(make_ExeContext_from_StackTrace)498 ExeContext* VG_(make_ExeContext_from_StackTrace)( Addr* ips, UInt n_ips )
499 {
500 init_ExeContext_storage();
501 return record_ExeContext_wrk2(ips, n_ips);
502 }
503
VG_(null_ExeContext)504 ExeContext* VG_(null_ExeContext) (void)
505 {
506 init_ExeContext_storage();
507 return null_ExeContext;
508 }
509
510 /*--------------------------------------------------------------------*/
511 /*--- end m_execontext.c ---*/
512 /*--------------------------------------------------------------------*/
513