1 //===- ScriptParser.cpp ---------------------------------------------------===//
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file contains a recursive-descendent parser for linker scripts.
11 // Parsed results are stored to Config and Script global objects.
13 //===----------------------------------------------------------------------===//
15 #include "ScriptParser.h"
18 #include "InputSection.h"
19 #include "LinkerScript.h"
20 #include "OutputSections.h"
21 #include "ScriptLexer.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"
39 using namespace llvm::ELF;
40 using namespace llvm::support::endian;
42 using namespace lld::elf;
44 static bool isUnderSysroot(StringRef Path);
47 class ScriptParser final : ScriptLexer {
49 ScriptParser(MemoryBufferRef MB)
51 IsUnderSysroot(isUnderSysroot(MB.getBufferIdentifier())) {}
53 void readLinkerScript();
54 void readVersionScript();
55 void readDynamicList();
56 void readDefsym(StringRef Name);
59 void addFile(StringRef Path);
69 void readOutputArch();
70 void readOutputFormat();
72 void readRegionAlias();
76 void readVersionScriptCommand();
78 SymbolAssignment *readSymbolAssignment(StringRef Name);
79 ByteCommand *readByteCommand(StringRef Tok);
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);
100 uint64_t readMemoryAssignment(StringRef, StringRef, StringRef);
101 std::pair<uint32_t, uint32_t> readMemoryAttributes();
103 Expr combine(StringRef Op, Expr L, Expr R);
105 Expr readExpr1(Expr Lhs, int MinPrec);
106 StringRef readParenLiteral();
108 Expr readTernary(Expr Cond);
109 Expr readParenExpr();
111 // For parsing version script.
112 std::vector<SymbolVersion> readVersionExtern();
113 void readAnonymousDeclaration();
114 void readVersionDeclaration(StringRef VerStr);
116 std::pair<std::vector<SymbolVersion>, std::vector<SymbolVersion>>
119 // True if a script being read is in a subdirectory specified by -sysroot.
122 // A set to detect an INCLUDE() cycle.
127 static StringRef unquote(StringRef S) {
128 if (S.startswith("\""))
129 return S.substr(1, S.size() - 2);
133 static bool isUnderSysroot(StringRef Path) {
134 if (Config->Sysroot == "")
136 for (; !Path.empty(); Path = sys::path::parent_path(Path))
137 if (sys::fs::equivalent(Config->Sysroot, Path))
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()))
148 error(A.Loc + ": at least one side of the expression must be absolute");
151 static ExprValue add(ExprValue A, ExprValue B) {
153 return {A.Sec, A.ForceAbsolute, A.getSectionOffset() + B.getValue(), A.Loc};
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};
163 static ExprValue bitAnd(ExprValue A, ExprValue B) {
165 return {A.Sec, A.ForceAbsolute,
166 (A.getValue() & B.getValue()) - A.getSecAddr(), A.Loc};
169 static ExprValue bitOr(ExprValue A, ExprValue B) {
171 return {A.Sec, A.ForceAbsolute,
172 (A.getValue() | B.getValue()) - A.getSecAddr(), A.Loc};
175 void ScriptParser::readDynamicList() {
176 Config->HasDynamicList = true;
178 std::vector<SymbolVersion> Locals;
179 std::vector<SymbolVersion> Globals;
180 std::tie(Locals, Globals) = readSymbols();
184 setError("EOF expected, but got " + next());
187 if (!Locals.empty()) {
188 setError("\"local:\" scope not supported in --dynamic-list");
192 for (SymbolVersion V : Globals)
193 Config->DynamicList.push_back(V);
196 void ScriptParser::readVersionScript() {
197 readVersionScriptCommand();
199 setError("EOF expected, but got " + next());
202 void ScriptParser::readVersionScriptCommand() {
204 readAnonymousDeclaration();
208 while (!atEOF() && !errorCount() && peek() != "}") {
209 StringRef VerStr = next();
211 setError("anonymous version definition is used in "
212 "combination with other version definitions");
216 readVersionDeclaration(VerStr);
220 void ScriptParser::readVersion() {
222 readVersionScriptCommand();
226 void ScriptParser::readLinkerScript() {
228 StringRef Tok = next();
232 if (Tok == "ENTRY") {
234 } else if (Tok == "EXTERN") {
236 } else if (Tok == "GROUP") {
238 } else if (Tok == "INCLUDE") {
240 } else if (Tok == "INPUT") {
242 } else if (Tok == "MEMORY") {
244 } else if (Tok == "OUTPUT") {
246 } else if (Tok == "OUTPUT_ARCH") {
248 } else if (Tok == "OUTPUT_FORMAT") {
250 } else if (Tok == "PHDRS") {
252 } else if (Tok == "REGION_ALIAS") {
254 } else if (Tok == "SEARCH_DIR") {
256 } else if (Tok == "SECTIONS") {
258 } else if (Tok == "VERSION") {
260 } else if (SymbolAssignment *Cmd = readAssignment(Tok)) {
261 Script->SectionCommands.push_back(Cmd);
263 setError("unknown directive: " + Tok);
268 void ScriptParser::readDefsym(StringRef Name) {
271 setError("EOF expected, but got " + next());
272 SymbolAssignment *Cmd = make<SymbolAssignment>(Name, E, getCurrentLocation());
273 Script->SectionCommands.push_back(Cmd);
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);
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);
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);
299 if (Optional<std::string> Path = findFromSearchPaths(S))
300 Driver->addFile(Saver.save(*Path), /*WithLOption=*/true);
302 setError("unable to find " + S);
306 void ScriptParser::readAsNeeded() {
308 bool Orig = Config->AsNeeded;
309 Config->AsNeeded = true;
310 while (!errorCount() && !consume(")"))
311 addFile(unquote(next()));
312 Config->AsNeeded = Orig;
315 void ScriptParser::readEntry() {
316 // -e <symbol> takes predecence over ENTRY(<symbol>).
318 StringRef Tok = next();
319 if (Config->Entry.empty())
324 void ScriptParser::readExtern() {
326 while (!errorCount() && !consume(")"))
327 Config->Undefined.push_back(next());
330 void ScriptParser::readGroup() {
331 bool Orig = InputFile::IsInGroup;
332 InputFile::IsInGroup = true;
334 InputFile::IsInGroup = Orig;
336 ++InputFile::NextGroupId;
339 void ScriptParser::readInclude() {
340 StringRef Tok = unquote(next());
342 if (!Seen.insert(Tok).second) {
343 setError("there is a cycle in linker script INCLUDEs");
347 if (Optional<std::string> Path = searchScript(Tok)) {
348 if (Optional<MemoryBufferRef> MB = readFile(*Path))
352 setError("cannot find linker script " + Tok);
355 void ScriptParser::readInput() {
357 while (!errorCount() && !consume(")")) {
358 if (consume("AS_NEEDED"))
361 addFile(unquote(next()));
365 void ScriptParser::readOutput() {
366 // -o <file> takes predecence over OUTPUT(<file>).
368 StringRef Tok = next();
369 if (Config->OutputFile.empty())
370 Config->OutputFile = unquote(Tok);
374 void ScriptParser::readOutputArch() {
375 // OUTPUT_ARCH is ignored for now.
377 while (!errorCount() && !consume(")"))
381 void ScriptParser::readOutputFormat() {
382 // Error checking only for now.
394 void ScriptParser::readPhdrs() {
397 while (!errorCount() && !consume("}")) {
400 Cmd.Type = readPhdrType();
402 while (!errorCount() && !consume(";")) {
403 if (consume("FILEHDR"))
404 Cmd.HasFilehdr = true;
405 else if (consume("PHDRS"))
407 else if (consume("AT"))
408 Cmd.LMAExpr = readParenExpr();
409 else if (consume("FLAGS"))
410 Cmd.Flags = readParenExpr()().getValue();
412 setError("unexpected header attribute: " + next());
415 Script->PhdrsCommands.push_back(Cmd);
419 void ScriptParser::readRegionAlias() {
421 StringRef Alias = unquote(next());
423 StringRef Name = next();
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]});
433 void ScriptParser::readSearchDir() {
435 StringRef Tok = next();
436 if (!Config->Nostdlib)
437 Config->SearchPaths.push_back(unquote(Tok));
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();
452 Expr LMAExpr = readParenExpr();
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;
463 OS->LMAExpr = [=] { return Prev->getLMA() + Prev->Size; };
465 OS->LMAExpr = LMAExpr;
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.
476 for (BaseCommand *Cmd : V)
477 Max = std::max(Max, cast<OutputSection>(Cmd)->Size);
478 return AddrExpr().getValue() + Max;
480 V.push_back(make<SymbolAssignment>(".", MoveDot, getCurrentLocation()));
484 void ScriptParser::readSections() {
485 Script->HasSectionsCommand = true;
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;
493 std::vector<BaseCommand *> V;
494 while (!errorCount() && !consume("}")) {
495 StringRef Tok = next();
496 if (Tok == "OVERLAY") {
497 for (BaseCommand *Cmd : readOverlay())
500 } else if (Tok == "INCLUDE") {
505 if (BaseCommand *Cmd = readAssignment(Tok))
508 V.push_back(readOutputSectionDescription(Tok));
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()];
518 setError("expected AFTER/BEFORE, but got '" + next() + "'");
520 Dest->insert(Dest->end(), V.begin(), V.end());
524 Script->SectionCommands.insert(Script->SectionCommands.end(), V.begin(),
528 static int precedence(StringRef Op) {
529 return StringSwitch<int>(Op)
530 .Cases("*", "/", "%", 8)
532 .Cases("<<", ">>", 6)
533 .Cases("<", "<=", ">", ">=", "==", "!=", 5)
541 StringMatcher ScriptParser::readFilePatterns() {
542 std::vector<StringRef> V;
543 while (!errorCount() && !consume(")"))
545 return StringMatcher(V);
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;
560 // Reads SECTIONS command contents in the following form:
562 // <contents> ::= <elem>*
563 // <elem> ::= <exclude>? <glob-pattern>
564 // <exclude> ::= "EXCLUDE_FILE" "(" <glob-pattern>+ ")"
568 // *(.foo EXCLUDE_FILE (a.o) .bar EXCLUDE_FILE (b.o) .baz)
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")) {
579 ExcludeFilePat = readFilePatterns();
582 std::vector<StringRef> V;
583 while (!errorCount() && peek() != ")" && peek() != "EXCLUDE_FILE")
587 Ret.push_back({std::move(ExcludeFilePat), StringMatcher(V)});
589 setError("section pattern is expected");
594 // Reads contents of "SECTIONS" directive. That directive contains a
595 // list of glob patterns for input sections. The grammar is as follows.
597 // <patterns> ::= <section-list>
598 // | <sort> "(" <section-list> ")"
599 // | <sort> "(" <sort> "(" <section-list> ")" ")"
601 // <sort> ::= "SORT" | "SORT_BY_NAME" | "SORT_BY_ALIGNMENT"
602 // | "SORT_BY_INIT_PRIORITY" | "SORT_NONE"
604 // <section-list> is parsed by readInputSectionsList().
605 InputSectionDescription *
606 ScriptParser::readInputSectionRules(StringRef FilePattern) {
607 auto *Cmd = make<InputSectionDescription>(FilePattern);
610 while (!errorCount() && !consume(")")) {
611 SortSectionPolicy Outer = readSortKind();
612 SortSectionPolicy Inner = SortSectionPolicy::Default;
613 std::vector<SectionPattern> V;
614 if (Outer != SortSectionPolicy::Default) {
616 Inner = readSortKind();
617 if (Inner != SortSectionPolicy::Default) {
619 V = readInputSectionsList();
622 V = readInputSectionsList();
626 V = readInputSectionsList();
629 for (SectionPattern &Pat : V) {
630 Pat.SortInner = Inner;
631 Pat.SortOuter = Outer;
634 std::move(V.begin(), V.end(), std::back_inserter(Cmd->SectionPatterns));
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
645 StringRef FilePattern = next();
646 InputSectionDescription *Cmd = readInputSectionRules(FilePattern);
648 Script->KeptSections.push_back(Cmd);
651 return readInputSectionRules(Tok);
654 void ScriptParser::readSort() {
656 expect("CONSTRUCTORS");
660 Expr ScriptParser::readAssert() {
664 StringRef Msg = unquote(next());
670 return Script->getDot();
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() {
680 uint32_t V = parseFill(next());
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)".
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
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) {
698 if (consume("NOLOAD")) {
703 if (consume("COPY") || consume("INFO") || consume("OVERLAY")) {
705 Cmd->NonAlloc = true;
708 Cmd->AddrExpr = readExpr();
711 Cmd->AddrExpr = readExpr();
721 static Expr checkAlignment(Expr E, std::string &Loc) {
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.
732 OutputSection *ScriptParser::readOverlaySectionDescription() {
734 Script->createOutputSection(next(), getCurrentLocation());
735 Cmd->InOverlay = true;
737 while (!errorCount() && !consume("}"))
738 Cmd->SectionCommands.push_back(readInputSectionRules(next()));
739 Cmd->Phdrs = readOutputSectionPhdrs();
743 OutputSection *ScriptParser::readOutputSectionDescription(StringRef OutSec) {
745 Script->createOutputSection(OutSec, getCurrentLocation());
747 size_t SymbolsReferenced = Script->ReferencedSymbols.size();
750 readSectionAddressType(Cmd);
753 std::string Location = getCurrentLocation();
755 Cmd->LMAExpr = readParenExpr();
756 if (consume("ALIGN"))
757 Cmd->AlignExpr = checkAlignment(readParenExpr(), Location);
758 if (consume("SUBALIGN"))
759 Cmd->SubalignExpr = checkAlignment(readParenExpr(), Location);
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;
768 while (!errorCount() && !consume("}")) {
769 StringRef Tok = next();
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") {
784 } else if (Tok == "INCLUDE") {
786 } else if (peek() == "(") {
787 Cmd->SectionCommands.push_back(readInputSectionDescription(Tok));
789 setError("unknown command " + Tok);
794 Cmd->MemoryRegionName = next();
798 Cmd->LMARegionName = next();
801 if (Cmd->LMAExpr && !Cmd->LMARegionName.empty())
802 error("section can't have both LMA and a load region");
804 Cmd->Phdrs = readOutputSectionPhdrs();
807 Cmd->Filler = parseFill(next());
808 else if (peek().startswith("="))
809 Cmd->Filler = parseFill(next().drop_front());
811 // Consume optional comma following output section command.
814 if (Script->ReferencedSymbols.size() > SymbolsReferenced)
815 Cmd->ExpressionsUseSymbols = true;
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
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) {
828 if (!to_integer(Tok, V))
829 setError("invalid filler expression: " + Tok);
836 SymbolAssignment *ScriptParser::readProvideHidden(bool Provide, bool Hidden) {
838 SymbolAssignment *Cmd = readSymbolAssignment(next());
839 Cmd->Provide = Provide;
840 Cmd->Hidden = Hidden;
845 SymbolAssignment *ScriptParser::readAssignment(StringRef Tok) {
846 // Assert expression returns Dot, so this is equal to ".=."
848 return make<SymbolAssignment>(".", readAssert(), getCurrentLocation());
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);
864 llvm::join(Tokens.begin() + OldPos, Tokens.begin() + Pos, " ");
870 SymbolAssignment *ScriptParser::readSymbolAssignment(StringRef Name) {
871 StringRef Op = next();
872 assert(Op == "=" || Op == "+=");
875 std::string Loc = getCurrentLocation();
876 E = [=] { return add(Script->getSymbolValue(Name, Loc), E()); };
878 return make<SymbolAssignment>(Name, E, getCurrentLocation());
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.
888 Expr E = readExpr1(readPrimary(), 0);
893 Expr ScriptParser::combine(StringRef Op, Expr L, Expr R) {
895 return [=] { return add(L(), R()); };
897 return [=] { return sub(L(), R()); };
899 return [=] { return L().getValue() * R().getValue(); };
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");
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");
919 return [=] { return L().getValue() << R().getValue(); };
921 return [=] { return L().getValue() >> R().getValue(); };
923 return [=] { return L().getValue() < R().getValue(); };
925 return [=] { return L().getValue() > R().getValue(); };
927 return [=] { return L().getValue() >= R().getValue(); };
929 return [=] { return L().getValue() <= R().getValue(); };
931 return [=] { return L().getValue() == R().getValue(); };
933 return [=] { return L().getValue() != R().getValue(); };
935 return [=] { return L().getValue() || R().getValue(); };
937 return [=] { return L().getValue() && R().getValue(); };
939 return [=] { return bitAnd(L(), R()); };
941 return [=] { return bitOr(L(), R()); };
942 llvm_unreachable("invalid operator");
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.
951 return readTernary(Lhs);
952 StringRef Op1 = peek();
953 if (precedence(Op1) < MinPrec)
956 Expr Rhs = readPrimary();
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.
963 StringRef Op2 = peek();
964 if (precedence(Op2) <= precedence(Op1))
966 Rhs = readExpr1(Rhs, precedence(Op2));
969 Lhs = combine(Op1, Lhs, Rhs);
974 Expr ScriptParser::getPageSize() {
975 std::string Location = getCurrentLocation();
976 return [=]() -> uint64_t {
978 return Target->PageSize;
979 error(Location + ": unable to calculate page size");
980 return 4096; // Return a dummy value.
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; };
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) {
1000 if (Tok.startswith_lower("0x")) {
1001 if (!to_integer(Tok.substr(2), Val, 16))
1005 if (Tok.endswith_lower("H")) {
1006 if (!to_integer(Tok.drop_back(), Val, 16))
1012 if (Tok.endswith_lower("K")) {
1013 if (!to_integer(Tok.drop_back(), Val, 10))
1017 if (Tok.endswith_lower("M")) {
1018 if (!to_integer(Tok.drop_back(), Val, 10))
1020 return Val * 1024 * 1024;
1022 if (!to_integer(Tok, Val, 10))
1027 ByteCommand *ScriptParser::readByteCommand(StringRef Tok) {
1028 int Size = StringSwitch<int>(Tok)
1037 size_t OldPos = Pos;
1038 Expr E = readParenExpr();
1039 std::string CommandString =
1041 llvm::join(Tokens.begin() + OldPos, Tokens.begin() + Pos, " ");
1042 return make<ByteCommand>(E, Size, CommandString);
1045 StringRef ScriptParser::readParenLiteral() {
1049 StringRef Tok = next();
1055 static void checkIfExists(OutputSection *Cmd, StringRef Location) {
1056 if (Cmd->Location.empty() && Script->ErrorOnMissingSection)
1057 error(Location + ": undefined section " + Cmd->Name);
1060 Expr ScriptParser::readPrimary() {
1062 return readParenExpr();
1065 Expr E = readPrimary();
1066 return [=] { return ~E().getValue(); };
1069 Expr E = readPrimary();
1070 return [=] { return !E().getValue(); };
1073 Expr E = readPrimary();
1074 return [=] { return -E().getValue(); };
1077 StringRef Tok = next();
1078 std::string Location = getCurrentLocation();
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();
1085 ExprValue I = Inner();
1086 I.ForceAbsolute = true;
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};
1098 if (Tok == "ALIGN") {
1100 Expr E = readExpr();
1102 E = checkAlignment(E, Location);
1103 return [=] { return alignTo(Script->getDot(), E().getValue()); };
1106 Expr E2 = checkAlignment(readExpr(), Location);
1110 V.Alignment = E2().getValue();
1114 if (Tok == "ALIGNOF") {
1115 StringRef Name = readParenLiteral();
1116 OutputSection *Cmd = Script->getOrCreateOutputSection(Name);
1118 checkIfExists(Cmd, Location);
1119 return Cmd->Alignment;
1122 if (Tok == "ASSERT")
1123 return readAssert();
1124 if (Tok == "CONSTANT")
1125 return readConstant();
1126 if (Tok == "DATA_SEGMENT_ALIGN") {
1128 Expr E = readExpr();
1133 return alignTo(Script->getDot(), std::max((uint64_t)1, E().getValue()));
1136 if (Tok == "DATA_SEGMENT_END") {
1140 return [] { return Script->getDot(); };
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.
1151 Expr E = getPageSize();
1152 return [=] { return alignTo(Script->getDot(), E().getValue()); };
1154 if (Tok == "DEFINED") {
1155 StringRef Name = readParenLiteral();
1156 return [=] { return Symtab->find(Name) ? 1 : 0; };
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; };
1164 return [=] { return Script->MemoryRegions[Name]->Length; };
1166 if (Tok == "LOADADDR") {
1167 StringRef Name = readParenLiteral();
1168 OutputSection *Cmd = Script->getOrCreateOutputSection(Name);
1170 checkIfExists(Cmd, Location);
1171 return Cmd->getLMA();
1174 if (Tok == "MAX" || Tok == "MIN") {
1176 Expr A = readExpr();
1178 Expr B = readExpr();
1181 return [=] { return std::min(A().getValue(), B().getValue()); };
1182 return [=] { return std::max(A().getValue(), B().getValue()); };
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; };
1190 return [=] { return Script->MemoryRegions[Name]->Origin; };
1192 if (Tok == "SEGMENT_START") {
1196 Expr E = readExpr();
1198 return [=] { return E(); };
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
1206 return [=] { return Cmd->Size; };
1208 if (Tok == "SIZEOF_HEADERS")
1209 return [=] { return elf::getHeaderSize(); };
1213 return [=] { return Script->getSymbolValue(Tok, Location); };
1215 // Tok is a literal number.
1216 if (Optional<uint64_t> Val = parseInt(Tok))
1217 return [=] { return *Val; };
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); };
1226 Expr ScriptParser::readTernary(Expr Cond) {
1227 Expr L = readExpr();
1229 Expr R = readExpr();
1230 return [=] { return Cond().getValue() ? L() : R(); };
1233 Expr ScriptParser::readParenExpr() {
1235 Expr E = readExpr();
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));
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))
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)
1273 if (Ret == (unsigned)-1) {
1274 setError("invalid program header type: " + Tok);
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();
1286 for (SymbolVersion V : Locals) {
1288 Config->DefaultSymbolVersion = VER_NDX_LOCAL;
1290 Config->VersionScriptLocals.push_back(V);
1293 for (SymbolVersion V : Globals)
1294 Config->VersionScriptGlobals.push_back(V);
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();
1307 for (SymbolVersion V : Locals) {
1309 Config->DefaultSymbolVersion = VER_NDX_LOCAL;
1311 Config->VersionScriptLocals.push_back(V);
1314 // Create a new version definition and add that to the global symbols.
1315 VersionDefinition Ver;
1317 Ver.Globals = Globals;
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);
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.
1334 static bool hasWildcard(StringRef S) {
1335 return S.find_first_of("?*[") != StringRef::npos;
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;
1345 while (!errorCount()) {
1348 if (consumeLabel("local")) {
1352 if (consumeLabel("global")) {
1357 if (consume("extern")) {
1358 std::vector<SymbolVersion> Ext = readVersionExtern();
1359 V->insert(V->end(), Ext.begin(), Ext.end());
1361 StringRef Tok = next();
1362 V->push_back({unquote(Tok), false, hasWildcard(Tok)});
1366 return {Locals, Globals};
1369 // Reads an "extern C++" directive, e.g.,
1370 // "extern "C++" { ns::*; "f(int, double)"; };"
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");
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});
1395 uint64_t ScriptParser::readMemoryAssignment(StringRef S1, StringRef S2,
1397 if (!consume(S1) && !consume(S2) && !consume(S3)) {
1398 setError("expected one of: " + S1 + ", " + S2 + ", or " + S3);
1402 return readExpr()().getValue();
1405 // Parse the MEMORY command as specified in:
1406 // https://sourceware.org/binutils/docs/ld/MEMORY.html
1408 // MEMORY { name [(attr)] : ORIGIN = origin, LENGTH = len ... }
1409 void ScriptParser::readMemory() {
1411 while (!errorCount() && !consume("}")) {
1412 StringRef Tok = next();
1413 if (Tok == "INCLUDE") {
1419 uint32_t NegFlags = 0;
1421 std::tie(Flags, NegFlags) = readMemoryAttributes();
1426 uint64_t Origin = readMemoryAssignment("ORIGIN", "org", "o");
1428 uint64_t Length = readMemoryAssignment("LENGTH", "len", "l");
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");
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() {
1442 uint32_t NegFlags = 0;
1443 bool Invert = false;
1445 for (char C : next().lower()) {
1452 Flag = SHF_EXECINSTR;
1456 setError("invalid memory region attribute");
1463 return {Flags, NegFlags};
1466 void elf::readLinkerScript(MemoryBufferRef MB) {
1467 ScriptParser(MB).readLinkerScript();
1470 void elf::readVersionScript(MemoryBufferRef MB) {
1471 ScriptParser(MB).readVersionScript();
1474 void elf::readDynamicList(MemoryBufferRef MB) {
1475 ScriptParser(MB).readDynamicList();
1478 void elf::readDefsym(StringRef Name, MemoryBufferRef MB) {
1479 ScriptParser(MB).readDefsym(Name);