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