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 <search.h> 35 #include <stdlib.h> 36 37 #include "encoded-value.h" 38 39 static int 40 compare_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 65 static struct dwarf_fde * 66 intern_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 /* Make sure the fde actually covers a real code range. */ 94 if (fde->start >= fde->end) 95 { 96 free (fde); 97 return (void *) -1; 98 } 99 100 fde->cie = cie; 101 102 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 Dwarf_Word len; 107 get_uleb128 (len, fde->instructions, fde->instructions_end); 108 if ((Dwarf_Word) (fde->instructions_end - fde->instructions) < len) 109 { 110 free (fde); 111 __libdw_seterrno (DWARF_E_INVALID_DWARF); 112 return NULL; 113 } 114 fde->instructions += len; 115 } 116 else 117 /* We had to understand all of the CIE augmentation string. 118 We've recorded the number of data bytes in FDEs. */ 119 fde->instructions += cie->fde_augmentation_data_size; 120 121 /* Add the new entry to the search tree. */ 122 struct dwarf_fde **tres = tsearch (fde, &cache->fde_tree, &compare_fde); 123 if (tres == NULL) 124 { 125 free (fde); 126 __libdw_seterrno (DWARF_E_NOMEM); 127 return NULL; 128 } 129 else if (*tres != fde) 130 { 131 /* There is already an FDE in the cache that covers the same 132 address range. That is odd. Ignore this FDE. And just use 133 the one in the cache for consistency. */ 134 free (fde); 135 return *tres; 136 } 137 138 return fde; 139 } 140 141 struct dwarf_fde * 142 internal_function 143 __libdw_fde_by_offset (Dwarf_CFI *cache, Dwarf_Off offset) 144 { 145 Dwarf_CFI_Entry entry; 146 Dwarf_Off next_offset; 147 int result = INTUSE(dwarf_next_cfi) (cache->e_ident, 148 &cache->data->d, CFI_IS_EH (cache), 149 offset, &next_offset, &entry); 150 if (result != 0) 151 { 152 if (result > 0) 153 invalid: 154 __libdw_seterrno (DWARF_E_INVALID_DWARF); 155 return NULL; 156 } 157 158 if (unlikely (dwarf_cfi_cie_p (&entry))) 159 goto invalid; 160 161 /* We have a new FDE to consider. */ 162 struct dwarf_fde *fde = intern_fde (cache, &entry.fde); 163 if (fde == (void *) -1l || fde == NULL) 164 return NULL; 165 166 /* If this happened to be what we would have read next, notice it. */ 167 if (cache->next_offset == offset) 168 cache->next_offset = next_offset; 169 170 return fde; 171 } 172 173 /* Use a binary search table in .eh_frame_hdr format, yield an FDE offset. */ 174 static Dwarf_Off 175 binary_search_fde (Dwarf_CFI *cache, Dwarf_Addr address) 176 { 177 const size_t size = 2 * encoded_value_size (&cache->data->d, cache->e_ident, 178 cache->search_table_encoding, 179 NULL); 180 if (unlikely (size == 0)) 181 return (Dwarf_Off) -1l; 182 183 /* Dummy used by read_encoded_value. */ 184 Elf_Data_Scn dummy_cfi_hdr_data = 185 { 186 .d = { .d_buf = (void *) cache->search_table, 187 .d_size = cache->search_table_len } 188 }; 189 190 Dwarf_CFI dummy_cfi = 191 { 192 .e_ident = cache->e_ident, 193 .datarel = cache->search_table_vaddr, 194 .frame_vaddr = cache->search_table_vaddr, 195 .data = &dummy_cfi_hdr_data 196 }; 197 198 size_t l = 0, u = cache->search_table_entries; 199 while (l < u) 200 { 201 size_t idx = (l + u) / 2; 202 203 /* Max idx * size is checked against search_table len when 204 loading eh_frame_hdr. */ 205 const uint8_t *p = &cache->search_table[idx * size]; 206 Dwarf_Addr start; 207 if (unlikely (read_encoded_value (&dummy_cfi, 208 cache->search_table_encoding, &p, 209 &start))) 210 break; 211 if (address < start) 212 u = idx; 213 else 214 { 215 l = idx + 1; 216 217 Dwarf_Addr fde; 218 if (unlikely (read_encoded_value (&dummy_cfi, 219 cache->search_table_encoding, &p, 220 &fde))) 221 break; 222 223 /* If this is the last entry, its upper bound is assumed to be 224 the end of the module. 225 XXX really should be end of containing PT_LOAD segment */ 226 if (l < cache->search_table_entries) 227 { 228 /* Look at the start address in the following entry. */ 229 Dwarf_Addr end; 230 if (unlikely (read_encoded_value 231 (&dummy_cfi, cache->search_table_encoding, &p, 232 &end))) 233 break; 234 if (address >= end) 235 continue; 236 } 237 238 return fde - cache->frame_vaddr; 239 } 240 } 241 242 return (Dwarf_Off) -1l; 243 } 244 245 struct dwarf_fde * 246 internal_function 247 __libdw_find_fde (Dwarf_CFI *cache, Dwarf_Addr address) 248 { 249 /* Look for a cached FDE covering this address. */ 250 251 const struct dwarf_fde fde_key = { .start = address, .end = 0 }; 252 struct dwarf_fde **found = tfind (&fde_key, &cache->fde_tree, &compare_fde); 253 if (found != NULL) 254 return *found; 255 256 /* Use .eh_frame_hdr binary search table if possible. */ 257 if (cache->search_table != NULL) 258 { 259 Dwarf_Off offset = binary_search_fde (cache, address); 260 if (offset == (Dwarf_Off) -1l) 261 goto no_match; 262 struct dwarf_fde *fde = __libdw_fde_by_offset (cache, offset); 263 if (likely (fde != NULL)) 264 { 265 /* Sanity check the address range. */ 266 if (unlikely (address < fde->start)) 267 { 268 __libdw_seterrno (DWARF_E_INVALID_DWARF); 269 return NULL; 270 } 271 /* .eh_frame_hdr does not indicate length covered by FDE. */ 272 if (unlikely (address >= fde->end)) 273 goto no_match; 274 } 275 return fde; 276 } 277 278 /* It's not there. Read more CFI entries until we find it. */ 279 while (1) 280 { 281 Dwarf_Off last_offset = cache->next_offset; 282 Dwarf_CFI_Entry entry; 283 int result = INTUSE(dwarf_next_cfi) (cache->e_ident, 284 &cache->data->d, CFI_IS_EH (cache), 285 last_offset, &cache->next_offset, 286 &entry); 287 if (result > 0) 288 break; 289 if (result < 0) 290 { 291 if (cache->next_offset == last_offset) 292 /* We couldn't progress past the bogus FDE. */ 293 break; 294 /* Skip the loser and look at the next entry. */ 295 continue; 296 } 297 298 if (dwarf_cfi_cie_p (&entry)) 299 { 300 /* This is a CIE, not an FDE. We eagerly intern these 301 because the next FDE will usually refer to this CIE. */ 302 __libdw_intern_cie (cache, last_offset, &entry.cie); 303 continue; 304 } 305 306 /* We have a new FDE to consider. */ 307 struct dwarf_fde *fde = intern_fde (cache, &entry.fde); 308 309 if (fde == (void *) -1l) /* Bad FDE, but we can keep looking. */ 310 continue; 311 312 if (fde == NULL) /* Bad data. */ 313 return NULL; 314 315 /* Is this the one we're looking for? */ 316 if (fde->start <= address && fde->end > address) 317 return fde; 318 } 319 320 no_match: 321 /* We found no FDE covering this address. */ 322 __libdw_seterrno (DWARF_E_NO_MATCH); 323 return NULL; 324 } 325
