vendor/lld/lld-release_39-r276489

1 files changed, 427 insertions, 139 deletions

diff --git a/ELF/LinkerScript.cpp b/ELF/LinkerScript.cpp
index a6df9ed48cdc..61abdc185e11 100644
--- a/ELF/LinkerScript.cpp
+++ b/ELF/LinkerScript.cpp
@@ -13,154 +13,366 @@
 //
 //===----------------------------------------------------------------------===//
 
+#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::elf2;
+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 LinkerScript {
+class ExprParser : public ScriptParserBase {
 public:
-  LinkerScript(BumpPtrAllocator *A, StringRef S, bool B)
-      : Saver(*A), Tokens(tokenize(S)), IsUnderSysroot(B) {}
-  void run();
+  ExprParser(std::vector<StringRef> &Tokens, uint64_t Dot)
+      : ScriptParserBase(Tokens), Dot(Dot) {}
+
+  uint64_t run();
 
 private:
-  static std::vector<StringRef> tokenize(StringRef S);
-  static StringRef skipSpace(StringRef S);
-  StringRef next();
-  bool skip(StringRef Tok);
-  bool atEOF() { return Tokens.size() == Pos; }
-  void expect(StringRef Expect);
+  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();
 
-  void addFile(StringRef Path);
+  uint64_t Dot;
+};
+}
 
-  void readAsNeeded();
-  void readEntry();
-  void readExtern();
-  void readGroup();
-  void readInclude();
-  void readOutput();
-  void readOutputArch();
-  void readOutputFormat();
-  void readSearchDir();
-  void readSections();
+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);
+}
 
-  void readOutputSectionDescription();
+static uint64_t evalExpr(std::vector<StringRef> &Tokens, uint64_t Dot) {
+  return ExprParser(Tokens, Dot).run();
+}
 
-  StringSaver Saver;
-  std::vector<StringRef> Tokens;
-  size_t Pos = 0;
-  bool IsUnderSysroot;
-};
+uint64_t ExprParser::run() {
+  uint64_t V = parseExpr();
+  if (!atEOF() && !Error)
+    setError("stray token: " + peek());
+  return V;
 }
 
