tools/dsymutil/DwarfLinker.h

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