contrib/llvm-project/lld/COFF/Writer.cpp

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