libdw/cfi.c

   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
  45 static Dwarf_Frame *
  46 duplicate_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
  59 static inline bool
  60 enough_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
  92 static inline void
  93 require_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.  */
 101 static int
 102 execute_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           FALLTHROUGH;
 142         case DW_CFA_advance_loc + 0 ... DW_CFA_advance_loc + CFI_PRIMARY_MAX:
 143         advance_loc:
 144           loc += operand * cie->code_alignment_factor;
 145           break;
 146
 147         case DW_CFA_advance_loc2:
 148           cfi_assert (program + 2 <= end);
 149           operand = read_2ubyte_unaligned_inc (cache, program);
 150           goto advance_loc;
 151         case DW_CFA_advance_loc4:
 152           cfi_assert (program + 4 <= end);
 153           operand = read_4ubyte_unaligned_inc (cache, program);
 154           goto advance_loc;
 155         case DW_CFA_MIPS_advance_loc8:
 156           cfi_assert (program + 8 <= end);
 157           operand = read_8ubyte_unaligned_inc (cache, program);
 158           goto advance_loc;
 159
 160         case DW_CFA_set_loc:
 161           if (likely (!read_encoded_value (cache, cie->fde_encoding,
 162                                            &program, &loc)))
 163             break;
 164           result = INTUSE(dwarf_errno) ();
 165           goto out;
 166
 167           /* Now all following cases affect this row, but do not touch LOC.
 168              These cases end with 'continue'.  We only get out of the
 169              switch block for the row-copying (LOC-moving) cases above.  */
 170
 171         case DW_CFA_def_cfa:
 172           get_uleb128 (operand, program, end);
 173           cfi_assert (program < end);
 174           get_uleb128 (offset, program, end);
 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, end);
 186           require_cfa_offset (fs);
 187           fs->cfa_val_reg = regno;
 188           continue;
 189
 190         case DW_CFA_def_cfa_sf:
 191           get_uleb128 (operand, program, end);
 192           cfi_assert (program < end);
 193           get_sleb128 (sf_offset, program, end);
 194           offset = sf_offset * cie->data_alignment_factor;
 195           goto def_cfa;
 196
 197         case DW_CFA_def_cfa_offset:
 198           get_uleb128 (offset, program, end);
 199         def_cfa_offset:
 200           require_cfa_offset (fs);
 201           fs->cfa_val_offset = offset;
 202           continue;
 203
 204         case DW_CFA_def_cfa_offset_sf:
 205           get_sleb128 (sf_offset, program, end);
 206           offset = sf_offset * cie->data_alignment_factor;
 207           goto def_cfa_offset;
 208
 209         case DW_CFA_def_cfa_expression:
 210           /* DW_FORM_block is a ULEB128 length followed by that many bytes.  */
 211           get_uleb128 (operand, program, end);
 212           cfi_assert (operand <= (Dwarf_Word) (end - program));
 213           fs->cfa_rule = cfa_expr;
 214           fs->cfa_data.expr.data = (unsigned char *) program;
 215           fs->cfa_data.expr.length = operand;
 216           program += operand;
 217           continue;
 218
 219         case DW_CFA_undefined:
 220           get_uleb128 (regno, program, end);
 221           register_rule (regno, undefined, 0);
 222           continue;
 223
 224         case DW_CFA_same_value:
 225           get_uleb128 (regno, program, end);
 226           register_rule (regno, same_value, 0);
 227           continue;
 228
 229         case DW_CFA_offset_extended:
 230           get_uleb128 (operand, program, end);
 231           cfi_assert (program < end);
 232           FALLTHROUGH;
 233         case DW_CFA_offset + 0 ... DW_CFA_offset + CFI_PRIMARY_MAX:
 234           get_uleb128 (offset, program, end);
 235           offset *= cie->data_alignment_factor;
 236         offset_extended:
 237           register_rule (operand, offset, offset);
 238           continue;
 239
 240         case DW_CFA_offset_extended_sf:
 241           get_uleb128 (operand, program, end);
 242           get_sleb128 (sf_offset, program, end);
 243         offset_extended_sf:
 244           offset = sf_offset * cie->data_alignment_factor;
 245           goto offset_extended;
 246
 247         case DW_CFA_GNU_negative_offset_extended:
 248           /* GNU extension obsoleted by DW_CFA_offset_extended_sf.  */
 249           get_uleb128 (operand, program, end);
 250           cfi_assert (program < end);
 251           get_uleb128 (offset, program, end);
 252           sf_offset = -offset;
 253           goto offset_extended_sf;
 254
 255         case DW_CFA_val_offset:
 256           get_uleb128 (operand, program, end);
 257           cfi_assert (program < end);
 258           get_uleb128 (offset, program, end);
 259           offset *= cie->data_alignment_factor;
 260         val_offset:
 261           register_rule (operand, val_offset, offset);
 262           continue;
 263
 264         case DW_CFA_val_offset_sf:
 265           get_uleb128 (operand, program, end);
 266           cfi_assert (program < end);
 267           get_sleb128 (sf_offset, program, end);
 268           offset = sf_offset * cie->data_alignment_factor;
 269           goto val_offset;
 270
 271         case DW_CFA_register:
 272           get_uleb128 (regno, program, end);
 273           cfi_assert (program < end);
 274           get_uleb128 (operand, program, end);
 275           register_rule (regno, register, operand);
 276           continue;
 277
 278         case DW_CFA_expression:
 279           /* Expression rule relies on section data, abi_cfi cannot use it.  */
 280           assert (! abi_cfi);
 281           get_uleb128 (regno, program, end);
 282           offset = program - (const uint8_t *) cache->data->d.d_buf;
 283           /* DW_FORM_block is a ULEB128 length followed by that many bytes.  */
 284           cfi_assert (program < end);
 285           get_uleb128 (operand, program, end);
 286           cfi_assert (operand <= (Dwarf_Word) (end - program));
 287           program += operand;
 288           register_rule (regno, expression, offset);
 289           continue;
 290
 291         case DW_CFA_val_expression:
 292           /* Expression rule relies on section data, abi_cfi cannot use it.  */
 293           assert (! abi_cfi);
 294           get_uleb128 (regno, program, end);
 295           /* DW_FORM_block is a ULEB128 length followed by that many bytes.  */
 296           offset = program - (const uint8_t *) cache->data->d.d_buf;
 297           get_uleb128 (operand, program, end);
 298           cfi_assert (operand <= (Dwarf_Word) (end - program));
 299           program += operand;
 300           register_rule (regno, val_expression, offset);
 301           continue;
 302
 303         case DW_CFA_restore_extended:
 304           get_uleb128 (operand, program, end);
 305           FALLTHROUGH;
 306         case DW_CFA_restore + 0 ... DW_CFA_restore + CFI_PRIMARY_MAX:
 307
 308           if (unlikely (abi_cfi) && likely (opcode == DW_CFA_restore))
 309             {
 310               /* Special case hack to give backend abi_cfi a shorthand.  */
 311               cache->default_same_value = true;
 312               continue;
 313             }
 314
 315           /* This can't be used in the CIE's own initial instructions.  */
 316           cfi_assert (cie->initial_state != NULL);
 317
 318           /* Restore the CIE's initial rule for this register.  */
 319           if (unlikely (! enough_registers (operand, &fs, &result)))
 320             goto out;
 321           if (cie->initial_state->nregs > operand)
 322             fs->regs[operand] = cie->initial_state->regs[operand];
 323           else
 324             fs->regs[operand].rule = reg_unspecified;
 325           continue;
 326
 327         case DW_CFA_remember_state:
 328           {
 329             /* Duplicate the state and chain the copy on.  */
 330             Dwarf_Frame *copy = duplicate_frame_state (fs, fs);
 331             if (unlikely (copy == NULL))
 332               {
 333                 result = DWARF_E_NOMEM;
 334                 goto out;
 335               }
 336             fs = copy;
 337             continue;
 338           }
 339
 340         case DW_CFA_restore_state:
 341           {
 342             /* Pop the current state off and use the old one instead.  */
 343             Dwarf_Frame *prev = fs->prev;
 344             cfi_assert (prev != NULL);
 345             free (fs);
 346             fs = prev;
 347             continue;
 348           }
 349
 350         case DW_CFA_nop:
 351           continue;
 352
 353         case DW_CFA_GNU_window_save: /* DW_CFA_AARCH64_negate_ra_state */
 354           if (cache->e_machine == EM_AARCH64)
 355             {
 356               /* Toggles the return address state, indicating whether
 357                  the return address is encrypted or not on
 358                  aarch64. XXX not handled yet.  */
 359             }
 360           else
 361             {
 362               /* This is magic shorthand used only by SPARC.  It's
 363                  equivalent to a bunch of DW_CFA_register and
 364                  DW_CFA_offset operations.  */
 365               if (unlikely (! enough_registers (31, &fs, &result)))
 366                 goto out;
 367               for (regno = 8; regno < 16; ++regno)
 368                 {
 369                   /* Find each %oN in %iN.  */
 370                   fs->regs[regno].rule = reg_register;
 371                   fs->regs[regno].value = regno + 16;
 372                 }
 373               unsigned int address_size;
 374               address_size = (cache->e_ident[EI_CLASS] == ELFCLASS32
 375                               ? 4 : 8);
 376               for (; regno < 32; ++regno)
 377                 {
 378                   /* Find %l0..%l7 and %i0..%i7 in a block at the CFA.  */
 379                   fs->regs[regno].rule = reg_offset;
 380                   fs->regs[regno].value = (regno - 16) * address_size;
 381                 }
 382             }
 383           continue;
 384
 385         case DW_CFA_GNU_args_size:
 386           /* XXX is this useful for anything? */
 387           get_uleb128 (operand, program, end);
 388           continue;
 389
 390         default:
 391           cfi_assert (false);
 392           continue;
 393         }
 394
 395       /* We get here only for the cases that have just moved LOC.  */
 396       cfi_assert (cie->initial_state != NULL);
 397       if (find_pc >= loc)
 398         /* This advance has not yet reached FIND_PC.  */
 399         fs->start = loc;
 400       else
 401         {
 402           /* We have just advanced past the address we're looking for.
 403              The state currently described is what we want to see.  */
 404           fs->end = loc;
 405           break;
 406         }
 407     }
 408
 409   /* "The end of the instruction stream can be thought of as a
 410      DW_CFA_set_loc (initial_location + address_range) instruction."
 411      (DWARF 3.0 Section 6.4.3)
 412
 413      When we fall off the end of the program without an advance_loc/set_loc
 414      that put us past FIND_PC, the final state left by the FDE program
 415      applies to this address (the caller ensured it was inside the FDE).
 416      This address (FDE->end) is already in FS->end as set by the caller.  */
 417
 418 #undef register_rule
 419 #undef cfi_assert
 420
 421  out:
 422
 423   /* Pop any remembered states left on the stack.  */
 424   while (fs->prev != NULL)
 425     {
 426       Dwarf_Frame *prev = fs->prev;
 427       fs->prev = prev->prev;
 428       free (prev);
 429     }
 430
 431   if (likely (result == DWARF_E_NOERROR))
 432     *state = fs;
 433   else
 434     free (fs);
 435
 436   return result;
 437 }
 438
 439 static int
 440 cie_cache_initial_state (Dwarf_CFI *cache, struct dwarf_cie *cie)
 441 {
 442   int result = DWARF_E_NOERROR;
 443
 444   if (likely (cie->initial_state != NULL))
 445     return result;
 446
 447   /* This CIE has not been used before.  Play out its initial
 448      instructions and cache the initial state that results.
 449      First we'll let the backend fill in the default initial
 450      state for this machine's ABI.  */
 451
 452   Dwarf_CIE abi_info = { DW_CIE_ID_64, NULL, NULL, 1, 1, -1, "", NULL, 0, 0 };
 453
 454   /* Make sure we have a backend handle cached.  */
 455   if (unlikely (cache->ebl == NULL))
 456     {
 457       cache->ebl = ebl_openbackend (cache->data->s->elf);
 458       if (unlikely (cache->ebl == NULL))
 459         cache->ebl = (void *) -1l;
 460     }
 461
 462   /* Fetch the ABI's default CFI program.  */
 463   if (likely (cache->ebl != (void *) -1l)
 464       && unlikely (ebl_abi_cfi (cache->ebl, &abi_info) < 0))
 465     return DWARF_E_UNKNOWN_ERROR;
 466
 467   Dwarf_Frame *cie_fs = calloc (1, sizeof (Dwarf_Frame));
 468   if (unlikely (cie_fs == NULL))
 469     return DWARF_E_NOMEM;
 470
 471   /* If the default state of any register is not "undefined"
 472      (i.e. call-clobbered), then the backend supplies instructions
 473      for the standard initial state.  */
 474   if (abi_info.initial_instructions_end > abi_info.initial_instructions)
 475     {
 476       /* Dummy CIE for backend's instructions.  */
 477       struct dwarf_cie abi_cie =
 478         {
 479           .code_alignment_factor = abi_info.code_alignment_factor,
 480           .data_alignment_factor = abi_info.data_alignment_factor,
 481         };
 482       result = execute_cfi (cache, &abi_cie, &cie_fs,
 483                             abi_info.initial_instructions,
 484                             abi_info.initial_instructions_end, true,
 485                             0, (Dwarf_Addr) -1l);
 486     }
 487
 488   /* Now run the CIE's initial instructions.  */
 489   if (cie->initial_instructions_end > cie->initial_instructions
 490       && likely (result == DWARF_E_NOERROR))
 491     result = execute_cfi (cache, cie, &cie_fs,
 492                           cie->initial_instructions,
 493                           cie->initial_instructions_end, false,
 494                           0, (Dwarf_Addr) -1l);
 495
 496   if (likely (result == DWARF_E_NOERROR))
 497     {
 498       /* Now we have the initial state of things that all
 499          FDEs using this CIE will start from.  */
 500       cie_fs->cache = cache;
 501       cie->initial_state = cie_fs;
 502     }
 503
 504   return result;
 505 }
 506
 507 int
 508 internal_function
 509 __libdw_frame_at_address (Dwarf_CFI *cache, struct dwarf_fde *fde,
 510                           Dwarf_Addr address, Dwarf_Frame **frame)
 511 {
 512   int result = cie_cache_initial_state (cache, fde->cie);
 513   if (likely (result == DWARF_E_NOERROR))
 514     {
 515       Dwarf_Frame *fs = duplicate_frame_state (fde->cie->initial_state, NULL);
 516       if (unlikely (fs == NULL))
 517         return DWARF_E_NOMEM;
 518
 519       fs->fde = fde;
 520       fs->start = fde->start;
 521       fs->end = fde->end;
 522
 523       result = execute_cfi (cache, fde->cie, &fs,
 524                             fde->instructions, fde->instructions_end, false,
 525                             fde->start, address);
 526       if (likely (result == DWARF_E_NOERROR))
 527         *frame = fs;
 528     }
 529   return result;
 530 }