callgrind/context.c

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