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-2017, 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 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 */ 119 static 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 */ 176 static __inline__ 177 BB* 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 195 static __inline__ 196 obj_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 */ 240 BB* 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'. */ 287 void 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
