Branch data 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 : 303134 : compare_fde (const void *a, const void *b)
41 : : {
42 : 303134 : const struct dwarf_fde *fde1 = a;
43 : 303134 : 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 [ + + ]: 303134 : if (fde1->end == 0)
48 : : {
49 [ + + ]: 70519 : if (fde1->start < fde2->start)
50 : : return -1;
51 [ + + ]: 62277 : if (fde1->start >= fde2->end)
52 : 62206 : return 1;
53 : : }
54 : : else
55 : : {
56 [ + + ]: 232615 : if (fde2->start < fde1->start)
57 : : return 1;
58 [ + + ]: 20289 : if (fde2->start >= fde1->end)
59 : 20283 : return -1;
60 : : }
61 : :
62 : : return 0;
63 : : }
64 : :
65 : : static struct dwarf_fde *
66 : 19015 : intern_fde (Dwarf_CFI *cache, const Dwarf_FDE *entry)
67 : : {
68 : : /* Look up the new entry's CIE. */
69 : 19015 : struct dwarf_cie *cie = __libdw_find_cie (cache, entry->CIE_pointer);
70 [ + - ]: 19015 : if (cie == NULL)
71 : : return (void *) -1l;
72 : :
73 : 19015 : struct dwarf_fde *fde = malloc (sizeof (struct dwarf_fde));
74 [ - + ]: 19015 : if (fde == NULL)
75 : : {
76 : 0 : __libdw_seterrno (DWARF_E_NOMEM);
77 : 0 : return NULL;
78 : : }
79 : :
80 : 19015 : fde->instructions = entry->start;
81 : 19015 : fde->instructions_end = entry->end;
82 [ + - ]: 19015 : if (unlikely (read_encoded_value (cache, cie->fde_encoding,
83 : : &fde->instructions, &fde->start))
84 [ - + ]: 19015 : || 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 : 19015 : fde->end += fde->start;
92 : :
93 : : /* Make sure the fde actually covers a real code range. */
94 [ + + ]: 19015 : if (fde->start >= fde->end)
95 : : {
96 : 4 : free (fde);
97 : 4 : return (void *) -1;
98 : : }
99 : :
100 : 19011 : fde->cie = cie;
101 : :
102 [ + + ]: 19011 : 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 : 18915 : Dwarf_Word len;
107 : 18915 : get_uleb128 (len, fde->instructions, fde->instructions_end);
108 [ - + ]: 18915 : 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 : 18915 : 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 : 96 : fde->instructions += cie->fde_augmentation_data_size;
120 : :
121 : : /* Add the new entry to the search tree. */
122 : 19011 : struct dwarf_fde **tres = tsearch (fde, &cache->fde_tree, &compare_fde);
123 [ - + ]: 19011 : if (tres == NULL)
124 : : {
125 : 0 : free (fde);
126 : 0 : __libdw_seterrno (DWARF_E_NOMEM);
127 : 0 : return NULL;
128 : : }
129 [ + + ]: 19011 : 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 : 6 : free (fde);
135 : 6 : return *tres;
136 : : }
137 : :
138 : : return fde;
139 : : }
140 : :
141 : : struct dwarf_fde *
142 : : internal_function
143 : 6239 : __libdw_fde_by_offset (Dwarf_CFI *cache, Dwarf_Off offset)
144 : : {
145 : 6239 : Dwarf_CFI_Entry entry;
146 : 6239 : Dwarf_Off next_offset;
147 : 12478 : int result = INTUSE(dwarf_next_cfi) (cache->e_ident,
148 : 6239 : &cache->data->d, CFI_IS_EH (cache),
149 : : offset, &next_offset, &entry);
150 [ - + ]: 6239 : if (result != 0)
151 : : {
152 [ # # ]: 0 : if (result > 0)
153 : 0 : invalid:
154 : 0 : __libdw_seterrno (DWARF_E_INVALID_DWARF);
155 : 0 : return NULL;
156 : : }
157 : :
158 [ - + ]: 6239 : if (unlikely (dwarf_cfi_cie_p (&entry)))
159 : 0 : goto invalid;
160 : :
161 : : /* We have a new FDE to consider. */
162 : 6239 : struct dwarf_fde *fde = intern_fde (cache, &entry.fde);
163 [ + - ]: 6239 : 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 [ + + ]: 6239 : if (cache->next_offset == offset)
168 : 2 : 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 : 6242 : binary_search_fde (Dwarf_CFI *cache, Dwarf_Addr address)
176 : : {
177 : 6242 : const size_t size = 2 * encoded_value_size (&cache->data->d, cache->e_ident,
178 : : cache->search_table_encoding,
179 : : NULL);
180 [ + - ]: 6242 : if (unlikely (size == 0))
181 : : return (Dwarf_Off) -1l;
182 : :
183 : : /* Dummy used by read_encoded_value. */
184 : 6242 : Elf_Data_Scn dummy_cfi_hdr_data =
185 : : {
186 : 6242 : .d = { .d_buf = (void *) cache->search_table,
187 : 6242 : .d_size = cache->search_table_len }
188 : : };
189 : :
190 : 6242 : Dwarf_CFI dummy_cfi =
191 : : {
192 : : .e_ident = cache->e_ident,
193 : : .datarel = cache->search_table_vaddr,
194 : 6242 : .frame_vaddr = cache->search_table_vaddr,
195 : : .data = &dummy_cfi_hdr_data
196 : : };
197 : :
198 : 6242 : size_t l = 0, u = cache->search_table_entries;
199 [ + + ]: 57721 : while (l < u)
200 : : {
201 : 57718 : size_t idx = (l + u) / 2;
202 : :
203 : : /* Max idx * size is checked against search_table len when
204 : : loading eh_frame_hdr. */
205 : 57718 : const uint8_t *p = &cache->search_table[idx * size];
206 : 57718 : Dwarf_Addr start;
207 [ + - ]: 57718 : if (unlikely (read_encoded_value (&dummy_cfi,
208 : : cache->search_table_encoding, &p,
209 : : &start)))
210 : : break;
211 [ + + ]: 57718 : if (address < start)
212 : 24396 : u = idx;
213 : : else
214 : : {
215 : 33322 : l = idx + 1;
216 : :
217 : 33322 : Dwarf_Addr fde;
218 [ + - ]: 33322 : 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 [ + + ]: 33322 : if (l < cache->search_table_entries)
227 : : {
228 : : /* Look at the start address in the following entry. */
229 : 33312 : Dwarf_Addr end;
230 [ + - ]: 33312 : if (unlikely (read_encoded_value
231 : : (&dummy_cfi, cache->search_table_encoding, &p,
232 : : &end)))
233 : : break;
234 [ + + ]: 33312 : if (address >= end)
235 : 27083 : continue;
236 : : }
237 : :
238 : 6239 : return fde - cache->frame_vaddr;
239 : : }
240 : : }
241 : :
242 : : return (Dwarf_Off) -1l;
243 : : }
244 : :
245 : : struct dwarf_fde *
246 : : internal_function
247 : 6475 : __libdw_find_fde (Dwarf_CFI *cache, Dwarf_Addr address)
248 : : {
249 : : /* Look for a cached FDE covering this address. */
250 : :
251 : 6475 : const struct dwarf_fde fde_key = { .start = address, .end = 0 };
252 : 6475 : struct dwarf_fde **found = tfind (&fde_key, &cache->fde_tree, &compare_fde);
253 [ + + ]: 6475 : if (found != NULL)
254 : 71 : return *found;
255 : :
256 : : /* Use .eh_frame_hdr binary search table if possible. */
257 [ + + ]: 6404 : if (cache->search_table != NULL)
258 : : {
259 : 6242 : Dwarf_Off offset = binary_search_fde (cache, address);
260 [ + + ]: 6242 : if (offset == (Dwarf_Off) -1l)
261 : 3 : goto no_match;
262 : 6239 : struct dwarf_fde *fde = __libdw_fde_by_offset (cache, offset);
263 [ + - ]: 6239 : if (likely (fde != NULL))
264 : : {
265 : : /* Sanity check the address range. */
266 [ - + ]: 6239 : 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 [ + + ]: 6239 : if (unlikely (address >= fde->end))
273 : 10 : goto no_match;
274 : : }
275 : : return fde;
276 : : }
277 : :
278 : : /* It's not there. Read more CFI entries until we find it. */
279 : 12995 : while (1)
280 : : {
281 : 12995 : Dwarf_Off last_offset = cache->next_offset;
282 : 12995 : Dwarf_CFI_Entry entry;
283 : 25990 : int result = INTUSE(dwarf_next_cfi) (cache->e_ident,
284 : 12995 : &cache->data->d, CFI_IS_EH (cache),
285 : : last_offset, &cache->next_offset,
286 : : &entry);
287 [ + + ]: 12995 : if (result > 0)
288 : : break;
289 [ - + ]: 12874 : 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 : 102 : continue;
296 : : }
297 : :
298 [ + + ]: 12874 : 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 : 98 : __libdw_intern_cie (cache, last_offset, &entry.cie);
303 : 98 : continue;
304 : : }
305 : :
306 : : /* We have a new FDE to consider. */
307 : 12776 : struct dwarf_fde *fde = intern_fde (cache, &entry.fde);
308 : :
309 [ + + ]: 12776 : if (fde == (void *) -1l) /* Bad FDE, but we can keep looking. */
310 : 4 : continue;
311 : :
312 [ + - ]: 12772 : if (fde == NULL) /* Bad data. */
313 : 41 : return NULL;
314 : :
315 : : /* Is this the one we're looking for? */
316 [ + + + + ]: 12772 : if (fde->start <= address && fde->end > address)
317 : 41 : return fde;
318 : : }
319 : :
320 : 134 : no_match:
321 : : /* We found no FDE covering this address. */
322 : 134 : __libdw_seterrno (DWARF_E_NO_MATCH);
323 : 134 : return NULL;
324 : : }
|
