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