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