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