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 : 625686 : compare_fde (const void *a, const void *b)
41 : : {
42 : 625686 : const struct dwarf_fde *fde1 = a;
43 : 625686 : 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 [ + + ]: 625686 : if (fde1->end == 0)
48 : : {
49 [ + + ]: 150798 : if (fde1->start < fde2->start)
50 : : return -1;
51 [ + + ]: 133732 : if (fde1->start >= fde2->end)
52 : 133582 : return 1;
53 : : }
54 : : else
55 : : {
56 [ + + ]: 474888 : if (fde2->start < fde1->start)
57 : : return 1;
58 [ + - ]: 41034 : if (fde2->start >= fde1->end)
59 : 41034 : return -1;
60 : : }
61 : :
62 : : return 0;
63 : : }
64 : :
65 : : static struct dwarf_fde *
66 : 38686 : intern_fde (Dwarf_CFI *cache, const Dwarf_FDE *entry)
67 : : {
68 : : /* Look up the new entry's CIE. */
69 : 38686 : struct dwarf_cie *cie = __libdw_find_cie (cache, entry->CIE_pointer);
70 [ - + ]: 38686 : if (cie == NULL)
71 : : return (void *) -1l;
72 : :
73 : 38686 : struct dwarf_fde *fde = malloc (sizeof (struct dwarf_fde));
74 [ - + ]: 38686 : if (fde == NULL)
75 : : {
76 : 0 : __libdw_seterrno (DWARF_E_NOMEM);
77 : 0 : return NULL;
78 : : }
79 : :
80 : 38686 : fde->instructions = entry->start;
81 : 38686 : fde->instructions_end = entry->end;
82 [ + - ]: 38686 : if (unlikely (read_encoded_value (cache, cie->fde_encoding,
83 : : &fde->instructions, &fde->start))
84 [ - + ]: 38686 : || 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 : 38686 : fde->end += fde->start;
92 : :
93 : : /* Make sure the fde actually covers a real code range. */
94 [ + + ]: 38686 : if (fde->start >= fde->end)
95 : : {
96 : 8 : free (fde);
97 : 8 : return (void *) -1;
98 : : }
99 : :
100 : 38678 : fde->cie = cie;
101 : :
102 [ + + ]: 38678 : 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 : 38486 : Dwarf_Word len;
107 [ - + ]: 38486 : if (fde->instructions >= fde->instructions_end)
108 : 0 : goto invalid;
109 : 38486 : get_uleb128 (len, fde->instructions, fde->instructions_end);
110 [ - + ]: 38486 : if ((Dwarf_Word) (fde->instructions_end - fde->instructions) < len)
111 : : {
112 : 0 : invalid:
113 : 0 : free (fde);
114 : 0 : __libdw_seterrno (DWARF_E_INVALID_DWARF);
115 : 0 : return NULL;
116 : : }
117 : 38486 : 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 : 192 : fde->instructions += cie->fde_augmentation_data_size;
123 : :
124 : : /* Add the new entry to the search tree. */
125 : 38678 : struct dwarf_fde **tres = tsearch (fde, &cache->fde_tree, &compare_fde);
126 [ - + ]: 38678 : if (tres == NULL)
127 : : {
128 : 0 : free (fde);
129 : 0 : __libdw_seterrno (DWARF_E_NOMEM);
130 : 0 : return NULL;
131 : : }
132 [ - + ]: 38678 : 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 : 0 : free (fde);
138 : 0 : return *tres;
139 : : }
140 : :
141 : : return fde;
142 : : }
143 : :
144 : : struct dwarf_fde *
145 : : internal_function
146 : 13126 : __libdw_fde_by_offset (Dwarf_CFI *cache, Dwarf_Off offset)
147 : : {
148 : 13126 : Dwarf_CFI_Entry entry;
149 : 13126 : Dwarf_Off next_offset;
150 : 26252 : int result = INTUSE(dwarf_next_cfi) (cache->e_ident,
151 : 13126 : &cache->data->d, CFI_IS_EH (cache),
152 : : offset, &next_offset, &entry);
153 [ - + ]: 13126 : if (result != 0)
154 : : {
155 [ # # ]: 0 : if (result > 0)
156 : 0 : invalid:
157 : 0 : __libdw_seterrno (DWARF_E_INVALID_DWARF);
158 : 0 : return NULL;
159 : : }
160 : :
161 [ - + ]: 13126 : if (unlikely (dwarf_cfi_cie_p (&entry)))
162 : 0 : goto invalid;
163 : :
164 : : /* We have a new FDE to consider. */
165 : 13126 : struct dwarf_fde *fde = intern_fde (cache, &entry.fde);
166 [ - + ]: 13126 : 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 [ + + ]: 13126 : if (cache->next_offset == offset)
171 : 12 : 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
178 : 13132 : binary_search_fde (Dwarf_CFI *cache, Dwarf_Addr address)
179 : : {
180 : 26264 : const size_t size = 2 * encoded_value_size (&cache->data->d, cache->e_ident,
181 : 13132 : cache->search_table_encoding,
182 : : NULL);
183 [ - + ]: 13132 : if (unlikely (size == 0))
184 : : return (Dwarf_Off) -1l;
185 : :
186 : : /* Dummy used by read_encoded_value. */
187 : 13132 : Elf_Data_Scn dummy_cfi_hdr_data =
188 : : {
189 : 13132 : .d = { .d_buf = (void *) cache->search_table,
190 : 13132 : .d_size = cache->search_table_len }
191 : : };
192 : :
193 : 13132 : Dwarf_CFI dummy_cfi =
194 : : {
195 : : .e_ident = cache->e_ident,
196 : : .datarel = cache->search_table_vaddr,
197 : 13132 : .frame_vaddr = cache->search_table_vaddr,
198 : : .data = &dummy_cfi_hdr_data
199 : : };
200 : :
201 : 13132 : size_t l = 0, u = cache->search_table_entries;
202 [ + + ]: 122408 : while (l < u)
203 : : {
204 : 122402 : size_t idx = (l + u) / 2;
205 : :
206 : : /* Max idx * size is checked against search_table len when
207 : : loading eh_frame_hdr. */
208 : 122402 : const uint8_t *p = &cache->search_table[idx * size];
209 : 122402 : Dwarf_Addr start;
210 [ + - ]: 122402 : if (unlikely (read_encoded_value (&dummy_cfi,
211 : : cache->search_table_encoding, &p,
212 : : &start)))
213 : : break;
214 [ + + ]: 122402 : if (address < start)
215 : 51358 : u = idx;
216 : : else
217 : : {
218 : 71044 : l = idx + 1;
219 : :
220 : 71044 : Dwarf_Addr fde;
221 [ + - ]: 71044 : 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 [ + + ]: 71044 : if (l < cache->search_table_entries)
230 : : {
231 : : /* Look at the start address in the following entry. */
232 : 71024 : Dwarf_Addr end;
233 [ + - ]: 71024 : if (unlikely (read_encoded_value
234 : : (&dummy_cfi, cache->search_table_encoding, &p,
235 : : &end)))
236 : : break;
237 [ + + ]: 71024 : if (address >= end)
238 : 57918 : continue;
239 : : }
240 : :
241 : 13126 : return fde - cache->frame_vaddr;
242 : : }
243 : : }
244 : :
245 : : return (Dwarf_Off) -1l;
246 : : }
247 : :
248 : : struct dwarf_fde *
249 : : internal_function
250 : 13610 : __libdw_find_fde (Dwarf_CFI *cache, Dwarf_Addr address)
251 : : {
252 : : /* Look for a cached FDE covering this address. */
253 : :
254 : 13610 : const struct dwarf_fde fde_key = { .start = address, .end = 0 };
255 : 13610 : struct dwarf_fde **found = tfind (&fde_key, &cache->fde_tree, &compare_fde);
256 [ + + ]: 13610 : if (found != NULL)
257 : 150 : return *found;
258 : :
259 : : /* Use .eh_frame_hdr binary search table if possible. */
260 [ + + ]: 13460 : if (cache->search_table != NULL)
261 : : {
262 : 13132 : Dwarf_Off offset = binary_search_fde (cache, address);
263 [ + + ]: 13132 : if (offset == (Dwarf_Off) -1l)
264 : 6 : goto no_match;
265 : 13126 : struct dwarf_fde *fde = __libdw_fde_by_offset (cache, offset);
266 [ + - ]: 13126 : if (likely (fde != NULL))
267 : : {
268 : : /* Sanity check the address range. */
269 [ - + ]: 13126 : if (unlikely (address < fde->start))
270 : : {
271 : 0 : __libdw_seterrno (DWARF_E_INVALID_DWARF);
272 : 0 : return NULL;
273 : : }
274 : : /* .eh_frame_hdr does not indicate length covered by FDE. */
275 [ + + ]: 13126 : if (unlikely (address >= fde->end))
276 : 2 : goto no_match;
277 : : }
278 : : return fde;
279 : : }
280 : :
281 : : /* It's not there. Read more CFI entries until we find it. */
282 : 26002 : while (1)
283 : : {
284 : 26002 : Dwarf_Off last_offset = cache->next_offset;
285 : 26002 : Dwarf_CFI_Entry entry;
286 : 52004 : int result = INTUSE(dwarf_next_cfi) (cache->e_ident,
287 : 26002 : &cache->data->d, CFI_IS_EH (cache),
288 : : last_offset, &cache->next_offset,
289 : : &entry);
290 [ + + ]: 26002 : if (result > 0)
291 : : break;
292 [ - + ]: 25756 : if (result < 0)
293 : : {
294 [ # # ]: 0 : 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 : 204 : continue;
299 : : }
300 : :
301 [ + + ]: 25756 : 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 : 196 : __libdw_intern_cie (cache, last_offset, &entry.cie);
306 : 196 : continue;
307 : : }
308 : :
309 : : /* We have a new FDE to consider. */
310 : 25560 : struct dwarf_fde *fde = intern_fde (cache, &entry.fde);
311 : :
312 [ + + ]: 25560 : if (fde == (void *) -1l) /* Bad FDE, but we can keep looking. */
313 : 8 : continue;
314 : :
315 [ + - ]: 25552 : if (fde == NULL) /* Bad data. */
316 : 82 : return NULL;
317 : :
318 : : /* Is this the one we're looking for? */
319 [ + + + + ]: 25552 : if (fde->start <= address && fde->end > address)
320 : 82 : return fde;
321 : : }
322 : :
323 : 254 : no_match:
324 : : /* We found no FDE covering this address. */
325 : 254 : __libdw_seterrno (DWARF_E_NO_MATCH);
326 : 254 : return NULL;
327 : : }
|