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