1 //===- tools/dsymutil/DwarfLinker.h - Dwarf debug info linker ---*- 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 #ifndef LLVM_TOOLS_DSYMUTIL_DWARFLINKER_H 11 #define LLVM_TOOLS_DSYMUTIL_DWARFLINKER_H 12 13 #include "BinaryHolder.h" 14 #include "CompileUnit.h" 15 #include "DebugMap.h" 16 #include "DeclContext.h" 17 #include "DwarfStreamer.h" 18 #include "LinkUtils.h" 19 #include "llvm/DebugInfo/DWARF/DWARFContext.h" 20 21 namespace llvm { 22 namespace dsymutil { 23 24 /// Partial address range for debug map objects. Besides an offset, only the 25 /// HighPC is stored. The structure is stored in a map where the LowPC is the 26 /// key. 27 struct DebugMapObjectRange { 28 /// Function HighPC. 29 uint64_t HighPC; 30 /// Offset to apply to the linked address. 31 int64_t Offset; 32 33 DebugMapObjectRange(uint64_t EndPC, int64_t Offset) 34 : HighPC(EndPC), Offset(Offset) {} 35 36 DebugMapObjectRange() : HighPC(0), Offset(0) {} 37 }; 38 39 /// Map LowPC to DebugMapObjectRange. 40 using RangesTy = std::map<uint64_t, DebugMapObjectRange>; 41 using UnitListTy = std::vector<std::unique_ptr<CompileUnit>>; 42 43 /// The core of the Dwarf linking logic. 44 /// 45 /// The link of the dwarf information from the object files will be 46 /// driven by the selection of 'root DIEs', which are DIEs that 47 /// describe variables or functions that are present in the linked 48 /// binary (and thus have entries in the debug map). All the debug 49 /// information that will be linked (the DIEs, but also the line 50 /// tables, ranges, ...) is derived from that set of root DIEs. 51 /// 52 /// The root DIEs are identified because they contain relocations that 53 /// correspond to a debug map entry at specific places (the low_pc for 54 /// a function, the location for a variable). These relocations are 55 /// called ValidRelocs in the DwarfLinker and are gathered as a very 56 /// first step when we start processing a DebugMapObject. 57 class DwarfLinker { 58 public: 59 DwarfLinker(raw_fd_ostream &OutFile, BinaryHolder &BinHolder, 60 const LinkOptions &Options) 61 : OutFile(OutFile), BinHolder(BinHolder), Options(Options) {} 62 63 /// Link the contents of the DebugMap. 64 bool link(const DebugMap &); 65 66 void reportWarning(const Twine &Warning, const DebugMapObject &DMO, 67 const DWARFDie *DIE = nullptr) const; 68 69 private: 70 /// Remembers the oldest and newest DWARF version we've seen in a unit. 71 void updateDwarfVersion(unsigned Version) { 72 MaxDwarfVersion = std::max(MaxDwarfVersion, Version); 73 MinDwarfVersion = std::min(MinDwarfVersion, Version); 74 } 75 76 /// Remembers the kinds of accelerator tables we've seen in a unit. 77 void updateAccelKind(DWARFContext &Dwarf); 78 79 /// Emit warnings as Dwarf compile units to leave a trail after linking. 80 bool emitPaperTrailWarnings(const DebugMapObject &DMO, const DebugMap &Map, 81 OffsetsStringPool &StringPool); 82 83 /// Keeps track of relocations. 84 class RelocationManager { 85 struct ValidReloc { 86 uint32_t Offset; 87 uint32_t Size; 88 uint64_t Addend; 89 const DebugMapObject::DebugMapEntry *Mapping; 90 91 ValidReloc(uint32_t Offset, uint32_t Size, uint64_t Addend, 92 const DebugMapObject::DebugMapEntry *Mapping) 93 : Offset(Offset), Size(Size), Addend(Addend), Mapping(Mapping) {} 94 95 bool operator<(const ValidReloc &RHS) const { 96 return Offset < RHS.Offset; 97 } 98 }; 99 100 const DwarfLinker &Linker; 101 102 /// The valid relocations for the current DebugMapObject. 103 /// This vector is sorted by relocation offset. 104 std::vector<ValidReloc> ValidRelocs; 105 106 /// Index into ValidRelocs of the next relocation to consider. As we walk 107 /// the DIEs in acsending file offset and as ValidRelocs is sorted by file 108 /// offset, keeping this index up to date is all we have to do to have a 109 /// cheap lookup during the root DIE selection and during DIE cloning. 110 unsigned NextValidReloc = 0; 111 112 public: 113 RelocationManager(DwarfLinker &Linker) : Linker(Linker) {} 114 115 bool hasValidRelocs() const { return !ValidRelocs.empty(); } 116 117 /// Reset the NextValidReloc counter. 118 void resetValidRelocs() { NextValidReloc = 0; } 119 120 /// \defgroup FindValidRelocations Translate debug map into a list 121 /// of relevant relocations 122 /// 123 /// @{ 124 bool findValidRelocsInDebugInfo(const object::ObjectFile &Obj, 125 const DebugMapObject &DMO); 126 127 bool findValidRelocs(const object::SectionRef &Section, 128 const object::ObjectFile &Obj, 129 const DebugMapObject &DMO); 130 131 void findValidRelocsMachO(const object::SectionRef &Section, 132 const object::MachOObjectFile &Obj, 133 const DebugMapObject &DMO); 134 /// @} 135 136 bool hasValidRelocation(uint32_t StartOffset, uint32_t EndOffset, 137 CompileUnit::DIEInfo &Info); 138 139 bool applyValidRelocs(MutableArrayRef<char> Data, uint32_t BaseOffset, 140 bool isLittleEndian); 141 }; 142 143 /// Keeps track of data associated with one object during linking. 144 struct LinkContext { 145 DebugMapObject &DMO; 146 const object::ObjectFile *ObjectFile; 147 RelocationManager RelocMgr; 148 std::unique_ptr<DWARFContext> DwarfContext; 149 RangesTy Ranges; 150 UnitListTy CompileUnits; 151 152 LinkContext(const DebugMap &Map, DwarfLinker &Linker, DebugMapObject &DMO) 153 : DMO(DMO), RelocMgr(Linker) { 154 // Swift ASTs are not object files. 155 if (DMO.getType() == MachO::N_AST) { 156 ObjectFile = nullptr; 157 return; 158 } 159 auto ErrOrObj = Linker.loadObject(DMO, Map); 160 ObjectFile = ErrOrObj ? &*ErrOrObj : nullptr; 161 DwarfContext = ObjectFile ? DWARFContext::create(*ObjectFile) : nullptr; 162 } 163 164 /// Clear part of the context that's no longer needed when we're done with 165 /// the debug object. 166 void Clear() { 167 DwarfContext.reset(nullptr); 168 CompileUnits.clear(); 169 Ranges.clear(); 170 } 171 }; 172 173 /// Called at the start of a debug object link. 174 void startDebugObject(LinkContext &Context); 175 176 /// Called at the end of a debug object link. 177 void endDebugObject(LinkContext &Context); 178 179 /// \defgroup FindRootDIEs Find DIEs corresponding to debug map entries. 180 /// 181 /// @{ 182 /// Recursively walk the \p DIE tree and look for DIEs to 183 /// keep. Store that information in \p CU's DIEInfo. 184 /// 185 /// The return value indicates whether the DIE is incomplete. 186 void lookForDIEsToKeep(RelocationManager &RelocMgr, RangesTy &Ranges, 187 const UnitListTy &Units, const DWARFDie &DIE, 188 const DebugMapObject &DMO, CompileUnit &CU, 189 unsigned Flags); 190 191 /// If this compile unit is really a skeleton CU that points to a 192 /// clang module, register it in ClangModules and return true. 193 /// 194 /// A skeleton CU is a CU without children, a DW_AT_gnu_dwo_name 195 /// pointing to the module, and a DW_AT_gnu_dwo_id with the module 196 /// hash. 197 bool registerModuleReference(const DWARFDie &CUDie, const DWARFUnit &Unit, 198 DebugMap &ModuleMap, const DebugMapObject &DMO, 199 RangesTy &Ranges, 200 OffsetsStringPool &OffsetsStringPool, 201 UniquingStringPool &UniquingStringPoolStringPool, 202 DeclContextTree &ODRContexts, unsigned &UnitID, 203 unsigned Indent = 0); 204 205 /// Recursively add the debug info in this clang module .pcm 206 /// file (and all the modules imported by it in a bottom-up fashion) 207 /// to Units. 208 Error loadClangModule(StringRef Filename, StringRef ModulePath, 209 StringRef ModuleName, uint64_t DwoId, 210 DebugMap &ModuleMap, const DebugMapObject &DMO, 211 RangesTy &Ranges, OffsetsStringPool &OffsetsStringPool, 212 UniquingStringPool &UniquingStringPool, 213 DeclContextTree &ODRContexts, unsigned &UnitID, 214 unsigned Indent = 0); 215 216 /// Flags passed to DwarfLinker::lookForDIEsToKeep 217 enum TraversalFlags { 218 TF_Keep = 1 << 0, ///< Mark the traversed DIEs as kept. 219 TF_InFunctionScope = 1 << 1, ///< Current scope is a function scope. 220 TF_DependencyWalk = 1 << 2, ///< Walking the dependencies of a kept DIE. 221 TF_ParentWalk = 1 << 3, ///< Walking up the parents of a kept DIE. 222 TF_ODR = 1 << 4, ///< Use the ODR while keeping dependents. 223 TF_SkipPC = 1 << 5, ///< Skip all location attributes. 224 }; 225 226 /// Mark the passed DIE as well as all the ones it depends on as kept. 227 void keepDIEAndDependencies(RelocationManager &RelocMgr, RangesTy &Ranges, 228 const UnitListTy &Units, const DWARFDie &DIE, 229 CompileUnit::DIEInfo &MyInfo, 230 const DebugMapObject &DMO, CompileUnit &CU, 231 bool UseODR); 232 233 unsigned shouldKeepDIE(RelocationManager &RelocMgr, RangesTy &Ranges, 234 const DWARFDie &DIE, const DebugMapObject &DMO, 235 CompileUnit &Unit, CompileUnit::DIEInfo &MyInfo, 236 unsigned Flags); 237 238 unsigned shouldKeepVariableDIE(RelocationManager &RelocMgr, 239 const DWARFDie &DIE, CompileUnit &Unit, 240 CompileUnit::DIEInfo &MyInfo, unsigned Flags); 241 242 unsigned shouldKeepSubprogramDIE(RelocationManager &RelocMgr, 243 RangesTy &Ranges, const DWARFDie &DIE, 244 const DebugMapObject &DMO, CompileUnit &Unit, 245 CompileUnit::DIEInfo &MyInfo, 246 unsigned Flags); 247 248 bool hasValidRelocation(uint32_t StartOffset, uint32_t EndOffset, 249 CompileUnit::DIEInfo &Info); 250 /// @} 251 252 /// \defgroup Linking Methods used to link the debug information 253 /// 254 /// @{ 255 256 class DIECloner { 257 DwarfLinker &Linker; 258 RelocationManager &RelocMgr; 259 260 /// Allocator used for all the DIEValue objects. 261 BumpPtrAllocator &DIEAlloc; 262 263 std::vector<std::unique_ptr<CompileUnit>> &CompileUnits; 264 LinkOptions Options; 265 266 public: 267 DIECloner(DwarfLinker &Linker, RelocationManager &RelocMgr, 268 BumpPtrAllocator &DIEAlloc, 269 std::vector<std::unique_ptr<CompileUnit>> &CompileUnits, 270 LinkOptions &Options) 271 : Linker(Linker), RelocMgr(RelocMgr), DIEAlloc(DIEAlloc), 272 CompileUnits(CompileUnits), Options(Options) {} 273 274 /// Recursively clone \p InputDIE into an tree of DIE objects 275 /// where useless (as decided by lookForDIEsToKeep()) bits have been 276 /// stripped out and addresses have been rewritten according to the 277 /// debug map. 278 /// 279 /// \param OutOffset is the offset the cloned DIE in the output 280 /// compile unit. 281 /// \param PCOffset (while cloning a function scope) is the offset 282 /// applied to the entry point of the function to get the linked address. 283 /// \param Die the output DIE to use, pass NULL to create one. 284 /// \returns the root of the cloned tree or null if nothing was selected. 285 DIE *cloneDIE(const DWARFDie &InputDIE, const DebugMapObject &DMO, 286 CompileUnit &U, OffsetsStringPool &StringPool, 287 int64_t PCOffset, uint32_t OutOffset, unsigned Flags, 288 DIE *Die = nullptr); 289 290 /// Construct the output DIE tree by cloning the DIEs we 291 /// chose to keep above. If there are no valid relocs, then there's 292 /// nothing to clone/emit. 293 void cloneAllCompileUnits(DWARFContext &DwarfContext, 294 const DebugMapObject &DMO, RangesTy &Ranges, 295 OffsetsStringPool &StringPool); 296 297 private: 298 using AttributeSpec = DWARFAbbreviationDeclaration::AttributeSpec; 299 300 /// Information gathered and exchanged between the various 301 /// clone*Attributes helpers about the attributes of a particular DIE. 302 struct AttributesInfo { 303 /// Names. 304 DwarfStringPoolEntryRef Name, MangledName, NameWithoutTemplate; 305 306 /// Offsets in the string pool. 307 uint32_t NameOffset = 0; 308 uint32_t MangledNameOffset = 0; 309 310 /// Value of AT_low_pc in the input DIE 311 uint64_t OrigLowPc = std::numeric_limits<uint64_t>::max(); 312 313 /// Value of AT_high_pc in the input DIE 314 uint64_t OrigHighPc = 0; 315 316 /// Offset to apply to PC addresses inside a function. 317 int64_t PCOffset = 0; 318 319 /// Does the DIE have a low_pc attribute? 320 bool HasLowPc = false; 321 322 /// Does the DIE have a ranges attribute? 323 bool HasRanges = false; 324 325 /// Is this DIE only a declaration? 326 bool IsDeclaration = false; 327 328 AttributesInfo() = default; 329 }; 330 331 /// Helper for cloneDIE. 332 unsigned cloneAttribute(DIE &Die, const DWARFDie &InputDIE, 333 const DebugMapObject &DMO, CompileUnit &U, 334 OffsetsStringPool &StringPool, 335 const DWARFFormValue &Val, 336 const AttributeSpec AttrSpec, unsigned AttrSize, 337 AttributesInfo &AttrInfo); 338 339 /// Clone a string attribute described by \p AttrSpec and add 340 /// it to \p Die. 341 /// \returns the size of the new attribute. 342 unsigned cloneStringAttribute(DIE &Die, AttributeSpec AttrSpec, 343 const DWARFFormValue &Val, const DWARFUnit &U, 344 OffsetsStringPool &StringPool, 345 AttributesInfo &Info); 346 347 /// Clone an attribute referencing another DIE and add 348 /// it to \p Die. 349 /// \returns the size of the new attribute. 350 unsigned cloneDieReferenceAttribute(DIE &Die, const DWARFDie &InputDIE, 351 AttributeSpec AttrSpec, 352 unsigned AttrSize, 353 const DWARFFormValue &Val, 354 const DebugMapObject &DMO, 355 CompileUnit &Unit); 356 357 /// Clone an attribute referencing another DIE and add 358 /// it to \p Die. 359 /// \returns the size of the new attribute. 360 unsigned cloneBlockAttribute(DIE &Die, AttributeSpec AttrSpec, 361 const DWARFFormValue &Val, unsigned AttrSize); 362 363 /// Clone an attribute referencing another DIE and add 364 /// it to \p Die. 365 /// \returns the size of the new attribute. 366 unsigned cloneAddressAttribute(DIE &Die, AttributeSpec AttrSpec, 367 const DWARFFormValue &Val, 368 const CompileUnit &Unit, 369 AttributesInfo &Info); 370 371 /// Clone a scalar attribute and add it to \p Die. 372 /// \returns the size of the new attribute. 373 unsigned cloneScalarAttribute(DIE &Die, const DWARFDie &InputDIE, 374 const DebugMapObject &DMO, CompileUnit &U, 375 AttributeSpec AttrSpec, 376 const DWARFFormValue &Val, unsigned AttrSize, 377 AttributesInfo &Info); 378 379 /// Get the potential name and mangled name for the entity 380 /// described by \p Die and store them in \Info if they are not 381 /// already there. 382 /// \returns is a name was found. 383 bool getDIENames(const DWARFDie &Die, AttributesInfo &Info, 384 OffsetsStringPool &StringPool, bool StripTemplate = false); 385 386 /// Create a copy of abbreviation Abbrev. 387 void copyAbbrev(const DWARFAbbreviationDeclaration &Abbrev, bool hasODR); 388 389 uint32_t hashFullyQualifiedName(DWARFDie DIE, CompileUnit &U, 390 const DebugMapObject &DMO, 391 int RecurseDepth = 0); 392 393 /// Helper for cloneDIE. 394 void addObjCAccelerator(CompileUnit &Unit, const DIE *Die, 395 DwarfStringPoolEntryRef Name, 396 OffsetsStringPool &StringPool, bool SkipPubSection); 397 }; 398 399 /// Assign an abbreviation number to \p Abbrev 400 void AssignAbbrev(DIEAbbrev &Abbrev); 401 402 /// Compute and emit debug_ranges section for \p Unit, and 403 /// patch the attributes referencing it. 404 void patchRangesForUnit(const CompileUnit &Unit, DWARFContext &Dwarf, 405 const DebugMapObject &DMO) const; 406 407 /// Generate and emit the DW_AT_ranges attribute for a compile_unit if it had 408 /// one. 409 void generateUnitRanges(CompileUnit &Unit) const; 410 411 /// Extract the line tables from the original dwarf, extract the relevant 412 /// parts according to the linked function ranges and emit the result in the 413 /// debug_line section. 414 void patchLineTableForUnit(CompileUnit &Unit, DWARFContext &OrigDwarf, 415 RangesTy &Ranges, const DebugMapObject &DMO); 416 417 /// Emit the accelerator entries for \p Unit. 418 void emitAcceleratorEntriesForUnit(CompileUnit &Unit); 419 void emitDwarfAcceleratorEntriesForUnit(CompileUnit &Unit); 420 void emitAppleAcceleratorEntriesForUnit(CompileUnit &Unit); 421 422 /// Patch the frame info for an object file and emit it. 423 void patchFrameInfoForObject(const DebugMapObject &, RangesTy &Ranges, 424 DWARFContext &, unsigned AddressSize); 425 426 /// FoldingSet that uniques the abbreviations. 427 FoldingSet<DIEAbbrev> AbbreviationsSet; 428 429 /// Storage for the unique Abbreviations. 430 /// This is passed to AsmPrinter::emitDwarfAbbrevs(), thus it cannot be 431 /// changed to a vector of unique_ptrs. 432 std::vector<std::unique_ptr<DIEAbbrev>> Abbreviations; 433 434 /// DIELoc objects that need to be destructed (but not freed!). 435 std::vector<DIELoc *> DIELocs; 436 437 /// DIEBlock objects that need to be destructed (but not freed!). 438 std::vector<DIEBlock *> DIEBlocks; 439 440 /// Allocator used for all the DIEValue objects. 441 BumpPtrAllocator DIEAlloc; 442 /// @} 443 444 /// \defgroup Helpers Various helper methods. 445 /// 446 /// @{ 447 bool createStreamer(const Triple &TheTriple, raw_fd_ostream &OutFile); 448 449 /// Attempt to load a debug object from disk. 450 ErrorOr<const object::ObjectFile &> loadObject(const DebugMapObject &Obj, 451 const DebugMap &Map); 452 /// @} 453 454 raw_fd_ostream &OutFile; 455 BinaryHolder &BinHolder; 456 LinkOptions Options; 457 std::unique_ptr<DwarfStreamer> Streamer; 458 uint64_t OutputDebugInfoSize; 459 460 unsigned MaxDwarfVersion = 0; 461 unsigned MinDwarfVersion = std::numeric_limits<unsigned>::max(); 462 463 bool AtLeastOneAppleAccelTable = false; 464 bool AtLeastOneDwarfAccelTable = false; 465 466 /// The CIEs that have been emitted in the output section. The actual CIE 467 /// data serves a the key to this StringMap, this takes care of comparing the 468 /// semantics of CIEs defined in different object files. 469 StringMap<uint32_t> EmittedCIEs; 470 471 /// Offset of the last CIE that has been emitted in the output 472 /// debug_frame section. 473 uint32_t LastCIEOffset = 0; 474 475 /// Apple accelerator tables. 476 AccelTable<DWARF5AccelTableStaticData> DebugNames; 477 AccelTable<AppleAccelTableStaticOffsetData> AppleNames; 478 AccelTable<AppleAccelTableStaticOffsetData> AppleNamespaces; 479 AccelTable<AppleAccelTableStaticOffsetData> AppleObjc; 480 AccelTable<AppleAccelTableStaticTypeData> AppleTypes; 481 482 /// Mapping the PCM filename to the DwoId. 483 StringMap<uint64_t> ClangModules; 484 485 bool ModuleCacheHintDisplayed = false; 486 bool ArchiveHintDisplayed = false; 487 }; 488 489 } // end namespace dsymutil 490 } // end namespace llvm 491 492 #endif // LLVM_TOOLS_DSYMUTIL_DWARFLINKER_H 493