1: /* ldcref.c -- output a cross reference table
    2:    Copyright 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2006,
    3:    2007  Free Software Foundation, Inc.
    4:    Written by Ian Lance Taylor <ian@cygnus.com>
    5: 
    6:    This file is part of the 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,
   21:    MA 02110-1301, USA.  */
   22: 
   23: 
   24: /* This file holds routines that manage the cross reference table.
   25:    The table is used to generate cross reference reports.  It is also
   26:    used to implement the NOCROSSREFS command in the linker script.  */
   27: 
   28: #include "sysdep.h"
   29: #include "bfd.h"
   30: #include "bfdlink.h"
   31: #include "libiberty.h"
   32: #include "demangle.h"
   33: #include "objalloc.h"
   34: 
   35: #include "ld.h"
   36: #include "ldmain.h"
   37: #include "ldmisc.h"
   38: #include "ldexp.h"
   39: #include "ldlang.h"
   40: 
   41: /* We keep an instance of this structure for each reference to a
   42:    symbol from a given object.  */
   43: 
   44: struct cref_ref {
   45:   /* The next reference.  */
   46:   struct cref_ref *next;
   47:   /* The object.  */
   48:   bfd *abfd;
   49:   /* True if the symbol is defined.  */
   50:   unsigned int def : 1;
   51:   /* True if the symbol is common.  */
   52:   unsigned int common : 1;
   53:   /* True if the symbol is undefined.  */
   54:   unsigned int undef : 1;
   55: };
   56: 
   57: /* We keep a hash table of symbols.  Each entry looks like this.  */
   58: 
   59: struct cref_hash_entry {
   60:   struct bfd_hash_entry root;
   61:   /* The demangled name.  */
   62:   const char *demangled;
   63:   /* References to and definitions of this symbol.  */
   64:   struct cref_ref *refs;
   65: };
   66: 
   67: /* This is what the hash table looks like.  */
   68: 
   69: struct cref_hash_table {
   70:   struct bfd_hash_table root;
   71: };
   72: 
   73: /* Forward declarations.  */
   74: 
   75: static void output_one_cref (FILE *, struct cref_hash_entry *);
   76: static void check_local_sym_xref (lang_input_statement_type *);
   77: static bfd_boolean check_nocrossref (struct cref_hash_entry *, void *);
   78: static void check_refs (const char *, bfd_boolean, asection *, bfd *,
   79:                         struct lang_nocrossrefs *);
   80: static void check_reloc_refs (bfd *, asection *, void *);
   81: 
   82: /* Look up an entry in the cref hash table.  */
   83: 
   84: #define cref_hash_lookup(table, string, create, copy)           \
   85:   ((struct cref_hash_entry *)                                   \
   86:    bfd_hash_lookup (&(table)->root, (string), (create), (copy)))
   87: 
   88: /* Traverse the cref hash table.  */
   89: 
   90: #define cref_hash_traverse(table, func, info)                           \
   91:   (bfd_hash_traverse                                                    \
   92:    (&(table)->root,                                                     \
   93:     (bfd_boolean (*) (struct bfd_hash_entry *, void *)) (func),         \
   94:     (info)))
   95: 
   96: /* The cref hash table.  */
   97: 
   98: static struct cref_hash_table cref_table;
   99: 
  100: /* Whether the cref hash table has been initialized.  */
  101: 
  102: static bfd_boolean cref_initialized;
  103: 
  104: /* The number of symbols seen so far.  */
  105: 
  106: static size_t cref_symcount;
  107: 
  108: /* Used to take a snapshot of the cref hash table when starting to
  109:    add syms from an as-needed library.  */
  110: static struct bfd_hash_entry **old_table;
  111: static unsigned int old_size;
  112: static unsigned int old_count;
  113: static void *old_tab;
  114: static void *alloc_mark;
  115: static size_t tabsize, entsize, refsize;
  116: static size_t old_symcount;
  117: 
  118: /* Create an entry in a cref hash table.  */
  119: 
  120: static struct bfd_hash_entry *
  121: cref_hash_newfunc (struct bfd_hash_entry *entry,
  122:                    struct bfd_hash_table *table,
  123:                    const char *string)
  124: {
  125:   struct cref_hash_entry *ret = (struct cref_hash_entry *) entry;
  126: 
  127:   /* Allocate the structure if it has not already been allocated by a
  128:      subclass.  */
  129:   if (ret == NULL)
  130:     ret = ((struct cref_hash_entry *)
  131:            bfd_hash_allocate (table, sizeof (struct cref_hash_entry)));
  132:   if (ret == NULL)
  133:     return NULL;
  134: 
  135:   /* Call the allocation method of the superclass.  */
  136:   ret = ((struct cref_hash_entry *)
  137:          bfd_hash_newfunc ((struct bfd_hash_entry *) ret, table, string));
  138:   if (ret != NULL)
  139:     {
  140:       /* Set local fields.  */
  141:       ret->demangled = NULL;
  142:       ret->refs = NULL;
  143: 
  144:       /* Keep a count of the number of entries created in the hash
  145:          table.  */
  146:       ++cref_symcount;
  147:     }
  148: 
  149:   return &ret->root;
  150: }
  151: 
  152: /* Add a symbol to the cref hash table.  This is called for every
  153:    global symbol that is seen during the link.  */
  154: 
  155: void
  156: add_cref (const char *name,
  157:           bfd *abfd,
  158:           asection *section,
  159:           bfd_vma value ATTRIBUTE_UNUSED)
  160: {
  161:   struct cref_hash_entry *h;
  162:   struct cref_ref *r;
  163: 
  164:   if (! cref_initialized)
  165:     {
  166:       if (!bfd_hash_table_init (&cref_table.root, cref_hash_newfunc,
  167:                                 sizeof (struct cref_hash_entry)))
  168:         einfo (_("%X%P: bfd_hash_table_init of cref table failed: %E\n"));
  169:       cref_initialized = TRUE;
  170:     }
  171: 
  172:   h = cref_hash_lookup (&cref_table, name, TRUE, FALSE);
  173:   if (h == NULL)
  174:     einfo (_("%X%P: cref_hash_lookup failed: %E\n"));
  175: 
  176:   for (r = h->refs; r != NULL; r = r->next)
  177:     if (r->abfd == abfd)
  178:       break;
  179: 
  180:   if (r == NULL)
  181:     {
  182:       r = bfd_hash_allocate (&cref_table.root, sizeof *r);
  183:       if (r == NULL)
  184:         einfo (_("%X%P: cref alloc failed: %E\n"));
  185:       r->next = h->refs;
  186:       h->refs = r;
  187:       r->abfd = abfd;
  188:       r->def = FALSE;
  189:       r->common = FALSE;
  190:       r->undef = FALSE;
  191:     }
  192: 
  193:   if (bfd_is_und_section (section))
  194:     r->undef = TRUE;
  195:   else if (bfd_is_com_section (section))
  196:     r->common = TRUE;
  197:   else
  198:     r->def = TRUE;
  199: }
  200: 
  201: /* Called before loading an as-needed library to take a snapshot of
  202:    the cref hash table, and after we have loaded or found that the
  203:    library was not needed.  */
  204: 
  205: bfd_boolean
  206: handle_asneeded_cref (bfd *abfd ATTRIBUTE_UNUSED,
  207:                       enum notice_asneeded_action act)
  208: {
  209:   unsigned int i;
  210: 
  211:   if (!cref_initialized)
  212:     return TRUE;
  213: 
  214:   if (act == notice_as_needed)
  215:     {
  216:       char *old_ent, *old_ref;
  217: 
  218:       for (i = 0; i < cref_table.root.size; i++)
  219:         {
  220:           struct bfd_hash_entry *p;
  221:           struct cref_hash_entry *c;
  222:           struct cref_ref *r;
  223: 
  224:           for (p = cref_table.root.table[i]; p != NULL; p = p->next)
  225:             {
  226:               entsize += cref_table.root.entsize;
  227:               c = (struct cref_hash_entry *) p;
  228:               for (r = c->refs; r != NULL; r = r->next)
  229:                 refsize += sizeof (struct cref_hash_entry);
  230:             }
  231:         }
  232: 
  233:       tabsize = cref_table.root.size * sizeof (struct bfd_hash_entry *);
  234:       old_tab = xmalloc (tabsize + entsize + refsize);
  235: 
  236:       alloc_mark = bfd_hash_allocate (&cref_table.root, 1);
  237:       if (alloc_mark == NULL)
  238:         return FALSE;
  239: 
  240:       memcpy (old_tab, cref_table.root.table, tabsize);
  241:       old_ent = (char *) old_tab + tabsize;
  242:       old_ref = (char *) old_ent + entsize;
  243:       old_table = cref_table.root.table;
  244:       old_size = cref_table.root.size;
  245:       old_count = cref_table.root.count;
  246:       old_symcount = cref_symcount;
  247: 
  248:       for (i = 0; i < cref_table.root.size; i++)
  249:         {
  250:           struct bfd_hash_entry *p;
  251:           struct cref_hash_entry *c;
  252:           struct cref_ref *r;
  253: 
  254:           for (p = cref_table.root.table[i]; p != NULL; p = p->next)
  255:             {
  256:               memcpy (old_ent, p, cref_table.root.entsize);
  257:               old_ent = (char *) old_ent + cref_table.root.entsize;
  258:               c = (struct cref_hash_entry *) p;
  259:               for (r = c->refs; r != NULL; r = r->next)
  260:                 {
  261:                   memcpy (old_ref, r, sizeof (struct cref_hash_entry));
  262:                   old_ref = (char *) old_ref + sizeof (struct cref_hash_entry);
  263:                 }
  264:             }
  265:         }
  266:       return TRUE;
  267:     }
  268: 
  269:   if (act == notice_not_needed)
  270:     {
  271:       char *old_ent, *old_ref;
  272: 
  273:       if (old_tab == NULL)
  274:         {
  275:           /* The only way old_tab can be NULL is if the cref hash table
  276:              had not been initialised when notice_as_needed.  */
  277:           bfd_hash_table_free (&cref_table.root);
  278:           cref_initialized = FALSE;
  279:           return TRUE;
  280:         }
  281: 
  282:       old_ent = (char *) old_tab + tabsize;
  283:       old_ref = (char *) old_ent + entsize;
  284:       cref_table.root.table = old_table;
  285:       cref_table.root.size = old_size;
  286:       cref_table.root.count = old_count;
  287:       memcpy (cref_table.root.table, old_tab, tabsize);
  288:       cref_symcount = old_symcount;
  289: 
  290:       for (i = 0; i < cref_table.root.size; i++)
  291:         {
  292:           struct bfd_hash_entry *p;
  293:           struct cref_hash_entry *c;
  294:           struct cref_ref *r;
  295: 
  296:           for (p = cref_table.root.table[i]; p != NULL; p = p->next)
  297:             {
  298:               memcpy (p, old_ent, cref_table.root.entsize);
  299:               old_ent = (char *) old_ent + cref_table.root.entsize;
  300:               c = (struct cref_hash_entry *) p;
  301:               for (r = c->refs; r != NULL; r = r->next)
  302:                 {
  303:                   memcpy (r, old_ref, sizeof (struct cref_hash_entry));
  304:                   old_ref = (char *) old_ref + sizeof (struct cref_hash_entry);
  305:                 }
  306:             }
  307:         }
  308: 
  309:       objalloc_free_block ((struct objalloc *) cref_table.root.memory,
  310:                            alloc_mark);
  311:     }
  312:   else if (act != notice_needed)
  313:     return FALSE;
  314: 
  315:   free (old_tab);
  316:   old_tab = NULL;
  317:   return TRUE;
  318: }
  319: 
  320: /* Copy the addresses of the hash table entries into an array.  This
  321:    is called via cref_hash_traverse.  We also fill in the demangled
  322:    name.  */
  323: 
  324: static bfd_boolean
  325: cref_fill_array (struct cref_hash_entry *h, void *data)
  326: {
  327:   struct cref_hash_entry ***pph = data;
  328: 
  329:   ASSERT (h->demangled == NULL);
  330:   h->demangled = bfd_demangle (output_bfd, h->root.string,
  331:                                DMGL_ANSI | DMGL_PARAMS);
  332:   if (h->demangled == NULL)
  333:     h->demangled = h->root.string;
  334: 
  335:   **pph = h;
  336: 
  337:   ++*pph;
  338: 
  339:   return TRUE;
  340: }
  341: 
  342: /* Sort an array of cref hash table entries by name.  */
  343: 
  344: static int
  345: cref_sort_array (const void *a1, const void *a2)
  346: {
  347:   const struct cref_hash_entry * const *p1 = a1;
  348:   const struct cref_hash_entry * const *p2 = a2;
  349: 
  350:   return strcmp ((*p1)->demangled, (*p2)->demangled);
  351: }
  352: 
  353: /* Write out the cref table.  */
  354: 
  355: #define FILECOL (50)
  356: 
  357: void
  358: output_cref (FILE *fp)
  359: {
  360:   int len;
  361:   struct cref_hash_entry **csyms, **csym_fill, **csym, **csym_end;
  362:   const char *msg;
  363: 
  364:   fprintf (fp, _("\nCross Reference Table\n\n"));
  365:   msg = _("Symbol");
  366:   fprintf (fp, "%s", msg);
  367:   len = strlen (msg);
  368:   while (len < FILECOL)
  369:     {
  370:       putc (' ', fp);
  371:       ++len;
  372:     }
  373:   fprintf (fp, _("File\n"));
  374: 
  375:   if (! cref_initialized)
  376:     {
  377:       fprintf (fp, _("No symbols\n"));
  378:       return;
  379:     }
  380: 
  381:   csyms = xmalloc (cref_symcount * sizeof (*csyms));
  382: 
  383:   csym_fill = csyms;
  384:   cref_hash_traverse (&cref_table, cref_fill_array, &csym_fill);
  385:   ASSERT ((size_t) (csym_fill - csyms) == cref_symcount);
  386: 
  387:   qsort (csyms, cref_symcount, sizeof (*csyms), cref_sort_array);
  388: 
  389:   csym_end = csyms + cref_symcount;
  390:   for (csym = csyms; csym < csym_end; csym++)
  391:     output_one_cref (fp, *csym);
  392: }
  393: 
  394: /* Output one entry in the cross reference table.  */
  395: 
  396: static void
  397: output_one_cref (FILE *fp, struct cref_hash_entry *h)
  398: {
  399:   int len;
  400:   struct bfd_link_hash_entry *hl;
  401:   struct cref_ref *r;
  402: 
  403:   hl = bfd_link_hash_lookup (link_info.hash, h->root.string, FALSE,
  404:                              FALSE, TRUE);
  405:   if (hl == NULL)
  406:     einfo ("%P: symbol `%T' missing from main hash table\n",
  407:            h->root.string);
  408:   else
  409:     {
  410:       /* If this symbol is defined in a dynamic object but never
  411:          referenced by a normal object, then don't print it.  */
  412:       if (hl->type == bfd_link_hash_defined)
  413:         {
  414:           if (hl->u.def.section->output_section == NULL)
  415:             return;
  416:           if (hl->u.def.section->owner != NULL
  417:               && (hl->u.def.section->owner->flags & DYNAMIC) != 0)
  418:             {
  419:               for (r = h->refs; r != NULL; r = r->next)
  420:                 if ((r->abfd->flags & DYNAMIC) == 0)
  421:                   break;
  422:               if (r == NULL)
  423:                 return;
  424:             }
  425:         }
  426:     }
  427: 
  428:   fprintf (fp, "%s ", h->demangled);
  429:   len = strlen (h->demangled) + 1;
  430: 
  431:   for (r = h->refs; r != NULL; r = r->next)
  432:     {
  433:       if (r->def)
  434:         {
  435:           while (len < FILECOL)
  436:             {
  437:               putc (' ', fp);
  438:               ++len;
  439:             }
  440:           lfinfo (fp, "%B\n", r->abfd);
  441:           len = 0;
  442:         }
  443:     }
  444: 
  445:   for (r = h->refs; r != NULL; r = r->next)
  446:     {
  447:       if (! r->def)
  448:         {
  449:           while (len < FILECOL)
  450:             {
  451:               putc (' ', fp);
  452:               ++len;
  453:             }
  454:           lfinfo (fp, "%B\n", r->abfd);
  455:           len = 0;
  456:         }
  457:     }
  458: 
  459:   ASSERT (len == 0);
  460: }
  461: 
  462: /* Check for prohibited cross references.  */
  463: 
  464: void
  465: check_nocrossrefs (void)
  466: {
  467:   if (! cref_initialized)
  468:     return;
  469: 
  470:   cref_hash_traverse (&cref_table, check_nocrossref, NULL);
  471: 
  472:   lang_for_each_file (check_local_sym_xref);
  473: }
  474: 
  475: /* Check for prohibited cross references to local and section symbols.  */
  476: 
  477: static void
  478: check_local_sym_xref (lang_input_statement_type *statement)
  479: {
  480:   bfd *abfd;
  481:   lang_input_statement_type *li;
  482:   asymbol **asymbols, **syms;
  483: 
  484:   abfd = statement->the_bfd;
  485:   if (abfd == NULL)
  486:     return;
  487: 
  488:   li = abfd->usrdata;
  489:   if (li != NULL && li->asymbols != NULL)
  490:     asymbols = li->asymbols;
  491:   else
  492:     {
  493:       long symsize;
  494:       long symbol_count;
  495: 
  496:       symsize = bfd_get_symtab_upper_bound (abfd);
  497:       if (symsize < 0)
  498:         einfo (_("%B%F: could not read symbols; %E\n"), abfd);
  499:       asymbols = xmalloc (symsize);
  500:       symbol_count = bfd_canonicalize_symtab (abfd, asymbols);
  501:       if (symbol_count < 0)
  502:         einfo (_("%B%F: could not read symbols: %E\n"), abfd);
  503:       if (li != NULL)
  504:         {
  505:           li->asymbols = asymbols;
  506:           li->symbol_count = symbol_count;
  507:         }
  508:     }
  509: 
  510:   for (syms = asymbols; *syms; ++syms)
  511:     {
  512:       asymbol *sym = *syms;
  513:       if (sym->flags & (BSF_GLOBAL | BSF_WARNING | BSF_INDIRECT | BSF_FILE))
  514:         continue;
  515:       if ((sym->flags & (BSF_LOCAL | BSF_SECTION_SYM)) != 0
  516:           && sym->section->output_section != NULL)
  517:         {
  518:           const char *outsecname, *symname;
  519:           struct lang_nocrossrefs *ncrs;
  520:           struct lang_nocrossref *ncr;
  521: 
  522:           outsecname = sym->section->output_section->name;
  523:           symname = NULL;
  524:           if ((sym->flags & BSF_SECTION_SYM) == 0)
  525:             symname = sym->name;
  526:           for (ncrs = nocrossref_list; ncrs != NULL; ncrs = ncrs->next)
  527:             for (ncr = ncrs->list; ncr != NULL; ncr = ncr->next)
  528:               if (strcmp (ncr->name, outsecname) == 0)
  529:                 check_refs (symname, FALSE, sym->section, abfd, ncrs);
  530:         }
  531:     }
  532: 
  533:   if (li == NULL)
  534:     free (asymbols);
  535: }
  536: 
  537: /* Check one symbol to see if it is a prohibited cross reference.  */
  538: 
  539: static bfd_boolean
  540: check_nocrossref (struct cref_hash_entry *h, void *ignore ATTRIBUTE_UNUSED)
  541: {
  542:   struct bfd_link_hash_entry *hl;
  543:   asection *defsec;
  544:   const char *defsecname;
  545:   struct lang_nocrossrefs *ncrs;
  546:   struct lang_nocrossref *ncr;
  547:   struct cref_ref *ref;
  548: 
  549:   hl = bfd_link_hash_lookup (link_info.hash, h->root.string, FALSE,
  550:                              FALSE, TRUE);
  551:   if (hl == NULL)
  552:     {
  553:       einfo (_("%P: symbol `%T' missing from main hash table\n"),
  554:              h->root.string);
  555:       return TRUE;
  556:     }
  557: 
  558:   if (hl->type != bfd_link_hash_defined
  559:       && hl->type != bfd_link_hash_defweak)
  560:     return TRUE;
  561: 
  562:   defsec = hl->u.def.section->output_section;
  563:   if (defsec == NULL)
  564:     return TRUE;
  565:   defsecname = bfd_get_section_name (defsec->owner, defsec);
  566: 
  567:   for (ncrs = nocrossref_list; ncrs != NULL; ncrs = ncrs->next)
  568:     for (ncr = ncrs->list; ncr != NULL; ncr = ncr->next)
  569:       if (strcmp (ncr->name, defsecname) == 0)
  570:         for (ref = h->refs; ref != NULL; ref = ref->next)
  571:           check_refs (hl->root.string, TRUE, hl->u.def.section,
  572:                       ref->abfd, ncrs);
  573: 
  574:   return TRUE;
  575: }
  576: 
  577: /* The struct is used to pass information from check_refs to
  578:    check_reloc_refs through bfd_map_over_sections.  */
  579: 
  580: struct check_refs_info {
  581:   const char *sym_name;