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