bolt/lib/Core/Exceptions.cpp

   1 //===- bolt/Core/Exceptions.cpp - Helpers for C++ exceptions --------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file implements functions for handling C++ exception meta data.
  10 //
  11 // Some of the code is taken from examples/ExceptionDemo
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "bolt/Core/Exceptions.h"
  16 #include "bolt/Core/BinaryFunction.h"
  17 #include "llvm/ADT/ArrayRef.h"
  18 #include "llvm/ADT/Twine.h"
  19 #include "llvm/BinaryFormat/Dwarf.h"
  20 #include "llvm/DebugInfo/DWARF/DWARFDebugFrame.h"
  21 #include "llvm/Support/Casting.h"
  22 #include "llvm/Support/CommandLine.h"
  23 #include "llvm/Support/Debug.h"
  24 #include "llvm/Support/Errc.h"
  25 #include "llvm/Support/LEB128.h"
  26 #include "llvm/Support/MathExtras.h"
  27 #include "llvm/Support/raw_ostream.h"
  28 #include <map>
  29
  30 #undef  DEBUG_TYPE
  31 #define DEBUG_TYPE "bolt-exceptions"
  32
  33 using namespace llvm::dwarf;
  34
  35 namespace opts {
  36
  37 extern llvm::cl::OptionCategory BoltCategory;
  38
  39 extern llvm::cl::opt<unsigned> Verbosity;
  40
  41 static llvm::cl::opt<bool>
  42     PrintExceptions("print-exceptions",
  43                     llvm::cl::desc("print exception handling data"),
  44                     llvm::cl::Hidden, llvm::cl::cat(BoltCategory));
  45
  46 } // namespace opts
  47
  48 namespace llvm {
  49 namespace bolt {
  50
  51 // Read and dump the .gcc_exception_table section entry.
  52 //
  53 // .gcc_except_table section contains a set of Language-Specific Data Areas -
  54 // a fancy name for exception handling tables. There's one  LSDA entry per
  55 // function. However, we can't actually tell which function LSDA refers to
  56 // unless we parse .eh_frame entry that refers to the LSDA.
  57 // Then inside LSDA most addresses are encoded relative to the function start,
  58 // so we need the function context in order to get to real addresses.
  59 //
  60 // The best visual representation of the tables comprising LSDA and
  61 // relationships between them is illustrated at:
  62 //   https://github.com/itanium-cxx-abi/cxx-abi/blob/master/exceptions.pdf
  63 // Keep in mind that GCC implementation deviates slightly from that document.
  64 //
  65 // To summarize, there are 4 tables in LSDA: call site table, actions table,
  66 // types table, and types index table (for indirection). The main table contains
  67 // call site entries. Each call site includes a PC range that can throw an
  68 // exception, a handler (landing pad), and a reference to an entry in the action
  69 // table. The handler and/or action could be 0. The action entry is a head
  70 // of a list of actions associated with a call site. The action table contains
  71 // all such lists (it could be optimized to share list tails). Each action could
  72 // be either to catch an exception of a given type, to perform a cleanup, or to
  73 // propagate the exception after filtering it out (e.g. to make sure function
  74 // exception specification is not violated). Catch action contains a reference
  75 // to an entry in the type table, and filter action refers to an entry in the
  76 // type index table to encode a set of types to filter.
  77 //
  78 // Call site table follows LSDA header. Action table immediately follows the
  79 // call site table.
  80 //
  81 // Both types table and type index table start at the same location, but they
  82 // grow in opposite directions (types go up, indices go down). The beginning of
  83 // these tables is encoded in LSDA header. Sizes for both of the tables are not
  84 // included anywhere.
  85 //
  86 // We have to parse all of the tables to determine their sizes. Then we have
  87 // to parse the call site table and associate discovered information with
  88 // actual call instructions and landing pad blocks.
  89 //
  90 // For the purpose of rewriting exception handling tables, we can reuse action,
  91 // and type index tables in their original binary format.
  92 //
  93 // Type table could be encoded using position-independent references, and thus
  94 // may require relocation.
  95 //
  96 // Ideally we should be able to re-write LSDA in-place, without the need to
  97 // allocate a new space for it. Sadly there's no guarantee that the new call
  98 // site table will be the same size as GCC uses uleb encodings for PC offsets.
  99 //
 100 // Note: some functions have LSDA entries with 0 call site entries.
 101 void BinaryFunction::parseLSDA(ArrayRef<uint8_t> LSDASectionData,
 102                                uint64_t LSDASectionAddress) {
 103   assert(CurrentState == State::Disassembled && "unexpected function state");
 104
 105   if (!getLSDAAddress())
 106     return;
 107
 108   DWARFDataExtractor Data(
 109       StringRef(reinterpret_cast<const char *>(LSDASectionData.data()),
 110                 LSDASectionData.size()),
 111       BC.DwCtx->getDWARFObj().isLittleEndian(),
 112       BC.DwCtx->getDWARFObj().getAddressSize());
 113   uint64_t Offset = getLSDAAddress() - LSDASectionAddress;
 114   assert(Data.isValidOffset(Offset) && "wrong LSDA address");
 115
 116   const uint8_t LPStartEncoding = Data.getU8(&Offset);
 117   uint64_t LPStart = Address;
 118   if (LPStartEncoding != dwarf::DW_EH_PE_omit) {
 119     std::optional<uint64_t> MaybeLPStart = Data.getEncodedPointer(
 120         &Offset, LPStartEncoding, Offset + LSDASectionAddress);
 121     if (!MaybeLPStart) {
 122       errs() << "BOLT-ERROR: unsupported LPStartEncoding: "
 123              << (unsigned)LPStartEncoding << '\n';
 124       exit(1);
 125     }
 126     LPStart = *MaybeLPStart;
 127   }
 128
 129   const uint8_t TTypeEncoding = Data.getU8(&Offset);
 130   LSDATypeEncoding = TTypeEncoding;
 131   size_t TTypeEncodingSize = 0;
 132   uintptr_t TTypeEnd = 0;
 133   if (TTypeEncoding != DW_EH_PE_omit) {
 134     TTypeEnd = Data.getULEB128(&Offset);
 135     TTypeEncodingSize = BC.getDWARFEncodingSize(TTypeEncoding);
 136   }
 137
 138   if (opts::PrintExceptions) {
 139     outs() << "[LSDA at 0x" << Twine::utohexstr(getLSDAAddress())
 140            << " for function " << *this << "]:\n";
 141     outs() << "LPStart Encoding = 0x" << Twine::utohexstr(LPStartEncoding)
 142            << '\n';
 143     outs() << "LPStart = 0x" << Twine::utohexstr(LPStart) << '\n';
 144     outs() << "TType Encoding = 0x" << Twine::utohexstr(TTypeEncoding) << '\n';
 145     outs() << "TType End = " << TTypeEnd << '\n';
 146   }
 147
 148   // Table to store list of indices in type table. Entries are uleb128 values.
 149   const uint64_t TypeIndexTableStart = Offset + TTypeEnd;
 150
 151   // Offset past the last decoded index.
 152   uint64_t MaxTypeIndexTableOffset = 0;
 153
 154   // Max positive index used in type table.
 155   unsigned MaxTypeIndex = 0;
 156
 157   // The actual type info table starts at the same location, but grows in
 158   // opposite direction. TTypeEncoding is used to encode stored values.
 159   const uint64_t TypeTableStart = Offset + TTypeEnd;
 160
 161   uint8_t CallSiteEncoding = Data.getU8(&Offset);
 162   uint32_t CallSiteTableLength = Data.getULEB128(&Offset);
 163   uint64_t CallSiteTableStart = Offset;
 164   uint64_t CallSiteTableEnd = CallSiteTableStart + CallSiteTableLength;
 165   uint64_t CallSitePtr = CallSiteTableStart;
 166   uint64_t ActionTableStart = CallSiteTableEnd;
 167
 168   if (opts::PrintExceptions) {
 169     outs() << "CallSite Encoding = " << (unsigned)CallSiteEncoding << '\n';
 170     outs() << "CallSite table length = " << CallSiteTableLength << '\n';
 171     outs() << '\n';
 172   }
 173
 174   this->HasEHRanges = CallSitePtr < CallSiteTableEnd;
 175   const uint64_t RangeBase = getAddress();
 176   while (CallSitePtr < CallSiteTableEnd) {
 177     uint64_t Start = *Data.getEncodedPointer(&CallSitePtr, CallSiteEncoding,
 178                                              CallSitePtr + LSDASectionAddress);
 179     uint64_t Length = *Data.getEncodedPointer(&CallSitePtr, CallSiteEncoding,
 180                                               CallSitePtr + LSDASectionAddress);
 181     uint64_t LandingPad = *Data.getEncodedPointer(
 182         &CallSitePtr, CallSiteEncoding, CallSitePtr + LSDASectionAddress);
 183     uint64_t ActionEntry = Data.getULEB128(&CallSitePtr);
 184     if (LandingPad)
 185       LandingPad += LPStart;
 186
 187     if (opts::PrintExceptions) {
 188       outs() << "Call Site: [0x" << Twine::utohexstr(RangeBase + Start)
 189              << ", 0x" << Twine::utohexstr(RangeBase + Start + Length)
 190              << "); landing pad: 0x" << Twine::utohexstr(LandingPad)
 191              << "; action entry: 0x" << Twine::utohexstr(ActionEntry) << "\n";
 192       outs() << "  current offset is " << (CallSitePtr - CallSiteTableStart)
 193              << '\n';
 194     }
 195
 196     // Create a handler entry if necessary.
 197     MCSymbol *LPSymbol = nullptr;
 198     if (LandingPad) {
 199       // Verify if landing pad code is located outside current function
 200       // Support landing pad to builtin_unreachable
 201       if (LandingPad < Address || LandingPad > Address + getSize()) {
 202         BinaryFunction *Fragment =
 203             BC.getBinaryFunctionContainingAddress(LandingPad);
 204         assert(Fragment != nullptr &&
 205                "BOLT-ERROR: cannot find landing pad fragment");
 206         BC.addInterproceduralReference(this, Fragment->getAddress());
 207         BC.processInterproceduralReferences();
 208         assert(isParentOrChildOf(*Fragment) &&
 209                "BOLT-ERROR: cannot have landing pads in different functions");
 210         setHasIndirectTargetToSplitFragment(true);
 211         BC.addFragmentsToSkip(this);
 212         return;
 213       }
 214
 215       const uint64_t LPOffset = LandingPad - getAddress();
 216       if (!getInstructionAtOffset(LPOffset)) {
 217         if (opts::Verbosity >= 1)
 218           errs() << "BOLT-WARNING: landing pad " << Twine::utohexstr(LPOffset)
 219                  << " not pointing to an instruction in function " << *this
 220                  << " - ignoring.\n";
 221       } else {
 222         auto Label = Labels.find(LPOffset);
 223         if (Label != Labels.end()) {
 224           LPSymbol = Label->second;
 225         } else {
 226           LPSymbol = BC.Ctx->createNamedTempSymbol("LP");
 227           Labels[LPOffset] = LPSymbol;
 228         }
 229       }
 230     }
 231
 232     // Mark all call instructions in the range.
 233     auto II = Instructions.find(Start);
 234     auto IE = Instructions.end();
 235     assert(II != IE && "exception range not pointing to an instruction");
 236     do {
 237       MCInst &Instruction = II->second;
 238       if (BC.MIB->isCall(Instruction) &&
 239           !BC.MIB->getConditionalTailCall(Instruction)) {
 240         assert(!BC.MIB->isInvoke(Instruction) &&
 241                "overlapping exception ranges detected");
 242         // Add extra operands to a call instruction making it an invoke from
 243         // now on.
 244         BC.MIB->addEHInfo(Instruction,
 245                           MCPlus::MCLandingPad(LPSymbol, ActionEntry));
 246       }
 247       ++II;
 248     } while (II != IE && II->first < Start + Length);
 249
 250     if (ActionEntry != 0) {
 251       auto printType = [&](int Index, raw_ostream &OS) {
 252         assert(Index > 0 && "only positive indices are valid");
 253         uint64_t TTEntry = TypeTableStart - Index * TTypeEncodingSize;
 254         const uint64_t TTEntryAddress = TTEntry + LSDASectionAddress;
 255         uint64_t TypeAddress =
 256             *Data.getEncodedPointer(&TTEntry, TTypeEncoding, TTEntryAddress);
 257         if ((TTypeEncoding & DW_EH_PE_pcrel) && TypeAddress == TTEntryAddress)
 258           TypeAddress = 0;
 259         if (TypeAddress == 0) {
 260           OS << "<all>";
 261           return;
 262         }
 263         if (TTypeEncoding & DW_EH_PE_indirect) {
 264           ErrorOr<uint64_t> PointerOrErr = BC.getPointerAtAddress(TypeAddress);
 265           assert(PointerOrErr && "failed to decode indirect address");
 266           TypeAddress = *PointerOrErr;
 267         }
 268         if (BinaryData *TypeSymBD = BC.getBinaryDataAtAddress(TypeAddress))
 269           OS << TypeSymBD->getName();
 270         else
 271           OS << "0x" << Twine::utohexstr(TypeAddress);
 272       };
 273       if (opts::PrintExceptions)
 274         outs() << "    actions: ";
 275       uint64_t ActionPtr = ActionTableStart + ActionEntry - 1;
 276       int64_t ActionType;
 277       int64_t ActionNext;
 278       const char *Sep = "";
 279       do {
 280         ActionType = Data.getSLEB128(&ActionPtr);
 281         const uint32_t Self = ActionPtr;
 282         ActionNext = Data.getSLEB128(&ActionPtr);
 283         if (opts::PrintExceptions)
 284           outs() << Sep << "(" << ActionType << ", " << ActionNext << ") ";
 285         if (ActionType == 0) {
 286           if (opts::PrintExceptions)
 287             outs() << "cleanup";
 288         } else if (ActionType > 0) {
 289           // It's an index into a type table.
 290           MaxTypeIndex =
 291               std::max(MaxTypeIndex, static_cast<unsigned>(ActionType));
 292           if (opts::PrintExceptions) {
 293             outs() << "catch type ";
 294             printType(ActionType, outs());
 295           }
 296         } else { // ActionType < 0
 297           if (opts::PrintExceptions)
 298             outs() << "filter exception types ";
 299           const char *TSep = "";
 300           // ActionType is a negative *byte* offset into *uleb128-encoded* table
 301           // of indices with base 1.
 302           // E.g. -1 means offset 0, -2 is offset 1, etc. The indices are
 303           // encoded using uleb128 thus we cannot directly dereference them.
 304           uint64_t TypeIndexTablePtr = TypeIndexTableStart - ActionType - 1;
 305           while (uint64_t Index = Data.getULEB128(&TypeIndexTablePtr)) {
 306             MaxTypeIndex = std::max(MaxTypeIndex, static_cast<unsigned>(Index));
 307             if (opts::PrintExceptions) {
 308               outs() << TSep;
 309               printType(Index, outs());
 310               TSep = ", ";
 311             }
 312           }
 313           MaxTypeIndexTableOffset = std::max(
 314               MaxTypeIndexTableOffset, TypeIndexTablePtr - TypeIndexTableStart);
 315         }
 316
 317         Sep = "; ";
 318
 319         ActionPtr = Self + ActionNext;
 320       } while (ActionNext);
 321       if (opts::PrintExceptions)
 322         outs() << '\n';
 323     }
 324   }
 325   if (opts::PrintExceptions)
 326     outs() << '\n';
 327
 328   assert(TypeIndexTableStart + MaxTypeIndexTableOffset <=
 329              Data.getData().size() &&
 330          "LSDA entry has crossed section boundary");
 331
 332   if (TTypeEnd) {
 333     LSDAActionTable = LSDASectionData.slice(
 334         ActionTableStart, TypeIndexTableStart -
 335                               MaxTypeIndex * TTypeEncodingSize -
 336                               ActionTableStart);
 337     for (unsigned Index = 1; Index <= MaxTypeIndex; ++Index) {
 338       uint64_t TTEntry = TypeTableStart - Index * TTypeEncodingSize;
 339       const uint64_t TTEntryAddress = TTEntry + LSDASectionAddress;
 340       uint64_t TypeAddress =
 341           *Data.getEncodedPointer(&TTEntry, TTypeEncoding, TTEntryAddress);
 342       if ((TTypeEncoding & DW_EH_PE_pcrel) && (TypeAddress == TTEntryAddress))
 343         TypeAddress = 0;
 344       if (TTypeEncoding & DW_EH_PE_indirect) {
 345         LSDATypeAddressTable.emplace_back(TypeAddress);
 346         if (TypeAddress) {
 347           ErrorOr<uint64_t> PointerOrErr = BC.getPointerAtAddress(TypeAddress);
 348           assert(PointerOrErr && "failed to decode indirect address");
 349           TypeAddress = *PointerOrErr;
 350         }
 351       }
 352       LSDATypeTable.emplace_back(TypeAddress);
 353     }
 354     LSDATypeIndexTable =
 355         LSDASectionData.slice(TypeIndexTableStart, MaxTypeIndexTableOffset);
 356   }
 357 }
 358
 359 void BinaryFunction::updateEHRanges() {
 360   if (getSize() == 0)
 361     return;
 362
 363   assert(CurrentState == State::CFG_Finalized && "unexpected state");
 364
 365   // Build call sites table.
 366   struct EHInfo {
 367     const MCSymbol *LP; // landing pad
 368     uint64_t Action;
 369   };
 370
 371   // Sites to update.
 372   CallSitesList Sites;
 373
 374   for (FunctionFragment &FF : getLayout().fragments()) {
 375     // If previous call can throw, this is its exception handler.
 376     EHInfo PreviousEH = {nullptr, 0};
 377
 378     // Marker for the beginning of exceptions range.
 379     const MCSymbol *StartRange = nullptr;
 380
 381     for (BinaryBasicBlock *const BB : FF) {
 382       for (MCInst &Instr : *BB) {
 383         if (!BC.MIB->isCall(Instr))
 384           continue;
 385
 386         // Instruction can throw an exception that should be handled.
 387         const bool Throws = BC.MIB->isInvoke(Instr);
 388
 389         // Ignore the call if it's a continuation of a no-throw gap.
 390         if (!Throws && !StartRange)
 391           continue;
 392
 393         // Extract exception handling information from the instruction.
 394         const MCSymbol *LP = nullptr;
 395         uint64_t Action = 0;
 396         if (const std::optional<MCPlus::MCLandingPad> EHInfo =
 397                 BC.MIB->getEHInfo(Instr))
 398           std::tie(LP, Action) = *EHInfo;
 399
 400         // No action if the exception handler has not changed.
 401         if (Throws && StartRange && PreviousEH.LP == LP &&
 402             PreviousEH.Action == Action)
 403           continue;
 404
 405         // Same symbol is used for the beginning and the end of the range.
 406         MCSymbol *EHSymbol;
 407         if (MCSymbol *InstrLabel = BC.MIB->getLabel(Instr)) {
 408           EHSymbol = InstrLabel;
 409         } else {
 410           std::unique_lock<llvm::sys::RWMutex> Lock(BC.CtxMutex);
 411           EHSymbol = BC.Ctx->createNamedTempSymbol("EH");
 412           BC.MIB->setLabel(Instr, EHSymbol);
 413         }
 414
 415         // At this point we could be in one of the following states:
 416         //
 417         // I. Exception handler has changed and we need to close previous range
 418         //    and start a new one.
 419         //
 420         // II. Start a new exception range after the gap.
 421         //
 422         // III. Close current exception range and start a new gap.
 423         const MCSymbol *EndRange;
 424         if (StartRange) {
 425           // I, III:
 426           EndRange = EHSymbol;
 427         } else {
 428           // II:
 429           StartRange = EHSymbol;
 430           EndRange = nullptr;
 431         }
 432
 433         // Close the previous range.
 434         if (EndRange)
 435           Sites.emplace_back(
 436               FF.getFragmentNum(),
 437               CallSite{StartRange, EndRange, PreviousEH.LP, PreviousEH.Action});
 438
 439         if (Throws) {
 440           // I, II:
 441           StartRange = EHSymbol;
 442           PreviousEH = EHInfo{LP, Action};
 443         } else {
 444           StartRange = nullptr;
 445         }
 446       }
 447     }
 448
 449     // Check if we need to close the range.
 450     if (StartRange) {
 451       const MCSymbol *EndRange = getFunctionEndLabel(FF.getFragmentNum());
 452       Sites.emplace_back(
 453           FF.getFragmentNum(),
 454           CallSite{StartRange, EndRange, PreviousEH.LP, PreviousEH.Action});
 455     }
 456   }
 457
 458   addCallSites(Sites);
 459 }
 460
 461 const uint8_t DWARF_CFI_PRIMARY_OPCODE_MASK = 0xc0;
 462
 463 CFIReaderWriter::CFIReaderWriter(const DWARFDebugFrame &EHFrame) {
 464   // Prepare FDEs for fast lookup
 465   for (const dwarf::FrameEntry &Entry : EHFrame.entries()) {
 466     const auto *CurFDE = dyn_cast<dwarf::FDE>(&Entry);
 467     // Skip CIEs.
 468     if (!CurFDE)
 469       continue;
 470     // There could me multiple FDEs with the same initial address, and perhaps
 471     // different sizes (address ranges). Use the first entry with non-zero size.
 472     auto FDEI = FDEs.lower_bound(CurFDE->getInitialLocation());
 473     if (FDEI != FDEs.end() && FDEI->first == CurFDE->getInitialLocation()) {
 474       if (CurFDE->getAddressRange()) {
 475         if (FDEI->second->getAddressRange() == 0) {
 476           FDEI->second = CurFDE;
 477         } else if (opts::Verbosity > 0) {
 478           errs() << "BOLT-WARNING: different FDEs for function at 0x"
 479                  << Twine::utohexstr(FDEI->first)
 480                  << " detected; sizes: " << FDEI->second->getAddressRange()
 481                  << " and " << CurFDE->getAddressRange() << '\n';
 482         }
 483       }
 484     } else {
 485       FDEs.emplace_hint(FDEI, CurFDE->getInitialLocation(), CurFDE);
 486     }
 487   }
 488 }
 489
 490 bool CFIReaderWriter::fillCFIInfoFor(BinaryFunction &Function) const {
 491   uint64_t Address = Function.getAddress();
 492   auto I = FDEs.find(Address);
 493   // Ignore zero-length FDE ranges.
 494   if (I == FDEs.end() || !I->second->getAddressRange())
 495     return true;
 496
 497   const FDE &CurFDE = *I->second;
 498   std::optional<uint64_t> LSDA = CurFDE.getLSDAAddress();
 499   Function.setLSDAAddress(LSDA ? *LSDA : 0);
 500
 501   uint64_t Offset = Function.getFirstInstructionOffset();
 502   uint64_t CodeAlignment = CurFDE.getLinkedCIE()->getCodeAlignmentFactor();
 503   uint64_t DataAlignment = CurFDE.getLinkedCIE()->getDataAlignmentFactor();
 504   if (CurFDE.getLinkedCIE()->getPersonalityAddress()) {
 505     Function.setPersonalityFunction(
 506         *CurFDE.getLinkedCIE()->getPersonalityAddress());
 507     Function.setPersonalityEncoding(
 508         *CurFDE.getLinkedCIE()->getPersonalityEncoding());
 509   }
 510
 511   auto decodeFrameInstruction = [&Function, &Offset, Address, CodeAlignment,
 512                                  DataAlignment](
 513                                     const CFIProgram::Instruction &Instr) {
 514     uint8_t Opcode = Instr.Opcode;
 515     if (Opcode & DWARF_CFI_PRIMARY_OPCODE_MASK)
 516       Opcode &= DWARF_CFI_PRIMARY_OPCODE_MASK;
 517     switch (Instr.Opcode) {
 518     case DW_CFA_nop:
 519       break;
 520     case DW_CFA_advance_loc4:
 521     case DW_CFA_advance_loc2:
 522     case DW_CFA_advance_loc1:
 523     case DW_CFA_advance_loc:
 524       // Advance our current address
 525       Offset += CodeAlignment * int64_t(Instr.Ops[0]);
 526       break;
 527     case DW_CFA_offset_extended_sf:
 528       Function.addCFIInstruction(
 529           Offset,
 530           MCCFIInstruction::createOffset(
 531               nullptr, Instr.Ops[0], DataAlignment * int64_t(Instr.Ops[1])));
 532       break;
 533     case DW_CFA_offset_extended:
 534     case DW_CFA_offset:
 535       Function.addCFIInstruction(
 536           Offset, MCCFIInstruction::createOffset(nullptr, Instr.Ops[0],
 537                                                  DataAlignment * Instr.Ops[1]));
 538       break;
 539     case DW_CFA_restore_extended:
 540     case DW_CFA_restore:
 541       Function.addCFIInstruction(
 542           Offset, MCCFIInstruction::createRestore(nullptr, Instr.Ops[0]));
 543       break;
 544     case DW_CFA_set_loc:
 545       assert(Instr.Ops[0] >= Address && "set_loc out of function bounds");
 546       assert(Instr.Ops[0] <= Address + Function.getSize() &&
 547              "set_loc out of function bounds");
 548       Offset = Instr.Ops[0] - Address;
 549       break;
 550
 551     case DW_CFA_undefined:
 552       Function.addCFIInstruction(
 553           Offset, MCCFIInstruction::createUndefined(nullptr, Instr.Ops[0]));
 554       break;
 555     case DW_CFA_same_value:
 556       Function.addCFIInstruction(
 557           Offset, MCCFIInstruction::createSameValue(nullptr, Instr.Ops[0]));
 558       break;
 559     case DW_CFA_register:
 560       Function.addCFIInstruction(
 561           Offset, MCCFIInstruction::createRegister(nullptr, Instr.Ops[0],
 562                                                    Instr.Ops[1]));
 563       break;
 564     case DW_CFA_remember_state:
 565       Function.addCFIInstruction(
 566           Offset, MCCFIInstruction::createRememberState(nullptr));
 567       break;
 568     case DW_CFA_restore_state:
 569       Function.addCFIInstruction(Offset,
 570                                  MCCFIInstruction::createRestoreState(nullptr));
 571       break;
 572     case DW_CFA_def_cfa:
 573       Function.addCFIInstruction(
 574           Offset,
 575           MCCFIInstruction::cfiDefCfa(nullptr, Instr.Ops[0], Instr.Ops[1]));
 576       break;
 577     case DW_CFA_def_cfa_sf:
 578       Function.addCFIInstruction(
 579           Offset,
 580           MCCFIInstruction::cfiDefCfa(nullptr, Instr.Ops[0],
 581                                       DataAlignment * int64_t(Instr.Ops[1])));
 582       break;
 583     case DW_CFA_def_cfa_register:
 584       Function.addCFIInstruction(Offset, MCCFIInstruction::createDefCfaRegister(
 585                                              nullptr, Instr.Ops[0]));
 586       break;
 587     case DW_CFA_def_cfa_offset:
 588       Function.addCFIInstruction(
 589           Offset, MCCFIInstruction::cfiDefCfaOffset(nullptr, Instr.Ops[0]));
 590       break;
 591     case DW_CFA_def_cfa_offset_sf:
 592       Function.addCFIInstruction(
 593           Offset, MCCFIInstruction::cfiDefCfaOffset(
 594                       nullptr, DataAlignment * int64_t(Instr.Ops[0])));
 595       break;
 596     case DW_CFA_GNU_args_size:
 597       Function.addCFIInstruction(
 598           Offset, MCCFIInstruction::createGnuArgsSize(nullptr, Instr.Ops[0]));
 599       Function.setUsesGnuArgsSize();
 600       break;
 601     case DW_CFA_val_offset_sf:
 602     case DW_CFA_val_offset:
 603       if (opts::Verbosity >= 1) {
 604         errs() << "BOLT-WARNING: DWARF val_offset() unimplemented\n";
 605       }
 606       return false;
 607     case DW_CFA_def_cfa_expression:
 608     case DW_CFA_val_expression:
 609     case DW_CFA_expression: {
 610       StringRef ExprBytes = Instr.Expression->getData();
 611       std::string Str;
 612       raw_string_ostream OS(Str);
 613       // Manually encode this instruction using CFI escape
 614       OS << Opcode;
 615       if (Opcode != DW_CFA_def_cfa_expression)
 616         encodeULEB128(Instr.Ops[0], OS);
 617       encodeULEB128(ExprBytes.size(), OS);
 618       OS << ExprBytes;
 619       Function.addCFIInstruction(
 620           Offset, MCCFIInstruction::createEscape(nullptr, OS.str()));
 621       break;
 622     }
 623     case DW_CFA_MIPS_advance_loc8:
 624       if (opts::Verbosity >= 1)
 625         errs() << "BOLT-WARNING: DW_CFA_MIPS_advance_loc unimplemented\n";
 626       return false;
 627     case DW_CFA_GNU_window_save:
 628       // DW_CFA_GNU_window_save and DW_CFA_GNU_NegateRAState just use the same
 629       // id but mean different things. The latter is used in AArch64.
 630       if (Function.getBinaryContext().isAArch64()) {
 631         Function.addCFIInstruction(
 632             Offset, MCCFIInstruction::createNegateRAState(nullptr));
 633         break;
 634       }
 635       if (opts::Verbosity >= 1)
 636         errs() << "BOLT-WARNING: DW_CFA_GNU_window_save unimplemented\n";
 637       return false;
 638     case DW_CFA_lo_user:
 639     case DW_CFA_hi_user:
 640       if (opts::Verbosity >= 1)
 641         errs() << "BOLT-WARNING: DW_CFA_*_user unimplemented\n";
 642       return false;
 643     default:
 644       if (opts::Verbosity >= 1)
 645         errs() << "BOLT-WARNING: Unrecognized CFI instruction: " << Instr.Opcode
 646                << '\n';
 647       return false;
 648     }
 649
 650     return true;
 651   };
 652
 653   for (const CFIProgram::Instruction &Instr : CurFDE.getLinkedCIE()->cfis())
 654     if (!decodeFrameInstruction(Instr))
 655       return false;
 656
 657   for (const CFIProgram::Instruction &Instr : CurFDE.cfis())
 658     if (!decodeFrameInstruction(Instr))
 659       return false;
 660
 661   return true;
 662 }
 663
 664 std::vector<char> CFIReaderWriter::generateEHFrameHeader(
 665     const DWARFDebugFrame &OldEHFrame, const DWARFDebugFrame &NewEHFrame,
 666     uint64_t EHFrameHeaderAddress,
 667     std::vector<uint64_t> &FailedAddresses) const {
 668   // Common PC -> FDE map to be written into .eh_frame_hdr.
 669   std::map<uint64_t, uint64_t> PCToFDE;
 670
 671   // Presort array for binary search.
 672   llvm::sort(FailedAddresses);
 673
 674   // Initialize PCToFDE using NewEHFrame.
 675   for (dwarf::FrameEntry &Entry : NewEHFrame.entries()) {
 676     const dwarf::FDE *FDE = dyn_cast<dwarf::FDE>(&Entry);
 677     if (FDE == nullptr)
 678       continue;
 679     const uint64_t FuncAddress = FDE->getInitialLocation();
 680     const uint64_t FDEAddress =
 681         NewEHFrame.getEHFrameAddress() + FDE->getOffset();
 682
 683     // Ignore unused FDEs.
 684     if (FuncAddress == 0)
 685       continue;
 686
 687     // Add the address to the map unless we failed to write it.
 688     if (!std::binary_search(FailedAddresses.begin(), FailedAddresses.end(),
 689                             FuncAddress)) {
 690       LLVM_DEBUG(dbgs() << "BOLT-DEBUG: FDE for function at 0x"
 691                         << Twine::utohexstr(FuncAddress) << " is at 0x"
 692                         << Twine::utohexstr(FDEAddress) << '\n');
 693       PCToFDE[FuncAddress] = FDEAddress;
 694     }
 695   };
 696
 697   LLVM_DEBUG(dbgs() << "BOLT-DEBUG: new .eh_frame contains "
 698                     << llvm::size(NewEHFrame.entries()) << " entries\n");
 699
 700   // Add entries from the original .eh_frame corresponding to the functions
 701   // that we did not update.
 702   for (const dwarf::FrameEntry &Entry : OldEHFrame) {
 703     const dwarf::FDE *FDE = dyn_cast<dwarf::FDE>(&Entry);
 704     if (FDE == nullptr)
 705       continue;
 706     const uint64_t FuncAddress = FDE->getInitialLocation();
 707     const uint64_t FDEAddress =
 708         OldEHFrame.getEHFrameAddress() + FDE->getOffset();
 709
 710     // Add the address if we failed to write it.
 711     if (PCToFDE.count(FuncAddress) == 0) {
 712       LLVM_DEBUG(dbgs() << "BOLT-DEBUG: old FDE for function at 0x"
 713                         << Twine::utohexstr(FuncAddress) << " is at 0x"
 714                         << Twine::utohexstr(FDEAddress) << '\n');
 715       PCToFDE[FuncAddress] = FDEAddress;
 716     }
 717   };
 718
 719   LLVM_DEBUG(dbgs() << "BOLT-DEBUG: old .eh_frame contains "
 720                     << llvm::size(OldEHFrame.entries()) << " entries\n");
 721
 722   // Generate a new .eh_frame_hdr based on the new map.
 723
 724   // Header plus table of entries of size 8 bytes.
 725   std::vector<char> EHFrameHeader(12 + PCToFDE.size() * 8);
 726
 727   // Version is 1.
 728   EHFrameHeader[0] = 1;
 729   // Encoding of the eh_frame pointer.
 730   EHFrameHeader[1] = DW_EH_PE_pcrel | DW_EH_PE_sdata4;
 731   // Encoding of the count field to follow.
 732   EHFrameHeader[2] = DW_EH_PE_udata4;
 733   // Encoding of the table entries - 4-byte offset from the start of the header.
 734   EHFrameHeader[3] = DW_EH_PE_datarel | DW_EH_PE_sdata4;
 735
 736   // Address of eh_frame. Use the new one.
 737   support::ulittle32_t::ref(EHFrameHeader.data() + 4) =
 738       NewEHFrame.getEHFrameAddress() - (EHFrameHeaderAddress + 4);
 739
 740   // Number of entries in the table (FDE count).
 741   support::ulittle32_t::ref(EHFrameHeader.data() + 8) = PCToFDE.size();
 742
 743   // Write the table at offset 12.
 744   char *Ptr = EHFrameHeader.data();
 745   uint32_t Offset = 12;
 746   for (const auto &PCI : PCToFDE) {
 747     int64_t InitialPCOffset = PCI.first - EHFrameHeaderAddress;
 748     assert(isInt<32>(InitialPCOffset) && "PC offset out of bounds");
 749     support::ulittle32_t::ref(Ptr + Offset) = InitialPCOffset;
 750     Offset += 4;
 751     int64_t FDEOffset = PCI.second - EHFrameHeaderAddress;
 752     assert(isInt<32>(FDEOffset) && "FDE offset out of bounds");
 753     support::ulittle32_t::ref(Ptr + Offset) = FDEOffset;
 754     Offset += 4;
 755   }
 756
 757   return EHFrameHeader;
 758 }
 759
 760 Error EHFrameParser::parseCIE(uint64_t StartOffset) {
 761   uint8_t Version = Data.getU8(&Offset);
 762   const char *Augmentation = Data.getCStr(&Offset);
 763   StringRef AugmentationString(Augmentation ? Augmentation : "");
 764   uint8_t AddressSize =
 765       Version < 4 ? Data.getAddressSize() : Data.getU8(&Offset);
 766   Data.setAddressSize(AddressSize);
 767   // Skip segment descriptor size
 768   if (Version >= 4)
 769     Offset += 1;
 770   // Skip code alignment factor
 771   Data.getULEB128(&Offset);
 772   // Skip data alignment
 773   Data.getSLEB128(&Offset);
 774   // Skip return address register
 775   if (Version == 1)
 776     Offset += 1;
 777   else
 778     Data.getULEB128(&Offset);
 779
 780   uint32_t FDEPointerEncoding = DW_EH_PE_absptr;
 781   uint32_t LSDAPointerEncoding = DW_EH_PE_omit;
 782   // Walk the augmentation string to get all the augmentation data.
 783   for (unsigned i = 0, e = AugmentationString.size(); i != e; ++i) {
 784     switch (AugmentationString[i]) {
 785     default:
 786       return createStringError(
 787           errc::invalid_argument,
 788           "unknown augmentation character in entry at 0x%" PRIx64, StartOffset);
 789     case 'L':
 790       LSDAPointerEncoding = Data.getU8(&Offset);
 791       break;
 792     case 'P': {
 793       uint32_t PersonalityEncoding = Data.getU8(&Offset);
 794       std::optional<uint64_t> Personality =
 795           Data.getEncodedPointer(&Offset, PersonalityEncoding,
 796                                  EHFrameAddress ? EHFrameAddress + Offset : 0);
 797       // Patch personality address
 798       if (Personality)
 799         PatcherCallback(*Personality, Offset, PersonalityEncoding);
 800       break;
 801     }
 802     case 'R':
 803       FDEPointerEncoding = Data.getU8(&Offset);
 804       break;
 805     case 'z':
 806       if (i)
 807         return createStringError(
 808             errc::invalid_argument,
 809             "'z' must be the first character at 0x%" PRIx64, StartOffset);
 810       // Skip augmentation length
 811       Data.getULEB128(&Offset);
 812       break;
 813     case 'S':
 814     case 'B':
 815       break;
 816     }
 817   }
 818   Entries.emplace_back(std::make_unique<CIEInfo>(
 819       FDEPointerEncoding, LSDAPointerEncoding, AugmentationString));
 820   CIEs[StartOffset] = &*Entries.back();
 821   return Error::success();
 822 }
 823
 824 Error EHFrameParser::parseFDE(uint64_t CIEPointer,
 825                               uint64_t StartStructureOffset) {
 826   std::optional<uint64_t> LSDAAddress;
 827   CIEInfo *Cie = CIEs[StartStructureOffset - CIEPointer];
 828
 829   // The address size is encoded in the CIE we reference.
 830   if (!Cie)
 831     return createStringError(errc::invalid_argument,
 832                              "parsing FDE data at 0x%" PRIx64
 833                              " failed due to missing CIE",
 834                              StartStructureOffset);
 835   // Patch initial location
 836   if (auto Val = Data.getEncodedPointer(&Offset, Cie->FDEPtrEncoding,
 837                                         EHFrameAddress + Offset)) {
 838     PatcherCallback(*Val, Offset, Cie->FDEPtrEncoding);
 839   }
 840   // Skip address range
 841   Data.getEncodedPointer(&Offset, Cie->FDEPtrEncoding, 0);
 842
 843   // Process augmentation data for this FDE.
 844   StringRef AugmentationString = Cie->AugmentationString;
 845   if (!AugmentationString.empty() && Cie->LSDAPtrEncoding != DW_EH_PE_omit) {
 846     // Skip augmentation length
 847     Data.getULEB128(&Offset);
 848     LSDAAddress =
 849         Data.getEncodedPointer(&Offset, Cie->LSDAPtrEncoding,
 850                                EHFrameAddress ? Offset + EHFrameAddress : 0);
 851     // Patch LSDA address
 852     PatcherCallback(*LSDAAddress, Offset, Cie->LSDAPtrEncoding);
 853   }
 854   return Error::success();
 855 }
 856
 857 Error EHFrameParser::parse() {
 858   while (Data.isValidOffset(Offset)) {
 859     const uint64_t StartOffset = Offset;
 860
 861     uint64_t Length;
 862     DwarfFormat Format;
 863     std::tie(Length, Format) = Data.getInitialLength(&Offset);
 864
 865     // If the Length is 0, then this CIE is a terminator
 866     if (Length == 0)
 867       break;
 868
 869     const uint64_t StartStructureOffset = Offset;
 870     const uint64_t EndStructureOffset = Offset + Length;
 871
 872     Error Err = Error::success();
 873     const uint64_t Id = Data.getRelocatedValue(4, &Offset,
 874                                                /*SectionIndex=*/nullptr, &Err);
 875     if (Err)
 876       return Err;
 877
 878     if (!Id) {
 879       if (Error Err = parseCIE(StartOffset))
 880         return Err;
 881     } else {
 882       if (Error Err = parseFDE(Id, StartStructureOffset))
 883         return Err;
 884     }
 885     Offset = EndStructureOffset;
 886   }
 887
 888   return Error::success();
 889 }
 890
 891 Error EHFrameParser::parse(DWARFDataExtractor Data, uint64_t EHFrameAddress,
 892                            PatcherCallbackTy PatcherCallback) {
 893   EHFrameParser Parser(Data, EHFrameAddress, PatcherCallback);
 894   return Parser.parse();
 895 }
 896
 897 } // namespace bolt
 898 } // namespace llvm