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