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 "eu-search.h"
35 : : #include <stdlib.h>
36 : :
37 : : #include "encoded-value.h"
38 : :
39 : : static int
40 : 650106 : compare_fde (const void *a, const void *b)
41 : : {
42 : 650106 : const struct dwarf_fde *fde1 = a;
43 : 650106 : 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 [ + + ]: 650106 : if (fde1->end == 0)
48 : : {
49 [ + + ]: 162938 : if (fde1->start < fde2->start)
50 : : return -1;
51 [ + + ]: 144754 : if (fde1->start >= fde2->end)
52 : 144610 : return 1;
53 : : }
54 : : else
55 : : {
56 [ + + ]: 487168 : if (fde2->start < fde1->start)
57 : : return 1;
58 [ + - ]: 42172 : if (fde2->start >= fde1->end)
59 : 42172 : return -1;
60 : : }
61 : :
62 : : return 0;
63 : : }
64 : :
65 : : static struct dwarf_fde *
66 : 39654 : intern_fde (Dwarf_CFI *cache, const Dwarf_FDE *entry)
67 : : {
68 : : /* Look up the new entry's CIE. */
69 : 39654 : struct dwarf_cie *cie = __libdw_find_cie (cache, entry->CIE_pointer);
70 [ - + ]: 39654 : if (cie == NULL)
71 : : return (void *) -1l;
72 : :
73 : 39654 : struct dwarf_fde *fde = malloc (sizeof (struct dwarf_fde));
74 [ - + ]: 39654 : if (fde == NULL)
75 : : {
76 : 0 : __libdw_seterrno (DWARF_E_NOMEM);
77 : 0 : return NULL;
78 : : }
79 : :
80 : 39654 : fde->instructions = entry->start;
81 : 39654 : fde->instructions_end = entry->end;
82 [ + - ]: 39654 : if (unlikely (read_encoded_value (cache, cie->fde_encoding,
83 : : &fde->instructions, &fde->start))
84 [ - + ]: 39654 : || 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 : 39654 : fde->end += fde->start;
92 : :
93 : : /* Make sure the fde actually covers a real code range. */
94 [ + + ]: 39654 : if (fde->start >= fde->end)
95 : : {
96 : 8 : free (fde);
97 : 8 : return (void *) -1;
98 : : }
99 : :
100 : 39646 : fde->cie = cie;
101 : :
102 [ + + ]: 39646 : 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 : 39454 : Dwarf_Word len;
107 [ - + ]: 39454 : if (fde->instructions >= fde->instructions_end)
108 : 0 : goto invalid;
109 : 39454 : get_uleb128 (len, fde->instructions, fde->instructions_end);
110 [ - + ]: 39454 : 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 : 39454 : 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 : 39646 : struct dwarf_fde **tres = eu_tsearch_nolock (fde, &cache->fde_tree,
126 : : &compare_fde);
127 [ - + ]: 39646 : if (tres == NULL)
128 : : {
129 : 0 : free (fde);
130 : 0 : __libdw_seterrno (DWARF_E_NOMEM);
131 : 0 : return NULL;
132 : : }
133 [ - + ]: 39646 : else if (*tres != fde)
134 : : {
135 : : /* There is already an FDE in the cache that covers the same
136 : : address range. That is odd. Ignore this FDE. And just use
137 : : the one in the cache for consistency. */
138 : 0 : free (fde);
139 : 0 : return *tres;
140 : : }
141 : :
142 : : return fde;
143 : : }
144 : :
145 : : struct dwarf_fde *
146 : : internal_function
147 : 14094 : __libdw_fde_by_offset (Dwarf_CFI *cache, Dwarf_Off offset)
148 : : {
149 : 14094 : Dwarf_CFI_Entry entry;
150 : 14094 : Dwarf_Off next_offset;
151 : 28188 : int result = INTUSE(dwarf_next_cfi) (cache->e_ident,
152 : 14094 : &cache->data->d, CFI_IS_EH (cache),
153 : : offset, &next_offset, &entry);
154 [ - + ]: 14094 : if (result != 0)
155 : : {
156 [ # # ]: 0 : if (result > 0)
157 : 0 : invalid:
158 : 0 : __libdw_seterrno (DWARF_E_INVALID_DWARF);
159 : 0 : return NULL;
160 : : }
161 : :
162 [ - + ]: 14094 : if (unlikely (dwarf_cfi_cie_p (&entry)))
163 : 0 : goto invalid;
164 : :
165 : : /* We have a new FDE to consider. */
166 : 14094 : struct dwarf_fde *fde = intern_fde (cache, &entry.fde);
167 [ - + ]: 14094 : if (fde == (void *) -1l || fde == NULL)
168 : : return NULL;
169 : :
170 : : /* If this happened to be what we would have read next, notice it. */
171 [ + + ]: 14094 : if (cache->next_offset == offset)
172 : 14 : cache->next_offset = next_offset;
173 : :
174 : : return fde;
175 : : }
176 : :
177 : : /* Use a binary search table in .eh_frame_hdr format, yield an FDE offset. */
178 : : static Dwarf_Off
179 : 14100 : binary_search_fde (Dwarf_CFI *cache, Dwarf_Addr address)
180 : : {
181 : 28200 : const size_t size = 2 * encoded_value_size (&cache->data->d, cache->e_ident,
182 : 14100 : cache->search_table_encoding,
183 : : NULL);
184 [ - + ]: 14100 : if (unlikely (size == 0))
185 : : return (Dwarf_Off) -1l;
186 : :
187 : : /* Dummy used by read_encoded_value. */
188 : 14100 : Elf_Data_Scn dummy_cfi_hdr_data =
189 : : {
190 : 14100 : .d = { .d_buf = (void *) cache->search_table,
191 : 14100 : .d_size = cache->search_table_len }
192 : : };
193 : :
194 : 14100 : Dwarf_CFI dummy_cfi =
195 : : {
196 : : .e_ident = cache->e_ident,
197 : : .datarel = cache->search_table_vaddr,
198 : 14100 : .frame_vaddr = cache->search_table_vaddr,
199 : : .data = &dummy_cfi_hdr_data
200 : : };
201 : :
202 : 14100 : size_t l = 0, u = cache->search_table_entries;
203 [ + + ]: 132746 : while (l < u)
204 : : {
205 : 132740 : size_t idx = (l + u) / 2;
206 : :
207 : : /* Max idx * size is checked against search_table len when
208 : : loading eh_frame_hdr. */
209 : 132740 : const uint8_t *p = &cache->search_table[idx * size];
210 : 132740 : Dwarf_Addr start;
211 [ + - ]: 132740 : if (unlikely (read_encoded_value (&dummy_cfi,
212 : : cache->search_table_encoding, &p,
213 : : &start)))
214 : : break;
215 [ + + ]: 132740 : if (address < start)
216 : 55728 : u = idx;
217 : : else
218 : : {
219 : 77012 : l = idx + 1;
220 : :
221 : 77012 : Dwarf_Addr fde;
222 [ + - ]: 77012 : if (unlikely (read_encoded_value (&dummy_cfi,
223 : : cache->search_table_encoding, &p,
224 : : &fde)))
225 : : break;
226 : :
227 : : /* If this is the last entry, its upper bound is assumed to be
228 : : the end of the module.
229 : : XXX really should be end of containing PT_LOAD segment */
230 [ + + ]: 77012 : if (l < cache->search_table_entries)
231 : : {
232 : : /* Look at the start address in the following entry. */
233 : 76992 : Dwarf_Addr end;
234 [ + - ]: 76992 : if (unlikely (read_encoded_value
235 : : (&dummy_cfi, cache->search_table_encoding, &p,
236 : : &end)))
237 : : break;
238 [ + + ]: 76992 : if (address >= end)
239 : 62918 : continue;
240 : : }
241 : :
242 : 14094 : return fde - cache->frame_vaddr;
243 : : }
244 : : }
245 : :
246 : : return (Dwarf_Off) -1l;
247 : : }
248 : :
249 : : struct dwarf_fde *
250 : : internal_function
251 : 14572 : __libdw_find_fde (Dwarf_CFI *cache, Dwarf_Addr address)
252 : : {
253 : : /* Look for a cached FDE covering this address. */
254 : :
255 : 14572 : const struct dwarf_fde fde_key = { .start = address, .end = 0 };
256 : 14572 : struct dwarf_fde **found = eu_tfind_nolock (&fde_key, &cache->fde_tree,
257 : : &compare_fde);
258 [ + + ]: 14572 : if (found != NULL)
259 : 144 : return *found;
260 : :
261 : : /* Use .eh_frame_hdr binary search table if possible. */
262 [ + + ]: 14428 : if (cache->search_table != NULL)
263 : : {
264 : 14100 : Dwarf_Off offset = binary_search_fde (cache, address);
265 [ + + ]: 14100 : if (offset == (Dwarf_Off) -1l)
266 : 6 : goto no_match;
267 : 14094 : struct dwarf_fde *fde = __libdw_fde_by_offset (cache, offset);
268 [ + - ]: 14094 : if (likely (fde != NULL))
269 : : {
270 : : /* Sanity check the address range. */
271 [ - + ]: 14094 : if (unlikely (address < fde->start))
272 : : {
273 : 0 : __libdw_seterrno (DWARF_E_INVALID_DWARF);
274 : 0 : return NULL;
275 : : }
276 : : /* .eh_frame_hdr does not indicate length covered by FDE. */
277 [ + + ]: 14094 : if (unlikely (address >= fde->end))
278 : 2 : goto no_match;
279 : : }
280 : : return fde;
281 : : }
282 : :
283 : : /* It's not there. Read more CFI entries until we find it. */
284 : 26002 : while (1)
285 : : {
286 : 26002 : Dwarf_Off last_offset = cache->next_offset;
287 : 26002 : Dwarf_CFI_Entry entry;
288 : 52004 : int result = INTUSE(dwarf_next_cfi) (cache->e_ident,
289 : 26002 : &cache->data->d, CFI_IS_EH (cache),
290 : : last_offset, &cache->next_offset,
291 : : &entry);
292 [ + + ]: 26002 : if (result > 0)
293 : : break;
294 [ - + ]: 25756 : if (result < 0)
295 : : {
296 [ # # ]: 0 : if (cache->next_offset == last_offset)
297 : : /* We couldn't progress past the bogus FDE. */
298 : : break;
299 : : /* Skip the loser and look at the next entry. */
300 : 204 : continue;
301 : : }
302 : :
303 [ + + ]: 25756 : if (dwarf_cfi_cie_p (&entry))
304 : : {
305 : : /* This is a CIE, not an FDE. We eagerly intern these
306 : : because the next FDE will usually refer to this CIE. */
307 : 196 : __libdw_intern_cie (cache, last_offset, &entry.cie);
308 : 196 : continue;
309 : : }
310 : :
311 : : /* We have a new FDE to consider. */
312 : 25560 : struct dwarf_fde *fde = intern_fde (cache, &entry.fde);
313 : :
314 [ + + ]: 25560 : if (fde == (void *) -1l) /* Bad FDE, but we can keep looking. */
315 : 8 : continue;
316 : :
317 [ + - ]: 25552 : if (fde == NULL) /* Bad data. */
318 : 82 : return NULL;
319 : :
320 : : /* Is this the one we're looking for? */
321 [ + + + + ]: 25552 : if (fde->start <= address && fde->end > address)
322 : 82 : return fde;
323 : : }
324 : :
325 : 254 : no_match:
326 : : /* We found no FDE covering this address. */
327 : 254 : __libdw_seterrno (DWARF_E_NO_MATCH);
328 : 254 : return NULL;
329 : : }
|