1	//===- LinkerScript.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	// This file contains the parser/evaluator of the linker script.
10	//
11	//===----------------------------------------------------------------------===//
12
13	#include "LinkerScript.h"
14	#include "Config.h"
15	#include "InputFiles.h"
16	#include "InputSection.h"
17	#include "OutputSections.h"
18	#include "SymbolTable.h"
19	#include "Symbols.h"
20	#include "SyntheticSections.h"
21	#include "Target.h"
22	#include "Writer.h"
23	#include "lld/Common/CommonLinkerContext.h"
24	#include "lld/Common/Strings.h"
25	#include "llvm/ADT/STLExtras.h"
26	#include "llvm/ADT/StringRef.h"
27	#include "llvm/BinaryFormat/ELF.h"
28	#include "llvm/Support/Casting.h"
29	#include "llvm/Support/Endian.h"
30	#include "llvm/Support/ErrorHandling.h"
31	#include "llvm/Support/TimeProfiler.h"
32	#include <algorithm>
33	#include <cassert>
34	#include <cstddef>
35	#include <cstdint>
36	#include <limits>
37	#include <string>
38	#include <vector>
39
40	using namespace llvm;
41	using namespace llvm::ELF;
42	using namespace llvm::object;
43	using namespace llvm::support::endian;
44	using namespace lld;
45	using namespace lld::elf;
46
47	std::unique_ptr<LinkerScript> elf::script;
48
49	static bool isSectionPrefix(StringRef prefix, StringRef name) {
50	return name.consume_front(Prefix: prefix) && (name.empty() || name[0] == '.');
51	}
52
53	static StringRef getOutputSectionName(const InputSectionBase *s) {
54	// This is for --emit-relocs and -r. If .text.foo is emitted as .text.bar, we
55	// want to emit .rela.text.foo as .rela.text.bar for consistency (this is not
56	// technically required, but not doing it is odd). This code guarantees that.
57	if (auto *isec = dyn_cast<InputSection>(Val: s)) {
58	if (InputSectionBase *rel = isec->getRelocatedSection()) {
59	OutputSection *out = rel->getOutputSection();
60	if (!out) {
61	assert(config->relocatable && (rel->flags & SHF_LINK_ORDER));
62	return s->name;
63	}
64	if (s->type == SHT_RELA)
65	return saver().save(S: ".rela" + out->name);
66	return saver().save(S: ".rel" + out->name);
67	}
68	}
69
70	if (config->relocatable)
71	return s->name;
72
73	// A BssSection created for a common symbol is identified as "COMMON" in
74	// linker scripts. It should go to .bss section.
75	if (s->name == "COMMON")
76	return ".bss";
77
78	if (script->hasSectionsCommand)
79	return s->name;
80
81	// When no SECTIONS is specified, emulate GNU ld's internal linker scripts
82	// by grouping sections with certain prefixes.
83
84	// GNU ld places text sections with prefix ".text.hot.", ".text.unknown.",
85	// ".text.unlikely.", ".text.startup." or ".text.exit." before others.
86	// We provide an option -z keep-text-section-prefix to group such sections
87	// into separate output sections. This is more flexible. See also
88	// sortISDBySectionOrder().
89	// ".text.unknown" means the hotness of the section is unknown. When
90	// SampleFDO is used, if a function doesn't have sample, it could be very
91	// cold or it could be a new function never being sampled. Those functions
92	// will be kept in the ".text.unknown" section.
93	// ".text.split." holds symbols which are split out from functions in other
94	// input sections. For example, with -fsplit-machine-functions, placing the
95	// cold parts in .text.split instead of .text.unlikely mitigates against poor
96	// profile inaccuracy. Techniques such as hugepage remapping can make
97	// conservative decisions at the section granularity.
98	if (isSectionPrefix(prefix: ".text", name: s->name)) {
99	if (config->zKeepTextSectionPrefix)
100	for (StringRef v : {".text.hot", ".text.unknown", ".text.unlikely",
101	".text.startup", ".text.exit", ".text.split"})
102	if (isSectionPrefix(prefix: v.substr(Start: 5), name: s->name.substr(Start: 5)))
103	return v;
104	return ".text";
105	}
106
107	for (StringRef v :
108	{".data.rel.ro", ".data", ".rodata", ".bss.rel.ro", ".bss", ".ldata",
109	".lrodata", ".lbss", ".gcc_except_table", ".init_array", ".fini_array",
110	".tbss", ".tdata", ".ARM.exidx", ".ARM.extab", ".ctors", ".dtors"})
111	if (isSectionPrefix(prefix: v, name: s->name))
112	return v;
113
114	return s->name;
115	}
116
117	uint64_t ExprValue::getValue() const {
118	if (sec)
119	return alignToPowerOf2(Value: sec->getOutputSection()->addr + sec->getOffset(offset: val),
120	Align: alignment);
121	return alignToPowerOf2(Value: val, Align: alignment);
122	}
123
124	uint64_t ExprValue::getSecAddr() const {
125	return sec ? sec->getOutputSection()->addr + sec->getOffset(offset: 0) : 0;
126	}
127
128	uint64_t ExprValue::getSectionOffset() const {
129	return getValue() - getSecAddr();
130	}
131
132	OutputDesc *LinkerScript::createOutputSection(StringRef name,
133	StringRef location) {
134	OutputDesc *&secRef = nameToOutputSection[CachedHashStringRef(name)];
135	OutputDesc *sec;
136	if (secRef && secRef->osec.location.empty()) {
137	// There was a forward reference.
138	sec = secRef;
139	} else {
140	sec = make<OutputDesc>(args&: name, args: SHT_PROGBITS, args: 0);
141	if (!secRef)
142	secRef = sec;
143	}
144	sec->osec.location = std::string(location);
145	return sec;
146	}
147
148	OutputDesc *LinkerScript::getOrCreateOutputSection(StringRef name) {
149	OutputDesc *&cmdRef = nameToOutputSection[CachedHashStringRef(name)];
150	if (!cmdRef)
151	cmdRef = make<OutputDesc>(args&: name, args: SHT_PROGBITS, args: 0);
152	return cmdRef;
153	}
154
155	// Expands the memory region by the specified size.
156	static void expandMemoryRegion(MemoryRegion *memRegion, uint64_t size,
157	StringRef secName) {
158	memRegion->curPos += size;
159	}
160
161	void LinkerScript::expandMemoryRegions(uint64_t size) {
162	if (state->memRegion)
163	expandMemoryRegion(memRegion: state->memRegion, size, secName: state->outSec->name);
164	// Only expand the LMARegion if it is different from memRegion.
165	if (state->lmaRegion && state->memRegion != state->lmaRegion)
166	expandMemoryRegion(memRegion: state->lmaRegion, size, secName: state->outSec->name);
167	}
168
169	void LinkerScript::expandOutputSection(uint64_t size) {
170	state->outSec->size += size;
171	expandMemoryRegions(size);
172	}
173
174	void LinkerScript::setDot(Expr e, const Twine &loc, bool inSec) {
175	uint64_t val = e().getValue();
176	// If val is smaller and we are in an output section, record the error and
177	// report it if this is the last assignAddresses iteration. dot may be smaller
178	// if there is another assignAddresses iteration.
179	if (val < dot && inSec) {
180	backwardDotErr =
181	(loc + ": unable to move location counter (0x" + Twine::utohexstr(Val: dot) +
182	") backward to 0x" + Twine::utohexstr(Val: val) + " for section '" +
183	state->outSec->name + "'")
184	.str();
185	}
186
187	// Update to location counter means update to section size.
188	if (inSec)
189	expandOutputSection(size: val - dot);
190
191	dot = val;
192	}
193
194	// Used for handling linker symbol assignments, for both finalizing
195	// their values and doing early declarations. Returns true if symbol
196	// should be defined from linker script.
197	static bool shouldDefineSym(SymbolAssignment *cmd) {
198	if (cmd->name == ".")
199	return false;
200
201	return !cmd->provide || LinkerScript::shouldAddProvideSym(symName: cmd->name);
202	}
203
204	// Called by processSymbolAssignments() to assign definitions to
205	// linker-script-defined symbols.
206	void LinkerScript::addSymbol(SymbolAssignment *cmd) {
207	if (!shouldDefineSym(cmd))
208	return;
209
210	// Define a symbol.
211	ExprValue value = cmd->expression();
212	SectionBase *sec = value.isAbsolute() ? nullptr : value.sec;
213	uint8_t visibility = cmd->hidden ? STV_HIDDEN : STV_DEFAULT;
214
215	// When this function is called, section addresses have not been
216	// fixed yet. So, we may or may not know the value of the RHS
217	// expression.
218	//
219	// For example, if an expression is `x = 42`, we know x is always 42.
220	// However, if an expression is `x = .`, there's no way to know its
221	// value at the moment.
222	//
223	// We want to set symbol values early if we can. This allows us to
224	// use symbols as variables in linker scripts. Doing so allows us to
225	// write expressions like this: `alignment = 16; . = ALIGN(., alignment)`.
226	uint64_t symValue = value.sec ? 0 : value.getValue();
227
228	Defined newSym(createInternalFile(name: cmd->location), cmd->name, STB_GLOBAL,
229	visibility, value.type, symValue, 0, sec);
230
231	Symbol *sym = symtab.insert(name: cmd->name);
232	sym->mergeProperties(other: newSym);
233	newSym.overwrite(sym&: *sym);
234	sym->isUsedInRegularObj = true;
235	cmd->sym = cast<Defined>(Val: sym);
236	}
237
238	// This function is called from LinkerScript::declareSymbols.
239	// It creates a placeholder symbol if needed.
240	static void declareSymbol(SymbolAssignment *cmd) {
241	if (!shouldDefineSym(cmd))
242	return;
243
244	uint8_t visibility = cmd->hidden ? STV_HIDDEN : STV_DEFAULT;
245	Defined newSym(ctx.internalFile, cmd->name, STB_GLOBAL, visibility,
246	STT_NOTYPE, 0, 0, nullptr);
247
248	// If the symbol is already defined, its order is 0 (with absence indicating
249	// 0); otherwise it's assigned the order of the SymbolAssignment.
250	Symbol *sym = symtab.insert(name: cmd->name);
251	if (!sym->isDefined())
252	ctx.scriptSymOrder.insert(KV: {sym, cmd->symOrder});
253
254	// We can't calculate final value right now.
255	sym->mergeProperties(other: newSym);
256	newSym.overwrite(sym&: *sym);
257
258	cmd->sym = cast<Defined>(Val: sym);
259	cmd->provide = false;
260	sym->isUsedInRegularObj = true;
261	sym->scriptDefined = true;
262	}
263
264	using SymbolAssignmentMap =
265	DenseMap<const Defined *, std::pair<SectionBase *, uint64_t>>;
266
267	// Collect section/value pairs of linker-script-defined symbols. This is used to
268	// check whether symbol values converge.
269	static SymbolAssignmentMap
270	getSymbolAssignmentValues(ArrayRef<SectionCommand *> sectionCommands) {
271	SymbolAssignmentMap ret;
272	for (SectionCommand *cmd : sectionCommands) {
273	if (auto *assign = dyn_cast<SymbolAssignment>(Val: cmd)) {
274	if (assign->sym) // sym is nullptr for dot.
275	ret.try_emplace(Key: assign->sym, Args: std::make_pair(x&: assign->sym->section,
276	y&: assign->sym->value));
277	continue;
278	}
279	for (SectionCommand *subCmd : cast<OutputDesc>(Val: cmd)->osec.commands)
280	if (auto *assign = dyn_cast<SymbolAssignment>(Val: subCmd))
281	if (assign->sym)
282	ret.try_emplace(Key: assign->sym, Args: std::make_pair(x&: assign->sym->section,
283	y&: assign->sym->value));
284	}
285	return ret;
286	}
287
288	// Returns the lexicographical smallest (for determinism) Defined whose
289	// section/value has changed.
290	static const Defined *
291	getChangedSymbolAssignment(const SymbolAssignmentMap &oldValues) {
292	const Defined *changed = nullptr;
293	for (auto &it : oldValues) {
294	const Defined *sym = it.first;
295	if (std::make_pair(x: sym->section, y: sym->value) != it.second &&
296	(!changed || sym->getName() < changed->getName()))
297	changed = sym;
298	}
299	return changed;
300	}
301
302	// Process INSERT [AFTER|BEFORE] commands. For each command, we move the
303	// specified output section to the designated place.
304	void LinkerScript::processInsertCommands() {
305	SmallVector<OutputDesc *, 0> moves;
306	for (const InsertCommand &cmd : insertCommands) {
307	for (StringRef name : cmd.names) {
308	// If base is empty, it may have been discarded by
309	// adjustOutputSections(). We do not handle such output sections.
310	auto from = llvm::find_if(Range&: sectionCommands, P: [&](SectionCommand *subCmd) {
311	return isa<OutputDesc>(Val: subCmd) &&
312	cast<OutputDesc>(Val: subCmd)->osec.name == name;
313	});
314	if (from == sectionCommands.end())
315	continue;
316	moves.push_back(Elt: cast<OutputDesc>(Val: *from));
317	sectionCommands.erase(CI: from);
318	}
319
320	auto insertPos =
321	llvm::find_if(Range&: sectionCommands, P: [&cmd](SectionCommand *subCmd) {
322	auto *to = dyn_cast<OutputDesc>(Val: subCmd);
323	return to != nullptr && to->osec.name == cmd.where;
324	});
325	if (insertPos == sectionCommands.end()) {
326	error(msg: "unable to insert " + cmd.names[0] +
327	(cmd.isAfter ? " after " : " before ") + cmd.where);
328	} else {
329	if (cmd.isAfter)
330	++insertPos;
331	sectionCommands.insert(I: insertPos, From: moves.begin(), To: moves.end());
332	}
333	moves.clear();
334	}
335	}
336
337	// Symbols defined in script should not be inlined by LTO. At the same time
338	// we don't know their final values until late stages of link. Here we scan
339	// over symbol assignment commands and create placeholder symbols if needed.
340	void LinkerScript::declareSymbols() {
341	assert(!state);
342	for (SectionCommand *cmd : sectionCommands) {
343	if (auto *assign = dyn_cast<SymbolAssignment>(Val: cmd)) {
344	declareSymbol(cmd: assign);
345	continue;
346	}
347
348	// If the output section directive has constraints,
349	// we can't say for sure if it is going to be included or not.
350	// Skip such sections for now. Improve the checks if we ever
351	// need symbols from that sections to be declared early.
352	const OutputSection &sec = cast<OutputDesc>(Val: cmd)->osec;
353	if (sec.constraint != ConstraintKind::NoConstraint)
354	continue;
355	for (SectionCommand *cmd : sec.commands)
356	if (auto *assign = dyn_cast<SymbolAssignment>(Val: cmd))
357	declareSymbol(cmd: assign);
358	}
359	}
360
361	// This function is called from assignAddresses, while we are
362	// fixing the output section addresses. This function is supposed
363	// to set the final value for a given symbol assignment.
364	void LinkerScript::assignSymbol(SymbolAssignment *cmd, bool inSec) {
365	if (cmd->name == ".") {
366	setDot(e: cmd->expression, loc: cmd->location, inSec);
367	return;
368	}
369
370	if (!cmd->sym)
371	return;
372
373	ExprValue v = cmd->expression();
374	if (v.isAbsolute()) {
375	cmd->sym->section = nullptr;
376	cmd->sym->value = v.getValue();
377	} else {
378	cmd->sym->section = v.sec;
379	cmd->sym->value = v.getSectionOffset();
380	}
381	cmd->sym->type = v.type;
382	}
383
384	static inline StringRef getFilename(const InputFile *file) {
385	return file ? file->getNameForScript() : StringRef();
386	}
387
388	bool InputSectionDescription::matchesFile(const InputFile *file) const {
389	if (filePat.isTrivialMatchAll())
390	return true;
391
392	if (!matchesFileCache || matchesFileCache->first != file)
393	matchesFileCache.emplace(args&: file, args: filePat.match(s: getFilename(file)));
394
395	return matchesFileCache->second;
396	}
397
398	bool SectionPattern::excludesFile(const InputFile *file) const {
399	if (excludedFilePat.empty())
400	return false;
401
402	if (!excludesFileCache || excludesFileCache->first != file)
403	excludesFileCache.emplace(args&: file, args: excludedFilePat.match(s: getFilename(file)));
404
405	return excludesFileCache->second;
406	}
407
408	bool LinkerScript::shouldKeep(InputSectionBase *s) {
409	for (InputSectionDescription *id : keptSections)
410	if (id->matchesFile(file: s->file))
411	for (SectionPattern &p : id->sectionPatterns)
412	if (p.sectionPat.match(s: s->name) &&
413	(s->flags & id->withFlags) == id->withFlags &&
414	(s->flags & id->withoutFlags) == 0)
415	return true;
416	return false;
417	}
418
419	// A helper function for the SORT() command.
420	static bool matchConstraints(ArrayRef<InputSectionBase *> sections,
421	ConstraintKind kind) {
422	if (kind == ConstraintKind::NoConstraint)
423	return true;
424
425	bool isRW = llvm::any_of(
426	Range&: sections, P: [](InputSectionBase *sec) { return sec->flags & SHF_WRITE; });
427
428	return (isRW && kind == ConstraintKind::ReadWrite) ||
429	(!isRW && kind == ConstraintKind::ReadOnly);
430	}
431
432	static void sortSections(MutableArrayRef<InputSectionBase *> vec,
433	SortSectionPolicy k) {
434	auto alignmentComparator = [](InputSectionBase *a, InputSectionBase *b) {
435	// ">" is not a mistake. Sections with larger alignments are placed
436	// before sections with smaller alignments in order to reduce the
437	// amount of padding necessary. This is compatible with GNU.
438	return a->addralign > b->addralign;
439	};
440	auto nameComparator = [](InputSectionBase *a, InputSectionBase *b) {
441	return a->name < b->name;
442	};
443	auto priorityComparator = [](InputSectionBase *a, InputSectionBase *b) {
444	return getPriority(s: a->name) < getPriority(s: b->name);
445	};
446
447	switch (k) {
448	case SortSectionPolicy::Default:
449	case SortSectionPolicy::None:
450	return;
451	case SortSectionPolicy::Alignment:
452	return llvm::stable_sort(Range&: vec, C: alignmentComparator);
453	case SortSectionPolicy::Name:
454	return llvm::stable_sort(Range&: vec, C: nameComparator);
455	case SortSectionPolicy::Priority:
456	return llvm::stable_sort(Range&: vec, C: priorityComparator);
457	case SortSectionPolicy::Reverse:
458	return std::reverse(first: vec.begin(), last: vec.end());
459	}
460	}
461
462	// Sort sections as instructed by SORT-family commands and --sort-section
463	// option. Because SORT-family commands can be nested at most two depth
464	// (e.g. SORT_BY_NAME(SORT_BY_ALIGNMENT(.text.*))) and because the command
465	// line option is respected even if a SORT command is given, the exact
466	// behavior we have here is a bit complicated. Here are the rules.
467	//
468	// 1. If two SORT commands are given, --sort-section is ignored.
469	// 2. If one SORT command is given, and if it is not SORT_NONE,
470	// --sort-section is handled as an inner SORT command.
471	// 3. If one SORT command is given, and if it is SORT_NONE, don't sort.
472	// 4. If no SORT command is given, sort according to --sort-section.
473	static void sortInputSections(MutableArrayRef<InputSectionBase *> vec,
474	SortSectionPolicy outer,
475	SortSectionPolicy inner) {
476	if (outer == SortSectionPolicy::None)
477	return;
478
479	if (inner == SortSectionPolicy::Default)
480	sortSections(vec, k: config->sortSection);
481	else
482	sortSections(vec, k: inner);
483	sortSections(vec, k: outer);
484	}
485
486	// Compute and remember which sections the InputSectionDescription matches.
487	SmallVector<InputSectionBase *, 0>
488	LinkerScript::computeInputSections(const InputSectionDescription *cmd,
489	ArrayRef<InputSectionBase *> sections) {
490	SmallVector<InputSectionBase *, 0> ret;
491	SmallVector<size_t, 0> indexes;
492	DenseSet<size_t> seen;
493	auto sortByPositionThenCommandLine = [&](size_t begin, size_t end) {
494	llvm::sort(C: MutableArrayRef<size_t>(indexes).slice(N: begin, M: end - begin));
495	for (size_t i = begin; i != end; ++i)
496	ret[i] = sections[indexes[i]];
497	sortInputSections(
498	vec: MutableArrayRef<InputSectionBase *>(ret).slice(N: begin, M: end - begin),
499	outer: config->sortSection, inner: SortSectionPolicy::None);
500	};
501
502	// Collects all sections that satisfy constraints of Cmd.
503	size_t sizeAfterPrevSort = 0;
504	for (const SectionPattern &pat : cmd->sectionPatterns) {
505	size_t sizeBeforeCurrPat = ret.size();
506
507	for (size_t i = 0, e = sections.size(); i != e; ++i) {
508	// Skip if the section is dead or has been matched by a previous input
509	// section description or a previous pattern.
510	InputSectionBase *sec = sections[i];
511	if (!sec->isLive() || sec->parent || seen.contains(V: i))
512	continue;
513
514	// For --emit-relocs we have to ignore entries like
515	// .rela.dyn : { *(.rela.data) }
516	// which are common because they are in the default bfd script.
517	// We do not ignore SHT_REL[A] linker-synthesized sections here because
518	// want to support scripts that do custom layout for them.
519	if (isa<InputSection>(Val: sec) &&
520	cast<InputSection>(Val: sec)->getRelocatedSection())
521	continue;
522
523	// Check the name early to improve performance in the common case.
524	if (!pat.sectionPat.match(s: sec->name))
525	continue;
526
527	if (!cmd->matchesFile(file: sec->file) || pat.excludesFile(file: sec->file) ||
528	(sec->flags & cmd->withFlags) != cmd->withFlags ||
529	(sec->flags & cmd->withoutFlags) != 0)
530	continue;
531
532	ret.push_back(Elt: sec);
533	indexes.push_back(Elt: i);
534	seen.insert(V: i);
535	}
536
537	if (pat.sortOuter == SortSectionPolicy::Default)
538	continue;
539
540	// Matched sections are ordered by radix sort with the keys being (SORT*,
541	// --sort-section, input order), where SORT* (if present) is most
542	// significant.
543	//
544	// Matched sections between the previous SORT* and this SORT* are sorted by
545	// (--sort-alignment, input order).
546	sortByPositionThenCommandLine(sizeAfterPrevSort, sizeBeforeCurrPat);
547	// Matched sections by this SORT* pattern are sorted using all 3 keys.
548	// ret[sizeBeforeCurrPat,ret.size()) are already in the input order, so we
549	// just sort by sortOuter and sortInner.
550	sortInputSections(
551	vec: MutableArrayRef<InputSectionBase *>(ret).slice(N: sizeBeforeCurrPat),
552	outer: pat.sortOuter, inner: pat.sortInner);
553	sizeAfterPrevSort = ret.size();
554	}
555	// Matched sections after the last SORT* are sorted by (--sort-alignment,
556	// input order).
557	sortByPositionThenCommandLine(sizeAfterPrevSort, ret.size());
558	return ret;
559	}
560
561	void LinkerScript::discard(InputSectionBase &s) {
562	if (&s == in.shStrTab.get())
563	error(msg: "discarding " + s.name + " section is not allowed");
564
565	s.markDead();
566	s.parent = nullptr;
567	for (InputSection *sec : s.dependentSections)
568	discard(s&: *sec);
569	}
570
571	void LinkerScript::discardSynthetic(OutputSection &outCmd) {
572	for (Partition &part : partitions) {
573	if (!part.armExidx || !part.armExidx->isLive())
574	continue;
575	SmallVector<InputSectionBase *, 0> secs(
576	part.armExidx->exidxSections.begin(),
577	part.armExidx->exidxSections.end());
578	for (SectionCommand *cmd : outCmd.commands)
579	if (auto *isd = dyn_cast<InputSectionDescription>(Val: cmd))
580	for (InputSectionBase *s : computeInputSections(cmd: isd, sections: secs))
581	discard(s&: *s);
582	}
583	}
584
585	SmallVector<InputSectionBase *, 0>
586	LinkerScript::createInputSectionList(OutputSection &outCmd) {
587	SmallVector<InputSectionBase *, 0> ret;
588
589	for (SectionCommand *cmd : outCmd.commands) {
590	if (auto *isd = dyn_cast<InputSectionDescription>(Val: cmd)) {
591	isd->sectionBases = computeInputSections(cmd: isd, sections: ctx.inputSections);
592	for (InputSectionBase *s : isd->sectionBases)
593	s->parent = &outCmd;
594	ret.insert(I: ret.end(), From: isd->sectionBases.begin(), To: isd->sectionBases.end());
595	}
596	}
597	return ret;
598	}
599
600	// Create output sections described by SECTIONS commands.
601	void LinkerScript::processSectionCommands() {
602	auto process = [this](OutputSection *osec) {
603	SmallVector<InputSectionBase *, 0> v = createInputSectionList(outCmd&: *osec);
604
605	// The output section name `/DISCARD/' is special.
606	// Any input section assigned to it is discarded.
607	if (osec->name == "/DISCARD/") {
608	for (InputSectionBase *s : v)
609	discard(s&: *s);
610	discardSynthetic(outCmd&: *osec);
611	osec->commands.clear();
612	return false;
613	}
614
615	// This is for ONLY_IF_RO and ONLY_IF_RW. An output section directive
616	// ".foo : ONLY_IF_R[OW] { ... }" is handled only if all member input
617	// sections satisfy a given constraint. If not, a directive is handled
618	// as if it wasn't present from the beginning.
619	//
620	// Because we'll iterate over SectionCommands many more times, the easy
621	// way to "make it as if it wasn't present" is to make it empty.
622	if (!matchConstraints(sections: v, kind: osec->constraint)) {
623	for (InputSectionBase *s : v)
624	s->parent = nullptr;
625	osec->commands.clear();
626	return false;
627	}
628
629	// Handle subalign (e.g. ".foo : SUBALIGN(32) { ... }"). If subalign
630	// is given, input sections are aligned to that value, whether the
631	// given value is larger or smaller than the original section alignment.
632	if (osec->subalignExpr) {
633	uint32_t subalign = osec->subalignExpr().getValue();
634	for (InputSectionBase *s : v)
635	s->addralign = subalign;
636	}
637
638	// Set the partition field the same way OutputSection::recordSection()
639	// does. Partitions cannot be used with the SECTIONS command, so this is
640	// always 1.
641	osec->partition = 1;
642	return true;
643	};
644
645	// Process OVERWRITE_SECTIONS first so that it can overwrite the main script
646	// or orphans.
647	DenseMap<CachedHashStringRef, OutputDesc *> map;
648	size_t i = 0;
649	for (OutputDesc *osd : overwriteSections) {
650	OutputSection *osec = &osd->osec;
651	if (process(osec) &&
652	!map.try_emplace(Key: CachedHashStringRef(osec->name), Args&: osd).second)
653	warn(msg: "OVERWRITE_SECTIONS specifies duplicate " + osec->name);
654	}
655	for (SectionCommand *&base : sectionCommands)
656	if (auto *osd = dyn_cast<OutputDesc>(Val: base)) {
657	OutputSection *osec = &osd->osec;
658	if (OutputDesc *overwrite = map.lookup(Val: CachedHashStringRef(osec->name))) {
659	log(msg: overwrite->osec.location + " overwrites " + osec->name);
660	overwrite->osec.sectionIndex = i++;
661	base = overwrite;
662	} else if (process(osec)) {
663	osec->sectionIndex = i++;
664	}
665	}
666
667	// If an OVERWRITE_SECTIONS specified output section is not in
668	// sectionCommands, append it to the end. The section will be inserted by
669	// orphan placement.
670	for (OutputDesc *osd : overwriteSections)
671	if (osd->osec.partition == 1 && osd->osec.sectionIndex == UINT32_MAX)
672	sectionCommands.push_back(Elt: osd);
673	}
674
675	void LinkerScript::processSymbolAssignments() {
676	// Dot outside an output section still represents a relative address, whose
677	// sh_shndx should not be SHN_UNDEF or SHN_ABS. Create a dummy aether section
678	// that fills the void outside a section. It has an index of one, which is
679	// indistinguishable from any other regular section index.
680	aether = make<OutputSection>(args: "", args: 0, args: SHF_ALLOC);
681	aether->sectionIndex = 1;
682
683	// `st` captures the local AddressState and makes it accessible deliberately.
684	// This is needed as there are some cases where we cannot just thread the
685	// current state through to a lambda function created by the script parser.
686	AddressState st;
687	state = &st;
688	st.outSec = aether;
689
690	for (SectionCommand *cmd : sectionCommands) {
691	if (auto *assign = dyn_cast<SymbolAssignment>(Val: cmd))
692	addSymbol(cmd: assign);
693	else
694	for (SectionCommand *subCmd : cast<OutputDesc>(Val: cmd)->osec.commands)
695	if (auto *assign = dyn_cast<SymbolAssignment>(Val: subCmd))
696	addSymbol(cmd: assign);
697	}
698
699	state = nullptr;
700	}
701
702	static OutputSection *findByName(ArrayRef<SectionCommand *> vec,
703	StringRef name) {
704	for (SectionCommand *cmd : vec)
705	if (auto *osd = dyn_cast<OutputDesc>(Val: cmd))
706	if (osd->osec.name == name)
707	return &osd->osec;
708	return nullptr;
709	}
710
711	static OutputDesc *createSection(InputSectionBase *isec, StringRef outsecName) {
712	OutputDesc *osd = script->createOutputSection(name: outsecName, location: "<internal>");
713	osd->osec.recordSection(isec);
714	return osd;
715	}
716
717	static OutputDesc *addInputSec(StringMap<TinyPtrVector<OutputSection *>> &map,
718	InputSectionBase *isec, StringRef outsecName) {
719	// Sections with SHT_GROUP or SHF_GROUP attributes reach here only when the -r
720	// option is given. A section with SHT_GROUP defines a "section group", and
721	// its members have SHF_GROUP attribute. Usually these flags have already been
722	// stripped by InputFiles.cpp as section groups are processed and uniquified.
723	// However, for the -r option, we want to pass through all section groups
724	// as-is because adding/removing members or merging them with other groups
725	// change their semantics.
726	if (isec->type == SHT_GROUP || (isec->flags & SHF_GROUP))
727	return createSection(isec, outsecName);
728
729	// Imagine .zed : { *(.foo) *(.bar) } script. Both foo and bar may have
730	// relocation sections .rela.foo and .rela.bar for example. Most tools do
731	// not allow multiple REL[A] sections for output section. Hence we
732	// should combine these relocation sections into single output.
733	// We skip synthetic sections because it can be .rela.dyn/.rela.plt or any
734	// other REL[A] sections created by linker itself.
735	if (!isa<SyntheticSection>(Val: isec) && isStaticRelSecType(type: isec->type)) {
736	auto *sec = cast<InputSection>(Val: isec);
737	OutputSection *out = sec->getRelocatedSection()->getOutputSection();
738
739	if (auto *relSec = out->relocationSection) {
740	relSec->recordSection(isec: sec);
741	return nullptr;
742	}
743
744	OutputDesc *osd = createSection(isec, outsecName);
745	out->relocationSection = &osd->osec;
746	return osd;
747	}
748
749	// The ELF spec just says
750	// ----------------------------------------------------------------
751	// In the first phase, input sections that match in name, type and
752	// attribute flags should be concatenated into single sections.
753	// ----------------------------------------------------------------
754	//
755	// However, it is clear that at least some flags have to be ignored for
756	// section merging. At the very least SHF_GROUP and SHF_COMPRESSED have to be
757	// ignored. We should not have two output .text sections just because one was
758	// in a group and another was not for example.
759	//
760	// It also seems that wording was a late addition and didn't get the
761	// necessary scrutiny.
762	//
763	// Merging sections with different flags is expected by some users. One
764	// reason is that if one file has
765	//
766	// int *const bar __attribute__((section(".foo"))) = (int *)0;
767	//
768	// gcc with -fPIC will produce a read only .foo section. But if another
769	// file has
770	//
771	// int zed;
772	// int *const bar __attribute__((section(".foo"))) = (int *)&zed;
773	//
774	// gcc with -fPIC will produce a read write section.
775	//
776	// Last but not least, when using linker script the merge rules are forced by
777	// the script. Unfortunately, linker scripts are name based. This means that
778	// expressions like *(.foo*) can refer to multiple input sections with
779	// different flags. We cannot put them in different output sections or we
780	// would produce wrong results for
781	//
782	// start = .; *(.foo.*) end = .; *(.bar)
783	//
784	// and a mapping of .foo1 and .bar1 to one section and .foo2 and .bar2 to
785	// another. The problem is that there is no way to layout those output
786	// sections such that the .foo sections are the only thing between the start
787	// and end symbols.
788	//
789	// Given the above issues, we instead merge sections by name and error on
790	// incompatible types and flags.
791	TinyPtrVector<OutputSection *> &v = map[outsecName];
792	for (OutputSection *sec : v) {
793	if (sec->partition != isec->partition)
794	continue;
795
796	if (config->relocatable && (isec->flags & SHF_LINK_ORDER)) {
797	// Merging two SHF_LINK_ORDER sections with different sh_link fields will
798	// change their semantics, so we only merge them in -r links if they will
799	// end up being linked to the same output section. The casts are fine
800	// because everything in the map was created by the orphan placement code.
801	auto *firstIsec = cast<InputSectionBase>(
802	Val: cast<InputSectionDescription>(Val: sec->commands[0])->sectionBases[0]);
803	OutputSection *firstIsecOut =
804	firstIsec->flags & SHF_LINK_ORDER
805	? firstIsec->getLinkOrderDep()->getOutputSection()
806	: nullptr;
807	if (firstIsecOut != isec->getLinkOrderDep()->getOutputSection())
808	continue;
809	}
810
811	sec->recordSection(isec);
812	return nullptr;
813	}
814
815	OutputDesc *osd = createSection(isec, outsecName);
816	v.push_back(NewVal: &osd->osec);
817	return osd;
818	}
819
820	// Add sections that didn't match any sections command.
821	void LinkerScript::addOrphanSections() {
822	StringMap<TinyPtrVector<OutputSection *>> map;
823	SmallVector<OutputDesc *, 0> v;
824
825	auto add = [&](InputSectionBase *s) {
826	if (s->isLive() && !s->parent) {
827	orphanSections.push_back(Elt: s);
828
829	StringRef name = getOutputSectionName(s);
830	if (config->unique) {
831	v.push_back(Elt: createSection(isec: s, outsecName: name));
832	} else if (OutputSection *sec = findByName(vec: sectionCommands, name)) {
833	sec->recordSection(isec: s);
834	} else {
835	if (OutputDesc *osd = addInputSec(map, isec: s, outsecName: name))
836	v.push_back(Elt: osd);
837	assert(isa<MergeInputSection>(s) ||
838	s->getOutputSection()->sectionIndex == UINT32_MAX);
839	}
840	}
841	};
842
843	// For further --emit-reloc handling code we need target output section
844	// to be created before we create relocation output section, so we want
845	// to create target sections first. We do not want priority handling
846	// for synthetic sections because them are special.
847	size_t n = 0;
848	for (InputSectionBase *isec : ctx.inputSections) {
849	// Process InputSection and MergeInputSection.
850	if (LLVM_LIKELY(isa<InputSection>(isec)))
851	ctx.inputSections[n++] = isec;
852
853	// In -r links, SHF_LINK_ORDER sections are added while adding their parent
854	// sections because we need to know the parent's output section before we
855	// can select an output section for the SHF_LINK_ORDER section.
856	if (config->relocatable && (isec->flags & SHF_LINK_ORDER))
857	continue;
858
859	if (auto *sec = dyn_cast<InputSection>(Val: isec))
860	if (InputSectionBase *rel = sec->getRelocatedSection())
861	if (auto *relIS = dyn_cast_or_null<InputSectionBase>(Val: rel->parent))
862	add(relIS);
863	add(isec);
864	if (config->relocatable)
865	for (InputSectionBase *depSec : isec->dependentSections)
866	if (depSec->flags & SHF_LINK_ORDER)
867	add(depSec);
868	}
869	// Keep just InputSection.
870	ctx.inputSections.resize(N: n);
871
872	// If no SECTIONS command was given, we should insert sections commands
873	// before others, so that we can handle scripts which refers them,
874	// for example: "foo = ABSOLUTE(ADDR(.text)));".
875	// When SECTIONS command is present we just add all orphans to the end.
876	if (hasSectionsCommand)
877	sectionCommands.insert(I: sectionCommands.end(), From: v.begin(), To: v.end());
878	else
879	sectionCommands.insert(I: sectionCommands.begin(), From: v.begin(), To: v.end());
880	}
881
882	void LinkerScript::diagnoseOrphanHandling() const {
883	llvm::TimeTraceScope timeScope("Diagnose orphan sections");
884	if (config->orphanHandling == OrphanHandlingPolicy::Place)
885	return;
886	for (const InputSectionBase *sec : orphanSections) {
887	// .relro_padding is inserted before DATA_SEGMENT_RELRO_END, if present,
888	// automatically. The section is not supposed to be specified by scripts.
889	if (sec == in.relroPadding.get())
890	continue;
891	// Input SHT_REL[A] retained by --emit-relocs are ignored by
892	// computeInputSections(). Don't warn/error.
893	if (isa<InputSection>(Val: sec) &&
894	cast<InputSection>(Val: sec)->getRelocatedSection())
895	continue;
896
897	StringRef name = getOutputSectionName(s: sec);
898	if (config->orphanHandling == OrphanHandlingPolicy::Error)
899	error(msg: toString(sec) + " is being placed in '" + name + "'");
900	else
901	warn(msg: toString(sec) + " is being placed in '" + name + "'");
902	}
903	}
904
905	void LinkerScript::diagnoseMissingSGSectionAddress() const {
906	if (!config->cmseImplib || !in.armCmseSGSection->isNeeded())
907	return;
908
909	OutputSection *sec = findByName(vec: sectionCommands, name: ".gnu.sgstubs");
910	if (sec && !sec->addrExpr && !config->sectionStartMap.count(Key: ".gnu.sgstubs"))
911	error(msg: "no address assigned to the veneers output section " + sec->name);
912	}
913
914	// This function searches for a memory region to place the given output
915	// section in. If found, a pointer to the appropriate memory region is
916	// returned in the first member of the pair. Otherwise, a nullptr is returned.
917	// The second member of the pair is a hint that should be passed to the
918	// subsequent call of this method.
919	std::pair<MemoryRegion *, MemoryRegion *>
920	LinkerScript::findMemoryRegion(OutputSection *sec, MemoryRegion *hint) {
921	// Non-allocatable sections are not part of the process image.
922	if (!(sec->flags & SHF_ALLOC)) {
923	bool hasInputOrByteCommand =
924	sec->hasInputSections ||
925	llvm::any_of(Range&: sec->commands, P: [](SectionCommand *comm) {
926	return ByteCommand::classof(c: comm);
927	});
928	if (!sec->memoryRegionName.empty() && hasInputOrByteCommand)
929	warn(msg: "ignoring memory region assignment for non-allocatable section '" +
930	sec->name + "'");
931	return {nullptr, nullptr};
932	}
933
934	// If a memory region name was specified in the output section command,
935	// then try to find that region first.
936	if (!sec->memoryRegionName.empty()) {
937	if (MemoryRegion *m = memoryRegions.lookup(Key: sec->memoryRegionName))
938	return {m, m};
939	error(msg: "memory region '" + sec->memoryRegionName + "' not declared");
940	return {nullptr, nullptr};
941	}
942
943	// If at least one memory region is defined, all sections must
944	// belong to some memory region. Otherwise, we don't need to do
945	// anything for memory regions.
946	if (memoryRegions.empty())
947	return {nullptr, nullptr};
948
949	// An orphan section should continue the previous memory region.
950	if (sec->sectionIndex == UINT32_MAX && hint)
951	return {hint, hint};
952
953	// See if a region can be found by matching section flags.
954	for (auto &pair : memoryRegions) {
955	MemoryRegion *m = pair.second;
956	if (m->compatibleWith(secFlags: sec->flags))
957	return {m, nullptr};
958	}
959
960	// Otherwise, no suitable region was found.
961	error(msg: "no memory region specified for section '" + sec->name + "'");
962	return {nullptr, nullptr};
963	}
964
965	static OutputSection *findFirstSection(PhdrEntry *load) {
966	for (OutputSection *sec : outputSections)
967	if (sec->ptLoad == load)
968	return sec;
969	return nullptr;
970	}
971
972	// This function assigns offsets to input sections and an output section
973	// for a single sections command (e.g. ".text { *(.text); }").
974	void LinkerScript::assignOffsets(OutputSection *sec) {
975	const bool isTbss = (sec->flags & SHF_TLS) && sec->type == SHT_NOBITS;
976	const bool sameMemRegion = state->memRegion == sec->memRegion;
977	const bool prevLMARegionIsDefault = state->lmaRegion == nullptr;
978	const uint64_t savedDot = dot;
979	state->memRegion = sec->memRegion;
980	state->lmaRegion = sec->lmaRegion;
981
982	if (!(sec->flags & SHF_ALLOC)) {
983	// Non-SHF_ALLOC sections have zero addresses.
984	dot = 0;
985	} else if (isTbss) {
986	// Allow consecutive SHF_TLS SHT_NOBITS output sections. The address range
987	// starts from the end address of the previous tbss section.
988	if (state->tbssAddr == 0)
989	state->tbssAddr = dot;
990	else
991	dot = state->tbssAddr;
992	} else {
993	if (state->memRegion)
994	dot = state->memRegion->curPos;
995	if (sec->addrExpr)
996	setDot(e: sec->addrExpr, loc: sec->location, inSec: false);
997
998	// If the address of the section has been moved forward by an explicit
999	// expression so that it now starts past the current curPos of the enclosing
1000	// region, we need to expand the current region to account for the space
1001	// between the previous section, if any, and the start of this section.
1002	if (state->memRegion && state->memRegion->curPos < dot)
1003	expandMemoryRegion(memRegion: state->memRegion, size: dot - state->memRegion->curPos,
1004	secName: sec->name);
1005	}
1006
1007	state->outSec = sec;
1008	if (sec->addrExpr && script->hasSectionsCommand) {
1009	// The alignment is ignored.
1010	sec->addr = dot;
1011	} else {
1012	// sec->alignment is the max of ALIGN and the maximum of input
1013	// section alignments.
1014	const uint64_t pos = dot;
1015	dot = alignToPowerOf2(Value: dot, Align: sec->addralign);
1016	sec->addr = dot;
1017	expandMemoryRegions(size: dot - pos);
1018	}
1019
1020	// state->lmaOffset is LMA minus VMA. If LMA is explicitly specified via AT()
1021	// or AT>, recompute state->lmaOffset; otherwise, if both previous/current LMA
1022	// region is the default, and the two sections are in the same memory region,
1023	// reuse previous lmaOffset; otherwise, reset lmaOffset to 0. This emulates
1024	// heuristics described in
1025	// https://sourceware.org/binutils/docs/ld/Output-Section-LMA.html
1026	if (sec->lmaExpr) {
1027	state->lmaOffset = sec->lmaExpr().getValue() - dot;
1028	} else if (MemoryRegion *mr = sec->lmaRegion) {
1029	uint64_t lmaStart = alignToPowerOf2(Value: mr->curPos, Align: sec->addralign);
1030	if (mr->curPos < lmaStart)
1031	expandMemoryRegion(memRegion: mr, size: lmaStart - mr->curPos, secName: sec->name);
1032	state->lmaOffset = lmaStart - dot;
1033	} else if (!sameMemRegion || !prevLMARegionIsDefault) {
1034	state->lmaOffset = 0;
1035	}
1036
1037	// Propagate state->lmaOffset to the first "non-header" section.
1038	if (PhdrEntry *l = sec->ptLoad)
1039	if (sec == findFirstSection(load: l))
1040	l->lmaOffset = state->lmaOffset;
1041
1042	// We can call this method multiple times during the creation of
1043	// thunks and want to start over calculation each time.
1044	sec->size = 0;
1045
1046	// We visited SectionsCommands from processSectionCommands to
1047	// layout sections. Now, we visit SectionsCommands again to fix
1048	// section offsets.
1049	for (SectionCommand *cmd : sec->commands) {
1050	// This handles the assignments to symbol or to the dot.
1051	if (auto *assign = dyn_cast<SymbolAssignment>(Val: cmd)) {
1052	assign->addr = dot;
1053	assignSymbol(cmd: assign, inSec: true);
1054	assign->size = dot - assign->addr;
1055	continue;
1056	}
1057
1058	// Handle BYTE(), SHORT(), LONG(), or QUAD().
1059	if (auto *data = dyn_cast<ByteCommand>(Val: cmd)) {
1060	data->offset = dot - sec->addr;
1061	dot += data->size;
1062	expandOutputSection(size: data->size);
1063	continue;
1064	}
1065
1066	// Handle a single input section description command.
1067	// It calculates and assigns the offsets for each section and also
1068	// updates the output section size.
1069	for (InputSection *isec : cast<InputSectionDescription>(Val: cmd)->sections) {
1070	assert(isec->getParent() == sec);
1071	const uint64_t pos = dot;
1072	dot = alignToPowerOf2(Value: dot, Align: isec->addralign);
1073	isec->outSecOff = dot - sec->addr;
1074	dot += isec->getSize();
1075
1076	// Update output section size after adding each section. This is so that
1077	// SIZEOF works correctly in the case below:
1078	// .foo { *(.aaa) a = SIZEOF(.foo); *(.bbb) }
1079	expandOutputSection(size: dot - pos);
1080	}
1081	}
1082
1083	// If .relro_padding is present, round up the end to a common-page-size
1084	// boundary to protect the last page.
1085	if (in.relroPadding && sec == in.relroPadding->getParent())
1086	expandOutputSection(size: alignToPowerOf2(Value: dot, Align: config->commonPageSize) - dot);
1087
1088	// Non-SHF_ALLOC sections do not affect the addresses of other OutputSections
1089	// as they are not part of the process image.
1090	if (!(sec->flags & SHF_ALLOC)) {
1091	dot = savedDot;
1092	} else if (isTbss) {
1093	// NOBITS TLS sections are similar. Additionally save the end address.
1094	state->tbssAddr = dot;
1095	dot = savedDot;
1096	}
1097	}
1098
1099	static bool isDiscardable(const OutputSection &sec) {
1100	if (sec.name == "/DISCARD/")
1101	return true;
1102
1103	// We do not want to remove OutputSections with expressions that reference
1104	// symbols even if the OutputSection is empty. We want to ensure that the
1105	// expressions can be evaluated and report an error if they cannot.
1106	if (sec.expressionsUseSymbols)
1107	return false;
1108
1109	// OutputSections may be referenced by name in ADDR and LOADADDR expressions,
1110	// as an empty Section can has a valid VMA and LMA we keep the OutputSection
1111	// to maintain the integrity of the other Expression.
1112	if (sec.usedInExpression)
1113	return false;
1114
1115	for (SectionCommand *cmd : sec.commands) {
1116	if (auto assign = dyn_cast<SymbolAssignment>(Val: cmd))
1117	// Don't create empty output sections just for unreferenced PROVIDE
1118	// symbols.
1119	if (assign->name != "." && !assign->sym)
1120	continue;
1121
1122	if (!isa<InputSectionDescription>(Val: *cmd))
1123	return false;
1124	}
1125	return true;
1126	}
1127
1128	bool LinkerScript::isDiscarded(const OutputSection *sec) const {
1129	return hasSectionsCommand && (getFirstInputSection(os: sec) == nullptr) &&
1130	isDiscardable(sec: *sec);
1131	}
1132
1133	static void maybePropagatePhdrs(OutputSection &sec,
1134	SmallVector<StringRef, 0> &phdrs) {
1135	if (sec.phdrs.empty()) {
1136	// To match the bfd linker script behaviour, only propagate program
1137	// headers to sections that are allocated.
1138	if (sec.flags & SHF_ALLOC)
1139	sec.phdrs = phdrs;
1140	} else {
1141	phdrs = sec.phdrs;
1142	}
1143	}
1144
1145	void LinkerScript::adjustOutputSections() {
1146	// If the output section contains only symbol assignments, create a
1147	// corresponding output section. The issue is what to do with linker script
1148	// like ".foo : { symbol = 42; }". One option would be to convert it to
1149	// "symbol = 42;". That is, move the symbol out of the empty section
1150	// description. That seems to be what bfd does for this simple case. The
1151	// problem is that this is not completely general. bfd will give up and
1152	// create a dummy section too if there is a ". = . + 1" inside the section
1153	// for example.
1154	// Given that we want to create the section, we have to worry what impact
1155	// it will have on the link. For example, if we just create a section with
1156	// 0 for flags, it would change which PT_LOADs are created.
1157	// We could remember that particular section is dummy and ignore it in
1158	// other parts of the linker, but unfortunately there are quite a few places
1159	// that would need to change:
1160	// * The program header creation.
1161	// * The orphan section placement.
1162	// * The address assignment.
1163	// The other option is to pick flags that minimize the impact the section
1164	// will have on the rest of the linker. That is why we copy the flags from
1165	// the previous sections. We copy just SHF_ALLOC and SHF_WRITE to keep the
1166	// impact low. We do not propagate SHF_EXECINSTR as in some cases this can
1167	// lead to executable writeable section.
1168	uint64_t flags = SHF_ALLOC;
1169
1170	SmallVector<StringRef, 0> defPhdrs;
1171	bool seenRelro = false;
1172	for (SectionCommand *&cmd : sectionCommands) {
1173	if (!isa<OutputDesc>(Val: cmd))
1174	continue;
1175	auto *sec = &cast<OutputDesc>(Val: cmd)->osec;
1176
1177	// Handle align (e.g. ".foo : ALIGN(16) { ... }").
1178	if (sec->alignExpr)
1179	sec->addralign =
1180	std::max<uint32_t>(a: sec->addralign, b: sec->alignExpr().getValue());
1181
1182	bool isEmpty = (getFirstInputSection(os: sec) == nullptr);
1183	bool discardable = isEmpty && isDiscardable(sec: *sec);
1184	// If sec has at least one input section and not discarded, remember its
1185	// flags to be inherited by subsequent output sections. (sec may contain
1186	// just one empty synthetic section.)
1187	if (sec->hasInputSections && !discardable)
1188	flags = sec->flags;
1189
1190	// We do not want to keep any special flags for output section
1191	// in case it is empty.
1192	if (isEmpty)
1193	sec->flags =
1194	flags & ((sec->nonAlloc ? 0 : (uint64_t)SHF_ALLOC) | SHF_WRITE);
1195
1196	// The code below may remove empty output sections. We should save the
1197	// specified program headers (if exist) and propagate them to subsequent
1198	// sections which do not specify program headers.
1199	// An example of such a linker script is:
1200	// SECTIONS { .empty : { *(.empty) } :rw
1201	// .foo : { *(.foo) } }
1202	// Note: at this point the order of output sections has not been finalized,
1203	// because orphans have not been inserted into their expected positions. We
1204	// will handle them in adjustSectionsAfterSorting().
1205	if (sec->sectionIndex != UINT32_MAX)
1206	maybePropagatePhdrs(sec&: *sec, phdrs&: defPhdrs);
1207
1208	// Discard .relro_padding if we have not seen one RELRO section. Note: when
1209	// .tbss is the only RELRO section, there is no associated PT_LOAD segment
1210	// (needsPtLoad), so we don't append .relro_padding in the case.
1211	if (in.relroPadding && in.relroPadding->getParent() == sec && !seenRelro)
1212	discardable = true;
1213	if (discardable) {
1214	sec->markDead();
1215	cmd = nullptr;
1216	} else {
1217	seenRelro |=
1218	sec->relro && !(sec->type == SHT_NOBITS && (sec->flags & SHF_TLS));
1219	}
1220	}
1221
1222	// It is common practice to use very generic linker scripts. So for any
1223	// given run some of the output sections in the script will be empty.
1224	// We could create corresponding empty output sections, but that would
1225	// clutter the output.
1226	// We instead remove trivially empty sections. The bfd linker seems even
1227	// more aggressive at removing them.
1228	llvm::erase_if(C&: sectionCommands, P: [&](SectionCommand *cmd) { return !cmd; });
1229	}
1230
1231	void LinkerScript::adjustSectionsAfterSorting() {
1232	// Try and find an appropriate memory region to assign offsets in.
1233	MemoryRegion *hint = nullptr;
1234	for (SectionCommand *cmd : sectionCommands) {
1235	if (auto *osd = dyn_cast<OutputDesc>(Val: cmd)) {
1236	OutputSection *sec = &osd->osec;
1237	if (!sec->lmaRegionName.empty()) {
1238	if (MemoryRegion *m = memoryRegions.lookup(Key: sec->lmaRegionName))
1239	sec->lmaRegion = m;
1240	else
1241	error(msg: "memory region '" + sec->lmaRegionName + "' not declared");
1242	}
1243	std::tie(args&: sec->memRegion, args&: hint) = findMemoryRegion(sec, hint);
1244	}
1245	}
1246
1247	// If output section command doesn't specify any segments,
1248	// and we haven't previously assigned any section to segment,
1249	// then we simply assign section to the very first load segment.
1250	// Below is an example of such linker script:
1251	// PHDRS { seg PT_LOAD; }
1252	// SECTIONS { .aaa : { *(.aaa) } }
1253	SmallVector<StringRef, 0> defPhdrs;
1254	auto firstPtLoad = llvm::find_if(Range&: phdrsCommands, P: [](const PhdrsCommand &cmd) {
1255	return cmd.type == PT_LOAD;
1256	});
1257	if (firstPtLoad != phdrsCommands.end())
1258	defPhdrs.push_back(Elt: firstPtLoad->name);
1259
1260	// Walk the commands and propagate the program headers to commands that don't
1261	// explicitly specify them.
1262	for (SectionCommand *cmd : sectionCommands)
1263	if (auto *osd = dyn_cast<OutputDesc>(Val: cmd))
1264	maybePropagatePhdrs(sec&: osd->osec, phdrs&: defPhdrs);
1265	}
1266
1267	static uint64_t computeBase(uint64_t min, bool allocateHeaders) {
1268	// If there is no SECTIONS or if the linkerscript is explicit about program
1269	// headers, do our best to allocate them.
1270	if (!script->hasSectionsCommand || allocateHeaders)
1271	return 0;
1272	// Otherwise only allocate program headers if that would not add a page.
1273	return alignDown(Value: min, Align: config->maxPageSize);
1274	}
1275
1276	// When the SECTIONS command is used, try to find an address for the file and
1277	// program headers output sections, which can be added to the first PT_LOAD
1278	// segment when program headers are created.
1279	//
1280	// We check if the headers fit below the first allocated section. If there isn't
1281	// enough space for these sections, we'll remove them from the PT_LOAD segment,
1282	// and we'll also remove the PT_PHDR segment.
1283	void LinkerScript::allocateHeaders(SmallVector<PhdrEntry *, 0> &phdrs) {
1284	uint64_t min = std::numeric_limits<uint64_t>::max();
1285	for (OutputSection *sec : outputSections)
1286	if (sec->flags & SHF_ALLOC)
1287	min = std::min<uint64_t>(a: min, b: sec->addr);
1288
1289	auto it = llvm::find_if(
1290	Range&: phdrs, P: [](const PhdrEntry *e) { return e->p_type == PT_LOAD; });
1291	if (it == phdrs.end())
1292	return;
1293	PhdrEntry *firstPTLoad = *it;
1294
1295	bool hasExplicitHeaders =
1296	llvm::any_of(Range&: phdrsCommands, P: [](const PhdrsCommand &cmd) {
1297	return cmd.hasPhdrs || cmd.hasFilehdr;
1298	});
1299	bool paged = !config->omagic && !config->nmagic;
1300	uint64_t headerSize = getHeaderSize();
1301	if ((paged || hasExplicitHeaders) &&
1302	headerSize <= min - computeBase(min, allocateHeaders: hasExplicitHeaders)) {
1303	min = alignDown(Value: min - headerSize, Align: config->maxPageSize);
1304	Out::elfHeader->addr = min;
1305	Out::programHeaders->addr = min + Out::elfHeader->size;
1306	return;
1307	}
1308
1309	// Error if we were explicitly asked to allocate headers.
1310	if (hasExplicitHeaders)
1311	error(msg: "could not allocate headers");
1312
1313	Out::elfHeader->ptLoad = nullptr;
1314	Out::programHeaders->ptLoad = nullptr;
1315	firstPTLoad->firstSec = findFirstSection(load: firstPTLoad);
1316
1317	llvm::erase_if(C&: phdrs,
1318	P: [](const PhdrEntry *e) { return e->p_type == PT_PHDR; });
1319	}
1320
1321	LinkerScript::AddressState::AddressState() {
1322	for (auto &mri : script->memoryRegions) {
1323	MemoryRegion *mr = mri.second;
1324	mr->curPos = (mr->origin)().getValue();
1325	}
1326	}
1327
1328	// Here we assign addresses as instructed by linker script SECTIONS
1329	// sub-commands. Doing that allows us to use final VA values, so here
1330	// we also handle rest commands like symbol assignments and ASSERTs.
1331	// Returns a symbol that has changed its section or value, or nullptr if no
1332	// symbol has changed.
1333	const Defined *LinkerScript::assignAddresses() {
1334	if (script->hasSectionsCommand) {
1335	// With a linker script, assignment of addresses to headers is covered by
1336	// allocateHeaders().
1337	dot = config->imageBase.value_or(u: 0);
1338	} else {
1339	// Assign addresses to headers right now.
1340	dot = target->getImageBase();
1341	Out::elfHeader->addr = dot;
1342	Out::programHeaders->addr = dot + Out::elfHeader->size;
1343	dot += getHeaderSize();
1344	}
1345
1346	AddressState st;
1347	state = &st;
1348	errorOnMissingSection = true;
1349	st.outSec = aether;
1350	backwardDotErr.clear();
1351
1352	SymbolAssignmentMap oldValues = getSymbolAssignmentValues(sectionCommands);
1353	for (SectionCommand *cmd : sectionCommands) {
1354	if (auto *assign = dyn_cast<SymbolAssignment>(Val: cmd)) {
1355	assign->addr = dot;
1356	assignSymbol(cmd: assign, inSec: false);
1357	assign->size = dot - assign->addr;
1358	continue;
1359	}
1360	assignOffsets(sec: &cast<OutputDesc>(Val: cmd)->osec);
1361	}
1362
1363	state = nullptr;
1364	return getChangedSymbolAssignment(oldValues);
1365	}
1366
1367	// Creates program headers as instructed by PHDRS linker script command.
1368	SmallVector<PhdrEntry *, 0> LinkerScript::createPhdrs() {
1369	SmallVector<PhdrEntry *, 0> ret;
1370
1371	// Process PHDRS and FILEHDR keywords because they are not
1372	// real output sections and cannot be added in the following loop.
1373	for (const PhdrsCommand &cmd : phdrsCommands) {
1374	PhdrEntry *phdr = make<PhdrEntry>(args: cmd.type, args: cmd.flags.value_or(u: PF_R));
1375
1376	if (cmd.hasFilehdr)
1377	phdr->add(sec: Out::elfHeader);
1378	if (cmd.hasPhdrs)
1379	phdr->add(sec: Out::programHeaders);
1380
1381	if (cmd.lmaExpr) {
1382	phdr->p_paddr = cmd.lmaExpr().getValue();
1383	phdr->hasLMA = true;
1384	}
1385	ret.push_back(Elt: phdr);
1386	}
1387
1388	// Add output sections to program headers.
1389	for (OutputSection *sec : outputSections) {
1390	// Assign headers specified by linker script
1391	for (size_t id : getPhdrIndices(sec)) {
1392	ret[id]->add(sec);
1393	if (!phdrsCommands[id].flags)
1394	ret[id]->p_flags |= sec->getPhdrFlags();
1395	}
1396	}
1397	return ret;
1398	}
1399
1400	// Returns true if we should emit an .interp section.
1401	//
1402	// We usually do. But if PHDRS commands are given, and
1403	// no PT_INTERP is there, there's no place to emit an
1404	// .interp, so we don't do that in that case.
1405	bool LinkerScript::needsInterpSection() {
1406	if (phdrsCommands.empty())
1407	return true;
1408	for (PhdrsCommand &cmd : phdrsCommands)
1409	if (cmd.type == PT_INTERP)
1410	return true;
1411	return false;
1412	}
1413
1414	ExprValue LinkerScript::getSymbolValue(StringRef name, const Twine &loc) {
1415	if (name == ".") {
1416	if (state)
1417	return {state->outSec, false, dot - state->outSec->addr, loc};
1418	error(msg: loc + ": unable to get location counter value");
1419	return 0;
1420	}
1421
1422	if (Symbol *sym = symtab.find(name)) {
1423	if (auto *ds = dyn_cast<Defined>(Val: sym)) {
1424	ExprValue v{ds->section, false, ds->value, loc};
1425	// Retain the original st_type, so that the alias will get the same
1426	// behavior in relocation processing. Any operation will reset st_type to
1427	// STT_NOTYPE.
1428	v.type = ds->type;
1429	return v;
1430	}
1431	if (isa<SharedSymbol>(Val: sym))
1432	if (!errorOnMissingSection)
1433	return {nullptr, false, 0, loc};
1434	}
1435
1436	error(msg: loc + ": symbol not found: " + name);
1437	return 0;
1438	}
1439
1440	// Returns the index of the segment named Name.
1441	static std::optional<size_t> getPhdrIndex(ArrayRef<PhdrsCommand> vec,
1442	StringRef name) {
1443	for (size_t i = 0; i < vec.size(); ++i)
1444	if (vec[i].name == name)
1445	return i;
1446	return std::nullopt;
1447	}
1448
1449	// Returns indices of ELF headers containing specific section. Each index is a
1450	// zero based number of ELF header listed within PHDRS {} script block.
1451	SmallVector<size_t, 0> LinkerScript::getPhdrIndices(OutputSection *cmd) {
1452	SmallVector<size_t, 0> ret;
1453
1454	for (StringRef s : cmd->phdrs) {
1455	if (std::optional<size_t> idx = getPhdrIndex(vec: phdrsCommands, name: s))
1456	ret.push_back(Elt: *idx);
1457	else if (s != "NONE")
1458	error(msg: cmd->location + ": program header '" + s +
1459	"' is not listed in PHDRS");
1460	}
1461	return ret;
1462	}
1463
1464	void LinkerScript::printMemoryUsage(raw_ostream& os) {
1465	auto printSize = [&](uint64_t size) {
1466	if ((size & 0x3fffffff) == 0)
1467	os << format_decimal(N: size >> 30, Width: 10) << " GB";
1468	else if ((size & 0xfffff) == 0)
1469	os << format_decimal(N: size >> 20, Width: 10) << " MB";
1470	else if ((size & 0x3ff) == 0)
1471	os << format_decimal(N: size >> 10, Width: 10) << " KB";
1472	else
1473	os << " " << format_decimal(N: size, Width: 10) << " B";
1474	};
1475	os << "Memory region Used Size Region Size %age Used\n";
1476	for (auto &pair : memoryRegions) {
1477	MemoryRegion *m = pair.second;
1478	uint64_t usedLength = m->curPos - m->getOrigin();
1479	os << right_justify(Str: m->name, Width: 16) << ": ";
1480	printSize(usedLength);
1481	uint64_t length = m->getLength();
1482	if (length != 0) {
1483	printSize(length);
1484	double percent = usedLength * 100.0 / length;
1485	os << " " << format(Fmt: "%6.2f%%", Vals: percent);
1486	}
1487	os << '\n';
1488	}
1489	}
1490
1491	static void checkMemoryRegion(const MemoryRegion *region,
1492	const OutputSection *osec, uint64_t addr) {
1493	uint64_t osecEnd = addr + osec->size;
1494	uint64_t regionEnd = region->getOrigin() + region->getLength();
1495	if (osecEnd > regionEnd) {
1496	error(msg: "section '" + osec->name + "' will not fit in region '" +
1497	region->name + "': overflowed by " + Twine(osecEnd - regionEnd) +
1498	" bytes");
1499	}
1500	}
1501
1502	void LinkerScript::checkFinalScriptConditions() const {
1503	if (backwardDotErr.size())
1504	errorOrWarn(msg: backwardDotErr);
1505	for (const OutputSection *sec : outputSections) {
1506	if (const MemoryRegion *memoryRegion = sec->memRegion)
1507	checkMemoryRegion(region: memoryRegion, osec: sec, addr: sec->addr);
1508	if (const MemoryRegion *lmaRegion = sec->lmaRegion)
1509	checkMemoryRegion(region: lmaRegion, osec: sec, addr: sec->getLMA());
1510	}
1511	}
1512
1513	void LinkerScript::addScriptReferencedSymbolsToSymTable() {
1514	// Some symbols (such as __ehdr_start) are defined lazily only when there
1515	// are undefined symbols for them, so we add these to trigger that logic.
1516	auto reference = [](StringRef name) {
1517	Symbol *sym = symtab.addUnusedUndefined(name);
1518	sym->isUsedInRegularObj = true;
1519	sym->referenced = true;
1520	};
1521	for (StringRef name : referencedSymbols)
1522	reference(name);
1523
1524	// Keeps track of references from which PROVIDE symbols have been added to the
1525	// symbol table.
1526	DenseSet<StringRef> added;
1527	SmallVector<const SmallVector<StringRef, 0> *, 0> symRefsVec;
1528	for (const auto &[name, symRefs] : provideMap)
1529	if (LinkerScript::shouldAddProvideSym(symName: name) && added.insert(V: name).second)
1530	symRefsVec.push_back(Elt: &symRefs);
1531	while (symRefsVec.size()) {
1532	for (StringRef name : *symRefsVec.pop_back_val()) {
1533	reference(name);
1534	// Prevent the symbol from being discarded by --gc-sections.
1535	script->referencedSymbols.push_back(Elt: name);
1536	auto it = script->provideMap.find(Key: name);
1537	if (it != script->provideMap.end() &&
1538	LinkerScript::shouldAddProvideSym(symName: name) &&
1539	added.insert(V: name).second) {
1540	symRefsVec.push_back(Elt: &it->second);
1541	}
1542	}
1543	}
1544	}
1545
1546	bool LinkerScript::shouldAddProvideSym(StringRef symName) {
1547	Symbol *sym = symtab.find(name: symName);
1548	return sym && !sym->isDefined() && !sym->isCommon();
1549	}
1550