llvm/tools/dsymutil/DwarfLinkerForBinary.cpp

   1 //===- tools/dsymutil/DwarfLinkerForBinary.cpp ----------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "DwarfLinkerForBinary.h"
  10 #include "BinaryHolder.h"
  11 #include "DebugMap.h"
  12 #include "MachOUtils.h"
  13 #include "dsymutil.h"
  14 #include "llvm/ADT/ArrayRef.h"
  15 #include "llvm/ADT/BitVector.h"
  16 #include "llvm/ADT/DenseMap.h"
  17 #include "llvm/ADT/DenseMapInfo.h"
  18 #include "llvm/ADT/DenseSet.h"
  19 #include "llvm/ADT/FoldingSet.h"
  20 #include "llvm/ADT/Hashing.h"
  21 #include "llvm/ADT/IntervalMap.h"
  22 #include "llvm/ADT/None.h"
  23 #include "llvm/ADT/Optional.h"
  24 #include "llvm/ADT/PointerIntPair.h"
  25 #include "llvm/ADT/STLExtras.h"
  26 #include "llvm/ADT/SmallString.h"
  27 #include "llvm/ADT/StringMap.h"
  28 #include "llvm/ADT/StringRef.h"
  29 #include "llvm/ADT/Triple.h"
  30 #include "llvm/ADT/Twine.h"
  31 #include "llvm/BinaryFormat/Dwarf.h"
  32 #include "llvm/BinaryFormat/MachO.h"
  33 #include "llvm/CodeGen/AccelTable.h"
  34 #include "llvm/CodeGen/AsmPrinter.h"
  35 #include "llvm/CodeGen/DIE.h"
  36 #include "llvm/CodeGen/NonRelocatableStringpool.h"
  37 #include "llvm/Config/config.h"
  38 #include "llvm/DWARFLinker/DWARFLinkerDeclContext.h"
  39 #include "llvm/DebugInfo/DIContext.h"
  40 #include "llvm/DebugInfo/DWARF/DWARFAbbreviationDeclaration.h"
  41 #include "llvm/DebugInfo/DWARF/DWARFContext.h"
  42 #include "llvm/DebugInfo/DWARF/DWARFDataExtractor.h"
  43 #include "llvm/DebugInfo/DWARF/DWARFDebugLine.h"
  44 #include "llvm/DebugInfo/DWARF/DWARFDebugRangeList.h"
  45 #include "llvm/DebugInfo/DWARF/DWARFDie.h"
  46 #include "llvm/DebugInfo/DWARF/DWARFFormValue.h"
  47 #include "llvm/DebugInfo/DWARF/DWARFSection.h"
  48 #include "llvm/DebugInfo/DWARF/DWARFUnit.h"
  49 #include "llvm/MC/MCAsmBackend.h"
  50 #include "llvm/MC/MCAsmInfo.h"
  51 #include "llvm/MC/MCCodeEmitter.h"
  52 #include "llvm/MC/MCContext.h"
  53 #include "llvm/MC/MCDwarf.h"
  54 #include "llvm/MC/MCInstrInfo.h"
  55 #include "llvm/MC/MCObjectFileInfo.h"
  56 #include "llvm/MC/MCObjectWriter.h"
  57 #include "llvm/MC/MCRegisterInfo.h"
  58 #include "llvm/MC/MCSection.h"
  59 #include "llvm/MC/MCStreamer.h"
  60 #include "llvm/MC/MCSubtargetInfo.h"
  61 #include "llvm/MC/MCTargetOptions.h"
  62 #include "llvm/MC/MCTargetOptionsCommandFlags.h"
  63 #include "llvm/MC/TargetRegistry.h"
  64 #include "llvm/Object/MachO.h"
  65 #include "llvm/Object/ObjectFile.h"
  66 #include "llvm/Object/SymbolicFile.h"
  67 #include "llvm/Support/Allocator.h"
  68 #include "llvm/Support/Casting.h"
  69 #include "llvm/Support/Compiler.h"
  70 #include "llvm/Support/DJB.h"
  71 #include "llvm/Support/DataExtractor.h"
  72 #include "llvm/Support/Error.h"
  73 #include "llvm/Support/ErrorHandling.h"
  74 #include "llvm/Support/ErrorOr.h"
  75 #include "llvm/Support/FileSystem.h"
  76 #include "llvm/Support/Format.h"
  77 #include "llvm/Support/LEB128.h"
  78 #include "llvm/Support/MathExtras.h"
  79 #include "llvm/Support/MemoryBuffer.h"
  80 #include "llvm/Support/Path.h"
  81 #include "llvm/Support/ThreadPool.h"
  82 #include "llvm/Support/ToolOutputFile.h"
  83 #include "llvm/Support/WithColor.h"
  84 #include "llvm/Support/raw_ostream.h"
  85 #include "llvm/Target/TargetMachine.h"
  86 #include "llvm/Target/TargetOptions.h"
  87 #include <algorithm>
  88 #include <cassert>
  89 #include <cinttypes>
  90 #include <climits>
  91 #include <cstdint>
  92 #include <cstdlib>
  93 #include <cstring>
  94 #include <limits>
  95 #include <map>
  96 #include <memory>
  97 #include <string>
  98 #include <system_error>
  99 #include <tuple>
 100 #include <utility>
 101 #include <vector>
 102
 103 namespace llvm {
 104
 105 static mc::RegisterMCTargetOptionsFlags MOF;
 106
 107 namespace dsymutil {
 108
 109 static Error copySwiftInterfaces(
 110     const std::map<std::string, std::string> &ParseableSwiftInterfaces,
 111     StringRef Architecture, const LinkOptions &Options) {
 112   std::error_code EC;
 113   SmallString<128> InputPath;
 114   SmallString<128> Path;
 115   sys::path::append(Path, *Options.ResourceDir, "Swift", Architecture);
 116   if ((EC = sys::fs::create_directories(Path.str(), true,
 117                                         sys::fs::perms::all_all)))
 118     return make_error<StringError>(
 119         "cannot create directory: " + toString(errorCodeToError(EC)), EC);
 120   unsigned BaseLength = Path.size();
 121
 122   for (auto &I : ParseableSwiftInterfaces) {
 123     StringRef ModuleName = I.first;
 124     StringRef InterfaceFile = I.second;
 125     if (!Options.PrependPath.empty()) {
 126       InputPath.clear();
 127       sys::path::append(InputPath, Options.PrependPath, InterfaceFile);
 128       InterfaceFile = InputPath;
 129     }
 130     sys::path::append(Path, ModuleName);
 131     Path.append(".swiftinterface");
 132     if (Options.Verbose)
 133       outs() << "copy parseable Swift interface " << InterfaceFile << " -> "
 134              << Path.str() << '\n';
 135
 136     // copy_file attempts an APFS clone first, so this should be cheap.
 137     if ((EC = sys::fs::copy_file(InterfaceFile, Path.str())))
 138       warn(Twine("cannot copy parseable Swift interface ") + InterfaceFile +
 139            ": " + toString(errorCodeToError(EC)));
 140     Path.resize(BaseLength);
 141   }
 142   return Error::success();
 143 }
 144
 145 /// Report a warning to the user, optionally including information about a
 146 /// specific \p DIE related to the warning.
 147 void DwarfLinkerForBinary::reportWarning(const Twine &Warning,
 148                                          StringRef Context,
 149                                          const DWARFDie *DIE) const {
 150
 151   warn(Warning, Context);
 152
 153   if (!Options.Verbose || !DIE)
 154     return;
 155
 156   DIDumpOptions DumpOpts;
 157   DumpOpts.ChildRecurseDepth = 0;
 158   DumpOpts.Verbose = Options.Verbose;
 159
 160   WithColor::note() << "    in DIE:\n";
 161   DIE->dump(errs(), 6 /* Indent */, DumpOpts);
 162 }
 163
 164 bool DwarfLinkerForBinary::createStreamer(const Triple &TheTriple,
 165                                           raw_fd_ostream &OutFile) {
 166   if (Options.NoOutput)
 167     return true;
 168
 169   Streamer = std::make_unique<DwarfStreamer>(
 170       Options.FileType, OutFile, Options.Translator,
 171       [&](const Twine &Error, StringRef Context, const DWARFDie *) {
 172         error(Error, Context);
 173       },
 174       [&](const Twine &Warning, StringRef Context, const DWARFDie *) {
 175         warn(Warning, Context);
 176       });
 177   return Streamer->init(TheTriple);
 178 }
 179
 180 ErrorOr<const object::ObjectFile &>
 181 DwarfLinkerForBinary::loadObject(const DebugMapObject &Obj,
 182                                  const Triple &Triple) {
 183   auto ObjectEntry =
 184       BinHolder.getObjectEntry(Obj.getObjectFilename(), Obj.getTimestamp());
 185   if (!ObjectEntry) {
 186     auto Err = ObjectEntry.takeError();
 187     reportWarning(Twine(Obj.getObjectFilename()) + ": " +
 188                       toString(std::move(Err)),
 189                   Obj.getObjectFilename());
 190     return errorToErrorCode(std::move(Err));
 191   }
 192
 193   auto Object = ObjectEntry->getObject(Triple);
 194   if (!Object) {
 195     auto Err = Object.takeError();
 196     reportWarning(Twine(Obj.getObjectFilename()) + ": " +
 197                       toString(std::move(Err)),
 198                   Obj.getObjectFilename());
 199     return errorToErrorCode(std::move(Err));
 200   }
 201
 202   return *Object;
 203 }
 204
 205 static Error remarksErrorHandler(const DebugMapObject &DMO,
 206                                  DwarfLinkerForBinary &Linker,
 207                                  std::unique_ptr<FileError> FE) {
 208   bool IsArchive = DMO.getObjectFilename().endswith(")");
 209   // Don't report errors for missing remark files from static
 210   // archives.
 211   if (!IsArchive)
 212     return Error(std::move(FE));
 213
 214   std::string Message = FE->message();
 215   Error E = FE->takeError();
 216   Error NewE = handleErrors(std::move(E), [&](std::unique_ptr<ECError> EC) {
 217     if (EC->convertToErrorCode() != std::errc::no_such_file_or_directory)
 218       return Error(std::move(EC));
 219
 220     Linker.reportWarning(Message, DMO.getObjectFilename());
 221     return Error(Error::success());
 222   });
 223
 224   if (!NewE)
 225     return Error::success();
 226
 227   return createFileError(FE->getFileName(), std::move(NewE));
 228 }
 229
 230 static Error emitRemarks(const LinkOptions &Options, StringRef BinaryPath,
 231                          StringRef ArchName, const remarks::RemarkLinker &RL) {
 232   // Make sure we don't create the directories and the file if there is nothing
 233   // to serialize.
 234   if (RL.empty())
 235     return Error::success();
 236
 237   SmallString<128> InputPath;
 238   SmallString<128> Path;
 239   // Create the "Remarks" directory in the "Resources" directory.
 240   sys::path::append(Path, *Options.ResourceDir, "Remarks");
 241   if (std::error_code EC = sys::fs::create_directories(Path.str(), true,
 242                                                        sys::fs::perms::all_all))
 243     return errorCodeToError(EC);
 244
 245   // Append the file name.
 246   // For fat binaries, also append a dash and the architecture name.
 247   sys::path::append(Path, sys::path::filename(BinaryPath));
 248   if (Options.NumDebugMaps > 1) {
 249     // More than one debug map means we have a fat binary.
 250     Path += '-';
 251     Path += ArchName;
 252   }
 253
 254   std::error_code EC;
 255   raw_fd_ostream OS(Options.NoOutput ? "-" : Path.str(), EC,
 256                     Options.RemarksFormat == remarks::Format::Bitstream
 257                         ? sys::fs::OF_None
 258                         : sys::fs::OF_Text);
 259   if (EC)
 260     return errorCodeToError(EC);
 261
 262   if (Error E = RL.serialize(OS, Options.RemarksFormat))
 263     return E;
 264
 265   return Error::success();
 266 }
 267
 268 ErrorOr<DWARFFile &>
 269 DwarfLinkerForBinary::loadObject(const DebugMapObject &Obj,
 270                                  const DebugMap &DebugMap,
 271                                  remarks::RemarkLinker &RL) {
 272   auto ErrorOrObj = loadObject(Obj, DebugMap.getTriple());
 273
 274   if (ErrorOrObj) {
 275     ContextForLinking.push_back(
 276         std::unique_ptr<DWARFContext>(DWARFContext::create(*ErrorOrObj)));
 277     AddressMapForLinking.push_back(
 278         std::make_unique<AddressManager>(*this, *ErrorOrObj, Obj));
 279
 280     ObjectsForLinking.push_back(std::make_unique<DWARFFile>(
 281         Obj.getObjectFilename(), ContextForLinking.back().get(),
 282         AddressMapForLinking.back().get(),
 283         Obj.empty() ? Obj.getWarnings() : EmptyWarnings));
 284
 285     Error E = RL.link(*ErrorOrObj);
 286     if (Error NewE = handleErrors(
 287             std::move(E), [&](std::unique_ptr<FileError> EC) -> Error {
 288               return remarksErrorHandler(Obj, *this, std::move(EC));
 289             }))
 290       return errorToErrorCode(std::move(NewE));
 291
 292     return *ObjectsForLinking.back();
 293   }
 294
 295   return ErrorOrObj.getError();
 296 }
 297
 298 bool DwarfLinkerForBinary::link(const DebugMap &Map) {
 299   if (!createStreamer(Map.getTriple(), OutFile))
 300     return false;
 301
 302   ObjectsForLinking.clear();
 303   ContextForLinking.clear();
 304   AddressMapForLinking.clear();
 305
 306   DebugMap DebugMap(Map.getTriple(), Map.getBinaryPath());
 307
 308   DWARFLinker GeneralLinker(Streamer.get(), DwarfLinkerClient::Dsymutil);
 309
 310   remarks::RemarkLinker RL;
 311   if (!Options.RemarksPrependPath.empty())
 312     RL.setExternalFilePrependPath(Options.RemarksPrependPath);
 313   GeneralLinker.setObjectPrefixMap(&Options.ObjectPrefixMap);
 314
 315   std::function<StringRef(StringRef)> TranslationLambda = [&](StringRef Input) {
 316     assert(Options.Translator);
 317     return Options.Translator(Input);
 318   };
 319
 320   GeneralLinker.setVerbosity(Options.Verbose);
 321   GeneralLinker.setStatistics(Options.Statistics);
 322   GeneralLinker.setNoOutput(Options.NoOutput);
 323   GeneralLinker.setNoODR(Options.NoODR);
 324   GeneralLinker.setUpdate(Options.Update);
 325   GeneralLinker.setNumThreads(Options.Threads);
 326   GeneralLinker.setAccelTableKind(Options.TheAccelTableKind);
 327   GeneralLinker.setPrependPath(Options.PrependPath);
 328   GeneralLinker.setKeepFunctionForStatic(Options.KeepFunctionForStatic);
 329   if (Options.Translator)
 330     GeneralLinker.setStringsTranslator(TranslationLambda);
 331   GeneralLinker.setWarningHandler(
 332       [&](const Twine &Warning, StringRef Context, const DWARFDie *DIE) {
 333         reportWarning(Warning, Context, DIE);
 334       });
 335   GeneralLinker.setErrorHandler(
 336       [&](const Twine &Error, StringRef Context, const DWARFDie *) {
 337         error(Error, Context);
 338       });
 339   GeneralLinker.setObjFileLoader(
 340       [&DebugMap, &RL, this](StringRef ContainerName,
 341                              StringRef Path) -> ErrorOr<DWARFFile &> {
 342         auto &Obj = DebugMap.addDebugMapObject(
 343             Path, sys::TimePoint<std::chrono::seconds>(), MachO::N_OSO);
 344
 345         if (auto ErrorOrObj = loadObject(Obj, DebugMap, RL)) {
 346           return *ErrorOrObj;
 347         } else {
 348           // Try and emit more helpful warnings by applying some heuristics.
 349           StringRef ObjFile = ContainerName;
 350           bool IsClangModule = sys::path::extension(Path).equals(".pcm");
 351           bool IsArchive = ObjFile.endswith(")");
 352
 353           if (IsClangModule) {
 354             StringRef ModuleCacheDir = sys::path::parent_path(Path);
 355             if (sys::fs::exists(ModuleCacheDir)) {
 356               // If the module's parent directory exists, we assume that the
 357               // module cache has expired and was pruned by clang.  A more
 358               // adventurous dsymutil would invoke clang to rebuild the module
 359               // now.
 360               if (!ModuleCacheHintDisplayed) {
 361                 WithColor::note()
 362                     << "The clang module cache may have expired since "
 363                        "this object file was built. Rebuilding the "
 364                        "object file will rebuild the module cache.\n";
 365                 ModuleCacheHintDisplayed = true;
 366               }
 367             } else if (IsArchive) {
 368               // If the module cache directory doesn't exist at all and the
 369               // object file is inside a static library, we assume that the
 370               // static library was built on a different machine. We don't want
 371               // to discourage module debugging for convenience libraries within
 372               // a project though.
 373               if (!ArchiveHintDisplayed) {
 374                 WithColor::note()
 375                     << "Linking a static library that was built with "
 376                        "-gmodules, but the module cache was not found.  "
 377                        "Redistributable static libraries should never be "
 378                        "built with module debugging enabled.  The debug "
 379                        "experience will be degraded due to incomplete "
 380                        "debug information.\n";
 381                 ArchiveHintDisplayed = true;
 382               }
 383             }
 384           }
 385
 386           return ErrorOrObj.getError();
 387         }
 388
 389         llvm_unreachable("Unhandled DebugMap object");
 390       });
 391   GeneralLinker.setSwiftInterfacesMap(&ParseableSwiftInterfaces);
 392
 393   for (const auto &Obj : Map.objects()) {
 394     // N_AST objects (swiftmodule files) should get dumped directly into the
 395     // appropriate DWARF section.
 396     if (Obj->getType() == MachO::N_AST) {
 397       if (Options.Verbose)
 398         outs() << "DEBUG MAP OBJECT: " << Obj->getObjectFilename() << "\n";
 399
 400       StringRef File = Obj->getObjectFilename();
 401       auto ErrorOrMem = MemoryBuffer::getFile(File);
 402       if (!ErrorOrMem) {
 403         warn("Could not open '" + File + "'\n");
 404         continue;
 405       }
 406       sys::fs::file_status Stat;
 407       if (auto Err = sys::fs::status(File, Stat)) {
 408         warn(Err.message());
 409         continue;
 410       }
 411       if (!Options.NoTimestamp) {
 412         // The modification can have sub-second precision so we need to cast
 413         // away the extra precision that's not present in the debug map.
 414         auto ModificationTime =
 415             std::chrono::time_point_cast<std::chrono::seconds>(
 416                 Stat.getLastModificationTime());
 417         if (ModificationTime != Obj->getTimestamp()) {
 418           // Not using the helper here as we can easily stream TimePoint<>.
 419           WithColor::warning()
 420               << File << ": timestamp mismatch between swift interface file ("
 421               << sys::TimePoint<>(Obj->getTimestamp()) << ") and debug map ("
 422               << sys::TimePoint<>(Obj->getTimestamp()) << ")\n";
 423           continue;
 424         }
 425       }
 426
 427       // Copy the module into the .swift_ast section.
 428       if (!Options.NoOutput)
 429         Streamer->emitSwiftAST((*ErrorOrMem)->getBuffer());
 430
 431       continue;
 432     }
 433
 434     if (auto ErrorOrObj = loadObject(*Obj, Map, RL))
 435       GeneralLinker.addObjectFile(*ErrorOrObj);
 436     else {
 437       ObjectsForLinking.push_back(std::make_unique<DWARFFile>(
 438           Obj->getObjectFilename(), nullptr, nullptr,
 439           Obj->empty() ? Obj->getWarnings() : EmptyWarnings));
 440       GeneralLinker.addObjectFile(*ObjectsForLinking.back());
 441     }
 442   }
 443
 444   // link debug info for loaded object files.
 445   GeneralLinker.link();
 446
 447   StringRef ArchName = Map.getTriple().getArchName();
 448   if (Error E = emitRemarks(Options, Map.getBinaryPath(), ArchName, RL))
 449     return error(toString(std::move(E)));
 450
 451   if (Options.NoOutput)
 452     return true;
 453
 454   if (Options.ResourceDir && !ParseableSwiftInterfaces.empty()) {
 455     StringRef ArchName = Triple::getArchTypeName(Map.getTriple().getArch());
 456     if (auto E =
 457             copySwiftInterfaces(ParseableSwiftInterfaces, ArchName, Options))
 458       return error(toString(std::move(E)));
 459   }
 460
 461   if (Map.getTriple().isOSDarwin() && !Map.getBinaryPath().empty() &&
 462       Options.FileType == OutputFileType::Object)
 463     return MachOUtils::generateDsymCompanion(
 464         Options.VFS, Map, Options.Translator,
 465         *Streamer->getAsmPrinter().OutStreamer, OutFile);
 466
 467   Streamer->finish();
 468   return true;
 469 }
 470
 471 static bool isMachOPairedReloc(uint64_t RelocType, uint64_t Arch) {
 472   switch (Arch) {
 473   case Triple::x86:
 474     return RelocType == MachO::GENERIC_RELOC_SECTDIFF ||
 475            RelocType == MachO::GENERIC_RELOC_LOCAL_SECTDIFF;
 476   case Triple::x86_64:
 477     return RelocType == MachO::X86_64_RELOC_SUBTRACTOR;
 478   case Triple::arm:
 479   case Triple::thumb:
 480     return RelocType == MachO::ARM_RELOC_SECTDIFF ||
 481            RelocType == MachO::ARM_RELOC_LOCAL_SECTDIFF ||
 482            RelocType == MachO::ARM_RELOC_HALF ||
 483            RelocType == MachO::ARM_RELOC_HALF_SECTDIFF;
 484   case Triple::aarch64:
 485     return RelocType == MachO::ARM64_RELOC_SUBTRACTOR;
 486   default:
 487     return false;
 488   }
 489 }
 490
 491 /// Iterate over the relocations of the given \p Section and
 492 /// store the ones that correspond to debug map entries into the
 493 /// ValidRelocs array.
 494 void DwarfLinkerForBinary::AddressManager::findValidRelocsMachO(
 495     const object::SectionRef &Section, const object::MachOObjectFile &Obj,
 496     const DebugMapObject &DMO, std::vector<ValidReloc> &ValidRelocs) {
 497   Expected<StringRef> ContentsOrErr = Section.getContents();
 498   if (!ContentsOrErr) {
 499     consumeError(ContentsOrErr.takeError());
 500     Linker.reportWarning("error reading section", DMO.getObjectFilename());
 501     return;
 502   }
 503   DataExtractor Data(*ContentsOrErr, Obj.isLittleEndian(), 0);
 504   bool SkipNext = false;
 505
 506   for (const object::RelocationRef &Reloc : Section.relocations()) {
 507     if (SkipNext) {
 508       SkipNext = false;
 509       continue;
 510     }
 511
 512     object::DataRefImpl RelocDataRef = Reloc.getRawDataRefImpl();
 513     MachO::any_relocation_info MachOReloc = Obj.getRelocation(RelocDataRef);
 514
 515     if (isMachOPairedReloc(Obj.getAnyRelocationType(MachOReloc),
 516                            Obj.getArch())) {
 517       SkipNext = true;
 518       Linker.reportWarning("unsupported relocation in " + *Section.getName() +
 519                                " section.",
 520                            DMO.getObjectFilename());
 521       continue;
 522     }
 523
 524     unsigned RelocSize = 1 << Obj.getAnyRelocationLength(MachOReloc);
 525     uint64_t Offset64 = Reloc.getOffset();
 526     if ((RelocSize != 4 && RelocSize != 8)) {
 527       Linker.reportWarning("unsupported relocation in " + *Section.getName() +
 528                                " section.",
 529                            DMO.getObjectFilename());
 530       continue;
 531     }
 532     uint64_t OffsetCopy = Offset64;
 533     // Mach-o uses REL relocations, the addend is at the relocation offset.
 534     uint64_t Addend = Data.getUnsigned(&OffsetCopy, RelocSize);
 535     uint64_t SymAddress;
 536     int64_t SymOffset;
 537
 538     if (Obj.isRelocationScattered(MachOReloc)) {
 539       // The address of the base symbol for scattered relocations is
 540       // stored in the reloc itself. The actual addend will store the
 541       // base address plus the offset.
 542       SymAddress = Obj.getScatteredRelocationValue(MachOReloc);
 543       SymOffset = int64_t(Addend) - SymAddress;
 544     } else {
 545       SymAddress = Addend;
 546       SymOffset = 0;
 547     }
 548
 549     auto Sym = Reloc.getSymbol();
 550     if (Sym != Obj.symbol_end()) {
 551       Expected<StringRef> SymbolName = Sym->getName();
 552       if (!SymbolName) {
 553         consumeError(SymbolName.takeError());
 554         Linker.reportWarning("error getting relocation symbol name.",
 555                              DMO.getObjectFilename());
 556         continue;
 557       }
 558       if (const auto *Mapping = DMO.lookupSymbol(*SymbolName))
 559         ValidRelocs.emplace_back(Offset64, RelocSize, Addend, Mapping);
 560     } else if (const auto *Mapping = DMO.lookupObjectAddress(SymAddress)) {
 561       // Do not store the addend. The addend was the address of the symbol in
 562       // the object file, the address in the binary that is stored in the debug
 563       // map doesn't need to be offset.
 564       ValidRelocs.emplace_back(Offset64, RelocSize, SymOffset, Mapping);
 565     }
 566   }
 567 }
 568
 569 /// Dispatch the valid relocation finding logic to the
 570 /// appropriate handler depending on the object file format.
 571 bool DwarfLinkerForBinary::AddressManager::findValidRelocs(
 572     const object::SectionRef &Section, const object::ObjectFile &Obj,
 573     const DebugMapObject &DMO, std::vector<ValidReloc> &Relocs) {
 574   // Dispatch to the right handler depending on the file type.
 575   if (auto *MachOObj = dyn_cast<object::MachOObjectFile>(&Obj))
 576     findValidRelocsMachO(Section, *MachOObj, DMO, Relocs);
 577   else
 578     Linker.reportWarning(Twine("unsupported object file type: ") +
 579                              Obj.getFileName(),
 580                          DMO.getObjectFilename());
 581   if (Relocs.empty())
 582     return false;
 583
 584   // Sort the relocations by offset. We will walk the DIEs linearly in
 585   // the file, this allows us to just keep an index in the relocation
 586   // array that we advance during our walk, rather than resorting to
 587   // some associative container. See DwarfLinkerForBinary::NextValidReloc.
 588   llvm::sort(Relocs);
 589   return true;
 590 }
 591
 592 /// Look for relocations in the debug_info and debug_addr section that match
 593 /// entries in the debug map. These relocations will drive the Dwarf link by
 594 /// indicating which DIEs refer to symbols present in the linked binary.
 595 /// \returns whether there are any valid relocations in the debug info.
 596 bool DwarfLinkerForBinary::AddressManager::findValidRelocsInDebugSections(
 597     const object::ObjectFile &Obj, const DebugMapObject &DMO) {
 598   // Find the debug_info section.
 599   bool FoundValidRelocs = false;
 600   for (const object::SectionRef &Section : Obj.sections()) {
 601     StringRef SectionName;
 602     if (Expected<StringRef> NameOrErr = Section.getName())
 603       SectionName = *NameOrErr;
 604     else
 605       consumeError(NameOrErr.takeError());
 606
 607     SectionName = SectionName.substr(SectionName.find_first_not_of("._"));
 608     if (SectionName == "debug_info")
 609       FoundValidRelocs |=
 610           findValidRelocs(Section, Obj, DMO, ValidDebugInfoRelocs);
 611     if (SectionName == "debug_addr")
 612       FoundValidRelocs |=
 613           findValidRelocs(Section, Obj, DMO, ValidDebugAddrRelocs);
 614   }
 615   return FoundValidRelocs;
 616 }
 617
 618 std::vector<DwarfLinkerForBinary::AddressManager::ValidReloc>
 619 DwarfLinkerForBinary::AddressManager::getRelocations(
 620     const std::vector<ValidReloc> &Relocs, uint64_t StartPos, uint64_t EndPos) {
 621   std::vector<DwarfLinkerForBinary::AddressManager::ValidReloc> Res;
 622
 623   auto CurReloc = partition_point(Relocs, [StartPos](const ValidReloc &Reloc) {
 624     return Reloc.Offset < StartPos;
 625   });
 626
 627   while (CurReloc != Relocs.end() && CurReloc->Offset >= StartPos &&
 628          CurReloc->Offset < EndPos) {
 629     Res.push_back(*CurReloc);
 630     CurReloc++;
 631   }
 632
 633   return Res;
 634 }
 635
 636 void DwarfLinkerForBinary::AddressManager::printReloc(const ValidReloc &Reloc) {
 637   const auto &Mapping = Reloc.Mapping->getValue();
 638   const uint64_t ObjectAddress = Mapping.ObjectAddress
 639                                      ? uint64_t(*Mapping.ObjectAddress)
 640                                      : std::numeric_limits<uint64_t>::max();
 641
 642   outs() << "Found valid debug map entry: " << Reloc.Mapping->getKey() << "\t"
 643          << format("0x%016" PRIx64 " => 0x%016" PRIx64 "\n", ObjectAddress,
 644                    uint64_t(Mapping.BinaryAddress));
 645 }
 646
 647 void DwarfLinkerForBinary::AddressManager::fillDieInfo(
 648     const ValidReloc &Reloc, CompileUnit::DIEInfo &Info) {
 649   Info.AddrAdjust = relocate(Reloc);
 650   if (Reloc.Mapping->getValue().ObjectAddress)
 651     Info.AddrAdjust -= uint64_t(*Reloc.Mapping->getValue().ObjectAddress);
 652   Info.InDebugMap = true;
 653 }
 654
 655 bool DwarfLinkerForBinary::AddressManager::hasValidRelocationAt(
 656     const std::vector<ValidReloc> &AllRelocs, uint64_t StartOffset,
 657     uint64_t EndOffset, CompileUnit::DIEInfo &Info) {
 658   std::vector<ValidReloc> Relocs =
 659       getRelocations(AllRelocs, StartOffset, EndOffset);
 660
 661   if (Relocs.size() == 0)
 662     return false;
 663
 664   if (Linker.Options.Verbose)
 665     printReloc(Relocs[0]);
 666   fillDieInfo(Relocs[0], Info);
 667
 668   return true;
 669 }
 670
 671 /// Get the starting and ending (exclusive) offset for the
 672 /// attribute with index \p Idx descibed by \p Abbrev. \p Offset is
 673 /// supposed to point to the position of the first attribute described
 674 /// by \p Abbrev.
 675 /// \return [StartOffset, EndOffset) as a pair.
 676 static std::pair<uint64_t, uint64_t>
 677 getAttributeOffsets(const DWARFAbbreviationDeclaration *Abbrev, unsigned Idx,
 678                     uint64_t Offset, const DWARFUnit &Unit) {
 679   DataExtractor Data = Unit.getDebugInfoExtractor();
 680
 681   for (unsigned I = 0; I < Idx; ++I)
 682     DWARFFormValue::skipValue(Abbrev->getFormByIndex(I), Data, &Offset,
 683                               Unit.getFormParams());
 684
 685   uint64_t End = Offset;
 686   DWARFFormValue::skipValue(Abbrev->getFormByIndex(Idx), Data, &End,
 687                             Unit.getFormParams());
 688
 689   return std::make_pair(Offset, End);
 690 }
 691
 692 bool DwarfLinkerForBinary::AddressManager::hasLiveMemoryLocation(
 693     const DWARFDie &DIE, CompileUnit::DIEInfo &MyInfo) {
 694   const auto *Abbrev = DIE.getAbbreviationDeclarationPtr();
 695
 696   Optional<uint32_t> LocationIdx =
 697       Abbrev->findAttributeIndex(dwarf::DW_AT_location);
 698   if (!LocationIdx)
 699     return false;
 700
 701   uint64_t Offset = DIE.getOffset() + getULEB128Size(Abbrev->getCode());
 702   uint64_t LocationOffset, LocationEndOffset;
 703   std::tie(LocationOffset, LocationEndOffset) =
 704       getAttributeOffsets(Abbrev, *LocationIdx, Offset, *DIE.getDwarfUnit());
 705
 706   // FIXME: Support relocations debug_addr.
 707   return hasValidRelocationAt(ValidDebugInfoRelocs, LocationOffset,
 708                               LocationEndOffset, MyInfo);
 709 }
 710
 711 bool DwarfLinkerForBinary::AddressManager::hasLiveAddressRange(
 712     const DWARFDie &DIE, CompileUnit::DIEInfo &MyInfo) {
 713   const auto *Abbrev = DIE.getAbbreviationDeclarationPtr();
 714
 715   Optional<uint32_t> LowPcIdx = Abbrev->findAttributeIndex(dwarf::DW_AT_low_pc);
 716   if (!LowPcIdx)
 717     return false;
 718
 719   dwarf::Form Form = Abbrev->getFormByIndex(*LowPcIdx);
 720
 721   if (Form == dwarf::DW_FORM_addr) {
 722     uint64_t Offset = DIE.getOffset() + getULEB128Size(Abbrev->getCode());
 723     uint64_t LowPcOffset, LowPcEndOffset;
 724     std::tie(LowPcOffset, LowPcEndOffset) =
 725         getAttributeOffsets(Abbrev, *LowPcIdx, Offset, *DIE.getDwarfUnit());
 726     return hasValidRelocationAt(ValidDebugInfoRelocs, LowPcOffset,
 727                                 LowPcEndOffset, MyInfo);
 728   }
 729
 730   if (Form == dwarf::DW_FORM_addrx) {
 731     Optional<DWARFFormValue> AddrValue = DIE.find(dwarf::DW_AT_low_pc);
 732     if (Optional<uint64_t> AddrOffsetSectionBase =
 733             DIE.getDwarfUnit()->getAddrOffsetSectionBase()) {
 734       uint64_t StartOffset = *AddrOffsetSectionBase + AddrValue->getRawUValue();
 735       uint64_t EndOffset =
 736           StartOffset + DIE.getDwarfUnit()->getAddressByteSize();
 737       return hasValidRelocationAt(ValidDebugAddrRelocs, StartOffset, EndOffset,
 738                                   MyInfo);
 739     } else
 740       Linker.reportWarning("no base offset for address table", SrcFileName);
 741   }
 742
 743   return false;
 744 }
 745
 746 uint64_t
 747 DwarfLinkerForBinary::AddressManager::relocate(const ValidReloc &Reloc) const {
 748   return Reloc.Mapping->getValue().BinaryAddress + Reloc.Addend;
 749 }
 750
 751 /// Apply the valid relocations found by findValidRelocs() to
 752 /// the buffer \p Data, taking into account that Data is at \p BaseOffset
 753 /// in the debug_info section.
 754 ///
 755 /// Like for findValidRelocs(), this function must be called with
 756 /// monotonic \p BaseOffset values.
 757 ///
 758 /// \returns whether any reloc has been applied.
 759 bool DwarfLinkerForBinary::AddressManager::applyValidRelocs(
 760     MutableArrayRef<char> Data, uint64_t BaseOffset, bool IsLittleEndian) {
 761   assert(areRelocationsResolved());
 762   std::vector<ValidReloc> Relocs = getRelocations(
 763       ValidDebugInfoRelocs, BaseOffset, BaseOffset + Data.size());
 764
 765   for (const ValidReloc &CurReloc : Relocs) {
 766     assert(CurReloc.Offset - BaseOffset < Data.size());
 767     assert(CurReloc.Offset - BaseOffset + CurReloc.Size <= Data.size());
 768     char Buf[8];
 769     uint64_t Value = relocate(CurReloc);
 770     for (unsigned I = 0; I != CurReloc.Size; ++I) {
 771       unsigned Index = IsLittleEndian ? I : (CurReloc.Size - I - 1);
 772       Buf[I] = uint8_t(Value >> (Index * 8));
 773     }
 774     assert(CurReloc.Size <= sizeof(Buf));
 775     memcpy(&Data[CurReloc.Offset - BaseOffset], Buf, CurReloc.Size);
 776   }
 777
 778   return Relocs.size() > 0;
 779 }
 780
 781 llvm::Expected<uint64_t>
 782 DwarfLinkerForBinary::AddressManager::relocateIndexedAddr(uint64_t StartOffset,
 783                                                           uint64_t EndOffset) {
 784   std::vector<ValidReloc> Relocs =
 785       getRelocations(ValidDebugAddrRelocs, StartOffset, EndOffset);
 786   if (Relocs.size() == 0)
 787     return createStringError(
 788         std::make_error_code(std::errc::invalid_argument),
 789         "no relocation for offset %llu in debug_addr section", StartOffset);
 790
 791   return relocate(Relocs[0]);
 792 }
 793
 794 bool linkDwarf(raw_fd_ostream &OutFile, BinaryHolder &BinHolder,
 795                const DebugMap &DM, LinkOptions Options) {
 796   DwarfLinkerForBinary Linker(OutFile, BinHolder, std::move(Options));
 797   return Linker.link(DM);
 798 }
 799
 800 } // namespace dsymutil
 801 } // namespace llvm