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 "lld/Common/Threads.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/FileSystem.h"
32 #include "llvm/Support/Path.h"
33 #include <algorithm>
34 #include <cassert>
35 #include <cstddef>
36 #include <cstdint>
37 #include <iterator>
38 #include <limits>
39 #include <string>
40 #include <vector>
41
42 using namespace llvm;
43 using namespace llvm::ELF;
44 using namespace llvm::object;
45 using namespace llvm::support::endian;
46 using namespace lld;
47 using namespace lld::elf;
48
49 LinkerScript *elf::script;
50
getOutputSectionVA(SectionBase * inputSec,StringRef loc)51 static uint64_t getOutputSectionVA(SectionBase *inputSec, StringRef loc) {
52 if (OutputSection *os = inputSec->getOutputSection())
53 return os->addr;
54 error(loc + ": unable to evaluate expression: input section " +
55 inputSec->name + " has no output section assigned");
56 return 0;
57 }
58
getValue() const59 uint64_t ExprValue::getValue() const {
60 if (sec)
61 return alignTo(sec->getOffset(val) + getOutputSectionVA(sec, loc),
62 alignment);
63 return alignTo(val, alignment);
64 }
65
getSecAddr() const66 uint64_t ExprValue::getSecAddr() const {
67 if (sec)
68 return sec->getOffset(0) + getOutputSectionVA(sec, loc);
69 return 0;
70 }
71
getSectionOffset() const72 uint64_t ExprValue::getSectionOffset() const {
73 // If the alignment is trivial, we don't have to compute the full
74 // value to know the offset. This allows this function to succeed in
75 // cases where the output section is not yet known.
76 if (alignment == 1 && (!sec || !sec->getOutputSection()))
77 return val;
78 return getValue() - getSecAddr();
79 }
80
createOutputSection(StringRef name,StringRef location)81 OutputSection *LinkerScript::createOutputSection(StringRef name,
82 StringRef location) {
83 OutputSection *&secRef = nameToOutputSection[name];
84 OutputSection *sec;
85 if (secRef && secRef->location.empty()) {
86 // There was a forward reference.
87 sec = secRef;
88 } else {
89 sec = make<OutputSection>(name, SHT_PROGBITS, 0);
90 if (!secRef)
91 secRef = sec;
92 }
93 sec->location = location;
94 return sec;
95 }
96
getOrCreateOutputSection(StringRef name)97 OutputSection *LinkerScript::getOrCreateOutputSection(StringRef name) {
98 OutputSection *&cmdRef = nameToOutputSection[name];
99 if (!cmdRef)
100 cmdRef = make<OutputSection>(name, SHT_PROGBITS, 0);
101 return cmdRef;
102 }
103
104 // Expands the memory region by the specified size.
expandMemoryRegion(MemoryRegion * memRegion,uint64_t size,StringRef regionName,StringRef secName)105 static void expandMemoryRegion(MemoryRegion *memRegion, uint64_t size,
106 StringRef regionName, StringRef secName) {
107 memRegion->curPos += size;
108 uint64_t newSize = memRegion->curPos - memRegion->origin;
109 if (newSize > memRegion->length)
110 error("section '" + secName + "' will not fit in region '" + regionName +
111 "': overflowed by " + Twine(newSize - memRegion->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 // This function is called from processSectionCommands,
161 // while we are fixing the output section layout.
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 New(nullptr, cmd->name, STB_GLOBAL, visibility, STT_NOTYPE, symValue,
185 0, sec);
186
187 Symbol *sym = symtab->insert(cmd->name);
188 sym->mergeProperties(New);
189 sym->replace(New);
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 New(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(New);
206 sym->replace(New);
207
208 cmd->sym = cast<Defined>(sym);
209 cmd->provide = false;
210 sym->scriptDefined = true;
211 }
212
213 // This method is used to handle INSERT AFTER statement. Here we rebuild
214 // the list of script commands to mix sections inserted into.
processInsertCommands()215 void LinkerScript::processInsertCommands() {
216 std::vector<BaseCommand *> v;
217 auto insert = [&](std::vector<BaseCommand *> &from) {
218 v.insert(v.end(), from.begin(), from.end());
219 from.clear();
220 };
221
222 for (BaseCommand *base : sectionCommands) {
223 if (auto *os = dyn_cast<OutputSection>(base)) {
224 insert(insertBeforeCommands[os->name]);
225 v.push_back(base);
226 insert(insertAfterCommands[os->name]);
227 continue;
228 }
229 v.push_back(base);
230 }
231
232 for (auto &cmds : {insertBeforeCommands, insertAfterCommands})
233 for (const std::pair<StringRef, std::vector<BaseCommand *>> &p : cmds)
234 if (!p.second.empty())
235 error("unable to INSERT AFTER/BEFORE " + p.first +
236 ": section not defined");
237
238 sectionCommands = std::move(v);
239 }
240
241 // Symbols defined in script should not be inlined by LTO. At the same time
242 // we don't know their final values until late stages of link. Here we scan
243 // over symbol assignment commands and create placeholder symbols if needed.
declareSymbols()244 void LinkerScript::declareSymbols() {
245 assert(!ctx);
246 for (BaseCommand *base : sectionCommands) {
247 if (auto *cmd = dyn_cast<SymbolAssignment>(base)) {
248 declareSymbol(cmd);
249 continue;
250 }
251
252 // If the output section directive has constraints,
253 // we can't say for sure if it is going to be included or not.
254 // Skip such sections for now. Improve the checks if we ever
255 // need symbols from that sections to be declared early.
256 auto *sec = cast<OutputSection>(base);
257 if (sec->constraint != ConstraintKind::NoConstraint)
258 continue;
259 for (BaseCommand *base2 : sec->sectionCommands)
260 if (auto *cmd = dyn_cast<SymbolAssignment>(base2))
261 declareSymbol(cmd);
262 }
263 }
264
265 // This function is called from assignAddresses, while we are
266 // fixing the output section addresses. This function is supposed
267 // to set the final value for a given symbol assignment.
assignSymbol(SymbolAssignment * cmd,bool inSec)268 void LinkerScript::assignSymbol(SymbolAssignment *cmd, bool inSec) {
269 if (cmd->name == ".") {
270 setDot(cmd->expression, cmd->location, inSec);
271 return;
272 }
273
274 if (!cmd->sym)
275 return;
276
277 ExprValue v = cmd->expression();
278 if (v.isAbsolute()) {
279 cmd->sym->section = nullptr;
280 cmd->sym->value = v.getValue();
281 } else {
282 cmd->sym->section = v.sec;
283 cmd->sym->value = v.getSectionOffset();
284 }
285 }
286
getFilename(InputFile * file)287 static std::string getFilename(InputFile *file) {
288 if (!file)
289 return "";
290 if (file->archiveName.empty())
291 return file->getName();
292 return (file->archiveName + "(" + file->getName() + ")").str();
293 }
294
shouldKeep(InputSectionBase * s)295 bool LinkerScript::shouldKeep(InputSectionBase *s) {
296 if (keptSections.empty())
297 return false;
298 std::string filename = getFilename(s->file);
299 for (InputSectionDescription *id : keptSections)
300 if (id->filePat.match(filename))
301 for (SectionPattern &p : id->sectionPatterns)
302 if (p.sectionPat.match(s->name))
303 return true;
304 return false;
305 }
306
307 // A helper function for the SORT() command.
308 static std::function<bool(InputSectionBase *, InputSectionBase *)>
getComparator(SortSectionPolicy k)309 getComparator(SortSectionPolicy k) {
310 switch (k) {
311 case SortSectionPolicy::Alignment:
312 return [](InputSectionBase *a, InputSectionBase *b) {
313 // ">" is not a mistake. Sections with larger alignments are placed
314 // before sections with smaller alignments in order to reduce the
315 // amount of padding necessary. This is compatible with GNU.
316 return a->alignment > b->alignment;
317 };
318 case SortSectionPolicy::Name:
319 return [](InputSectionBase *a, InputSectionBase *b) {
320 return a->name < b->name;
321 };
322 case SortSectionPolicy::Priority:
323 return [](InputSectionBase *a, InputSectionBase *b) {
324 return getPriority(a->name) < getPriority(b->name);
325 };
326 default:
327 llvm_unreachable("unknown sort policy");
328 }
329 }
330
331 // A helper function for the SORT() command.
matchConstraints(ArrayRef<InputSection * > sections,ConstraintKind kind)332 static bool matchConstraints(ArrayRef<InputSection *> sections,
333 ConstraintKind kind) {
334 if (kind == ConstraintKind::NoConstraint)
335 return true;
336
337 bool isRW = llvm::any_of(
338 sections, [](InputSection *sec) { return sec->flags & SHF_WRITE; });
339
340 return (isRW && kind == ConstraintKind::ReadWrite) ||
341 (!isRW && kind == ConstraintKind::ReadOnly);
342 }
343
sortSections(MutableArrayRef<InputSection * > vec,SortSectionPolicy k)344 static void sortSections(MutableArrayRef<InputSection *> vec,
345 SortSectionPolicy k) {
346 if (k != SortSectionPolicy::Default && k != SortSectionPolicy::None)
347 llvm::stable_sort(vec, getComparator(k));
348 }
349
350 // Sort sections as instructed by SORT-family commands and --sort-section
351 // option. Because SORT-family commands can be nested at most two depth
352 // (e.g. SORT_BY_NAME(SORT_BY_ALIGNMENT(.text.*))) and because the command
353 // line option is respected even if a SORT command is given, the exact
354 // behavior we have here is a bit complicated. Here are the rules.
355 //
356 // 1. If two SORT commands are given, --sort-section is ignored.
357 // 2. If one SORT command is given, and if it is not SORT_NONE,
358 // --sort-section is handled as an inner SORT command.
359 // 3. If one SORT command is given, and if it is SORT_NONE, don't sort.
360 // 4. If no SORT command is given, sort according to --sort-section.
sortInputSections(MutableArrayRef<InputSection * > vec,const SectionPattern & pat)361 static void sortInputSections(MutableArrayRef<InputSection *> vec,
362 const SectionPattern &pat) {
363 if (pat.sortOuter == SortSectionPolicy::None)
364 return;
365
366 if (pat.sortInner == SortSectionPolicy::Default)
367 sortSections(vec, config->sortSection);
368 else
369 sortSections(vec, pat.sortInner);
370 sortSections(vec, pat.sortOuter);
371 }
372
373 // Compute and remember which sections the InputSectionDescription matches.
374 std::vector<InputSection *>
computeInputSections(const InputSectionDescription * cmd)375 LinkerScript::computeInputSections(const InputSectionDescription *cmd) {
376 std::vector<InputSection *> ret;
377
378 // Collects all sections that satisfy constraints of Cmd.
379 for (const SectionPattern &pat : cmd->sectionPatterns) {
380 size_t sizeBefore = ret.size();
381
382 for (InputSectionBase *sec : inputSections) {
383 if (!sec->isLive() || sec->assigned)
384 continue;
385
386 // For -emit-relocs we have to ignore entries like
387 // .rela.dyn : { *(.rela.data) }
388 // which are common because they are in the default bfd script.
389 // We do not ignore SHT_REL[A] linker-synthesized sections here because
390 // want to support scripts that do custom layout for them.
391 if (auto *isec = dyn_cast<InputSection>(sec))
392 if (isec->getRelocatedSection())
393 continue;
394
395 std::string filename = getFilename(sec->file);
396 if (!cmd->filePat.match(filename) ||
397 pat.excludedFilePat.match(filename) ||
398 !pat.sectionPat.match(sec->name))
399 continue;
400
401 // It is safe to assume that Sec is an InputSection
402 // because mergeable or EH input sections have already been
403 // handled and eliminated.
404 ret.push_back(cast<InputSection>(sec));
405 sec->assigned = true;
406 }
407
408 sortInputSections(MutableArrayRef<InputSection *>(ret).slice(sizeBefore),
409 pat);
410 }
411 return ret;
412 }
413
discard(ArrayRef<InputSection * > v)414 void LinkerScript::discard(ArrayRef<InputSection *> v) {
415 for (InputSection *s : v) {
416 if (s == in.shStrTab || s == mainPart->relaDyn || s == mainPart->relrDyn)
417 error("discarding " + s->name + " section is not allowed");
418
419 // You can discard .hash and .gnu.hash sections by linker scripts. Since
420 // they are synthesized sections, we need to handle them differently than
421 // other regular sections.
422 if (s == mainPart->gnuHashTab)
423 mainPart->gnuHashTab = nullptr;
424 if (s == mainPart->hashTab)
425 mainPart->hashTab = nullptr;
426
427 s->assigned = false;
428 s->markDead();
429 discard(s->dependentSections);
430 }
431 }
432
433 std::vector<InputSection *>
createInputSectionList(OutputSection & outCmd)434 LinkerScript::createInputSectionList(OutputSection &outCmd) {
435 std::vector<InputSection *> ret;
436
437 for (BaseCommand *base : outCmd.sectionCommands) {
438 if (auto *cmd = dyn_cast<InputSectionDescription>(base)) {
439 cmd->sections = computeInputSections(cmd);
440 ret.insert(ret.end(), cmd->sections.begin(), cmd->sections.end());
441 }
442 }
443 return ret;
444 }
445
processSectionCommands()446 void LinkerScript::processSectionCommands() {
447 // A symbol can be assigned before any section is mentioned in the linker
448 // script. In an DSO, the symbol values are addresses, so the only important
449 // section values are:
450 // * SHN_UNDEF
451 // * SHN_ABS
452 // * Any value meaning a regular section.
453 // To handle that, create a dummy aether section that fills the void before
454 // the linker scripts switches to another section. It has an index of one
455 // which will map to whatever the first actual section is.
456 aether = make<OutputSection>("", 0, SHF_ALLOC);
457 aether->sectionIndex = 1;
458
459 // Ctx captures the local AddressState and makes it accessible deliberately.
460 // This is needed as there are some cases where we cannot just
461 // thread the current state through to a lambda function created by the
462 // script parser.
463 auto deleter = make_unique<AddressState>();
464 ctx = deleter.get();
465 ctx->outSec = aether;
466
467 size_t i = 0;
468 // Add input sections to output sections.
469 for (BaseCommand *base : sectionCommands) {
470 // Handle symbol assignments outside of any output section.
471 if (auto *cmd = dyn_cast<SymbolAssignment>(base)) {
472 addSymbol(cmd);
473 continue;
474 }
475
476 if (auto *sec = dyn_cast<OutputSection>(base)) {
477 std::vector<InputSection *> v = createInputSectionList(*sec);
478
479 // The output section name `/DISCARD/' is special.
480 // Any input section assigned to it is discarded.
481 if (sec->name == "/DISCARD/") {
482 discard(v);
483 sec->sectionCommands.clear();
484 continue;
485 }
486
487 // This is for ONLY_IF_RO and ONLY_IF_RW. An output section directive
488 // ".foo : ONLY_IF_R[OW] { ... }" is handled only if all member input
489 // sections satisfy a given constraint. If not, a directive is handled
490 // as if it wasn't present from the beginning.
491 //
492 // Because we'll iterate over SectionCommands many more times, the easy
493 // way to "make it as if it wasn't present" is to make it empty.
494 if (!matchConstraints(v, sec->constraint)) {
495 for (InputSectionBase *s : v)
496 s->assigned = false;
497 sec->sectionCommands.clear();
498 continue;
499 }
500
501 // A directive may contain symbol definitions like this:
502 // ".foo : { ...; bar = .; }". Handle them.
503 for (BaseCommand *base : sec->sectionCommands)
504 if (auto *outCmd = dyn_cast<SymbolAssignment>(base))
505 addSymbol(outCmd);
506
507 // Handle subalign (e.g. ".foo : SUBALIGN(32) { ... }"). If subalign
508 // is given, input sections are aligned to that value, whether the
509 // given value is larger or smaller than the original section alignment.
510 if (sec->subalignExpr) {
511 uint32_t subalign = sec->subalignExpr().getValue();
512 for (InputSectionBase *s : v)
513 s->alignment = subalign;
514 }
515
516 // Add input sections to an output section.
517 for (InputSection *s : v)
518 sec->addSection(s);
519
520 sec->sectionIndex = i++;
521 if (sec->noload)
522 sec->type = SHT_NOBITS;
523 if (sec->nonAlloc)
524 sec->flags &= ~(uint64_t)SHF_ALLOC;
525 }
526 }
527 ctx = nullptr;
528 }
529
findByName(ArrayRef<BaseCommand * > vec,StringRef name)530 static OutputSection *findByName(ArrayRef<BaseCommand *> vec,
531 StringRef name) {
532 for (BaseCommand *base : vec)
533 if (auto *sec = dyn_cast<OutputSection>(base))
534 if (sec->name == name)
535 return sec;
536 return nullptr;
537 }
538
createSection(InputSectionBase * isec,StringRef outsecName)539 static OutputSection *createSection(InputSectionBase *isec,
540 StringRef outsecName) {
541 OutputSection *sec = script->createOutputSection(outsecName, "<internal>");
542 sec->addSection(cast<InputSection>(isec));
543 return sec;
544 }
545
546 static OutputSection *
addInputSec(StringMap<TinyPtrVector<OutputSection * >> & map,InputSectionBase * isec,StringRef outsecName)547 addInputSec(StringMap<TinyPtrVector<OutputSection *>> &map,
548 InputSectionBase *isec, StringRef outsecName) {
549 // Sections with SHT_GROUP or SHF_GROUP attributes reach here only when the -r
550 // option is given. A section with SHT_GROUP defines a "section group", and
551 // its members have SHF_GROUP attribute. Usually these flags have already been
552 // stripped by InputFiles.cpp as section groups are processed and uniquified.
553 // However, for the -r option, we want to pass through all section groups
554 // as-is because adding/removing members or merging them with other groups
555 // change their semantics.
556 if (isec->type == SHT_GROUP || (isec->flags & SHF_GROUP))
557 return createSection(isec, outsecName);
558
559 // Imagine .zed : { *(.foo) *(.bar) } script. Both foo and bar may have
560 // relocation sections .rela.foo and .rela.bar for example. Most tools do
561 // not allow multiple REL[A] sections for output section. Hence we
562 // should combine these relocation sections into single output.
563 // We skip synthetic sections because it can be .rela.dyn/.rela.plt or any
564 // other REL[A] sections created by linker itself.
565 if (!isa<SyntheticSection>(isec) &&
566 (isec->type == SHT_REL || isec->type == SHT_RELA)) {
567 auto *sec = cast<InputSection>(isec);
568 OutputSection *out = sec->getRelocatedSection()->getOutputSection();
569
570 if (out->relocationSection) {
571 out->relocationSection->addSection(sec);
572 return nullptr;
573 }
574
575 out->relocationSection = createSection(isec, outsecName);
576 return out->relocationSection;
577 }
578
579 // When control reaches here, mergeable sections have already been merged into
580 // synthetic sections. For relocatable case we want to create one output
581 // section per syntetic section so that they have a valid sh_entsize.
582 if (config->relocatable && (isec->flags & SHF_MERGE))
583 return createSection(isec, outsecName);
584
585 // The ELF spec just says
586 // ----------------------------------------------------------------
587 // In the first phase, input sections that match in name, type and
588 // attribute flags should be concatenated into single sections.
589 // ----------------------------------------------------------------
590 //
591 // However, it is clear that at least some flags have to be ignored for
592 // section merging. At the very least SHF_GROUP and SHF_COMPRESSED have to be
593 // ignored. We should not have two output .text sections just because one was
594 // in a group and another was not for example.
595 //
596 // It also seems that wording was a late addition and didn't get the
597 // necessary scrutiny.
598 //
599 // Merging sections with different flags is expected by some users. One
600 // reason is that if one file has
601 //
602 // int *const bar __attribute__((section(".foo"))) = (int *)0;
603 //
604 // gcc with -fPIC will produce a read only .foo section. But if another
605 // file has
606 //
607 // int zed;
608 // int *const bar __attribute__((section(".foo"))) = (int *)&zed;
609 //
610 // gcc with -fPIC will produce a read write section.
611 //
612 // Last but not least, when using linker script the merge rules are forced by
613 // the script. Unfortunately, linker scripts are name based. This means that
614 // expressions like *(.foo*) can refer to multiple input sections with
615 // different flags. We cannot put them in different output sections or we
616 // would produce wrong results for
617 //
618 // start = .; *(.foo.*) end = .; *(.bar)
619 //
620 // and a mapping of .foo1 and .bar1 to one section and .foo2 and .bar2 to
621 // another. The problem is that there is no way to layout those output
622 // sections such that the .foo sections are the only thing between the start
623 // and end symbols.
624 //
625 // Given the above issues, we instead merge sections by name and error on
626 // incompatible types and flags.
627 TinyPtrVector<OutputSection *> &v = map[outsecName];
628 for (OutputSection *sec : v) {
629 if (sec->partition != isec->partition)
630 continue;
631 sec->addSection(cast<InputSection>(isec));
632 return nullptr;
633 }
634
635 OutputSection *sec = createSection(isec, outsecName);
636 v.push_back(sec);
637 return sec;
638 }
639
640 // Add sections that didn't match any sections command.
addOrphanSections()641 void LinkerScript::addOrphanSections() {
642 StringMap<TinyPtrVector<OutputSection *>> map;
643 std::vector<OutputSection *> v;
644
645 auto add = [&](InputSectionBase *s) {
646 if (!s->isLive() || s->parent)
647 return;
648
649 StringRef name = getOutputSectionName(s);
650
651 if (config->orphanHandling == OrphanHandlingPolicy::Error)
652 error(toString(s) + " is being placed in '" + name + "'");
653 else if (config->orphanHandling == OrphanHandlingPolicy::Warn)
654 warn(toString(s) + " is being placed in '" + name + "'");
655
656 if (OutputSection *sec = findByName(sectionCommands, name)) {
657 sec->addSection(cast<InputSection>(s));
658 return;
659 }
660
661 if (OutputSection *os = addInputSec(map, s, name))
662 v.push_back(os);
663 assert(s->getOutputSection()->sectionIndex == UINT32_MAX);
664 };
665
666 // For futher --emit-reloc handling code we need target output section
667 // to be created before we create relocation output section, so we want
668 // to create target sections first. We do not want priority handling
669 // for synthetic sections because them are special.
670 for (InputSectionBase *isec : inputSections) {
671 if (auto *sec = dyn_cast<InputSection>(isec))
672 if (InputSectionBase *rel = sec->getRelocatedSection())
673 if (auto *relIS = dyn_cast_or_null<InputSectionBase>(rel->parent))
674 add(relIS);
675 add(isec);
676 }
677
678 // If no SECTIONS command was given, we should insert sections commands
679 // before others, so that we can handle scripts which refers them,
680 // for example: "foo = ABSOLUTE(ADDR(.text)));".
681 // When SECTIONS command is present we just add all orphans to the end.
682 if (hasSectionsCommand)
683 sectionCommands.insert(sectionCommands.end(), v.begin(), v.end());
684 else
685 sectionCommands.insert(sectionCommands.begin(), v.begin(), v.end());
686 }
687
advance(uint64_t size,unsigned alignment)688 uint64_t LinkerScript::advance(uint64_t size, unsigned alignment) {
689 bool isTbss =
690 (ctx->outSec->flags & SHF_TLS) && ctx->outSec->type == SHT_NOBITS;
691 uint64_t start = isTbss ? dot + ctx->threadBssOffset : dot;
692 start = alignTo(start, alignment);
693 uint64_t end = start + size;
694
695 if (isTbss)
696 ctx->threadBssOffset = end - dot;
697 else
698 dot = end;
699 return end;
700 }
701
output(InputSection * s)702 void LinkerScript::output(InputSection *s) {
703 assert(ctx->outSec == s->getParent());
704 uint64_t before = advance(0, 1);
705 uint64_t pos = advance(s->getSize(), s->alignment);
706 s->outSecOff = pos - s->getSize() - ctx->outSec->addr;
707
708 // Update output section size after adding each section. This is so that
709 // SIZEOF works correctly in the case below:
710 // .foo { *(.aaa) a = SIZEOF(.foo); *(.bbb) }
711 expandOutputSection(pos - before);
712 }
713
switchTo(OutputSection * sec)714 void LinkerScript::switchTo(OutputSection *sec) {
715 ctx->outSec = sec;
716
717 uint64_t before = advance(0, 1);
718 ctx->outSec->addr = advance(0, ctx->outSec->alignment);
719 expandMemoryRegions(ctx->outSec->addr - before);
720 }
721
722 // This function searches for a memory region to place the given output
723 // section in. If found, a pointer to the appropriate memory region is
724 // returned. Otherwise, a nullptr is returned.
findMemoryRegion(OutputSection * sec)725 MemoryRegion *LinkerScript::findMemoryRegion(OutputSection *sec) {
726 // If a memory region name was specified in the output section command,
727 // then try to find that region first.
728 if (!sec->memoryRegionName.empty()) {
729 if (MemoryRegion *m = memoryRegions.lookup(sec->memoryRegionName))
730 return m;
731 error("memory region '" + sec->memoryRegionName + "' not declared");
732 return nullptr;
733 }
734
735 // If at least one memory region is defined, all sections must
736 // belong to some memory region. Otherwise, we don't need to do
737 // anything for memory regions.
738 if (memoryRegions.empty())
739 return nullptr;
740
741 // See if a region can be found by matching section flags.
742 for (auto &pair : memoryRegions) {
743 MemoryRegion *m = pair.second;
744 if ((m->flags & sec->flags) && (m->negFlags & sec->flags) == 0)
745 return m;
746 }
747
748 // Otherwise, no suitable region was found.
749 if (sec->flags & SHF_ALLOC)
750 error("no memory region specified for section '" + sec->name + "'");
751 return nullptr;
752 }
753
findFirstSection(PhdrEntry * load)754 static OutputSection *findFirstSection(PhdrEntry *load) {
755 for (OutputSection *sec : outputSections)
756 if (sec->ptLoad == load)
757 return sec;
758 return nullptr;
759 }
760
761 // This function assigns offsets to input sections and an output section
762 // for a single sections command (e.g. ".text { *(.text); }").
assignOffsets(OutputSection * sec)763 void LinkerScript::assignOffsets(OutputSection *sec) {
764 if (!(sec->flags & SHF_ALLOC))
765 dot = 0;
766
767 ctx->memRegion = sec->memRegion;
768 ctx->lmaRegion = sec->lmaRegion;
769 if (ctx->memRegion)
770 dot = ctx->memRegion->curPos;
771
772 if ((sec->flags & SHF_ALLOC) && sec->addrExpr)
773 setDot(sec->addrExpr, sec->location, false);
774
775 switchTo(sec);
776
777 if (sec->lmaExpr)
778 ctx->lmaOffset = sec->lmaExpr().getValue() - dot;
779
780 if (MemoryRegion *mr = sec->lmaRegion)
781 ctx->lmaOffset = mr->curPos - dot;
782
783 // If neither AT nor AT> is specified for an allocatable section, the linker
784 // will set the LMA such that the difference between VMA and LMA for the
785 // section is the same as the preceding output section in the same region
786 // https://sourceware.org/binutils/docs-2.20/ld/Output-Section-LMA.html
787 // This, however, should only be done by the first "non-header" section
788 // in the segment.
789 if (PhdrEntry *l = ctx->outSec->ptLoad)
790 if (sec == findFirstSection(l))
791 l->lmaOffset = ctx->lmaOffset;
792
793 // We can call this method multiple times during the creation of
794 // thunks and want to start over calculation each time.
795 sec->size = 0;
796
797 // We visited SectionsCommands from processSectionCommands to
798 // layout sections. Now, we visit SectionsCommands again to fix
799 // section offsets.
800 for (BaseCommand *base : sec->sectionCommands) {
801 // This handles the assignments to symbol or to the dot.
802 if (auto *cmd = dyn_cast<SymbolAssignment>(base)) {
803 cmd->addr = dot;
804 assignSymbol(cmd, true);
805 cmd->size = dot - cmd->addr;
806 continue;
807 }
808
809 // Handle BYTE(), SHORT(), LONG(), or QUAD().
810 if (auto *cmd = dyn_cast<ByteCommand>(base)) {
811 cmd->offset = dot - ctx->outSec->addr;
812 dot += cmd->size;
813 expandOutputSection(cmd->size);
814 continue;
815 }
816
817 // Handle a single input section description command.
818 // It calculates and assigns the offsets for each section and also
819 // updates the output section size.
820 for (InputSection *sec : cast<InputSectionDescription>(base)->sections)
821 output(sec);
822 }
823 }
824
isDiscardable(OutputSection & sec)825 static bool isDiscardable(OutputSection &sec) {
826 if (sec.name == "/DISCARD/")
827 return true;
828
829 // We do not remove empty sections that are explicitly
830 // assigned to any segment.
831 if (!sec.phdrs.empty())
832 return false;
833
834 // We do not want to remove OutputSections with expressions that reference
835 // symbols even if the OutputSection is empty. We want to ensure that the
836 // expressions can be evaluated and report an error if they cannot.
837 if (sec.expressionsUseSymbols)
838 return false;
839
840 // OutputSections may be referenced by name in ADDR and LOADADDR expressions,
841 // as an empty Section can has a valid VMA and LMA we keep the OutputSection
842 // to maintain the integrity of the other Expression.
843 if (sec.usedInExpression)
844 return false;
845
846 for (BaseCommand *base : sec.sectionCommands) {
847 if (auto cmd = dyn_cast<SymbolAssignment>(base))
848 // Don't create empty output sections just for unreferenced PROVIDE
849 // symbols.
850 if (cmd->name != "." && !cmd->sym)
851 continue;
852
853 if (!isa<InputSectionDescription>(*base))
854 return false;
855 }
856 return true;
857 }
858
adjustSectionsBeforeSorting()859 void LinkerScript::adjustSectionsBeforeSorting() {
860 // If the output section contains only symbol assignments, create a
861 // corresponding output section. The issue is what to do with linker script
862 // like ".foo : { symbol = 42; }". One option would be to convert it to
863 // "symbol = 42;". That is, move the symbol out of the empty section
864 // description. That seems to be what bfd does for this simple case. The
865 // problem is that this is not completely general. bfd will give up and
866 // create a dummy section too if there is a ". = . + 1" inside the section
867 // for example.
868 // Given that we want to create the section, we have to worry what impact
869 // it will have on the link. For example, if we just create a section with
870 // 0 for flags, it would change which PT_LOADs are created.
871 // We could remember that particular section is dummy and ignore it in
872 // other parts of the linker, but unfortunately there are quite a few places
873 // that would need to change:
874 // * The program header creation.
875 // * The orphan section placement.
876 // * The address assignment.
877 // The other option is to pick flags that minimize the impact the section
878 // will have on the rest of the linker. That is why we copy the flags from
879 // the previous sections. Only a few flags are needed to keep the impact low.
880 uint64_t flags = SHF_ALLOC;
881
882 for (BaseCommand *&cmd : sectionCommands) {
883 auto *sec = dyn_cast<OutputSection>(cmd);
884 if (!sec)
885 continue;
886
887 // Handle align (e.g. ".foo : ALIGN(16) { ... }").
888 if (sec->alignExpr)
889 sec->alignment =
890 std::max<uint32_t>(sec->alignment, sec->alignExpr().getValue());
891
892 // The input section might have been removed (if it was an empty synthetic
893 // section), but we at least know the flags.
894 if (sec->hasInputSections)
895 flags = sec->flags;
896
897 // We do not want to keep any special flags for output section
898 // in case it is empty.
899 bool isEmpty = getInputSections(sec).empty();
900 if (isEmpty)
901 sec->flags = flags & ((sec->nonAlloc ? 0 : (uint64_t)SHF_ALLOC) |
902 SHF_WRITE | SHF_EXECINSTR);
903
904 if (isEmpty && isDiscardable(*sec)) {
905 sec->markDead();
906 cmd = nullptr;
907 } else if (!sec->isLive()) {
908 sec->markLive();
909 }
910 }
911
912 // It is common practice to use very generic linker scripts. So for any
913 // given run some of the output sections in the script will be empty.
914 // We could create corresponding empty output sections, but that would
915 // clutter the output.
916 // We instead remove trivially empty sections. The bfd linker seems even
917 // more aggressive at removing them.
918 llvm::erase_if(sectionCommands, [&](BaseCommand *base) { return !base; });
919 }
920
adjustSectionsAfterSorting()921 void LinkerScript::adjustSectionsAfterSorting() {
922 // Try and find an appropriate memory region to assign offsets in.
923 for (BaseCommand *base : sectionCommands) {
924 if (auto *sec = dyn_cast<OutputSection>(base)) {
925 if (!sec->lmaRegionName.empty()) {
926 if (MemoryRegion *m = memoryRegions.lookup(sec->lmaRegionName))
927 sec->lmaRegion = m;
928 else
929 error("memory region '" + sec->lmaRegionName + "' not declared");
930 }
931 sec->memRegion = findMemoryRegion(sec);
932 }
933 }
934
935 // If output section command doesn't specify any segments,
936 // and we haven't previously assigned any section to segment,
937 // then we simply assign section to the very first load segment.
938 // Below is an example of such linker script:
939 // PHDRS { seg PT_LOAD; }
940 // SECTIONS { .aaa : { *(.aaa) } }
941 std::vector<StringRef> defPhdrs;
942 auto firstPtLoad = llvm::find_if(phdrsCommands, [](const PhdrsCommand &cmd) {
943 return cmd.type == PT_LOAD;
944 });
945 if (firstPtLoad != phdrsCommands.end())
946 defPhdrs.push_back(firstPtLoad->name);
947
948 // Walk the commands and propagate the program headers to commands that don't
949 // explicitly specify them.
950 for (BaseCommand *base : sectionCommands) {
951 auto *sec = dyn_cast<OutputSection>(base);
952 if (!sec)
953 continue;
954
955 if (sec->phdrs.empty()) {
956 // To match the bfd linker script behaviour, only propagate program
957 // headers to sections that are allocated.
958 if (sec->flags & SHF_ALLOC)
959 sec->phdrs = defPhdrs;
960 } else {
961 defPhdrs = sec->phdrs;
962 }
963 }
964 }
965
computeBase(uint64_t min,bool allocateHeaders)966 static uint64_t computeBase(uint64_t min, bool allocateHeaders) {
967 // If there is no SECTIONS or if the linkerscript is explicit about program
968 // headers, do our best to allocate them.
969 if (!script->hasSectionsCommand || allocateHeaders)
970 return 0;
971 // Otherwise only allocate program headers if that would not add a page.
972 return alignDown(min, config->maxPageSize);
973 }
974
975 // Try to find an address for the file and program headers output sections,
976 // which were unconditionally added to the first PT_LOAD segment earlier.
977 //
978 // When using the default layout, we check if the headers fit below the first
979 // allocated section. When using a linker script, we also check if the headers
980 // are covered by the output section. This allows omitting the headers by not
981 // leaving enough space for them in the linker script; this pattern is common
982 // in embedded systems.
983 //
984 // If there isn't enough space for these sections, we'll remove them from the
985 // PT_LOAD segment, and we'll also remove the PT_PHDR segment.
allocateHeaders(std::vector<PhdrEntry * > & phdrs)986 void LinkerScript::allocateHeaders(std::vector<PhdrEntry *> &phdrs) {
987 uint64_t min = std::numeric_limits<uint64_t>::max();
988 for (OutputSection *sec : outputSections)
989 if (sec->flags & SHF_ALLOC)
990 min = std::min<uint64_t>(min, sec->addr);
991
992 auto it = llvm::find_if(
993 phdrs, [](const PhdrEntry *e) { return e->p_type == PT_LOAD; });
994 if (it == phdrs.end())
995 return;
996 PhdrEntry *firstPTLoad = *it;
997
998 bool hasExplicitHeaders =
999 llvm::any_of(phdrsCommands, [](const PhdrsCommand &cmd) {
1000 return cmd.hasPhdrs || cmd.hasFilehdr;
1001 });
1002 bool paged = !config->omagic && !config->nmagic;
1003 uint64_t headerSize = getHeaderSize();
1004 if ((paged || hasExplicitHeaders) &&
1005 headerSize <= min - computeBase(min, hasExplicitHeaders)) {
1006 min = alignDown(min - headerSize, config->maxPageSize);
1007 Out::elfHeader->addr = min;
1008 Out::programHeaders->addr = min + Out::elfHeader->size;
1009 return;
1010 }
1011
1012 // Error if we were explicitly asked to allocate headers.
1013 if (hasExplicitHeaders)
1014 error("could not allocate headers");
1015
1016 Out::elfHeader->ptLoad = nullptr;
1017 Out::programHeaders->ptLoad = nullptr;
1018 firstPTLoad->firstSec = findFirstSection(firstPTLoad);
1019
1020 llvm::erase_if(phdrs,
1021 [](const PhdrEntry *e) { return e->p_type == PT_PHDR; });
1022 }
1023
AddressState()1024 LinkerScript::AddressState::AddressState() {
1025 for (auto &mri : script->memoryRegions) {
1026 MemoryRegion *mr = mri.second;
1027 mr->curPos = mr->origin;
1028 }
1029 }
1030
getInitialDot()1031 static uint64_t getInitialDot() {
1032 // By default linker scripts use an initial value of 0 for '.',
1033 // but prefer -image-base if set.
1034 if (script->hasSectionsCommand)
1035 return config->imageBase ? *config->imageBase : 0;
1036
1037 uint64_t startAddr = UINT64_MAX;
1038 // The sections with -T<section> have been sorted in order of ascending
1039 // address. We must lower startAddr if the lowest -T<section address> as
1040 // calls to setDot() must be monotonically increasing.
1041 for (auto &kv : config->sectionStartMap)
1042 startAddr = std::min(startAddr, kv.second);
1043 return std::min(startAddr, target->getImageBase() + elf::getHeaderSize());
1044 }
1045
1046 // Here we assign addresses as instructed by linker script SECTIONS
1047 // sub-commands. Doing that allows us to use final VA values, so here
1048 // we also handle rest commands like symbol assignments and ASSERTs.
assignAddresses()1049 void LinkerScript::assignAddresses() {
1050 dot = getInitialDot();
1051
1052 auto deleter = make_unique<AddressState>();
1053 ctx = deleter.get();
1054 errorOnMissingSection = true;
1055 switchTo(aether);
1056
1057 for (BaseCommand *base : sectionCommands) {
1058 if (auto *cmd = dyn_cast<SymbolAssignment>(base)) {
1059 cmd->addr = dot;
1060 assignSymbol(cmd, false);
1061 cmd->size = dot - cmd->addr;
1062 continue;
1063 }
1064 assignOffsets(cast<OutputSection>(base));
1065 }
1066 ctx = nullptr;
1067 }
1068
1069 // Creates program headers as instructed by PHDRS linker script command.
createPhdrs()1070 std::vector<PhdrEntry *> LinkerScript::createPhdrs() {
1071 std::vector<PhdrEntry *> ret;
1072
1073 // Process PHDRS and FILEHDR keywords because they are not
1074 // real output sections and cannot be added in the following loop.
1075 for (const PhdrsCommand &cmd : phdrsCommands) {
1076 PhdrEntry *phdr = make<PhdrEntry>(cmd.type, cmd.flags ? *cmd.flags : PF_R);
1077
1078 if (cmd.hasFilehdr)
1079 phdr->add(Out::elfHeader);
1080 if (cmd.hasPhdrs)
1081 phdr->add(Out::programHeaders);
1082
1083 if (cmd.lmaExpr) {
1084 phdr->p_paddr = cmd.lmaExpr().getValue();
1085 phdr->hasLMA = true;
1086 }
1087 ret.push_back(phdr);
1088 }
1089
1090 // Add output sections to program headers.
1091 for (OutputSection *sec : outputSections) {
1092 // Assign headers specified by linker script
1093 for (size_t id : getPhdrIndices(sec)) {
1094 ret[id]->add(sec);
1095 if (!phdrsCommands[id].flags.hasValue())
1096 ret[id]->p_flags |= sec->getPhdrFlags();
1097 }
1098 }
1099 return ret;
1100 }
1101
1102 // Returns true if we should emit an .interp section.
1103 //
1104 // We usually do. But if PHDRS commands are given, and
1105 // no PT_INTERP is there, there's no place to emit an
1106 // .interp, so we don't do that in that case.
needsInterpSection()1107 bool LinkerScript::needsInterpSection() {
1108 if (phdrsCommands.empty())
1109 return true;
1110 for (PhdrsCommand &cmd : phdrsCommands)
1111 if (cmd.type == PT_INTERP)
1112 return true;
1113 return false;
1114 }
1115
getSymbolValue(StringRef name,const Twine & loc)1116 ExprValue LinkerScript::getSymbolValue(StringRef name, const Twine &loc) {
1117 if (name == ".") {
1118 if (ctx)
1119 return {ctx->outSec, false, dot - ctx->outSec->addr, loc};
1120 error(loc + ": unable to get location counter value");
1121 return 0;
1122 }
1123
1124 if (Symbol *sym = symtab->find(name)) {
1125 if (auto *ds = dyn_cast<Defined>(sym))
1126 return {ds->section, false, ds->value, loc};
1127 if (isa<SharedSymbol>(sym))
1128 if (!errorOnMissingSection)
1129 return {nullptr, false, 0, loc};
1130 }
1131
1132 error(loc + ": symbol not found: " + name);
1133 return 0;
1134 }
1135
1136 // Returns the index of the segment named Name.
getPhdrIndex(ArrayRef<PhdrsCommand> vec,StringRef name)1137 static Optional<size_t> getPhdrIndex(ArrayRef<PhdrsCommand> vec,
1138 StringRef name) {
1139 for (size_t i = 0; i < vec.size(); ++i)
1140 if (vec[i].name == name)
1141 return i;
1142 return None;
1143 }
1144
1145 // Returns indices of ELF headers containing specific section. Each index is a
1146 // zero based number of ELF header listed within PHDRS {} script block.
getPhdrIndices(OutputSection * cmd)1147 std::vector<size_t> LinkerScript::getPhdrIndices(OutputSection *cmd) {
1148 std::vector<size_t> ret;
1149
1150 for (StringRef s : cmd->phdrs) {
1151 if (Optional<size_t> idx = getPhdrIndex(phdrsCommands, s))
1152 ret.push_back(*idx);
1153 else if (s != "NONE")
1154 error(cmd->location + ": section header '" + s +
1155 "' is not listed in PHDRS");
1156 }
1157 return ret;
1158 }
1159