contrib/llvm/tools/lld/ELF/LinkerScript.cpp

   1 //===- LinkerScript.cpp ---------------------------------------------------===//
   2 //
   3 //                             The LLVM Linker
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  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.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "LinkerScript.h"
  17 #include "Config.h"
  18 #include "Driver.h"
  19 #include "InputSection.h"
  20 #include "OutputSections.h"
  21 #include "ScriptParser.h"
  22 #include "Strings.h"
  23 #include "Symbols.h"
  24 #include "SymbolTable.h"
  25 #include "Target.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"
  32
  33 using namespace llvm;
  34 using namespace llvm::ELF;
  35 using namespace llvm::object;
  36 using namespace lld;
  37 using namespace lld::elf;
  38
  39 ScriptConfiguration *elf::ScriptConfig;
  40
  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.
  45 namespace {
  46 class ExprParser : public ScriptParserBase {
  47 public:
  48   ExprParser(std::vector<StringRef> &Tokens, uint64_t Dot)
  49       : ScriptParserBase(Tokens), Dot(Dot) {}
  50
  51   uint64_t run();
  52
  53 private:
  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);
  58   uint64_t parseExpr();
  59
  60   uint64_t Dot;
  61 };
  62 }
  63
  64 static int precedence(StringRef Op) {
  65   return StringSwitch<int>(Op)
  66       .Case("*", 4)
  67       .Case("/", 4)
  68       .Case("+", 3)
  69       .Case("-", 3)
  70       .Case("<", 2)
  71       .Case(">", 2)
  72       .Case(">=", 2)
  73       .Case("<=", 2)
  74       .Case("==", 2)
  75       .Case("!=", 2)
  76       .Case("&", 1)
  77       .Default(-1);
  78 }
  79
  80 static uint64_t evalExpr(std::vector<StringRef> &Tokens, uint64_t Dot) {
  81   return ExprParser(Tokens, Dot).run();
  82 }
  83
  84 uint64_t ExprParser::run() {
  85   uint64_t V = parseExpr();
  86   if (!atEOF() && !Error)
  87     setError("stray token: " + peek());
  88   return V;
  89 }
  90
  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();
  97   if (Tok == ".")
  98     return Dot;
  99   if (Tok == "(") {
 100     uint64_t V = parseExpr();
 101     expect(")");
 102     return V;
 103   }
 104   if (Tok == "ALIGN") {
 105     expect("(");
 106     uint64_t V = parseExpr();
 107     expect(")");
 108     return alignTo(Dot, V);
 109   }
 110   uint64_t V = 0;
 111   if (Tok.getAsInteger(0, V))
 112     setError("malformed number: " + Tok);
 113   return V;
 114 }
 115
 116 uint64_t ExprParser::parseTernary(uint64_t Cond) {
 117   next();
 118   uint64_t V = parseExpr();
 119   expect(":");
 120   uint64_t W = parseExpr();
 121   return Cond ? V : W;
 122 }
 123
 124 uint64_t ExprParser::apply(StringRef Op, uint64_t L, uint64_t R) {
 125   if (Op == "*")
 126     return L * R;
 127   if (Op == "/") {
 128     if (R == 0) {
 129       error("division by zero");
 130       return 0;
 131     }
 132     return L / R;
 133   }
 134   if (Op == "+")
 135     return L + R;
 136   if (Op == "-")
 137     return L - R;
 138   if (Op == "<")
 139     return L < R;
 140   if (Op == ">")
 141     return L > R;
 142   if (Op == ">=")
 143     return L >= R;
 144   if (Op == "<=")
 145     return L <= R;
 146   if (Op == "==")
 147     return L == R;
 148   if (Op == "!=")
 149     return L != R;
 150   if (Op == "&")
 151     return L & R;
 152   llvm_unreachable("invalid operator");
 153 }
 154
 155 // This is a part of the operator-precedence parser.
 156 // This function assumes that the remaining token stream starts
 157 // with an operator.
 158 uint64_t ExprParser::parseExpr1(uint64_t Lhs, int MinPrec) {
 159   while (!atEOF()) {
 160     // Read an operator and an expression.
 161     StringRef Op1 = peek();
 162     if (Op1 == "?")
 163       return parseTernary(Lhs);
 164     if (precedence(Op1) < MinPrec)
 165       return Lhs;
 166     next();
 167     uint64_t Rhs = parsePrimary();
 168
 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.
 173     while (!atEOF()) {
 174       StringRef Op2 = peek();
 175       if (precedence(Op2) <= precedence(Op1))
 176         break;
 177       Rhs = parseExpr1(Rhs, precedence(Op2));
 178     }
 179
 180     Lhs = apply(Op1, Lhs, Rhs);
 181   }
 182   return Lhs;
 183 }
 184
 185 // Reads and evaluates an arithmetic expression.
 186 uint64_t ExprParser::parseExpr() { return parseExpr1(parsePrimary(), 0); }
 187
 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()))
 192       return R.Dest;
 193   return "";
 194 }
 195
 196 template <class ELFT>
 197 bool LinkerScript<ELFT>::isDiscarded(InputSectionBase<ELFT> *S) {
 198   return getOutputSection(S) == "/DISCARD/";
 199 }
 200
 201 template <class ELFT>
 202 bool LinkerScript<ELFT>::shouldKeep(InputSectionBase<ELFT> *S) {
 203   for (StringRef Pat : Opt.KeptSections)
 204     if (globMatch(Pat, S->getSectionName()))
 205       return true;
 206   return false;
 207 }
 208
 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});
 221   }
 222
 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;
 227
 228   for (SectionsCommand &Cmd : Opt.Commands) {
 229     if (Cmd.Kind == AssignmentKind) {
 230       uint64_t Val = evalExpr(Cmd.Expr, Dot);
 231
 232       if (Cmd.Name == ".") {
 233         Dot = Val;
 234       } else {
 235         auto *D = cast<DefinedRegular<ELFT>>(Symtab<ELFT>::X->find(Cmd.Name));
 236         D->Value = Val;
 237       }
 238       continue;
 239     }
 240
 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)
 247         continue;
 248
 249       if ((Sec->getFlags() & SHF_TLS) && Sec->getType() == SHT_NOBITS) {
 250         uintX_t TVA = Dot + ThreadBssOffset;
 251         TVA = alignTo(TVA, Sec->getAlignment());
 252         Sec->setVA(TVA);
 253         ThreadBssOffset = TVA - Dot + Sec->getSize();
 254         continue;
 255       }
 256
 257       if (Sec->getFlags() & SHF_ALLOC) {
 258         Dot = alignTo(Dot, Sec->getAlignment());
 259         Sec->setVA(Dot);
 260         MinVA = std::min(MinVA, Dot);
 261         Dot += Sec->getSize();
 262         continue;
 263       }
 264     }
 265   }
 266
 267   // ELF and Program headers need to be right before the first section in
 268   // memory.
 269   // Set their addresses accordingly.
 270   MinVA = alignDown(MinVA - Out<ELFT>::ElfHeader->getSize() -
 271                         Out<ELFT>::ProgramHeaders->getSize(),
 272                     Target->PageSize);
 273   Out<ELFT>::ElfHeader->setVA(MinVA);
 274   Out<ELFT>::ProgramHeaders->setVA(Out<ELFT>::ElfHeader->getSize() + MinVA);
 275 }
 276
 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())
 281     return {};
 282   return I->second;
 283 }
 284
 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;
 295   });
 296   return I == End ? INT_MAX : (I - Begin);
 297 }
 298
 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)
 306     return 0;
 307   return I < J ? -1 : 1;
 308 }
 309
 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);
 316 }
 317
 318 class elf::ScriptParser : public ScriptParserBase {
 319   typedef void (ScriptParser::*Handler)();
 320
 321 public:
 322   ScriptParser(StringRef S, bool B) : ScriptParserBase(S), IsUnderSysroot(B) {}
 323
 324   void run();
 325
 326 private:
 327   void addFile(StringRef Path);
 328
 329   void readAsNeeded();
 330   void readEntry();
 331   void readExtern();
 332   void readGroup();
 333   void readInclude();
 334   void readNothing() {}
 335   void readOutput();
 336   void readOutputArch();
 337   void readOutputFormat();
 338   void readSearchDir();
 339   void readSections();
 340
 341   void readLocationCounterValue();
 342   void readOutputSectionDescription(StringRef OutSec);
 343   void readSymbolAssignment(StringRef Name);
 344   std::vector<StringRef> readSectionsCommandExpr();
 345
 346   const static StringMap<Handler> Cmd;
 347   ScriptConfiguration &Opt = *ScriptConfig;
 348   StringSaver Saver = {ScriptConfig->Alloc};
 349   bool IsUnderSysroot;
 350 };
 351
 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}};
 364
 365 void ScriptParser::run() {
 366   while (!atEOF()) {
 367     StringRef Tok = next();
 368     if (Handler Fn = Cmd.lookup(Tok))
 369       (this->*Fn)();
 370     else
 371       setError("unknown directive: " + Tok);
 372   }
 373 }
 374
 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()));
 381       return;
 382     }
 383   }
 384
 385   if (sys::path::is_absolute(S)) {
 386     Driver->addFile(S);
 387   } else if (S.startswith("=")) {
 388     if (Config->Sysroot.empty())
 389       Driver->addFile(S.substr(1));
 390     else
 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)) {
 395     Driver->addFile(S);
 396   } else {
 397     std::string Path = findFromSearchPaths(S);
 398     if (Path.empty())
 399       setError("unable to find " + S);
 400     else
 401       Driver->addFile(Saver.save(Path));
 402   }
 403 }
 404
 405 void ScriptParser::readAsNeeded() {
 406   expect("(");
 407   bool Orig = Config->AsNeeded;
 408   Config->AsNeeded = true;
 409   while (!Error) {
 410     StringRef Tok = next();
 411     if (Tok == ")")
 412       break;
 413     addFile(Tok);
 414   }
 415   Config->AsNeeded = Orig;
 416 }
 417
 418 void ScriptParser::readEntry() {
 419   // -e <symbol> takes predecence over ENTRY(<symbol>).
 420   expect("(");
 421   StringRef Tok = next();
 422   if (Config->Entry.empty())
 423     Config->Entry = Tok;
 424   expect(")");
 425 }
 426
 427 void ScriptParser::readExtern() {
 428   expect("(");
 429   while (!Error) {
 430     StringRef Tok = next();
 431     if (Tok == ")")
 432       return;
 433     Config->Undefined.push_back(Tok);
 434   }
 435 }
 436
 437 void ScriptParser::readGroup() {
 438   expect("(");
 439   while (!Error) {
 440     StringRef Tok = next();
 441     if (Tok == ")")
 442       return;
 443     if (Tok == "AS_NEEDED") {
 444       readAsNeeded();
 445       continue;
 446     }
 447     addFile(Tok);
 448   }
 449 }
 450
 451 void ScriptParser::readInclude() {
 452   StringRef Tok = next();
 453   auto MBOrErr = MemoryBuffer::getFile(Tok);
 454   if (!MBOrErr) {
 455     setError("cannot open " + Tok);
 456     return;
 457   }
 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());
 462 }
 463
 464 void ScriptParser::readOutput() {
 465   // -o <file> takes predecence over OUTPUT(<file>).
 466   expect("(");
 467   StringRef Tok = next();
 468   if (Config->OutputFile.empty())
 469     Config->OutputFile = Tok;
 470   expect(")");
 471 }
 472
 473 void ScriptParser::readOutputArch() {
 474   // Error checking only for now.
 475   expect("(");
 476   next();
 477   expect(")");
 478 }
 479
 480 void ScriptParser::readOutputFormat() {
 481   // Error checking only for now.
 482   expect("(");
 483   next();
 484   StringRef Tok = next();
 485   if (Tok == ")")
 486    return;
 487   if (Tok != ",") {
 488     setError("unexpected token: " + Tok);
 489     return;
 490   }
 491   next();
 492   expect(",");
 493   next();
 494   expect(")");
 495 }
 496
 497 void ScriptParser::readSearchDir() {
 498   expect("(");
 499   Config->SearchPaths.push_back(next());
 500   expect(")");
 501 }
 502
 503 void ScriptParser::readSections() {
 504   Opt.DoLayout = true;
 505   expect("{");
 506   while (!Error && !skip("}")) {
 507     StringRef Tok = peek();
 508     if (Tok == ".") {
 509       readLocationCounterValue();
 510       continue;
 511     }
 512     next();
 513     if (peek() == "=")
 514       readSymbolAssignment(Tok);
 515     else
 516       readOutputSectionDescription(Tok);
 517   }
 518 }
 519
 520 void ScriptParser::readLocationCounterValue() {
 521   expect(".");
 522   expect("=");
 523   std::vector<StringRef> Expr = readSectionsCommandExpr();
 524   if (Expr.empty())
 525     error("error in location counter expression");
 526   else
 527     Opt.Commands.push_back({AssignmentKind, std::move(Expr), "."});
 528 }
 529
 530 void ScriptParser::readOutputSectionDescription(StringRef OutSec) {
 531   Opt.Commands.push_back({SectionKind, {}, OutSec});
 532   expect(":");
 533   expect("{");
 534
 535   while (!Error && !skip("}")) {
 536     StringRef Tok = next();
 537     if (Tok == "*") {
 538       expect("(");
 539       while (!Error && !skip(")"))
 540         Opt.Sections.emplace_back(OutSec, next());
 541     } else if (Tok == "KEEP") {
 542       expect("(");
 543       expect("*");
 544       expect("(");
 545       while (!Error && !skip(")")) {
 546         StringRef Sec = next();
 547         Opt.Sections.emplace_back(OutSec, Sec);
 548         Opt.KeptSections.push_back(Sec);
 549       }
 550       expect(")");
 551     } else {
 552       setError("unknown command " + Tok);
 553     }
 554   }
 555
 556   StringRef Tok = peek();
 557   if (Tok.startswith("=")) {
 558     if (!Tok.startswith("=0x")) {
 559       setError("filler should be a hexadecimal value");
 560       return;
 561     }
 562     Tok = Tok.substr(3);
 563     Opt.Filler[OutSec] = parseHex(Tok);
 564     next();
 565   }
 566 }
 567
 568 void ScriptParser::readSymbolAssignment(StringRef Name) {
 569   expect("=");
 570   std::vector<StringRef> Expr = readSectionsCommandExpr();
 571   if (Expr.empty())
 572     error("error in symbol assignment expression");
 573   else
 574     Opt.Commands.push_back({AssignmentKind, std::move(Expr), Name});
 575 }
 576
 577 std::vector<StringRef> ScriptParser::readSectionsCommandExpr() {
 578   std::vector<StringRef> Expr;
 579   while (!Error) {
 580     StringRef Tok = next();
 581     if (Tok == ";")
 582       break;
 583     Expr.push_back(Tok);
 584   }
 585   return Expr;
 586 }
 587
 588 static bool isUnderSysroot(StringRef Path) {
 589   if (Config->Sysroot == "")
 590     return false;
 591   for (; !Path.empty(); Path = sys::path::parent_path(Path))
 592     if (sys::fs::equivalent(Config->Sysroot, Path))
 593       return true;
 594   return false;
 595 }
 596
 597 // Entry point.
 598 void elf::readLinkerScript(MemoryBufferRef MB) {
 599   StringRef Path = MB.getBufferIdentifier();
 600   ScriptParser(MB.getBuffer(), isUnderSysroot(Path)).run();
 601 }
 602
 603 template class elf::LinkerScript<ELF32LE>;
 604 template class elf::LinkerScript<ELF32BE>;
 605 template class elf::LinkerScript<ELF64LE>;
 606 template class elf::LinkerScript<ELF64BE>;