Merge branch 'vendor/LESS'
[dragonfly.git] / contrib / binutils-2.20 / ld / ldcref.c
1 /* ldcref.c -- output a cross reference table
2    Copyright 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006,
3    2007, 2008  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 = (struct cref_ref *) 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 = (struct cref_hash_entry ***) data;
328
329   ASSERT (h->demangled == NULL);
330   h->demangled = bfd_demangle (link_info.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 =
348       (const struct cref_hash_entry * const *) a1;
349   const struct cref_hash_entry * const *p2 =
350       (const struct cref_hash_entry * const *) a2;
351
352   return strcmp ((*p1)->demangled, (*p2)->demangled);
353 }
354
355 /* Write out the cref table.  */
356
357 #define FILECOL (50)
358
359 void
360 output_cref (FILE *fp)
361 {
362   int len;
363   struct cref_hash_entry **csyms, **csym_fill, **csym, **csym_end;
364   const char *msg;
365
366   fprintf (fp, _("\nCross Reference Table\n\n"));
367   msg = _("Symbol");
368   fprintf (fp, "%s", msg);
369   len = strlen (msg);
370   while (len < FILECOL)
371     {
372       putc (' ', fp);
373       ++len;
374     }
375   fprintf (fp, _("File\n"));
376
377   if (! cref_initialized)
378     {
379       fprintf (fp, _("No symbols\n"));
380       return;
381     }
382
383   csyms = (struct cref_hash_entry **) xmalloc (cref_symcount * sizeof (*csyms));
384
385   csym_fill = csyms;
386   cref_hash_traverse (&cref_table, cref_fill_array, &csym_fill);
387   ASSERT ((size_t) (csym_fill - csyms) == cref_symcount);
388
389   qsort (csyms, cref_symcount, sizeof (*csyms), cref_sort_array);
390
391   csym_end = csyms + cref_symcount;
392   for (csym = csyms; csym < csym_end; csym++)
393     output_one_cref (fp, *csym);
394 }
395
396 /* Output one entry in the cross reference table.  */
397
398 static void
399 output_one_cref (FILE *fp, struct cref_hash_entry *h)
400 {
401   int len;
402   struct bfd_link_hash_entry *hl;
403   struct cref_ref *r;
404
405   hl = bfd_link_hash_lookup (link_info.hash, h->root.string, FALSE,
406                              FALSE, TRUE);
407   if (hl == NULL)
408     einfo ("%P: symbol `%T' missing from main hash table\n",
409            h->root.string);
410   else
411     {
412       /* If this symbol is defined in a dynamic object but never
413          referenced by a normal object, then don't print it.  */
414       if (hl->type == bfd_link_hash_defined)
415         {
416           if (hl->u.def.section->output_section == NULL)
417             return;
418           if (hl->u.def.section->owner != NULL
419               && (hl->u.def.section->owner->flags & DYNAMIC) != 0)
420             {
421               for (r = h->refs; r != NULL; r = r->next)
422                 if ((r->abfd->flags & DYNAMIC) == 0)
423                   break;
424               if (r == NULL)
425                 return;
426             }
427         }
428     }
429
430   fprintf (fp, "%s ", h->demangled);
431   len = strlen (h->demangled) + 1;
432
433   for (r = h->refs; r != NULL; r = r->next)
434     {
435       if (r->def)
436         {
437           while (len < FILECOL)
438             {
439               putc (' ', fp);
440               ++len;
441             }
442           lfinfo (fp, "%B\n", r->abfd);
443           len = 0;
444         }
445     }
446
447   for (r = h->refs; r != NULL; r = r->next)
448     {
449       if (! r->def)
450         {
451           while (len < FILECOL)
452             {
453               putc (' ', fp);
454               ++len;
455             }
456           lfinfo (fp, "%B\n", r->abfd);
457           len = 0;
458         }
459     }
460
461   ASSERT (len == 0);
462 }
463
464 /* Check for prohibited cross references.  */
465
466 void
467 check_nocrossrefs (void)
468 {
469   if (! cref_initialized)
470     return;
471
472   cref_hash_traverse (&cref_table, check_nocrossref, NULL);
473
474   lang_for_each_file (check_local_sym_xref);
475 }
476
477 /* Check for prohibited cross references to local and section symbols.  */
478
479 static void
480 check_local_sym_xref (lang_input_statement_type *statement)
481 {
482   bfd *abfd;
483   asymbol **syms;
484
485   abfd = statement->the_bfd;
486   if (abfd == NULL)
487     return;
488
489   if (!bfd_generic_link_read_symbols (abfd))
490     einfo (_("%B%F: could not read symbols: %E\n"), abfd);
491
492   for (syms = bfd_get_outsymbols (abfd); *syms; ++syms)
493     {
494       asymbol *sym = *syms;
495       if (sym->flags & (BSF_GLOBAL | BSF_WARNING | BSF_INDIRECT | BSF_FILE))
496         continue;
497       if ((sym->flags & (BSF_LOCAL | BSF_SECTION_SYM)) != 0
498           && sym->section->output_section != NULL)
499         {
500           const char *outsecname, *symname;
501           struct lang_nocrossrefs *ncrs;
502           struct lang_nocrossref *ncr;
503
504           outsecname = sym->section->output_section->name;
505           symname = NULL;
506           if ((sym->flags & BSF_SECTION_SYM) == 0)
507             symname = sym->name;
508           for (ncrs = nocrossref_list; ncrs != NULL; ncrs = ncrs->next)
509             for (ncr = ncrs->list; ncr != NULL; ncr = ncr->next)
510               if (strcmp (ncr->name, outsecname) == 0)
511                 check_refs (symname, FALSE, sym->section, abfd, ncrs);
512         }
513     }
514 }
515
516 /* Check one symbol to see if it is a prohibited cross reference.  */
517
518 static bfd_boolean
519 check_nocrossref (struct cref_hash_entry *h, void *ignore ATTRIBUTE_UNUSED)
520 {
521   struct bfd_link_hash_entry *hl;
522   asection *defsec;
523   const char *defsecname;
524   struct lang_nocrossrefs *ncrs;
525   struct lang_nocrossref *ncr;
526   struct cref_ref *ref;
527
528   hl = bfd_link_hash_lookup (link_info.hash, h->root.string, FALSE,
529                              FALSE, TRUE);
530   if (hl == NULL)
531     {
532       einfo (_("%P: symbol `%T' missing from main hash table\n"),
533              h->root.string);
534       return TRUE;
535     }
536
537   if (hl->type != bfd_link_hash_defined
538       && hl->type != bfd_link_hash_defweak)
539     return TRUE;
540
541   defsec = hl->u.def.section->output_section;
542   if (defsec == NULL)
543     return TRUE;
544   defsecname = bfd_get_section_name (defsec->owner, defsec);
545
546   for (ncrs = nocrossref_list; ncrs != NULL; ncrs = ncrs->next)
547     for (ncr = ncrs->list; ncr != NULL; ncr = ncr->next)
548       if (strcmp (ncr->name, defsecname) == 0)
549         for (ref = h->refs; ref != NULL; ref = ref->next)
550           check_refs (hl->root.string, TRUE, hl->u.def.section,
551                       ref->abfd, ncrs);
552
553   return TRUE;
554 }
555
556 /* The struct is used to pass information from check_refs to
557    check_reloc_refs through bfd_map_over_sections.  */
558
559 struct check_refs_info {
560   const char *sym_name;
561   asection *defsec;
562   struct lang_nocrossrefs *ncrs;
563   asymbol **asymbols;
564   bfd_boolean global;
565 };
566
567 /* This function is called for each symbol defined in a section which
568    prohibits cross references.  We need to look through all references
569    to this symbol, and ensure that the references are not from
570    prohibited sections.  */
571
572 static void
573 check_refs (const char *name,
574             bfd_boolean global,
575             asection *sec,
576             bfd *abfd,
577             struct lang_nocrossrefs *ncrs)
578 {
579   struct check_refs_info info;
580
581   /* We need to look through the relocations for this BFD, to see
582      if any of the relocations which refer to this symbol are from
583      a prohibited section.  Note that we need to do this even for
584      the BFD in which the symbol is defined, since even a single
585      BFD might contain a prohibited cross reference.  */
586
587   if (!bfd_generic_link_read_symbols (abfd))
588     einfo (_("%B%F: could not read symbols: %E\n"), abfd);
589
590   info.sym_name = name;
591   info.global = global;
592   info.defsec = sec;
593   info.ncrs = ncrs;
594   info.asymbols = bfd_get_outsymbols (abfd);
595   bfd_map_over_sections (abfd, check_reloc_refs, &info);
596 }
597
598 /* This is called via bfd_map_over_sections.  INFO->SYM_NAME is a symbol
599    defined in INFO->DEFSECNAME.  If this section maps into any of the
600    sections listed in INFO->NCRS, other than INFO->DEFSECNAME, then we
601    look through the relocations.  If any of the relocations are to
602    INFO->SYM_NAME, then we report a prohibited cross reference error.  */
603
604 static void
605 check_reloc_refs (bfd *abfd, asection *sec, void *iarg)
606 {
607   struct check_refs_info *info = (struct check_refs_info *) iarg;
608   asection *outsec;
609   const char *outsecname;
610   asection *outdefsec;
611   const char *outdefsecname;
612   struct lang_nocrossref *ncr;
613   const char *symname;
614   bfd_boolean global;
615   long relsize;
616   arelent **relpp;
617   long relcount;
618   arelent **p, **pend;
619
620   outsec = sec->output_section;
621   outsecname = bfd_get_section_name (outsec->owner, outsec);
622
623   outdefsec = info->defsec->output_section;
624   outdefsecname = bfd_get_section_name (outdefsec->owner, outdefsec);
625
626   /* The section where the symbol is defined is permitted.  */
627   if (strcmp (outsecname, outdefsecname) == 0)
628     return;
629
630   for (ncr = info->ncrs->list; ncr != NULL; ncr = ncr->next)
631     if (strcmp (outsecname, ncr->name) == 0)
632       break;
633
634   if (ncr == NULL)
635     return;
636
637   /* This section is one for which cross references are prohibited.
638      Look through the relocations, and see if any of them are to
639      INFO->SYM_NAME.  If INFO->SYMNAME is NULL, check for relocations
640      against the section symbol.  If INFO->GLOBAL is TRUE, the
641      definition is global, check for relocations against the global
642      symbols.  Otherwise check for relocations against the local and
643      section symbols.  */
644
645   symname = info->sym_name;
646   global = info->global;
647
648   relsize = bfd_get_reloc_upper_bound (abfd, sec);
649   if (relsize < 0)
650     einfo (_("%B%F: could not read relocs: %E\n"), abfd);
651   if (relsize == 0)
652     return;
653
654   relpp = (arelent **) xmalloc (relsize);
655   relcount = bfd_canonicalize_reloc (abfd, sec, relpp, info->asymbols);
656   if (relcount < 0)
657     einfo (_("%B%F: could not read relocs: %E\n"), abfd);
658
659   p = relpp;
660   pend = p + relcount;
661   for (; p < pend && *p != NULL; p++)
662     {
663       arelent *q = *p;
664
665       if (q->sym_ptr_ptr != NULL
666           && *q->sym_ptr_ptr != NULL
667           && ((global
668                && (bfd_is_und_section (bfd_get_section (*q->sym_ptr_ptr))
669                    || bfd_is_com_section (bfd_get_section (*q->sym_ptr_ptr))
670                    || ((*q->sym_ptr_ptr)->flags & (BSF_GLOBAL
671                                                    | BSF_WEAK)) != 0))
672               || (!global
673                   && ((*q->sym_ptr_ptr)->flags & (BSF_LOCAL
674                                                   | BSF_SECTION_SYM)) != 0
675                   && bfd_get_section (*q->sym_ptr_ptr) == info->defsec))
676           && (symname != NULL
677               ? strcmp (bfd_asymbol_name (*q->sym_ptr_ptr), symname) == 0
678               : ((*q->sym_ptr_ptr)->flags & BSF_SECTION_SYM) != 0))
679         {
680           /* We found a reloc for the symbol.  The symbol is defined
681              in OUTSECNAME.  This reloc is from a section which is
682              mapped into a section from which references to OUTSECNAME
683              are prohibited.  We must report an error.  */
684           einfo (_("%X%C: prohibited cross reference from %s to `%T' in %s\n"),
685                  abfd, sec, q->address, outsecname,
686                  bfd_asymbol_name (*q->sym_ptr_ptr), outdefsecname);
687         }
688     }
689
690   free (relpp);
691 }