weidendo | a17f2a3 | 2006-03-20 10:27:30 +0000 | [diff] [blame] | 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-2004, 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 | |
| 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(bbs.size * sizeof(BB*)); |
| 45 | |
| 46 | for (i = 0; i < bbs.size; i++) bbs.table[i] = NULL; |
| 47 | } |
| 48 | |
| 49 | bb_hash* CLG_(get_bb_hash)() |
| 50 | { |
| 51 | return &bbs; |
| 52 | } |
| 53 | |
| 54 | /* The hash stores BBs according to |
| 55 | * - ELF object (is 0 for code in anonymous mapping) |
| 56 | * - BB base as object file offset |
| 57 | */ |
| 58 | static __inline__ |
| 59 | UInt bb_hash_idx(obj_node* obj, OffT offset, UInt size) |
| 60 | { |
| 61 | return (((Addr)obj) + offset) % size; |
| 62 | } |
| 63 | |
| 64 | /* double size of bb table */ |
| 65 | static |
| 66 | void resize_bb_table(void) |
| 67 | { |
| 68 | Int i, new_size, conflicts1 = 0, conflicts2 = 0; |
| 69 | BB **new_table, *curr, *next; |
| 70 | UInt new_idx; |
| 71 | |
| 72 | new_size = 2* bbs.size +3; |
| 73 | new_table = (BB**) CLG_MALLOC(new_size * sizeof(BB*)); |
| 74 | |
| 75 | if (!new_table) return; |
| 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: %d => %d (entries %d, 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, OffT offset, |
| 120 | UInt instr_count, UInt cjmp_count, Bool cjmp_inverted) |
| 121 | { |
| 122 | BB* new; |
| 123 | UInt new_idx; |
| 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 | new = (BB*) CLG_MALLOC(sizeof(BB) + |
| 131 | instr_count * sizeof(InstrInfo) + |
| 132 | (cjmp_count+1) * sizeof(CJmpInfo)); |
| 133 | |
| 134 | new->obj = obj; |
| 135 | new->offset = offset; |
| 136 | |
| 137 | new->instr_count = instr_count; |
| 138 | new->cjmp_count = cjmp_count; |
| 139 | new->cjmp_inverted = cjmp_inverted; |
| 140 | new->jmp = (CJmpInfo*) &(new->instr[instr_count]); |
| 141 | new->instr_len = 0; |
| 142 | new->cost_count = 0; |
| 143 | new->sect_kind = VG_(seginfo_sect_kind)(offset + obj->offset); |
| 144 | new->fn = 0; |
| 145 | new->line = 0; |
| 146 | new->is_entry = 0; |
| 147 | new->bbcc_list = 0; |
| 148 | new->last_bbcc = 0; |
| 149 | |
| 150 | /* insert into BB hash table */ |
| 151 | new_idx = bb_hash_idx(obj, offset, bbs.size); |
| 152 | new->next = bbs.table[new_idx]; |
| 153 | bbs.table[new_idx] = new; |
| 154 | |
| 155 | CLG_(stat).distinct_bbs++; |
| 156 | |
| 157 | #if CLG_ENABLE_DEBUG |
| 158 | CLG_DEBUGIF(3) { |
| 159 | VG_(printf)(" new_bb (instr %d, jmps %d, inv %s) [now %d]: ", |
| 160 | instr_count, cjmp_count, |
| 161 | cjmp_inverted ? "yes":"no", |
| 162 | CLG_(stat).distinct_bbs); |
| 163 | CLG_(print_bb)(0, new); |
| 164 | VG_(printf)("\n"); |
| 165 | } |
| 166 | #endif |
| 167 | |
| 168 | CLG_(get_fn_node)(new); |
| 169 | |
| 170 | return new; |
| 171 | } |
| 172 | |
| 173 | |
| 174 | /* get the BB structure for a BB start address */ |
| 175 | static __inline__ |
| 176 | BB* lookup_bb(obj_node* obj, OffT offset) |
| 177 | { |
| 178 | BB* bb; |
| 179 | Int idx; |
| 180 | |
| 181 | idx = bb_hash_idx(obj, offset, bbs.size); |
| 182 | bb = bbs.table[idx]; |
| 183 | |
| 184 | while(bb) { |
| 185 | if ((bb->obj == obj) && (bb->offset == offset)) break; |
| 186 | bb = bb->next; |
| 187 | } |
| 188 | |
| 189 | CLG_DEBUG(5, " lookup_bb (Obj %s, off %p): %p\n", |
| 190 | obj->name, offset, bb); |
| 191 | return bb; |
| 192 | } |
| 193 | |
| 194 | static __inline__ |
| 195 | obj_node* obj_of_address(Addr addr) |
| 196 | { |
| 197 | obj_node* obj; |
| 198 | SegInfo* si; |
| 199 | OffT offset; |
| 200 | |
| 201 | si = VG_(find_seginfo)(addr); |
| 202 | obj = CLG_(get_obj_node)( si ); |
| 203 | |
| 204 | /* Update symbol offset in object if remapped */ |
| 205 | offset = si ? VG_(seginfo_sym_offset)(si):0; |
| 206 | if (obj->offset != offset) { |
| 207 | Addr start = si ? VG_(seginfo_start)(si) : 0; |
| 208 | |
| 209 | CLG_DEBUG(0, "Mapping changed for '%s': %p -> %p\n", |
| 210 | obj->name, obj->start, start); |
| 211 | |
| 212 | /* Size should be the same, and offset diff == start diff */ |
| 213 | CLG_ASSERT( obj->size == (si ? VG_(seginfo_size)(si) : 0) ); |
| 214 | CLG_ASSERT( obj->start - start == obj->offset - offset ); |
| 215 | obj->offset = offset; |
| 216 | obj->start = start; |
| 217 | } |
| 218 | |
| 219 | return obj; |
| 220 | } |
| 221 | |
| 222 | /* Get the BB structure for a BB start address. |
| 223 | * If the BB has to be created, the IRBB is needed to |
| 224 | * compute the event type list for costs, and seen_before is |
| 225 | * set to False. Otherwise, seen_before is set to True. |
| 226 | * |
| 227 | * BBs are never discarded. There are 2 cases where this function |
| 228 | * is called from CLG_(instrument)() and a BB already exists: |
| 229 | * - The instrumented version was removed from Valgrinds TT cache |
| 230 | * - The ELF object of the BB was unmapped and mapped again. |
| 231 | * This involves a possibly different address, but is handled by |
| 232 | * looking up a BB keyed by (obj_node, file offset). |
| 233 | * |
| 234 | * bbIn==0 is possible for artifical BB without real code. |
| 235 | * Such a BB is created when returning to an unknown function. |
| 236 | */ |
| 237 | BB* CLG_(get_bb)(Addr addr, IRBB* bbIn, /*OUT*/ Bool *seen_before) |
| 238 | { |
| 239 | BB* bb; |
| 240 | obj_node* obj; |
| 241 | UInt n_instrs, n_jmps; |
| 242 | Bool cjmp_inverted = False; |
| 243 | |
| 244 | CLG_DEBUG(5, "+ get_bb(BB %p)\n", addr); |
| 245 | |
| 246 | obj = obj_of_address(addr); |
| 247 | bb = lookup_bb(obj, addr - obj->offset); |
| 248 | |
| 249 | n_instrs = 0; |
| 250 | n_jmps = 0; |
| 251 | CLG_(collectBlockInfo)(bbIn, &n_instrs, &n_jmps, &cjmp_inverted); |
| 252 | |
| 253 | *seen_before = bb ? True : False; |
| 254 | if (*seen_before) { |
| 255 | if (bb->instr_count != n_instrs) { |
| 256 | VG_(message)(Vg_DebugMsg, |
| 257 | "ERROR: BB Retranslation Mismatch at BB %p", addr); |
| 258 | VG_(message)(Vg_DebugMsg, |
| 259 | " new: Obj %s, Off %p, BBOff %p, Instrs %u", |
| 260 | obj->name, obj->offset, |
| 261 | addr - obj->offset, n_instrs); |
| 262 | VG_(message)(Vg_DebugMsg, |
| 263 | " old: Obj %s, Off %p, BBOff %p, Instrs %u", |
| 264 | bb->obj->name, bb->obj->offset, |
| 265 | bb->offset, bb->instr_count); |
| 266 | CLG_ASSERT(bb->instr_count == n_instrs ); |
| 267 | } |
| 268 | CLG_ASSERT(bb->cjmp_count == n_jmps ); |
| 269 | CLG_(stat).bb_retranslations++; |
| 270 | |
| 271 | CLG_DEBUG(5, "- get_bb(BB %p): seen before.\n", addr); |
| 272 | return bb; |
| 273 | } |
| 274 | |
| 275 | bb = new_bb(obj, addr - obj->offset, n_instrs, n_jmps, cjmp_inverted); |
| 276 | |
| 277 | CLG_DEBUG(5, "- get_bb(BB %p)\n", addr); |
| 278 | |
| 279 | return bb; |
| 280 | } |
| 281 | |
| 282 | /* Delete the BB info for the bb with unredirected entry-point |
| 283 | address 'addr'. */ |
| 284 | void CLG_(delete_bb)(Addr addr) |
| 285 | { |
| 286 | BB *bb, *bp; |
| 287 | Int idx, size; |
| 288 | |
| 289 | obj_node* obj = obj_of_address(addr); |
| 290 | OffT offset = addr - obj->offset; |
| 291 | |
| 292 | idx = bb_hash_idx(obj, offset, bbs.size); |
| 293 | bb = bbs.table[idx]; |
| 294 | |
| 295 | /* bb points at the current bb under consideration, and bp is the |
| 296 | one before. */ |
| 297 | bp = NULL; |
| 298 | while(bb) { |
| 299 | if ((bb->obj == obj) && (bb->offset == offset)) break; |
| 300 | bp = bb; |
| 301 | bb = bb->next; |
| 302 | } |
| 303 | |
| 304 | if (bb == NULL) { |
| 305 | CLG_DEBUG(3, " delete_bb (Obj %s, off %p): NOT FOUND\n", |
| 306 | obj->name, offset); |
| 307 | |
| 308 | /* we didn't find it. That's strange. */ |
| 309 | return; |
| 310 | } |
| 311 | |
| 312 | /* unlink it from hash table */ |
| 313 | |
| 314 | if (bp == NULL) { |
| 315 | /* we found the first one in the list. */ |
| 316 | tl_assert(bb == bbs.table[idx]); |
| 317 | bbs.table[idx] = bb->next; |
| 318 | } else { |
| 319 | tl_assert(bb != bbs.table[idx]); |
| 320 | bp->next = bb->next; |
| 321 | } |
| 322 | |
| 323 | CLG_DEBUG(3, " delete_bb (Obj %s, off %p): %p, BBCC head: %p\n", |
| 324 | obj->name, offset, bb, bb->bbcc_list); |
| 325 | |
| 326 | if (bb->bbcc_list == 0) { |
| 327 | /* can be safely deleted */ |
| 328 | |
| 329 | /* Fill the block up with junk and then free it, so we will |
| 330 | hopefully get a segfault if it is used again by mistake. */ |
| 331 | size = sizeof(BB) |
| 332 | + bb->instr_count * sizeof(InstrInfo) |
| 333 | + (bb->cjmp_count+1) * sizeof(CJmpInfo); |
| 334 | VG_(memset)( bb, 0xAA, size ); |
| 335 | CLG_FREE(bb); |
| 336 | } |
| 337 | CLG_DEBUG(3, " delete_bb: BB in use, can not free!\n"); |
| 338 | } |