xref: /freebsd/contrib/llvm-project/lld/ELF/Writer.cpp (revision e6bfd18d21b225af6a0ed67ceeaf1293b7b9eba5)
1 //===- Writer.cpp ---------------------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #include "Writer.h"
10 #include "AArch64ErrataFix.h"
11 #include "ARMErrataFix.h"
12 #include "CallGraphSort.h"
13 #include "Config.h"
14 #include "InputFiles.h"
15 #include "LinkerScript.h"
16 #include "MapFile.h"
17 #include "OutputSections.h"
18 #include "Relocations.h"
19 #include "SymbolTable.h"
20 #include "Symbols.h"
21 #include "SyntheticSections.h"
22 #include "Target.h"
23 #include "lld/Common/Arrays.h"
24 #include "lld/Common/CommonLinkerContext.h"
25 #include "lld/Common/Filesystem.h"
26 #include "lld/Common/Strings.h"
27 #include "llvm/ADT/StringMap.h"
28 #include "llvm/Support/BLAKE3.h"
29 #include "llvm/Support/Parallel.h"
30 #include "llvm/Support/RandomNumberGenerator.h"
31 #include "llvm/Support/TimeProfiler.h"
32 #include "llvm/Support/xxhash.h"
33 #include <climits>
34 
35 #define DEBUG_TYPE "lld"
36 
37 using namespace llvm;
38 using namespace llvm::ELF;
39 using namespace llvm::object;
40 using namespace llvm::support;
41 using namespace llvm::support::endian;
42 using namespace lld;
43 using namespace lld::elf;
44 
45 namespace {
46 // The writer writes a SymbolTable result to a file.
47 template <class ELFT> class Writer {
48 public:
49   LLVM_ELF_IMPORT_TYPES_ELFT(ELFT)
50 
51   Writer() : buffer(errorHandler().outputBuffer) {}
52 
53   void run();
54 
55 private:
56   void copyLocalSymbols();
57   void addSectionSymbols();
58   void sortSections();
59   void resolveShfLinkOrder();
60   void finalizeAddressDependentContent();
61   void optimizeBasicBlockJumps();
62   void sortInputSections();
63   void finalizeSections();
64   void checkExecuteOnly();
65   void setReservedSymbolSections();
66 
67   SmallVector<PhdrEntry *, 0> createPhdrs(Partition &part);
68   void addPhdrForSection(Partition &part, unsigned shType, unsigned pType,
69                          unsigned pFlags);
70   void assignFileOffsets();
71   void assignFileOffsetsBinary();
72   void setPhdrs(Partition &part);
73   void checkSections();
74   void fixSectionAlignments();
75   void openFile();
76   void writeTrapInstr();
77   void writeHeader();
78   void writeSections();
79   void writeSectionsBinary();
80   void writeBuildId();
81 
82   std::unique_ptr<FileOutputBuffer> &buffer;
83 
84   void addRelIpltSymbols();
85   void addStartEndSymbols();
86   void addStartStopSymbols(OutputSection &osec);
87 
88   uint64_t fileSize;
89   uint64_t sectionHeaderOff;
90 };
91 } // anonymous namespace
92 
93 static bool needsInterpSection() {
94   return !config->relocatable && !config->shared &&
95          !config->dynamicLinker.empty() && script->needsInterpSection();
96 }
97 
98 template <class ELFT> void elf::writeResult() {
99   Writer<ELFT>().run();
100 }
101 
102 static void removeEmptyPTLoad(SmallVector<PhdrEntry *, 0> &phdrs) {
103   auto it = std::stable_partition(
104       phdrs.begin(), phdrs.end(), [&](const PhdrEntry *p) {
105         if (p->p_type != PT_LOAD)
106           return true;
107         if (!p->firstSec)
108           return false;
109         uint64_t size = p->lastSec->addr + p->lastSec->size - p->firstSec->addr;
110         return size != 0;
111       });
112 
113   // Clear OutputSection::ptLoad for sections contained in removed
114   // segments.
115   DenseSet<PhdrEntry *> removed(it, phdrs.end());
116   for (OutputSection *sec : outputSections)
117     if (removed.count(sec->ptLoad))
118       sec->ptLoad = nullptr;
119   phdrs.erase(it, phdrs.end());
120 }
121 
122 void elf::copySectionsIntoPartitions() {
123   SmallVector<InputSectionBase *, 0> newSections;
124   for (unsigned part = 2; part != partitions.size() + 1; ++part) {
125     for (InputSectionBase *s : inputSections) {
126       if (!(s->flags & SHF_ALLOC) || !s->isLive())
127         continue;
128       InputSectionBase *copy;
129       if (s->type == SHT_NOTE)
130         copy = make<InputSection>(cast<InputSection>(*s));
131       else if (auto *es = dyn_cast<EhInputSection>(s))
132         copy = make<EhInputSection>(*es);
133       else
134         continue;
135       copy->partition = part;
136       newSections.push_back(copy);
137     }
138   }
139 
140   inputSections.insert(inputSections.end(), newSections.begin(),
141                        newSections.end());
142 }
143 
144 void elf::combineEhSections() {
145   llvm::TimeTraceScope timeScope("Combine EH sections");
146   for (InputSectionBase *&s : inputSections) {
147     // Ignore dead sections and the partition end marker (.part.end),
148     // whose partition number is out of bounds.
149     if (!s->isLive() || s->partition == 255)
150       continue;
151 
152     Partition &part = s->getPartition();
153     if (auto *es = dyn_cast<EhInputSection>(s)) {
154       part.ehFrame->addSection(es);
155       s = nullptr;
156     } else if (s->kind() == SectionBase::Regular && part.armExidx &&
157                part.armExidx->addSection(cast<InputSection>(s))) {
158       s = nullptr;
159     }
160   }
161 
162   llvm::erase_value(inputSections, nullptr);
163 }
164 
165 static Defined *addOptionalRegular(StringRef name, SectionBase *sec,
166                                    uint64_t val, uint8_t stOther = STV_HIDDEN) {
167   Symbol *s = symtab->find(name);
168   if (!s || s->isDefined() || s->isCommon())
169     return nullptr;
170 
171   s->resolve(Defined{nullptr, StringRef(), STB_GLOBAL, stOther, STT_NOTYPE, val,
172                      /*size=*/0, sec});
173   s->isUsedInRegularObj = true;
174   return cast<Defined>(s);
175 }
176 
177 static Defined *addAbsolute(StringRef name) {
178   Symbol *sym = symtab->addSymbol(Defined{nullptr, name, STB_GLOBAL, STV_HIDDEN,
179                                           STT_NOTYPE, 0, 0, nullptr});
180   sym->isUsedInRegularObj = true;
181   return cast<Defined>(sym);
182 }
183 
184 // The linker is expected to define some symbols depending on
185 // the linking result. This function defines such symbols.
186 void elf::addReservedSymbols() {
187   if (config->emachine == EM_MIPS) {
188     // Define _gp for MIPS. st_value of _gp symbol will be updated by Writer
189     // so that it points to an absolute address which by default is relative
190     // to GOT. Default offset is 0x7ff0.
191     // See "Global Data Symbols" in Chapter 6 in the following document:
192     // ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf
193     ElfSym::mipsGp = addAbsolute("_gp");
194 
195     // On MIPS O32 ABI, _gp_disp is a magic symbol designates offset between
196     // start of function and 'gp' pointer into GOT.
197     if (symtab->find("_gp_disp"))
198       ElfSym::mipsGpDisp = addAbsolute("_gp_disp");
199 
200     // The __gnu_local_gp is a magic symbol equal to the current value of 'gp'
201     // pointer. This symbol is used in the code generated by .cpload pseudo-op
202     // in case of using -mno-shared option.
203     // https://sourceware.org/ml/binutils/2004-12/msg00094.html
204     if (symtab->find("__gnu_local_gp"))
205       ElfSym::mipsLocalGp = addAbsolute("__gnu_local_gp");
206   } else if (config->emachine == EM_PPC) {
207     // glibc *crt1.o has a undefined reference to _SDA_BASE_. Since we don't
208     // support Small Data Area, define it arbitrarily as 0.
209     addOptionalRegular("_SDA_BASE_", nullptr, 0, STV_HIDDEN);
210   } else if (config->emachine == EM_PPC64) {
211     addPPC64SaveRestore();
212   }
213 
214   // The Power Architecture 64-bit v2 ABI defines a TableOfContents (TOC) which
215   // combines the typical ELF GOT with the small data sections. It commonly
216   // includes .got .toc .sdata .sbss. The .TOC. symbol replaces both
217   // _GLOBAL_OFFSET_TABLE_ and _SDA_BASE_ from the 32-bit ABI. It is used to
218   // represent the TOC base which is offset by 0x8000 bytes from the start of
219   // the .got section.
220   // We do not allow _GLOBAL_OFFSET_TABLE_ to be defined by input objects as the
221   // correctness of some relocations depends on its value.
222   StringRef gotSymName =
223       (config->emachine == EM_PPC64) ? ".TOC." : "_GLOBAL_OFFSET_TABLE_";
224 
225   if (Symbol *s = symtab->find(gotSymName)) {
226     if (s->isDefined()) {
227       error(toString(s->file) + " cannot redefine linker defined symbol '" +
228             gotSymName + "'");
229       return;
230     }
231 
232     uint64_t gotOff = 0;
233     if (config->emachine == EM_PPC64)
234       gotOff = 0x8000;
235 
236     s->resolve(Defined{/*file=*/nullptr, StringRef(), STB_GLOBAL, STV_HIDDEN,
237                        STT_NOTYPE, gotOff, /*size=*/0, Out::elfHeader});
238     ElfSym::globalOffsetTable = cast<Defined>(s);
239   }
240 
241   // __ehdr_start is the location of ELF file headers. Note that we define
242   // this symbol unconditionally even when using a linker script, which
243   // differs from the behavior implemented by GNU linker which only define
244   // this symbol if ELF headers are in the memory mapped segment.
245   addOptionalRegular("__ehdr_start", Out::elfHeader, 0, STV_HIDDEN);
246 
247   // __executable_start is not documented, but the expectation of at
248   // least the Android libc is that it points to the ELF header.
249   addOptionalRegular("__executable_start", Out::elfHeader, 0, STV_HIDDEN);
250 
251   // __dso_handle symbol is passed to cxa_finalize as a marker to identify
252   // each DSO. The address of the symbol doesn't matter as long as they are
253   // different in different DSOs, so we chose the start address of the DSO.
254   addOptionalRegular("__dso_handle", Out::elfHeader, 0, STV_HIDDEN);
255 
256   // If linker script do layout we do not need to create any standard symbols.
257   if (script->hasSectionsCommand)
258     return;
259 
260   auto add = [](StringRef s, int64_t pos) {
261     return addOptionalRegular(s, Out::elfHeader, pos, STV_DEFAULT);
262   };
263 
264   ElfSym::bss = add("__bss_start", 0);
265   ElfSym::end1 = add("end", -1);
266   ElfSym::end2 = add("_end", -1);
267   ElfSym::etext1 = add("etext", -1);
268   ElfSym::etext2 = add("_etext", -1);
269   ElfSym::edata1 = add("edata", -1);
270   ElfSym::edata2 = add("_edata", -1);
271 }
272 
273 static OutputSection *findSection(StringRef name, unsigned partition = 1) {
274   for (SectionCommand *cmd : script->sectionCommands)
275     if (auto *osd = dyn_cast<OutputDesc>(cmd))
276       if (osd->osec.name == name && osd->osec.partition == partition)
277         return &osd->osec;
278   return nullptr;
279 }
280 
281 template <class ELFT> void elf::createSyntheticSections() {
282   // Initialize all pointers with NULL. This is needed because
283   // you can call lld::elf::main more than once as a library.
284   Out::tlsPhdr = nullptr;
285   Out::preinitArray = nullptr;
286   Out::initArray = nullptr;
287   Out::finiArray = nullptr;
288 
289   // Add the .interp section first because it is not a SyntheticSection.
290   // The removeUnusedSyntheticSections() function relies on the
291   // SyntheticSections coming last.
292   if (needsInterpSection()) {
293     for (size_t i = 1; i <= partitions.size(); ++i) {
294       InputSection *sec = createInterpSection();
295       sec->partition = i;
296       inputSections.push_back(sec);
297     }
298   }
299 
300   auto add = [](SyntheticSection &sec) { inputSections.push_back(&sec); };
301 
302   in.shStrTab = std::make_unique<StringTableSection>(".shstrtab", false);
303 
304   Out::programHeaders = make<OutputSection>("", 0, SHF_ALLOC);
305   Out::programHeaders->alignment = config->wordsize;
306 
307   if (config->strip != StripPolicy::All) {
308     in.strTab = std::make_unique<StringTableSection>(".strtab", false);
309     in.symTab = std::make_unique<SymbolTableSection<ELFT>>(*in.strTab);
310     in.symTabShndx = std::make_unique<SymtabShndxSection>();
311   }
312 
313   in.bss = std::make_unique<BssSection>(".bss", 0, 1);
314   add(*in.bss);
315 
316   // If there is a SECTIONS command and a .data.rel.ro section name use name
317   // .data.rel.ro.bss so that we match in the .data.rel.ro output section.
318   // This makes sure our relro is contiguous.
319   bool hasDataRelRo = script->hasSectionsCommand && findSection(".data.rel.ro");
320   in.bssRelRo = std::make_unique<BssSection>(
321       hasDataRelRo ? ".data.rel.ro.bss" : ".bss.rel.ro", 0, 1);
322   add(*in.bssRelRo);
323 
324   // Add MIPS-specific sections.
325   if (config->emachine == EM_MIPS) {
326     if (!config->shared && config->hasDynSymTab) {
327       in.mipsRldMap = std::make_unique<MipsRldMapSection>();
328       add(*in.mipsRldMap);
329     }
330     if ((in.mipsAbiFlags = MipsAbiFlagsSection<ELFT>::create()))
331       add(*in.mipsAbiFlags);
332     if ((in.mipsOptions = MipsOptionsSection<ELFT>::create()))
333       add(*in.mipsOptions);
334     if ((in.mipsReginfo = MipsReginfoSection<ELFT>::create()))
335       add(*in.mipsReginfo);
336   }
337 
338   StringRef relaDynName = config->isRela ? ".rela.dyn" : ".rel.dyn";
339 
340   for (Partition &part : partitions) {
341     auto add = [&](SyntheticSection &sec) {
342       sec.partition = part.getNumber();
343       inputSections.push_back(&sec);
344     };
345 
346     if (!part.name.empty()) {
347       part.elfHeader = std::make_unique<PartitionElfHeaderSection<ELFT>>();
348       part.elfHeader->name = part.name;
349       add(*part.elfHeader);
350 
351       part.programHeaders =
352           std::make_unique<PartitionProgramHeadersSection<ELFT>>();
353       add(*part.programHeaders);
354     }
355 
356     if (config->buildId != BuildIdKind::None) {
357       part.buildId = std::make_unique<BuildIdSection>();
358       add(*part.buildId);
359     }
360 
361     part.dynStrTab = std::make_unique<StringTableSection>(".dynstr", true);
362     part.dynSymTab =
363         std::make_unique<SymbolTableSection<ELFT>>(*part.dynStrTab);
364     part.dynamic = std::make_unique<DynamicSection<ELFT>>();
365 
366     if (config->emachine == EM_AARCH64 &&
367         config->androidMemtagMode != ELF::NT_MEMTAG_LEVEL_NONE) {
368       part.memtagAndroidNote = std::make_unique<MemtagAndroidNote>();
369       add(*part.memtagAndroidNote);
370     }
371 
372     if (config->androidPackDynRelocs)
373       part.relaDyn =
374           std::make_unique<AndroidPackedRelocationSection<ELFT>>(relaDynName);
375     else
376       part.relaDyn = std::make_unique<RelocationSection<ELFT>>(
377           relaDynName, config->zCombreloc);
378 
379     if (config->hasDynSymTab) {
380       add(*part.dynSymTab);
381 
382       part.verSym = std::make_unique<VersionTableSection>();
383       add(*part.verSym);
384 
385       if (!namedVersionDefs().empty()) {
386         part.verDef = std::make_unique<VersionDefinitionSection>();
387         add(*part.verDef);
388       }
389 
390       part.verNeed = std::make_unique<VersionNeedSection<ELFT>>();
391       add(*part.verNeed);
392 
393       if (config->gnuHash) {
394         part.gnuHashTab = std::make_unique<GnuHashTableSection>();
395         add(*part.gnuHashTab);
396       }
397 
398       if (config->sysvHash) {
399         part.hashTab = std::make_unique<HashTableSection>();
400         add(*part.hashTab);
401       }
402 
403       add(*part.dynamic);
404       add(*part.dynStrTab);
405       add(*part.relaDyn);
406     }
407 
408     if (config->relrPackDynRelocs) {
409       part.relrDyn = std::make_unique<RelrSection<ELFT>>();
410       add(*part.relrDyn);
411     }
412 
413     if (!config->relocatable) {
414       if (config->ehFrameHdr) {
415         part.ehFrameHdr = std::make_unique<EhFrameHeader>();
416         add(*part.ehFrameHdr);
417       }
418       part.ehFrame = std::make_unique<EhFrameSection>();
419       add(*part.ehFrame);
420     }
421 
422     if (config->emachine == EM_ARM && !config->relocatable) {
423       // The ARMExidxsyntheticsection replaces all the individual .ARM.exidx
424       // InputSections.
425       part.armExidx = std::make_unique<ARMExidxSyntheticSection>();
426       add(*part.armExidx);
427     }
428 
429     if (!config->packageMetadata.empty()) {
430       part.packageMetadataNote = std::make_unique<PackageMetadataNote>();
431       add(*part.packageMetadataNote);
432     }
433   }
434 
435   if (partitions.size() != 1) {
436     // Create the partition end marker. This needs to be in partition number 255
437     // so that it is sorted after all other partitions. It also has other
438     // special handling (see createPhdrs() and combineEhSections()).
439     in.partEnd =
440         std::make_unique<BssSection>(".part.end", config->maxPageSize, 1);
441     in.partEnd->partition = 255;
442     add(*in.partEnd);
443 
444     in.partIndex = std::make_unique<PartitionIndexSection>();
445     addOptionalRegular("__part_index_begin", in.partIndex.get(), 0);
446     addOptionalRegular("__part_index_end", in.partIndex.get(),
447                        in.partIndex->getSize());
448     add(*in.partIndex);
449   }
450 
451   // Add .got. MIPS' .got is so different from the other archs,
452   // it has its own class.
453   if (config->emachine == EM_MIPS) {
454     in.mipsGot = std::make_unique<MipsGotSection>();
455     add(*in.mipsGot);
456   } else {
457     in.got = std::make_unique<GotSection>();
458     add(*in.got);
459   }
460 
461   if (config->emachine == EM_PPC) {
462     in.ppc32Got2 = std::make_unique<PPC32Got2Section>();
463     add(*in.ppc32Got2);
464   }
465 
466   if (config->emachine == EM_PPC64) {
467     in.ppc64LongBranchTarget = std::make_unique<PPC64LongBranchTargetSection>();
468     add(*in.ppc64LongBranchTarget);
469   }
470 
471   in.gotPlt = std::make_unique<GotPltSection>();
472   add(*in.gotPlt);
473   in.igotPlt = std::make_unique<IgotPltSection>();
474   add(*in.igotPlt);
475 
476   // _GLOBAL_OFFSET_TABLE_ is defined relative to either .got.plt or .got. Treat
477   // it as a relocation and ensure the referenced section is created.
478   if (ElfSym::globalOffsetTable && config->emachine != EM_MIPS) {
479     if (target->gotBaseSymInGotPlt)
480       in.gotPlt->hasGotPltOffRel = true;
481     else
482       in.got->hasGotOffRel = true;
483   }
484 
485   if (config->gdbIndex)
486     add(*GdbIndexSection::create<ELFT>());
487 
488   // We always need to add rel[a].plt to output if it has entries.
489   // Even for static linking it can contain R_[*]_IRELATIVE relocations.
490   in.relaPlt = std::make_unique<RelocationSection<ELFT>>(
491       config->isRela ? ".rela.plt" : ".rel.plt", /*sort=*/false);
492   add(*in.relaPlt);
493 
494   // The relaIplt immediately follows .rel[a].dyn to ensure that the IRelative
495   // relocations are processed last by the dynamic loader. We cannot place the
496   // iplt section in .rel.dyn when Android relocation packing is enabled because
497   // that would cause a section type mismatch. However, because the Android
498   // dynamic loader reads .rel.plt after .rel.dyn, we can get the desired
499   // behaviour by placing the iplt section in .rel.plt.
500   in.relaIplt = std::make_unique<RelocationSection<ELFT>>(
501       config->androidPackDynRelocs ? in.relaPlt->name : relaDynName,
502       /*sort=*/false);
503   add(*in.relaIplt);
504 
505   if ((config->emachine == EM_386 || config->emachine == EM_X86_64) &&
506       (config->andFeatures & GNU_PROPERTY_X86_FEATURE_1_IBT)) {
507     in.ibtPlt = std::make_unique<IBTPltSection>();
508     add(*in.ibtPlt);
509   }
510 
511   if (config->emachine == EM_PPC)
512     in.plt = std::make_unique<PPC32GlinkSection>();
513   else
514     in.plt = std::make_unique<PltSection>();
515   add(*in.plt);
516   in.iplt = std::make_unique<IpltSection>();
517   add(*in.iplt);
518 
519   if (config->andFeatures)
520     add(*make<GnuPropertySection>());
521 
522   // .note.GNU-stack is always added when we are creating a re-linkable
523   // object file. Other linkers are using the presence of this marker
524   // section to control the executable-ness of the stack area, but that
525   // is irrelevant these days. Stack area should always be non-executable
526   // by default. So we emit this section unconditionally.
527   if (config->relocatable)
528     add(*make<GnuStackSection>());
529 
530   if (in.symTab)
531     add(*in.symTab);
532   if (in.symTabShndx)
533     add(*in.symTabShndx);
534   add(*in.shStrTab);
535   if (in.strTab)
536     add(*in.strTab);
537 }
538 
539 // The main function of the writer.
540 template <class ELFT> void Writer<ELFT>::run() {
541   copyLocalSymbols();
542 
543   if (config->copyRelocs)
544     addSectionSymbols();
545 
546   // Now that we have a complete set of output sections. This function
547   // completes section contents. For example, we need to add strings
548   // to the string table, and add entries to .got and .plt.
549   // finalizeSections does that.
550   finalizeSections();
551   checkExecuteOnly();
552 
553   // If --compressed-debug-sections is specified, compress .debug_* sections.
554   // Do it right now because it changes the size of output sections.
555   for (OutputSection *sec : outputSections)
556     sec->maybeCompress<ELFT>();
557 
558   if (script->hasSectionsCommand)
559     script->allocateHeaders(mainPart->phdrs);
560 
561   // Remove empty PT_LOAD to avoid causing the dynamic linker to try to mmap a
562   // 0 sized region. This has to be done late since only after assignAddresses
563   // we know the size of the sections.
564   for (Partition &part : partitions)
565     removeEmptyPTLoad(part.phdrs);
566 
567   if (!config->oFormatBinary)
568     assignFileOffsets();
569   else
570     assignFileOffsetsBinary();
571 
572   for (Partition &part : partitions)
573     setPhdrs(part);
574 
575   // Handle --print-map(-M)/--Map and --cref. Dump them before checkSections()
576   // because the files may be useful in case checkSections() or openFile()
577   // fails, for example, due to an erroneous file size.
578   writeMapAndCref();
579 
580   if (config->checkSections)
581     checkSections();
582 
583   // It does not make sense try to open the file if we have error already.
584   if (errorCount())
585     return;
586 
587   {
588     llvm::TimeTraceScope timeScope("Write output file");
589     // Write the result down to a file.
590     openFile();
591     if (errorCount())
592       return;
593 
594     if (!config->oFormatBinary) {
595       if (config->zSeparate != SeparateSegmentKind::None)
596         writeTrapInstr();
597       writeHeader();
598       writeSections();
599     } else {
600       writeSectionsBinary();
601     }
602 
603     // Backfill .note.gnu.build-id section content. This is done at last
604     // because the content is usually a hash value of the entire output file.
605     writeBuildId();
606     if (errorCount())
607       return;
608 
609     if (auto e = buffer->commit())
610       error("failed to write to the output file: " + toString(std::move(e)));
611   }
612 }
613 
614 template <class ELFT, class RelTy>
615 static void markUsedLocalSymbolsImpl(ObjFile<ELFT> *file,
616                                      llvm::ArrayRef<RelTy> rels) {
617   for (const RelTy &rel : rels) {
618     Symbol &sym = file->getRelocTargetSym(rel);
619     if (sym.isLocal())
620       sym.used = true;
621   }
622 }
623 
624 // The function ensures that the "used" field of local symbols reflects the fact
625 // that the symbol is used in a relocation from a live section.
626 template <class ELFT> static void markUsedLocalSymbols() {
627   // With --gc-sections, the field is already filled.
628   // See MarkLive<ELFT>::resolveReloc().
629   if (config->gcSections)
630     return;
631   for (ELFFileBase *file : ctx->objectFiles) {
632     ObjFile<ELFT> *f = cast<ObjFile<ELFT>>(file);
633     for (InputSectionBase *s : f->getSections()) {
634       InputSection *isec = dyn_cast_or_null<InputSection>(s);
635       if (!isec)
636         continue;
637       if (isec->type == SHT_REL)
638         markUsedLocalSymbolsImpl(f, isec->getDataAs<typename ELFT::Rel>());
639       else if (isec->type == SHT_RELA)
640         markUsedLocalSymbolsImpl(f, isec->getDataAs<typename ELFT::Rela>());
641     }
642   }
643 }
644 
645 static bool shouldKeepInSymtab(const Defined &sym) {
646   if (sym.isSection())
647     return false;
648 
649   // If --emit-reloc or -r is given, preserve symbols referenced by relocations
650   // from live sections.
651   if (sym.used && config->copyRelocs)
652     return true;
653 
654   // Exclude local symbols pointing to .ARM.exidx sections.
655   // They are probably mapping symbols "$d", which are optional for these
656   // sections. After merging the .ARM.exidx sections, some of these symbols
657   // may become dangling. The easiest way to avoid the issue is not to add
658   // them to the symbol table from the beginning.
659   if (config->emachine == EM_ARM && sym.section &&
660       sym.section->type == SHT_ARM_EXIDX)
661     return false;
662 
663   if (config->discard == DiscardPolicy::None)
664     return true;
665   if (config->discard == DiscardPolicy::All)
666     return false;
667 
668   // In ELF assembly .L symbols are normally discarded by the assembler.
669   // If the assembler fails to do so, the linker discards them if
670   // * --discard-locals is used.
671   // * The symbol is in a SHF_MERGE section, which is normally the reason for
672   //   the assembler keeping the .L symbol.
673   if (sym.getName().startswith(".L") &&
674       (config->discard == DiscardPolicy::Locals ||
675        (sym.section && (sym.section->flags & SHF_MERGE))))
676     return false;
677   return true;
678 }
679 
680 static bool includeInSymtab(const Symbol &b) {
681   if (auto *d = dyn_cast<Defined>(&b)) {
682     // Always include absolute symbols.
683     SectionBase *sec = d->section;
684     if (!sec)
685       return true;
686 
687     if (auto *s = dyn_cast<MergeInputSection>(sec))
688       return s->getSectionPiece(d->value).live;
689     return sec->isLive();
690   }
691   return b.used || !config->gcSections;
692 }
693 
694 // Local symbols are not in the linker's symbol table. This function scans
695 // each object file's symbol table to copy local symbols to the output.
696 template <class ELFT> void Writer<ELFT>::copyLocalSymbols() {
697   if (!in.symTab)
698     return;
699   llvm::TimeTraceScope timeScope("Add local symbols");
700   if (config->copyRelocs && config->discard != DiscardPolicy::None)
701     markUsedLocalSymbols<ELFT>();
702   for (ELFFileBase *file : ctx->objectFiles) {
703     for (Symbol *b : file->getLocalSymbols()) {
704       assert(b->isLocal() && "should have been caught in initializeSymbols()");
705       auto *dr = dyn_cast<Defined>(b);
706 
707       // No reason to keep local undefined symbol in symtab.
708       if (!dr)
709         continue;
710       if (includeInSymtab(*b) && shouldKeepInSymtab(*dr))
711         in.symTab->addSymbol(b);
712     }
713   }
714 }
715 
716 // Create a section symbol for each output section so that we can represent
717 // relocations that point to the section. If we know that no relocation is
718 // referring to a section (that happens if the section is a synthetic one), we
719 // don't create a section symbol for that section.
720 template <class ELFT> void Writer<ELFT>::addSectionSymbols() {
721   for (SectionCommand *cmd : script->sectionCommands) {
722     auto *osd = dyn_cast<OutputDesc>(cmd);
723     if (!osd)
724       continue;
725     OutputSection &osec = osd->osec;
726     InputSectionBase *isec = nullptr;
727     // Iterate over all input sections and add a STT_SECTION symbol if any input
728     // section may be a relocation target.
729     for (SectionCommand *cmd : osec.commands) {
730       auto *isd = dyn_cast<InputSectionDescription>(cmd);
731       if (!isd)
732         continue;
733       for (InputSectionBase *s : isd->sections) {
734         // Relocations are not using REL[A] section symbols.
735         if (s->type == SHT_REL || s->type == SHT_RELA)
736           continue;
737 
738         // Unlike other synthetic sections, mergeable output sections contain
739         // data copied from input sections, and there may be a relocation
740         // pointing to its contents if -r or --emit-reloc is given.
741         if (isa<SyntheticSection>(s) && !(s->flags & SHF_MERGE))
742           continue;
743 
744         isec = s;
745         break;
746       }
747     }
748     if (!isec)
749       continue;
750 
751     // Set the symbol to be relative to the output section so that its st_value
752     // equals the output section address. Note, there may be a gap between the
753     // start of the output section and isec.
754     in.symTab->addSymbol(makeDefined(isec->file, "", STB_LOCAL, /*stOther=*/0,
755                                      STT_SECTION,
756                                      /*value=*/0, /*size=*/0, &osec));
757   }
758 }
759 
760 // Today's loaders have a feature to make segments read-only after
761 // processing dynamic relocations to enhance security. PT_GNU_RELRO
762 // is defined for that.
763 //
764 // This function returns true if a section needs to be put into a
765 // PT_GNU_RELRO segment.
766 static bool isRelroSection(const OutputSection *sec) {
767   if (!config->zRelro)
768     return false;
769   if (sec->relro)
770     return true;
771 
772   uint64_t flags = sec->flags;
773 
774   // Non-allocatable or non-writable sections don't need RELRO because
775   // they are not writable or not even mapped to memory in the first place.
776   // RELRO is for sections that are essentially read-only but need to
777   // be writable only at process startup to allow dynamic linker to
778   // apply relocations.
779   if (!(flags & SHF_ALLOC) || !(flags & SHF_WRITE))
780     return false;
781 
782   // Once initialized, TLS data segments are used as data templates
783   // for a thread-local storage. For each new thread, runtime
784   // allocates memory for a TLS and copy templates there. No thread
785   // are supposed to use templates directly. Thus, it can be in RELRO.
786   if (flags & SHF_TLS)
787     return true;
788 
789   // .init_array, .preinit_array and .fini_array contain pointers to
790   // functions that are executed on process startup or exit. These
791   // pointers are set by the static linker, and they are not expected
792   // to change at runtime. But if you are an attacker, you could do
793   // interesting things by manipulating pointers in .fini_array, for
794   // example. So they are put into RELRO.
795   uint32_t type = sec->type;
796   if (type == SHT_INIT_ARRAY || type == SHT_FINI_ARRAY ||
797       type == SHT_PREINIT_ARRAY)
798     return true;
799 
800   // .got contains pointers to external symbols. They are resolved by
801   // the dynamic linker when a module is loaded into memory, and after
802   // that they are not expected to change. So, it can be in RELRO.
803   if (in.got && sec == in.got->getParent())
804     return true;
805 
806   // .toc is a GOT-ish section for PowerPC64. Their contents are accessed
807   // through r2 register, which is reserved for that purpose. Since r2 is used
808   // for accessing .got as well, .got and .toc need to be close enough in the
809   // virtual address space. Usually, .toc comes just after .got. Since we place
810   // .got into RELRO, .toc needs to be placed into RELRO too.
811   if (sec->name.equals(".toc"))
812     return true;
813 
814   // .got.plt contains pointers to external function symbols. They are
815   // by default resolved lazily, so we usually cannot put it into RELRO.
816   // However, if "-z now" is given, the lazy symbol resolution is
817   // disabled, which enables us to put it into RELRO.
818   if (sec == in.gotPlt->getParent())
819     return config->zNow;
820 
821   // .dynamic section contains data for the dynamic linker, and
822   // there's no need to write to it at runtime, so it's better to put
823   // it into RELRO.
824   if (sec->name == ".dynamic")
825     return true;
826 
827   // Sections with some special names are put into RELRO. This is a
828   // bit unfortunate because section names shouldn't be significant in
829   // ELF in spirit. But in reality many linker features depend on
830   // magic section names.
831   StringRef s = sec->name;
832   return s == ".data.rel.ro" || s == ".bss.rel.ro" || s == ".ctors" ||
833          s == ".dtors" || s == ".jcr" || s == ".eh_frame" ||
834          s == ".fini_array" || s == ".init_array" ||
835          s == ".openbsd.randomdata" || s == ".preinit_array";
836 }
837 
838 // We compute a rank for each section. The rank indicates where the
839 // section should be placed in the file.  Instead of using simple
840 // numbers (0,1,2...), we use a series of flags. One for each decision
841 // point when placing the section.
842 // Using flags has two key properties:
843 // * It is easy to check if a give branch was taken.
844 // * It is easy two see how similar two ranks are (see getRankProximity).
845 enum RankFlags {
846   RF_NOT_ADDR_SET = 1 << 27,
847   RF_NOT_ALLOC = 1 << 26,
848   RF_PARTITION = 1 << 18, // Partition number (8 bits)
849   RF_NOT_PART_EHDR = 1 << 17,
850   RF_NOT_PART_PHDR = 1 << 16,
851   RF_NOT_INTERP = 1 << 15,
852   RF_NOT_NOTE = 1 << 14,
853   RF_WRITE = 1 << 13,
854   RF_EXEC_WRITE = 1 << 12,
855   RF_EXEC = 1 << 11,
856   RF_RODATA = 1 << 10,
857   RF_NOT_RELRO = 1 << 9,
858   RF_NOT_TLS = 1 << 8,
859   RF_BSS = 1 << 7,
860   RF_PPC_NOT_TOCBSS = 1 << 6,
861   RF_PPC_TOCL = 1 << 5,
862   RF_PPC_TOC = 1 << 4,
863   RF_PPC_GOT = 1 << 3,
864   RF_PPC_BRANCH_LT = 1 << 2,
865   RF_MIPS_GPREL = 1 << 1,
866   RF_MIPS_NOT_GOT = 1 << 0
867 };
868 
869 static unsigned getSectionRank(const OutputSection &osec) {
870   unsigned rank = osec.partition * RF_PARTITION;
871 
872   // We want to put section specified by -T option first, so we
873   // can start assigning VA starting from them later.
874   if (config->sectionStartMap.count(osec.name))
875     return rank;
876   rank |= RF_NOT_ADDR_SET;
877 
878   // Allocatable sections go first to reduce the total PT_LOAD size and
879   // so debug info doesn't change addresses in actual code.
880   if (!(osec.flags & SHF_ALLOC))
881     return rank | RF_NOT_ALLOC;
882 
883   if (osec.type == SHT_LLVM_PART_EHDR)
884     return rank;
885   rank |= RF_NOT_PART_EHDR;
886 
887   if (osec.type == SHT_LLVM_PART_PHDR)
888     return rank;
889   rank |= RF_NOT_PART_PHDR;
890 
891   // Put .interp first because some loaders want to see that section
892   // on the first page of the executable file when loaded into memory.
893   if (osec.name == ".interp")
894     return rank;
895   rank |= RF_NOT_INTERP;
896 
897   // Put .note sections (which make up one PT_NOTE) at the beginning so that
898   // they are likely to be included in a core file even if core file size is
899   // limited. In particular, we want a .note.gnu.build-id and a .note.tag to be
900   // included in a core to match core files with executables.
901   if (osec.type == SHT_NOTE)
902     return rank;
903   rank |= RF_NOT_NOTE;
904 
905   // Sort sections based on their access permission in the following
906   // order: R, RX, RWX, RW.  This order is based on the following
907   // considerations:
908   // * Read-only sections come first such that they go in the
909   //   PT_LOAD covering the program headers at the start of the file.
910   // * Read-only, executable sections come next.
911   // * Writable, executable sections follow such that .plt on
912   //   architectures where it needs to be writable will be placed
913   //   between .text and .data.
914   // * Writable sections come last, such that .bss lands at the very
915   //   end of the last PT_LOAD.
916   bool isExec = osec.flags & SHF_EXECINSTR;
917   bool isWrite = osec.flags & SHF_WRITE;
918 
919   if (isExec) {
920     if (isWrite)
921       rank |= RF_EXEC_WRITE;
922     else
923       rank |= RF_EXEC;
924   } else if (isWrite) {
925     rank |= RF_WRITE;
926   } else if (osec.type == SHT_PROGBITS) {
927     // Make non-executable and non-writable PROGBITS sections (e.g .rodata
928     // .eh_frame) closer to .text. They likely contain PC or GOT relative
929     // relocations and there could be relocation overflow if other huge sections
930     // (.dynstr .dynsym) were placed in between.
931     rank |= RF_RODATA;
932   }
933 
934   // Place RelRo sections first. After considering SHT_NOBITS below, the
935   // ordering is PT_LOAD(PT_GNU_RELRO(.data.rel.ro .bss.rel.ro) | .data .bss),
936   // where | marks where page alignment happens. An alternative ordering is
937   // PT_LOAD(.data | PT_GNU_RELRO( .data.rel.ro .bss.rel.ro) | .bss), but it may
938   // waste more bytes due to 2 alignment places.
939   if (!isRelroSection(&osec))
940     rank |= RF_NOT_RELRO;
941 
942   // If we got here we know that both A and B are in the same PT_LOAD.
943 
944   // The TLS initialization block needs to be a single contiguous block in a R/W
945   // PT_LOAD, so stick TLS sections directly before the other RelRo R/W
946   // sections. Since p_filesz can be less than p_memsz, place NOBITS sections
947   // after PROGBITS.
948   if (!(osec.flags & SHF_TLS))
949     rank |= RF_NOT_TLS;
950 
951   // Within TLS sections, or within other RelRo sections, or within non-RelRo
952   // sections, place non-NOBITS sections first.
953   if (osec.type == SHT_NOBITS)
954     rank |= RF_BSS;
955 
956   // Some architectures have additional ordering restrictions for sections
957   // within the same PT_LOAD.
958   if (config->emachine == EM_PPC64) {
959     // PPC64 has a number of special SHT_PROGBITS+SHF_ALLOC+SHF_WRITE sections
960     // that we would like to make sure appear is a specific order to maximize
961     // their coverage by a single signed 16-bit offset from the TOC base
962     // pointer. Conversely, the special .tocbss section should be first among
963     // all SHT_NOBITS sections. This will put it next to the loaded special
964     // PPC64 sections (and, thus, within reach of the TOC base pointer).
965     StringRef name = osec.name;
966     if (name != ".tocbss")
967       rank |= RF_PPC_NOT_TOCBSS;
968 
969     if (name == ".toc1")
970       rank |= RF_PPC_TOCL;
971 
972     if (name == ".toc")
973       rank |= RF_PPC_TOC;
974 
975     if (name == ".got")
976       rank |= RF_PPC_GOT;
977 
978     if (name == ".branch_lt")
979       rank |= RF_PPC_BRANCH_LT;
980   }
981 
982   if (config->emachine == EM_MIPS) {
983     // All sections with SHF_MIPS_GPREL flag should be grouped together
984     // because data in these sections is addressable with a gp relative address.
985     if (osec.flags & SHF_MIPS_GPREL)
986       rank |= RF_MIPS_GPREL;
987 
988     if (osec.name != ".got")
989       rank |= RF_MIPS_NOT_GOT;
990   }
991 
992   return rank;
993 }
994 
995 static bool compareSections(const SectionCommand *aCmd,
996                             const SectionCommand *bCmd) {
997   const OutputSection *a = &cast<OutputDesc>(aCmd)->osec;
998   const OutputSection *b = &cast<OutputDesc>(bCmd)->osec;
999 
1000   if (a->sortRank != b->sortRank)
1001     return a->sortRank < b->sortRank;
1002 
1003   if (!(a->sortRank & RF_NOT_ADDR_SET))
1004     return config->sectionStartMap.lookup(a->name) <
1005            config->sectionStartMap.lookup(b->name);
1006   return false;
1007 }
1008 
1009 void PhdrEntry::add(OutputSection *sec) {
1010   lastSec = sec;
1011   if (!firstSec)
1012     firstSec = sec;
1013   p_align = std::max(p_align, sec->alignment);
1014   if (p_type == PT_LOAD)
1015     sec->ptLoad = this;
1016 }
1017 
1018 // The beginning and the ending of .rel[a].plt section are marked
1019 // with __rel[a]_iplt_{start,end} symbols if it is a statically linked
1020 // executable. The runtime needs these symbols in order to resolve
1021 // all IRELATIVE relocs on startup. For dynamic executables, we don't
1022 // need these symbols, since IRELATIVE relocs are resolved through GOT
1023 // and PLT. For details, see http://www.airs.com/blog/archives/403.
1024 template <class ELFT> void Writer<ELFT>::addRelIpltSymbols() {
1025   if (config->relocatable || config->isPic)
1026     return;
1027 
1028   // By default, __rela_iplt_{start,end} belong to a dummy section 0
1029   // because .rela.plt might be empty and thus removed from output.
1030   // We'll override Out::elfHeader with In.relaIplt later when we are
1031   // sure that .rela.plt exists in output.
1032   ElfSym::relaIpltStart = addOptionalRegular(
1033       config->isRela ? "__rela_iplt_start" : "__rel_iplt_start",
1034       Out::elfHeader, 0, STV_HIDDEN);
1035 
1036   ElfSym::relaIpltEnd = addOptionalRegular(
1037       config->isRela ? "__rela_iplt_end" : "__rel_iplt_end",
1038       Out::elfHeader, 0, STV_HIDDEN);
1039 }
1040 
1041 // This function generates assignments for predefined symbols (e.g. _end or
1042 // _etext) and inserts them into the commands sequence to be processed at the
1043 // appropriate time. This ensures that the value is going to be correct by the
1044 // time any references to these symbols are processed and is equivalent to
1045 // defining these symbols explicitly in the linker script.
1046 template <class ELFT> void Writer<ELFT>::setReservedSymbolSections() {
1047   if (ElfSym::globalOffsetTable) {
1048     // The _GLOBAL_OFFSET_TABLE_ symbol is defined by target convention usually
1049     // to the start of the .got or .got.plt section.
1050     InputSection *sec = in.gotPlt.get();
1051     if (!target->gotBaseSymInGotPlt)
1052       sec = in.mipsGot.get() ? cast<InputSection>(in.mipsGot.get())
1053                              : cast<InputSection>(in.got.get());
1054     ElfSym::globalOffsetTable->section = sec;
1055   }
1056 
1057   // .rela_iplt_{start,end} mark the start and the end of in.relaIplt.
1058   if (ElfSym::relaIpltStart && in.relaIplt->isNeeded()) {
1059     ElfSym::relaIpltStart->section = in.relaIplt.get();
1060     ElfSym::relaIpltEnd->section = in.relaIplt.get();
1061     ElfSym::relaIpltEnd->value = in.relaIplt->getSize();
1062   }
1063 
1064   PhdrEntry *last = nullptr;
1065   PhdrEntry *lastRO = nullptr;
1066 
1067   for (Partition &part : partitions) {
1068     for (PhdrEntry *p : part.phdrs) {
1069       if (p->p_type != PT_LOAD)
1070         continue;
1071       last = p;
1072       if (!(p->p_flags & PF_W))
1073         lastRO = p;
1074     }
1075   }
1076 
1077   if (lastRO) {
1078     // _etext is the first location after the last read-only loadable segment.
1079     if (ElfSym::etext1)
1080       ElfSym::etext1->section = lastRO->lastSec;
1081     if (ElfSym::etext2)
1082       ElfSym::etext2->section = lastRO->lastSec;
1083   }
1084 
1085   if (last) {
1086     // _edata points to the end of the last mapped initialized section.
1087     OutputSection *edata = nullptr;
1088     for (OutputSection *os : outputSections) {
1089       if (os->type != SHT_NOBITS)
1090         edata = os;
1091       if (os == last->lastSec)
1092         break;
1093     }
1094 
1095     if (ElfSym::edata1)
1096       ElfSym::edata1->section = edata;
1097     if (ElfSym::edata2)
1098       ElfSym::edata2->section = edata;
1099 
1100     // _end is the first location after the uninitialized data region.
1101     if (ElfSym::end1)
1102       ElfSym::end1->section = last->lastSec;
1103     if (ElfSym::end2)
1104       ElfSym::end2->section = last->lastSec;
1105   }
1106 
1107   if (ElfSym::bss)
1108     ElfSym::bss->section = findSection(".bss");
1109 
1110   // Setup MIPS _gp_disp/__gnu_local_gp symbols which should
1111   // be equal to the _gp symbol's value.
1112   if (ElfSym::mipsGp) {
1113     // Find GP-relative section with the lowest address
1114     // and use this address to calculate default _gp value.
1115     for (OutputSection *os : outputSections) {
1116       if (os->flags & SHF_MIPS_GPREL) {
1117         ElfSym::mipsGp->section = os;
1118         ElfSym::mipsGp->value = 0x7ff0;
1119         break;
1120       }
1121     }
1122   }
1123 }
1124 
1125 // We want to find how similar two ranks are.
1126 // The more branches in getSectionRank that match, the more similar they are.
1127 // Since each branch corresponds to a bit flag, we can just use
1128 // countLeadingZeros.
1129 static int getRankProximityAux(const OutputSection &a, const OutputSection &b) {
1130   return countLeadingZeros(a.sortRank ^ b.sortRank);
1131 }
1132 
1133 static int getRankProximity(OutputSection *a, SectionCommand *b) {
1134   auto *osd = dyn_cast<OutputDesc>(b);
1135   return (osd && osd->osec.hasInputSections)
1136              ? getRankProximityAux(*a, osd->osec)
1137              : -1;
1138 }
1139 
1140 // When placing orphan sections, we want to place them after symbol assignments
1141 // so that an orphan after
1142 //   begin_foo = .;
1143 //   foo : { *(foo) }
1144 //   end_foo = .;
1145 // doesn't break the intended meaning of the begin/end symbols.
1146 // We don't want to go over sections since findOrphanPos is the
1147 // one in charge of deciding the order of the sections.
1148 // We don't want to go over changes to '.', since doing so in
1149 //  rx_sec : { *(rx_sec) }
1150 //  . = ALIGN(0x1000);
1151 //  /* The RW PT_LOAD starts here*/
1152 //  rw_sec : { *(rw_sec) }
1153 // would mean that the RW PT_LOAD would become unaligned.
1154 static bool shouldSkip(SectionCommand *cmd) {
1155   if (auto *assign = dyn_cast<SymbolAssignment>(cmd))
1156     return assign->name != ".";
1157   return false;
1158 }
1159 
1160 // We want to place orphan sections so that they share as much
1161 // characteristics with their neighbors as possible. For example, if
1162 // both are rw, or both are tls.
1163 static SmallVectorImpl<SectionCommand *>::iterator
1164 findOrphanPos(SmallVectorImpl<SectionCommand *>::iterator b,
1165               SmallVectorImpl<SectionCommand *>::iterator e) {
1166   OutputSection *sec = &cast<OutputDesc>(*e)->osec;
1167 
1168   // Find the first element that has as close a rank as possible.
1169   auto i = std::max_element(b, e, [=](SectionCommand *a, SectionCommand *b) {
1170     return getRankProximity(sec, a) < getRankProximity(sec, b);
1171   });
1172   if (i == e)
1173     return e;
1174   if (!isa<OutputDesc>(*i))
1175     return e;
1176   auto foundSec = &cast<OutputDesc>(*i)->osec;
1177 
1178   // Consider all existing sections with the same proximity.
1179   int proximity = getRankProximity(sec, *i);
1180   unsigned sortRank = sec->sortRank;
1181   if (script->hasPhdrsCommands() || !script->memoryRegions.empty())
1182     // Prevent the orphan section to be placed before the found section. If
1183     // custom program headers are defined, that helps to avoid adding it to a
1184     // previous segment and changing flags of that segment, for example, making
1185     // a read-only segment writable. If memory regions are defined, an orphan
1186     // section should continue the same region as the found section to better
1187     // resemble the behavior of GNU ld.
1188     sortRank = std::max(sortRank, foundSec->sortRank);
1189   for (; i != e; ++i) {
1190     auto *curSecDesc = dyn_cast<OutputDesc>(*i);
1191     if (!curSecDesc || !curSecDesc->osec.hasInputSections)
1192       continue;
1193     if (getRankProximity(sec, curSecDesc) != proximity ||
1194         sortRank < curSecDesc->osec.sortRank)
1195       break;
1196   }
1197 
1198   auto isOutputSecWithInputSections = [](SectionCommand *cmd) {
1199     auto *osd = dyn_cast<OutputDesc>(cmd);
1200     return osd && osd->osec.hasInputSections;
1201   };
1202   auto j =
1203       std::find_if(std::make_reverse_iterator(i), std::make_reverse_iterator(b),
1204                    isOutputSecWithInputSections);
1205   i = j.base();
1206 
1207   // As a special case, if the orphan section is the last section, put
1208   // it at the very end, past any other commands.
1209   // This matches bfd's behavior and is convenient when the linker script fully
1210   // specifies the start of the file, but doesn't care about the end (the non
1211   // alloc sections for example).
1212   auto nextSec = std::find_if(i, e, isOutputSecWithInputSections);
1213   if (nextSec == e)
1214     return e;
1215 
1216   while (i != e && shouldSkip(*i))
1217     ++i;
1218   return i;
1219 }
1220 
1221 // Adds random priorities to sections not already in the map.
1222 static void maybeShuffle(DenseMap<const InputSectionBase *, int> &order) {
1223   if (config->shuffleSections.empty())
1224     return;
1225 
1226   SmallVector<InputSectionBase *, 0> matched, sections = inputSections;
1227   matched.reserve(sections.size());
1228   for (const auto &patAndSeed : config->shuffleSections) {
1229     matched.clear();
1230     for (InputSectionBase *sec : sections)
1231       if (patAndSeed.first.match(sec->name))
1232         matched.push_back(sec);
1233     const uint32_t seed = patAndSeed.second;
1234     if (seed == UINT32_MAX) {
1235       // If --shuffle-sections <section-glob>=-1, reverse the section order. The
1236       // section order is stable even if the number of sections changes. This is
1237       // useful to catch issues like static initialization order fiasco
1238       // reliably.
1239       std::reverse(matched.begin(), matched.end());
1240     } else {
1241       std::mt19937 g(seed ? seed : std::random_device()());
1242       llvm::shuffle(matched.begin(), matched.end(), g);
1243     }
1244     size_t i = 0;
1245     for (InputSectionBase *&sec : sections)
1246       if (patAndSeed.first.match(sec->name))
1247         sec = matched[i++];
1248   }
1249 
1250   // Existing priorities are < 0, so use priorities >= 0 for the missing
1251   // sections.
1252   int prio = 0;
1253   for (InputSectionBase *sec : sections) {
1254     if (order.try_emplace(sec, prio).second)
1255       ++prio;
1256   }
1257 }
1258 
1259 // Builds section order for handling --symbol-ordering-file.
1260 static DenseMap<const InputSectionBase *, int> buildSectionOrder() {
1261   DenseMap<const InputSectionBase *, int> sectionOrder;
1262   // Use the rarely used option --call-graph-ordering-file to sort sections.
1263   if (!config->callGraphProfile.empty())
1264     return computeCallGraphProfileOrder();
1265 
1266   if (config->symbolOrderingFile.empty())
1267     return sectionOrder;
1268 
1269   struct SymbolOrderEntry {
1270     int priority;
1271     bool present;
1272   };
1273 
1274   // Build a map from symbols to their priorities. Symbols that didn't
1275   // appear in the symbol ordering file have the lowest priority 0.
1276   // All explicitly mentioned symbols have negative (higher) priorities.
1277   DenseMap<CachedHashStringRef, SymbolOrderEntry> symbolOrder;
1278   int priority = -config->symbolOrderingFile.size();
1279   for (StringRef s : config->symbolOrderingFile)
1280     symbolOrder.insert({CachedHashStringRef(s), {priority++, false}});
1281 
1282   // Build a map from sections to their priorities.
1283   auto addSym = [&](Symbol &sym) {
1284     auto it = symbolOrder.find(CachedHashStringRef(sym.getName()));
1285     if (it == symbolOrder.end())
1286       return;
1287     SymbolOrderEntry &ent = it->second;
1288     ent.present = true;
1289 
1290     maybeWarnUnorderableSymbol(&sym);
1291 
1292     if (auto *d = dyn_cast<Defined>(&sym)) {
1293       if (auto *sec = dyn_cast_or_null<InputSectionBase>(d->section)) {
1294         int &priority = sectionOrder[cast<InputSectionBase>(sec)];
1295         priority = std::min(priority, ent.priority);
1296       }
1297     }
1298   };
1299 
1300   // We want both global and local symbols. We get the global ones from the
1301   // symbol table and iterate the object files for the local ones.
1302   for (Symbol *sym : symtab->symbols())
1303     addSym(*sym);
1304 
1305   for (ELFFileBase *file : ctx->objectFiles)
1306     for (Symbol *sym : file->getLocalSymbols())
1307       addSym(*sym);
1308 
1309   if (config->warnSymbolOrdering)
1310     for (auto orderEntry : symbolOrder)
1311       if (!orderEntry.second.present)
1312         warn("symbol ordering file: no such symbol: " + orderEntry.first.val());
1313 
1314   return sectionOrder;
1315 }
1316 
1317 // Sorts the sections in ISD according to the provided section order.
1318 static void
1319 sortISDBySectionOrder(InputSectionDescription *isd,
1320                       const DenseMap<const InputSectionBase *, int> &order,
1321                       bool executableOutputSection) {
1322   SmallVector<InputSection *, 0> unorderedSections;
1323   SmallVector<std::pair<InputSection *, int>, 0> orderedSections;
1324   uint64_t unorderedSize = 0;
1325   uint64_t totalSize = 0;
1326 
1327   for (InputSection *isec : isd->sections) {
1328     if (executableOutputSection)
1329       totalSize += isec->getSize();
1330     auto i = order.find(isec);
1331     if (i == order.end()) {
1332       unorderedSections.push_back(isec);
1333       unorderedSize += isec->getSize();
1334       continue;
1335     }
1336     orderedSections.push_back({isec, i->second});
1337   }
1338   llvm::sort(orderedSections, llvm::less_second());
1339 
1340   // Find an insertion point for the ordered section list in the unordered
1341   // section list. On targets with limited-range branches, this is the mid-point
1342   // of the unordered section list. This decreases the likelihood that a range
1343   // extension thunk will be needed to enter or exit the ordered region. If the
1344   // ordered section list is a list of hot functions, we can generally expect
1345   // the ordered functions to be called more often than the unordered functions,
1346   // making it more likely that any particular call will be within range, and
1347   // therefore reducing the number of thunks required.
1348   //
1349   // For example, imagine that you have 8MB of hot code and 32MB of cold code.
1350   // If the layout is:
1351   //
1352   // 8MB hot
1353   // 32MB cold
1354   //
1355   // only the first 8-16MB of the cold code (depending on which hot function it
1356   // is actually calling) can call the hot code without a range extension thunk.
1357   // However, if we use this layout:
1358   //
1359   // 16MB cold
1360   // 8MB hot
1361   // 16MB cold
1362   //
1363   // both the last 8-16MB of the first block of cold code and the first 8-16MB
1364   // of the second block of cold code can call the hot code without a thunk. So
1365   // we effectively double the amount of code that could potentially call into
1366   // the hot code without a thunk.
1367   //
1368   // The above is not necessary if total size of input sections in this "isd"
1369   // is small. Note that we assume all input sections are executable if the
1370   // output section is executable (which is not always true but supposed to
1371   // cover most cases).
1372   size_t insPt = 0;
1373   if (executableOutputSection && !orderedSections.empty() &&
1374       target->getThunkSectionSpacing() &&
1375       totalSize >= target->getThunkSectionSpacing()) {
1376     uint64_t unorderedPos = 0;
1377     for (; insPt != unorderedSections.size(); ++insPt) {
1378       unorderedPos += unorderedSections[insPt]->getSize();
1379       if (unorderedPos > unorderedSize / 2)
1380         break;
1381     }
1382   }
1383 
1384   isd->sections.clear();
1385   for (InputSection *isec : makeArrayRef(unorderedSections).slice(0, insPt))
1386     isd->sections.push_back(isec);
1387   for (std::pair<InputSection *, int> p : orderedSections)
1388     isd->sections.push_back(p.first);
1389   for (InputSection *isec : makeArrayRef(unorderedSections).slice(insPt))
1390     isd->sections.push_back(isec);
1391 }
1392 
1393 static void sortSection(OutputSection &osec,
1394                         const DenseMap<const InputSectionBase *, int> &order) {
1395   StringRef name = osec.name;
1396 
1397   // Never sort these.
1398   if (name == ".init" || name == ".fini")
1399     return;
1400 
1401   // IRelative relocations that usually live in the .rel[a].dyn section should
1402   // be processed last by the dynamic loader. To achieve that we add synthetic
1403   // sections in the required order from the beginning so that the in.relaIplt
1404   // section is placed last in an output section. Here we just do not apply
1405   // sorting for an output section which holds the in.relaIplt section.
1406   if (in.relaIplt->getParent() == &osec)
1407     return;
1408 
1409   // Sort input sections by priority using the list provided by
1410   // --symbol-ordering-file or --shuffle-sections=. This is a least significant
1411   // digit radix sort. The sections may be sorted stably again by a more
1412   // significant key.
1413   if (!order.empty())
1414     for (SectionCommand *b : osec.commands)
1415       if (auto *isd = dyn_cast<InputSectionDescription>(b))
1416         sortISDBySectionOrder(isd, order, osec.flags & SHF_EXECINSTR);
1417 
1418   if (script->hasSectionsCommand)
1419     return;
1420 
1421   if (name == ".init_array" || name == ".fini_array") {
1422     osec.sortInitFini();
1423   } else if (name == ".ctors" || name == ".dtors") {
1424     osec.sortCtorsDtors();
1425   } else if (config->emachine == EM_PPC64 && name == ".toc") {
1426     // .toc is allocated just after .got and is accessed using GOT-relative
1427     // relocations. Object files compiled with small code model have an
1428     // addressable range of [.got, .got + 0xFFFC] for GOT-relative relocations.
1429     // To reduce the risk of relocation overflow, .toc contents are sorted so
1430     // that sections having smaller relocation offsets are at beginning of .toc
1431     assert(osec.commands.size() == 1);
1432     auto *isd = cast<InputSectionDescription>(osec.commands[0]);
1433     llvm::stable_sort(isd->sections,
1434                       [](const InputSection *a, const InputSection *b) -> bool {
1435                         return a->file->ppc64SmallCodeModelTocRelocs &&
1436                                !b->file->ppc64SmallCodeModelTocRelocs;
1437                       });
1438   }
1439 }
1440 
1441 // If no layout was provided by linker script, we want to apply default
1442 // sorting for special input sections. This also handles --symbol-ordering-file.
1443 template <class ELFT> void Writer<ELFT>::sortInputSections() {
1444   // Build the order once since it is expensive.
1445   DenseMap<const InputSectionBase *, int> order = buildSectionOrder();
1446   maybeShuffle(order);
1447   for (SectionCommand *cmd : script->sectionCommands)
1448     if (auto *osd = dyn_cast<OutputDesc>(cmd))
1449       sortSection(osd->osec, order);
1450 }
1451 
1452 template <class ELFT> void Writer<ELFT>::sortSections() {
1453   llvm::TimeTraceScope timeScope("Sort sections");
1454 
1455   // Don't sort if using -r. It is not necessary and we want to preserve the
1456   // relative order for SHF_LINK_ORDER sections.
1457   if (config->relocatable) {
1458     script->adjustOutputSections();
1459     return;
1460   }
1461 
1462   sortInputSections();
1463 
1464   for (SectionCommand *cmd : script->sectionCommands)
1465     if (auto *osd = dyn_cast<OutputDesc>(cmd))
1466       osd->osec.sortRank = getSectionRank(osd->osec);
1467   if (!script->hasSectionsCommand) {
1468     // We know that all the OutputSections are contiguous in this case.
1469     auto isSection = [](SectionCommand *cmd) { return isa<OutputDesc>(cmd); };
1470     std::stable_sort(
1471         llvm::find_if(script->sectionCommands, isSection),
1472         llvm::find_if(llvm::reverse(script->sectionCommands), isSection).base(),
1473         compareSections);
1474   }
1475 
1476   // Process INSERT commands and update output section attributes. From this
1477   // point onwards the order of script->sectionCommands is fixed.
1478   script->processInsertCommands();
1479   script->adjustOutputSections();
1480 
1481   if (!script->hasSectionsCommand)
1482     return;
1483 
1484   // Orphan sections are sections present in the input files which are
1485   // not explicitly placed into the output file by the linker script.
1486   //
1487   // The sections in the linker script are already in the correct
1488   // order. We have to figuere out where to insert the orphan
1489   // sections.
1490   //
1491   // The order of the sections in the script is arbitrary and may not agree with
1492   // compareSections. This means that we cannot easily define a strict weak
1493   // ordering. To see why, consider a comparison of a section in the script and
1494   // one not in the script. We have a two simple options:
1495   // * Make them equivalent (a is not less than b, and b is not less than a).
1496   //   The problem is then that equivalence has to be transitive and we can
1497   //   have sections a, b and c with only b in a script and a less than c
1498   //   which breaks this property.
1499   // * Use compareSectionsNonScript. Given that the script order doesn't have
1500   //   to match, we can end up with sections a, b, c, d where b and c are in the
1501   //   script and c is compareSectionsNonScript less than b. In which case d
1502   //   can be equivalent to c, a to b and d < a. As a concrete example:
1503   //   .a (rx) # not in script
1504   //   .b (rx) # in script
1505   //   .c (ro) # in script
1506   //   .d (ro) # not in script
1507   //
1508   // The way we define an order then is:
1509   // *  Sort only the orphan sections. They are in the end right now.
1510   // *  Move each orphan section to its preferred position. We try
1511   //    to put each section in the last position where it can share
1512   //    a PT_LOAD.
1513   //
1514   // There is some ambiguity as to where exactly a new entry should be
1515   // inserted, because Commands contains not only output section
1516   // commands but also other types of commands such as symbol assignment
1517   // expressions. There's no correct answer here due to the lack of the
1518   // formal specification of the linker script. We use heuristics to
1519   // determine whether a new output command should be added before or
1520   // after another commands. For the details, look at shouldSkip
1521   // function.
1522 
1523   auto i = script->sectionCommands.begin();
1524   auto e = script->sectionCommands.end();
1525   auto nonScriptI = std::find_if(i, e, [](SectionCommand *cmd) {
1526     if (auto *osd = dyn_cast<OutputDesc>(cmd))
1527       return osd->osec.sectionIndex == UINT32_MAX;
1528     return false;
1529   });
1530 
1531   // Sort the orphan sections.
1532   std::stable_sort(nonScriptI, e, compareSections);
1533 
1534   // As a horrible special case, skip the first . assignment if it is before any
1535   // section. We do this because it is common to set a load address by starting
1536   // the script with ". = 0xabcd" and the expectation is that every section is
1537   // after that.
1538   auto firstSectionOrDotAssignment =
1539       std::find_if(i, e, [](SectionCommand *cmd) { return !shouldSkip(cmd); });
1540   if (firstSectionOrDotAssignment != e &&
1541       isa<SymbolAssignment>(**firstSectionOrDotAssignment))
1542     ++firstSectionOrDotAssignment;
1543   i = firstSectionOrDotAssignment;
1544 
1545   while (nonScriptI != e) {
1546     auto pos = findOrphanPos(i, nonScriptI);
1547     OutputSection *orphan = &cast<OutputDesc>(*nonScriptI)->osec;
1548 
1549     // As an optimization, find all sections with the same sort rank
1550     // and insert them with one rotate.
1551     unsigned rank = orphan->sortRank;
1552     auto end = std::find_if(nonScriptI + 1, e, [=](SectionCommand *cmd) {
1553       return cast<OutputDesc>(cmd)->osec.sortRank != rank;
1554     });
1555     std::rotate(pos, nonScriptI, end);
1556     nonScriptI = end;
1557   }
1558 
1559   script->adjustSectionsAfterSorting();
1560 }
1561 
1562 static bool compareByFilePosition(InputSection *a, InputSection *b) {
1563   InputSection *la = a->flags & SHF_LINK_ORDER ? a->getLinkOrderDep() : nullptr;
1564   InputSection *lb = b->flags & SHF_LINK_ORDER ? b->getLinkOrderDep() : nullptr;
1565   // SHF_LINK_ORDER sections with non-zero sh_link are ordered before
1566   // non-SHF_LINK_ORDER sections and SHF_LINK_ORDER sections with zero sh_link.
1567   if (!la || !lb)
1568     return la && !lb;
1569   OutputSection *aOut = la->getParent();
1570   OutputSection *bOut = lb->getParent();
1571 
1572   if (aOut != bOut)
1573     return aOut->addr < bOut->addr;
1574   return la->outSecOff < lb->outSecOff;
1575 }
1576 
1577 template <class ELFT> void Writer<ELFT>::resolveShfLinkOrder() {
1578   llvm::TimeTraceScope timeScope("Resolve SHF_LINK_ORDER");
1579   for (OutputSection *sec : outputSections) {
1580     if (!(sec->flags & SHF_LINK_ORDER))
1581       continue;
1582 
1583     // The ARM.exidx section use SHF_LINK_ORDER, but we have consolidated
1584     // this processing inside the ARMExidxsyntheticsection::finalizeContents().
1585     if (!config->relocatable && config->emachine == EM_ARM &&
1586         sec->type == SHT_ARM_EXIDX)
1587       continue;
1588 
1589     // Link order may be distributed across several InputSectionDescriptions.
1590     // Sorting is performed separately.
1591     SmallVector<InputSection **, 0> scriptSections;
1592     SmallVector<InputSection *, 0> sections;
1593     for (SectionCommand *cmd : sec->commands) {
1594       auto *isd = dyn_cast<InputSectionDescription>(cmd);
1595       if (!isd)
1596         continue;
1597       bool hasLinkOrder = false;
1598       scriptSections.clear();
1599       sections.clear();
1600       for (InputSection *&isec : isd->sections) {
1601         if (isec->flags & SHF_LINK_ORDER) {
1602           InputSection *link = isec->getLinkOrderDep();
1603           if (link && !link->getParent())
1604             error(toString(isec) + ": sh_link points to discarded section " +
1605                   toString(link));
1606           hasLinkOrder = true;
1607         }
1608         scriptSections.push_back(&isec);
1609         sections.push_back(isec);
1610       }
1611       if (hasLinkOrder && errorCount() == 0) {
1612         llvm::stable_sort(sections, compareByFilePosition);
1613         for (int i = 0, n = sections.size(); i != n; ++i)
1614           *scriptSections[i] = sections[i];
1615       }
1616     }
1617   }
1618 }
1619 
1620 static void finalizeSynthetic(SyntheticSection *sec) {
1621   if (sec && sec->isNeeded() && sec->getParent()) {
1622     llvm::TimeTraceScope timeScope("Finalize synthetic sections", sec->name);
1623     sec->finalizeContents();
1624   }
1625 }
1626 
1627 // We need to generate and finalize the content that depends on the address of
1628 // InputSections. As the generation of the content may also alter InputSection
1629 // addresses we must converge to a fixed point. We do that here. See the comment
1630 // in Writer<ELFT>::finalizeSections().
1631 template <class ELFT> void Writer<ELFT>::finalizeAddressDependentContent() {
1632   llvm::TimeTraceScope timeScope("Finalize address dependent content");
1633   ThunkCreator tc;
1634   AArch64Err843419Patcher a64p;
1635   ARMErr657417Patcher a32p;
1636   script->assignAddresses();
1637   // .ARM.exidx and SHF_LINK_ORDER do not require precise addresses, but they
1638   // do require the relative addresses of OutputSections because linker scripts
1639   // can assign Virtual Addresses to OutputSections that are not monotonically
1640   // increasing.
1641   for (Partition &part : partitions)
1642     finalizeSynthetic(part.armExidx.get());
1643   resolveShfLinkOrder();
1644 
1645   // Converts call x@GDPLT to call __tls_get_addr
1646   if (config->emachine == EM_HEXAGON)
1647     hexagonTLSSymbolUpdate(outputSections);
1648 
1649   uint32_t pass = 0, assignPasses = 0;
1650   for (;;) {
1651     bool changed = target->needsThunks ? tc.createThunks(pass, outputSections)
1652                                        : target->relaxOnce(pass);
1653     ++pass;
1654 
1655     // With Thunk Size much smaller than branch range we expect to
1656     // converge quickly; if we get to 15 something has gone wrong.
1657     if (changed && pass >= 15) {
1658       error(target->needsThunks ? "thunk creation not converged"
1659                                 : "relaxation not converged");
1660       break;
1661     }
1662 
1663     if (config->fixCortexA53Errata843419) {
1664       if (changed)
1665         script->assignAddresses();
1666       changed |= a64p.createFixes();
1667     }
1668     if (config->fixCortexA8) {
1669       if (changed)
1670         script->assignAddresses();
1671       changed |= a32p.createFixes();
1672     }
1673 
1674     if (in.mipsGot)
1675       in.mipsGot->updateAllocSize();
1676 
1677     for (Partition &part : partitions) {
1678       changed |= part.relaDyn->updateAllocSize();
1679       if (part.relrDyn)
1680         changed |= part.relrDyn->updateAllocSize();
1681     }
1682 
1683     const Defined *changedSym = script->assignAddresses();
1684     if (!changed) {
1685       // Some symbols may be dependent on section addresses. When we break the
1686       // loop, the symbol values are finalized because a previous
1687       // assignAddresses() finalized section addresses.
1688       if (!changedSym)
1689         break;
1690       if (++assignPasses == 5) {
1691         errorOrWarn("assignment to symbol " + toString(*changedSym) +
1692                     " does not converge");
1693         break;
1694       }
1695     }
1696   }
1697   if (!config->relocatable && config->emachine == EM_RISCV)
1698     riscvFinalizeRelax(pass);
1699 
1700   if (config->relocatable)
1701     for (OutputSection *sec : outputSections)
1702       sec->addr = 0;
1703 
1704   // If addrExpr is set, the address may not be a multiple of the alignment.
1705   // Warn because this is error-prone.
1706   for (SectionCommand *cmd : script->sectionCommands)
1707     if (auto *osd = dyn_cast<OutputDesc>(cmd)) {
1708       OutputSection *osec = &osd->osec;
1709       if (osec->addr % osec->alignment != 0)
1710         warn("address (0x" + Twine::utohexstr(osec->addr) + ") of section " +
1711              osec->name + " is not a multiple of alignment (" +
1712              Twine(osec->alignment) + ")");
1713     }
1714 }
1715 
1716 // If Input Sections have been shrunk (basic block sections) then
1717 // update symbol values and sizes associated with these sections.  With basic
1718 // block sections, input sections can shrink when the jump instructions at
1719 // the end of the section are relaxed.
1720 static void fixSymbolsAfterShrinking() {
1721   for (InputFile *File : ctx->objectFiles) {
1722     parallelForEach(File->getSymbols(), [&](Symbol *Sym) {
1723       auto *def = dyn_cast<Defined>(Sym);
1724       if (!def)
1725         return;
1726 
1727       const SectionBase *sec = def->section;
1728       if (!sec)
1729         return;
1730 
1731       const InputSectionBase *inputSec = dyn_cast<InputSectionBase>(sec);
1732       if (!inputSec || !inputSec->bytesDropped)
1733         return;
1734 
1735       const size_t OldSize = inputSec->rawData.size();
1736       const size_t NewSize = OldSize - inputSec->bytesDropped;
1737 
1738       if (def->value > NewSize && def->value <= OldSize) {
1739         LLVM_DEBUG(llvm::dbgs()
1740                    << "Moving symbol " << Sym->getName() << " from "
1741                    << def->value << " to "
1742                    << def->value - inputSec->bytesDropped << " bytes\n");
1743         def->value -= inputSec->bytesDropped;
1744         return;
1745       }
1746 
1747       if (def->value + def->size > NewSize && def->value <= OldSize &&
1748           def->value + def->size <= OldSize) {
1749         LLVM_DEBUG(llvm::dbgs()
1750                    << "Shrinking symbol " << Sym->getName() << " from "
1751                    << def->size << " to " << def->size - inputSec->bytesDropped
1752                    << " bytes\n");
1753         def->size -= inputSec->bytesDropped;
1754       }
1755     });
1756   }
1757 }
1758 
1759 // If basic block sections exist, there are opportunities to delete fall thru
1760 // jumps and shrink jump instructions after basic block reordering.  This
1761 // relaxation pass does that.  It is only enabled when --optimize-bb-jumps
1762 // option is used.
1763 template <class ELFT> void Writer<ELFT>::optimizeBasicBlockJumps() {
1764   assert(config->optimizeBBJumps);
1765   SmallVector<InputSection *, 0> storage;
1766 
1767   script->assignAddresses();
1768   // For every output section that has executable input sections, this
1769   // does the following:
1770   //   1. Deletes all direct jump instructions in input sections that
1771   //      jump to the following section as it is not required.
1772   //   2. If there are two consecutive jump instructions, it checks
1773   //      if they can be flipped and one can be deleted.
1774   for (OutputSection *osec : outputSections) {
1775     if (!(osec->flags & SHF_EXECINSTR))
1776       continue;
1777     ArrayRef<InputSection *> sections = getInputSections(*osec, storage);
1778     size_t numDeleted = 0;
1779     // Delete all fall through jump instructions.  Also, check if two
1780     // consecutive jump instructions can be flipped so that a fall
1781     // through jmp instruction can be deleted.
1782     for (size_t i = 0, e = sections.size(); i != e; ++i) {
1783       InputSection *next = i + 1 < sections.size() ? sections[i + 1] : nullptr;
1784       InputSection &sec = *sections[i];
1785       numDeleted += target->deleteFallThruJmpInsn(sec, sec.file, next);
1786     }
1787     if (numDeleted > 0) {
1788       script->assignAddresses();
1789       LLVM_DEBUG(llvm::dbgs()
1790                  << "Removing " << numDeleted << " fall through jumps\n");
1791     }
1792   }
1793 
1794   fixSymbolsAfterShrinking();
1795 
1796   for (OutputSection *osec : outputSections)
1797     for (InputSection *is : getInputSections(*osec, storage))
1798       is->trim();
1799 }
1800 
1801 // In order to allow users to manipulate linker-synthesized sections,
1802 // we had to add synthetic sections to the input section list early,
1803 // even before we make decisions whether they are needed. This allows
1804 // users to write scripts like this: ".mygot : { .got }".
1805 //
1806 // Doing it has an unintended side effects. If it turns out that we
1807 // don't need a .got (for example) at all because there's no
1808 // relocation that needs a .got, we don't want to emit .got.
1809 //
1810 // To deal with the above problem, this function is called after
1811 // scanRelocations is called to remove synthetic sections that turn
1812 // out to be empty.
1813 static void removeUnusedSyntheticSections() {
1814   // All input synthetic sections that can be empty are placed after
1815   // all regular ones. Reverse iterate to find the first synthetic section
1816   // after a non-synthetic one which will be our starting point.
1817   auto start = std::find_if(inputSections.rbegin(), inputSections.rend(),
1818                             [](InputSectionBase *s) {
1819                               return !isa<SyntheticSection>(s);
1820                             })
1821                    .base();
1822 
1823   // Remove unused synthetic sections from inputSections;
1824   DenseSet<InputSectionBase *> unused;
1825   auto end =
1826       std::remove_if(start, inputSections.end(), [&](InputSectionBase *s) {
1827         auto *sec = cast<SyntheticSection>(s);
1828         if (sec->getParent() && sec->isNeeded())
1829           return false;
1830         unused.insert(sec);
1831         return true;
1832       });
1833   inputSections.erase(end, inputSections.end());
1834 
1835   // Remove unused synthetic sections from the corresponding input section
1836   // description and orphanSections.
1837   for (auto *sec : unused)
1838     if (OutputSection *osec = cast<SyntheticSection>(sec)->getParent())
1839       for (SectionCommand *cmd : osec->commands)
1840         if (auto *isd = dyn_cast<InputSectionDescription>(cmd))
1841           llvm::erase_if(isd->sections, [&](InputSection *isec) {
1842             return unused.count(isec);
1843           });
1844   llvm::erase_if(script->orphanSections, [&](const InputSectionBase *sec) {
1845     return unused.count(sec);
1846   });
1847 }
1848 
1849 // Create output section objects and add them to OutputSections.
1850 template <class ELFT> void Writer<ELFT>::finalizeSections() {
1851   Out::preinitArray = findSection(".preinit_array");
1852   Out::initArray = findSection(".init_array");
1853   Out::finiArray = findSection(".fini_array");
1854 
1855   // The linker needs to define SECNAME_start, SECNAME_end and SECNAME_stop
1856   // symbols for sections, so that the runtime can get the start and end
1857   // addresses of each section by section name. Add such symbols.
1858   if (!config->relocatable) {
1859     addStartEndSymbols();
1860     for (SectionCommand *cmd : script->sectionCommands)
1861       if (auto *osd = dyn_cast<OutputDesc>(cmd))
1862         addStartStopSymbols(osd->osec);
1863   }
1864 
1865   // Add _DYNAMIC symbol. Unlike GNU gold, our _DYNAMIC symbol has no type.
1866   // It should be okay as no one seems to care about the type.
1867   // Even the author of gold doesn't remember why gold behaves that way.
1868   // https://sourceware.org/ml/binutils/2002-03/msg00360.html
1869   if (mainPart->dynamic->parent)
1870     symtab->addSymbol(Defined{/*file=*/nullptr, "_DYNAMIC", STB_WEAK, STV_HIDDEN, STT_NOTYPE,
1871         /*value=*/0, /*size=*/0, mainPart->dynamic.get()})->isUsedInRegularObj = true;
1872 
1873   // Define __rel[a]_iplt_{start,end} symbols if needed.
1874   addRelIpltSymbols();
1875 
1876   // RISC-V's gp can address +/- 2 KiB, set it to .sdata + 0x800. This symbol
1877   // should only be defined in an executable. If .sdata does not exist, its
1878   // value/section does not matter but it has to be relative, so set its
1879   // st_shndx arbitrarily to 1 (Out::elfHeader).
1880   if (config->emachine == EM_RISCV && !config->shared) {
1881     OutputSection *sec = findSection(".sdata");
1882     ElfSym::riscvGlobalPointer =
1883         addOptionalRegular("__global_pointer$", sec ? sec : Out::elfHeader,
1884                            0x800, STV_DEFAULT);
1885   }
1886 
1887   if (config->emachine == EM_386 || config->emachine == EM_X86_64) {
1888     // On targets that support TLSDESC, _TLS_MODULE_BASE_ is defined in such a
1889     // way that:
1890     //
1891     // 1) Without relaxation: it produces a dynamic TLSDESC relocation that
1892     // computes 0.
1893     // 2) With LD->LE relaxation: _TLS_MODULE_BASE_@tpoff = 0 (lowest address in
1894     // the TLS block).
1895     //
1896     // 2) is special cased in @tpoff computation. To satisfy 1), we define it as
1897     // an absolute symbol of zero. This is different from GNU linkers which
1898     // define _TLS_MODULE_BASE_ relative to the first TLS section.
1899     Symbol *s = symtab->find("_TLS_MODULE_BASE_");
1900     if (s && s->isUndefined()) {
1901       s->resolve(Defined{/*file=*/nullptr, StringRef(), STB_GLOBAL, STV_HIDDEN,
1902                          STT_TLS, /*value=*/0, 0,
1903                          /*section=*/nullptr});
1904       ElfSym::tlsModuleBase = cast<Defined>(s);
1905     }
1906   }
1907 
1908   {
1909     llvm::TimeTraceScope timeScope("Finalize .eh_frame");
1910     // This responsible for splitting up .eh_frame section into
1911     // pieces. The relocation scan uses those pieces, so this has to be
1912     // earlier.
1913     for (Partition &part : partitions)
1914       finalizeSynthetic(part.ehFrame.get());
1915   }
1916 
1917   if (config->hasDynSymTab) {
1918     parallelForEach(symtab->symbols(), [](Symbol *sym) {
1919       sym->isPreemptible = computeIsPreemptible(*sym);
1920     });
1921   }
1922 
1923   // Change values of linker-script-defined symbols from placeholders (assigned
1924   // by declareSymbols) to actual definitions.
1925   script->processSymbolAssignments();
1926 
1927   {
1928     llvm::TimeTraceScope timeScope("Scan relocations");
1929     // Scan relocations. This must be done after every symbol is declared so
1930     // that we can correctly decide if a dynamic relocation is needed. This is
1931     // called after processSymbolAssignments() because it needs to know whether
1932     // a linker-script-defined symbol is absolute.
1933     ppc64noTocRelax.clear();
1934     if (!config->relocatable) {
1935       // Scan all relocations. Each relocation goes through a series of tests to
1936       // determine if it needs special treatment, such as creating GOT, PLT,
1937       // copy relocations, etc. Note that relocations for non-alloc sections are
1938       // directly processed by InputSection::relocateNonAlloc.
1939       for (InputSectionBase *sec : inputSections)
1940         if (sec->isLive() && isa<InputSection>(sec) && (sec->flags & SHF_ALLOC))
1941           scanRelocations<ELFT>(*sec);
1942       for (Partition &part : partitions) {
1943         for (EhInputSection *sec : part.ehFrame->sections)
1944           scanRelocations<ELFT>(*sec);
1945         if (part.armExidx && part.armExidx->isLive())
1946           for (InputSection *sec : part.armExidx->exidxSections)
1947             scanRelocations<ELFT>(*sec);
1948       }
1949 
1950       reportUndefinedSymbols();
1951       postScanRelocations();
1952     }
1953   }
1954 
1955   if (in.plt && in.plt->isNeeded())
1956     in.plt->addSymbols();
1957   if (in.iplt && in.iplt->isNeeded())
1958     in.iplt->addSymbols();
1959 
1960   if (config->unresolvedSymbolsInShlib != UnresolvedPolicy::Ignore) {
1961     auto diagnose =
1962         config->unresolvedSymbolsInShlib == UnresolvedPolicy::ReportError
1963             ? errorOrWarn
1964             : warn;
1965     // Error on undefined symbols in a shared object, if all of its DT_NEEDED
1966     // entries are seen. These cases would otherwise lead to runtime errors
1967     // reported by the dynamic linker.
1968     //
1969     // ld.bfd traces all DT_NEEDED to emulate the logic of the dynamic linker to
1970     // catch more cases. That is too much for us. Our approach resembles the one
1971     // used in ld.gold, achieves a good balance to be useful but not too smart.
1972     for (SharedFile *file : ctx->sharedFiles) {
1973       bool allNeededIsKnown =
1974           llvm::all_of(file->dtNeeded, [&](StringRef needed) {
1975             return symtab->soNames.count(CachedHashStringRef(needed));
1976           });
1977       if (!allNeededIsKnown)
1978         continue;
1979       for (Symbol *sym : file->requiredSymbols)
1980         if (sym->isUndefined() && !sym->isWeak())
1981           diagnose("undefined reference due to --no-allow-shlib-undefined: " +
1982                    toString(*sym) + "\n>>> referenced by " + toString(file));
1983     }
1984   }
1985 
1986   {
1987     llvm::TimeTraceScope timeScope("Add symbols to symtabs");
1988     // Now that we have defined all possible global symbols including linker-
1989     // synthesized ones. Visit all symbols to give the finishing touches.
1990     for (Symbol *sym : symtab->symbols()) {
1991       if (!sym->isUsedInRegularObj || !includeInSymtab(*sym))
1992         continue;
1993       if (!config->relocatable)
1994         sym->binding = sym->computeBinding();
1995       if (in.symTab)
1996         in.symTab->addSymbol(sym);
1997 
1998       if (sym->includeInDynsym()) {
1999         partitions[sym->partition - 1].dynSymTab->addSymbol(sym);
2000         if (auto *file = dyn_cast_or_null<SharedFile>(sym->file))
2001           if (file->isNeeded && !sym->isUndefined())
2002             addVerneed(sym);
2003       }
2004     }
2005 
2006     // We also need to scan the dynamic relocation tables of the other
2007     // partitions and add any referenced symbols to the partition's dynsym.
2008     for (Partition &part : MutableArrayRef<Partition>(partitions).slice(1)) {
2009       DenseSet<Symbol *> syms;
2010       for (const SymbolTableEntry &e : part.dynSymTab->getSymbols())
2011         syms.insert(e.sym);
2012       for (DynamicReloc &reloc : part.relaDyn->relocs)
2013         if (reloc.sym && reloc.needsDynSymIndex() &&
2014             syms.insert(reloc.sym).second)
2015           part.dynSymTab->addSymbol(reloc.sym);
2016     }
2017   }
2018 
2019   if (in.mipsGot)
2020     in.mipsGot->build();
2021 
2022   removeUnusedSyntheticSections();
2023   script->diagnoseOrphanHandling();
2024 
2025   sortSections();
2026 
2027   // Create a list of OutputSections, assign sectionIndex, and populate
2028   // in.shStrTab.
2029   for (SectionCommand *cmd : script->sectionCommands)
2030     if (auto *osd = dyn_cast<OutputDesc>(cmd)) {
2031       OutputSection *osec = &osd->osec;
2032       outputSections.push_back(osec);
2033       osec->sectionIndex = outputSections.size();
2034       osec->shName = in.shStrTab->addString(osec->name);
2035     }
2036 
2037   // Prefer command line supplied address over other constraints.
2038   for (OutputSection *sec : outputSections) {
2039     auto i = config->sectionStartMap.find(sec->name);
2040     if (i != config->sectionStartMap.end())
2041       sec->addrExpr = [=] { return i->second; };
2042   }
2043 
2044   // With the outputSections available check for GDPLT relocations
2045   // and add __tls_get_addr symbol if needed.
2046   if (config->emachine == EM_HEXAGON && hexagonNeedsTLSSymbol(outputSections)) {
2047     Symbol *sym = symtab->addSymbol(Undefined{
2048         nullptr, "__tls_get_addr", STB_GLOBAL, STV_DEFAULT, STT_NOTYPE});
2049     sym->isPreemptible = true;
2050     partitions[0].dynSymTab->addSymbol(sym);
2051   }
2052 
2053   // This is a bit of a hack. A value of 0 means undef, so we set it
2054   // to 1 to make __ehdr_start defined. The section number is not
2055   // particularly relevant.
2056   Out::elfHeader->sectionIndex = 1;
2057   Out::elfHeader->size = sizeof(typename ELFT::Ehdr);
2058 
2059   // Binary and relocatable output does not have PHDRS.
2060   // The headers have to be created before finalize as that can influence the
2061   // image base and the dynamic section on mips includes the image base.
2062   if (!config->relocatable && !config->oFormatBinary) {
2063     for (Partition &part : partitions) {
2064       part.phdrs = script->hasPhdrsCommands() ? script->createPhdrs()
2065                                               : createPhdrs(part);
2066       if (config->emachine == EM_ARM) {
2067         // PT_ARM_EXIDX is the ARM EHABI equivalent of PT_GNU_EH_FRAME
2068         addPhdrForSection(part, SHT_ARM_EXIDX, PT_ARM_EXIDX, PF_R);
2069       }
2070       if (config->emachine == EM_MIPS) {
2071         // Add separate segments for MIPS-specific sections.
2072         addPhdrForSection(part, SHT_MIPS_REGINFO, PT_MIPS_REGINFO, PF_R);
2073         addPhdrForSection(part, SHT_MIPS_OPTIONS, PT_MIPS_OPTIONS, PF_R);
2074         addPhdrForSection(part, SHT_MIPS_ABIFLAGS, PT_MIPS_ABIFLAGS, PF_R);
2075       }
2076     }
2077     Out::programHeaders->size = sizeof(Elf_Phdr) * mainPart->phdrs.size();
2078 
2079     // Find the TLS segment. This happens before the section layout loop so that
2080     // Android relocation packing can look up TLS symbol addresses. We only need
2081     // to care about the main partition here because all TLS symbols were moved
2082     // to the main partition (see MarkLive.cpp).
2083     for (PhdrEntry *p : mainPart->phdrs)
2084       if (p->p_type == PT_TLS)
2085         Out::tlsPhdr = p;
2086   }
2087 
2088   // Some symbols are defined in term of program headers. Now that we
2089   // have the headers, we can find out which sections they point to.
2090   setReservedSymbolSections();
2091 
2092   {
2093     llvm::TimeTraceScope timeScope("Finalize synthetic sections");
2094 
2095     finalizeSynthetic(in.bss.get());
2096     finalizeSynthetic(in.bssRelRo.get());
2097     finalizeSynthetic(in.symTabShndx.get());
2098     finalizeSynthetic(in.shStrTab.get());
2099     finalizeSynthetic(in.strTab.get());
2100     finalizeSynthetic(in.got.get());
2101     finalizeSynthetic(in.mipsGot.get());
2102     finalizeSynthetic(in.igotPlt.get());
2103     finalizeSynthetic(in.gotPlt.get());
2104     finalizeSynthetic(in.relaIplt.get());
2105     finalizeSynthetic(in.relaPlt.get());
2106     finalizeSynthetic(in.plt.get());
2107     finalizeSynthetic(in.iplt.get());
2108     finalizeSynthetic(in.ppc32Got2.get());
2109     finalizeSynthetic(in.partIndex.get());
2110 
2111     // Dynamic section must be the last one in this list and dynamic
2112     // symbol table section (dynSymTab) must be the first one.
2113     for (Partition &part : partitions) {
2114       if (part.relaDyn) {
2115         // Compute DT_RELACOUNT to be used by part.dynamic.
2116         part.relaDyn->partitionRels();
2117         finalizeSynthetic(part.relaDyn.get());
2118       }
2119 
2120       finalizeSynthetic(part.dynSymTab.get());
2121       finalizeSynthetic(part.gnuHashTab.get());
2122       finalizeSynthetic(part.hashTab.get());
2123       finalizeSynthetic(part.verDef.get());
2124       finalizeSynthetic(part.relrDyn.get());
2125       finalizeSynthetic(part.ehFrameHdr.get());
2126       finalizeSynthetic(part.verSym.get());
2127       finalizeSynthetic(part.verNeed.get());
2128       finalizeSynthetic(part.dynamic.get());
2129     }
2130   }
2131 
2132   if (!script->hasSectionsCommand && !config->relocatable)
2133     fixSectionAlignments();
2134 
2135   // This is used to:
2136   // 1) Create "thunks":
2137   //    Jump instructions in many ISAs have small displacements, and therefore
2138   //    they cannot jump to arbitrary addresses in memory. For example, RISC-V
2139   //    JAL instruction can target only +-1 MiB from PC. It is a linker's
2140   //    responsibility to create and insert small pieces of code between
2141   //    sections to extend the ranges if jump targets are out of range. Such
2142   //    code pieces are called "thunks".
2143   //
2144   //    We add thunks at this stage. We couldn't do this before this point
2145   //    because this is the earliest point where we know sizes of sections and
2146   //    their layouts (that are needed to determine if jump targets are in
2147   //    range).
2148   //
2149   // 2) Update the sections. We need to generate content that depends on the
2150   //    address of InputSections. For example, MIPS GOT section content or
2151   //    android packed relocations sections content.
2152   //
2153   // 3) Assign the final values for the linker script symbols. Linker scripts
2154   //    sometimes using forward symbol declarations. We want to set the correct
2155   //    values. They also might change after adding the thunks.
2156   finalizeAddressDependentContent();
2157 
2158   // All information needed for OutputSection part of Map file is available.
2159   if (errorCount())
2160     return;
2161 
2162   {
2163     llvm::TimeTraceScope timeScope("Finalize synthetic sections");
2164     // finalizeAddressDependentContent may have added local symbols to the
2165     // static symbol table.
2166     finalizeSynthetic(in.symTab.get());
2167     finalizeSynthetic(in.ppc64LongBranchTarget.get());
2168   }
2169 
2170   // Relaxation to delete inter-basic block jumps created by basic block
2171   // sections. Run after in.symTab is finalized as optimizeBasicBlockJumps
2172   // can relax jump instructions based on symbol offset.
2173   if (config->optimizeBBJumps)
2174     optimizeBasicBlockJumps();
2175 
2176   // Fill other section headers. The dynamic table is finalized
2177   // at the end because some tags like RELSZ depend on result
2178   // of finalizing other sections.
2179   for (OutputSection *sec : outputSections)
2180     sec->finalize();
2181 }
2182 
2183 // Ensure data sections are not mixed with executable sections when
2184 // --execute-only is used. --execute-only make pages executable but not
2185 // readable.
2186 template <class ELFT> void Writer<ELFT>::checkExecuteOnly() {
2187   if (!config->executeOnly)
2188     return;
2189 
2190   SmallVector<InputSection *, 0> storage;
2191   for (OutputSection *osec : outputSections)
2192     if (osec->flags & SHF_EXECINSTR)
2193       for (InputSection *isec : getInputSections(*osec, storage))
2194         if (!(isec->flags & SHF_EXECINSTR))
2195           error("cannot place " + toString(isec) + " into " +
2196                 toString(osec->name) +
2197                 ": --execute-only does not support intermingling data and code");
2198 }
2199 
2200 // The linker is expected to define SECNAME_start and SECNAME_end
2201 // symbols for a few sections. This function defines them.
2202 template <class ELFT> void Writer<ELFT>::addStartEndSymbols() {
2203   // If a section does not exist, there's ambiguity as to how we
2204   // define _start and _end symbols for an init/fini section. Since
2205   // the loader assume that the symbols are always defined, we need to
2206   // always define them. But what value? The loader iterates over all
2207   // pointers between _start and _end to run global ctors/dtors, so if
2208   // the section is empty, their symbol values don't actually matter
2209   // as long as _start and _end point to the same location.
2210   //
2211   // That said, we don't want to set the symbols to 0 (which is
2212   // probably the simplest value) because that could cause some
2213   // program to fail to link due to relocation overflow, if their
2214   // program text is above 2 GiB. We use the address of the .text
2215   // section instead to prevent that failure.
2216   //
2217   // In rare situations, the .text section may not exist. If that's the
2218   // case, use the image base address as a last resort.
2219   OutputSection *Default = findSection(".text");
2220   if (!Default)
2221     Default = Out::elfHeader;
2222 
2223   auto define = [=](StringRef start, StringRef end, OutputSection *os) {
2224     if (os && !script->isDiscarded(os)) {
2225       addOptionalRegular(start, os, 0);
2226       addOptionalRegular(end, os, -1);
2227     } else {
2228       addOptionalRegular(start, Default, 0);
2229       addOptionalRegular(end, Default, 0);
2230     }
2231   };
2232 
2233   define("__preinit_array_start", "__preinit_array_end", Out::preinitArray);
2234   define("__init_array_start", "__init_array_end", Out::initArray);
2235   define("__fini_array_start", "__fini_array_end", Out::finiArray);
2236 
2237   if (OutputSection *sec = findSection(".ARM.exidx"))
2238     define("__exidx_start", "__exidx_end", sec);
2239 }
2240 
2241 // If a section name is valid as a C identifier (which is rare because of
2242 // the leading '.'), linkers are expected to define __start_<secname> and
2243 // __stop_<secname> symbols. They are at beginning and end of the section,
2244 // respectively. This is not requested by the ELF standard, but GNU ld and
2245 // gold provide the feature, and used by many programs.
2246 template <class ELFT>
2247 void Writer<ELFT>::addStartStopSymbols(OutputSection &osec) {
2248   StringRef s = osec.name;
2249   if (!isValidCIdentifier(s))
2250     return;
2251   addOptionalRegular(saver().save("__start_" + s), &osec, 0,
2252                      config->zStartStopVisibility);
2253   addOptionalRegular(saver().save("__stop_" + s), &osec, -1,
2254                      config->zStartStopVisibility);
2255 }
2256 
2257 static bool needsPtLoad(OutputSection *sec) {
2258   if (!(sec->flags & SHF_ALLOC))
2259     return false;
2260 
2261   // Don't allocate VA space for TLS NOBITS sections. The PT_TLS PHDR is
2262   // responsible for allocating space for them, not the PT_LOAD that
2263   // contains the TLS initialization image.
2264   if ((sec->flags & SHF_TLS) && sec->type == SHT_NOBITS)
2265     return false;
2266   return true;
2267 }
2268 
2269 // Linker scripts are responsible for aligning addresses. Unfortunately, most
2270 // linker scripts are designed for creating two PT_LOADs only, one RX and one
2271 // RW. This means that there is no alignment in the RO to RX transition and we
2272 // cannot create a PT_LOAD there.
2273 static uint64_t computeFlags(uint64_t flags) {
2274   if (config->omagic)
2275     return PF_R | PF_W | PF_X;
2276   if (config->executeOnly && (flags & PF_X))
2277     return flags & ~PF_R;
2278   if (config->singleRoRx && !(flags & PF_W))
2279     return flags | PF_X;
2280   return flags;
2281 }
2282 
2283 // Decide which program headers to create and which sections to include in each
2284 // one.
2285 template <class ELFT>
2286 SmallVector<PhdrEntry *, 0> Writer<ELFT>::createPhdrs(Partition &part) {
2287   SmallVector<PhdrEntry *, 0> ret;
2288   auto addHdr = [&](unsigned type, unsigned flags) -> PhdrEntry * {
2289     ret.push_back(make<PhdrEntry>(type, flags));
2290     return ret.back();
2291   };
2292 
2293   unsigned partNo = part.getNumber();
2294   bool isMain = partNo == 1;
2295 
2296   // Add the first PT_LOAD segment for regular output sections.
2297   uint64_t flags = computeFlags(PF_R);
2298   PhdrEntry *load = nullptr;
2299 
2300   // nmagic or omagic output does not have PT_PHDR, PT_INTERP, or the readonly
2301   // PT_LOAD.
2302   if (!config->nmagic && !config->omagic) {
2303     // The first phdr entry is PT_PHDR which describes the program header
2304     // itself.
2305     if (isMain)
2306       addHdr(PT_PHDR, PF_R)->add(Out::programHeaders);
2307     else
2308       addHdr(PT_PHDR, PF_R)->add(part.programHeaders->getParent());
2309 
2310     // PT_INTERP must be the second entry if exists.
2311     if (OutputSection *cmd = findSection(".interp", partNo))
2312       addHdr(PT_INTERP, cmd->getPhdrFlags())->add(cmd);
2313 
2314     // Add the headers. We will remove them if they don't fit.
2315     // In the other partitions the headers are ordinary sections, so they don't
2316     // need to be added here.
2317     if (isMain) {
2318       load = addHdr(PT_LOAD, flags);
2319       load->add(Out::elfHeader);
2320       load->add(Out::programHeaders);
2321     }
2322   }
2323 
2324   // PT_GNU_RELRO includes all sections that should be marked as
2325   // read-only by dynamic linker after processing relocations.
2326   // Current dynamic loaders only support one PT_GNU_RELRO PHDR, give
2327   // an error message if more than one PT_GNU_RELRO PHDR is required.
2328   PhdrEntry *relRo = make<PhdrEntry>(PT_GNU_RELRO, PF_R);
2329   bool inRelroPhdr = false;
2330   OutputSection *relroEnd = nullptr;
2331   for (OutputSection *sec : outputSections) {
2332     if (sec->partition != partNo || !needsPtLoad(sec))
2333       continue;
2334     if (isRelroSection(sec)) {
2335       inRelroPhdr = true;
2336       if (!relroEnd)
2337         relRo->add(sec);
2338       else
2339         error("section: " + sec->name + " is not contiguous with other relro" +
2340               " sections");
2341     } else if (inRelroPhdr) {
2342       inRelroPhdr = false;
2343       relroEnd = sec;
2344     }
2345   }
2346 
2347   for (OutputSection *sec : outputSections) {
2348     if (!needsPtLoad(sec))
2349       continue;
2350 
2351     // Normally, sections in partitions other than the current partition are
2352     // ignored. But partition number 255 is a special case: it contains the
2353     // partition end marker (.part.end). It needs to be added to the main
2354     // partition so that a segment is created for it in the main partition,
2355     // which will cause the dynamic loader to reserve space for the other
2356     // partitions.
2357     if (sec->partition != partNo) {
2358       if (isMain && sec->partition == 255)
2359         addHdr(PT_LOAD, computeFlags(sec->getPhdrFlags()))->add(sec);
2360       continue;
2361     }
2362 
2363     // Segments are contiguous memory regions that has the same attributes
2364     // (e.g. executable or writable). There is one phdr for each segment.
2365     // Therefore, we need to create a new phdr when the next section has
2366     // different flags or is loaded at a discontiguous address or memory
2367     // region using AT or AT> linker script command, respectively. At the same
2368     // time, we don't want to create a separate load segment for the headers,
2369     // even if the first output section has an AT or AT> attribute.
2370     uint64_t newFlags = computeFlags(sec->getPhdrFlags());
2371     bool sameLMARegion =
2372         load && !sec->lmaExpr && sec->lmaRegion == load->firstSec->lmaRegion;
2373     if (!(load && newFlags == flags && sec != relroEnd &&
2374           sec->memRegion == load->firstSec->memRegion &&
2375           (sameLMARegion || load->lastSec == Out::programHeaders))) {
2376       load = addHdr(PT_LOAD, newFlags);
2377       flags = newFlags;
2378     }
2379 
2380     load->add(sec);
2381   }
2382 
2383   // Add a TLS segment if any.
2384   PhdrEntry *tlsHdr = make<PhdrEntry>(PT_TLS, PF_R);
2385   for (OutputSection *sec : outputSections)
2386     if (sec->partition == partNo && sec->flags & SHF_TLS)
2387       tlsHdr->add(sec);
2388   if (tlsHdr->firstSec)
2389     ret.push_back(tlsHdr);
2390 
2391   // Add an entry for .dynamic.
2392   if (OutputSection *sec = part.dynamic->getParent())
2393     addHdr(PT_DYNAMIC, sec->getPhdrFlags())->add(sec);
2394 
2395   if (relRo->firstSec)
2396     ret.push_back(relRo);
2397 
2398   // PT_GNU_EH_FRAME is a special section pointing on .eh_frame_hdr.
2399   if (part.ehFrame->isNeeded() && part.ehFrameHdr &&
2400       part.ehFrame->getParent() && part.ehFrameHdr->getParent())
2401     addHdr(PT_GNU_EH_FRAME, part.ehFrameHdr->getParent()->getPhdrFlags())
2402         ->add(part.ehFrameHdr->getParent());
2403 
2404   // PT_OPENBSD_RANDOMIZE is an OpenBSD-specific feature. That makes
2405   // the dynamic linker fill the segment with random data.
2406   if (OutputSection *cmd = findSection(".openbsd.randomdata", partNo))
2407     addHdr(PT_OPENBSD_RANDOMIZE, cmd->getPhdrFlags())->add(cmd);
2408 
2409   if (config->zGnustack != GnuStackKind::None) {
2410     // PT_GNU_STACK is a special section to tell the loader to make the
2411     // pages for the stack non-executable. If you really want an executable
2412     // stack, you can pass -z execstack, but that's not recommended for
2413     // security reasons.
2414     unsigned perm = PF_R | PF_W;
2415     if (config->zGnustack == GnuStackKind::Exec)
2416       perm |= PF_X;
2417     addHdr(PT_GNU_STACK, perm)->p_memsz = config->zStackSize;
2418   }
2419 
2420   // PT_OPENBSD_WXNEEDED is a OpenBSD-specific header to mark the executable
2421   // is expected to perform W^X violations, such as calling mprotect(2) or
2422   // mmap(2) with PROT_WRITE | PROT_EXEC, which is prohibited by default on
2423   // OpenBSD.
2424   if (config->zWxneeded)
2425     addHdr(PT_OPENBSD_WXNEEDED, PF_X);
2426 
2427   if (OutputSection *cmd = findSection(".note.gnu.property", partNo))
2428     addHdr(PT_GNU_PROPERTY, PF_R)->add(cmd);
2429 
2430   // Create one PT_NOTE per a group of contiguous SHT_NOTE sections with the
2431   // same alignment.
2432   PhdrEntry *note = nullptr;
2433   for (OutputSection *sec : outputSections) {
2434     if (sec->partition != partNo)
2435       continue;
2436     if (sec->type == SHT_NOTE && (sec->flags & SHF_ALLOC)) {
2437       if (!note || sec->lmaExpr || note->lastSec->alignment != sec->alignment)
2438         note = addHdr(PT_NOTE, PF_R);
2439       note->add(sec);
2440     } else {
2441       note = nullptr;
2442     }
2443   }
2444   return ret;
2445 }
2446 
2447 template <class ELFT>
2448 void Writer<ELFT>::addPhdrForSection(Partition &part, unsigned shType,
2449                                      unsigned pType, unsigned pFlags) {
2450   unsigned partNo = part.getNumber();
2451   auto i = llvm::find_if(outputSections, [=](OutputSection *cmd) {
2452     return cmd->partition == partNo && cmd->type == shType;
2453   });
2454   if (i == outputSections.end())
2455     return;
2456 
2457   PhdrEntry *entry = make<PhdrEntry>(pType, pFlags);
2458   entry->add(*i);
2459   part.phdrs.push_back(entry);
2460 }
2461 
2462 // Place the first section of each PT_LOAD to a different page (of maxPageSize).
2463 // This is achieved by assigning an alignment expression to addrExpr of each
2464 // such section.
2465 template <class ELFT> void Writer<ELFT>::fixSectionAlignments() {
2466   const PhdrEntry *prev;
2467   auto pageAlign = [&](const PhdrEntry *p) {
2468     OutputSection *cmd = p->firstSec;
2469     if (!cmd)
2470       return;
2471     cmd->alignExpr = [align = cmd->alignment]() { return align; };
2472     if (!cmd->addrExpr) {
2473       // Prefer advancing to align(dot, maxPageSize) + dot%maxPageSize to avoid
2474       // padding in the file contents.
2475       //
2476       // When -z separate-code is used we must not have any overlap in pages
2477       // between an executable segment and a non-executable segment. We align to
2478       // the next maximum page size boundary on transitions between executable
2479       // and non-executable segments.
2480       //
2481       // SHT_LLVM_PART_EHDR marks the start of a partition. The partition
2482       // sections will be extracted to a separate file. Align to the next
2483       // maximum page size boundary so that we can find the ELF header at the
2484       // start. We cannot benefit from overlapping p_offset ranges with the
2485       // previous segment anyway.
2486       if (config->zSeparate == SeparateSegmentKind::Loadable ||
2487           (config->zSeparate == SeparateSegmentKind::Code && prev &&
2488            (prev->p_flags & PF_X) != (p->p_flags & PF_X)) ||
2489           cmd->type == SHT_LLVM_PART_EHDR)
2490         cmd->addrExpr = [] {
2491           return alignToPowerOf2(script->getDot(), config->maxPageSize);
2492         };
2493       // PT_TLS is at the start of the first RW PT_LOAD. If `p` includes PT_TLS,
2494       // it must be the RW. Align to p_align(PT_TLS) to make sure
2495       // p_vaddr(PT_LOAD)%p_align(PT_LOAD) = 0. Otherwise, if
2496       // sh_addralign(.tdata) < sh_addralign(.tbss), we will set p_align(PT_TLS)
2497       // to sh_addralign(.tbss), while p_vaddr(PT_TLS)=p_vaddr(PT_LOAD) may not
2498       // be congruent to 0 modulo p_align(PT_TLS).
2499       //
2500       // Technically this is not required, but as of 2019, some dynamic loaders
2501       // don't handle p_vaddr%p_align != 0 correctly, e.g. glibc (i386 and
2502       // x86-64) doesn't make runtime address congruent to p_vaddr modulo
2503       // p_align for dynamic TLS blocks (PR/24606), FreeBSD rtld has the same
2504       // bug, musl (TLS Variant 1 architectures) before 1.1.23 handled TLS
2505       // blocks correctly. We need to keep the workaround for a while.
2506       else if (Out::tlsPhdr && Out::tlsPhdr->firstSec == p->firstSec)
2507         cmd->addrExpr = [] {
2508           return alignToPowerOf2(script->getDot(), config->maxPageSize) +
2509                  alignToPowerOf2(script->getDot() % config->maxPageSize,
2510                                  Out::tlsPhdr->p_align);
2511         };
2512       else
2513         cmd->addrExpr = [] {
2514           return alignToPowerOf2(script->getDot(), config->maxPageSize) +
2515                  script->getDot() % config->maxPageSize;
2516         };
2517     }
2518   };
2519 
2520   for (Partition &part : partitions) {
2521     prev = nullptr;
2522     for (const PhdrEntry *p : part.phdrs)
2523       if (p->p_type == PT_LOAD && p->firstSec) {
2524         pageAlign(p);
2525         prev = p;
2526       }
2527   }
2528 }
2529 
2530 // Compute an in-file position for a given section. The file offset must be the
2531 // same with its virtual address modulo the page size, so that the loader can
2532 // load executables without any address adjustment.
2533 static uint64_t computeFileOffset(OutputSection *os, uint64_t off) {
2534   // The first section in a PT_LOAD has to have congruent offset and address
2535   // modulo the maximum page size.
2536   if (os->ptLoad && os->ptLoad->firstSec == os)
2537     return alignTo(off, os->ptLoad->p_align, os->addr);
2538 
2539   // File offsets are not significant for .bss sections other than the first one
2540   // in a PT_LOAD/PT_TLS. By convention, we keep section offsets monotonically
2541   // increasing rather than setting to zero.
2542   if (os->type == SHT_NOBITS &&
2543       (!Out::tlsPhdr || Out::tlsPhdr->firstSec != os))
2544      return off;
2545 
2546   // If the section is not in a PT_LOAD, we just have to align it.
2547   if (!os->ptLoad)
2548      return alignToPowerOf2(off, os->alignment);
2549 
2550   // If two sections share the same PT_LOAD the file offset is calculated
2551   // using this formula: Off2 = Off1 + (VA2 - VA1).
2552   OutputSection *first = os->ptLoad->firstSec;
2553   return first->offset + os->addr - first->addr;
2554 }
2555 
2556 template <class ELFT> void Writer<ELFT>::assignFileOffsetsBinary() {
2557   // Compute the minimum LMA of all non-empty non-NOBITS sections as minAddr.
2558   auto needsOffset = [](OutputSection &sec) {
2559     return sec.type != SHT_NOBITS && (sec.flags & SHF_ALLOC) && sec.size > 0;
2560   };
2561   uint64_t minAddr = UINT64_MAX;
2562   for (OutputSection *sec : outputSections)
2563     if (needsOffset(*sec)) {
2564       sec->offset = sec->getLMA();
2565       minAddr = std::min(minAddr, sec->offset);
2566     }
2567 
2568   // Sections are laid out at LMA minus minAddr.
2569   fileSize = 0;
2570   for (OutputSection *sec : outputSections)
2571     if (needsOffset(*sec)) {
2572       sec->offset -= minAddr;
2573       fileSize = std::max(fileSize, sec->offset + sec->size);
2574     }
2575 }
2576 
2577 static std::string rangeToString(uint64_t addr, uint64_t len) {
2578   return "[0x" + utohexstr(addr) + ", 0x" + utohexstr(addr + len - 1) + "]";
2579 }
2580 
2581 // Assign file offsets to output sections.
2582 template <class ELFT> void Writer<ELFT>::assignFileOffsets() {
2583   Out::programHeaders->offset = Out::elfHeader->size;
2584   uint64_t off = Out::elfHeader->size + Out::programHeaders->size;
2585 
2586   PhdrEntry *lastRX = nullptr;
2587   for (Partition &part : partitions)
2588     for (PhdrEntry *p : part.phdrs)
2589       if (p->p_type == PT_LOAD && (p->p_flags & PF_X))
2590         lastRX = p;
2591 
2592   // Layout SHF_ALLOC sections before non-SHF_ALLOC sections. A non-SHF_ALLOC
2593   // will not occupy file offsets contained by a PT_LOAD.
2594   for (OutputSection *sec : outputSections) {
2595     if (!(sec->flags & SHF_ALLOC))
2596       continue;
2597     off = computeFileOffset(sec, off);
2598     sec->offset = off;
2599     if (sec->type != SHT_NOBITS)
2600       off += sec->size;
2601 
2602     // If this is a last section of the last executable segment and that
2603     // segment is the last loadable segment, align the offset of the
2604     // following section to avoid loading non-segments parts of the file.
2605     if (config->zSeparate != SeparateSegmentKind::None && lastRX &&
2606         lastRX->lastSec == sec)
2607       off = alignToPowerOf2(off, config->maxPageSize);
2608   }
2609   for (OutputSection *osec : outputSections)
2610     if (!(osec->flags & SHF_ALLOC)) {
2611       osec->offset = alignToPowerOf2(off, osec->alignment);
2612       off = osec->offset + osec->size;
2613     }
2614 
2615   sectionHeaderOff = alignToPowerOf2(off, config->wordsize);
2616   fileSize = sectionHeaderOff + (outputSections.size() + 1) * sizeof(Elf_Shdr);
2617 
2618   // Our logic assumes that sections have rising VA within the same segment.
2619   // With use of linker scripts it is possible to violate this rule and get file
2620   // offset overlaps or overflows. That should never happen with a valid script
2621   // which does not move the location counter backwards and usually scripts do
2622   // not do that. Unfortunately, there are apps in the wild, for example, Linux
2623   // kernel, which control segment distribution explicitly and move the counter
2624   // backwards, so we have to allow doing that to support linking them. We
2625   // perform non-critical checks for overlaps in checkSectionOverlap(), but here
2626   // we want to prevent file size overflows because it would crash the linker.
2627   for (OutputSection *sec : outputSections) {
2628     if (sec->type == SHT_NOBITS)
2629       continue;
2630     if ((sec->offset > fileSize) || (sec->offset + sec->size > fileSize))
2631       error("unable to place section " + sec->name + " at file offset " +
2632             rangeToString(sec->offset, sec->size) +
2633             "; check your linker script for overflows");
2634   }
2635 }
2636 
2637 // Finalize the program headers. We call this function after we assign
2638 // file offsets and VAs to all sections.
2639 template <class ELFT> void Writer<ELFT>::setPhdrs(Partition &part) {
2640   for (PhdrEntry *p : part.phdrs) {
2641     OutputSection *first = p->firstSec;
2642     OutputSection *last = p->lastSec;
2643 
2644     if (first) {
2645       p->p_filesz = last->offset - first->offset;
2646       if (last->type != SHT_NOBITS)
2647         p->p_filesz += last->size;
2648 
2649       p->p_memsz = last->addr + last->size - first->addr;
2650       p->p_offset = first->offset;
2651       p->p_vaddr = first->addr;
2652 
2653       // File offsets in partitions other than the main partition are relative
2654       // to the offset of the ELF headers. Perform that adjustment now.
2655       if (part.elfHeader)
2656         p->p_offset -= part.elfHeader->getParent()->offset;
2657 
2658       if (!p->hasLMA)
2659         p->p_paddr = first->getLMA();
2660     }
2661 
2662     if (p->p_type == PT_GNU_RELRO) {
2663       p->p_align = 1;
2664       // musl/glibc ld.so rounds the size down, so we need to round up
2665       // to protect the last page. This is a no-op on FreeBSD which always
2666       // rounds up.
2667       p->p_memsz =
2668           alignToPowerOf2(p->p_offset + p->p_memsz, config->commonPageSize) -
2669           p->p_offset;
2670     }
2671   }
2672 }
2673 
2674 // A helper struct for checkSectionOverlap.
2675 namespace {
2676 struct SectionOffset {
2677   OutputSection *sec;
2678   uint64_t offset;
2679 };
2680 } // namespace
2681 
2682 // Check whether sections overlap for a specific address range (file offsets,
2683 // load and virtual addresses).
2684 static void checkOverlap(StringRef name, std::vector<SectionOffset> &sections,
2685                          bool isVirtualAddr) {
2686   llvm::sort(sections, [=](const SectionOffset &a, const SectionOffset &b) {
2687     return a.offset < b.offset;
2688   });
2689 
2690   // Finding overlap is easy given a vector is sorted by start position.
2691   // If an element starts before the end of the previous element, they overlap.
2692   for (size_t i = 1, end = sections.size(); i < end; ++i) {
2693     SectionOffset a = sections[i - 1];
2694     SectionOffset b = sections[i];
2695     if (b.offset >= a.offset + a.sec->size)
2696       continue;
2697 
2698     // If both sections are in OVERLAY we allow the overlapping of virtual
2699     // addresses, because it is what OVERLAY was designed for.
2700     if (isVirtualAddr && a.sec->inOverlay && b.sec->inOverlay)
2701       continue;
2702 
2703     errorOrWarn("section " + a.sec->name + " " + name +
2704                 " range overlaps with " + b.sec->name + "\n>>> " + a.sec->name +
2705                 " range is " + rangeToString(a.offset, a.sec->size) + "\n>>> " +
2706                 b.sec->name + " range is " +
2707                 rangeToString(b.offset, b.sec->size));
2708   }
2709 }
2710 
2711 // Check for overlapping sections and address overflows.
2712 //
2713 // In this function we check that none of the output sections have overlapping
2714 // file offsets. For SHF_ALLOC sections we also check that the load address
2715 // ranges and the virtual address ranges don't overlap
2716 template <class ELFT> void Writer<ELFT>::checkSections() {
2717   // First, check that section's VAs fit in available address space for target.
2718   for (OutputSection *os : outputSections)
2719     if ((os->addr + os->size < os->addr) ||
2720         (!ELFT::Is64Bits && os->addr + os->size > UINT32_MAX))
2721       errorOrWarn("section " + os->name + " at 0x" + utohexstr(os->addr) +
2722                   " of size 0x" + utohexstr(os->size) +
2723                   " exceeds available address space");
2724 
2725   // Check for overlapping file offsets. In this case we need to skip any
2726   // section marked as SHT_NOBITS. These sections don't actually occupy space in
2727   // the file so Sec->Offset + Sec->Size can overlap with others. If --oformat
2728   // binary is specified only add SHF_ALLOC sections are added to the output
2729   // file so we skip any non-allocated sections in that case.
2730   std::vector<SectionOffset> fileOffs;
2731   for (OutputSection *sec : outputSections)
2732     if (sec->size > 0 && sec->type != SHT_NOBITS &&
2733         (!config->oFormatBinary || (sec->flags & SHF_ALLOC)))
2734       fileOffs.push_back({sec, sec->offset});
2735   checkOverlap("file", fileOffs, false);
2736 
2737   // When linking with -r there is no need to check for overlapping virtual/load
2738   // addresses since those addresses will only be assigned when the final
2739   // executable/shared object is created.
2740   if (config->relocatable)
2741     return;
2742 
2743   // Checking for overlapping virtual and load addresses only needs to take
2744   // into account SHF_ALLOC sections since others will not be loaded.
2745   // Furthermore, we also need to skip SHF_TLS sections since these will be
2746   // mapped to other addresses at runtime and can therefore have overlapping
2747   // ranges in the file.
2748   std::vector<SectionOffset> vmas;
2749   for (OutputSection *sec : outputSections)
2750     if (sec->size > 0 && (sec->flags & SHF_ALLOC) && !(sec->flags & SHF_TLS))
2751       vmas.push_back({sec, sec->addr});
2752   checkOverlap("virtual address", vmas, true);
2753 
2754   // Finally, check that the load addresses don't overlap. This will usually be
2755   // the same as the virtual addresses but can be different when using a linker
2756   // script with AT().
2757   std::vector<SectionOffset> lmas;
2758   for (OutputSection *sec : outputSections)
2759     if (sec->size > 0 && (sec->flags & SHF_ALLOC) && !(sec->flags & SHF_TLS))
2760       lmas.push_back({sec, sec->getLMA()});
2761   checkOverlap("load address", lmas, false);
2762 }
2763 
2764 // The entry point address is chosen in the following ways.
2765 //
2766 // 1. the '-e' entry command-line option;
2767 // 2. the ENTRY(symbol) command in a linker control script;
2768 // 3. the value of the symbol _start, if present;
2769 // 4. the number represented by the entry symbol, if it is a number;
2770 // 5. the address 0.
2771 static uint64_t getEntryAddr() {
2772   // Case 1, 2 or 3
2773   if (Symbol *b = symtab->find(config->entry))
2774     return b->getVA();
2775 
2776   // Case 4
2777   uint64_t addr;
2778   if (to_integer(config->entry, addr))
2779     return addr;
2780 
2781   // Case 5
2782   if (config->warnMissingEntry)
2783     warn("cannot find entry symbol " + config->entry +
2784          "; not setting start address");
2785   return 0;
2786 }
2787 
2788 static uint16_t getELFType() {
2789   if (config->isPic)
2790     return ET_DYN;
2791   if (config->relocatable)
2792     return ET_REL;
2793   return ET_EXEC;
2794 }
2795 
2796 template <class ELFT> void Writer<ELFT>::writeHeader() {
2797   writeEhdr<ELFT>(Out::bufferStart, *mainPart);
2798   writePhdrs<ELFT>(Out::bufferStart + sizeof(Elf_Ehdr), *mainPart);
2799 
2800   auto *eHdr = reinterpret_cast<Elf_Ehdr *>(Out::bufferStart);
2801   eHdr->e_type = getELFType();
2802   eHdr->e_entry = getEntryAddr();
2803   eHdr->e_shoff = sectionHeaderOff;
2804 
2805   // Write the section header table.
2806   //
2807   // The ELF header can only store numbers up to SHN_LORESERVE in the e_shnum
2808   // and e_shstrndx fields. When the value of one of these fields exceeds
2809   // SHN_LORESERVE ELF requires us to put sentinel values in the ELF header and
2810   // use fields in the section header at index 0 to store
2811   // the value. The sentinel values and fields are:
2812   // e_shnum = 0, SHdrs[0].sh_size = number of sections.
2813   // e_shstrndx = SHN_XINDEX, SHdrs[0].sh_link = .shstrtab section index.
2814   auto *sHdrs = reinterpret_cast<Elf_Shdr *>(Out::bufferStart + eHdr->e_shoff);
2815   size_t num = outputSections.size() + 1;
2816   if (num >= SHN_LORESERVE)
2817     sHdrs->sh_size = num;
2818   else
2819     eHdr->e_shnum = num;
2820 
2821   uint32_t strTabIndex = in.shStrTab->getParent()->sectionIndex;
2822   if (strTabIndex >= SHN_LORESERVE) {
2823     sHdrs->sh_link = strTabIndex;
2824     eHdr->e_shstrndx = SHN_XINDEX;
2825   } else {
2826     eHdr->e_shstrndx = strTabIndex;
2827   }
2828 
2829   for (OutputSection *sec : outputSections)
2830     sec->writeHeaderTo<ELFT>(++sHdrs);
2831 }
2832 
2833 // Open a result file.
2834 template <class ELFT> void Writer<ELFT>::openFile() {
2835   uint64_t maxSize = config->is64 ? INT64_MAX : UINT32_MAX;
2836   if (fileSize != size_t(fileSize) || maxSize < fileSize) {
2837     std::string msg;
2838     raw_string_ostream s(msg);
2839     s << "output file too large: " << Twine(fileSize) << " bytes\n"
2840       << "section sizes:\n";
2841     for (OutputSection *os : outputSections)
2842       s << os->name << ' ' << os->size << "\n";
2843     error(s.str());
2844     return;
2845   }
2846 
2847   unlinkAsync(config->outputFile);
2848   unsigned flags = 0;
2849   if (!config->relocatable)
2850     flags |= FileOutputBuffer::F_executable;
2851   if (!config->mmapOutputFile)
2852     flags |= FileOutputBuffer::F_no_mmap;
2853   Expected<std::unique_ptr<FileOutputBuffer>> bufferOrErr =
2854       FileOutputBuffer::create(config->outputFile, fileSize, flags);
2855 
2856   if (!bufferOrErr) {
2857     error("failed to open " + config->outputFile + ": " +
2858           llvm::toString(bufferOrErr.takeError()));
2859     return;
2860   }
2861   buffer = std::move(*bufferOrErr);
2862   Out::bufferStart = buffer->getBufferStart();
2863 }
2864 
2865 template <class ELFT> void Writer<ELFT>::writeSectionsBinary() {
2866   for (OutputSection *sec : outputSections)
2867     if (sec->flags & SHF_ALLOC)
2868       sec->writeTo<ELFT>(Out::bufferStart + sec->offset);
2869 }
2870 
2871 static void fillTrap(uint8_t *i, uint8_t *end) {
2872   for (; i + 4 <= end; i += 4)
2873     memcpy(i, &target->trapInstr, 4);
2874 }
2875 
2876 // Fill the last page of executable segments with trap instructions
2877 // instead of leaving them as zero. Even though it is not required by any
2878 // standard, it is in general a good thing to do for security reasons.
2879 //
2880 // We'll leave other pages in segments as-is because the rest will be
2881 // overwritten by output sections.
2882 template <class ELFT> void Writer<ELFT>::writeTrapInstr() {
2883   for (Partition &part : partitions) {
2884     // Fill the last page.
2885     for (PhdrEntry *p : part.phdrs)
2886       if (p->p_type == PT_LOAD && (p->p_flags & PF_X))
2887         fillTrap(Out::bufferStart +
2888                      alignDown(p->firstSec->offset + p->p_filesz, 4),
2889                  Out::bufferStart +
2890                      alignToPowerOf2(p->firstSec->offset + p->p_filesz,
2891                                      config->maxPageSize));
2892 
2893     // Round up the file size of the last segment to the page boundary iff it is
2894     // an executable segment to ensure that other tools don't accidentally
2895     // trim the instruction padding (e.g. when stripping the file).
2896     PhdrEntry *last = nullptr;
2897     for (PhdrEntry *p : part.phdrs)
2898       if (p->p_type == PT_LOAD)
2899         last = p;
2900 
2901     if (last && (last->p_flags & PF_X))
2902       last->p_memsz = last->p_filesz =
2903           alignToPowerOf2(last->p_filesz, config->maxPageSize);
2904   }
2905 }
2906 
2907 // Write section contents to a mmap'ed file.
2908 template <class ELFT> void Writer<ELFT>::writeSections() {
2909   llvm::TimeTraceScope timeScope("Write sections");
2910 
2911   // In -r or --emit-relocs mode, write the relocation sections first as in
2912   // ELf_Rel targets we might find out that we need to modify the relocated
2913   // section while doing it.
2914   for (OutputSection *sec : outputSections)
2915     if (sec->type == SHT_REL || sec->type == SHT_RELA)
2916       sec->writeTo<ELFT>(Out::bufferStart + sec->offset);
2917 
2918   for (OutputSection *sec : outputSections)
2919     if (sec->type != SHT_REL && sec->type != SHT_RELA)
2920       sec->writeTo<ELFT>(Out::bufferStart + sec->offset);
2921 
2922   // Finally, check that all dynamic relocation addends were written correctly.
2923   if (config->checkDynamicRelocs && config->writeAddends) {
2924     for (OutputSection *sec : outputSections)
2925       if (sec->type == SHT_REL || sec->type == SHT_RELA)
2926         sec->checkDynRelAddends(Out::bufferStart);
2927   }
2928 }
2929 
2930 // Computes a hash value of Data using a given hash function.
2931 // In order to utilize multiple cores, we first split data into 1MB
2932 // chunks, compute a hash for each chunk, and then compute a hash value
2933 // of the hash values.
2934 static void
2935 computeHash(llvm::MutableArrayRef<uint8_t> hashBuf,
2936             llvm::ArrayRef<uint8_t> data,
2937             std::function<void(uint8_t *dest, ArrayRef<uint8_t> arr)> hashFn) {
2938   std::vector<ArrayRef<uint8_t>> chunks = split(data, 1024 * 1024);
2939   const size_t hashesSize = chunks.size() * hashBuf.size();
2940   std::unique_ptr<uint8_t[]> hashes(new uint8_t[hashesSize]);
2941 
2942   // Compute hash values.
2943   parallelFor(0, chunks.size(), [&](size_t i) {
2944     hashFn(hashes.get() + i * hashBuf.size(), chunks[i]);
2945   });
2946 
2947   // Write to the final output buffer.
2948   hashFn(hashBuf.data(), makeArrayRef(hashes.get(), hashesSize));
2949 }
2950 
2951 template <class ELFT> void Writer<ELFT>::writeBuildId() {
2952   if (!mainPart->buildId || !mainPart->buildId->getParent())
2953     return;
2954 
2955   if (config->buildId == BuildIdKind::Hexstring) {
2956     for (Partition &part : partitions)
2957       part.buildId->writeBuildId(config->buildIdVector);
2958     return;
2959   }
2960 
2961   // Compute a hash of all sections of the output file.
2962   size_t hashSize = mainPart->buildId->hashSize;
2963   std::unique_ptr<uint8_t[]> buildId(new uint8_t[hashSize]);
2964   MutableArrayRef<uint8_t> output(buildId.get(), hashSize);
2965   llvm::ArrayRef<uint8_t> input{Out::bufferStart, size_t(fileSize)};
2966 
2967   // Fedora introduced build ID as "approximation of true uniqueness across all
2968   // binaries that might be used by overlapping sets of people". It does not
2969   // need some security goals that some hash algorithms strive to provide, e.g.
2970   // (second-)preimage and collision resistance. In practice people use 'md5'
2971   // and 'sha1' just for different lengths. Implement them with the more
2972   // efficient BLAKE3.
2973   switch (config->buildId) {
2974   case BuildIdKind::Fast:
2975     computeHash(output, input, [](uint8_t *dest, ArrayRef<uint8_t> arr) {
2976       write64le(dest, xxHash64(arr));
2977     });
2978     break;
2979   case BuildIdKind::Md5:
2980     computeHash(output, input, [&](uint8_t *dest, ArrayRef<uint8_t> arr) {
2981       memcpy(dest, BLAKE3::hash<16>(arr).data(), hashSize);
2982     });
2983     break;
2984   case BuildIdKind::Sha1:
2985     computeHash(output, input, [&](uint8_t *dest, ArrayRef<uint8_t> arr) {
2986       memcpy(dest, BLAKE3::hash<20>(arr).data(), hashSize);
2987     });
2988     break;
2989   case BuildIdKind::Uuid:
2990     if (auto ec = llvm::getRandomBytes(buildId.get(), hashSize))
2991       error("entropy source failure: " + ec.message());
2992     break;
2993   default:
2994     llvm_unreachable("unknown BuildIdKind");
2995   }
2996   for (Partition &part : partitions)
2997     part.buildId->writeBuildId(output);
2998 }
2999 
3000 template void elf::createSyntheticSections<ELF32LE>();
3001 template void elf::createSyntheticSections<ELF32BE>();
3002 template void elf::createSyntheticSections<ELF64LE>();
3003 template void elf::createSyntheticSections<ELF64BE>();
3004 
3005 template void elf::writeResult<ELF32LE>();
3006 template void elf::writeResult<ELF32BE>();
3007 template void elf::writeResult<ELF64LE>();
3008 template void elf::writeResult<ELF64BE>();
3009