1: /* symtab.c
    2: 
    3:    Copyright 1999, 2000, 2001, 2002, 2004, 2007 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: ^L
   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: }