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