1/* FDE reading. 2 Copyright (C) 2009-2010, 2014 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 39static int 40compare_fde (const void *a, const void *b) 41{ 42 const struct dwarf_fde *fde1 = a; 43 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 if (fde1->end == 0) 48 { 49 if (fde1->start < fde2->start) 50 return -1; 51 if (fde1->start >= fde2->end) 52 return 1; 53 } 54 else 55 { 56 if (fde2->start < fde1->start) 57 return 1; 58 if (fde2->start >= fde1->end) 59 return -1; 60 } 61 62 return 0; 63} 64 65static struct dwarf_fde * 66intern_fde (Dwarf_CFI *cache, const Dwarf_FDE *entry) 67{ 68 /* Look up the new entry's CIE. */ 69 struct dwarf_cie *cie = __libdw_find_cie (cache, entry->CIE_pointer); 70 if (cie == NULL) 71 return (void *) -1l; 72 73 struct dwarf_fde *fde = malloc (sizeof (struct dwarf_fde)); 74 if (fde == NULL) 75 { 76 __libdw_seterrno (DWARF_E_NOMEM); 77 return NULL; 78 } 79 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))) 86 { 87 free (fde); 88 __libdw_seterrno (DWARF_E_INVALID_DWARF); 89 return NULL; 90 } 91 fde->end += fde->start; 92 93 fde->cie = cie; 94 95 if (cie->sized_augmentation_data) 96 { 97 /* The CIE augmentation says the FDE has a DW_FORM_block 98 before its actual instruction stream. */ 99 Dwarf_Word len; 100 get_uleb128 (len, fde->instructions, fde->instructions_end); 101 if ((Dwarf_Word) (fde->instructions_end - fde->instructions) < len) 102 { 103 free (fde); 104 __libdw_seterrno (DWARF_E_INVALID_DWARF); 105 return NULL; 106 } 107 fde->instructions += len; 108 } 109 else 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; 113 114 /* Add the new entry to the search tree. */ 115 if (tsearch (fde, &cache->fde_tree, &compare_fde) == NULL) 116 { 117 free (fde); 118 __libdw_seterrno (DWARF_E_NOMEM); 119 return NULL; 120 } 121 122 return fde; 123} 124 125struct dwarf_fde * 126internal_function 127__libdw_fde_by_offset (Dwarf_CFI *cache, Dwarf_Off offset) 128{ 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); 134 if (result != 0) 135 { 136 if (result > 0) 137 invalid: 138 __libdw_seterrno (DWARF_E_INVALID_DWARF); 139 return NULL; 140 } 141 142 if (unlikely (dwarf_cfi_cie_p (&entry))) 143 goto invalid; 144 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) 148 return NULL; 149 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; 153 154 return fde; 155} 156 157/* Use a binary search table in .eh_frame_hdr format, yield an FDE offset. */ 158static Dwarf_Off 159binary_search_fde (Dwarf_CFI *cache, Dwarf_Addr address) 160{ 161 const size_t size = 2 * encoded_value_size (&cache->data->d, cache->e_ident, 162 cache->search_table_encoding, 163 NULL); 164 165 /* Dummy used by read_encoded_value. */ 166 Dwarf_CFI dummy_cfi = 167 { 168 .e_ident = cache->e_ident, 169 .datarel = cache->search_table_vaddr, 170 .frame_vaddr = cache->search_table_vaddr, 171 }; 172 173 size_t l = 0, u = cache->search_table_entries; 174 while (l < u) 175 { 176 size_t idx = (l + u) / 2; 177 178 const uint8_t *p = &cache->search_table[idx * size]; 179 Dwarf_Addr start; 180 if (unlikely (read_encoded_value (&dummy_cfi, 181 cache->search_table_encoding, &p, 182 &start))) 183 break; 184 if (address < start) 185 u = idx; 186 else 187 { 188 l = idx + 1; 189 190 Dwarf_Addr fde; 191 if (unlikely (read_encoded_value (&dummy_cfi, 192 cache->search_table_encoding, &p, 193 &fde))) 194 break; 195 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) 200 { 201 /* Look at the start address in the following entry. */ 202 Dwarf_Addr end; 203 if (unlikely (read_encoded_value 204 (&dummy_cfi, cache->search_table_encoding, &p, 205 &end))) 206 break; 207 if (address >= end) 208 continue; 209 } 210 211 return fde - cache->frame_vaddr; 212 } 213 } 214 215 return (Dwarf_Off) -1l; 216} 217 218struct dwarf_fde * 219internal_function 220__libdw_find_fde (Dwarf_CFI *cache, Dwarf_Addr address) 221{ 222 /* Look for a cached FDE covering this address. */ 223 224 const struct dwarf_fde fde_key = { .start = address, .end = 0 }; 225 struct dwarf_fde **found = tfind (&fde_key, &cache->fde_tree, &compare_fde); 226 if (found != NULL) 227 return *found; 228 229 /* Use .eh_frame_hdr binary search table if possible. */ 230 if (cache->search_table != NULL) 231 { 232 Dwarf_Off offset = binary_search_fde (cache, address); 233 if (offset == (Dwarf_Off) -1l) 234 goto no_match; 235 struct dwarf_fde *fde = __libdw_fde_by_offset (cache, offset); 236 if (likely (fde != NULL)) 237 { 238 /* Sanity check the address range. */ 239 if (unlikely (address < fde->start)) 240 { 241 __libdw_seterrno (DWARF_E_INVALID_DWARF); 242 return NULL; 243 } 244 /* .eh_frame_hdr does not indicate length covered by FDE. */ 245 if (unlikely (address >= fde->end)) 246 goto no_match; 247 } 248 return fde; 249 } 250 251 /* It's not there. Read more CFI entries until we find it. */ 252 while (1) 253 { 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, 259 &entry); 260 if (result > 0) 261 break; 262 if (result < 0) 263 { 264 if (cache->next_offset == last_offset) 265 /* We couldn't progress past the bogus FDE. */ 266 break; 267 /* Skip the loser and look at the next entry. */ 268 continue; 269 } 270 271 if (dwarf_cfi_cie_p (&entry)) 272 { 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); 276 continue; 277 } 278 279 /* We have a new FDE to consider. */ 280 struct dwarf_fde *fde = intern_fde (cache, &entry.fde); 281 282 if (fde == (void *) -1l) /* Bad FDE, but we can keep looking. */ 283 continue; 284 285 if (fde == NULL) /* Bad data. */ 286 return NULL; 287 288 /* Is this the one we're looking for? */ 289 if (fde->start <= address && fde->end > address) 290 return fde; 291 } 292 293 no_match: 294 /* We found no FDE covering this address. */ 295 __libdw_seterrno (DWARF_E_NO_MATCH); 296 return NULL; 297} 298