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