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