callgrind/bb.c

   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@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   DiEpoch ep = VG_(current_DiEpoch)();
 203   di = VG_(find_DebugInfo)(ep, addr);
 204   obj = CLG_(get_obj_node)( di );
 205
 206   /* Update symbol offset in object if remapped */
 207   /* FIXME (or at least check this) 2008 Feb 19: 'offset' is
 208      only correct for text symbols, not for data symbols */
 209   offset = di ? VG_(DebugInfo_get_text_bias)(di):0;
 210   if (obj->offset != offset) {
 211       Addr start = di ? VG_(DebugInfo_get_text_avma)(di) : 0;
 212
 213       CLG_DEBUG(0, "Mapping changed for '%s': %#lx -> %#lx\n",
 214                 obj->name, obj->start, start);
 215
 216       /* Size should be the same, and offset diff == start diff */
 217       CLG_ASSERT( obj->size == (di ? VG_(DebugInfo_get_text_size)(di) : 0) );
 218       CLG_ASSERT( obj->start - start == obj->offset - offset );
 219       obj->offset = offset;
 220       obj->start = start;
 221   }
 222
 223   return obj;
 224 }
 225
 226 /* Get the BB structure for a BB start address.
 227  * If the BB has to be created, the IRBB is needed to
 228  * compute the event type list for costs, and seen_before is
 229  * set to False. Otherwise, seen_before is set to True.
 230  *
 231  * BBs are never discarded. There are 2 cases where this function
 232  * is called from CLG_(instrument)() and a BB already exists:
 233  * - The instrumented version was removed from Valgrinds TT cache
 234  * - The ELF object of the BB was unmapped and mapped again.
 235  *   This involves a possibly different address, but is handled by
 236  *   looking up a BB keyed by (obj_node, file offset).
 237  *
 238  * bbIn==0 is possible for artificial BB without real code.
 239  * Such a BB is created when returning to an unknown function.
 240  */
 241 BB* CLG_(get_bb)(Addr addr, IRSB* bbIn, /*OUT*/ Bool *seen_before)
 242 {
 243   BB*   bb;
 244   obj_node* obj;
 245   UInt n_instrs, n_jmps;
 246   Bool cjmp_inverted = False;
 247
 248   CLG_DEBUG(5, "+ get_bb(BB %#lx)\n", addr);
 249
 250   obj = obj_of_address(addr);
 251   bb = lookup_bb(obj, addr - obj->offset);
 252
 253   n_instrs = 0;
 254   n_jmps = 0;
 255   CLG_(collectBlockInfo)(bbIn, &n_instrs, &n_jmps, &cjmp_inverted);
 256
 257   *seen_before = bb ? True : False;
 258   if (*seen_before) {
 259     if (bb->instr_count != n_instrs) {
 260       VG_(message)(Vg_DebugMsg,
 261                    "ERROR: BB Retranslation Mismatch at BB %#lx\n", addr);
 262       VG_(message)(Vg_DebugMsg,
 263                    "  new: Obj %s, Off %#lx, BBOff %#lx, Instrs %u\n",
 264                    obj->name, (UWord)obj->offset,
 265                    addr - obj->offset, n_instrs);
 266       VG_(message)(Vg_DebugMsg,
 267                    "  old: Obj %s, Off %#lx, BBOff %#lx, Instrs %u\n",
 268                    bb->obj->name, (UWord)bb->obj->offset,
 269                    (UWord)bb->offset, bb->instr_count);
 270       CLG_ASSERT(bb->instr_count == n_instrs );
 271     }
 272     CLG_ASSERT(bb->cjmp_count == n_jmps );
 273     CLG_(stat).bb_retranslations++;
 274
 275     CLG_DEBUG(5, "- get_bb(BB %#lx): seen before.\n", addr);
 276     return bb;
 277   }
 278
 279   bb = new_bb(obj, addr - obj->offset, n_instrs, n_jmps, cjmp_inverted);
 280
 281   CLG_DEBUG(5, "- get_bb(BB %#lx)\n", addr);
 282
 283   return bb;
 284 }
 285
 286 /* Delete the BB info for the bb with unredirected entry-point
 287    address 'addr'. */
 288 void CLG_(delete_bb)(Addr addr)
 289 {
 290     BB  *bb, *bp;
 291     Int idx, size;
 292
 293     obj_node* obj = obj_of_address(addr);
 294     PtrdiffT offset = addr - obj->offset;
 295
 296     idx = bb_hash_idx(obj, offset, bbs.size);
 297     bb = bbs.table[idx];
 298
 299     /* bb points at the current bb under consideration, and bp is the
 300        one before. */
 301     bp = NULL;
 302     while(bb) {
 303       if ((bb->obj == obj) && (bb->offset == offset)) break;
 304       bp = bb;
 305       bb = bb->next;
 306     }
 307
 308     if (bb == NULL) {
 309         CLG_DEBUG(3, "  delete_bb (Obj %s, off %#lx): NOT FOUND\n",
 310                   obj->name, (UWord)offset);
 311
 312         /* we didn't find it.
 313          * this happens when callgrinds instrumentation mode
 314          * was off at BB translation time, ie. no BB was created.
 315          */
 316         return;
 317     }
 318
 319     /* unlink it from hash table */
 320
 321     if (bp == NULL) {
 322        /* we found the first one in the list. */
 323        tl_assert(bb == bbs.table[idx]);
 324        bbs.table[idx] = bb->next;
 325     } else {
 326        tl_assert(bb != bbs.table[idx]);
 327        bp->next = bb->next;
 328     }
 329
 330     CLG_DEBUG(3, "  delete_bb (Obj %s, off %#lx): %p, BBCC head: %p\n",
 331               obj->name, (UWord)offset, bb, bb->bbcc_list);
 332
 333     if (bb->bbcc_list == 0) {
 334         /* can be safely deleted */
 335
 336         /* Fill the block up with junk and then free it, so we will
 337            hopefully get a segfault if it is used again by mistake. */
 338         size = sizeof(BB)
 339             + bb->instr_count * sizeof(InstrInfo)
 340             + (bb->cjmp_count+1) * sizeof(CJmpInfo);
 341         VG_(memset)( bb, 0xAA, size );
 342         CLG_FREE(bb);
 343         return;
 344     }
 345     CLG_DEBUG(3, "  delete_bb: BB in use, can not free!\n");
 346 }