1 //===-- DWARFDebugFrame.h - Parsing of .debug_frame -------------*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #include "llvm/DebugInfo/DWARF/DWARFDebugFrame.h"
11 #include "llvm/ADT/ArrayRef.h"
12 #include "llvm/ADT/DenseMap.h"
13 #include "llvm/ADT/SmallString.h"
14 #include "llvm/Support/Casting.h"
15 #include "llvm/Support/DataTypes.h"
16 #include "llvm/Support/Dwarf.h"
17 #include "llvm/Support/ErrorHandling.h"
18 #include "llvm/Support/Format.h"
19 #include "llvm/Support/raw_ostream.h"
20 #include <string>
21 #include <vector>
22 
23 using namespace llvm;
24 using namespace dwarf;
25 
26 
27 /// \brief Abstract frame entry defining the common interface concrete
28 /// entries implement.
29 class llvm::FrameEntry {
30 public:
31   enum FrameKind {FK_CIE, FK_FDE};
32   FrameEntry(FrameKind K, uint64_t Offset, uint64_t Length)
33       : Kind(K), Offset(Offset), Length(Length) {}
34 
35   virtual ~FrameEntry() {
36   }
37 
38   FrameKind getKind() const { return Kind; }
39   virtual uint64_t getOffset() const { return Offset; }
40 
41   /// \brief Parse and store a sequence of CFI instructions from Data,
42   /// starting at *Offset and ending at EndOffset. If everything
43   /// goes well, *Offset should be equal to EndOffset when this method
44   /// returns. Otherwise, an error occurred.
45   virtual void parseInstructions(DataExtractor Data, uint32_t *Offset,
46                                  uint32_t EndOffset);
47 
48   /// \brief Dump the entry header to the given output stream.
49   virtual void dumpHeader(raw_ostream &OS) const = 0;
50 
51   /// \brief Dump the entry's instructions to the given output stream.
52   virtual void dumpInstructions(raw_ostream &OS) const;
53 
54 protected:
55   const FrameKind Kind;
56 
57   /// \brief Offset of this entry in the section.
58   uint64_t Offset;
59 
60   /// \brief Entry length as specified in DWARF.
61   uint64_t Length;
62 
63   /// An entry may contain CFI instructions. An instruction consists of an
64   /// opcode and an optional sequence of operands.
65   typedef std::vector<uint64_t> Operands;
66   struct Instruction {
67     Instruction(uint8_t Opcode)
68       : Opcode(Opcode)
69     {}
70 
71     uint8_t Opcode;
72     Operands Ops;
73   };
74 
75   std::vector<Instruction> Instructions;
76 
77   /// Convenience methods to add a new instruction with the given opcode and
78   /// operands to the Instructions vector.
79   void addInstruction(uint8_t Opcode) {
80     Instructions.push_back(Instruction(Opcode));
81   }
82 
83   void addInstruction(uint8_t Opcode, uint64_t Operand1) {
84     Instructions.push_back(Instruction(Opcode));
85     Instructions.back().Ops.push_back(Operand1);
86   }
87 
88   void addInstruction(uint8_t Opcode, uint64_t Operand1, uint64_t Operand2) {
89     Instructions.push_back(Instruction(Opcode));
90     Instructions.back().Ops.push_back(Operand1);
91     Instructions.back().Ops.push_back(Operand2);
92   }
93 };
94 
95 
96 // See DWARF standard v3, section 7.23
97 const uint8_t DWARF_CFI_PRIMARY_OPCODE_MASK = 0xc0;
98 const uint8_t DWARF_CFI_PRIMARY_OPERAND_MASK = 0x3f;
99 
100 void FrameEntry::parseInstructions(DataExtractor Data, uint32_t *Offset,
101                                    uint32_t EndOffset) {
102   while (*Offset < EndOffset) {
103     uint8_t Opcode = Data.getU8(Offset);
104     // Some instructions have a primary opcode encoded in the top bits.
105     uint8_t Primary = Opcode & DWARF_CFI_PRIMARY_OPCODE_MASK;
106 
107     if (Primary) {
108       // If it's a primary opcode, the first operand is encoded in the bottom
109       // bits of the opcode itself.
110       uint64_t Op1 = Opcode & DWARF_CFI_PRIMARY_OPERAND_MASK;
111       switch (Primary) {
112         default: llvm_unreachable("Impossible primary CFI opcode");
113         case DW_CFA_advance_loc:
114         case DW_CFA_restore:
115           addInstruction(Primary, Op1);
116           break;
117         case DW_CFA_offset:
118           addInstruction(Primary, Op1, Data.getULEB128(Offset));
119           break;
120       }
121     } else {
122       // Extended opcode - its value is Opcode itself.
123       switch (Opcode) {
124         default: llvm_unreachable("Invalid extended CFI opcode");
125         case DW_CFA_nop:
126         case DW_CFA_remember_state:
127         case DW_CFA_restore_state:
128         case DW_CFA_GNU_window_save:
129           // No operands
130           addInstruction(Opcode);
131           break;
132         case DW_CFA_set_loc:
133           // Operands: Address
134           addInstruction(Opcode, Data.getAddress(Offset));
135           break;
136         case DW_CFA_advance_loc1:
137           // Operands: 1-byte delta
138           addInstruction(Opcode, Data.getU8(Offset));
139           break;
140         case DW_CFA_advance_loc2:
141           // Operands: 2-byte delta
142           addInstruction(Opcode, Data.getU16(Offset));
143           break;
144         case DW_CFA_advance_loc4:
145           // Operands: 4-byte delta
146           addInstruction(Opcode, Data.getU32(Offset));
147           break;
148         case DW_CFA_restore_extended:
149         case DW_CFA_undefined:
150         case DW_CFA_same_value:
151         case DW_CFA_def_cfa_register:
152         case DW_CFA_def_cfa_offset:
153           // Operands: ULEB128
154           addInstruction(Opcode, Data.getULEB128(Offset));
155           break;
156         case DW_CFA_def_cfa_offset_sf:
157           // Operands: SLEB128
158           addInstruction(Opcode, Data.getSLEB128(Offset));
159           break;
160         case DW_CFA_offset_extended:
161         case DW_CFA_register:
162         case DW_CFA_def_cfa:
163         case DW_CFA_val_offset:
164           // Operands: ULEB128, ULEB128
165           addInstruction(Opcode, Data.getULEB128(Offset),
166                                  Data.getULEB128(Offset));
167           break;
168         case DW_CFA_offset_extended_sf:
169         case DW_CFA_def_cfa_sf:
170         case DW_CFA_val_offset_sf:
171           // Operands: ULEB128, SLEB128
172           addInstruction(Opcode, Data.getULEB128(Offset),
173                                  Data.getSLEB128(Offset));
174           break;
175         case DW_CFA_def_cfa_expression:
176         case DW_CFA_expression:
177         case DW_CFA_val_expression:
178           // TODO: implement this
179           report_fatal_error("Values with expressions not implemented yet!");
180       }
181     }
182   }
183 }
184 
185 namespace {
186 /// \brief DWARF Common Information Entry (CIE)
187 class CIE : public FrameEntry {
188 public:
189   // CIEs (and FDEs) are simply container classes, so the only sensible way to
190   // create them is by providing the full parsed contents in the constructor.
191   CIE(uint64_t Offset, uint64_t Length, uint8_t Version,
192       SmallString<8> Augmentation, uint64_t CodeAlignmentFactor,
193       int64_t DataAlignmentFactor, uint64_t ReturnAddressRegister)
194       : FrameEntry(FK_CIE, Offset, Length), Version(Version),
195         Augmentation(std::move(Augmentation)),
196         CodeAlignmentFactor(CodeAlignmentFactor),
197         DataAlignmentFactor(DataAlignmentFactor),
198         ReturnAddressRegister(ReturnAddressRegister) {}
199 
200   ~CIE() {
201   }
202 
203   uint64_t getCodeAlignmentFactor() const { return CodeAlignmentFactor; }
204   int64_t getDataAlignmentFactor() const { return DataAlignmentFactor; }
205 
206   void dumpHeader(raw_ostream &OS) const override {
207     OS << format("%08x %08x %08x CIE",
208                  (uint32_t)Offset, (uint32_t)Length, DW_CIE_ID)
209        << "\n";
210     OS << format("  Version:               %d\n", Version);
211     OS << "  Augmentation:          \"" << Augmentation << "\"\n";
212     OS << format("  Code alignment factor: %u\n",
213                  (uint32_t)CodeAlignmentFactor);
214     OS << format("  Data alignment factor: %d\n",
215                  (int32_t)DataAlignmentFactor);
216     OS << format("  Return address column: %d\n",
217                  (int32_t)ReturnAddressRegister);
218     OS << "\n";
219   }
220 
221   static bool classof(const FrameEntry *FE) {
222     return FE->getKind() == FK_CIE;
223   }
224 
225 private:
226   /// The following fields are defined in section 6.4.1 of the DWARF standard v3
227   uint8_t Version;
228   SmallString<8> Augmentation;
229   uint64_t CodeAlignmentFactor;
230   int64_t DataAlignmentFactor;
231   uint64_t ReturnAddressRegister;
232 };
233 
234 
235 /// \brief DWARF Frame Description Entry (FDE)
236 class FDE : public FrameEntry {
237 public:
238   // Each FDE has a CIE it's "linked to". Our FDE contains is constructed with
239   // an offset to the CIE (provided by parsing the FDE header). The CIE itself
240   // is obtained lazily once it's actually required.
241   FDE(uint64_t Offset, uint64_t Length, int64_t LinkedCIEOffset,
242       uint64_t InitialLocation, uint64_t AddressRange,
243       CIE *Cie)
244       : FrameEntry(FK_FDE, Offset, Length), LinkedCIEOffset(LinkedCIEOffset),
245         InitialLocation(InitialLocation), AddressRange(AddressRange),
246         LinkedCIE(Cie) {}
247 
248   ~FDE() {
249   }
250 
251   CIE *getLinkedCIE() const { return LinkedCIE; }
252 
253   void dumpHeader(raw_ostream &OS) const override {
254     OS << format("%08x %08x %08x FDE ",
255                  (uint32_t)Offset, (uint32_t)Length, (int32_t)LinkedCIEOffset);
256     OS << format("cie=%08x pc=%08x...%08x\n",
257                  (int32_t)LinkedCIEOffset,
258                  (uint32_t)InitialLocation,
259                  (uint32_t)InitialLocation + (uint32_t)AddressRange);
260   }
261 
262   static bool classof(const FrameEntry *FE) {
263     return FE->getKind() == FK_FDE;
264   }
265 
266 private:
267   /// The following fields are defined in section 6.4.1 of the DWARF standard v3
268   uint64_t LinkedCIEOffset;
269   uint64_t InitialLocation;
270   uint64_t AddressRange;
271   CIE *LinkedCIE;
272 };
273 
274 /// \brief Types of operands to CF instructions.
275 enum OperandType {
276   OT_Unset,
277   OT_None,
278   OT_Address,
279   OT_Offset,
280   OT_FactoredCodeOffset,
281   OT_SignedFactDataOffset,
282   OT_UnsignedFactDataOffset,
283   OT_Register,
284   OT_Expression
285 };
286 
287 } // end anonymous namespace
288 
289 /// \brief Initialize the array describing the types of operands.
290 static ArrayRef<OperandType[2]> getOperandTypes() {
291   static OperandType OpTypes[DW_CFA_restore+1][2];
292 
293 #define DECLARE_OP2(OP, OPTYPE0, OPTYPE1)       \
294   do {                                          \
295     OpTypes[OP][0] = OPTYPE0;                   \
296     OpTypes[OP][1] = OPTYPE1;                   \
297   } while (0)
298 #define DECLARE_OP1(OP, OPTYPE0) DECLARE_OP2(OP, OPTYPE0, OT_None)
299 #define DECLARE_OP0(OP) DECLARE_OP1(OP, OT_None)
300 
301   DECLARE_OP1(DW_CFA_set_loc, OT_Address);
302   DECLARE_OP1(DW_CFA_advance_loc, OT_FactoredCodeOffset);
303   DECLARE_OP1(DW_CFA_advance_loc1, OT_FactoredCodeOffset);
304   DECLARE_OP1(DW_CFA_advance_loc2, OT_FactoredCodeOffset);
305   DECLARE_OP1(DW_CFA_advance_loc4, OT_FactoredCodeOffset);
306   DECLARE_OP1(DW_CFA_MIPS_advance_loc8, OT_FactoredCodeOffset);
307   DECLARE_OP2(DW_CFA_def_cfa, OT_Register, OT_Offset);
308   DECLARE_OP2(DW_CFA_def_cfa_sf, OT_Register, OT_SignedFactDataOffset);
309   DECLARE_OP1(DW_CFA_def_cfa_register, OT_Register);
310   DECLARE_OP1(DW_CFA_def_cfa_offset, OT_Offset);
311   DECLARE_OP1(DW_CFA_def_cfa_offset_sf, OT_SignedFactDataOffset);
312   DECLARE_OP1(DW_CFA_def_cfa_expression, OT_Expression);
313   DECLARE_OP1(DW_CFA_undefined, OT_Register);
314   DECLARE_OP1(DW_CFA_same_value, OT_Register);
315   DECLARE_OP2(DW_CFA_offset, OT_Register, OT_UnsignedFactDataOffset);
316   DECLARE_OP2(DW_CFA_offset_extended, OT_Register, OT_UnsignedFactDataOffset);
317   DECLARE_OP2(DW_CFA_offset_extended_sf, OT_Register, OT_SignedFactDataOffset);
318   DECLARE_OP2(DW_CFA_val_offset, OT_Register, OT_UnsignedFactDataOffset);
319   DECLARE_OP2(DW_CFA_val_offset_sf, OT_Register, OT_SignedFactDataOffset);
320   DECLARE_OP2(DW_CFA_register, OT_Register, OT_Register);
321   DECLARE_OP2(DW_CFA_expression, OT_Register, OT_Expression);
322   DECLARE_OP2(DW_CFA_val_expression, OT_Register, OT_Expression);
323   DECLARE_OP1(DW_CFA_restore, OT_Register);
324   DECLARE_OP1(DW_CFA_restore_extended, OT_Register);
325   DECLARE_OP0(DW_CFA_remember_state);
326   DECLARE_OP0(DW_CFA_restore_state);
327   DECLARE_OP0(DW_CFA_GNU_window_save);
328   DECLARE_OP1(DW_CFA_GNU_args_size, OT_Offset);
329   DECLARE_OP0(DW_CFA_nop);
330 
331 #undef DECLARE_OP0
332 #undef DECLARE_OP1
333 #undef DECLARE_OP2
334   return ArrayRef<OperandType[2]>(&OpTypes[0], DW_CFA_restore+1);
335 }
336 
337 static ArrayRef<OperandType[2]> OpTypes = getOperandTypes();
338 
339 /// \brief Print \p Opcode's operand number \p OperandIdx which has
340 /// value \p Operand.
341 static void printOperand(raw_ostream &OS, uint8_t Opcode, unsigned OperandIdx,
342                          uint64_t Operand, uint64_t CodeAlignmentFactor,
343                          int64_t DataAlignmentFactor) {
344   assert(OperandIdx < 2);
345   OperandType Type = OpTypes[Opcode][OperandIdx];
346 
347   switch (Type) {
348   case OT_Unset:
349     OS << " Unsupported " << (OperandIdx ? "second" : "first") << " operand to";
350     if (const char *OpcodeName = CallFrameString(Opcode))
351       OS << " " << OpcodeName;
352     else
353       OS << format(" Opcode %x",  Opcode);
354     break;
355   case OT_None:
356     break;
357   case OT_Address:
358     OS << format(" %" PRIx64, Operand);
359     break;
360   case OT_Offset:
361     // The offsets are all encoded in a unsigned form, but in practice
362     // consumers use them signed. It's most certainly legacy due to
363     // the lack of signed variants in the first Dwarf standards.
364     OS << format(" %+" PRId64, int64_t(Operand));
365     break;
366   case OT_FactoredCodeOffset: // Always Unsigned
367     if (CodeAlignmentFactor)
368       OS << format(" %" PRId64, Operand * CodeAlignmentFactor);
369     else
370       OS << format(" %" PRId64 "*code_alignment_factor" , Operand);
371     break;
372   case OT_SignedFactDataOffset:
373     if (DataAlignmentFactor)
374       OS << format(" %" PRId64, int64_t(Operand) * DataAlignmentFactor);
375     else
376       OS << format(" %" PRId64 "*data_alignment_factor" , int64_t(Operand));
377     break;
378   case OT_UnsignedFactDataOffset:
379     if (DataAlignmentFactor)
380       OS << format(" %" PRId64, Operand * DataAlignmentFactor);
381     else
382       OS << format(" %" PRId64 "*data_alignment_factor" , Operand);
383     break;
384   case OT_Register:
385     OS << format(" reg%" PRId64, Operand);
386     break;
387   case OT_Expression:
388     OS << " expression";
389     break;
390   }
391 }
392 
393 void FrameEntry::dumpInstructions(raw_ostream &OS) const {
394   uint64_t CodeAlignmentFactor = 0;
395   int64_t DataAlignmentFactor = 0;
396   const CIE *Cie = dyn_cast<CIE>(this);
397 
398   if (!Cie)
399     Cie = cast<FDE>(this)->getLinkedCIE();
400   if (Cie) {
401     CodeAlignmentFactor = Cie->getCodeAlignmentFactor();
402     DataAlignmentFactor = Cie->getDataAlignmentFactor();
403   }
404 
405   for (const auto &Instr : Instructions) {
406     uint8_t Opcode = Instr.Opcode;
407     if (Opcode & DWARF_CFI_PRIMARY_OPCODE_MASK)
408       Opcode &= DWARF_CFI_PRIMARY_OPCODE_MASK;
409     OS << "  " << CallFrameString(Opcode) << ":";
410     for (unsigned i = 0; i < Instr.Ops.size(); ++i)
411       printOperand(OS, Opcode, i, Instr.Ops[i], CodeAlignmentFactor,
412                    DataAlignmentFactor);
413     OS << '\n';
414   }
415 }
416 
417 DWARFDebugFrame::DWARFDebugFrame() {
418 }
419 
420 DWARFDebugFrame::~DWARFDebugFrame() {
421 }
422 
423 static void LLVM_ATTRIBUTE_UNUSED dumpDataAux(DataExtractor Data,
424                                               uint32_t Offset, int Length) {
425   errs() << "DUMP: ";
426   for (int i = 0; i < Length; ++i) {
427     uint8_t c = Data.getU8(&Offset);
428     errs().write_hex(c); errs() << " ";
429   }
430   errs() << "\n";
431 }
432 
433 
434 void DWARFDebugFrame::parse(DataExtractor Data) {
435   uint32_t Offset = 0;
436   DenseMap<uint32_t, CIE *> CIEs;
437 
438   while (Data.isValidOffset(Offset)) {
439     uint32_t StartOffset = Offset;
440 
441     bool IsDWARF64 = false;
442     uint64_t Length = Data.getU32(&Offset);
443     uint64_t Id;
444 
445     if (Length == UINT32_MAX) {
446       // DWARF-64 is distinguished by the first 32 bits of the initial length
447       // field being 0xffffffff. Then, the next 64 bits are the actual entry
448       // length.
449       IsDWARF64 = true;
450       Length = Data.getU64(&Offset);
451     }
452 
453     // At this point, Offset points to the next field after Length.
454     // Length is the structure size excluding itself. Compute an offset one
455     // past the end of the structure (needed to know how many instructions to
456     // read).
457     // TODO: For honest DWARF64 support, DataExtractor will have to treat
458     //       offset_ptr as uint64_t*
459     uint32_t EndStructureOffset = Offset + static_cast<uint32_t>(Length);
460 
461     // The Id field's size depends on the DWARF format
462     Id = Data.getUnsigned(&Offset, IsDWARF64 ? 8 : 4);
463     bool IsCIE = ((IsDWARF64 && Id == DW64_CIE_ID) || Id == DW_CIE_ID);
464 
465     if (IsCIE) {
466       // Note: this is specifically DWARFv3 CIE header structure. It was
467       // changed in DWARFv4. We currently don't support reading DWARFv4
468       // here because LLVM itself does not emit it (and LLDB doesn't
469       // support it either).
470       uint8_t Version = Data.getU8(&Offset);
471       const char *Augmentation = Data.getCStr(&Offset);
472       uint64_t CodeAlignmentFactor = Data.getULEB128(&Offset);
473       int64_t DataAlignmentFactor = Data.getSLEB128(&Offset);
474       uint64_t ReturnAddressRegister = Data.getULEB128(&Offset);
475 
476       auto Cie = make_unique<CIE>(StartOffset, Length, Version,
477                                   StringRef(Augmentation), CodeAlignmentFactor,
478                                   DataAlignmentFactor, ReturnAddressRegister);
479       CIEs[StartOffset] = Cie.get();
480       Entries.emplace_back(std::move(Cie));
481     } else {
482       // FDE
483       uint64_t CIEPointer = Id;
484       uint64_t InitialLocation = Data.getAddress(&Offset);
485       uint64_t AddressRange = Data.getAddress(&Offset);
486 
487       Entries.emplace_back(new FDE(StartOffset, Length, CIEPointer,
488                                    InitialLocation, AddressRange,
489                                    CIEs[CIEPointer]));
490     }
491 
492     Entries.back()->parseInstructions(Data, &Offset, EndStructureOffset);
493 
494     if (Offset != EndStructureOffset) {
495       std::string Str;
496       raw_string_ostream OS(Str);
497       OS << format("Parsing entry instructions at %lx failed", StartOffset);
498       report_fatal_error(Str);
499     }
500   }
501 }
502 
503 
504 void DWARFDebugFrame::dump(raw_ostream &OS) const {
505   OS << "\n";
506   for (const auto &Entry : Entries) {
507     Entry->dumpHeader(OS);
508     Entry->dumpInstructions(OS);
509     OS << "\n";
510   }
511 }
512 
513