l4/pkg/valgrind/src/valgrind-3.6.0-svn/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-2010 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
  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 /*--------------------------------------------------------------------*/