sewardj | 267100d | 2005-04-24 12:33:12 +0000 | [diff] [blame] | 1 | |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 2 | /*--------------------------------------------------------------------*/ |
sewardj | 267100d | 2005-04-24 12:33:12 +0000 | [diff] [blame] | 3 | /*--- Store and compare stack backtraces m_execontext.c ---*/ |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 4 | /*--------------------------------------------------------------------*/ |
| 5 | |
| 6 | /* |
| 7 | This file is part of Valgrind, a dynamic binary instrumentation |
| 8 | framework. |
| 9 | |
sewardj | e4b0bf0 | 2006-06-05 23:21:15 +0000 | [diff] [blame] | 10 | Copyright (C) 2000-2006 Julian Seward |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 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 | |
njn | c7561b9 | 2005-06-19 01:24:32 +0000 | [diff] [blame] | 31 | #include "pub_core_basics.h" |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 32 | #include "pub_core_execontext.h" |
njn | 132bfcc | 2005-06-04 19:16:06 +0000 | [diff] [blame] | 33 | #include "pub_core_libcassert.h" |
njn | 24a6efb | 2005-06-20 03:36:51 +0000 | [diff] [blame] | 34 | #include "pub_core_libcprint.h" // For VG_(message)() |
njn | af1d7df | 2005-06-11 01:31:52 +0000 | [diff] [blame] | 35 | #include "pub_core_mallocfree.h" |
njn | 2024234 | 2005-05-16 23:31:24 +0000 | [diff] [blame] | 36 | #include "pub_core_options.h" |
njn | d0d7c1f | 2005-06-21 00:33:19 +0000 | [diff] [blame] | 37 | #include "pub_core_stacktrace.h" |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 38 | |
| 39 | /*------------------------------------------------------------*/ |
| 40 | /*--- Low-level ExeContext storage. ---*/ |
| 41 | /*------------------------------------------------------------*/ |
| 42 | |
sewardj | ef52b9d | 2005-06-28 00:12:31 +0000 | [diff] [blame] | 43 | /* The first 4 IP values are used in comparisons to remove duplicate errors, |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 44 | and for comparing against suppression specifications. The rest are |
| 45 | purely informational (but often important). */ |
| 46 | |
| 47 | struct _ExeContext { |
| 48 | struct _ExeContext * next; |
njn | c0ec8e9 | 2005-12-25 06:34:04 +0000 | [diff] [blame] | 49 | UInt n_ips; |
| 50 | /* Variable-length array. The size is 'n_ips'; at |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 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. */ |
sewardj | 34483bc | 2005-09-28 11:50:20 +0000 | [diff] [blame] | 58 | #define N_EC_LISTS 30011 /*4999*/ /* a prime number */ |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 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 | |
| 63 | static ExeContext* ec_list[N_EC_LISTS]; |
| 64 | |
| 65 | /* Stats only: the number of times the system was searched to locate a |
| 66 | context. */ |
njn | 0fd92f4 | 2005-10-06 03:32:42 +0000 | [diff] [blame] | 67 | static ULong ec_searchreqs; |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 68 | |
| 69 | /* Stats only: the number of full context comparisons done. */ |
njn | 0fd92f4 | 2005-10-06 03:32:42 +0000 | [diff] [blame] | 70 | static ULong ec_searchcmps; |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 71 | |
| 72 | /* Stats only: total number of stored contexts. */ |
njn | 0fd92f4 | 2005-10-06 03:32:42 +0000 | [diff] [blame] | 73 | static ULong ec_totstored; |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 74 | |
| 75 | /* Number of 2, 4 and (fast) full cmps done. */ |
njn | 0fd92f4 | 2005-10-06 03:32:42 +0000 | [diff] [blame] | 76 | static ULong ec_cmp2s; |
| 77 | static ULong ec_cmp4s; |
| 78 | static ULong ec_cmpAlls; |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 79 | |
| 80 | |
| 81 | /*------------------------------------------------------------*/ |
| 82 | /*--- Exported functions. ---*/ |
| 83 | /*------------------------------------------------------------*/ |
| 84 | |
| 85 | |
| 86 | /* Initialise this subsystem. */ |
| 87 | static 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. */ |
| 106 | void VG_(print_ExeContext_stats) ( void ) |
| 107 | { |
| 108 | init_ExeContext_storage(); |
| 109 | VG_(message)(Vg_DebugMsg, |
njn | 0fd92f4 | 2005-10-06 03:32:42 +0000 | [diff] [blame] | 110 | " exectx: %,lu lists, %,llu contexts (avg %,llu per list)", |
| 111 | N_EC_LISTS, ec_totstored, ec_totstored / N_EC_LISTS |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 112 | ); |
| 113 | VG_(message)(Vg_DebugMsg, |
njn | 0fd92f4 | 2005-10-06 03:32:42 +0000 | [diff] [blame] | 114 | " exectx: %,llu searches, %,llu full compares (%,llu per 1000)", |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 115 | ec_searchreqs, ec_searchcmps, |
| 116 | ec_searchreqs == 0 |
njn | 0fd92f4 | 2005-10-06 03:32:42 +0000 | [diff] [blame] | 117 | ? 0L |
| 118 | : ( (ec_searchcmps * 1000) / ec_searchreqs ) |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 119 | ); |
| 120 | VG_(message)(Vg_DebugMsg, |
njn | 0fd92f4 | 2005-10-06 03:32:42 +0000 | [diff] [blame] | 121 | " exectx: %,llu cmp2, %,llu cmp4, %,llu cmpAll", |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 122 | ec_cmp2s, ec_cmp4s, ec_cmpAlls |
| 123 | ); |
| 124 | } |
| 125 | |
| 126 | |
| 127 | /* Print an ExeContext. */ |
| 128 | void VG_(pp_ExeContext) ( ExeContext* ec ) |
| 129 | { |
njn | c0ec8e9 | 2005-12-25 06:34:04 +0000 | [diff] [blame] | 130 | VG_(pp_StackTrace)( ec->ips, ec->n_ips ); |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 131 | } |
| 132 | |
| 133 | |
| 134 | /* Compare two ExeContexts, comparing all callers. */ |
| 135 | Bool VG_(eq_ExeContext) ( VgRes res, ExeContext* e1, ExeContext* e2 ) |
| 136 | { |
njn | c0ec8e9 | 2005-12-25 06:34:04 +0000 | [diff] [blame] | 137 | Int i; |
| 138 | |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 139 | if (e1 == NULL || e2 == NULL) |
| 140 | return False; |
njn | c0ec8e9 | 2005-12-25 06:34:04 +0000 | [diff] [blame] | 141 | |
| 142 | // Must be at least one address in each trace. |
| 143 | tl_assert(e1->n_ips >= 1 && e2->n_ips >= 1); |
| 144 | |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 145 | switch (res) { |
| 146 | case Vg_LowRes: |
| 147 | /* Just compare the top two callers. */ |
| 148 | ec_cmp2s++; |
njn | c0ec8e9 | 2005-12-25 06:34:04 +0000 | [diff] [blame] | 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 | } |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 155 | return True; |
| 156 | |
| 157 | case Vg_MedRes: |
| 158 | /* Just compare the top four callers. */ |
| 159 | ec_cmp4s++; |
njn | c0ec8e9 | 2005-12-25 06:34:04 +0000 | [diff] [blame] | 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 | } |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 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 | */ |
sewardj | bb2e09f | 2006-10-24 21:43:38 +0000 | [diff] [blame^] | 188 | static inline UWord ROLW ( UWord w, Int n ) |
| 189 | { |
| 190 | Int bpw = 8 * sizeof(UWord); |
| 191 | w = (w << n) | (w >> (bpw-n)); |
| 192 | return w; |
| 193 | } |
| 194 | |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 195 | ExeContext* VG_(record_ExeContext) ( ThreadId tid ) |
| 196 | { |
| 197 | Int i; |
| 198 | Addr ips[VG_DEEPEST_BACKTRACE]; |
| 199 | Bool same; |
| 200 | UWord hash; |
| 201 | ExeContext* new_ec; |
| 202 | ExeContext* list; |
njn | c0ec8e9 | 2005-12-25 06:34:04 +0000 | [diff] [blame] | 203 | UInt n_ips; |
sewardj | bb2e09f | 2006-10-24 21:43:38 +0000 | [diff] [blame^] | 204 | ExeContext *prev2, *prev; |
| 205 | |
| 206 | static UInt ctr = 0; |
| 207 | |
| 208 | vg_assert(sizeof(void*) == sizeof(UWord)); |
| 209 | vg_assert(sizeof(void*) == sizeof(Addr)); |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 210 | |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 211 | init_ExeContext_storage(); |
njn | c0ec8e9 | 2005-12-25 06:34:04 +0000 | [diff] [blame] | 212 | vg_assert(VG_(clo_backtrace_size) >= 1 && |
| 213 | VG_(clo_backtrace_size) <= VG_DEEPEST_BACKTRACE); |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 214 | |
njn | c0ec8e9 | 2005-12-25 06:34:04 +0000 | [diff] [blame] | 215 | n_ips = VG_(get_StackTrace)( tid, ips, VG_(clo_backtrace_size) ); |
| 216 | tl_assert(n_ips >= 1); |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 217 | |
| 218 | /* Now figure out if we've seen this one before. First hash it so |
| 219 | as to determine the list number. */ |
| 220 | |
| 221 | hash = 0; |
njn | c0ec8e9 | 2005-12-25 06:34:04 +0000 | [diff] [blame] | 222 | for (i = 0; i < n_ips; i++) { |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 223 | hash ^= ips[i]; |
sewardj | bb2e09f | 2006-10-24 21:43:38 +0000 | [diff] [blame^] | 224 | hash = ROLW(hash, 19); |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 225 | } |
sewardj | bb2e09f | 2006-10-24 21:43:38 +0000 | [diff] [blame^] | 226 | if (0) VG_(printf)("hash 0x%lx ", hash); |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 227 | hash = hash % N_EC_LISTS; |
sewardj | bb2e09f | 2006-10-24 21:43:38 +0000 | [diff] [blame^] | 228 | if (0) VG_(printf)("%lu\n", hash); |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 229 | |
| 230 | /* And (the expensive bit) look a matching entry in the list. */ |
| 231 | |
| 232 | ec_searchreqs++; |
| 233 | |
sewardj | bb2e09f | 2006-10-24 21:43:38 +0000 | [diff] [blame^] | 234 | prev2 = NULL; |
| 235 | prev = NULL; |
| 236 | list = ec_list[hash]; |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 237 | |
| 238 | while (True) { |
| 239 | if (list == NULL) break; |
| 240 | ec_searchcmps++; |
| 241 | same = True; |
njn | c0ec8e9 | 2005-12-25 06:34:04 +0000 | [diff] [blame] | 242 | for (i = 0; i < n_ips; i++) { |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 243 | if (list->ips[i] != ips[i]) { |
| 244 | same = False; |
| 245 | break; |
| 246 | } |
| 247 | } |
| 248 | if (same) break; |
sewardj | bb2e09f | 2006-10-24 21:43:38 +0000 | [diff] [blame^] | 249 | prev2 = prev; |
| 250 | prev = list; |
| 251 | list = list->next; |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 252 | } |
| 253 | |
| 254 | if (list != NULL) { |
sewardj | bb2e09f | 2006-10-24 21:43:38 +0000 | [diff] [blame^] | 255 | /* Yay! We found it. Once every 8 searches, move it one step |
| 256 | closer to the start of the list to make future searches |
| 257 | cheaper. */ |
| 258 | if (prev2 && prev && 0 == ((ctr++) & 7)) { |
| 259 | vg_assert(prev2->next == prev); |
| 260 | vg_assert(prev->next == list); |
| 261 | prev2->next = list; |
| 262 | prev->next = list->next; |
| 263 | list->next = prev; |
| 264 | } |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 265 | return list; |
| 266 | } |
| 267 | |
| 268 | /* Bummer. We have to allocate a new context record. */ |
| 269 | ec_totstored++; |
| 270 | |
| 271 | new_ec = VG_(arena_malloc)( VG_AR_EXECTXT, |
njn | c0ec8e9 | 2005-12-25 06:34:04 +0000 | [diff] [blame] | 272 | sizeof(struct _ExeContext) |
| 273 | + n_ips * sizeof(Addr) ); |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 274 | |
njn | c0ec8e9 | 2005-12-25 06:34:04 +0000 | [diff] [blame] | 275 | for (i = 0; i < n_ips; i++) |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 276 | new_ec->ips[i] = ips[i]; |
| 277 | |
njn | c0ec8e9 | 2005-12-25 06:34:04 +0000 | [diff] [blame] | 278 | new_ec->n_ips = n_ips; |
| 279 | new_ec->next = ec_list[hash]; |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 280 | ec_list[hash] = new_ec; |
| 281 | |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 282 | return new_ec; |
| 283 | } |
| 284 | |
| 285 | StackTrace VG_(extract_StackTrace) ( ExeContext* e ) |
| 286 | { |
| 287 | return e->ips; |
| 288 | } |
| 289 | |
| 290 | /*--------------------------------------------------------------------*/ |
sewardj | 267100d | 2005-04-24 12:33:12 +0000 | [diff] [blame] | 291 | /*--- end m_execontext.c ---*/ |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 292 | /*--------------------------------------------------------------------*/ |