1 /*--------------------------------------------------------------------*/
2 /*--- Callgrind ---*/
3 /*--- bb.c ---*/
4 /*--------------------------------------------------------------------*/
5
6 /*
7 This file is part of Callgrind, a Valgrind tool for call tracing.
8
9 Copyright (C) 2002-2012, 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 /*--- Basic block (BB) operations ---*/
33 /*------------------------------------------------------------*/
34
35 /* BB hash, resizable */
36 bb_hash bbs;
37
CLG_(init_bb_hash)38 void CLG_(init_bb_hash)()
39 {
40 Int i;
41
42 bbs.size = 8437;
43 bbs.entries = 0;
44 bbs.table = (BB**) CLG_MALLOC("cl.bb.ibh.1",
45 bbs.size * sizeof(BB*));
46
47 for (i = 0; i < bbs.size; i++) bbs.table[i] = NULL;
48 }
49
CLG_(get_bb_hash)50 bb_hash* CLG_(get_bb_hash)()
51 {
52 return &bbs;
53 }
54
55 /* The hash stores BBs according to
56 * - ELF object (is 0 for code in anonymous mapping)
57 * - BB base as object file offset
58 */
59 static __inline__
bb_hash_idx(obj_node * obj,PtrdiffT offset,UInt size)60 UInt bb_hash_idx(obj_node* obj, PtrdiffT offset, UInt size)
61 {
62 return (((Addr)obj) + offset) % size;
63 }
64
65 /* double size of bb table */
66 static
resize_bb_table(void)67 void resize_bb_table(void)
68 {
69 Int i, new_size, conflicts1 = 0, conflicts2 = 0;
70 BB **new_table, *curr, *next;
71 UInt new_idx;
72
73 new_size = 2* bbs.size +3;
74 new_table = (BB**) CLG_MALLOC("cl.bb.rbt.1",
75 new_size * sizeof(BB*));
76
77 if (!new_table) return;
78
79 for (i = 0; i < new_size; i++)
80 new_table[i] = NULL;
81
82 for (i = 0; i < bbs.size; i++) {
83 if (bbs.table[i] == NULL) continue;
84
85 curr = bbs.table[i];
86 while (NULL != curr) {
87 next = curr->next;
88
89 new_idx = bb_hash_idx(curr->obj, curr->offset, new_size);
90
91 curr->next = new_table[new_idx];
92 new_table[new_idx] = curr;
93 if (curr->next) {
94 conflicts1++;
95 if (curr->next->next)
96 conflicts2++;
97 }
98
99 curr = next;
100 }
101 }
102
103 VG_(free)(bbs.table);
104
105
106 CLG_DEBUG(0, "Resize BB Hash: %d => %d (entries %d, conflicts %d/%d)\n",
107 bbs.size, new_size,
108 bbs.entries, conflicts1, conflicts2);
109
110 bbs.size = new_size;
111 bbs.table = new_table;
112 CLG_(stat).bb_hash_resizes++;
113 }
114
115
116 /**
117 * Allocate new BB structure (including space for event type list)
118 * Not initialized:
119 * - instr_len, cost_count, instr[]
120 */
new_bb(obj_node * obj,PtrdiffT offset,UInt instr_count,UInt cjmp_count,Bool cjmp_inverted)121 static BB* new_bb(obj_node* obj, PtrdiffT offset,
122 UInt instr_count, UInt cjmp_count, Bool cjmp_inverted)
123 {
124 BB* bb;
125 UInt idx, size;
126
127 /* check fill degree of bb hash table and resize if needed (>80%) */
128 bbs.entries++;
129 if (10 * bbs.entries / bbs.size > 8)
130 resize_bb_table();
131
132 size = sizeof(BB) + instr_count * sizeof(InstrInfo)
133 + (cjmp_count+1) * sizeof(CJmpInfo);
134 bb = (BB*) CLG_MALLOC("cl.bb.nb.1", size);
135 VG_(memset)(bb, 0, size);
136
137 bb->obj = obj;
138 bb->offset = offset;
139
140 bb->instr_count = instr_count;
141 bb->cjmp_count = cjmp_count;
142 bb->cjmp_inverted = cjmp_inverted;
143 bb->jmp = (CJmpInfo*) &(bb->instr[instr_count]);
144 bb->instr_len = 0;
145 bb->cost_count = 0;
146 bb->sect_kind = VG_(DebugInfo_sect_kind)(NULL, 0, offset + obj->offset);
147 bb->fn = 0;
148 bb->line = 0;
149 bb->is_entry = 0;
150 bb->bbcc_list = 0;
151 bb->last_bbcc = 0;
152
153 /* insert into BB hash table */
154 idx = bb_hash_idx(obj, offset, bbs.size);
155 bb->next = bbs.table[idx];
156 bbs.table[idx] = bb;
157
158 CLG_(stat).distinct_bbs++;
159
160 #if CLG_ENABLE_DEBUG
161 CLG_DEBUGIF(3) {
162 VG_(printf)(" new_bb (instr %d, jmps %d, inv %s) [now %d]: ",
163 instr_count, cjmp_count,
164 cjmp_inverted ? "yes":"no",
165 CLG_(stat).distinct_bbs);
166 CLG_(print_bb)(0, bb);
167 VG_(printf)("\n");
168 }
169 #endif
170
171 CLG_(get_fn_node)(bb);
172
173 return bb;
174 }
175
176
177 /* get the BB structure for a BB start address */
178 static __inline__
lookup_bb(obj_node * obj,PtrdiffT offset)179 BB* lookup_bb(obj_node* obj, PtrdiffT offset)
180 {
181 BB* bb;
182 Int idx;
183
184 idx = bb_hash_idx(obj, offset, bbs.size);
185 bb = bbs.table[idx];
186
187 while(bb) {
188 if ((bb->obj == obj) && (bb->offset == offset)) break;
189 bb = bb->next;
190 }
191
192 CLG_DEBUG(5, " lookup_bb (Obj %s, off %#lx): %p\n",
193 obj->name, offset, bb);
194 return bb;
195 }
196
197 static __inline__
obj_of_address(Addr addr)198 obj_node* obj_of_address(Addr addr)
199 {
200 obj_node* obj;
201 DebugInfo* di;
202 PtrdiffT offset;
203
204 di = VG_(find_DebugInfo)(addr);
205 obj = CLG_(get_obj_node)( di );
206
207 /* Update symbol offset in object if remapped */
208 /* FIXME (or at least check this) 2008 Feb 19: 'offset' is
209 only correct for text symbols, not for data symbols */
210 offset = di ? VG_(DebugInfo_get_text_bias)(di):0;
211 if (obj->offset != offset) {
212 Addr start = di ? VG_(DebugInfo_get_text_avma)(di) : 0;
213
214 CLG_DEBUG(0, "Mapping changed for '%s': %#lx -> %#lx\n",
215 obj->name, obj->start, start);
216
217 /* Size should be the same, and offset diff == start diff */
218 CLG_ASSERT( obj->size == (di ? VG_(DebugInfo_get_text_size)(di) : 0) );
219 CLG_ASSERT( obj->start - start == obj->offset - offset );
220 obj->offset = offset;
221 obj->start = start;
222 }
223
224 return obj;
225 }
226
227 /* Get the BB structure for a BB start address.
228 * If the BB has to be created, the IRBB is needed to
229 * compute the event type list for costs, and seen_before is
230 * set to False. Otherwise, seen_before is set to True.
231 *
232 * BBs are never discarded. There are 2 cases where this function
233 * is called from CLG_(instrument)() and a BB already exists:
234 * - The instrumented version was removed from Valgrinds TT cache
235 * - The ELF object of the BB was unmapped and mapped again.
236 * This involves a possibly different address, but is handled by
237 * looking up a BB keyed by (obj_node, file offset).
238 *
239 * bbIn==0 is possible for artifical BB without real code.
240 * Such a BB is created when returning to an unknown function.
241 */
CLG_(get_bb)242 BB* CLG_(get_bb)(Addr addr, IRSB* bbIn, /*OUT*/ Bool *seen_before)
243 {
244 BB* bb;
245 obj_node* obj;
246 UInt n_instrs, n_jmps;
247 Bool cjmp_inverted = False;
248
249 CLG_DEBUG(5, "+ get_bb(BB %#lx)\n", addr);
250
251 obj = obj_of_address(addr);
252 bb = lookup_bb(obj, addr - obj->offset);
253
254 n_instrs = 0;
255 n_jmps = 0;
256 CLG_(collectBlockInfo)(bbIn, &n_instrs, &n_jmps, &cjmp_inverted);
257
258 *seen_before = bb ? True : False;
259 if (*seen_before) {
260 if (bb->instr_count != n_instrs) {
261 VG_(message)(Vg_DebugMsg,
262 "ERROR: BB Retranslation Mismatch at BB %#lx\n", addr);
263 VG_(message)(Vg_DebugMsg,
264 " new: Obj %s, Off %#lx, BBOff %#lx, Instrs %u\n",
265 obj->name, obj->offset,
266 addr - obj->offset, n_instrs);
267 VG_(message)(Vg_DebugMsg,
268 " old: Obj %s, Off %#lx, BBOff %#lx, Instrs %u\n",
269 bb->obj->name, bb->obj->offset,
270 bb->offset, bb->instr_count);
271 CLG_ASSERT(bb->instr_count == n_instrs );
272 }
273 CLG_ASSERT(bb->cjmp_count == n_jmps );
274 CLG_(stat).bb_retranslations++;
275
276 CLG_DEBUG(5, "- get_bb(BB %#lx): seen before.\n", addr);
277 return bb;
278 }
279
280 bb = new_bb(obj, addr - obj->offset, n_instrs, n_jmps, cjmp_inverted);
281
282 CLG_DEBUG(5, "- get_bb(BB %#lx)\n", addr);
283
284 return bb;
285 }
286
287 /* Delete the BB info for the bb with unredirected entry-point
288 address 'addr'. */
CLG_(delete_bb)289 void CLG_(delete_bb)(Addr addr)
290 {
291 BB *bb, *bp;
292 Int idx, size;
293
294 obj_node* obj = obj_of_address(addr);
295 PtrdiffT offset = addr - obj->offset;
296
297 idx = bb_hash_idx(obj, offset, bbs.size);
298 bb = bbs.table[idx];
299
300 /* bb points at the current bb under consideration, and bp is the
301 one before. */
302 bp = NULL;
303 while(bb) {
304 if ((bb->obj == obj) && (bb->offset == offset)) break;
305 bp = bb;
306 bb = bb->next;
307 }
308
309 if (bb == NULL) {
310 CLG_DEBUG(3, " delete_bb (Obj %s, off %#lx): NOT FOUND\n",
311 obj->name, offset);
312
313 /* we didn't find it.
314 * this happens when callgrinds instrumentation mode
315 * was off at BB translation time, ie. no BB was created.
316 */
317 return;
318 }
319
320 /* unlink it from hash table */
321
322 if (bp == NULL) {
323 /* we found the first one in the list. */
324 tl_assert(bb == bbs.table[idx]);
325 bbs.table[idx] = bb->next;
326 } else {
327 tl_assert(bb != bbs.table[idx]);
328 bp->next = bb->next;
329 }
330
331 CLG_DEBUG(3, " delete_bb (Obj %s, off %#lx): %p, BBCC head: %p\n",
332 obj->name, offset, bb, bb->bbcc_list);
333
334 if (bb->bbcc_list == 0) {
335 /* can be safely deleted */
336
337 /* Fill the block up with junk and then free it, so we will
338 hopefully get a segfault if it is used again by mistake. */
339 size = sizeof(BB)
340 + bb->instr_count * sizeof(InstrInfo)
341 + (bb->cjmp_count+1) * sizeof(CJmpInfo);
342 VG_(memset)( bb, 0xAA, size );
343 CLG_FREE(bb);
344 return;
345 }
346 CLG_DEBUG(3, " delete_bb: BB in use, can not free!\n");
347 }
348