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 
39 static int
compare_fde(const void * a,const void * b)40 compare_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 
65 static struct dwarf_fde *
intern_fde(Dwarf_CFI * cache,const Dwarf_FDE * entry)66 intern_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 
141 struct dwarf_fde *
142 internal_function
__libdw_fde_by_offset(Dwarf_CFI * cache,Dwarf_Off offset)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.  */
174 static Dwarf_Off
binary_search_fde(Dwarf_CFI * cache,Dwarf_Addr address)175 binary_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 
245 struct dwarf_fde *
246 internal_function
__libdw_find_fde(Dwarf_CFI * cache,Dwarf_Addr address)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