gprof/symtab.c

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