tools/dsymutil/DwarfLinker.cpp

   1 //===- tools/dsymutil/DwarfLinker.cpp - Dwarf debug info linker -----------===//
   2 //
   3 //                             The LLVM Linker
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 #include "DebugMap.h"
  10 #include "BinaryHolder.h"
  11 #include "DebugMap.h"
  12 #include "dsymutil.h"
  13 #include "llvm/DebugInfo/DWARF/DWARFContext.h"
  14 #include "llvm/DebugInfo/DWARF/DWARFDebugInfoEntry.h"
  15 #include "llvm/DebugInfo/DWARF/DWARFFormValue.h"
  16 #include "llvm/Object/MachO.h"
  17 #include <string>
  18
  19 namespace llvm {
  20 namespace dsymutil {
  21
  22 namespace {
  23
  24 /// \brief Stores all information relating to a compile unit, be it in
  25 /// its original instance in the object file to its brand new cloned
  26 /// and linked DIE tree.
  27 class CompileUnit {
  28 public:
  29   /// \brief Information gathered about a DIE in the object file.
  30   struct DIEInfo {
  31     uint32_t ParentIdx;
  32   };
  33
  34   CompileUnit(DWARFUnit &OrigUnit) : OrigUnit(OrigUnit) {
  35     Info.resize(OrigUnit.getNumDIEs());
  36   }
  37
  38   DWARFUnit &getOrigUnit() const { return OrigUnit; }
  39
  40   DIEInfo &getInfo(unsigned Idx) { return Info[Idx]; }
  41   const DIEInfo &getInfo(unsigned Idx) const { return Info[Idx]; }
  42
  43 private:
  44   DWARFUnit &OrigUnit;
  45   std::vector<DIEInfo> Info; ///< DIE info indexed by DIE index.
  46 };
  47
  48 /// \brief The core of the Dwarf linking logic.
  49 ///
  50 /// The link of the dwarf information from the object files will be
  51 /// driven by the selection of 'root DIEs', which are DIEs that
  52 /// describe variables or functions that are present in the linked
  53 /// binary (and thus have entries in the debug map). All the debug
  54 /// information that will be linked (the DIEs, but also the line
  55 /// tables, ranges, ...) is derived from that set of root DIEs.
  56 ///
  57 /// The root DIEs are identified because they contain relocations that
  58 /// correspond to a debug map entry at specific places (the low_pc for
  59 /// a function, the location for a variable). These relocations are
  60 /// called ValidRelocs in the DwarfLinker and are gathered as a very
  61 /// first step when we start processing a DebugMapObject.
  62 class DwarfLinker {
  63 public:
  64   DwarfLinker(StringRef OutputFilename, bool Verbose)
  65       : OutputFilename(OutputFilename), Verbose(Verbose), BinHolder(Verbose) {}
  66
  67   /// \brief Link the contents of the DebugMap.
  68   bool link(const DebugMap &);
  69
  70 private:
  71   /// \brief Called at the start of a debug object link.
  72   void startDebugObject(DWARFContext &);
  73
  74   /// \brief Called at the end of a debug object link.
  75   void endDebugObject();
  76
  77   /// \defgroup FindValidRelocations Translate debug map into a list
  78   /// of relevant relocations
  79   ///
  80   /// @{
  81   struct ValidReloc {
  82     uint32_t Offset;
  83     uint32_t Size;
  84     uint64_t Addend;
  85     const DebugMapObject::DebugMapEntry *Mapping;
  86
  87     ValidReloc(uint32_t Offset, uint32_t Size, uint64_t Addend,
  88                const DebugMapObject::DebugMapEntry *Mapping)
  89         : Offset(Offset), Size(Size), Addend(Addend), Mapping(Mapping) {}
  90
  91     bool operator<(const ValidReloc &RHS) const { return Offset < RHS.Offset; }
  92   };
  93
  94   /// \brief The valid relocations for the current DebugMapObject.
  95   /// This vector is sorted by relocation offset.
  96   std::vector<ValidReloc> ValidRelocs;
  97
  98   /// \brief Index into ValidRelocs of the next relocation to
  99   /// consider. As we walk the DIEs in acsending file offset and as
 100   /// ValidRelocs is sorted by file offset, keeping this index
 101   /// uptodate is all we have to do to have a cheap lookup during the
 102   /// root DIE selection.
 103   unsigned NextValidReloc;
 104
 105   bool findValidRelocsInDebugInfo(const object::ObjectFile &Obj,
 106                                   const DebugMapObject &DMO);
 107
 108   bool findValidRelocs(const object::SectionRef &Section,
 109                        const object::ObjectFile &Obj,
 110                        const DebugMapObject &DMO);
 111
 112   void findValidRelocsMachO(const object::SectionRef &Section,
 113                             const object::MachOObjectFile &Obj,
 114                             const DebugMapObject &DMO);
 115   /// @}
 116
 117   /// \defgroup Helpers Various helper methods.
 118   ///
 119   /// @{
 120   const DWARFDebugInfoEntryMinimal *
 121   resolveDIEReference(DWARFFormValue &RefValue, const DWARFUnit &Unit,
 122                       const DWARFDebugInfoEntryMinimal &DIE,
 123                       CompileUnit *&ReferencedCU);
 124
 125   CompileUnit *getUnitForOffset(unsigned Offset);
 126
 127   void reportWarning(const Twine &Warning, const DWARFUnit *Unit = nullptr,
 128                      const DWARFDebugInfoEntryMinimal *DIE = nullptr);
 129   /// @}
 130
 131 private:
 132   std::string OutputFilename;
 133   bool Verbose;
 134   BinaryHolder BinHolder;
 135
 136   /// The units of the current debug map object.
 137   std::vector<CompileUnit> Units;
 138
 139   /// The debug map object curently under consideration.
 140   DebugMapObject *CurrentDebugObject;
 141 };
 142
 143 /// \brief Similar to DWARFUnitSection::getUnitForOffset(), but
 144 /// returning our CompileUnit object instead.
 145 CompileUnit *DwarfLinker::getUnitForOffset(unsigned Offset) {
 146   auto CU =
 147       std::upper_bound(Units.begin(), Units.end(), Offset,
 148                        [](uint32_t LHS, const CompileUnit &RHS) {
 149                          return LHS < RHS.getOrigUnit().getNextUnitOffset();
 150                        });
 151   return CU != Units.end() ? &*CU : nullptr;
 152 }
 153
 154 /// \brief Resolve the DIE attribute reference that has been
 155 /// extracted in \p RefValue. The resulting DIE migh be in another
 156 /// CompileUnit which is stored into \p ReferencedCU.
 157 /// \returns null if resolving fails for any reason.
 158 const DWARFDebugInfoEntryMinimal *DwarfLinker::resolveDIEReference(
 159     DWARFFormValue &RefValue, const DWARFUnit &Unit,
 160     const DWARFDebugInfoEntryMinimal &DIE, CompileUnit *&RefCU) {
 161   assert(RefValue.isFormClass(DWARFFormValue::FC_Reference));
 162   uint64_t RefOffset = *RefValue.getAsReference(&Unit);
 163
 164   if ((RefCU = getUnitForOffset(RefOffset)))
 165     if (const auto *RefDie = RefCU->getOrigUnit().getDIEForOffset(RefOffset))
 166       return RefDie;
 167
 168   reportWarning("could not find referenced DIE", &Unit, &DIE);
 169   return nullptr;
 170 }
 171
 172 /// \brief Report a warning to the user, optionaly including
 173 /// information about a specific \p DIE related to the warning.
 174 void DwarfLinker::reportWarning(const Twine &Warning, const DWARFUnit *Unit,
 175                                 const DWARFDebugInfoEntryMinimal *DIE) {
 176   if (CurrentDebugObject)
 177     errs() << Twine("while processing ") +
 178                   CurrentDebugObject->getObjectFilename() + ":\n";
 179   errs() << Twine("warning: ") + Warning + "\n";
 180
 181   if (!Verbose || !DIE)
 182     return;
 183
 184   errs() << "    in DIE:\n";
 185   DIE->dump(errs(), const_cast<DWARFUnit *>(Unit), 0 /* RecurseDepth */,
 186             6 /* Indent */);
 187 }
 188
 189 /// \brief Recursive helper to gather the child->parent relationships in the
 190 /// original compile unit.
 191 void GatherDIEParents(const DWARFDebugInfoEntryMinimal *DIE, unsigned ParentIdx,
 192                       CompileUnit &CU) {
 193   unsigned MyIdx = CU.getOrigUnit().getDIEIndex(DIE);
 194   CU.getInfo(MyIdx).ParentIdx = ParentIdx;
 195
 196   if (DIE->hasChildren())
 197     for (auto *Child = DIE->getFirstChild(); Child && !Child->isNULL();
 198          Child = Child->getSibling())
 199       GatherDIEParents(Child, MyIdx, CU);
 200 }
 201
 202 void DwarfLinker::startDebugObject(DWARFContext &Dwarf) {
 203   Units.reserve(Dwarf.getNumCompileUnits());
 204   NextValidReloc = 0;
 205 }
 206
 207 void DwarfLinker::endDebugObject() {
 208   Units.clear();
 209   ValidRelocs.clear();
 210 }
 211
 212 /// \brief Iterate over the relocations of the given \p Section and
 213 /// store the ones that correspond to debug map entries into the
 214 /// ValidRelocs array.
 215 void DwarfLinker::findValidRelocsMachO(const object::SectionRef &Section,
 216                                        const object::MachOObjectFile &Obj,
 217                                        const DebugMapObject &DMO) {
 218   StringRef Contents;
 219   Section.getContents(Contents);
 220   DataExtractor Data(Contents, Obj.isLittleEndian(), 0);
 221
 222   for (const object::RelocationRef &Reloc : Section.relocations()) {
 223     object::DataRefImpl RelocDataRef = Reloc.getRawDataRefImpl();
 224     MachO::any_relocation_info MachOReloc = Obj.getRelocation(RelocDataRef);
 225     unsigned RelocSize = 1 << Obj.getAnyRelocationLength(MachOReloc);
 226     uint64_t Offset64;
 227     if ((RelocSize != 4 && RelocSize != 8) || Reloc.getOffset(Offset64)) {
 228       reportWarning(" unsupported relocation in debug_info section.");
 229       continue;
 230     }
 231     uint32_t Offset = Offset64;
 232     // Mach-o uses REL relocations, the addend is at the relocation offset.
 233     uint64_t Addend = Data.getUnsigned(&Offset, RelocSize);
 234
 235     auto Sym = Reloc.getSymbol();
 236     if (Sym != Obj.symbol_end()) {
 237       StringRef SymbolName;
 238       if (Sym->getName(SymbolName)) {
 239         reportWarning("error getting relocation symbol name.");
 240         continue;
 241       }
 242       if (const auto *Mapping = DMO.lookupSymbol(SymbolName))
 243         ValidRelocs.emplace_back(Offset64, RelocSize, Addend, Mapping);
 244     } else if (const auto *Mapping = DMO.lookupObjectAddress(Addend)) {
 245       // Do not store the addend. The addend was the address of the
 246       // symbol in the object file, the address in the binary that is
 247       // stored in the debug map doesn't need to be offseted.
 248       ValidRelocs.emplace_back(Offset64, RelocSize, 0, Mapping);
 249     }
 250   }
 251 }
 252
 253 /// \brief Dispatch the valid relocation finding logic to the
 254 /// appropriate handler depending on the object file format.
 255 bool DwarfLinker::findValidRelocs(const object::SectionRef &Section,
 256                                   const object::ObjectFile &Obj,
 257                                   const DebugMapObject &DMO) {
 258   // Dispatch to the right handler depending on the file type.
 259   if (auto *MachOObj = dyn_cast<object::MachOObjectFile>(&Obj))
 260     findValidRelocsMachO(Section, *MachOObj, DMO);
 261   else
 262     reportWarning(Twine("unsupported object file type: ") + Obj.getFileName());
 263
 264   if (ValidRelocs.empty())
 265     return false;
 266
 267   // Sort the relocations by offset. We will walk the DIEs linearly in
 268   // the file, this allows us to just keep an index in the relocation
 269   // array that we advance during our walk, rather than resorting to
 270   // some associative container. See DwarfLinker::NextValidReloc.
 271   std::sort(ValidRelocs.begin(), ValidRelocs.end());
 272   return true;
 273 }
 274
 275 /// \brief Look for relocations in the debug_info section that match
 276 /// entries in the debug map. These relocations will drive the Dwarf
 277 /// link by indicating which DIEs refer to symbols present in the
 278 /// linked binary.
 279 /// \returns wether there are any valid relocations in the debug info.
 280 bool DwarfLinker::findValidRelocsInDebugInfo(const object::ObjectFile &Obj,
 281                                              const DebugMapObject &DMO) {
 282   // Find the debug_info section.
 283   for (const object::SectionRef &Section : Obj.sections()) {
 284     StringRef SectionName;
 285     Section.getName(SectionName);
 286     SectionName = SectionName.substr(SectionName.find_first_not_of("._"));
 287     if (SectionName != "debug_info")
 288       continue;
 289     return findValidRelocs(Section, Obj, DMO);
 290   }
 291   return false;
 292 }
 293
 294 bool DwarfLinker::link(const DebugMap &Map) {
 295
 296   if (Map.begin() == Map.end()) {
 297     errs() << "Empty debug map.\n";
 298     return false;
 299   }
 300
 301   for (const auto &Obj : Map.objects()) {
 302     CurrentDebugObject = Obj.get();
 303
 304     if (Verbose)
 305       outs() << "DEBUG MAP OBJECT: " << Obj->getObjectFilename() << "\n";
 306     auto ErrOrObj = BinHolder.GetObjectFile(Obj->getObjectFilename());
 307     if (std::error_code EC = ErrOrObj.getError()) {
 308       reportWarning(Twine(Obj->getObjectFilename()) + ": " + EC.message());
 309       continue;
 310     }
 311
 312     // Look for relocations that correspond to debug map entries.
 313     if (!findValidRelocsInDebugInfo(*ErrOrObj, *Obj)) {
 314       if (Verbose)
 315         outs() << "No valid relocations found. Skipping.\n";
 316       continue;
 317     }
 318
 319     // Setup access to the debug info.
 320     DWARFContextInMemory DwarfContext(*ErrOrObj);
 321     startDebugObject(DwarfContext);
 322
 323     // In a first phase, just read in the debug info and store the DIE
 324     // parent links that we will use during the next phase.
 325     for (const auto &CU : DwarfContext.compile_units()) {
 326       auto *CUDie = CU->getCompileUnitDIE(false);
 327       if (Verbose) {
 328         outs() << "Input compilation unit:";
 329         CUDie->dump(outs(), CU.get(), 0);
 330       }
 331       Units.emplace_back(*CU);
 332       GatherDIEParents(CUDie, 0, Units.back());
 333     }
 334
 335     // Clean-up before starting working on the next object.
 336     endDebugObject();
 337   }
 338
 339   return true;
 340 }
 341 }
 342
 343 bool linkDwarf(StringRef OutputFilename, const DebugMap &DM, bool Verbose) {
 344   DwarfLinker Linker(OutputFilename, Verbose);
 345   return Linker.link(DM);
 346 }
 347 }
 348 }