m_execontext.c revision 9877e9b983797707c37bbf01bba491e894073617 
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-2007 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_execontext.h"    // self
34#include "pub_core_libcassert.h"
35#include "pub_core_libcprint.h"     // For VG_(message)()
36#include "pub_core_mallocfree.h"
37#include "pub_core_options.h"
38#include "pub_core_stacktrace.h"
39
40/*------------------------------------------------------------*/
41/*--- Low-level ExeContext storage.                        ---*/
42/*------------------------------------------------------------*/
43
44/* The first 4 IP values are used in comparisons to remove duplicate
45   errors, and for comparing against suppression specifications.  The
46   rest are purely informational (but often important).
47
48   The contexts are stored in a traditional chained hash table, so as
49   to allow quick determination of whether a new context already
50   exists.  The hash table starts small and expands dynamically, so as
51   to keep the load factor below 1.0.
52
53   The idea is only to ever store any one context once, so as to save
54   space and make exact comparisons faster. */
55
56
57/* Primes for the hash table */
58
59#define N_EC_PRIMES 18
60
61static SizeT ec_primes[N_EC_PRIMES] = {
62         769UL,         1543UL,         3079UL,          6151UL,
63       12289UL,        24593UL,        49157UL,         98317UL,
64      196613UL,       393241UL,       786433UL,       1572869UL,
65     3145739UL,      6291469UL,     12582917UL,      25165843UL,
66    50331653UL,    100663319UL
67};
68
69
70/* Each element is present in a hash chain, and also contains a
71   variable length array of guest code addresses (the useful part). */
72
73struct _ExeContext {
74   struct _ExeContext* chain;
75   UInt   n_ips;
76   /* Variable-length array.  The size is 'n_ips'; at
77      least 1, at most VG_DEEPEST_BACKTRACE.  [0] is the current IP,
78      [1] is its caller, [2] is the caller of [1], etc. */
79   Addr ips[0];
80};
81
82
83/* This is the dynamically expanding hash table. */
84static ExeContext** ec_htab; /* array [ec_htab_size] of ExeContext* */
85static SizeT        ec_htab_size;     /* one of the values in ec_primes */
86static SizeT        ec_htab_size_idx; /* 0 .. N_EC_PRIMES-1 */
87
88
89/* Stats only: the number of times the system was searched to locate a
90   context. */
91static ULong ec_searchreqs;
92
93/* Stats only: the number of full context comparisons done. */
94static ULong ec_searchcmps;
95
96/* Stats only: total number of stored contexts. */
97static ULong ec_totstored;
98
99/* Number of 2, 4 and (fast) full cmps done. */
100static ULong ec_cmp2s;
101static ULong ec_cmp4s;
102static ULong ec_cmpAlls;
103
104
105/*------------------------------------------------------------*/
106/*--- Exported functions.                                  ---*/
107/*------------------------------------------------------------*/
108
109
110/* Initialise this subsystem. */
111static void init_ExeContext_storage ( void )
112{
113   Int i;
114   static Bool init_done = False;
115   if (init_done)
116      return;
117   ec_searchreqs = 0;
118   ec_searchcmps = 0;
119   ec_totstored = 0;
120   ec_cmp2s = 0;
121   ec_cmp4s = 0;
122   ec_cmpAlls = 0;
123
124   ec_htab_size_idx = 0;
125   ec_htab_size = ec_primes[ec_htab_size_idx];
126   ec_htab = VG_(arena_malloc)(VG_AR_EXECTXT,
127                               sizeof(ExeContext*) * ec_htab_size);
128   for (i = 0; i < ec_htab_size; i++)
129      ec_htab[i] = NULL;
130
131   init_done = True;
132}
133
134
135/* Print stats. */
136void VG_(print_ExeContext_stats) ( void )
137{
138   init_ExeContext_storage();
139   VG_(message)(Vg_DebugMsg,
140      "   exectx: %,lu lists, %,llu contexts (avg %,llu per list)",
141      ec_htab_size, ec_totstored, ec_totstored / ec_htab_size
142   );
143   VG_(message)(Vg_DebugMsg,
144      "   exectx: %,llu searches, %,llu full compares (%,llu per 1000)",
145      ec_searchreqs, ec_searchcmps,
146      ec_searchreqs == 0
147         ? 0L
148         : ( (ec_searchcmps * 1000) / ec_searchreqs )
149   );
150   VG_(message)(Vg_DebugMsg,
151      "   exectx: %,llu cmp2, %,llu cmp4, %,llu cmpAll",
152      ec_cmp2s, ec_cmp4s, ec_cmpAlls
153   );
154}
155
156
157/* Print an ExeContext. */
158void VG_(pp_ExeContext) ( ExeContext* ec )
159{
160   VG_(pp_StackTrace)( ec->ips, ec->n_ips );
161}
162
163
164/* Compare two ExeContexts, comparing all callers. */
165Bool VG_(eq_ExeContext) ( VgRes res, ExeContext* e1, ExeContext* e2 )
166{
167   Int i;
168
169   if (e1 == NULL || e2 == NULL)
170      return False;
171
172   // Must be at least one address in each trace.
173   tl_assert(e1->n_ips >= 1 && e2->n_ips >= 1);
174
175   switch (res) {
176   case Vg_LowRes:
177      /* Just compare the top two callers. */
178      ec_cmp2s++;
179      for (i = 0; i < 2; i++) {
180         if ( (e1->n_ips <= i) &&  (e2->n_ips <= i)) return True;
181         if ( (e1->n_ips <= i) && !(e2->n_ips <= i)) return False;
182         if (!(e1->n_ips <= i) &&  (e2->n_ips <= i)) return False;
183         if (e1->ips[i] != e2->ips[i])               return False;
184      }
185      return True;
186
187   case Vg_MedRes:
188      /* Just compare the top four callers. */
189      ec_cmp4s++;
190      for (i = 0; i < 4; i++) {
191         if ( (e1->n_ips <= i) &&  (e2->n_ips <= i)) return True;
192         if ( (e1->n_ips <= i) && !(e2->n_ips <= i)) return False;
193         if (!(e1->n_ips <= i) &&  (e2->n_ips <= i)) return False;
194         if (e1->ips[i] != e2->ips[i])               return False;
195      }
196      return True;
197
198   case Vg_HighRes:
199      ec_cmpAlls++;
200      /* Compare them all -- just do pointer comparison. */
201      if (e1 != e2) return False;
202      return True;
203
204   default:
205      VG_(core_panic)("VG_(eq_ExeContext): unrecognised VgRes");
206   }
207}
208
209/* VG_(record_ExeContext) is the head honcho here.  Take a snapshot of
210   the client's stack.  Search our collection of ExeContexts to see if
211   we already have it, and if not, allocate a new one.  Either way,
212   return a pointer to the context.  If there is a matching context we
213   guarantee to not allocate a new one.  Thus we never store
214   duplicates, and so exact equality can be quickly done as equality
215   on the returned ExeContext* values themselves.  Inspired by Hugs's
216   Text type.
217
218   Also checks whether the hash table needs expanding, and expands it
219   if so. */
220
221static inline UWord ROLW ( UWord w, Int n )
222{
223   Int bpw = 8 * sizeof(UWord);
224   w = (w << n) | (w >> (bpw-n));
225   return w;
226}
227
228static UWord calc_hash ( Addr* ips, UInt n_ips, UWord htab_sz )
229{
230   UInt  i;
231   UWord hash = 0;
232   vg_assert(htab_sz > 0);
233   for (i = 0; i < n_ips; i++) {
234      hash ^= ips[i];
235      hash = ROLW(hash, 19);
236   }
237   return hash % htab_sz;
238}
239
240static void resize_ec_htab ( void )
241{
242   SizeT        i;
243   SizeT        new_size;
244   ExeContext** new_ec_htab;
245
246   vg_assert(ec_htab_size_idx >= 0 && ec_htab_size_idx < N_EC_PRIMES);
247   if (ec_htab_size_idx == N_EC_PRIMES-1)
248      return; /* out of primes - can't resize further */
249
250   new_size = ec_primes[ec_htab_size_idx + 1];
251   new_ec_htab = VG_(arena_malloc)(VG_AR_EXECTXT,
252                                   sizeof(ExeContext*) * new_size);
253
254   VG_(debugLog)(
255      1, "execontext",
256         "resizing htab from size %lu to %lu (idx %lu)  Total#ECs=%llu\n",
257         ec_htab_size, new_size, ec_htab_size_idx + 1, ec_totstored);
258
259   for (i = 0; i < new_size; i++)
260      new_ec_htab[i] = NULL;
261
262   for (i = 0; i < ec_htab_size; i++) {
263      ExeContext* cur = ec_htab[i];
264      while (cur) {
265         ExeContext* next = cur->chain;
266         UWord hash = calc_hash(cur->ips, cur->n_ips, new_size);
267         vg_assert(hash < new_size);
268         cur->chain = new_ec_htab[hash];
269         new_ec_htab[hash] = cur;
270         cur = next;
271      }
272   }
273
274   VG_(arena_free)(VG_AR_EXECTXT, ec_htab);
275   ec_htab      = new_ec_htab;
276   ec_htab_size = new_size;
277   ec_htab_size_idx++;
278}
279
280ExeContext* VG_(record_ExeContext) ( ThreadId tid )
281{
282   Int         i;
283   Addr        ips[VG_DEEPEST_BACKTRACE];
284   Bool        same;
285   UWord       hash;
286   ExeContext* new_ec;
287   ExeContext* list;
288   UInt        n_ips;
289   ExeContext  *prev2, *prev;
290
291   static UInt ctr = 0;
292
293   vg_assert(sizeof(void*) == sizeof(UWord));
294   vg_assert(sizeof(void*) == sizeof(Addr));
295
296   init_ExeContext_storage();
297   vg_assert(VG_(clo_backtrace_size) >= 1 &&
298             VG_(clo_backtrace_size) <= VG_DEEPEST_BACKTRACE);
299
300   n_ips = VG_(get_StackTrace)( tid, ips, VG_(clo_backtrace_size) );
301   tl_assert(n_ips >= 1 && n_ips <= VG_(clo_backtrace_size));
302
303   /* Now figure out if we've seen this one before.  First hash it so
304      as to determine the list number. */
305   hash = calc_hash( ips, n_ips, ec_htab_size );
306
307   /* And (the expensive bit) look a for matching entry in the list. */
308
309   ec_searchreqs++;
310
311   prev2 = NULL;
312   prev  = NULL;
313   list  = ec_htab[hash];
314
315   while (True) {
316      if (list == NULL) break;
317      ec_searchcmps++;
318      same = True;
319      for (i = 0; i < n_ips; i++) {
320         if (list->ips[i] != ips[i]) {
321            same = False;
322            break;
323         }
324      }
325      if (same) break;
326      prev2 = prev;
327      prev  = list;
328      list  = list->chain;
329   }
330
331   if (list != NULL) {
332      /* Yay!  We found it.  Once every 8 searches, move it one step
333         closer to the start of the list to make future searches
334         cheaper. */
335      if (0 == ((ctr++) & 7)) {
336         if (prev2 != NULL && prev != NULL) {
337            /* Found at 3rd or later position in the chain. */
338            vg_assert(prev2->chain == prev);
339            vg_assert(prev->chain  == list);
340            prev2->chain = list;
341            prev->chain  = list->chain;
342            list->chain  = prev;
343         }
344         else if (prev2 == NULL && prev != NULL) {
345            /* Found at 2nd position in the chain. */
346            vg_assert(ec_htab[hash] == prev);
347            vg_assert(prev->chain == list);
348            prev->chain = list->chain;
349            list->chain = prev;
350            ec_htab[hash] = list;
351         }
352      }
353      return list;
354   }
355
356   /* Bummer.  We have to allocate a new context record. */
357   ec_totstored++;
358
359   new_ec = VG_(arena_malloc)( VG_AR_EXECTXT,
360                               sizeof(struct _ExeContext)
361                               + n_ips * sizeof(Addr) );
362
363   for (i = 0; i < n_ips; i++)
364      new_ec->ips[i] = ips[i];
365
366   new_ec->n_ips = n_ips;
367   new_ec->chain = ec_htab[hash];
368   ec_htab[hash] = new_ec;
369
370   /* Resize the hash table, maybe? */
371   if ( ((ULong)ec_totstored) > ((ULong)ec_htab_size) ) {
372      vg_assert(ec_htab_size_idx >= 0 && ec_htab_size_idx < N_EC_PRIMES);
373      if (ec_htab_size_idx < N_EC_PRIMES-1)
374         resize_ec_htab();
375   }
376
377   return new_ec;
378}
379
380StackTrace VG_(extract_StackTrace) ( ExeContext* e )
381{
382   return e->ips;
383}
384
385/*--------------------------------------------------------------------*/
386/*--- end                                           m_execontext.c ---*/
387/*--------------------------------------------------------------------*/
388