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