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-2015 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_threadstate.h" // VG_(is_valid_tid) 40 #include "pub_core_execontext.h" // self 41 42 /*------------------------------------------------------------*/ 43 /*--- Low-level ExeContext storage. ---*/ 44 /*------------------------------------------------------------*/ 45 46 /* Depending on VgRes, the first 2, 4 or all IP values are used in 47 comparisons to remove duplicate errors, and for comparing against 48 suppression specifications. If not used in comparison, the rest 49 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 static ExeContext* null_ExeContext; 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 static ExeContext* record_ExeContext_wrk2 ( const Addr* ips, UInt n_ips ); 123 124 /* Initialise this subsystem. */ 125 static void init_ExeContext_storage ( void ) 126 { 127 Int i; 128 static Bool init_done = False; 129 if (LIKELY(init_done)) 130 return; 131 ec_searchreqs = 0; 132 ec_searchcmps = 0; 133 ec_totstored = 0; 134 ec_cmp2s = 0; 135 ec_cmp4s = 0; 136 ec_cmpAlls = 0; 137 138 ec_htab_size_idx = 0; 139 ec_htab_size = ec_primes[ec_htab_size_idx]; 140 ec_htab = VG_(malloc)("execontext.iEs1", 141 sizeof(ExeContext*) * ec_htab_size); 142 for (i = 0; i < ec_htab_size; i++) 143 ec_htab[i] = NULL; 144 145 { 146 Addr ips[1]; 147 ips[0] = 0; 148 null_ExeContext = record_ExeContext_wrk2(ips, 1); 149 // null execontext must be the first one created and get ecu 4. 150 vg_assert(null_ExeContext->ecu == 4); 151 } 152 153 init_done = True; 154 } 155 156 157 /* Print stats. */ 158 void VG_(print_ExeContext_stats) ( Bool with_stacktraces ) 159 { 160 Int i; 161 ULong total_n_ips; 162 ExeContext* ec; 163 164 init_ExeContext_storage(); 165 166 if (with_stacktraces) { 167 VG_(message)(Vg_DebugMsg, " exectx: Printing contexts stacktraces\n"); 168 for (i = 0; i < ec_htab_size; i++) { 169 for (ec = ec_htab[i]; ec; ec = ec->chain) { 170 VG_(message)(Vg_DebugMsg, " exectx: stacktrace ecu %u n_ips %u\n", 171 ec->ecu, ec->n_ips); 172 VG_(pp_StackTrace)( ec->ips, ec->n_ips ); 173 } 174 } 175 VG_(message)(Vg_DebugMsg, 176 " exectx: Printed %'llu contexts stacktraces\n", 177 ec_totstored); 178 } 179 180 total_n_ips = 0; 181 for (i = 0; i < ec_htab_size; i++) { 182 for (ec = ec_htab[i]; ec; ec = ec->chain) 183 total_n_ips += ec->n_ips; 184 } 185 VG_(message)(Vg_DebugMsg, 186 " exectx: %'lu lists, %'llu contexts (avg %3.2f per list)" 187 " (avg %3.2f IP per context)\n", 188 ec_htab_size, ec_totstored, (Double)ec_totstored / (Double)ec_htab_size, 189 (Double)total_n_ips / (Double)ec_htab_size 190 ); 191 VG_(message)(Vg_DebugMsg, 192 " exectx: %'llu searches, %'llu full compares (%'llu per 1000)\n", 193 ec_searchreqs, ec_searchcmps, 194 ec_searchreqs == 0 195 ? 0ULL 196 : ( (ec_searchcmps * 1000ULL) / ec_searchreqs ) 197 ); 198 VG_(message)(Vg_DebugMsg, 199 " exectx: %'llu cmp2, %'llu cmp4, %'llu cmpAll\n", 200 ec_cmp2s, ec_cmp4s, ec_cmpAlls 201 ); 202 } 203 204 205 /* Print an ExeContext. */ 206 void VG_(pp_ExeContext) ( ExeContext* ec ) 207 { 208 VG_(pp_StackTrace)( ec->ips, ec->n_ips ); 209 } 210 211 212 /* Compare two ExeContexts. Number of callers considered depends on res. */ 213 Bool VG_(eq_ExeContext) ( VgRes res, const ExeContext* e1, 214 const ExeContext* e2 ) 215 { 216 Int i; 217 218 if (e1 == NULL || e2 == NULL) 219 return False; 220 221 // Must be at least one address in each trace. 222 vg_assert(e1->n_ips >= 1 && e2->n_ips >= 1); 223 224 switch (res) { 225 case Vg_LowRes: 226 /* Just compare the top two callers. */ 227 ec_cmp2s++; 228 for (i = 0; i < 2; i++) { 229 if ( (e1->n_ips <= i) && (e2->n_ips <= i)) return True; 230 if ( (e1->n_ips <= i) && !(e2->n_ips <= i)) return False; 231 if (!(e1->n_ips <= i) && (e2->n_ips <= i)) return False; 232 if (e1->ips[i] != e2->ips[i]) return False; 233 } 234 return True; 235 236 case Vg_MedRes: 237 /* Just compare the top four callers. */ 238 ec_cmp4s++; 239 for (i = 0; i < 4; i++) { 240 if ( (e1->n_ips <= i) && (e2->n_ips <= i)) return True; 241 if ( (e1->n_ips <= i) && !(e2->n_ips <= i)) return False; 242 if (!(e1->n_ips <= i) && (e2->n_ips <= i)) return False; 243 if (e1->ips[i] != e2->ips[i]) return False; 244 } 245 return True; 246 247 case Vg_HighRes: 248 ec_cmpAlls++; 249 /* Compare them all -- just do pointer comparison. */ 250 if (e1 != e2) return False; 251 return True; 252 253 default: 254 VG_(core_panic)("VG_(eq_ExeContext): unrecognised VgRes"); 255 } 256 } 257 258 /* VG_(record_ExeContext) is the head honcho here. Take a snapshot of 259 the client's stack. Search our collection of ExeContexts to see if 260 we already have it, and if not, allocate a new one. Either way, 261 return a pointer to the context. If there is a matching context we 262 guarantee to not allocate a new one. Thus we never store 263 duplicates, and so exact equality can be quickly done as equality 264 on the returned ExeContext* values themselves. Inspired by Hugs's 265 Text type. 266 267 Also checks whether the hash table needs expanding, and expands it 268 if so. */ 269 270 static inline UWord ROLW ( UWord w, Int n ) 271 { 272 Int bpw = 8 * sizeof(UWord); 273 w = (w << n) | (w >> (bpw-n)); 274 return w; 275 } 276 277 static UWord calc_hash ( const Addr* ips, UInt n_ips, UWord htab_sz ) 278 { 279 UInt i; 280 UWord hash = 0; 281 vg_assert(htab_sz > 0); 282 for (i = 0; i < n_ips; i++) { 283 hash ^= ips[i]; 284 hash = ROLW(hash, 19); 285 } 286 return hash % htab_sz; 287 } 288 289 static void resize_ec_htab ( void ) 290 { 291 SizeT i; 292 SizeT new_size; 293 ExeContext** new_ec_htab; 294 295 vg_assert(ec_htab_size_idx >= 0 && ec_htab_size_idx < N_EC_PRIMES); 296 if (ec_htab_size_idx == N_EC_PRIMES-1) 297 return; /* out of primes - can't resize further */ 298 299 new_size = ec_primes[ec_htab_size_idx + 1]; 300 new_ec_htab = VG_(malloc)("execontext.reh1", 301 sizeof(ExeContext*) * new_size); 302 303 VG_(debugLog)( 304 1, "execontext", 305 "resizing htab from size %lu to %lu (idx %lu) Total#ECs=%llu\n", 306 ec_htab_size, new_size, ec_htab_size_idx + 1, ec_totstored); 307 308 for (i = 0; i < new_size; i++) 309 new_ec_htab[i] = NULL; 310 311 for (i = 0; i < ec_htab_size; i++) { 312 ExeContext* cur = ec_htab[i]; 313 while (cur) { 314 ExeContext* next = cur->chain; 315 UWord hash = calc_hash(cur->ips, cur->n_ips, new_size); 316 vg_assert(hash < new_size); 317 cur->chain = new_ec_htab[hash]; 318 new_ec_htab[hash] = cur; 319 cur = next; 320 } 321 } 322 323 VG_(free)(ec_htab); 324 ec_htab = new_ec_htab; 325 ec_htab_size = new_size; 326 ec_htab_size_idx++; 327 } 328 329 /* Do the first part of getting a stack trace: actually unwind the 330 stack, and hand the results off to the duplicate-trace-finder 331 (_wrk2). */ 332 static ExeContext* record_ExeContext_wrk ( ThreadId tid, Word first_ip_delta, 333 Bool first_ip_only ) 334 { 335 Addr ips[VG_(clo_backtrace_size)]; 336 UInt n_ips; 337 338 init_ExeContext_storage(); 339 340 vg_assert(sizeof(void*) == sizeof(UWord)); 341 vg_assert(sizeof(void*) == sizeof(Addr)); 342 343 vg_assert(VG_(is_valid_tid)(tid)); 344 345 if (first_ip_only) { 346 n_ips = 1; 347 ips[0] = VG_(get_IP)(tid) + first_ip_delta; 348 } else { 349 n_ips = VG_(get_StackTrace)( tid, ips, VG_(clo_backtrace_size), 350 NULL/*array to dump SP values in*/, 351 NULL/*array to dump FP values in*/, 352 first_ip_delta ); 353 } 354 355 return record_ExeContext_wrk2 ( ips, n_ips ); 356 } 357 358 /* Do the second part of getting a stack trace: ips[0 .. n_ips-1] 359 holds a proposed trace. Find or allocate a suitable ExeContext. 360 Note that callers must have done init_ExeContext_storage() before 361 getting to this point. */ 362 static ExeContext* record_ExeContext_wrk2 ( const Addr* ips, UInt n_ips ) 363 { 364 Int i; 365 Bool same; 366 UWord hash; 367 ExeContext* new_ec; 368 ExeContext* list; 369 ExeContext *prev2, *prev; 370 371 static UInt ctr = 0; 372 373 vg_assert(n_ips >= 1 && n_ips <= VG_(clo_backtrace_size)); 374 375 /* Now figure out if we've seen this one before. First hash it so 376 as to determine the list number. */ 377 hash = calc_hash( ips, n_ips, ec_htab_size ); 378 379 /* And (the expensive bit) look a for matching entry in the list. */ 380 381 ec_searchreqs++; 382 383 prev2 = NULL; 384 prev = NULL; 385 list = ec_htab[hash]; 386 387 while (True) { 388 if (list == NULL) break; 389 ec_searchcmps++; 390 same = list->n_ips == n_ips; 391 for (i = 0; i < n_ips && same ; i++) { 392 same = list->ips[i] == ips[i]; 393 } 394 if (same) break; 395 prev2 = prev; 396 prev = list; 397 list = list->chain; 398 } 399 400 if (list != NULL) { 401 /* Yay! We found it. Once every 8 searches, move it one step 402 closer to the start of the list to make future searches 403 cheaper. */ 404 if (0 == ((ctr++) & 7)) { 405 if (prev2 != NULL && prev != NULL) { 406 /* Found at 3rd or later position in the chain. */ 407 vg_assert(prev2->chain == prev); 408 vg_assert(prev->chain == list); 409 prev2->chain = list; 410 prev->chain = list->chain; 411 list->chain = prev; 412 } 413 else if (prev2 == NULL && prev != NULL) { 414 /* Found at 2nd position in the chain. */ 415 vg_assert(ec_htab[hash] == prev); 416 vg_assert(prev->chain == list); 417 prev->chain = list->chain; 418 list->chain = prev; 419 ec_htab[hash] = list; 420 } 421 } 422 return list; 423 } 424 425 /* Bummer. We have to allocate a new context record. */ 426 ec_totstored++; 427 428 new_ec = VG_(perm_malloc)( sizeof(struct _ExeContext) 429 + n_ips * sizeof(Addr), 430 vg_alignof(struct _ExeContext)); 431 432 for (i = 0; i < n_ips; i++) 433 new_ec->ips[i] = ips[i]; 434 435 vg_assert(VG_(is_plausible_ECU)(ec_next_ecu)); 436 new_ec->ecu = ec_next_ecu; 437 ec_next_ecu += 4; 438 if (ec_next_ecu == 0) { 439 /* Urr. Now we're hosed; we emitted 2^30 ExeContexts already 440 and have run out of numbers. Not sure what to do. */ 441 VG_(core_panic)("m_execontext: more than 2^30 ExeContexts created"); 442 } 443 444 new_ec->n_ips = n_ips; 445 new_ec->chain = ec_htab[hash]; 446 ec_htab[hash] = new_ec; 447 448 /* Resize the hash table, maybe? */ 449 if ( ((ULong)ec_totstored) > ((ULong)ec_htab_size) ) { 450 vg_assert(ec_htab_size_idx >= 0 && ec_htab_size_idx < N_EC_PRIMES); 451 if (ec_htab_size_idx < N_EC_PRIMES-1) 452 resize_ec_htab(); 453 } 454 455 return new_ec; 456 } 457 458 ExeContext* VG_(record_ExeContext)( ThreadId tid, Word first_ip_delta ) { 459 return record_ExeContext_wrk( tid, first_ip_delta, 460 False/*!first_ip_only*/ ); 461 } 462 463 ExeContext* VG_(record_depth_1_ExeContext)( ThreadId tid, Word first_ip_delta ) 464 { 465 return record_ExeContext_wrk( tid, first_ip_delta, 466 True/*first_ip_only*/ ); 467 } 468 469 ExeContext* VG_(make_depth_1_ExeContext_from_Addr)( Addr a ) { 470 init_ExeContext_storage(); 471 return record_ExeContext_wrk2( &a, 1 ); 472 } 473 474 StackTrace VG_(get_ExeContext_StackTrace) ( ExeContext* e ) { 475 return e->ips; 476 } 477 478 UInt VG_(get_ECU_from_ExeContext)( const ExeContext* e ) { 479 vg_assert(VG_(is_plausible_ECU)(e->ecu)); 480 return e->ecu; 481 } 482 483 Int VG_(get_ExeContext_n_ips)( const ExeContext* e ) { 484 vg_assert(e->n_ips >= 1); 485 return e->n_ips; 486 } 487 488 ExeContext* VG_(get_ExeContext_from_ECU)( UInt ecu ) 489 { 490 UWord i; 491 ExeContext* ec; 492 vg_assert(VG_(is_plausible_ECU)(ecu)); 493 vg_assert(ec_htab_size > 0); 494 for (i = 0; i < ec_htab_size; i++) { 495 for (ec = ec_htab[i]; ec; ec = ec->chain) { 496 if (ec->ecu == ecu) 497 return ec; 498 } 499 } 500 return NULL; 501 } 502 503 ExeContext* VG_(make_ExeContext_from_StackTrace)( const Addr* ips, UInt n_ips ) 504 { 505 init_ExeContext_storage(); 506 return record_ExeContext_wrk2(ips, n_ips); 507 } 508 509 ExeContext* VG_(null_ExeContext) (void) 510 { 511 init_ExeContext_storage(); 512 return null_ExeContext; 513 } 514 515 /*--------------------------------------------------------------------*/ 516 /*--- end m_execontext.c ---*/ 517 /*--------------------------------------------------------------------*/ 518
