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