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