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-2012 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_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 65static 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 77struct _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. */ 94static ExeContext** ec_htab; /* array [ec_htab_size] of ExeContext* */ 95static SizeT ec_htab_size; /* one of the values in ec_primes */ 96static SizeT ec_htab_size_idx; /* 0 .. N_EC_PRIMES-1 */ 97 98/* ECU serial number */ 99static 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. */ 104static ULong ec_searchreqs; 105 106/* Stats only: the number of full context comparisons done. */ 107static ULong ec_searchcmps; 108 109/* Stats only: total number of stored contexts. */ 110static ULong ec_totstored; 111 112/* Number of 2, 4 and (fast) full cmps done. */ 113static ULong ec_cmp2s; 114static ULong ec_cmp4s; 115static ULong ec_cmpAlls; 116 117 118/*------------------------------------------------------------*/ 119/*--- Exported functions. ---*/ 120/*------------------------------------------------------------*/ 121 122 123/* Initialise this subsystem. */ 124static 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. */ 149void 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. */ 171void 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. */ 178Bool 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 234static 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 241static 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 253static 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). */ 296static ExeContext* record_ExeContext_wrk2 ( Addr* ips, UInt n_ips ); /*fwds*/ 297static ExeContext* record_ExeContext_wrk ( ThreadId tid, Word first_ip_delta, 298 Bool first_ip_only ) 299{ 300 Addr ips[VG_(clo_backtrace_size)]; 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 if (first_ip_only) { 311 n_ips = 1; 312 ips[0] = VG_(get_IP)(tid) + first_ip_delta; 313 } else { 314 n_ips = VG_(get_StackTrace)( tid, ips, VG_(clo_backtrace_size), 315 NULL/*array to dump SP values in*/, 316 NULL/*array to dump FP values in*/, 317 first_ip_delta ); 318 } 319 320 return record_ExeContext_wrk2 ( ips, n_ips ); 321} 322 323/* Do the second part of getting a stack trace: ips[0 .. n_ips-1] 324 holds a proposed trace. Find or allocate a suitable ExeContext. 325 Note that callers must have done init_ExeContext_storage() before 326 getting to this point. */ 327static ExeContext* record_ExeContext_wrk2 ( Addr* ips, UInt n_ips ) 328{ 329 Int i; 330 Bool same; 331 UWord hash; 332 ExeContext* new_ec; 333 ExeContext* list; 334 ExeContext *prev2, *prev; 335 336 static UInt ctr = 0; 337 338 tl_assert(n_ips >= 1 && n_ips <= VG_(clo_backtrace_size)); 339 340 /* Now figure out if we've seen this one before. First hash it so 341 as to determine the list number. */ 342 hash = calc_hash( ips, n_ips, ec_htab_size ); 343 344 /* And (the expensive bit) look a for matching entry in the list. */ 345 346 ec_searchreqs++; 347 348 prev2 = NULL; 349 prev = NULL; 350 list = ec_htab[hash]; 351 352 while (True) { 353 if (list == NULL) break; 354 ec_searchcmps++; 355 same = True; 356 for (i = 0; i < n_ips; i++) { 357 if (list->ips[i] != ips[i]) { 358 same = False; 359 break; 360 } 361 } 362 if (same) break; 363 prev2 = prev; 364 prev = list; 365 list = list->chain; 366 } 367 368 if (list != NULL) { 369 /* Yay! We found it. Once every 8 searches, move it one step 370 closer to the start of the list to make future searches 371 cheaper. */ 372 if (0 == ((ctr++) & 7)) { 373 if (prev2 != NULL && prev != NULL) { 374 /* Found at 3rd or later position in the chain. */ 375 vg_assert(prev2->chain == prev); 376 vg_assert(prev->chain == list); 377 prev2->chain = list; 378 prev->chain = list->chain; 379 list->chain = prev; 380 } 381 else if (prev2 == NULL && prev != NULL) { 382 /* Found at 2nd position in the chain. */ 383 vg_assert(ec_htab[hash] == prev); 384 vg_assert(prev->chain == list); 385 prev->chain = list->chain; 386 list->chain = prev; 387 ec_htab[hash] = list; 388 } 389 } 390 return list; 391 } 392 393 /* Bummer. We have to allocate a new context record. */ 394 ec_totstored++; 395 396 new_ec = VG_(arena_malloc)( VG_AR_EXECTXT, "execontext.rEw2.2", 397 sizeof(struct _ExeContext) 398 + n_ips * sizeof(Addr) ); 399 400 for (i = 0; i < n_ips; i++) 401 new_ec->ips[i] = ips[i]; 402 403 vg_assert(VG_(is_plausible_ECU)(ec_next_ecu)); 404 new_ec->ecu = ec_next_ecu; 405 ec_next_ecu += 4; 406 if (ec_next_ecu == 0) { 407 /* Urr. Now we're hosed; we emitted 2^30 ExeContexts already 408 and have run out of numbers. Not sure what to do. */ 409 VG_(core_panic)("m_execontext: more than 2^30 ExeContexts created"); 410 } 411 412 new_ec->n_ips = n_ips; 413 new_ec->chain = ec_htab[hash]; 414 ec_htab[hash] = new_ec; 415 416 /* Resize the hash table, maybe? */ 417 if ( ((ULong)ec_totstored) > ((ULong)ec_htab_size) ) { 418 vg_assert(ec_htab_size_idx >= 0 && ec_htab_size_idx < N_EC_PRIMES); 419 if (ec_htab_size_idx < N_EC_PRIMES-1) 420 resize_ec_htab(); 421 } 422 423 return new_ec; 424} 425 426ExeContext* VG_(record_ExeContext)( ThreadId tid, Word first_ip_delta ) { 427 return record_ExeContext_wrk( tid, first_ip_delta, 428 False/*!first_ip_only*/ ); 429} 430 431ExeContext* VG_(record_depth_1_ExeContext)( ThreadId tid, Word first_ip_delta ) 432{ 433 return record_ExeContext_wrk( tid, first_ip_delta, 434 True/*first_ip_only*/ ); 435} 436 437ExeContext* VG_(make_depth_1_ExeContext_from_Addr)( Addr a ) { 438 init_ExeContext_storage(); 439 return record_ExeContext_wrk2( &a, 1 ); 440} 441 442StackTrace VG_(get_ExeContext_StackTrace) ( ExeContext* e ) { 443 return e->ips; 444} 445 446UInt VG_(get_ECU_from_ExeContext)( ExeContext* e ) { 447 vg_assert(VG_(is_plausible_ECU)(e->ecu)); 448 return e->ecu; 449} 450 451Int VG_(get_ExeContext_n_ips)( ExeContext* e ) { 452 vg_assert(e->n_ips >= 1); 453 return e->n_ips; 454} 455 456ExeContext* VG_(get_ExeContext_from_ECU)( UInt ecu ) 457{ 458 UWord i; 459 ExeContext* ec; 460 vg_assert(VG_(is_plausible_ECU)(ecu)); 461 vg_assert(ec_htab_size > 0); 462 for (i = 0; i < ec_htab_size; i++) { 463 for (ec = ec_htab[i]; ec; ec = ec->chain) { 464 if (ec->ecu == ecu) 465 return ec; 466 } 467 } 468 return NULL; 469} 470 471ExeContext* VG_(make_ExeContext_from_StackTrace)( Addr* ips, UInt n_ips ) 472{ 473 return record_ExeContext_wrk2(ips, n_ips); 474} 475 476/*--------------------------------------------------------------------*/ 477/*--- end m_execontext.c ---*/ 478/*--------------------------------------------------------------------*/ 479