Home | History | Annotate | Download | only in callgrind
      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-2010, 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 : (Char*)"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 : (Char*)"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 : (Char*)"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