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         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
 425 static int
 426 cie_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
 493 int
 494 internal_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 }