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