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/ErrorHandling.h"
30#include "llvm/Support/TimeProfiler.h"
31#include <algorithm>
32#include <cassert>
33#include <cstddef>
34#include <cstdint>
35#include <limits>
36#include <string>
37
38using namespace llvm;
39using namespace llvm::ELF;
40using namespace llvm::object;
41using namespace llvm::support::endian;
42using namespace lld;
43using namespace lld::elf;
44
45static bool isSectionPrefix(StringRef prefix, StringRef name) {
46 return name.consume_front(Prefix: prefix) && (name.empty() || name[0] == '.');
47}
48
49StringRef LinkerScript::getOutputSectionName(const InputSectionBase *s) const {
50 // This is for --emit-relocs and -r. If .text.foo is emitted as .text.bar, we
51 // want to emit .rela.text.foo as .rela.text.bar for consistency (this is not
52 // technically required, but not doing it is odd). This code guarantees that.
53 if (LLVM_UNLIKELY(ctx.arg.copyRelocs)) {
54 InputSectionBase *rel = nullptr;
55 if (auto *isec = dyn_cast<InputSection>(Val: s))
56 rel = isec->getRelocatedSection();
57 if (rel) {
58 OutputSection *out = rel->getOutputSection();
59 if (!out) {
60 assert(ctx.arg.relocatable && (rel->flags & SHF_LINK_ORDER));
61 return s->name;
62 }
63 StringSaver &ss = ctx.saver;
64 if (s->type == SHT_CREL)
65 return ss.save(S: ".crel" + out->name);
66 if (s->type == SHT_RELA)
67 return ss.save(S: ".rela" + out->name);
68 return ss.save(S: ".rel" + out->name);
69 }
70 // Use default LLD behavior for the embedded unoptimized dynamic debugging
71 // relocatable link.
72 if (ctx.arg.relocatable && !ctx.dynDbgRelocatable)
73 return s->name;
74 }
75
76 // A BssSection created for a common symbol is identified as "COMMON" in
77 // linker scripts. It should go to .bss section.
78 if (s->name == "COMMON")
79 return ".bss";
80
81 if (hasSectionsCommand)
82 return s->name;
83
84 // When no SECTIONS is specified, emulate GNU ld's internal linker scripts
85 // by grouping sections with certain prefixes.
86
87 // GNU ld places text sections with prefix ".text.hot.", ".text.unknown.",
88 // ".text.unlikely.", ".text.startup." or ".text.exit." before others.
89 // We provide an option -z keep-text-section-prefix to group such sections
90 // into separate output sections. This is more flexible. See also
91 // sortISDBySectionOrder().
92 // ".text.unknown" means the hotness of the section is unknown. When
93 // SampleFDO is used, if a function doesn't have sample, it could be very
94 // cold or it could be a new function never being sampled. Those functions
95 // will be kept in the ".text.unknown" section.
96 // ".text.split." holds symbols which are split out from functions in other
97 // input sections. For example, with -fsplit-machine-functions, placing the
98 // cold parts in .text.split instead of .text.unlikely mitigates against poor
99 // profile inaccuracy. Techniques such as hugepage remapping can make
100 // conservative decisions at the section granularity.
101 if (isSectionPrefix(prefix: ".text", name: s->name)) {
102 if (ctx.arg.zKeepTextSectionPrefix)
103 for (StringRef v : {".text.hot", ".text.unknown", ".text.unlikely",
104 ".text.startup", ".text.exit", ".text.split"})
105 if (isSectionPrefix(prefix: v.substr(Start: 5), name: s->name.substr(Start: 5)))
106 return v;
107 return ".text";
108 }
109 if (isSectionPrefix(prefix: ".ltext", name: s->name)) {
110 if (ctx.arg.zKeepTextSectionPrefix)
111 for (StringRef v : {".ltext.hot", ".ltext.unknown", ".ltext.unlikely",
112 ".ltext.startup", ".ltext.exit", ".ltext.split"})
113 if (isSectionPrefix(prefix: v.substr(Start: 6), name: s->name.substr(Start: 6)))
114 return v;
115 return ".ltext";
116 }
117
118 // When zKeepDataSectionPrefix is true, keep .hot and .unlikely suffixes
119 // in data sections.
120 static constexpr StringRef dataSectionPrefixes[] = {
121 ".data.rel.ro", ".data", ".rodata", ".bss.rel.ro", ".bss",
122 };
123
124 // If keep-data-section-prefix is enabled, map hot-prefixed data sections
125 // to a .hot variant in the output and map unlikely-prefixed data sections
126 // to a .unlikely variant. Mapping for the hot input sections is illustrated
127 // below, and the same applies for unlikely ones.
128 // [bar] is a placeholder to represent optional global variable name below
129 // - .data.rel.ro.hot.[bar] => .data.rel.ro.hot
130 // - .data.hot.[bar] => .data.hot
131 // - {.rodata.hot.[bar], .rodata.str.*.hot., .rodata.cst*.hot.} => .rodata.hot
132 // - .bss.rel.ro => .bss.rel.ro
133 // - .bss.hot.[bar] => .bss.hot
134 // Note .bss.rel.ro doesn't have hot / unlikely mapping. It's placed before
135 // .bss so they get processed before `.bss` prefix is seen, just like
136 // how `.data.rel.ro` should be processed before seeing the `.data` prefix.
137 if (ctx.arg.zKeepDataSectionPrefix)
138 for (auto [index, v] : llvm::enumerate(First: dataSectionPrefixes)) {
139 StringRef secName = s->name;
140 // If v is the prefix, trim it from secName. Otherwise just continue to
141 // try the next prefix.
142 if (!secName.consume_front(Prefix: v))
143 continue;
144
145 // Object file writer emits the trailing dot in `.hot.` and `.unlikely.`
146 // to disambiguate between `.<section>.<variable-name>` (without trailing
147 // dot) and `.<section>.hot.[optional-variable-name]`. We check the same
148 // (trailing dot required) to not map a C variable named `unlikely` to a
149 // unlikely variant.
150 if (secName.starts_with(Prefix: ".hot."))
151 return s->name.substr(Start: 0, N: v.size() + 4);
152 if (secName.starts_with(Prefix: ".unlikely."))
153 return s->name.substr(Start: 0, N: v.size() + 9);
154 if (index == 2) {
155 // Place input .rodata.str<N>.hot. or .rodata.cst<N>.hot. into the
156 // .rodata.hot section.
157 if (s->name.ends_with(Suffix: ".hot."))
158 return ".rodata.hot";
159 // Place input .rodata.str<N>.hot. or .rodata.cst<N>.unlikely. into
160 // the .rodata.unlikely section.
161 if (s->name.ends_with(Suffix: ".unlikely."))
162 return ".rodata.unlikely";
163 }
164 }
165
166 for (StringRef v : {".data.rel.ro", ".data", ".rodata",
167 ".bss.rel.ro", ".bss", ".ldata",
168 ".lrodata", ".lbss", ".gcc_except_table",
169 ".init_array", ".fini_array", ".tbss",
170 ".tdata", ".ARM.exidx", ".ARM.extab",
171 ".ctors", ".dtors", ".sbss",
172 ".sdata", ".srodata", ".gnu.build.attributes"})
173 if (isSectionPrefix(prefix: v, name: s->name))
174 return v;
175
176 return s->name;
177}
178
179uint64_t ExprValue::getValue() const {
180 if (sec)
181 return alignToPowerOf2(Value: sec->getOutputSection()->addr + sec->getOffset(offset: val),
182 Align: alignment);
183 return alignToPowerOf2(Value: val, Align: alignment);
184}
185
186uint64_t ExprValue::getSecAddr() const {
187 return sec ? sec->getOutputSection()->addr + sec->getOffset(offset: 0) : 0;
188}
189
190uint64_t ExprValue::getSectionOffset() const {
191 return getValue() - getSecAddr();
192}
193
194// std::unique_ptr<OutputSection> may be incomplete type.
195LinkerScript::LinkerScript(Ctx &ctx) : ctx(ctx) {}
196LinkerScript::~LinkerScript() {}
197
198OutputDesc *LinkerScript::createOutputSection(StringRef name,
199 StringRef location) {
200 OutputDesc *&secRef = nameToOutputSection[CachedHashStringRef(name)];
201 OutputDesc *sec;
202 if (secRef && secRef->osec.location.empty()) {
203 // There was a forward reference.
204 sec = secRef;
205 } else {
206 descPool.emplace_back(
207 Args: std::make_unique<OutputDesc>(args&: ctx, args&: name, args: SHT_PROGBITS, args: 0));
208 sec = descPool.back().get();
209 if (!secRef)
210 secRef = sec;
211 }
212 sec->osec.location = std::string(location);
213 return sec;
214}
215
216OutputDesc *LinkerScript::getOrCreateOutputSection(StringRef name) {
217 auto &secRef = nameToOutputSection[CachedHashStringRef(name)];
218 if (!secRef) {
219 secRef = descPool
220 .emplace_back(
221 Args: std::make_unique<OutputDesc>(args&: ctx, args&: name, args: SHT_PROGBITS, args: 0))
222 .get();
223 }
224 return secRef;
225}
226
227// Expands the memory region by the specified size.
228static void expandMemoryRegion(MemoryRegion *memRegion, uint64_t size,
229 StringRef secName) {
230 memRegion->curPos += size;
231}
232
233void LinkerScript::expandMemoryRegions(uint64_t size) {
234 if (state->memRegion)
235 expandMemoryRegion(memRegion: state->memRegion, size, secName: state->outSec->name);
236 // Only expand the LMARegion if it is different from memRegion.
237 if (state->lmaRegion && state->memRegion != state->lmaRegion)
238 expandMemoryRegion(memRegion: state->lmaRegion, size, secName: state->outSec->name);
239}
240
241void LinkerScript::expandOutputSection(uint64_t size) {
242 state->outSec->size += size;
243 size_t regionSize = size;
244 if (state->outSec->inOverlay) {
245 // Expand the overlay if necessary, and expand the region by the
246 // corresponding amount.
247 if (state->outSec->size > state->overlaySize) {
248 regionSize = state->outSec->size - state->overlaySize;
249 state->overlaySize = state->outSec->size;
250 } else {
251 regionSize = 0;
252 }
253 }
254 expandMemoryRegions(size: regionSize);
255}
256
257void LinkerScript::setDot(Expr e, const Twine &loc, bool inSec) {
258 uint64_t val = e().getValue();
259 // If val is smaller and we are in an output section, record the error and
260 // report it if this is the last assignAddresses iteration. dot may be smaller
261 // if there is another assignAddresses iteration.
262 if (val < dot && inSec) {
263 recordError(msg: loc + ": unable to move location counter (0x" +
264 Twine::utohexstr(Val: dot) + ") backward to 0x" +
265 Twine::utohexstr(Val: val) + " for section '" + state->outSec->name +
266 "'");
267 }
268
269 // Update to location counter means update to section size.
270 if (inSec)
271 expandOutputSection(size: val - dot);
272
273 dot = val;
274}
275
276// Used for handling linker symbol assignments, for both finalizing
277// their values and doing early declarations. Returns true if symbol
278// should be defined from linker script.
279static bool shouldDefineSym(Ctx &ctx, SymbolAssignment *cmd) {
280 if (cmd->name == ".")
281 return false;
282
283 return !cmd->provide || ctx.script->shouldAddProvideSym(symName: cmd->name);
284}
285
286// Called by processSymbolAssignments() to assign definitions to
287// linker-script-defined symbols.
288void LinkerScript::addSymbol(SymbolAssignment *cmd) {
289 if (!shouldDefineSym(ctx, cmd))
290 return;
291
292 // Define a symbol.
293 ExprValue value = cmd->expression();
294 SectionBase *sec = value.isAbsolute() ? nullptr : value.sec;
295 uint8_t visibility = cmd->hidden ? STV_HIDDEN : STV_DEFAULT;
296
297 // When this function is called, section addresses have not been
298 // fixed yet. So, we may or may not know the value of the RHS
299 // expression.
300 //
301 // For example, if an expression is `x = 42`, we know x is always 42.
302 // However, if an expression is `x = .`, there's no way to know its
303 // value at the moment.
304 //
305 // We want to set symbol values early if we can. This allows us to
306 // use symbols as variables in linker scripts. Doing so allows us to
307 // write expressions like this: `alignment = 16; . = ALIGN(., alignment)`.
308 uint64_t symValue = value.sec ? 0 : value.getValue();
309
310 Defined newSym(ctx, createInternalFile(ctx, name: cmd->location), cmd->name,
311 STB_GLOBAL, visibility, value.type, symValue, 0, sec);
312
313 Symbol *sym = ctx.symtab->insert(name: cmd->name);
314 sym->mergeProperties(other: newSym);
315 newSym.overwrite(sym&: *sym);
316 sym->isUsedInRegularObj = true;
317 cmd->sym = cast<Defined>(Val: sym);
318}
319
320// This function is called from LinkerScript::declareSymbols.
321// It creates a placeholder symbol if needed.
322void LinkerScript::declareSymbol(SymbolAssignment *cmd) {
323 if (!shouldDefineSym(ctx, cmd))
324 return;
325
326 uint8_t visibility = cmd->hidden ? STV_HIDDEN : STV_DEFAULT;
327 Defined newSym(ctx, ctx.internalFile, cmd->name, STB_GLOBAL, visibility,
328 STT_NOTYPE, 0, 0, nullptr);
329
330 // If the symbol is already defined, its order is 0 (with absence indicating
331 // 0); otherwise it's assigned the order of the SymbolAssignment.
332 Symbol *sym = ctx.symtab->insert(name: cmd->name);
333 if (!sym->isDefined())
334 ctx.scriptSymOrder.insert(KV: {sym, cmd->symOrder});
335
336 // We can't calculate final value right now.
337 sym->mergeProperties(other: newSym);
338 newSym.overwrite(sym&: *sym);
339
340 cmd->sym = cast<Defined>(Val: sym);
341 cmd->provide = false;
342 sym->isUsedInRegularObj = true;
343 sym->scriptDefined = true;
344}
345
346using SymbolAssignmentMap =
347 DenseMap<const Defined *, std::pair<SectionBase *, uint64_t>>;
348
349// Collect section/value pairs of linker-script-defined symbols. This is used to
350// check whether symbol values converge.
351static SymbolAssignmentMap
352getSymbolAssignmentValues(ArrayRef<SectionCommand *> sectionCommands) {
353 SymbolAssignmentMap ret;
354 for (SectionCommand *cmd : sectionCommands) {
355 if (auto *assign = dyn_cast<SymbolAssignment>(Val: cmd)) {
356 if (assign->sym) // sym is nullptr for dot.
357 ret.try_emplace(Key: assign->sym, Args: std::make_pair(x&: assign->sym->section,
358 y&: assign->sym->value));
359 continue;
360 }
361 if (isa<SectionClassDesc>(Val: cmd))
362 continue;
363 for (SectionCommand *subCmd : cast<OutputDesc>(Val: cmd)->osec.commands)
364 if (auto *assign = dyn_cast<SymbolAssignment>(Val: subCmd))
365 if (assign->sym)
366 ret.try_emplace(Key: assign->sym, Args: std::make_pair(x&: assign->sym->section,
367 y&: assign->sym->value));
368 }
369 return ret;
370}
371
372// Returns the lexicographical smallest (for determinism) Defined whose
373// section/value has changed.
374static const Defined *
375getChangedSymbolAssignment(const SymbolAssignmentMap &oldValues) {
376 const Defined *changed = nullptr;
377 for (auto &it : oldValues) {
378 const Defined *sym = it.first;
379 if (std::make_pair(x: sym->section, y: sym->value) != it.second &&
380 (!changed || sym->getName() < changed->getName()))
381 changed = sym;
382 }
383 return changed;
384}
385
386// Process INSERT [AFTER|BEFORE] commands. For each command, we move the
387// specified output section to the designated place.
388void LinkerScript::processInsertCommands() {
389 SmallVector<OutputDesc *, 0> moves;
390 for (const InsertCommand &cmd : insertCommands) {
391 if (ctx.arg.enableNonContiguousRegions)
392 ErrAlways(ctx)
393 << "INSERT cannot be used with --enable-non-contiguous-regions";
394
395 for (StringRef name : cmd.names) {
396 // If base is empty, it may have been discarded by
397 // adjustOutputSections(). We do not handle such output sections.
398 auto from = llvm::find_if(Range&: sectionCommands, P: [&](SectionCommand *subCmd) {
399 return isa<OutputDesc>(Val: subCmd) &&
400 cast<OutputDesc>(Val: subCmd)->osec.name == name;
401 });
402 if (from == sectionCommands.end())
403 continue;
404 moves.push_back(Elt: cast<OutputDesc>(Val: *from));
405 sectionCommands.erase(CI: from);
406 }
407
408 auto insertPos =
409 llvm::find_if(Range&: sectionCommands, P: [&cmd](SectionCommand *subCmd) {
410 auto *to = dyn_cast<OutputDesc>(Val: subCmd);
411 return to != nullptr && to->osec.name == cmd.where;
412 });
413 if (insertPos == sectionCommands.end()) {
414 ErrAlways(ctx) << "unable to insert " << cmd.names[0]
415 << (cmd.isAfter ? " after " : " before ") << cmd.where;
416 } else {
417 if (cmd.isAfter)
418 ++insertPos;
419 sectionCommands.insert(I: insertPos, From: moves.begin(), To: moves.end());
420 }
421 moves.clear();
422 }
423}
424
425// Symbols defined in script should not be inlined by LTO. At the same time
426// we don't know their final values until late stages of link. Here we scan
427// over symbol assignment commands and create placeholder symbols if needed.
428void LinkerScript::declareSymbols() {
429 assert(!state);
430 for (SectionCommand *cmd : sectionCommands) {
431 if (auto *assign = dyn_cast<SymbolAssignment>(Val: cmd)) {
432 declareSymbol(cmd: assign);
433 continue;
434 }
435 if (isa<SectionClassDesc>(Val: cmd))
436 continue;
437
438 // If the output section directive has constraints,
439 // we can't say for sure if it is going to be included or not.
440 // Skip such sections for now. Improve the checks if we ever
441 // need symbols from that sections to be declared early.
442 const OutputSection &sec = cast<OutputDesc>(Val: cmd)->osec;
443 if (sec.constraint != ConstraintKind::NoConstraint)
444 continue;
445 for (SectionCommand *cmd : sec.commands)
446 if (auto *assign = dyn_cast<SymbolAssignment>(Val: cmd))
447 declareSymbol(cmd: assign);
448 }
449}
450
451// This function is called from assignAddresses, while we are
452// fixing the output section addresses. This function is supposed
453// to set the final value for a given symbol assignment.
454void LinkerScript::assignSymbol(SymbolAssignment *cmd, bool inSec) {
455 if (cmd->name == ".") {
456 setDot(e: cmd->expression, loc: cmd->location, inSec);
457 return;
458 }
459
460 if (!cmd->sym)
461 return;
462
463 ExprValue v = cmd->expression();
464 if (v.isAbsolute()) {
465 cmd->sym->section = nullptr;
466 cmd->sym->value = v.getValue();
467 } else {
468 cmd->sym->section = v.sec;
469 cmd->sym->value = v.getSectionOffset();
470 }
471 cmd->sym->type = v.type;
472}
473
474bool InputSectionDescription::matchesFile(const InputFile &file) const {
475 if (filePat.isTrivialMatchAll())
476 return true;
477
478 if (!matchesFileCache || matchesFileCache->first != &file) {
479 if (matchType == MatchType::WholeArchive) {
480 matchesFileCache.emplace(args: &file, args: filePat.match(s: file.archiveName));
481 } else {
482 if (matchType == MatchType::ArchivesExcluded && !file.archiveName.empty())
483 matchesFileCache.emplace(args: &file, args: false);
484 else
485 matchesFileCache.emplace(args: &file, args: filePat.match(s: file.getNameForScript()));
486 }
487 }
488
489 return matchesFileCache->second;
490}
491
492bool SectionPattern::excludesFile(const InputFile &file) const {
493 if (excludedFilePat.empty())
494 return false;
495
496 if (!excludesFileCache || excludesFileCache->first != &file)
497 excludesFileCache.emplace(args: &file,
498 args: excludedFilePat.match(s: file.getNameForScript()));
499
500 return excludesFileCache->second;
501}
502
503bool LinkerScript::shouldKeep(InputSectionBase *s) {
504 for (InputSectionDescription *id : keptSections)
505 if (id->matchesFile(file: *s->file))
506 for (SectionPattern &p : id->sectionPatterns)
507 if (p.sectionPat.match(s: s->name) &&
508 (s->flags & id->withFlags) == id->withFlags &&
509 (s->flags & id->withoutFlags) == 0)
510 return true;
511 return false;
512}
513
514// A helper function for the SORT() command.
515static bool matchConstraints(ArrayRef<InputSectionBase *> sections,
516 ConstraintKind kind) {
517 if (kind == ConstraintKind::NoConstraint)
518 return true;
519
520 bool isRW = llvm::any_of(
521 Range&: sections, P: [](InputSectionBase *sec) { return sec->flags & SHF_WRITE; });
522
523 return (isRW && kind == ConstraintKind::ReadWrite) ||
524 (!isRW && kind == ConstraintKind::ReadOnly);
525}
526
527static void sortSections(MutableArrayRef<InputSectionBase *> vec,
528 SortSectionPolicy k) {
529 auto alignmentComparator = [](InputSectionBase *a, InputSectionBase *b) {
530 // ">" is not a mistake. Sections with larger alignments are placed
531 // before sections with smaller alignments in order to reduce the
532 // amount of padding necessary. This is compatible with GNU.
533 return a->addralign > b->addralign;
534 };
535 auto nameComparator = [](InputSectionBase *a, InputSectionBase *b) {
536 return a->name < b->name;
537 };
538 auto priorityComparator = [](InputSectionBase *a, InputSectionBase *b) {
539 return getPriority(s: a->name) < getPriority(s: b->name);
540 };
541
542 switch (k) {
543 case SortSectionPolicy::Default:
544 case SortSectionPolicy::None:
545 return;
546 case SortSectionPolicy::Alignment:
547 return llvm::stable_sort(Range&: vec, C: alignmentComparator);
548 case SortSectionPolicy::Name:
549 return llvm::stable_sort(Range&: vec, C: nameComparator);
550 case SortSectionPolicy::Priority:
551 return llvm::stable_sort(Range&: vec, C: priorityComparator);
552 case SortSectionPolicy::Reverse:
553 return std::reverse(first: vec.begin(), last: vec.end());
554 }
555}
556
557// Sort sections as instructed by SORT-family commands and --sort-section
558// option. Because SORT-family commands can be nested at most two depth
559// (e.g. SORT_BY_NAME(SORT_BY_ALIGNMENT(.text.*))) and because the command
560// line option is respected even if a SORT command is given, the exact
561// behavior we have here is a bit complicated. Here are the rules.
562//
563// 1. If two SORT commands are given, --sort-section is ignored.
564// 2. If one SORT command is given, and if it is not SORT_NONE,
565// --sort-section is handled as an inner SORT command.
566// 3. If one SORT command is given, and if it is SORT_NONE, don't sort.
567// 4. If no SORT command is given, sort according to --sort-section.
568static void sortInputSections(Ctx &ctx, MutableArrayRef<InputSectionBase *> vec,
569 SortSectionPolicy outer,
570 SortSectionPolicy inner) {
571 if (outer == SortSectionPolicy::None)
572 return;
573
574 if (inner == SortSectionPolicy::Default)
575 sortSections(vec, k: ctx.arg.sortSection);
576 else
577 sortSections(vec, k: inner);
578 sortSections(vec, k: outer);
579}
580
581// Compute and remember which sections the InputSectionDescription matches.
582SmallVector<InputSectionBase *, 0>
583LinkerScript::computeInputSections(const InputSectionDescription *cmd,
584 ArrayRef<InputSectionBase *> sections,
585 const SectionBase &outCmd) {
586 SmallVector<InputSectionBase *, 0> ret;
587 DenseSet<InputSectionBase *> spills;
588
589 // Returns whether an input section's flags match the input section
590 // description's specifiers.
591 auto flagsMatch = [cmd](InputSectionBase *sec) {
592 return (sec->flags & cmd->withFlags) == cmd->withFlags &&
593 (sec->flags & cmd->withoutFlags) == 0;
594 };
595
596 // Collects all sections that satisfy constraints of Cmd.
597 if (cmd->classRef.empty()) {
598 DenseSet<size_t> seen;
599 size_t sizeAfterPrevSort = 0;
600 SmallVector<size_t, 0> indexes;
601 auto sortByPositionThenCommandLine = [&](size_t begin, size_t end) {
602 llvm::sort(C: MutableArrayRef<size_t>(indexes).slice(N: begin, M: end - begin));
603 for (size_t i = begin; i != end; ++i)
604 ret[i] = sections[indexes[i]];
605 sortInputSections(
606 ctx,
607 vec: MutableArrayRef<InputSectionBase *>(ret).slice(N: begin, M: end - begin),
608 outer: ctx.arg.sortSection, inner: SortSectionPolicy::None);
609 };
610
611 bool enableNonContiguousRegions = ctx.arg.enableNonContiguousRegions;
612 for (const SectionPattern &pat : cmd->sectionPatterns) {
613 size_t sizeBeforeCurrPat = ret.size();
614
615 for (size_t i = 0, e = sections.size(); i != e; ++i) {
616 // Skip if the section is dead, has been matched by a previous input
617 // section description with non-contiguous regions disabled, or has been
618 // matched by a previous pattern in this input section description.
619 InputSectionBase *sec = sections[i];
620 if (!sec->isLive() || (!enableNonContiguousRegions && sec->parent) ||
621 seen.contains(V: i))
622 continue;
623
624 // For --emit-relocs we have to ignore entries like
625 // .rela.dyn : { *(.rela.data) }
626 // which are common because they are in the default bfd script.
627 // We do not ignore SHT_REL[A] linker-synthesized sections here because
628 // want to support scripts that do custom layout for them.
629 if (isa<InputSection>(Val: sec) &&
630 cast<InputSection>(Val: sec)->getRelocatedSection())
631 continue;
632
633 // Check the name early to improve performance in the common case.
634 if (!pat.sectionPat.match(s: sec->name))
635 continue;
636
637 if (!cmd->matchesFile(file: *sec->file) || pat.excludesFile(file: *sec->file) ||
638 !flagsMatch(sec))
639 continue;
640
641 if (sec->parent) {
642 assert(ctx.arg.enableNonContiguousRegions);
643
644 // Disallow spilling into /DISCARD/; special handling would be needed
645 // for this in address assignment, and the semantics are nebulous.
646 if (outCmd.name == "/DISCARD/")
647 continue;
648
649 // Class definitions cannot contain spills, nor can a class definition
650 // generate a spill in a subsequent match. Those behaviors belong to
651 // class references and additional matches.
652 if (!isa<SectionClass>(Val: outCmd) && !isa<SectionClass>(Val: sec->parent))
653 spills.insert(V: sec);
654 }
655
656 ret.push_back(Elt: sec);
657 indexes.push_back(Elt: i);
658 seen.insert(V: i);
659 }
660
661 if (pat.sortOuter == SortSectionPolicy::Default)
662 continue;
663
664 // Matched sections are ordered by radix sort with the keys being (SORT*,
665 // --sort-section, input order), where SORT* (if present) is most
666 // significant.
667 //
668 // Matched sections between the previous SORT* and this SORT* are sorted
669 // by (--sort-alignment, input order).
670 sortByPositionThenCommandLine(sizeAfterPrevSort, sizeBeforeCurrPat);
671 // Matched sections by this SORT* pattern are sorted using all 3 keys.
672 // ret[sizeBeforeCurrPat,ret.size()) are already in the input order, so we
673 // just sort by sortOuter and sortInner.
674 sortInputSections(
675 ctx,
676 vec: MutableArrayRef<InputSectionBase *>(ret).slice(N: sizeBeforeCurrPat),
677 outer: pat.sortOuter, inner: pat.sortInner);
678 sizeAfterPrevSort = ret.size();
679 }
680
681 // Matched sections after the last SORT* are sorted by (--sort-alignment,
682 // input order).
683 sortByPositionThenCommandLine(sizeAfterPrevSort, ret.size());
684 } else {
685 SectionClassDesc *scd =
686 sectionClasses.lookup(Val: CachedHashStringRef(cmd->classRef));
687 if (!scd) {
688 Err(ctx) << "undefined section class '" << cmd->classRef << "'";
689 return ret;
690 }
691 if (!scd->sc.assigned) {
692 Err(ctx) << "section class '" << cmd->classRef << "' referenced by '"
693 << outCmd.name << "' before class definition";
694 return ret;
695 }
696
697 for (InputSectionDescription *isd : scd->sc.commands) {
698 for (InputSectionBase *sec : isd->sectionBases) {
699 if (!flagsMatch(sec))
700 continue;
701 bool isSpill = sec->parent && isa<OutputSection>(Val: sec->parent);
702 if (!sec->parent || (isSpill && outCmd.name == "/DISCARD/")) {
703 Err(ctx) << "section '" << sec->name
704 << "' cannot spill from/to /DISCARD/";
705 continue;
706 }
707 if (isSpill)
708 spills.insert(V: sec);
709 ret.push_back(Elt: sec);
710 }
711 }
712 }
713
714 // The flag --enable-non-contiguous-regions or the section CLASS syntax may
715 // cause sections to match an InputSectionDescription in more than one
716 // OutputSection. Matches after the first were collected in the spills set, so
717 // replace these with potential spill sections.
718 if (!spills.empty()) {
719 for (InputSectionBase *&sec : ret) {
720 if (!spills.contains(V: sec))
721 continue;
722
723 // Append the spill input section to the list for the input section,
724 // creating it if necessary.
725 PotentialSpillSection *pss = make<PotentialSpillSection>(
726 args&: *sec, args&: const_cast<InputSectionDescription &>(*cmd));
727 auto [it, inserted] =
728 potentialSpillLists.try_emplace(Key: sec, Args: PotentialSpillList{.head: pss, .tail: pss});
729 if (!inserted) {
730 PotentialSpillSection *&tail = it->second.tail;
731 tail = tail->next = pss;
732 }
733 sec = pss;
734 }
735 }
736
737 return ret;
738}
739
740void LinkerScript::discard(InputSectionBase &s) {
741 if (&s == ctx.in.shStrTab.get())
742 ErrAlways(ctx) << "discarding " << s.name << " section is not allowed";
743
744 s.markDead();
745 s.parent = nullptr;
746 for (InputSection *sec : s.dependentSections)
747 discard(s&: *sec);
748}
749
750void LinkerScript::discardSynthetic(OutputSection &outCmd) {
751 ARMExidxSyntheticSection *armExidx = ctx.in.armExidx.get();
752 if (!armExidx || !armExidx->isLive())
753 return;
754 SmallVector<InputSectionBase *, 0> secs(armExidx->exidxSections.begin(),
755 armExidx->exidxSections.end());
756 for (SectionCommand *cmd : outCmd.commands)
757 if (auto *isd = dyn_cast<InputSectionDescription>(Val: cmd))
758 for (InputSectionBase *s : computeInputSections(cmd: isd, sections: secs, outCmd))
759 discard(s&: *s);
760}
761
762SmallVector<InputSectionBase *, 0>
763LinkerScript::createInputSectionList(OutputSection &outCmd) {
764 SmallVector<InputSectionBase *, 0> ret;
765
766 for (SectionCommand *cmd : outCmd.commands) {
767 if (auto *isd = dyn_cast<InputSectionDescription>(Val: cmd)) {
768 isd->sectionBases = computeInputSections(cmd: isd, sections: ctx.inputSections, outCmd);
769 for (InputSectionBase *s : isd->sectionBases)
770 s->parent = &outCmd;
771 ret.insert(I: ret.end(), From: isd->sectionBases.begin(), To: isd->sectionBases.end());
772 }
773 }
774 return ret;
775}
776
777// Create output sections described by SECTIONS commands.
778void LinkerScript::processSectionCommands() {
779 auto process = [this](OutputSection *osec) {
780 SmallVector<InputSectionBase *, 0> v = createInputSectionList(outCmd&: *osec);
781
782 // The output section name `/DISCARD/' is special.
783 // Any input section assigned to it is discarded.
784 if (osec->name == "/DISCARD/") {
785 for (InputSectionBase *s : v)
786 discard(s&: *s);
787 discardSynthetic(outCmd&: *osec);
788 osec->commands.clear();
789 return false;
790 }
791
792 // This is for ONLY_IF_RO and ONLY_IF_RW. An output section directive
793 // ".foo : ONLY_IF_R[OW] { ... }" is handled only if all member input
794 // sections satisfy a given constraint. If not, a directive is handled
795 // as if it wasn't present from the beginning.
796 //
797 // Because we'll iterate over SectionCommands many more times, the easy
798 // way to "make it as if it wasn't present" is to make it empty.
799 if (!matchConstraints(sections: v, kind: osec->constraint)) {
800 for (InputSectionBase *s : v)
801 s->parent = nullptr;
802 osec->commands.clear();
803 return false;
804 }
805
806 // Handle subalign (e.g. ".foo : SUBALIGN(32) { ... }"). If subalign
807 // is given, input sections are aligned to that value, whether the
808 // given value is larger or smaller than the original section alignment.
809 if (osec->subalignExpr) {
810 uint32_t subalign = osec->subalignExpr().getValue();
811 for (InputSectionBase *s : v)
812 s->addralign = subalign;
813 }
814
815 // Mark the output section live, like OutputSection::recordSection().
816 osec->partition = 1;
817 return true;
818 };
819
820 // Process OVERWRITE_SECTIONS first so that it can overwrite the main script
821 // or orphans.
822 if (ctx.arg.enableNonContiguousRegions && !overwriteSections.empty())
823 ErrAlways(ctx) << "OVERWRITE_SECTIONS cannot be used with "
824 "--enable-non-contiguous-regions";
825 DenseMap<CachedHashStringRef, OutputDesc *> map;
826 size_t i = 0;
827 for (OutputDesc *osd : overwriteSections) {
828 OutputSection *osec = &osd->osec;
829 if (process(osec) &&
830 !map.try_emplace(Key: CachedHashStringRef(osec->name), Args&: osd).second)
831 Warn(ctx) << "OVERWRITE_SECTIONS specifies duplicate " << osec->name;
832 }
833 for (SectionCommand *&base : sectionCommands) {
834 if (auto *osd = dyn_cast<OutputDesc>(Val: base)) {
835 OutputSection *osec = &osd->osec;
836 if (OutputDesc *overwrite = map.lookup(Val: CachedHashStringRef(osec->name))) {
837 Log(ctx) << overwrite->osec.location << " overwrites " << osec->name;
838 overwrite->osec.sectionIndex = i++;
839 base = overwrite;
840 } else if (process(osec)) {
841 osec->sectionIndex = i++;
842 }
843 } else if (auto *sc = dyn_cast<SectionClassDesc>(Val: base)) {
844 for (InputSectionDescription *isd : sc->sc.commands) {
845 isd->sectionBases =
846 computeInputSections(cmd: isd, sections: ctx.inputSections, outCmd: sc->sc);
847 for (InputSectionBase *s : isd->sectionBases) {
848 // A section class containing a section with different parent isn't
849 // necessarily an error due to --enable-non-contiguous-regions. Such
850 // sections all become potential spills when the class is referenced.
851 if (!s->parent)
852 s->parent = &sc->sc;
853 }
854 }
855 sc->sc.assigned = true;
856 }
857 }
858
859 // Check that input sections cannot spill into or out of INSERT,
860 // since the semantics are nebulous. This is also true for OVERWRITE_SECTIONS,
861 // but no check is needed, since the order of processing ensures they cannot
862 // legally reference classes.
863 if (!potentialSpillLists.empty()) {
864 DenseSet<StringRef> insertNames;
865 for (InsertCommand &ic : insertCommands)
866 insertNames.insert_range(R&: ic.names);
867 for (SectionCommand *&base : sectionCommands) {
868 auto *osd = dyn_cast<OutputDesc>(Val: base);
869 if (!osd)
870 continue;
871 OutputSection *os = &osd->osec;
872 if (!insertNames.contains(V: os->name))
873 continue;
874 for (SectionCommand *sc : os->commands) {
875 auto *isd = dyn_cast<InputSectionDescription>(Val: sc);
876 if (!isd)
877 continue;
878 for (InputSectionBase *isec : isd->sectionBases)
879 if (isa<PotentialSpillSection>(Val: isec) ||
880 potentialSpillLists.contains(Val: isec))
881 Err(ctx) << "section '" << isec->name
882 << "' cannot spill from/to INSERT section '" << os->name
883 << "'";
884 }
885 }
886 }
887
888 // If an OVERWRITE_SECTIONS specified output section is not in
889 // sectionCommands, append it to the end. The section will be inserted by
890 // orphan placement.
891 for (OutputDesc *osd : overwriteSections)
892 if (osd->osec.partition == 1 && osd->osec.sectionIndex == UINT32_MAX)
893 sectionCommands.push_back(Elt: osd);
894
895 // Input sections cannot have a section class parent past this point; they
896 // must have been assigned to an output section.
897 for (const auto &[_, sc] : sectionClasses) {
898 for (InputSectionDescription *isd : sc->sc.commands) {
899 for (InputSectionBase *sec : isd->sectionBases) {
900 if (sec->parent && isa<SectionClass>(Val: sec->parent)) {
901 Err(ctx) << "section class '" << sec->parent->name
902 << "' is unreferenced";
903 goto nextClass;
904 }
905 }
906 }
907 nextClass:;
908 }
909}
910
911void LinkerScript::processSymbolAssignments() {
912 // Dot outside an output section still represents a relative address, whose
913 // sh_shndx should not be SHN_UNDEF or SHN_ABS. Create a dummy aether section
914 // that fills the void outside a section. It has an index of one, which is
915 // indistinguishable from any other regular section index.
916 aether = std::make_unique<OutputSection>(args&: ctx, args: "", args: 0, args: SHF_ALLOC);
917 aether->sectionIndex = 1;
918
919 // `st` captures the local AddressState and makes it accessible deliberately.
920 // This is needed as there are some cases where we cannot just thread the
921 // current state through to a lambda function created by the script parser.
922 AddressState st(*this);
923 state = &st;
924 st.outSec = aether.get();
925
926 for (SectionCommand *cmd : sectionCommands) {
927 if (auto *assign = dyn_cast<SymbolAssignment>(Val: cmd))
928 addSymbol(cmd: assign);
929 else if (auto *osd = dyn_cast<OutputDesc>(Val: cmd))
930 for (SectionCommand *subCmd : osd->osec.commands)
931 if (auto *assign = dyn_cast<SymbolAssignment>(Val: subCmd))
932 addSymbol(cmd: assign);
933 }
934
935 state = nullptr;
936}
937
938static OutputSection *findByName(ArrayRef<SectionCommand *> vec,
939 StringRef name) {
940 for (SectionCommand *cmd : vec)
941 if (auto *osd = dyn_cast<OutputDesc>(Val: cmd))
942 if (osd->osec.name == name)
943 return &osd->osec;
944 return nullptr;
945}
946
947static OutputDesc *createSection(Ctx &ctx, InputSectionBase *isec,
948 StringRef outsecName) {
949 OutputDesc *osd = ctx.script->createOutputSection(name: outsecName, location: "<internal>");
950 osd->osec.recordSection(isec);
951 return osd;
952}
953
954static OutputDesc *addInputSec(Ctx &ctx,
955 StringMap<TinyPtrVector<OutputSection *>> &map,
956 InputSectionBase *isec, StringRef outsecName) {
957 // Sections with SHT_GROUP or SHF_GROUP attributes reach here only when the -r
958 // option is given. A section with SHT_GROUP defines a "section group", and
959 // its members have SHF_GROUP attribute. Usually these flags have already been
960 // stripped by InputFiles.cpp as section groups are processed and uniquified.
961 // However, for the -r option, we want to pass through all section groups
962 // as-is because adding/removing members or merging them with other groups
963 // change their semantics.
964 if (isec->type == SHT_GROUP || (isec->flags & SHF_GROUP))
965 return createSection(ctx, isec, outsecName);
966
967 // Imagine .zed : { *(.foo) *(.bar) } script. Both foo and bar may have
968 // relocation sections .rela.foo and .rela.bar for example. Most tools do
969 // not allow multiple REL[A] sections for output section. Hence we
970 // should combine these relocation sections into single output.
971 // We skip synthetic sections because it can be .rela.dyn/.rela.plt or any
972 // other REL[A] sections created by linker itself.
973 if (!isa<SyntheticSection>(Val: isec) && isStaticRelSecType(type: isec->type)) {
974 auto *sec = cast<InputSection>(Val: isec);
975 OutputSection *out = sec->getRelocatedSection()->getOutputSection();
976
977 if (auto *relSec = out->relocationSection) {
978 relSec->recordSection(isec: sec);
979 return nullptr;
980 }
981
982 OutputDesc *osd = createSection(ctx, isec, outsecName);
983 out->relocationSection = &osd->osec;
984 return osd;
985 }
986
987 // The ELF spec just says
988 // ----------------------------------------------------------------
989 // In the first phase, input sections that match in name, type and
990 // attribute flags should be concatenated into single sections.
991 // ----------------------------------------------------------------
992 //
993 // However, it is clear that at least some flags have to be ignored for
994 // section merging. At the very least SHF_GROUP and SHF_COMPRESSED have to be
995 // ignored. We should not have two output .text sections just because one was
996 // in a group and another was not for example.
997 //
998 // It also seems that wording was a late addition and didn't get the
999 // necessary scrutiny.
1000 //
1001 // Merging sections with different flags is expected by some users. One
1002 // reason is that if one file has
1003 //
1004 // int *const bar __attribute__((section(".foo"))) = (int *)0;
1005 //
1006 // gcc with -fPIC will produce a read only .foo section. But if another
1007 // file has
1008 //
1009 // int zed;
1010 // int *const bar __attribute__((section(".foo"))) = (int *)&zed;
1011 //
1012 // gcc with -fPIC will produce a read write section.
1013 //
1014 // Last but not least, when using linker script the merge rules are forced by
1015 // the script. Unfortunately, linker scripts are name based. This means that
1016 // expressions like *(.foo*) can refer to multiple input sections with
1017 // different flags. We cannot put them in different output sections or we
1018 // would produce wrong results for
1019 //
1020 // start = .; *(.foo.*) end = .; *(.bar)
1021 //
1022 // and a mapping of .foo1 and .bar1 to one section and .foo2 and .bar2 to
1023 // another. The problem is that there is no way to layout those output
1024 // sections such that the .foo sections are the only thing between the start
1025 // and end symbols.
1026 //
1027 // Given the above issues, we instead merge sections by name and error on
1028 // incompatible types and flags.
1029 TinyPtrVector<OutputSection *> &v = map[outsecName];
1030 for (OutputSection *sec : v) {
1031 if (sec->partition != isec->partition)
1032 continue;
1033
1034 if (ctx.arg.relocatable && (isec->flags & SHF_LINK_ORDER)) {
1035 // Merging two SHF_LINK_ORDER sections with different sh_link fields will
1036 // change their semantics, so we only merge them in -r links if they will
1037 // end up being linked to the same output section. The casts are fine
1038 // because everything in the map was created by the orphan placement code.
1039 auto *firstIsec = cast<InputSectionBase>(
1040 Val: cast<InputSectionDescription>(Val: sec->commands[0])->sectionBases[0]);
1041 OutputSection *firstIsecOut =
1042 (firstIsec->flags & SHF_LINK_ORDER)
1043 ? firstIsec->getLinkOrderDep()->getOutputSection()
1044 : nullptr;
1045 if (firstIsecOut != isec->getLinkOrderDep()->getOutputSection())
1046 continue;
1047 }
1048
1049 sec->recordSection(isec);
1050 return nullptr;
1051 }
1052
1053 OutputDesc *osd = createSection(ctx, isec, outsecName);
1054 v.push_back(NewVal: &osd->osec);
1055 return osd;
1056}
1057
1058// Add sections that didn't match any sections command.
1059void LinkerScript::addOrphanSections() {
1060 StringMap<TinyPtrVector<OutputSection *>> map;
1061 SmallVector<OutputDesc *, 0> v;
1062
1063 auto add = [&](InputSectionBase *s, StringRef name = {}) {
1064 if (s->isLive() && !s->parent) {
1065 orphanSections.push_back(Elt: s);
1066
1067 if (name.empty())
1068 name = getOutputSectionName(s);
1069 if (ctx.arg.unique) {
1070 v.push_back(Elt: createSection(ctx, isec: s, outsecName: name));
1071 } else if (OutputSection *sec = findByName(vec: sectionCommands, name)) {
1072 sec->recordSection(isec: s);
1073 } else {
1074 if (OutputDesc *osd = addInputSec(ctx, map, isec: s, outsecName: name))
1075 v.push_back(Elt: osd);
1076 assert(isa<MergeInputSection>(s) ||
1077 s->getOutputSection()->sectionIndex == UINT32_MAX);
1078 }
1079 }
1080 };
1081
1082 const bool copyRelocs = ctx.arg.copyRelocs;
1083 const bool relocatable = ctx.arg.relocatable;
1084 // Under --emit-relocs/-r, getOutputSectionName derives the name from the
1085 // relocated section, and saving it is not thread-safe. Otherwise, the names
1086 // can be precomputed in parallel.
1087 SmallVector<StringRef, 0> names(ctx.inputSections.size());
1088 if (!copyRelocs) {
1089 parallelFor(Begin: 0, End: ctx.inputSections.size(), Fn: [&](size_t i) {
1090 InputSectionBase *s = ctx.inputSections[i];
1091 if (s->isLive() && !s->parent)
1092 names[i] = getOutputSectionName(s);
1093 });
1094 }
1095 size_t n = 0;
1096 for (auto [i, isec] : llvm::enumerate(First&: ctx.inputSections)) {
1097 // Process InputSection and MergeInputSection.
1098 if (LLVM_LIKELY(isa<InputSection>(isec)))
1099 ctx.inputSections[n++] = isec;
1100
1101 if (LLVM_UNLIKELY(copyRelocs)) {
1102 // In -r links, SHF_LINK_ORDER sections are added while adding their
1103 // parent sections because we need to know the parent's output section
1104 // before we can select an output section for the SHF_LINK_ORDER section.
1105 if (relocatable && (isec->flags & SHF_LINK_ORDER))
1106 continue;
1107
1108 if (auto *sec = dyn_cast<InputSection>(Val: isec))
1109 if (InputSectionBase *relocated = sec->getRelocatedSection()) {
1110 // For --emit-relocs and -r, ensure the output section for .text.foo
1111 // is created before the output section for .rela.text.foo.
1112 add(relocated);
1113 // EhInputSection sections are not added to ctx.inputSections. If we
1114 // see .rela.eh_frame, ensure the output section for the synthetic
1115 // EhFrameSection is created first.
1116 if (auto *p = dyn_cast_or_null<InputSectionBase>(Val: relocated->parent))
1117 add(p);
1118 }
1119 }
1120
1121 add(isec, names[i]);
1122 if (LLVM_UNLIKELY(relocatable))
1123 for (InputSectionBase *depSec : isec->dependentSections)
1124 if (depSec->flags & SHF_LINK_ORDER)
1125 add(depSec);
1126 }
1127 // Keep just InputSection.
1128 ctx.inputSections.resize(N: n);
1129
1130 // If no SECTIONS command was given, we should insert sections commands
1131 // before others, so that we can handle scripts which refers them,
1132 // for example: "foo = ABSOLUTE(ADDR(.text)));".
1133 // When SECTIONS command is present we just add all orphans to the end.
1134 if (hasSectionsCommand)
1135 sectionCommands.insert(I: sectionCommands.end(), From: v.begin(), To: v.end());
1136 else
1137 sectionCommands.insert(I: sectionCommands.begin(), From: v.begin(), To: v.end());
1138}
1139
1140void LinkerScript::diagnoseOrphanHandling() const {
1141 llvm::TimeTraceScope timeScope("Diagnose orphan sections");
1142 if (ctx.arg.orphanHandling == OrphanHandlingPolicy::Place ||
1143 !hasSectionsCommand)
1144 return;
1145 for (const InputSectionBase *sec : orphanSections) {
1146 // .relro_padding is inserted before DATA_SEGMENT_RELRO_END, if present,
1147 // automatically. The section is not supposed to be specified by scripts.
1148 if (sec == ctx.in.relroPadding.get())
1149 continue;
1150 // Input SHT_REL[A] retained by --emit-relocs are ignored by
1151 // computeInputSections(). Don't warn/error.
1152 if (isa<InputSection>(Val: sec) &&
1153 cast<InputSection>(Val: sec)->getRelocatedSection())
1154 continue;
1155
1156 StringRef name = getOutputSectionName(s: sec);
1157 if (ctx.arg.orphanHandling == OrphanHandlingPolicy::Error)
1158 ErrAlways(ctx) << sec << " is being placed in '" << name << "'";
1159 else
1160 Warn(ctx) << sec << " is being placed in '" << name << "'";
1161 }
1162}
1163
1164void LinkerScript::diagnoseMissingSGSectionAddress() const {
1165 if (!ctx.arg.cmseImplib || !ctx.in.armCmseSGSection->isNeeded())
1166 return;
1167
1168 OutputSection *sec = findByName(vec: sectionCommands, name: ".gnu.sgstubs");
1169 if (sec && !sec->addrExpr &&
1170 !ctx.arg.sectionStartMap.contains(Key: ".gnu.sgstubs"))
1171 ErrAlways(ctx) << "no address assigned to the veneers output section "
1172 << sec->name;
1173}
1174
1175// This function searches for a memory region to place the given output
1176// section in. If found, a pointer to the appropriate memory region is
1177// returned in the first member of the pair. Otherwise, a nullptr is returned.
1178// The second member of the pair is a hint that should be passed to the
1179// subsequent call of this method.
1180std::pair<MemoryRegion *, MemoryRegion *>
1181LinkerScript::findMemoryRegion(OutputSection *sec, MemoryRegion *hint) {
1182 // Non-allocatable sections are not part of the process image.
1183 if (!(sec->flags & SHF_ALLOC)) {
1184 bool hasInputOrByteCommand =
1185 sec->hasInputSections ||
1186 llvm::any_of(Range&: sec->commands, P: [](SectionCommand *comm) {
1187 return ByteCommand::classof(c: comm);
1188 });
1189 if (!sec->memoryRegionName.empty() && hasInputOrByteCommand)
1190 Warn(ctx)
1191 << "ignoring memory region assignment for non-allocatable section '"
1192 << sec->name << "'";
1193 return {nullptr, nullptr};
1194 }
1195
1196 // If a memory region name was specified in the output section command,
1197 // then try to find that region first.
1198 if (!sec->memoryRegionName.empty()) {
1199 if (MemoryRegion *m = memoryRegions.lookup(Key: sec->memoryRegionName))
1200 return {m, m};
1201 ErrAlways(ctx) << "memory region '" << sec->memoryRegionName
1202 << "' not declared";
1203 return {nullptr, nullptr};
1204 }
1205
1206 // If at least one memory region is defined, all sections must
1207 // belong to some memory region. Otherwise, we don't need to do
1208 // anything for memory regions.
1209 if (memoryRegions.empty())
1210 return {nullptr, nullptr};
1211
1212 // An orphan section should continue the previous memory region.
1213 if (sec->sectionIndex == UINT32_MAX && hint)
1214 return {hint, hint};
1215
1216 // See if a region can be found by matching section flags.
1217 for (auto &pair : memoryRegions) {
1218 MemoryRegion *m = pair.second;
1219 if (m->compatibleWith(secFlags: sec->flags))
1220 return {m, nullptr};
1221 }
1222
1223 // Otherwise, no suitable region was found.
1224 ErrAlways(ctx) << "no memory region specified for section '" << sec->name
1225 << "'";
1226 return {nullptr, nullptr};
1227}
1228
1229static OutputSection *findFirstSection(Ctx &ctx, PhdrEntry *load) {
1230 for (OutputSection *sec : ctx.outputSections)
1231 if (sec->ptLoad == load)
1232 return sec;
1233 return nullptr;
1234}
1235
1236// Assign addresses to an output section and offsets to its input sections and
1237// symbol assignments. Return true if the output section's address has changed.
1238bool LinkerScript::assignOffsets(OutputSection *sec) {
1239 const bool isTbss = (sec->flags & SHF_TLS) && sec->type == SHT_NOBITS;
1240 const bool sameMemRegion = state->memRegion == sec->memRegion;
1241 const bool prevLMARegionIsDefault = state->lmaRegion == nullptr;
1242 const uint64_t savedDot = dot;
1243 bool addressChanged = false;
1244 state->memRegion = sec->memRegion;
1245 state->lmaRegion = sec->lmaRegion;
1246
1247 if (!(sec->flags & SHF_ALLOC)) {
1248 // Non-SHF_ALLOC sections have zero addresses.
1249 dot = 0;
1250 } else if (isTbss && !sec->addrExpr) {
1251 // Allow consecutive SHF_TLS SHT_NOBITS output sections. The address range
1252 // starts from the end address of the previous tbss section.
1253 if (state->tbssAddr == 0)
1254 state->tbssAddr = dot;
1255 else
1256 dot = state->tbssAddr;
1257 } else {
1258 // If there is an explicit address expression this takes precedence over
1259 // the memory region address.
1260 if (state->memRegion && !(hasSectionsCommand && sec->addrExpr))
1261 dot = state->memRegion->curPos;
1262 if (sec->addrExpr)
1263 setDot(e: sec->addrExpr, loc: sec->location, inSec: false);
1264
1265 // If the address of the section has been moved forward by an explicit
1266 // expression so that it now starts past the current curPos of the enclosing
1267 // region, we need to expand the current region to account for the space
1268 // between the previous section, if any, and the start of this section.
1269 if (state->memRegion && state->memRegion->curPos < dot)
1270 expandMemoryRegion(memRegion: state->memRegion, size: dot - state->memRegion->curPos,
1271 secName: sec->name);
1272 }
1273
1274 state->outSec = sec;
1275 if (!(sec->addrExpr && hasSectionsCommand)) {
1276 // ALIGN is respected. sec->alignment is the max of ALIGN and the maximum of
1277 // input section alignments.
1278 const uint64_t pos = dot;
1279 dot = alignToPowerOf2(Value: dot, Align: sec->addralign);
1280 expandMemoryRegions(size: dot - pos);
1281 }
1282 addressChanged = sec->addr != dot;
1283 sec->addr = dot;
1284
1285 // state->lmaOffset is LMA minus VMA. If LMA is explicitly specified via AT()
1286 // or AT>, recompute state->lmaOffset; otherwise, if both previous/current LMA
1287 // region is the default, and the two sections are in the same memory region,
1288 // reuse previous lmaOffset; otherwise, reset lmaOffset to 0. This emulates
1289 // heuristics described in
1290 // https://sourceware.org/binutils/docs/ld/Output-Section-LMA.html
1291 if (sec->lmaExpr) {
1292 state->lmaOffset = sec->lmaExpr().getValue() - dot;
1293 } else if (MemoryRegion *mr = sec->lmaRegion) {
1294 uint64_t lmaStart = alignToPowerOf2(Value: mr->curPos, Align: sec->addralign);
1295 if (mr->curPos < lmaStart)
1296 expandMemoryRegion(memRegion: mr, size: lmaStart - mr->curPos, secName: sec->name);
1297 state->lmaOffset = lmaStart - dot;
1298 } else if (!sameMemRegion || !prevLMARegionIsDefault) {
1299 state->lmaOffset = 0;
1300 }
1301
1302 // Propagate state->lmaOffset to the first "non-header" section.
1303 if (PhdrEntry *l = sec->ptLoad)
1304 if (sec == findFirstSection(ctx, load: l))
1305 l->lmaOffset = state->lmaOffset;
1306
1307 // We can call this method multiple times during the creation of
1308 // thunks and want to start over calculation each time.
1309 sec->size = 0;
1310 if (sec->firstInOverlay)
1311 state->overlaySize = 0;
1312
1313 bool synthesizeAlign =
1314 ctx.arg.relocatable && ctx.arg.relax && (sec->flags & SHF_EXECINSTR) &&
1315 (ctx.arg.emachine == EM_LOONGARCH || ctx.arg.emachine == EM_RISCV);
1316 // We visited SectionsCommands from processSectionCommands to
1317 // layout sections. Now, we visit SectionsCommands again to fix
1318 // section offsets.
1319 for (SectionCommand *cmd : sec->commands) {
1320 // This handles the assignments to symbol or to the dot.
1321 if (auto *assign = dyn_cast<SymbolAssignment>(Val: cmd)) {
1322 assign->addr = dot;
1323 assignSymbol(cmd: assign, inSec: true);
1324 assign->size = dot - assign->addr;
1325 continue;
1326 }
1327
1328 // Handle BYTE(), SHORT(), LONG(), or QUAD().
1329 if (auto *data = dyn_cast<ByteCommand>(Val: cmd)) {
1330 data->offset = dot - sec->addr;
1331 dot += data->size;
1332 expandOutputSection(size: data->size);
1333 continue;
1334 }
1335
1336 // Handle a single input section description command.
1337 // It calculates and assigns the offsets for each section and also
1338 // updates the output section size.
1339
1340 auto &sections = cast<InputSectionDescription>(Val: cmd)->sections;
1341 for (InputSection *isec : sections) {
1342 assert(isec->getParent() == sec);
1343 if (isa<PotentialSpillSection>(Val: isec))
1344 continue;
1345 const uint64_t pos = dot;
1346 // If synthesized ALIGN may be needed, call maybeSynthesizeAlign and
1347 // disable the default handling if the return value is true.
1348 if (!(synthesizeAlign && ctx.target->synthesizeAlign(dot, sec: isec)))
1349 dot = alignToPowerOf2(Value: dot, Align: isec->addralign);
1350 isec->outSecOff = dot - sec->addr;
1351 dot += isec->getSize();
1352
1353 // Update output section size after adding each section. This is so that
1354 // SIZEOF works correctly in the case below:
1355 // .foo { *(.aaa) a = SIZEOF(.foo); *(.bbb) }
1356 expandOutputSection(size: dot - pos);
1357 }
1358 }
1359
1360 // If .relro_padding is present, round up the end to a common-page-size
1361 // boundary to protect the last page.
1362 if (ctx.in.relroPadding && sec == ctx.in.relroPadding->getParent())
1363 expandOutputSection(size: alignToPowerOf2(Value: dot, Align: ctx.arg.commonPageSize) - dot);
1364
1365 if (synthesizeAlign) {
1366 const uint64_t pos = dot;
1367 ctx.target->synthesizeAlign(dot, sec: nullptr);
1368 expandOutputSection(size: dot - pos);
1369 }
1370
1371 // Non-SHF_ALLOC sections do not affect the addresses of other OutputSections
1372 // as they are not part of the process image.
1373 if (!(sec->flags & SHF_ALLOC)) {
1374 dot = savedDot;
1375 } else if (isTbss) {
1376 // NOBITS TLS sections are similar. Additionally save the end address.
1377 state->tbssAddr = dot;
1378 dot = savedDot;
1379 }
1380 return addressChanged;
1381}
1382
1383static bool isDiscardable(const OutputSection &sec) {
1384 if (sec.name == "/DISCARD/")
1385 return true;
1386
1387 // We do not want to remove OutputSections with expressions that reference
1388 // symbols even if the OutputSection is empty. We want to ensure that the
1389 // expressions can be evaluated and report an error if they cannot.
1390 if (sec.expressionsUseSymbols)
1391 return false;
1392
1393 // OutputSections may be referenced by name in ADDR and LOADADDR expressions,
1394 // as an empty Section can has a valid VMA and LMA we keep the OutputSection
1395 // to maintain the integrity of the other Expression.
1396 if (sec.usedInExpression)
1397 return false;
1398
1399 for (SectionCommand *cmd : sec.commands) {
1400 if (auto assign = dyn_cast<SymbolAssignment>(Val: cmd))
1401 // Don't create empty output sections just for unreferenced PROVIDE
1402 // symbols.
1403 if (assign->name != "." && !assign->sym)
1404 continue;
1405
1406 if (!isa<InputSectionDescription>(Val: *cmd))
1407 return false;
1408 }
1409 return true;
1410}
1411
1412static void maybePropagatePhdrs(OutputSection &sec,
1413 SmallVector<StringRef, 0> &phdrs) {
1414 if (sec.phdrs.empty()) {
1415 // To match the bfd linker script behaviour, only propagate program
1416 // headers to sections that are allocated.
1417 if (sec.flags & SHF_ALLOC)
1418 sec.phdrs = phdrs;
1419 } else {
1420 phdrs = sec.phdrs;
1421 }
1422}
1423
1424void LinkerScript::adjustOutputSections() {
1425 // If the output section contains only symbol assignments, create a
1426 // corresponding output section. The issue is what to do with linker script
1427 // like ".foo : { symbol = 42; }". One option would be to convert it to
1428 // "symbol = 42;". That is, move the symbol out of the empty section
1429 // description. That seems to be what bfd does for this simple case. The
1430 // problem is that this is not completely general. bfd will give up and
1431 // create a dummy section too if there is a ". = . + 1" inside the section
1432 // for example.
1433 // Given that we want to create the section, we have to worry what impact
1434 // it will have on the link. For example, if we just create a section with
1435 // 0 for flags, it would change which PT_LOADs are created.
1436 // We could remember that particular section is dummy and ignore it in
1437 // other parts of the linker, but unfortunately there are quite a few places
1438 // that would need to change:
1439 // * The program header creation.
1440 // * The orphan section placement.
1441 // * The address assignment.
1442 // The other option is to pick flags that minimize the impact the section
1443 // will have on the rest of the linker. That is why we copy the flags from
1444 // the previous sections. We copy just SHF_ALLOC and SHF_WRITE to keep the
1445 // impact low. We do not propagate SHF_EXECINSTR as in some cases this can
1446 // lead to executable writeable section.
1447 uint64_t flags = SHF_ALLOC;
1448
1449 SmallVector<StringRef, 0> defPhdrs;
1450 bool seenRelro = false;
1451 for (SectionCommand *&cmd : sectionCommands) {
1452 if (!isa<OutputDesc>(Val: cmd))
1453 continue;
1454 auto *sec = &cast<OutputDesc>(Val: cmd)->osec;
1455
1456 // Handle align (e.g. ".foo : ALIGN(16) { ... }").
1457 if (sec->alignExpr)
1458 sec->addralign =
1459 std::max<uint32_t>(a: sec->addralign, b: sec->alignExpr().getValue());
1460
1461 bool isEmpty = (getFirstInputSection(os: sec) == nullptr);
1462 bool discardable = isEmpty && isDiscardable(sec: *sec);
1463 // If sec has at least one input section and not discarded, remember its
1464 // flags to be inherited by subsequent output sections. (sec may contain
1465 // just one empty synthetic section.)
1466 if (sec->hasInputSections && !discardable)
1467 flags = sec->flags;
1468
1469 // We do not want to keep any special flags for output section
1470 // in case it is empty.
1471 if (isEmpty) {
1472 sec->flags =
1473 flags & ((sec->nonAlloc ? 0 : (uint64_t)SHF_ALLOC) | SHF_WRITE);
1474 sec->sortRank = getSectionRank(ctx, osec&: *sec);
1475 }
1476
1477 // The code below may remove empty output sections. We should save the
1478 // specified program headers (if exist) and propagate them to subsequent
1479 // sections which do not specify program headers.
1480 // An example of such a linker script is:
1481 // SECTIONS { .empty : { *(.empty) } :rw
1482 // .foo : { *(.foo) } }
1483 // Note: at this point the order of output sections has not been finalized,
1484 // because orphans have not been inserted into their expected positions. We
1485 // will handle them in adjustSectionsAfterSorting().
1486 if (sec->sectionIndex != UINT32_MAX)
1487 maybePropagatePhdrs(sec&: *sec, phdrs&: defPhdrs);
1488
1489 // Discard .relro_padding if we have not seen one RELRO section. Note: when
1490 // .tbss is the only RELRO section, there is no associated PT_LOAD segment
1491 // (needsPtLoad), so we don't append .relro_padding in the case.
1492 if (ctx.in.relroPadding && ctx.in.relroPadding->getParent() == sec &&
1493 !seenRelro)
1494 discardable = true;
1495 if (discardable) {
1496 sec->markDead();
1497 cmd = nullptr;
1498 } else {
1499 seenRelro |=
1500 sec->relro && !(sec->type == SHT_NOBITS && (sec->flags & SHF_TLS));
1501 }
1502 }
1503
1504 // It is common practice to use very generic linker scripts. So for any
1505 // given run some of the output sections in the script will be empty.
1506 // We could create corresponding empty output sections, but that would
1507 // clutter the output.
1508 // We instead remove trivially empty sections. The bfd linker seems even
1509 // more aggressive at removing them.
1510 llvm::erase_if(C&: sectionCommands, P: [&](SectionCommand *cmd) { return !cmd; });
1511}
1512
1513void LinkerScript::adjustSectionsAfterSorting() {
1514 // Try and find an appropriate memory region to assign offsets in.
1515 MemoryRegion *hint = nullptr;
1516 for (SectionCommand *cmd : sectionCommands) {
1517 if (auto *osd = dyn_cast<OutputDesc>(Val: cmd)) {
1518 OutputSection *sec = &osd->osec;
1519 if (!sec->lmaRegionName.empty()) {
1520 if (MemoryRegion *m = memoryRegions.lookup(Key: sec->lmaRegionName))
1521 sec->lmaRegion = m;
1522 else
1523 ErrAlways(ctx) << "memory region '" << sec->lmaRegionName
1524 << "' not declared";
1525 }
1526 std::tie(args&: sec->memRegion, args&: hint) = findMemoryRegion(sec, hint);
1527 }
1528 }
1529
1530 // If output section command doesn't specify any segments,
1531 // and we haven't previously assigned any section to segment,
1532 // then we simply assign section to the very first load segment.
1533 // Below is an example of such linker script:
1534 // PHDRS { seg PT_LOAD; }
1535 // SECTIONS { .aaa : { *(.aaa) } }
1536 SmallVector<StringRef, 0> defPhdrs;
1537 auto firstPtLoad = llvm::find_if(Range&: phdrsCommands, P: [](const PhdrsCommand &cmd) {
1538 return cmd.type == PT_LOAD;
1539 });
1540 if (firstPtLoad != phdrsCommands.end())
1541 defPhdrs.push_back(Elt: firstPtLoad->name);
1542
1543 // Walk the commands and propagate the program headers to commands that don't
1544 // explicitly specify them.
1545 for (SectionCommand *cmd : sectionCommands)
1546 if (auto *osd = dyn_cast<OutputDesc>(Val: cmd))
1547 maybePropagatePhdrs(sec&: osd->osec, phdrs&: defPhdrs);
1548}
1549
1550// When the SECTIONS command is used, try to find an address for the file and
1551// program headers output sections, which can be added to the first PT_LOAD
1552// segment when program headers are created.
1553//
1554// We check if the headers fit below the first allocated section. If there isn't
1555// enough space for these sections, we'll remove them from the PT_LOAD segment,
1556// and we'll also remove the PT_PHDR segment.
1557void LinkerScript::allocateHeaders(
1558 SmallVector<std::unique_ptr<PhdrEntry>, 0> &phdrs) {
1559 uint64_t min = std::numeric_limits<uint64_t>::max();
1560 for (OutputSection *sec : ctx.outputSections)
1561 if (sec->flags & SHF_ALLOC)
1562 min = std::min<uint64_t>(a: min, b: sec->addr);
1563
1564 auto it = llvm::find_if(Range&: phdrs, P: [](auto &e) { return e->p_type == PT_LOAD; });
1565 if (it == phdrs.end())
1566 return;
1567 PhdrEntry *firstPTLoad = it->get();
1568
1569 bool hasExplicitHeaders =
1570 llvm::any_of(Range&: phdrsCommands, P: [](const PhdrsCommand &cmd) {
1571 return cmd.hasPhdrs || cmd.hasFilehdr;
1572 });
1573 bool paged = !ctx.arg.omagic && !ctx.arg.nmagic;
1574 uint64_t headerSize = getHeaderSize(ctx);
1575
1576 uint64_t base = 0;
1577 // If SECTIONS is present and the linkerscript is not explicit about program
1578 // headers, only allocate program headers if that would not add a page.
1579 if (hasSectionsCommand && !hasExplicitHeaders)
1580 base = alignDown(Value: min, Align: ctx.arg.maxPageSize);
1581 if ((paged || hasExplicitHeaders) && headerSize <= min - base) {
1582 min = alignDown(Value: min - headerSize, Align: ctx.arg.maxPageSize);
1583 ctx.out.elfHeader->addr = min;
1584 ctx.out.programHeaders->addr = min + ctx.out.elfHeader->size;
1585 return;
1586 }
1587
1588 // Error if we were explicitly asked to allocate headers.
1589 if (hasExplicitHeaders)
1590 ErrAlways(ctx) << "could not allocate headers";
1591
1592 ctx.out.elfHeader->ptLoad = nullptr;
1593 ctx.out.programHeaders->ptLoad = nullptr;
1594 firstPTLoad->firstSec = findFirstSection(ctx, load: firstPTLoad);
1595
1596 llvm::erase_if(C&: phdrs, P: [](auto &e) { return e->p_type == PT_PHDR; });
1597}
1598
1599LinkerScript::AddressState::AddressState(const LinkerScript &script) {
1600 for (auto &mri : script.memoryRegions) {
1601 MemoryRegion *mr = mri.second;
1602 mr->curPos = (mr->origin)().getValue();
1603 }
1604}
1605
1606// Here we assign addresses as instructed by linker script SECTIONS
1607// sub-commands. Doing that allows us to use final VA values, so here
1608// we also handle rest commands like symbol assignments and ASSERTs.
1609// Return an output section that has changed its address or null, and a symbol
1610// that has changed its section or value (or nullptr if no symbol has changed).
1611std::pair<const OutputSection *, const Defined *>
1612LinkerScript::assignAddresses() {
1613 if (hasSectionsCommand) {
1614 // With a linker script, assignment of addresses to headers is covered by
1615 // allocateHeaders().
1616 dot = ctx.arg.imageBase.value_or(u: 0);
1617 } else {
1618 // Assign addresses to headers right now.
1619 dot = ctx.target->getImageBase();
1620 ctx.out.elfHeader->addr = dot;
1621 ctx.out.programHeaders->addr = dot + ctx.out.elfHeader->size;
1622 dot += getHeaderSize(ctx);
1623 }
1624
1625 OutputSection *changedOsec = nullptr;
1626 AddressState st(*this);
1627 state = &st;
1628 errorOnMissingSection = true;
1629 st.outSec = aether.get();
1630 recordedErrors.clear();
1631
1632 SymbolAssignmentMap oldValues = getSymbolAssignmentValues(sectionCommands);
1633 for (SectionCommand *cmd : sectionCommands) {
1634 if (auto *assign = dyn_cast<SymbolAssignment>(Val: cmd)) {
1635 assign->addr = dot;
1636 assignSymbol(cmd: assign, inSec: false);
1637 assign->size = dot - assign->addr;
1638 continue;
1639 }
1640 if (isa<SectionClassDesc>(Val: cmd))
1641 continue;
1642 if (assignOffsets(sec: &cast<OutputDesc>(Val: cmd)->osec) && !changedOsec)
1643 changedOsec = &cast<OutputDesc>(Val: cmd)->osec;
1644 }
1645
1646 state = nullptr;
1647 return {changedOsec, getChangedSymbolAssignment(oldValues)};
1648}
1649
1650static bool hasRegionOverflowed(MemoryRegion *mr) {
1651 if (!mr)
1652 return false;
1653 return mr->curPos - mr->getOrigin() > mr->getLength();
1654}
1655
1656// Spill input sections in reverse order of address assignment to (potentially)
1657// bring memory regions out of overflow. The size savings of a spill can only be
1658// estimated, since general linker script arithmetic may occur afterwards.
1659// Under-estimates may cause unnecessary spills, but over-estimates can always
1660// be corrected on the next pass.
1661bool LinkerScript::spillSections() {
1662 if (potentialSpillLists.empty())
1663 return false;
1664
1665 DenseSet<PotentialSpillSection *> skippedSpills;
1666
1667 bool spilled = false;
1668 for (SectionCommand *cmd : reverse(C&: sectionCommands)) {
1669 auto *osd = dyn_cast<OutputDesc>(Val: cmd);
1670 if (!osd)
1671 continue;
1672 OutputSection *osec = &osd->osec;
1673 if (!osec->memRegion)
1674 continue;
1675
1676 // Input sections that have replaced a potential spill and should be removed
1677 // from their input section description.
1678 DenseSet<InputSection *> spilledInputSections;
1679
1680 for (SectionCommand *cmd : reverse(C&: osec->commands)) {
1681 if (!hasRegionOverflowed(mr: osec->memRegion) &&
1682 !hasRegionOverflowed(mr: osec->lmaRegion))
1683 break;
1684
1685 auto *isd = dyn_cast<InputSectionDescription>(Val: cmd);
1686 if (!isd)
1687 continue;
1688 for (InputSection *isec : reverse(C&: isd->sections)) {
1689 // Potential spill locations cannot be spilled.
1690 if (isa<PotentialSpillSection>(Val: isec))
1691 continue;
1692
1693 auto it = potentialSpillLists.find(Val: isec);
1694 if (it == potentialSpillLists.end())
1695 break;
1696
1697 // Consume spills until finding one that might help, then consume it.
1698 auto canSpillHelp = [&](PotentialSpillSection *spill) {
1699 // Spills to the same region that overflowed cannot help.
1700 if (hasRegionOverflowed(mr: osec->memRegion) &&
1701 spill->getParent()->memRegion == osec->memRegion)
1702 return false;
1703 if (hasRegionOverflowed(mr: osec->lmaRegion) &&
1704 spill->getParent()->lmaRegion == osec->lmaRegion)
1705 return false;
1706 return true;
1707 };
1708 PotentialSpillList &list = it->second;
1709 PotentialSpillSection *spill;
1710 for (spill = list.head; spill; spill = spill->next) {
1711 if (list.head->next)
1712 list.head = spill->next;
1713 else
1714 potentialSpillLists.erase(Val: isec);
1715 if (canSpillHelp(spill))
1716 break;
1717 skippedSpills.insert(V: spill);
1718 }
1719 if (!spill)
1720 continue;
1721
1722 // Replace the next spill location with the spilled section and adjust
1723 // its properties to match the new location. Note that the alignment of
1724 // the spill section may have diverged from the original due to e.g. a
1725 // SUBALIGN. Correct assignment requires the spill's alignment to be
1726 // used, not the original.
1727 spilledInputSections.insert(V: isec);
1728 *llvm::find(Range&: spill->isd->sections, Val: spill) = isec;
1729 isec->parent = spill->parent;
1730 isec->addralign = spill->addralign;
1731
1732 // Record the (potential) reduction in the region's end position.
1733 osec->memRegion->curPos -= isec->getSize();
1734 if (osec->lmaRegion)
1735 osec->lmaRegion->curPos -= isec->getSize();
1736
1737 // Spilling continues until the end position no longer overflows the
1738 // region. Then, another round of address assignment will either confirm
1739 // the spill's success or lead to yet more spilling.
1740 if (!hasRegionOverflowed(mr: osec->memRegion) &&
1741 !hasRegionOverflowed(mr: osec->lmaRegion))
1742 break;
1743 }
1744
1745 // Remove any spilled input sections to complete their move.
1746 if (!spilledInputSections.empty()) {
1747 spilled = true;
1748 llvm::erase_if(C&: isd->sections, P: [&](InputSection *isec) {
1749 return spilledInputSections.contains(V: isec);
1750 });
1751 }
1752 }
1753 }
1754
1755 // Clean up any skipped spills.
1756 DenseSet<InputSectionDescription *> isds;
1757 for (PotentialSpillSection *s : skippedSpills)
1758 isds.insert(V: s->isd);
1759 for (InputSectionDescription *isd : isds)
1760 llvm::erase_if(C&: isd->sections, P: [&](InputSection *s) {
1761 return skippedSpills.contains(V: dyn_cast<PotentialSpillSection>(Val: s));
1762 });
1763
1764 return spilled;
1765}
1766
1767// Erase any potential spill sections that were not used.
1768void LinkerScript::erasePotentialSpillSections() {
1769 if (potentialSpillLists.empty())
1770 return;
1771
1772 // Collect the set of input section descriptions that contain potential
1773 // spills.
1774 DenseSet<InputSectionDescription *> isds;
1775 for (const auto &[_, list] : potentialSpillLists)
1776 for (PotentialSpillSection *s = list.head; s; s = s->next)
1777 isds.insert(V: s->isd);
1778
1779 for (InputSectionDescription *isd : isds)
1780 llvm::erase_if(C&: isd->sections, P: [](InputSection *s) {
1781 return isa<PotentialSpillSection>(Val: s);
1782 });
1783
1784 potentialSpillLists.clear();
1785}
1786
1787// Creates program headers as instructed by PHDRS linker script command.
1788SmallVector<std::unique_ptr<PhdrEntry>, 0> LinkerScript::createPhdrs() {
1789 SmallVector<std::unique_ptr<PhdrEntry>, 0> ret;
1790
1791 // Process PHDRS and FILEHDR keywords because they are not
1792 // real output sections and cannot be added in the following loop.
1793 for (const PhdrsCommand &cmd : phdrsCommands) {
1794 auto phdr =
1795 std::make_unique<PhdrEntry>(args&: ctx, args: cmd.type, args: cmd.flags.value_or(u: PF_R));
1796
1797 if (cmd.hasFilehdr)
1798 phdr->add(sec: ctx.out.elfHeader.get());
1799 if (cmd.hasPhdrs)
1800 phdr->add(sec: ctx.out.programHeaders.get());
1801
1802 if (cmd.lmaExpr) {
1803 phdr->p_paddr = cmd.lmaExpr().getValue();
1804 phdr->hasLMA = true;
1805 }
1806 ret.push_back(Elt: std::move(phdr));
1807 }
1808
1809 // Add output sections to program headers.
1810 for (OutputSection *sec : ctx.outputSections) {
1811 // Assign headers specified by linker script
1812 for (size_t id : getPhdrIndices(sec)) {
1813 ret[id]->add(sec);
1814 if (!phdrsCommands[id].flags)
1815 ret[id]->p_flags |= sec->getPhdrFlags();
1816 }
1817 }
1818 return ret;
1819}
1820
1821// Returns true if we should emit an .interp section.
1822//
1823// We usually do. But if PHDRS commands are given, and
1824// no PT_INTERP is there, there's no place to emit an
1825// .interp, so we don't do that in that case.
1826bool LinkerScript::needsInterpSection() {
1827 if (phdrsCommands.empty())
1828 return true;
1829 for (PhdrsCommand &cmd : phdrsCommands)
1830 if (cmd.type == PT_INTERP)
1831 return true;
1832 return false;
1833}
1834
1835ExprValue LinkerScript::getSymbolValue(StringRef name, const Twine &loc) {
1836 if (name == ".") {
1837 if (state)
1838 return {state->outSec, false, dot - state->outSec->addr, loc};
1839 ErrAlways(ctx) << loc << ": unable to get location counter value";
1840 return 0;
1841 }
1842
1843 if (Symbol *sym = ctx.symtab->find(name)) {
1844 if (auto *ds = dyn_cast<Defined>(Val: sym)) {
1845 ExprValue v{ds->section, false, ds->value, loc};
1846 // Retain the original st_type, so that the alias will get the same
1847 // behavior in relocation processing. Any operation will reset st_type to
1848 // STT_NOTYPE.
1849 v.type = ds->type;
1850 return v;
1851 }
1852 if (isa<SharedSymbol>(Val: sym))
1853 if (!errorOnMissingSection)
1854 return {nullptr, false, 0, loc};
1855 }
1856
1857 ErrAlways(ctx) << loc << ": symbol not found: " << name;
1858 return 0;
1859}
1860
1861// Returns the index of the segment named Name.
1862static std::optional<size_t> getPhdrIndex(ArrayRef<PhdrsCommand> vec,
1863 StringRef name) {
1864 for (size_t i = 0; i < vec.size(); ++i)
1865 if (vec[i].name == name)
1866 return i;
1867 return std::nullopt;
1868}
1869
1870// Returns indices of ELF headers containing specific section. Each index is a
1871// zero based number of ELF header listed within PHDRS {} script block.
1872SmallVector<size_t, 0> LinkerScript::getPhdrIndices(OutputSection *cmd) {
1873 SmallVector<size_t, 0> ret;
1874
1875 for (StringRef s : cmd->phdrs) {
1876 if (std::optional<size_t> idx = getPhdrIndex(vec: phdrsCommands, name: s))
1877 ret.push_back(Elt: *idx);
1878 else if (s != "NONE")
1879 ErrAlways(ctx) << cmd->location << ": program header '" << s
1880 << "' is not listed in PHDRS";
1881 }
1882 return ret;
1883}
1884
1885void LinkerScript::printMemoryUsage(raw_ostream& os) {
1886 auto printSize = [&](uint64_t size) {
1887 if ((size & 0x3fffffff) == 0)
1888 os << format_decimal(N: size >> 30, Width: 10) << " GB";
1889 else if ((size & 0xfffff) == 0)
1890 os << format_decimal(N: size >> 20, Width: 10) << " MB";
1891 else if ((size & 0x3ff) == 0)
1892 os << format_decimal(N: size >> 10, Width: 10) << " KB";
1893 else
1894 os << " " << format_decimal(N: size, Width: 10) << " B";
1895 };
1896 os << "Memory region Used Size Region Size %age Used\n";
1897 for (auto &pair : memoryRegions) {
1898 MemoryRegion *m = pair.second;
1899 uint64_t usedLength = m->curPos - m->getOrigin();
1900 os << right_justify(Str: m->name, Width: 16) << ": ";
1901 printSize(usedLength);
1902 uint64_t length = m->getLength();
1903 if (length != 0) {
1904 printSize(length);
1905 double percent = usedLength * 100.0 / length;
1906 os << " " << format(Fmt: "%6.2f%%", Vals: percent);
1907 }
1908 os << '\n';
1909 }
1910}
1911
1912void LinkerScript::recordError(const Twine &msg) {
1913 auto &str = recordedErrors.emplace_back();
1914 msg.toVector(Out&: str);
1915}
1916
1917static void checkMemoryRegion(Ctx &ctx, const MemoryRegion *region,
1918 const OutputSection *osec, uint64_t addr) {
1919 uint64_t osecEnd = addr + osec->size;
1920 uint64_t regionEnd = region->getOrigin() + region->getLength();
1921 if (osecEnd > regionEnd) {
1922 ErrAlways(ctx) << "section '" << osec->name << "' will not fit in region '"
1923 << region->name << "': overflowed by "
1924 << (osecEnd - regionEnd) << " bytes";
1925 }
1926}
1927
1928void LinkerScript::checkFinalScriptConditions() const {
1929 for (StringRef err : recordedErrors)
1930 Err(ctx) << err;
1931 for (const OutputSection *sec : ctx.outputSections) {
1932 if (const MemoryRegion *memoryRegion = sec->memRegion)
1933 checkMemoryRegion(ctx, region: memoryRegion, osec: sec, addr: sec->addr);
1934 if (const MemoryRegion *lmaRegion = sec->lmaRegion)
1935 checkMemoryRegion(ctx, region: lmaRegion, osec: sec, addr: sec->getLMA());
1936 }
1937}
1938
1939void LinkerScript::addScriptReferencedSymbolsToSymTable() {
1940 // Some symbols (such as __ehdr_start) are defined lazily only when there
1941 // are undefined symbols for them, so we add these to trigger that logic.
1942 auto reference = [&ctx = ctx](StringRef name) {
1943 Symbol *sym = ctx.symtab->addUnusedUndefined(name);
1944 sym->isUsedInRegularObj = true;
1945 sym->referenced = true;
1946 };
1947 for (StringRef name : referencedSymbols)
1948 reference(name);
1949
1950 // Keeps track of references from which PROVIDE symbols have been added to the
1951 // symbol table.
1952 DenseSet<StringRef> added;
1953 SmallVector<const SmallVector<StringRef, 0> *, 0> symRefsVec;
1954 for (const auto &[name, symRefs] : provideMap)
1955 if (shouldAddProvideSym(symName: name) && added.insert(V: name).second)
1956 symRefsVec.push_back(Elt: &symRefs);
1957 while (symRefsVec.size()) {
1958 for (StringRef name : *symRefsVec.pop_back_val()) {
1959 reference(name);
1960 // Prevent the symbol from being discarded by --gc-sections.
1961 referencedSymbols.push_back(Elt: name);
1962 auto it = provideMap.find(Key: name);
1963 if (it != provideMap.end() && shouldAddProvideSym(symName: name) &&
1964 added.insert(V: name).second) {
1965 symRefsVec.push_back(Elt: &it->second);
1966 }
1967 }
1968 }
1969}
1970
1971bool LinkerScript::shouldAddProvideSym(StringRef symName) {
1972 // This function is called before and after garbage collection. To prevent
1973 // undefined references from the RHS, the result of this function for a
1974 // symbol must be the same for each call. We use unusedProvideSyms to not
1975 // change the return value of a demoted symbol.
1976 Symbol *sym = ctx.symtab->find(name: symName);
1977 if (!sym)
1978 return false;
1979 if (sym->isDefined() || sym->isCommon()) {
1980 unusedProvideSyms.insert(V: sym);
1981 return false;
1982 }
1983 return !unusedProvideSyms.contains(V: sym);
1984}
1985