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/PointerIntPair.h"
22 #include "llvm/ADT/STLExtras.h"
23 #include "llvm/ADT/SmallString.h"
24 #include "llvm/ADT/StringMap.h"
25 #include "llvm/ADT/StringRef.h"
26 #include "llvm/ADT/Triple.h"
27 #include "llvm/ADT/Twine.h"
28 #include "llvm/BinaryFormat/Dwarf.h"
29 #include "llvm/BinaryFormat/MachO.h"
30 #include "llvm/BinaryFormat/Swift.h"
31 #include "llvm/CodeGen/AccelTable.h"
32 #include "llvm/CodeGen/AsmPrinter.h"
33 #include "llvm/CodeGen/DIE.h"
34 #include "llvm/CodeGen/NonRelocatableStringpool.h"
35 #include "llvm/Config/config.h"
36 #include "llvm/DWARFLinker/DWARFLinkerDeclContext.h"
37 #include "llvm/DebugInfo/DIContext.h"
38 #include "llvm/DebugInfo/DWARF/DWARFAbbreviationDeclaration.h"
39 #include "llvm/DebugInfo/DWARF/DWARFContext.h"
40 #include "llvm/DebugInfo/DWARF/DWARFDataExtractor.h"
41 #include "llvm/DebugInfo/DWARF/DWARFDebugLine.h"
42 #include "llvm/DebugInfo/DWARF/DWARFDebugRangeList.h"
43 #include "llvm/DebugInfo/DWARF/DWARFDie.h"
44 #include "llvm/DebugInfo/DWARF/DWARFFormValue.h"
45 #include "llvm/DebugInfo/DWARF/DWARFSection.h"
46 #include "llvm/DebugInfo/DWARF/DWARFUnit.h"
47 #include "llvm/MC/MCAsmBackend.h"
48 #include "llvm/MC/MCAsmInfo.h"
49 #include "llvm/MC/MCCodeEmitter.h"
50 #include "llvm/MC/MCContext.h"
51 #include "llvm/MC/MCDwarf.h"
52 #include "llvm/MC/MCInstrInfo.h"
53 #include "llvm/MC/MCObjectFileInfo.h"
54 #include "llvm/MC/MCObjectWriter.h"
55 #include "llvm/MC/MCRegisterInfo.h"
56 #include "llvm/MC/MCSection.h"
57 #include "llvm/MC/MCStreamer.h"
58 #include "llvm/MC/MCSubtargetInfo.h"
59 #include "llvm/MC/MCTargetOptions.h"
60 #include "llvm/MC/MCTargetOptionsCommandFlags.h"
61 #include "llvm/MC/TargetRegistry.h"
62 #include "llvm/Object/MachO.h"
63 #include "llvm/Object/ObjectFile.h"
64 #include "llvm/Object/SymbolicFile.h"
65 #include "llvm/Support/Allocator.h"
66 #include "llvm/Support/Casting.h"
67 #include "llvm/Support/Compiler.h"
68 #include "llvm/Support/DJB.h"
69 #include "llvm/Support/DataExtractor.h"
70 #include "llvm/Support/Error.h"
71 #include "llvm/Support/ErrorHandling.h"
72 #include "llvm/Support/ErrorOr.h"
73 #include "llvm/Support/FileSystem.h"
74 #include "llvm/Support/Format.h"
75 #include "llvm/Support/LEB128.h"
76 #include "llvm/Support/MathExtras.h"
77 #include "llvm/Support/MemoryBuffer.h"
78 #include "llvm/Support/Path.h"
79 #include "llvm/Support/ThreadPool.h"
80 #include "llvm/Support/ToolOutputFile.h"
81 #include "llvm/Support/WithColor.h"
82 #include "llvm/Support/raw_ostream.h"
83 #include "llvm/Target/TargetMachine.h"
84 #include "llvm/Target/TargetOptions.h"
85 #include <algorithm>
86 #include <cassert>
87 #include <cinttypes>
88 #include <climits>
89 #include <cstdint>
90 #include <cstdlib>
91 #include <cstring>
92 #include <limits>
93 #include <map>
94 #include <memory>
95 #include <optional>
96 #include <string>
97 #include <system_error>
98 #include <tuple>
99 #include <utility>
100 #include <vector>
101 
102 namespace llvm {
103 
104 static mc::RegisterMCTargetOptionsFlags MOF;
105 
106 namespace dsymutil {
107 
108 static Error copySwiftInterfaces(
109     const std::map<std::string, std::string> &ParseableSwiftInterfaces,
110     StringRef Architecture, const LinkOptions &Options) {
111   std::error_code EC;
112   SmallString<128> InputPath;
113   SmallString<128> Path;
114   sys::path::append(Path, *Options.ResourceDir, "Swift", Architecture);
115   if ((EC = sys::fs::create_directories(Path.str(), true,
116                                         sys::fs::perms::all_all)))
117     return make_error<StringError>(
118         "cannot create directory: " + toString(errorCodeToError(EC)), EC);
119   unsigned BaseLength = Path.size();
120 
121   for (auto &I : ParseableSwiftInterfaces) {
122     StringRef ModuleName = I.first;
123     StringRef InterfaceFile = I.second;
124     if (!Options.PrependPath.empty()) {
125       InputPath.clear();
126       sys::path::append(InputPath, Options.PrependPath, InterfaceFile);
127       InterfaceFile = InputPath;
128     }
129     sys::path::append(Path, ModuleName);
130     Path.append(".swiftinterface");
131     if (Options.Verbose)
132       outs() << "copy parseable Swift interface " << InterfaceFile << " -> "
133              << Path.str() << '\n';
134 
135     // copy_file attempts an APFS clone first, so this should be cheap.
136     if ((EC = sys::fs::copy_file(InterfaceFile, Path.str())))
137       warn(Twine("cannot copy parseable Swift interface ") + InterfaceFile +
138            ": " + toString(errorCodeToError(EC)));
139     Path.resize(BaseLength);
140   }
141   return Error::success();
142 }
143 
144 /// Report a warning to the user, optionally including information about a
145 /// specific \p DIE related to the warning.
146 void DwarfLinkerForBinary::reportWarning(const Twine &Warning,
147                                          StringRef Context,
148                                          const DWARFDie *DIE) const {
149 
150   warn(Warning, Context);
151 
152   if (!Options.Verbose || !DIE)
153     return;
154 
155   DIDumpOptions DumpOpts;
156   DumpOpts.ChildRecurseDepth = 0;
157   DumpOpts.Verbose = Options.Verbose;
158 
159   WithColor::note() << "    in DIE:\n";
160   DIE->dump(errs(), 6 /* Indent */, DumpOpts);
161 }
162 
163 bool DwarfLinkerForBinary::createStreamer(const Triple &TheTriple,
164                                           raw_fd_ostream &OutFile) {
165   if (Options.NoOutput)
166     return true;
167 
168   Streamer = std::make_unique<DwarfStreamer>(
169       Options.FileType, OutFile, Options.Translator,
170       [&](const Twine &Error, StringRef Context, const DWARFDie *) {
171         error(Error, Context);
172       },
173       [&](const Twine &Warning, StringRef Context, const DWARFDie *) {
174         warn(Warning, Context);
175       });
176   return Streamer->init(TheTriple, "__DWARF");
177 }
178 
179 ErrorOr<const object::ObjectFile &>
180 DwarfLinkerForBinary::loadObject(const DebugMapObject &Obj,
181                                  const Triple &Triple) {
182   auto ObjectEntry =
183       BinHolder.getObjectEntry(Obj.getObjectFilename(), Obj.getTimestamp());
184   if (!ObjectEntry) {
185     auto Err = ObjectEntry.takeError();
186     reportWarning(Twine(Obj.getObjectFilename()) + ": " +
187                       toString(std::move(Err)),
188                   Obj.getObjectFilename());
189     return errorToErrorCode(std::move(Err));
190   }
191 
192   auto Object = ObjectEntry->getObject(Triple);
193   if (!Object) {
194     auto Err = Object.takeError();
195     reportWarning(Twine(Obj.getObjectFilename()) + ": " +
196                       toString(std::move(Err)),
197                   Obj.getObjectFilename());
198     return errorToErrorCode(std::move(Err));
199   }
200 
201   return *Object;
202 }
203 
204 static Error remarksErrorHandler(const DebugMapObject &DMO,
205                                  DwarfLinkerForBinary &Linker,
206                                  std::unique_ptr<FileError> FE) {
207   bool IsArchive = DMO.getObjectFilename().endswith(")");
208   // Don't report errors for missing remark files from static
209   // archives.
210   if (!IsArchive)
211     return Error(std::move(FE));
212 
213   std::string Message = FE->message();
214   Error E = FE->takeError();
215   Error NewE = handleErrors(std::move(E), [&](std::unique_ptr<ECError> EC) {
216     if (EC->convertToErrorCode() != std::errc::no_such_file_or_directory)
217       return Error(std::move(EC));
218 
219     Linker.reportWarning(Message, DMO.getObjectFilename());
220     return Error(Error::success());
221   });
222 
223   if (!NewE)
224     return Error::success();
225 
226   return createFileError(FE->getFileName(), std::move(NewE));
227 }
228 
229 static Error emitRemarks(const LinkOptions &Options, StringRef BinaryPath,
230                          StringRef ArchName, const remarks::RemarkLinker &RL) {
231   // Make sure we don't create the directories and the file if there is nothing
232   // to serialize.
233   if (RL.empty())
234     return Error::success();
235 
236   SmallString<128> InputPath;
237   SmallString<128> Path;
238   // Create the "Remarks" directory in the "Resources" directory.
239   sys::path::append(Path, *Options.ResourceDir, "Remarks");
240   if (std::error_code EC = sys::fs::create_directories(Path.str(), true,
241                                                        sys::fs::perms::all_all))
242     return errorCodeToError(EC);
243 
244   // Append the file name.
245   // For fat binaries, also append a dash and the architecture name.
246   sys::path::append(Path, sys::path::filename(BinaryPath));
247   if (Options.NumDebugMaps > 1) {
248     // More than one debug map means we have a fat binary.
249     Path += '-';
250     Path += ArchName;
251   }
252 
253   std::error_code EC;
254   raw_fd_ostream OS(Options.NoOutput ? "-" : Path.str(), EC,
255                     Options.RemarksFormat == remarks::Format::Bitstream
256                         ? sys::fs::OF_None
257                         : sys::fs::OF_Text);
258   if (EC)
259     return errorCodeToError(EC);
260 
261   if (Error E = RL.serialize(OS, Options.RemarksFormat))
262     return E;
263 
264   return Error::success();
265 }
266 
267 ErrorOr<DWARFFile &>
268 DwarfLinkerForBinary::loadObject(const DebugMapObject &Obj,
269                                  const DebugMap &DebugMap,
270                                  remarks::RemarkLinker &RL) {
271   auto ErrorOrObj = loadObject(Obj, DebugMap.getTriple());
272 
273   if (ErrorOrObj) {
274     ContextForLinking.push_back(
275         std::unique_ptr<DWARFContext>(DWARFContext::create(*ErrorOrObj)));
276     AddressMapForLinking.push_back(
277         std::make_unique<AddressManager>(*this, *ErrorOrObj, Obj));
278 
279     ObjectsForLinking.push_back(std::make_unique<DWARFFile>(
280         Obj.getObjectFilename(), ContextForLinking.back().get(),
281         AddressMapForLinking.back().get(),
282         Obj.empty() ? Obj.getWarnings() : EmptyWarnings));
283 
284     Error E = RL.link(*ErrorOrObj);
285     if (Error NewE = handleErrors(
286             std::move(E), [&](std::unique_ptr<FileError> EC) -> Error {
287               return remarksErrorHandler(Obj, *this, std::move(EC));
288             }))
289       return errorToErrorCode(std::move(NewE));
290 
291     return *ObjectsForLinking.back();
292   }
293 
294   return ErrorOrObj.getError();
295 }
296 
297 static bool binaryHasStrippableSwiftReflectionSections(
298     const DebugMap &Map, const LinkOptions &Options, BinaryHolder &BinHolder) {
299   // If the input binary has strippable swift5 reflection sections, there is no
300   // need to copy them to the .dSYM. Only copy them for binaries where the
301   // linker omitted the reflection metadata.
302   if (!Map.getBinaryPath().empty() &&
303       Options.FileType == OutputFileType::Object) {
304 
305     auto ObjectEntry = BinHolder.getObjectEntry(Map.getBinaryPath());
306     // If ObjectEntry or Object has an error, no binary exists, therefore no
307     // reflection sections exist.
308     if (!ObjectEntry) {
309       // Any errors will be diagnosed later in the main loop, ignore them here.
310       llvm::consumeError(ObjectEntry.takeError());
311       return false;
312     }
313 
314     auto Object =
315         ObjectEntry->getObjectAs<object::MachOObjectFile>(Map.getTriple());
316     if (!Object) {
317       // Any errors will be diagnosed later in the main loop, ignore them here.
318       llvm::consumeError(Object.takeError());
319       return false;
320     }
321 
322     for (auto &Section : Object->sections()) {
323       llvm::Expected<llvm::StringRef> NameOrErr =
324           Object->getSectionName(Section.getRawDataRefImpl());
325       if (!NameOrErr) {
326         llvm::consumeError(NameOrErr.takeError());
327         continue;
328       }
329       NameOrErr->consume_back("__TEXT");
330       auto ReflectionSectionKind =
331           Object->mapReflectionSectionNameToEnumValue(*NameOrErr);
332       if (Object->isReflectionSectionStrippable(ReflectionSectionKind)) {
333         return true;
334       }
335     }
336   }
337   return false;
338 }
339 
340 /// Calculate the start of the strippable swift reflection sections in Dwarf.
341 /// Note that there's an assumption that the reflection sections will appear
342 /// in alphabetic order.
343 static std::vector<uint64_t>
344 calculateStartOfStrippableReflectionSections(const DebugMap &Map) {
345   using llvm::binaryformat::Swift5ReflectionSectionKind;
346   uint64_t AssocTySize = 0;
347   uint64_t FieldMdSize = 0;
348   for (const auto &Obj : Map.objects()) {
349     auto OF =
350         llvm::object::ObjectFile::createObjectFile(Obj->getObjectFilename());
351     if (!OF) {
352       llvm::consumeError(OF.takeError());
353       continue;
354     }
355     if (auto *MO = dyn_cast<llvm::object::MachOObjectFile>(OF->getBinary())) {
356       for (auto &Section : MO->sections()) {
357         llvm::Expected<llvm::StringRef> NameOrErr =
358             MO->getSectionName(Section.getRawDataRefImpl());
359         if (!NameOrErr) {
360           llvm::consumeError(NameOrErr.takeError());
361           continue;
362         }
363         NameOrErr->consume_back("__TEXT");
364         auto ReflSectionKind =
365             MO->mapReflectionSectionNameToEnumValue(*NameOrErr);
366         switch (ReflSectionKind) {
367         case Swift5ReflectionSectionKind::assocty:
368           AssocTySize += Section.getSize();
369           break;
370         case Swift5ReflectionSectionKind::fieldmd:
371           FieldMdSize += Section.getSize();
372           break;
373         default:
374           break;
375         }
376       }
377     }
378   }
379   // Initialize the vector with enough space to fit every reflection section
380   // kind.
381   std::vector<uint64_t> SectionToOffset(Swift5ReflectionSectionKind::last, 0);
382   SectionToOffset[Swift5ReflectionSectionKind::assocty] = 0;
383   SectionToOffset[Swift5ReflectionSectionKind::fieldmd] =
384       llvm::alignTo(AssocTySize, 4);
385   SectionToOffset[Swift5ReflectionSectionKind::reflstr] = llvm::alignTo(
386       SectionToOffset[Swift5ReflectionSectionKind::fieldmd] + FieldMdSize, 4);
387 
388   return SectionToOffset;
389 }
390 
391 void DwarfLinkerForBinary::collectRelocationsToApplyToSwiftReflectionSections(
392     const object::SectionRef &Section, StringRef &Contents,
393     const llvm::object::MachOObjectFile *MO,
394     const std::vector<uint64_t> &SectionToOffsetInDwarf,
395     const llvm::dsymutil::DebugMapObject *Obj,
396     std::vector<MachOUtils::DwarfRelocationApplicationInfo> &RelocationsToApply)
397     const {
398   for (auto It = Section.relocation_begin(); It != Section.relocation_end();
399        ++It) {
400     object::DataRefImpl RelocDataRef = It->getRawDataRefImpl();
401     MachO::any_relocation_info MachOReloc = MO->getRelocation(RelocDataRef);
402 
403     if (!object::MachOObjectFile::isMachOPairedReloc(
404             MO->getAnyRelocationType(MachOReloc), MO->getArch())) {
405       reportWarning(
406           "Unimplemented relocation type in strippable reflection section ",
407           Obj->getObjectFilename());
408       continue;
409     }
410 
411     auto CalculateAddressOfSymbolInDwarfSegment =
412         [&]() -> std::optional<int64_t> {
413       auto Symbol = It->getSymbol();
414       auto SymbolAbsoluteAddress = Symbol->getAddress();
415       if (!SymbolAbsoluteAddress)
416         return {};
417       auto Section = Symbol->getSection();
418       if (!Section) {
419         llvm::consumeError(Section.takeError());
420         return {};
421       }
422 
423       if ((*Section)->getObject()->section_end() == *Section)
424         return {};
425 
426       auto SectionStart = (*Section)->getAddress();
427       auto SymbolAddressInSection = *SymbolAbsoluteAddress - SectionStart;
428       auto SectionName = (*Section)->getName();
429       if (!SectionName)
430         return {};
431       auto ReflSectionKind =
432           MO->mapReflectionSectionNameToEnumValue(*SectionName);
433 
434       int64_t SectionStartInLinkedBinary =
435           SectionToOffsetInDwarf[ReflSectionKind];
436 
437       auto Addr = SectionStartInLinkedBinary + SymbolAddressInSection;
438       return Addr;
439     };
440 
441     // The first symbol should always be in the section we're currently
442     // iterating over.
443     auto FirstSymbolAddress = CalculateAddressOfSymbolInDwarfSegment();
444     ++It;
445 
446     bool ShouldSubtractDwarfVM = false;
447     // For the second symbol there are two possibilities.
448     std::optional<int64_t> SecondSymbolAddress;
449     auto Sym = It->getSymbol();
450     if (Sym != MO->symbol_end()) {
451       Expected<StringRef> SymbolName = Sym->getName();
452       if (SymbolName) {
453         if (const auto *Mapping = Obj->lookupSymbol(*SymbolName)) {
454           // First possibility: the symbol exists in the binary, and exists in a
455           // non-strippable section (for example, typeref, or __TEXT,__const),
456           // in which case we look up its address in the  binary, which dsymutil
457           // will copy verbatim.
458           SecondSymbolAddress = Mapping->getValue().BinaryAddress;
459           // Since the symbols live in different segments, we have to substract
460           // the start of the Dwarf's vmaddr so the value calculated points to
461           // the correct place.
462           ShouldSubtractDwarfVM = true;
463         }
464       }
465     }
466 
467     if (!SecondSymbolAddress) {
468       // Second possibility, this symbol is not present in the main binary, and
469       // must be in one of the strippable sections (for example, reflstr).
470       // Calculate its address in the same way as we did the first one.
471       SecondSymbolAddress = CalculateAddressOfSymbolInDwarfSegment();
472     }
473 
474     if (!FirstSymbolAddress || !SecondSymbolAddress)
475       continue;
476 
477     auto SectionName = Section.getName();
478     if (!SectionName)
479       continue;
480 
481     int32_t Addend;
482     memcpy(&Addend, Contents.data() + It->getOffset(), sizeof(int32_t));
483     int32_t Value = (*SecondSymbolAddress + Addend) - *FirstSymbolAddress;
484     auto ReflSectionKind =
485         MO->mapReflectionSectionNameToEnumValue(*SectionName);
486     uint64_t AddressFromDwarfVM =
487         SectionToOffsetInDwarf[ReflSectionKind] + It->getOffset();
488     RelocationsToApply.emplace_back(AddressFromDwarfVM, Value,
489                                     ShouldSubtractDwarfVM);
490   }
491 }
492 
493 void DwarfLinkerForBinary::copySwiftReflectionMetadata(
494     const llvm::dsymutil::DebugMapObject *Obj, DwarfStreamer *Streamer,
495     std::vector<uint64_t> &SectionToOffsetInDwarf,
496     std::vector<MachOUtils::DwarfRelocationApplicationInfo>
497         &RelocationsToApply) {
498   using binaryformat::Swift5ReflectionSectionKind;
499   auto OF =
500       llvm::object::ObjectFile::createObjectFile(Obj->getObjectFilename());
501   if (!OF) {
502     llvm::consumeError(OF.takeError());
503     return;
504   }
505   if (auto *MO = dyn_cast<llvm::object::MachOObjectFile>(OF->getBinary())) {
506     // Collect the swift reflection sections before emitting them. This is
507     // done so we control the order they're emitted.
508     std::array<std::optional<object::SectionRef>,
509                Swift5ReflectionSectionKind::last + 1>
510         SwiftSections;
511     for (auto &Section : MO->sections()) {
512       llvm::Expected<llvm::StringRef> NameOrErr =
513           MO->getSectionName(Section.getRawDataRefImpl());
514       if (!NameOrErr) {
515         llvm::consumeError(NameOrErr.takeError());
516         continue;
517       }
518       NameOrErr->consume_back("__TEXT");
519       auto ReflSectionKind =
520           MO->mapReflectionSectionNameToEnumValue(*NameOrErr);
521       if (MO->isReflectionSectionStrippable(ReflSectionKind))
522         SwiftSections[ReflSectionKind] = Section;
523     }
524     // Make sure we copy the sections in alphabetic order.
525     auto SectionKindsToEmit = {Swift5ReflectionSectionKind::assocty,
526                                Swift5ReflectionSectionKind::fieldmd,
527                                Swift5ReflectionSectionKind::reflstr};
528     for (auto SectionKind : SectionKindsToEmit) {
529       if (!SwiftSections[SectionKind])
530         continue;
531       auto &Section = *SwiftSections[SectionKind];
532       llvm::Expected<llvm::StringRef> SectionContents = Section.getContents();
533       if (!SectionContents)
534         continue;
535       const auto *MO =
536           llvm::cast<llvm::object::MachOObjectFile>(Section.getObject());
537       collectRelocationsToApplyToSwiftReflectionSections(
538           Section, *SectionContents, MO, SectionToOffsetInDwarf, Obj,
539           RelocationsToApply);
540       // Update the section start with the current section's contribution, so
541       // the next section we copy from a different .o file points to the correct
542       // place.
543       SectionToOffsetInDwarf[SectionKind] += Section.getSize();
544       Streamer->emitSwiftReflectionSection(SectionKind, *SectionContents,
545                                            Section.getAlignment().value(),
546                                            Section.getSize());
547     }
548   }
549 }
550 
551 bool DwarfLinkerForBinary::link(const DebugMap &Map) {
552   if (!createStreamer(Map.getTriple(), OutFile))
553     return false;
554 
555   ObjectsForLinking.clear();
556   ContextForLinking.clear();
557   AddressMapForLinking.clear();
558 
559   DebugMap DebugMap(Map.getTriple(), Map.getBinaryPath());
560 
561   DWARFLinker GeneralLinker(Streamer.get(), DwarfLinkerClient::Dsymutil);
562 
563   remarks::RemarkLinker RL;
564   if (!Options.RemarksPrependPath.empty())
565     RL.setExternalFilePrependPath(Options.RemarksPrependPath);
566   GeneralLinker.setObjectPrefixMap(&Options.ObjectPrefixMap);
567 
568   std::function<StringRef(StringRef)> TranslationLambda = [&](StringRef Input) {
569     assert(Options.Translator);
570     return Options.Translator(Input);
571   };
572 
573   GeneralLinker.setVerbosity(Options.Verbose);
574   GeneralLinker.setStatistics(Options.Statistics);
575   GeneralLinker.setVerifyInputDWARF(Options.VerifyInputDWARF);
576   GeneralLinker.setNoOutput(Options.NoOutput);
577   GeneralLinker.setNoODR(Options.NoODR);
578   GeneralLinker.setUpdate(Options.Update);
579   GeneralLinker.setNumThreads(Options.Threads);
580   GeneralLinker.setPrependPath(Options.PrependPath);
581   GeneralLinker.setKeepFunctionForStatic(Options.KeepFunctionForStatic);
582   if (Options.Translator)
583     GeneralLinker.setStringsTranslator(TranslationLambda);
584   GeneralLinker.setWarningHandler(
585       [&](const Twine &Warning, StringRef Context, const DWARFDie *DIE) {
586         reportWarning(Warning, Context, DIE);
587       });
588   GeneralLinker.setErrorHandler(
589       [&](const Twine &Error, StringRef Context, const DWARFDie *) {
590         error(Error, Context);
591       });
592   objFileLoader Loader = [&DebugMap, &RL,
593                           this](StringRef ContainerName,
594                                 StringRef Path) -> ErrorOr<DWARFFile &> {
595     auto &Obj = DebugMap.addDebugMapObject(
596         Path, sys::TimePoint<std::chrono::seconds>(), MachO::N_OSO);
597 
598     if (auto ErrorOrObj = loadObject(Obj, DebugMap, RL)) {
599       return *ErrorOrObj;
600     } else {
601       // Try and emit more helpful warnings by applying some heuristics.
602       StringRef ObjFile = ContainerName;
603       bool IsClangModule = sys::path::extension(Path).equals(".pcm");
604       bool IsArchive = ObjFile.endswith(")");
605 
606       if (IsClangModule) {
607         StringRef ModuleCacheDir = sys::path::parent_path(Path);
608         if (sys::fs::exists(ModuleCacheDir)) {
609           // If the module's parent directory exists, we assume that the
610           // module cache has expired and was pruned by clang.  A more
611           // adventurous dsymutil would invoke clang to rebuild the module
612           // now.
613           if (!ModuleCacheHintDisplayed) {
614             WithColor::note()
615                 << "The clang module cache may have expired since "
616                    "this object file was built. Rebuilding the "
617                    "object file will rebuild the module cache.\n";
618             ModuleCacheHintDisplayed = true;
619           }
620         } else if (IsArchive) {
621           // If the module cache directory doesn't exist at all and the
622           // object file is inside a static library, we assume that the
623           // static library was built on a different machine. We don't want
624           // to discourage module debugging for convenience libraries within
625           // a project though.
626           if (!ArchiveHintDisplayed) {
627             WithColor::note()
628                 << "Linking a static library that was built with "
629                    "-gmodules, but the module cache was not found.  "
630                    "Redistributable static libraries should never be "
631                    "built with module debugging enabled.  The debug "
632                    "experience will be degraded due to incomplete "
633                    "debug information.\n";
634             ArchiveHintDisplayed = true;
635           }
636         }
637       }
638 
639       return ErrorOrObj.getError();
640     }
641 
642     llvm_unreachable("Unhandled DebugMap object");
643   };
644   GeneralLinker.setSwiftInterfacesMap(&ParseableSwiftInterfaces);
645   bool ReflectionSectionsPresentInBinary = false;
646   // If there is no output specified, no point in checking the binary for swift5
647   // reflection sections.
648   if (!Options.NoOutput) {
649     ReflectionSectionsPresentInBinary =
650         binaryHasStrippableSwiftReflectionSections(Map, Options, BinHolder);
651   }
652 
653   std::vector<MachOUtils::DwarfRelocationApplicationInfo> RelocationsToApply;
654   if (!Options.NoOutput && !ReflectionSectionsPresentInBinary) {
655     auto SectionToOffsetInDwarf =
656         calculateStartOfStrippableReflectionSections(Map);
657     for (const auto &Obj : Map.objects())
658       copySwiftReflectionMetadata(Obj.get(), Streamer.get(),
659                                   SectionToOffsetInDwarf, RelocationsToApply);
660   }
661 
662   uint16_t MaxDWARFVersion = 0;
663   std::function<void(const DWARFUnit &Unit)> OnCUDieLoaded =
664       [&MaxDWARFVersion](const DWARFUnit &Unit) {
665         MaxDWARFVersion = std::max(Unit.getVersion(), MaxDWARFVersion);
666       };
667 
668   for (const auto &Obj : Map.objects()) {
669     // N_AST objects (swiftmodule files) should get dumped directly into the
670     // appropriate DWARF section.
671     if (Obj->getType() == MachO::N_AST) {
672       if (Options.Verbose)
673         outs() << "DEBUG MAP OBJECT: " << Obj->getObjectFilename() << "\n";
674 
675       StringRef File = Obj->getObjectFilename();
676       auto ErrorOrMem = MemoryBuffer::getFile(File);
677       if (!ErrorOrMem) {
678         warn("Could not open '" + File + "'\n");
679         continue;
680       }
681       sys::fs::file_status Stat;
682       if (auto Err = sys::fs::status(File, Stat)) {
683         warn(Err.message());
684         continue;
685       }
686       if (!Options.NoTimestamp) {
687         // The modification can have sub-second precision so we need to cast
688         // away the extra precision that's not present in the debug map.
689         auto ModificationTime =
690             std::chrono::time_point_cast<std::chrono::seconds>(
691                 Stat.getLastModificationTime());
692         if (Obj->getTimestamp() != sys::TimePoint<>() &&
693             ModificationTime != Obj->getTimestamp()) {
694           // Not using the helper here as we can easily stream TimePoint<>.
695           WithColor::warning()
696               << File << ": timestamp mismatch between swift interface file ("
697               << sys::TimePoint<>(ModificationTime) << ") and debug map ("
698               << sys::TimePoint<>(Obj->getTimestamp()) << ")\n";
699           continue;
700         }
701       }
702 
703       // Copy the module into the .swift_ast section.
704       if (!Options.NoOutput)
705         Streamer->emitSwiftAST((*ErrorOrMem)->getBuffer());
706 
707       continue;
708     }
709 
710     if (auto ErrorOrObj = loadObject(*Obj, Map, RL))
711       GeneralLinker.addObjectFile(*ErrorOrObj, Loader, OnCUDieLoaded);
712     else {
713       ObjectsForLinking.push_back(std::make_unique<DWARFFile>(
714           Obj->getObjectFilename(), nullptr, nullptr,
715           Obj->empty() ? Obj->getWarnings() : EmptyWarnings));
716       GeneralLinker.addObjectFile(*ObjectsForLinking.back());
717     }
718   }
719 
720   // If we haven't seen any CUs, pick an arbitrary valid Dwarf version anyway.
721   if (MaxDWARFVersion == 0)
722     MaxDWARFVersion = 3;
723 
724   if (Error E = GeneralLinker.setTargetDWARFVersion(MaxDWARFVersion))
725     return error(toString(std::move(E)));
726 
727   switch (Options.TheAccelTableKind) {
728   case DsymutilAccelTableKind::Apple:
729     GeneralLinker.addAccelTableKind(DwarfLinkerAccelTableKind::Apple);
730     break;
731   case DsymutilAccelTableKind::Dwarf:
732     GeneralLinker.addAccelTableKind(DwarfLinkerAccelTableKind::DebugNames);
733     break;
734   case DsymutilAccelTableKind::Pub:
735     GeneralLinker.addAccelTableKind(DwarfLinkerAccelTableKind::Pub);
736     break;
737   case DsymutilAccelTableKind::Default:
738     if (MaxDWARFVersion >= 5)
739       GeneralLinker.addAccelTableKind(DwarfLinkerAccelTableKind::DebugNames);
740     else
741       GeneralLinker.addAccelTableKind(DwarfLinkerAccelTableKind::Apple);
742     break;
743   case DsymutilAccelTableKind::None:
744     // Nothing to do.
745     break;
746   }
747 
748   // link debug info for loaded object files.
749   if (Error E = GeneralLinker.link())
750     return error(toString(std::move(E)));
751 
752   StringRef ArchName = Map.getTriple().getArchName();
753   if (Error E = emitRemarks(Options, Map.getBinaryPath(), ArchName, RL))
754     return error(toString(std::move(E)));
755 
756   if (Options.NoOutput)
757     return true;
758 
759   if (Options.ResourceDir && !ParseableSwiftInterfaces.empty()) {
760     StringRef ArchName = Triple::getArchTypeName(Map.getTriple().getArch());
761     if (auto E =
762             copySwiftInterfaces(ParseableSwiftInterfaces, ArchName, Options))
763       return error(toString(std::move(E)));
764   }
765 
766   if (Map.getTriple().isOSDarwin() && !Map.getBinaryPath().empty() &&
767       Options.FileType == OutputFileType::Object)
768     return MachOUtils::generateDsymCompanion(
769         Options.VFS, Map, Options.Translator,
770         *Streamer->getAsmPrinter().OutStreamer, OutFile, RelocationsToApply);
771 
772   Streamer->finish();
773   return true;
774 }
775 
776 /// Iterate over the relocations of the given \p Section and
777 /// store the ones that correspond to debug map entries into the
778 /// ValidRelocs array.
779 void DwarfLinkerForBinary::AddressManager::findValidRelocsMachO(
780     const object::SectionRef &Section, const object::MachOObjectFile &Obj,
781     const DebugMapObject &DMO, std::vector<ValidReloc> &ValidRelocs) {
782   Expected<StringRef> ContentsOrErr = Section.getContents();
783   if (!ContentsOrErr) {
784     consumeError(ContentsOrErr.takeError());
785     Linker.reportWarning("error reading section", DMO.getObjectFilename());
786     return;
787   }
788   DataExtractor Data(*ContentsOrErr, Obj.isLittleEndian(), 0);
789   bool SkipNext = false;
790 
791   for (const object::RelocationRef &Reloc : Section.relocations()) {
792     if (SkipNext) {
793       SkipNext = false;
794       continue;
795     }
796 
797     object::DataRefImpl RelocDataRef = Reloc.getRawDataRefImpl();
798     MachO::any_relocation_info MachOReloc = Obj.getRelocation(RelocDataRef);
799 
800     if (object::MachOObjectFile::isMachOPairedReloc(Obj.getAnyRelocationType(MachOReloc),
801                            Obj.getArch())) {
802       SkipNext = true;
803       Linker.reportWarning("unsupported relocation in " + *Section.getName() +
804                                " section.",
805                            DMO.getObjectFilename());
806       continue;
807     }
808 
809     unsigned RelocSize = 1 << Obj.getAnyRelocationLength(MachOReloc);
810     uint64_t Offset64 = Reloc.getOffset();
811     if ((RelocSize != 4 && RelocSize != 8)) {
812       Linker.reportWarning("unsupported relocation in " + *Section.getName() +
813                                " section.",
814                            DMO.getObjectFilename());
815       continue;
816     }
817     uint64_t OffsetCopy = Offset64;
818     // Mach-o uses REL relocations, the addend is at the relocation offset.
819     uint64_t Addend = Data.getUnsigned(&OffsetCopy, RelocSize);
820     uint64_t SymAddress;
821     int64_t SymOffset;
822 
823     if (Obj.isRelocationScattered(MachOReloc)) {
824       // The address of the base symbol for scattered relocations is
825       // stored in the reloc itself. The actual addend will store the
826       // base address plus the offset.
827       SymAddress = Obj.getScatteredRelocationValue(MachOReloc);
828       SymOffset = int64_t(Addend) - SymAddress;
829     } else {
830       SymAddress = Addend;
831       SymOffset = 0;
832     }
833 
834     auto Sym = Reloc.getSymbol();
835     if (Sym != Obj.symbol_end()) {
836       Expected<StringRef> SymbolName = Sym->getName();
837       if (!SymbolName) {
838         consumeError(SymbolName.takeError());
839         Linker.reportWarning("error getting relocation symbol name.",
840                              DMO.getObjectFilename());
841         continue;
842       }
843       if (const auto *Mapping = DMO.lookupSymbol(*SymbolName))
844         ValidRelocs.emplace_back(Offset64, RelocSize, Addend, Mapping);
845     } else if (const auto *Mapping = DMO.lookupObjectAddress(SymAddress)) {
846       // Do not store the addend. The addend was the address of the symbol in
847       // the object file, the address in the binary that is stored in the debug
848       // map doesn't need to be offset.
849       ValidRelocs.emplace_back(Offset64, RelocSize, SymOffset, Mapping);
850     }
851   }
852 }
853 
854 /// Dispatch the valid relocation finding logic to the
855 /// appropriate handler depending on the object file format.
856 bool DwarfLinkerForBinary::AddressManager::findValidRelocs(
857     const object::SectionRef &Section, const object::ObjectFile &Obj,
858     const DebugMapObject &DMO, std::vector<ValidReloc> &Relocs) {
859   // Dispatch to the right handler depending on the file type.
860   if (auto *MachOObj = dyn_cast<object::MachOObjectFile>(&Obj))
861     findValidRelocsMachO(Section, *MachOObj, DMO, Relocs);
862   else
863     Linker.reportWarning(Twine("unsupported object file type: ") +
864                              Obj.getFileName(),
865                          DMO.getObjectFilename());
866   if (Relocs.empty())
867     return false;
868 
869   // Sort the relocations by offset. We will walk the DIEs linearly in
870   // the file, this allows us to just keep an index in the relocation
871   // array that we advance during our walk, rather than resorting to
872   // some associative container. See DwarfLinkerForBinary::NextValidReloc.
873   llvm::sort(Relocs);
874   return true;
875 }
876 
877 /// Look for relocations in the debug_info and debug_addr section that match
878 /// entries in the debug map. These relocations will drive the Dwarf link by
879 /// indicating which DIEs refer to symbols present in the linked binary.
880 /// \returns whether there are any valid relocations in the debug info.
881 bool DwarfLinkerForBinary::AddressManager::findValidRelocsInDebugSections(
882     const object::ObjectFile &Obj, const DebugMapObject &DMO) {
883   // Find the debug_info section.
884   bool FoundValidRelocs = false;
885   for (const object::SectionRef &Section : Obj.sections()) {
886     StringRef SectionName;
887     if (Expected<StringRef> NameOrErr = Section.getName())
888       SectionName = *NameOrErr;
889     else
890       consumeError(NameOrErr.takeError());
891 
892     SectionName = SectionName.substr(SectionName.find_first_not_of("._"));
893     if (SectionName == "debug_info")
894       FoundValidRelocs |=
895           findValidRelocs(Section, Obj, DMO, ValidDebugInfoRelocs);
896     if (SectionName == "debug_addr")
897       FoundValidRelocs |=
898           findValidRelocs(Section, Obj, DMO, ValidDebugAddrRelocs);
899   }
900   return FoundValidRelocs;
901 }
902 
903 std::vector<DwarfLinkerForBinary::AddressManager::ValidReloc>
904 DwarfLinkerForBinary::AddressManager::getRelocations(
905     const std::vector<ValidReloc> &Relocs, uint64_t StartPos, uint64_t EndPos) {
906   std::vector<DwarfLinkerForBinary::AddressManager::ValidReloc> Res;
907 
908   auto CurReloc = partition_point(Relocs, [StartPos](const ValidReloc &Reloc) {
909     return Reloc.Offset < StartPos;
910   });
911 
912   while (CurReloc != Relocs.end() && CurReloc->Offset >= StartPos &&
913          CurReloc->Offset < EndPos) {
914     Res.push_back(*CurReloc);
915     CurReloc++;
916   }
917 
918   return Res;
919 }
920 
921 void DwarfLinkerForBinary::AddressManager::printReloc(const ValidReloc &Reloc) {
922   const auto &Mapping = Reloc.Mapping->getValue();
923   const uint64_t ObjectAddress = Mapping.ObjectAddress
924                                      ? uint64_t(*Mapping.ObjectAddress)
925                                      : std::numeric_limits<uint64_t>::max();
926 
927   outs() << "Found valid debug map entry: " << Reloc.Mapping->getKey() << "\t"
928          << format("0x%016" PRIx64 " => 0x%016" PRIx64 "\n", ObjectAddress,
929                    uint64_t(Mapping.BinaryAddress));
930 }
931 
932 void DwarfLinkerForBinary::AddressManager::fillDieInfo(
933     const ValidReloc &Reloc, CompileUnit::DIEInfo &Info) {
934   Info.AddrAdjust = relocate(Reloc);
935   if (Reloc.Mapping->getValue().ObjectAddress)
936     Info.AddrAdjust -= uint64_t(*Reloc.Mapping->getValue().ObjectAddress);
937   Info.InDebugMap = true;
938 }
939 
940 bool DwarfLinkerForBinary::AddressManager::hasValidRelocationAt(
941     const std::vector<ValidReloc> &AllRelocs, uint64_t StartOffset,
942     uint64_t EndOffset, CompileUnit::DIEInfo &Info) {
943   std::vector<ValidReloc> Relocs =
944       getRelocations(AllRelocs, StartOffset, EndOffset);
945 
946   if (Relocs.size() == 0)
947     return false;
948 
949   if (Linker.Options.Verbose)
950     printReloc(Relocs[0]);
951   fillDieInfo(Relocs[0], Info);
952 
953   return true;
954 }
955 
956 /// Get the starting and ending (exclusive) offset for the
957 /// attribute with index \p Idx descibed by \p Abbrev. \p Offset is
958 /// supposed to point to the position of the first attribute described
959 /// by \p Abbrev.
960 /// \return [StartOffset, EndOffset) as a pair.
961 static std::pair<uint64_t, uint64_t>
962 getAttributeOffsets(const DWARFAbbreviationDeclaration *Abbrev, unsigned Idx,
963                     uint64_t Offset, const DWARFUnit &Unit) {
964   DataExtractor Data = Unit.getDebugInfoExtractor();
965 
966   for (unsigned I = 0; I < Idx; ++I)
967     DWARFFormValue::skipValue(Abbrev->getFormByIndex(I), Data, &Offset,
968                               Unit.getFormParams());
969 
970   uint64_t End = Offset;
971   DWARFFormValue::skipValue(Abbrev->getFormByIndex(Idx), Data, &End,
972                             Unit.getFormParams());
973 
974   return std::make_pair(Offset, End);
975 }
976 
977 bool DwarfLinkerForBinary::AddressManager::isLiveVariable(
978     const DWARFDie &DIE, CompileUnit::DIEInfo &MyInfo) {
979   const auto *Abbrev = DIE.getAbbreviationDeclarationPtr();
980 
981   std::optional<uint32_t> LocationIdx =
982       Abbrev->findAttributeIndex(dwarf::DW_AT_location);
983   if (!LocationIdx)
984     return false;
985 
986   uint64_t Offset = DIE.getOffset() + getULEB128Size(Abbrev->getCode());
987   uint64_t LocationOffset, LocationEndOffset;
988   std::tie(LocationOffset, LocationEndOffset) =
989       getAttributeOffsets(Abbrev, *LocationIdx, Offset, *DIE.getDwarfUnit());
990 
991   // FIXME: Support relocations debug_addr.
992   return hasValidRelocationAt(ValidDebugInfoRelocs, LocationOffset,
993                               LocationEndOffset, MyInfo);
994 }
995 
996 bool DwarfLinkerForBinary::AddressManager::isLiveSubprogram(
997     const DWARFDie &DIE, CompileUnit::DIEInfo &MyInfo) {
998   const auto *Abbrev = DIE.getAbbreviationDeclarationPtr();
999 
1000   std::optional<uint32_t> LowPcIdx =
1001       Abbrev->findAttributeIndex(dwarf::DW_AT_low_pc);
1002   if (!LowPcIdx)
1003     return false;
1004 
1005   dwarf::Form Form = Abbrev->getFormByIndex(*LowPcIdx);
1006 
1007   if (Form == dwarf::DW_FORM_addr) {
1008     uint64_t Offset = DIE.getOffset() + getULEB128Size(Abbrev->getCode());
1009     uint64_t LowPcOffset, LowPcEndOffset;
1010     std::tie(LowPcOffset, LowPcEndOffset) =
1011         getAttributeOffsets(Abbrev, *LowPcIdx, Offset, *DIE.getDwarfUnit());
1012     return hasValidRelocationAt(ValidDebugInfoRelocs, LowPcOffset,
1013                                 LowPcEndOffset, MyInfo);
1014   }
1015 
1016   if (Form == dwarf::DW_FORM_addrx) {
1017     std::optional<DWARFFormValue> AddrValue = DIE.find(dwarf::DW_AT_low_pc);
1018     if (std::optional<uint64_t> AddrOffsetSectionBase =
1019             DIE.getDwarfUnit()->getAddrOffsetSectionBase()) {
1020       uint64_t StartOffset = *AddrOffsetSectionBase + AddrValue->getRawUValue();
1021       uint64_t EndOffset =
1022           StartOffset + DIE.getDwarfUnit()->getAddressByteSize();
1023       return hasValidRelocationAt(ValidDebugAddrRelocs, StartOffset, EndOffset,
1024                                   MyInfo);
1025     } else
1026       Linker.reportWarning("no base offset for address table", SrcFileName);
1027   }
1028 
1029   return false;
1030 }
1031 
1032 uint64_t
1033 DwarfLinkerForBinary::AddressManager::relocate(const ValidReloc &Reloc) const {
1034   return Reloc.Mapping->getValue().BinaryAddress + Reloc.Addend;
1035 }
1036 
1037 /// Apply the valid relocations found by findValidRelocs() to
1038 /// the buffer \p Data, taking into account that Data is at \p BaseOffset
1039 /// in the debug_info section.
1040 ///
1041 /// Like for findValidRelocs(), this function must be called with
1042 /// monotonic \p BaseOffset values.
1043 ///
1044 /// \returns whether any reloc has been applied.
1045 bool DwarfLinkerForBinary::AddressManager::applyValidRelocs(
1046     MutableArrayRef<char> Data, uint64_t BaseOffset, bool IsLittleEndian) {
1047   std::vector<ValidReloc> Relocs = getRelocations(
1048       ValidDebugInfoRelocs, BaseOffset, BaseOffset + Data.size());
1049 
1050   for (const ValidReloc &CurReloc : Relocs) {
1051     assert(CurReloc.Offset - BaseOffset < Data.size());
1052     assert(CurReloc.Offset - BaseOffset + CurReloc.Size <= Data.size());
1053     char Buf[8];
1054     uint64_t Value = relocate(CurReloc);
1055     for (unsigned I = 0; I != CurReloc.Size; ++I) {
1056       unsigned Index = IsLittleEndian ? I : (CurReloc.Size - I - 1);
1057       Buf[I] = uint8_t(Value >> (Index * 8));
1058     }
1059     assert(CurReloc.Size <= sizeof(Buf));
1060     memcpy(&Data[CurReloc.Offset - BaseOffset], Buf, CurReloc.Size);
1061   }
1062 
1063   return Relocs.size() > 0;
1064 }
1065 
1066 llvm::Expected<uint64_t>
1067 DwarfLinkerForBinary::AddressManager::relocateIndexedAddr(uint64_t StartOffset,
1068                                                           uint64_t EndOffset) {
1069   std::vector<ValidReloc> Relocs =
1070       getRelocations(ValidDebugAddrRelocs, StartOffset, EndOffset);
1071   if (Relocs.size() == 0)
1072     return createStringError(
1073         std::make_error_code(std::errc::invalid_argument),
1074         "no relocation for offset %llu in debug_addr section", StartOffset);
1075 
1076   return relocate(Relocs[0]);
1077 }
1078 
1079 bool linkDwarf(raw_fd_ostream &OutFile, BinaryHolder &BinHolder,
1080                const DebugMap &DM, LinkOptions Options) {
1081   DwarfLinkerForBinary Linker(OutFile, BinHolder, std::move(Options));
1082   return Linker.link(DM);
1083 }
1084 
1085 } // namespace dsymutil
1086 } // namespace llvm
1087