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         case DW_CFA_offset + 0 ... DW_CFA_offset + CFI_PRIMARY_MAX:
 233           get_uleb128 (offset, program, end);
 234           offset *= cie->data_alignment_factor;
 235         offset_extended:
 236           register_rule (operand, offset, offset);
 237           continue;
 238
 239         case DW_CFA_offset_extended_sf:
 240           get_uleb128 (operand, program, end);
 241           get_sleb128 (sf_offset, program, end);
 242         offset_extended_sf:
 243           offset = sf_offset * cie->data_alignment_factor;
 244           goto offset_extended;
 245
 246         case DW_CFA_GNU_negative_offset_extended:
 247           /* GNU extension obsoleted by DW_CFA_offset_extended_sf.  */
 248           get_uleb128 (operand, program, end);
 249           cfi_assert (program < end);
 250           get_uleb128 (offset, program, end);
 251           sf_offset = -offset;
 252           goto offset_extended_sf;
 253
 254         case DW_CFA_val_offset:
 255           get_uleb128 (operand, program, end);
 256           cfi_assert (program < end);
 257           get_uleb128 (offset, program, end);
 258           offset *= cie->data_alignment_factor;
 259         val_offset:
 260           register_rule (operand, val_offset, offset);
 261           continue;
 262
 263         case DW_CFA_val_offset_sf:
 264           get_uleb128 (operand, program, end);
 265           cfi_assert (program < end);
 266           get_sleb128 (sf_offset, program, end);
 267           offset = sf_offset * cie->data_alignment_factor;
 268           goto val_offset;
 269
 270         case DW_CFA_register:
 271           get_uleb128 (regno, program, end);
 272           cfi_assert (program < end);
 273           get_uleb128 (operand, program, end);
 274           register_rule (regno, register, operand);
 275           continue;
 276
 277         case DW_CFA_expression:
 278           /* Expression rule relies on section data, abi_cfi cannot use it.  */
 279           assert (! abi_cfi);
 280           get_uleb128 (regno, program, end);
 281           offset = program - (const uint8_t *) cache->data->d.d_buf;
 282           /* DW_FORM_block is a ULEB128 length followed by that many bytes.  */
 283           cfi_assert (program < end);
 284           get_uleb128 (operand, program, end);
 285           cfi_assert (operand <= (Dwarf_Word) (end - program));
 286           program += operand;
 287           register_rule (regno, expression, offset);
 288           continue;
 289
 290         case DW_CFA_val_expression:
 291           /* Expression rule relies on section data, abi_cfi cannot use it.  */
 292           assert (! abi_cfi);
 293           get_uleb128 (regno, program, end);
 294           /* DW_FORM_block is a ULEB128 length followed by that many bytes.  */
 295           offset = program - (const uint8_t *) cache->data->d.d_buf;
 296           get_uleb128 (operand, program, end);
 297           cfi_assert (operand <= (Dwarf_Word) (end - program));
 298           program += operand;
 299           register_rule (regno, val_expression, offset);
 300           continue;
 301
 302         case DW_CFA_restore_extended:
 303           get_uleb128 (operand, program, end);
 304           FALLTHROUGH;
 305         case DW_CFA_restore + 0 ... DW_CFA_restore + CFI_PRIMARY_MAX:
 306
 307           if (unlikely (abi_cfi) && likely (opcode == DW_CFA_restore))
 308             {
 309               /* Special case hack to give backend abi_cfi a shorthand.  */
 310               cache->default_same_value = true;
 311               continue;
 312             }
 313
 314           /* This can't be used in the CIE's own initial instructions.  */
 315           cfi_assert (cie->initial_state != NULL);
 316
 317           /* Restore the CIE's initial rule for this register.  */
 318           if (unlikely (! enough_registers (operand, &fs, &result)))
 319             goto out;
 320           if (cie->initial_state->nregs > operand)
 321             fs->regs[operand] = cie->initial_state->regs[operand];
 322           else
 323             fs->regs[operand].rule = reg_unspecified;
 324           continue;
 325
 326         case DW_CFA_remember_state:
 327           {
 328             /* Duplicate the state and chain the copy on.  */
 329             Dwarf_Frame *copy = duplicate_frame_state (fs, fs);
 330             if (unlikely (copy == NULL))
 331               {
 332                 result = DWARF_E_NOMEM;
 333                 goto out;
 334               }
 335             fs = copy;
 336             continue;
 337           }
 338
 339         case DW_CFA_restore_state:
 340           {
 341             /* Pop the current state off and use the old one instead.  */
 342             Dwarf_Frame *prev = fs->prev;
 343             cfi_assert (prev != NULL);
 344             free (fs);
 345             fs = prev;
 346             continue;
 347           }
 348
 349         case DW_CFA_nop:
 350           continue;
 351
 352         case DW_CFA_GNU_window_save:
 353           /* This is magic shorthand used only by SPARC.  It's equivalent
 354              to a bunch of DW_CFA_register and DW_CFA_offset operations.  */
 355           if (unlikely (! enough_registers (31, &fs, &result)))
 356             goto out;
 357           for (regno = 8; regno < 16; ++regno)
 358             {
 359               /* Find each %oN in %iN.  */
 360               fs->regs[regno].rule = reg_register;
 361               fs->regs[regno].value = regno + 16;
 362             }
 363           unsigned int address_size = (cache->e_ident[EI_CLASS] == ELFCLASS32
 364                                        ? 4 : 8);
 365           for (; regno < 32; ++regno)
 366             {
 367               /* Find %l0..%l7 and %i0..%i7 in a block at the CFA.  */
 368               fs->regs[regno].rule = reg_offset;
 369               fs->regs[regno].value = (regno - 16) * address_size;
 370             }
 371           continue;
 372
 373         case DW_CFA_GNU_args_size:
 374           /* XXX is this useful for anything? */
 375           get_uleb128 (operand, program, end);
 376           continue;
 377
 378         default:
 379           cfi_assert (false);
 380           continue;
 381         }
 382
 383       /* We get here only for the cases that have just moved LOC.  */
 384       cfi_assert (cie->initial_state != NULL);
 385       if (find_pc >= loc)
 386         /* This advance has not yet reached FIND_PC.  */
 387         fs->start = loc;
 388       else
 389         {
 390           /* We have just advanced past the address we're looking for.
 391              The state currently described is what we want to see.  */
 392           fs->end = loc;
 393           break;
 394         }
 395     }
 396
 397   /* "The end of the instruction stream can be thought of as a
 398      DW_CFA_set_loc (initial_location + address_range) instruction."
 399      (DWARF 3.0 Section 6.4.3)
 400
 401      When we fall off the end of the program without an advance_loc/set_loc
 402      that put us past FIND_PC, the final state left by the FDE program
 403      applies to this address (the caller ensured it was inside the FDE).
 404      This address (FDE->end) is already in FS->end as set by the caller.  */
 405
 406 #undef register_rule
 407 #undef cfi_assert
 408
 409  out:
 410
 411   /* Pop any remembered states left on the stack.  */
 412   while (fs->prev != NULL)
 413     {
 414       Dwarf_Frame *prev = fs->prev;
 415       fs->prev = prev->prev;
 416       free (prev);
 417     }
 418
 419   if (likely (result == DWARF_E_NOERROR))
 420     *state = fs;
 421   else
 422     free (fs);
 423
 424   return result;
 425 }
 426
 427 static int
 428 cie_cache_initial_state (Dwarf_CFI *cache, struct dwarf_cie *cie)
 429 {
 430   int result = DWARF_E_NOERROR;
 431
 432   if (likely (cie->initial_state != NULL))
 433     return result;
 434
 435   /* This CIE has not been used before.  Play out its initial
 436      instructions and cache the initial state that results.
 437      First we'll let the backend fill in the default initial
 438      state for this machine's ABI.  */
 439
 440   Dwarf_CIE abi_info = { DW_CIE_ID_64, NULL, NULL, 1, 1, -1, "", NULL, 0, 0 };
 441
 442   /* Make sure we have a backend handle cached.  */
 443   if (unlikely (cache->ebl == NULL))
 444     {
 445       cache->ebl = ebl_openbackend (cache->data->s->elf);
 446       if (unlikely (cache->ebl == NULL))
 447         cache->ebl = (void *) -1l;
 448     }
 449
 450   /* Fetch the ABI's default CFI program.  */
 451   if (likely (cache->ebl != (void *) -1l)
 452       && unlikely (ebl_abi_cfi (cache->ebl, &abi_info) < 0))
 453     return DWARF_E_UNKNOWN_ERROR;
 454
 455   Dwarf_Frame *cie_fs = calloc (1, sizeof (Dwarf_Frame));
 456   if (unlikely (cie_fs == NULL))
 457     return DWARF_E_NOMEM;
 458
 459   /* If the default state of any register is not "undefined"
 460      (i.e. call-clobbered), then the backend supplies instructions
 461      for the standard initial state.  */
 462   if (abi_info.initial_instructions_end > abi_info.initial_instructions)
 463     {
 464       /* Dummy CIE for backend's instructions.  */
 465       struct dwarf_cie abi_cie =
 466         {
 467           .code_alignment_factor = abi_info.code_alignment_factor,
 468           .data_alignment_factor = abi_info.data_alignment_factor,
 469         };
 470       result = execute_cfi (cache, &abi_cie, &cie_fs,
 471                             abi_info.initial_instructions,
 472                             abi_info.initial_instructions_end, true,
 473                             0, (Dwarf_Addr) -1l);
 474     }
 475
 476   /* Now run the CIE's initial instructions.  */
 477   if (cie->initial_instructions_end > cie->initial_instructions
 478       && likely (result == DWARF_E_NOERROR))
 479     result = execute_cfi (cache, cie, &cie_fs,
 480                           cie->initial_instructions,
 481                           cie->initial_instructions_end, false,
 482                           0, (Dwarf_Addr) -1l);
 483
 484   if (likely (result == DWARF_E_NOERROR))
 485     {
 486       /* Now we have the initial state of things that all
 487          FDEs using this CIE will start from.  */
 488       cie_fs->cache = cache;
 489       cie->initial_state = cie_fs;
 490     }
 491
 492   return result;
 493 }
 494
 495 int
 496 internal_function
 497 __libdw_frame_at_address (Dwarf_CFI *cache, struct dwarf_fde *fde,
 498                           Dwarf_Addr address, Dwarf_Frame **frame)
 499 {
 500   int result = cie_cache_initial_state (cache, fde->cie);
 501   if (likely (result == DWARF_E_NOERROR))
 502     {
 503       Dwarf_Frame *fs = duplicate_frame_state (fde->cie->initial_state, NULL);
 504       if (unlikely (fs == NULL))
 505         return DWARF_E_NOMEM;
 506
 507       fs->fde = fde;
 508       fs->start = fde->start;
 509       fs->end = fde->end;
 510
 511       result = execute_cfi (cache, fde->cie, &fs,
 512                             fde->instructions, fde->instructions_end, false,
 513                             fde->start, address);
 514       if (likely (result == DWARF_E_NOERROR))
 515         *frame = fs;
 516     }
 517   return result;
 518 }