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