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-2010 Julian Seward 11 jseward (at) 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_threadstate.h" // VG_(is_valid_tid) 41 #include "pub_core_execontext.h" // self 42 43 /*------------------------------------------------------------*/ 44 /*--- Low-level ExeContext storage. ---*/ 45 /*------------------------------------------------------------*/ 46 47 /* The first 4 IP values are used in comparisons to remove duplicate 48 errors, and for comparing against suppression specifications. The 49 rest are purely informational (but often important). 50 51 The contexts are stored in a traditional chained hash table, so as 52 to allow quick determination of whether a new context already 53 exists. The hash table starts small and expands dynamically, so as 54 to keep the load factor below 1.0. 55 56 The idea is only to ever store any one context once, so as to save 57 space and make exact comparisons faster. */ 58 59 60 /* Primes for the hash table */ 61 62 #define N_EC_PRIMES 18 63 64 static SizeT ec_primes[N_EC_PRIMES] = { 65 769UL, 1543UL, 3079UL, 6151UL, 66 12289UL, 24593UL, 49157UL, 98317UL, 67 196613UL, 393241UL, 786433UL, 1572869UL, 68 3145739UL, 6291469UL, 12582917UL, 25165843UL, 69 50331653UL, 100663319UL 70 }; 71 72 73 /* Each element is present in a hash chain, and also contains a 74 variable length array of guest code addresses (the useful part). */ 75 76 struct _ExeContext { 77 struct _ExeContext* chain; 78 /* A 32-bit unsigned integer that uniquely identifies this 79 ExeContext. Memcheck uses these for origin tracking. Values 80 must be nonzero (else Memcheck's origin tracking is hosed), must 81 be a multiple of four, and must be unique. Hence they start at 82 4. */ 83 UInt ecu; 84 /* Variable-length array. The size is 'n_ips'; at 85 least 1, at most VG_DEEPEST_BACKTRACE. [0] is the current IP, 86 [1] is its caller, [2] is the caller of [1], etc. */ 87 UInt n_ips; 88 Addr ips[0]; 89 }; 90 91 92 /* This is the dynamically expanding hash table. */ 93 static ExeContext** ec_htab; /* array [ec_htab_size] of ExeContext* */ 94 static SizeT ec_htab_size; /* one of the values in ec_primes */ 95 static SizeT ec_htab_size_idx; /* 0 .. N_EC_PRIMES-1 */ 96 97 /* ECU serial number */ 98 static UInt ec_next_ecu = 4; /* We must never issue zero */ 99 100 101 /* Stats only: the number of times the system was searched to locate a 102 context. */ 103 static ULong ec_searchreqs; 104 105 /* Stats only: the number of full context comparisons done. */ 106 static ULong ec_searchcmps; 107 108 /* Stats only: total number of stored contexts. */ 109 static ULong ec_totstored; 110 111 /* Number of 2, 4 and (fast) full cmps done. */ 112 static ULong ec_cmp2s; 113 static ULong ec_cmp4s; 114 static ULong ec_cmpAlls; 115 116 117 /*------------------------------------------------------------*/ 118 /*--- Exported functions. ---*/ 119 /*------------------------------------------------------------*/ 120 121 122 /* Initialise this subsystem. */ 123 static void init_ExeContext_storage ( void ) 124 { 125 Int i; 126 static Bool init_done = False; 127 if (LIKELY(init_done)) 128 return; 129 ec_searchreqs = 0; 130 ec_searchcmps = 0; 131 ec_totstored = 0; 132 ec_cmp2s = 0; 133 ec_cmp4s = 0; 134 ec_cmpAlls = 0; 135 136 ec_htab_size_idx = 0; 137 ec_htab_size = ec_primes[ec_htab_size_idx]; 138 ec_htab = VG_(arena_malloc)(VG_AR_EXECTXT, "execontext.iEs1", 139 sizeof(ExeContext*) * ec_htab_size); 140 for (i = 0; i < ec_htab_size; i++) 141 ec_htab[i] = NULL; 142 143 init_done = True; 144 } 145 146 147 /* Print stats. */ 148 void VG_(print_ExeContext_stats) ( void ) 149 { 150 init_ExeContext_storage(); 151 VG_(message)(Vg_DebugMsg, 152 " exectx: %'lu lists, %'llu contexts (avg %'llu per list)\n", 153 ec_htab_size, ec_totstored, ec_totstored / (ULong)ec_htab_size 154 ); 155 VG_(message)(Vg_DebugMsg, 156 " exectx: %'llu searches, %'llu full compares (%'llu per 1000)\n", 157 ec_searchreqs, ec_searchcmps, 158 ec_searchreqs == 0 159 ? 0ULL 160 : ( (ec_searchcmps * 1000ULL) / ec_searchreqs ) 161 ); 162 VG_(message)(Vg_DebugMsg, 163 " exectx: %'llu cmp2, %'llu cmp4, %'llu cmpAll\n", 164 ec_cmp2s, ec_cmp4s, ec_cmpAlls 165 ); 166 } 167 168 169 /* Print an ExeContext. */ 170 void VG_(pp_ExeContext) ( ExeContext* ec ) 171 { 172 VG_(pp_StackTrace)( ec->ips, ec->n_ips ); 173 } 174 175 176 /* Compare two ExeContexts. Number of callers considered depends on res. */ 177 Bool VG_(eq_ExeContext) ( VgRes res, ExeContext* e1, ExeContext* e2 ) 178 { 179 Int i; 180 181 if (e1 == NULL || e2 == NULL) 182 return False; 183 184 // Must be at least one address in each trace. 185 tl_assert(e1->n_ips >= 1 && e2->n_ips >= 1); 186 187 switch (res) { 188 case Vg_LowRes: 189 /* Just compare the top two callers. */ 190 ec_cmp2s++; 191 for (i = 0; i < 2; i++) { 192 if ( (e1->n_ips <= i) && (e2->n_ips <= i)) return True; 193 if ( (e1->n_ips <= i) && !(e2->n_ips <= i)) return False; 194 if (!(e1->n_ips <= i) && (e2->n_ips <= i)) return False; 195 if (e1->ips[i] != e2->ips[i]) return False; 196 } 197 return True; 198 199 case Vg_MedRes: 200 /* Just compare the top four callers. */ 201 ec_cmp4s++; 202 for (i = 0; i < 4; i++) { 203 if ( (e1->n_ips <= i) && (e2->n_ips <= i)) return True; 204 if ( (e1->n_ips <= i) && !(e2->n_ips <= i)) return False; 205 if (!(e1->n_ips <= i) && (e2->n_ips <= i)) return False; 206 if (e1->ips[i] != e2->ips[i]) return False; 207 } 208 return True; 209 210 case Vg_HighRes: 211 ec_cmpAlls++; 212 /* Compare them all -- just do pointer comparison. */ 213 if (e1 != e2) return False; 214 return True; 215 216 default: 217 VG_(core_panic)("VG_(eq_ExeContext): unrecognised VgRes"); 218 } 219 } 220 221 /* VG_(record_ExeContext) is the head honcho here. Take a snapshot of 222 the client's stack. Search our collection of ExeContexts to see if 223 we already have it, and if not, allocate a new one. Either way, 224 return a pointer to the context. If there is a matching context we 225 guarantee to not allocate a new one. Thus we never store 226 duplicates, and so exact equality can be quickly done as equality 227 on the returned ExeContext* values themselves. Inspired by Hugs's 228 Text type. 229 230 Also checks whether the hash table needs expanding, and expands it 231 if so. */ 232 233 static inline UWord ROLW ( UWord w, Int n ) 234 { 235 Int bpw = 8 * sizeof(UWord); 236 w = (w << n) | (w >> (bpw-n)); 237 return w; 238 } 239 240 static UWord calc_hash ( Addr* ips, UInt n_ips, UWord htab_sz ) 241 { 242 UInt i; 243 UWord hash = 0; 244 vg_assert(htab_sz > 0); 245 for (i = 0; i < n_ips; i++) { 246 hash ^= ips[i]; 247 hash = ROLW(hash, 19); 248 } 249 return hash % htab_sz; 250 } 251 252 static void resize_ec_htab ( void ) 253 { 254 SizeT i; 255 SizeT new_size; 256 ExeContext** new_ec_htab; 257 258 vg_assert(ec_htab_size_idx >= 0 && ec_htab_size_idx < N_EC_PRIMES); 259 if (ec_htab_size_idx == N_EC_PRIMES-1) 260 return; /* out of primes - can't resize further */ 261 262 new_size = ec_primes[ec_htab_size_idx + 1]; 263 new_ec_htab = VG_(arena_malloc)(VG_AR_EXECTXT, "execontext.reh1", 264 sizeof(ExeContext*) * new_size); 265 266 VG_(debugLog)( 267 1, "execontext", 268 "resizing htab from size %lu to %lu (idx %lu) Total#ECs=%llu\n", 269 ec_htab_size, new_size, ec_htab_size_idx + 1, ec_totstored); 270 271 for (i = 0; i < new_size; i++) 272 new_ec_htab[i] = NULL; 273 274 for (i = 0; i < ec_htab_size; i++) { 275 ExeContext* cur = ec_htab[i]; 276 while (cur) { 277 ExeContext* next = cur->chain; 278 UWord hash = calc_hash(cur->ips, cur->n_ips, new_size); 279 vg_assert(hash < new_size); 280 cur->chain = new_ec_htab[hash]; 281 new_ec_htab[hash] = cur; 282 cur = next; 283 } 284 } 285 286 VG_(arena_free)(VG_AR_EXECTXT, ec_htab); 287 ec_htab = new_ec_htab; 288 ec_htab_size = new_size; 289 ec_htab_size_idx++; 290 } 291 292 /* Do the first part of getting a stack trace: actually unwind the 293 stack, and hand the results off to the duplicate-trace-finder 294 (_wrk2). */ 295 static ExeContext* record_ExeContext_wrk2 ( Addr* ips, UInt n_ips ); /*fwds*/ 296 static ExeContext* record_ExeContext_wrk ( ThreadId tid, Word first_ip_delta, 297 Bool first_ip_only ) 298 { 299 Addr ips[VG_DEEPEST_BACKTRACE]; 300 UInt n_ips; 301 302 init_ExeContext_storage(); 303 304 vg_assert(sizeof(void*) == sizeof(UWord)); 305 vg_assert(sizeof(void*) == sizeof(Addr)); 306 307 vg_assert(VG_(is_valid_tid)(tid)); 308 309 vg_assert(VG_(clo_backtrace_size) >= 1 && 310 VG_(clo_backtrace_size) <= VG_DEEPEST_BACKTRACE); 311 312 if (first_ip_only) { 313 n_ips = 1; 314 ips[0] = VG_(get_IP)(tid); 315 } else { 316 n_ips = VG_(get_StackTrace)( tid, ips, VG_(clo_backtrace_size), 317 NULL/*array to dump SP values in*/, 318 NULL/*array to dump FP values in*/, 319 first_ip_delta ); 320 } 321 322 return record_ExeContext_wrk2 ( ips, n_ips ); 323 } 324 325 /* Do the second part of getting a stack trace: ips[0 .. n_ips-1] 326 holds a proposed trace. Find or allocate a suitable ExeContext. 327 Note that callers must have done init_ExeContext_storage() before 328 getting to this point. */ 329 static ExeContext* record_ExeContext_wrk2 ( Addr* ips, UInt n_ips ) 330 { 331 Int i; 332 Bool same; 333 UWord hash; 334 ExeContext* new_ec; 335 ExeContext* list; 336 ExeContext *prev2, *prev; 337 338 static UInt ctr = 0; 339 340 tl_assert(n_ips >= 1 && n_ips <= VG_(clo_backtrace_size)); 341 342 /* Now figure out if we've seen this one before. First hash it so 343 as to determine the list number. */ 344 hash = calc_hash( ips, n_ips, ec_htab_size ); 345 346 /* And (the expensive bit) look a for matching entry in the list. */ 347 348 ec_searchreqs++; 349 350 prev2 = NULL; 351 prev = NULL; 352 list = ec_htab[hash]; 353 354 while (True) { 355 if (list == NULL) break; 356 ec_searchcmps++; 357 same = True; 358 for (i = 0; i < n_ips; i++) { 359 if (list->ips[i] != ips[i]) { 360 same = False; 361 break; 362 } 363 } 364 if (same) break; 365 prev2 = prev; 366 prev = list; 367 list = list->chain; 368 } 369 370 if (list != NULL) { 371 /* Yay! We found it. Once every 8 searches, move it one step 372 closer to the start of the list to make future searches 373 cheaper. */ 374 if (0 == ((ctr++) & 7)) { 375 if (prev2 != NULL && prev != NULL) { 376 /* Found at 3rd or later position in the chain. */ 377 vg_assert(prev2->chain == prev); 378 vg_assert(prev->chain == list); 379 prev2->chain = list; 380 prev->chain = list->chain; 381 list->chain = prev; 382 } 383 else if (prev2 == NULL && prev != NULL) { 384 /* Found at 2nd position in the chain. */ 385 vg_assert(ec_htab[hash] == prev); 386 vg_assert(prev->chain == list); 387 prev->chain = list->chain; 388 list->chain = prev; 389 ec_htab[hash] = list; 390 } 391 } 392 return list; 393 } 394 395 /* Bummer. We have to allocate a new context record. */ 396 ec_totstored++; 397 398 new_ec = VG_(arena_malloc)( VG_AR_EXECTXT, "execontext.rEw2.2", 399 sizeof(struct _ExeContext) 400 + n_ips * sizeof(Addr) ); 401 402 for (i = 0; i < n_ips; i++) 403 new_ec->ips[i] = ips[i]; 404 405 vg_assert(VG_(is_plausible_ECU)(ec_next_ecu)); 406 new_ec->ecu = ec_next_ecu; 407 ec_next_ecu += 4; 408 if (ec_next_ecu == 0) { 409 /* Urr. Now we're hosed; we emitted 2^30 ExeContexts already 410 and have run out of numbers. Not sure what to do. */ 411 VG_(core_panic)("m_execontext: more than 2^30 ExeContexts created"); 412 } 413 414 new_ec->n_ips = n_ips; 415 new_ec->chain = ec_htab[hash]; 416 ec_htab[hash] = new_ec; 417 418 /* Resize the hash table, maybe? */ 419 if ( ((ULong)ec_totstored) > ((ULong)ec_htab_size) ) { 420 vg_assert(ec_htab_size_idx >= 0 && ec_htab_size_idx < N_EC_PRIMES); 421 if (ec_htab_size_idx < N_EC_PRIMES-1) 422 resize_ec_htab(); 423 } 424 425 return new_ec; 426 } 427 428 ExeContext* VG_(record_ExeContext)( ThreadId tid, Word first_ip_delta ) { 429 return record_ExeContext_wrk( tid, first_ip_delta, 430 False/*!first_ip_only*/ ); 431 } 432 433 ExeContext* VG_(record_depth_1_ExeContext)( ThreadId tid ) { 434 return record_ExeContext_wrk( tid, 0/*first_ip_delta*/, 435 True/*first_ip_only*/ ); 436 } 437 438 ExeContext* VG_(make_depth_1_ExeContext_from_Addr)( Addr a ) { 439 init_ExeContext_storage(); 440 return record_ExeContext_wrk2( &a, 1 ); 441 } 442 443 StackTrace VG_(get_ExeContext_StackTrace) ( ExeContext* e ) { 444 return e->ips; 445 } 446 447 UInt VG_(get_ECU_from_ExeContext)( ExeContext* e ) { 448 vg_assert(VG_(is_plausible_ECU)(e->ecu)); 449 return e->ecu; 450 } 451 452 Int VG_(get_ExeContext_n_ips)( ExeContext* e ) { 453 vg_assert(e->n_ips >= 1); 454 return e->n_ips; 455 } 456 457 ExeContext* VG_(get_ExeContext_from_ECU)( UInt ecu ) 458 { 459 UWord i; 460 ExeContext* ec; 461 vg_assert(VG_(is_plausible_ECU)(ecu)); 462 vg_assert(ec_htab_size > 0); 463 for (i = 0; i < ec_htab_size; i++) { 464 for (ec = ec_htab[i]; ec; ec = ec->chain) { 465 if (ec->ecu == ecu) 466 return ec; 467 } 468 } 469 return NULL; 470 } 471 472 ExeContext* VG_(make_ExeContext_from_StackTrace)( Addr* ips, UInt n_ips ) 473 { 474 return record_ExeContext_wrk2(ips, n_ips); 475 } 476 477 /*--------------------------------------------------------------------*/ 478 /*--- end m_execontext.c ---*/ 479 /*--------------------------------------------------------------------*/ 480