-void LinkerScript::run() {
-  while (!atEOF()) {
-    StringRef Tok = next();
-    if (Tok == ";")
-      continue;
-    if (Tok == "ENTRY") {
-      readEntry();
-    } else if (Tok == "EXTERN") {
-      readExtern();
-    } else if (Tok == "GROUP" || Tok == "INPUT") {
-      readGroup();
-    } else if (Tok == "INCLUDE") {
-      readInclude();
-    } else if (Tok == "OUTPUT") {
-      readOutput();
-    } else if (Tok == "OUTPUT_ARCH") {
-      readOutputArch();
-    } else if (Tok == "OUTPUT_FORMAT") {
-      readOutputFormat();
-    } else if (Tok == "SEARCH_DIR") {
-      readSearchDir();
-    } else if (Tok == "SECTIONS") {
-      readSections();
-    } else {
-      error("unknown directive: " + Tok);
+// 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");
 }
 
-// Split S into linker script tokens.
-std::vector<StringRef> LinkerScript::tokenize(StringRef S) {
-  std::vector<StringRef> Ret;
-  for (;;) {
-    S = skipSpace(S);
-    if (S.empty())
-      return Ret;
-
-    // Quoted token
-    if (S.startswith("\"")) {
-      size_t E = S.find("\"", 1);
-      if (E == StringRef::npos)
-        error("unclosed quote");
-      Ret.push_back(S.substr(1, E));
-      S = S.substr(E + 1);
-      continue;
+// 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));
     }
 
-    // Unquoted token
-    size_t Pos = S.find_first_not_of(
-        "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
-        "0123456789_.$/\\~=+[]*?-:");
-    // A character that cannot start a word (which is usually a
-    // punctuation) forms a single character token.
-    if (Pos == 0)
-      Pos = 1;
-    Ret.push_back(S.substr(0, Pos));
-    S = S.substr(Pos);
+    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/";
 }
 
-// Skip leading whitespace characters or /**/-style comments.
-StringRef LinkerScript::skipSpace(StringRef S) {
-  for (;;) {
-    if (S.startswith("/*")) {
-      size_t E = S.find("*/", 2);
-      if (E == StringRef::npos)
-        error("unclosed comment in a linker script");
-      S = S.substr(E + 2);
+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;
     }
-    size_t Size = S.size();
-    S = S.ltrim();
-    if (S.size() == Size)
-      return S;
+
+    // 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);
 }
 
-StringRef LinkerScript::next() {
-  if (atEOF())
-    error("unexpected EOF");
-  return Tokens[Pos++];
+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;
 }
 
-bool LinkerScript::skip(StringRef Tok) {
-  if (atEOF())
-    error("unexpected EOF");
-  if (Tok != Tokens[Pos])
-    return false;
-  ++Pos;
-  return true;
+// 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);
 }
 
-void LinkerScript::expect(StringRef Expect) {
-  StringRef Tok = next();
-  if (Tok != Expect)
-    error(Expect + " expected, but got " + Tok);
+// 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);
 }
 
-void LinkerScript::addFile(StringRef S) {
+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);
@@ -178,22 +390,23 @@ void LinkerScript::addFile(StringRef S) {
     else
       Driver->addFile(Saver.save(Config->Sysroot + "/" + S.substr(1)));
   } else if (S.startswith("-l")) {
-    Driver->addFile(searchLibrary(S.substr(2)));
+    Driver->addLibrary(S.substr(2));
   } else if (sys::fs::exists(S)) {
     Driver->addFile(S);
   } else {
     std::string Path = findFromSearchPaths(S);
     if (Path.empty())
-      error("Unable to find " + S);
-    Driver->addFile(Saver.save(Path));
+      setError("unable to find " + S);
+    else
+      Driver->addFile(Saver.save(Path));
   }
 }
 
-void LinkerScript::readAsNeeded() {
+void ScriptParser::readAsNeeded() {
   expect("(");
   bool Orig = Config->AsNeeded;
   Config->AsNeeded = true;
-  for (;;) {
+  while (!Error) {
     StringRef Tok = next();
     if (Tok == ")")
       break;
@@ -202,7 +415,7 @@ void LinkerScript::readAsNeeded() {
   Config->AsNeeded = Orig;
 }
 
-void LinkerScript::readEntry() {
+void ScriptParser::readEntry() {
   // -e <symbol> takes predecence over ENTRY(<symbol>).
   expect("(");
   StringRef Tok = next();
@@ -211,9 +424,9 @@ void LinkerScript::readEntry() {
   expect(")");
 }
 
-void LinkerScript::readExtern() {
+void ScriptParser::readExtern() {
   expect("(");
-  for (;;) {
+  while (!Error) {
     StringRef Tok = next();
     if (Tok == ")")
       return;
@@ -221,9 +434,9 @@ void LinkerScript::readExtern() {
   }
 }
 
-void LinkerScript::readGroup() {
+void ScriptParser::readGroup() {
   expect("(");
-  for (;;) {
+  while (!Error) {
     StringRef Tok = next();
     if (Tok == ")")
       return;
@@ -235,17 +448,20 @@ void LinkerScript::readGroup() {
   }
 }
 
-void LinkerScript::readInclude() {
+void ScriptParser::readInclude() {
   StringRef Tok = next();
   auto MBOrErr = MemoryBuffer::getFile(Tok);
-  error(MBOrErr, "cannot open " + 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 LinkerScript::readOutput() {
+void ScriptParser::readOutput() {
   // -o <file> takes predecence over OUTPUT(<file>).
   expect("(");
   StringRef Tok = next();
@@ -254,54 +470,121 @@ void LinkerScript::readOutput() {
   expect(")");
 }
 
-void LinkerScript::readOutputArch() {
+void ScriptParser::readOutputArch() {
   // Error checking only for now.
   expect("(");
   next();
   expect(")");
 }
 
-void LinkerScript::readOutputFormat() {
+void ScriptParser::readOutputFormat() {
   // Error checking only for now.
   expect("(");
   next();
   StringRef Tok = next();
   if (Tok == ")")
    return;
-  if (Tok != ",")
-    error("unexpected token: " + Tok);
+  if (Tok != ",") {
+    setError("unexpected token: " + Tok);
+    return;
+  }
   next();
   expect(",");
   next();
   expect(")");
 }
 
-void LinkerScript::readSearchDir() {
+void ScriptParser::readSearchDir() {
   expect("(");
   Config->SearchPaths.push_back(next());
   expect(")");
 }
 
-void LinkerScript::readSections() {
+void ScriptParser::readSections() {
+  Opt.DoLayout = true;
   expect("{");
-  while (!skip("}"))
-    readOutputSectionDescription();
+  while (!Error && !skip("}")) {
+    StringRef Tok = peek();
+    if (Tok == ".") {
+      readLocationCounterValue();
+      continue;
+    }
+    next();
+    if (peek() == "=")
+      readSymbolAssignment(Tok);
+    else
+      readOutputSectionDescription(Tok);
+  }
 }
 
-void LinkerScript::readOutputSectionDescription() {
-  StringRef Name = next();
-  std::vector<StringRef> &InputSections = Config->OutputSections[Name];
+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 (!skip("}")) {
-    next(); // Skip input file name.
-    expect("(");
-    while (!skip(")"))
-      InputSections.push_back(next());
+
+  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;
@@ -311,8 +594,13 @@ static bool isUnderSysroot(StringRef Path) {
   return false;
 }
 
-// Entry point. The other functions or classes are private to this file.
-void elf2::readLinkerScript(BumpPtrAllocator *A, MemoryBufferRef MB) {
+// Entry point.
+void elf::readLinkerScript(MemoryBufferRef MB) {
   StringRef Path = MB.getBufferIdentifier();
-  LinkerScript(A, MB.getBuffer(), isUnderSysroot(Path)).run();
+  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>;