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
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("cl.context.ifs.1",
47                                     s->size * sizeof(fn_node*));
48  s->top    = s->bottom;
49  s->bottom[0] = 0;
50}
51
52void 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
61void 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
70static cxt_hash cxts;
71
72void 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
85cxt_hash* CLG_(get_cxt_hash)()
86{
87  return &cxts;
88}
89
90/* double size of cxt table  */
91static 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__
140static 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__
154static 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 */
175static 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 */
235Context* 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 */
281void 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 : "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 : "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 : "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