update copyright dates
[platform/upstream/binutils.git] / 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 = 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 (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 = 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   asymbol **syms;
482
483   abfd = statement->the_bfd;
484   if (abfd == NULL)
485     return;
486
487   if (!bfd_generic_link_read_symbols (abfd))
488     einfo (_("%B%F: could not read symbols: %E\n"), abfd);
489
490   for (syms = bfd_get_outsymbols (abfd); *syms; ++syms)
491     {
492       asymbol *sym = *syms;
493       if (sym->flags & (BSF_GLOBAL | BSF_WARNING | BSF_INDIRECT | BSF_FILE))
494         continue;
495       if ((sym->flags & (BSF_LOCAL | BSF_SECTION_SYM)) != 0
496           && sym->section->output_section != NULL)
497         {
498           const char *outsecname, *symname;
499           struct lang_nocrossrefs *ncrs;
500           struct lang_nocrossref *ncr;
501
502           outsecname = sym->section->output_section->name;
503           symname = NULL;
504           if ((sym->flags & BSF_SECTION_SYM) == 0)
505             symname = sym->name;
506           for (ncrs = nocrossref_list; ncrs != NULL; ncrs = ncrs->next)
507             for (ncr = ncrs->list; ncr != NULL; ncr = ncr->next)
508               if (strcmp (ncr->name, outsecname) == 0)
509                 check_refs (symname, FALSE, sym->section, abfd, ncrs);
510         }
511     }
512 }
513
514 /* Check one symbol to see if it is a prohibited cross reference.  */
515
516 static bfd_boolean
517 check_nocrossref (struct cref_hash_entry *h, void *ignore ATTRIBUTE_UNUSED)
518 {
519   struct bfd_link_hash_entry *hl;
520   asection *defsec;
521   const char *defsecname;
522   struct lang_nocrossrefs *ncrs;
523   struct lang_nocrossref *ncr;
524   struct cref_ref *ref;
525
526   hl = bfd_link_hash_lookup (link_info.hash, h->root.string, FALSE,
527                              FALSE, TRUE);
528   if (hl == NULL)
529     {
530       einfo (_("%P: symbol `%T' missing from main hash table\n"),
531              h->root.string);
532       return TRUE;
533     }
534
535   if (hl->type != bfd_link_hash_defined
536       && hl->type != bfd_link_hash_defweak)
537     return TRUE;
538
539   defsec = hl->u.def.section->output_section;
540   if (defsec == NULL)
541     return TRUE;
542   defsecname = bfd_get_section_name (defsec->owner, defsec);
543
544   for (ncrs = nocrossref_list; ncrs != NULL; ncrs = ncrs->next)
545     for (ncr = ncrs->list; ncr != NULL; ncr = ncr->next)
546       if (strcmp (ncr->name, defsecname) == 0)
547         for (ref = h->refs; ref != NULL; ref = ref->next)
548           check_refs (hl->root.string, TRUE, hl->u.def.section,
549                       ref->abfd, ncrs);
550
551   return TRUE;
552 }
553
554 /* The struct is used to pass information from check_refs to
555    check_reloc_refs through bfd_map_over_sections.  */
556
557 struct check_refs_info {
558   const char *sym_name;
559   asection *defsec;
560   struct lang_nocrossrefs *ncrs;
561   asymbol **asymbols;
562   bfd_boolean global;
563 };
564
565 /* This function is called for each symbol defined in a section which
566    prohibits cross references.  We need to look through all references
567    to this symbol, and ensure that the references are not from
568    prohibited sections.  */
569
570 static void
571 check_refs (const char *name,
572             bfd_boolean global,
573             asection *sec,
574             bfd *abfd,
575             struct lang_nocrossrefs *ncrs)
576 {
577   struct check_refs_info info;
578
579   /* We need to look through the relocations for this BFD, to see
580      if any of the relocations which refer to this symbol are from
581      a prohibited section.  Note that we need to do this even for
582      the BFD in which the symbol is defined, since even a single
583      BFD might contain a prohibited cross reference.  */
584
585   if (!bfd_generic_link_read_symbols (abfd))
586     einfo (_("%B%F: could not read symbols: %E\n"), abfd);
587
588   info.sym_name = name;
589   info.global = global;
590   info.defsec = sec;
591   info.ncrs = ncrs;
592   info.asymbols = bfd_get_outsymbols (abfd);
593   bfd_map_over_sections (abfd, check_reloc_refs, &info);
594 }
595
596 /* This is called via bfd_map_over_sections.  INFO->SYM_NAME is a symbol
597    defined in INFO->DEFSECNAME.  If this section maps into any of the
598    sections listed in INFO->NCRS, other than INFO->DEFSECNAME, then we
599    look through the relocations.  If any of the relocations are to
600    INFO->SYM_NAME, then we report a prohibited cross reference error.  */
601
602 static void
603 check_reloc_refs (bfd *abfd, asection *sec, void *iarg)
604 {
605   struct check_refs_info *info = iarg;
606   asection *outsec;
607   const char *outsecname;
608   asection *outdefsec;
609   const char *outdefsecname;
610   struct lang_nocrossref *ncr;
611   const char *symname;
612   bfd_boolean global;
613   long relsize;
614   arelent **relpp;
615   long relcount;
616   arelent **p, **pend;
617
618   outsec = sec->output_section;
619   outsecname = bfd_get_section_name (outsec->owner, outsec);
620
621   outdefsec = info->defsec->output_section;
622   outdefsecname = bfd_get_section_name (outdefsec->owner, outdefsec);
623
624   /* The section where the symbol is defined is permitted.  */
625   if (strcmp (outsecname, outdefsecname) == 0)
626     return;
627
628   for (ncr = info->ncrs->list; ncr != NULL; ncr = ncr->next)
629     if (strcmp (outsecname, ncr->name) == 0)
630       break;
631
632   if (ncr == NULL)
633     return;
634
635   /* This section is one for which cross references are prohibited.
636      Look through the relocations, and see if any of them are to
637      INFO->SYM_NAME.  If INFO->SYMNAME is NULL, check for relocations
638      against the section symbol.  If INFO->GLOBAL is TRUE, the
639      definition is global, check for relocations against the global
640      symbols.  Otherwise check for relocations against the local and
641      section symbols.  */
642
643   symname = info->sym_name;
644   global = info->global;
645
646   relsize = bfd_get_reloc_upper_bound (abfd, sec);
647   if (relsize < 0)
648     einfo (_("%B%F: could not read relocs: %E\n"), abfd);
649   if (relsize == 0)
650     return;
651
652   relpp = xmalloc (relsize);
653   relcount = bfd_canonicalize_reloc (abfd, sec, relpp, info->asymbols);
654   if (relcount < 0)
655     einfo (_("%B%F: could not read relocs: %E\n"), abfd);
656
657   p = relpp;
658   pend = p + relcount;
659   for (; p < pend && *p != NULL; p++)
660     {
661       arelent *q = *p;
662
663       if (q->sym_ptr_ptr != NULL
664           && *q->sym_ptr_ptr != NULL
665           && ((global
666                && (bfd_is_und_section (bfd_get_section (*q->sym_ptr_ptr))
667                    || bfd_is_com_section (bfd_get_section (*q->sym_ptr_ptr))
668                    || ((*q->sym_ptr_ptr)->flags & (BSF_GLOBAL
669                                                    | BSF_WEAK)) != 0))
670               || (!global
671                   && ((*q->sym_ptr_ptr)->flags & (BSF_LOCAL
672                                                   | BSF_SECTION_SYM)) != 0
673                   && bfd_get_section (*q->sym_ptr_ptr) == info->defsec))
674           && (symname != NULL
675               ? strcmp (bfd_asymbol_name (*q->sym_ptr_ptr), symname) == 0
676               : ((*q->sym_ptr_ptr)->flags & BSF_SECTION_SYM) != 0))
677         {
678           /* We found a reloc for the symbol.  The symbol is defined
679              in OUTSECNAME.  This reloc is from a section which is
680              mapped into a section from which references to OUTSECNAME
681              are prohibited.  We must report an error.  */
682           einfo (_("%X%C: prohibited cross reference from %s to `%T' in %s\n"),
683                  abfd, sec, q->address, outsecname,
684                  bfd_asymbol_name (*q->sym_ptr_ptr), outdefsecname);
685         }
686     }
687
688   free (relpp);
689 }