1 /* symtab.c 2 3 Copyright 1999, 2000, 2001, 2002, 2004 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 2 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 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 (long) tab->base[j].addr, (long) tab->base[j].end_addr, 168 tab->base[j].name); 169 } 170 ); 171 } 172 173 174 #ifdef DEBUG 175 176 Sym * 177 dbg_sym_lookup (Sym_Table *sym_tab, bfd_vma address) 178 { 179 long low, mid, high; 180 Sym *sym; 181 182 fprintf (stderr, "[dbg_sym_lookup] address 0x%lx\n", 183 (unsigned long) address); 184 185 sym = sym_tab->base; 186 for (low = 0, high = sym_tab->len - 1; low != high;) 187 { 188 mid = (high + low) >> 1; 189 190 fprintf (stderr, "[dbg_sym_lookup] low=0x%lx, mid=0x%lx, high=0x%lx\n", 191 low, mid, high); 192 fprintf (stderr, "[dbg_sym_lookup] sym[m]=0x%lx sym[m + 1]=0x%lx\n", 193 (unsigned long) sym[mid].addr, 194 (unsigned long) sym[mid + 1].addr); 195 196 if (sym[mid].addr <= address && sym[mid + 1].addr > address) 197 return &sym[mid]; 198 199 if (sym[mid].addr > address) 200 high = mid; 201 else 202 low = mid + 1; 203 } 204 205 fprintf (stderr, "[dbg_sym_lookup] binary search fails???\n"); 206 207 return 0; 208 } 209 210 #endif /* DEBUG */ 211 212 213 /* Look up an address in the symbol-table that is sorted by address. 214 If address does not hit any symbol, 0 is returned. */ 215 Sym * 216 sym_lookup (Sym_Table *sym_tab, bfd_vma address) 217 { 218 long low, high; 219 long mid = -1; 220 Sym *sym; 221 #ifdef DEBUG 222 int probes = 0; 223 #endif /* DEBUG */ 224 225 if (!sym_tab->len) 226 return 0; 227 228 sym = sym_tab->base; 229 for (low = 0, high = sym_tab->len - 1; low != high;) 230 { 231 DBG (LOOKUPDEBUG, ++probes); 232 mid = (high + low) / 2; 233 234 if (sym[mid].addr <= address && sym[mid + 1].addr > address) 235 { 236 if (address > sym[mid].end_addr) 237 { 238 /* Address falls into gap between 239 sym[mid] and sym[mid + 1]. */ 240 return 0; 241 } 242 else 243 { 244 DBG (LOOKUPDEBUG, 245 printf ("[sym_lookup] %d probes (symtab->len=%u)\n", 246 probes, sym_tab->len - 1)); 247 return &sym[mid]; 248 } 249 } 250 251 if (sym[mid].addr > address) 252 high = mid; 253 else 254 low = mid + 1; 255 } 256 257 if (sym[mid + 1].addr <= address) 258 { 259 if (address > sym[mid + 1].end_addr) 260 { 261 /* Address is beyond end of sym[mid + 1]. */ 262 return 0; 263 } 264 else 265 { 266 DBG (LOOKUPDEBUG, printf ("[sym_lookup] %d (%u) probes, fall off\n", 267 probes, sym_tab->len - 1)); 268 return &sym[mid + 1]; 269 } 270 } 271 272 return 0; 273 } 274