m_execontext.c revision e4b0bf07b0ee0a18eacc5aba91686ab5fc1d327b 
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-2006 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_execontext.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
39/*------------------------------------------------------------*/
40/*--- Low-level ExeContext storage.                        ---*/
41/*------------------------------------------------------------*/
42
43/* The first 4 IP values are used in comparisons to remove duplicate errors,
44   and for comparing against suppression specifications.  The rest are
45   purely informational (but often important). */
46
47struct _ExeContext {
48   struct _ExeContext * next;
49   UInt   n_ips;
50   /* Variable-length array.  The size is 'n_ips'; at
51      least 1, at most VG_DEEPEST_BACKTRACE.  [0] is the current IP,
52      [1] is its caller, [2] is the caller of [1], etc. */
53   Addr ips[0];
54};
55
56/* Number of lists in which we keep track of ExeContexts.  Should be
57   prime. */
58#define N_EC_LISTS 30011 /*4999*/ /* a prime number */
59
60/* The idea is only to ever store any one context once, so as to save
61   space and make exact comparisons faster. */
62
63static ExeContext* ec_list[N_EC_LISTS];
64
65/* Stats only: the number of times the system was searched to locate a
66   context. */
67static ULong ec_searchreqs;
68
69/* Stats only: the number of full context comparisons done. */
70static ULong ec_searchcmps;
71
72/* Stats only: total number of stored contexts. */
73static ULong ec_totstored;
74
75/* Number of 2, 4 and (fast) full cmps done. */
76static ULong ec_cmp2s;
77static ULong ec_cmp4s;
78static ULong ec_cmpAlls;
79
80
81/*------------------------------------------------------------*/
82/*--- Exported functions.                                  ---*/
83/*------------------------------------------------------------*/
84
85
86/* Initialise this subsystem. */
87static void init_ExeContext_storage ( void )
88{
89   Int i;
90   static Bool init_done = False;
91   if (init_done)
92      return;
93   ec_searchreqs = 0;
94   ec_searchcmps = 0;
95   ec_totstored = 0;
96   ec_cmp2s = 0;
97   ec_cmp4s = 0;
98   ec_cmpAlls = 0;
99   for (i = 0; i < N_EC_LISTS; i++)
100      ec_list[i] = NULL;
101   init_done = True;
102}
103
104
105/* Print stats. */
106void VG_(print_ExeContext_stats) ( void )
107{
108   init_ExeContext_storage();
109   VG_(message)(Vg_DebugMsg,
110      "   exectx: %,lu lists, %,llu contexts (avg %,llu per list)",
111      N_EC_LISTS, ec_totstored, ec_totstored / N_EC_LISTS
112   );
113   VG_(message)(Vg_DebugMsg,
114      "   exectx: %,llu searches, %,llu full compares (%,llu per 1000)",
115      ec_searchreqs, ec_searchcmps,
116      ec_searchreqs == 0
117         ? 0L
118         : ( (ec_searchcmps * 1000) / ec_searchreqs )
119   );
120   VG_(message)(Vg_DebugMsg,
121      "   exectx: %,llu cmp2, %,llu cmp4, %,llu cmpAll",
122      ec_cmp2s, ec_cmp4s, ec_cmpAlls
123   );
124}
125
126
127/* Print an ExeContext. */
128void VG_(pp_ExeContext) ( ExeContext* ec )
129{
130   VG_(pp_StackTrace)( ec->ips, ec->n_ips );
131}
132
133
134/* Compare two ExeContexts, comparing all callers. */
135Bool VG_(eq_ExeContext) ( VgRes res, ExeContext* e1, ExeContext* e2 )
136{
137   Int i;
138
139   if (e1 == NULL || e2 == NULL)
140      return False;
141
142   // Must be at least one address in each trace.
143   tl_assert(e1->n_ips >= 1 && e2->n_ips >= 1);
144
145   switch (res) {
146   case Vg_LowRes:
147      /* Just compare the top two callers. */
148      ec_cmp2s++;
149      for (i = 0; i < 2; i++) {
150         if ( (e1->n_ips <= i) &&  (e2->n_ips <= i)) return True;
151         if ( (e1->n_ips <= i) && !(e2->n_ips <= i)) return False;
152         if (!(e1->n_ips <= i) &&  (e2->n_ips <= i)) return False;
153         if (e1->ips[i] != e2->ips[i])               return False;
154      }
155      return True;
156
157   case Vg_MedRes:
158      /* Just compare the top four callers. */
159      ec_cmp4s++;
160      for (i = 0; i < 4; i++) {
161         if ( (e1->n_ips <= i) &&  (e2->n_ips <= i)) return True;
162         if ( (e1->n_ips <= i) && !(e2->n_ips <= i)) return False;
163         if (!(e1->n_ips <= i) &&  (e2->n_ips <= i)) return False;
164         if (e1->ips[i] != e2->ips[i])               return False;
165      }
166      return True;
167
168   case Vg_HighRes:
169      ec_cmpAlls++;
170      /* Compare them all -- just do pointer comparison. */
171      if (e1 != e2) return False;
172      return True;
173
174   default:
175      VG_(core_panic)("VG_(eq_ExeContext): unrecognised VgRes");
176   }
177}
178
179/* This guy is the head honcho here.  Take a snapshot of the client's
180   stack.  Search our collection of ExeContexts to see if we already
181   have it, and if not, allocate a new one.  Either way, return a
182   pointer to the context.  If there is a matching context we
183   guarantee to not allocate a new one.  Thus we never store
184   duplicates, and so exact equality can be quickly done as equality
185   on the returned ExeContext* values themselves.  Inspired by Hugs's
186   Text type.
187*/
188ExeContext* VG_(record_ExeContext) ( ThreadId tid )
189{
190   Int         i;
191   Addr        ips[VG_DEEPEST_BACKTRACE];
192   Bool        same;
193   UWord       hash;
194   ExeContext* new_ec;
195   ExeContext* list;
196   UInt        n_ips;
197
198   init_ExeContext_storage();
199   vg_assert(VG_(clo_backtrace_size) >= 1 &&
200             VG_(clo_backtrace_size) <= VG_DEEPEST_BACKTRACE);
201
202   n_ips = VG_(get_StackTrace)( tid, ips, VG_(clo_backtrace_size) );
203   tl_assert(n_ips >= 1);
204
205   /* Now figure out if we've seen this one before.  First hash it so
206      as to determine the list number. */
207
208   hash = 0;
209   for (i = 0; i < n_ips; i++) {
210      hash ^= ips[i];
211      hash = (hash << 29) | (hash >> 3);
212   }
213   hash = hash % N_EC_LISTS;
214
215   /* And (the expensive bit) look a matching entry in the list. */
216
217   ec_searchreqs++;
218
219   list = ec_list[hash];
220
221   while (True) {
222      if (list == NULL) break;
223      ec_searchcmps++;
224      same = True;
225      for (i = 0; i < n_ips; i++) {
226         if (list->ips[i] != ips[i]) {
227            same = False;
228            break;
229         }
230      }
231      if (same) break;
232      list = list->next;
233   }
234
235   if (list != NULL) {
236      /* Yay!  We found it.  */
237      return list;
238   }
239
240   /* Bummer.  We have to allocate a new context record. */
241   ec_totstored++;
242
243   new_ec = VG_(arena_malloc)( VG_AR_EXECTXT,
244                               sizeof(struct _ExeContext)
245                               + n_ips * sizeof(Addr) );
246
247   for (i = 0; i < n_ips; i++)
248      new_ec->ips[i] = ips[i];
249
250   new_ec->n_ips = n_ips;
251   new_ec->next  = ec_list[hash];
252   ec_list[hash] = new_ec;
253
254   return new_ec;
255}
256
257StackTrace VG_(extract_StackTrace) ( ExeContext* e )
258{
259   return e->ips;
260}
261
262/*--------------------------------------------------------------------*/
263/*--- end                                           m_execontext.c ---*/
264/*--------------------------------------------------------------------*/
265