contrib/llvm/tools/lld/ELF/Writer.cpp

   1 //===- Writer.cpp ---------------------------------------------------------===//
   2 //
   3 //                             The LLVM Linker
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "Writer.h"
  11 #include "AArch64ErrataFix.h"
  12 #include "Config.h"
  13 #include "Filesystem.h"
  14 #include "LinkerScript.h"
  15 #include "MapFile.h"
  16 #include "OutputSections.h"
  17 #include "Relocations.h"
  18 #include "Strings.h"
  19 #include "SymbolTable.h"
  20 #include "Symbols.h"
  21 #include "SyntheticSections.h"
  22 #include "Target.h"
  23 #include "lld/Common/Memory.h"
  24 #include "lld/Common/Threads.h"
  25 #include "llvm/ADT/StringMap.h"
  26 #include "llvm/ADT/StringSwitch.h"
  27 #include <climits>
  28
  29 using namespace llvm;
  30 using namespace llvm::ELF;
  31 using namespace llvm::object;
  32 using namespace llvm::support;
  33 using namespace llvm::support::endian;
  34
  35 using namespace lld;
  36 using namespace lld::elf;
  37
  38 namespace {
  39 // The writer writes a SymbolTable result to a file.
  40 template <class ELFT> class Writer {
  41 public:
  42   Writer() : Buffer(errorHandler().OutputBuffer) {}
  43   typedef typename ELFT::Shdr Elf_Shdr;
  44   typedef typename ELFT::Ehdr Elf_Ehdr;
  45   typedef typename ELFT::Phdr Elf_Phdr;
  46
  47   void run();
  48
  49 private:
  50   void copyLocalSymbols();
  51   void addSectionSymbols();
  52   void forEachRelSec(std::function<void(InputSectionBase &)> Fn);
  53   void sortSections();
  54   void resolveShfLinkOrder();
  55   void sortInputSections();
  56   void finalizeSections();
  57   void addPredefinedSections();
  58   void setReservedSymbolSections();
  59
  60   std::vector<PhdrEntry *> createPhdrs();
  61   void removeEmptyPTLoad();
  62   void addPtArmExid(std::vector<PhdrEntry *> &Phdrs);
  63   void assignFileOffsets();
  64   void assignFileOffsetsBinary();
  65   void setPhdrs();
  66   void fixSectionAlignments();
  67   void openFile();
  68   void writeTrapInstr();
  69   void writeHeader();
  70   void writeSections();
  71   void writeSectionsBinary();
  72   void writeBuildId();
  73
  74   std::unique_ptr<FileOutputBuffer> &Buffer;
  75
  76   void addRelIpltSymbols();
  77   void addStartEndSymbols();
  78   void addStartStopSymbols(OutputSection *Sec);
  79   uint64_t getEntryAddr();
  80
  81   std::vector<PhdrEntry *> Phdrs;
  82
  83   uint64_t FileSize;
  84   uint64_t SectionHeaderOff;
  85
  86   bool HasGotBaseSym = false;
  87 };
  88 } // anonymous namespace
  89
  90 StringRef elf::getOutputSectionName(InputSectionBase *S) {
  91   // ".zdebug_" is a prefix for ZLIB-compressed sections.
  92   // Because we decompressed input sections, we want to remove 'z'.
  93   if (S->Name.startswith(".zdebug_"))
  94     return Saver.save("." + S->Name.substr(2));
  95
  96   if (Config->Relocatable)
  97     return S->Name;
  98
  99   // This is for --emit-relocs. If .text.foo is emitted as .text.bar, we want
 100   // to emit .rela.text.foo as .rela.text.bar for consistency (this is not
 101   // technically required, but not doing it is odd). This code guarantees that.
 102   if ((S->Type == SHT_REL || S->Type == SHT_RELA) &&
 103       !isa<SyntheticSection>(S)) {
 104     OutputSection *Out =
 105         cast<InputSection>(S)->getRelocatedSection()->getOutputSection();
 106     if (S->Type == SHT_RELA)
 107       return Saver.save(".rela" + Out->Name);
 108     return Saver.save(".rel" + Out->Name);
 109   }
 110
 111   for (StringRef V :
 112        {".text.", ".rodata.", ".data.rel.ro.", ".data.", ".bss.rel.ro.",
 113         ".bss.", ".init_array.", ".fini_array.", ".ctors.", ".dtors.", ".tbss.",
 114         ".gcc_except_table.", ".tdata.", ".ARM.exidx.", ".ARM.extab."}) {
 115     StringRef Prefix = V.drop_back();
 116     if (S->Name.startswith(V) || S->Name == Prefix)
 117       return Prefix;
 118   }
 119
 120   // CommonSection is identified as "COMMON" in linker scripts.
 121   // By default, it should go to .bss section.
 122   if (S->Name == "COMMON")
 123     return ".bss";
 124
 125   return S->Name;
 126 }
 127
 128 static bool needsInterpSection() {
 129   return !SharedFiles.empty() && !Config->DynamicLinker.empty() &&
 130          Script->needsInterpSection();
 131 }
 132
 133 template <class ELFT> void elf::writeResult() { Writer<ELFT>().run(); }
 134
 135 template <class ELFT> void Writer<ELFT>::removeEmptyPTLoad() {
 136   llvm::erase_if(Phdrs, [&](const PhdrEntry *P) {
 137     if (P->p_type != PT_LOAD)
 138       return false;
 139     if (!P->FirstSec)
 140       return true;
 141     uint64_t Size = P->LastSec->Addr + P->LastSec->Size - P->FirstSec->Addr;
 142     return Size == 0;
 143   });
 144 }
 145
 146 template <class ELFT> static void combineEhFrameSections() {
 147   for (InputSectionBase *&S : InputSections) {
 148     EhInputSection *ES = dyn_cast<EhInputSection>(S);
 149     if (!ES || !ES->Live)
 150       continue;
 151
 152     InX::EhFrame->addSection<ELFT>(ES);
 153     S = nullptr;
 154   }
 155
 156   std::vector<InputSectionBase *> &V = InputSections;
 157   V.erase(std::remove(V.begin(), V.end(), nullptr), V.end());
 158 }
 159
 160 template <class ELFT>
 161 static Defined *addOptionalRegular(StringRef Name, SectionBase *Sec,
 162                                    uint64_t Val, uint8_t StOther = STV_HIDDEN,
 163                                    uint8_t Binding = STB_GLOBAL) {
 164   Symbol *S = Symtab->find(Name);
 165   if (!S || S->isDefined())
 166     return nullptr;
 167   Symbol *Sym = Symtab->addRegular<ELFT>(Name, StOther, STT_NOTYPE, Val,
 168                                          /*Size=*/0, Binding, Sec,
 169                                          /*File=*/nullptr);
 170   return cast<Defined>(Sym);
 171 }
 172
 173 // The linker is expected to define some symbols depending on
 174 // the linking result. This function defines such symbols.
 175 template <class ELFT> void elf::addReservedSymbols() {
 176   if (Config->EMachine == EM_MIPS) {
 177     // Define _gp for MIPS. st_value of _gp symbol will be updated by Writer
 178     // so that it points to an absolute address which by default is relative
 179     // to GOT. Default offset is 0x7ff0.
 180     // See "Global Data Symbols" in Chapter 6 in the following document:
 181     // ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf
 182     ElfSym::MipsGp = Symtab->addAbsolute<ELFT>("_gp", STV_HIDDEN, STB_GLOBAL);
 183
 184     // On MIPS O32 ABI, _gp_disp is a magic symbol designates offset between
 185     // start of function and 'gp' pointer into GOT.
 186     if (Symtab->find("_gp_disp"))
 187       ElfSym::MipsGpDisp =
 188           Symtab->addAbsolute<ELFT>("_gp_disp", STV_HIDDEN, STB_GLOBAL);
 189
 190     // The __gnu_local_gp is a magic symbol equal to the current value of 'gp'
 191     // pointer. This symbol is used in the code generated by .cpload pseudo-op
 192     // in case of using -mno-shared option.
 193     // https://sourceware.org/ml/binutils/2004-12/msg00094.html
 194     if (Symtab->find("__gnu_local_gp"))
 195       ElfSym::MipsLocalGp =
 196           Symtab->addAbsolute<ELFT>("__gnu_local_gp", STV_HIDDEN, STB_GLOBAL);
 197   }
 198
 199   ElfSym::GlobalOffsetTable = addOptionalRegular<ELFT>(
 200       "_GLOBAL_OFFSET_TABLE_", Out::ElfHeader, Target->GotBaseSymOff);
 201
 202   // __ehdr_start is the location of ELF file headers. Note that we define
 203   // this symbol unconditionally even when using a linker script, which
 204   // differs from the behavior implemented by GNU linker which only define
 205   // this symbol if ELF headers are in the memory mapped segment.
 206   // __executable_start is not documented, but the expectation of at
 207   // least the android libc is that it points to the elf header too.
 208   // __dso_handle symbol is passed to cxa_finalize as a marker to identify
 209   // each DSO. The address of the symbol doesn't matter as long as they are
 210   // different in different DSOs, so we chose the start address of the DSO.
 211   for (const char *Name :
 212        {"__ehdr_start", "__executable_start", "__dso_handle"})
 213     addOptionalRegular<ELFT>(Name, Out::ElfHeader, 0, STV_HIDDEN);
 214
 215   // If linker script do layout we do not need to create any standart symbols.
 216   if (Script->HasSectionsCommand)
 217     return;
 218
 219   auto Add = [](StringRef S, int64_t Pos) {
 220     return addOptionalRegular<ELFT>(S, Out::ElfHeader, Pos, STV_DEFAULT);
 221   };
 222
 223   ElfSym::Bss = Add("__bss_start", 0);
 224   ElfSym::End1 = Add("end", -1);
 225   ElfSym::End2 = Add("_end", -1);
 226   ElfSym::Etext1 = Add("etext", -1);
 227   ElfSym::Etext2 = Add("_etext", -1);
 228   ElfSym::Edata1 = Add("edata", -1);
 229   ElfSym::Edata2 = Add("_edata", -1);
 230 }
 231
 232 static OutputSection *findSection(StringRef Name) {
 233   for (BaseCommand *Base : Script->SectionCommands)
 234     if (auto *Sec = dyn_cast<OutputSection>(Base))
 235       if (Sec->Name == Name)
 236         return Sec;
 237   return nullptr;
 238 }
 239
 240 // Initialize Out members.
 241 template <class ELFT> static void createSyntheticSections() {
 242   // Initialize all pointers with NULL. This is needed because
 243   // you can call lld::elf::main more than once as a library.
 244   memset(&Out::First, 0, sizeof(Out));
 245
 246   auto Add = [](InputSectionBase *Sec) { InputSections.push_back(Sec); };
 247
 248   InX::DynStrTab = make<StringTableSection>(".dynstr", true);
 249   InX::Dynamic = make<DynamicSection<ELFT>>();
 250   if (Config->AndroidPackDynRelocs) {
 251     InX::RelaDyn = make<AndroidPackedRelocationSection<ELFT>>(
 252         Config->IsRela ? ".rela.dyn" : ".rel.dyn");
 253   } else {
 254     InX::RelaDyn = make<RelocationSection<ELFT>>(
 255         Config->IsRela ? ".rela.dyn" : ".rel.dyn", Config->ZCombreloc);
 256   }
 257   InX::ShStrTab = make<StringTableSection>(".shstrtab", false);
 258
 259   Out::ProgramHeaders = make<OutputSection>("", 0, SHF_ALLOC);
 260   Out::ProgramHeaders->Alignment = Config->Wordsize;
 261
 262   if (needsInterpSection()) {
 263     InX::Interp = createInterpSection();
 264     Add(InX::Interp);
 265   } else {
 266     InX::Interp = nullptr;
 267   }
 268
 269   if (Config->Strip != StripPolicy::All) {
 270     InX::StrTab = make<StringTableSection>(".strtab", false);
 271     InX::SymTab = make<SymbolTableSection<ELFT>>(*InX::StrTab);
 272   }
 273
 274   if (Config->BuildId != BuildIdKind::None) {
 275     InX::BuildId = make<BuildIdSection>();
 276     Add(InX::BuildId);
 277   }
 278
 279   InX::Bss = make<BssSection>(".bss", 0, 1);
 280   Add(InX::Bss);
 281
 282   // If there is a SECTIONS command and a .data.rel.ro section name use name
 283   // .data.rel.ro.bss so that we match in the .data.rel.ro output section.
 284   // This makes sure our relro is contiguous.
 285   bool HasDataRelRo =
 286       Script->HasSectionsCommand && findSection(".data.rel.ro");
 287   InX::BssRelRo = make<BssSection>(
 288       HasDataRelRo ? ".data.rel.ro.bss" : ".bss.rel.ro", 0, 1);
 289   Add(InX::BssRelRo);
 290
 291   // Add MIPS-specific sections.
 292   if (Config->EMachine == EM_MIPS) {
 293     if (!Config->Shared && Config->HasDynSymTab) {
 294       InX::MipsRldMap = make<MipsRldMapSection>();
 295       Add(InX::MipsRldMap);
 296     }
 297     if (auto *Sec = MipsAbiFlagsSection<ELFT>::create())
 298       Add(Sec);
 299     if (auto *Sec = MipsOptionsSection<ELFT>::create())
 300       Add(Sec);
 301     if (auto *Sec = MipsReginfoSection<ELFT>::create())
 302       Add(Sec);
 303   }
 304
 305   if (Config->HasDynSymTab) {
 306     InX::DynSymTab = make<SymbolTableSection<ELFT>>(*InX::DynStrTab);
 307     Add(InX::DynSymTab);
 308
 309     In<ELFT>::VerSym = make<VersionTableSection<ELFT>>();
 310     Add(In<ELFT>::VerSym);
 311
 312     if (!Config->VersionDefinitions.empty()) {
 313       In<ELFT>::VerDef = make<VersionDefinitionSection<ELFT>>();
 314       Add(In<ELFT>::VerDef);
 315     }
 316
 317     In<ELFT>::VerNeed = make<VersionNeedSection<ELFT>>();
 318     Add(In<ELFT>::VerNeed);
 319
 320     if (Config->GnuHash) {
 321       InX::GnuHashTab = make<GnuHashTableSection>();
 322       Add(InX::GnuHashTab);
 323     }
 324
 325     if (Config->SysvHash) {
 326       InX::HashTab = make<HashTableSection>();
 327       Add(InX::HashTab);
 328     }
 329
 330     Add(InX::Dynamic);
 331     Add(InX::DynStrTab);
 332     Add(InX::RelaDyn);
 333   }
 334
 335   // Add .got. MIPS' .got is so different from the other archs,
 336   // it has its own class.
 337   if (Config->EMachine == EM_MIPS) {
 338     InX::MipsGot = make<MipsGotSection>();
 339     Add(InX::MipsGot);
 340   } else {
 341     InX::Got = make<GotSection>();
 342     Add(InX::Got);
 343   }
 344
 345   InX::GotPlt = make<GotPltSection>();
 346   Add(InX::GotPlt);
 347   InX::IgotPlt = make<IgotPltSection>();
 348   Add(InX::IgotPlt);
 349
 350   if (Config->GdbIndex) {
 351     InX::GdbIndex = createGdbIndex<ELFT>();
 352     Add(InX::GdbIndex);
 353   }
 354
 355   // We always need to add rel[a].plt to output if it has entries.
 356   // Even for static linking it can contain R_[*]_IRELATIVE relocations.
 357   InX::RelaPlt = make<RelocationSection<ELFT>>(
 358       Config->IsRela ? ".rela.plt" : ".rel.plt", false /*Sort*/);
 359   Add(InX::RelaPlt);
 360
 361   // The RelaIplt immediately follows .rel.plt (.rel.dyn for ARM) to ensure
 362   // that the IRelative relocations are processed last by the dynamic loader.
 363   // We cannot place the iplt section in .rel.dyn when Android relocation
 364   // packing is enabled because that would cause a section type mismatch.
 365   // However, because the Android dynamic loader reads .rel.plt after .rel.dyn,
 366   // we can get the desired behaviour by placing the iplt section in .rel.plt.
 367   InX::RelaIplt = make<RelocationSection<ELFT>>(
 368       (Config->EMachine == EM_ARM && !Config->AndroidPackDynRelocs)
 369           ? ".rel.dyn"
 370           : InX::RelaPlt->Name,
 371       false /*Sort*/);
 372   Add(InX::RelaIplt);
 373
 374   InX::Plt = make<PltSection>(Target->PltHeaderSize);
 375   Add(InX::Plt);
 376   InX::Iplt = make<PltSection>(0);
 377   Add(InX::Iplt);
 378
 379   if (!Config->Relocatable) {
 380     if (Config->EhFrameHdr) {
 381       InX::EhFrameHdr = make<EhFrameHeader>();
 382       Add(InX::EhFrameHdr);
 383     }
 384     InX::EhFrame = make<EhFrameSection>();
 385     Add(InX::EhFrame);
 386   }
 387
 388   if (InX::SymTab)
 389     Add(InX::SymTab);
 390   Add(InX::ShStrTab);
 391   if (InX::StrTab)
 392     Add(InX::StrTab);
 393 }
 394
 395 // The main function of the writer.
 396 template <class ELFT> void Writer<ELFT>::run() {
 397   // Create linker-synthesized sections such as .got or .plt.
 398   // Such sections are of type input section.
 399   createSyntheticSections<ELFT>();
 400
 401   if (!Config->Relocatable)
 402     combineEhFrameSections<ELFT>();
 403
 404   // We want to process linker script commands. When SECTIONS command
 405   // is given we let it create sections.
 406   Script->processSectionCommands();
 407
 408   // Linker scripts controls how input sections are assigned to output sections.
 409   // Input sections that were not handled by scripts are called "orphans", and
 410   // they are assigned to output sections by the default rule. Process that.
 411   Script->addOrphanSections();
 412
 413   if (Config->Discard != DiscardPolicy::All)
 414     copyLocalSymbols();
 415
 416   if (Config->CopyRelocs)
 417     addSectionSymbols();
 418
 419   // Now that we have a complete set of output sections. This function
 420   // completes section contents. For example, we need to add strings
 421   // to the string table, and add entries to .got and .plt.
 422   // finalizeSections does that.
 423   finalizeSections();
 424   if (errorCount())
 425     return;
 426
 427   // If -compressed-debug-sections is specified, we need to compress
 428   // .debug_* sections. Do it right now because it changes the size of
 429   // output sections.
 430   parallelForEach(OutputSections,
 431                   [](OutputSection *Sec) { Sec->maybeCompress<ELFT>(); });
 432
 433   Script->assignAddresses();
 434   Script->allocateHeaders(Phdrs);
 435
 436   // Remove empty PT_LOAD to avoid causing the dynamic linker to try to mmap a
 437   // 0 sized region. This has to be done late since only after assignAddresses
 438   // we know the size of the sections.
 439   removeEmptyPTLoad();
 440
 441   if (!Config->OFormatBinary)
 442     assignFileOffsets();
 443   else
 444     assignFileOffsetsBinary();
 445
 446   setPhdrs();
 447
 448   if (Config->Relocatable) {
 449     for (OutputSection *Sec : OutputSections)
 450       Sec->Addr = 0;
 451   }
 452
 453   // It does not make sense try to open the file if we have error already.
 454   if (errorCount())
 455     return;
 456   // Write the result down to a file.
 457   openFile();
 458   if (errorCount())
 459     return;
 460
 461   if (!Config->OFormatBinary) {
 462     writeTrapInstr();
 463     writeHeader();
 464     writeSections();
 465   } else {
 466     writeSectionsBinary();
 467   }
 468
 469   // Backfill .note.gnu.build-id section content. This is done at last
 470   // because the content is usually a hash value of the entire output file.
 471   writeBuildId();
 472   if (errorCount())
 473     return;
 474
 475   // Handle -Map option.
 476   writeMapFile();
 477   if (errorCount())
 478     return;
 479
 480   if (auto E = Buffer->commit())
 481     error("failed to write to the output file: " + toString(std::move(E)));
 482 }
 483
 484 static bool shouldKeepInSymtab(SectionBase *Sec, StringRef SymName,
 485                                const Symbol &B) {
 486   if (B.isFile() || B.isSection())
 487     return false;
 488
 489   // If sym references a section in a discarded group, don't keep it.
 490   if (Sec == &InputSection::Discarded)
 491     return false;
 492
 493   if (Config->Discard == DiscardPolicy::None)
 494     return true;
 495
 496   // In ELF assembly .L symbols are normally discarded by the assembler.
 497   // If the assembler fails to do so, the linker discards them if
 498   // * --discard-locals is used.
 499   // * The symbol is in a SHF_MERGE section, which is normally the reason for
 500   //   the assembler keeping the .L symbol.
 501   if (!SymName.startswith(".L") && !SymName.empty())
 502     return true;
 503
 504   if (Config->Discard == DiscardPolicy::Locals)
 505     return false;
 506
 507   return !Sec || !(Sec->Flags & SHF_MERGE);
 508 }
 509
 510 static bool includeInSymtab(const Symbol &B) {
 511   if (!B.isLocal() && !B.IsUsedInRegularObj)
 512     return false;
 513
 514   if (auto *D = dyn_cast<Defined>(&B)) {
 515     // Always include absolute symbols.
 516     SectionBase *Sec = D->Section;
 517     if (!Sec)
 518       return true;
 519     Sec = Sec->Repl;
 520     // Exclude symbols pointing to garbage-collected sections.
 521     if (isa<InputSectionBase>(Sec) && !Sec->Live)
 522       return false;
 523     if (auto *S = dyn_cast<MergeInputSection>(Sec))
 524       if (!S->getSectionPiece(D->Value)->Live)
 525         return false;
 526     return true;
 527   }
 528   return B.Used;
 529 }
 530
 531 // Local symbols are not in the linker's symbol table. This function scans
 532 // each object file's symbol table to copy local symbols to the output.
 533 template <class ELFT> void Writer<ELFT>::copyLocalSymbols() {
 534   if (!InX::SymTab)
 535     return;
 536   for (InputFile *File : ObjectFiles) {
 537     ObjFile<ELFT> *F = cast<ObjFile<ELFT>>(File);
 538     for (Symbol *B : F->getLocalSymbols()) {
 539       if (!B->isLocal())
 540         fatal(toString(F) +
 541               ": broken object: getLocalSymbols returns a non-local symbol");
 542       auto *DR = dyn_cast<Defined>(B);
 543
 544       // No reason to keep local undefined symbol in symtab.
 545       if (!DR)
 546         continue;
 547       if (!includeInSymtab(*B))
 548         continue;
 549
 550       SectionBase *Sec = DR->Section;
 551       if (!shouldKeepInSymtab(Sec, B->getName(), *B))
 552         continue;
 553       InX::SymTab->addSymbol(B);
 554     }
 555   }
 556 }
 557
 558 template <class ELFT> void Writer<ELFT>::addSectionSymbols() {
 559   // Create a section symbol for each output section so that we can represent
 560   // relocations that point to the section. If we know that no relocation is
 561   // referring to a section (that happens if the section is a synthetic one), we
 562   // don't create a section symbol for that section.
 563   for (BaseCommand *Base : Script->SectionCommands) {
 564     auto *Sec = dyn_cast<OutputSection>(Base);
 565     if (!Sec)
 566       continue;
 567     auto I = llvm::find_if(Sec->SectionCommands, [](BaseCommand *Base) {
 568       if (auto *ISD = dyn_cast<InputSectionDescription>(Base))
 569         return !ISD->Sections.empty();
 570       return false;
 571     });
 572     if (I == Sec->SectionCommands.end())
 573       continue;
 574     InputSection *IS = cast<InputSectionDescription>(*I)->Sections[0];
 575
 576     // Relocations are not using REL[A] section symbols.
 577     if (IS->Type == SHT_REL || IS->Type == SHT_RELA)
 578       continue;
 579
 580     // Unlike other synthetic sections, mergeable output sections contain data
 581     // copied from input sections, and there may be a relocation pointing to its
 582     // contents if -r or -emit-reloc are given.
 583     if (isa<SyntheticSection>(IS) && !(IS->Flags & SHF_MERGE))
 584       continue;
 585
 586     auto *Sym =
 587         make<Defined>(IS->File, "", STB_LOCAL, /*StOther=*/0, STT_SECTION,
 588                       /*Value=*/0, /*Size=*/0, IS);
 589     InX::SymTab->addSymbol(Sym);
 590   }
 591 }
 592
 593 // Today's loaders have a feature to make segments read-only after
 594 // processing dynamic relocations to enhance security. PT_GNU_RELRO
 595 // is defined for that.
 596 //
 597 // This function returns true if a section needs to be put into a
 598 // PT_GNU_RELRO segment.
 599 static bool isRelroSection(const OutputSection *Sec) {
 600   if (!Config->ZRelro)
 601     return false;
 602
 603   uint64_t Flags = Sec->Flags;
 604
 605   // Non-allocatable or non-writable sections don't need RELRO because
 606   // they are not writable or not even mapped to memory in the first place.
 607   // RELRO is for sections that are essentially read-only but need to
 608   // be writable only at process startup to allow dynamic linker to
 609   // apply relocations.
 610   if (!(Flags & SHF_ALLOC) || !(Flags & SHF_WRITE))
 611     return false;
 612
 613   // Once initialized, TLS data segments are used as data templates
 614   // for a thread-local storage. For each new thread, runtime
 615   // allocates memory for a TLS and copy templates there. No thread
 616   // are supposed to use templates directly. Thus, it can be in RELRO.
 617   if (Flags & SHF_TLS)
 618     return true;
 619
 620   // .init_array, .preinit_array and .fini_array contain pointers to
 621   // functions that are executed on process startup or exit. These
 622   // pointers are set by the static linker, and they are not expected
 623   // to change at runtime. But if you are an attacker, you could do
 624   // interesting things by manipulating pointers in .fini_array, for
 625   // example. So they are put into RELRO.
 626   uint32_t Type = Sec->Type;
 627   if (Type == SHT_INIT_ARRAY || Type == SHT_FINI_ARRAY ||
 628       Type == SHT_PREINIT_ARRAY)
 629     return true;
 630
 631   // .got contains pointers to external symbols. They are resolved by
 632   // the dynamic linker when a module is loaded into memory, and after
 633   // that they are not expected to change. So, it can be in RELRO.
 634   if (InX::Got && Sec == InX::Got->getParent())
 635     return true;
 636
 637   // .got.plt contains pointers to external function symbols. They are
 638   // by default resolved lazily, so we usually cannot put it into RELRO.
 639   // However, if "-z now" is given, the lazy symbol resolution is
 640   // disabled, which enables us to put it into RELRO.
 641   if (Sec == InX::GotPlt->getParent())
 642     return Config->ZNow;
 643
 644   // .dynamic section contains data for the dynamic linker, and
 645   // there's no need to write to it at runtime, so it's better to put
 646   // it into RELRO.
 647   if (Sec == InX::Dynamic->getParent())
 648     return true;
 649
 650   // Sections with some special names are put into RELRO. This is a
 651   // bit unfortunate because section names shouldn't be significant in
 652   // ELF in spirit. But in reality many linker features depend on
 653   // magic section names.
 654   StringRef S = Sec->Name;
 655   return S == ".data.rel.ro" || S == ".bss.rel.ro" || S == ".ctors" ||
 656          S == ".dtors" || S == ".jcr" || S == ".eh_frame" ||
 657          S == ".openbsd.randomdata";
 658 }
 659
 660 // We compute a rank for each section. The rank indicates where the
 661 // section should be placed in the file.  Instead of using simple
 662 // numbers (0,1,2...), we use a series of flags. One for each decision
 663 // point when placing the section.
 664 // Using flags has two key properties:
 665 // * It is easy to check if a give branch was taken.
 666 // * It is easy two see how similar two ranks are (see getRankProximity).
 667 enum RankFlags {
 668   RF_NOT_ADDR_SET = 1 << 16,
 669   RF_NOT_INTERP = 1 << 15,
 670   RF_NOT_ALLOC = 1 << 14,
 671   RF_WRITE = 1 << 13,
 672   RF_EXEC_WRITE = 1 << 12,
 673   RF_EXEC = 1 << 11,
 674   RF_NON_TLS_BSS = 1 << 10,
 675   RF_NON_TLS_BSS_RO = 1 << 9,
 676   RF_NOT_TLS = 1 << 8,
 677   RF_BSS = 1 << 7,
 678   RF_PPC_NOT_TOCBSS = 1 << 6,
 679   RF_PPC_OPD = 1 << 5,
 680   RF_PPC_TOCL = 1 << 4,
 681   RF_PPC_TOC = 1 << 3,
 682   RF_PPC_BRANCH_LT = 1 << 2,
 683   RF_MIPS_GPREL = 1 << 1,
 684   RF_MIPS_NOT_GOT = 1 << 0
 685 };
 686
 687 static unsigned getSectionRank(const OutputSection *Sec) {
 688   unsigned Rank = 0;
 689
 690   // We want to put section specified by -T option first, so we
 691   // can start assigning VA starting from them later.
 692   if (Config->SectionStartMap.count(Sec->Name))
 693     return Rank;
 694   Rank |= RF_NOT_ADDR_SET;
 695
 696   // Put .interp first because some loaders want to see that section
 697   // on the first page of the executable file when loaded into memory.
 698   if (Sec->Name == ".interp")
 699     return Rank;
 700   Rank |= RF_NOT_INTERP;
 701
 702   // Allocatable sections go first to reduce the total PT_LOAD size and
 703   // so debug info doesn't change addresses in actual code.
 704   if (!(Sec->Flags & SHF_ALLOC))
 705     return Rank | RF_NOT_ALLOC;
 706
 707   // Sort sections based on their access permission in the following
 708   // order: R, RX, RWX, RW.  This order is based on the following
 709   // considerations:
 710   // * Read-only sections come first such that they go in the
 711   //   PT_LOAD covering the program headers at the start of the file.
 712   // * Read-only, executable sections come next, unless the
 713   //   -no-rosegment option is used.
 714   // * Writable, executable sections follow such that .plt on
 715   //   architectures where it needs to be writable will be placed
 716   //   between .text and .data.
 717   // * Writable sections come last, such that .bss lands at the very
 718   //   end of the last PT_LOAD.
 719   bool IsExec = Sec->Flags & SHF_EXECINSTR;
 720   bool IsWrite = Sec->Flags & SHF_WRITE;
 721
 722   if (IsExec) {
 723     if (IsWrite)
 724       Rank |= RF_EXEC_WRITE;
 725     else if (!Config->SingleRoRx)
 726       Rank |= RF_EXEC;
 727   } else {
 728     if (IsWrite)
 729       Rank |= RF_WRITE;
 730   }
 731
 732   // If we got here we know that both A and B are in the same PT_LOAD.
 733
 734   bool IsTls = Sec->Flags & SHF_TLS;
 735   bool IsNoBits = Sec->Type == SHT_NOBITS;
 736
 737   // The first requirement we have is to put (non-TLS) nobits sections last. The
 738   // reason is that the only thing the dynamic linker will see about them is a
 739   // p_memsz that is larger than p_filesz. Seeing that it zeros the end of the
 740   // PT_LOAD, so that has to correspond to the nobits sections.
 741   bool IsNonTlsNoBits = IsNoBits && !IsTls;
 742   if (IsNonTlsNoBits)
 743     Rank |= RF_NON_TLS_BSS;
 744
 745   // We place nobits RelRo sections before plain r/w ones, and non-nobits RelRo
 746   // sections after r/w ones, so that the RelRo sections are contiguous.
 747   bool IsRelRo = isRelroSection(Sec);
 748   if (IsNonTlsNoBits && !IsRelRo)
 749     Rank |= RF_NON_TLS_BSS_RO;
 750   if (!IsNonTlsNoBits && IsRelRo)
 751     Rank |= RF_NON_TLS_BSS_RO;
 752
 753   // The TLS initialization block needs to be a single contiguous block in a R/W
 754   // PT_LOAD, so stick TLS sections directly before the other RelRo R/W
 755   // sections. The TLS NOBITS sections are placed here as they don't take up
 756   // virtual address space in the PT_LOAD.
 757   if (!IsTls)
 758     Rank |= RF_NOT_TLS;
 759
 760   // Within the TLS initialization block, the non-nobits sections need to appear
 761   // first.
 762   if (IsNoBits)
 763     Rank |= RF_BSS;
 764
 765   // Some architectures have additional ordering restrictions for sections
 766   // within the same PT_LOAD.
 767   if (Config->EMachine == EM_PPC64) {
 768     // PPC64 has a number of special SHT_PROGBITS+SHF_ALLOC+SHF_WRITE sections
 769     // that we would like to make sure appear is a specific order to maximize
 770     // their coverage by a single signed 16-bit offset from the TOC base
 771     // pointer. Conversely, the special .tocbss section should be first among
 772     // all SHT_NOBITS sections. This will put it next to the loaded special
 773     // PPC64 sections (and, thus, within reach of the TOC base pointer).
 774     StringRef Name = Sec->Name;
 775     if (Name != ".tocbss")
 776       Rank |= RF_PPC_NOT_TOCBSS;
 777
 778     if (Name == ".opd")
 779       Rank |= RF_PPC_OPD;
 780
 781     if (Name == ".toc1")
 782       Rank |= RF_PPC_TOCL;
 783
 784     if (Name == ".toc")
 785       Rank |= RF_PPC_TOC;
 786
 787     if (Name == ".branch_lt")
 788       Rank |= RF_PPC_BRANCH_LT;
 789   }
 790   if (Config->EMachine == EM_MIPS) {
 791     // All sections with SHF_MIPS_GPREL flag should be grouped together
 792     // because data in these sections is addressable with a gp relative address.
 793     if (Sec->Flags & SHF_MIPS_GPREL)
 794       Rank |= RF_MIPS_GPREL;
 795
 796     if (Sec->Name != ".got")
 797       Rank |= RF_MIPS_NOT_GOT;
 798   }
 799
 800   return Rank;
 801 }
 802
 803 static bool compareSections(const BaseCommand *ACmd, const BaseCommand *BCmd) {
 804   const OutputSection *A = cast<OutputSection>(ACmd);
 805   const OutputSection *B = cast<OutputSection>(BCmd);
 806   if (A->SortRank != B->SortRank)
 807     return A->SortRank < B->SortRank;
 808   if (!(A->SortRank & RF_NOT_ADDR_SET))
 809     return Config->SectionStartMap.lookup(A->Name) <
 810            Config->SectionStartMap.lookup(B->Name);
 811   return false;
 812 }
 813
 814 void PhdrEntry::add(OutputSection *Sec) {
 815   LastSec = Sec;
 816   if (!FirstSec)
 817     FirstSec = Sec;
 818   p_align = std::max(p_align, Sec->Alignment);
 819   if (p_type == PT_LOAD)
 820     Sec->PtLoad = this;
 821 }
 822
 823 // The beginning and the ending of .rel[a].plt section are marked
 824 // with __rel[a]_iplt_{start,end} symbols if it is a statically linked
 825 // executable. The runtime needs these symbols in order to resolve
 826 // all IRELATIVE relocs on startup. For dynamic executables, we don't
 827 // need these symbols, since IRELATIVE relocs are resolved through GOT
 828 // and PLT. For details, see http://www.airs.com/blog/archives/403.
 829 template <class ELFT> void Writer<ELFT>::addRelIpltSymbols() {
 830   if (!Config->Static)
 831     return;
 832   StringRef S = Config->IsRela ? "__rela_iplt_start" : "__rel_iplt_start";
 833   addOptionalRegular<ELFT>(S, InX::RelaIplt, 0, STV_HIDDEN, STB_WEAK);
 834
 835   S = Config->IsRela ? "__rela_iplt_end" : "__rel_iplt_end";
 836   addOptionalRegular<ELFT>(S, InX::RelaIplt, -1, STV_HIDDEN, STB_WEAK);
 837 }
 838
 839 template <class ELFT>
 840 void Writer<ELFT>::forEachRelSec(std::function<void(InputSectionBase &)> Fn) {
 841   // Scan all relocations. Each relocation goes through a series
 842   // of tests to determine if it needs special treatment, such as
 843   // creating GOT, PLT, copy relocations, etc.
 844   // Note that relocations for non-alloc sections are directly
 845   // processed by InputSection::relocateNonAlloc.
 846   for (InputSectionBase *IS : InputSections)
 847     if (IS->Live && isa<InputSection>(IS) && (IS->Flags & SHF_ALLOC))
 848       Fn(*IS);
 849   for (EhInputSection *ES : InX::EhFrame->Sections)
 850     Fn(*ES);
 851 }
 852
 853 // This function generates assignments for predefined symbols (e.g. _end or
 854 // _etext) and inserts them into the commands sequence to be processed at the
 855 // appropriate time. This ensures that the value is going to be correct by the
 856 // time any references to these symbols are processed and is equivalent to
 857 // defining these symbols explicitly in the linker script.
 858 template <class ELFT> void Writer<ELFT>::setReservedSymbolSections() {
 859   if (ElfSym::GlobalOffsetTable) {
 860     // The _GLOBAL_OFFSET_TABLE_ symbol is defined by target convention to
 861     // be at some offset from the base of the .got section, usually 0 or the end
 862     // of the .got
 863     InputSection *GotSection = InX::MipsGot ? cast<InputSection>(InX::MipsGot)
 864                                             : cast<InputSection>(InX::Got);
 865     ElfSym::GlobalOffsetTable->Section = GotSection;
 866   }
 867
 868   PhdrEntry *Last = nullptr;
 869   PhdrEntry *LastRO = nullptr;
 870
 871   for (PhdrEntry *P : Phdrs) {
 872     if (P->p_type != PT_LOAD)
 873       continue;
 874     Last = P;
 875     if (!(P->p_flags & PF_W))
 876       LastRO = P;
 877   }
 878
 879   if (LastRO) {
 880     // _etext is the first location after the last read-only loadable segment.
 881     if (ElfSym::Etext1)
 882       ElfSym::Etext1->Section = LastRO->LastSec;
 883     if (ElfSym::Etext2)
 884       ElfSym::Etext2->Section = LastRO->LastSec;
 885   }
 886
 887   if (Last) {
 888     // _edata points to the end of the last mapped initialized section.
 889     OutputSection *Edata = nullptr;
 890     for (OutputSection *OS : OutputSections) {
 891       if (OS->Type != SHT_NOBITS)
 892         Edata = OS;
 893       if (OS == Last->LastSec)
 894         break;
 895     }
 896
 897     if (ElfSym::Edata1)
 898       ElfSym::Edata1->Section = Edata;
 899     if (ElfSym::Edata2)
 900       ElfSym::Edata2->Section = Edata;
 901
 902     // _end is the first location after the uninitialized data region.
 903     if (ElfSym::End1)
 904       ElfSym::End1->Section = Last->LastSec;
 905     if (ElfSym::End2)
 906       ElfSym::End2->Section = Last->LastSec;
 907   }
 908
 909   if (ElfSym::Bss)
 910     ElfSym::Bss->Section = findSection(".bss");
 911
 912   // Setup MIPS _gp_disp/__gnu_local_gp symbols which should
 913   // be equal to the _gp symbol's value.
 914   if (ElfSym::MipsGp) {
 915     // Find GP-relative section with the lowest address
 916     // and use this address to calculate default _gp value.
 917     for (OutputSection *OS : OutputSections) {
 918       if (OS->Flags & SHF_MIPS_GPREL) {
 919         ElfSym::MipsGp->Section = OS;
 920         ElfSym::MipsGp->Value = 0x7ff0;
 921         break;
 922       }
 923     }
 924   }
 925 }
 926
 927 // We want to find how similar two ranks are.
 928 // The more branches in getSectionRank that match, the more similar they are.
 929 // Since each branch corresponds to a bit flag, we can just use
 930 // countLeadingZeros.
 931 static int getRankProximityAux(OutputSection *A, OutputSection *B) {
 932   return countLeadingZeros(A->SortRank ^ B->SortRank);
 933 }
 934
 935 static int getRankProximity(OutputSection *A, BaseCommand *B) {
 936   if (auto *Sec = dyn_cast<OutputSection>(B))
 937     if (Sec->Live)
 938       return getRankProximityAux(A, Sec);
 939   return -1;
 940 }
 941
 942 // When placing orphan sections, we want to place them after symbol assignments
 943 // so that an orphan after
 944 //   begin_foo = .;
 945 //   foo : { *(foo) }
 946 //   end_foo = .;
 947 // doesn't break the intended meaning of the begin/end symbols.
 948 // We don't want to go over sections since findOrphanPos is the
 949 // one in charge of deciding the order of the sections.
 950 // We don't want to go over changes to '.', since doing so in
 951 //  rx_sec : { *(rx_sec) }
 952 //  . = ALIGN(0x1000);
 953 //  /* The RW PT_LOAD starts here*/
 954 //  rw_sec : { *(rw_sec) }
 955 // would mean that the RW PT_LOAD would become unaligned.
 956 static bool shouldSkip(BaseCommand *Cmd) {
 957   if (isa<OutputSection>(Cmd))
 958     return false;
 959   if (auto *Assign = dyn_cast<SymbolAssignment>(Cmd))
 960     return Assign->Name != ".";
 961   return true;
 962 }
 963
 964 // We want to place orphan sections so that they share as much
 965 // characteristics with their neighbors as possible. For example, if
 966 // both are rw, or both are tls.
 967 template <typename ELFT>
 968 static std::vector<BaseCommand *>::iterator
 969 findOrphanPos(std::vector<BaseCommand *>::iterator B,
 970               std::vector<BaseCommand *>::iterator E) {
 971   OutputSection *Sec = cast<OutputSection>(*E);
 972
 973   // Find the first element that has as close a rank as possible.
 974   auto I = std::max_element(B, E, [=](BaseCommand *A, BaseCommand *B) {
 975     return getRankProximity(Sec, A) < getRankProximity(Sec, B);
 976   });
 977   if (I == E)
 978     return E;
 979
 980   // Consider all existing sections with the same proximity.
 981   int Proximity = getRankProximity(Sec, *I);
 982   for (; I != E; ++I) {
 983     auto *CurSec = dyn_cast<OutputSection>(*I);
 984     if (!CurSec || !CurSec->Live)
 985       continue;
 986     if (getRankProximity(Sec, CurSec) != Proximity ||
 987         Sec->SortRank < CurSec->SortRank)
 988       break;
 989   }
 990
 991   auto IsLiveSection = [](BaseCommand *Cmd) {
 992     auto *OS = dyn_cast<OutputSection>(Cmd);
 993     return OS && OS->Live;
 994   };
 995
 996   auto J = std::find_if(llvm::make_reverse_iterator(I),
 997                         llvm::make_reverse_iterator(B), IsLiveSection);
 998   I = J.base();
 999
1000   // As a special case, if the orphan section is the last section, put
1001   // it at the very end, past any other commands.
1002   // This matches bfd's behavior and is convenient when the linker script fully
1003   // specifies the start of the file, but doesn't care about the end (the non
1004   // alloc sections for example).
1005   auto NextSec = std::find_if(I, E, IsLiveSection);
1006   if (NextSec == E)
1007     return E;
1008
1009   while (I != E && shouldSkip(*I))
1010     ++I;
1011   return I;
1012 }
1013
1014 // If no layout was provided by linker script, we want to apply default
1015 // sorting for special input sections and handle --symbol-ordering-file.
1016 template <class ELFT> void Writer<ELFT>::sortInputSections() {
1017   assert(!Script->HasSectionsCommand);
1018
1019   // Sort input sections by priority using the list provided
1020   // by --symbol-ordering-file.
1021   DenseMap<SectionBase *, int> Order = buildSectionOrder();
1022   if (!Order.empty())
1023     for (BaseCommand *Base : Script->SectionCommands)
1024       if (auto *Sec = dyn_cast<OutputSection>(Base))
1025         if (Sec->Live)
1026           Sec->sort([&](InputSectionBase *S) { return Order.lookup(S); });
1027
1028   // Sort input sections by section name suffixes for
1029   // __attribute__((init_priority(N))).
1030   if (OutputSection *Sec = findSection(".init_array"))
1031     Sec->sortInitFini();
1032   if (OutputSection *Sec = findSection(".fini_array"))
1033     Sec->sortInitFini();
1034
1035   // Sort input sections by the special rule for .ctors and .dtors.
1036   if (OutputSection *Sec = findSection(".ctors"))
1037     Sec->sortCtorsDtors();
1038   if (OutputSection *Sec = findSection(".dtors"))
1039     Sec->sortCtorsDtors();
1040 }
1041
1042 template <class ELFT> void Writer<ELFT>::sortSections() {
1043   Script->adjustSectionsBeforeSorting();
1044
1045   // Don't sort if using -r. It is not necessary and we want to preserve the
1046   // relative order for SHF_LINK_ORDER sections.
1047   if (Config->Relocatable)
1048     return;
1049
1050   for (BaseCommand *Base : Script->SectionCommands)
1051     if (auto *Sec = dyn_cast<OutputSection>(Base))
1052       Sec->SortRank = getSectionRank(Sec);
1053
1054   if (!Script->HasSectionsCommand) {
1055     sortInputSections();
1056
1057     // We know that all the OutputSections are contiguous in this case.
1058     auto E = Script->SectionCommands.end();
1059     auto I = Script->SectionCommands.begin();
1060     auto IsSection = [](BaseCommand *Base) { return isa<OutputSection>(Base); };
1061     I = std::find_if(I, E, IsSection);
1062     E = std::find_if(llvm::make_reverse_iterator(E),
1063                      llvm::make_reverse_iterator(I), IsSection)
1064             .base();
1065     std::stable_sort(I, E, compareSections);
1066     return;
1067   }
1068
1069   // Orphan sections are sections present in the input files which are
1070   // not explicitly placed into the output file by the linker script.
1071   //
1072   // The sections in the linker script are already in the correct
1073   // order. We have to figuere out where to insert the orphan
1074   // sections.
1075   //
1076   // The order of the sections in the script is arbitrary and may not agree with
1077   // compareSections. This means that we cannot easily define a strict weak
1078   // ordering. To see why, consider a comparison of a section in the script and
1079   // one not in the script. We have a two simple options:
1080   // * Make them equivalent (a is not less than b, and b is not less than a).
1081   //   The problem is then that equivalence has to be transitive and we can
1082   //   have sections a, b and c with only b in a script and a less than c
1083   //   which breaks this property.
1084   // * Use compareSectionsNonScript. Given that the script order doesn't have
1085   //   to match, we can end up with sections a, b, c, d where b and c are in the
1086   //   script and c is compareSectionsNonScript less than b. In which case d
1087   //   can be equivalent to c, a to b and d < a. As a concrete example:
1088   //   .a (rx) # not in script
1089   //   .b (rx) # in script
1090   //   .c (ro) # in script
1091   //   .d (ro) # not in script
1092   //
1093   // The way we define an order then is:
1094   // *  Sort only the orphan sections. They are in the end right now.
1095   // *  Move each orphan section to its preferred position. We try
1096   //    to put each section in the last position where it it can share
1097   //    a PT_LOAD.
1098   //
1099   // There is some ambiguity as to where exactly a new entry should be
1100   // inserted, because Commands contains not only output section
1101   // commands but also other types of commands such as symbol assignment
1102   // expressions. There's no correct answer here due to the lack of the
1103   // formal specification of the linker script. We use heuristics to
1104   // determine whether a new output command should be added before or
1105   // after another commands. For the details, look at shouldSkip
1106   // function.
1107
1108   auto I = Script->SectionCommands.begin();
1109   auto E = Script->SectionCommands.end();
1110   auto NonScriptI = std::find_if(I, E, [](BaseCommand *Base) {
1111     if (auto *Sec = dyn_cast<OutputSection>(Base))
1112       return Sec->Live && Sec->SectionIndex == INT_MAX;
1113     return false;
1114   });
1115
1116   // Sort the orphan sections.
1117   std::stable_sort(NonScriptI, E, compareSections);
1118
1119   // As a horrible special case, skip the first . assignment if it is before any
1120   // section. We do this because it is common to set a load address by starting
1121   // the script with ". = 0xabcd" and the expectation is that every section is
1122   // after that.
1123   auto FirstSectionOrDotAssignment =
1124       std::find_if(I, E, [](BaseCommand *Cmd) { return !shouldSkip(Cmd); });
1125   if (FirstSectionOrDotAssignment != E &&
1126       isa<SymbolAssignment>(**FirstSectionOrDotAssignment))
1127     ++FirstSectionOrDotAssignment;
1128   I = FirstSectionOrDotAssignment;
1129
1130   while (NonScriptI != E) {
1131     auto Pos = findOrphanPos<ELFT>(I, NonScriptI);
1132     OutputSection *Orphan = cast<OutputSection>(*NonScriptI);
1133
1134     // As an optimization, find all sections with the same sort rank
1135     // and insert them with one rotate.
1136     unsigned Rank = Orphan->SortRank;
1137     auto End = std::find_if(NonScriptI + 1, E, [=](BaseCommand *Cmd) {
1138       return cast<OutputSection>(Cmd)->SortRank != Rank;
1139     });
1140     std::rotate(Pos, NonScriptI, End);
1141     NonScriptI = End;
1142   }
1143
1144   Script->adjustSectionsAfterSorting();
1145 }
1146
1147 static bool compareByFilePosition(InputSection *A, InputSection *B) {
1148   // Synthetic doesn't have link order dependecy, stable_sort will keep it last
1149   if (A->kind() == InputSectionBase::Synthetic ||
1150       B->kind() == InputSectionBase::Synthetic)
1151     return false;
1152   InputSection *LA = A->getLinkOrderDep();
1153   InputSection *LB = B->getLinkOrderDep();
1154   OutputSection *AOut = LA->getParent();
1155   OutputSection *BOut = LB->getParent();
1156   if (AOut != BOut)
1157     return AOut->SectionIndex < BOut->SectionIndex;
1158   return LA->OutSecOff < LB->OutSecOff;
1159 }
1160
1161 // This function is used by the --merge-exidx-entries to detect duplicate
1162 // .ARM.exidx sections. It is Arm only.
1163 //
1164 // The .ARM.exidx section is of the form:
1165 // | PREL31 offset to function | Unwind instructions for function |
1166 // where the unwind instructions are either a small number of unwind
1167 // instructions inlined into the table entry, the special CANT_UNWIND value of
1168 // 0x1 or a PREL31 offset into a .ARM.extab Section that contains unwind
1169 // instructions.
1170 //
1171 // We return true if all the unwind instructions in the .ARM.exidx entries of
1172 // Cur can be merged into the last entry of Prev.
1173 static bool isDuplicateArmExidxSec(InputSection *Prev, InputSection *Cur) {
1174
1175   // References to .ARM.Extab Sections have bit 31 clear and are not the
1176   // special EXIDX_CANTUNWIND bit-pattern.
1177   auto IsExtabRef = [](uint32_t Unwind) {
1178     return (Unwind & 0x80000000) == 0 && Unwind != 0x1;
1179   };
1180
1181   struct ExidxEntry {
1182     ulittle32_t Fn;
1183     ulittle32_t Unwind;
1184   };
1185
1186   // Get the last table Entry from the previous .ARM.exidx section.
1187   const ExidxEntry &PrevEntry = *reinterpret_cast<const ExidxEntry *>(
1188       Prev->Data.data() + Prev->getSize() - sizeof(ExidxEntry));
1189   if (IsExtabRef(PrevEntry.Unwind))
1190     return false;
1191
1192   // We consider the unwind instructions of an .ARM.exidx table entry
1193   // a duplicate if the previous unwind instructions if:
1194   // - Both are the special EXIDX_CANTUNWIND.
1195   // - Both are the same inline unwind instructions.
1196   // We do not attempt to follow and check links into .ARM.extab tables as
1197   // consecutive identical entries are rare and the effort to check that they
1198   // are identical is high.
1199
1200   if (isa<SyntheticSection>(Cur))
1201     // Exidx sentinel section has implicit EXIDX_CANTUNWIND;
1202     return PrevEntry.Unwind == 0x1;
1203
1204   ArrayRef<const ExidxEntry> Entries(
1205       reinterpret_cast<const ExidxEntry *>(Cur->Data.data()),
1206       Cur->getSize() / sizeof(ExidxEntry));
1207   for (const ExidxEntry &Entry : Entries)
1208     if (IsExtabRef(Entry.Unwind) || Entry.Unwind != PrevEntry.Unwind)
1209       return false;
1210   // All table entries in this .ARM.exidx Section can be merged into the
1211   // previous Section.
1212   return true;
1213 }
1214
1215 template <class ELFT> void Writer<ELFT>::resolveShfLinkOrder() {
1216   for (OutputSection *Sec : OutputSections) {
1217     if (!(Sec->Flags & SHF_LINK_ORDER))
1218       continue;
1219
1220     // Link order may be distributed across several InputSectionDescriptions
1221     // but sort must consider them all at once.
1222     std::vector<InputSection **> ScriptSections;
1223     std::vector<InputSection *> Sections;
1224     for (BaseCommand *Base : Sec->SectionCommands) {
1225       if (auto *ISD = dyn_cast<InputSectionDescription>(Base)) {
1226         for (InputSection *&IS : ISD->Sections) {
1227           ScriptSections.push_back(&IS);
1228           Sections.push_back(IS);
1229         }
1230       }
1231     }
1232     std::stable_sort(Sections.begin(), Sections.end(), compareByFilePosition);
1233
1234     if (Config->MergeArmExidx && !Config->Relocatable &&
1235         Config->EMachine == EM_ARM && Sec->Type == SHT_ARM_EXIDX) {
1236       // The EHABI for the Arm Architecture permits consecutive identical
1237       // table entries to be merged. We use a simple implementation that
1238       // removes a .ARM.exidx Input Section if it can be merged into the
1239       // previous one. This does not require any rewriting of InputSection
1240       // contents but misses opportunities for fine grained deduplication where
1241       // only a subset of the InputSection contents can be merged.
1242       int Cur = 1;
1243       int Prev = 0;
1244       int N = Sections.size();
1245       while (Cur < N) {
1246         if (isDuplicateArmExidxSec(Sections[Prev], Sections[Cur]))
1247           Sections[Cur] = nullptr;
1248         else
1249           Prev = Cur;
1250         ++Cur;
1251       }
1252     }
1253
1254     for (int I = 0, N = Sections.size(); I < N; ++I)
1255       *ScriptSections[I] = Sections[I];
1256
1257     // Remove the Sections we marked as duplicate earlier.
1258     for (BaseCommand *Base : Sec->SectionCommands)
1259       if (auto *ISD = dyn_cast<InputSectionDescription>(Base))
1260         ISD->Sections.erase(
1261             std::remove(ISD->Sections.begin(), ISD->Sections.end(), nullptr),
1262             ISD->Sections.end());
1263   }
1264 }
1265
1266 static void applySynthetic(const std::vector<SyntheticSection *> &Sections,
1267                            std::function<void(SyntheticSection *)> Fn) {
1268   for (SyntheticSection *SS : Sections)
1269     if (SS && SS->getParent() && !SS->empty())
1270       Fn(SS);
1271 }
1272
1273 // In order to allow users to manipulate linker-synthesized sections,
1274 // we had to add synthetic sections to the input section list early,
1275 // even before we make decisions whether they are needed. This allows
1276 // users to write scripts like this: ".mygot : { .got }".
1277 //
1278 // Doing it has an unintended side effects. If it turns out that we
1279 // don't need a .got (for example) at all because there's no
1280 // relocation that needs a .got, we don't want to emit .got.
1281 //
1282 // To deal with the above problem, this function is called after
1283 // scanRelocations is called to remove synthetic sections that turn
1284 // out to be empty.
1285 static void removeUnusedSyntheticSections() {
1286   // All input synthetic sections that can be empty are placed after
1287   // all regular ones. We iterate over them all and exit at first
1288   // non-synthetic.
1289   for (InputSectionBase *S : llvm::reverse(InputSections)) {
1290     SyntheticSection *SS = dyn_cast<SyntheticSection>(S);
1291     if (!SS)
1292       return;
1293     OutputSection *OS = SS->getParent();
1294     if (!SS->empty() || !OS)
1295       continue;
1296
1297     std::vector<BaseCommand *>::iterator Empty = OS->SectionCommands.end();
1298     for (auto I = OS->SectionCommands.begin(), E = OS->SectionCommands.end();
1299          I != E; ++I) {
1300       BaseCommand *B = *I;
1301       if (auto *ISD = dyn_cast<InputSectionDescription>(B)) {
1302         llvm::erase_if(ISD->Sections,
1303                        [=](InputSection *IS) { return IS == SS; });
1304         if (ISD->Sections.empty())
1305           Empty = I;
1306       }
1307     }
1308     if (Empty != OS->SectionCommands.end())
1309       OS->SectionCommands.erase(Empty);
1310
1311     // If there are no other sections in the output section, remove it from the
1312     // output.
1313     if (OS->SectionCommands.empty())
1314       OS->Live = false;
1315   }
1316 }
1317
1318 // Returns true if a symbol can be replaced at load-time by a symbol
1319 // with the same name defined in other ELF executable or DSO.
1320 static bool computeIsPreemptible(const Symbol &B) {
1321   assert(!B.isLocal());
1322   // Only symbols that appear in dynsym can be preempted.
1323   if (!B.includeInDynsym())
1324     return false;
1325
1326   // Only default visibility symbols can be preempted.
1327   if (B.Visibility != STV_DEFAULT)
1328     return false;
1329
1330   // At this point copy relocations have not been created yet, so any
1331   // symbol that is not defined locally is preemptible.
1332   if (!B.isDefined())
1333     return true;
1334
1335   // If we have a dynamic list it specifies which local symbols are preemptible.
1336   if (Config->HasDynamicList)
1337     return false;
1338
1339   if (!Config->Shared)
1340     return false;
1341
1342   // -Bsymbolic means that definitions are not preempted.
1343   if (Config->Bsymbolic || (Config->BsymbolicFunctions && B.isFunc()))
1344     return false;
1345   return true;
1346 }
1347
1348 // Create output section objects and add them to OutputSections.
1349 template <class ELFT> void Writer<ELFT>::finalizeSections() {
1350   Out::DebugInfo = findSection(".debug_info");
1351   Out::PreinitArray = findSection(".preinit_array");
1352   Out::InitArray = findSection(".init_array");
1353   Out::FiniArray = findSection(".fini_array");
1354
1355   // The linker needs to define SECNAME_start, SECNAME_end and SECNAME_stop
1356   // symbols for sections, so that the runtime can get the start and end
1357   // addresses of each section by section name. Add such symbols.
1358   if (!Config->Relocatable) {
1359     addStartEndSymbols();
1360     for (BaseCommand *Base : Script->SectionCommands)
1361       if (auto *Sec = dyn_cast<OutputSection>(Base))
1362         addStartStopSymbols(Sec);
1363   }
1364
1365   // Add _DYNAMIC symbol. Unlike GNU gold, our _DYNAMIC symbol has no type.
1366   // It should be okay as no one seems to care about the type.
1367   // Even the author of gold doesn't remember why gold behaves that way.
1368   // https://sourceware.org/ml/binutils/2002-03/msg00360.html
1369   if (InX::DynSymTab)
1370     Symtab->addRegular<ELFT>("_DYNAMIC", STV_HIDDEN, STT_NOTYPE, 0 /*Value*/,
1371                              /*Size=*/0, STB_WEAK, InX::Dynamic,
1372                              /*File=*/nullptr);
1373
1374   // Define __rel[a]_iplt_{start,end} symbols if needed.
1375   addRelIpltSymbols();
1376
1377   // This responsible for splitting up .eh_frame section into
1378   // pieces. The relocation scan uses those pieces, so this has to be
1379   // earlier.
1380   applySynthetic({InX::EhFrame},
1381                  [](SyntheticSection *SS) { SS->finalizeContents(); });
1382
1383   for (Symbol *S : Symtab->getSymbols())
1384     S->IsPreemptible |= computeIsPreemptible(*S);
1385
1386   // Scan relocations. This must be done after every symbol is declared so that
1387   // we can correctly decide if a dynamic relocation is needed.
1388   if (!Config->Relocatable)
1389     forEachRelSec(scanRelocations<ELFT>);
1390
1391   if (InX::Plt && !InX::Plt->empty())
1392     InX::Plt->addSymbols();
1393   if (InX::Iplt && !InX::Iplt->empty())
1394     InX::Iplt->addSymbols();
1395
1396   // Now that we have defined all possible global symbols including linker-
1397   // synthesized ones. Visit all symbols to give the finishing touches.
1398   for (Symbol *Sym : Symtab->getSymbols()) {
1399     if (!includeInSymtab(*Sym))
1400       continue;
1401     if (InX::SymTab)
1402       InX::SymTab->addSymbol(Sym);
1403
1404     if (InX::DynSymTab && Sym->includeInDynsym()) {
1405       InX::DynSymTab->addSymbol(Sym);
1406       if (auto *SS = dyn_cast<SharedSymbol>(Sym))
1407         if (cast<SharedFile<ELFT>>(Sym->File)->IsNeeded)
1408           In<ELFT>::VerNeed->addSymbol(SS);
1409     }
1410   }
1411
1412   // Do not proceed if there was an undefined symbol.
1413   if (errorCount())
1414     return;
1415
1416   addPredefinedSections();
1417   removeUnusedSyntheticSections();
1418
1419   sortSections();
1420   Script->removeEmptyCommands();
1421
1422   // Now that we have the final list, create a list of all the
1423   // OutputSections for convenience.
1424   for (BaseCommand *Base : Script->SectionCommands)
1425     if (auto *Sec = dyn_cast<OutputSection>(Base))
1426       OutputSections.push_back(Sec);
1427
1428   // Prefer command line supplied address over other constraints.
1429   for (OutputSection *Sec : OutputSections) {
1430     auto I = Config->SectionStartMap.find(Sec->Name);
1431     if (I != Config->SectionStartMap.end())
1432       Sec->AddrExpr = [=] { return I->second; };
1433   }
1434
1435   // This is a bit of a hack. A value of 0 means undef, so we set it
1436   // to 1 t make __ehdr_start defined. The section number is not
1437   // particularly relevant.
1438   Out::ElfHeader->SectionIndex = 1;
1439
1440   unsigned I = 1;
1441   for (OutputSection *Sec : OutputSections) {
1442     Sec->SectionIndex = I++;
1443     Sec->ShName = InX::ShStrTab->addString(Sec->Name);
1444   }
1445
1446   // Binary and relocatable output does not have PHDRS.
1447   // The headers have to be created before finalize as that can influence the
1448   // image base and the dynamic section on mips includes the image base.
1449   if (!Config->Relocatable && !Config->OFormatBinary) {
1450     Phdrs = Script->hasPhdrsCommands() ? Script->createPhdrs() : createPhdrs();
1451     addPtArmExid(Phdrs);
1452     Out::ProgramHeaders->Size = sizeof(Elf_Phdr) * Phdrs.size();
1453   }
1454
1455   // Some symbols are defined in term of program headers. Now that we
1456   // have the headers, we can find out which sections they point to.
1457   setReservedSymbolSections();
1458
1459   // Dynamic section must be the last one in this list and dynamic
1460   // symbol table section (DynSymTab) must be the first one.
1461   applySynthetic(
1462       {InX::DynSymTab,   InX::Bss,          InX::BssRelRo, InX::GnuHashTab,
1463        InX::HashTab,     InX::SymTab,       InX::ShStrTab, InX::StrTab,
1464        In<ELFT>::VerDef, InX::DynStrTab,    InX::Got,      InX::MipsGot,
1465        InX::IgotPlt,     InX::GotPlt,       InX::RelaDyn,  InX::RelaIplt,
1466        InX::RelaPlt,     InX::Plt,          InX::Iplt,     InX::EhFrameHdr,
1467        In<ELFT>::VerSym, In<ELFT>::VerNeed, InX::Dynamic},
1468       [](SyntheticSection *SS) { SS->finalizeContents(); });
1469
1470   if (!Script->HasSectionsCommand && !Config->Relocatable)
1471     fixSectionAlignments();
1472
1473   // After link order processing .ARM.exidx sections can be deduplicated, which
1474   // needs to be resolved before any other address dependent operation.
1475   resolveShfLinkOrder();
1476
1477   // Some architectures need to generate content that depends on the address
1478   // of InputSections. For example some architectures use small displacements
1479   // for jump instructions that is is the linker's responsibility for creating
1480   // range extension thunks for. As the generation of the content may also
1481   // alter InputSection addresses we must converge to a fixed point.
1482   if (Target->NeedsThunks || Config->AndroidPackDynRelocs) {
1483     ThunkCreator TC;
1484     AArch64Err843419Patcher A64P;
1485     bool Changed;
1486     do {
1487       Script->assignAddresses();
1488       Changed = false;
1489       if (Target->NeedsThunks)
1490         Changed |= TC.createThunks(OutputSections);
1491       if (Config->FixCortexA53Errata843419) {
1492         if (Changed)
1493           Script->assignAddresses();
1494         Changed |= A64P.createFixes();
1495       }
1496       if (InX::MipsGot)
1497         InX::MipsGot->updateAllocSize();
1498       Changed |= InX::RelaDyn->updateAllocSize();
1499     } while (Changed);
1500   }
1501
1502   // Fill other section headers. The dynamic table is finalized
1503   // at the end because some tags like RELSZ depend on result
1504   // of finalizing other sections.
1505   for (OutputSection *Sec : OutputSections)
1506     Sec->finalize<ELFT>();
1507
1508   // createThunks may have added local symbols to the static symbol table
1509   applySynthetic({InX::SymTab},
1510                  [](SyntheticSection *SS) { SS->postThunkContents(); });
1511 }
1512
1513 template <class ELFT> void Writer<ELFT>::addPredefinedSections() {
1514   // ARM ABI requires .ARM.exidx to be terminated by some piece of data.
1515   // We have the terminater synthetic section class. Add that at the end.
1516   OutputSection *Cmd = findSection(".ARM.exidx");
1517   if (!Cmd || !Cmd->Live || Config->Relocatable)
1518     return;
1519
1520   auto *Sentinel = make<ARMExidxSentinelSection>();
1521   Cmd->addSection(Sentinel);
1522 }
1523
1524 // The linker is expected to define SECNAME_start and SECNAME_end
1525 // symbols for a few sections. This function defines them.
1526 template <class ELFT> void Writer<ELFT>::addStartEndSymbols() {
1527   auto Define = [&](StringRef Start, StringRef End, OutputSection *OS) {
1528     // These symbols resolve to the image base if the section does not exist.
1529     // A special value -1 indicates end of the section.
1530     if (OS) {
1531       addOptionalRegular<ELFT>(Start, OS, 0);
1532       addOptionalRegular<ELFT>(End, OS, -1);
1533     } else {
1534       if (Config->Pic)
1535         OS = Out::ElfHeader;
1536       addOptionalRegular<ELFT>(Start, OS, 0);
1537       addOptionalRegular<ELFT>(End, OS, 0);
1538     }
1539   };
1540
1541   Define("__preinit_array_start", "__preinit_array_end", Out::PreinitArray);
1542   Define("__init_array_start", "__init_array_end", Out::InitArray);
1543   Define("__fini_array_start", "__fini_array_end", Out::FiniArray);
1544
1545   if (OutputSection *Sec = findSection(".ARM.exidx"))
1546     Define("__exidx_start", "__exidx_end", Sec);
1547 }
1548
1549 // If a section name is valid as a C identifier (which is rare because of
1550 // the leading '.'), linkers are expected to define __start_<secname> and
1551 // __stop_<secname> symbols. They are at beginning and end of the section,
1552 // respectively. This is not requested by the ELF standard, but GNU ld and
1553 // gold provide the feature, and used by many programs.
1554 template <class ELFT>
1555 void Writer<ELFT>::addStartStopSymbols(OutputSection *Sec) {
1556   StringRef S = Sec->Name;
1557   if (!isValidCIdentifier(S))
1558     return;
1559   addOptionalRegular<ELFT>(Saver.save("__start_" + S), Sec, 0, STV_DEFAULT);
1560   addOptionalRegular<ELFT>(Saver.save("__stop_" + S), Sec, -1, STV_DEFAULT);
1561 }
1562
1563 static bool needsPtLoad(OutputSection *Sec) {
1564   if (!(Sec->Flags & SHF_ALLOC))
1565     return false;
1566
1567   // Don't allocate VA space for TLS NOBITS sections. The PT_TLS PHDR is
1568   // responsible for allocating space for them, not the PT_LOAD that
1569   // contains the TLS initialization image.
1570   if (Sec->Flags & SHF_TLS && Sec->Type == SHT_NOBITS)
1571     return false;
1572   return true;
1573 }
1574
1575 // Linker scripts are responsible for aligning addresses. Unfortunately, most
1576 // linker scripts are designed for creating two PT_LOADs only, one RX and one
1577 // RW. This means that there is no alignment in the RO to RX transition and we
1578 // cannot create a PT_LOAD there.
1579 static uint64_t computeFlags(uint64_t Flags) {
1580   if (Config->Omagic)
1581     return PF_R | PF_W | PF_X;
1582   if (Config->SingleRoRx && !(Flags & PF_W))
1583     return Flags | PF_X;
1584   return Flags;
1585 }
1586
1587 // Decide which program headers to create and which sections to include in each
1588 // one.
1589 template <class ELFT> std::vector<PhdrEntry *> Writer<ELFT>::createPhdrs() {
1590   std::vector<PhdrEntry *> Ret;
1591   auto AddHdr = [&](unsigned Type, unsigned Flags) -> PhdrEntry * {
1592     Ret.push_back(make<PhdrEntry>(Type, Flags));
1593     return Ret.back();
1594   };
1595
1596   // The first phdr entry is PT_PHDR which describes the program header itself.
1597   AddHdr(PT_PHDR, PF_R)->add(Out::ProgramHeaders);
1598
1599   // PT_INTERP must be the second entry if exists.
1600   if (OutputSection *Cmd = findSection(".interp"))
1601     AddHdr(PT_INTERP, Cmd->getPhdrFlags())->add(Cmd);
1602
1603   // Add the first PT_LOAD segment for regular output sections.
1604   uint64_t Flags = computeFlags(PF_R);
1605   PhdrEntry *Load = AddHdr(PT_LOAD, Flags);
1606
1607   // Add the headers. We will remove them if they don't fit.
1608   Load->add(Out::ElfHeader);
1609   Load->add(Out::ProgramHeaders);
1610
1611   for (OutputSection *Sec : OutputSections) {
1612     if (!(Sec->Flags & SHF_ALLOC))
1613       break;
1614     if (!needsPtLoad(Sec))
1615       continue;
1616
1617     // Segments are contiguous memory regions that has the same attributes
1618     // (e.g. executable or writable). There is one phdr for each segment.
1619     // Therefore, we need to create a new phdr when the next section has
1620     // different flags or is loaded at a discontiguous address using AT linker
1621     // script command.
1622     uint64_t NewFlags = computeFlags(Sec->getPhdrFlags());
1623     if (Sec->LMAExpr || Flags != NewFlags) {
1624       Load = AddHdr(PT_LOAD, NewFlags);
1625       Flags = NewFlags;
1626     }
1627
1628     Load->add(Sec);
1629   }
1630
1631   // Add a TLS segment if any.
1632   PhdrEntry *TlsHdr = make<PhdrEntry>(PT_TLS, PF_R);
1633   for (OutputSection *Sec : OutputSections)
1634     if (Sec->Flags & SHF_TLS)
1635       TlsHdr->add(Sec);
1636   if (TlsHdr->FirstSec)
1637     Ret.push_back(TlsHdr);
1638
1639   // Add an entry for .dynamic.
1640   if (InX::DynSymTab)
1641     AddHdr(PT_DYNAMIC, InX::Dynamic->getParent()->getPhdrFlags())
1642         ->add(InX::Dynamic->getParent());
1643
1644   // PT_GNU_RELRO includes all sections that should be marked as
1645   // read-only by dynamic linker after proccessing relocations.
1646   // Current dynamic loaders only support one PT_GNU_RELRO PHDR, give
1647   // an error message if more than one PT_GNU_RELRO PHDR is required.
1648   PhdrEntry *RelRo = make<PhdrEntry>(PT_GNU_RELRO, PF_R);
1649   bool InRelroPhdr = false;
1650   bool IsRelroFinished = false;
1651   for (OutputSection *Sec : OutputSections) {
1652     if (!needsPtLoad(Sec))
1653       continue;
1654     if (isRelroSection(Sec)) {
1655       InRelroPhdr = true;
1656       if (!IsRelroFinished)
1657         RelRo->add(Sec);
1658       else
1659         error("section: " + Sec->Name + " is not contiguous with other relro" +
1660               " sections");
1661     } else if (InRelroPhdr) {
1662       InRelroPhdr = false;
1663       IsRelroFinished = true;
1664     }
1665   }
1666   if (RelRo->FirstSec)
1667     Ret.push_back(RelRo);
1668
1669   // PT_GNU_EH_FRAME is a special section pointing on .eh_frame_hdr.
1670   if (!InX::EhFrame->empty() && InX::EhFrameHdr && InX::EhFrame->getParent() &&
1671       InX::EhFrameHdr->getParent())
1672     AddHdr(PT_GNU_EH_FRAME, InX::EhFrameHdr->getParent()->getPhdrFlags())
1673         ->add(InX::EhFrameHdr->getParent());
1674
1675   // PT_OPENBSD_RANDOMIZE is an OpenBSD-specific feature. That makes
1676   // the dynamic linker fill the segment with random data.
1677   if (OutputSection *Cmd = findSection(".openbsd.randomdata"))
1678     AddHdr(PT_OPENBSD_RANDOMIZE, Cmd->getPhdrFlags())->add(Cmd);
1679
1680   // PT_GNU_STACK is a special section to tell the loader to make the
1681   // pages for the stack non-executable. If you really want an executable
1682   // stack, you can pass -z execstack, but that's not recommended for
1683   // security reasons.
1684   unsigned Perm;
1685   if (Config->ZExecstack)
1686     Perm = PF_R | PF_W | PF_X;
1687   else
1688     Perm = PF_R | PF_W;
1689   AddHdr(PT_GNU_STACK, Perm)->p_memsz = Config->ZStackSize;
1690
1691   // PT_OPENBSD_WXNEEDED is a OpenBSD-specific header to mark the executable
1692   // is expected to perform W^X violations, such as calling mprotect(2) or
1693   // mmap(2) with PROT_WRITE | PROT_EXEC, which is prohibited by default on
1694   // OpenBSD.
1695   if (Config->ZWxneeded)
1696     AddHdr(PT_OPENBSD_WXNEEDED, PF_X);
1697
1698   // Create one PT_NOTE per a group of contiguous .note sections.
1699   PhdrEntry *Note = nullptr;
1700   for (OutputSection *Sec : OutputSections) {
1701     if (Sec->Type == SHT_NOTE) {
1702       if (!Note || Sec->LMAExpr)
1703         Note = AddHdr(PT_NOTE, PF_R);
1704       Note->add(Sec);
1705     } else {
1706       Note = nullptr;
1707     }
1708   }
1709   return Ret;
1710 }
1711
1712 template <class ELFT>
1713 void Writer<ELFT>::addPtArmExid(std::vector<PhdrEntry *> &Phdrs) {
1714   if (Config->EMachine != EM_ARM)
1715     return;
1716   auto I = llvm::find_if(OutputSections, [](OutputSection *Cmd) {
1717     return Cmd->Type == SHT_ARM_EXIDX;
1718   });
1719   if (I == OutputSections.end())
1720     return;
1721
1722   // PT_ARM_EXIDX is the ARM EHABI equivalent of PT_GNU_EH_FRAME
1723   PhdrEntry *ARMExidx = make<PhdrEntry>(PT_ARM_EXIDX, PF_R);
1724   ARMExidx->add(*I);
1725   Phdrs.push_back(ARMExidx);
1726 }
1727
1728 // The first section of each PT_LOAD, the first section in PT_GNU_RELRO and the
1729 // first section after PT_GNU_RELRO have to be page aligned so that the dynamic
1730 // linker can set the permissions.
1731 template <class ELFT> void Writer<ELFT>::fixSectionAlignments() {
1732   auto PageAlign = [](OutputSection *Cmd) {
1733     if (Cmd && !Cmd->AddrExpr)
1734       Cmd->AddrExpr = [=] {
1735         return alignTo(Script->getDot(), Config->MaxPageSize);
1736       };
1737   };
1738
1739   for (const PhdrEntry *P : Phdrs)
1740     if (P->p_type == PT_LOAD && P->FirstSec)
1741       PageAlign(P->FirstSec);
1742
1743   for (const PhdrEntry *P : Phdrs) {
1744     if (P->p_type != PT_GNU_RELRO)
1745       continue;
1746     if (P->FirstSec)
1747       PageAlign(P->FirstSec);
1748     // Find the first section after PT_GNU_RELRO. If it is in a PT_LOAD we
1749     // have to align it to a page.
1750     auto End = OutputSections.end();
1751     auto I = std::find(OutputSections.begin(), End, P->LastSec);
1752     if (I == End || (I + 1) == End)
1753       continue;
1754     OutputSection *Cmd = (*(I + 1));
1755     if (needsPtLoad(Cmd))
1756       PageAlign(Cmd);
1757   }
1758 }
1759
1760 // Adjusts the file alignment for a given output section and returns
1761 // its new file offset. The file offset must be the same with its
1762 // virtual address (modulo the page size) so that the loader can load
1763 // executables without any address adjustment.
1764 static uint64_t getFileAlignment(uint64_t Off, OutputSection *Cmd) {
1765   // If the section is not in a PT_LOAD, we just have to align it.
1766   if (!Cmd->PtLoad)
1767     return alignTo(Off, Cmd->Alignment);
1768
1769   OutputSection *First = Cmd->PtLoad->FirstSec;
1770   // The first section in a PT_LOAD has to have congruent offset and address
1771   // module the page size.
1772   if (Cmd == First)
1773     return alignTo(Off, std::max<uint64_t>(Cmd->Alignment, Config->MaxPageSize),
1774                    Cmd->Addr);
1775
1776   // If two sections share the same PT_LOAD the file offset is calculated
1777   // using this formula: Off2 = Off1 + (VA2 - VA1).
1778   return First->Offset + Cmd->Addr - First->Addr;
1779 }
1780
1781 static uint64_t setOffset(OutputSection *Cmd, uint64_t Off) {
1782   if (Cmd->Type == SHT_NOBITS) {
1783     Cmd->Offset = Off;
1784     return Off;
1785   }
1786
1787   Off = getFileAlignment(Off, Cmd);
1788   Cmd->Offset = Off;
1789   return Off + Cmd->Size;
1790 }
1791
1792 template <class ELFT> void Writer<ELFT>::assignFileOffsetsBinary() {
1793   uint64_t Off = 0;
1794   for (OutputSection *Sec : OutputSections)
1795     if (Sec->Flags & SHF_ALLOC)
1796       Off = setOffset(Sec, Off);
1797   FileSize = alignTo(Off, Config->Wordsize);
1798 }
1799
1800 // Assign file offsets to output sections.
1801 template <class ELFT> void Writer<ELFT>::assignFileOffsets() {
1802   uint64_t Off = 0;
1803   Off = setOffset(Out::ElfHeader, Off);
1804   Off = setOffset(Out::ProgramHeaders, Off);
1805
1806   PhdrEntry *LastRX = nullptr;
1807   for (PhdrEntry *P : Phdrs)
1808     if (P->p_type == PT_LOAD && (P->p_flags & PF_X))
1809       LastRX = P;
1810
1811   for (OutputSection *Sec : OutputSections) {
1812     Off = setOffset(Sec, Off);
1813     if (Script->HasSectionsCommand)
1814       continue;
1815     // If this is a last section of the last executable segment and that
1816     // segment is the last loadable segment, align the offset of the
1817     // following section to avoid loading non-segments parts of the file.
1818     if (LastRX && LastRX->LastSec == Sec)
1819       Off = alignTo(Off, Target->PageSize);
1820   }
1821
1822   SectionHeaderOff = alignTo(Off, Config->Wordsize);
1823   FileSize = SectionHeaderOff + (OutputSections.size() + 1) * sizeof(Elf_Shdr);
1824 }
1825
1826 // Finalize the program headers. We call this function after we assign
1827 // file offsets and VAs to all sections.
1828 template <class ELFT> void Writer<ELFT>::setPhdrs() {
1829   for (PhdrEntry *P : Phdrs) {
1830     OutputSection *First = P->FirstSec;
1831     OutputSection *Last = P->LastSec;
1832     if (First) {
1833       P->p_filesz = Last->Offset - First->Offset;
1834       if (Last->Type != SHT_NOBITS)
1835         P->p_filesz += Last->Size;
1836       P->p_memsz = Last->Addr + Last->Size - First->Addr;
1837       P->p_offset = First->Offset;
1838       P->p_vaddr = First->Addr;
1839       if (!P->HasLMA)
1840         P->p_paddr = First->getLMA();
1841     }
1842     if (P->p_type == PT_LOAD)
1843       P->p_align = std::max<uint64_t>(P->p_align, Config->MaxPageSize);
1844     else if (P->p_type == PT_GNU_RELRO) {
1845       P->p_align = 1;
1846       // The glibc dynamic loader rounds the size down, so we need to round up
1847       // to protect the last page. This is a no-op on FreeBSD which always
1848       // rounds up.
1849       P->p_memsz = alignTo(P->p_memsz, Target->PageSize);
1850     }
1851
1852     // The TLS pointer goes after PT_TLS. At least glibc will align it,
1853     // so round up the size to make sure the offsets are correct.
1854     if (P->p_type == PT_TLS) {
1855       Out::TlsPhdr = P;
1856       if (P->p_memsz)
1857         P->p_memsz = alignTo(P->p_memsz, P->p_align);
1858     }
1859   }
1860 }
1861
1862 // The entry point address is chosen in the following ways.
1863 //
1864 // 1. the '-e' entry command-line option;
1865 // 2. the ENTRY(symbol) command in a linker control script;
1866 // 3. the value of the symbol _start, if present;
1867 // 4. the number represented by the entry symbol, if it is a number;
1868 // 5. the address of the first byte of the .text section, if present;
1869 // 6. the address 0.
1870 template <class ELFT> uint64_t Writer<ELFT>::getEntryAddr() {
1871   // Case 1, 2 or 3
1872   if (Symbol *B = Symtab->find(Config->Entry))
1873     return B->getVA();
1874
1875   // Case 4
1876   uint64_t Addr;
1877   if (to_integer(Config->Entry, Addr))
1878     return Addr;
1879
1880   // Case 5
1881   if (OutputSection *Sec = findSection(".text")) {
1882     if (Config->WarnMissingEntry)
1883       warn("cannot find entry symbol " + Config->Entry + "; defaulting to 0x" +
1884            utohexstr(Sec->Addr));
1885     return Sec->Addr;
1886   }
1887
1888   // Case 6
1889   if (Config->WarnMissingEntry)
1890     warn("cannot find entry symbol " + Config->Entry +
1891          "; not setting start address");
1892   return 0;
1893 }
1894
1895 static uint16_t getELFType() {
1896   if (Config->Pic)
1897     return ET_DYN;
1898   if (Config->Relocatable)
1899     return ET_REL;
1900   return ET_EXEC;
1901 }
1902
1903 template <class ELFT> void Writer<ELFT>::writeHeader() {
1904   uint8_t *Buf = Buffer->getBufferStart();
1905   memcpy(Buf, "\177ELF", 4);
1906
1907   // Write the ELF header.
1908   auto *EHdr = reinterpret_cast<Elf_Ehdr *>(Buf);
1909   EHdr->e_ident[EI_CLASS] = Config->Is64 ? ELFCLASS64 : ELFCLASS32;
1910   EHdr->e_ident[EI_DATA] = Config->IsLE ? ELFDATA2LSB : ELFDATA2MSB;
1911   EHdr->e_ident[EI_VERSION] = EV_CURRENT;
1912   EHdr->e_ident[EI_OSABI] = Config->OSABI;
1913   EHdr->e_type = getELFType();
1914   EHdr->e_machine = Config->EMachine;
1915   EHdr->e_version = EV_CURRENT;
1916   EHdr->e_entry = getEntryAddr();
1917   EHdr->e_shoff = SectionHeaderOff;
1918   EHdr->e_flags = Config->EFlags;
1919   EHdr->e_ehsize = sizeof(Elf_Ehdr);
1920   EHdr->e_phnum = Phdrs.size();
1921   EHdr->e_shentsize = sizeof(Elf_Shdr);
1922   EHdr->e_shnum = OutputSections.size() + 1;
1923   EHdr->e_shstrndx = InX::ShStrTab->getParent()->SectionIndex;
1924
1925   if (!Config->Relocatable) {
1926     EHdr->e_phoff = sizeof(Elf_Ehdr);
1927     EHdr->e_phentsize = sizeof(Elf_Phdr);
1928   }
1929
1930   // Write the program header table.
1931   auto *HBuf = reinterpret_cast<Elf_Phdr *>(Buf + EHdr->e_phoff);
1932   for (PhdrEntry *P : Phdrs) {
1933     HBuf->p_type = P->p_type;
1934     HBuf->p_flags = P->p_flags;
1935     HBuf->p_offset = P->p_offset;
1936     HBuf->p_vaddr = P->p_vaddr;
1937     HBuf->p_paddr = P->p_paddr;
1938     HBuf->p_filesz = P->p_filesz;
1939     HBuf->p_memsz = P->p_memsz;
1940     HBuf->p_align = P->p_align;
1941     ++HBuf;
1942   }
1943
1944   // Write the section header table. Note that the first table entry is null.
1945   auto *SHdrs = reinterpret_cast<Elf_Shdr *>(Buf + EHdr->e_shoff);
1946   for (OutputSection *Sec : OutputSections)
1947     Sec->writeHeaderTo<ELFT>(++SHdrs);
1948 }
1949
1950 // Open a result file.
1951 template <class ELFT> void Writer<ELFT>::openFile() {
1952   if (!Config->Is64 && FileSize > UINT32_MAX) {
1953     error("output file too large: " + Twine(FileSize) + " bytes");
1954     return;
1955   }
1956
1957   unlinkAsync(Config->OutputFile);
1958   unsigned Flags = 0;
1959   if (!Config->Relocatable)
1960     Flags = FileOutputBuffer::F_executable;
1961   Expected<std::unique_ptr<FileOutputBuffer>> BufferOrErr =
1962       FileOutputBuffer::create(Config->OutputFile, FileSize, Flags);
1963
1964   if (!BufferOrErr)
1965     error("failed to open " + Config->OutputFile + ": " +
1966           llvm::toString(BufferOrErr.takeError()));
1967   else
1968     Buffer = std::move(*BufferOrErr);
1969 }
1970
1971 template <class ELFT> void Writer<ELFT>::writeSectionsBinary() {
1972   uint8_t *Buf = Buffer->getBufferStart();
1973   for (OutputSection *Sec : OutputSections)
1974     if (Sec->Flags & SHF_ALLOC)
1975       Sec->writeTo<ELFT>(Buf + Sec->Offset);
1976 }
1977
1978 static void fillTrap(uint8_t *I, uint8_t *End) {
1979   for (; I + 4 <= End; I += 4)
1980     memcpy(I, &Target->TrapInstr, 4);
1981 }
1982
1983 // Fill the last page of executable segments with trap instructions
1984 // instead of leaving them as zero. Even though it is not required by any
1985 // standard, it is in general a good thing to do for security reasons.
1986 //
1987 // We'll leave other pages in segments as-is because the rest will be
1988 // overwritten by output sections.
1989 template <class ELFT> void Writer<ELFT>::writeTrapInstr() {
1990   if (Script->HasSectionsCommand)
1991     return;
1992
1993   // Fill the last page.
1994   uint8_t *Buf = Buffer->getBufferStart();
1995   for (PhdrEntry *P : Phdrs)
1996     if (P->p_type == PT_LOAD && (P->p_flags & PF_X))
1997       fillTrap(Buf + alignDown(P->p_offset + P->p_filesz, Target->PageSize),
1998                Buf + alignTo(P->p_offset + P->p_filesz, Target->PageSize));
1999
2000   // Round up the file size of the last segment to the page boundary iff it is
2001   // an executable segment to ensure that other tools don't accidentally
2002   // trim the instruction padding (e.g. when stripping the file).
2003   PhdrEntry *Last = nullptr;
2004   for (PhdrEntry *P : Phdrs)
2005     if (P->p_type == PT_LOAD)
2006       Last = P;
2007
2008   if (Last && (Last->p_flags & PF_X))
2009     Last->p_memsz = Last->p_filesz = alignTo(Last->p_filesz, Target->PageSize);
2010 }
2011
2012 // Write section contents to a mmap'ed file.
2013 template <class ELFT> void Writer<ELFT>::writeSections() {
2014   uint8_t *Buf = Buffer->getBufferStart();
2015
2016   // PPC64 needs to process relocations in the .opd section
2017   // before processing relocations in code-containing sections.
2018   if (auto *OpdCmd = findSection(".opd")) {
2019     Out::Opd = OpdCmd;
2020     Out::OpdBuf = Buf + Out::Opd->Offset;
2021     OpdCmd->template writeTo<ELFT>(Buf + Out::Opd->Offset);
2022   }
2023
2024   OutputSection *EhFrameHdr = nullptr;
2025   if (InX::EhFrameHdr && !InX::EhFrameHdr->empty())
2026     EhFrameHdr = InX::EhFrameHdr->getParent();
2027
2028   // In -r or -emit-relocs mode, write the relocation sections first as in
2029   // ELf_Rel targets we might find out that we need to modify the relocated
2030   // section while doing it.
2031   for (OutputSection *Sec : OutputSections)
2032     if (Sec->Type == SHT_REL || Sec->Type == SHT_RELA)
2033       Sec->writeTo<ELFT>(Buf + Sec->Offset);
2034
2035   for (OutputSection *Sec : OutputSections)
2036     if (Sec != Out::Opd && Sec != EhFrameHdr && Sec->Type != SHT_REL &&
2037         Sec->Type != SHT_RELA)
2038       Sec->writeTo<ELFT>(Buf + Sec->Offset);
2039
2040   // The .eh_frame_hdr depends on .eh_frame section contents, therefore
2041   // it should be written after .eh_frame is written.
2042   if (EhFrameHdr)
2043     EhFrameHdr->writeTo<ELFT>(Buf + EhFrameHdr->Offset);
2044 }
2045
2046 template <class ELFT> void Writer<ELFT>::writeBuildId() {
2047   if (!InX::BuildId || !InX::BuildId->getParent())
2048     return;
2049
2050   // Compute a hash of all sections of the output file.
2051   uint8_t *Start = Buffer->getBufferStart();
2052   uint8_t *End = Start + FileSize;
2053   InX::BuildId->writeBuildId({Start, End});
2054 }
2055
2056 template void elf::writeResult<ELF32LE>();
2057 template void elf::writeResult<ELF32BE>();
2058 template void elf::writeResult<ELF64LE>();
2059 template void elf::writeResult<ELF64BE>();
2060
2061 template void elf::addReservedSymbols<ELF32LE>();
2062 template void elf::addReservedSymbols<ELF32BE>();
2063 template void elf::addReservedSymbols<ELF64LE>();
2064 template void elf::addReservedSymbols<ELF64BE>();