sewardj | 267100d | 2005-04-24 12:33:12 +0000 | [diff] [blame] | 1 | |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 2 | /*--------------------------------------------------------------------*/ |
sewardj | 267100d | 2005-04-24 12:33:12 +0000 | [diff] [blame] | 3 | /*--- Store and compare stack backtraces m_execontext.c ---*/ |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 4 | /*--------------------------------------------------------------------*/ |
| 5 | |
| 6 | /* |
| 7 | This file is part of Valgrind, a dynamic binary instrumentation |
| 8 | framework. |
| 9 | |
sewardj | b3a1e4b | 2015-08-21 11:32:26 +0000 | [diff] [blame] | 10 | Copyright (C) 2000-2015 Julian Seward |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 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 | |
njn | c7561b9 | 2005-06-19 01:24:32 +0000 | [diff] [blame] | 31 | #include "pub_core_basics.h" |
sewardj | 9877e9b | 2007-08-23 10:24:30 +0000 | [diff] [blame] | 32 | #include "pub_core_debuglog.h" |
njn | 132bfcc | 2005-06-04 19:16:06 +0000 | [diff] [blame] | 33 | #include "pub_core_libcassert.h" |
njn | 24a6efb | 2005-06-20 03:36:51 +0000 | [diff] [blame] | 34 | #include "pub_core_libcprint.h" // For VG_(message)() |
njn | af1d7df | 2005-06-11 01:31:52 +0000 | [diff] [blame] | 35 | #include "pub_core_mallocfree.h" |
njn | 2024234 | 2005-05-16 23:31:24 +0000 | [diff] [blame] | 36 | #include "pub_core_options.h" |
njn | d0d7c1f | 2005-06-21 00:33:19 +0000 | [diff] [blame] | 37 | #include "pub_core_stacktrace.h" |
sewardj | 3059d27 | 2007-12-21 01:24:59 +0000 | [diff] [blame] | 38 | #include "pub_core_machine.h" // VG_(get_IP) |
sewardj | 3059d27 | 2007-12-21 01:24:59 +0000 | [diff] [blame] | 39 | #include "pub_core_threadstate.h" // VG_(is_valid_tid) |
| 40 | #include "pub_core_execontext.h" // self |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 41 | |
| 42 | /*------------------------------------------------------------*/ |
| 43 | /*--- Low-level ExeContext storage. ---*/ |
| 44 | /*------------------------------------------------------------*/ |
| 45 | |
philippe | 63ea01e | 2013-01-13 15:18:51 +0000 | [diff] [blame] | 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). |
sewardj | 9877e9b | 2007-08-23 10:24:30 +0000 | [diff] [blame] | 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). */ |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 75 | |
| 76 | struct _ExeContext { |
sewardj | 9877e9b | 2007-08-23 10:24:30 +0000 | [diff] [blame] | 77 | struct _ExeContext* chain; |
sewardj | 7cf4e6b | 2008-05-01 20:24:26 +0000 | [diff] [blame] | 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; |
njn | c0ec8e9 | 2005-12-25 06:34:04 +0000 | [diff] [blame] | 84 | /* Variable-length array. The size is 'n_ips'; at |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 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. */ |
sewardj | 7cf4e6b | 2008-05-01 20:24:26 +0000 | [diff] [blame] | 87 | UInt n_ips; |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 88 | Addr ips[0]; |
| 89 | }; |
| 90 | |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 91 | |
sewardj | 9877e9b | 2007-08-23 10:24:30 +0000 | [diff] [blame] | 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 */ |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 96 | |
sewardj | 7cf4e6b | 2008-05-01 20:24:26 +0000 | [diff] [blame] | 97 | /* ECU serial number */ |
| 98 | static UInt ec_next_ecu = 4; /* We must never issue zero */ |
| 99 | |
philippe | 8617b5b | 2013-01-12 19:53:08 +0000 | [diff] [blame] | 100 | static ExeContext* null_ExeContext; |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 101 | |
| 102 | /* Stats only: the number of times the system was searched to locate a |
| 103 | context. */ |
njn | 0fd92f4 | 2005-10-06 03:32:42 +0000 | [diff] [blame] | 104 | static ULong ec_searchreqs; |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 105 | |
| 106 | /* Stats only: the number of full context comparisons done. */ |
njn | 0fd92f4 | 2005-10-06 03:32:42 +0000 | [diff] [blame] | 107 | static ULong ec_searchcmps; |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 108 | |
| 109 | /* Stats only: total number of stored contexts. */ |
njn | 0fd92f4 | 2005-10-06 03:32:42 +0000 | [diff] [blame] | 110 | static ULong ec_totstored; |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 111 | |
| 112 | /* Number of 2, 4 and (fast) full cmps done. */ |
njn | 0fd92f4 | 2005-10-06 03:32:42 +0000 | [diff] [blame] | 113 | static ULong ec_cmp2s; |
| 114 | static ULong ec_cmp4s; |
| 115 | static ULong ec_cmpAlls; |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 116 | |
| 117 | |
| 118 | /*------------------------------------------------------------*/ |
| 119 | /*--- Exported functions. ---*/ |
| 120 | /*------------------------------------------------------------*/ |
| 121 | |
florian | 518850b | 2014-10-22 22:25:30 +0000 | [diff] [blame] | 122 | static ExeContext* record_ExeContext_wrk2 ( const Addr* ips, UInt n_ips ); |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 123 | |
| 124 | /* Initialise this subsystem. */ |
| 125 | static void init_ExeContext_storage ( void ) |
| 126 | { |
| 127 | Int i; |
| 128 | static Bool init_done = False; |
sewardj | 7cf4e6b | 2008-05-01 20:24:26 +0000 | [diff] [blame] | 129 | if (LIKELY(init_done)) |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 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; |
sewardj | 9877e9b | 2007-08-23 10:24:30 +0000 | [diff] [blame] | 137 | |
| 138 | ec_htab_size_idx = 0; |
| 139 | ec_htab_size = ec_primes[ec_htab_size_idx]; |
florian | a2968cc | 2013-09-20 21:34:40 +0000 | [diff] [blame] | 140 | ec_htab = VG_(malloc)("execontext.iEs1", |
| 141 | sizeof(ExeContext*) * ec_htab_size); |
sewardj | 9877e9b | 2007-08-23 10:24:30 +0000 | [diff] [blame] | 142 | for (i = 0; i < ec_htab_size; i++) |
| 143 | ec_htab[i] = NULL; |
| 144 | |
philippe | 8617b5b | 2013-01-12 19:53:08 +0000 | [diff] [blame] | 145 | { |
| 146 | Addr ips[1]; |
| 147 | ips[0] = 0; |
| 148 | null_ExeContext = record_ExeContext_wrk2(ips, 1); |
philippe | 63ea01e | 2013-01-13 15:18:51 +0000 | [diff] [blame] | 149 | // null execontext must be the first one created and get ecu 4. |
| 150 | vg_assert(null_ExeContext->ecu == 4); |
philippe | 8617b5b | 2013-01-12 19:53:08 +0000 | [diff] [blame] | 151 | } |
| 152 | |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 153 | init_done = True; |
| 154 | } |
| 155 | |
| 156 | |
| 157 | /* Print stats. */ |
philippe | f3a6e93 | 2013-01-10 20:42:51 +0000 | [diff] [blame] | 158 | void VG_(print_ExeContext_stats) ( Bool with_stacktraces ) |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 159 | { |
philippe | 24f33d7 | 2015-03-26 22:12:40 +0000 | [diff] [blame] | 160 | Int i; |
| 161 | ULong total_n_ips; |
| 162 | ExeContext* ec; |
| 163 | |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 164 | init_ExeContext_storage(); |
philippe | f3a6e93 | 2013-01-10 20:42:51 +0000 | [diff] [blame] | 165 | |
| 166 | if (with_stacktraces) { |
philippe | f3a6e93 | 2013-01-10 20:42:51 +0000 | [diff] [blame] | 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) { |
philippe | 550c826 | 2013-01-11 23:48:28 +0000 | [diff] [blame] | 170 | VG_(message)(Vg_DebugMsg, " exectx: stacktrace ecu %u n_ips %u\n", |
| 171 | ec->ecu, ec->n_ips); |
philippe | f3a6e93 | 2013-01-10 20:42:51 +0000 | [diff] [blame] | 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 | } |
philippe | 24f33d7 | 2015-03-26 22:12:40 +0000 | [diff] [blame] | 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 | } |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 185 | VG_(message)(Vg_DebugMsg, |
philippe | 24f33d7 | 2015-03-26 22:12:40 +0000 | [diff] [blame] | 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 |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 190 | ); |
| 191 | VG_(message)(Vg_DebugMsg, |
sewardj | 738856f | 2009-07-15 14:48:32 +0000 | [diff] [blame] | 192 | " exectx: %'llu searches, %'llu full compares (%'llu per 1000)\n", |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 193 | ec_searchreqs, ec_searchcmps, |
| 194 | ec_searchreqs == 0 |
sewardj | a8ffda6 | 2008-07-18 18:23:24 +0000 | [diff] [blame] | 195 | ? 0ULL |
| 196 | : ( (ec_searchcmps * 1000ULL) / ec_searchreqs ) |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 197 | ); |
| 198 | VG_(message)(Vg_DebugMsg, |
sewardj | 738856f | 2009-07-15 14:48:32 +0000 | [diff] [blame] | 199 | " exectx: %'llu cmp2, %'llu cmp4, %'llu cmpAll\n", |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 200 | ec_cmp2s, ec_cmp4s, ec_cmpAlls |
| 201 | ); |
| 202 | } |
| 203 | |
| 204 | |
| 205 | /* Print an ExeContext. */ |
| 206 | void VG_(pp_ExeContext) ( ExeContext* ec ) |
| 207 | { |
njn | c0ec8e9 | 2005-12-25 06:34:04 +0000 | [diff] [blame] | 208 | VG_(pp_StackTrace)( ec->ips, ec->n_ips ); |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 209 | } |
| 210 | |
| 211 | |
njn | b7a4e2e | 2009-05-01 00:30:43 +0000 | [diff] [blame] | 212 | /* Compare two ExeContexts. Number of callers considered depends on res. */ |
florian | 518850b | 2014-10-22 22:25:30 +0000 | [diff] [blame] | 213 | Bool VG_(eq_ExeContext) ( VgRes res, const ExeContext* e1, |
| 214 | const ExeContext* e2 ) |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 215 | { |
njn | c0ec8e9 | 2005-12-25 06:34:04 +0000 | [diff] [blame] | 216 | Int i; |
| 217 | |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 218 | if (e1 == NULL || e2 == NULL) |
| 219 | return False; |
njn | c0ec8e9 | 2005-12-25 06:34:04 +0000 | [diff] [blame] | 220 | |
| 221 | // Must be at least one address in each trace. |
florian | e2800c9 | 2014-09-15 20:57:45 +0000 | [diff] [blame] | 222 | vg_assert(e1->n_ips >= 1 && e2->n_ips >= 1); |
njn | c0ec8e9 | 2005-12-25 06:34:04 +0000 | [diff] [blame] | 223 | |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 224 | switch (res) { |
| 225 | case Vg_LowRes: |
| 226 | /* Just compare the top two callers. */ |
| 227 | ec_cmp2s++; |
njn | c0ec8e9 | 2005-12-25 06:34:04 +0000 | [diff] [blame] | 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 | } |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 234 | return True; |
| 235 | |
| 236 | case Vg_MedRes: |
| 237 | /* Just compare the top four callers. */ |
| 238 | ec_cmp4s++; |
njn | c0ec8e9 | 2005-12-25 06:34:04 +0000 | [diff] [blame] | 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 | } |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 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 | |
sewardj | 9877e9b | 2007-08-23 10:24:30 +0000 | [diff] [blame] | 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 |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 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 |
sewardj | 9877e9b | 2007-08-23 10:24:30 +0000 | [diff] [blame] | 265 | Text type. |
| 266 | |
| 267 | Also checks whether the hash table needs expanding, and expands it |
| 268 | if so. */ |
| 269 | |
sewardj | bb2e09f | 2006-10-24 21:43:38 +0000 | [diff] [blame] | 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 | |
florian | 518850b | 2014-10-22 22:25:30 +0000 | [diff] [blame] | 277 | static UWord calc_hash ( const Addr* ips, UInt n_ips, UWord htab_sz ) |
sewardj | 9877e9b | 2007-08-23 10:24:30 +0000 | [diff] [blame] | 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]; |
florian | a2968cc | 2013-09-20 21:34:40 +0000 | [diff] [blame] | 300 | new_ec_htab = VG_(malloc)("execontext.reh1", |
| 301 | sizeof(ExeContext*) * new_size); |
sewardj | 9877e9b | 2007-08-23 10:24:30 +0000 | [diff] [blame] | 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 | |
florian | a2968cc | 2013-09-20 21:34:40 +0000 | [diff] [blame] | 323 | VG_(free)(ec_htab); |
sewardj | 9877e9b | 2007-08-23 10:24:30 +0000 | [diff] [blame] | 324 | ec_htab = new_ec_htab; |
| 325 | ec_htab_size = new_size; |
| 326 | ec_htab_size_idx++; |
| 327 | } |
| 328 | |
sewardj | 7cf4e6b | 2008-05-01 20:24:26 +0000 | [diff] [blame] | 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). */ |
sewardj | 3059d27 | 2007-12-21 01:24:59 +0000 | [diff] [blame] | 332 | static ExeContext* record_ExeContext_wrk ( ThreadId tid, Word first_ip_delta, |
| 333 | Bool first_ip_only ) |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 334 | { |
florian | 7711f9e | 2012-06-29 21:20:52 +0000 | [diff] [blame] | 335 | Addr ips[VG_(clo_backtrace_size)]; |
sewardj | 7cf4e6b | 2008-05-01 20:24:26 +0000 | [diff] [blame] | 336 | UInt n_ips; |
sewardj | bb2e09f | 2006-10-24 21:43:38 +0000 | [diff] [blame] | 337 | |
sewardj | 7cf4e6b | 2008-05-01 20:24:26 +0000 | [diff] [blame] | 338 | init_ExeContext_storage(); |
sewardj | bb2e09f | 2006-10-24 21:43:38 +0000 | [diff] [blame] | 339 | |
| 340 | vg_assert(sizeof(void*) == sizeof(UWord)); |
| 341 | vg_assert(sizeof(void*) == sizeof(Addr)); |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 342 | |
sewardj | 7cf4e6b | 2008-05-01 20:24:26 +0000 | [diff] [blame] | 343 | vg_assert(VG_(is_valid_tid)(tid)); |
| 344 | |
sewardj | 3059d27 | 2007-12-21 01:24:59 +0000 | [diff] [blame] | 345 | if (first_ip_only) { |
sewardj | 3059d27 | 2007-12-21 01:24:59 +0000 | [diff] [blame] | 346 | n_ips = 1; |
florian | 78b83ae | 2012-07-26 02:14:28 +0000 | [diff] [blame] | 347 | ips[0] = VG_(get_IP)(tid) + first_ip_delta; |
sewardj | 3059d27 | 2007-12-21 01:24:59 +0000 | [diff] [blame] | 348 | } else { |
| 349 | n_ips = VG_(get_StackTrace)( tid, ips, VG_(clo_backtrace_size), |
sewardj | b8b79ad | 2008-03-03 01:35:41 +0000 | [diff] [blame] | 350 | NULL/*array to dump SP values in*/, |
| 351 | NULL/*array to dump FP values in*/, |
sewardj | 3059d27 | 2007-12-21 01:24:59 +0000 | [diff] [blame] | 352 | first_ip_delta ); |
| 353 | } |
| 354 | |
njn | 3a4b58f | 2009-05-07 23:08:10 +0000 | [diff] [blame] | 355 | return record_ExeContext_wrk2 ( ips, n_ips ); |
sewardj | 7cf4e6b | 2008-05-01 20:24:26 +0000 | [diff] [blame] | 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. */ |
florian | 518850b | 2014-10-22 22:25:30 +0000 | [diff] [blame] | 362 | static ExeContext* record_ExeContext_wrk2 ( const Addr* ips, UInt n_ips ) |
sewardj | 7cf4e6b | 2008-05-01 20:24:26 +0000 | [diff] [blame] | 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 | |
florian | e2800c9 | 2014-09-15 20:57:45 +0000 | [diff] [blame] | 373 | vg_assert(n_ips >= 1 && n_ips <= VG_(clo_backtrace_size)); |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 374 | |
| 375 | /* Now figure out if we've seen this one before. First hash it so |
| 376 | as to determine the list number. */ |
sewardj | 9877e9b | 2007-08-23 10:24:30 +0000 | [diff] [blame] | 377 | hash = calc_hash( ips, n_ips, ec_htab_size ); |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 378 | |
sewardj | 9877e9b | 2007-08-23 10:24:30 +0000 | [diff] [blame] | 379 | /* And (the expensive bit) look a for matching entry in the list. */ |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 380 | |
| 381 | ec_searchreqs++; |
| 382 | |
sewardj | bb2e09f | 2006-10-24 21:43:38 +0000 | [diff] [blame] | 383 | prev2 = NULL; |
| 384 | prev = NULL; |
sewardj | 9877e9b | 2007-08-23 10:24:30 +0000 | [diff] [blame] | 385 | list = ec_htab[hash]; |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 386 | |
| 387 | while (True) { |
| 388 | if (list == NULL) break; |
| 389 | ec_searchcmps++; |
philippe | da56900 | 2014-06-24 22:13:43 +0000 | [diff] [blame] | 390 | same = list->n_ips == n_ips; |
| 391 | for (i = 0; i < n_ips && same ; i++) { |
| 392 | same = list->ips[i] == ips[i]; |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 393 | } |
| 394 | if (same) break; |
sewardj | bb2e09f | 2006-10-24 21:43:38 +0000 | [diff] [blame] | 395 | prev2 = prev; |
| 396 | prev = list; |
sewardj | 9877e9b | 2007-08-23 10:24:30 +0000 | [diff] [blame] | 397 | list = list->chain; |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 398 | } |
| 399 | |
| 400 | if (list != NULL) { |
sewardj | bb2e09f | 2006-10-24 21:43:38 +0000 | [diff] [blame] | 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. */ |
sewardj | 9877e9b | 2007-08-23 10:24:30 +0000 | [diff] [blame] | 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 | } |
sewardj | bb2e09f | 2006-10-24 21:43:38 +0000 | [diff] [blame] | 421 | } |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 422 | return list; |
| 423 | } |
| 424 | |
| 425 | /* Bummer. We have to allocate a new context record. */ |
| 426 | ec_totstored++; |
| 427 | |
florian | a2968cc | 2013-09-20 21:34:40 +0000 | [diff] [blame] | 428 | new_ec = VG_(perm_malloc)( sizeof(struct _ExeContext) |
| 429 | + n_ips * sizeof(Addr), |
| 430 | vg_alignof(struct _ExeContext)); |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 431 | |
njn | c0ec8e9 | 2005-12-25 06:34:04 +0000 | [diff] [blame] | 432 | for (i = 0; i < n_ips; i++) |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 433 | new_ec->ips[i] = ips[i]; |
| 434 | |
sewardj | 7cf4e6b | 2008-05-01 20:24:26 +0000 | [diff] [blame] | 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 | |
njn | c0ec8e9 | 2005-12-25 06:34:04 +0000 | [diff] [blame] | 444 | new_ec->n_ips = n_ips; |
sewardj | 9877e9b | 2007-08-23 10:24:30 +0000 | [diff] [blame] | 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 | } |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 454 | |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 455 | return new_ec; |
| 456 | } |
| 457 | |
sewardj | 3059d27 | 2007-12-21 01:24:59 +0000 | [diff] [blame] | 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 | |
florian | bb4f5da | 2012-07-23 15:40:41 +0000 | [diff] [blame] | 463 | ExeContext* VG_(record_depth_1_ExeContext)( ThreadId tid, Word first_ip_delta ) |
| 464 | { |
| 465 | return record_ExeContext_wrk( tid, first_ip_delta, |
sewardj | 3059d27 | 2007-12-21 01:24:59 +0000 | [diff] [blame] | 466 | True/*first_ip_only*/ ); |
| 467 | } |
| 468 | |
sewardj | 7cf4e6b | 2008-05-01 20:24:26 +0000 | [diff] [blame] | 469 | ExeContext* VG_(make_depth_1_ExeContext_from_Addr)( Addr a ) { |
| 470 | init_ExeContext_storage(); |
| 471 | return record_ExeContext_wrk2( &a, 1 ); |
| 472 | } |
sewardj | 3059d27 | 2007-12-21 01:24:59 +0000 | [diff] [blame] | 473 | |
sewardj | 7cf4e6b | 2008-05-01 20:24:26 +0000 | [diff] [blame] | 474 | StackTrace VG_(get_ExeContext_StackTrace) ( ExeContext* e ) { |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 475 | return e->ips; |
| 476 | } |
| 477 | |
florian | 518850b | 2014-10-22 22:25:30 +0000 | [diff] [blame] | 478 | UInt VG_(get_ECU_from_ExeContext)( const ExeContext* e ) { |
sewardj | 7cf4e6b | 2008-05-01 20:24:26 +0000 | [diff] [blame] | 479 | vg_assert(VG_(is_plausible_ECU)(e->ecu)); |
| 480 | return e->ecu; |
| 481 | } |
| 482 | |
florian | 518850b | 2014-10-22 22:25:30 +0000 | [diff] [blame] | 483 | Int VG_(get_ExeContext_n_ips)( const ExeContext* e ) { |
sewardj | 7cf4e6b | 2008-05-01 20:24:26 +0000 | [diff] [blame] | 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 | |
florian | 518850b | 2014-10-22 22:25:30 +0000 | [diff] [blame] | 503 | ExeContext* VG_(make_ExeContext_from_StackTrace)( const Addr* ips, UInt n_ips ) |
sewardj | f98e1c0 | 2008-10-25 16:22:41 +0000 | [diff] [blame] | 504 | { |
philippe | 8617b5b | 2013-01-12 19:53:08 +0000 | [diff] [blame] | 505 | init_ExeContext_storage(); |
sewardj | f98e1c0 | 2008-10-25 16:22:41 +0000 | [diff] [blame] | 506 | return record_ExeContext_wrk2(ips, n_ips); |
| 507 | } |
| 508 | |
philippe | 8617b5b | 2013-01-12 19:53:08 +0000 | [diff] [blame] | 509 | ExeContext* VG_(null_ExeContext) (void) |
| 510 | { |
| 511 | init_ExeContext_storage(); |
| 512 | return null_ExeContext; |
| 513 | } |
| 514 | |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 515 | /*--------------------------------------------------------------------*/ |
sewardj | 267100d | 2005-04-24 12:33:12 +0000 | [diff] [blame] | 516 | /*--- end m_execontext.c ---*/ |
njn | d01fef7 | 2005-03-25 23:35:48 +0000 | [diff] [blame] | 517 | /*--------------------------------------------------------------------*/ |