1/* CFI program execution. 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 <dwarf.h> 34#include "../libebl/libebl.h" 35#include "cfi.h" 36#include "memory-access.h" 37#include "encoded-value.h" 38#include "system.h" 39#include <assert.h> 40#include <stdlib.h> 41#include <string.h> 42 43#define CFI_PRIMARY_MAX 0x3f 44 45static Dwarf_Frame * 46duplicate_frame_state (const Dwarf_Frame *original, 47 Dwarf_Frame *prev) 48{ 49 size_t size = offsetof (Dwarf_Frame, regs[original->nregs]); 50 Dwarf_Frame *copy = malloc (size); 51 if (likely (copy != NULL)) 52 { 53 memcpy (copy, original, size); 54 copy->prev = prev; 55 } 56 return copy; 57} 58 59static inline bool 60enough_registers (Dwarf_Word reg, Dwarf_Frame **pfs, int *result) 61{ 62 /* Don't allow insanely large register numbers. 268435456 registers 63 should be enough for anybody. And very large values might overflow 64 the array size and offsetof calculations below. */ 65 if (unlikely (reg >= INT32_MAX / sizeof ((*pfs)->regs[0]))) 66 { 67 *result = DWARF_E_INVALID_CFI; 68 return false; 69 } 70 71 if ((*pfs)->nregs <= reg) 72 { 73 size_t size = offsetof (Dwarf_Frame, regs[reg + 1]); 74 Dwarf_Frame *bigger = realloc (*pfs, size); 75 if (unlikely (bigger == NULL)) 76 { 77 *result = DWARF_E_NOMEM; 78 return false; 79 } 80 else 81 { 82 eu_static_assert (reg_unspecified == 0); 83 memset (bigger->regs + bigger->nregs, 0, 84 (reg + 1 - bigger->nregs) * sizeof bigger->regs[0]); 85 bigger->nregs = reg + 1; 86 *pfs = bigger; 87 } 88 } 89 return true; 90} 91 92static inline void 93require_cfa_offset (Dwarf_Frame *fs) 94{ 95 if (unlikely (fs->cfa_rule != cfa_offset)) 96 fs->cfa_rule = cfa_invalid; 97} 98 99/* Returns a DWARF_E_* error code, usually NOERROR or INVALID_CFI. 100 Frees *STATE on failure. */ 101static int 102execute_cfi (Dwarf_CFI *cache, 103 const struct dwarf_cie *cie, 104 Dwarf_Frame **state, 105 const uint8_t *program, const uint8_t *const end, bool abi_cfi, 106 Dwarf_Addr loc, Dwarf_Addr find_pc) 107{ 108 /* The caller should not give us anything out of range. */ 109 assert (loc <= find_pc); 110 111 int result = DWARF_E_NOERROR; 112 113#define cfi_assert(ok) do { \ 114 if (likely (ok)) break; \ 115 result = DWARF_E_INVALID_CFI; \ 116 goto out; \ 117 } while (0) 118 119 Dwarf_Frame *fs = *state; 120 121#define register_rule(regno, r_rule, r_value) do { \ 122 if (unlikely (! enough_registers (regno, &fs, &result))) \ 123 goto out; \ 124 fs->regs[regno].rule = reg_##r_rule; \ 125 fs->regs[regno].value = (r_value); \ 126 } while (0) 127 128 while (program < end) 129 { 130 uint8_t opcode = *program++; 131 Dwarf_Word regno; 132 Dwarf_Word offset; 133 Dwarf_Word sf_offset; 134 Dwarf_Word operand = opcode & CFI_PRIMARY_MAX; 135 switch (opcode) 136 { 137 /* These cases move LOC, i.e. "create a new table row". */ 138 139 case DW_CFA_advance_loc1: 140 operand = *program++; 141 case DW_CFA_advance_loc + 0 ... DW_CFA_advance_loc + CFI_PRIMARY_MAX: 142 advance_loc: 143 loc += operand * cie->code_alignment_factor; 144 break; 145 146 case DW_CFA_advance_loc2: 147 cfi_assert (program + 2 <= end); 148 operand = read_2ubyte_unaligned_inc (cache, program); 149 goto advance_loc; 150 case DW_CFA_advance_loc4: 151 cfi_assert (program + 4 <= end); 152 operand = read_4ubyte_unaligned_inc (cache, program); 153 goto advance_loc; 154 case DW_CFA_MIPS_advance_loc8: 155 cfi_assert (program + 8 <= end); 156 operand = read_8ubyte_unaligned_inc (cache, program); 157 goto advance_loc; 158 159 case DW_CFA_set_loc: 160 if (likely (!read_encoded_value (cache, cie->fde_encoding, 161 &program, &loc))) 162 break; 163 result = INTUSE(dwarf_errno) (); 164 goto out; 165 166 /* Now all following cases affect this row, but do not touch LOC. 167 These cases end with 'continue'. We only get out of the 168 switch block for the row-copying (LOC-moving) cases above. */ 169 170 case DW_CFA_def_cfa: 171 get_uleb128 (operand, program, end); 172 cfi_assert (program < end); 173 get_uleb128 (offset, program, end); 174 def_cfa: 175 fs->cfa_rule = cfa_offset; 176 fs->cfa_val_reg = operand; 177 fs->cfa_val_offset = offset; 178 /* Prime the rest of the Dwarf_Op so dwarf_frame_cfa can use it. */ 179 fs->cfa_data.offset.atom = DW_OP_bregx; 180 fs->cfa_data.offset.offset = 0; 181 continue; 182 183 case DW_CFA_def_cfa_register: 184 get_uleb128 (regno, program, end); 185 require_cfa_offset (fs); 186 fs->cfa_val_reg = regno; 187 continue; 188 189 case DW_CFA_def_cfa_sf: 190 get_uleb128 (operand, program, end); 191 cfi_assert (program < end); 192 get_sleb128 (sf_offset, program, end); 193 offset = sf_offset * cie->data_alignment_factor; 194 goto def_cfa; 195 196 case DW_CFA_def_cfa_offset: 197 get_uleb128 (offset, program, end); 198 def_cfa_offset: 199 require_cfa_offset (fs); 200 fs->cfa_val_offset = offset; 201 continue; 202 203 case DW_CFA_def_cfa_offset_sf: 204 get_sleb128 (sf_offset, program, end); 205 offset = sf_offset * cie->data_alignment_factor; 206 goto def_cfa_offset; 207 208 case DW_CFA_def_cfa_expression: 209 /* DW_FORM_block is a ULEB128 length followed by that many bytes. */ 210 get_uleb128 (operand, program, end); 211 cfi_assert (operand <= (Dwarf_Word) (end - program)); 212 fs->cfa_rule = cfa_expr; 213 fs->cfa_data.expr.data = (unsigned char *) program; 214 fs->cfa_data.expr.length = operand; 215 program += operand; 216 continue; 217 218 case DW_CFA_undefined: 219 get_uleb128 (regno, program, end); 220 register_rule (regno, undefined, 0); 221 continue; 222 223 case DW_CFA_same_value: 224 get_uleb128 (regno, program, end); 225 register_rule (regno, same_value, 0); 226 continue; 227 228 case DW_CFA_offset_extended: 229 get_uleb128 (operand, program, end); 230 cfi_assert (program < end); 231 case DW_CFA_offset + 0 ... DW_CFA_offset + CFI_PRIMARY_MAX: 232 get_uleb128 (offset, program, end); 233 offset *= cie->data_alignment_factor; 234 offset_extended: 235 register_rule (operand, offset, offset); 236 continue; 237 238 case DW_CFA_offset_extended_sf: 239 get_uleb128 (operand, program, end); 240 get_sleb128 (sf_offset, program, end); 241 offset_extended_sf: 242 offset = sf_offset * cie->data_alignment_factor; 243 goto offset_extended; 244 245 case DW_CFA_GNU_negative_offset_extended: 246 /* GNU extension obsoleted by DW_CFA_offset_extended_sf. */ 247 get_uleb128 (operand, program, end); 248 cfi_assert (program < end); 249 get_uleb128 (offset, program, end); 250 sf_offset = -offset; 251 goto offset_extended_sf; 252 253 case DW_CFA_val_offset: 254 get_uleb128 (operand, program, end); 255 cfi_assert (program < end); 256 get_uleb128 (offset, program, end); 257 offset *= cie->data_alignment_factor; 258 val_offset: 259 register_rule (operand, val_offset, offset); 260 continue; 261 262 case DW_CFA_val_offset_sf: 263 get_uleb128 (operand, program, end); 264 cfi_assert (program < end); 265 get_sleb128 (sf_offset, program, end); 266 offset = sf_offset * cie->data_alignment_factor; 267 goto val_offset; 268 269 case DW_CFA_register: 270 get_uleb128 (regno, program, end); 271 cfi_assert (program < end); 272 get_uleb128 (operand, program, end); 273 register_rule (regno, register, operand); 274 continue; 275 276 case DW_CFA_expression: 277 /* Expression rule relies on section data, abi_cfi cannot use it. */ 278 assert (! abi_cfi); 279 get_uleb128 (regno, program, end); 280 offset = program - (const uint8_t *) cache->data->d.d_buf; 281 /* DW_FORM_block is a ULEB128 length followed by that many bytes. */ 282 cfi_assert (program < end); 283 get_uleb128 (operand, program, end); 284 cfi_assert (operand <= (Dwarf_Word) (end - program)); 285 program += operand; 286 register_rule (regno, expression, offset); 287 continue; 288 289 case DW_CFA_val_expression: 290 /* Expression rule relies on section data, abi_cfi cannot use it. */ 291 assert (! abi_cfi); 292 get_uleb128 (regno, program, end); 293 /* DW_FORM_block is a ULEB128 length followed by that many bytes. */ 294 offset = program - (const uint8_t *) cache->data->d.d_buf; 295 get_uleb128 (operand, program, end); 296 cfi_assert (operand <= (Dwarf_Word) (end - program)); 297 program += operand; 298 register_rule (regno, val_expression, offset); 299 continue; 300 301 case DW_CFA_restore_extended: 302 get_uleb128 (operand, program, end); 303 case DW_CFA_restore + 0 ... DW_CFA_restore + CFI_PRIMARY_MAX: 304 305 if (unlikely (abi_cfi) && likely (opcode == DW_CFA_restore)) 306 { 307 /* Special case hack to give backend abi_cfi a shorthand. */ 308 cache->default_same_value = true; 309 continue; 310 } 311 312 /* This can't be used in the CIE's own initial instructions. */ 313 cfi_assert (cie->initial_state != NULL); 314 315 /* Restore the CIE's initial rule for this register. */ 316 if (unlikely (! enough_registers (operand, &fs, &result))) 317 goto out; 318 if (cie->initial_state->nregs > operand) 319 fs->regs[operand] = cie->initial_state->regs[operand]; 320 else 321 fs->regs[operand].rule = reg_unspecified; 322 continue; 323 324 case DW_CFA_remember_state: 325 { 326 /* Duplicate the state and chain the copy on. */ 327 Dwarf_Frame *copy = duplicate_frame_state (fs, fs); 328 if (unlikely (copy == NULL)) 329 { 330 result = DWARF_E_NOMEM; 331 goto out; 332 } 333 fs = copy; 334 continue; 335 } 336 337 case DW_CFA_restore_state: 338 { 339 /* Pop the current state off and use the old one instead. */ 340 Dwarf_Frame *prev = fs->prev; 341 cfi_assert (prev != NULL); 342 free (fs); 343 fs = prev; 344 continue; 345 } 346 347 case DW_CFA_nop: 348 continue; 349 350 case DW_CFA_GNU_window_save: 351 /* This is magic shorthand used only by SPARC. It's equivalent 352 to a bunch of DW_CFA_register and DW_CFA_offset operations. */ 353 if (unlikely (! enough_registers (31, &fs, &result))) 354 goto out; 355 for (regno = 8; regno < 16; ++regno) 356 { 357 /* Find each %oN in %iN. */ 358 fs->regs[regno].rule = reg_register; 359 fs->regs[regno].value = regno + 16; 360 } 361 unsigned int address_size = (cache->e_ident[EI_CLASS] == ELFCLASS32 362 ? 4 : 8); 363 for (; regno < 32; ++regno) 364 { 365 /* Find %l0..%l7 and %i0..%i7 in a block at the CFA. */ 366 fs->regs[regno].rule = reg_offset; 367 fs->regs[regno].value = (regno - 16) * address_size; 368 } 369 continue; 370 371 case DW_CFA_GNU_args_size: 372 /* XXX is this useful for anything? */ 373 get_uleb128 (operand, program, end); 374 continue; 375 376 default: 377 cfi_assert (false); 378 continue; 379 } 380 381 /* We get here only for the cases that have just moved LOC. */ 382 cfi_assert (cie->initial_state != NULL); 383 if (find_pc >= loc) 384 /* This advance has not yet reached FIND_PC. */ 385 fs->start = loc; 386 else 387 { 388 /* We have just advanced past the address we're looking for. 389 The state currently described is what we want to see. */ 390 fs->end = loc; 391 break; 392 } 393 } 394 395 /* "The end of the instruction stream can be thought of as a 396 DW_CFA_set_loc (initial_location + address_range) instruction." 397 (DWARF 3.0 Section 6.4.3) 398 399 When we fall off the end of the program without an advance_loc/set_loc 400 that put us past FIND_PC, the final state left by the FDE program 401 applies to this address (the caller ensured it was inside the FDE). 402 This address (FDE->end) is already in FS->end as set by the caller. */ 403 404#undef register_rule 405#undef cfi_assert 406 407 out: 408 409 /* Pop any remembered states left on the stack. */ 410 while (fs->prev != NULL) 411 { 412 Dwarf_Frame *prev = fs->prev; 413 fs->prev = prev->prev; 414 free (prev); 415 } 416 417 if (likely (result == DWARF_E_NOERROR)) 418 *state = fs; 419 else 420 free (fs); 421 422 return result; 423} 424 425static int 426cie_cache_initial_state (Dwarf_CFI *cache, struct dwarf_cie *cie) 427{ 428 int result = DWARF_E_NOERROR; 429 430 if (likely (cie->initial_state != NULL)) 431 return result; 432 433 /* This CIE has not been used before. Play out its initial 434 instructions and cache the initial state that results. 435 First we'll let the backend fill in the default initial 436 state for this machine's ABI. */ 437 438 Dwarf_CIE abi_info = { DW_CIE_ID_64, NULL, NULL, 1, 1, -1, "", NULL, 0, 0 }; 439 440 /* Make sure we have a backend handle cached. */ 441 if (unlikely (cache->ebl == NULL)) 442 { 443 cache->ebl = ebl_openbackend (cache->data->s->elf); 444 if (unlikely (cache->ebl == NULL)) 445 cache->ebl = (void *) -1l; 446 } 447 448 /* Fetch the ABI's default CFI program. */ 449 if (likely (cache->ebl != (void *) -1l) 450 && unlikely (ebl_abi_cfi (cache->ebl, &abi_info) < 0)) 451 return DWARF_E_UNKNOWN_ERROR; 452 453 Dwarf_Frame *cie_fs = calloc (1, sizeof (Dwarf_Frame)); 454 if (unlikely (cie_fs == NULL)) 455 return DWARF_E_NOMEM; 456 457 /* If the default state of any register is not "undefined" 458 (i.e. call-clobbered), then the backend supplies instructions 459 for the standard initial state. */ 460 if (abi_info.initial_instructions_end > abi_info.initial_instructions) 461 { 462 /* Dummy CIE for backend's instructions. */ 463 struct dwarf_cie abi_cie = 464 { 465 .code_alignment_factor = abi_info.code_alignment_factor, 466 .data_alignment_factor = abi_info.data_alignment_factor, 467 }; 468 result = execute_cfi (cache, &abi_cie, &cie_fs, 469 abi_info.initial_instructions, 470 abi_info.initial_instructions_end, true, 471 0, (Dwarf_Addr) -1l); 472 } 473 474 /* Now run the CIE's initial instructions. */ 475 if (cie->initial_instructions_end > cie->initial_instructions 476 && likely (result == DWARF_E_NOERROR)) 477 result = execute_cfi (cache, cie, &cie_fs, 478 cie->initial_instructions, 479 cie->initial_instructions_end, false, 480 0, (Dwarf_Addr) -1l); 481 482 if (likely (result == DWARF_E_NOERROR)) 483 { 484 /* Now we have the initial state of things that all 485 FDEs using this CIE will start from. */ 486 cie_fs->cache = cache; 487 cie->initial_state = cie_fs; 488 } 489 490 return result; 491} 492 493int 494internal_function 495__libdw_frame_at_address (Dwarf_CFI *cache, struct dwarf_fde *fde, 496 Dwarf_Addr address, Dwarf_Frame **frame) 497{ 498 int result = cie_cache_initial_state (cache, fde->cie); 499 if (likely (result == DWARF_E_NOERROR)) 500 { 501 Dwarf_Frame *fs = duplicate_frame_state (fde->cie->initial_state, NULL); 502 if (unlikely (fs == NULL)) 503 return DWARF_E_NOMEM; 504 505 fs->fde = fde; 506 fs->start = fde->start; 507 fs->end = fde->end; 508 509 result = execute_cfi (cache, fde->cie, &fs, 510 fde->instructions, fde->instructions_end, false, 511 fde->start, address); 512 if (likely (result == DWARF_E_NOERROR)) 513 *frame = fs; 514 } 515 return result; 516} 517