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