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