m_execontext.c revision 6e4b71339ecdf4accc77e86a892718516a531b0f 
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/* 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
66static 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
78struct _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. */
95static ExeContext** ec_htab; /* array [ec_htab_size] of ExeContext* */
96static SizeT        ec_htab_size;     /* one of the values in ec_primes */
97static SizeT        ec_htab_size_idx; /* 0 .. N_EC_PRIMES-1 */
98
99/* ECU serial number */
100static UInt ec_next_ecu = 4; /* We must never issue zero */
101
102static ExeContext* null_ExeContext;
103
104/* Stats only: the number of times the system was searched to locate a
105   context. */
106static ULong ec_searchreqs;
107
108/* Stats only: the number of full context comparisons done. */
109static ULong ec_searchcmps;
110
111/* Stats only: total number of stored contexts. */
112static ULong ec_totstored;
113
114/* Number of 2, 4 and (fast) full cmps done. */
115static ULong ec_cmp2s;
116static ULong ec_cmp4s;
117static ULong ec_cmpAlls;
118
119
120/*------------------------------------------------------------*/
121/*--- Exported functions.                                  ---*/
122/*------------------------------------------------------------*/
123
124static ExeContext* record_ExeContext_wrk2 ( Addr* ips, UInt n_ips ); /*fwds*/
125
126/* Initialise this subsystem. */
127static 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_(arena_malloc)(VG_AR_EXECTXT, "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. */
160void 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. */
199void 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. */
206Bool 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
262static 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
269static 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
281static 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_(arena_malloc)(VG_AR_EXECTXT, "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_(arena_free)(VG_AR_EXECTXT, 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). */
324static 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. */
354static 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_(arena_perm_malloc)( VG_AR_EXECTXT,
424                                    sizeof(struct _ExeContext)
425                                    + n_ips * sizeof(Addr),
426                                    vg_alignof(struct _ExeContext));
427
428   for (i = 0; i < n_ips; i++)
429      new_ec->ips[i] = ips[i];
430
431   vg_assert(VG_(is_plausible_ECU)(ec_next_ecu));
432   new_ec->ecu = ec_next_ecu;
433   ec_next_ecu += 4;
434   if (ec_next_ecu == 0) {
435      /* Urr.  Now we're hosed; we emitted 2^30 ExeContexts already
436         and have run out of numbers.  Not sure what to do. */
437      VG_(core_panic)("m_execontext: more than 2^30 ExeContexts created");
438   }
439
440   new_ec->n_ips = n_ips;
441   new_ec->chain = ec_htab[hash];
442   ec_htab[hash] = new_ec;
443
444   /* Resize the hash table, maybe? */
445   if ( ((ULong)ec_totstored) > ((ULong)ec_htab_size) ) {
446      vg_assert(ec_htab_size_idx >= 0 && ec_htab_size_idx < N_EC_PRIMES);
447      if (ec_htab_size_idx < N_EC_PRIMES-1)
448         resize_ec_htab();
449   }
450
451   return new_ec;
452}
453
454ExeContext* VG_(record_ExeContext)( ThreadId tid, Word first_ip_delta ) {
455   return record_ExeContext_wrk( tid, first_ip_delta,
456                                      False/*!first_ip_only*/ );
457}
458
459ExeContext* VG_(record_depth_1_ExeContext)( ThreadId tid, Word first_ip_delta )
460{
461   return record_ExeContext_wrk( tid, first_ip_delta,
462                                      True/*first_ip_only*/ );
463}
464
465ExeContext* VG_(make_depth_1_ExeContext_from_Addr)( Addr a ) {
466   init_ExeContext_storage();
467   return record_ExeContext_wrk2( &a, 1 );
468}
469
470StackTrace VG_(get_ExeContext_StackTrace) ( ExeContext* e ) {
471   return e->ips;
472}
473
474UInt VG_(get_ECU_from_ExeContext)( ExeContext* e ) {
475   vg_assert(VG_(is_plausible_ECU)(e->ecu));
476   return e->ecu;
477}
478
479Int VG_(get_ExeContext_n_ips)( ExeContext* e ) {
480   vg_assert(e->n_ips >= 1);
481   return e->n_ips;
482}
483
484ExeContext* VG_(get_ExeContext_from_ECU)( UInt ecu )
485{
486   UWord i;
487   ExeContext* ec;
488   vg_assert(VG_(is_plausible_ECU)(ecu));
489   vg_assert(ec_htab_size > 0);
490   for (i = 0; i < ec_htab_size; i++) {
491      for (ec = ec_htab[i]; ec; ec = ec->chain) {
492         if (ec->ecu == ecu)
493            return ec;
494      }
495   }
496   return NULL;
497}
498
499ExeContext* VG_(make_ExeContext_from_StackTrace)( Addr* ips, UInt n_ips )
500{
501   init_ExeContext_storage();
502   return record_ExeContext_wrk2(ips, n_ips);
503}
504
505ExeContext* VG_(null_ExeContext) (void)
506{
507   init_ExeContext_storage();
508   return null_ExeContext;
509}
510
511/*--------------------------------------------------------------------*/
512/*--- end                                           m_execontext.c ---*/
513/*--------------------------------------------------------------------*/
514