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)))
87 fde->end += fde->start;
91 if (cie->sized_augmentation_data)
93 /* The CIE augmentation says the FDE has a DW_FORM_block
94 before its actual instruction stream. */
96 get_uleb128 (len, fde->instructions);
97 if ((Dwarf_Word) (fde->instructions_end - fde->instructions) < len)
100 __libdw_seterrno (DWARF_E_INVALID_DWARF);
103 fde->instructions += len;
106 /* We had to understand all of the CIE augmentation string.
107 We've recorded the number of data bytes in FDEs. */
108 fde->instructions += cie->fde_augmentation_data_size;
110 /* Add the new entry to the search tree. */
111 if (tsearch (fde, &cache->fde_tree, &compare_fde) == NULL)
114 __libdw_seterrno (DWARF_E_NOMEM);
123 __libdw_fde_by_offset (Dwarf_CFI *cache, Dwarf_Off offset)
125 Dwarf_CFI_Entry entry;
126 Dwarf_Off next_offset;
127 int result = INTUSE(dwarf_next_cfi) (cache->e_ident,
128 &cache->data->d, CFI_IS_EH (cache),
129 offset, &next_offset, &entry);
134 __libdw_seterrno (DWARF_E_INVALID_DWARF);
138 if (unlikely (dwarf_cfi_cie_p (&entry)))
141 /* We have a new FDE to consider. */
142 struct dwarf_fde *fde = intern_fde (cache, &entry.fde);
143 if (fde == (void *) -1l || fde == NULL)
146 /* If this happened to be what we would have read next, notice it. */
147 if (cache->next_offset == offset)
148 cache->next_offset = next_offset;
153 /* Use a binary search table in .eh_frame_hdr format, yield an FDE offset. */
155 binary_search_fde (Dwarf_CFI *cache, Dwarf_Addr address)
157 const size_t size = 2 * encoded_value_size (&cache->data->d, cache->e_ident,
158 cache->search_table_encoding,
161 /* Dummy used by read_encoded_value. */
162 Dwarf_CFI dummy_cfi =
164 .e_ident = cache->e_ident,
165 .datarel = cache->search_table_vaddr,
166 .frame_vaddr = cache->search_table_vaddr,
169 size_t l = 0, u = cache->search_table_entries;
172 size_t idx = (l + u) / 2;
174 const uint8_t *p = &cache->search_table[idx * size];
176 if (unlikely (read_encoded_value (&dummy_cfi,
177 cache->search_table_encoding, &p,
185 if (unlikely (read_encoded_value (&dummy_cfi,
186 cache->search_table_encoding, &p,
189 if (address >= start)
193 /* If this is the last entry, its upper bound is assumed to be
194 the end of the module.
195 XXX really should be end of containing PT_LOAD segment */
196 if (l < cache->search_table_entries)
198 /* Look at the start address in the following entry. */
200 if (unlikely (read_encoded_value
201 (&dummy_cfi, cache->search_table_encoding, &p,
208 return fde - cache->frame_vaddr;
213 return (Dwarf_Off) -1l;
218 __libdw_find_fde (Dwarf_CFI *cache, Dwarf_Addr address)
220 /* Look for a cached FDE covering this address. */
222 const struct dwarf_fde fde_key = { .start = address, .end = 0 };
223 struct dwarf_fde **found = tfind (&fde_key, &cache->fde_tree, &compare_fde);
227 /* Use .eh_frame_hdr binary search table if possible. */
228 if (cache->search_table != NULL)
230 Dwarf_Off offset = binary_search_fde (cache, address);
231 if (offset == (Dwarf_Off) -1l)
233 struct dwarf_fde *fde = __libdw_fde_by_offset (cache, offset);
234 if (unlikely (fde != NULL)
235 /* Sanity check the address range. */
236 && unlikely (address < fde->start || address >= fde->end))
238 __libdw_seterrno (DWARF_E_INVALID_DWARF);
244 /* It's not there. Read more CFI entries until we find it. */
247 Dwarf_Off last_offset = cache->next_offset;
248 Dwarf_CFI_Entry entry;
249 int result = INTUSE(dwarf_next_cfi) (cache->e_ident,
250 &cache->data->d, CFI_IS_EH (cache),
251 last_offset, &cache->next_offset,
257 if (cache->next_offset == last_offset)
258 /* We couldn't progress past the bogus FDE. */
260 /* Skip the loser and look at the next entry. */
264 if (dwarf_cfi_cie_p (&entry))
266 /* This is a CIE, not an FDE. We eagerly intern these
267 because the next FDE will usually refer to this CIE. */
268 __libdw_intern_cie (cache, last_offset, &entry.cie);
272 /* We have a new FDE to consider. */
273 struct dwarf_fde *fde = intern_fde (cache, &entry.fde);
275 if (fde == (void *) -1l) /* Bad FDE, but we can keep looking. */
278 if (fde == NULL) /* Bad data. */
281 /* Is this the one we're looking for? */
282 if (fde->start <= address && fde->end > address)
287 /* We found no FDE covering this address. */
288 __libdw_seterrno (DWARF_E_NO_MATCH);