contrib/llvm-project/lld/COFF/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 "Config.h"
  11 #include "DLL.h"
  12 #include "InputFiles.h"
  13 #include "LLDMapFile.h"
  14 #include "MapFile.h"
  15 #include "PDB.h"
  16 #include "SymbolTable.h"
  17 #include "Symbols.h"
  18 #include "lld/Common/ErrorHandler.h"
  19 #include "lld/Common/Memory.h"
  20 #include "lld/Common/Timer.h"
  21 #include "llvm/ADT/DenseMap.h"
  22 #include "llvm/ADT/STLExtras.h"
  23 #include "llvm/ADT/StringSet.h"
  24 #include "llvm/ADT/StringSwitch.h"
  25 #include "llvm/Support/BinaryStreamReader.h"
  26 #include "llvm/Support/Debug.h"
  27 #include "llvm/Support/Endian.h"
  28 #include "llvm/Support/FileOutputBuffer.h"
  29 #include "llvm/Support/Parallel.h"
  30 #include "llvm/Support/Path.h"
  31 #include "llvm/Support/RandomNumberGenerator.h"
  32 #include "llvm/Support/xxhash.h"
  33 #include <algorithm>
  34 #include <cstdio>
  35 #include <map>
  36 #include <memory>
  37 #include <utility>
  38
  39 using namespace llvm;
  40 using namespace llvm::COFF;
  41 using namespace llvm::object;
  42 using namespace llvm::support;
  43 using namespace llvm::support::endian;
  44 using namespace lld;
  45 using namespace lld::coff;
  46
  47 /* To re-generate DOSProgram:
  48 $ cat > /tmp/DOSProgram.asm
  49 org 0
  50         ; Copy cs to ds.
  51         push cs
  52         pop ds
  53         ; Point ds:dx at the $-terminated string.
  54         mov dx, str
  55         ; Int 21/AH=09h: Write string to standard output.
  56         mov ah, 0x9
  57         int 0x21
  58         ; Int 21/AH=4Ch: Exit with return code (in AL).
  59         mov ax, 0x4C01
  60         int 0x21
  61 str:
  62         db 'This program cannot be run in DOS mode.$'
  63 align 8, db 0
  64 $ nasm -fbin /tmp/DOSProgram.asm -o /tmp/DOSProgram.bin
  65 $ xxd -i /tmp/DOSProgram.bin
  66 */
  67 static unsigned char dosProgram[] = {
  68   0x0e, 0x1f, 0xba, 0x0e, 0x00, 0xb4, 0x09, 0xcd, 0x21, 0xb8, 0x01, 0x4c,
  69   0xcd, 0x21, 0x54, 0x68, 0x69, 0x73, 0x20, 0x70, 0x72, 0x6f, 0x67, 0x72,
  70   0x61, 0x6d, 0x20, 0x63, 0x61, 0x6e, 0x6e, 0x6f, 0x74, 0x20, 0x62, 0x65,
  71   0x20, 0x72, 0x75, 0x6e, 0x20, 0x69, 0x6e, 0x20, 0x44, 0x4f, 0x53, 0x20,
  72   0x6d, 0x6f, 0x64, 0x65, 0x2e, 0x24, 0x00, 0x00
  73 };
  74 static_assert(sizeof(dosProgram) % 8 == 0,
  75               "DOSProgram size must be multiple of 8");
  76
  77 static const int dosStubSize = sizeof(dos_header) + sizeof(dosProgram);
  78 static_assert(dosStubSize % 8 == 0, "DOSStub size must be multiple of 8");
  79
  80 static const int numberOfDataDirectory = 16;
  81
  82 // Global vector of all output sections. After output sections are finalized,
  83 // this can be indexed by Chunk::getOutputSection.
  84 static std::vector<OutputSection *> outputSections;
  85
  86 OutputSection *Chunk::getOutputSection() const {
  87   return osidx == 0 ? nullptr : outputSections[osidx - 1];
  88 }
  89
  90 namespace {
  91
  92 class DebugDirectoryChunk : public NonSectionChunk {
  93 public:
  94   DebugDirectoryChunk(const std::vector<std::pair<COFF::DebugType, Chunk *>> &r,
  95                       bool writeRepro)
  96       : records(r), writeRepro(writeRepro) {}
  97
  98   size_t getSize() const override {
  99     return (records.size() + int(writeRepro)) * sizeof(debug_directory);
 100   }
 101
 102   void writeTo(uint8_t *b) const override {
 103     auto *d = reinterpret_cast<debug_directory *>(b);
 104
 105     for (const std::pair<COFF::DebugType, Chunk *>& record : records) {
 106       Chunk *c = record.second;
 107       OutputSection *os = c->getOutputSection();
 108       uint64_t offs = os->getFileOff() + (c->getRVA() - os->getRVA());
 109       fillEntry(d, record.first, c->getSize(), c->getRVA(), offs);
 110       ++d;
 111     }
 112
 113     if (writeRepro) {
 114       // FIXME: The COFF spec allows either a 0-sized entry to just say
 115       // "the timestamp field is really a hash", or a 4-byte size field
 116       // followed by that many bytes containing a longer hash (with the
 117       // lowest 4 bytes usually being the timestamp in little-endian order).
 118       // Consider storing the full 8 bytes computed by xxHash64 here.
 119       fillEntry(d, COFF::IMAGE_DEBUG_TYPE_REPRO, 0, 0, 0);
 120     }
 121   }
 122
 123   void setTimeDateStamp(uint32_t timeDateStamp) {
 124     for (support::ulittle32_t *tds : timeDateStamps)
 125       *tds = timeDateStamp;
 126   }
 127
 128 private:
 129   void fillEntry(debug_directory *d, COFF::DebugType debugType, size_t size,
 130                  uint64_t rva, uint64_t offs) const {
 131     d->Characteristics = 0;
 132     d->TimeDateStamp = 0;
 133     d->MajorVersion = 0;
 134     d->MinorVersion = 0;
 135     d->Type = debugType;
 136     d->SizeOfData = size;
 137     d->AddressOfRawData = rva;
 138     d->PointerToRawData = offs;
 139
 140     timeDateStamps.push_back(&d->TimeDateStamp);
 141   }
 142
 143   mutable std::vector<support::ulittle32_t *> timeDateStamps;
 144   const std::vector<std::pair<COFF::DebugType, Chunk *>> &records;
 145   bool writeRepro;
 146 };
 147
 148 class CVDebugRecordChunk : public NonSectionChunk {
 149 public:
 150   size_t getSize() const override {
 151     return sizeof(codeview::DebugInfo) + config->pdbAltPath.size() + 1;
 152   }
 153
 154   void writeTo(uint8_t *b) const override {
 155     // Save off the DebugInfo entry to backfill the file signature (build id)
 156     // in Writer::writeBuildId
 157     buildId = reinterpret_cast<codeview::DebugInfo *>(b);
 158
 159     // variable sized field (PDB Path)
 160     char *p = reinterpret_cast<char *>(b + sizeof(*buildId));
 161     if (!config->pdbAltPath.empty())
 162       memcpy(p, config->pdbAltPath.data(), config->pdbAltPath.size());
 163     p[config->pdbAltPath.size()] = '\0';
 164   }
 165
 166   mutable codeview::DebugInfo *buildId = nullptr;
 167 };
 168
 169 class ExtendedDllCharacteristicsChunk : public NonSectionChunk {
 170 public:
 171   ExtendedDllCharacteristicsChunk(uint32_t c) : characteristics(c) {}
 172
 173   size_t getSize() const override { return 4; }
 174
 175   void writeTo(uint8_t *buf) const override { write32le(buf, characteristics); }
 176
 177   uint32_t characteristics = 0;
 178 };
 179
 180 // PartialSection represents a group of chunks that contribute to an
 181 // OutputSection. Collating a collection of PartialSections of same name and
 182 // characteristics constitutes the OutputSection.
 183 class PartialSectionKey {
 184 public:
 185   StringRef name;
 186   unsigned characteristics;
 187
 188   bool operator<(const PartialSectionKey &other) const {
 189     int c = name.compare(other.name);
 190     if (c == 1)
 191       return false;
 192     if (c == 0)
 193       return characteristics < other.characteristics;
 194     return true;
 195   }
 196 };
 197
 198 // The writer writes a SymbolTable result to a file.
 199 class Writer {
 200 public:
 201   Writer() : buffer(errorHandler().outputBuffer) {}
 202   void run();
 203
 204 private:
 205   void createSections();
 206   void createMiscChunks();
 207   void createImportTables();
 208   void appendImportThunks();
 209   void locateImportTables();
 210   void createExportTable();
 211   void mergeSections();
 212   void removeUnusedSections();
 213   void assignAddresses();
 214   void finalizeAddresses();
 215   void removeEmptySections();
 216   void assignOutputSectionIndices();
 217   void createSymbolAndStringTable();
 218   void openFile(StringRef outputPath);
 219   template <typename PEHeaderTy> void writeHeader();
 220   void createSEHTable();
 221   void createRuntimePseudoRelocs();
 222   void insertCtorDtorSymbols();
 223   void createGuardCFTables();
 224   void markSymbolsForRVATable(ObjFile *file,
 225                               ArrayRef<SectionChunk *> symIdxChunks,
 226                               SymbolRVASet &tableSymbols);
 227   void maybeAddRVATable(SymbolRVASet tableSymbols, StringRef tableSym,
 228                         StringRef countSym);
 229   void setSectionPermissions();
 230   void writeSections();
 231   void writeBuildId();
 232   void sortExceptionTable();
 233   void sortCRTSectionChunks(std::vector<Chunk *> &chunks);
 234   void addSyntheticIdata();
 235   void fixPartialSectionChars(StringRef name, uint32_t chars);
 236   bool fixGnuImportChunks();
 237   PartialSection *createPartialSection(StringRef name, uint32_t outChars);
 238   PartialSection *findPartialSection(StringRef name, uint32_t outChars);
 239
 240   llvm::Optional<coff_symbol16> createSymbol(Defined *d);
 241   size_t addEntryToStringTable(StringRef str);
 242
 243   OutputSection *findSection(StringRef name);
 244   void addBaserels();
 245   void addBaserelBlocks(std::vector<Baserel> &v);
 246
 247   uint32_t getSizeOfInitializedData();
 248
 249   std::unique_ptr<FileOutputBuffer> &buffer;
 250   std::map<PartialSectionKey, PartialSection *> partialSections;
 251   std::vector<char> strtab;
 252   std::vector<llvm::object::coff_symbol16> outputSymtab;
 253   IdataContents idata;
 254   Chunk *importTableStart = nullptr;
 255   uint64_t importTableSize = 0;
 256   Chunk *edataStart = nullptr;
 257   Chunk *edataEnd = nullptr;
 258   Chunk *iatStart = nullptr;
 259   uint64_t iatSize = 0;
 260   DelayLoadContents delayIdata;
 261   EdataContents edata;
 262   bool setNoSEHCharacteristic = false;
 263
 264   DebugDirectoryChunk *debugDirectory = nullptr;
 265   std::vector<std::pair<COFF::DebugType, Chunk *>> debugRecords;
 266   CVDebugRecordChunk *buildId = nullptr;
 267   ArrayRef<uint8_t> sectionTable;
 268
 269   uint64_t fileSize;
 270   uint32_t pointerToSymbolTable = 0;
 271   uint64_t sizeOfImage;
 272   uint64_t sizeOfHeaders;
 273
 274   OutputSection *textSec;
 275   OutputSection *rdataSec;
 276   OutputSection *buildidSec;
 277   OutputSection *dataSec;
 278   OutputSection *pdataSec;
 279   OutputSection *idataSec;
 280   OutputSection *edataSec;
 281   OutputSection *didatSec;
 282   OutputSection *rsrcSec;
 283   OutputSection *relocSec;
 284   OutputSection *ctorsSec;
 285   OutputSection *dtorsSec;
 286
 287   // The first and last .pdata sections in the output file.
 288   //
 289   // We need to keep track of the location of .pdata in whichever section it
 290   // gets merged into so that we can sort its contents and emit a correct data
 291   // directory entry for the exception table. This is also the case for some
 292   // other sections (such as .edata) but because the contents of those sections
 293   // are entirely linker-generated we can keep track of their locations using
 294   // the chunks that the linker creates. All .pdata chunks come from input
 295   // files, so we need to keep track of them separately.
 296   Chunk *firstPdata = nullptr;
 297   Chunk *lastPdata;
 298 };
 299 } // anonymous namespace
 300
 301 static Timer codeLayoutTimer("Code Layout", Timer::root());
 302 static Timer diskCommitTimer("Commit Output File", Timer::root());
 303
 304 void lld::coff::writeResult() { Writer().run(); }
 305
 306 void OutputSection::addChunk(Chunk *c) {
 307   chunks.push_back(c);
 308 }
 309
 310 void OutputSection::insertChunkAtStart(Chunk *c) {
 311   chunks.insert(chunks.begin(), c);
 312 }
 313
 314 void OutputSection::setPermissions(uint32_t c) {
 315   header.Characteristics &= ~permMask;
 316   header.Characteristics |= c;
 317 }
 318
 319 void OutputSection::merge(OutputSection *other) {
 320   chunks.insert(chunks.end(), other->chunks.begin(), other->chunks.end());
 321   other->chunks.clear();
 322   contribSections.insert(contribSections.end(), other->contribSections.begin(),
 323                          other->contribSections.end());
 324   other->contribSections.clear();
 325 }
 326
 327 // Write the section header to a given buffer.
 328 void OutputSection::writeHeaderTo(uint8_t *buf) {
 329   auto *hdr = reinterpret_cast<coff_section *>(buf);
 330   *hdr = header;
 331   if (stringTableOff) {
 332     // If name is too long, write offset into the string table as a name.
 333     sprintf(hdr->Name, "/%d", stringTableOff);
 334   } else {
 335     assert(!config->debug || name.size() <= COFF::NameSize ||
 336            (hdr->Characteristics & IMAGE_SCN_MEM_DISCARDABLE) == 0);
 337     strncpy(hdr->Name, name.data(),
 338             std::min(name.size(), (size_t)COFF::NameSize));
 339   }
 340 }
 341
 342 void OutputSection::addContributingPartialSection(PartialSection *sec) {
 343   contribSections.push_back(sec);
 344 }
 345
 346 // Check whether the target address S is in range from a relocation
 347 // of type relType at address P.
 348 static bool isInRange(uint16_t relType, uint64_t s, uint64_t p, int margin) {
 349   if (config->machine == ARMNT) {
 350     int64_t diff = AbsoluteDifference(s, p + 4) + margin;
 351     switch (relType) {
 352     case IMAGE_REL_ARM_BRANCH20T:
 353       return isInt<21>(diff);
 354     case IMAGE_REL_ARM_BRANCH24T:
 355     case IMAGE_REL_ARM_BLX23T:
 356       return isInt<25>(diff);
 357     default:
 358       return true;
 359     }
 360   } else if (config->machine == ARM64) {
 361     int64_t diff = AbsoluteDifference(s, p) + margin;
 362     switch (relType) {
 363     case IMAGE_REL_ARM64_BRANCH26:
 364       return isInt<28>(diff);
 365     case IMAGE_REL_ARM64_BRANCH19:
 366       return isInt<21>(diff);
 367     case IMAGE_REL_ARM64_BRANCH14:
 368       return isInt<16>(diff);
 369     default:
 370       return true;
 371     }
 372   } else {
 373     llvm_unreachable("Unexpected architecture");
 374   }
 375 }
 376
 377 // Return the last thunk for the given target if it is in range,
 378 // or create a new one.
 379 static std::pair<Defined *, bool>
 380 getThunk(DenseMap<uint64_t, Defined *> &lastThunks, Defined *target, uint64_t p,
 381          uint16_t type, int margin) {
 382   Defined *&lastThunk = lastThunks[target->getRVA()];
 383   if (lastThunk && isInRange(type, lastThunk->getRVA(), p, margin))
 384     return {lastThunk, false};
 385   Chunk *c;
 386   switch (config->machine) {
 387   case ARMNT:
 388     c = make<RangeExtensionThunkARM>(target);
 389     break;
 390   case ARM64:
 391     c = make<RangeExtensionThunkARM64>(target);
 392     break;
 393   default:
 394     llvm_unreachable("Unexpected architecture");
 395   }
 396   Defined *d = make<DefinedSynthetic>("", c);
 397   lastThunk = d;
 398   return {d, true};
 399 }
 400
 401 // This checks all relocations, and for any relocation which isn't in range
 402 // it adds a thunk after the section chunk that contains the relocation.
 403 // If the latest thunk for the specific target is in range, that is used
 404 // instead of creating a new thunk. All range checks are done with the
 405 // specified margin, to make sure that relocations that originally are in
 406 // range, but only barely, also get thunks - in case other added thunks makes
 407 // the target go out of range.
 408 //
 409 // After adding thunks, we verify that all relocations are in range (with
 410 // no extra margin requirements). If this failed, we restart (throwing away
 411 // the previously created thunks) and retry with a wider margin.
 412 static bool createThunks(OutputSection *os, int margin) {
 413   bool addressesChanged = false;
 414   DenseMap<uint64_t, Defined *> lastThunks;
 415   DenseMap<std::pair<ObjFile *, Defined *>, uint32_t> thunkSymtabIndices;
 416   size_t thunksSize = 0;
 417   // Recheck Chunks.size() each iteration, since we can insert more
 418   // elements into it.
 419   for (size_t i = 0; i != os->chunks.size(); ++i) {
 420     SectionChunk *sc = dyn_cast_or_null<SectionChunk>(os->chunks[i]);
 421     if (!sc)
 422       continue;
 423     size_t thunkInsertionSpot = i + 1;
 424
 425     // Try to get a good enough estimate of where new thunks will be placed.
 426     // Offset this by the size of the new thunks added so far, to make the
 427     // estimate slightly better.
 428     size_t thunkInsertionRVA = sc->getRVA() + sc->getSize() + thunksSize;
 429     ObjFile *file = sc->file;
 430     std::vector<std::pair<uint32_t, uint32_t>> relocReplacements;
 431     ArrayRef<coff_relocation> originalRelocs =
 432         file->getCOFFObj()->getRelocations(sc->header);
 433     for (size_t j = 0, e = originalRelocs.size(); j < e; ++j) {
 434       const coff_relocation &rel = originalRelocs[j];
 435       Symbol *relocTarget = file->getSymbol(rel.SymbolTableIndex);
 436
 437       // The estimate of the source address P should be pretty accurate,
 438       // but we don't know whether the target Symbol address should be
 439       // offset by thunksSize or not (or by some of thunksSize but not all of
 440       // it), giving us some uncertainty once we have added one thunk.
 441       uint64_t p = sc->getRVA() + rel.VirtualAddress + thunksSize;
 442
 443       Defined *sym = dyn_cast_or_null<Defined>(relocTarget);
 444       if (!sym)
 445         continue;
 446
 447       uint64_t s = sym->getRVA();
 448
 449       if (isInRange(rel.Type, s, p, margin))
 450         continue;
 451
 452       // If the target isn't in range, hook it up to an existing or new
 453       // thunk.
 454       Defined *thunk;
 455       bool wasNew;
 456       std::tie(thunk, wasNew) = getThunk(lastThunks, sym, p, rel.Type, margin);
 457       if (wasNew) {
 458         Chunk *thunkChunk = thunk->getChunk();
 459         thunkChunk->setRVA(
 460             thunkInsertionRVA); // Estimate of where it will be located.
 461         os->chunks.insert(os->chunks.begin() + thunkInsertionSpot, thunkChunk);
 462         thunkInsertionSpot++;
 463         thunksSize += thunkChunk->getSize();
 464         thunkInsertionRVA += thunkChunk->getSize();
 465         addressesChanged = true;
 466       }
 467
 468       // To redirect the relocation, add a symbol to the parent object file's
 469       // symbol table, and replace the relocation symbol table index with the
 470       // new index.
 471       auto insertion = thunkSymtabIndices.insert({{file, thunk}, ~0U});
 472       uint32_t &thunkSymbolIndex = insertion.first->second;
 473       if (insertion.second)
 474         thunkSymbolIndex = file->addRangeThunkSymbol(thunk);
 475       relocReplacements.push_back({j, thunkSymbolIndex});
 476     }
 477
 478     // Get a writable copy of this section's relocations so they can be
 479     // modified. If the relocations point into the object file, allocate new
 480     // memory. Otherwise, this must be previously allocated memory that can be
 481     // modified in place.
 482     ArrayRef<coff_relocation> curRelocs = sc->getRelocs();
 483     MutableArrayRef<coff_relocation> newRelocs;
 484     if (originalRelocs.data() == curRelocs.data()) {
 485       newRelocs = makeMutableArrayRef(
 486           bAlloc.Allocate<coff_relocation>(originalRelocs.size()),
 487           originalRelocs.size());
 488     } else {
 489       newRelocs = makeMutableArrayRef(
 490           const_cast<coff_relocation *>(curRelocs.data()), curRelocs.size());
 491     }
 492
 493     // Copy each relocation, but replace the symbol table indices which need
 494     // thunks.
 495     auto nextReplacement = relocReplacements.begin();
 496     auto endReplacement = relocReplacements.end();
 497     for (size_t i = 0, e = originalRelocs.size(); i != e; ++i) {
 498       newRelocs[i] = originalRelocs[i];
 499       if (nextReplacement != endReplacement && nextReplacement->first == i) {
 500         newRelocs[i].SymbolTableIndex = nextReplacement->second;
 501         ++nextReplacement;
 502       }
 503     }
 504
 505     sc->setRelocs(newRelocs);
 506   }
 507   return addressesChanged;
 508 }
 509
 510 // Verify that all relocations are in range, with no extra margin requirements.
 511 static bool verifyRanges(const std::vector<Chunk *> chunks) {
 512   for (Chunk *c : chunks) {
 513     SectionChunk *sc = dyn_cast_or_null<SectionChunk>(c);
 514     if (!sc)
 515       continue;
 516
 517     ArrayRef<coff_relocation> relocs = sc->getRelocs();
 518     for (size_t j = 0, e = relocs.size(); j < e; ++j) {
 519       const coff_relocation &rel = relocs[j];
 520       Symbol *relocTarget = sc->file->getSymbol(rel.SymbolTableIndex);
 521
 522       Defined *sym = dyn_cast_or_null<Defined>(relocTarget);
 523       if (!sym)
 524         continue;
 525
 526       uint64_t p = sc->getRVA() + rel.VirtualAddress;
 527       uint64_t s = sym->getRVA();
 528
 529       if (!isInRange(rel.Type, s, p, 0))
 530         return false;
 531     }
 532   }
 533   return true;
 534 }
 535
 536 // Assign addresses and add thunks if necessary.
 537 void Writer::finalizeAddresses() {
 538   assignAddresses();
 539   if (config->machine != ARMNT && config->machine != ARM64)
 540     return;
 541
 542   size_t origNumChunks = 0;
 543   for (OutputSection *sec : outputSections) {
 544     sec->origChunks = sec->chunks;
 545     origNumChunks += sec->chunks.size();
 546   }
 547
 548   int pass = 0;
 549   int margin = 1024 * 100;
 550   while (true) {
 551     // First check whether we need thunks at all, or if the previous pass of
 552     // adding them turned out ok.
 553     bool rangesOk = true;
 554     size_t numChunks = 0;
 555     for (OutputSection *sec : outputSections) {
 556       if (!verifyRanges(sec->chunks)) {
 557         rangesOk = false;
 558         break;
 559       }
 560       numChunks += sec->chunks.size();
 561     }
 562     if (rangesOk) {
 563       if (pass > 0)
 564         log("Added " + Twine(numChunks - origNumChunks) + " thunks with " +
 565             "margin " + Twine(margin) + " in " + Twine(pass) + " passes");
 566       return;
 567     }
 568
 569     if (pass >= 10)
 570       fatal("adding thunks hasn't converged after " + Twine(pass) + " passes");
 571
 572     if (pass > 0) {
 573       // If the previous pass didn't work out, reset everything back to the
 574       // original conditions before retrying with a wider margin. This should
 575       // ideally never happen under real circumstances.
 576       for (OutputSection *sec : outputSections)
 577         sec->chunks = sec->origChunks;
 578       margin *= 2;
 579     }
 580
 581     // Try adding thunks everywhere where it is needed, with a margin
 582     // to avoid things going out of range due to the added thunks.
 583     bool addressesChanged = false;
 584     for (OutputSection *sec : outputSections)
 585       addressesChanged |= createThunks(sec, margin);
 586     // If the verification above thought we needed thunks, we should have
 587     // added some.
 588     assert(addressesChanged);
 589
 590     // Recalculate the layout for the whole image (and verify the ranges at
 591     // the start of the next round).
 592     assignAddresses();
 593
 594     pass++;
 595   }
 596 }
 597
 598 // The main function of the writer.
 599 void Writer::run() {
 600   ScopedTimer t1(codeLayoutTimer);
 601
 602   createImportTables();
 603   createSections();
 604   createMiscChunks();
 605   appendImportThunks();
 606   createExportTable();
 607   mergeSections();
 608   removeUnusedSections();
 609   finalizeAddresses();
 610   removeEmptySections();
 611   assignOutputSectionIndices();
 612   setSectionPermissions();
 613   createSymbolAndStringTable();
 614
 615   if (fileSize > UINT32_MAX)
 616     fatal("image size (" + Twine(fileSize) + ") " +
 617         "exceeds maximum allowable size (" + Twine(UINT32_MAX) + ")");
 618
 619   openFile(config->outputFile);
 620   if (config->is64()) {
 621     writeHeader<pe32plus_header>();
 622   } else {
 623     writeHeader<pe32_header>();
 624   }
 625   writeSections();
 626   sortExceptionTable();
 627
 628   t1.stop();
 629
 630   if (!config->pdbPath.empty() && config->debug) {
 631     assert(buildId);
 632     createPDB(symtab, outputSections, sectionTable, buildId->buildId);
 633   }
 634   writeBuildId();
 635
 636   writeLLDMapFile(outputSections);
 637   writeMapFile(outputSections);
 638
 639   if (errorCount())
 640     return;
 641
 642   ScopedTimer t2(diskCommitTimer);
 643   if (auto e = buffer->commit())
 644     fatal("failed to write the output file: " + toString(std::move(e)));
 645 }
 646
 647 static StringRef getOutputSectionName(StringRef name) {
 648   StringRef s = name.split('$').first;
 649
 650   // Treat a later period as a separator for MinGW, for sections like
 651   // ".ctors.01234".
 652   return s.substr(0, s.find('.', 1));
 653 }
 654
 655 // For /order.
 656 static void sortBySectionOrder(std::vector<Chunk *> &chunks) {
 657   auto getPriority = [](const Chunk *c) {
 658     if (auto *sec = dyn_cast<SectionChunk>(c))
 659       if (sec->sym)
 660         return config->order.lookup(sec->sym->getName());
 661     return 0;
 662   };
 663
 664   llvm::stable_sort(chunks, [=](const Chunk *a, const Chunk *b) {
 665     return getPriority(a) < getPriority(b);
 666   });
 667 }
 668
 669 // Change the characteristics of existing PartialSections that belong to the
 670 // section Name to Chars.
 671 void Writer::fixPartialSectionChars(StringRef name, uint32_t chars) {
 672   for (auto it : partialSections) {
 673     PartialSection *pSec = it.second;
 674     StringRef curName = pSec->name;
 675     if (!curName.consume_front(name) ||
 676         (!curName.empty() && !curName.startswith("$")))
 677       continue;
 678     if (pSec->characteristics == chars)
 679       continue;
 680     PartialSection *destSec = createPartialSection(pSec->name, chars);
 681     destSec->chunks.insert(destSec->chunks.end(), pSec->chunks.begin(),
 682                            pSec->chunks.end());
 683     pSec->chunks.clear();
 684   }
 685 }
 686
 687 // Sort concrete section chunks from GNU import libraries.
 688 //
 689 // GNU binutils doesn't use short import files, but instead produces import
 690 // libraries that consist of object files, with section chunks for the .idata$*
 691 // sections. These are linked just as regular static libraries. Each import
 692 // library consists of one header object, one object file for every imported
 693 // symbol, and one trailer object. In order for the .idata tables/lists to
 694 // be formed correctly, the section chunks within each .idata$* section need
 695 // to be grouped by library, and sorted alphabetically within each library
 696 // (which makes sure the header comes first and the trailer last).
 697 bool Writer::fixGnuImportChunks() {
 698   uint32_t rdata = IMAGE_SCN_CNT_INITIALIZED_DATA | IMAGE_SCN_MEM_READ;
 699
 700   // Make sure all .idata$* section chunks are mapped as RDATA in order to
 701   // be sorted into the same sections as our own synthesized .idata chunks.
 702   fixPartialSectionChars(".idata", rdata);
 703
 704   bool hasIdata = false;
 705   // Sort all .idata$* chunks, grouping chunks from the same library,
 706   // with alphabetical ordering of the object fils within a library.
 707   for (auto it : partialSections) {
 708     PartialSection *pSec = it.second;
 709     if (!pSec->name.startswith(".idata"))
 710       continue;
 711
 712     if (!pSec->chunks.empty())
 713       hasIdata = true;
 714     llvm::stable_sort(pSec->chunks, [&](Chunk *s, Chunk *t) {
 715       SectionChunk *sc1 = dyn_cast_or_null<SectionChunk>(s);
 716       SectionChunk *sc2 = dyn_cast_or_null<SectionChunk>(t);
 717       if (!sc1 || !sc2) {
 718         // if SC1, order them ascending. If SC2 or both null,
 719         // S is not less than T.
 720         return sc1 != nullptr;
 721       }
 722       // Make a string with "libraryname/objectfile" for sorting, achieving
 723       // both grouping by library and sorting of objects within a library,
 724       // at once.
 725       std::string key1 =
 726           (sc1->file->parentName + "/" + sc1->file->getName()).str();
 727       std::string key2 =
 728           (sc2->file->parentName + "/" + sc2->file->getName()).str();
 729       return key1 < key2;
 730     });
 731   }
 732   return hasIdata;
 733 }
 734
 735 // Add generated idata chunks, for imported symbols and DLLs, and a
 736 // terminator in .idata$2.
 737 void Writer::addSyntheticIdata() {
 738   uint32_t rdata = IMAGE_SCN_CNT_INITIALIZED_DATA | IMAGE_SCN_MEM_READ;
 739   idata.create();
 740
 741   // Add the .idata content in the right section groups, to allow
 742   // chunks from other linked in object files to be grouped together.
 743   // See Microsoft PE/COFF spec 5.4 for details.
 744   auto add = [&](StringRef n, std::vector<Chunk *> &v) {
 745     PartialSection *pSec = createPartialSection(n, rdata);
 746     pSec->chunks.insert(pSec->chunks.end(), v.begin(), v.end());
 747   };
 748
 749   // The loader assumes a specific order of data.
 750   // Add each type in the correct order.
 751   add(".idata$2", idata.dirs);
 752   add(".idata$4", idata.lookups);
 753   add(".idata$5", idata.addresses);
 754   if (!idata.hints.empty())
 755     add(".idata$6", idata.hints);
 756   add(".idata$7", idata.dllNames);
 757 }
 758
 759 // Locate the first Chunk and size of the import directory list and the
 760 // IAT.
 761 void Writer::locateImportTables() {
 762   uint32_t rdata = IMAGE_SCN_CNT_INITIALIZED_DATA | IMAGE_SCN_MEM_READ;
 763
 764   if (PartialSection *importDirs = findPartialSection(".idata$2", rdata)) {
 765     if (!importDirs->chunks.empty())
 766       importTableStart = importDirs->chunks.front();
 767     for (Chunk *c : importDirs->chunks)
 768       importTableSize += c->getSize();
 769   }
 770
 771   if (PartialSection *importAddresses = findPartialSection(".idata$5", rdata)) {
 772     if (!importAddresses->chunks.empty())
 773       iatStart = importAddresses->chunks.front();
 774     for (Chunk *c : importAddresses->chunks)
 775       iatSize += c->getSize();
 776   }
 777 }
 778
 779 // Return whether a SectionChunk's suffix (the dollar and any trailing
 780 // suffix) should be removed and sorted into the main suffixless
 781 // PartialSection.
 782 static bool shouldStripSectionSuffix(SectionChunk *sc, StringRef name) {
 783   // On MinGW, comdat groups are formed by putting the comdat group name
 784   // after the '$' in the section name. For .eh_frame$<symbol>, that must
 785   // still be sorted before the .eh_frame trailer from crtend.o, thus just
 786   // strip the section name trailer. For other sections, such as
 787   // .tls$$<symbol> (where non-comdat .tls symbols are otherwise stored in
 788   // ".tls$"), they must be strictly sorted after .tls. And for the
 789   // hypothetical case of comdat .CRT$XCU, we definitely need to keep the
 790   // suffix for sorting. Thus, to play it safe, only strip the suffix for
 791   // the standard sections.
 792   if (!config->mingw)
 793     return false;
 794   if (!sc || !sc->isCOMDAT())
 795     return false;
 796   return name.startswith(".text$") || name.startswith(".data$") ||
 797          name.startswith(".rdata$") || name.startswith(".pdata$") ||
 798          name.startswith(".xdata$") || name.startswith(".eh_frame$");
 799 }
 800
 801 // Create output section objects and add them to OutputSections.
 802 void Writer::createSections() {
 803   // First, create the builtin sections.
 804   const uint32_t data = IMAGE_SCN_CNT_INITIALIZED_DATA;
 805   const uint32_t bss = IMAGE_SCN_CNT_UNINITIALIZED_DATA;
 806   const uint32_t code = IMAGE_SCN_CNT_CODE;
 807   const uint32_t discardable = IMAGE_SCN_MEM_DISCARDABLE;
 808   const uint32_t r = IMAGE_SCN_MEM_READ;
 809   const uint32_t w = IMAGE_SCN_MEM_WRITE;
 810   const uint32_t x = IMAGE_SCN_MEM_EXECUTE;
 811
 812   SmallDenseMap<std::pair<StringRef, uint32_t>, OutputSection *> sections;
 813   auto createSection = [&](StringRef name, uint32_t outChars) {
 814     OutputSection *&sec = sections[{name, outChars}];
 815     if (!sec) {
 816       sec = make<OutputSection>(name, outChars);
 817       outputSections.push_back(sec);
 818     }
 819     return sec;
 820   };
 821
 822   // Try to match the section order used by link.exe.
 823   textSec = createSection(".text", code | r | x);
 824   createSection(".bss", bss | r | w);
 825   rdataSec = createSection(".rdata", data | r);
 826   buildidSec = createSection(".buildid", data | r);
 827   dataSec = createSection(".data", data | r | w);
 828   pdataSec = createSection(".pdata", data | r);
 829   idataSec = createSection(".idata", data | r);
 830   edataSec = createSection(".edata", data | r);
 831   didatSec = createSection(".didat", data | r);
 832   rsrcSec = createSection(".rsrc", data | r);
 833   relocSec = createSection(".reloc", data | discardable | r);
 834   ctorsSec = createSection(".ctors", data | r | w);
 835   dtorsSec = createSection(".dtors", data | r | w);
 836
 837   // Then bin chunks by name and output characteristics.
 838   for (Chunk *c : symtab->getChunks()) {
 839     auto *sc = dyn_cast<SectionChunk>(c);
 840     if (sc && !sc->live) {
 841       if (config->verbose)
 842         sc->printDiscardedMessage();
 843       continue;
 844     }
 845     StringRef name = c->getSectionName();
 846     if (shouldStripSectionSuffix(sc, name))
 847       name = name.split('$').first;
 848     PartialSection *pSec = createPartialSection(name,
 849                                                 c->getOutputCharacteristics());
 850     pSec->chunks.push_back(c);
 851   }
 852
 853   fixPartialSectionChars(".rsrc", data | r);
 854   fixPartialSectionChars(".edata", data | r);
 855   // Even in non MinGW cases, we might need to link against GNU import
 856   // libraries.
 857   bool hasIdata = fixGnuImportChunks();
 858   if (!idata.empty())
 859     hasIdata = true;
 860
 861   if (hasIdata)
 862     addSyntheticIdata();
 863
 864   // Process an /order option.
 865   if (!config->order.empty())
 866     for (auto it : partialSections)
 867       sortBySectionOrder(it.second->chunks);
 868
 869   if (hasIdata)
 870     locateImportTables();
 871
 872   // Then create an OutputSection for each section.
 873   // '$' and all following characters in input section names are
 874   // discarded when determining output section. So, .text$foo
 875   // contributes to .text, for example. See PE/COFF spec 3.2.
 876   for (auto it : partialSections) {
 877     PartialSection *pSec = it.second;
 878     StringRef name = getOutputSectionName(pSec->name);
 879     uint32_t outChars = pSec->characteristics;
 880
 881     if (name == ".CRT") {
 882       // In link.exe, there is a special case for the I386 target where .CRT
 883       // sections are treated as if they have output characteristics DATA | R if
 884       // their characteristics are DATA | R | W. This implements the same
 885       // special case for all architectures.
 886       outChars = data | r;
 887
 888       log("Processing section " + pSec->name + " -> " + name);
 889
 890       sortCRTSectionChunks(pSec->chunks);
 891     }
 892
 893     OutputSection *sec = createSection(name, outChars);
 894     for (Chunk *c : pSec->chunks)
 895       sec->addChunk(c);
 896
 897     sec->addContributingPartialSection(pSec);
 898   }
 899
 900   // Finally, move some output sections to the end.
 901   auto sectionOrder = [&](const OutputSection *s) {
 902     // Move DISCARDABLE (or non-memory-mapped) sections to the end of file
 903     // because the loader cannot handle holes. Stripping can remove other
 904     // discardable ones than .reloc, which is first of them (created early).
 905     if (s->header.Characteristics & IMAGE_SCN_MEM_DISCARDABLE)
 906       return 2;
 907     // .rsrc should come at the end of the non-discardable sections because its
 908     // size may change by the Win32 UpdateResources() function, causing
 909     // subsequent sections to move (see https://crbug.com/827082).
 910     if (s == rsrcSec)
 911       return 1;
 912     return 0;
 913   };
 914   llvm::stable_sort(outputSections,
 915                     [&](const OutputSection *s, const OutputSection *t) {
 916                       return sectionOrder(s) < sectionOrder(t);
 917                     });
 918 }
 919
 920 void Writer::createMiscChunks() {
 921   for (MergeChunk *p : MergeChunk::instances) {
 922     if (p) {
 923       p->finalizeContents();
 924       rdataSec->addChunk(p);
 925     }
 926   }
 927
 928   // Create thunks for locally-dllimported symbols.
 929   if (!symtab->localImportChunks.empty()) {
 930     for (Chunk *c : symtab->localImportChunks)
 931       rdataSec->addChunk(c);
 932   }
 933
 934   // Create Debug Information Chunks
 935   OutputSection *debugInfoSec = config->mingw ? buildidSec : rdataSec;
 936   if (config->debug || config->repro || config->cetCompat) {
 937     debugDirectory = make<DebugDirectoryChunk>(debugRecords, config->repro);
 938     debugDirectory->setAlignment(4);
 939     debugInfoSec->addChunk(debugDirectory);
 940   }
 941
 942   if (config->debug) {
 943     // Make a CVDebugRecordChunk even when /DEBUG:CV is not specified.  We
 944     // output a PDB no matter what, and this chunk provides the only means of
 945     // allowing a debugger to match a PDB and an executable.  So we need it even
 946     // if we're ultimately not going to write CodeView data to the PDB.
 947     buildId = make<CVDebugRecordChunk>();
 948     debugRecords.push_back({COFF::IMAGE_DEBUG_TYPE_CODEVIEW, buildId});
 949   }
 950
 951   if (config->cetCompat) {
 952     ExtendedDllCharacteristicsChunk *extendedDllChars =
 953         make<ExtendedDllCharacteristicsChunk>(
 954             IMAGE_DLL_CHARACTERISTICS_EX_CET_COMPAT);
 955     debugRecords.push_back(
 956         {COFF::IMAGE_DEBUG_TYPE_EX_DLLCHARACTERISTICS, extendedDllChars});
 957   }
 958
 959   if (debugRecords.size() > 0) {
 960     for (std::pair<COFF::DebugType, Chunk *> r : debugRecords)
 961       debugInfoSec->addChunk(r.second);
 962   }
 963
 964   // Create SEH table. x86-only.
 965   if (config->safeSEH)
 966     createSEHTable();
 967
 968   // Create /guard:cf tables if requested.
 969   if (config->guardCF != GuardCFLevel::Off)
 970     createGuardCFTables();
 971
 972   if (config->autoImport)
 973     createRuntimePseudoRelocs();
 974
 975   if (config->mingw)
 976     insertCtorDtorSymbols();
 977 }
 978
 979 // Create .idata section for the DLL-imported symbol table.
 980 // The format of this section is inherently Windows-specific.
 981 // IdataContents class abstracted away the details for us,
 982 // so we just let it create chunks and add them to the section.
 983 void Writer::createImportTables() {
 984   // Initialize DLLOrder so that import entries are ordered in
 985   // the same order as in the command line. (That affects DLL
 986   // initialization order, and this ordering is MSVC-compatible.)
 987   for (ImportFile *file : ImportFile::instances) {
 988     if (!file->live)
 989       continue;
 990
 991     std::string dll = StringRef(file->dllName).lower();
 992     if (config->dllOrder.count(dll) == 0)
 993       config->dllOrder[dll] = config->dllOrder.size();
 994
 995     if (file->impSym && !isa<DefinedImportData>(file->impSym))
 996       fatal(toString(*file->impSym) + " was replaced");
 997     DefinedImportData *impSym = cast_or_null<DefinedImportData>(file->impSym);
 998     if (config->delayLoads.count(StringRef(file->dllName).lower())) {
 999       if (!file->thunkSym)
1000         fatal("cannot delay-load " + toString(file) +
1001               " due to import of data: " + toString(*impSym));
1002       delayIdata.add(impSym);
1003     } else {
1004       idata.add(impSym);
1005     }
1006   }
1007 }
1008
1009 void Writer::appendImportThunks() {
1010   if (ImportFile::instances.empty())
1011     return;
1012
1013   for (ImportFile *file : ImportFile::instances) {
1014     if (!file->live)
1015       continue;
1016
1017     if (!file->thunkSym)
1018       continue;
1019
1020     if (!isa<DefinedImportThunk>(file->thunkSym))
1021       fatal(toString(*file->thunkSym) + " was replaced");
1022     DefinedImportThunk *thunk = cast<DefinedImportThunk>(file->thunkSym);
1023     if (file->thunkLive)
1024       textSec->addChunk(thunk->getChunk());
1025   }
1026
1027   if (!delayIdata.empty()) {
1028     Defined *helper = cast<Defined>(config->delayLoadHelper);
1029     delayIdata.create(helper);
1030     for (Chunk *c : delayIdata.getChunks())
1031       didatSec->addChunk(c);
1032     for (Chunk *c : delayIdata.getDataChunks())
1033       dataSec->addChunk(c);
1034     for (Chunk *c : delayIdata.getCodeChunks())
1035       textSec->addChunk(c);
1036   }
1037 }
1038
1039 void Writer::createExportTable() {
1040   if (!edataSec->chunks.empty()) {
1041     // Allow using a custom built export table from input object files, instead
1042     // of having the linker synthesize the tables.
1043     if (config->hadExplicitExports)
1044       warn("literal .edata sections override exports");
1045   } else if (!config->exports.empty()) {
1046     for (Chunk *c : edata.chunks)
1047       edataSec->addChunk(c);
1048   }
1049   if (!edataSec->chunks.empty()) {
1050     edataStart = edataSec->chunks.front();
1051     edataEnd = edataSec->chunks.back();
1052   }
1053 }
1054
1055 void Writer::removeUnusedSections() {
1056   // Remove sections that we can be sure won't get content, to avoid
1057   // allocating space for their section headers.
1058   auto isUnused = [this](OutputSection *s) {
1059     if (s == relocSec)
1060       return false; // This section is populated later.
1061     // MergeChunks have zero size at this point, as their size is finalized
1062     // later. Only remove sections that have no Chunks at all.
1063     return s->chunks.empty();
1064   };
1065   outputSections.erase(
1066       std::remove_if(outputSections.begin(), outputSections.end(), isUnused),
1067       outputSections.end());
1068 }
1069
1070 // The Windows loader doesn't seem to like empty sections,
1071 // so we remove them if any.
1072 void Writer::removeEmptySections() {
1073   auto isEmpty = [](OutputSection *s) { return s->getVirtualSize() == 0; };
1074   outputSections.erase(
1075       std::remove_if(outputSections.begin(), outputSections.end(), isEmpty),
1076       outputSections.end());
1077 }
1078
1079 void Writer::assignOutputSectionIndices() {
1080   // Assign final output section indices, and assign each chunk to its output
1081   // section.
1082   uint32_t idx = 1;
1083   for (OutputSection *os : outputSections) {
1084     os->sectionIndex = idx;
1085     for (Chunk *c : os->chunks)
1086       c->setOutputSectionIdx(idx);
1087     ++idx;
1088   }
1089
1090   // Merge chunks are containers of chunks, so assign those an output section
1091   // too.
1092   for (MergeChunk *mc : MergeChunk::instances)
1093     if (mc)
1094       for (SectionChunk *sc : mc->sections)
1095         if (sc && sc->live)
1096           sc->setOutputSectionIdx(mc->getOutputSectionIdx());
1097 }
1098
1099 size_t Writer::addEntryToStringTable(StringRef str) {
1100   assert(str.size() > COFF::NameSize);
1101   size_t offsetOfEntry = strtab.size() + 4; // +4 for the size field
1102   strtab.insert(strtab.end(), str.begin(), str.end());
1103   strtab.push_back('\0');
1104   return offsetOfEntry;
1105 }
1106
1107 Optional<coff_symbol16> Writer::createSymbol(Defined *def) {
1108   coff_symbol16 sym;
1109   switch (def->kind()) {
1110   case Symbol::DefinedAbsoluteKind:
1111     sym.Value = def->getRVA();
1112     sym.SectionNumber = IMAGE_SYM_ABSOLUTE;
1113     break;
1114   case Symbol::DefinedSyntheticKind:
1115     // Relative symbols are unrepresentable in a COFF symbol table.
1116     return None;
1117   default: {
1118     // Don't write symbols that won't be written to the output to the symbol
1119     // table.
1120     Chunk *c = def->getChunk();
1121     if (!c)
1122       return None;
1123     OutputSection *os = c->getOutputSection();
1124     if (!os)
1125       return None;
1126
1127     sym.Value = def->getRVA() - os->getRVA();
1128     sym.SectionNumber = os->sectionIndex;
1129     break;
1130   }
1131   }
1132
1133   // Symbols that are runtime pseudo relocations don't point to the actual
1134   // symbol data itself (as they are imported), but points to the IAT entry
1135   // instead. Avoid emitting them to the symbol table, as they can confuse
1136   // debuggers.
1137   if (def->isRuntimePseudoReloc)
1138     return None;
1139
1140   StringRef name = def->getName();
1141   if (name.size() > COFF::NameSize) {
1142     sym.Name.Offset.Zeroes = 0;
1143     sym.Name.Offset.Offset = addEntryToStringTable(name);
1144   } else {
1145     memset(sym.Name.ShortName, 0, COFF::NameSize);
1146     memcpy(sym.Name.ShortName, name.data(), name.size());
1147   }
1148
1149   if (auto *d = dyn_cast<DefinedCOFF>(def)) {
1150     COFFSymbolRef ref = d->getCOFFSymbol();
1151     sym.Type = ref.getType();
1152     sym.StorageClass = ref.getStorageClass();
1153   } else {
1154     sym.Type = IMAGE_SYM_TYPE_NULL;
1155     sym.StorageClass = IMAGE_SYM_CLASS_EXTERNAL;
1156   }
1157   sym.NumberOfAuxSymbols = 0;
1158   return sym;
1159 }
1160
1161 void Writer::createSymbolAndStringTable() {
1162   // PE/COFF images are limited to 8 byte section names. Longer names can be
1163   // supported by writing a non-standard string table, but this string table is
1164   // not mapped at runtime and the long names will therefore be inaccessible.
1165   // link.exe always truncates section names to 8 bytes, whereas binutils always
1166   // preserves long section names via the string table. LLD adopts a hybrid
1167   // solution where discardable sections have long names preserved and
1168   // non-discardable sections have their names truncated, to ensure that any
1169   // section which is mapped at runtime also has its name mapped at runtime.
1170   for (OutputSection *sec : outputSections) {
1171     if (sec->name.size() <= COFF::NameSize)
1172       continue;
1173     if ((sec->header.Characteristics & IMAGE_SCN_MEM_DISCARDABLE) == 0)
1174       continue;
1175     if (config->warnLongSectionNames) {
1176       warn("section name " + sec->name +
1177            " is longer than 8 characters and will use a non-standard string "
1178            "table");
1179     }
1180     sec->setStringTableOff(addEntryToStringTable(sec->name));
1181   }
1182
1183   if (config->debugDwarf || config->debugSymtab) {
1184     for (ObjFile *file : ObjFile::instances) {
1185       for (Symbol *b : file->getSymbols()) {
1186         auto *d = dyn_cast_or_null<Defined>(b);
1187         if (!d || d->writtenToSymtab)
1188           continue;
1189         d->writtenToSymtab = true;
1190
1191         if (Optional<coff_symbol16> sym = createSymbol(d))
1192           outputSymtab.push_back(*sym);
1193       }
1194     }
1195   }
1196
1197   if (outputSymtab.empty() && strtab.empty())
1198     return;
1199
1200   // We position the symbol table to be adjacent to the end of the last section.
1201   uint64_t fileOff = fileSize;
1202   pointerToSymbolTable = fileOff;
1203   fileOff += outputSymtab.size() * sizeof(coff_symbol16);
1204   fileOff += 4 + strtab.size();
1205   fileSize = alignTo(fileOff, config->fileAlign);
1206 }
1207
1208 void Writer::mergeSections() {
1209   if (!pdataSec->chunks.empty()) {
1210     firstPdata = pdataSec->chunks.front();
1211     lastPdata = pdataSec->chunks.back();
1212   }
1213
1214   for (auto &p : config->merge) {
1215     StringRef toName = p.second;
1216     if (p.first == toName)
1217       continue;
1218     StringSet<> names;
1219     while (1) {
1220       if (!names.insert(toName).second)
1221         fatal("/merge: cycle found for section '" + p.first + "'");
1222       auto i = config->merge.find(toName);
1223       if (i == config->merge.end())
1224         break;
1225       toName = i->second;
1226     }
1227     OutputSection *from = findSection(p.first);
1228     OutputSection *to = findSection(toName);
1229     if (!from)
1230       continue;
1231     if (!to) {
1232       from->name = toName;
1233       continue;
1234     }
1235     to->merge(from);
1236   }
1237 }
1238
1239 // Visits all sections to assign incremental, non-overlapping RVAs and
1240 // file offsets.
1241 void Writer::assignAddresses() {
1242   sizeOfHeaders = dosStubSize + sizeof(PEMagic) + sizeof(coff_file_header) +
1243                   sizeof(data_directory) * numberOfDataDirectory +
1244                   sizeof(coff_section) * outputSections.size();
1245   sizeOfHeaders +=
1246       config->is64() ? sizeof(pe32plus_header) : sizeof(pe32_header);
1247   sizeOfHeaders = alignTo(sizeOfHeaders, config->fileAlign);
1248   fileSize = sizeOfHeaders;
1249
1250   // The first page is kept unmapped.
1251   uint64_t rva = alignTo(sizeOfHeaders, config->align);
1252
1253   for (OutputSection *sec : outputSections) {
1254     if (sec == relocSec)
1255       addBaserels();
1256     uint64_t rawSize = 0, virtualSize = 0;
1257     sec->header.VirtualAddress = rva;
1258
1259     // If /FUNCTIONPADMIN is used, functions are padded in order to create a
1260     // hotpatchable image.
1261     const bool isCodeSection =
1262         (sec->header.Characteristics & IMAGE_SCN_CNT_CODE) &&
1263         (sec->header.Characteristics & IMAGE_SCN_MEM_READ) &&
1264         (sec->header.Characteristics & IMAGE_SCN_MEM_EXECUTE);
1265     uint32_t padding = isCodeSection ? config->functionPadMin : 0;
1266
1267     for (Chunk *c : sec->chunks) {
1268       if (padding && c->isHotPatchable())
1269         virtualSize += padding;
1270       virtualSize = alignTo(virtualSize, c->getAlignment());
1271       c->setRVA(rva + virtualSize);
1272       virtualSize += c->getSize();
1273       if (c->hasData)
1274         rawSize = alignTo(virtualSize, config->fileAlign);
1275     }
1276     if (virtualSize > UINT32_MAX)
1277       error("section larger than 4 GiB: " + sec->name);
1278     sec->header.VirtualSize = virtualSize;
1279     sec->header.SizeOfRawData = rawSize;
1280     if (rawSize != 0)
1281       sec->header.PointerToRawData = fileSize;
1282     rva += alignTo(virtualSize, config->align);
1283     fileSize += alignTo(rawSize, config->fileAlign);
1284   }
1285   sizeOfImage = alignTo(rva, config->align);
1286
1287   // Assign addresses to sections in MergeChunks.
1288   for (MergeChunk *mc : MergeChunk::instances)
1289     if (mc)
1290       mc->assignSubsectionRVAs();
1291 }
1292
1293 template <typename PEHeaderTy> void Writer::writeHeader() {
1294   // Write DOS header. For backwards compatibility, the first part of a PE/COFF
1295   // executable consists of an MS-DOS MZ executable. If the executable is run
1296   // under DOS, that program gets run (usually to just print an error message).
1297   // When run under Windows, the loader looks at AddressOfNewExeHeader and uses
1298   // the PE header instead.
1299   uint8_t *buf = buffer->getBufferStart();
1300   auto *dos = reinterpret_cast<dos_header *>(buf);
1301   buf += sizeof(dos_header);
1302   dos->Magic[0] = 'M';
1303   dos->Magic[1] = 'Z';
1304   dos->UsedBytesInTheLastPage = dosStubSize % 512;
1305   dos->FileSizeInPages = divideCeil(dosStubSize, 512);
1306   dos->HeaderSizeInParagraphs = sizeof(dos_header) / 16;
1307
1308   dos->AddressOfRelocationTable = sizeof(dos_header);
1309   dos->AddressOfNewExeHeader = dosStubSize;
1310
1311   // Write DOS program.
1312   memcpy(buf, dosProgram, sizeof(dosProgram));
1313   buf += sizeof(dosProgram);
1314
1315   // Write PE magic
1316   memcpy(buf, PEMagic, sizeof(PEMagic));
1317   buf += sizeof(PEMagic);
1318
1319   // Write COFF header
1320   auto *coff = reinterpret_cast<coff_file_header *>(buf);
1321   buf += sizeof(*coff);
1322   coff->Machine = config->machine;
1323   coff->NumberOfSections = outputSections.size();
1324   coff->Characteristics = IMAGE_FILE_EXECUTABLE_IMAGE;
1325   if (config->largeAddressAware)
1326     coff->Characteristics |= IMAGE_FILE_LARGE_ADDRESS_AWARE;
1327   if (!config->is64())
1328     coff->Characteristics |= IMAGE_FILE_32BIT_MACHINE;
1329   if (config->dll)
1330     coff->Characteristics |= IMAGE_FILE_DLL;
1331   if (config->driverUponly)
1332     coff->Characteristics |= IMAGE_FILE_UP_SYSTEM_ONLY;
1333   if (!config->relocatable)
1334     coff->Characteristics |= IMAGE_FILE_RELOCS_STRIPPED;
1335   if (config->swaprunCD)
1336     coff->Characteristics |= IMAGE_FILE_REMOVABLE_RUN_FROM_SWAP;
1337   if (config->swaprunNet)
1338     coff->Characteristics |= IMAGE_FILE_NET_RUN_FROM_SWAP;
1339   coff->SizeOfOptionalHeader =
1340       sizeof(PEHeaderTy) + sizeof(data_directory) * numberOfDataDirectory;
1341
1342   // Write PE header
1343   auto *pe = reinterpret_cast<PEHeaderTy *>(buf);
1344   buf += sizeof(*pe);
1345   pe->Magic = config->is64() ? PE32Header::PE32_PLUS : PE32Header::PE32;
1346
1347   // If {Major,Minor}LinkerVersion is left at 0.0, then for some
1348   // reason signing the resulting PE file with Authenticode produces a
1349   // signature that fails to validate on Windows 7 (but is OK on 10).
1350   // Set it to 14.0, which is what VS2015 outputs, and which avoids
1351   // that problem.
1352   pe->MajorLinkerVersion = 14;
1353   pe->MinorLinkerVersion = 0;
1354
1355   pe->ImageBase = config->imageBase;
1356   pe->SectionAlignment = config->align;
1357   pe->FileAlignment = config->fileAlign;
1358   pe->MajorImageVersion = config->majorImageVersion;
1359   pe->MinorImageVersion = config->minorImageVersion;
1360   pe->MajorOperatingSystemVersion = config->majorOSVersion;
1361   pe->MinorOperatingSystemVersion = config->minorOSVersion;
1362   pe->MajorSubsystemVersion = config->majorOSVersion;
1363   pe->MinorSubsystemVersion = config->minorOSVersion;
1364   pe->Subsystem = config->subsystem;
1365   pe->SizeOfImage = sizeOfImage;
1366   pe->SizeOfHeaders = sizeOfHeaders;
1367   if (!config->noEntry) {
1368     Defined *entry = cast<Defined>(config->entry);
1369     pe->AddressOfEntryPoint = entry->getRVA();
1370     // Pointer to thumb code must have the LSB set, so adjust it.
1371     if (config->machine == ARMNT)
1372       pe->AddressOfEntryPoint |= 1;
1373   }
1374   pe->SizeOfStackReserve = config->stackReserve;
1375   pe->SizeOfStackCommit = config->stackCommit;
1376   pe->SizeOfHeapReserve = config->heapReserve;
1377   pe->SizeOfHeapCommit = config->heapCommit;
1378   if (config->appContainer)
1379     pe->DLLCharacteristics |= IMAGE_DLL_CHARACTERISTICS_APPCONTAINER;
1380   if (config->driverWdm)
1381     pe->DLLCharacteristics |= IMAGE_DLL_CHARACTERISTICS_WDM_DRIVER;
1382   if (config->dynamicBase)
1383     pe->DLLCharacteristics |= IMAGE_DLL_CHARACTERISTICS_DYNAMIC_BASE;
1384   if (config->highEntropyVA)
1385     pe->DLLCharacteristics |= IMAGE_DLL_CHARACTERISTICS_HIGH_ENTROPY_VA;
1386   if (!config->allowBind)
1387     pe->DLLCharacteristics |= IMAGE_DLL_CHARACTERISTICS_NO_BIND;
1388   if (config->nxCompat)
1389     pe->DLLCharacteristics |= IMAGE_DLL_CHARACTERISTICS_NX_COMPAT;
1390   if (!config->allowIsolation)
1391     pe->DLLCharacteristics |= IMAGE_DLL_CHARACTERISTICS_NO_ISOLATION;
1392   if (config->guardCF != GuardCFLevel::Off)
1393     pe->DLLCharacteristics |= IMAGE_DLL_CHARACTERISTICS_GUARD_CF;
1394   if (config->integrityCheck)
1395     pe->DLLCharacteristics |= IMAGE_DLL_CHARACTERISTICS_FORCE_INTEGRITY;
1396   if (setNoSEHCharacteristic || config->noSEH)
1397     pe->DLLCharacteristics |= IMAGE_DLL_CHARACTERISTICS_NO_SEH;
1398   if (config->terminalServerAware)
1399     pe->DLLCharacteristics |= IMAGE_DLL_CHARACTERISTICS_TERMINAL_SERVER_AWARE;
1400   pe->NumberOfRvaAndSize = numberOfDataDirectory;
1401   if (textSec->getVirtualSize()) {
1402     pe->BaseOfCode = textSec->getRVA();
1403     pe->SizeOfCode = textSec->getRawSize();
1404   }
1405   pe->SizeOfInitializedData = getSizeOfInitializedData();
1406
1407   // Write data directory
1408   auto *dir = reinterpret_cast<data_directory *>(buf);
1409   buf += sizeof(*dir) * numberOfDataDirectory;
1410   if (edataStart) {
1411     dir[EXPORT_TABLE].RelativeVirtualAddress = edataStart->getRVA();
1412     dir[EXPORT_TABLE].Size =
1413         edataEnd->getRVA() + edataEnd->getSize() - edataStart->getRVA();
1414   }
1415   if (importTableStart) {
1416     dir[IMPORT_TABLE].RelativeVirtualAddress = importTableStart->getRVA();
1417     dir[IMPORT_TABLE].Size = importTableSize;
1418   }
1419   if (iatStart) {
1420     dir[IAT].RelativeVirtualAddress = iatStart->getRVA();
1421     dir[IAT].Size = iatSize;
1422   }
1423   if (rsrcSec->getVirtualSize()) {
1424     dir[RESOURCE_TABLE].RelativeVirtualAddress = rsrcSec->getRVA();
1425     dir[RESOURCE_TABLE].Size = rsrcSec->getVirtualSize();
1426   }
1427   if (firstPdata) {
1428     dir[EXCEPTION_TABLE].RelativeVirtualAddress = firstPdata->getRVA();
1429     dir[EXCEPTION_TABLE].Size =
1430         lastPdata->getRVA() + lastPdata->getSize() - firstPdata->getRVA();
1431   }
1432   if (relocSec->getVirtualSize()) {
1433     dir[BASE_RELOCATION_TABLE].RelativeVirtualAddress = relocSec->getRVA();
1434     dir[BASE_RELOCATION_TABLE].Size = relocSec->getVirtualSize();
1435   }
1436   if (Symbol *sym = symtab->findUnderscore("_tls_used")) {
1437     if (Defined *b = dyn_cast<Defined>(sym)) {
1438       dir[TLS_TABLE].RelativeVirtualAddress = b->getRVA();
1439       dir[TLS_TABLE].Size = config->is64()
1440                                 ? sizeof(object::coff_tls_directory64)
1441                                 : sizeof(object::coff_tls_directory32);
1442     }
1443   }
1444   if (debugDirectory) {
1445     dir[DEBUG_DIRECTORY].RelativeVirtualAddress = debugDirectory->getRVA();
1446     dir[DEBUG_DIRECTORY].Size = debugDirectory->getSize();
1447   }
1448   if (Symbol *sym = symtab->findUnderscore("_load_config_used")) {
1449     if (auto *b = dyn_cast<DefinedRegular>(sym)) {
1450       SectionChunk *sc = b->getChunk();
1451       assert(b->getRVA() >= sc->getRVA());
1452       uint64_t offsetInChunk = b->getRVA() - sc->getRVA();
1453       if (!sc->hasData || offsetInChunk + 4 > sc->getSize())
1454         fatal("_load_config_used is malformed");
1455
1456       ArrayRef<uint8_t> secContents = sc->getContents();
1457       uint32_t loadConfigSize =
1458           *reinterpret_cast<const ulittle32_t *>(&secContents[offsetInChunk]);
1459       if (offsetInChunk + loadConfigSize > sc->getSize())
1460         fatal("_load_config_used is too large");
1461       dir[LOAD_CONFIG_TABLE].RelativeVirtualAddress = b->getRVA();
1462       dir[LOAD_CONFIG_TABLE].Size = loadConfigSize;
1463     }
1464   }
1465   if (!delayIdata.empty()) {
1466     dir[DELAY_IMPORT_DESCRIPTOR].RelativeVirtualAddress =
1467         delayIdata.getDirRVA();
1468     dir[DELAY_IMPORT_DESCRIPTOR].Size = delayIdata.getDirSize();
1469   }
1470
1471   // Write section table
1472   for (OutputSection *sec : outputSections) {
1473     sec->writeHeaderTo(buf);
1474     buf += sizeof(coff_section);
1475   }
1476   sectionTable = ArrayRef<uint8_t>(
1477       buf - outputSections.size() * sizeof(coff_section), buf);
1478
1479   if (outputSymtab.empty() && strtab.empty())
1480     return;
1481
1482   coff->PointerToSymbolTable = pointerToSymbolTable;
1483   uint32_t numberOfSymbols = outputSymtab.size();
1484   coff->NumberOfSymbols = numberOfSymbols;
1485   auto *symbolTable = reinterpret_cast<coff_symbol16 *>(
1486       buffer->getBufferStart() + coff->PointerToSymbolTable);
1487   for (size_t i = 0; i != numberOfSymbols; ++i)
1488     symbolTable[i] = outputSymtab[i];
1489   // Create the string table, it follows immediately after the symbol table.
1490   // The first 4 bytes is length including itself.
1491   buf = reinterpret_cast<uint8_t *>(&symbolTable[numberOfSymbols]);
1492   write32le(buf, strtab.size() + 4);
1493   if (!strtab.empty())
1494     memcpy(buf + 4, strtab.data(), strtab.size());
1495 }
1496
1497 void Writer::openFile(StringRef path) {
1498   buffer = CHECK(
1499       FileOutputBuffer::create(path, fileSize, FileOutputBuffer::F_executable),
1500       "failed to open " + path);
1501 }
1502
1503 void Writer::createSEHTable() {
1504   SymbolRVASet handlers;
1505   for (ObjFile *file : ObjFile::instances) {
1506     if (!file->hasSafeSEH())
1507       error("/safeseh: " + file->getName() + " is not compatible with SEH");
1508     markSymbolsForRVATable(file, file->getSXDataChunks(), handlers);
1509   }
1510
1511   // Set the "no SEH" characteristic if there really were no handlers, or if
1512   // there is no load config object to point to the table of handlers.
1513   setNoSEHCharacteristic =
1514       handlers.empty() || !symtab->findUnderscore("_load_config_used");
1515
1516   maybeAddRVATable(std::move(handlers), "__safe_se_handler_table",
1517                    "__safe_se_handler_count");
1518 }
1519
1520 // Add a symbol to an RVA set. Two symbols may have the same RVA, but an RVA set
1521 // cannot contain duplicates. Therefore, the set is uniqued by Chunk and the
1522 // symbol's offset into that Chunk.
1523 static void addSymbolToRVASet(SymbolRVASet &rvaSet, Defined *s) {
1524   Chunk *c = s->getChunk();
1525   if (auto *sc = dyn_cast<SectionChunk>(c))
1526     c = sc->repl; // Look through ICF replacement.
1527   uint32_t off = s->getRVA() - (c ? c->getRVA() : 0);
1528   rvaSet.insert({c, off});
1529 }
1530
1531 // Given a symbol, add it to the GFIDs table if it is a live, defined, function
1532 // symbol in an executable section.
1533 static void maybeAddAddressTakenFunction(SymbolRVASet &addressTakenSyms,
1534                                          Symbol *s) {
1535   if (!s)
1536     return;
1537
1538   switch (s->kind()) {
1539   case Symbol::DefinedLocalImportKind:
1540   case Symbol::DefinedImportDataKind:
1541     // Defines an __imp_ pointer, so it is data, so it is ignored.
1542     break;
1543   case Symbol::DefinedCommonKind:
1544     // Common is always data, so it is ignored.
1545     break;
1546   case Symbol::DefinedAbsoluteKind:
1547   case Symbol::DefinedSyntheticKind:
1548     // Absolute is never code, synthetic generally isn't and usually isn't
1549     // determinable.
1550     break;
1551   case Symbol::LazyArchiveKind:
1552   case Symbol::LazyObjectKind:
1553   case Symbol::UndefinedKind:
1554     // Undefined symbols resolve to zero, so they don't have an RVA. Lazy
1555     // symbols shouldn't have relocations.
1556     break;
1557
1558   case Symbol::DefinedImportThunkKind:
1559     // Thunks are always code, include them.
1560     addSymbolToRVASet(addressTakenSyms, cast<Defined>(s));
1561     break;
1562
1563   case Symbol::DefinedRegularKind: {
1564     // This is a regular, defined, symbol from a COFF file. Mark the symbol as
1565     // address taken if the symbol type is function and it's in an executable
1566     // section.
1567     auto *d = cast<DefinedRegular>(s);
1568     if (d->getCOFFSymbol().getComplexType() == COFF::IMAGE_SYM_DTYPE_FUNCTION) {
1569       SectionChunk *sc = dyn_cast<SectionChunk>(d->getChunk());
1570       if (sc && sc->live &&
1571           sc->getOutputCharacteristics() & IMAGE_SCN_MEM_EXECUTE)
1572         addSymbolToRVASet(addressTakenSyms, d);
1573     }
1574     break;
1575   }
1576   }
1577 }
1578
1579 // Visit all relocations from all section contributions of this object file and
1580 // mark the relocation target as address-taken.
1581 static void markSymbolsWithRelocations(ObjFile *file,
1582                                        SymbolRVASet &usedSymbols) {
1583   for (Chunk *c : file->getChunks()) {
1584     // We only care about live section chunks. Common chunks and other chunks
1585     // don't generally contain relocations.
1586     SectionChunk *sc = dyn_cast<SectionChunk>(c);
1587     if (!sc || !sc->live)
1588       continue;
1589
1590     for (const coff_relocation &reloc : sc->getRelocs()) {
1591       if (config->machine == I386 && reloc.Type == COFF::IMAGE_REL_I386_REL32)
1592         // Ignore relative relocations on x86. On x86_64 they can't be ignored
1593         // since they're also used to compute absolute addresses.
1594         continue;
1595
1596       Symbol *ref = sc->file->getSymbol(reloc.SymbolTableIndex);
1597       maybeAddAddressTakenFunction(usedSymbols, ref);
1598     }
1599   }
1600 }
1601
1602 // Create the guard function id table. This is a table of RVAs of all
1603 // address-taken functions. It is sorted and uniqued, just like the safe SEH
1604 // table.
1605 void Writer::createGuardCFTables() {
1606   SymbolRVASet addressTakenSyms;
1607   SymbolRVASet longJmpTargets;
1608   for (ObjFile *file : ObjFile::instances) {
1609     // If the object was compiled with /guard:cf, the address taken symbols
1610     // are in .gfids$y sections, and the longjmp targets are in .gljmp$y
1611     // sections. If the object was not compiled with /guard:cf, we assume there
1612     // were no setjmp targets, and that all code symbols with relocations are
1613     // possibly address-taken.
1614     if (file->hasGuardCF()) {
1615       markSymbolsForRVATable(file, file->getGuardFidChunks(), addressTakenSyms);
1616       markSymbolsForRVATable(file, file->getGuardLJmpChunks(), longJmpTargets);
1617     } else {
1618       markSymbolsWithRelocations(file, addressTakenSyms);
1619     }
1620   }
1621
1622   // Mark the image entry as address-taken.
1623   if (config->entry)
1624     maybeAddAddressTakenFunction(addressTakenSyms, config->entry);
1625
1626   // Mark exported symbols in executable sections as address-taken.
1627   for (Export &e : config->exports)
1628     maybeAddAddressTakenFunction(addressTakenSyms, e.sym);
1629
1630   // Ensure sections referenced in the gfid table are 16-byte aligned.
1631   for (const ChunkAndOffset &c : addressTakenSyms)
1632     if (c.inputChunk->getAlignment() < 16)
1633       c.inputChunk->setAlignment(16);
1634
1635   maybeAddRVATable(std::move(addressTakenSyms), "__guard_fids_table",
1636                    "__guard_fids_count");
1637
1638   // Add the longjmp target table unless the user told us not to.
1639   if (config->guardCF == GuardCFLevel::Full)
1640     maybeAddRVATable(std::move(longJmpTargets), "__guard_longjmp_table",
1641                      "__guard_longjmp_count");
1642
1643   // Set __guard_flags, which will be used in the load config to indicate that
1644   // /guard:cf was enabled.
1645   uint32_t guardFlags = uint32_t(coff_guard_flags::CFInstrumented) |
1646                         uint32_t(coff_guard_flags::HasFidTable);
1647   if (config->guardCF == GuardCFLevel::Full)
1648     guardFlags |= uint32_t(coff_guard_flags::HasLongJmpTable);
1649   Symbol *flagSym = symtab->findUnderscore("__guard_flags");
1650   cast<DefinedAbsolute>(flagSym)->setVA(guardFlags);
1651 }
1652
1653 // Take a list of input sections containing symbol table indices and add those
1654 // symbols to an RVA table. The challenge is that symbol RVAs are not known and
1655 // depend on the table size, so we can't directly build a set of integers.
1656 void Writer::markSymbolsForRVATable(ObjFile *file,
1657                                     ArrayRef<SectionChunk *> symIdxChunks,
1658                                     SymbolRVASet &tableSymbols) {
1659   for (SectionChunk *c : symIdxChunks) {
1660     // Skip sections discarded by linker GC. This comes up when a .gfids section
1661     // is associated with something like a vtable and the vtable is discarded.
1662     // In this case, the associated gfids section is discarded, and we don't
1663     // mark the virtual member functions as address-taken by the vtable.
1664     if (!c->live)
1665       continue;
1666
1667     // Validate that the contents look like symbol table indices.
1668     ArrayRef<uint8_t> data = c->getContents();
1669     if (data.size() % 4 != 0) {
1670       warn("ignoring " + c->getSectionName() +
1671            " symbol table index section in object " + toString(file));
1672       continue;
1673     }
1674
1675     // Read each symbol table index and check if that symbol was included in the
1676     // final link. If so, add it to the table symbol set.
1677     ArrayRef<ulittle32_t> symIndices(
1678         reinterpret_cast<const ulittle32_t *>(data.data()), data.size() / 4);
1679     ArrayRef<Symbol *> objSymbols = file->getSymbols();
1680     for (uint32_t symIndex : symIndices) {
1681       if (symIndex >= objSymbols.size()) {
1682         warn("ignoring invalid symbol table index in section " +
1683              c->getSectionName() + " in object " + toString(file));
1684         continue;
1685       }
1686       if (Symbol *s = objSymbols[symIndex]) {
1687         if (s->isLive())
1688           addSymbolToRVASet(tableSymbols, cast<Defined>(s));
1689       }
1690     }
1691   }
1692 }
1693
1694 // Replace the absolute table symbol with a synthetic symbol pointing to
1695 // tableChunk so that we can emit base relocations for it and resolve section
1696 // relative relocations.
1697 void Writer::maybeAddRVATable(SymbolRVASet tableSymbols, StringRef tableSym,
1698                               StringRef countSym) {
1699   if (tableSymbols.empty())
1700     return;
1701
1702   RVATableChunk *tableChunk = make<RVATableChunk>(std::move(tableSymbols));
1703   rdataSec->addChunk(tableChunk);
1704
1705   Symbol *t = symtab->findUnderscore(tableSym);
1706   Symbol *c = symtab->findUnderscore(countSym);
1707   replaceSymbol<DefinedSynthetic>(t, t->getName(), tableChunk);
1708   cast<DefinedAbsolute>(c)->setVA(tableChunk->getSize() / 4);
1709 }
1710
1711 // MinGW specific. Gather all relocations that are imported from a DLL even
1712 // though the code didn't expect it to, produce the table that the runtime
1713 // uses for fixing them up, and provide the synthetic symbols that the
1714 // runtime uses for finding the table.
1715 void Writer::createRuntimePseudoRelocs() {
1716   std::vector<RuntimePseudoReloc> rels;
1717
1718   for (Chunk *c : symtab->getChunks()) {
1719     auto *sc = dyn_cast<SectionChunk>(c);
1720     if (!sc || !sc->live)
1721       continue;
1722     sc->getRuntimePseudoRelocs(rels);
1723   }
1724
1725   if (!config->pseudoRelocs) {
1726     // Not writing any pseudo relocs; if some were needed, error out and
1727     // indicate what required them.
1728     for (const RuntimePseudoReloc &rpr : rels)
1729       error("automatic dllimport of " + rpr.sym->getName() + " in " +
1730             toString(rpr.target->file) + " requires pseudo relocations");
1731     return;
1732   }
1733
1734   if (!rels.empty())
1735     log("Writing " + Twine(rels.size()) + " runtime pseudo relocations");
1736   PseudoRelocTableChunk *table = make<PseudoRelocTableChunk>(rels);
1737   rdataSec->addChunk(table);
1738   EmptyChunk *endOfList = make<EmptyChunk>();
1739   rdataSec->addChunk(endOfList);
1740
1741   Symbol *headSym = symtab->findUnderscore("__RUNTIME_PSEUDO_RELOC_LIST__");
1742   Symbol *endSym = symtab->findUnderscore("__RUNTIME_PSEUDO_RELOC_LIST_END__");
1743   replaceSymbol<DefinedSynthetic>(headSym, headSym->getName(), table);
1744   replaceSymbol<DefinedSynthetic>(endSym, endSym->getName(), endOfList);
1745 }
1746
1747 // MinGW specific.
1748 // The MinGW .ctors and .dtors lists have sentinels at each end;
1749 // a (uintptr_t)-1 at the start and a (uintptr_t)0 at the end.
1750 // There's a symbol pointing to the start sentinel pointer, __CTOR_LIST__
1751 // and __DTOR_LIST__ respectively.
1752 void Writer::insertCtorDtorSymbols() {
1753   AbsolutePointerChunk *ctorListHead = make<AbsolutePointerChunk>(-1);
1754   AbsolutePointerChunk *ctorListEnd = make<AbsolutePointerChunk>(0);
1755   AbsolutePointerChunk *dtorListHead = make<AbsolutePointerChunk>(-1);
1756   AbsolutePointerChunk *dtorListEnd = make<AbsolutePointerChunk>(0);
1757   ctorsSec->insertChunkAtStart(ctorListHead);
1758   ctorsSec->addChunk(ctorListEnd);
1759   dtorsSec->insertChunkAtStart(dtorListHead);
1760   dtorsSec->addChunk(dtorListEnd);
1761
1762   Symbol *ctorListSym = symtab->findUnderscore("__CTOR_LIST__");
1763   Symbol *dtorListSym = symtab->findUnderscore("__DTOR_LIST__");
1764   replaceSymbol<DefinedSynthetic>(ctorListSym, ctorListSym->getName(),
1765                                   ctorListHead);
1766   replaceSymbol<DefinedSynthetic>(dtorListSym, dtorListSym->getName(),
1767                                   dtorListHead);
1768 }
1769
1770 // Handles /section options to allow users to overwrite
1771 // section attributes.
1772 void Writer::setSectionPermissions() {
1773   for (auto &p : config->section) {
1774     StringRef name = p.first;
1775     uint32_t perm = p.second;
1776     for (OutputSection *sec : outputSections)
1777       if (sec->name == name)
1778         sec->setPermissions(perm);
1779   }
1780 }
1781
1782 // Write section contents to a mmap'ed file.
1783 void Writer::writeSections() {
1784   // Record the number of sections to apply section index relocations
1785   // against absolute symbols. See applySecIdx in Chunks.cpp..
1786   DefinedAbsolute::numOutputSections = outputSections.size();
1787
1788   uint8_t *buf = buffer->getBufferStart();
1789   for (OutputSection *sec : outputSections) {
1790     uint8_t *secBuf = buf + sec->getFileOff();
1791     // Fill gaps between functions in .text with INT3 instructions
1792     // instead of leaving as NUL bytes (which can be interpreted as
1793     // ADD instructions).
1794     if (sec->header.Characteristics & IMAGE_SCN_CNT_CODE)
1795       memset(secBuf, 0xCC, sec->getRawSize());
1796     parallelForEach(sec->chunks, [&](Chunk *c) {
1797       c->writeTo(secBuf + c->getRVA() - sec->getRVA());
1798     });
1799   }
1800 }
1801
1802 void Writer::writeBuildId() {
1803   // There are two important parts to the build ID.
1804   // 1) If building with debug info, the COFF debug directory contains a
1805   //    timestamp as well as a Guid and Age of the PDB.
1806   // 2) In all cases, the PE COFF file header also contains a timestamp.
1807   // For reproducibility, instead of a timestamp we want to use a hash of the
1808   // PE contents.
1809   if (config->debug) {
1810     assert(buildId && "BuildId is not set!");
1811     // BuildId->BuildId was filled in when the PDB was written.
1812   }
1813
1814   // At this point the only fields in the COFF file which remain unset are the
1815   // "timestamp" in the COFF file header, and the ones in the coff debug
1816   // directory.  Now we can hash the file and write that hash to the various
1817   // timestamp fields in the file.
1818   StringRef outputFileData(
1819       reinterpret_cast<const char *>(buffer->getBufferStart()),
1820       buffer->getBufferSize());
1821
1822   uint32_t timestamp = config->timestamp;
1823   uint64_t hash = 0;
1824   bool generateSyntheticBuildId =
1825       config->mingw && config->debug && config->pdbPath.empty();
1826
1827   if (config->repro || generateSyntheticBuildId)
1828     hash = xxHash64(outputFileData);
1829
1830   if (config->repro)
1831     timestamp = static_cast<uint32_t>(hash);
1832
1833   if (generateSyntheticBuildId) {
1834     // For MinGW builds without a PDB file, we still generate a build id
1835     // to allow associating a crash dump to the executable.
1836     buildId->buildId->PDB70.CVSignature = OMF::Signature::PDB70;
1837     buildId->buildId->PDB70.Age = 1;
1838     memcpy(buildId->buildId->PDB70.Signature, &hash, 8);
1839     // xxhash only gives us 8 bytes, so put some fixed data in the other half.
1840     memcpy(&buildId->buildId->PDB70.Signature[8], "LLD PDB.", 8);
1841   }
1842
1843   if (debugDirectory)
1844     debugDirectory->setTimeDateStamp(timestamp);
1845
1846   uint8_t *buf = buffer->getBufferStart();
1847   buf += dosStubSize + sizeof(PEMagic);
1848   object::coff_file_header *coffHeader =
1849       reinterpret_cast<coff_file_header *>(buf);
1850   coffHeader->TimeDateStamp = timestamp;
1851 }
1852
1853 // Sort .pdata section contents according to PE/COFF spec 5.5.
1854 void Writer::sortExceptionTable() {
1855   if (!firstPdata)
1856     return;
1857   // We assume .pdata contains function table entries only.
1858   auto bufAddr = [&](Chunk *c) {
1859     OutputSection *os = c->getOutputSection();
1860     return buffer->getBufferStart() + os->getFileOff() + c->getRVA() -
1861            os->getRVA();
1862   };
1863   uint8_t *begin = bufAddr(firstPdata);
1864   uint8_t *end = bufAddr(lastPdata) + lastPdata->getSize();
1865   if (config->machine == AMD64) {
1866     struct Entry { ulittle32_t begin, end, unwind; };
1867     if ((end - begin) % sizeof(Entry) != 0) {
1868       fatal("unexpected .pdata size: " + Twine(end - begin) +
1869             " is not a multiple of " + Twine(sizeof(Entry)));
1870     }
1871     parallelSort(
1872         MutableArrayRef<Entry>((Entry *)begin, (Entry *)end),
1873         [](const Entry &a, const Entry &b) { return a.begin < b.begin; });
1874     return;
1875   }
1876   if (config->machine == ARMNT || config->machine == ARM64) {
1877     struct Entry { ulittle32_t begin, unwind; };
1878     if ((end - begin) % sizeof(Entry) != 0) {
1879       fatal("unexpected .pdata size: " + Twine(end - begin) +
1880             " is not a multiple of " + Twine(sizeof(Entry)));
1881     }
1882     parallelSort(
1883         MutableArrayRef<Entry>((Entry *)begin, (Entry *)end),
1884         [](const Entry &a, const Entry &b) { return a.begin < b.begin; });
1885     return;
1886   }
1887   lld::errs() << "warning: don't know how to handle .pdata.\n";
1888 }
1889
1890 // The CRT section contains, among other things, the array of function
1891 // pointers that initialize every global variable that is not trivially
1892 // constructed. The CRT calls them one after the other prior to invoking
1893 // main().
1894 //
1895 // As per C++ spec, 3.6.2/2.3,
1896 // "Variables with ordered initialization defined within a single
1897 // translation unit shall be initialized in the order of their definitions
1898 // in the translation unit"
1899 //
1900 // It is therefore critical to sort the chunks containing the function
1901 // pointers in the order that they are listed in the object file (top to
1902 // bottom), otherwise global objects might not be initialized in the
1903 // correct order.
1904 void Writer::sortCRTSectionChunks(std::vector<Chunk *> &chunks) {
1905   auto sectionChunkOrder = [](const Chunk *a, const Chunk *b) {
1906     auto sa = dyn_cast<SectionChunk>(a);
1907     auto sb = dyn_cast<SectionChunk>(b);
1908     assert(sa && sb && "Non-section chunks in CRT section!");
1909
1910     StringRef sAObj = sa->file->mb.getBufferIdentifier();
1911     StringRef sBObj = sb->file->mb.getBufferIdentifier();
1912
1913     return sAObj == sBObj && sa->getSectionNumber() < sb->getSectionNumber();
1914   };
1915   llvm::stable_sort(chunks, sectionChunkOrder);
1916
1917   if (config->verbose) {
1918     for (auto &c : chunks) {
1919       auto sc = dyn_cast<SectionChunk>(c);
1920       log("  " + sc->file->mb.getBufferIdentifier().str() +
1921           ", SectionID: " + Twine(sc->getSectionNumber()));
1922     }
1923   }
1924 }
1925
1926 OutputSection *Writer::findSection(StringRef name) {
1927   for (OutputSection *sec : outputSections)
1928     if (sec->name == name)
1929       return sec;
1930   return nullptr;
1931 }
1932
1933 uint32_t Writer::getSizeOfInitializedData() {
1934   uint32_t res = 0;
1935   for (OutputSection *s : outputSections)
1936     if (s->header.Characteristics & IMAGE_SCN_CNT_INITIALIZED_DATA)
1937       res += s->getRawSize();
1938   return res;
1939 }
1940
1941 // Add base relocations to .reloc section.
1942 void Writer::addBaserels() {
1943   if (!config->relocatable)
1944     return;
1945   relocSec->chunks.clear();
1946   std::vector<Baserel> v;
1947   for (OutputSection *sec : outputSections) {
1948     if (sec->header.Characteristics & IMAGE_SCN_MEM_DISCARDABLE)
1949       continue;
1950     // Collect all locations for base relocations.
1951     for (Chunk *c : sec->chunks)
1952       c->getBaserels(&v);
1953     // Add the addresses to .reloc section.
1954     if (!v.empty())
1955       addBaserelBlocks(v);
1956     v.clear();
1957   }
1958 }
1959
1960 // Add addresses to .reloc section. Note that addresses are grouped by page.
1961 void Writer::addBaserelBlocks(std::vector<Baserel> &v) {
1962   const uint32_t mask = ~uint32_t(pageSize - 1);
1963   uint32_t page = v[0].rva & mask;
1964   size_t i = 0, j = 1;
1965   for (size_t e = v.size(); j < e; ++j) {
1966     uint32_t p = v[j].rva & mask;
1967     if (p == page)
1968       continue;
1969     relocSec->addChunk(make<BaserelChunk>(page, &v[i], &v[0] + j));
1970     i = j;
1971     page = p;
1972   }
1973   if (i == j)
1974     return;
1975   relocSec->addChunk(make<BaserelChunk>(page, &v[i], &v[0] + j));
1976 }
1977
1978 PartialSection *Writer::createPartialSection(StringRef name,
1979                                              uint32_t outChars) {
1980   PartialSection *&pSec = partialSections[{name, outChars}];
1981   if (pSec)
1982     return pSec;
1983   pSec = make<PartialSection>(name, outChars);
1984   return pSec;
1985 }
1986
1987 PartialSection *Writer::findPartialSection(StringRef name, uint32_t outChars) {
1988   auto it = partialSections.find({name, outChars});
1989   if (it != partialSections.end())
1990     return it->second;
1991   return nullptr;
1992 }