context.c revision 45057907429928e628b9934079a62e59d3df7242 
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-2006, 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