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-2010, Josef Weidendorfer (Josef.Weidendorfer (at) 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 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 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__ 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 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 */ 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__ 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__ 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 */ 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'. */ 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
