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 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;
582   asection *defsec;
583   struct lang_nocrossrefs *ncrs;
584   asymbol **asymbols;
585   bfd_boolean global;
586 };
587
588 /* This function is called for each symbol defined in a section which
589    prohibits cross references.  We need to look through all references
590    to this symbol, and ensure that the references are not from
591    prohibited sections.  */
592
593 static void
594 check_refs (const char *name,
595             bfd_boolean global,
596             asection *sec,
597             bfd *abfd,
598             struct lang_nocrossrefs *ncrs)
599 {
600   lang_input_statement_type *li;
601   asymbol **asymbols;
602   struct check_refs_info info;
603
604   /* We need to look through the relocations for this BFD, to see
605      if any of the relocations which refer to this symbol are from
606      a prohibited section.  Note that we need to do this even for
607      the BFD in which the symbol is defined, since even a single
608      BFD might contain a prohibited cross reference.  */
609
610   li = abfd->usrdata;
611   if (li != NULL && li->asymbols != NULL)
612     asymbols = li->asymbols;
613   else
614     {
615       long symsize;
616       long symbol_count;
617
618       symsize = bfd_get_symtab_upper_bound (abfd);
619       if (symsize < 0)
620         einfo (_("%B%F: could not read symbols; %E\n"), abfd);
621       asymbols = xmalloc (symsize);
622       symbol_count = bfd_canonicalize_symtab (abfd, asymbols);
623       if (symbol_count < 0)
624         einfo (_("%B%F: could not read symbols: %E\n"), abfd);
625       if (li != NULL)
626         {
627           li->asymbols = asymbols;
628           li->symbol_count = symbol_count;
629         }
630     }
631
632   info.sym_name = name;
633   info.global = global;
634   info.defsec = sec;
635   info.ncrs = ncrs;
636   info.asymbols = asymbols;
637   bfd_map_over_sections (abfd, check_reloc_refs, &info);
638
639   if (li == NULL)
640     free (asymbols);
641 }
642
643 /* This is called via bfd_map_over_sections.  INFO->SYM_NAME is a symbol
644    defined in INFO->DEFSECNAME.  If this section maps into any of the
645    sections listed in INFO->NCRS, other than INFO->DEFSECNAME, then we
646    look through the relocations.  If any of the relocations are to
647    INFO->SYM_NAME, then we report a prohibited cross reference error.  */
648
649 static void
650 check_reloc_refs (bfd *abfd, asection *sec, void *iarg)
651 {
652   struct check_refs_info *info = iarg;
653   asection *outsec;
654   const char *outsecname;
655   asection *outdefsec;
656   const char *outdefsecname;
657   struct lang_nocrossref *ncr;
658   const char *symname;
659   bfd_boolean global;
660   long relsize;
661   arelent **relpp;
662   long relcount;
663   arelent **p, **pend;
664
665   outsec = sec->output_section;
666   outsecname = bfd_get_section_name (outsec->owner, outsec);
667
668   outdefsec = info->defsec->output_section;
669   outdefsecname = bfd_get_section_name (outdefsec->owner, outdefsec);
670
671   /* The section where the symbol is defined is permitted.  */
672   if (strcmp (outsecname, outdefsecname) == 0)
673     return;
674
675   for (ncr = info->ncrs->list; ncr != NULL; ncr = ncr->next)
676     if (strcmp (outsecname, ncr->name) == 0)
677       break;
678
679   if (ncr == NULL)
680     return;
681
682   /* This section is one for which cross references are prohibited.
683      Look through the relocations, and see if any of them are to
684      INFO->SYM_NAME.  If INFO->SYMNAME is NULL, check for relocations
685      against the section symbol.  If INFO->GLOBAL is TRUE, the
686      definition is global, check for relocations against the global
687      symbols.  Otherwise check for relocations against the local and
688      section symbols.  */
689
690   symname = info->sym_name;
691   global = info->global;
692
693   relsize = bfd_get_reloc_upper_bound (abfd, sec);
694   if (relsize < 0)
695     einfo (_("%B%F: could not read relocs: %E\n"), abfd);
696   if (relsize == 0)
697     return;
698
699   relpp = xmalloc (relsize);
700   relcount = bfd_canonicalize_reloc (abfd, sec, relpp, info->asymbols);
701   if (relcount < 0)
702     einfo (_("%B%F: could not read relocs: %E\n"), abfd);
703
704   p = relpp;
705   pend = p + relcount;
706   for (; p < pend && *p != NULL; p++)
707     {
708       arelent *q = *p;
709
710       if (q->sym_ptr_ptr != NULL
711           && *q->sym_ptr_ptr != NULL
712           && ((global
713                && (bfd_is_und_section (bfd_get_section (*q->sym_ptr_ptr))
714                    || bfd_is_com_section (bfd_get_section (*q->sym_ptr_ptr))
715                    || ((*q->sym_ptr_ptr)->flags & (BSF_GLOBAL
716                                                    | BSF_WEAK)) != 0))
717               || (!global
718                   && ((*q->sym_ptr_ptr)->flags & (BSF_LOCAL
719                                                   | BSF_SECTION_SYM)) != 0
720                   && bfd_get_section (*q->sym_ptr_ptr) == info->defsec))
721           && (symname != NULL
722               ? strcmp (bfd_asymbol_name (*q->sym_ptr_ptr), symname) == 0
723               : ((*q->sym_ptr_ptr)->flags & BSF_SECTION_SYM) != 0))
724         {
725           /* We found a reloc for the symbol.  The symbol is defined
726              in OUTSECNAME.  This reloc is from a section which is
727              mapped into a section from which references to OUTSECNAME
728              are prohibited.  We must report an error.  */
729           einfo (_("%X%C: prohibited cross reference from %s to `%T' in %s\n"),
730                  abfd, sec, q->address, outsecname,
731                  bfd_asymbol_name (*q->sym_ptr_ptr), outdefsecname);
732         }
733     }
734
735   free (relpp);
736 }