1 /* symtab.c
2
3 Copyright (C) 1999-2023 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
29 static int cmp_addr (const void *, const void *);
30
31 Sym_Table symtab;
32
33
34 /* Initialize a symbol (so it's empty). */
35
36 void
37 sym_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
60 static int
61 cmp_addr (const void *lp, const void *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
78 void
79 symtab_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 > tab->base && 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
177 Sym *
178 dbg_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. */
216 Sym *
217 sym_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 }