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

   1 //===- ScriptParser.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 a recursive-descendent parser for linker scripts.
  11 // Parsed results are stored to Config and Script global objects.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "ScriptParser.h"
  16 #include "Config.h"
  17 #include "Driver.h"
  18 #include "InputSection.h"
  19 #include "LinkerScript.h"
  20 #include "OutputSections.h"
  21 #include "ScriptLexer.h"
  22 #include "Symbols.h"
  23 #include "Target.h"
  24 #include "lld/Common/Memory.h"
  25 #include "llvm/ADT/SmallString.h"
  26 #include "llvm/ADT/StringRef.h"
  27 #include "llvm/ADT/StringSet.h"
  28 #include "llvm/ADT/StringSwitch.h"
  29 #include "llvm/BinaryFormat/ELF.h"
  30 #include "llvm/Support/Casting.h"
  31 #include "llvm/Support/ErrorHandling.h"
  32 #include "llvm/Support/FileSystem.h"
  33 #include "llvm/Support/Path.h"
  34 #include <cassert>
  35 #include <limits>
  36 #include <vector>
  37
  38 using namespace llvm;
  39 using namespace llvm::ELF;
  40 using namespace llvm::support::endian;
  41 using namespace lld;
  42 using namespace lld::elf;
  43
  44 static bool isUnderSysroot(StringRef Path);
  45
  46 namespace {
  47 class ScriptParser final : ScriptLexer {
  48 public:
  49   ScriptParser(MemoryBufferRef MB)
  50       : ScriptLexer(MB),
  51         IsUnderSysroot(isUnderSysroot(MB.getBufferIdentifier())) {}
  52
  53   void readLinkerScript();
  54   void readVersionScript();
  55   void readDynamicList();
  56   void readDefsym(StringRef Name);
  57
  58 private:
  59   void addFile(StringRef Path);
  60
  61   void readAsNeeded();
  62   void readEntry();
  63   void readExtern();
  64   void readGroup();
  65   void readInclude();
  66   void readInput();
  67   void readMemory();
  68   void readOutput();
  69   void readOutputArch();
  70   void readOutputFormat();
  71   void readPhdrs();
  72   void readRegionAlias();
  73   void readSearchDir();
  74   void readSections();
  75   void readVersion();
  76   void readVersionScriptCommand();
  77
  78   SymbolAssignment *readSymbolAssignment(StringRef Name);
  79   ByteCommand *readByteCommand(StringRef Tok);
  80   uint32_t readFill();
  81   uint32_t parseFill(StringRef Tok);
  82   void readSectionAddressType(OutputSection *Cmd);
  83   OutputSection *readOverlaySectionDescription();
  84   OutputSection *readOutputSectionDescription(StringRef OutSec);
  85   std::vector<BaseCommand *> readOverlay();
  86   std::vector<StringRef> readOutputSectionPhdrs();
  87   InputSectionDescription *readInputSectionDescription(StringRef Tok);
  88   StringMatcher readFilePatterns();
  89   std::vector<SectionPattern> readInputSectionsList();
  90   InputSectionDescription *readInputSectionRules(StringRef FilePattern);
  91   unsigned readPhdrType();
  92   SortSectionPolicy readSortKind();
  93   SymbolAssignment *readProvideHidden(bool Provide, bool Hidden);
  94   SymbolAssignment *readAssignment(StringRef Tok);
  95   void readSort();
  96   Expr readAssert();
  97   Expr readConstant();
  98   Expr getPageSize();
  99
 100   uint64_t readMemoryAssignment(StringRef, StringRef, StringRef);
 101   std::pair<uint32_t, uint32_t> readMemoryAttributes();
 102
 103   Expr combine(StringRef Op, Expr L, Expr R);
 104   Expr readExpr();
 105   Expr readExpr1(Expr Lhs, int MinPrec);
 106   StringRef readParenLiteral();
 107   Expr readPrimary();
 108   Expr readTernary(Expr Cond);
 109   Expr readParenExpr();
 110
 111   // For parsing version script.
 112   std::vector<SymbolVersion> readVersionExtern();
 113   void readAnonymousDeclaration();
 114   void readVersionDeclaration(StringRef VerStr);
 115
 116   std::pair<std::vector<SymbolVersion>, std::vector<SymbolVersion>>
 117   readSymbols();
 118
 119   // True if a script being read is in a subdirectory specified by -sysroot.
 120   bool IsUnderSysroot;
 121
 122   // A set to detect an INCLUDE() cycle.
 123   StringSet<> Seen;
 124 };
 125 } // namespace
 126
 127 static StringRef unquote(StringRef S) {
 128   if (S.startswith("\""))
 129     return S.substr(1, S.size() - 2);
 130   return S;
 131 }
 132
 133 static bool isUnderSysroot(StringRef Path) {
 134   if (Config->Sysroot == "")
 135     return false;
 136   for (; !Path.empty(); Path = sys::path::parent_path(Path))
 137     if (sys::fs::equivalent(Config->Sysroot, Path))
 138       return true;
 139   return false;
 140 }
 141
 142 // Some operations only support one non absolute value. Move the
 143 // absolute one to the right hand side for convenience.
 144 static void moveAbsRight(ExprValue &A, ExprValue &B) {
 145   if (A.Sec == nullptr || (A.ForceAbsolute && !B.isAbsolute()))
 146     std::swap(A, B);
 147   if (!B.isAbsolute())
 148     error(A.Loc + ": at least one side of the expression must be absolute");
 149 }
 150
 151 static ExprValue add(ExprValue A, ExprValue B) {
 152   moveAbsRight(A, B);
 153   return {A.Sec, A.ForceAbsolute, A.getSectionOffset() + B.getValue(), A.Loc};
 154 }
 155
 156 static ExprValue sub(ExprValue A, ExprValue B) {
 157   // The distance between two symbols in sections is absolute.
 158   if (!A.isAbsolute() && !B.isAbsolute())
 159     return A.getValue() - B.getValue();
 160   return {A.Sec, false, A.getSectionOffset() - B.getValue(), A.Loc};
 161 }
 162
 163 static ExprValue bitAnd(ExprValue A, ExprValue B) {
 164   moveAbsRight(A, B);
 165   return {A.Sec, A.ForceAbsolute,
 166           (A.getValue() & B.getValue()) - A.getSecAddr(), A.Loc};
 167 }
 168
 169 static ExprValue bitOr(ExprValue A, ExprValue B) {
 170   moveAbsRight(A, B);
 171   return {A.Sec, A.ForceAbsolute,
 172           (A.getValue() | B.getValue()) - A.getSecAddr(), A.Loc};
 173 }
 174
 175 void ScriptParser::readDynamicList() {
 176   Config->HasDynamicList = true;
 177   expect("{");
 178   std::vector<SymbolVersion> Locals;
 179   std::vector<SymbolVersion> Globals;
 180   std::tie(Locals, Globals) = readSymbols();
 181   expect(";");
 182
 183   if (!atEOF()) {
 184     setError("EOF expected, but got " + next());
 185     return;
 186   }
 187   if (!Locals.empty()) {
 188     setError("\"local:\" scope not supported in --dynamic-list");
 189     return;
 190   }
 191
 192   for (SymbolVersion V : Globals)
 193     Config->DynamicList.push_back(V);
 194 }
 195
 196 void ScriptParser::readVersionScript() {
 197   readVersionScriptCommand();
 198   if (!atEOF())
 199     setError("EOF expected, but got " + next());
 200 }
 201
 202 void ScriptParser::readVersionScriptCommand() {
 203   if (consume("{")) {
 204     readAnonymousDeclaration();
 205     return;
 206   }
 207
 208   while (!atEOF() && !errorCount() && peek() != "}") {
 209     StringRef VerStr = next();
 210     if (VerStr == "{") {
 211       setError("anonymous version definition is used in "
 212                "combination with other version definitions");
 213       return;
 214     }
 215     expect("{");
 216     readVersionDeclaration(VerStr);
 217   }
 218 }
 219
 220 void ScriptParser::readVersion() {
 221   expect("{");
 222   readVersionScriptCommand();
 223   expect("}");
 224 }
 225
 226 void ScriptParser::readLinkerScript() {
 227   while (!atEOF()) {
 228     StringRef Tok = next();
 229     if (Tok == ";")
 230       continue;
 231
 232     if (Tok == "ENTRY") {
 233       readEntry();
 234     } else if (Tok == "EXTERN") {
 235       readExtern();
 236     } else if (Tok == "GROUP") {
 237       readGroup();
 238     } else if (Tok == "INCLUDE") {
 239       readInclude();
 240     } else if (Tok == "INPUT") {
 241       readInput();
 242     } else if (Tok == "MEMORY") {
 243       readMemory();
 244     } else if (Tok == "OUTPUT") {
 245       readOutput();
 246     } else if (Tok == "OUTPUT_ARCH") {
 247       readOutputArch();
 248     } else if (Tok == "OUTPUT_FORMAT") {
 249       readOutputFormat();
 250     } else if (Tok == "PHDRS") {
 251       readPhdrs();
 252     } else if (Tok == "REGION_ALIAS") {
 253       readRegionAlias();
 254     } else if (Tok == "SEARCH_DIR") {
 255       readSearchDir();
 256     } else if (Tok == "SECTIONS") {
 257       readSections();
 258     } else if (Tok == "VERSION") {
 259       readVersion();
 260     } else if (SymbolAssignment *Cmd = readAssignment(Tok)) {
 261       Script->SectionCommands.push_back(Cmd);
 262     } else {
 263       setError("unknown directive: " + Tok);
 264     }
 265   }
 266 }
 267
 268 void ScriptParser::readDefsym(StringRef Name) {
 269   Expr E = readExpr();
 270   if (!atEOF())
 271     setError("EOF expected, but got " + next());
 272   SymbolAssignment *Cmd = make<SymbolAssignment>(Name, E, getCurrentLocation());
 273   Script->SectionCommands.push_back(Cmd);
 274 }
 275
 276 void ScriptParser::addFile(StringRef S) {
 277   if (IsUnderSysroot && S.startswith("/")) {
 278     SmallString<128> PathData;
 279     StringRef Path = (Config->Sysroot + S).toStringRef(PathData);
 280     if (sys::fs::exists(Path)) {
 281       Driver->addFile(Saver.save(Path), /*WithLOption=*/false);
 282       return;
 283     }
 284   }
 285
 286   if (S.startswith("/")) {
 287     Driver->addFile(S, /*WithLOption=*/false);
 288   } else if (S.startswith("=")) {
 289     if (Config->Sysroot.empty())
 290       Driver->addFile(S.substr(1), /*WithLOption=*/false);
 291     else
 292       Driver->addFile(Saver.save(Config->Sysroot + "/" + S.substr(1)),
 293                       /*WithLOption=*/false);
 294   } else if (S.startswith("-l")) {
 295     Driver->addLibrary(S.substr(2));
 296   } else if (sys::fs::exists(S)) {
 297     Driver->addFile(S, /*WithLOption=*/false);
 298   } else {
 299     if (Optional<std::string> Path = findFromSearchPaths(S))
 300       Driver->addFile(Saver.save(*Path), /*WithLOption=*/true);
 301     else
 302       setError("unable to find " + S);
 303   }
 304 }
 305
 306 void ScriptParser::readAsNeeded() {
 307   expect("(");
 308   bool Orig = Config->AsNeeded;
 309   Config->AsNeeded = true;
 310   while (!errorCount() && !consume(")"))
 311     addFile(unquote(next()));
 312   Config->AsNeeded = Orig;
 313 }
 314
 315 void ScriptParser::readEntry() {
 316   // -e <symbol> takes predecence over ENTRY(<symbol>).
 317   expect("(");
 318   StringRef Tok = next();
 319   if (Config->Entry.empty())
 320     Config->Entry = Tok;
 321   expect(")");
 322 }
 323
 324 void ScriptParser::readExtern() {
 325   expect("(");
 326   while (!errorCount() && !consume(")"))
 327     Config->Undefined.push_back(next());
 328 }
 329
 330 void ScriptParser::readGroup() {
 331   bool Orig = InputFile::IsInGroup;
 332   InputFile::IsInGroup = true;
 333   readInput();
 334   InputFile::IsInGroup = Orig;
 335   if (!Orig)
 336     ++InputFile::NextGroupId;
 337 }
 338
 339 void ScriptParser::readInclude() {
 340   StringRef Tok = unquote(next());
 341
 342   if (!Seen.insert(Tok).second) {
 343     setError("there is a cycle in linker script INCLUDEs");
 344     return;
 345   }
 346
 347   if (Optional<std::string> Path = searchScript(Tok)) {
 348     if (Optional<MemoryBufferRef> MB = readFile(*Path))
 349       tokenize(*MB);
 350     return;
 351   }
 352   setError("cannot find linker script " + Tok);
 353 }
 354
 355 void ScriptParser::readInput() {
 356   expect("(");
 357   while (!errorCount() && !consume(")")) {
 358     if (consume("AS_NEEDED"))
 359       readAsNeeded();
 360     else
 361       addFile(unquote(next()));
 362   }
 363 }
 364
 365 void ScriptParser::readOutput() {
 366   // -o <file> takes predecence over OUTPUT(<file>).
 367   expect("(");
 368   StringRef Tok = next();
 369   if (Config->OutputFile.empty())
 370     Config->OutputFile = unquote(Tok);
 371   expect(")");
 372 }
 373
 374 void ScriptParser::readOutputArch() {
 375   // OUTPUT_ARCH is ignored for now.
 376   expect("(");
 377   while (!errorCount() && !consume(")"))
 378     skip();
 379 }
 380
 381 void ScriptParser::readOutputFormat() {
 382   // Error checking only for now.
 383   expect("(");
 384   skip();
 385   if (consume(")"))
 386     return;
 387   expect(",");
 388   skip();
 389   expect(",");
 390   skip();
 391   expect(")");
 392 }
 393
 394 void ScriptParser::readPhdrs() {
 395   expect("{");
 396
 397   while (!errorCount() && !consume("}")) {
 398     PhdrsCommand Cmd;
 399     Cmd.Name = next();
 400     Cmd.Type = readPhdrType();
 401
 402     while (!errorCount() && !consume(";")) {
 403       if (consume("FILEHDR"))
 404         Cmd.HasFilehdr = true;
 405       else if (consume("PHDRS"))
 406         Cmd.HasPhdrs = true;
 407       else if (consume("AT"))
 408         Cmd.LMAExpr = readParenExpr();
 409       else if (consume("FLAGS"))
 410         Cmd.Flags = readParenExpr()().getValue();
 411       else
 412         setError("unexpected header attribute: " + next());
 413     }
 414
 415     Script->PhdrsCommands.push_back(Cmd);
 416   }
 417 }
 418
 419 void ScriptParser::readRegionAlias() {
 420   expect("(");
 421   StringRef Alias = unquote(next());
 422   expect(",");
 423   StringRef Name = next();
 424   expect(")");
 425
 426   if (Script->MemoryRegions.count(Alias))
 427     setError("redefinition of memory region '" + Alias + "'");
 428   if (!Script->MemoryRegions.count(Name))
 429     setError("memory region '" + Name + "' is not defined");
 430   Script->MemoryRegions.insert({Alias, Script->MemoryRegions[Name]});
 431 }
 432
 433 void ScriptParser::readSearchDir() {
 434   expect("(");
 435   StringRef Tok = next();
 436   if (!Config->Nostdlib)
 437     Config->SearchPaths.push_back(unquote(Tok));
 438   expect(")");
 439 }
 440
 441 // This reads an overlay description. Overlays are used to describe output
 442 // sections that use the same virtual memory range and normally would trigger
 443 // linker's sections sanity check failures.
 444 // https://sourceware.org/binutils/docs/ld/Overlay-Description.html#Overlay-Description
 445 std::vector<BaseCommand *> ScriptParser::readOverlay() {
 446   // VA and LMA expressions are optional, though for simplicity of
 447   // implementation we assume they are not. That is what OVERLAY was designed
 448   // for first of all: to allow sections with overlapping VAs at different LMAs.
 449   Expr AddrExpr = readExpr();
 450   expect(":");
 451   expect("AT");
 452   Expr LMAExpr = readParenExpr();
 453   expect("{");
 454
 455   std::vector<BaseCommand *> V;
 456   OutputSection *Prev = nullptr;
 457   while (!errorCount() && !consume("}")) {
 458     // VA is the same for all sections. The LMAs are consecutive in memory
 459     // starting from the base load address specified.
 460     OutputSection *OS = readOverlaySectionDescription();
 461     OS->AddrExpr = AddrExpr;
 462     if (Prev)
 463       OS->LMAExpr = [=] { return Prev->getLMA() + Prev->Size; };
 464     else
 465       OS->LMAExpr = LMAExpr;
 466     V.push_back(OS);
 467     Prev = OS;
 468   }
 469
 470   // According to the specification, at the end of the overlay, the location
 471   // counter should be equal to the overlay base address plus size of the
 472   // largest section seen in the overlay.
 473   // Here we want to create the Dot assignment command to achieve that.
 474   Expr MoveDot = [=] {
 475     uint64_t Max = 0;
 476     for (BaseCommand *Cmd : V)
 477       Max = std::max(Max, cast<OutputSection>(Cmd)->Size);
 478     return AddrExpr().getValue() + Max;
 479   };
 480   V.push_back(make<SymbolAssignment>(".", MoveDot, getCurrentLocation()));
 481   return V;
 482 }
 483
 484 void ScriptParser::readSections() {
 485   Script->HasSectionsCommand = true;
 486
 487   // -no-rosegment is used to avoid placing read only non-executable sections in
 488   // their own segment. We do the same if SECTIONS command is present in linker
 489   // script. See comment for computeFlags().
 490   Config->SingleRoRx = true;
 491
 492   expect("{");
 493   std::vector<BaseCommand *> V;
 494   while (!errorCount() && !consume("}")) {
 495     StringRef Tok = next();
 496     if (Tok == "OVERLAY") {
 497       for (BaseCommand *Cmd : readOverlay())
 498         V.push_back(Cmd);
 499       continue;
 500     } else if (Tok == "INCLUDE") {
 501       readInclude();
 502       continue;
 503     }
 504
 505     if (BaseCommand *Cmd = readAssignment(Tok))
 506       V.push_back(Cmd);
 507     else
 508       V.push_back(readOutputSectionDescription(Tok));
 509   }
 510
 511   if (!atEOF() && consume("INSERT")) {
 512     std::vector<BaseCommand *> *Dest = nullptr;
 513     if (consume("AFTER"))
 514       Dest = &Script->InsertAfterCommands[next()];
 515     else if (consume("BEFORE"))
 516       Dest = &Script->InsertBeforeCommands[next()];
 517     else
 518       setError("expected AFTER/BEFORE, but got '" + next() + "'");
 519     if (Dest)
 520       Dest->insert(Dest->end(), V.begin(), V.end());
 521     return;
 522   }
 523
 524   Script->SectionCommands.insert(Script->SectionCommands.end(), V.begin(),
 525                                  V.end());
 526 }
 527
 528 static int precedence(StringRef Op) {
 529   return StringSwitch<int>(Op)
 530       .Cases("*", "/", "%", 8)
 531       .Cases("+", "-", 7)
 532       .Cases("<<", ">>", 6)
 533       .Cases("<", "<=", ">", ">=", "==", "!=", 5)
 534       .Case("&", 4)
 535       .Case("|", 3)
 536       .Case("&&", 2)
 537       .Case("||", 1)
 538       .Default(-1);
 539 }
 540
 541 StringMatcher ScriptParser::readFilePatterns() {
 542   std::vector<StringRef> V;
 543   while (!errorCount() && !consume(")"))
 544     V.push_back(next());
 545   return StringMatcher(V);
 546 }
 547
 548 SortSectionPolicy ScriptParser::readSortKind() {
 549   if (consume("SORT") || consume("SORT_BY_NAME"))
 550     return SortSectionPolicy::Name;
 551   if (consume("SORT_BY_ALIGNMENT"))
 552     return SortSectionPolicy::Alignment;
 553   if (consume("SORT_BY_INIT_PRIORITY"))
 554     return SortSectionPolicy::Priority;
 555   if (consume("SORT_NONE"))
 556     return SortSectionPolicy::None;
 557   return SortSectionPolicy::Default;
 558 }
 559
 560 // Reads SECTIONS command contents in the following form:
 561 //
 562 // <contents> ::= <elem>*
 563 // <elem>     ::= <exclude>? <glob-pattern>
 564 // <exclude>  ::= "EXCLUDE_FILE" "(" <glob-pattern>+ ")"
 565 //
 566 // For example,
 567 //
 568 // *(.foo EXCLUDE_FILE (a.o) .bar EXCLUDE_FILE (b.o) .baz)
 569 //
 570 // is parsed as ".foo", ".bar" with "a.o", and ".baz" with "b.o".
 571 // The semantics of that is section .foo in any file, section .bar in
 572 // any file but a.o, and section .baz in any file but b.o.
 573 std::vector<SectionPattern> ScriptParser::readInputSectionsList() {
 574   std::vector<SectionPattern> Ret;
 575   while (!errorCount() && peek() != ")") {
 576     StringMatcher ExcludeFilePat;
 577     if (consume("EXCLUDE_FILE")) {
 578       expect("(");
 579       ExcludeFilePat = readFilePatterns();
 580     }
 581
 582     std::vector<StringRef> V;
 583     while (!errorCount() && peek() != ")" && peek() != "EXCLUDE_FILE")
 584       V.push_back(next());
 585
 586     if (!V.empty())
 587       Ret.push_back({std::move(ExcludeFilePat), StringMatcher(V)});
 588     else
 589       setError("section pattern is expected");
 590   }
 591   return Ret;
 592 }
 593
 594 // Reads contents of "SECTIONS" directive. That directive contains a
 595 // list of glob patterns for input sections. The grammar is as follows.
 596 //
 597 // <patterns> ::= <section-list>
 598 //              | <sort> "(" <section-list> ")"
 599 //              | <sort> "(" <sort> "(" <section-list> ")" ")"
 600 //
 601 // <sort>     ::= "SORT" | "SORT_BY_NAME" | "SORT_BY_ALIGNMENT"
 602 //              | "SORT_BY_INIT_PRIORITY" | "SORT_NONE"
 603 //
 604 // <section-list> is parsed by readInputSectionsList().
 605 InputSectionDescription *
 606 ScriptParser::readInputSectionRules(StringRef FilePattern) {
 607   auto *Cmd = make<InputSectionDescription>(FilePattern);
 608   expect("(");
 609
 610   while (!errorCount() && !consume(")")) {
 611     SortSectionPolicy Outer = readSortKind();
 612     SortSectionPolicy Inner = SortSectionPolicy::Default;
 613     std::vector<SectionPattern> V;
 614     if (Outer != SortSectionPolicy::Default) {
 615       expect("(");
 616       Inner = readSortKind();
 617       if (Inner != SortSectionPolicy::Default) {
 618         expect("(");
 619         V = readInputSectionsList();
 620         expect(")");
 621       } else {
 622         V = readInputSectionsList();
 623       }
 624       expect(")");
 625     } else {
 626       V = readInputSectionsList();
 627     }
 628
 629     for (SectionPattern &Pat : V) {
 630       Pat.SortInner = Inner;
 631       Pat.SortOuter = Outer;
 632     }
 633
 634     std::move(V.begin(), V.end(), std::back_inserter(Cmd->SectionPatterns));
 635   }
 636   return Cmd;
 637 }
 638
 639 InputSectionDescription *
 640 ScriptParser::readInputSectionDescription(StringRef Tok) {
 641   // Input section wildcard can be surrounded by KEEP.
 642   // https://sourceware.org/binutils/docs/ld/Input-Section-Keep.html#Input-Section-Keep
 643   if (Tok == "KEEP") {
 644     expect("(");
 645     StringRef FilePattern = next();
 646     InputSectionDescription *Cmd = readInputSectionRules(FilePattern);
 647     expect(")");
 648     Script->KeptSections.push_back(Cmd);
 649     return Cmd;
 650   }
 651   return readInputSectionRules(Tok);
 652 }
 653
 654 void ScriptParser::readSort() {
 655   expect("(");
 656   expect("CONSTRUCTORS");
 657   expect(")");
 658 }
 659
 660 Expr ScriptParser::readAssert() {
 661   expect("(");
 662   Expr E = readExpr();
 663   expect(",");
 664   StringRef Msg = unquote(next());
 665   expect(")");
 666
 667   return [=] {
 668     if (!E().getValue())
 669       error(Msg);
 670     return Script->getDot();
 671   };
 672 }
 673
 674 // Reads a FILL(expr) command. We handle the FILL command as an
 675 // alias for =fillexp section attribute, which is different from
 676 // what GNU linkers do.
 677 // https://sourceware.org/binutils/docs/ld/Output-Section-Data.html
 678 uint32_t ScriptParser::readFill() {
 679   expect("(");
 680   uint32_t V = parseFill(next());
 681   expect(")");
 682   return V;
 683 }
 684
 685 // Reads an expression and/or the special directive for an output
 686 // section definition. Directive is one of following: "(NOLOAD)",
 687 // "(COPY)", "(INFO)" or "(OVERLAY)".
 688 //
 689 // An output section name can be followed by an address expression
 690 // and/or directive. This grammar is not LL(1) because "(" can be
 691 // interpreted as either the beginning of some expression or beginning
 692 // of directive.
 693 //
 694 // https://sourceware.org/binutils/docs/ld/Output-Section-Address.html
 695 // https://sourceware.org/binutils/docs/ld/Output-Section-Type.html
 696 void ScriptParser::readSectionAddressType(OutputSection *Cmd) {
 697   if (consume("(")) {
 698     if (consume("NOLOAD")) {
 699       expect(")");
 700       Cmd->Noload = true;
 701       return;
 702     }
 703     if (consume("COPY") || consume("INFO") || consume("OVERLAY")) {
 704       expect(")");
 705       Cmd->NonAlloc = true;
 706       return;
 707     }
 708     Cmd->AddrExpr = readExpr();
 709     expect(")");
 710   } else {
 711     Cmd->AddrExpr = readExpr();
 712   }
 713
 714   if (consume("(")) {
 715     expect("NOLOAD");
 716     expect(")");
 717     Cmd->Noload = true;
 718   }
 719 }
 720
 721 static Expr checkAlignment(Expr E, std::string &Loc) {
 722   return [=] {
 723     uint64_t Alignment = std::max((uint64_t)1, E().getValue());
 724     if (!isPowerOf2_64(Alignment)) {
 725       error(Loc + ": alignment must be power of 2");
 726       return (uint64_t)1; // Return a dummy value.
 727     }
 728     return Alignment;
 729   };
 730 }
 731
 732 OutputSection *ScriptParser::readOverlaySectionDescription() {
 733   OutputSection *Cmd =
 734       Script->createOutputSection(next(), getCurrentLocation());
 735   Cmd->InOverlay = true;
 736   expect("{");
 737   while (!errorCount() && !consume("}"))
 738     Cmd->SectionCommands.push_back(readInputSectionRules(next()));
 739   Cmd->Phdrs = readOutputSectionPhdrs();
 740   return Cmd;
 741 }
 742
 743 OutputSection *ScriptParser::readOutputSectionDescription(StringRef OutSec) {
 744   OutputSection *Cmd =
 745       Script->createOutputSection(OutSec, getCurrentLocation());
 746
 747   size_t SymbolsReferenced = Script->ReferencedSymbols.size();
 748
 749   if (peek() != ":")
 750     readSectionAddressType(Cmd);
 751   expect(":");
 752
 753   std::string Location = getCurrentLocation();
 754   if (consume("AT"))
 755     Cmd->LMAExpr = readParenExpr();
 756   if (consume("ALIGN"))
 757     Cmd->AlignExpr = checkAlignment(readParenExpr(), Location);
 758   if (consume("SUBALIGN"))
 759     Cmd->SubalignExpr = checkAlignment(readParenExpr(), Location);
 760
 761   // Parse constraints.
 762   if (consume("ONLY_IF_RO"))
 763     Cmd->Constraint = ConstraintKind::ReadOnly;
 764   if (consume("ONLY_IF_RW"))
 765     Cmd->Constraint = ConstraintKind::ReadWrite;
 766   expect("{");
 767
 768   while (!errorCount() && !consume("}")) {
 769     StringRef Tok = next();
 770     if (Tok == ";") {
 771       // Empty commands are allowed. Do nothing here.
 772     } else if (SymbolAssignment *Assign = readAssignment(Tok)) {
 773       Cmd->SectionCommands.push_back(Assign);
 774     } else if (ByteCommand *Data = readByteCommand(Tok)) {
 775       Cmd->SectionCommands.push_back(Data);
 776     } else if (Tok == "CONSTRUCTORS") {
 777       // CONSTRUCTORS is a keyword to make the linker recognize C++ ctors/dtors
 778       // by name. This is for very old file formats such as ECOFF/XCOFF.
 779       // For ELF, we should ignore.
 780     } else if (Tok == "FILL") {
 781       Cmd->Filler = readFill();
 782     } else if (Tok == "SORT") {
 783       readSort();
 784     } else if (Tok == "INCLUDE") {
 785       readInclude();
 786     } else if (peek() == "(") {
 787       Cmd->SectionCommands.push_back(readInputSectionDescription(Tok));
 788     } else {
 789       setError("unknown command " + Tok);
 790     }
 791   }
 792
 793   if (consume(">"))
 794     Cmd->MemoryRegionName = next();
 795
 796   if (consume("AT")) {
 797     expect(">");
 798     Cmd->LMARegionName = next();
 799   }
 800
 801   if (Cmd->LMAExpr && !Cmd->LMARegionName.empty())
 802     error("section can't have both LMA and a load region");
 803
 804   Cmd->Phdrs = readOutputSectionPhdrs();
 805
 806   if (consume("="))
 807     Cmd->Filler = parseFill(next());
 808   else if (peek().startswith("="))
 809     Cmd->Filler = parseFill(next().drop_front());
 810
 811   // Consume optional comma following output section command.
 812   consume(",");
 813
 814   if (Script->ReferencedSymbols.size() > SymbolsReferenced)
 815     Cmd->ExpressionsUseSymbols = true;
 816   return Cmd;
 817 }
 818
 819 // Parses a given string as a octal/decimal/hexadecimal number and
 820 // returns it as a big-endian number. Used for `=<fillexp>`.
 821 // https://sourceware.org/binutils/docs/ld/Output-Section-Fill.html
 822 //
 823 // When reading a hexstring, ld.bfd handles it as a blob of arbitrary
 824 // size, while ld.gold always handles it as a 32-bit big-endian number.
 825 // We are compatible with ld.gold because it's easier to implement.
 826 uint32_t ScriptParser::parseFill(StringRef Tok) {
 827   uint32_t V = 0;
 828   if (!to_integer(Tok, V))
 829     setError("invalid filler expression: " + Tok);
 830
 831   uint32_t Buf;
 832   write32be(&Buf, V);
 833   return Buf;
 834 }
 835
 836 SymbolAssignment *ScriptParser::readProvideHidden(bool Provide, bool Hidden) {
 837   expect("(");
 838   SymbolAssignment *Cmd = readSymbolAssignment(next());
 839   Cmd->Provide = Provide;
 840   Cmd->Hidden = Hidden;
 841   expect(")");
 842   return Cmd;
 843 }
 844
 845 SymbolAssignment *ScriptParser::readAssignment(StringRef Tok) {
 846   // Assert expression returns Dot, so this is equal to ".=."
 847   if (Tok == "ASSERT")
 848     return make<SymbolAssignment>(".", readAssert(), getCurrentLocation());
 849
 850   size_t OldPos = Pos;
 851   SymbolAssignment *Cmd = nullptr;
 852   if (peek() == "=" || peek() == "+=")
 853     Cmd = readSymbolAssignment(Tok);
 854   else if (Tok == "PROVIDE")
 855     Cmd = readProvideHidden(true, false);
 856   else if (Tok == "HIDDEN")
 857     Cmd = readProvideHidden(false, true);
 858   else if (Tok == "PROVIDE_HIDDEN")
 859     Cmd = readProvideHidden(true, true);
 860
 861   if (Cmd) {
 862     Cmd->CommandString =
 863         Tok.str() + " " +
 864         llvm::join(Tokens.begin() + OldPos, Tokens.begin() + Pos, " ");
 865     expect(";");
 866   }
 867   return Cmd;
 868 }
 869
 870 SymbolAssignment *ScriptParser::readSymbolAssignment(StringRef Name) {
 871   StringRef Op = next();
 872   assert(Op == "=" || Op == "+=");
 873   Expr E = readExpr();
 874   if (Op == "+=") {
 875     std::string Loc = getCurrentLocation();
 876     E = [=] { return add(Script->getSymbolValue(Name, Loc), E()); };
 877   }
 878   return make<SymbolAssignment>(Name, E, getCurrentLocation());
 879 }
 880
 881 // This is an operator-precedence parser to parse a linker
 882 // script expression.
 883 Expr ScriptParser::readExpr() {
 884   // Our lexer is context-aware. Set the in-expression bit so that
 885   // they apply different tokenization rules.
 886   bool Orig = InExpr;
 887   InExpr = true;
 888   Expr E = readExpr1(readPrimary(), 0);
 889   InExpr = Orig;
 890   return E;
 891 }
 892
 893 Expr ScriptParser::combine(StringRef Op, Expr L, Expr R) {
 894   if (Op == "+")
 895     return [=] { return add(L(), R()); };
 896   if (Op == "-")
 897     return [=] { return sub(L(), R()); };
 898   if (Op == "*")
 899     return [=] { return L().getValue() * R().getValue(); };
 900   if (Op == "/") {
 901     std::string Loc = getCurrentLocation();
 902     return [=]() -> uint64_t {
 903       if (uint64_t RV = R().getValue())
 904         return L().getValue() / RV;
 905       error(Loc + ": division by zero");
 906       return 0;
 907     };
 908   }
 909   if (Op == "%") {
 910     std::string Loc = getCurrentLocation();
 911     return [=]() -> uint64_t {
 912       if (uint64_t RV = R().getValue())
 913         return L().getValue() % RV;
 914       error(Loc + ": modulo by zero");
 915       return 0;
 916     };
 917   }
 918   if (Op == "<<")
 919     return [=] { return L().getValue() << R().getValue(); };
 920   if (Op == ">>")
 921     return [=] { return L().getValue() >> R().getValue(); };
 922   if (Op == "<")
 923     return [=] { return L().getValue() < R().getValue(); };
 924   if (Op == ">")
 925     return [=] { return L().getValue() > R().getValue(); };
 926   if (Op == ">=")
 927     return [=] { return L().getValue() >= R().getValue(); };
 928   if (Op == "<=")
 929     return [=] { return L().getValue() <= R().getValue(); };
 930   if (Op == "==")
 931     return [=] { return L().getValue() == R().getValue(); };
 932   if (Op == "!=")
 933     return [=] { return L().getValue() != R().getValue(); };
 934   if (Op == "||")
 935     return [=] { return L().getValue() || R().getValue(); };
 936   if (Op == "&&")
 937     return [=] { return L().getValue() && R().getValue(); };
 938   if (Op == "&")
 939     return [=] { return bitAnd(L(), R()); };
 940   if (Op == "|")
 941     return [=] { return bitOr(L(), R()); };
 942   llvm_unreachable("invalid operator");
 943 }
 944
 945 // This is a part of the operator-precedence parser. This function
 946 // assumes that the remaining token stream starts with an operator.
 947 Expr ScriptParser::readExpr1(Expr Lhs, int MinPrec) {
 948   while (!atEOF() && !errorCount()) {
 949     // Read an operator and an expression.
 950     if (consume("?"))
 951       return readTernary(Lhs);
 952     StringRef Op1 = peek();
 953     if (precedence(Op1) < MinPrec)
 954       break;
 955     skip();
 956     Expr Rhs = readPrimary();
 957
 958     // Evaluate the remaining part of the expression first if the
 959     // next operator has greater precedence than the previous one.
 960     // For example, if we have read "+" and "3", and if the next
 961     // operator is "*", then we'll evaluate 3 * ... part first.
 962     while (!atEOF()) {
 963       StringRef Op2 = peek();
 964       if (precedence(Op2) <= precedence(Op1))
 965         break;
 966       Rhs = readExpr1(Rhs, precedence(Op2));
 967     }
 968
 969     Lhs = combine(Op1, Lhs, Rhs);
 970   }
 971   return Lhs;
 972 }
 973
 974 Expr ScriptParser::getPageSize() {
 975   std::string Location = getCurrentLocation();
 976   return [=]() -> uint64_t {
 977     if (Target)
 978       return Target->PageSize;
 979     error(Location + ": unable to calculate page size");
 980     return 4096; // Return a dummy value.
 981   };
 982 }
 983
 984 Expr ScriptParser::readConstant() {
 985   StringRef S = readParenLiteral();
 986   if (S == "COMMONPAGESIZE")
 987     return getPageSize();
 988   if (S == "MAXPAGESIZE")
 989     return [] { return Config->MaxPageSize; };
 990   setError("unknown constant: " + S);
 991   return [] { return 0; };
 992 }
 993
 994 // Parses Tok as an integer. It recognizes hexadecimal (prefixed with
 995 // "0x" or suffixed with "H") and decimal numbers. Decimal numbers may
 996 // have "K" (Ki) or "M" (Mi) suffixes.
 997 static Optional<uint64_t> parseInt(StringRef Tok) {
 998   // Hexadecimal
 999   uint64_t Val;
1000   if (Tok.startswith_lower("0x")) {
1001     if (!to_integer(Tok.substr(2), Val, 16))
1002       return None;
1003     return Val;
1004   }
1005   if (Tok.endswith_lower("H")) {
1006     if (!to_integer(Tok.drop_back(), Val, 16))
1007       return None;
1008     return Val;
1009   }
1010
1011   // Decimal
1012   if (Tok.endswith_lower("K")) {
1013     if (!to_integer(Tok.drop_back(), Val, 10))
1014       return None;
1015     return Val * 1024;
1016   }
1017   if (Tok.endswith_lower("M")) {
1018     if (!to_integer(Tok.drop_back(), Val, 10))
1019       return None;
1020     return Val * 1024 * 1024;
1021   }
1022   if (!to_integer(Tok, Val, 10))
1023     return None;
1024   return Val;
1025 }
1026
1027 ByteCommand *ScriptParser::readByteCommand(StringRef Tok) {
1028   int Size = StringSwitch<int>(Tok)
1029                  .Case("BYTE", 1)
1030                  .Case("SHORT", 2)
1031                  .Case("LONG", 4)
1032                  .Case("QUAD", 8)
1033                  .Default(-1);
1034   if (Size == -1)
1035     return nullptr;
1036
1037   size_t OldPos = Pos;
1038   Expr E = readParenExpr();
1039   std::string CommandString =
1040       Tok.str() + " " +
1041       llvm::join(Tokens.begin() + OldPos, Tokens.begin() + Pos, " ");
1042   return make<ByteCommand>(E, Size, CommandString);
1043 }
1044
1045 StringRef ScriptParser::readParenLiteral() {
1046   expect("(");
1047   bool Orig = InExpr;
1048   InExpr = false;
1049   StringRef Tok = next();
1050   InExpr = Orig;
1051   expect(")");
1052   return Tok;
1053 }
1054
1055 static void checkIfExists(OutputSection *Cmd, StringRef Location) {
1056   if (Cmd->Location.empty() && Script->ErrorOnMissingSection)
1057     error(Location + ": undefined section " + Cmd->Name);
1058 }
1059
1060 Expr ScriptParser::readPrimary() {
1061   if (peek() == "(")
1062     return readParenExpr();
1063
1064   if (consume("~")) {
1065     Expr E = readPrimary();
1066     return [=] { return ~E().getValue(); };
1067   }
1068   if (consume("!")) {
1069     Expr E = readPrimary();
1070     return [=] { return !E().getValue(); };
1071   }
1072   if (consume("-")) {
1073     Expr E = readPrimary();
1074     return [=] { return -E().getValue(); };
1075   }
1076
1077   StringRef Tok = next();
1078   std::string Location = getCurrentLocation();
1079
1080   // Built-in functions are parsed here.
1081   // https://sourceware.org/binutils/docs/ld/Builtin-Functions.html.
1082   if (Tok == "ABSOLUTE") {
1083     Expr Inner = readParenExpr();
1084     return [=] {
1085       ExprValue I = Inner();
1086       I.ForceAbsolute = true;
1087       return I;
1088     };
1089   }
1090   if (Tok == "ADDR") {
1091     StringRef Name = readParenLiteral();
1092     OutputSection *Sec = Script->getOrCreateOutputSection(Name);
1093     return [=]() -> ExprValue {
1094       checkIfExists(Sec, Location);
1095       return {Sec, false, 0, Location};
1096     };
1097   }
1098   if (Tok == "ALIGN") {
1099     expect("(");
1100     Expr E = readExpr();
1101     if (consume(")")) {
1102       E = checkAlignment(E, Location);
1103       return [=] { return alignTo(Script->getDot(), E().getValue()); };
1104     }
1105     expect(",");
1106     Expr E2 = checkAlignment(readExpr(), Location);
1107     expect(")");
1108     return [=] {
1109       ExprValue V = E();
1110       V.Alignment = E2().getValue();
1111       return V;
1112     };
1113   }
1114   if (Tok == "ALIGNOF") {
1115     StringRef Name = readParenLiteral();
1116     OutputSection *Cmd = Script->getOrCreateOutputSection(Name);
1117     return [=] {
1118       checkIfExists(Cmd, Location);
1119       return Cmd->Alignment;
1120     };
1121   }
1122   if (Tok == "ASSERT")
1123     return readAssert();
1124   if (Tok == "CONSTANT")
1125     return readConstant();
1126   if (Tok == "DATA_SEGMENT_ALIGN") {
1127     expect("(");
1128     Expr E = readExpr();
1129     expect(",");
1130     readExpr();
1131     expect(")");
1132     return [=] {
1133       return alignTo(Script->getDot(), std::max((uint64_t)1, E().getValue()));
1134     };
1135   }
1136   if (Tok == "DATA_SEGMENT_END") {
1137     expect("(");
1138     expect(".");
1139     expect(")");
1140     return [] { return Script->getDot(); };
1141   }
1142   if (Tok == "DATA_SEGMENT_RELRO_END") {
1143     // GNU linkers implements more complicated logic to handle
1144     // DATA_SEGMENT_RELRO_END. We instead ignore the arguments and
1145     // just align to the next page boundary for simplicity.
1146     expect("(");
1147     readExpr();
1148     expect(",");
1149     readExpr();
1150     expect(")");
1151     Expr E = getPageSize();
1152     return [=] { return alignTo(Script->getDot(), E().getValue()); };
1153   }
1154   if (Tok == "DEFINED") {
1155     StringRef Name = readParenLiteral();
1156     return [=] { return Symtab->find(Name) ? 1 : 0; };
1157   }
1158   if (Tok == "LENGTH") {
1159     StringRef Name = readParenLiteral();
1160     if (Script->MemoryRegions.count(Name) == 0) {
1161       setError("memory region not defined: " + Name);
1162       return [] { return 0; };
1163     }
1164     return [=] { return Script->MemoryRegions[Name]->Length; };
1165   }
1166   if (Tok == "LOADADDR") {
1167     StringRef Name = readParenLiteral();
1168     OutputSection *Cmd = Script->getOrCreateOutputSection(Name);
1169     return [=] {
1170       checkIfExists(Cmd, Location);
1171       return Cmd->getLMA();
1172     };
1173   }
1174   if (Tok == "MAX" || Tok == "MIN") {
1175     expect("(");
1176     Expr A = readExpr();
1177     expect(",");
1178     Expr B = readExpr();
1179     expect(")");
1180     if (Tok == "MIN")
1181       return [=] { return std::min(A().getValue(), B().getValue()); };
1182     return [=] { return std::max(A().getValue(), B().getValue()); };
1183   }
1184   if (Tok == "ORIGIN") {
1185     StringRef Name = readParenLiteral();
1186     if (Script->MemoryRegions.count(Name) == 0) {
1187       setError("memory region not defined: " + Name);
1188       return [] { return 0; };
1189     }
1190     return [=] { return Script->MemoryRegions[Name]->Origin; };
1191   }
1192   if (Tok == "SEGMENT_START") {
1193     expect("(");
1194     skip();
1195     expect(",");
1196     Expr E = readExpr();
1197     expect(")");
1198     return [=] { return E(); };
1199   }
1200   if (Tok == "SIZEOF") {
1201     StringRef Name = readParenLiteral();
1202     OutputSection *Cmd = Script->getOrCreateOutputSection(Name);
1203     // Linker script does not create an output section if its content is empty.
1204     // We want to allow SIZEOF(.foo) where .foo is a section which happened to
1205     // be empty.
1206     return [=] { return Cmd->Size; };
1207   }
1208   if (Tok == "SIZEOF_HEADERS")
1209     return [=] { return elf::getHeaderSize(); };
1210
1211   // Tok is the dot.
1212   if (Tok == ".")
1213     return [=] { return Script->getSymbolValue(Tok, Location); };
1214
1215   // Tok is a literal number.
1216   if (Optional<uint64_t> Val = parseInt(Tok))
1217     return [=] { return *Val; };
1218
1219   // Tok is a symbol name.
1220   if (!isValidCIdentifier(Tok))
1221     setError("malformed number: " + Tok);
1222   Script->ReferencedSymbols.push_back(Tok);
1223   return [=] { return Script->getSymbolValue(Tok, Location); };
1224 }
1225
1226 Expr ScriptParser::readTernary(Expr Cond) {
1227   Expr L = readExpr();
1228   expect(":");
1229   Expr R = readExpr();
1230   return [=] { return Cond().getValue() ? L() : R(); };
1231 }
1232
1233 Expr ScriptParser::readParenExpr() {
1234   expect("(");
1235   Expr E = readExpr();
1236   expect(")");
1237   return E;
1238 }
1239
1240 std::vector<StringRef> ScriptParser::readOutputSectionPhdrs() {
1241   std::vector<StringRef> Phdrs;
1242   while (!errorCount() && peek().startswith(":")) {
1243     StringRef Tok = next();
1244     Phdrs.push_back((Tok.size() == 1) ? next() : Tok.substr(1));
1245   }
1246   return Phdrs;
1247 }
1248
1249 // Read a program header type name. The next token must be a
1250 // name of a program header type or a constant (e.g. "0x3").
1251 unsigned ScriptParser::readPhdrType() {
1252   StringRef Tok = next();
1253   if (Optional<uint64_t> Val = parseInt(Tok))
1254     return *Val;
1255
1256   unsigned Ret = StringSwitch<unsigned>(Tok)
1257                      .Case("PT_NULL", PT_NULL)
1258                      .Case("PT_LOAD", PT_LOAD)
1259                      .Case("PT_DYNAMIC", PT_DYNAMIC)
1260                      .Case("PT_INTERP", PT_INTERP)
1261                      .Case("PT_NOTE", PT_NOTE)
1262                      .Case("PT_SHLIB", PT_SHLIB)
1263                      .Case("PT_PHDR", PT_PHDR)
1264                      .Case("PT_TLS", PT_TLS)
1265                      .Case("PT_GNU_EH_FRAME", PT_GNU_EH_FRAME)
1266                      .Case("PT_GNU_STACK", PT_GNU_STACK)
1267                      .Case("PT_GNU_RELRO", PT_GNU_RELRO)
1268                      .Case("PT_OPENBSD_RANDOMIZE", PT_OPENBSD_RANDOMIZE)
1269                      .Case("PT_OPENBSD_WXNEEDED", PT_OPENBSD_WXNEEDED)
1270                      .Case("PT_OPENBSD_BOOTDATA", PT_OPENBSD_BOOTDATA)
1271                      .Default(-1);
1272
1273   if (Ret == (unsigned)-1) {
1274     setError("invalid program header type: " + Tok);
1275     return PT_NULL;
1276   }
1277   return Ret;
1278 }
1279
1280 // Reads an anonymous version declaration.
1281 void ScriptParser::readAnonymousDeclaration() {
1282   std::vector<SymbolVersion> Locals;
1283   std::vector<SymbolVersion> Globals;
1284   std::tie(Locals, Globals) = readSymbols();
1285
1286   for (SymbolVersion V : Locals) {
1287     if (V.Name == "*")
1288       Config->DefaultSymbolVersion = VER_NDX_LOCAL;
1289     else
1290       Config->VersionScriptLocals.push_back(V);
1291   }
1292
1293   for (SymbolVersion V : Globals)
1294     Config->VersionScriptGlobals.push_back(V);
1295
1296   expect(";");
1297 }
1298
1299 // Reads a non-anonymous version definition,
1300 // e.g. "VerStr { global: foo; bar; local: *; };".
1301 void ScriptParser::readVersionDeclaration(StringRef VerStr) {
1302   // Read a symbol list.
1303   std::vector<SymbolVersion> Locals;
1304   std::vector<SymbolVersion> Globals;
1305   std::tie(Locals, Globals) = readSymbols();
1306
1307   for (SymbolVersion V : Locals) {
1308     if (V.Name == "*")
1309       Config->DefaultSymbolVersion = VER_NDX_LOCAL;
1310     else
1311       Config->VersionScriptLocals.push_back(V);
1312   }
1313
1314   // Create a new version definition and add that to the global symbols.
1315   VersionDefinition Ver;
1316   Ver.Name = VerStr;
1317   Ver.Globals = Globals;
1318
1319   // User-defined version number starts from 2 because 0 and 1 are
1320   // reserved for VER_NDX_LOCAL and VER_NDX_GLOBAL, respectively.
1321   Ver.Id = Config->VersionDefinitions.size() + 2;
1322   Config->VersionDefinitions.push_back(Ver);
1323
1324   // Each version may have a parent version. For example, "Ver2"
1325   // defined as "Ver2 { global: foo; local: *; } Ver1;" has "Ver1"
1326   // as a parent. This version hierarchy is, probably against your
1327   // instinct, purely for hint; the runtime doesn't care about it
1328   // at all. In LLD, we simply ignore it.
1329   if (peek() != ";")
1330     skip();
1331   expect(";");
1332 }
1333
1334 static bool hasWildcard(StringRef S) {
1335   return S.find_first_of("?*[") != StringRef::npos;
1336 }
1337
1338 // Reads a list of symbols, e.g. "{ global: foo; bar; local: *; };".
1339 std::pair<std::vector<SymbolVersion>, std::vector<SymbolVersion>>
1340 ScriptParser::readSymbols() {
1341   std::vector<SymbolVersion> Locals;
1342   std::vector<SymbolVersion> Globals;
1343   std::vector<SymbolVersion> *V = &Globals;
1344
1345   while (!errorCount()) {
1346     if (consume("}"))
1347       break;
1348     if (consumeLabel("local")) {
1349       V = &Locals;
1350       continue;
1351     }
1352     if (consumeLabel("global")) {
1353       V = &Globals;
1354       continue;
1355     }
1356
1357     if (consume("extern")) {
1358       std::vector<SymbolVersion> Ext = readVersionExtern();
1359       V->insert(V->end(), Ext.begin(), Ext.end());
1360     } else {
1361       StringRef Tok = next();
1362       V->push_back({unquote(Tok), false, hasWildcard(Tok)});
1363     }
1364     expect(";");
1365   }
1366   return {Locals, Globals};
1367 }
1368
1369 // Reads an "extern C++" directive, e.g.,
1370 // "extern "C++" { ns::*; "f(int, double)"; };"
1371 //
1372 // The last semicolon is optional. E.g. this is OK:
1373 // "extern "C++" { ns::*; "f(int, double)" };"
1374 std::vector<SymbolVersion> ScriptParser::readVersionExtern() {
1375   StringRef Tok = next();
1376   bool IsCXX = Tok == "\"C++\"";
1377   if (!IsCXX && Tok != "\"C\"")
1378     setError("Unknown language");
1379   expect("{");
1380
1381   std::vector<SymbolVersion> Ret;
1382   while (!errorCount() && peek() != "}") {
1383     StringRef Tok = next();
1384     bool HasWildcard = !Tok.startswith("\"") && hasWildcard(Tok);
1385     Ret.push_back({unquote(Tok), IsCXX, HasWildcard});
1386     if (consume("}"))
1387       return Ret;
1388     expect(";");
1389   }
1390
1391   expect("}");
1392   return Ret;
1393 }
1394
1395 uint64_t ScriptParser::readMemoryAssignment(StringRef S1, StringRef S2,
1396                                             StringRef S3) {
1397   if (!consume(S1) && !consume(S2) && !consume(S3)) {
1398     setError("expected one of: " + S1 + ", " + S2 + ", or " + S3);
1399     return 0;
1400   }
1401   expect("=");
1402   return readExpr()().getValue();
1403 }
1404
1405 // Parse the MEMORY command as specified in:
1406 // https://sourceware.org/binutils/docs/ld/MEMORY.html
1407 //
1408 // MEMORY { name [(attr)] : ORIGIN = origin, LENGTH = len ... }
1409 void ScriptParser::readMemory() {
1410   expect("{");
1411   while (!errorCount() && !consume("}")) {
1412     StringRef Tok = next();
1413     if (Tok == "INCLUDE") {
1414       readInclude();
1415       continue;
1416     }
1417
1418     uint32_t Flags = 0;
1419     uint32_t NegFlags = 0;
1420     if (consume("(")) {
1421       std::tie(Flags, NegFlags) = readMemoryAttributes();
1422       expect(")");
1423     }
1424     expect(":");
1425
1426     uint64_t Origin = readMemoryAssignment("ORIGIN", "org", "o");
1427     expect(",");
1428     uint64_t Length = readMemoryAssignment("LENGTH", "len", "l");
1429
1430     // Add the memory region to the region map.
1431     MemoryRegion *MR = make<MemoryRegion>(Tok, Origin, Length, Flags, NegFlags);
1432     if (!Script->MemoryRegions.insert({Tok, MR}).second)
1433       setError("region '" + Tok + "' already defined");
1434   }
1435 }
1436
1437 // This function parses the attributes used to match against section
1438 // flags when placing output sections in a memory region. These flags
1439 // are only used when an explicit memory region name is not used.
1440 std::pair<uint32_t, uint32_t> ScriptParser::readMemoryAttributes() {
1441   uint32_t Flags = 0;
1442   uint32_t NegFlags = 0;
1443   bool Invert = false;
1444
1445   for (char C : next().lower()) {
1446     uint32_t Flag = 0;
1447     if (C == '!')
1448       Invert = !Invert;
1449     else if (C == 'w')
1450       Flag = SHF_WRITE;
1451     else if (C == 'x')
1452       Flag = SHF_EXECINSTR;
1453     else if (C == 'a')
1454       Flag = SHF_ALLOC;
1455     else if (C != 'r')
1456       setError("invalid memory region attribute");
1457
1458     if (Invert)
1459       NegFlags |= Flag;
1460     else
1461       Flags |= Flag;
1462   }
1463   return {Flags, NegFlags};
1464 }
1465
1466 void elf::readLinkerScript(MemoryBufferRef MB) {
1467   ScriptParser(MB).readLinkerScript();
1468 }
1469
1470 void elf::readVersionScript(MemoryBufferRef MB) {
1471   ScriptParser(MB).readVersionScript();
1472 }
1473
1474 void elf::readDynamicList(MemoryBufferRef MB) {
1475   ScriptParser(MB).readDynamicList();
1476 }
1477
1478 void elf::readDefsym(StringRef Name, MemoryBufferRef MB) {
1479   ScriptParser(MB).readDefsym(Name);
1480 }