summaryrefslogtreecommitdiffstats
path: root/contrib/llvm/tools/lld/ELF/LinkerScript.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'contrib/llvm/tools/lld/ELF/LinkerScript.cpp')
-rw-r--r--contrib/llvm/tools/lld/ELF/LinkerScript.cpp606
1 files changed, 606 insertions, 0 deletions
diff --git a/contrib/llvm/tools/lld/ELF/LinkerScript.cpp b/contrib/llvm/tools/lld/ELF/LinkerScript.cpp
new file mode 100644
index 0000000..61abdc1
--- /dev/null
+++ b/contrib/llvm/tools/lld/ELF/LinkerScript.cpp
@@ -0,0 +1,606 @@
+//===- LinkerScript.cpp ---------------------------------------------------===//
+//
+// The LLVM Linker
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains the parser/evaluator of the linker script.
+// It does not construct an AST but consume linker script directives directly.
+// Results are written to Driver or Config object.
+//
+//===----------------------------------------------------------------------===//
+
+#include "LinkerScript.h"
+#include "Config.h"
+#include "Driver.h"
+#include "InputSection.h"
+#include "OutputSections.h"
+#include "ScriptParser.h"
+#include "Strings.h"
+#include "Symbols.h"
+#include "SymbolTable.h"
+#include "Target.h"
+#include "llvm/ADT/StringSwitch.h"
+#include "llvm/Support/ELF.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Support/Path.h"
+#include "llvm/Support/StringSaver.h"
+
+using namespace llvm;
+using namespace llvm::ELF;
+using namespace llvm::object;
+using namespace lld;
+using namespace lld::elf;
+
+ScriptConfiguration *elf::ScriptConfig;
+
+// This is an operator-precedence parser to parse and evaluate
+// a linker script expression. For each linker script arithmetic
+// expression (e.g. ". = . + 0x1000"), a new instance of ExprParser
+// is created and ran.
+namespace {
+class ExprParser : public ScriptParserBase {
+public:
+ ExprParser(std::vector<StringRef> &Tokens, uint64_t Dot)
+ : ScriptParserBase(Tokens), Dot(Dot) {}
+
+ uint64_t run();
+
+private:
+ uint64_t parsePrimary();
+ uint64_t parseTernary(uint64_t Cond);
+ uint64_t apply(StringRef Op, uint64_t L, uint64_t R);
+ uint64_t parseExpr1(uint64_t Lhs, int MinPrec);
+ uint64_t parseExpr();
+
+ uint64_t Dot;
+};
+}
+
+static int precedence(StringRef Op) {
+ return StringSwitch<int>(Op)
+ .Case("*", 4)
+ .Case("/", 4)
+ .Case("+", 3)
+ .Case("-", 3)
+ .Case("<", 2)
+ .Case(">", 2)
+ .Case(">=", 2)
+ .Case("<=", 2)
+ .Case("==", 2)
+ .Case("!=", 2)
+ .Case("&", 1)
+ .Default(-1);
+}
+
+static uint64_t evalExpr(std::vector<StringRef> &Tokens, uint64_t Dot) {
+ return ExprParser(Tokens, Dot).run();
+}
+
+uint64_t ExprParser::run() {
+ uint64_t V = parseExpr();
+ if (!atEOF() && !Error)
+ setError("stray token: " + peek());
+ return V;
+}
+
+// This is a part of the operator-precedence parser to evaluate
+// arithmetic expressions in SECTIONS command. This function evaluates an
+// integer literal, a parenthesized expression, the ALIGN function,
+// or the special variable ".".
+uint64_t ExprParser::parsePrimary() {
+ StringRef Tok = next();
+ if (Tok == ".")
+ return Dot;
+ if (Tok == "(") {
+ uint64_t V = parseExpr();
+ expect(")");
+ return V;
+ }
+ if (Tok == "ALIGN") {
+ expect("(");
+ uint64_t V = parseExpr();
+ expect(")");
+ return alignTo(Dot, V);
+ }
+ uint64_t V = 0;
+ if (Tok.getAsInteger(0, V))
+ setError("malformed number: " + Tok);
+ return V;
+}
+
+uint64_t ExprParser::parseTernary(uint64_t Cond) {
+ next();
+ uint64_t V = parseExpr();
+ expect(":");
+ uint64_t W = parseExpr();
+ return Cond ? V : W;
+}
+
+uint64_t ExprParser::apply(StringRef Op, uint64_t L, uint64_t R) {
+ if (Op == "*")
+ return L * R;
+ if (Op == "/") {
+ if (R == 0) {
+ error("division by zero");
+ return 0;
+ }
+ return L / R;
+ }
+ if (Op == "+")
+ return L + R;
+ if (Op == "-")
+ return L - R;
+ if (Op == "<")
+ return L < R;
+ if (Op == ">")
+ return L > R;
+ if (Op == ">=")
+ return L >= R;
+ if (Op == "<=")
+ return L <= R;
+ if (Op == "==")
+ return L == R;
+ if (Op == "!=")
+ return L != R;
+ if (Op == "&")
+ return L & R;
+ llvm_unreachable("invalid operator");
+}
+
+// This is a part of the operator-precedence parser.
+// This function assumes that the remaining token stream starts
+// with an operator.
+uint64_t ExprParser::parseExpr1(uint64_t Lhs, int MinPrec) {
+ while (!atEOF()) {
+ // Read an operator and an expression.
+ StringRef Op1 = peek();
+ if (Op1 == "?")
+ return parseTernary(Lhs);
+ if (precedence(Op1) < MinPrec)
+ return Lhs;
+ next();
+ uint64_t Rhs = parsePrimary();
+
+ // Evaluate the remaining part of the expression first if the
+ // next operator has greater precedence than the previous one.
+ // For example, if we have read "+" and "3", and if the next
+ // operator is "*", then we'll evaluate 3 * ... part first.
+ while (!atEOF()) {
+ StringRef Op2 = peek();
+ if (precedence(Op2) <= precedence(Op1))
+ break;
+ Rhs = parseExpr1(Rhs, precedence(Op2));
+ }
+
+ Lhs = apply(Op1, Lhs, Rhs);
+ }
+ return Lhs;
+}
+
+// Reads and evaluates an arithmetic expression.
+uint64_t ExprParser::parseExpr() { return parseExpr1(parsePrimary(), 0); }
+
+template <class ELFT>
+StringRef LinkerScript<ELFT>::getOutputSection(InputSectionBase<ELFT> *S) {
+ for (SectionRule &R : Opt.Sections)
+ if (globMatch(R.SectionPattern, S->getSectionName()))
+ return R.Dest;
+ return "";
+}
+
+template <class ELFT>
+bool LinkerScript<ELFT>::isDiscarded(InputSectionBase<ELFT> *S) {
+ return getOutputSection(S) == "/DISCARD/";
+}
+
+template <class ELFT>
+bool LinkerScript<ELFT>::shouldKeep(InputSectionBase<ELFT> *S) {
+ for (StringRef Pat : Opt.KeptSections)
+ if (globMatch(Pat, S->getSectionName()))
+ return true;
+ return false;
+}
+
+template <class ELFT>
+void LinkerScript<ELFT>::assignAddresses(
+ ArrayRef<OutputSectionBase<ELFT> *> Sections) {
+ // Orphan sections are sections present in the input files which
+ // are not explicitly placed into the output file by the linker script.
+ // We place orphan sections at end of file.
+ // Other linkers places them using some heuristics as described in
+ // https://sourceware.org/binutils/docs/ld/Orphan-Sections.html#Orphan-Sections.
+ for (OutputSectionBase<ELFT> *Sec : Sections) {
+ StringRef Name = Sec->getName();
+ if (getSectionIndex(Name) == INT_MAX)
+ Opt.Commands.push_back({SectionKind, {}, Name});
+ }
+
+ // Assign addresses as instructed by linker script SECTIONS sub-commands.
+ Dot = Out<ELFT>::ElfHeader->getSize() + Out<ELFT>::ProgramHeaders->getSize();
+ uintX_t MinVA = std::numeric_limits<uintX_t>::max();
+ uintX_t ThreadBssOffset = 0;
+
+ for (SectionsCommand &Cmd : Opt.Commands) {
+ if (Cmd.Kind == AssignmentKind) {
+ uint64_t Val = evalExpr(Cmd.Expr, Dot);
+
+ if (Cmd.Name == ".") {
+ Dot = Val;
+ } else {
+ auto *D = cast<DefinedRegular<ELFT>>(Symtab<ELFT>::X->find(Cmd.Name));
+ D->Value = Val;
+ }
+ continue;
+ }
+
+ // Find all the sections with required name. There can be more than
+ // ont section with such name, if the alignment, flags or type
+ // attribute differs.
+ assert(Cmd.Kind == SectionKind);
+ for (OutputSectionBase<ELFT> *Sec : Sections) {
+ if (Sec->getName() != Cmd.Name)
+ continue;
+
+ if ((Sec->getFlags() & SHF_TLS) && Sec->getType() == SHT_NOBITS) {
+ uintX_t TVA = Dot + ThreadBssOffset;
+ TVA = alignTo(TVA, Sec->getAlignment());
+ Sec->setVA(TVA);
+ ThreadBssOffset = TVA - Dot + Sec->getSize();
+ continue;
+ }
+
+ if (Sec->getFlags() & SHF_ALLOC) {
+ Dot = alignTo(Dot, Sec->getAlignment());
+ Sec->setVA(Dot);
+ MinVA = std::min(MinVA, Dot);
+ Dot += Sec->getSize();
+ continue;
+ }
+ }
+ }
+
+ // ELF and Program headers need to be right before the first section in
+ // memory.
+ // Set their addresses accordingly.
+ MinVA = alignDown(MinVA - Out<ELFT>::ElfHeader->getSize() -
+ Out<ELFT>::ProgramHeaders->getSize(),
+ Target->PageSize);
+ Out<ELFT>::ElfHeader->setVA(MinVA);
+ Out<ELFT>::ProgramHeaders->setVA(Out<ELFT>::ElfHeader->getSize() + MinVA);
+}
+
+template <class ELFT>
+ArrayRef<uint8_t> LinkerScript<ELFT>::getFiller(StringRef Name) {
+ auto I = Opt.Filler.find(Name);
+ if (I == Opt.Filler.end())
+ return {};
+ return I->second;
+}
+
+// Returns the index of the given section name in linker script
+// SECTIONS commands. Sections are laid out as the same order as they
+// were in the script. If a given name did not appear in the script,
+// it returns INT_MAX, so that it will be laid out at end of file.
+template <class ELFT>
+int LinkerScript<ELFT>::getSectionIndex(StringRef Name) {
+ auto Begin = Opt.Commands.begin();
+ auto End = Opt.Commands.end();
+ auto I = std::find_if(Begin, End, [&](SectionsCommand &N) {
+ return N.Kind == SectionKind && N.Name == Name;
+ });
+ return I == End ? INT_MAX : (I - Begin);
+}
+
+// A compartor to sort output sections. Returns -1 or 1 if
+// A or B are mentioned in linker script. Otherwise, returns 0.
+template <class ELFT>
+int LinkerScript<ELFT>::compareSections(StringRef A, StringRef B) {
+ int I = getSectionIndex(A);
+ int J = getSectionIndex(B);
+ if (I == INT_MAX && J == INT_MAX)
+ return 0;
+ return I < J ? -1 : 1;
+}
+
+template <class ELFT>
+void LinkerScript<ELFT>::addScriptedSymbols() {
+ for (SectionsCommand &Cmd : Opt.Commands)
+ if (Cmd.Kind == AssignmentKind)
+ if (Cmd.Name != "." && Symtab<ELFT>::X->find(Cmd.Name) == nullptr)
+ Symtab<ELFT>::X->addAbsolute(Cmd.Name, STV_DEFAULT);
+}
+
+class elf::ScriptParser : public ScriptParserBase {
+ typedef void (ScriptParser::*Handler)();
+
+public:
+ ScriptParser(StringRef S, bool B) : ScriptParserBase(S), IsUnderSysroot(B) {}
+
+ void run();
+
+private:
+ void addFile(StringRef Path);
+
+ void readAsNeeded();
+ void readEntry();
+ void readExtern();
+ void readGroup();
+ void readInclude();
+ void readNothing() {}
+ void readOutput();
+ void readOutputArch();
+ void readOutputFormat();
+ void readSearchDir();
+ void readSections();
+
+ void readLocationCounterValue();
+ void readOutputSectionDescription(StringRef OutSec);
+ void readSymbolAssignment(StringRef Name);
+ std::vector<StringRef> readSectionsCommandExpr();
+
+ const static StringMap<Handler> Cmd;
+ ScriptConfiguration &Opt = *ScriptConfig;
+ StringSaver Saver = {ScriptConfig->Alloc};
+ bool IsUnderSysroot;
+};
+
+const StringMap<elf::ScriptParser::Handler> elf::ScriptParser::Cmd = {
+ {"ENTRY", &ScriptParser::readEntry},
+ {"EXTERN", &ScriptParser::readExtern},
+ {"GROUP", &ScriptParser::readGroup},
+ {"INCLUDE", &ScriptParser::readInclude},
+ {"INPUT", &ScriptParser::readGroup},
+ {"OUTPUT", &ScriptParser::readOutput},
+ {"OUTPUT_ARCH", &ScriptParser::readOutputArch},
+ {"OUTPUT_FORMAT", &ScriptParser::readOutputFormat},
+ {"SEARCH_DIR", &ScriptParser::readSearchDir},
+ {"SECTIONS", &ScriptParser::readSections},
+ {";", &ScriptParser::readNothing}};
+
+void ScriptParser::run() {
+ while (!atEOF()) {
+ StringRef Tok = next();
+ if (Handler Fn = Cmd.lookup(Tok))
+ (this->*Fn)();
+ else
+ setError("unknown directive: " + Tok);
+ }
+}
+
+void ScriptParser::addFile(StringRef S) {
+ if (IsUnderSysroot && S.startswith("/")) {
+ SmallString<128> Path;
+ (Config->Sysroot + S).toStringRef(Path);
+ if (sys::fs::exists(Path)) {
+ Driver->addFile(Saver.save(Path.str()));
+ return;
+ }
+ }
+
+ if (sys::path::is_absolute(S)) {
+ Driver->addFile(S);
+ } else if (S.startswith("=")) {
+ if (Config->Sysroot.empty())
+ Driver->addFile(S.substr(1));
+ else
+ Driver->addFile(Saver.save(Config->Sysroot + "/" + S.substr(1)));
+ } else if (S.startswith("-l")) {
+ Driver->addLibrary(S.substr(2));
+ } else if (sys::fs::exists(S)) {
+ Driver->addFile(S);
+ } else {
+ std::string Path = findFromSearchPaths(S);
+ if (Path.empty())
+ setError("unable to find " + S);
+ else
+ Driver->addFile(Saver.save(Path));
+ }
+}
+
+void ScriptParser::readAsNeeded() {
+ expect("(");
+ bool Orig = Config->AsNeeded;
+ Config->AsNeeded = true;
+ while (!Error) {
+ StringRef Tok = next();
+ if (Tok == ")")
+ break;
+ addFile(Tok);
+ }
+ Config->AsNeeded = Orig;
+}
+
+void ScriptParser::readEntry() {
+ // -e <symbol> takes predecence over ENTRY(<symbol>).
+ expect("(");
+ StringRef Tok = next();
+ if (Config->Entry.empty())
+ Config->Entry = Tok;
+ expect(")");
+}
+
+void ScriptParser::readExtern() {
+ expect("(");
+ while (!Error) {
+ StringRef Tok = next();
+ if (Tok == ")")
+ return;
+ Config->Undefined.push_back(Tok);
+ }
+}
+
+void ScriptParser::readGroup() {
+ expect("(");
+ while (!Error) {
+ StringRef Tok = next();
+ if (Tok == ")")
+ return;
+ if (Tok == "AS_NEEDED") {
+ readAsNeeded();
+ continue;
+ }
+ addFile(Tok);
+ }
+}
+
+void ScriptParser::readInclude() {
+ StringRef Tok = next();
+ auto MBOrErr = MemoryBuffer::getFile(Tok);
+ if (!MBOrErr) {
+ setError("cannot open " + Tok);
+ return;
+ }
+ std::unique_ptr<MemoryBuffer> &MB = *MBOrErr;
+ StringRef S = Saver.save(MB->getMemBufferRef().getBuffer());
+ std::vector<StringRef> V = tokenize(S);
+ Tokens.insert(Tokens.begin() + Pos, V.begin(), V.end());
+}
+
+void ScriptParser::readOutput() {
+ // -o <file> takes predecence over OUTPUT(<file>).
+ expect("(");
+ StringRef Tok = next();
+ if (Config->OutputFile.empty())
+ Config->OutputFile = Tok;
+ expect(")");
+}
+
+void ScriptParser::readOutputArch() {
+ // Error checking only for now.
+ expect("(");
+ next();
+ expect(")");
+}
+
+void ScriptParser::readOutputFormat() {
+ // Error checking only for now.
+ expect("(");
+ next();
+ StringRef Tok = next();
+ if (Tok == ")")
+ return;
+ if (Tok != ",") {
+ setError("unexpected token: " + Tok);
+ return;
+ }
+ next();
+ expect(",");
+ next();
+ expect(")");
+}
+
+void ScriptParser::readSearchDir() {
+ expect("(");
+ Config->SearchPaths.push_back(next());
+ expect(")");
+}
+
+void ScriptParser::readSections() {
+ Opt.DoLayout = true;
+ expect("{");
+ while (!Error && !skip("}")) {
+ StringRef Tok = peek();
+ if (Tok == ".") {
+ readLocationCounterValue();
+ continue;
+ }
+ next();
+ if (peek() == "=")
+ readSymbolAssignment(Tok);
+ else
+ readOutputSectionDescription(Tok);
+ }
+}
+
+void ScriptParser::readLocationCounterValue() {
+ expect(".");
+ expect("=");
+ std::vector<StringRef> Expr = readSectionsCommandExpr();
+ if (Expr.empty())
+ error("error in location counter expression");
+ else
+ Opt.Commands.push_back({AssignmentKind, std::move(Expr), "."});
+}
+
+void ScriptParser::readOutputSectionDescription(StringRef OutSec) {
+ Opt.Commands.push_back({SectionKind, {}, OutSec});
+ expect(":");
+ expect("{");
+
+ while (!Error && !skip("}")) {
+ StringRef Tok = next();
+ if (Tok == "*") {
+ expect("(");
+ while (!Error && !skip(")"))
+ Opt.Sections.emplace_back(OutSec, next());
+ } else if (Tok == "KEEP") {
+ expect("(");
+ expect("*");
+ expect("(");
+ while (!Error && !skip(")")) {
+ StringRef Sec = next();
+ Opt.Sections.emplace_back(OutSec, Sec);
+ Opt.KeptSections.push_back(Sec);
+ }
+ expect(")");
+ } else {
+ setError("unknown command " + Tok);
+ }
+ }
+
+ StringRef Tok = peek();
+ if (Tok.startswith("=")) {
+ if (!Tok.startswith("=0x")) {
+ setError("filler should be a hexadecimal value");
+ return;
+ }
+ Tok = Tok.substr(3);
+ Opt.Filler[OutSec] = parseHex(Tok);
+ next();
+ }
+}
+
+void ScriptParser::readSymbolAssignment(StringRef Name) {
+ expect("=");
+ std::vector<StringRef> Expr = readSectionsCommandExpr();
+ if (Expr.empty())
+ error("error in symbol assignment expression");
+ else
+ Opt.Commands.push_back({AssignmentKind, std::move(Expr), Name});
+}
+
+std::vector<StringRef> ScriptParser::readSectionsCommandExpr() {
+ std::vector<StringRef> Expr;
+ while (!Error) {
+ StringRef Tok = next();
+ if (Tok == ";")
+ break;
+ Expr.push_back(Tok);
+ }
+ return Expr;
+}
+
+static bool isUnderSysroot(StringRef Path) {
+ if (Config->Sysroot == "")
+ return false;
+ for (; !Path.empty(); Path = sys::path::parent_path(Path))
+ if (sys::fs::equivalent(Config->Sysroot, Path))
+ return true;
+ return false;
+}
+
+// Entry point.
+void elf::readLinkerScript(MemoryBufferRef MB) {
+ StringRef Path = MB.getBufferIdentifier();
+ ScriptParser(MB.getBuffer(), isUnderSysroot(Path)).run();
+}
+
+template class elf::LinkerScript<ELF32LE>;
+template class elf::LinkerScript<ELF32BE>;
+template class elf::LinkerScript<ELF64LE>;
+template class elf::LinkerScript<ELF64BE>;
OpenPOWER on IntegriCloud