2 Copyright (C) 2009-2010 Red Hat, Inc.
3 This file is part of elfutils.
5 This file is free software; you can redistribute it and/or modify
6 it under the terms of either
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
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
18 or both in parallel, as here.
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.
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/>. */
37 #include "encoded-value.h"
40 compare_fde (const void *a, const void *b)
42 const struct dwarf_fde *fde1 = a;
43 const struct dwarf_fde *fde2 = b;
45 /* Find out which of the two arguments is the search value.
46 It has end offset 0. */
49 if (fde1->start < fde2->start)
51 if (fde1->start >= fde2->end)
56 if (fde2->start < fde1->start)
58 if (fde2->start >= fde1->end)
65 static struct dwarf_fde *
66 intern_fde (Dwarf_CFI *cache, const Dwarf_FDE *entry)
68 /* Look up the new entry's CIE. */
69 struct dwarf_cie *cie = __libdw_find_cie (cache, entry->CIE_pointer);
73 struct dwarf_fde *fde = malloc (sizeof (struct dwarf_fde));
76 __libdw_seterrno (DWARF_E_NOMEM);
80 fde->instructions = entry->start;
81 fde->instructions_end = entry->end;
82 if (unlikely (read_encoded_value (cache, cie->fde_encoding,
83 &fde->instructions, &fde->start))
84 || unlikely (read_encoded_value (cache, cie->fde_encoding & 0x0f,
85 &fde->instructions, &fde->end)))
88 __libdw_seterrno (DWARF_E_INVALID_DWARF);
91 fde->end += fde->start;
95 if (cie->sized_augmentation_data)
97 /* The CIE augmentation says the FDE has a DW_FORM_block
98 before its actual instruction stream. */
100 get_uleb128 (len, fde->instructions);
101 if ((Dwarf_Word) (fde->instructions_end - fde->instructions) < len)
104 __libdw_seterrno (DWARF_E_INVALID_DWARF);
107 fde->instructions += len;
110 /* We had to understand all of the CIE augmentation string.
111 We've recorded the number of data bytes in FDEs. */
112 fde->instructions += cie->fde_augmentation_data_size;
114 /* Add the new entry to the search tree. */
115 if (tsearch (fde, &cache->fde_tree, &compare_fde) == NULL)
118 __libdw_seterrno (DWARF_E_NOMEM);
127 __libdw_fde_by_offset (Dwarf_CFI *cache, Dwarf_Off offset)
129 Dwarf_CFI_Entry entry;
130 Dwarf_Off next_offset;
131 int result = INTUSE(dwarf_next_cfi) (cache->e_ident,
132 &cache->data->d, CFI_IS_EH (cache),
133 offset, &next_offset, &entry);
138 __libdw_seterrno (DWARF_E_INVALID_DWARF);
142 if (unlikely (dwarf_cfi_cie_p (&entry)))
145 /* We have a new FDE to consider. */
146 struct dwarf_fde *fde = intern_fde (cache, &entry.fde);
147 if (fde == (void *) -1l || fde == NULL)
150 /* If this happened to be what we would have read next, notice it. */
151 if (cache->next_offset == offset)
152 cache->next_offset = next_offset;
157 /* Use a binary search table in .eh_frame_hdr format, yield an FDE offset. */
159 binary_search_fde (Dwarf_CFI *cache, Dwarf_Addr address)
161 const size_t size = 2 * encoded_value_size (&cache->data->d, cache->e_ident,
162 cache->search_table_encoding,
165 /* Dummy used by read_encoded_value. */
166 Dwarf_CFI dummy_cfi =
168 .e_ident = cache->e_ident,
169 .datarel = cache->search_table_vaddr,
170 .frame_vaddr = cache->search_table_vaddr,
173 size_t l = 0, u = cache->search_table_entries;
176 size_t idx = (l + u) / 2;
178 const uint8_t *p = &cache->search_table[idx * size];
180 if (unlikely (read_encoded_value (&dummy_cfi,
181 cache->search_table_encoding, &p,
191 if (unlikely (read_encoded_value (&dummy_cfi,
192 cache->search_table_encoding, &p,
196 /* If this is the last entry, its upper bound is assumed to be
197 the end of the module.
198 XXX really should be end of containing PT_LOAD segment */
199 if (l < cache->search_table_entries)
201 /* Look at the start address in the following entry. */
203 if (unlikely (read_encoded_value
204 (&dummy_cfi, cache->search_table_encoding, &p,
211 return fde - cache->frame_vaddr;
215 return (Dwarf_Off) -1l;
220 __libdw_find_fde (Dwarf_CFI *cache, Dwarf_Addr address)
222 /* Look for a cached FDE covering this address. */
224 const struct dwarf_fde fde_key = { .start = address, .end = 0 };
225 struct dwarf_fde **found = tfind (&fde_key, &cache->fde_tree, &compare_fde);
229 /* Use .eh_frame_hdr binary search table if possible. */
230 if (cache->search_table != NULL)
232 Dwarf_Off offset = binary_search_fde (cache, address);
233 if (offset == (Dwarf_Off) -1l)
235 struct dwarf_fde *fde = __libdw_fde_by_offset (cache, offset);
236 if (likely (fde != NULL))
238 /* Sanity check the address range. */
239 if (unlikely (address < fde->start))
241 __libdw_seterrno (DWARF_E_INVALID_DWARF);
244 /* .eh_frame_hdr does not indicate length covered by FDE. */
245 if (unlikely (address >= fde->end))
251 /* It's not there. Read more CFI entries until we find it. */
254 Dwarf_Off last_offset = cache->next_offset;
255 Dwarf_CFI_Entry entry;
256 int result = INTUSE(dwarf_next_cfi) (cache->e_ident,
257 &cache->data->d, CFI_IS_EH (cache),
258 last_offset, &cache->next_offset,
264 if (cache->next_offset == last_offset)
265 /* We couldn't progress past the bogus FDE. */
267 /* Skip the loser and look at the next entry. */
271 if (dwarf_cfi_cie_p (&entry))
273 /* This is a CIE, not an FDE. We eagerly intern these
274 because the next FDE will usually refer to this CIE. */
275 __libdw_intern_cie (cache, last_offset, &entry.cie);
279 /* We have a new FDE to consider. */
280 struct dwarf_fde *fde = intern_fde (cache, &entry.fde);
282 if (fde == (void *) -1l) /* Bad FDE, but we can keep looking. */
285 if (fde == NULL) /* Bad data. */
288 /* Is this the one we're looking for? */
289 if (fde->start <= address && fde->end > address)
294 /* We found no FDE covering this address. */
295 __libdw_seterrno (DWARF_E_NO_MATCH);