1/* symtab.c
2
3   Copyright 1999, 2000, 2001, 2002, 2004 Free Software Foundation, Inc.
4
5   This file is part of 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 2 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, MA
20   02110-1301, USA.  */
21
22#include "gprof.h"
23#include "search_list.h"
24#include "source.h"
25#include "symtab.h"
26#include "cg_arcs.h"
27#include "corefile.h"
28
29static int cmp_addr (const PTR, const PTR);
30
31Sym_Table symtab;
32
33
34/* Initialize a symbol (so it's empty).  */
35
36void
37sym_init (Sym *sym)
38{
39  memset (sym, 0, sizeof (*sym));
40
41  /* It is not safe to assume that a binary zero corresponds
42     to a floating-point 0.0, so initialize floats explicitly.  */
43  sym->hist.time = 0.0;
44  sym->cg.child_time = 0.0;
45  sym->cg.prop.fract = 0.0;
46  sym->cg.prop.self = 0.0;
47  sym->cg.prop.child = 0.0;
48}
49
50
51/* Compare the function entry-point of two symbols and return <0, =0,
52   or >0 depending on whether the left value is smaller than, equal
53   to, or greater than the right value.  If two symbols are equal
54   but one has is_func set and the other doesn't, we make the
55   non-function symbol one "bigger" so that the function symbol will
56   survive duplicate removal.  Finally, if both symbols have the
57   same is_func value, we discriminate against is_static such that
58   the global symbol survives.  */
59
60static int
61cmp_addr (const PTR lp, const PTR rp)
62{
63  const Sym *left = (const Sym *) lp;
64  const Sym *right = (const Sym *) rp;
65
66  if (left->addr > right->addr)
67    return 1;
68  else if (left->addr < right->addr)
69    return -1;
70
71  if (left->is_func != right->is_func)
72    return right->is_func - left->is_func;
73
74  return left->is_static - right->is_static;
75}
76
77
78void
79symtab_finalize (Sym_Table *tab)
80{
81  Sym *src, *dst;
82  bfd_vma prev_addr;
83
84  if (!tab->len)
85    return;
86
87  /* Sort symbol table in order of increasing function addresses.  */
88  qsort (tab->base, tab->len, sizeof (Sym), cmp_addr);
89
90  /* Remove duplicate entries to speed-up later processing and
91     set end_addr if its not set yet.  */
92  prev_addr = tab->base[0].addr + 1;
93
94  for (src = dst = tab->base; src < tab->limit; ++src)
95    {
96      if (src->addr == prev_addr)
97	{
98	  /* If same address, favor global symbol over static one,
99	     then function over line number.  If both symbols are
100	     either static or global and either function or line, check
101	     whether one has name beginning with underscore while
102	     the other doesn't.  In such cases, keep sym without
103	     underscore.  This takes cares of compiler generated
104	     symbols (such as __gnu_compiled, __c89_used, etc.).  */
105	  if ((!src->is_static && dst[-1].is_static)
106	      || ((src->is_static == dst[-1].is_static)
107		  && ((src->is_func && !dst[-1].is_func)
108		      || ((src->is_func == dst[-1].is_func)
109			  && ((src->name[0] != '_' && dst[-1].name[0] == '_')
110			      || (src->name[0]
111				  && src->name[1] != '_'
112				  && dst[-1].name[1] == '_'))))))
113	    {
114	      DBG (AOUTDEBUG | IDDEBUG,
115		   printf ("[symtab_finalize] favor %s@%c%c over %s@%c%c",
116			   src->name, src->is_static ? 't' : 'T',
117			   src->is_func ? 'F' : 'f',
118			   dst[-1].name, dst[-1].is_static ? 't' : 'T',
119			   dst[-1].is_func ? 'F' : 'f');
120		   printf (" (addr=%lx)\n", (unsigned long) src->addr));
121
122	      dst[-1] = *src;
123	    }
124	  else
125	    {
126	      DBG (AOUTDEBUG | IDDEBUG,
127		   printf ("[symtab_finalize] favor %s@%c%c over %s@%c%c",
128			   dst[-1].name, dst[-1].is_static ? 't' : 'T',
129			   dst[-1].is_func ? 'F' : 'f',
130			   src->name, src->is_static ? 't' : 'T',
131			   src->is_func ? 'F' : 'f');
132		   printf (" (addr=%lx)\n", (unsigned long) src->addr));
133	    }
134	}
135      else
136	{
137	  if (dst > tab->base && dst[-1].end_addr == 0)
138	    dst[-1].end_addr = src->addr - 1;
139
140	  /* Retain sym only if it has a non-empty address range.  */
141	  if (!src->end_addr || src->addr <= src->end_addr)
142	    {
143	      *dst = *src;
144	      dst++;
145	      prev_addr = src->addr;
146	    }
147	}
148    }
149
150  if (tab->len > 0 && dst[-1].end_addr == 0)
151    dst[-1].end_addr
152      = core_text_sect->vma + bfd_get_section_size (core_text_sect) - 1;
153
154  DBG (AOUTDEBUG | IDDEBUG,
155       printf ("[symtab_finalize]: removed %d duplicate entries\n",
156	       tab->len - (int) (dst - tab->base)));
157
158  tab->limit = dst;
159  tab->len = tab->limit - tab->base;
160
161  DBG (AOUTDEBUG | IDDEBUG,
162       unsigned int j;
163
164       for (j = 0; j < tab->len; ++j)
165	 {
166	   printf ("[symtab_finalize] 0x%lx-0x%lx\t%s\n",
167		 (long) tab->base[j].addr, (long) tab->base[j].end_addr,
168		 tab->base[j].name);
169	 }
170  );
171}
172
173
174#ifdef DEBUG
175
176Sym *
177dbg_sym_lookup (Sym_Table *sym_tab, bfd_vma address)
178{
179  long low, mid, high;
180  Sym *sym;
181
182  fprintf (stderr, "[dbg_sym_lookup] address 0x%lx\n",
183	   (unsigned long) address);
184
185  sym = sym_tab->base;
186  for (low = 0, high = sym_tab->len - 1; low != high;)
187    {
188      mid = (high + low) >> 1;
189
190      fprintf (stderr, "[dbg_sym_lookup] low=0x%lx, mid=0x%lx, high=0x%lx\n",
191	       low, mid, high);
192      fprintf (stderr, "[dbg_sym_lookup] sym[m]=0x%lx sym[m + 1]=0x%lx\n",
193	       (unsigned long) sym[mid].addr,
194	       (unsigned long) sym[mid + 1].addr);
195
196      if (sym[mid].addr <= address && sym[mid + 1].addr > address)
197	return &sym[mid];
198
199      if (sym[mid].addr > address)
200	high = mid;
201      else
202	low = mid + 1;
203    }
204
205  fprintf (stderr, "[dbg_sym_lookup] binary search fails???\n");
206
207  return 0;
208}
209
210#endif	/* DEBUG */
211
212
213/* Look up an address in the symbol-table that is sorted by address.
214   If address does not hit any symbol, 0 is returned.  */
215Sym *
216sym_lookup (Sym_Table *sym_tab, bfd_vma address)
217{
218  long low, high;
219  long mid = -1;
220  Sym *sym;
221#ifdef DEBUG
222  int probes = 0;
223#endif /* DEBUG */
224
225  if (!sym_tab->len)
226    return 0;
227
228  sym = sym_tab->base;
229  for (low = 0, high = sym_tab->len - 1; low != high;)
230    {
231      DBG (LOOKUPDEBUG, ++probes);
232      mid = (high + low) / 2;
233
234      if (sym[mid].addr <= address && sym[mid + 1].addr > address)
235	{
236	  if (address > sym[mid].end_addr)
237	    {
238	      /* Address falls into gap between
239		 sym[mid] and sym[mid + 1].  */
240	      return 0;
241	    }
242	  else
243	    {
244	      DBG (LOOKUPDEBUG,
245		   printf ("[sym_lookup] %d probes (symtab->len=%u)\n",
246			   probes, sym_tab->len - 1));
247	      return &sym[mid];
248	    }
249	}
250
251      if (sym[mid].addr > address)
252	high = mid;
253      else
254	low = mid + 1;
255    }
256
257  if (sym[mid + 1].addr <= address)
258    {
259      if (address > sym[mid + 1].end_addr)
260	{
261	  /* Address is beyond end of sym[mid + 1].  */
262	  return 0;
263	}
264      else
265	{
266	  DBG (LOOKUPDEBUG, printf ("[sym_lookup] %d (%u) probes, fall off\n",
267				    probes, sym_tab->len - 1));
268	  return &sym[mid + 1];
269	}
270    }
271
272  return 0;
273}
274