1 /* FDE reading. 2 Copyright (C) 2009-2010 Red Hat, Inc. 3 This file is part of Red Hat elfutils. 4 5 Red Hat elfutils is free software; you can redistribute it and/or modify 6 it under the terms of the GNU General Public License as published by the 7 Free Software Foundation; version 2 of the License. 8 9 Red Hat elfutils is distributed in the hope that it will be useful, but 10 WITHOUT ANY WARRANTY; without even the implied warranty of 11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 12 General Public License for more details. 13 14 You should have received a copy of the GNU General Public License along 15 with Red Hat elfutils; if not, write to the Free Software Foundation, 16 Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301 USA. 17 18 In addition, as a special exception, Red Hat, Inc. gives You the 19 additional right to link the code of Red Hat elfutils with code licensed 20 under any Open Source Initiative certified open source license 21 (http://www.opensource.org/licenses/index.php) which requires the 22 distribution of source code with any binary distribution and to 23 distribute linked combinations of the two. Non-GPL Code permitted under 24 this exception must only link to the code of Red Hat elfutils through 25 those well defined interfaces identified in the file named EXCEPTION 26 found in the source code files (the "Approved Interfaces"). The files 27 of Non-GPL Code may instantiate templates or use macros or inline 28 functions from the Approved Interfaces without causing the resulting 29 work to be covered by the GNU General Public License. Only Red Hat, 30 Inc. may make changes or additions to the list of Approved Interfaces. 31 Red Hat's grant of this exception is conditioned upon your not adding 32 any new exceptions. If you wish to add a new Approved Interface or 33 exception, please contact Red Hat. You must obey the GNU General Public 34 License in all respects for all of the Red Hat elfutils code and other 35 code used in conjunction with Red Hat elfutils except the Non-GPL Code 36 covered by this exception. If you modify this file, you may extend this 37 exception to your version of the file, but you are not obligated to do 38 so. If you do not wish to provide this exception without modification, 39 you must delete this exception statement from your version and license 40 this file solely under the GPL without exception. 41 42 Red Hat elfutils is an included package of the Open Invention Network. 43 An included package of the Open Invention Network is a package for which 44 Open Invention Network licensees cross-license their patents. No patent 45 license is granted, either expressly or impliedly, by designation as an 46 included package. Should you wish to participate in the Open Invention 47 Network licensing program, please visit www.openinventionnetwork.com 48 <http://www.openinventionnetwork.com>. */ 49 50 #ifdef HAVE_CONFIG_H 51 # include <config.h> 52 #endif 53 54 #include "cfi.h" 55 #include <search.h> 56 #include <stdlib.h> 57 58 #include "encoded-value.h" 59 60 static int 61 compare_fde (const void *a, const void *b) 62 { 63 const struct dwarf_fde *fde1 = a; 64 const struct dwarf_fde *fde2 = b; 65 66 /* Find out which of the two arguments is the search value. 67 It has end offset 0. */ 68 if (fde1->end == 0) 69 { 70 if (fde1->start < fde2->start) 71 return -1; 72 if (fde1->start >= fde2->end) 73 return 1; 74 } 75 else 76 { 77 if (fde2->start < fde1->start) 78 return 1; 79 if (fde2->start >= fde1->end) 80 return -1; 81 } 82 83 return 0; 84 } 85 86 static struct dwarf_fde * 87 intern_fde (Dwarf_CFI *cache, const Dwarf_FDE *entry) 88 { 89 /* Look up the new entry's CIE. */ 90 struct dwarf_cie *cie = __libdw_find_cie (cache, entry->CIE_pointer); 91 if (cie == NULL) 92 return (void *) -1l; 93 94 struct dwarf_fde *fde = malloc (sizeof (struct dwarf_fde)); 95 if (fde == NULL) 96 { 97 __libdw_seterrno (DWARF_E_NOMEM); 98 return NULL; 99 } 100 101 fde->instructions = entry->start; 102 fde->instructions_end = entry->end; 103 if (unlikely (read_encoded_value (cache, cie->fde_encoding, 104 &fde->instructions, &fde->start)) 105 || unlikely (read_encoded_value (cache, cie->fde_encoding & 0x0f, 106 &fde->instructions, &fde->end))) 107 return NULL; 108 fde->end += fde->start; 109 110 fde->cie = cie; 111 112 if (cie->sized_augmentation_data) 113 { 114 /* The CIE augmentation says the FDE has a DW_FORM_block 115 before its actual instruction stream. */ 116 Dwarf_Word len; 117 get_uleb128 (len, fde->instructions); 118 if ((Dwarf_Word) (fde->instructions_end - fde->instructions) < len) 119 { 120 free (fde); 121 __libdw_seterrno (DWARF_E_INVALID_DWARF); 122 return NULL; 123 } 124 fde->instructions += len; 125 } 126 else 127 /* We had to understand all of the CIE augmentation string. 128 We've recorded the number of data bytes in FDEs. */ 129 fde->instructions += cie->fde_augmentation_data_size; 130 131 /* Add the new entry to the search tree. */ 132 if (tsearch (fde, &cache->fde_tree, &compare_fde) == NULL) 133 { 134 free (fde); 135 __libdw_seterrno (DWARF_E_NOMEM); 136 return NULL; 137 } 138 139 return fde; 140 } 141 142 struct dwarf_fde * 143 internal_function 144 __libdw_fde_by_offset (Dwarf_CFI *cache, Dwarf_Off offset) 145 { 146 Dwarf_CFI_Entry entry; 147 Dwarf_Off next_offset; 148 int result = INTUSE(dwarf_next_cfi) (cache->e_ident, 149 &cache->data->d, CFI_IS_EH (cache), 150 offset, &next_offset, &entry); 151 if (result != 0) 152 { 153 if (result > 0) 154 invalid: 155 __libdw_seterrno (DWARF_E_INVALID_DWARF); 156 return NULL; 157 } 158 159 if (unlikely (dwarf_cfi_cie_p (&entry))) 160 goto invalid; 161 162 /* We have a new FDE to consider. */ 163 struct dwarf_fde *fde = intern_fde (cache, &entry.fde); 164 if (fde == (void *) -1l || fde == NULL) 165 return NULL; 166 167 /* If this happened to be what we would have read next, notice it. */ 168 if (cache->next_offset == offset) 169 cache->next_offset = next_offset; 170 171 return fde; 172 } 173 174 /* Use a binary search table in .eh_frame_hdr format, yield an FDE offset. */ 175 static Dwarf_Off 176 binary_search_fde (Dwarf_CFI *cache, Dwarf_Addr address) 177 { 178 const size_t size = 2 * encoded_value_size (&cache->data->d, cache->e_ident, 179 cache->search_table_encoding, 180 NULL); 181 182 /* Dummy used by read_encoded_value. */ 183 Dwarf_CFI dummy_cfi = 184 { 185 .e_ident = cache->e_ident, 186 .datarel = cache->search_table_vaddr, 187 .frame_vaddr = cache->search_table_vaddr, 188 }; 189 190 size_t l = 0, u = cache->search_table_entries; 191 while (l < u) 192 { 193 size_t idx = (l + u) / 2; 194 195 const uint8_t *p = &cache->search_table[idx * size]; 196 Dwarf_Addr start; 197 if (unlikely (read_encoded_value (&dummy_cfi, 198 cache->search_table_encoding, &p, 199 &start))) 200 break; 201 if (address < start) 202 u = idx; 203 else 204 { 205 Dwarf_Addr fde; 206 if (unlikely (read_encoded_value (&dummy_cfi, 207 cache->search_table_encoding, &p, 208 &fde))) 209 break; 210 if (address >= start) 211 { 212 l = idx + 1; 213 214 /* If this is the last entry, its upper bound is assumed to be 215 the end of the module. 216 XXX really should be end of containing PT_LOAD segment */ 217 if (l < cache->search_table_entries) 218 { 219 /* Look at the start address in the following entry. */ 220 Dwarf_Addr end; 221 if (unlikely (read_encoded_value 222 (&dummy_cfi, cache->search_table_encoding, &p, 223 &end))) 224 break; 225 if (address >= end) 226 continue; 227 } 228 229 return fde - cache->frame_vaddr; 230 } 231 } 232 } 233 234 return (Dwarf_Off) -1l; 235 } 236 237 struct dwarf_fde * 238 internal_function 239 __libdw_find_fde (Dwarf_CFI *cache, Dwarf_Addr address) 240 { 241 /* Look for a cached FDE covering this address. */ 242 243 const struct dwarf_fde fde_key = { .start = address, .end = 0 }; 244 struct dwarf_fde **found = tfind (&fde_key, &cache->fde_tree, &compare_fde); 245 if (found != NULL) 246 return *found; 247 248 /* Use .eh_frame_hdr binary search table if possible. */ 249 if (cache->search_table != NULL) 250 { 251 Dwarf_Off offset = binary_search_fde (cache, address); 252 if (offset == (Dwarf_Off) -1l) 253 goto no_match; 254 struct dwarf_fde *fde = __libdw_fde_by_offset (cache, offset); 255 if (unlikely (fde != NULL) 256 /* Sanity check the address range. */ 257 && unlikely (address < fde->start || address >= fde->end)) 258 { 259 __libdw_seterrno (DWARF_E_INVALID_DWARF); 260 return NULL; 261 } 262 return fde; 263 } 264 265 /* It's not there. Read more CFI entries until we find it. */ 266 while (1) 267 { 268 Dwarf_Off last_offset = cache->next_offset; 269 Dwarf_CFI_Entry entry; 270 int result = INTUSE(dwarf_next_cfi) (cache->e_ident, 271 &cache->data->d, CFI_IS_EH (cache), 272 last_offset, &cache->next_offset, 273 &entry); 274 if (result > 0) 275 break; 276 if (result < 0) 277 { 278 if (cache->next_offset == last_offset) 279 /* We couldn't progress past the bogus FDE. */ 280 break; 281 /* Skip the loser and look at the next entry. */ 282 continue; 283 } 284 285 if (dwarf_cfi_cie_p (&entry)) 286 { 287 /* This is a CIE, not an FDE. We eagerly intern these 288 because the next FDE will usually refer to this CIE. */ 289 __libdw_intern_cie (cache, last_offset, &entry.cie); 290 continue; 291 } 292 293 /* We have a new FDE to consider. */ 294 struct dwarf_fde *fde = intern_fde (cache, &entry.fde); 295 296 if (fde == (void *) -1l) /* Bad FDE, but we can keep looking. */ 297 continue; 298 299 if (fde == NULL) /* Bad data. */ 300 return NULL; 301 302 /* Is this the one we're looking for? */ 303 if (fde->start <= address && fde->end > address) 304 return fde; 305 } 306 307 no_match: 308 /* We found no FDE covering this address. */ 309 __libdw_seterrno (DWARF_E_NO_MATCH); 310 return NULL; 311 } 312
