1/* FDE reading.
2   Copyright (C) 2009-2010, 2014, 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#ifdef HAVE_CONFIG_H
30# include <config.h>
31#endif
32
33#include "cfi.h"
34#include <search.h>
35#include <stdlib.h>
36
37#include "encoded-value.h"
38
39static int
40compare_fde (const void *a, const void *b)
41{
42  const struct dwarf_fde *fde1 = a;
43  const struct dwarf_fde *fde2 = b;
44
45  /* Find out which of the two arguments is the search value.
46     It has end offset 0.  */
47  if (fde1->end == 0)
48    {
49      if (fde1->start < fde2->start)
50	return -1;
51      if (fde1->start >= fde2->end)
52	return 1;
53    }
54  else
55    {
56      if (fde2->start < fde1->start)
57	return 1;
58      if (fde2->start >= fde1->end)
59	return -1;
60    }
61
62  return 0;
63}
64
65static struct dwarf_fde *
66intern_fde (Dwarf_CFI *cache, const Dwarf_FDE *entry)
67{
68  /* Look up the new entry's CIE.  */
69  struct dwarf_cie *cie = __libdw_find_cie (cache, entry->CIE_pointer);
70  if (cie == NULL)
71    return (void *) -1l;
72
73  struct dwarf_fde *fde = malloc (sizeof (struct dwarf_fde));
74  if (fde == NULL)
75    {
76      __libdw_seterrno (DWARF_E_NOMEM);
77      return NULL;
78    }
79
80  fde->instructions = entry->start;
81  fde->instructions_end = entry->end;
82  if (unlikely (read_encoded_value (cache, cie->fde_encoding,
83				    &fde->instructions, &fde->start))
84      || unlikely (read_encoded_value (cache, cie->fde_encoding & 0x0f,
85				       &fde->instructions, &fde->end)))
86    {
87      free (fde);
88      __libdw_seterrno (DWARF_E_INVALID_DWARF);
89      return NULL;
90    }
91  fde->end += fde->start;
92
93  /* Make sure the fde actually covers a real code range.  */
94  if (fde->start >= fde->end)
95    {
96      free (fde);
97      return (void *) -1;
98    }
99
100  fde->cie = cie;
101
102  if (cie->sized_augmentation_data)
103    {
104      /* The CIE augmentation says the FDE has a DW_FORM_block
105	 before its actual instruction stream.  */
106      Dwarf_Word len;
107      get_uleb128 (len, fde->instructions, fde->instructions_end);
108      if ((Dwarf_Word) (fde->instructions_end - fde->instructions) < len)
109	{
110	  free (fde);
111	  __libdw_seterrno (DWARF_E_INVALID_DWARF);
112	  return NULL;
113	}
114      fde->instructions += len;
115    }
116  else
117    /* We had to understand all of the CIE augmentation string.
118       We've recorded the number of data bytes in FDEs.  */
119    fde->instructions += cie->fde_augmentation_data_size;
120
121  /* Add the new entry to the search tree.  */
122  struct dwarf_fde **tres = tsearch (fde, &cache->fde_tree, &compare_fde);
123  if (tres == NULL)
124    {
125      free (fde);
126      __libdw_seterrno (DWARF_E_NOMEM);
127      return NULL;
128    }
129  else if (*tres != fde)
130    {
131      /* There is already an FDE in the cache that covers the same
132	 address range.  That is odd.  Ignore this FDE.  And just use
133	 the one in the cache for consistency.  */
134      free (fde);
135      return *tres;
136    }
137
138  return fde;
139}
140
141struct dwarf_fde *
142internal_function
143__libdw_fde_by_offset (Dwarf_CFI *cache, Dwarf_Off offset)
144{
145  Dwarf_CFI_Entry entry;
146  Dwarf_Off next_offset;
147  int result = INTUSE(dwarf_next_cfi) (cache->e_ident,
148				       &cache->data->d, CFI_IS_EH (cache),
149				       offset, &next_offset, &entry);
150  if (result != 0)
151    {
152      if (result > 0)
153      invalid:
154	__libdw_seterrno (DWARF_E_INVALID_DWARF);
155      return NULL;
156    }
157
158  if (unlikely (dwarf_cfi_cie_p (&entry)))
159    goto invalid;
160
161  /* We have a new FDE to consider.  */
162  struct dwarf_fde *fde = intern_fde (cache, &entry.fde);
163  if (fde == (void *) -1l || fde == NULL)
164    return NULL;
165
166  /* If this happened to be what we would have read next, notice it.  */
167  if (cache->next_offset == offset)
168    cache->next_offset = next_offset;
169
170  return fde;
171}
172
173/* Use a binary search table in .eh_frame_hdr format, yield an FDE offset.  */
174static Dwarf_Off
175binary_search_fde (Dwarf_CFI *cache, Dwarf_Addr address)
176{
177  const size_t size = 2 * encoded_value_size (&cache->data->d, cache->e_ident,
178					      cache->search_table_encoding,
179					      NULL);
180  if (unlikely (size == 0))
181    return (Dwarf_Off) -1l;
182
183  /* Dummy used by read_encoded_value.  */
184  Elf_Data_Scn dummy_cfi_hdr_data =
185    {
186      .d = { .d_buf = (void *) cache->search_table,
187	     .d_size = cache->search_table_len }
188    };
189
190  Dwarf_CFI dummy_cfi =
191    {
192      .e_ident = cache->e_ident,
193      .datarel = cache->search_table_vaddr,
194      .frame_vaddr = cache->search_table_vaddr,
195      .data = &dummy_cfi_hdr_data
196    };
197
198  size_t l = 0, u = cache->search_table_entries;
199  while (l < u)
200    {
201      size_t idx = (l + u) / 2;
202
203      /* Max idx * size is checked against search_table len when
204	 loading eh_frame_hdr.  */
205      const uint8_t *p = &cache->search_table[idx * size];
206      Dwarf_Addr start;
207      if (unlikely (read_encoded_value (&dummy_cfi,
208					cache->search_table_encoding, &p,
209					&start)))
210	break;
211      if (address < start)
212	u = idx;
213      else
214	{
215	  l = idx + 1;
216
217	  Dwarf_Addr fde;
218	  if (unlikely (read_encoded_value (&dummy_cfi,
219					    cache->search_table_encoding, &p,
220					    &fde)))
221	    break;
222
223	  /* If this is the last entry, its upper bound is assumed to be
224	     the end of the module.
225	     XXX really should be end of containing PT_LOAD segment */
226	  if (l < cache->search_table_entries)
227	    {
228	      /* Look at the start address in the following entry.  */
229	      Dwarf_Addr end;
230	      if (unlikely (read_encoded_value
231			    (&dummy_cfi, cache->search_table_encoding, &p,
232			     &end)))
233		break;
234	      if (address >= end)
235		continue;
236	    }
237
238	  return fde - cache->frame_vaddr;
239	}
240    }
241
242  return (Dwarf_Off) -1l;
243}
244
245struct dwarf_fde *
246internal_function
247__libdw_find_fde (Dwarf_CFI *cache, Dwarf_Addr address)
248{
249  /* Look for a cached FDE covering this address.  */
250
251  const struct dwarf_fde fde_key = { .start = address, .end = 0 };
252  struct dwarf_fde **found = tfind (&fde_key, &cache->fde_tree, &compare_fde);
253  if (found != NULL)
254    return *found;
255
256  /* Use .eh_frame_hdr binary search table if possible.  */
257  if (cache->search_table != NULL)
258    {
259      Dwarf_Off offset = binary_search_fde (cache, address);
260      if (offset == (Dwarf_Off) -1l)
261	goto no_match;
262      struct dwarf_fde *fde = __libdw_fde_by_offset (cache, offset);
263      if (likely (fde != NULL))
264	{
265	  /* Sanity check the address range.  */
266	  if (unlikely (address < fde->start))
267	    {
268	      __libdw_seterrno (DWARF_E_INVALID_DWARF);
269	      return NULL;
270	    }
271	  /* .eh_frame_hdr does not indicate length covered by FDE.  */
272	  if (unlikely (address >= fde->end))
273	    goto no_match;
274	}
275      return fde;
276    }
277
278  /* It's not there.  Read more CFI entries until we find it.  */
279  while (1)
280    {
281      Dwarf_Off last_offset = cache->next_offset;
282      Dwarf_CFI_Entry entry;
283      int result = INTUSE(dwarf_next_cfi) (cache->e_ident,
284					   &cache->data->d, CFI_IS_EH (cache),
285					   last_offset, &cache->next_offset,
286					   &entry);
287      if (result > 0)
288	break;
289      if (result < 0)
290	{
291	  if (cache->next_offset == last_offset)
292	    /* We couldn't progress past the bogus FDE.  */
293	    break;
294	  /* Skip the loser and look at the next entry.  */
295	  continue;
296	}
297
298      if (dwarf_cfi_cie_p (&entry))
299	{
300	  /* This is a CIE, not an FDE.  We eagerly intern these
301	     because the next FDE will usually refer to this CIE.  */
302	  __libdw_intern_cie (cache, last_offset, &entry.cie);
303	  continue;
304	}
305
306      /* We have a new FDE to consider.  */
307      struct dwarf_fde *fde = intern_fde (cache, &entry.fde);
308
309      if (fde == (void *) -1l)	/* Bad FDE, but we can keep looking.  */
310	continue;
311
312      if (fde == NULL)		/* Bad data.  */
313	return NULL;
314
315      /* Is this the one we're looking for?  */
316      if (fde->start <= address && fde->end > address)
317	return fde;
318    }
319
320 no_match:
321  /* We found no FDE covering this address.  */
322  __libdw_seterrno (DWARF_E_NO_MATCH);
323  return NULL;
324}
325