• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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-2017 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. */
init_ExeContext_storage(void)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. */
VG_(print_ExeContext_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_totstored
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. */
VG_(pp_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. */
VG_(eq_ExeContext)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 
ROLW(UWord w,Int n)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 
calc_hash(const Addr * ips,UInt n_ips,UWord htab_sz)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 
resize_ec_htab(void)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 /* Used by the outer as a marker to separate the frames of the inner valgrind
330    from the frames of the inner guest frames. */
_______VVVVVVVV_appended_inner_guest_stack_VVVVVVVV_______(void)331 static void _______VVVVVVVV_appended_inner_guest_stack_VVVVVVVV_______ (void)
332 {
333 }
334 
335 /* Do the first part of getting a stack trace: actually unwind the
336    stack, and hand the results off to the duplicate-trace-finder
337    (_wrk2). */
record_ExeContext_wrk(ThreadId tid,Word first_ip_delta,Bool first_ip_only)338 static ExeContext* record_ExeContext_wrk ( ThreadId tid, Word first_ip_delta,
339                                            Bool first_ip_only )
340 {
341    Addr ips[VG_(clo_backtrace_size)];
342    UInt n_ips;
343 
344    init_ExeContext_storage();
345 
346    vg_assert(sizeof(void*) == sizeof(UWord));
347    vg_assert(sizeof(void*) == sizeof(Addr));
348 
349    vg_assert(VG_(is_valid_tid)(tid));
350 
351    if (first_ip_only) {
352       n_ips = 1;
353       ips[0] = VG_(get_IP)(tid) + first_ip_delta;
354    } else {
355       n_ips = VG_(get_StackTrace)( tid, ips, VG_(clo_backtrace_size),
356                                    NULL/*array to dump SP values in*/,
357                                    NULL/*array to dump FP values in*/,
358                                    first_ip_delta );
359       if (VG_(inner_threads) != NULL
360           && n_ips + 1 < VG_(clo_backtrace_size)) {
361          /* An inner V has informed us (the outer) of its thread array.
362             Append the inner guest stack trace, if we still have some
363             room in the ips array for the separator and (some) inner
364             guest IPs. */
365          UInt inner_tid;
366 
367          for (inner_tid = 1; inner_tid < VG_N_THREADS; inner_tid++) {
368             if (VG_(threads)[tid].os_state.lwpid
369                 == VG_(inner_threads)[inner_tid].os_state.lwpid) {
370                ThreadState* save_outer_vg_threads = VG_(threads);
371                UInt n_ips_inner_guest;
372 
373                /* Append the separator + the inner guest stack trace. */
374                ips[n_ips] = (Addr)
375                   _______VVVVVVVV_appended_inner_guest_stack_VVVVVVVV_______;
376                n_ips++;
377                VG_(threads) = VG_(inner_threads);
378                n_ips_inner_guest
379                   = VG_(get_StackTrace)( inner_tid,
380                                          ips + n_ips,
381                                          VG_(clo_backtrace_size) - n_ips,
382                                          NULL/*array to dump SP values in*/,
383                                          NULL/*array to dump FP values in*/,
384                                          first_ip_delta );
385                n_ips += n_ips_inner_guest;
386                VG_(threads) = save_outer_vg_threads;
387                break;
388             }
389          }
390       }
391    }
392 
393    return record_ExeContext_wrk2 ( ips, n_ips );
394 }
395 
396 /* Do the second part of getting a stack trace: ips[0 .. n_ips-1]
397    holds a proposed trace.  Find or allocate a suitable ExeContext.
398    Note that callers must have done init_ExeContext_storage() before
399    getting to this point. */
record_ExeContext_wrk2(const Addr * ips,UInt n_ips)400 static ExeContext* record_ExeContext_wrk2 ( const Addr* ips, UInt n_ips )
401 {
402    Int         i;
403    Bool        same;
404    UWord       hash;
405    ExeContext* new_ec;
406    ExeContext* list;
407    ExeContext  *prev2, *prev;
408 
409    static UInt ctr = 0;
410 
411    vg_assert(n_ips >= 1 && n_ips <= VG_(clo_backtrace_size));
412 
413    /* Now figure out if we've seen this one before.  First hash it so
414       as to determine the list number. */
415    hash = calc_hash( ips, n_ips, ec_htab_size );
416 
417    /* And (the expensive bit) look a for matching entry in the list. */
418 
419    ec_searchreqs++;
420 
421    prev2 = NULL;
422    prev  = NULL;
423    list  = ec_htab[hash];
424 
425    while (True) {
426       if (list == NULL) break;
427       ec_searchcmps++;
428       same = list->n_ips == n_ips;
429       for (i = 0; i < n_ips && same ; i++) {
430          same = list->ips[i] == ips[i];
431       }
432       if (same) break;
433       prev2 = prev;
434       prev  = list;
435       list  = list->chain;
436    }
437 
438    if (list != NULL) {
439       /* Yay!  We found it.  Once every 8 searches, move it one step
440          closer to the start of the list to make future searches
441          cheaper. */
442       if (0 == ((ctr++) & 7)) {
443          if (prev2 != NULL && prev != NULL) {
444             /* Found at 3rd or later position in the chain. */
445             vg_assert(prev2->chain == prev);
446             vg_assert(prev->chain  == list);
447             prev2->chain = list;
448             prev->chain  = list->chain;
449             list->chain  = prev;
450          }
451          else if (prev2 == NULL && prev != NULL) {
452             /* Found at 2nd position in the chain. */
453             vg_assert(ec_htab[hash] == prev);
454             vg_assert(prev->chain == list);
455             prev->chain = list->chain;
456             list->chain = prev;
457             ec_htab[hash] = list;
458          }
459       }
460       return list;
461    }
462 
463    /* Bummer.  We have to allocate a new context record. */
464    ec_totstored++;
465 
466    new_ec = VG_(perm_malloc)( sizeof(struct _ExeContext)
467                               + n_ips * sizeof(Addr),
468                               vg_alignof(struct _ExeContext));
469 
470    for (i = 0; i < n_ips; i++)
471       new_ec->ips[i] = ips[i];
472 
473    vg_assert(VG_(is_plausible_ECU)(ec_next_ecu));
474    new_ec->ecu = ec_next_ecu;
475    ec_next_ecu += 4;
476    if (ec_next_ecu == 0) {
477       /* Urr.  Now we're hosed; we emitted 2^30 ExeContexts already
478          and have run out of numbers.  Not sure what to do. */
479       VG_(core_panic)("m_execontext: more than 2^30 ExeContexts created");
480    }
481 
482    new_ec->n_ips = n_ips;
483    new_ec->chain = ec_htab[hash];
484    ec_htab[hash] = new_ec;
485 
486    /* Resize the hash table, maybe? */
487    if ( ((ULong)ec_totstored) > ((ULong)ec_htab_size) ) {
488       vg_assert(ec_htab_size_idx >= 0 && ec_htab_size_idx < N_EC_PRIMES);
489       if (ec_htab_size_idx < N_EC_PRIMES-1)
490          resize_ec_htab();
491    }
492 
493    return new_ec;
494 }
495 
VG_(record_ExeContext)496 ExeContext* VG_(record_ExeContext)( ThreadId tid, Word first_ip_delta ) {
497    return record_ExeContext_wrk( tid, first_ip_delta,
498                                       False/*!first_ip_only*/ );
499 }
500 
VG_(record_depth_1_ExeContext)501 ExeContext* VG_(record_depth_1_ExeContext)( ThreadId tid, Word first_ip_delta )
502 {
503    return record_ExeContext_wrk( tid, first_ip_delta,
504                                       True/*first_ip_only*/ );
505 }
506 
VG_(make_depth_1_ExeContext_from_Addr)507 ExeContext* VG_(make_depth_1_ExeContext_from_Addr)( Addr a ) {
508    init_ExeContext_storage();
509    return record_ExeContext_wrk2( &a, 1 );
510 }
511 
VG_(get_ExeContext_StackTrace)512 StackTrace VG_(get_ExeContext_StackTrace) ( ExeContext* e ) {
513    return e->ips;
514 }
515 
VG_(get_ECU_from_ExeContext)516 UInt VG_(get_ECU_from_ExeContext)( const ExeContext* e ) {
517    vg_assert(VG_(is_plausible_ECU)(e->ecu));
518    return e->ecu;
519 }
520 
VG_(get_ExeContext_n_ips)521 Int VG_(get_ExeContext_n_ips)( const ExeContext* e ) {
522    vg_assert(e->n_ips >= 1);
523    return e->n_ips;
524 }
525 
VG_(get_ExeContext_from_ECU)526 ExeContext* VG_(get_ExeContext_from_ECU)( UInt ecu )
527 {
528    UWord i;
529    ExeContext* ec;
530    vg_assert(VG_(is_plausible_ECU)(ecu));
531    vg_assert(ec_htab_size > 0);
532    for (i = 0; i < ec_htab_size; i++) {
533       for (ec = ec_htab[i]; ec; ec = ec->chain) {
534          if (ec->ecu == ecu)
535             return ec;
536       }
537    }
538    return NULL;
539 }
540 
VG_(make_ExeContext_from_StackTrace)541 ExeContext* VG_(make_ExeContext_from_StackTrace)( const Addr* ips, UInt n_ips )
542 {
543    init_ExeContext_storage();
544    return record_ExeContext_wrk2(ips, n_ips);
545 }
546 
VG_(null_ExeContext)547 ExeContext* VG_(null_ExeContext) (void)
548 {
549    init_ExeContext_storage();
550    return null_ExeContext;
551 }
552 
553 /*--------------------------------------------------------------------*/
554 /*--- end                                           m_execontext.c ---*/
555 /*--------------------------------------------------------------------*/
556