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
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
85 /* double size of cxt table */
resize_cxt_table(void)86 static 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__
cxt_hash_val(fn_node ** fn,UInt size)133 static 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__
is_cxt(UWord hash,fn_node ** fn,Context * cxt)147 static 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 */
new_cxt(fn_node ** fn)168 static 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 */
CLG_(get_cxt)228 Context* 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 */
CLG_(push_cxt)274 void 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