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