Home | History | Annotate | Download | only in callgrind
      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