sys/lib/libunwind/DwarfParser.hpp

   1 //===--------------------------- DwarfParser.hpp --------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is dual licensed under the MIT and the University of Illinois Open
   6 // Source Licenses. See LICENSE.TXT for details.
   7 //
   8 //
   9 //  Parses DWARF CFIs (FDEs and CIEs).
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #ifndef __DWARF_PARSER_HPP__
  14 #define __DWARF_PARSER_HPP__
  15
  16 #include <cstdint>
  17 #include <cstdlib>
  18
  19 #include "dwarf2.h"
  20 #include "AddressSpace.hpp"
  21
  22 namespace _Unwind {
  23
  24 /// CFI_Parser does basic parsing of a CFI (Call Frame Information) records.
  25 /// See Dwarf Spec for details:
  26 ///    http://refspecs.linuxbase.org/LSB_3.1.0/LSB-Core-generic/LSB-Core-generic/ehframechpt.html
  27 ///
  28 template <typename A, typename R> class CFI_Parser {
  29 public:
  30   typedef typename A::pint_t pint_t;
  31
  32   /// Information encoded in a CIE (Common Information Entry)
  33   struct CIE_Info {
  34     pint_t cieStart;
  35     pint_t cieLength;
  36     pint_t cieInstructions;
  37     pint_t personality;
  38     uint32_t codeAlignFactor;
  39     int dataAlignFactor;
  40     uint8_t pointerEncoding;
  41     uint8_t lsdaEncoding;
  42     uint8_t personalityEncoding;
  43     uint8_t personalityOffsetInCIE;
  44     bool isSignalFrame;
  45     bool fdesHaveAugmentationData;
  46     uint8_t returnAddressRegister;
  47   };
  48
  49   /// Information about an FDE (Frame Description Entry)
  50   struct FDE_Info {
  51     pint_t fdeStart;
  52     pint_t fdeLength;
  53     pint_t fdeInstructions;
  54     pint_t pcStart;
  55     pint_t pcEnd;
  56     pint_t lsda;
  57   };
  58
  59   /// Information about a frame layout and registers saved determined
  60   /// by "running" the DWARF FDE "instructions"
  61   enum {
  62     kMaxRegisterNumber = R::LAST_REGISTER + 1
  63   };
  64   enum RegisterSavedWhere {
  65     kRegisterUnused,
  66     kRegisterInCFA,
  67     kRegisterOffsetFromCFA,
  68     kRegisterInRegister,
  69     kRegisterAtExpression,
  70     kRegisterIsExpression,
  71   };
  72   struct RegisterLocation {
  73     RegisterSavedWhere location;
  74     int64_t value;
  75   };
  76   struct PrologInfo {
  77     uint32_t cfaRegister;
  78     int32_t cfaRegisterOffset; // CFA = (cfaRegister)+cfaRegisterOffset
  79     int64_t cfaExpression;     // CFA = expression
  80     uint32_t spExtraArgSize;
  81     uint32_t codeOffsetAtStackDecrement;
  82     RegisterLocation savedRegisters[kMaxRegisterNumber];
  83   };
  84
  85   struct PrologInfoStackEntry {
  86     PrologInfoStackEntry(PrologInfoStackEntry *n, const PrologInfo &i)
  87         : next(n), info(i) {}
  88     PrologInfoStackEntry *next;
  89     PrologInfo info;
  90   };
  91
  92   static void findPCRange(A &, pint_t, pint_t &, pint_t &);
  93
  94   static bool decodeFDE(A &, pint_t, FDE_Info *, CIE_Info *,
  95                         unw_proc_info_t *ctx);
  96   static bool parseFDEInstructions(A &, const FDE_Info &, const CIE_Info &,
  97                                    pint_t, PrologInfo *, unw_proc_info_t *ctx);
  98
  99   static bool parseCIE(A &, pint_t, CIE_Info *);
 100
 101 private:
 102   static bool parseInstructions(A &, pint_t, pint_t, const CIE_Info &, pint_t,
 103                                 PrologInfoStackEntry *&, PrologInfo *,
 104                                 unw_proc_info_t *ctx);
 105 };
 106
 107 ///
 108 /// Parse a FDE and return the last PC it covers.
 109 ///
 110 template <typename A, typename R>
 111 void CFI_Parser<A, R>::findPCRange(A &addressSpace, pint_t fde, pint_t &pcStart,
 112                                    pint_t &pcEnd) {
 113   pcStart = 0;
 114   pcEnd = 0;
 115   pint_t p = fde;
 116   uint64_t cfiLength = addressSpace.get32(p);
 117   p += 4;
 118   if (cfiLength == 0xffffffff) {
 119     // 0xffffffff means length is really the next 8 Bytes.
 120     cfiLength = addressSpace.get64(p);
 121     p += 8;
 122   }
 123   if (cfiLength == 0)
 124     return;
 125   uint32_t ciePointer = addressSpace.get32(p);
 126   if (ciePointer == 0)
 127     return;
 128   pint_t nextCFI = p + cfiLength;
 129   pint_t cieStart = p - ciePointer;
 130   typename CFI_Parser<A, R>::CIE_Info cieInfo;
 131   if (!parseCIE(addressSpace, cieStart, &cieInfo))
 132     return;
 133   p += 4;
 134   // Parse pc begin and range.
 135   pcStart = addressSpace.getEncodedP(p, nextCFI, cieInfo.pointerEncoding, NULL);
 136   pcEnd = pcStart + addressSpace.getEncodedP(
 137                         p, nextCFI, cieInfo.pointerEncoding & 0x0F, NULL);
 138 }
 139
 140 ///
 141 /// Parse a FDE into a CIE_Info and an FDE_Info
 142 ///
 143 template <typename A, typename R>
 144 bool CFI_Parser<A, R>::decodeFDE(A &addressSpace, pint_t fdeStart,
 145                                  FDE_Info *fdeInfo, CIE_Info *cieInfo,
 146                                  unw_proc_info_t *ctx) {
 147   pint_t p = fdeStart;
 148   uint64_t cfiLength = addressSpace.get32(p);
 149   p += 4;
 150   if (cfiLength == 0xffffffff) {
 151     // 0xffffffff means length is really the next 8 Bytes.
 152     cfiLength = addressSpace.get64(p);
 153     p += 8;
 154   }
 155   if (cfiLength == 0)
 156     return false;
 157   uint32_t ciePointer = addressSpace.get32(p);
 158   if (ciePointer == 0)
 159     return false;
 160   pint_t nextCFI = p + cfiLength;
 161   pint_t cieStart = p - ciePointer;
 162   if (!parseCIE(addressSpace, cieStart, cieInfo))
 163     return false;
 164   p += 4;
 165   // Parse pc begin and range.
 166   pint_t pcStart =
 167       addressSpace.getEncodedP(p, nextCFI, cieInfo->pointerEncoding, ctx);
 168   pint_t pcRange = addressSpace.getEncodedP(
 169       p, nextCFI, cieInfo->pointerEncoding & 0x0F, ctx);
 170   // Parse rest of info.
 171   fdeInfo->lsda = 0;
 172   // Check for augmentation length
 173   if (cieInfo->fdesHaveAugmentationData) {
 174     uintptr_t augLen = addressSpace.getULEB128(p, nextCFI);
 175     pint_t endOfAug = p + augLen;
 176     if (cieInfo->lsdaEncoding != DW_EH_PE_omit) {
 177       // Peek at value (without indirection).  Zero means no LSDA.
 178       pint_t lsdaStart = p;
 179       if (addressSpace.getEncodedP(p, nextCFI, cieInfo->lsdaEncoding & 0x0F,
 180                                    ctx) != 0) {
 181         // Reset pointer and re-parse LSDA address.
 182         p = lsdaStart;
 183         fdeInfo->lsda =
 184             addressSpace.getEncodedP(p, nextCFI, cieInfo->lsdaEncoding, ctx);
 185       }
 186     }
 187     p = endOfAug;
 188   }
 189   fdeInfo->fdeStart = fdeStart;
 190   fdeInfo->fdeLength = nextCFI - fdeStart;
 191   fdeInfo->fdeInstructions = p;
 192   fdeInfo->pcStart = pcStart;
 193   fdeInfo->pcEnd = pcStart + pcRange;
 194   return true;
 195 }
 196
 197 /// Extract info from a CIE
 198 template <typename A, typename R>
 199 bool CFI_Parser<A, R>::parseCIE(A &addressSpace, pint_t cie,
 200                                 CIE_Info *cieInfo) {
 201   cieInfo->pointerEncoding = 0;
 202   cieInfo->lsdaEncoding = DW_EH_PE_omit;
 203   cieInfo->personalityEncoding = 0;
 204   cieInfo->personalityOffsetInCIE = 0;
 205   cieInfo->personality = 0;
 206   cieInfo->codeAlignFactor = 0;
 207   cieInfo->dataAlignFactor = 0;
 208   cieInfo->isSignalFrame = false;
 209   cieInfo->fdesHaveAugmentationData = false;
 210   cieInfo->cieStart = cie;
 211   pint_t p = cie;
 212   uint64_t cieLength = addressSpace.get32(p);
 213   p += 4;
 214   pint_t cieContentEnd = p + cieLength;
 215   if (cieLength == 0xffffffff) {
 216     // 0xffffffff means length is really the next 8 Bytes.
 217     cieLength = addressSpace.get64(p);
 218     p += 8;
 219     cieContentEnd = p + cieLength;
 220   }
 221   if (cieLength == 0)
 222     return true;
 223   // CIE ID is always 0
 224   if (addressSpace.get32(p) != 0)
 225     return false;
 226   p += 4;
 227   // Version is always 1 or 3
 228   uint8_t version = addressSpace.get8(p);
 229   if (version != 1 && version != 3)
 230     return false;
 231   ++p;
 232   // Save start of augmentation string and find end.
 233   pint_t strStart = p;
 234   while (addressSpace.get8(p) != 0)
 235     ++p;
 236   ++p;
 237   // Parse code aligment factor
 238   cieInfo->codeAlignFactor = addressSpace.getULEB128(p, cieContentEnd);
 239   // Parse data alignment factor
 240   cieInfo->dataAlignFactor = addressSpace.getSLEB128(p, cieContentEnd);
 241   // Parse return address register
 242   cieInfo->returnAddressRegister = (uint8_t)addressSpace.getULEB128(p, cieContentEnd);
 243   // Parse augmentation data based on augmentation string.
 244   if (addressSpace.get8(strStart) == 'z') {
 245     // parse augmentation data length
 246     addressSpace.getULEB128(p, cieContentEnd);
 247     for (pint_t s = strStart; addressSpace.get8(s) != '\0'; ++s) {
 248       switch (addressSpace.get8(s)) {
 249       case 'z':
 250         cieInfo->fdesHaveAugmentationData = true;
 251         break;
 252       case 'P':
 253         cieInfo->personalityEncoding = addressSpace.get8(p);
 254         ++p;
 255         cieInfo->personalityOffsetInCIE = p - cie;
 256         cieInfo->personality = addressSpace.getEncodedP(
 257             p, cieContentEnd, cieInfo->personalityEncoding, NULL);
 258         break;
 259       case 'L':
 260         cieInfo->lsdaEncoding = addressSpace.get8(p);
 261         ++p;
 262         break;
 263       case 'R':
 264         cieInfo->pointerEncoding = addressSpace.get8(p);
 265         ++p;
 266         break;
 267       case 'S':
 268         cieInfo->isSignalFrame = true;
 269         break;
 270       default:
 271         // ignore unknown letters
 272         break;
 273       }
 274     }
 275   }
 276   cieInfo->cieLength = cieContentEnd - cieInfo->cieStart;
 277   cieInfo->cieInstructions = p;
 278   return true;
 279 }
 280
 281 /// "Run" the dwarf instructions and create the abstact PrologInfo for an FDE.
 282 template <typename A, typename R>
 283 bool CFI_Parser<A, R>::parseFDEInstructions(A &addressSpace,
 284                                             const FDE_Info &fdeInfo,
 285                                             const CIE_Info &cieInfo,
 286                                             pint_t upToPC, PrologInfo *results,
 287                                             unw_proc_info_t *ctx) {
 288   // Clear results.
 289   memset(results, 0, sizeof(*results));
 290   PrologInfoStackEntry *rememberStack = NULL;
 291
 292   // First parse the CIE then FDE instructions.
 293   if (!parseInstructions(addressSpace, cieInfo.cieInstructions,
 294                          cieInfo.cieStart + cieInfo.cieLength, cieInfo,
 295                          (pint_t)(-1), rememberStack, results, ctx))
 296     return false;
 297   return parseInstructions(addressSpace, fdeInfo.fdeInstructions,
 298                            fdeInfo.fdeStart + fdeInfo.fdeLength, cieInfo,
 299                            upToPC - fdeInfo.pcStart, rememberStack, results,
 300                            ctx);
 301 }
 302
 303 /// "Run" the DWARF instructions.
 304 template <typename A, typename R>
 305 bool
 306 CFI_Parser<A, R>::parseInstructions(A &addressSpace, pint_t instructions,
 307                                     pint_t instructionsEnd,
 308                                     const CIE_Info &cieInfo, pint_t pcoffset,
 309                                     PrologInfoStackEntry *&rememberStack,
 310                                     PrologInfo *results, unw_proc_info_t *ctx) {
 311   pint_t p = instructions;
 312   uint32_t codeOffset = 0;
 313   PrologInfo initialState = *results;
 314
 315   // See Dwarf Spec, section 6.4.2 for details on unwind opcodes.
 316   while (p < instructionsEnd && codeOffset < pcoffset) {
 317     uint64_t reg;
 318     uint64_t reg2;
 319     int64_t offset;
 320     uint64_t length;
 321     uint8_t opcode = addressSpace.get8(p);
 322     uint8_t operand;
 323     PrologInfoStackEntry *entry;
 324     ++p;
 325     switch (opcode) {
 326     case DW_CFA_nop:
 327       break;
 328     case DW_CFA_set_loc:
 329       codeOffset = addressSpace.getEncodedP(p, instructionsEnd,
 330                                             cieInfo.pointerEncoding, ctx);
 331       break;
 332     case DW_CFA_advance_loc1:
 333       codeOffset += (addressSpace.get8(p) * cieInfo.codeAlignFactor);
 334       p += 1;
 335       break;
 336     case DW_CFA_advance_loc2:
 337       codeOffset += (addressSpace.get16(p) * cieInfo.codeAlignFactor);
 338       p += 2;
 339       break;
 340     case DW_CFA_advance_loc4:
 341       codeOffset += (addressSpace.get32(p) * cieInfo.codeAlignFactor);
 342       p += 4;
 343       break;
 344     case DW_CFA_offset_extended:
 345       reg = R::dwarf2regno(addressSpace.getULEB128(p, instructionsEnd));
 346       offset =
 347           addressSpace.getULEB128(p, instructionsEnd) * cieInfo.dataAlignFactor;
 348       if (reg > kMaxRegisterNumber)
 349         return false;
 350       results->savedRegisters[reg].location = kRegisterInCFA;
 351       results->savedRegisters[reg].value = offset;
 352       break;
 353     case DW_CFA_restore_extended:
 354       reg = R::dwarf2regno(addressSpace.getULEB128(p, instructionsEnd));
 355       if (reg > kMaxRegisterNumber)
 356         return false;
 357       results->savedRegisters[reg] = initialState.savedRegisters[reg];
 358       break;
 359     case DW_CFA_undefined:
 360       reg = R::dwarf2regno(addressSpace.getULEB128(p, instructionsEnd));
 361       if (reg > kMaxRegisterNumber)
 362         return false;
 363       results->savedRegisters[reg].location = kRegisterUnused;
 364       break;
 365     case DW_CFA_same_value:
 366       reg = R::dwarf2regno(addressSpace.getULEB128(p, instructionsEnd));
 367       if (reg > kMaxRegisterNumber)
 368         return false;
 369       // "same value" means register was stored in frame, but its current
 370       // value has not changed, so no need to restore from frame.
 371       // We model this as if the register was never saved.
 372       results->savedRegisters[reg].location = kRegisterUnused;
 373       break;
 374     case DW_CFA_register:
 375       reg = R::dwarf2regno(addressSpace.getULEB128(p, instructionsEnd));
 376       reg2 = R::dwarf2regno(addressSpace.getULEB128(p, instructionsEnd));
 377       if (reg > kMaxRegisterNumber)
 378         return false;
 379       if (reg2 > kMaxRegisterNumber)
 380         return false;
 381       results->savedRegisters[reg].location = kRegisterInRegister;
 382       results->savedRegisters[reg].value = reg2;
 383       break;
 384     case DW_CFA_remember_state:
 385       // avoid operator new, because that would be an upward dependency
 386       entry = (PrologInfoStackEntry *)malloc(sizeof(PrologInfoStackEntry));
 387       if (entry == NULL)
 388         return false;
 389
 390       entry->next = rememberStack;
 391       entry->info = *results;
 392       rememberStack = entry;
 393       break;
 394     case DW_CFA_restore_state:
 395       if (rememberStack == NULL)
 396         return false;
 397       {
 398         PrologInfoStackEntry *top = rememberStack;
 399         *results = top->info;
 400         rememberStack = top->next;
 401         free((char *)top);
 402       }
 403       break;
 404     case DW_CFA_def_cfa:
 405       reg = R::dwarf2regno(addressSpace.getULEB128(p, instructionsEnd));
 406       offset = addressSpace.getULEB128(p, instructionsEnd);
 407       if (reg > kMaxRegisterNumber)
 408         return false;
 409       results->cfaRegister = reg;
 410       results->cfaRegisterOffset = offset;
 411       break;
 412     case DW_CFA_def_cfa_register:
 413       reg = R::dwarf2regno(addressSpace.getULEB128(p, instructionsEnd));
 414       if (reg > kMaxRegisterNumber)
 415         return false;
 416       results->cfaRegister = reg;
 417       break;
 418     case DW_CFA_def_cfa_offset:
 419       results->cfaRegisterOffset = addressSpace.getULEB128(p, instructionsEnd);
 420       results->codeOffsetAtStackDecrement = codeOffset;
 421       break;
 422     case DW_CFA_def_cfa_expression:
 423       results->cfaRegister = 0;
 424       results->cfaExpression = p;
 425       length = addressSpace.getULEB128(p, instructionsEnd);
 426       p += length;
 427       break;
 428     case DW_CFA_expression:
 429       reg = R::dwarf2regno(addressSpace.getULEB128(p, instructionsEnd));
 430       if (reg > kMaxRegisterNumber)
 431         return false;
 432       results->savedRegisters[reg].location = kRegisterAtExpression;
 433       results->savedRegisters[reg].value = p;
 434       length = addressSpace.getULEB128(p, instructionsEnd);
 435       p += length;
 436       break;
 437     case DW_CFA_offset_extended_sf:
 438       reg = R::dwarf2regno(addressSpace.getULEB128(p, instructionsEnd));
 439       if (reg > kMaxRegisterNumber)
 440         return false;
 441       offset =
 442           addressSpace.getSLEB128(p, instructionsEnd) * cieInfo.dataAlignFactor;
 443       results->savedRegisters[reg].location = kRegisterInCFA;
 444       results->savedRegisters[reg].value = offset;
 445       break;
 446     case DW_CFA_def_cfa_sf:
 447       reg = R::dwarf2regno(addressSpace.getULEB128(p, instructionsEnd));
 448       offset =
 449           addressSpace.getSLEB128(p, instructionsEnd) * cieInfo.dataAlignFactor;
 450       if (reg > kMaxRegisterNumber)
 451         return false;
 452       results->cfaRegister = reg;
 453       results->cfaRegisterOffset = offset;
 454       break;
 455     case DW_CFA_def_cfa_offset_sf:
 456       results->cfaRegisterOffset =
 457           addressSpace.getSLEB128(p, instructionsEnd) * cieInfo.dataAlignFactor;
 458       results->codeOffsetAtStackDecrement = codeOffset;
 459       break;
 460     case DW_CFA_val_offset:
 461       reg = R::dwarf2regno(addressSpace.getULEB128(p, instructionsEnd));
 462       offset =
 463           addressSpace.getULEB128(p, instructionsEnd) * cieInfo.dataAlignFactor;
 464       if (reg > kMaxRegisterNumber)
 465         return false;
 466       results->savedRegisters[reg].location = kRegisterOffsetFromCFA;
 467       results->savedRegisters[reg].value = offset;
 468       break;
 469     case DW_CFA_val_offset_sf:
 470       reg = R::dwarf2regno(addressSpace.getULEB128(p, instructionsEnd));
 471       if (reg > kMaxRegisterNumber)
 472         return false;
 473       offset =
 474           addressSpace.getSLEB128(p, instructionsEnd) * cieInfo.dataAlignFactor;
 475       results->savedRegisters[reg].location = kRegisterOffsetFromCFA;
 476       results->savedRegisters[reg].value = offset;
 477       break;
 478     case DW_CFA_val_expression:
 479       reg = R::dwarf2regno(addressSpace.getULEB128(p, instructionsEnd));
 480       if (reg > kMaxRegisterNumber)
 481         return false;
 482       results->savedRegisters[reg].location = kRegisterIsExpression;
 483       results->savedRegisters[reg].value = p;
 484       length = addressSpace.getULEB128(p, instructionsEnd);
 485       p += length;
 486       break;
 487     case DW_CFA_GNU_window_save:
 488 #if defined(__sparc__)
 489       for (reg = 8; reg < 16; ++reg) {
 490         results->savedRegisters[reg].location = kRegisterInRegister;
 491         results->savedRegisters[reg].value = reg + 16;
 492       }
 493       for (reg = 16; reg < 32; ++reg) {
 494         results->savedRegisters[reg].location = kRegisterInCFA;
 495         results->savedRegisters[reg].value = (reg - 16) * sizeof(typename R::reg_t);
 496       }
 497       break;
 498 #else
 499       return false;
 500 #endif
 501     case DW_CFA_GNU_args_size:
 502       offset = addressSpace.getULEB128(p, instructionsEnd);
 503       results->spExtraArgSize = offset;
 504       break;
 505     case DW_CFA_GNU_negative_offset_extended:
 506       reg = R::dwarf2regno(addressSpace.getULEB128(p, instructionsEnd));
 507       if (reg > kMaxRegisterNumber)
 508         return false;
 509       offset =
 510           addressSpace.getULEB128(p, instructionsEnd) * cieInfo.dataAlignFactor;
 511       results->savedRegisters[reg].location = kRegisterInCFA;
 512       results->savedRegisters[reg].value = -offset;
 513       break;
 514     default:
 515       operand = opcode & 0x3F;
 516       switch (opcode & 0xC0) {
 517       case DW_CFA_offset:
 518         reg = R::dwarf2regno(operand);
 519         if (reg > kMaxRegisterNumber)
 520           return false;
 521         offset = addressSpace.getULEB128(p, instructionsEnd) *
 522                  cieInfo.dataAlignFactor;
 523         results->savedRegisters[reg].location = kRegisterInCFA;
 524         results->savedRegisters[reg].value = offset;
 525         break;
 526       case DW_CFA_advance_loc:
 527         codeOffset += operand * cieInfo.codeAlignFactor;
 528         break;
 529       case DW_CFA_restore:
 530         reg = R::dwarf2regno(operand);
 531         if (reg > kMaxRegisterNumber)
 532           return false;
 533         results->savedRegisters[reg] = initialState.savedRegisters[reg];
 534         break;
 535       default:
 536         return false;
 537       }
 538     }
 539   }
 540
 541   return true;
 542 }
 543
 544 } // namespace _Unwind
 545
 546 #endif // __DWARF_PARSER_HPP__