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