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