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