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