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