1//===- DWARFDebugFrame.h - Parsing of .debug_frame ------------------------===//
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#include "llvm/DebugInfo/DWARF/DWARFDebugFrame.h"
10#include "llvm/ADT/DenseMap.h"
11#include "llvm/ADT/Optional.h"
12#include "llvm/ADT/StringExtras.h"
13#include "llvm/ADT/StringRef.h"
14#include "llvm/BinaryFormat/Dwarf.h"
15#include "llvm/Support/Casting.h"
16#include "llvm/Support/Compiler.h"
17#include "llvm/Support/DataExtractor.h"
18#include "llvm/Support/Errc.h"
19#include "llvm/Support/ErrorHandling.h"
20#include "llvm/Support/Format.h"
21#include "llvm/Support/raw_ostream.h"
22#include <algorithm>
23#include <cassert>
24#include <cinttypes>
25#include <cstdint>
26#include <string>
27#include <vector>
28
29using namespace llvm;
30using namespace dwarf;
31
32
33// See DWARF standard v3, section 7.23
34const uint8_t DWARF_CFI_PRIMARY_OPCODE_MASK = 0xc0;
35const uint8_t DWARF_CFI_PRIMARY_OPERAND_MASK = 0x3f;
36
37Error CFIProgram::parse(DWARFDataExtractor Data, uint64_t *Offset,
38                        uint64_t EndOffset) {
39  while (*Offset < EndOffset) {
40    uint8_t Opcode = Data.getRelocatedValue(1, Offset);
41    // Some instructions have a primary opcode encoded in the top bits.
42    uint8_t Primary = Opcode & DWARF_CFI_PRIMARY_OPCODE_MASK;
43
44    if (Primary) {
45      // If it's a primary opcode, the first operand is encoded in the bottom
46      // bits of the opcode itself.
47      uint64_t Op1 = Opcode & DWARF_CFI_PRIMARY_OPERAND_MASK;
48      switch (Primary) {
49      default:
50        return createStringError(errc::illegal_byte_sequence,
51                                 "Invalid primary CFI opcode 0x%" PRIx8,
52                                 Primary);
53      case DW_CFA_advance_loc:
54      case DW_CFA_restore:
55        addInstruction(Primary, Op1);
56        break;
57      case DW_CFA_offset:
58        addInstruction(Primary, Op1, Data.getULEB128(Offset));
59        break;
60      }
61    } else {
62      // Extended opcode - its value is Opcode itself.
63      switch (Opcode) {
64      default:
65        return createStringError(errc::illegal_byte_sequence,
66                                 "Invalid extended CFI opcode 0x%" PRIx8,
67                                 Opcode);
68      case DW_CFA_nop:
69      case DW_CFA_remember_state:
70      case DW_CFA_restore_state:
71      case DW_CFA_GNU_window_save:
72        // No operands
73        addInstruction(Opcode);
74        break;
75      case DW_CFA_set_loc:
76        // Operands: Address
77        addInstruction(Opcode, Data.getRelocatedAddress(Offset));
78        break;
79      case DW_CFA_advance_loc1:
80        // Operands: 1-byte delta
81        addInstruction(Opcode, Data.getRelocatedValue(1, Offset));
82        break;
83      case DW_CFA_advance_loc2:
84        // Operands: 2-byte delta
85        addInstruction(Opcode, Data.getRelocatedValue(2, Offset));
86        break;
87      case DW_CFA_advance_loc4:
88        // Operands: 4-byte delta
89        addInstruction(Opcode, Data.getRelocatedValue(4, Offset));
90        break;
91      case DW_CFA_restore_extended:
92      case DW_CFA_undefined:
93      case DW_CFA_same_value:
94      case DW_CFA_def_cfa_register:
95      case DW_CFA_def_cfa_offset:
96      case DW_CFA_GNU_args_size:
97        // Operands: ULEB128
98        addInstruction(Opcode, Data.getULEB128(Offset));
99        break;
100      case DW_CFA_def_cfa_offset_sf:
101        // Operands: SLEB128
102        addInstruction(Opcode, Data.getSLEB128(Offset));
103        break;
104      case DW_CFA_offset_extended:
105      case DW_CFA_register:
106      case DW_CFA_def_cfa:
107      case DW_CFA_val_offset: {
108        // Operands: ULEB128, ULEB128
109        // Note: We can not embed getULEB128 directly into function
110        // argument list. getULEB128 changes Offset and order of evaluation
111        // for arguments is unspecified.
112        auto op1 = Data.getULEB128(Offset);
113        auto op2 = Data.getULEB128(Offset);
114        addInstruction(Opcode, op1, op2);
115        break;
116        }
117        case DW_CFA_offset_extended_sf:
118        case DW_CFA_def_cfa_sf:
119        case DW_CFA_val_offset_sf: {
120          // Operands: ULEB128, SLEB128
121          // Note: see comment for the previous case
122          auto op1 = Data.getULEB128(Offset);
123          auto op2 = (uint64_t)Data.getSLEB128(Offset);
124          addInstruction(Opcode, op1, op2);
125          break;
126        }
127        case DW_CFA_def_cfa_expression: {
128          uint32_t ExprLength = Data.getULEB128(Offset);
129          addInstruction(Opcode, 0);
130          DataExtractor Extractor(
131              Data.getData().slice(*Offset, *Offset + ExprLength),
132              Data.isLittleEndian(), Data.getAddressSize());
133          Instructions.back().Expression = DWARFExpression(
134              Extractor, Data.getAddressSize(), dwarf::DWARF_VERSION);
135          *Offset += ExprLength;
136          break;
137        }
138        case DW_CFA_expression:
139        case DW_CFA_val_expression: {
140          auto RegNum = Data.getULEB128(Offset);
141          auto BlockLength = Data.getULEB128(Offset);
142          addInstruction(Opcode, RegNum, 0);
143          DataExtractor Extractor(
144              Data.getData().slice(*Offset, *Offset + BlockLength),
145              Data.isLittleEndian(), Data.getAddressSize());
146          Instructions.back().Expression = DWARFExpression(
147              Extractor, Data.getAddressSize(), dwarf::DWARF_VERSION);
148          *Offset += BlockLength;
149          break;
150        }
151      }
152    }
153  }
154
155  return Error::success();
156}
157
158namespace {
159
160
161} // end anonymous namespace
162
163ArrayRef<CFIProgram::OperandType[2]> CFIProgram::getOperandTypes() {
164  static OperandType OpTypes[DW_CFA_restore+1][2];
165  static bool Initialized = false;
166  if (Initialized) {
167    return ArrayRef<OperandType[2]>(&OpTypes[0], DW_CFA_restore+1);
168  }
169  Initialized = true;
170
171#define DECLARE_OP2(OP, OPTYPE0, OPTYPE1)       \
172  do {                                          \
173    OpTypes[OP][0] = OPTYPE0;                   \
174    OpTypes[OP][1] = OPTYPE1;                   \
175  } while (false)
176#define DECLARE_OP1(OP, OPTYPE0) DECLARE_OP2(OP, OPTYPE0, OT_None)
177#define DECLARE_OP0(OP) DECLARE_OP1(OP, OT_None)
178
179  DECLARE_OP1(DW_CFA_set_loc, OT_Address);
180  DECLARE_OP1(DW_CFA_advance_loc, OT_FactoredCodeOffset);
181  DECLARE_OP1(DW_CFA_advance_loc1, OT_FactoredCodeOffset);
182  DECLARE_OP1(DW_CFA_advance_loc2, OT_FactoredCodeOffset);
183  DECLARE_OP1(DW_CFA_advance_loc4, OT_FactoredCodeOffset);
184  DECLARE_OP1(DW_CFA_MIPS_advance_loc8, OT_FactoredCodeOffset);
185  DECLARE_OP2(DW_CFA_def_cfa, OT_Register, OT_Offset);
186  DECLARE_OP2(DW_CFA_def_cfa_sf, OT_Register, OT_SignedFactDataOffset);
187  DECLARE_OP1(DW_CFA_def_cfa_register, OT_Register);
188  DECLARE_OP1(DW_CFA_def_cfa_offset, OT_Offset);
189  DECLARE_OP1(DW_CFA_def_cfa_offset_sf, OT_SignedFactDataOffset);
190  DECLARE_OP1(DW_CFA_def_cfa_expression, OT_Expression);
191  DECLARE_OP1(DW_CFA_undefined, OT_Register);
192  DECLARE_OP1(DW_CFA_same_value, OT_Register);
193  DECLARE_OP2(DW_CFA_offset, OT_Register, OT_UnsignedFactDataOffset);
194  DECLARE_OP2(DW_CFA_offset_extended, OT_Register, OT_UnsignedFactDataOffset);
195  DECLARE_OP2(DW_CFA_offset_extended_sf, OT_Register, OT_SignedFactDataOffset);
196  DECLARE_OP2(DW_CFA_val_offset, OT_Register, OT_UnsignedFactDataOffset);
197  DECLARE_OP2(DW_CFA_val_offset_sf, OT_Register, OT_SignedFactDataOffset);
198  DECLARE_OP2(DW_CFA_register, OT_Register, OT_Register);
199  DECLARE_OP2(DW_CFA_expression, OT_Register, OT_Expression);
200  DECLARE_OP2(DW_CFA_val_expression, OT_Register, OT_Expression);
201  DECLARE_OP1(DW_CFA_restore, OT_Register);
202  DECLARE_OP1(DW_CFA_restore_extended, OT_Register);
203  DECLARE_OP0(DW_CFA_remember_state);
204  DECLARE_OP0(DW_CFA_restore_state);
205  DECLARE_OP0(DW_CFA_GNU_window_save);
206  DECLARE_OP1(DW_CFA_GNU_args_size, OT_Offset);
207  DECLARE_OP0(DW_CFA_nop);
208
209#undef DECLARE_OP0
210#undef DECLARE_OP1
211#undef DECLARE_OP2
212
213  return ArrayRef<OperandType[2]>(&OpTypes[0], DW_CFA_restore+1);
214}
215
216/// Print \p Opcode's operand number \p OperandIdx which has value \p Operand.
217void CFIProgram::printOperand(raw_ostream &OS, const MCRegisterInfo *MRI,
218                              bool IsEH, const Instruction &Instr,
219                              unsigned OperandIdx, uint64_t Operand) const {
220  assert(OperandIdx < 2);
221  uint8_t Opcode = Instr.Opcode;
222  OperandType Type = getOperandTypes()[Opcode][OperandIdx];
223
224  switch (Type) {
225  case OT_Unset: {
226    OS << " Unsupported " << (OperandIdx ? "second" : "first") << " operand to";
227    auto OpcodeName = CallFrameString(Opcode, Arch);
228    if (!OpcodeName.empty())
229      OS << " " << OpcodeName;
230    else
231      OS << format(" Opcode %x",  Opcode);
232    break;
233  }
234  case OT_None:
235    break;
236  case OT_Address:
237    OS << format(" %" PRIx64, Operand);
238    break;
239  case OT_Offset:
240    // The offsets are all encoded in a unsigned form, but in practice
241    // consumers use them signed. It's most certainly legacy due to
242    // the lack of signed variants in the first Dwarf standards.
243    OS << format(" %+" PRId64, int64_t(Operand));
244    break;
245  case OT_FactoredCodeOffset: // Always Unsigned
246    if (CodeAlignmentFactor)
247      OS << format(" %" PRId64, Operand * CodeAlignmentFactor);
248    else
249      OS << format(" %" PRId64 "*code_alignment_factor" , Operand);
250    break;
251  case OT_SignedFactDataOffset:
252    if (DataAlignmentFactor)
253      OS << format(" %" PRId64, int64_t(Operand) * DataAlignmentFactor);
254    else
255      OS << format(" %" PRId64 "*data_alignment_factor" , int64_t(Operand));
256    break;
257  case OT_UnsignedFactDataOffset:
258    if (DataAlignmentFactor)
259      OS << format(" %" PRId64, Operand * DataAlignmentFactor);
260    else
261      OS << format(" %" PRId64 "*data_alignment_factor" , Operand);
262    break;
263  case OT_Register:
264    OS << format(" reg%" PRId64, Operand);
265    break;
266  case OT_Expression:
267    assert(Instr.Expression && "missing DWARFExpression object");
268    OS << " ";
269    Instr.Expression->print(OS, MRI, nullptr, IsEH);
270    break;
271  }
272}
273
274void CFIProgram::dump(raw_ostream &OS, const MCRegisterInfo *MRI, bool IsEH,
275                      unsigned IndentLevel) const {
276  for (const auto &Instr : Instructions) {
277    uint8_t Opcode = Instr.Opcode;
278    if (Opcode & DWARF_CFI_PRIMARY_OPCODE_MASK)
279      Opcode &= DWARF_CFI_PRIMARY_OPCODE_MASK;
280    OS.indent(2 * IndentLevel);
281    OS << CallFrameString(Opcode, Arch) << ":";
282    for (unsigned i = 0; i < Instr.Ops.size(); ++i)
283      printOperand(OS, MRI, IsEH, Instr, i, Instr.Ops[i]);
284    OS << '\n';
285  }
286}
287
288void CIE::dump(raw_ostream &OS, const MCRegisterInfo *MRI, bool IsEH) const {
289  OS << format("%08x %08x %08x CIE", (uint32_t)Offset, (uint32_t)Length,
290               DW_CIE_ID)
291     << "\n";
292  OS << format("  Version:               %d\n", Version);
293  OS << "  Augmentation:          \"" << Augmentation << "\"\n";
294  if (Version >= 4) {
295    OS << format("  Address size:          %u\n", (uint32_t)AddressSize);
296    OS << format("  Segment desc size:     %u\n",
297                 (uint32_t)SegmentDescriptorSize);
298  }
299  OS << format("  Code alignment factor: %u\n", (uint32_t)CodeAlignmentFactor);
300  OS << format("  Data alignment factor: %d\n", (int32_t)DataAlignmentFactor);
301  OS << format("  Return address column: %d\n", (int32_t)ReturnAddressRegister);
302  if (Personality)
303    OS << format("  Personality Address: %016" PRIx64 "\n", *Personality);
304  if (!AugmentationData.empty()) {
305    OS << "  Augmentation data:    ";
306    for (uint8_t Byte : AugmentationData)
307      OS << ' ' << hexdigit(Byte >> 4) << hexdigit(Byte & 0xf);
308    OS << "\n";
309  }
310  OS << "\n";
311  CFIs.dump(OS, MRI, IsEH);
312  OS << "\n";
313}
314
315void FDE::dump(raw_ostream &OS, const MCRegisterInfo *MRI, bool IsEH) const {
316  OS << format("%08x %08x %08x FDE ", (uint32_t)Offset, (uint32_t)Length,
317               (int32_t)LinkedCIEOffset);
318  OS << format("cie=%08x pc=%08x...%08x\n", (int32_t)LinkedCIEOffset,
319               (uint32_t)InitialLocation,
320               (uint32_t)InitialLocation + (uint32_t)AddressRange);
321  if (LSDAAddress)
322    OS << format("  LSDA Address: %016" PRIx64 "\n", *LSDAAddress);
323  CFIs.dump(OS, MRI, IsEH);
324  OS << "\n";
325}
326
327DWARFDebugFrame::DWARFDebugFrame(Triple::ArchType Arch,
328    bool IsEH, uint64_t EHFrameAddress)
329    : Arch(Arch), IsEH(IsEH), EHFrameAddress(EHFrameAddress) {}
330
331DWARFDebugFrame::~DWARFDebugFrame() = default;
332
333static void LLVM_ATTRIBUTE_UNUSED dumpDataAux(DataExtractor Data,
334                                              uint64_t Offset, int Length) {
335  errs() << "DUMP: ";
336  for (int i = 0; i < Length; ++i) {
337    uint8_t c = Data.getU8(&Offset);
338    errs().write_hex(c); errs() << " ";
339  }
340  errs() << "\n";
341}
342
343// This is a workaround for old compilers which do not allow
344// noreturn attribute usage in lambdas. Once the support for those
345// compilers are phased out, we can remove this and return back to
346// a ReportError lambda: [StartOffset](const char *ErrorMsg).
347static void LLVM_ATTRIBUTE_NORETURN ReportError(uint64_t StartOffset,
348                                                const char *ErrorMsg) {
349  std::string Str;
350  raw_string_ostream OS(Str);
351  OS << format(ErrorMsg, StartOffset);
352  OS.flush();
353  report_fatal_error(Str);
354}
355
356void DWARFDebugFrame::parse(DWARFDataExtractor Data) {
357  uint64_t Offset = 0;
358  DenseMap<uint64_t, CIE *> CIEs;
359
360  while (Data.isValidOffset(Offset)) {
361    uint64_t StartOffset = Offset;
362
363    bool IsDWARF64 = false;
364    uint64_t Length = Data.getRelocatedValue(4, &Offset);
365    uint64_t Id;
366
367    if (Length == dwarf::DW_LENGTH_DWARF64) {
368      // DWARF-64 is distinguished by the first 32 bits of the initial length
369      // field being 0xffffffff. Then, the next 64 bits are the actual entry
370      // length.
371      IsDWARF64 = true;
372      Length = Data.getRelocatedValue(8, &Offset);
373    }
374
375    // At this point, Offset points to the next field after Length.
376    // Length is the structure size excluding itself. Compute an offset one
377    // past the end of the structure (needed to know how many instructions to
378    // read).
379    uint64_t StartStructureOffset = Offset;
380    uint64_t EndStructureOffset = Offset + Length;
381
382    // The Id field's size depends on the DWARF format
383    Id = Data.getUnsigned(&Offset, (IsDWARF64 && !IsEH) ? 8 : 4);
384    bool IsCIE =
385        ((IsDWARF64 && Id == DW64_CIE_ID) || Id == DW_CIE_ID || (IsEH && !Id));
386
387    if (IsCIE) {
388      uint8_t Version = Data.getU8(&Offset);
389      const char *Augmentation = Data.getCStr(&Offset);
390      StringRef AugmentationString(Augmentation ? Augmentation : "");
391      uint8_t AddressSize = Version < 4 ? Data.getAddressSize() :
392                                          Data.getU8(&Offset);
393      Data.setAddressSize(AddressSize);
394      uint8_t SegmentDescriptorSize = Version < 4 ? 0 : Data.getU8(&Offset);
395      uint64_t CodeAlignmentFactor = Data.getULEB128(&Offset);
396      int64_t DataAlignmentFactor = Data.getSLEB128(&Offset);
397      uint64_t ReturnAddressRegister =
398          Version == 1 ? Data.getU8(&Offset) : Data.getULEB128(&Offset);
399
400      // Parse the augmentation data for EH CIEs
401      StringRef AugmentationData("");
402      uint32_t FDEPointerEncoding = DW_EH_PE_absptr;
403      uint32_t LSDAPointerEncoding = DW_EH_PE_omit;
404      Optional<uint64_t> Personality;
405      Optional<uint32_t> PersonalityEncoding;
406      if (IsEH) {
407        Optional<uint64_t> AugmentationLength;
408        uint64_t StartAugmentationOffset;
409        uint64_t EndAugmentationOffset;
410
411        // Walk the augmentation string to get all the augmentation data.
412        for (unsigned i = 0, e = AugmentationString.size(); i != e; ++i) {
413          switch (AugmentationString[i]) {
414            default:
415              ReportError(
416                  StartOffset,
417                  "Unknown augmentation character in entry at %" PRIx64);
418            case 'L':
419              LSDAPointerEncoding = Data.getU8(&Offset);
420              break;
421            case 'P': {
422              if (Personality)
423                ReportError(StartOffset,
424                            "Duplicate personality in entry at %" PRIx64);
425              PersonalityEncoding = Data.getU8(&Offset);
426              Personality = Data.getEncodedPointer(
427                  &Offset, *PersonalityEncoding,
428                  EHFrameAddress ? EHFrameAddress + Offset : 0);
429              break;
430            }
431            case 'R':
432              FDEPointerEncoding = Data.getU8(&Offset);
433              break;
434            case 'S':
435              // Current frame is a signal trampoline.
436              break;
437            case 'z':
438              if (i)
439                ReportError(StartOffset,
440                            "'z' must be the first character at %" PRIx64);
441              // Parse the augmentation length first.  We only parse it if
442              // the string contains a 'z'.
443              AugmentationLength = Data.getULEB128(&Offset);
444              StartAugmentationOffset = Offset;
445              EndAugmentationOffset = Offset + *AugmentationLength;
446              break;
447            case 'B':
448              // B-Key is used for signing functions associated with this
449              // augmentation string
450              break;
451          }
452        }
453
454        if (AugmentationLength.hasValue()) {
455          if (Offset != EndAugmentationOffset)
456            ReportError(StartOffset,
457                        "Parsing augmentation data at %" PRIx64 " failed");
458
459          AugmentationData = Data.getData().slice(StartAugmentationOffset,
460                                                  EndAugmentationOffset);
461        }
462      }
463
464      auto Cie = std::make_unique<CIE>(
465          StartOffset, Length, Version, AugmentationString, AddressSize,
466          SegmentDescriptorSize, CodeAlignmentFactor, DataAlignmentFactor,
467          ReturnAddressRegister, AugmentationData, FDEPointerEncoding,
468          LSDAPointerEncoding, Personality, PersonalityEncoding, Arch);
469      CIEs[StartOffset] = Cie.get();
470      Entries.emplace_back(std::move(Cie));
471    } else {
472      // FDE
473      uint64_t CIEPointer = Id;
474      uint64_t InitialLocation = 0;
475      uint64_t AddressRange = 0;
476      Optional<uint64_t> LSDAAddress;
477      CIE *Cie = CIEs[IsEH ? (StartStructureOffset - CIEPointer) : CIEPointer];
478
479      if (IsEH) {
480        // The address size is encoded in the CIE we reference.
481        if (!Cie)
482          ReportError(StartOffset, "Parsing FDE data at %" PRIx64
483                                   " failed due to missing CIE");
484
485        if (auto Val = Data.getEncodedPointer(
486                &Offset, Cie->getFDEPointerEncoding(),
487                EHFrameAddress ? EHFrameAddress + Offset : 0)) {
488          InitialLocation = *Val;
489        }
490        if (auto Val = Data.getEncodedPointer(
491                &Offset, Cie->getFDEPointerEncoding(), 0)) {
492          AddressRange = *Val;
493        }
494
495        StringRef AugmentationString = Cie->getAugmentationString();
496        if (!AugmentationString.empty()) {
497          // Parse the augmentation length and data for this FDE.
498          uint64_t AugmentationLength = Data.getULEB128(&Offset);
499
500          uint64_t EndAugmentationOffset = Offset + AugmentationLength;
501
502          // Decode the LSDA if the CIE augmentation string said we should.
503          if (Cie->getLSDAPointerEncoding() != DW_EH_PE_omit) {
504            LSDAAddress = Data.getEncodedPointer(
505                &Offset, Cie->getLSDAPointerEncoding(),
506                EHFrameAddress ? Offset + EHFrameAddress : 0);
507          }
508
509          if (Offset != EndAugmentationOffset)
510            ReportError(StartOffset,
511                        "Parsing augmentation data at %" PRIx64 " failed");
512        }
513      } else {
514        InitialLocation = Data.getRelocatedAddress(&Offset);
515        AddressRange = Data.getRelocatedAddress(&Offset);
516      }
517
518      Entries.emplace_back(new FDE(StartOffset, Length, CIEPointer,
519                                   InitialLocation, AddressRange,
520                                   Cie, LSDAAddress, Arch));
521    }
522
523    if (Error E =
524            Entries.back()->cfis().parse(Data, &Offset, EndStructureOffset)) {
525      report_fatal_error(toString(std::move(E)));
526    }
527
528    if (Offset != EndStructureOffset)
529      ReportError(StartOffset,
530                  "Parsing entry instructions at %" PRIx64 " failed");
531  }
532}
533
534FrameEntry *DWARFDebugFrame::getEntryAtOffset(uint64_t Offset) const {
535  auto It = partition_point(Entries, [=](const std::unique_ptr<FrameEntry> &E) {
536    return E->getOffset() < Offset;
537  });
538  if (It != Entries.end() && (*It)->getOffset() == Offset)
539    return It->get();
540  return nullptr;
541}
542
543void DWARFDebugFrame::dump(raw_ostream &OS, const MCRegisterInfo *MRI,
544                           Optional<uint64_t> Offset) const {
545  if (Offset) {
546    if (auto *Entry = getEntryAtOffset(*Offset))
547      Entry->dump(OS, MRI, IsEH);
548    return;
549  }
550
551  OS << "\n";
552  for (const auto &Entry : Entries)
553    Entry->dump(OS, MRI, IsEH);
554}
555