m_execontext.c revision d0d7c1fc4e59b97115620fdae795f1128bda2d31 
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-2005 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_profile.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 do remove duplicate errors,
45   and for comparing against suppression specifications.  The rest are
46   purely informational (but often important). */
47
48struct _ExeContext {
49   struct _ExeContext * next;
50   /* Variable-length array.  The size is VG_(clo_backtrace_size); 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 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 UInt ec_searchreqs;
68
69/* Stats only: the number of full context comparisons done. */
70static UInt ec_searchcmps;
71
72/* Stats only: total number of stored contexts. */
73static UInt ec_totstored;
74
75/* Number of 2, 4 and (fast) full cmps done. */
76static UInt ec_cmp2s;
77static UInt ec_cmp4s;
78static UInt 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: %d lists, %d contexts (avg %d per list)",
111      N_EC_LISTS, ec_totstored,
112      ec_totstored / N_EC_LISTS
113   );
114   VG_(message)(Vg_DebugMsg,
115      "   exectx: %d searches, %d full compares (%d per 1000)",
116      ec_searchreqs, ec_searchcmps,
117      ec_searchreqs == 0
118         ? 0
119         : (UInt)( (((ULong)ec_searchcmps) * 1000)
120           / ((ULong)ec_searchreqs ))
121   );
122   VG_(message)(Vg_DebugMsg,
123      "   exectx: %d cmp2, %d cmp4, %d cmpAll",
124      ec_cmp2s, ec_cmp4s, ec_cmpAlls
125   );
126}
127
128
129/* Print an ExeContext. */
130void VG_(pp_ExeContext) ( ExeContext* ec )
131{
132   VG_(pp_StackTrace)( ec->ips, VG_(clo_backtrace_size) );
133}
134
135
136/* Compare two ExeContexts, comparing all callers. */
137Bool VG_(eq_ExeContext) ( VgRes res, ExeContext* e1, ExeContext* e2 )
138{
139   if (e1 == NULL || e2 == NULL)
140      return False;
141   switch (res) {
142   case Vg_LowRes:
143      /* Just compare the top two callers. */
144      ec_cmp2s++;
145      if (e1->ips[0] != e2->ips[0]) return False;
146
147      if (VG_(clo_backtrace_size) < 2) return True;
148      if (e1->ips[1] != e2->ips[1]) return False;
149      return True;
150
151   case Vg_MedRes:
152      /* Just compare the top four callers. */
153      ec_cmp4s++;
154      if (e1->ips[0] != e2->ips[0]) return False;
155
156      if (VG_(clo_backtrace_size) < 2) return True;
157      if (e1->ips[1] != e2->ips[1]) return False;
158
159      if (VG_(clo_backtrace_size) < 3) return True;
160      if (e1->ips[2] != e2->ips[2]) return False;
161
162      if (VG_(clo_backtrace_size) < 4) return True;
163      if (e1->ips[3] != e2->ips[3]) return False;
164      return True;
165
166   case Vg_HighRes:
167      ec_cmpAlls++;
168      /* Compare them all -- just do pointer comparison. */
169      if (e1 != e2) return False;
170      return True;
171
172   default:
173      VG_(core_panic)("VG_(eq_ExeContext): unrecognised VgRes");
174   }
175}
176
177/* This guy is the head honcho here.  Take a snapshot of the client's
178   stack.  Search our collection of ExeContexts to see if we already
179   have it, and if not, allocate a new one.  Either way, return a
180   pointer to the context.  If there is a matching context we
181   guarantee to not allocate a new one.  Thus we never store
182   duplicates, and so exact equality can be quickly done as equality
183   on the returned ExeContext* values themselves.  Inspired by Hugs's
184   Text type.
185*/
186ExeContext* VG_(record_ExeContext) ( ThreadId tid )
187{
188   Int         i;
189   Addr        ips[VG_DEEPEST_BACKTRACE];
190   Bool        same;
191   UWord       hash;
192   ExeContext* new_ec;
193   ExeContext* list;
194
195   VGP_PUSHCC(VgpExeContext);
196
197   init_ExeContext_storage();
198   vg_assert(VG_(clo_backtrace_size) >= 1
199             && VG_(clo_backtrace_size) <= VG_DEEPEST_BACKTRACE);
200
201   VG_(get_StackTrace)( tid, ips, VG_(clo_backtrace_size) );
202
203   /* Now figure out if we've seen this one before.  First hash it so
204      as to determine the list number. */
205
206   hash = 0;
207   for (i = 0; i < VG_(clo_backtrace_size); i++) {
208      hash ^= ips[i];
209      hash = (hash << 29) | (hash >> 3);
210   }
211   hash = hash % N_EC_LISTS;
212
213   /* And (the expensive bit) look a matching entry in the list. */
214
215   ec_searchreqs++;
216
217   list = ec_list[hash];
218
219   while (True) {
220      if (list == NULL) break;
221      ec_searchcmps++;
222      same = True;
223      for (i = 0; i < VG_(clo_backtrace_size); i++) {
224         if (list->ips[i] != ips[i]) {
225            same = False;
226            break;
227         }
228      }
229      if (same) break;
230      list = list->next;
231   }
232
233   if (list != NULL) {
234      /* Yay!  We found it.  */
235      VGP_POPCC(VgpExeContext);
236      return list;
237   }
238
239   /* Bummer.  We have to allocate a new context record. */
240   ec_totstored++;
241
242   new_ec = VG_(arena_malloc)( VG_AR_EXECTXT,
243                               sizeof(struct _ExeContext *)
244                               + VG_(clo_backtrace_size) * sizeof(Addr) );
245
246   for (i = 0; i < VG_(clo_backtrace_size); i++)
247      new_ec->ips[i] = ips[i];
248
249   new_ec->next = ec_list[hash];
250   ec_list[hash] = new_ec;
251
252   VGP_POPCC(VgpExeContext);
253   return new_ec;
254}
255
256StackTrace VG_(extract_StackTrace) ( ExeContext* e )
257{
258   return e->ips;
259}
260
261/*--------------------------------------------------------------------*/
262/*--- end                                           m_execontext.c ---*/
263/*--------------------------------------------------------------------*/
264