weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 1 | /*--------------------------------------------------------------------*/ |
| 2 | /*--- Callgrind ---*/ |
| 3 | /*--- ct_context.c ---*/ |
| 4 | /*--------------------------------------------------------------------*/ |
| 5 | |
| 6 | /* |
| 7 | This file is part of Callgrind, a Valgrind tool for call tracing. |
| 8 | |
Elliott Hughes | ed39800 | 2017-06-21 14:41:24 -0700 | [diff] [blame] | 9 | Copyright (C) 2002-2017, Josef Weidendorfer (Josef.Weidendorfer@gmx.de) |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 10 | |
| 11 | This program is free software; you can redistribute it and/or |
| 12 | modify it under the terms of the GNU General Public License as |
| 13 | published by the Free Software Foundation; either version 2 of the |
| 14 | License, or (at your option) any later version. |
| 15 | |
| 16 | This program is distributed in the hope that it will be useful, but |
| 17 | WITHOUT ANY WARRANTY; without even the implied warranty of |
| 18 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| 19 | General Public License for more details. |
| 20 | |
| 21 | You should have received a copy of the GNU General Public License |
| 22 | along with this program; if not, write to the Free Software |
| 23 | Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA |
| 24 | 02111-1307, USA. |
| 25 | |
| 26 | The GNU General Public License is contained in the file COPYING. |
| 27 | */ |
| 28 | |
| 29 | #include "global.h" |
| 30 | |
| 31 | |
| 32 | /*------------------------------------------------------------*/ |
| 33 | /*--- Context operations ---*/ |
| 34 | /*------------------------------------------------------------*/ |
| 35 | |
| 36 | #define N_FNSTACK_INITIAL_ENTRIES 500 |
| 37 | #define N_CXT_INITIAL_ENTRIES 2537 |
| 38 | |
| 39 | fn_stack CLG_(current_fn_stack); |
| 40 | |
| 41 | void CLG_(init_fn_stack)(fn_stack* s) |
| 42 | { |
| 43 | CLG_ASSERT(s != 0); |
| 44 | |
| 45 | s->size = N_FNSTACK_INITIAL_ENTRIES; |
sewardj | 9c606bd | 2008-09-18 18:12:50 +0000 | [diff] [blame] | 46 | s->bottom = (fn_node**) CLG_MALLOC("cl.context.ifs.1", |
| 47 | s->size * sizeof(fn_node*)); |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 48 | s->top = s->bottom; |
| 49 | s->bottom[0] = 0; |
| 50 | } |
| 51 | |
| 52 | void CLG_(copy_current_fn_stack)(fn_stack* dst) |
| 53 | { |
| 54 | CLG_ASSERT(dst != 0); |
| 55 | |
| 56 | dst->size = CLG_(current_fn_stack).size; |
| 57 | dst->bottom = CLG_(current_fn_stack).bottom; |
| 58 | dst->top = CLG_(current_fn_stack).top; |
| 59 | } |
| 60 | |
| 61 | void CLG_(set_current_fn_stack)(fn_stack* s) |
| 62 | { |
| 63 | CLG_ASSERT(s != 0); |
| 64 | |
| 65 | CLG_(current_fn_stack).size = s->size; |
| 66 | CLG_(current_fn_stack).bottom = s->bottom; |
| 67 | CLG_(current_fn_stack).top = s->top; |
| 68 | } |
| 69 | |
| 70 | static cxt_hash cxts; |
| 71 | |
| 72 | void CLG_(init_cxt_table)() |
| 73 | { |
| 74 | Int i; |
| 75 | |
| 76 | cxts.size = N_CXT_INITIAL_ENTRIES; |
| 77 | cxts.entries = 0; |
sewardj | 9c606bd | 2008-09-18 18:12:50 +0000 | [diff] [blame] | 78 | cxts.table = (Context**) CLG_MALLOC("cl.context.ict.1", |
| 79 | cxts.size * sizeof(Context*)); |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 80 | |
| 81 | for (i = 0; i < cxts.size; i++) |
| 82 | cxts.table[i] = 0; |
| 83 | } |
| 84 | |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 85 | /* double size of cxt table */ |
| 86 | static void resize_cxt_table(void) |
| 87 | { |
| 88 | UInt i, new_size, conflicts1 = 0, conflicts2 = 0; |
| 89 | Context **new_table, *curr, *next; |
| 90 | UInt new_idx; |
| 91 | |
| 92 | new_size = 2* cxts.size +3; |
sewardj | 9c606bd | 2008-09-18 18:12:50 +0000 | [diff] [blame] | 93 | new_table = (Context**) CLG_MALLOC("cl.context.rct.1", |
| 94 | new_size * sizeof(Context*)); |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 95 | |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 96 | for (i = 0; i < new_size; i++) |
| 97 | new_table[i] = NULL; |
| 98 | |
| 99 | for (i = 0; i < cxts.size; i++) { |
| 100 | if (cxts.table[i] == NULL) continue; |
| 101 | |
| 102 | curr = cxts.table[i]; |
| 103 | while (NULL != curr) { |
| 104 | next = curr->next; |
| 105 | |
| 106 | new_idx = (UInt) (curr->hash % new_size); |
| 107 | |
| 108 | curr->next = new_table[new_idx]; |
| 109 | new_table[new_idx] = curr; |
| 110 | if (curr->next) { |
| 111 | conflicts1++; |
| 112 | if (curr->next->next) |
| 113 | conflicts2++; |
| 114 | } |
| 115 | |
| 116 | curr = next; |
| 117 | } |
| 118 | } |
| 119 | |
| 120 | VG_(free)(cxts.table); |
| 121 | |
| 122 | |
florian | b7876db | 2015-08-05 19:04:51 +0000 | [diff] [blame] | 123 | CLG_DEBUG(0, "Resize Context Hash: %u => %u (entries %u, conflicts %u/%u)\n", |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 124 | cxts.size, new_size, |
| 125 | cxts.entries, conflicts1, conflicts2); |
| 126 | |
| 127 | cxts.size = new_size; |
| 128 | cxts.table = new_table; |
| 129 | CLG_(stat).cxt_hash_resizes++; |
| 130 | } |
| 131 | |
| 132 | __inline__ |
| 133 | static UWord cxt_hash_val(fn_node** fn, UInt size) |
| 134 | { |
| 135 | UWord hash = 0; |
| 136 | UInt count = size; |
| 137 | while(*fn != 0) { |
| 138 | hash = (hash<<7) + (hash>>25) + (UWord)(*fn); |
| 139 | fn--; |
| 140 | count--; |
| 141 | if (count==0) break; |
| 142 | } |
| 143 | return hash; |
| 144 | } |
| 145 | |
| 146 | __inline__ |
| 147 | static Bool is_cxt(UWord hash, fn_node** fn, Context* cxt) |
| 148 | { |
| 149 | int count; |
| 150 | fn_node** cxt_fn; |
| 151 | |
| 152 | if (hash != cxt->hash) return False; |
| 153 | |
| 154 | count = cxt->size; |
| 155 | cxt_fn = &(cxt->fn[0]); |
| 156 | while((*fn != 0) && (count>0)) { |
| 157 | if (*cxt_fn != *fn) return False; |
| 158 | fn--; |
| 159 | cxt_fn++; |
| 160 | count--; |
| 161 | } |
| 162 | return True; |
| 163 | } |
| 164 | |
| 165 | /** |
| 166 | * Allocate new Context structure |
| 167 | */ |
| 168 | static Context* new_cxt(fn_node** fn) |
| 169 | { |
weidendo | 0b23d6e | 2009-06-15 00:16:32 +0000 | [diff] [blame] | 170 | Context* cxt; |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 171 | UInt idx, offset; |
| 172 | UWord hash; |
| 173 | int size, recs; |
| 174 | fn_node* top_fn; |
| 175 | |
| 176 | CLG_ASSERT(fn); |
| 177 | top_fn = *fn; |
| 178 | if (top_fn == 0) return 0; |
| 179 | |
| 180 | size = top_fn->separate_callers +1; |
| 181 | recs = top_fn->separate_recursions; |
| 182 | if (recs<1) recs=1; |
| 183 | |
| 184 | /* check fill degree of context hash table and resize if needed (>80%) */ |
| 185 | cxts.entries++; |
| 186 | if (10 * cxts.entries / cxts.size > 8) |
| 187 | resize_cxt_table(); |
| 188 | |
weidendo | 0b23d6e | 2009-06-15 00:16:32 +0000 | [diff] [blame] | 189 | cxt = (Context*) CLG_MALLOC("cl.context.nc.1", |
sewardj | 9c606bd | 2008-09-18 18:12:50 +0000 | [diff] [blame] | 190 | sizeof(Context)+sizeof(fn_node*)*size); |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 191 | |
| 192 | // hash value calculation similar to cxt_hash_val(), but additionally |
| 193 | // copying function pointers in one run |
| 194 | hash = 0; |
| 195 | offset = 0; |
| 196 | while(*fn != 0) { |
| 197 | hash = (hash<<7) + (hash>>25) + (UWord)(*fn); |
weidendo | 0b23d6e | 2009-06-15 00:16:32 +0000 | [diff] [blame] | 198 | cxt->fn[offset] = *fn; |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 199 | offset++; |
| 200 | fn--; |
| 201 | if (offset >= size) break; |
| 202 | } |
| 203 | if (offset < size) size = offset; |
| 204 | |
weidendo | 0b23d6e | 2009-06-15 00:16:32 +0000 | [diff] [blame] | 205 | cxt->size = size; |
| 206 | cxt->base_number = CLG_(stat).context_counter; |
| 207 | cxt->hash = hash; |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 208 | |
| 209 | CLG_(stat).context_counter += recs; |
| 210 | CLG_(stat).distinct_contexts++; |
| 211 | |
| 212 | /* insert into Context hash table */ |
| 213 | idx = (UInt) (hash % cxts.size); |
weidendo | 0b23d6e | 2009-06-15 00:16:32 +0000 | [diff] [blame] | 214 | cxt->next = cxts.table[idx]; |
| 215 | cxts.table[idx] = cxt; |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 216 | |
| 217 | #if CLG_ENABLE_DEBUG |
| 218 | CLG_DEBUGIF(3) { |
weidendo | 0b23d6e | 2009-06-15 00:16:32 +0000 | [diff] [blame] | 219 | VG_(printf)(" new_cxt ox%p: ", cxt); |
| 220 | CLG_(print_cxt)(12, cxt, 0); |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 221 | } |
| 222 | #endif |
| 223 | |
weidendo | 0b23d6e | 2009-06-15 00:16:32 +0000 | [diff] [blame] | 224 | return cxt; |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 225 | } |
| 226 | |
| 227 | /* get the Context structure for current context */ |
| 228 | Context* CLG_(get_cxt)(fn_node** fn) |
| 229 | { |
| 230 | Context* cxt; |
| 231 | UInt size, idx; |
| 232 | UWord hash; |
| 233 | |
| 234 | CLG_ASSERT(fn != 0); |
| 235 | if (*fn == 0) return 0; |
| 236 | size = (*fn)->separate_callers+1; |
| 237 | if (size<=0) { size = -size+1; } |
| 238 | |
florian | b7876db | 2015-08-05 19:04:51 +0000 | [diff] [blame] | 239 | CLG_DEBUG(5, "+ get_cxt(fn '%s'): size %u\n", |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 240 | (*fn)->name, size); |
| 241 | |
| 242 | hash = cxt_hash_val(fn, size); |
| 243 | |
| 244 | if ( ((cxt = (*fn)->last_cxt) != 0) && is_cxt(hash, fn, cxt)) { |
| 245 | CLG_DEBUG(5, "- get_cxt: %p\n", cxt); |
| 246 | return cxt; |
| 247 | } |
| 248 | |
| 249 | CLG_(stat).cxt_lru_misses++; |
| 250 | |
| 251 | idx = (UInt) (hash % cxts.size); |
| 252 | cxt = cxts.table[idx]; |
| 253 | |
| 254 | while(cxt) { |
| 255 | if (is_cxt(hash,fn,cxt)) break; |
| 256 | cxt = cxt->next; |
| 257 | } |
| 258 | |
| 259 | if (!cxt) |
| 260 | cxt = new_cxt(fn); |
| 261 | |
| 262 | (*fn)->last_cxt = cxt; |
| 263 | |
| 264 | CLG_DEBUG(5, "- get_cxt: %p\n", cxt); |
| 265 | |
| 266 | return cxt; |
| 267 | } |
| 268 | |
| 269 | |
| 270 | /** |
| 271 | * Change execution context by calling a new function from current context |
weidendo | 6145324 | 2009-07-01 23:56:23 +0000 | [diff] [blame] | 272 | * Pushing 0x0 specifies a marker for a signal handler entry |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 273 | */ |
| 274 | void CLG_(push_cxt)(fn_node* fn) |
| 275 | { |
| 276 | call_stack* cs = &CLG_(current_call_stack); |
| 277 | Int fn_entries; |
| 278 | |
weidendo | f3e0b49 | 2006-09-10 22:34:20 +0000 | [diff] [blame] | 279 | CLG_DEBUG(5, "+ push_cxt(fn '%s'): old ctx %d\n", |
florian | 19f91bb | 2012-11-10 22:29:54 +0000 | [diff] [blame] | 280 | fn ? fn->name : "0x0", |
weidendo | f3e0b49 | 2006-09-10 22:34:20 +0000 | [diff] [blame] | 281 | CLG_(current_state).cxt ? |
florian | b7876db | 2015-08-05 19:04:51 +0000 | [diff] [blame] | 282 | (Int)CLG_(current_state).cxt->base_number : -1); |
weidendo | f3e0b49 | 2006-09-10 22:34:20 +0000 | [diff] [blame] | 283 | |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 284 | /* save old context on stack (even if not changed at all!) */ |
| 285 | CLG_ASSERT(cs->sp < cs->size); |
| 286 | CLG_ASSERT(cs->entry[cs->sp].cxt == 0); |
| 287 | cs->entry[cs->sp].cxt = CLG_(current_state).cxt; |
| 288 | cs->entry[cs->sp].fn_sp = CLG_(current_fn_stack).top - CLG_(current_fn_stack).bottom; |
| 289 | |
weidendo | 6145324 | 2009-07-01 23:56:23 +0000 | [diff] [blame] | 290 | if (fn && (*(CLG_(current_fn_stack).top) == fn)) return; |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 291 | if (fn && (fn->group>0) && |
| 292 | ((*(CLG_(current_fn_stack).top))->group == fn->group)) return; |
| 293 | |
| 294 | /* resizing needed ? */ |
| 295 | fn_entries = CLG_(current_fn_stack).top - CLG_(current_fn_stack).bottom; |
| 296 | if (fn_entries == CLG_(current_fn_stack).size-1) { |
florian | b7876db | 2015-08-05 19:04:51 +0000 | [diff] [blame] | 297 | UInt new_size = CLG_(current_fn_stack).size *2; |
weidendo | 0b23d6e | 2009-06-15 00:16:32 +0000 | [diff] [blame] | 298 | fn_node** new_array = (fn_node**) CLG_MALLOC("cl.context.pc.1", |
| 299 | new_size * sizeof(fn_node*)); |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 300 | int i; |
| 301 | for(i=0;i<CLG_(current_fn_stack).size;i++) |
weidendo | 0b23d6e | 2009-06-15 00:16:32 +0000 | [diff] [blame] | 302 | new_array[i] = CLG_(current_fn_stack).bottom[i]; |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 303 | VG_(free)(CLG_(current_fn_stack).bottom); |
weidendo | 0b23d6e | 2009-06-15 00:16:32 +0000 | [diff] [blame] | 304 | CLG_(current_fn_stack).top = new_array + fn_entries; |
| 305 | CLG_(current_fn_stack).bottom = new_array; |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 306 | |
florian | b7876db | 2015-08-05 19:04:51 +0000 | [diff] [blame] | 307 | CLG_DEBUG(0, "Resize Context Stack: %u => %u (pushing '%s')\n", |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 308 | CLG_(current_fn_stack).size, new_size, |
florian | 19f91bb | 2012-11-10 22:29:54 +0000 | [diff] [blame] | 309 | fn ? fn->name : "0x0"); |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 310 | |
| 311 | CLG_(current_fn_stack).size = new_size; |
| 312 | } |
| 313 | |
weidendo | 6145324 | 2009-07-01 23:56:23 +0000 | [diff] [blame] | 314 | if (fn && (*(CLG_(current_fn_stack).top) == 0)) { |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 315 | UInt *pactive; |
| 316 | |
| 317 | /* this is first function: increment its active count */ |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 318 | pactive = CLG_(get_fn_entry)(fn->number); |
| 319 | (*pactive)++; |
| 320 | } |
| 321 | |
| 322 | CLG_(current_fn_stack).top++; |
| 323 | *(CLG_(current_fn_stack).top) = fn; |
| 324 | CLG_(current_state).cxt = CLG_(get_cxt)(CLG_(current_fn_stack).top); |
| 325 | |
bart | a0b6b2c | 2008-07-07 06:49:24 +0000 | [diff] [blame] | 326 | CLG_DEBUG(5, "- push_cxt(fn '%s'): new cxt %d, fn_sp %ld\n", |
florian | 19f91bb | 2012-11-10 22:29:54 +0000 | [diff] [blame] | 327 | fn ? fn->name : "0x0", |
weidendo | f3e0b49 | 2006-09-10 22:34:20 +0000 | [diff] [blame] | 328 | CLG_(current_state).cxt ? |
florian | b7876db | 2015-08-05 19:04:51 +0000 | [diff] [blame] | 329 | (Int)CLG_(current_state).cxt->base_number : -1, |
bart | a0b6b2c | 2008-07-07 06:49:24 +0000 | [diff] [blame] | 330 | CLG_(current_fn_stack).top - CLG_(current_fn_stack).bottom + 0L); |
weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 331 | } |
| 332 | |