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