1/* symtab.c
2
3   Copyright (C) 1999-2020 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 3 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] == '_' && dst[-1].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_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		   (unsigned long) tab->base[j].addr,
168		   (unsigned long) tab->base[j].end_addr,
169		   tab->base[j].name);
170	 }
171  );
172}
173
174
175#ifdef DEBUG
176
177Sym *
178dbg_sym_lookup (Sym_Table *sym_tab, bfd_vma address)
179{
180  unsigned long low, mid, high;
181  Sym *sym;
182
183  fprintf (stderr, "[dbg_sym_lookup] address 0x%lx\n",
184	   (unsigned long) address);
185
186  sym = sym_tab->base;
187  for (low = 0, high = sym_tab->len - 1; low != high;)
188    {
189      mid = (high + low) >> 1;
190
191      fprintf (stderr, "[dbg_sym_lookup] low=0x%lx, mid=0x%lx, high=0x%lx\n",
192	       low, mid, high);
193      fprintf (stderr, "[dbg_sym_lookup] sym[m]=0x%lx sym[m + 1]=0x%lx\n",
194	       (unsigned long) sym[mid].addr,
195	       (unsigned long) sym[mid + 1].addr);
196
197      if (sym[mid].addr <= address && sym[mid + 1].addr > address)
198	return &sym[mid];
199
200      if (sym[mid].addr > address)
201	high = mid;
202      else
203	low = mid + 1;
204    }
205
206  fprintf (stderr, "[dbg_sym_lookup] binary search fails???\n");
207
208  return 0;
209}
210
211#endif	/* DEBUG */
212
213
214/* Look up an address in the symbol-table that is sorted by address.
215   If address does not hit any symbol, 0 is returned.  */
216Sym *
217sym_lookup (Sym_Table *sym_tab, bfd_vma address)
218{
219  long low, high;
220  long mid = -1;
221  Sym *sym;
222#ifdef DEBUG
223  int probes = 0;
224#endif /* DEBUG */
225
226  if (!sym_tab->len)
227    return 0;
228
229  sym = sym_tab->base;
230  for (low = 0, high = sym_tab->len - 1; low != high;)
231    {
232      DBG (LOOKUPDEBUG, ++probes);
233      mid = (high + low) / 2;
234
235      if (sym[mid].addr <= address && sym[mid + 1].addr > address)
236	{
237	  if (address > sym[mid].end_addr)
238	    {
239	      /* Address falls into gap between
240		 sym[mid] and sym[mid + 1].  */
241	      return 0;
242	    }
243	  else
244	    {
245	      DBG (LOOKUPDEBUG,
246		   printf ("[sym_lookup] %d probes (symtab->len=%u)\n",
247			   probes, sym_tab->len - 1));
248	      return &sym[mid];
249	    }
250	}
251
252      if (sym[mid].addr > address)
253	high = mid;
254      else
255	low = mid + 1;
256    }
257
258  if (sym[mid + 1].addr <= address)
259    {
260      if (address > sym[mid + 1].end_addr)
261	{
262	  /* Address is beyond end of sym[mid + 1].  */
263	  return 0;
264	}
265      else
266	{
267	  DBG (LOOKUPDEBUG, printf ("[sym_lookup] %d (%u) probes, fall off\n",
268				    probes, sym_tab->len - 1));
269	  return &sym[mid + 1];
270	}
271    }
272
273  return 0;
274}
275