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 if (fde->instructions >= fde->instructions_end)
108 goto invalid;
109 get_uleb128 (len, fde->instructions, fde->instructions_end);
110 if ((Dwarf_Word) (fde->instructions_end - fde->instructions) < len)
111 {
112 invalid:
113 free (fde);
114 __libdw_seterrno (DWARF_E_INVALID_DWARF);
115 return NULL;
116 }
117 fde->instructions += len;
118 }
119 else
120 /* We had to understand all of the CIE augmentation string.
121 We've recorded the number of data bytes in FDEs. */
122 fde->instructions += cie->fde_augmentation_data_size;
123
124 /* Add the new entry to the search tree. */
125 struct dwarf_fde **tres = tsearch (fde, &cache->fde_tree, &compare_fde);
126 if (tres == NULL)
127 {
128 free (fde);
129 __libdw_seterrno (DWARF_E_NOMEM);
130 return NULL;
131 }
132 else if (*tres != fde)
133 {
134 /* There is already an FDE in the cache that covers the same
135 address range. That is odd. Ignore this FDE. And just use
136 the one in the cache for consistency. */
137 free (fde);
138 return *tres;
139 }
140
141 return fde;
142 }
143
144 struct dwarf_fde *
145 internal_function
__libdw_fde_by_offset(Dwarf_CFI * cache,Dwarf_Off offset)146 __libdw_fde_by_offset (Dwarf_CFI *cache, Dwarf_Off offset)
147 {
148 Dwarf_CFI_Entry entry;
149 Dwarf_Off next_offset;
150 int result = INTUSE(dwarf_next_cfi) (cache->e_ident,
151 &cache->data->d, CFI_IS_EH (cache),
152 offset, &next_offset, &entry);
153 if (result != 0)
154 {
155 if (result > 0)
156 invalid:
157 __libdw_seterrno (DWARF_E_INVALID_DWARF);
158 return NULL;
159 }
160
161 if (unlikely (dwarf_cfi_cie_p (&entry)))
162 goto invalid;
163
164 /* We have a new FDE to consider. */
165 struct dwarf_fde *fde = intern_fde (cache, &entry.fde);
166 if (fde == (void *) -1l || fde == NULL)
167 return NULL;
168
169 /* If this happened to be what we would have read next, notice it. */
170 if (cache->next_offset == offset)
171 cache->next_offset = next_offset;
172
173 return fde;
174 }
175
176 /* Use a binary search table in .eh_frame_hdr format, yield an FDE offset. */
177 static Dwarf_Off
binary_search_fde(Dwarf_CFI * cache,Dwarf_Addr address)178 binary_search_fde (Dwarf_CFI *cache, Dwarf_Addr address)
179 {
180 const size_t size = 2 * encoded_value_size (&cache->data->d, cache->e_ident,
181 cache->search_table_encoding,
182 NULL);
183 if (unlikely (size == 0))
184 return (Dwarf_Off) -1l;
185
186 /* Dummy used by read_encoded_value. */
187 Elf_Data_Scn dummy_cfi_hdr_data =
188 {
189 .d = { .d_buf = (void *) cache->search_table,
190 .d_size = cache->search_table_len }
191 };
192
193 Dwarf_CFI dummy_cfi =
194 {
195 .e_ident = cache->e_ident,
196 .datarel = cache->search_table_vaddr,
197 .frame_vaddr = cache->search_table_vaddr,
198 .data = &dummy_cfi_hdr_data
199 };
200
201 size_t l = 0, u = cache->search_table_entries;
202 while (l < u)
203 {
204 size_t idx = (l + u) / 2;
205
206 /* Max idx * size is checked against search_table len when
207 loading eh_frame_hdr. */
208 const uint8_t *p = &cache->search_table[idx * size];
209 Dwarf_Addr start;
210 if (unlikely (read_encoded_value (&dummy_cfi,
211 cache->search_table_encoding, &p,
212 &start)))
213 break;
214 if (address < start)
215 u = idx;
216 else
217 {
218 l = idx + 1;
219
220 Dwarf_Addr fde;
221 if (unlikely (read_encoded_value (&dummy_cfi,
222 cache->search_table_encoding, &p,
223 &fde)))
224 break;
225
226 /* If this is the last entry, its upper bound is assumed to be
227 the end of the module.
228 XXX really should be end of containing PT_LOAD segment */
229 if (l < cache->search_table_entries)
230 {
231 /* Look at the start address in the following entry. */
232 Dwarf_Addr end;
233 if (unlikely (read_encoded_value
234 (&dummy_cfi, cache->search_table_encoding, &p,
235 &end)))
236 break;
237 if (address >= end)
238 continue;
239 }
240
241 return fde - cache->frame_vaddr;
242 }
243 }
244
245 return (Dwarf_Off) -1l;
246 }
247
248 struct dwarf_fde *
249 internal_function
__libdw_find_fde(Dwarf_CFI * cache,Dwarf_Addr address)250 __libdw_find_fde (Dwarf_CFI *cache, Dwarf_Addr address)
251 {
252 /* Look for a cached FDE covering this address. */
253
254 const struct dwarf_fde fde_key = { .start = address, .end = 0 };
255 struct dwarf_fde **found = tfind (&fde_key, &cache->fde_tree, &compare_fde);
256 if (found != NULL)
257 return *found;
258
259 /* Use .eh_frame_hdr binary search table if possible. */
260 if (cache->search_table != NULL)
261 {
262 Dwarf_Off offset = binary_search_fde (cache, address);
263 if (offset == (Dwarf_Off) -1l)
264 goto no_match;
265 struct dwarf_fde *fde = __libdw_fde_by_offset (cache, offset);
266 if (likely (fde != NULL))
267 {
268 /* Sanity check the address range. */
269 if (unlikely (address < fde->start))
270 {
271 __libdw_seterrno (DWARF_E_INVALID_DWARF);
272 return NULL;
273 }
274 /* .eh_frame_hdr does not indicate length covered by FDE. */
275 if (unlikely (address >= fde->end))
276 goto no_match;
277 }
278 return fde;
279 }
280
281 /* It's not there. Read more CFI entries until we find it. */
282 while (1)
283 {
284 Dwarf_Off last_offset = cache->next_offset;
285 Dwarf_CFI_Entry entry;
286 int result = INTUSE(dwarf_next_cfi) (cache->e_ident,
287 &cache->data->d, CFI_IS_EH (cache),
288 last_offset, &cache->next_offset,
289 &entry);
290 if (result > 0)
291 break;
292 if (result < 0)
293 {
294 if (cache->next_offset == last_offset)
295 /* We couldn't progress past the bogus FDE. */
296 break;
297 /* Skip the loser and look at the next entry. */
298 continue;
299 }
300
301 if (dwarf_cfi_cie_p (&entry))
302 {
303 /* This is a CIE, not an FDE. We eagerly intern these
304 because the next FDE will usually refer to this CIE. */
305 __libdw_intern_cie (cache, last_offset, &entry.cie);
306 continue;
307 }
308
309 /* We have a new FDE to consider. */
310 struct dwarf_fde *fde = intern_fde (cache, &entry.fde);
311
312 if (fde == (void *) -1l) /* Bad FDE, but we can keep looking. */
313 continue;
314
315 if (fde == NULL) /* Bad data. */
316 return NULL;
317
318 /* Is this the one we're looking for? */
319 if (fde->start <= address && fde->end > address)
320 return fde;
321 }
322
323 no_match:
324 /* We found no FDE covering this address. */
325 __libdw_seterrno (DWARF_E_NO_MATCH);
326 return NULL;
327 }
328