Add support for the Linux membarrier() system call
[valgrind.git] / coregrind / m_execontext.c
blob50ec9f4ee5ae6fe519854c69ff6df8969ab9d93f
2 /*--------------------------------------------------------------------*/
3 /*--- Store and compare stack backtraces m_execontext.c ---*/
4 /*--------------------------------------------------------------------*/
6 /*
7 This file is part of Valgrind, a dynamic binary instrumentation
8 framework.
10 Copyright (C) 2000-2017 Julian Seward
11 jseward@acm.org
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
26 02111-1307, USA.
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). */
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];
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
118 context. */
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 )
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;
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;
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);
168 init_done = True;
171 DiEpoch VG_(get_ExeContext_epoch)( const ExeContext* e )
173 if (is_DiEpoch_INVALID (e->epoch))
174 return VG_(current_DiEpoch)();
175 else
176 return e->epoch;
179 /* Print stats. */
180 void VG_(print_ExeContext_stats) ( Bool with_stacktraces )
182 Int i;
183 ULong total_n_ips;
184 ExeContext* ec;
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",
201 ec_totstored);
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;
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,
218 ec_searchreqs == 0
219 ? 0ULL
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 )
239 Int i;
240 ExeContext* ec;
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;
253 n_archived++;
254 break;
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 )
269 Int i;
271 if (e1 == NULL || e2 == NULL)
272 return False;
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.
280 switch (res) {
281 case Vg_LowRes:
282 /* Just compare the top two callers. */
283 ec_cmp2s++;
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;
292 case Vg_MedRes:
293 /* Just compare the top four callers. */
294 ec_cmp4s++;
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;
303 case Vg_HighRes:
304 ec_cmpAlls++;
305 /* Compare them all -- just do pointer comparison. */
306 if (e1 != e2) return False;
307 return True;
309 default:
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
321 Text type.
323 Also checks whether the hash table needs expanding, and expands it
324 if so. */
326 static inline UWord ROLW ( UWord w, Int n )
328 Int bpw = 8 * sizeof(UWord);
329 w = (w << n) | (w >> (bpw-n));
330 return w;
333 static UWord calc_hash ( const Addr* ips, UInt n_ips, UWord htab_sz )
335 UInt i;
336 UWord hash = 0;
337 vg_assert(htab_sz > 0);
338 for (i = 0; i < n_ips; i++) {
339 hash ^= ips[i];
340 hash = ROLW(hash, 19);
342 return hash % htab_sz;
345 static void resize_ec_htab ( void )
347 SizeT i;
348 SizeT new_size;
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);
359 VG_(debugLog)(
360 1, "execontext",
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];
369 while (cur) {
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;
375 cur = next;
379 VG_(free)(ec_htab);
380 ec_htab = new_ec_htab;
381 ec_htab_size = new_size;
382 ec_htab_size_idx++;
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
393 (_wrk2). */
394 static ExeContext* record_ExeContext_wrk ( ThreadId tid, Word first_ip_delta,
395 Bool first_ip_only )
397 Addr ips[VG_(clo_backtrace_size)];
398 UInt n_ips;
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));
407 if (first_ip_only) {
408 n_ips = 1;
409 ips[0] = VG_(get_IP)(tid) + first_ip_delta;
410 } else {
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*/,
414 first_ip_delta );
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
420 guest IPs. */
421 UInt inner_tid;
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. */
430 ips[n_ips] = (Addr)
431 _______VVVVVVVV_appended_inner_guest_stack_VVVVVVVV_______;
432 n_ips++;
433 VG_(threads) = VG_(inner_threads);
434 n_ips_inner_guest
435 = VG_(get_StackTrace)( inner_tid,
436 ips + n_ips,
437 VG_(clo_backtrace_size) - n_ips,
438 NULL/*array to dump SP values in*/,
439 NULL/*array to dump FP values in*/,
440 first_ip_delta );
441 n_ips += n_ips_inner_guest;
442 VG_(threads) = save_outer_vg_threads;
443 break;
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 )
458 Int i;
459 Bool same;
460 UWord hash;
461 ExeContext* new_ec;
462 ExeContext* list;
463 ExeContext *prev2, *prev;
465 static UInt ctr = 0;
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. */
475 ec_searchreqs++;
477 prev2 = NULL;
478 prev = NULL;
479 list = ec_htab[hash];
481 while (True) {
482 if (list == NULL) break;
483 ec_searchcmps++;
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];
488 if (same) break;
489 prev2 = prev;
490 prev = list;
491 list = list->chain;
494 if (list != NULL) {
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
497 cheaper. */
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);
503 prev2->chain = list;
504 prev->chain = list->chain;
505 list->chain = prev;
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;
512 list->chain = prev;
513 ec_htab[hash] = list;
516 return list;
519 /* Bummer. We have to allocate a new context record. */
520 ec_totstored++;
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;
531 ec_next_ecu += 4;
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)
546 resize_ec_htab();
549 return new_ec;
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 ) {
569 return e->ips;
572 UInt VG_(get_ECU_from_ExeContext)( const ExeContext* e ) {
573 vg_assert(VG_(is_plausible_ECU)(e->ecu));
574 return e->ecu;
577 Int VG_(get_ExeContext_n_ips)( const ExeContext* e ) {
578 vg_assert(e->n_ips >= 1);
579 return e->n_ips;
582 ExeContext* VG_(get_ExeContext_from_ECU)( UInt ecu )
584 UWord i;
585 ExeContext* ec;
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) {
590 if (ec->ecu == ecu)
591 return ec;
594 return NULL;
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 /*--------------------------------------------------------------------*/