| 1 | /* symtab.c |
| 2 | |
| 3 | Copyright (C) 1999-2015 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 | \f |
| 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 PTR, const PTR); |
| 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 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 | |
| 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] |
| 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 | (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 | } |