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