gprof/symtab.c

   1 /* symtab.c
   2
   3    Copyright 1999, 2000, 2001, 2002, 2004, 2007, 2008
   4    Free Software Foundation, Inc.
   5
   6    This file is part of GNU Binutils.
   7
   8    This program is free software; you can redistribute it and/or modify
   9    it under the terms of the GNU General Public License as published by
  10    the Free Software Foundation; either version 3 of the License, or
  11    (at your option) any later version.
  12
  13    This program is distributed in the hope that it will be useful,
  14    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16    GNU General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with this program; if not, write to the Free Software
  20    Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA
  21    02110-1301, USA.  */
  22 \f
  23 #include "gprof.h"
  24 #include "search_list.h"
  25 #include "source.h"
  26 #include "symtab.h"
  27 #include "cg_arcs.h"
  28 #include "corefile.h"
  29
  30 static int cmp_addr (const PTR, const PTR);
  31
  32 Sym_Table symtab;
  33
  34
  35 /* Initialize a symbol (so it's empty).  */
  36
  37 void
  38 sym_init (Sym *sym)
  39 {
  40   memset (sym, 0, sizeof (*sym));
  41
  42   /* It is not safe to assume that a binary zero corresponds
  43      to a floating-point 0.0, so initialize floats explicitly.  */
  44   sym->hist.time = 0.0;
  45   sym->cg.child_time = 0.0;
  46   sym->cg.prop.fract = 0.0;
  47   sym->cg.prop.self = 0.0;
  48   sym->cg.prop.child = 0.0;
  49 }
  50
  51
  52 /* Compare the function entry-point of two symbols and return <0, =0,
  53    or >0 depending on whether the left value is smaller than, equal
  54    to, or greater than the right value.  If two symbols are equal
  55    but one has is_func set and the other doesn't, we make the
  56    non-function symbol one "bigger" so that the function symbol will
  57    survive duplicate removal.  Finally, if both symbols have the
  58    same is_func value, we discriminate against is_static such that
  59    the global symbol survives.  */
  60
  61 static int
  62 cmp_addr (const PTR lp, const PTR rp)
  63 {
  64   const Sym *left = (const Sym *) lp;
  65   const Sym *right = (const Sym *) rp;
  66
  67   if (left->addr > right->addr)
  68     return 1;
  69   else if (left->addr < right->addr)
  70     return -1;
  71
  72   if (left->is_func != right->is_func)
  73     return right->is_func - left->is_func;
  74
  75   return left->is_static - right->is_static;
  76 }
  77
  78
  79 void
  80 symtab_finalize (Sym_Table *tab)
  81 {
  82   Sym *src, *dst;
  83   bfd_vma prev_addr;
  84
  85   if (!tab->len)
  86     return;
  87
  88   /* Sort symbol table in order of increasing function addresses.  */
  89   qsort (tab->base, tab->len, sizeof (Sym), cmp_addr);
  90
  91   /* Remove duplicate entries to speed-up later processing and
  92      set end_addr if its not set yet.  */
  93   prev_addr = tab->base[0].addr + 1;
  94
  95   for (src = dst = tab->base; src < tab->limit; ++src)
  96     {
  97       if (src->addr == prev_addr)
  98         {
  99           /* If same address, favor global symbol over static one,
 100              then function over line number.  If both symbols are
 101              either static or global and either function or line, check
 102              whether one has name beginning with underscore while
 103              the other doesn't.  In such cases, keep sym without
 104              underscore.  This takes cares of compiler generated
 105              symbols (such as __gnu_compiled, __c89_used, etc.).  */
 106           if ((!src->is_static && dst[-1].is_static)
 107               || ((src->is_static == dst[-1].is_static)
 108                   && ((src->is_func && !dst[-1].is_func)
 109                       || ((src->is_func == dst[-1].is_func)
 110                           && ((src->name[0] != '_' && dst[-1].name[0] == '_')
 111                               || (src->name[0]
 112                                   && src->name[1] != '_'
 113                                   && dst[-1].name[1] == '_'))))))
 114             {
 115               DBG (AOUTDEBUG | IDDEBUG,
 116                    printf ("[symtab_finalize] favor %s@%c%c over %s@%c%c",
 117                            src->name, src->is_static ? 't' : 'T',
 118                            src->is_func ? 'F' : 'f',
 119                            dst[-1].name, dst[-1].is_static ? 't' : 'T',
 120                            dst[-1].is_func ? 'F' : 'f');
 121                    printf (" (addr=%lx)\n", (unsigned long) src->addr));
 122
 123               dst[-1] = *src;
 124             }
 125           else
 126             {
 127               DBG (AOUTDEBUG | IDDEBUG,
 128                    printf ("[symtab_finalize] favor %s@%c%c over %s@%c%c",
 129                            dst[-1].name, dst[-1].is_static ? 't' : 'T',
 130                            dst[-1].is_func ? 'F' : 'f',
 131                            src->name, src->is_static ? 't' : 'T',
 132                            src->is_func ? 'F' : 'f');
 133                    printf (" (addr=%lx)\n", (unsigned long) src->addr));
 134             }
 135         }
 136       else
 137         {
 138           if (dst > tab->base && dst[-1].end_addr == 0)
 139             dst[-1].end_addr = src->addr - 1;
 140
 141           /* Retain sym only if it has a non-empty address range.  */
 142           if (!src->end_addr || src->addr <= src->end_addr)
 143             {
 144               *dst = *src;
 145               dst++;
 146               prev_addr = src->addr;
 147             }
 148         }
 149     }
 150
 151   if (tab->len > 0 && dst[-1].end_addr == 0)
 152     dst[-1].end_addr
 153       = core_text_sect->vma + bfd_get_section_size (core_text_sect) - 1;
 154
 155   DBG (AOUTDEBUG | IDDEBUG,
 156        printf ("[symtab_finalize]: removed %d duplicate entries\n",
 157                tab->len - (int) (dst - tab->base)));
 158
 159   tab->limit = dst;
 160   tab->len = tab->limit - tab->base;
 161
 162   DBG (AOUTDEBUG | IDDEBUG,
 163        unsigned int j;
 164
 165        for (j = 0; j < tab->len; ++j)
 166          {
 167            printf ("[symtab_finalize] 0x%lx-0x%lx\t%s\n",
 168                    (unsigned long) tab->base[j].addr,
 169                    (unsigned long) tab->base[j].end_addr,
 170                    tab->base[j].name);
 171          }
 172   );
 173 }
 174
 175
 176 #ifdef DEBUG
 177
 178 Sym *
 179 dbg_sym_lookup (Sym_Table *sym_tab, bfd_vma address)
 180 {
 181   unsigned long low, mid, high;
 182   Sym *sym;
 183
 184   fprintf (stderr, "[dbg_sym_lookup] address 0x%lx\n",
 185            (unsigned long) address);
 186
 187   sym = sym_tab->base;
 188   for (low = 0, high = sym_tab->len - 1; low != high;)
 189     {
 190       mid = (high + low) >> 1;
 191
 192       fprintf (stderr, "[dbg_sym_lookup] low=0x%lx, mid=0x%lx, high=0x%lx\n",
 193                low, mid, high);
 194       fprintf (stderr, "[dbg_sym_lookup] sym[m]=0x%lx sym[m + 1]=0x%lx\n",
 195                (unsigned long) sym[mid].addr,
 196                (unsigned long) sym[mid + 1].addr);
 197
 198       if (sym[mid].addr <= address && sym[mid + 1].addr > address)
 199         return &sym[mid];
 200
 201       if (sym[mid].addr > address)
 202         high = mid;
 203       else
 204         low = mid + 1;
 205     }
 206
 207   fprintf (stderr, "[dbg_sym_lookup] binary search fails???\n");
 208
 209   return 0;
 210 }
 211
 212 #endif  /* DEBUG */
 213
 214
 215 /* Look up an address in the symbol-table that is sorted by address.
 216    If address does not hit any symbol, 0 is returned.  */
 217 Sym *
 218 sym_lookup (Sym_Table *sym_tab, bfd_vma address)
 219 {
 220   long low, high;
 221   long mid = -1;
 222   Sym *sym;
 223 #ifdef DEBUG
 224   int probes = 0;
 225 #endif /* DEBUG */
 226
 227   if (!sym_tab->len)
 228     return 0;
 229
 230   sym = sym_tab->base;
 231   for (low = 0, high = sym_tab->len - 1; low != high;)
 232     {
 233       DBG (LOOKUPDEBUG, ++probes);
 234       mid = (high + low) / 2;
 235
 236       if (sym[mid].addr <= address && sym[mid + 1].addr > address)
 237         {
 238           if (address > sym[mid].end_addr)
 239             {
 240               /* Address falls into gap between
 241                  sym[mid] and sym[mid + 1].  */
 242               return 0;
 243             }
 244           else
 245             {
 246               DBG (LOOKUPDEBUG,
 247                    printf ("[sym_lookup] %d probes (symtab->len=%u)\n",
 248                            probes, sym_tab->len - 1));
 249               return &sym[mid];
 250             }
 251         }
 252
 253       if (sym[mid].addr > address)
 254         high = mid;
 255       else
 256         low = mid + 1;
 257     }
 258
 259   if (sym[mid + 1].addr <= address)
 260     {
 261       if (address > sym[mid + 1].end_addr)
 262         {
 263           /* Address is beyond end of sym[mid + 1].  */
 264           return 0;
 265         }
 266       else
 267         {
 268           DBG (LOOKUPDEBUG, printf ("[sym_lookup] %d (%u) probes, fall off\n",
 269                                     probes, sym_tab->len - 1));
 270           return &sym[mid + 1];
 271         }
 272     }
 273
 274   return 0;
 275 }