gprof/symtab.c

   1 /* symtab.c
   2
   3    Copyright 2000, 2001, 2002, 2004 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 2 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., 59 Temple Place - Suite 330, Boston, MA
  20    02111-1307, 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                  (long) tab->base[j].addr, (long) tab->base[j].end_addr,
 168                  tab->base[j].name);
 169          }
 170   );
 171 }
 172
 173
 174 #ifdef DEBUG
 175
 176 Sym *
 177 dbg_sym_lookup (Sym_Table *sym_tab, bfd_vma address)
 178 {
 179   long low, mid, high;
 180   Sym *sym;
 181
 182   fprintf (stderr, "[dbg_sym_lookup] address 0x%lx\n",
 183            (unsigned long) address);
 184
 185   sym = sym_tab->base;
 186   for (low = 0, high = sym_tab->len - 1; low != high;)
 187     {
 188       mid = (high + low) >> 1;
 189
 190       fprintf (stderr, "[dbg_sym_lookup] low=0x%lx, mid=0x%lx, high=0x%lx\n",
 191                low, mid, high);
 192       fprintf (stderr, "[dbg_sym_lookup] sym[m]=0x%lx sym[m + 1]=0x%lx\n",
 193                (unsigned long) sym[mid].addr,
 194                (unsigned long) sym[mid + 1].addr);
 195
 196       if (sym[mid].addr <= address && sym[mid + 1].addr > address)
 197         return &sym[mid];
 198
 199       if (sym[mid].addr > address)
 200         high = mid;
 201       else
 202         low = mid + 1;
 203     }
 204
 205   fprintf (stderr, "[dbg_sym_lookup] binary search fails???\n");
 206
 207   return 0;
 208 }
 209
 210 #endif  /* DEBUG */
 211
 212
 213 /* Look up an address in the symbol-table that is sorted by address.
 214    If address does not hit any symbol, 0 is returned.  */
 215 Sym *
 216 sym_lookup (Sym_Table *sym_tab, bfd_vma address)
 217 {
 218   long low, high;
 219   long mid = -1;
 220   Sym *sym;
 221 #ifdef DEBUG
 222   int probes = 0;
 223 #endif /* DEBUG */
 224
 225   if (!sym_tab->len)
 226     return 0;
 227
 228   sym = sym_tab->base;
 229   for (low = 0, high = sym_tab->len - 1; low != high;)
 230     {
 231       DBG (LOOKUPDEBUG, ++probes);
 232       mid = (high + low) / 2;
 233
 234       if (sym[mid].addr <= address && sym[mid + 1].addr > address)
 235         {
 236           if (address > sym[mid].end_addr)
 237             {
 238               /* Address falls into gap between
 239                  sym[mid] and sym[mid + 1].  */
 240               return 0;
 241             }
 242           else
 243             {
 244               DBG (LOOKUPDEBUG,
 245                    printf ("[sym_lookup] %d probes (symtab->len=%u)\n",
 246                            probes, sym_tab->len - 1));
 247               return &sym[mid];
 248             }
 249         }
 250
 251       if (sym[mid].addr > address)
 252         high = mid;
 253       else
 254         low = mid + 1;
 255     }
 256
 257   if (sym[mid + 1].addr <= address)
 258     {
 259       if (address > sym[mid + 1].end_addr)
 260         {
 261           /* Address is beyond end of sym[mid + 1].  */
 262           return 0;
 263         }
 264       else
 265         {
 266           DBG (LOOKUPDEBUG, printf ("[sym_lookup] %d (%u) probes, fall off\n",
 267                                     probes, sym_tab->len - 1));
 268           return &sym[mid + 1];
 269         }
 270     }
 271
 272   return 0;
 273 }