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