1 /*--------------------------------------------------------------------*/ 2 /*--- Callgrind ---*/ 3 /*--- ct_context.c ---*/ 4 /*--------------------------------------------------------------------*/ 5 6 /* 7 This file is part of Callgrind, a Valgrind tool for call tracing. 8 9 Copyright (C) 2002-2015, Josef Weidendorfer (Josef.Weidendorfer (at) gmx.de) 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; 46 s->bottom = (fn_node**) CLG_MALLOC("cl.context.ifs.1", 47 s->size * sizeof(fn_node*)); 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; 78 cxts.table = (Context**) CLG_MALLOC("cl.context.ict.1", 79 cxts.size * sizeof(Context*)); 80 81 for (i = 0; i < cxts.size; i++) 82 cxts.table[i] = 0; 83 } 84 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; 93 new_table = (Context**) CLG_MALLOC("cl.context.rct.1", 94 new_size * sizeof(Context*)); 95 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 123 CLG_DEBUG(0, "Resize Context Hash: %u => %u (entries %u, conflicts %u/%u)\n", 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 { 170 Context* cxt; 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 189 cxt = (Context*) CLG_MALLOC("cl.context.nc.1", 190 sizeof(Context)+sizeof(fn_node*)*size); 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); 198 cxt->fn[offset] = *fn; 199 offset++; 200 fn--; 201 if (offset >= size) break; 202 } 203 if (offset < size) size = offset; 204 205 cxt->size = size; 206 cxt->base_number = CLG_(stat).context_counter; 207 cxt->hash = hash; 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); 214 cxt->next = cxts.table[idx]; 215 cxts.table[idx] = cxt; 216 217 #if CLG_ENABLE_DEBUG 218 CLG_DEBUGIF(3) { 219 VG_(printf)(" new_cxt ox%p: ", cxt); 220 CLG_(print_cxt)(12, cxt, 0); 221 } 222 #endif 223 224 return cxt; 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 239 CLG_DEBUG(5, "+ get_cxt(fn '%s'): size %u\n", 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 272 * Pushing 0x0 specifies a marker for a signal handler entry 273 */ 274 void CLG_(push_cxt)(fn_node* fn) 275 { 276 call_stack* cs = &CLG_(current_call_stack); 277 Int fn_entries; 278 279 CLG_DEBUG(5, "+ push_cxt(fn '%s'): old ctx %d\n", 280 fn ? fn->name : "0x0", 281 CLG_(current_state).cxt ? 282 (Int)CLG_(current_state).cxt->base_number : -1); 283 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 290 if (fn && (*(CLG_(current_fn_stack).top) == fn)) return; 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) { 297 UInt new_size = CLG_(current_fn_stack).size *2; 298 fn_node** new_array = (fn_node**) CLG_MALLOC("cl.context.pc.1", 299 new_size * sizeof(fn_node*)); 300 int i; 301 for(i=0;i<CLG_(current_fn_stack).size;i++) 302 new_array[i] = CLG_(current_fn_stack).bottom[i]; 303 VG_(free)(CLG_(current_fn_stack).bottom); 304 CLG_(current_fn_stack).top = new_array + fn_entries; 305 CLG_(current_fn_stack).bottom = new_array; 306 307 CLG_DEBUG(0, "Resize Context Stack: %u => %u (pushing '%s')\n", 308 CLG_(current_fn_stack).size, new_size, 309 fn ? fn->name : "0x0"); 310 311 CLG_(current_fn_stack).size = new_size; 312 } 313 314 if (fn && (*(CLG_(current_fn_stack).top) == 0)) { 315 UInt *pactive; 316 317 /* this is first function: increment its active count */ 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 326 CLG_DEBUG(5, "- push_cxt(fn '%s'): new cxt %d, fn_sp %ld\n", 327 fn ? fn->name : "0x0", 328 CLG_(current_state).cxt ? 329 (Int)CLG_(current_state).cxt->base_number : -1, 330 CLG_(current_fn_stack).top - CLG_(current_fn_stack).bottom + 0L); 331 } 332 333
