1/* Recover relocatibility for addresses computed from debug information.
2   Copyright (C) 2005-2010, 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#include "libdwflP.h"
30
31struct dwfl_relocation
32{
33  size_t count;
34  struct
35  {
36    Elf_Scn *scn;
37    Elf_Scn *relocs;
38    const char *name;
39    GElf_Addr start, end;
40  } refs[0];
41};
42
43
44struct secref
45{
46  struct secref *next;
47  Elf_Scn *scn;
48  Elf_Scn *relocs;
49  const char *name;
50  GElf_Addr start, end;
51};
52
53static int
54compare_secrefs (const void *a, const void *b)
55{
56  struct secref *const *p1 = a;
57  struct secref *const *p2 = b;
58
59  /* No signed difference calculation is correct here, since the
60     terms are unsigned and could be more than INT64_MAX apart.  */
61  if ((*p1)->start < (*p2)->start)
62    return -1;
63  if ((*p1)->start > (*p2)->start)
64    return 1;
65
66  return 0;
67}
68
69static int
70cache_sections (Dwfl_Module *mod)
71{
72  if (likely (mod->reloc_info != NULL))
73    return mod->reloc_info->count;
74
75  struct secref *refs = NULL;
76  size_t nrefs = 0;
77
78  size_t shstrndx;
79  if (unlikely (elf_getshdrstrndx (mod->main.elf, &shstrndx) < 0))
80    {
81    elf_error:
82      __libdwfl_seterrno (DWFL_E_LIBELF);
83      return -1;
84    }
85
86  bool check_reloc_sections = false;
87  Elf_Scn *scn = NULL;
88  while ((scn = elf_nextscn (mod->main.elf, scn)) != NULL)
89    {
90      GElf_Shdr shdr_mem;
91      GElf_Shdr *shdr = gelf_getshdr (scn, &shdr_mem);
92      if (shdr == NULL)
93	goto elf_error;
94
95      if ((shdr->sh_flags & SHF_ALLOC) && shdr->sh_addr == 0
96	  && mod->e_type == ET_REL)
97	{
98	  /* This section might not yet have been looked at.  */
99	  if (__libdwfl_relocate_value (mod, mod->main.elf, &shstrndx,
100					elf_ndxscn (scn),
101					&shdr->sh_addr) != DWFL_E_NOERROR)
102	    continue;
103	  shdr = gelf_getshdr (scn, &shdr_mem);
104	  if (unlikely (shdr == NULL))
105	    goto elf_error;
106	}
107
108      if (shdr->sh_flags & SHF_ALLOC)
109	{
110	  const char *name = elf_strptr (mod->main.elf, shstrndx,
111					 shdr->sh_name);
112	  if (unlikely (name == NULL))
113	    goto elf_error;
114
115	  struct secref *newref = alloca (sizeof *newref);
116	  newref->scn = scn;
117	  newref->relocs = NULL;
118	  newref->name = name;
119	  newref->start = dwfl_adjusted_address (mod, shdr->sh_addr);
120	  newref->end = newref->start + shdr->sh_size;
121	  newref->next = refs;
122	  refs = newref;
123	  ++nrefs;
124	}
125
126      if (mod->e_type == ET_REL
127	  && shdr->sh_size != 0
128	  && (shdr->sh_type == SHT_REL || shdr->sh_type == SHT_RELA)
129	  && mod->dwfl->callbacks->section_address != NULL)
130	{
131	  if (shdr->sh_info < elf_ndxscn (scn))
132	    {
133	      /* We've already looked at the section these relocs apply to.  */
134	      Elf_Scn *tscn = elf_getscn (mod->main.elf, shdr->sh_info);
135	      if (likely (tscn != NULL))
136		for (struct secref *sec = refs; sec != NULL; sec = sec->next)
137		  if (sec->scn == tscn)
138		    {
139		      sec->relocs = scn;
140		      break;
141		    }
142	    }
143	  else
144	    /* We'll have to do a second pass.  */
145	    check_reloc_sections = true;
146	}
147    }
148
149  mod->reloc_info = malloc (offsetof (struct dwfl_relocation, refs[nrefs]));
150  if (mod->reloc_info == NULL)
151    {
152      __libdwfl_seterrno (DWFL_E_NOMEM);
153      return -1;
154    }
155
156  struct secref **sortrefs = alloca (nrefs * sizeof sortrefs[0]);
157  for (size_t i = nrefs; i-- > 0; refs = refs->next)
158    sortrefs[i] = refs;
159  assert (refs == NULL);
160
161  qsort (sortrefs, nrefs, sizeof sortrefs[0], &compare_secrefs);
162
163  mod->reloc_info->count = nrefs;
164  for (size_t i = 0; i < nrefs; ++i)
165    {
166      mod->reloc_info->refs[i].name = sortrefs[i]->name;
167      mod->reloc_info->refs[i].scn = sortrefs[i]->scn;
168      mod->reloc_info->refs[i].relocs = sortrefs[i]->relocs;
169      mod->reloc_info->refs[i].start = sortrefs[i]->start;
170      mod->reloc_info->refs[i].end = sortrefs[i]->end;
171    }
172
173  if (unlikely (check_reloc_sections))
174    {
175      /* There was a reloc section that preceded its target section.
176	 So we have to scan again now that we have cached all the
177	 possible target sections we care about.  */
178
179      scn = NULL;
180      while ((scn = elf_nextscn (mod->main.elf, scn)) != NULL)
181	{
182	  GElf_Shdr shdr_mem;
183	  GElf_Shdr *shdr = gelf_getshdr (scn, &shdr_mem);
184	  if (shdr == NULL)
185	    goto elf_error;
186
187      	  if (shdr->sh_size != 0
188	      && (shdr->sh_type == SHT_REL || shdr->sh_type == SHT_RELA))
189	    {
190	      Elf_Scn *tscn = elf_getscn (mod->main.elf, shdr->sh_info);
191	      if (likely (tscn != NULL))
192		for (size_t i = 0; i < nrefs; ++i)
193		  if (mod->reloc_info->refs[i].scn == tscn)
194		    {
195		      mod->reloc_info->refs[i].relocs = scn;
196		      break;
197		    }
198	    }
199	}
200    }
201
202  return nrefs;
203}
204
205
206int
207dwfl_module_relocations (Dwfl_Module *mod)
208{
209  if (mod == NULL)
210    return -1;
211
212  switch (mod->e_type)
213    {
214    case ET_REL:
215      return cache_sections (mod);
216
217    case ET_DYN:
218      return 1;
219
220    case ET_EXEC:
221      assert (mod->main.vaddr == mod->low_addr);
222      break;
223    }
224
225  return 0;
226}
227
228const char *
229dwfl_module_relocation_info (Dwfl_Module *mod, unsigned int idx,
230			     Elf32_Word *shndxp)
231{
232  if (mod == NULL)
233    return NULL;
234
235  switch (mod->e_type)
236    {
237    case ET_REL:
238      break;
239
240    case ET_DYN:
241      if (idx != 0)
242	return NULL;
243      if (shndxp)
244	*shndxp = SHN_ABS;
245      return "";
246
247    default:
248      return NULL;
249    }
250
251  if (cache_sections (mod) < 0)
252    return NULL;
253
254  struct dwfl_relocation *sections = mod->reloc_info;
255
256  if (idx >= sections->count)
257    return NULL;
258
259  if (shndxp)
260    *shndxp = elf_ndxscn (sections->refs[idx].scn);
261
262  return sections->refs[idx].name;
263}
264
265/* Check that MOD is valid and make sure its relocation has been done.  */
266static bool
267check_module (Dwfl_Module *mod)
268{
269  if (INTUSE(dwfl_module_getsymtab) (mod) < 0)
270    {
271      Dwfl_Error error = dwfl_errno ();
272      if (error != DWFL_E_NO_SYMTAB)
273	{
274	  __libdwfl_seterrno (error);
275	  return true;
276	}
277    }
278
279  if (mod->dw == NULL)
280    {
281      Dwarf_Addr bias;
282      if (INTUSE(dwfl_module_getdwarf) (mod, &bias) == NULL)
283	{
284	  Dwfl_Error error = dwfl_errno ();
285	  if (error != DWFL_E_NO_DWARF)
286	    {
287	      __libdwfl_seterrno (error);
288	      return true;
289	    }
290	}
291    }
292
293  return false;
294}
295
296/* Find the index in MOD->reloc_info.refs containing *ADDR.  */
297static int
298find_section (Dwfl_Module *mod, Dwarf_Addr *addr)
299{
300  if (cache_sections (mod) < 0)
301    return -1;
302
303  struct dwfl_relocation *sections = mod->reloc_info;
304
305  /* The sections are sorted by address, so we can use binary search.  */
306  size_t l = 0, u = sections->count;
307  while (l < u)
308    {
309      size_t idx = (l + u) / 2;
310      if (*addr < sections->refs[idx].start)
311	u = idx;
312      else if (*addr > sections->refs[idx].end)
313	l = idx + 1;
314      else
315	{
316	  /* Consider the limit of a section to be inside it, unless it's
317	     inside the next one.  A section limit address can appear in
318	     line records.  */
319	  if (*addr == sections->refs[idx].end
320	      && idx + 1 < sections->count
321	      && *addr == sections->refs[idx + 1].start)
322	    ++idx;
323
324	  *addr -= sections->refs[idx].start;
325	  return idx;
326	}
327    }
328
329  __libdwfl_seterrno (DWFL_E (LIBDW, DWARF_E_NO_MATCH));
330  return -1;
331}
332
333size_t
334internal_function
335__libdwfl_find_section_ndx (Dwfl_Module *mod, Dwarf_Addr *addr)
336{
337  int idx = find_section (mod, addr);
338  if (unlikely (idx == -1))
339    return SHN_UNDEF;
340
341  return elf_ndxscn (mod->reloc_info->refs[idx].scn);
342}
343
344int
345dwfl_module_relocate_address (Dwfl_Module *mod, Dwarf_Addr *addr)
346{
347  if (unlikely (check_module (mod)))
348    return -1;
349
350  switch (mod->e_type)
351    {
352    case ET_REL:
353      return find_section (mod, addr);
354
355    case ET_DYN:
356      /* All relative to first and only relocation base: module start.  */
357      *addr -= mod->low_addr;
358      break;
359
360    default:
361      /* Already absolute, dwfl_module_relocations returned zero.  We
362	 shouldn't really have been called, but it's a harmless no-op.  */
363      break;
364    }
365
366  return 0;
367}
368INTDEF (dwfl_module_relocate_address)
369
370Elf_Scn *
371dwfl_module_address_section (Dwfl_Module *mod, Dwarf_Addr *address,
372			     Dwarf_Addr *bias)
373{
374  if (check_module (mod))
375    return NULL;
376
377  int idx = find_section (mod, address);
378  if (idx < 0)
379    return NULL;
380
381  if (mod->reloc_info->refs[idx].relocs != NULL)
382    {
383      assert (mod->e_type == ET_REL);
384
385      Elf_Scn *tscn = mod->reloc_info->refs[idx].scn;
386      Elf_Scn *relocscn = mod->reloc_info->refs[idx].relocs;
387      Dwfl_Error result = __libdwfl_relocate_section (mod, mod->main.elf,
388						      relocscn, tscn, true);
389      if (likely (result == DWFL_E_NOERROR))
390	mod->reloc_info->refs[idx].relocs = NULL;
391      else
392	{
393	  __libdwfl_seterrno (result);
394	  return NULL;
395	}
396    }
397
398  *bias = dwfl_adjusted_address (mod, 0);
399  return mod->reloc_info->refs[idx].scn;
400}
401INTDEF (dwfl_module_address_section)
402