bfd/
[external/binutils.git] / ld / ldcref.c
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 GLD, the Gnu Linker.
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 2 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 02110-1301, USA.  */
21
22 /* This file holds routines that manage the cross reference table.
23    The table is used to generate cross reference reports.  It is also
24    used to implement the NOCROSSREFS command in the linker script.  */
25
26 #include "sysdep.h"
27 #include "bfd.h"
28 #include "bfdlink.h"
29 #include "libiberty.h"
30 #include "demangle.h"
31 #include "objalloc.h"
32
33 #include "ld.h"
34 #include "ldmain.h"
35 #include "ldmisc.h"
36 #include "ldexp.h"
37 #include "ldlang.h"
38
39 /* We keep an instance of this structure for each reference to a
40    symbol from a given object.  */
41
42 struct cref_ref {
43   /* The next reference.  */
44   struct cref_ref *next;
45   /* The object.  */
46   bfd *abfd;
47   /* True if the symbol is defined.  */
48   unsigned int def : 1;
49   /* True if the symbol is common.  */
50   unsigned int common : 1;
51   /* True if the symbol is undefined.  */
52   unsigned int undef : 1;
53 };
54
55 /* We keep a hash table of symbols.  Each entry looks like this.  */
56
57 struct cref_hash_entry {
58   struct bfd_hash_entry root;
59   /* The demangled name.  */
60   char *demangled;
61   /* References to and definitions of this symbol.  */
62   struct cref_ref *refs;
63 };
64
65 /* This is what the hash table looks like.  */
66
67 struct cref_hash_table {
68   struct bfd_hash_table root;
69 };
70
71 /* Forward declarations.  */
72
73 static void output_one_cref (FILE *, struct cref_hash_entry *);
74 static void check_local_sym_xref (lang_input_statement_type *);
75 static bfd_boolean check_nocrossref (struct cref_hash_entry *, void *);
76 static void check_refs (const char *, bfd_boolean, asection *, bfd *,
77                         struct lang_nocrossrefs *);
78 static void check_reloc_refs (bfd *, asection *, void *);
79
80 /* Look up an entry in the cref hash table.  */
81
82 #define cref_hash_lookup(table, string, create, copy)           \
83   ((struct cref_hash_entry *)                                   \
84    bfd_hash_lookup (&(table)->root, (string), (create), (copy)))
85
86 /* Traverse the cref hash table.  */
87
88 #define cref_hash_traverse(table, func, info)                           \
89   (bfd_hash_traverse                                                    \
90    (&(table)->root,                                                     \
91     (bfd_boolean (*) (struct bfd_hash_entry *, void *)) (func),         \
92     (info)))
93
94 /* The cref hash table.  */
95
96 static struct cref_hash_table cref_table;
97
98 /* Whether the cref hash table has been initialized.  */
99
100 static bfd_boolean cref_initialized;
101
102 /* The number of symbols seen so far.  */
103
104 static size_t cref_symcount;
105
106 /* Used to take a snapshot of the cref hash table when starting to
107    add syms from an as-needed library.  */
108 static struct bfd_hash_entry **old_table;
109 static unsigned int old_size;
110 static unsigned int old_count;
111 static void *old_tab;
112 static void *alloc_mark;
113 static size_t tabsize, entsize, refsize;
114 static size_t old_symcount;
115
116 /* Create an entry in a cref hash table.  */
117
118 static struct bfd_hash_entry *
119 cref_hash_newfunc (struct bfd_hash_entry *entry,
120                    struct bfd_hash_table *table,
121                    const char *string)
122 {
123   struct cref_hash_entry *ret = (struct cref_hash_entry *) entry;
124
125   /* Allocate the structure if it has not already been allocated by a
126      subclass.  */
127   if (ret == NULL)
128     ret = ((struct cref_hash_entry *)
129            bfd_hash_allocate (table, sizeof (struct cref_hash_entry)));
130   if (ret == NULL)
131     return NULL;
132
133   /* Call the allocation method of the superclass.  */
134   ret = ((struct cref_hash_entry *)
135          bfd_hash_newfunc ((struct bfd_hash_entry *) ret, table, string));
136   if (ret != NULL)
137     {
138       /* Set local fields.  */
139       ret->demangled = NULL;
140       ret->refs = NULL;
141
142       /* Keep a count of the number of entries created in the hash
143          table.  */
144       ++cref_symcount;
145     }
146
147   return &ret->root;
148 }
149
150 /* Add a symbol to the cref hash table.  This is called for every
151    global symbol that is seen during the link.  */
152
153 void
154 add_cref (const char *name,
155           bfd *abfd,
156           asection *section,
157           bfd_vma value ATTRIBUTE_UNUSED)
158 {
159   struct cref_hash_entry *h;
160   struct cref_ref *r;
161
162   if (! cref_initialized)
163     {
164       if (!bfd_hash_table_init (&cref_table.root, cref_hash_newfunc,
165                                 sizeof (struct cref_hash_entry)))
166         einfo (_("%X%P: bfd_hash_table_init of cref table failed: %E\n"));
167       cref_initialized = TRUE;
168     }
169
170   h = cref_hash_lookup (&cref_table, name, TRUE, FALSE);
171   if (h == NULL)
172     einfo (_("%X%P: cref_hash_lookup failed: %E\n"));
173
174   for (r = h->refs; r != NULL; r = r->next)
175     if (r->abfd == abfd)
176       break;
177
178   if (r == NULL)
179     {
180       r = bfd_hash_allocate (&cref_table.root, sizeof *r);
181       if (r == NULL)
182         einfo (_("%X%P: cref alloc failed: %E\n"));
183       r->next = h->refs;
184       h->refs = r;
185       r->abfd = abfd;
186       r->def = FALSE;
187       r->common = FALSE;
188       r->undef = FALSE;
189     }
190
191   if (bfd_is_und_section (section))
192     r->undef = TRUE;
193   else if (bfd_is_com_section (section))
194     r->common = TRUE;
195   else
196     r->def = TRUE;
197 }
198
199 /* Called before loading an as-needed library to take a snapshot of
200    the cref hash table, and after we have loaded or found that the
201    library was not needed.  */
202
203 bfd_boolean
204 handle_asneeded_cref (bfd *abfd ATTRIBUTE_UNUSED,
205                       enum notice_asneeded_action act)
206 {
207   unsigned int i;
208
209   if (!cref_initialized)
210     return TRUE;
211
212   if (act == notice_as_needed)
213     {
214       char *old_ent, *old_ref;
215
216       for (i = 0; i < cref_table.root.size; i++)
217         {
218           struct bfd_hash_entry *p;
219           struct cref_hash_entry *c;
220           struct cref_ref *r;
221
222           for (p = cref_table.root.table[i]; p != NULL; p = p->next)
223             {
224               entsize += cref_table.root.entsize;
225               c = (struct cref_hash_entry *) p;
226               for (r = c->refs; r != NULL; r = r->next)
227                 refsize += sizeof (struct cref_hash_entry);
228             }
229         }
230
231       tabsize = cref_table.root.size * sizeof (struct bfd_hash_entry *);
232       old_tab = xmalloc (tabsize + entsize + refsize);
233
234       alloc_mark = bfd_hash_allocate (&cref_table.root, 1);
235       if (alloc_mark == NULL)
236         return FALSE;
237
238       memcpy (old_tab, cref_table.root.table, tabsize);
239       old_ent = (char *) old_tab + tabsize;
240       old_ref = (char *) old_ent + entsize;
241       old_table = cref_table.root.table;
242       old_size = cref_table.root.size;
243       old_count = cref_table.root.count;
244       old_symcount = cref_symcount;
245
246       for (i = 0; i < cref_table.root.size; i++)
247         {
248           struct bfd_hash_entry *p;
249           struct cref_hash_entry *c;
250           struct cref_ref *r;
251
252           for (p = cref_table.root.table[i]; p != NULL; p = p->next)
253             {
254               memcpy (old_ent, p, cref_table.root.entsize);
255               old_ent = (char *) old_ent + cref_table.root.entsize;
256               c = (struct cref_hash_entry *) p;
257               for (r = c->refs; r != NULL; r = r->next)
258                 {
259                   memcpy (old_ref, r, sizeof (struct cref_hash_entry));
260                   old_ref = (char *) old_ref + sizeof (struct cref_hash_entry);
261                 }
262             }
263         }
264       return TRUE;
265     }
266
267   if (act == notice_not_needed)
268     {
269       char *old_ent, *old_ref;
270
271       if (old_tab == NULL)
272         {
273           /* The only way old_tab can be NULL is if the cref hash table
274              had not been initialised when notice_as_needed.  */
275           bfd_hash_table_free (&cref_table.root);
276           cref_initialized = FALSE;
277           return TRUE;
278         }
279
280       old_ent = (char *) old_tab + tabsize;
281       old_ref = (char *) old_ent + entsize;
282       cref_table.root.table = old_table;
283       cref_table.root.size = old_size;
284       cref_table.root.count = old_count;
285       memcpy (cref_table.root.table, old_tab, tabsize);
286       cref_symcount = old_symcount;
287
288       for (i = 0; i < cref_table.root.size; i++)
289         {
290           struct bfd_hash_entry *p;
291           struct cref_hash_entry *c;
292           struct cref_ref *r;
293
294           for (p = cref_table.root.table[i]; p != NULL; p = p->next)
295             {
296               memcpy (p, old_ent, cref_table.root.entsize);
297               old_ent = (char *) old_ent + cref_table.root.entsize;
298               c = (struct cref_hash_entry *) p;
299               for (r = c->refs; r != NULL; r = r->next)
300                 {
301                   memcpy (r, old_ref, sizeof (struct cref_hash_entry));
302                   old_ref = (char *) old_ref + sizeof (struct cref_hash_entry);
303                 }
304             }
305         }
306
307       objalloc_free_block ((struct objalloc *) cref_table.root.memory,
308                            alloc_mark);
309     }
310   else if (act != notice_needed)
311     return FALSE;
312
313   free (old_tab);
314   old_tab = NULL;
315   return TRUE;
316 }
317
318 /* Copy the addresses of the hash table entries into an array.  This
319    is called via cref_hash_traverse.  We also fill in the demangled
320    name.  */
321
322 static bfd_boolean
323 cref_fill_array (struct cref_hash_entry *h, void *data)
324 {
325   struct cref_hash_entry ***pph = data;
326
327   ASSERT (h->demangled == NULL);
328   h->demangled = bfd_demangle (output_bfd, h->root.string,
329                                DMGL_ANSI | DMGL_PARAMS);
330
331   **pph = h;
332
333   ++*pph;
334
335   return TRUE;
336 }
337
338 /* Sort an array of cref hash table entries by name.  */
339
340 static int
341 cref_sort_array (const void *a1, const void *a2)
342 {
343   const struct cref_hash_entry * const *p1 = a1;
344   const struct cref_hash_entry * const *p2 = a2;
345
346   return strcmp ((*p1)->demangled, (*p2)->demangled);
347 }
348
349 /* Write out the cref table.  */
350
351 #define FILECOL (50)
352
353 void
354 output_cref (FILE *fp)
355 {
356   int len;
357   struct cref_hash_entry **csyms, **csym_fill, **csym, **csym_end;
358   const char *msg;
359
360   fprintf (fp, _("\nCross Reference Table\n\n"));
361   msg = _("Symbol");
362   fprintf (fp, "%s", msg);
363   len = strlen (msg);
364   while (len < FILECOL)
365     {
366       putc (' ', fp);
367       ++len;
368     }
369   fprintf (fp, _("File\n"));
370
371   if (! cref_initialized)
372     {
373       fprintf (fp, _("No symbols\n"));
374       return;
375     }
376
377   csyms = xmalloc (cref_symcount * sizeof (*csyms));
378
379   csym_fill = csyms;
380   cref_hash_traverse (&cref_table, cref_fill_array, &csym_fill);
381   ASSERT ((size_t) (csym_fill - csyms) == cref_symcount);
382
383   qsort (csyms, cref_symcount, sizeof (*csyms), cref_sort_array);
384
385   csym_end = csyms + cref_symcount;
386   for (csym = csyms; csym < csym_end; csym++)
387     output_one_cref (fp, *csym);
388 }
389
390 /* Output one entry in the cross reference table.  */
391
392 static void
393 output_one_cref (FILE *fp, struct cref_hash_entry *h)
394 {
395   int len;
396   struct bfd_link_hash_entry *hl;
397   struct cref_ref *r;
398
399   hl = bfd_link_hash_lookup (link_info.hash, h->root.string, FALSE,
400                              FALSE, TRUE);
401   if (hl == NULL)
402     einfo ("%P: symbol `%T' missing from main hash table\n",
403            h->root.string);
404   else
405     {
406       /* If this symbol is defined in a dynamic object but never
407          referenced by a normal object, then don't print it.  */
408       if (hl->type == bfd_link_hash_defined)
409         {
410           if (hl->u.def.section->output_section == NULL)
411             return;
412           if (hl->u.def.section->owner != NULL
413               && (hl->u.def.section->owner->flags & DYNAMIC) != 0)
414             {
415               for (r = h->refs; r != NULL; r = r->next)
416                 if ((r->abfd->flags & DYNAMIC) == 0)
417                   break;
418               if (r == NULL)
419                 return;
420             }
421         }
422     }
423
424   fprintf (fp, "%s ", h->demangled);
425   len = strlen (h->demangled) + 1;
426
427   for (r = h->refs; r != NULL; r = r->next)
428     {
429       if (r->def)
430         {
431           while (len < FILECOL)
432             {
433               putc (' ', fp);
434               ++len;
435             }
436           lfinfo (fp, "%B\n", r->abfd);
437           len = 0;
438         }
439     }
440
441   for (r = h->refs; r != NULL; r = r->next)
442     {
443       if (! r->def)
444         {
445           while (len < FILECOL)
446             {
447               putc (' ', fp);
448               ++len;
449             }
450           lfinfo (fp, "%B\n", r->abfd);
451           len = 0;
452         }
453     }
454
455   ASSERT (len == 0);
456 }
457
458 /* Check for prohibited cross references.  */
459
460 void
461 check_nocrossrefs (void)
462 {
463   if (! cref_initialized)
464     return;
465
466   cref_hash_traverse (&cref_table, check_nocrossref, NULL);
467
468   lang_for_each_file (check_local_sym_xref);
469 }
470
471 /* Check for prohibited cross references to local and section symbols.  */
472
473 static void
474 check_local_sym_xref (lang_input_statement_type *statement)
475 {
476   bfd *abfd;
477   lang_input_statement_type *li;
478   asymbol **asymbols, **syms;
479
480   abfd = statement->the_bfd;
481   if (abfd == NULL)
482     return;
483
484   li = abfd->usrdata;
485   if (li != NULL && li->asymbols != NULL)
486     asymbols = li->asymbols;
487   else
488     {
489       long symsize;
490       long symbol_count;
491
492       symsize = bfd_get_symtab_upper_bound (abfd);
493       if (symsize < 0)
494         einfo (_("%B%F: could not read symbols; %E\n"), abfd);
495       asymbols = xmalloc (symsize);
496       symbol_count = bfd_canonicalize_symtab (abfd, asymbols);
497       if (symbol_count < 0)
498         einfo (_("%B%F: could not read symbols: %E\n"), abfd);
499       if (li != NULL)
500         {
501           li->asymbols = asymbols;
502           li->symbol_count = symbol_count;
503         }
504     }
505
506   for (syms = asymbols; *syms; ++syms)
507     {
508       asymbol *sym = *syms;
509       if (sym->flags & (BSF_GLOBAL | BSF_WARNING | BSF_INDIRECT | BSF_FILE))
510         continue;
511       if ((sym->flags & (BSF_LOCAL | BSF_SECTION_SYM)) != 0
512           && sym->section->output_section != NULL)
513         {
514           const char *outsecname, *symname;
515           struct lang_nocrossrefs *ncrs;
516           struct lang_nocrossref *ncr;
517
518           outsecname = sym->section->output_section->name;
519           symname = NULL;
520           if ((sym->flags & BSF_SECTION_SYM) == 0)
521             symname = sym->name;
522           for (ncrs = nocrossref_list; ncrs != NULL; ncrs = ncrs->next)
523             for (ncr = ncrs->list; ncr != NULL; ncr = ncr->next)
524               if (strcmp (ncr->name, outsecname) == 0)
525                 check_refs (symname, FALSE, sym->section, abfd, ncrs);
526         }
527     }
528
529   if (li == NULL)
530     free (asymbols);
531 }
532
533 /* Check one symbol to see if it is a prohibited cross reference.  */
534
535 static bfd_boolean
536 check_nocrossref (struct cref_hash_entry *h, void *ignore ATTRIBUTE_UNUSED)
537 {
538   struct bfd_link_hash_entry *hl;
539   asection *defsec;
540   const char *defsecname;
541   struct lang_nocrossrefs *ncrs;
542   struct lang_nocrossref *ncr;
543   struct cref_ref *ref;
544
545   hl = bfd_link_hash_lookup (link_info.hash, h->root.string, FALSE,
546                              FALSE, TRUE);
547   if (hl == NULL)
548     {
549       einfo (_("%P: symbol `%T' missing from main hash table\n"),
550              h->root.string);
551       return TRUE;
552     }
553
554   if (hl->type != bfd_link_hash_defined
555       && hl->type != bfd_link_hash_defweak)
556     return TRUE;
557
558   defsec = hl->u.def.section->output_section;
559   if (defsec == NULL)
560     return TRUE;
561   defsecname = bfd_get_section_name (defsec->owner, defsec);
562
563   for (ncrs = nocrossref_list; ncrs != NULL; ncrs = ncrs->next)
564     for (ncr = ncrs->list; ncr != NULL; ncr = ncr->next)
565       if (strcmp (ncr->name, defsecname) == 0)
566         for (ref = h->refs; ref != NULL; ref = ref->next)
567           check_refs (hl->root.string, TRUE, hl->u.def.section,
568                       ref->abfd, ncrs);
569
570   return TRUE;
571 }
572
573 /* The struct is used to pass information from check_refs to
574    check_reloc_refs through bfd_map_over_sections.  */
575
576 struct check_refs_info {
577   const char *sym_name;
578   asection *defsec;
579   struct lang_nocrossrefs *ncrs;
580   asymbol **asymbols;
581   bfd_boolean global;
582 };
583
584 /* This function is called for each symbol defined in a section which
585    prohibits cross references.  We need to look through all references
586    to this symbol, and ensure that the references are not from
587    prohibited sections.  */
588
589 static void
590 check_refs (const char *name,
591             bfd_boolean global,
592             asection *sec,
593             bfd *abfd,
594             struct lang_nocrossrefs *ncrs)
595 {
596   lang_input_statement_type *li;
597   asymbol **asymbols;
598   struct check_refs_info info;
599
600   /* We need to look through the relocations for this BFD, to see
601      if any of the relocations which refer to this symbol are from
602      a prohibited section.  Note that we need to do this even for
603      the BFD in which the symbol is defined, since even a single
604      BFD might contain a prohibited cross reference.  */
605
606   li = abfd->usrdata;
607   if (li != NULL && li->asymbols != NULL)
608     asymbols = li->asymbols;
609   else
610     {
611       long symsize;
612       long symbol_count;
613
614       symsize = bfd_get_symtab_upper_bound (abfd);
615       if (symsize < 0)
616         einfo (_("%B%F: could not read symbols; %E\n"), abfd);
617       asymbols = xmalloc (symsize);
618       symbol_count = bfd_canonicalize_symtab (abfd, asymbols);
619       if (symbol_count < 0)
620         einfo (_("%B%F: could not read symbols: %E\n"), abfd);
621       if (li != NULL)
622         {
623           li->asymbols = asymbols;
624           li->symbol_count = symbol_count;
625         }
626     }
627
628   info.sym_name = name;
629   info.global = global;
630   info.defsec = sec;
631   info.ncrs = ncrs;
632   info.asymbols = asymbols;
633   bfd_map_over_sections (abfd, check_reloc_refs, &info);
634
635   if (li == NULL)
636     free (asymbols);
637 }
638
639 /* This is called via bfd_map_over_sections.  INFO->SYM_NAME is a symbol
640    defined in INFO->DEFSECNAME.  If this section maps into any of the
641    sections listed in INFO->NCRS, other than INFO->DEFSECNAME, then we
642    look through the relocations.  If any of the relocations are to
643    INFO->SYM_NAME, then we report a prohibited cross reference error.  */
644
645 static void
646 check_reloc_refs (bfd *abfd, asection *sec, void *iarg)
647 {
648   struct check_refs_info *info = iarg;
649   asection *outsec;
650   const char *outsecname;
651   asection *outdefsec;
652   const char *outdefsecname;
653   struct lang_nocrossref *ncr;
654   const char *symname;
655   bfd_boolean global;
656   long relsize;
657   arelent **relpp;
658   long relcount;
659   arelent **p, **pend;
660
661   outsec = sec->output_section;
662   outsecname = bfd_get_section_name (outsec->owner, outsec);
663
664   outdefsec = info->defsec->output_section;
665   outdefsecname = bfd_get_section_name (outdefsec->owner, outdefsec);
666
667   /* The section where the symbol is defined is permitted.  */
668   if (strcmp (outsecname, outdefsecname) == 0)
669     return;
670
671   for (ncr = info->ncrs->list; ncr != NULL; ncr = ncr->next)
672     if (strcmp (outsecname, ncr->name) == 0)
673       break;
674
675   if (ncr == NULL)
676     return;
677
678   /* This section is one for which cross references are prohibited.
679      Look through the relocations, and see if any of them are to
680      INFO->SYM_NAME.  If INFO->SYMNAME is NULL, check for relocations
681      against the section symbol.  If INFO->GLOBAL is TRUE, the
682      definition is global, check for relocations against the global
683      symbols.  Otherwise check for relocations against the local and
684      section symbols.  */
685
686   symname = info->sym_name;
687   global = info->global;
688
689   relsize = bfd_get_reloc_upper_bound (abfd, sec);
690   if (relsize < 0)
691     einfo (_("%B%F: could not read relocs: %E\n"), abfd);
692   if (relsize == 0)
693     return;
694
695   relpp = xmalloc (relsize);
696   relcount = bfd_canonicalize_reloc (abfd, sec, relpp, info->asymbols);
697   if (relcount < 0)
698     einfo (_("%B%F: could not read relocs: %E\n"), abfd);
699
700   p = relpp;
701   pend = p + relcount;
702   for (; p < pend && *p != NULL; p++)
703     {
704       arelent *q = *p;
705
706       if (q->sym_ptr_ptr != NULL
707           && *q->sym_ptr_ptr != NULL
708           && ((global
709                && (bfd_is_und_section (bfd_get_section (*q->sym_ptr_ptr))
710                    || bfd_is_com_section (bfd_get_section (*q->sym_ptr_ptr))
711                    || ((*q->sym_ptr_ptr)->flags & (BSF_GLOBAL
712                                                    | BSF_WEAK)) != 0))
713               || (!global
714                   && ((*q->sym_ptr_ptr)->flags & (BSF_LOCAL
715                                                   | BSF_SECTION_SYM)) != 0
716                   && bfd_get_section (*q->sym_ptr_ptr) == info->defsec))
717           && (symname != NULL
718               ? strcmp (bfd_asymbol_name (*q->sym_ptr_ptr), symname) == 0
719               : ((*q->sym_ptr_ptr)->flags & BSF_SECTION_SYM) != 0))
720         {
721           /* We found a reloc for the symbol.  The symbol is defined
722              in OUTSECNAME.  This reloc is from a section which is
723              mapped into a section from which references to OUTSECNAME
724              are prohibited.  We must report an error.  */
725           einfo (_("%X%C: prohibited cross reference from %s to `%T' in %s\n"),
726                  abfd, sec, q->address, outsecname,
727                  bfd_asymbol_name (*q->sym_ptr_ptr), outdefsecname);
728         }
729     }
730
731   free (relpp);
732 }