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@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
CLG_(init_fn_stack)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
CLG_(copy_current_fn_stack)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
CLG_(set_current_fn_stack)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
CLG_(init_cxt_table)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
CLG_(get_cxt_hash)85 cxt_hash* CLG_(get_cxt_hash)()
86 {
87 return &cxts;
88 }
89
90 /* double size of cxt table */
resize_cxt_table(void)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__
cxt_hash_val(fn_node ** fn,UInt size)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__
is_cxt(UWord hash,fn_node ** fn,Context * cxt)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 */
new_cxt(fn_node ** fn)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 */
CLG_(get_cxt)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 */
CLG_(push_cxt)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