coregrind/m_execontext.c

   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_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 /*--------------------------------------------------------------------*/