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