1 //===- LinkerScript.cpp ---------------------------------------------------===//
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file contains the parser/evaluator of the linker script.
11 // It does not construct an AST but consume linker script directives directly.
12 // Results are written to Driver or Config object.
14 //===----------------------------------------------------------------------===//
16 #include "LinkerScript.h"
19 #include "InputSection.h"
20 #include "OutputSections.h"
21 #include "ScriptParser.h"
24 #include "SymbolTable.h"
26 #include "llvm/ADT/StringSwitch.h"
27 #include "llvm/Support/ELF.h"
28 #include "llvm/Support/FileSystem.h"
29 #include "llvm/Support/MemoryBuffer.h"
30 #include "llvm/Support/Path.h"
31 #include "llvm/Support/StringSaver.h"
34 using namespace llvm::ELF;
35 using namespace llvm::object;
37 using namespace lld::elf;
39 ScriptConfiguration *elf::ScriptConfig;
41 // This is an operator-precedence parser to parse and evaluate
42 // a linker script expression. For each linker script arithmetic
43 // expression (e.g. ". = . + 0x1000"), a new instance of ExprParser
44 // is created and ran.
46 class ExprParser : public ScriptParserBase {
48 ExprParser(std::vector<StringRef> &Tokens, uint64_t Dot)
49 : ScriptParserBase(Tokens), Dot(Dot) {}
54 uint64_t parsePrimary();
55 uint64_t parseTernary(uint64_t Cond);
56 uint64_t apply(StringRef Op, uint64_t L, uint64_t R);
57 uint64_t parseExpr1(uint64_t Lhs, int MinPrec);
64 static int precedence(StringRef Op) {
65 return StringSwitch<int>(Op)
80 static uint64_t evalExpr(std::vector<StringRef> &Tokens, uint64_t Dot) {
81 return ExprParser(Tokens, Dot).run();
84 uint64_t ExprParser::run() {
85 uint64_t V = parseExpr();
86 if (!atEOF() && !Error)
87 setError("stray token: " + peek());
91 // This is a part of the operator-precedence parser to evaluate
92 // arithmetic expressions in SECTIONS command. This function evaluates an
93 // integer literal, a parenthesized expression, the ALIGN function,
94 // or the special variable ".".
95 uint64_t ExprParser::parsePrimary() {
96 StringRef Tok = next();
100 uint64_t V = parseExpr();
104 if (Tok == "ALIGN") {
106 uint64_t V = parseExpr();
108 return alignTo(Dot, V);
111 if (Tok.getAsInteger(0, V))
112 setError("malformed number: " + Tok);
116 uint64_t ExprParser::parseTernary(uint64_t Cond) {
118 uint64_t V = parseExpr();
120 uint64_t W = parseExpr();
124 uint64_t ExprParser::apply(StringRef Op, uint64_t L, uint64_t R) {
129 error("division by zero");
152 llvm_unreachable("invalid operator");
155 // This is a part of the operator-precedence parser.
156 // This function assumes that the remaining token stream starts
158 uint64_t ExprParser::parseExpr1(uint64_t Lhs, int MinPrec) {
160 // Read an operator and an expression.
161 StringRef Op1 = peek();
163 return parseTernary(Lhs);
164 if (precedence(Op1) < MinPrec)
167 uint64_t Rhs = parsePrimary();
169 // Evaluate the remaining part of the expression first if the
170 // next operator has greater precedence than the previous one.
171 // For example, if we have read "+" and "3", and if the next
172 // operator is "*", then we'll evaluate 3 * ... part first.
174 StringRef Op2 = peek();
175 if (precedence(Op2) <= precedence(Op1))
177 Rhs = parseExpr1(Rhs, precedence(Op2));
180 Lhs = apply(Op1, Lhs, Rhs);
185 // Reads and evaluates an arithmetic expression.
186 uint64_t ExprParser::parseExpr() { return parseExpr1(parsePrimary(), 0); }
188 template <class ELFT>
189 StringRef LinkerScript<ELFT>::getOutputSection(InputSectionBase<ELFT> *S) {
190 for (SectionRule &R : Opt.Sections)
191 if (globMatch(R.SectionPattern, S->getSectionName()))
196 template <class ELFT>
197 bool LinkerScript<ELFT>::isDiscarded(InputSectionBase<ELFT> *S) {
198 return getOutputSection(S) == "/DISCARD/";
201 template <class ELFT>
202 bool LinkerScript<ELFT>::shouldKeep(InputSectionBase<ELFT> *S) {
203 for (StringRef Pat : Opt.KeptSections)
204 if (globMatch(Pat, S->getSectionName()))
209 template <class ELFT>
210 void LinkerScript<ELFT>::assignAddresses(
211 ArrayRef<OutputSectionBase<ELFT> *> Sections) {
212 // Orphan sections are sections present in the input files which
213 // are not explicitly placed into the output file by the linker script.
214 // We place orphan sections at end of file.
215 // Other linkers places them using some heuristics as described in
216 // https://sourceware.org/binutils/docs/ld/Orphan-Sections.html#Orphan-Sections.
217 for (OutputSectionBase<ELFT> *Sec : Sections) {
218 StringRef Name = Sec->getName();
219 if (getSectionIndex(Name) == INT_MAX)
220 Opt.Commands.push_back({SectionKind, {}, Name});
223 // Assign addresses as instructed by linker script SECTIONS sub-commands.
224 Dot = Out<ELFT>::ElfHeader->getSize() + Out<ELFT>::ProgramHeaders->getSize();
225 uintX_t MinVA = std::numeric_limits<uintX_t>::max();
226 uintX_t ThreadBssOffset = 0;
228 for (SectionsCommand &Cmd : Opt.Commands) {
229 if (Cmd.Kind == AssignmentKind) {
230 uint64_t Val = evalExpr(Cmd.Expr, Dot);
232 if (Cmd.Name == ".") {
235 auto *D = cast<DefinedRegular<ELFT>>(Symtab<ELFT>::X->find(Cmd.Name));
241 // Find all the sections with required name. There can be more than
242 // ont section with such name, if the alignment, flags or type
243 // attribute differs.
244 assert(Cmd.Kind == SectionKind);
245 for (OutputSectionBase<ELFT> *Sec : Sections) {
246 if (Sec->getName() != Cmd.Name)
249 if ((Sec->getFlags() & SHF_TLS) && Sec->getType() == SHT_NOBITS) {
250 uintX_t TVA = Dot + ThreadBssOffset;
251 TVA = alignTo(TVA, Sec->getAlignment());
253 ThreadBssOffset = TVA - Dot + Sec->getSize();
257 if (Sec->getFlags() & SHF_ALLOC) {
258 Dot = alignTo(Dot, Sec->getAlignment());
260 MinVA = std::min(MinVA, Dot);
261 Dot += Sec->getSize();
267 // ELF and Program headers need to be right before the first section in
269 // Set their addresses accordingly.
270 MinVA = alignDown(MinVA - Out<ELFT>::ElfHeader->getSize() -
271 Out<ELFT>::ProgramHeaders->getSize(),
273 Out<ELFT>::ElfHeader->setVA(MinVA);
274 Out<ELFT>::ProgramHeaders->setVA(Out<ELFT>::ElfHeader->getSize() + MinVA);
277 template <class ELFT>
278 ArrayRef<uint8_t> LinkerScript<ELFT>::getFiller(StringRef Name) {
279 auto I = Opt.Filler.find(Name);
280 if (I == Opt.Filler.end())
285 // Returns the index of the given section name in linker script
286 // SECTIONS commands. Sections are laid out as the same order as they
287 // were in the script. If a given name did not appear in the script,
288 // it returns INT_MAX, so that it will be laid out at end of file.
289 template <class ELFT>
290 int LinkerScript<ELFT>::getSectionIndex(StringRef Name) {
291 auto Begin = Opt.Commands.begin();
292 auto End = Opt.Commands.end();
293 auto I = std::find_if(Begin, End, [&](SectionsCommand &N) {
294 return N.Kind == SectionKind && N.Name == Name;
296 return I == End ? INT_MAX : (I - Begin);
299 // A compartor to sort output sections. Returns -1 or 1 if
300 // A or B are mentioned in linker script. Otherwise, returns 0.
301 template <class ELFT>
302 int LinkerScript<ELFT>::compareSections(StringRef A, StringRef B) {
303 int I = getSectionIndex(A);
304 int J = getSectionIndex(B);
305 if (I == INT_MAX && J == INT_MAX)
307 return I < J ? -1 : 1;
310 template <class ELFT>
311 void LinkerScript<ELFT>::addScriptedSymbols() {
312 for (SectionsCommand &Cmd : Opt.Commands)
313 if (Cmd.Kind == AssignmentKind)
314 if (Cmd.Name != "." && Symtab<ELFT>::X->find(Cmd.Name) == nullptr)
315 Symtab<ELFT>::X->addAbsolute(Cmd.Name, STV_DEFAULT);
318 class elf::ScriptParser : public ScriptParserBase {
319 typedef void (ScriptParser::*Handler)();
322 ScriptParser(StringRef S, bool B) : ScriptParserBase(S), IsUnderSysroot(B) {}
327 void addFile(StringRef Path);
334 void readNothing() {}
336 void readOutputArch();
337 void readOutputFormat();
338 void readSearchDir();
341 void readLocationCounterValue();
342 void readOutputSectionDescription(StringRef OutSec);
343 void readSymbolAssignment(StringRef Name);
344 std::vector<StringRef> readSectionsCommandExpr();
346 const static StringMap<Handler> Cmd;
347 ScriptConfiguration &Opt = *ScriptConfig;
348 StringSaver Saver = {ScriptConfig->Alloc};
352 const StringMap<elf::ScriptParser::Handler> elf::ScriptParser::Cmd = {
353 {"ENTRY", &ScriptParser::readEntry},
354 {"EXTERN", &ScriptParser::readExtern},
355 {"GROUP", &ScriptParser::readGroup},
356 {"INCLUDE", &ScriptParser::readInclude},
357 {"INPUT", &ScriptParser::readGroup},
358 {"OUTPUT", &ScriptParser::readOutput},
359 {"OUTPUT_ARCH", &ScriptParser::readOutputArch},
360 {"OUTPUT_FORMAT", &ScriptParser::readOutputFormat},
361 {"SEARCH_DIR", &ScriptParser::readSearchDir},
362 {"SECTIONS", &ScriptParser::readSections},
363 {";", &ScriptParser::readNothing}};
365 void ScriptParser::run() {
367 StringRef Tok = next();
368 if (Handler Fn = Cmd.lookup(Tok))
371 setError("unknown directive: " + Tok);
375 void ScriptParser::addFile(StringRef S) {
376 if (IsUnderSysroot && S.startswith("/")) {
377 SmallString<128> Path;
378 (Config->Sysroot + S).toStringRef(Path);
379 if (sys::fs::exists(Path)) {
380 Driver->addFile(Saver.save(Path.str()));
385 if (sys::path::is_absolute(S)) {
387 } else if (S.startswith("=")) {
388 if (Config->Sysroot.empty())
389 Driver->addFile(S.substr(1));
391 Driver->addFile(Saver.save(Config->Sysroot + "/" + S.substr(1)));
392 } else if (S.startswith("-l")) {
393 Driver->addLibrary(S.substr(2));
394 } else if (sys::fs::exists(S)) {
397 std::string Path = findFromSearchPaths(S);
399 setError("unable to find " + S);
401 Driver->addFile(Saver.save(Path));
405 void ScriptParser::readAsNeeded() {
407 bool Orig = Config->AsNeeded;
408 Config->AsNeeded = true;
410 StringRef Tok = next();
415 Config->AsNeeded = Orig;
418 void ScriptParser::readEntry() {
419 // -e <symbol> takes predecence over ENTRY(<symbol>).
421 StringRef Tok = next();
422 if (Config->Entry.empty())
427 void ScriptParser::readExtern() {
430 StringRef Tok = next();
433 Config->Undefined.push_back(Tok);
437 void ScriptParser::readGroup() {
440 StringRef Tok = next();
443 if (Tok == "AS_NEEDED") {
451 void ScriptParser::readInclude() {
452 StringRef Tok = next();
453 auto MBOrErr = MemoryBuffer::getFile(Tok);
455 setError("cannot open " + Tok);
458 std::unique_ptr<MemoryBuffer> &MB = *MBOrErr;
459 StringRef S = Saver.save(MB->getMemBufferRef().getBuffer());
460 std::vector<StringRef> V = tokenize(S);
461 Tokens.insert(Tokens.begin() + Pos, V.begin(), V.end());
464 void ScriptParser::readOutput() {
465 // -o <file> takes predecence over OUTPUT(<file>).
467 StringRef Tok = next();
468 if (Config->OutputFile.empty())
469 Config->OutputFile = Tok;
473 void ScriptParser::readOutputArch() {
474 // Error checking only for now.
480 void ScriptParser::readOutputFormat() {
481 // Error checking only for now.
484 StringRef Tok = next();
488 setError("unexpected token: " + Tok);
497 void ScriptParser::readSearchDir() {
499 Config->SearchPaths.push_back(next());
503 void ScriptParser::readSections() {
506 while (!Error && !skip("}")) {
507 StringRef Tok = peek();
509 readLocationCounterValue();
514 readSymbolAssignment(Tok);
516 readOutputSectionDescription(Tok);
520 void ScriptParser::readLocationCounterValue() {
523 std::vector<StringRef> Expr = readSectionsCommandExpr();
525 error("error in location counter expression");
527 Opt.Commands.push_back({AssignmentKind, std::move(Expr), "."});
530 void ScriptParser::readOutputSectionDescription(StringRef OutSec) {
531 Opt.Commands.push_back({SectionKind, {}, OutSec});
535 while (!Error && !skip("}")) {
536 StringRef Tok = next();
539 while (!Error && !skip(")"))
540 Opt.Sections.emplace_back(OutSec, next());
541 } else if (Tok == "KEEP") {
545 while (!Error && !skip(")")) {
546 StringRef Sec = next();
547 Opt.Sections.emplace_back(OutSec, Sec);
548 Opt.KeptSections.push_back(Sec);
552 setError("unknown command " + Tok);
556 StringRef Tok = peek();
557 if (Tok.startswith("=")) {
558 if (!Tok.startswith("=0x")) {
559 setError("filler should be a hexadecimal value");
563 Opt.Filler[OutSec] = parseHex(Tok);
568 void ScriptParser::readSymbolAssignment(StringRef Name) {
570 std::vector<StringRef> Expr = readSectionsCommandExpr();
572 error("error in symbol assignment expression");
574 Opt.Commands.push_back({AssignmentKind, std::move(Expr), Name});
577 std::vector<StringRef> ScriptParser::readSectionsCommandExpr() {
578 std::vector<StringRef> Expr;
580 StringRef Tok = next();
588 static bool isUnderSysroot(StringRef Path) {
589 if (Config->Sysroot == "")
591 for (; !Path.empty(); Path = sys::path::parent_path(Path))
592 if (sys::fs::equivalent(Config->Sysroot, Path))
598 void elf::readLinkerScript(MemoryBufferRef MB) {
599 StringRef Path = MB.getBufferIdentifier();
600 ScriptParser(MB.getBuffer(), isUnderSysroot(Path)).run();
603 template class elf::LinkerScript<ELF32LE>;
604 template class elf::LinkerScript<ELF32BE>;
605 template class elf::LinkerScript<ELF64LE>;
606 template class elf::LinkerScript<ELF64BE>;