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-2011, 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 */
36bb_hash bbs;
37
38void 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
50bb_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 */
59static __inline__
60UInt 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  */
66static
67void 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 */
121static 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 */
178static __inline__
179BB* 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
197static __inline__
198obj_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 */
242BB* 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'. */
289void 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