Line data Source code
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
40 253204 : compare_fde (const void *a, const void *b)
41 : {
42 253204 : const struct dwarf_fde *fde1 = a;
43 253204 : 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 253204 : if (fde1->end == 0)
48 : {
49 45594 : if (fde1->start < fde2->start)
50 : return -1;
51 39187 : if (fde1->start >= fde2->end)
52 : return 1;
53 : }
54 : else
55 : {
56 207610 : if (fde2->start < fde1->start)
57 : return 1;
58 18404 : if (fde2->start >= fde1->end)
59 : return -1;
60 : }
61 :
62 76 : return 0;
63 : }
64 :
65 : static struct dwarf_fde *
66 17369 : intern_fde (Dwarf_CFI *cache, const Dwarf_FDE *entry)
67 : {
68 : /* Look up the new entry's CIE. */
69 17369 : struct dwarf_cie *cie = __libdw_find_cie (cache, entry->CIE_pointer);
70 17369 : if (cie == NULL)
71 : return (void *) -1l;
72 :
73 17369 : struct dwarf_fde *fde = malloc (sizeof (struct dwarf_fde));
74 17369 : if (fde == NULL)
75 : {
76 0 : __libdw_seterrno (DWARF_E_NOMEM);
77 0 : return NULL;
78 : }
79 :
80 17369 : fde->instructions = entry->start;
81 17369 : fde->instructions_end = entry->end;
82 17369 : if (unlikely (read_encoded_value (cache, cie->fde_encoding,
83 : &fde->instructions, &fde->start))
84 17369 : || unlikely (read_encoded_value (cache, cie->fde_encoding & 0x0f,
85 : &fde->instructions, &fde->end)))
86 : {
87 0 : free (fde);
88 0 : __libdw_seterrno (DWARF_E_INVALID_DWARF);
89 0 : return NULL;
90 : }
91 17369 : fde->end += fde->start;
92 :
93 : /* Make sure the fde actually covers a real code range. */
94 17369 : if (fde->start >= fde->end)
95 : {
96 4 : free (fde);
97 4 : return (void *) -1;
98 : }
99 :
100 17365 : fde->cie = cie;
101 :
102 17365 : 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 17281 : get_uleb128 (len, fde->instructions, fde->instructions_end);
108 17281 : if ((Dwarf_Word) (fde->instructions_end - fde->instructions) < len)
109 : {
110 0 : free (fde);
111 0 : __libdw_seterrno (DWARF_E_INVALID_DWARF);
112 0 : return NULL;
113 : }
114 17281 : 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 84 : fde->instructions += cie->fde_augmentation_data_size;
120 :
121 : /* Add the new entry to the search tree. */
122 17365 : struct dwarf_fde **tres = tsearch (fde, &cache->fde_tree, &compare_fde);
123 17365 : if (tres == NULL)
124 : {
125 0 : free (fde);
126 0 : __libdw_seterrno (DWARF_E_NOMEM);
127 0 : return NULL;
128 : }
129 17365 : 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 2 : free (fde);
135 2 : return *tres;
136 : }
137 :
138 : return fde;
139 : }
140 :
141 : struct dwarf_fde *
142 : internal_function
143 4607 : __libdw_fde_by_offset (Dwarf_CFI *cache, Dwarf_Off offset)
144 : {
145 : Dwarf_CFI_Entry entry;
146 : Dwarf_Off next_offset;
147 9214 : int result = INTUSE(dwarf_next_cfi) (cache->e_ident,
148 9214 : &cache->data->d, CFI_IS_EH (cache),
149 : offset, &next_offset, &entry);
150 4607 : if (result != 0)
151 : {
152 0 : if (result > 0)
153 0 : invalid:
154 0 : __libdw_seterrno (DWARF_E_INVALID_DWARF);
155 : return NULL;
156 : }
157 :
158 4607 : if (unlikely (dwarf_cfi_cie_p (&entry)))
159 : goto invalid;
160 :
161 : /* We have a new FDE to consider. */
162 4607 : struct dwarf_fde *fde = intern_fde (cache, &entry.fde);
163 4607 : 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 4607 : if (cache->next_offset == offset)
168 7 : 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
175 4610 : binary_search_fde (Dwarf_CFI *cache, Dwarf_Addr address)
176 : {
177 9220 : const size_t size = 2 * encoded_value_size (&cache->data->d, cache->e_ident,
178 4610 : cache->search_table_encoding,
179 : NULL);
180 4610 : if (unlikely (size == 0))
181 : return (Dwarf_Off) -1l;
182 :
183 : /* Dummy used by read_encoded_value. */
184 13830 : Elf_Data_Scn dummy_cfi_hdr_data =
185 : {
186 4610 : .d = { .d_buf = (void *) cache->search_table,
187 4610 : .d_size = cache->search_table_len }
188 : };
189 :
190 9220 : Dwarf_CFI dummy_cfi =
191 : {
192 : .e_ident = cache->e_ident,
193 : .datarel = cache->search_table_vaddr,
194 4610 : .frame_vaddr = cache->search_table_vaddr,
195 : .data = &dummy_cfi_hdr_data
196 : };
197 :
198 4610 : size_t l = 0, u = cache->search_table_entries;
199 42024 : while (l < u)
200 : {
201 37411 : size_t idx = (l + u) / 2;
202 :
203 : /* Max idx * size is checked against search_table len when
204 : loading eh_frame_hdr. */
205 37411 : const uint8_t *p = &cache->search_table[idx * size];
206 : Dwarf_Addr start;
207 37411 : if (unlikely (read_encoded_value (&dummy_cfi,
208 : cache->search_table_encoding, &p,
209 : &start)))
210 : break;
211 37411 : if (address < start)
212 15825 : u = idx;
213 : else
214 : {
215 21586 : l = idx + 1;
216 :
217 : Dwarf_Addr fde;
218 21586 : 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 21586 : if (l < cache->search_table_entries)
227 : {
228 : /* Look at the start address in the following entry. */
229 : Dwarf_Addr end;
230 21580 : if (unlikely (read_encoded_value
231 : (&dummy_cfi, cache->search_table_encoding, &p,
232 : &end)))
233 : break;
234 21580 : if (address >= end)
235 16979 : continue;
236 : }
237 :
238 4607 : return fde - cache->frame_vaddr;
239 : }
240 : }
241 :
242 : return (Dwarf_Off) -1l;
243 : }
244 :
245 : struct dwarf_fde *
246 : internal_function
247 4835 : __libdw_find_fde (Dwarf_CFI *cache, Dwarf_Addr address)
248 : {
249 : /* Look for a cached FDE covering this address. */
250 :
251 4835 : const struct dwarf_fde fde_key = { .start = address, .end = 0 };
252 4835 : struct dwarf_fde **found = tfind (&fde_key, &cache->fde_tree, &compare_fde);
253 4835 : if (found != NULL)
254 74 : return *found;
255 :
256 : /* Use .eh_frame_hdr binary search table if possible. */
257 4761 : if (cache->search_table != NULL)
258 : {
259 4610 : Dwarf_Off offset = binary_search_fde (cache, address);
260 4610 : if (offset == (Dwarf_Off) -1l)
261 : goto no_match;
262 4607 : struct dwarf_fde *fde = __libdw_fde_by_offset (cache, offset);
263 4607 : if (likely (fde != NULL))
264 : {
265 : /* Sanity check the address range. */
266 4607 : if (unlikely (address < fde->start))
267 : {
268 0 : __libdw_seterrno (DWARF_E_INVALID_DWARF);
269 0 : return NULL;
270 : }
271 : /* .eh_frame_hdr does not indicate length covered by FDE. */
272 4607 : 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 12965 : Dwarf_Off last_offset = cache->next_offset;
282 : Dwarf_CFI_Entry entry;
283 38895 : int result = INTUSE(dwarf_next_cfi) (cache->e_ident,
284 25930 : &cache->data->d, CFI_IS_EH (cache),
285 : last_offset, &cache->next_offset,
286 : &entry);
287 12965 : if (result > 0)
288 : break;
289 12848 : if (result < 0)
290 : {
291 0 : 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 90 : continue;
296 : }
297 :
298 12848 : 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 86 : __libdw_intern_cie (cache, last_offset, &entry.cie);
303 86 : continue;
304 : }
305 :
306 : /* We have a new FDE to consider. */
307 12762 : struct dwarf_fde *fde = intern_fde (cache, &entry.fde);
308 :
309 12762 : if (fde == (void *) -1l) /* Bad FDE, but we can keep looking. */
310 4 : continue;
311 :
312 12758 : if (fde == NULL) /* Bad data. */
313 34 : return NULL;
314 :
315 : /* Is this the one we're looking for? */
316 12758 : if (fde->start <= address && fde->end > address)
317 : return fde;
318 : }
319 :
320 7 : no_match:
321 : /* We found no FDE covering this address. */
322 124 : __libdw_seterrno (DWARF_E_NO_MATCH);
323 124 : return NULL;
324 : }
|
