1/* Find debugging and symbol information for a module in libdwfl.
2   Copyright (C) 2005-2013 Red Hat, Inc.
3   This file is part of elfutils.
4
5   This file is free software; you can redistribute it and/or modify
6   it under the terms of either
7
8     * the GNU Lesser General Public License as published by the Free
9       Software Foundation; either version 3 of the License, or (at
10       your option) any later version
11
12   or
13
14     * the GNU General Public License as published by the Free
15       Software Foundation; either version 2 of the License, or (at
16       your option) any later version
17
18   or both in parallel, as here.
19
20   elfutils is distributed in the hope that it will be useful, but
21   WITHOUT ANY WARRANTY; without even the implied warranty of
22   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
23   General Public License for more details.
24
25   You should have received copies of the GNU General Public License and
26   the GNU Lesser General Public License along with this program.  If
27   not, see <http://www.gnu.org/licenses/>.  */
28
29#ifdef HAVE_CONFIG_H
30# include <config.h>
31#endif
32
33#include "libdwflP.h"
34
35struct search_state
36{
37  Dwfl_Module *mod;
38  GElf_Addr addr;
39
40  GElf_Sym *closest_sym;
41  bool adjust_st_value;
42  GElf_Word addr_shndx;
43  Elf *addr_symelf;
44
45  /* Keep track of the closest symbol we have seen so far.
46     Here we store only symbols with nonzero st_size.  */
47  const char *closest_name;
48  GElf_Addr closest_value;
49  GElf_Word closest_shndx;
50  Elf *closest_elf;
51
52  /* Keep track of an eligible symbol with st_size == 0 as a fallback.  */
53  const char *sizeless_name;
54  GElf_Sym sizeless_sym;
55  GElf_Addr sizeless_value;
56  GElf_Word sizeless_shndx;
57  Elf *sizeless_elf;
58
59  /* Keep track of the lowest address a relevant sizeless symbol could have.  */
60  GElf_Addr min_label;
61};
62
63/* Return true iff we consider ADDR to lie in the same section as SYM.  */
64static inline bool
65same_section (struct search_state *state,
66	      GElf_Addr value, Elf *symelf, GElf_Word shndx)
67{
68  /* For absolute symbols and the like, only match exactly.  */
69  if (shndx >= SHN_LORESERVE)
70    return value == state->addr;
71
72  /* If value might not be st_value, the shndx of the symbol might
73      not match the section of the value. Explicitly look both up.  */
74  if (! state->adjust_st_value)
75    {
76      Dwarf_Addr v;
77      if (state->addr_shndx == SHN_UNDEF)
78        {
79          v = state->addr;
80          state->addr_shndx = __libdwfl_find_section_ndx (state->mod, &v);
81        }
82
83      v = value;
84      return state->addr_shndx == __libdwfl_find_section_ndx (state->mod, &v);
85    }
86
87  /* Figure out what section ADDR lies in.  */
88  if (state->addr_shndx == SHN_UNDEF || state->addr_symelf != symelf)
89    {
90      GElf_Addr mod_addr = dwfl_deadjust_st_value (state->mod, symelf,
91						   state->addr);
92      Elf_Scn *scn = NULL;
93      state->addr_shndx = SHN_ABS;
94      state->addr_symelf = symelf;
95      while ((scn = elf_nextscn (symelf, scn)) != NULL)
96        {
97          GElf_Shdr shdr_mem;
98          GElf_Shdr *shdr = gelf_getshdr (scn, &shdr_mem);
99          if (likely (shdr != NULL)
100              && mod_addr >= shdr->sh_addr
101              && mod_addr < shdr->sh_addr + shdr->sh_size)
102            {
103              state->addr_shndx = elf_ndxscn (scn);
104              break;
105            }
106        }
107    }
108
109  return shndx == state->addr_shndx && state->addr_symelf == symelf;
110}
111
112/* Return GELF_ST_BIND as higher-is-better integer.  */
113static inline int
114binding_value (const GElf_Sym *symp)
115{
116  switch (GELF_ST_BIND (symp->st_info))
117    {
118    case STB_GLOBAL:
119      return 3;
120    case STB_WEAK:
121      return 2;
122    case STB_LOCAL:
123      return 1;
124    default:
125      return 0;
126    }
127}
128
129/* Try one symbol and associated value from the search table.  */
130static inline void
131try_sym_value (struct search_state *state,
132               GElf_Addr value, GElf_Sym *sym,
133               const char *name, GElf_Word shndx,
134               Elf *elf, bool resolved)
135{
136    /* Even if we don't choose this symbol, its existence excludes
137       any sizeless symbol (assembly label) that is below its upper
138       bound.  */
139    if (value + sym->st_size > state->min_label)
140      state->min_label = value + sym->st_size;
141
142    if (sym->st_size == 0 || state->addr - value < sym->st_size)
143      {
144	/* This symbol is a better candidate than the current one
145	   if it's closer to ADDR or is global when it was local.  */
146	if (state->closest_name == NULL
147	    || state->closest_value < value
148	    || binding_value (state->closest_sym) < binding_value (sym))
149	  {
150	    if (sym->st_size != 0)
151	      {
152		*state->closest_sym = *sym;
153		state->closest_value = value;
154		state->closest_shndx = shndx;
155		state->closest_elf = elf;
156		state->closest_name = name;
157	      }
158	    else if (state->closest_name == NULL
159		     && value >= state->min_label
160		     && same_section (state, value,
161				      resolved ? state->mod->main.elf : elf,
162				      shndx))
163	      {
164		/* Handwritten assembly symbols sometimes have no
165		   st_size.  If no symbol with proper size includes
166		   the address, we'll use the closest one that is in
167		   the same section as ADDR.  */
168		state->sizeless_sym = *sym;
169		state->sizeless_value = value;
170		state->sizeless_shndx = shndx;
171		state->sizeless_elf = elf;
172		state->sizeless_name = name;
173	      }
174	  }
175	/* When the beginning of its range is no closer,
176	   the end of its range might be.  Otherwise follow
177	   GELF_ST_BIND preference.  If all are equal prefer
178	   the first symbol found.  */
179	else if (sym->st_size != 0
180		 && state->closest_value == value
181		 && ((state->closest_sym->st_size > sym->st_size
182		      && (binding_value (state->closest_sym)
183			  <= binding_value (sym)))
184		     || (state->closest_sym->st_size >= sym->st_size
185			 && (binding_value (state->closest_sym)
186			     < binding_value (sym)))))
187	  {
188	    *state->closest_sym = *sym;
189	    state->closest_value = value;
190	    state->closest_shndx = shndx;
191	    state->closest_elf = elf;
192	    state->closest_name = name;
193	  }
194      }
195}
196
197/* Look through the symbol table for a matching symbol.  */
198static inline void
199search_table (struct search_state *state, int start, int end)
200{
201      for (int i = start; i < end; ++i)
202	{
203	  GElf_Sym sym;
204	  GElf_Addr value;
205	  GElf_Word shndx;
206	  Elf *elf;
207	  bool resolved;
208	  const char *name = __libdwfl_getsym (state->mod, i, &sym, &value,
209					       &shndx, &elf, NULL,
210					       &resolved,
211					       state->adjust_st_value);
212	  if (name != NULL && name[0] != '\0'
213	      && sym.st_shndx != SHN_UNDEF
214	      && value <= state->addr
215	      && GELF_ST_TYPE (sym.st_info) != STT_SECTION
216	      && GELF_ST_TYPE (sym.st_info) != STT_FILE
217	      && GELF_ST_TYPE (sym.st_info) != STT_TLS)
218	    {
219	      try_sym_value (state, value, &sym, name, shndx, elf, resolved);
220
221	      /* If this is an addrinfo variant and the value could be
222		 resolved then also try matching the (adjusted) st_value.  */
223	      if (resolved && state->mod->e_type != ET_REL)
224		{
225		  GElf_Addr adjusted_st_value;
226		  adjusted_st_value = dwfl_adjusted_st_value (state->mod, elf,
227							      sym.st_value);
228		  if (value != adjusted_st_value
229		      && adjusted_st_value <= state->addr)
230		    try_sym_value (state, adjusted_st_value, &sym, name, shndx,
231				   elf, false);
232		}
233	    }
234	}
235}
236
237/* Returns the name of the symbol "closest" to ADDR.
238   Never returns symbols at addresses above ADDR.
239
240   Wrapper for old dwfl_module_addrsym and new dwfl_module_addrinfo.
241   adjust_st_value set to true returns adjusted SYM st_value, set to false
242   it will not adjust SYM at all, but does match against resolved values.   */
243static const char *
244__libdwfl_addrsym (Dwfl_Module *_mod, GElf_Addr _addr, GElf_Off *off,
245		   GElf_Sym *_closest_sym, GElf_Word *shndxp,
246		   Elf **elfp, Dwarf_Addr *biasp, bool _adjust_st_value)
247{
248  int syments = INTUSE(dwfl_module_getsymtab) (_mod);
249  if (syments < 0)
250    return NULL;
251
252  struct search_state state =
253    {
254      .addr = _addr,
255      .mod = _mod,
256      .closest_sym = _closest_sym,
257      .adjust_st_value = _adjust_st_value,
258      .addr_shndx = SHN_UNDEF,
259      .addr_symelf = NULL,
260      .closest_name = NULL,
261      .closest_value = 0,
262      .closest_shndx = SHN_UNDEF,
263      .closest_elf = NULL,
264      .sizeless_name = NULL,
265      .sizeless_sym = { 0, 0, 0, 0, 0, SHN_UNDEF },
266      .sizeless_value = 0,
267      .sizeless_shndx = SHN_UNDEF,
268      .sizeless_elf = NULL,
269      .min_label = 0
270    };
271
272  /* First go through global symbols.  mod->first_global and
273     mod->aux_first_global are setup by dwfl_module_getsymtab to the
274     index of the first global symbol in those symbol tables.  Both
275     are non-zero when the table exist, except when there is only a
276     dynsym table loaded through phdrs, then first_global is zero and
277     there will be no auxiliary table.  All symbols with local binding
278     come first in the symbol table, then all globals.  The zeroth,
279     null entry, in the auxiliary table is skipped if there is a main
280     table.  */
281  int first_global = INTUSE (dwfl_module_getsymtab_first_global) (state.mod);
282  if (first_global < 0)
283    return NULL;
284  search_table (&state, first_global == 0 ? 1 : first_global, syments);
285
286  /* If we found nothing searching the global symbols, then try the locals.
287     Unless we have a global sizeless symbol that matches exactly.  */
288  if (state.closest_name == NULL && first_global > 1
289      && (state.sizeless_name == NULL || state.sizeless_value != state.addr))
290    search_table (&state, 1, first_global);
291
292  /* If we found no proper sized symbol to use, fall back to the best
293     candidate sizeless symbol we found, if any.  */
294  if (state.closest_name == NULL
295      && state.sizeless_name != NULL
296      && state.sizeless_value >= state.min_label)
297    {
298      *state.closest_sym = state.sizeless_sym;
299      state.closest_value = state.sizeless_value;
300      state.closest_shndx = state.sizeless_shndx;
301      state.closest_elf = state.sizeless_elf;
302      state.closest_name = state.sizeless_name;
303    }
304
305  *off = state.addr - state.closest_value;
306
307  if (shndxp != NULL)
308    *shndxp = state.closest_shndx;
309  if (elfp != NULL)
310    *elfp = state.closest_elf;
311  if (biasp != NULL)
312    *biasp = dwfl_adjusted_st_value (state.mod, state.closest_elf, 0);
313  return state.closest_name;
314}
315
316
317const char *
318dwfl_module_addrsym (Dwfl_Module *mod, GElf_Addr addr,
319		     GElf_Sym *closest_sym, GElf_Word *shndxp)
320{
321  GElf_Off off;
322  return __libdwfl_addrsym (mod, addr, &off, closest_sym, shndxp,
323			    NULL, NULL, true);
324}
325INTDEF (dwfl_module_addrsym)
326
327const char
328*dwfl_module_addrinfo (Dwfl_Module *mod, GElf_Addr address,
329		       GElf_Off *offset, GElf_Sym *sym,
330		       GElf_Word *shndxp, Elf **elfp, Dwarf_Addr *bias)
331{
332  return __libdwfl_addrsym (mod, address, offset, sym, shndxp, elfp, bias,
333			    false);
334}
335INTDEF (dwfl_module_addrinfo)
336