1/* ldcref.c -- output a cross reference table
2   Copyright 1996, 1997, 1998, 2000, 2002, 2003
3   Free Software Foundation, Inc.
4   Written by Ian Lance Taylor <ian@cygnus.com>
5
6This file is part of GLD, the Gnu Linker.
7
8This program is free software; you can redistribute it and/or modify
9it under the terms of the GNU General Public License as published by
10the Free Software Foundation; either version 2 of the License, or
11(at your option) any later version.
12
13This program is distributed in the hope that it will be useful,
14but WITHOUT ANY WARRANTY; without even the implied warranty of
15MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16GNU General Public License for more details.
17
18You should have received a copy of the GNU General Public License
19along with this program; if not, write to the Free Software
20Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, 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
31#include "ld.h"
32#include "ldmain.h"
33#include "ldmisc.h"
34#include "ldexp.h"
35#include "ldlang.h"
36
37/* We keep an instance of this structure for each reference to a
38   symbol from a given object.  */
39
40struct cref_ref {
41  /* The next reference.  */
42  struct cref_ref *next;
43  /* The object.  */
44  bfd *abfd;
45  /* True if the symbol is defined.  */
46  unsigned int def : 1;
47  /* True if the symbol is common.  */
48  unsigned int common : 1;
49  /* True if the symbol is undefined.  */
50  unsigned int undef : 1;
51};
52
53/* We keep a hash table of symbols.  Each entry looks like this.  */
54
55struct cref_hash_entry {
56  struct bfd_hash_entry root;
57  /* The demangled name.  */
58  char *demangled;
59  /* References to and definitions of this symbol.  */
60  struct cref_ref *refs;
61};
62
63/* This is what the hash table looks like.  */
64
65struct cref_hash_table {
66  struct bfd_hash_table root;
67};
68
69/* Forward declarations.  */
70
71static void output_one_cref (FILE *, struct cref_hash_entry *);
72static void check_section_sym_xref (lang_input_statement_type *);
73static bfd_boolean check_nocrossref (struct cref_hash_entry *, void *);
74static void check_refs (const char *, asection *, bfd *,
75			struct lang_nocrossrefs *);
76static void check_reloc_refs (bfd *, asection *, void *);
77
78/* Look up an entry in the cref hash table.  */
79
80#define cref_hash_lookup(table, string, create, copy)		\
81  ((struct cref_hash_entry *)					\
82   bfd_hash_lookup (&(table)->root, (string), (create), (copy)))
83
84/* Traverse the cref hash table.  */
85
86#define cref_hash_traverse(table, func, info)				\
87  (bfd_hash_traverse							\
88   (&(table)->root,							\
89    (bfd_boolean (*) (struct bfd_hash_entry *, void *)) (func),		\
90    (info)))
91
92/* The cref hash table.  */
93
94static struct cref_hash_table cref_table;
95
96/* Whether the cref hash table has been initialized.  */
97
98static bfd_boolean cref_initialized;
99
100/* The number of symbols seen so far.  */
101
102static size_t cref_symcount;
103
104/* Create an entry in a cref hash table.  */
105
106static struct bfd_hash_entry *
107cref_hash_newfunc (struct bfd_hash_entry *entry,
108		   struct bfd_hash_table *table,
109		   const char *string)
110{
111  struct cref_hash_entry *ret = (struct cref_hash_entry *) entry;
112
113  /* Allocate the structure if it has not already been allocated by a
114     subclass.  */
115  if (ret == NULL)
116    ret = ((struct cref_hash_entry *)
117	   bfd_hash_allocate (table, sizeof (struct cref_hash_entry)));
118  if (ret == NULL)
119    return NULL;
120
121  /* Call the allocation method of the superclass.  */
122  ret = ((struct cref_hash_entry *)
123	 bfd_hash_newfunc ((struct bfd_hash_entry *) ret, table, string));
124  if (ret != NULL)
125    {
126      /* Set local fields.  */
127      ret->demangled = NULL;
128      ret->refs = NULL;
129
130      /* Keep a count of the number of entries created in the hash
131	 table.  */
132      ++cref_symcount;
133    }
134
135  return &ret->root;
136}
137
138/* Add a symbol to the cref hash table.  This is called for every
139   symbol that is seen during the link.  */
140
141void
142add_cref (const char *name,
143	  bfd *abfd,
144	  asection *section,
145	  bfd_vma value ATTRIBUTE_UNUSED)
146{
147  struct cref_hash_entry *h;
148  struct cref_ref *r;
149
150  if (! cref_initialized)
151    {
152      if (! bfd_hash_table_init (&cref_table.root, cref_hash_newfunc))
153	einfo (_("%X%P: bfd_hash_table_init of cref table failed: %E\n"));
154      cref_initialized = TRUE;
155    }
156
157  h = cref_hash_lookup (&cref_table, name, TRUE, FALSE);
158  if (h == NULL)
159    einfo (_("%X%P: cref_hash_lookup failed: %E\n"));
160
161  for (r = h->refs; r != NULL; r = r->next)
162    if (r->abfd == abfd)
163      break;
164
165  if (r == NULL)
166    {
167      r = xmalloc (sizeof *r);
168      r->next = h->refs;
169      h->refs = r;
170      r->abfd = abfd;
171      r->def = FALSE;
172      r->common = FALSE;
173      r->undef = FALSE;
174    }
175
176  if (bfd_is_und_section (section))
177    r->undef = TRUE;
178  else if (bfd_is_com_section (section))
179    r->common = TRUE;
180  else
181    r->def = TRUE;
182}
183
184/* Copy the addresses of the hash table entries into an array.  This
185   is called via cref_hash_traverse.  We also fill in the demangled
186   name.  */
187
188static bfd_boolean
189cref_fill_array (struct cref_hash_entry *h, void *data)
190{
191  struct cref_hash_entry ***pph = data;
192
193  ASSERT (h->demangled == NULL);
194  h->demangled = demangle (h->root.string);
195
196  **pph = h;
197
198  ++*pph;
199
200  return TRUE;
201}
202
203/* Sort an array of cref hash table entries by name.  */
204
205static int
206cref_sort_array (const void *a1, const void *a2)
207{
208  const struct cref_hash_entry * const *p1 = a1;
209  const struct cref_hash_entry * const *p2 = a2;
210
211  return strcmp ((*p1)->demangled, (*p2)->demangled);
212}
213
214/* Write out the cref table.  */
215
216#define FILECOL (50)
217
218void
219output_cref (FILE *fp)
220{
221  int len;
222  struct cref_hash_entry **csyms, **csym_fill, **csym, **csym_end;
223  const char *msg;
224
225  fprintf (fp, _("\nCross Reference Table\n\n"));
226  msg = _("Symbol");
227  fprintf (fp, "%s", msg);
228  len = strlen (msg);
229  while (len < FILECOL)
230    {
231      putc (' ', fp);
232      ++len;
233    }
234  fprintf (fp, _("File\n"));
235
236  if (! cref_initialized)
237    {
238      fprintf (fp, _("No symbols\n"));
239      return;
240    }
241
242  csyms = xmalloc (cref_symcount * sizeof (*csyms));
243
244  csym_fill = csyms;
245  cref_hash_traverse (&cref_table, cref_fill_array, &csym_fill);
246  ASSERT ((size_t) (csym_fill - csyms) == cref_symcount);
247
248  qsort (csyms, cref_symcount, sizeof (*csyms), cref_sort_array);
249
250  csym_end = csyms + cref_symcount;
251  for (csym = csyms; csym < csym_end; csym++)
252    output_one_cref (fp, *csym);
253}
254
255/* Output one entry in the cross reference table.  */
256
257static void
258output_one_cref (FILE *fp, struct cref_hash_entry *h)
259{
260  int len;
261  struct bfd_link_hash_entry *hl;
262  struct cref_ref *r;
263
264  hl = bfd_link_hash_lookup (link_info.hash, h->root.string, FALSE,
265			     FALSE, TRUE);
266  if (hl == NULL)
267    einfo ("%P: symbol `%T' missing from main hash table\n",
268	   h->root.string);
269  else
270    {
271      /* If this symbol is defined in a dynamic object but never
272	 referenced by a normal object, then don't print it.  */
273      if (hl->type == bfd_link_hash_defined)
274	{
275	  if (hl->u.def.section->output_section == NULL)
276	    return;
277	  if (hl->u.def.section->owner != NULL
278	      && (hl->u.def.section->owner->flags & DYNAMIC) != 0)
279	    {
280	      for (r = h->refs; r != NULL; r = r->next)
281		if ((r->abfd->flags & DYNAMIC) == 0)
282		  break;
283	      if (r == NULL)
284		return;
285	    }
286	}
287    }
288
289  fprintf (fp, "%s ", h->demangled);
290  len = strlen (h->demangled) + 1;
291
292  for (r = h->refs; r != NULL; r = r->next)
293    {
294      if (r->def)
295	{
296	  while (len < FILECOL)
297	    {
298	      putc (' ', fp);
299	      ++len;
300	    }
301	  lfinfo (fp, "%B\n", r->abfd);
302	  len = 0;
303	}
304    }
305
306  for (r = h->refs; r != NULL; r = r->next)
307    {
308      if (! r->def)
309	{
310	  while (len < FILECOL)
311	    {
312	      putc (' ', fp);
313	      ++len;
314	    }
315	  lfinfo (fp, "%B\n", r->abfd);
316	  len = 0;
317	}
318    }
319
320  ASSERT (len == 0);
321}
322
323/* Check for prohibited cross references.  */
324
325void
326check_nocrossrefs (void)
327{
328  if (! cref_initialized)
329    return;
330
331  cref_hash_traverse (&cref_table, check_nocrossref, NULL);
332
333  lang_for_each_file (check_section_sym_xref);
334}
335
336/* Checks for prohibited cross references to section symbols.  */
337
338static void
339check_section_sym_xref (lang_input_statement_type *statement)
340{
341  bfd *abfd;
342  asection *sec;
343
344  abfd = statement->the_bfd;
345  if (abfd == NULL)
346    return;
347
348  for (sec = abfd->sections; sec != NULL; sec = sec->next)
349    {
350      asection *outsec;
351
352      outsec = sec->output_section;
353      if (outsec != NULL)
354	{
355	  const char *outsecname;
356	  struct lang_nocrossrefs *ncrs;
357	  struct lang_nocrossref *ncr;
358
359	  outsecname = outsec->name;
360	  for (ncrs = nocrossref_list; ncrs != NULL; ncrs = ncrs->next)
361	    for (ncr = ncrs->list; ncr != NULL; ncr = ncr->next)
362	      if (strcmp (ncr->name, outsecname) == 0)
363		check_refs (NULL, sec, abfd, ncrs);
364	}
365    }
366}
367
368/* Check one symbol to see if it is a prohibited cross reference.  */
369
370static bfd_boolean
371check_nocrossref (struct cref_hash_entry *h, void *ignore ATTRIBUTE_UNUSED)
372{
373  struct bfd_link_hash_entry *hl;
374  asection *defsec;
375  const char *defsecname;
376  struct lang_nocrossrefs *ncrs;
377  struct lang_nocrossref *ncr;
378  struct cref_ref *ref;
379
380  hl = bfd_link_hash_lookup (link_info.hash, h->root.string, FALSE,
381			     FALSE, TRUE);
382  if (hl == NULL)
383    {
384      einfo (_("%P: symbol `%T' missing from main hash table\n"),
385	     h->root.string);
386      return TRUE;
387    }
388
389  if (hl->type != bfd_link_hash_defined
390      && hl->type != bfd_link_hash_defweak)
391    return TRUE;
392
393  defsec = hl->u.def.section->output_section;
394  if (defsec == NULL)
395    return TRUE;
396  defsecname = bfd_get_section_name (defsec->owner, defsec);
397
398  for (ncrs = nocrossref_list; ncrs != NULL; ncrs = ncrs->next)
399    for (ncr = ncrs->list; ncr != NULL; ncr = ncr->next)
400      if (strcmp (ncr->name, defsecname) == 0)
401	for (ref = h->refs; ref != NULL; ref = ref->next)
402	  check_refs (hl->root.string, hl->u.def.section, ref->abfd, ncrs);
403
404  return TRUE;
405}
406
407/* The struct is used to pass information from check_refs to
408   check_reloc_refs through bfd_map_over_sections.  */
409
410struct check_refs_info {
411  const char *sym_name;
412  asection *defsec;
413  struct lang_nocrossrefs *ncrs;
414  asymbol **asymbols;
415};
416
417/* This function is called for each symbol defined in a section which
418   prohibits cross references.  We need to look through all references
419   to this symbol, and ensure that the references are not from
420   prohibited sections.  */
421
422static void
423check_refs (const char *name,
424	    asection *sec,
425	    bfd *abfd,
426	    struct lang_nocrossrefs *ncrs)
427{
428  lang_input_statement_type *li;
429  asymbol **asymbols;
430  struct check_refs_info info;
431
432  /* We need to look through the relocations for this BFD, to see
433     if any of the relocations which refer to this symbol are from
434     a prohibited section.  Note that we need to do this even for
435     the BFD in which the symbol is defined, since even a single
436     BFD might contain a prohibited cross reference.  */
437
438  li = abfd->usrdata;
439  if (li != NULL && li->asymbols != NULL)
440    asymbols = li->asymbols;
441  else
442    {
443      long symsize;
444      long symbol_count;
445
446      symsize = bfd_get_symtab_upper_bound (abfd);
447      if (symsize < 0)
448	einfo (_("%B%F: could not read symbols; %E\n"), abfd);
449      asymbols = xmalloc (symsize);
450      symbol_count = bfd_canonicalize_symtab (abfd, asymbols);
451      if (symbol_count < 0)
452	einfo (_("%B%F: could not read symbols: %E\n"), abfd);
453      if (li != NULL)
454	{
455	  li->asymbols = asymbols;
456	  li->symbol_count = symbol_count;
457	}
458    }
459
460  info.sym_name = name;
461  info.defsec = sec;
462  info.ncrs = ncrs;
463  info.asymbols = asymbols;
464  bfd_map_over_sections (abfd, check_reloc_refs, &info);
465
466  if (li == NULL)
467    free (asymbols);
468}
469
470/* This is called via bfd_map_over_sections.  INFO->SYM_NAME is a symbol
471   defined in INFO->DEFSECNAME.  If this section maps into any of the
472   sections listed in INFO->NCRS, other than INFO->DEFSECNAME, then we
473   look through the relocations.  If any of the relocations are to
474   INFO->SYM_NAME, then we report a prohibited cross reference error.  */
475
476static void
477check_reloc_refs (bfd *abfd, asection *sec, void *iarg)
478{
479  struct check_refs_info *info = iarg;
480  asection *outsec;
481  const char *outsecname;
482  asection *outdefsec;
483  const char *outdefsecname;
484  struct lang_nocrossref *ncr;
485  const char *symname;
486  long relsize;
487  arelent **relpp;
488  long relcount;
489  arelent **p, **pend;
490
491  outsec = sec->output_section;
492  outsecname = bfd_get_section_name (outsec->owner, outsec);
493
494  outdefsec = info->defsec->output_section;
495  outdefsecname = bfd_get_section_name (outdefsec->owner, outdefsec);
496
497  /* The section where the symbol is defined is permitted.  */
498  if (strcmp (outsecname, outdefsecname) == 0)
499    return;
500
501  for (ncr = info->ncrs->list; ncr != NULL; ncr = ncr->next)
502    if (strcmp (outsecname, ncr->name) == 0)
503      break;
504
505  if (ncr == NULL)
506    return;
507
508  /* This section is one for which cross references are prohibited.
509     Look through the relocations, and see if any of them are to
510     INFO->SYM_NAME.  If INFO->SYMNAME is NULL, check for relocations
511     against the section symbol.  */
512
513  symname = info->sym_name;
514
515  relsize = bfd_get_reloc_upper_bound (abfd, sec);
516  if (relsize < 0)
517    einfo (_("%B%F: could not read relocs: %E\n"), abfd);
518  if (relsize == 0)
519    return;
520
521  relpp = xmalloc (relsize);
522  relcount = bfd_canonicalize_reloc (abfd, sec, relpp, info->asymbols);
523  if (relcount < 0)
524    einfo (_("%B%F: could not read relocs: %E\n"), abfd);
525
526  p = relpp;
527  pend = p + relcount;
528  for (; p < pend && *p != NULL; p++)
529    {
530      arelent *q = *p;
531
532      if (q->sym_ptr_ptr != NULL
533	  && *q->sym_ptr_ptr != NULL
534	  && (symname != NULL
535	      ? strcmp (bfd_asymbol_name (*q->sym_ptr_ptr), symname) == 0
536	      : (((*q->sym_ptr_ptr)->flags & BSF_SECTION_SYM) != 0
537		 && bfd_get_section (*q->sym_ptr_ptr) == info->defsec)))
538	{
539	  /* We found a reloc for the symbol.  The symbol is defined
540	     in OUTSECNAME.  This reloc is from a section which is
541	     mapped into a section from which references to OUTSECNAME
542	     are prohibited.  We must report an error.  */
543	  einfo (_("%X%C: prohibited cross reference from %s to `%T' in %s\n"),
544		 abfd, sec, q->address, outsecname,
545		 bfd_asymbol_name (*q->sym_ptr_ptr), outdefsecname);
546	}
547    }
548
549  free (relpp);
550}
551