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-2013, 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 cxt_hash* CLG_(get_cxt_hash)() 86 { 87 return &cxts; 88 } 89 90 /* double size of cxt table */ 91 static void resize_cxt_table(void) 92 { 93 UInt i, new_size, conflicts1 = 0, conflicts2 = 0; 94 Context **new_table, *curr, *next; 95 UInt new_idx; 96 97 new_size = 2* cxts.size +3; 98 new_table = (Context**) CLG_MALLOC("cl.context.rct.1", 99 new_size * sizeof(Context*)); 100 101 if (!new_table) return; 102 103 for (i = 0; i < new_size; i++) 104 new_table[i] = NULL; 105 106 for (i = 0; i < cxts.size; i++) { 107 if (cxts.table[i] == NULL) continue; 108 109 curr = cxts.table[i]; 110 while (NULL != curr) { 111 next = curr->next; 112 113 new_idx = (UInt) (curr->hash % new_size); 114 115 curr->next = new_table[new_idx]; 116 new_table[new_idx] = curr; 117 if (curr->next) { 118 conflicts1++; 119 if (curr->next->next) 120 conflicts2++; 121 } 122 123 curr = next; 124 } 125 } 126 127 VG_(free)(cxts.table); 128 129 130 CLG_DEBUG(0, "Resize Context Hash: %d => %d (entries %d, conflicts %d/%d)\n", 131 cxts.size, new_size, 132 cxts.entries, conflicts1, conflicts2); 133 134 cxts.size = new_size; 135 cxts.table = new_table; 136 CLG_(stat).cxt_hash_resizes++; 137 } 138 139 __inline__ 140 static UWord cxt_hash_val(fn_node** fn, UInt size) 141 { 142 UWord hash = 0; 143 UInt count = size; 144 while(*fn != 0) { 145 hash = (hash<<7) + (hash>>25) + (UWord)(*fn); 146 fn--; 147 count--; 148 if (count==0) break; 149 } 150 return hash; 151 } 152 153 __inline__ 154 static Bool is_cxt(UWord hash, fn_node** fn, Context* cxt) 155 { 156 int count; 157 fn_node** cxt_fn; 158 159 if (hash != cxt->hash) return False; 160 161 count = cxt->size; 162 cxt_fn = &(cxt->fn[0]); 163 while((*fn != 0) && (count>0)) { 164 if (*cxt_fn != *fn) return False; 165 fn--; 166 cxt_fn++; 167 count--; 168 } 169 return True; 170 } 171 172 /** 173 * Allocate new Context structure 174 */ 175 static Context* new_cxt(fn_node** fn) 176 { 177 Context* cxt; 178 UInt idx, offset; 179 UWord hash; 180 int size, recs; 181 fn_node* top_fn; 182 183 CLG_ASSERT(fn); 184 top_fn = *fn; 185 if (top_fn == 0) return 0; 186 187 size = top_fn->separate_callers +1; 188 recs = top_fn->separate_recursions; 189 if (recs<1) recs=1; 190 191 /* check fill degree of context hash table and resize if needed (>80%) */ 192 cxts.entries++; 193 if (10 * cxts.entries / cxts.size > 8) 194 resize_cxt_table(); 195 196 cxt = (Context*) CLG_MALLOC("cl.context.nc.1", 197 sizeof(Context)+sizeof(fn_node*)*size); 198 199 // hash value calculation similar to cxt_hash_val(), but additionally 200 // copying function pointers in one run 201 hash = 0; 202 offset = 0; 203 while(*fn != 0) { 204 hash = (hash<<7) + (hash>>25) + (UWord)(*fn); 205 cxt->fn[offset] = *fn; 206 offset++; 207 fn--; 208 if (offset >= size) break; 209 } 210 if (offset < size) size = offset; 211 212 cxt->size = size; 213 cxt->base_number = CLG_(stat).context_counter; 214 cxt->hash = hash; 215 216 CLG_(stat).context_counter += recs; 217 CLG_(stat).distinct_contexts++; 218 219 /* insert into Context hash table */ 220 idx = (UInt) (hash % cxts.size); 221 cxt->next = cxts.table[idx]; 222 cxts.table[idx] = cxt; 223 224 #if CLG_ENABLE_DEBUG 225 CLG_DEBUGIF(3) { 226 VG_(printf)(" new_cxt ox%p: ", cxt); 227 CLG_(print_cxt)(12, cxt, 0); 228 } 229 #endif 230 231 return cxt; 232 } 233 234 /* get the Context structure for current context */ 235 Context* CLG_(get_cxt)(fn_node** fn) 236 { 237 Context* cxt; 238 UInt size, idx; 239 UWord hash; 240 241 CLG_ASSERT(fn != 0); 242 if (*fn == 0) return 0; 243 size = (*fn)->separate_callers+1; 244 if (size<=0) { size = -size+1; } 245 246 CLG_DEBUG(5, "+ get_cxt(fn '%s'): size %d\n", 247 (*fn)->name, size); 248 249 hash = cxt_hash_val(fn, size); 250 251 if ( ((cxt = (*fn)->last_cxt) != 0) && is_cxt(hash, fn, cxt)) { 252 CLG_DEBUG(5, "- get_cxt: %p\n", cxt); 253 return cxt; 254 } 255 256 CLG_(stat).cxt_lru_misses++; 257 258 idx = (UInt) (hash % cxts.size); 259 cxt = cxts.table[idx]; 260 261 while(cxt) { 262 if (is_cxt(hash,fn,cxt)) break; 263 cxt = cxt->next; 264 } 265 266 if (!cxt) 267 cxt = new_cxt(fn); 268 269 (*fn)->last_cxt = cxt; 270 271 CLG_DEBUG(5, "- get_cxt: %p\n", cxt); 272 273 return cxt; 274 } 275 276 277 /** 278 * Change execution context by calling a new function from current context 279 * Pushing 0x0 specifies a marker for a signal handler entry 280 */ 281 void CLG_(push_cxt)(fn_node* fn) 282 { 283 call_stack* cs = &CLG_(current_call_stack); 284 Int fn_entries; 285 286 CLG_DEBUG(5, "+ push_cxt(fn '%s'): old ctx %d\n", 287 fn ? fn->name : "0x0", 288 CLG_(current_state).cxt ? 289 CLG_(current_state).cxt->base_number : -1); 290 291 /* save old context on stack (even if not changed at all!) */ 292 CLG_ASSERT(cs->sp < cs->size); 293 CLG_ASSERT(cs->entry[cs->sp].cxt == 0); 294 cs->entry[cs->sp].cxt = CLG_(current_state).cxt; 295 cs->entry[cs->sp].fn_sp = CLG_(current_fn_stack).top - CLG_(current_fn_stack).bottom; 296 297 if (fn && (*(CLG_(current_fn_stack).top) == fn)) return; 298 if (fn && (fn->group>0) && 299 ((*(CLG_(current_fn_stack).top))->group == fn->group)) return; 300 301 /* resizing needed ? */ 302 fn_entries = CLG_(current_fn_stack).top - CLG_(current_fn_stack).bottom; 303 if (fn_entries == CLG_(current_fn_stack).size-1) { 304 int new_size = CLG_(current_fn_stack).size *2; 305 fn_node** new_array = (fn_node**) CLG_MALLOC("cl.context.pc.1", 306 new_size * sizeof(fn_node*)); 307 int i; 308 for(i=0;i<CLG_(current_fn_stack).size;i++) 309 new_array[i] = CLG_(current_fn_stack).bottom[i]; 310 VG_(free)(CLG_(current_fn_stack).bottom); 311 CLG_(current_fn_stack).top = new_array + fn_entries; 312 CLG_(current_fn_stack).bottom = new_array; 313 314 CLG_DEBUG(0, "Resize Context Stack: %d => %d (pushing '%s')\n", 315 CLG_(current_fn_stack).size, new_size, 316 fn ? fn->name : "0x0"); 317 318 CLG_(current_fn_stack).size = new_size; 319 } 320 321 if (fn && (*(CLG_(current_fn_stack).top) == 0)) { 322 UInt *pactive; 323 324 /* this is first function: increment its active count */ 325 pactive = CLG_(get_fn_entry)(fn->number); 326 (*pactive)++; 327 } 328 329 CLG_(current_fn_stack).top++; 330 *(CLG_(current_fn_stack).top) = fn; 331 CLG_(current_state).cxt = CLG_(get_cxt)(CLG_(current_fn_stack).top); 332 333 CLG_DEBUG(5, "- push_cxt(fn '%s'): new cxt %d, fn_sp %ld\n", 334 fn ? fn->name : "0x0", 335 CLG_(current_state).cxt ? 336 CLG_(current_state).cxt->base_number : -1, 337 CLG_(current_fn_stack).top - CLG_(current_fn_stack).bottom + 0L); 338 } 339 340
