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