lld/MachO/Writer.cpp

   1 //===- Writer.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 "Writer.h"
  10 #include "ConcatOutputSection.h"
  11 #include "Config.h"
  12 #include "InputFiles.h"
  13 #include "InputSection.h"
  14 #include "MapFile.h"
  15 #include "OutputSection.h"
  16 #include "OutputSegment.h"
  17 #include "SectionPriorities.h"
  18 #include "SymbolTable.h"
  19 #include "Symbols.h"
  20 #include "SyntheticSections.h"
  21 #include "Target.h"
  22 #include "UnwindInfoSection.h"
  23
  24 #include "lld/Common/Arrays.h"
  25 #include "lld/Common/CommonLinkerContext.h"
  26 #include "llvm/BinaryFormat/MachO.h"
  27 #include "llvm/Config/llvm-config.h"
  28 #include "llvm/Support/LEB128.h"
  29 #include "llvm/Support/Parallel.h"
  30 #include "llvm/Support/Path.h"
  31 #include "llvm/Support/ThreadPool.h"
  32 #include "llvm/Support/TimeProfiler.h"
  33 #include "llvm/Support/xxhash.h"
  34
  35 #include <algorithm>
  36
  37 using namespace llvm;
  38 using namespace llvm::MachO;
  39 using namespace llvm::sys;
  40 using namespace lld;
  41 using namespace lld::macho;
  42
  43 namespace {
  44 class LCUuid;
  45
  46 class Writer {
  47 public:
  48   Writer() : buffer(errorHandler().outputBuffer) {}
  49
  50   void treatSpecialUndefineds();
  51   void scanRelocations();
  52   void scanSymbols();
  53   template <class LP> void createOutputSections();
  54   template <class LP> void createLoadCommands();
  55   void finalizeAddresses();
  56   void finalizeLinkEditSegment();
  57   void assignAddresses(OutputSegment *);
  58
  59   void openFile();
  60   void writeSections();
  61   void applyOptimizationHints();
  62   void buildFixupChains();
  63   void writeUuid();
  64   void writeCodeSignature();
  65   void writeOutputFile();
  66
  67   template <class LP> void run();
  68
  69   ThreadPool threadPool;
  70   std::unique_ptr<FileOutputBuffer> &buffer;
  71   uint64_t addr = 0;
  72   uint64_t fileOff = 0;
  73   MachHeaderSection *header = nullptr;
  74   StringTableSection *stringTableSection = nullptr;
  75   SymtabSection *symtabSection = nullptr;
  76   IndirectSymtabSection *indirectSymtabSection = nullptr;
  77   CodeSignatureSection *codeSignatureSection = nullptr;
  78   DataInCodeSection *dataInCodeSection = nullptr;
  79   FunctionStartsSection *functionStartsSection = nullptr;
  80
  81   LCUuid *uuidCommand = nullptr;
  82   OutputSegment *linkEditSegment = nullptr;
  83 };
  84
  85 // LC_DYLD_INFO_ONLY stores the offsets of symbol import/export information.
  86 class LCDyldInfo final : public LoadCommand {
  87 public:
  88   LCDyldInfo(RebaseSection *rebaseSection, BindingSection *bindingSection,
  89              WeakBindingSection *weakBindingSection,
  90              LazyBindingSection *lazyBindingSection,
  91              ExportSection *exportSection)
  92       : rebaseSection(rebaseSection), bindingSection(bindingSection),
  93         weakBindingSection(weakBindingSection),
  94         lazyBindingSection(lazyBindingSection), exportSection(exportSection) {}
  95
  96   uint32_t getSize() const override { return sizeof(dyld_info_command); }
  97
  98   void writeTo(uint8_t *buf) const override {
  99     auto *c = reinterpret_cast<dyld_info_command *>(buf);
 100     c->cmd = LC_DYLD_INFO_ONLY;
 101     c->cmdsize = getSize();
 102     if (rebaseSection->isNeeded()) {
 103       c->rebase_off = rebaseSection->fileOff;
 104       c->rebase_size = rebaseSection->getFileSize();
 105     }
 106     if (bindingSection->isNeeded()) {
 107       c->bind_off = bindingSection->fileOff;
 108       c->bind_size = bindingSection->getFileSize();
 109     }
 110     if (weakBindingSection->isNeeded()) {
 111       c->weak_bind_off = weakBindingSection->fileOff;
 112       c->weak_bind_size = weakBindingSection->getFileSize();
 113     }
 114     if (lazyBindingSection->isNeeded()) {
 115       c->lazy_bind_off = lazyBindingSection->fileOff;
 116       c->lazy_bind_size = lazyBindingSection->getFileSize();
 117     }
 118     if (exportSection->isNeeded()) {
 119       c->export_off = exportSection->fileOff;
 120       c->export_size = exportSection->getFileSize();
 121     }
 122   }
 123
 124   RebaseSection *rebaseSection;
 125   BindingSection *bindingSection;
 126   WeakBindingSection *weakBindingSection;
 127   LazyBindingSection *lazyBindingSection;
 128   ExportSection *exportSection;
 129 };
 130
 131 class LCSubFramework final : public LoadCommand {
 132 public:
 133   LCSubFramework(StringRef umbrella) : umbrella(umbrella) {}
 134
 135   uint32_t getSize() const override {
 136     return alignToPowerOf2(sizeof(sub_framework_command) + umbrella.size() + 1,
 137                            target->wordSize);
 138   }
 139
 140   void writeTo(uint8_t *buf) const override {
 141     auto *c = reinterpret_cast<sub_framework_command *>(buf);
 142     buf += sizeof(sub_framework_command);
 143
 144     c->cmd = LC_SUB_FRAMEWORK;
 145     c->cmdsize = getSize();
 146     c->umbrella = sizeof(sub_framework_command);
 147
 148     memcpy(buf, umbrella.data(), umbrella.size());
 149     buf[umbrella.size()] = '\0';
 150   }
 151
 152 private:
 153   const StringRef umbrella;
 154 };
 155
 156 class LCFunctionStarts final : public LoadCommand {
 157 public:
 158   explicit LCFunctionStarts(FunctionStartsSection *functionStartsSection)
 159       : functionStartsSection(functionStartsSection) {}
 160
 161   uint32_t getSize() const override { return sizeof(linkedit_data_command); }
 162
 163   void writeTo(uint8_t *buf) const override {
 164     auto *c = reinterpret_cast<linkedit_data_command *>(buf);
 165     c->cmd = LC_FUNCTION_STARTS;
 166     c->cmdsize = getSize();
 167     c->dataoff = functionStartsSection->fileOff;
 168     c->datasize = functionStartsSection->getFileSize();
 169   }
 170
 171 private:
 172   FunctionStartsSection *functionStartsSection;
 173 };
 174
 175 class LCDataInCode final : public LoadCommand {
 176 public:
 177   explicit LCDataInCode(DataInCodeSection *dataInCodeSection)
 178       : dataInCodeSection(dataInCodeSection) {}
 179
 180   uint32_t getSize() const override { return sizeof(linkedit_data_command); }
 181
 182   void writeTo(uint8_t *buf) const override {
 183     auto *c = reinterpret_cast<linkedit_data_command *>(buf);
 184     c->cmd = LC_DATA_IN_CODE;
 185     c->cmdsize = getSize();
 186     c->dataoff = dataInCodeSection->fileOff;
 187     c->datasize = dataInCodeSection->getFileSize();
 188   }
 189
 190 private:
 191   DataInCodeSection *dataInCodeSection;
 192 };
 193
 194 class LCDysymtab final : public LoadCommand {
 195 public:
 196   LCDysymtab(SymtabSection *symtabSection,
 197              IndirectSymtabSection *indirectSymtabSection)
 198       : symtabSection(symtabSection),
 199         indirectSymtabSection(indirectSymtabSection) {}
 200
 201   uint32_t getSize() const override { return sizeof(dysymtab_command); }
 202
 203   void writeTo(uint8_t *buf) const override {
 204     auto *c = reinterpret_cast<dysymtab_command *>(buf);
 205     c->cmd = LC_DYSYMTAB;
 206     c->cmdsize = getSize();
 207
 208     c->ilocalsym = 0;
 209     c->iextdefsym = c->nlocalsym = symtabSection->getNumLocalSymbols();
 210     c->nextdefsym = symtabSection->getNumExternalSymbols();
 211     c->iundefsym = c->iextdefsym + c->nextdefsym;
 212     c->nundefsym = symtabSection->getNumUndefinedSymbols();
 213
 214     c->indirectsymoff = indirectSymtabSection->fileOff;
 215     c->nindirectsyms = indirectSymtabSection->getNumSymbols();
 216   }
 217
 218   SymtabSection *symtabSection;
 219   IndirectSymtabSection *indirectSymtabSection;
 220 };
 221
 222 template <class LP> class LCSegment final : public LoadCommand {
 223 public:
 224   LCSegment(StringRef name, OutputSegment *seg) : name(name), seg(seg) {}
 225
 226   uint32_t getSize() const override {
 227     return sizeof(typename LP::segment_command) +
 228            seg->numNonHiddenSections() * sizeof(typename LP::section);
 229   }
 230
 231   void writeTo(uint8_t *buf) const override {
 232     using SegmentCommand = typename LP::segment_command;
 233     using SectionHeader = typename LP::section;
 234
 235     auto *c = reinterpret_cast<SegmentCommand *>(buf);
 236     buf += sizeof(SegmentCommand);
 237
 238     c->cmd = LP::segmentLCType;
 239     c->cmdsize = getSize();
 240     memcpy(c->segname, name.data(), name.size());
 241     c->fileoff = seg->fileOff;
 242     c->maxprot = seg->maxProt;
 243     c->initprot = seg->initProt;
 244
 245     c->vmaddr = seg->addr;
 246     c->vmsize = seg->vmSize;
 247     c->filesize = seg->fileSize;
 248     c->nsects = seg->numNonHiddenSections();
 249     c->flags = seg->flags;
 250
 251     for (const OutputSection *osec : seg->getSections()) {
 252       if (osec->isHidden())
 253         continue;
 254
 255       auto *sectHdr = reinterpret_cast<SectionHeader *>(buf);
 256       buf += sizeof(SectionHeader);
 257
 258       memcpy(sectHdr->sectname, osec->name.data(), osec->name.size());
 259       memcpy(sectHdr->segname, name.data(), name.size());
 260
 261       sectHdr->addr = osec->addr;
 262       sectHdr->offset = osec->fileOff;
 263       sectHdr->align = Log2_32(osec->align);
 264       sectHdr->flags = osec->flags;
 265       sectHdr->size = osec->getSize();
 266       sectHdr->reserved1 = osec->reserved1;
 267       sectHdr->reserved2 = osec->reserved2;
 268     }
 269   }
 270
 271 private:
 272   StringRef name;
 273   OutputSegment *seg;
 274 };
 275
 276 class LCMain final : public LoadCommand {
 277   uint32_t getSize() const override {
 278     return sizeof(structs::entry_point_command);
 279   }
 280
 281   void writeTo(uint8_t *buf) const override {
 282     auto *c = reinterpret_cast<structs::entry_point_command *>(buf);
 283     c->cmd = LC_MAIN;
 284     c->cmdsize = getSize();
 285
 286     if (config->entry->isInStubs())
 287       c->entryoff =
 288           in.stubs->fileOff + config->entry->stubsIndex * target->stubSize;
 289     else
 290       c->entryoff = config->entry->getVA() - in.header->addr;
 291
 292     c->stacksize = 0;
 293   }
 294 };
 295
 296 class LCSymtab final : public LoadCommand {
 297 public:
 298   LCSymtab(SymtabSection *symtabSection, StringTableSection *stringTableSection)
 299       : symtabSection(symtabSection), stringTableSection(stringTableSection) {}
 300
 301   uint32_t getSize() const override { return sizeof(symtab_command); }
 302
 303   void writeTo(uint8_t *buf) const override {
 304     auto *c = reinterpret_cast<symtab_command *>(buf);
 305     c->cmd = LC_SYMTAB;
 306     c->cmdsize = getSize();
 307     c->symoff = symtabSection->fileOff;
 308     c->nsyms = symtabSection->getNumSymbols();
 309     c->stroff = stringTableSection->fileOff;
 310     c->strsize = stringTableSection->getFileSize();
 311   }
 312
 313   SymtabSection *symtabSection = nullptr;
 314   StringTableSection *stringTableSection = nullptr;
 315 };
 316
 317 // There are several dylib load commands that share the same structure:
 318 //   * LC_LOAD_DYLIB
 319 //   * LC_ID_DYLIB
 320 //   * LC_REEXPORT_DYLIB
 321 class LCDylib final : public LoadCommand {
 322 public:
 323   LCDylib(LoadCommandType type, StringRef path,
 324           uint32_t compatibilityVersion = 0, uint32_t currentVersion = 0)
 325       : type(type), path(path), compatibilityVersion(compatibilityVersion),
 326         currentVersion(currentVersion) {
 327     instanceCount++;
 328   }
 329
 330   uint32_t getSize() const override {
 331     return alignToPowerOf2(sizeof(dylib_command) + path.size() + 1,
 332                            target->wordSize);
 333   }
 334
 335   void writeTo(uint8_t *buf) const override {
 336     auto *c = reinterpret_cast<dylib_command *>(buf);
 337     buf += sizeof(dylib_command);
 338
 339     c->cmd = type;
 340     c->cmdsize = getSize();
 341     c->dylib.name = sizeof(dylib_command);
 342     c->dylib.timestamp = 0;
 343     c->dylib.compatibility_version = compatibilityVersion;
 344     c->dylib.current_version = currentVersion;
 345
 346     memcpy(buf, path.data(), path.size());
 347     buf[path.size()] = '\0';
 348   }
 349
 350   static uint32_t getInstanceCount() { return instanceCount; }
 351   static void resetInstanceCount() { instanceCount = 0; }
 352
 353 private:
 354   LoadCommandType type;
 355   StringRef path;
 356   uint32_t compatibilityVersion;
 357   uint32_t currentVersion;
 358   static uint32_t instanceCount;
 359 };
 360
 361 uint32_t LCDylib::instanceCount = 0;
 362
 363 class LCLoadDylinker final : public LoadCommand {
 364 public:
 365   uint32_t getSize() const override {
 366     return alignToPowerOf2(sizeof(dylinker_command) + path.size() + 1,
 367                            target->wordSize);
 368   }
 369
 370   void writeTo(uint8_t *buf) const override {
 371     auto *c = reinterpret_cast<dylinker_command *>(buf);
 372     buf += sizeof(dylinker_command);
 373
 374     c->cmd = LC_LOAD_DYLINKER;
 375     c->cmdsize = getSize();
 376     c->name = sizeof(dylinker_command);
 377
 378     memcpy(buf, path.data(), path.size());
 379     buf[path.size()] = '\0';
 380   }
 381
 382 private:
 383   // Recent versions of Darwin won't run any binary that has dyld at a
 384   // different location.
 385   const StringRef path = "/usr/lib/dyld";
 386 };
 387
 388 class LCRPath final : public LoadCommand {
 389 public:
 390   explicit LCRPath(StringRef path) : path(path) {}
 391
 392   uint32_t getSize() const override {
 393     return alignToPowerOf2(sizeof(rpath_command) + path.size() + 1,
 394                            target->wordSize);
 395   }
 396
 397   void writeTo(uint8_t *buf) const override {
 398     auto *c = reinterpret_cast<rpath_command *>(buf);
 399     buf += sizeof(rpath_command);
 400
 401     c->cmd = LC_RPATH;
 402     c->cmdsize = getSize();
 403     c->path = sizeof(rpath_command);
 404
 405     memcpy(buf, path.data(), path.size());
 406     buf[path.size()] = '\0';
 407   }
 408
 409 private:
 410   StringRef path;
 411 };
 412
 413 class LCDyldEnv final : public LoadCommand {
 414 public:
 415   explicit LCDyldEnv(StringRef name) : name(name) {}
 416
 417   uint32_t getSize() const override {
 418     return alignToPowerOf2(sizeof(dyld_env_command) + name.size() + 1,
 419                            target->wordSize);
 420   }
 421
 422   void writeTo(uint8_t *buf) const override {
 423     auto *c = reinterpret_cast<dyld_env_command *>(buf);
 424     buf += sizeof(dyld_env_command);
 425
 426     c->cmd = LC_DYLD_ENVIRONMENT;
 427     c->cmdsize = getSize();
 428     c->name = sizeof(dyld_env_command);
 429
 430     memcpy(buf, name.data(), name.size());
 431     buf[name.size()] = '\0';
 432   }
 433
 434 private:
 435   StringRef name;
 436 };
 437
 438 class LCMinVersion final : public LoadCommand {
 439 public:
 440   explicit LCMinVersion(const PlatformInfo &platformInfo)
 441       : platformInfo(platformInfo) {}
 442
 443   uint32_t getSize() const override { return sizeof(version_min_command); }
 444
 445   void writeTo(uint8_t *buf) const override {
 446     auto *c = reinterpret_cast<version_min_command *>(buf);
 447     switch (platformInfo.target.Platform) {
 448     case PLATFORM_MACOS:
 449       c->cmd = LC_VERSION_MIN_MACOSX;
 450       break;
 451     case PLATFORM_IOS:
 452     case PLATFORM_IOSSIMULATOR:
 453       c->cmd = LC_VERSION_MIN_IPHONEOS;
 454       break;
 455     case PLATFORM_TVOS:
 456     case PLATFORM_TVOSSIMULATOR:
 457       c->cmd = LC_VERSION_MIN_TVOS;
 458       break;
 459     case PLATFORM_WATCHOS:
 460     case PLATFORM_WATCHOSSIMULATOR:
 461       c->cmd = LC_VERSION_MIN_WATCHOS;
 462       break;
 463     default:
 464       llvm_unreachable("invalid platform");
 465       break;
 466     }
 467     c->cmdsize = getSize();
 468     c->version = encodeVersion(platformInfo.target.MinDeployment);
 469     c->sdk = encodeVersion(platformInfo.sdk);
 470   }
 471
 472 private:
 473   const PlatformInfo &platformInfo;
 474 };
 475
 476 class LCBuildVersion final : public LoadCommand {
 477 public:
 478   explicit LCBuildVersion(const PlatformInfo &platformInfo)
 479       : platformInfo(platformInfo) {}
 480
 481   const int ntools = 1;
 482
 483   uint32_t getSize() const override {
 484     return sizeof(build_version_command) + ntools * sizeof(build_tool_version);
 485   }
 486
 487   void writeTo(uint8_t *buf) const override {
 488     auto *c = reinterpret_cast<build_version_command *>(buf);
 489     c->cmd = LC_BUILD_VERSION;
 490     c->cmdsize = getSize();
 491
 492     c->platform = static_cast<uint32_t>(platformInfo.target.Platform);
 493     c->minos = encodeVersion(platformInfo.target.MinDeployment);
 494     c->sdk = encodeVersion(platformInfo.sdk);
 495
 496     c->ntools = ntools;
 497     auto *t = reinterpret_cast<build_tool_version *>(&c[1]);
 498     t->tool = TOOL_LLD;
 499     t->version = encodeVersion(VersionTuple(
 500         LLVM_VERSION_MAJOR, LLVM_VERSION_MINOR, LLVM_VERSION_PATCH));
 501   }
 502
 503 private:
 504   const PlatformInfo &platformInfo;
 505 };
 506
 507 // Stores a unique identifier for the output file based on an MD5 hash of its
 508 // contents. In order to hash the contents, we must first write them, but
 509 // LC_UUID itself must be part of the written contents in order for all the
 510 // offsets to be calculated correctly. We resolve this circular paradox by
 511 // first writing an LC_UUID with an all-zero UUID, then updating the UUID with
 512 // its real value later.
 513 class LCUuid final : public LoadCommand {
 514 public:
 515   uint32_t getSize() const override { return sizeof(uuid_command); }
 516
 517   void writeTo(uint8_t *buf) const override {
 518     auto *c = reinterpret_cast<uuid_command *>(buf);
 519     c->cmd = LC_UUID;
 520     c->cmdsize = getSize();
 521     uuidBuf = c->uuid;
 522   }
 523
 524   void writeUuid(uint64_t digest) const {
 525     // xxhash only gives us 8 bytes, so put some fixed data in the other half.
 526     static_assert(sizeof(uuid_command::uuid) == 16, "unexpected uuid size");
 527     memcpy(uuidBuf, "LLD\xa1UU1D", 8);
 528     memcpy(uuidBuf + 8, &digest, 8);
 529
 530     // RFC 4122 conformance. We need to fix 4 bits in byte 6 and 2 bits in
 531     // byte 8. Byte 6 is already fine due to the fixed data we put in. We don't
 532     // want to lose bits of the digest in byte 8, so swap that with a byte of
 533     // fixed data that happens to have the right bits set.
 534     std::swap(uuidBuf[3], uuidBuf[8]);
 535
 536     // Claim that this is an MD5-based hash. It isn't, but this signals that
 537     // this is not a time-based and not a random hash. MD5 seems like the least
 538     // bad lie we can put here.
 539     assert((uuidBuf[6] & 0xf0) == 0x30 && "See RFC 4122 Sections 4.2.2, 4.1.3");
 540     assert((uuidBuf[8] & 0xc0) == 0x80 && "See RFC 4122 Section 4.2.2");
 541   }
 542
 543   mutable uint8_t *uuidBuf;
 544 };
 545
 546 template <class LP> class LCEncryptionInfo final : public LoadCommand {
 547 public:
 548   uint32_t getSize() const override {
 549     return sizeof(typename LP::encryption_info_command);
 550   }
 551
 552   void writeTo(uint8_t *buf) const override {
 553     using EncryptionInfo = typename LP::encryption_info_command;
 554     auto *c = reinterpret_cast<EncryptionInfo *>(buf);
 555     buf += sizeof(EncryptionInfo);
 556     c->cmd = LP::encryptionInfoLCType;
 557     c->cmdsize = getSize();
 558     c->cryptoff = in.header->getSize();
 559     auto it = find_if(outputSegments, [](const OutputSegment *seg) {
 560       return seg->name == segment_names::text;
 561     });
 562     assert(it != outputSegments.end());
 563     c->cryptsize = (*it)->fileSize - c->cryptoff;
 564   }
 565 };
 566
 567 class LCCodeSignature final : public LoadCommand {
 568 public:
 569   LCCodeSignature(CodeSignatureSection *section) : section(section) {}
 570
 571   uint32_t getSize() const override { return sizeof(linkedit_data_command); }
 572
 573   void writeTo(uint8_t *buf) const override {
 574     auto *c = reinterpret_cast<linkedit_data_command *>(buf);
 575     c->cmd = LC_CODE_SIGNATURE;
 576     c->cmdsize = getSize();
 577     c->dataoff = static_cast<uint32_t>(section->fileOff);
 578     c->datasize = section->getSize();
 579   }
 580
 581   CodeSignatureSection *section;
 582 };
 583
 584 class LCExportsTrie final : public LoadCommand {
 585 public:
 586   LCExportsTrie(ExportSection *section) : section(section) {}
 587
 588   uint32_t getSize() const override { return sizeof(linkedit_data_command); }
 589
 590   void writeTo(uint8_t *buf) const override {
 591     auto *c = reinterpret_cast<linkedit_data_command *>(buf);
 592     c->cmd = LC_DYLD_EXPORTS_TRIE;
 593     c->cmdsize = getSize();
 594     c->dataoff = section->fileOff;
 595     c->datasize = section->getSize();
 596   }
 597
 598   ExportSection *section;
 599 };
 600
 601 class LCChainedFixups final : public LoadCommand {
 602 public:
 603   LCChainedFixups(ChainedFixupsSection *section) : section(section) {}
 604
 605   uint32_t getSize() const override { return sizeof(linkedit_data_command); }
 606
 607   void writeTo(uint8_t *buf) const override {
 608     auto *c = reinterpret_cast<linkedit_data_command *>(buf);
 609     c->cmd = LC_DYLD_CHAINED_FIXUPS;
 610     c->cmdsize = getSize();
 611     c->dataoff = section->fileOff;
 612     c->datasize = section->getSize();
 613   }
 614
 615   ChainedFixupsSection *section;
 616 };
 617
 618 } // namespace
 619
 620 void Writer::treatSpecialUndefineds() {
 621   if (config->entry)
 622     if (auto *undefined = dyn_cast<Undefined>(config->entry))
 623       treatUndefinedSymbol(*undefined, "the entry point");
 624
 625   // FIXME: This prints symbols that are undefined both in input files and
 626   // via -u flag twice.
 627   for (const Symbol *sym : config->explicitUndefineds) {
 628     if (const auto *undefined = dyn_cast<Undefined>(sym))
 629       treatUndefinedSymbol(*undefined, "-u");
 630   }
 631   // Literal exported-symbol names must be defined, but glob
 632   // patterns need not match.
 633   for (const CachedHashStringRef &cachedName :
 634        config->exportedSymbols.literals) {
 635     if (const Symbol *sym = symtab->find(cachedName))
 636       if (const auto *undefined = dyn_cast<Undefined>(sym))
 637         treatUndefinedSymbol(*undefined, "-exported_symbol(s_list)");
 638   }
 639 }
 640
 641 static void prepareSymbolRelocation(Symbol *sym, const InputSection *isec,
 642                                     const lld::macho::Reloc &r) {
 643   assert(sym->isLive());
 644   const RelocAttrs &relocAttrs = target->getRelocAttrs(r.type);
 645
 646   if (relocAttrs.hasAttr(RelocAttrBits::BRANCH)) {
 647     if (needsBinding(sym))
 648       in.stubs->addEntry(sym);
 649   } else if (relocAttrs.hasAttr(RelocAttrBits::GOT)) {
 650     if (relocAttrs.hasAttr(RelocAttrBits::POINTER) || needsBinding(sym))
 651       in.got->addEntry(sym);
 652   } else if (relocAttrs.hasAttr(RelocAttrBits::TLV)) {
 653     if (needsBinding(sym))
 654       in.tlvPointers->addEntry(sym);
 655   } else if (relocAttrs.hasAttr(RelocAttrBits::UNSIGNED)) {
 656     // References from thread-local variable sections are treated as offsets
 657     // relative to the start of the referent section, and therefore have no
 658     // need of rebase opcodes.
 659     if (!(isThreadLocalVariables(isec->getFlags()) && isa<Defined>(sym)))
 660       addNonLazyBindingEntries(sym, isec, r.offset, r.addend);
 661   }
 662 }
 663
 664 void Writer::scanRelocations() {
 665   TimeTraceScope timeScope("Scan relocations");
 666
 667   // This can't use a for-each loop: It calls treatUndefinedSymbol(), which can
 668   // add to inputSections, which invalidates inputSections's iterators.
 669   for (size_t i = 0; i < inputSections.size(); ++i) {
 670     ConcatInputSection *isec = inputSections[i];
 671
 672     if (isec->shouldOmitFromOutput())
 673       continue;
 674
 675     for (auto it = isec->relocs.begin(); it != isec->relocs.end(); ++it) {
 676       lld::macho::Reloc &r = *it;
 677
 678       // Canonicalize the referent so that later accesses in Writer won't
 679       // have to worry about it.
 680       if (auto *referentIsec = r.referent.dyn_cast<InputSection *>())
 681         r.referent = referentIsec->canonical();
 682
 683       if (target->hasAttr(r.type, RelocAttrBits::SUBTRAHEND)) {
 684         // Skip over the following UNSIGNED relocation -- it's just there as the
 685         // minuend, and doesn't have the usual UNSIGNED semantics. We don't want
 686         // to emit rebase opcodes for it.
 687         ++it;
 688         // Canonicalize the referent so that later accesses in Writer won't
 689         // have to worry about it.
 690         if (auto *referentIsec = it->referent.dyn_cast<InputSection *>())
 691           it->referent = referentIsec->canonical();
 692         continue;
 693       }
 694       if (auto *sym = r.referent.dyn_cast<Symbol *>()) {
 695         if (auto *undefined = dyn_cast<Undefined>(sym))
 696           treatUndefinedSymbol(*undefined, isec, r.offset);
 697         // treatUndefinedSymbol() can replace sym with a DylibSymbol; re-check.
 698         if (!isa<Undefined>(sym) && validateSymbolRelocation(sym, isec, r))
 699           prepareSymbolRelocation(sym, isec, r);
 700       } else {
 701         if (!r.pcrel) {
 702           if (config->emitChainedFixups)
 703             in.chainedFixups->addRebase(isec, r.offset);
 704           else
 705             in.rebase->addEntry(isec, r.offset);
 706         }
 707       }
 708     }
 709   }
 710
 711   in.unwindInfo->prepare();
 712 }
 713
 714 static void addNonWeakDefinition(const Defined *defined) {
 715   if (config->emitChainedFixups)
 716     in.chainedFixups->setHasNonWeakDefinition();
 717   else
 718     in.weakBinding->addNonWeakDefinition(defined);
 719 }
 720
 721 void Writer::scanSymbols() {
 722   TimeTraceScope timeScope("Scan symbols");
 723   for (Symbol *sym : symtab->getSymbols()) {
 724     if (auto *defined = dyn_cast<Defined>(sym)) {
 725       if (!defined->isLive())
 726         continue;
 727       defined->canonicalize();
 728       if (defined->overridesWeakDef)
 729         addNonWeakDefinition(defined);
 730       if (!defined->isAbsolute() && isCodeSection(defined->isec))
 731         in.unwindInfo->addSymbol(defined);
 732     } else if (const auto *dysym = dyn_cast<DylibSymbol>(sym)) {
 733       // This branch intentionally doesn't check isLive().
 734       if (dysym->isDynamicLookup())
 735         continue;
 736       dysym->getFile()->refState =
 737           std::max(dysym->getFile()->refState, dysym->getRefState());
 738     } else if (isa<Undefined>(sym)) {
 739       if (sym->getName().starts_with(ObjCStubsSection::symbolPrefix))
 740         in.objcStubs->addEntry(sym);
 741     }
 742   }
 743
 744   for (const InputFile *file : inputFiles) {
 745     if (auto *objFile = dyn_cast<ObjFile>(file))
 746       for (Symbol *sym : objFile->symbols) {
 747         if (auto *defined = dyn_cast_or_null<Defined>(sym)) {
 748           if (!defined->isLive())
 749             continue;
 750           defined->canonicalize();
 751           if (!defined->isExternal() && !defined->isAbsolute() &&
 752               isCodeSection(defined->isec))
 753             in.unwindInfo->addSymbol(defined);
 754         }
 755       }
 756   }
 757 }
 758
 759 // TODO: ld64 enforces the old load commands in a few other cases.
 760 static bool useLCBuildVersion(const PlatformInfo &platformInfo) {
 761   static const std::array<std::pair<PlatformType, VersionTuple>, 7> minVersion =
 762       {{{PLATFORM_MACOS, VersionTuple(10, 14)},
 763         {PLATFORM_IOS, VersionTuple(12, 0)},
 764         {PLATFORM_IOSSIMULATOR, VersionTuple(13, 0)},
 765         {PLATFORM_TVOS, VersionTuple(12, 0)},
 766         {PLATFORM_TVOSSIMULATOR, VersionTuple(13, 0)},
 767         {PLATFORM_WATCHOS, VersionTuple(5, 0)},
 768         {PLATFORM_WATCHOSSIMULATOR, VersionTuple(6, 0)}}};
 769   auto it = llvm::find_if(minVersion, [&](const auto &p) {
 770     return p.first == platformInfo.target.Platform;
 771   });
 772   return it == minVersion.end()
 773              ? true
 774              : platformInfo.target.MinDeployment >= it->second;
 775 }
 776
 777 template <class LP> void Writer::createLoadCommands() {
 778   uint8_t segIndex = 0;
 779   for (OutputSegment *seg : outputSegments) {
 780     in.header->addLoadCommand(make<LCSegment<LP>>(seg->name, seg));
 781     seg->index = segIndex++;
 782   }
 783
 784   if (config->emitChainedFixups) {
 785     in.header->addLoadCommand(make<LCChainedFixups>(in.chainedFixups));
 786     in.header->addLoadCommand(make<LCExportsTrie>(in.exports));
 787   } else {
 788     in.header->addLoadCommand(make<LCDyldInfo>(
 789         in.rebase, in.binding, in.weakBinding, in.lazyBinding, in.exports));
 790   }
 791   in.header->addLoadCommand(make<LCSymtab>(symtabSection, stringTableSection));
 792   in.header->addLoadCommand(
 793       make<LCDysymtab>(symtabSection, indirectSymtabSection));
 794   if (!config->umbrella.empty())
 795     in.header->addLoadCommand(make<LCSubFramework>(config->umbrella));
 796   if (config->emitEncryptionInfo)
 797     in.header->addLoadCommand(make<LCEncryptionInfo<LP>>());
 798   for (StringRef path : config->runtimePaths)
 799     in.header->addLoadCommand(make<LCRPath>(path));
 800
 801   switch (config->outputType) {
 802   case MH_EXECUTE:
 803     in.header->addLoadCommand(make<LCLoadDylinker>());
 804     break;
 805   case MH_DYLIB:
 806     in.header->addLoadCommand(make<LCDylib>(LC_ID_DYLIB, config->installName,
 807                                             config->dylibCompatibilityVersion,
 808                                             config->dylibCurrentVersion));
 809     break;
 810   case MH_BUNDLE:
 811     break;
 812   default:
 813     llvm_unreachable("unhandled output file type");
 814   }
 815
 816   if (config->generateUuid) {
 817     uuidCommand = make<LCUuid>();
 818     in.header->addLoadCommand(uuidCommand);
 819   }
 820
 821   if (useLCBuildVersion(config->platformInfo))
 822     in.header->addLoadCommand(make<LCBuildVersion>(config->platformInfo));
 823   else
 824     in.header->addLoadCommand(make<LCMinVersion>(config->platformInfo));
 825
 826   if (config->secondaryPlatformInfo) {
 827     in.header->addLoadCommand(
 828         make<LCBuildVersion>(*config->secondaryPlatformInfo));
 829   }
 830
 831   // This is down here to match ld64's load command order.
 832   if (config->outputType == MH_EXECUTE)
 833     in.header->addLoadCommand(make<LCMain>());
 834
 835   // See ld64's OutputFile::buildDylibOrdinalMapping for the corresponding
 836   // library ordinal computation code in ld64.
 837   int64_t dylibOrdinal = 1;
 838   DenseMap<StringRef, int64_t> ordinalForInstallName;
 839
 840   std::vector<DylibFile *> dylibFiles;
 841   for (InputFile *file : inputFiles) {
 842     if (auto *dylibFile = dyn_cast<DylibFile>(file))
 843       dylibFiles.push_back(dylibFile);
 844   }
 845   for (size_t i = 0; i < dylibFiles.size(); ++i)
 846     dylibFiles.insert(dylibFiles.end(), dylibFiles[i]->extraDylibs.begin(),
 847                       dylibFiles[i]->extraDylibs.end());
 848
 849   for (DylibFile *dylibFile : dylibFiles) {
 850     if (dylibFile->isBundleLoader) {
 851       dylibFile->ordinal = BIND_SPECIAL_DYLIB_MAIN_EXECUTABLE;
 852       // Shortcut since bundle-loader does not re-export the symbols.
 853
 854       dylibFile->reexport = false;
 855       continue;
 856     }
 857
 858     // Don't emit load commands for a dylib that is not referenced if:
 859     // - it was added implicitly (via a reexport, an LC_LOAD_DYLINKER --
 860     //   if it's on the linker command line, it's explicit)
 861     // - or it's marked MH_DEAD_STRIPPABLE_DYLIB
 862     // - or the flag -dead_strip_dylibs is used
 863     // FIXME: `isReferenced()` is currently computed before dead code
 864     // stripping, so references from dead code keep a dylib alive. This
 865     // matches ld64, but it's something we should do better.
 866     if (!dylibFile->isReferenced() && !dylibFile->forceNeeded &&
 867         (!dylibFile->isExplicitlyLinked() || dylibFile->deadStrippable ||
 868          config->deadStripDylibs))
 869       continue;
 870
 871     // Several DylibFiles can have the same installName. Only emit a single
 872     // load command for that installName and give all these DylibFiles the
 873     // same ordinal.
 874     // This can happen in several cases:
 875     // - a new framework could change its installName to an older
 876     //   framework name via an $ld$ symbol depending on platform_version
 877     // - symlinks (for example, libpthread.tbd is a symlink to libSystem.tbd;
 878     //   Foo.framework/Foo.tbd is usually a symlink to
 879     //   Foo.framework/Versions/Current/Foo.tbd, where
 880     //   Foo.framework/Versions/Current is usually a symlink to
 881     //   Foo.framework/Versions/A)
 882     // - a framework can be linked both explicitly on the linker
 883     //   command line and implicitly as a reexport from a different
 884     //   framework. The re-export will usually point to the tbd file
 885     //   in Foo.framework/Versions/A/Foo.tbd, while the explicit link will
 886     //   usually find Foo.framework/Foo.tbd. These are usually symlinks,
 887     //   but in a --reproduce archive they will be identical but distinct
 888     //   files.
 889     // In the first case, *semantically distinct* DylibFiles will have the
 890     // same installName.
 891     int64_t &ordinal = ordinalForInstallName[dylibFile->installName];
 892     if (ordinal) {
 893       dylibFile->ordinal = ordinal;
 894       continue;
 895     }
 896
 897     ordinal = dylibFile->ordinal = dylibOrdinal++;
 898     LoadCommandType lcType =
 899         dylibFile->forceWeakImport || dylibFile->refState == RefState::Weak
 900             ? LC_LOAD_WEAK_DYLIB
 901             : LC_LOAD_DYLIB;
 902     in.header->addLoadCommand(make<LCDylib>(lcType, dylibFile->installName,
 903                                             dylibFile->compatibilityVersion,
 904                                             dylibFile->currentVersion));
 905
 906     if (dylibFile->reexport)
 907       in.header->addLoadCommand(
 908           make<LCDylib>(LC_REEXPORT_DYLIB, dylibFile->installName));
 909   }
 910
 911   for (const auto &dyldEnv : config->dyldEnvs)
 912     in.header->addLoadCommand(make<LCDyldEnv>(dyldEnv));
 913
 914   if (functionStartsSection)
 915     in.header->addLoadCommand(make<LCFunctionStarts>(functionStartsSection));
 916   if (dataInCodeSection)
 917     in.header->addLoadCommand(make<LCDataInCode>(dataInCodeSection));
 918   if (codeSignatureSection)
 919     in.header->addLoadCommand(make<LCCodeSignature>(codeSignatureSection));
 920
 921   const uint32_t MACOS_MAXPATHLEN = 1024;
 922   config->headerPad = std::max(
 923       config->headerPad, (config->headerPadMaxInstallNames
 924                               ? LCDylib::getInstanceCount() * MACOS_MAXPATHLEN
 925                               : 0));
 926 }
 927
 928 // Sorting only can happen once all outputs have been collected. Here we sort
 929 // segments, output sections within each segment, and input sections within each
 930 // output segment.
 931 static void sortSegmentsAndSections() {
 932   TimeTraceScope timeScope("Sort segments and sections");
 933   sortOutputSegments();
 934
 935   DenseMap<const InputSection *, size_t> isecPriorities =
 936       priorityBuilder.buildInputSectionPriorities();
 937
 938   uint32_t sectionIndex = 0;
 939   for (OutputSegment *seg : outputSegments) {
 940     seg->sortOutputSections();
 941     // References from thread-local variable sections are treated as offsets
 942     // relative to the start of the thread-local data memory area, which
 943     // is initialized via copying all the TLV data sections (which are all
 944     // contiguous). If later data sections require a greater alignment than
 945     // earlier ones, the offsets of data within those sections won't be
 946     // guaranteed to aligned unless we normalize alignments. We therefore use
 947     // the largest alignment for all TLV data sections.
 948     uint32_t tlvAlign = 0;
 949     for (const OutputSection *osec : seg->getSections())
 950       if (isThreadLocalData(osec->flags) && osec->align > tlvAlign)
 951         tlvAlign = osec->align;
 952
 953     for (OutputSection *osec : seg->getSections()) {
 954       // Now that the output sections are sorted, assign the final
 955       // output section indices.
 956       if (!osec->isHidden())
 957         osec->index = ++sectionIndex;
 958       if (isThreadLocalData(osec->flags)) {
 959         if (!firstTLVDataSection)
 960           firstTLVDataSection = osec;
 961         osec->align = tlvAlign;
 962       }
 963
 964       if (!isecPriorities.empty()) {
 965         if (auto *merged = dyn_cast<ConcatOutputSection>(osec)) {
 966           llvm::stable_sort(
 967               merged->inputs, [&](InputSection *a, InputSection *b) {
 968                 return isecPriorities.lookup(a) > isecPriorities.lookup(b);
 969               });
 970         }
 971       }
 972     }
 973   }
 974 }
 975
 976 template <class LP> void Writer::createOutputSections() {
 977   TimeTraceScope timeScope("Create output sections");
 978   // First, create hidden sections
 979   stringTableSection = make<StringTableSection>();
 980   symtabSection = makeSymtabSection<LP>(*stringTableSection);
 981   indirectSymtabSection = make<IndirectSymtabSection>();
 982   if (config->adhocCodesign)
 983     codeSignatureSection = make<CodeSignatureSection>();
 984   if (config->emitDataInCodeInfo)
 985     dataInCodeSection = make<DataInCodeSection>();
 986   if (config->emitFunctionStarts)
 987     functionStartsSection = make<FunctionStartsSection>();
 988
 989   switch (config->outputType) {
 990   case MH_EXECUTE:
 991     make<PageZeroSection>();
 992     break;
 993   case MH_DYLIB:
 994   case MH_BUNDLE:
 995     break;
 996   default:
 997     llvm_unreachable("unhandled output file type");
 998   }
 999
1000   // Then add input sections to output sections.
1001   for (ConcatInputSection *isec : inputSections) {
1002     if (isec->shouldOmitFromOutput())
1003       continue;
1004     ConcatOutputSection *osec = cast<ConcatOutputSection>(isec->parent);
1005     osec->addInput(isec);
1006     osec->inputOrder =
1007         std::min(osec->inputOrder, static_cast<int>(isec->outSecOff));
1008   }
1009
1010   // Once all the inputs are added, we can finalize the output section
1011   // properties and create the corresponding output segments.
1012   for (const auto &it : concatOutputSections) {
1013     StringRef segname = it.first.first;
1014     ConcatOutputSection *osec = it.second;
1015     assert(segname != segment_names::ld);
1016     if (osec->isNeeded()) {
1017       // See comment in ObjFile::splitEhFrames()
1018       if (osec->name == section_names::ehFrame &&
1019           segname == segment_names::text)
1020         osec->align = target->wordSize;
1021
1022       // MC keeps the default 1-byte alignment for __thread_vars, even though it
1023       // contains pointers that are fixed up by dyld, which requires proper
1024       // alignment.
1025       if (isThreadLocalVariables(osec->flags))
1026         osec->align = std::max<uint32_t>(osec->align, target->wordSize);
1027
1028       getOrCreateOutputSegment(segname)->addOutputSection(osec);
1029     }
1030   }
1031
1032   for (SyntheticSection *ssec : syntheticSections) {
1033     auto it = concatOutputSections.find({ssec->segname, ssec->name});
1034     // We add all LinkEdit sections here because we don't know if they are
1035     // needed until their finalizeContents() methods get called later. While
1036     // this means that we add some redundant sections to __LINKEDIT, there is
1037     // is no redundancy in the output, as we do not emit section headers for
1038     // any LinkEdit sections.
1039     if (ssec->isNeeded() || ssec->segname == segment_names::linkEdit) {
1040       if (it == concatOutputSections.end()) {
1041         getOrCreateOutputSegment(ssec->segname)->addOutputSection(ssec);
1042       } else {
1043         fatal("section from " +
1044               toString(it->second->firstSection()->getFile()) +
1045               " conflicts with synthetic section " + ssec->segname + "," +
1046               ssec->name);
1047       }
1048     }
1049   }
1050
1051   // dyld requires __LINKEDIT segment to always exist (even if empty).
1052   linkEditSegment = getOrCreateOutputSegment(segment_names::linkEdit);
1053 }
1054
1055 void Writer::finalizeAddresses() {
1056   TimeTraceScope timeScope("Finalize addresses");
1057   uint64_t pageSize = target->getPageSize();
1058
1059   // We could parallelize this loop, but local benchmarking indicates it is
1060   // faster to do it all in the main thread.
1061   for (OutputSegment *seg : outputSegments) {
1062     if (seg == linkEditSegment)
1063       continue;
1064     for (OutputSection *osec : seg->getSections()) {
1065       if (!osec->isNeeded())
1066         continue;
1067       // Other kinds of OutputSections have already been finalized.
1068       if (auto *concatOsec = dyn_cast<ConcatOutputSection>(osec))
1069         concatOsec->finalizeContents();
1070     }
1071   }
1072
1073   // Ensure that segments (and the sections they contain) are allocated
1074   // addresses in ascending order, which dyld requires.
1075   //
1076   // Note that at this point, __LINKEDIT sections are empty, but we need to
1077   // determine addresses of other segments/sections before generating its
1078   // contents.
1079   for (OutputSegment *seg : outputSegments) {
1080     if (seg == linkEditSegment)
1081       continue;
1082     seg->addr = addr;
1083     assignAddresses(seg);
1084     // codesign / libstuff checks for segment ordering by verifying that
1085     // `fileOff + fileSize == next segment fileOff`. So we call
1086     // alignToPowerOf2() before (instead of after) computing fileSize to ensure
1087     // that the segments are contiguous. We handle addr / vmSize similarly for
1088     // the same reason.
1089     fileOff = alignToPowerOf2(fileOff, pageSize);
1090     addr = alignToPowerOf2(addr, pageSize);
1091     seg->vmSize = addr - seg->addr;
1092     seg->fileSize = fileOff - seg->fileOff;
1093     seg->assignAddressesToStartEndSymbols();
1094   }
1095 }
1096
1097 void Writer::finalizeLinkEditSegment() {
1098   TimeTraceScope timeScope("Finalize __LINKEDIT segment");
1099   // Fill __LINKEDIT contents.
1100   std::array<LinkEditSection *, 10> linkEditSections{
1101       in.rebase,         in.binding,
1102       in.weakBinding,    in.lazyBinding,
1103       in.exports,        in.chainedFixups,
1104       symtabSection,     indirectSymtabSection,
1105       dataInCodeSection, functionStartsSection,
1106   };
1107   SmallVector<std::shared_future<void>> threadFutures;
1108   threadFutures.reserve(linkEditSections.size());
1109   for (LinkEditSection *osec : linkEditSections)
1110     if (osec)
1111       threadFutures.emplace_back(threadPool.async(
1112           [](LinkEditSection *osec) { osec->finalizeContents(); }, osec));
1113   for (std::shared_future<void> &future : threadFutures)
1114     future.wait();
1115
1116   // Now that __LINKEDIT is filled out, do a proper calculation of its
1117   // addresses and offsets.
1118   linkEditSegment->addr = addr;
1119   assignAddresses(linkEditSegment);
1120   // No need to page-align fileOff / addr here since this is the last segment.
1121   linkEditSegment->vmSize = addr - linkEditSegment->addr;
1122   linkEditSegment->fileSize = fileOff - linkEditSegment->fileOff;
1123 }
1124
1125 void Writer::assignAddresses(OutputSegment *seg) {
1126   seg->fileOff = fileOff;
1127
1128   for (OutputSection *osec : seg->getSections()) {
1129     if (!osec->isNeeded())
1130       continue;
1131     addr = alignToPowerOf2(addr, osec->align);
1132     fileOff = alignToPowerOf2(fileOff, osec->align);
1133     osec->addr = addr;
1134     osec->fileOff = isZeroFill(osec->flags) ? 0 : fileOff;
1135     osec->finalize();
1136     osec->assignAddressesToStartEndSymbols();
1137
1138     addr += osec->getSize();
1139     fileOff += osec->getFileSize();
1140   }
1141 }
1142
1143 void Writer::openFile() {
1144   Expected<std::unique_ptr<FileOutputBuffer>> bufferOrErr =
1145       FileOutputBuffer::create(config->outputFile, fileOff,
1146                                FileOutputBuffer::F_executable);
1147
1148   if (!bufferOrErr)
1149     fatal("failed to open " + config->outputFile + ": " +
1150           llvm::toString(bufferOrErr.takeError()));
1151   buffer = std::move(*bufferOrErr);
1152   in.bufferStart = buffer->getBufferStart();
1153 }
1154
1155 void Writer::writeSections() {
1156   uint8_t *buf = buffer->getBufferStart();
1157   std::vector<const OutputSection *> osecs;
1158   for (const OutputSegment *seg : outputSegments)
1159     append_range(osecs, seg->getSections());
1160
1161   parallelForEach(osecs.begin(), osecs.end(), [&](const OutputSection *osec) {
1162     osec->writeTo(buf + osec->fileOff);
1163   });
1164 }
1165
1166 void Writer::applyOptimizationHints() {
1167   if (config->arch() != AK_arm64 || config->ignoreOptimizationHints)
1168     return;
1169
1170   uint8_t *buf = buffer->getBufferStart();
1171   TimeTraceScope timeScope("Apply linker optimization hints");
1172   parallelForEach(inputFiles, [buf](const InputFile *file) {
1173     if (const auto *objFile = dyn_cast<ObjFile>(file))
1174       target->applyOptimizationHints(buf, *objFile);
1175   });
1176 }
1177
1178 // In order to utilize multiple cores, we first split the buffer into chunks,
1179 // compute a hash for each chunk, and then compute a hash value of the hash
1180 // values.
1181 void Writer::writeUuid() {
1182   TimeTraceScope timeScope("Computing UUID");
1183
1184   ArrayRef<uint8_t> data{buffer->getBufferStart(), buffer->getBufferEnd()};
1185   std::vector<ArrayRef<uint8_t>> chunks = split(data, 1024 * 1024);
1186   // Leave one slot for filename
1187   std::vector<uint64_t> hashes(chunks.size() + 1);
1188   SmallVector<std::shared_future<void>> threadFutures;
1189   threadFutures.reserve(chunks.size());
1190   for (size_t i = 0; i < chunks.size(); ++i)
1191     threadFutures.emplace_back(threadPool.async(
1192         [&](size_t j) { hashes[j] = xxh3_64bits(chunks[j]); }, i));
1193   for (std::shared_future<void> &future : threadFutures)
1194     future.wait();
1195   // Append the output filename so that identical binaries with different names
1196   // don't get the same UUID.
1197   hashes[chunks.size()] = xxh3_64bits(sys::path::filename(config->finalOutput));
1198   uint64_t digest = xxh3_64bits({reinterpret_cast<uint8_t *>(hashes.data()),
1199                                  hashes.size() * sizeof(uint64_t)});
1200   uuidCommand->writeUuid(digest);
1201 }
1202
1203 // This is step 5 of the algorithm described in the class comment of
1204 // ChainedFixupsSection.
1205 void Writer::buildFixupChains() {
1206   if (!config->emitChainedFixups)
1207     return;
1208
1209   const std::vector<Location> &loc = in.chainedFixups->getLocations();
1210   if (loc.empty())
1211     return;
1212
1213   TimeTraceScope timeScope("Build fixup chains");
1214
1215   const uint64_t pageSize = target->getPageSize();
1216   constexpr uint32_t stride = 4; // for DYLD_CHAINED_PTR_64
1217
1218   for (size_t i = 0, count = loc.size(); i < count;) {
1219     const OutputSegment *oseg = loc[i].isec->parent->parent;
1220     uint8_t *buf = buffer->getBufferStart() + oseg->fileOff;
1221     uint64_t pageIdx = loc[i].offset / pageSize;
1222     ++i;
1223
1224     while (i < count && loc[i].isec->parent->parent == oseg &&
1225            (loc[i].offset / pageSize) == pageIdx) {
1226       uint64_t offset = loc[i].offset - loc[i - 1].offset;
1227
1228       auto fail = [&](Twine message) {
1229         error(loc[i].isec->getSegName() + "," + loc[i].isec->getName() +
1230               ", offset " +
1231               Twine(loc[i].offset - loc[i].isec->parent->getSegmentOffset()) +
1232               ": " + message);
1233       };
1234
1235       if (offset < target->wordSize)
1236         return fail("fixups overlap");
1237       if (offset % stride != 0)
1238         return fail(
1239             "fixups are unaligned (offset " + Twine(offset) +
1240             " is not a multiple of the stride). Re-link with -no_fixup_chains");
1241
1242       // The "next" field is in the same location for bind and rebase entries.
1243       reinterpret_cast<dyld_chained_ptr_64_bind *>(buf + loc[i - 1].offset)
1244           ->next = offset / stride;
1245       ++i;
1246     }
1247   }
1248 }
1249
1250 void Writer::writeCodeSignature() {
1251   if (codeSignatureSection) {
1252     TimeTraceScope timeScope("Write code signature");
1253     codeSignatureSection->writeHashes(buffer->getBufferStart());
1254   }
1255 }
1256
1257 void Writer::writeOutputFile() {
1258   TimeTraceScope timeScope("Write output file");
1259   openFile();
1260   reportPendingUndefinedSymbols();
1261   if (errorCount())
1262     return;
1263   writeSections();
1264   applyOptimizationHints();
1265   buildFixupChains();
1266   if (config->generateUuid)
1267     writeUuid();
1268   writeCodeSignature();
1269
1270   if (auto e = buffer->commit())
1271     fatal("failed to write output '" + buffer->getPath() +
1272           "': " + toString(std::move(e)));
1273 }
1274
1275 template <class LP> void Writer::run() {
1276   treatSpecialUndefineds();
1277   if (config->entry && needsBinding(config->entry))
1278     in.stubs->addEntry(config->entry);
1279
1280   // Canonicalization of all pointers to InputSections should be handled by
1281   // these two scan* methods. I.e. from this point onward, for all live
1282   // InputSections, we should have `isec->canonical() == isec`.
1283   scanSymbols();
1284   if (in.objcStubs->isNeeded())
1285     in.objcStubs->setUp();
1286   scanRelocations();
1287   if (in.initOffsets->isNeeded())
1288     in.initOffsets->setUp();
1289
1290   // Do not proceed if there were undefined or duplicate symbols.
1291   reportPendingUndefinedSymbols();
1292   reportPendingDuplicateSymbols();
1293   if (errorCount())
1294     return;
1295
1296   if (in.stubHelper && in.stubHelper->isNeeded())
1297     in.stubHelper->setUp();
1298
1299   if (in.objCImageInfo->isNeeded())
1300     in.objCImageInfo->finalizeContents();
1301
1302   // At this point, we should know exactly which output sections are needed,
1303   // courtesy of scanSymbols() and scanRelocations().
1304   createOutputSections<LP>();
1305
1306   // After this point, we create no new segments; HOWEVER, we might
1307   // yet create branch-range extension thunks for architectures whose
1308   // hardware call instructions have limited range, e.g., ARM(64).
1309   // The thunks are created as InputSections interspersed among
1310   // the ordinary __TEXT,_text InputSections.
1311   sortSegmentsAndSections();
1312   createLoadCommands<LP>();
1313   finalizeAddresses();
1314   threadPool.async([&] {
1315     if (LLVM_ENABLE_THREADS && config->timeTraceEnabled)
1316       timeTraceProfilerInitialize(config->timeTraceGranularity, "writeMapFile");
1317     writeMapFile();
1318     if (LLVM_ENABLE_THREADS && config->timeTraceEnabled)
1319       timeTraceProfilerFinishThread();
1320   });
1321   finalizeLinkEditSegment();
1322   writeOutputFile();
1323 }
1324
1325 template <class LP> void macho::writeResult() { Writer().run<LP>(); }
1326
1327 void macho::resetWriter() { LCDylib::resetInstanceCount(); }
1328
1329 void macho::createSyntheticSections() {
1330   in.header = make<MachHeaderSection>();
1331   if (config->dedupStrings)
1332     in.cStringSection =
1333         make<DeduplicatedCStringSection>(section_names::cString);
1334   else
1335     in.cStringSection = make<CStringSection>(section_names::cString);
1336   in.objcMethnameSection =
1337       make<DeduplicatedCStringSection>(section_names::objcMethname);
1338   in.wordLiteralSection = make<WordLiteralSection>();
1339   if (config->emitChainedFixups) {
1340     in.chainedFixups = make<ChainedFixupsSection>();
1341   } else {
1342     in.rebase = make<RebaseSection>();
1343     in.binding = make<BindingSection>();
1344     in.weakBinding = make<WeakBindingSection>();
1345     in.lazyBinding = make<LazyBindingSection>();
1346     in.lazyPointers = make<LazyPointerSection>();
1347     in.stubHelper = make<StubHelperSection>();
1348   }
1349   in.exports = make<ExportSection>();
1350   in.got = make<GotSection>();
1351   in.tlvPointers = make<TlvPointerSection>();
1352   in.stubs = make<StubsSection>();
1353   in.objcStubs = make<ObjCStubsSection>();
1354   in.unwindInfo = makeUnwindInfoSection();
1355   in.objCImageInfo = make<ObjCImageInfoSection>();
1356   in.initOffsets = make<InitOffsetsSection>();
1357
1358   // This section contains space for just a single word, and will be used by
1359   // dyld to cache an address to the image loader it uses.
1360   uint8_t *arr = bAlloc().Allocate<uint8_t>(target->wordSize);
1361   memset(arr, 0, target->wordSize);
1362   in.imageLoaderCache = makeSyntheticInputSection(
1363       segment_names::data, section_names::data, S_REGULAR,
1364       ArrayRef<uint8_t>{arr, target->wordSize},
1365       /*align=*/target->wordSize);
1366   // References from dyld are not visible to us, so ensure this section is
1367   // always treated as live.
1368   in.imageLoaderCache->live = true;
1369 }
1370
1371 OutputSection *macho::firstTLVDataSection = nullptr;
1372
1373 template void macho::writeResult<LP64>();
1374 template void macho::writeResult<ILP32>();