1 //===- ScriptParser.cpp ---------------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file contains a recursive-descendent parser for linker scripts.
10 // Parsed results are stored to Config and Script global objects.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "ScriptParser.h"
15 #include "Config.h"
16 #include "Driver.h"
17 #include "InputFiles.h"
18 #include "LinkerScript.h"
19 #include "OutputSections.h"
20 #include "ScriptLexer.h"
21 #include "SymbolTable.h"
22 #include "Symbols.h"
23 #include "Target.h"
24 #include "lld/Common/CommonLinkerContext.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/MathExtras.h"
34 #include "llvm/Support/Path.h"
35 #include "llvm/Support/SaveAndRestore.h"
36 #include "llvm/Support/TimeProfiler.h"
37 #include <cassert>
38 #include <limits>
39 #include <vector>
40 
41 using namespace llvm;
42 using namespace llvm::ELF;
43 using namespace llvm::support::endian;
44 using namespace lld;
45 using namespace lld::elf;
46 
47 namespace {
48 class ScriptParser final : ScriptLexer {
49 public:
ScriptParser(MemoryBufferRef mb)50   ScriptParser(MemoryBufferRef mb) : ScriptLexer(mb) {
51     // Initialize IsUnderSysroot
52     if (config->sysroot == "")
53       return;
54     StringRef path = mb.getBufferIdentifier();
55     for (; !path.empty(); path = sys::path::parent_path(path)) {
56       if (!sys::fs::equivalent(config->sysroot, path))
57         continue;
58       isUnderSysroot = true;
59       return;
60     }
61   }
62 
63   void readLinkerScript();
64   void readVersionScript();
65   void readDynamicList();
66   void readDefsym(StringRef name);
67 
68 private:
69   void addFile(StringRef path);
70 
71   void readAsNeeded();
72   void readEntry();
73   void readExtern();
74   void readGroup();
75   void readInclude();
76   void readInput();
77   void readMemory();
78   void readOutput();
79   void readOutputArch();
80   void readOutputFormat();
81   void readOverwriteSections();
82   void readPhdrs();
83   void readRegionAlias();
84   void readSearchDir();
85   void readSections();
86   void readTarget();
87   void readVersion();
88   void readVersionScriptCommand();
89 
90   SymbolAssignment *readSymbolAssignment(StringRef name);
91   ByteCommand *readByteCommand(StringRef tok);
92   std::array<uint8_t, 4> readFill();
93   bool readSectionDirective(OutputSection *cmd, StringRef tok1, StringRef tok2);
94   void readSectionAddressType(OutputSection *cmd);
95   OutputDesc *readOverlaySectionDescription();
96   OutputDesc *readOutputSectionDescription(StringRef outSec);
97   SmallVector<SectionCommand *, 0> readOverlay();
98   SmallVector<StringRef, 0> readOutputSectionPhdrs();
99   std::pair<uint64_t, uint64_t> readInputSectionFlags();
100   InputSectionDescription *readInputSectionDescription(StringRef tok);
101   StringMatcher readFilePatterns();
102   SmallVector<SectionPattern, 0> readInputSectionsList();
103   InputSectionDescription *readInputSectionRules(StringRef filePattern,
104                                                  uint64_t withFlags,
105                                                  uint64_t withoutFlags);
106   unsigned readPhdrType();
107   SortSectionPolicy peekSortKind();
108   SortSectionPolicy readSortKind();
109   SymbolAssignment *readProvideHidden(bool provide, bool hidden);
110   SymbolAssignment *readAssignment(StringRef tok);
111   void readSort();
112   Expr readAssert();
113   Expr readConstant();
114   Expr getPageSize();
115 
116   Expr readMemoryAssignment(StringRef, StringRef, StringRef);
117   void readMemoryAttributes(uint32_t &flags, uint32_t &invFlags,
118                             uint32_t &negFlags, uint32_t &negInvFlags);
119 
120   Expr combine(StringRef op, Expr l, Expr r);
121   Expr readExpr();
122   Expr readExpr1(Expr lhs, int minPrec);
123   StringRef readParenLiteral();
124   Expr readPrimary();
125   Expr readTernary(Expr cond);
126   Expr readParenExpr();
127 
128   // For parsing version script.
129   SmallVector<SymbolVersion, 0> readVersionExtern();
130   void readAnonymousDeclaration();
131   void readVersionDeclaration(StringRef verStr);
132 
133   std::pair<SmallVector<SymbolVersion, 0>, SmallVector<SymbolVersion, 0>>
134   readSymbols();
135 
136   // True if a script being read is in the --sysroot directory.
137   bool isUnderSysroot = false;
138 
139   // A set to detect an INCLUDE() cycle.
140   StringSet<> seen;
141 };
142 } // namespace
143 
unquote(StringRef s)144 static StringRef unquote(StringRef s) {
145   if (s.starts_with("\""))
146     return s.substr(1, s.size() - 2);
147   return s;
148 }
149 
150 // Some operations only support one non absolute value. Move the
151 // absolute one to the right hand side for convenience.
moveAbsRight(ExprValue & a,ExprValue & b)152 static void moveAbsRight(ExprValue &a, ExprValue &b) {
153   if (a.sec == nullptr || (a.forceAbsolute && !b.isAbsolute()))
154     std::swap(a, b);
155   if (!b.isAbsolute())
156     error(a.loc + ": at least one side of the expression must be absolute");
157 }
158 
add(ExprValue a,ExprValue b)159 static ExprValue add(ExprValue a, ExprValue b) {
160   moveAbsRight(a, b);
161   return {a.sec, a.forceAbsolute, a.getSectionOffset() + b.getValue(), a.loc};
162 }
163 
sub(ExprValue a,ExprValue b)164 static ExprValue sub(ExprValue a, ExprValue b) {
165   // The distance between two symbols in sections is absolute.
166   if (!a.isAbsolute() && !b.isAbsolute())
167     return a.getValue() - b.getValue();
168   return {a.sec, false, a.getSectionOffset() - b.getValue(), a.loc};
169 }
170 
bitAnd(ExprValue a,ExprValue b)171 static ExprValue bitAnd(ExprValue a, ExprValue b) {
172   moveAbsRight(a, b);
173   return {a.sec, a.forceAbsolute,
174           (a.getValue() & b.getValue()) - a.getSecAddr(), a.loc};
175 }
176 
bitXor(ExprValue a,ExprValue b)177 static ExprValue bitXor(ExprValue a, ExprValue b) {
178   moveAbsRight(a, b);
179   return {a.sec, a.forceAbsolute,
180           (a.getValue() ^ b.getValue()) - a.getSecAddr(), a.loc};
181 }
182 
bitOr(ExprValue a,ExprValue b)183 static ExprValue bitOr(ExprValue a, ExprValue b) {
184   moveAbsRight(a, b);
185   return {a.sec, a.forceAbsolute,
186           (a.getValue() | b.getValue()) - a.getSecAddr(), a.loc};
187 }
188 
readDynamicList()189 void ScriptParser::readDynamicList() {
190   expect("{");
191   SmallVector<SymbolVersion, 0> locals;
192   SmallVector<SymbolVersion, 0> globals;
193   std::tie(locals, globals) = readSymbols();
194   expect(";");
195 
196   if (!atEOF()) {
197     setError("EOF expected, but got " + next());
198     return;
199   }
200   if (!locals.empty()) {
201     setError("\"local:\" scope not supported in --dynamic-list");
202     return;
203   }
204 
205   for (SymbolVersion v : globals)
206     config->dynamicList.push_back(v);
207 }
208 
readVersionScript()209 void ScriptParser::readVersionScript() {
210   readVersionScriptCommand();
211   if (!atEOF())
212     setError("EOF expected, but got " + next());
213 }
214 
readVersionScriptCommand()215 void ScriptParser::readVersionScriptCommand() {
216   if (consume("{")) {
217     readAnonymousDeclaration();
218     return;
219   }
220 
221   while (!atEOF() && !errorCount() && peek() != "}") {
222     StringRef verStr = next();
223     if (verStr == "{") {
224       setError("anonymous version definition is used in "
225                "combination with other version definitions");
226       return;
227     }
228     expect("{");
229     readVersionDeclaration(verStr);
230   }
231 }
232 
readVersion()233 void ScriptParser::readVersion() {
234   expect("{");
235   readVersionScriptCommand();
236   expect("}");
237 }
238 
readLinkerScript()239 void ScriptParser::readLinkerScript() {
240   while (!atEOF()) {
241     StringRef tok = next();
242     if (tok == ";")
243       continue;
244 
245     if (tok == "ENTRY") {
246       readEntry();
247     } else if (tok == "EXTERN") {
248       readExtern();
249     } else if (tok == "GROUP") {
250       readGroup();
251     } else if (tok == "INCLUDE") {
252       readInclude();
253     } else if (tok == "INPUT") {
254       readInput();
255     } else if (tok == "MEMORY") {
256       readMemory();
257     } else if (tok == "OUTPUT") {
258       readOutput();
259     } else if (tok == "OUTPUT_ARCH") {
260       readOutputArch();
261     } else if (tok == "OUTPUT_FORMAT") {
262       readOutputFormat();
263     } else if (tok == "OVERWRITE_SECTIONS") {
264       readOverwriteSections();
265     } else if (tok == "PHDRS") {
266       readPhdrs();
267     } else if (tok == "REGION_ALIAS") {
268       readRegionAlias();
269     } else if (tok == "SEARCH_DIR") {
270       readSearchDir();
271     } else if (tok == "SECTIONS") {
272       readSections();
273     } else if (tok == "TARGET") {
274       readTarget();
275     } else if (tok == "VERSION") {
276       readVersion();
277     } else if (SymbolAssignment *cmd = readAssignment(tok)) {
278       script->sectionCommands.push_back(cmd);
279     } else {
280       setError("unknown directive: " + tok);
281     }
282   }
283 }
284 
readDefsym(StringRef name)285 void ScriptParser::readDefsym(StringRef name) {
286   if (errorCount())
287     return;
288   Expr e = readExpr();
289   if (!atEOF())
290     setError("EOF expected, but got " + next());
291   auto *cmd = make<SymbolAssignment>(
292       name, e, 0, getCurrentMB().getBufferIdentifier().str());
293   script->sectionCommands.push_back(cmd);
294 }
295 
addFile(StringRef s)296 void ScriptParser::addFile(StringRef s) {
297   if (isUnderSysroot && s.starts_with("/")) {
298     SmallString<128> pathData;
299     StringRef path = (config->sysroot + s).toStringRef(pathData);
300     if (sys::fs::exists(path))
301       ctx.driver.addFile(saver().save(path), /*withLOption=*/false);
302     else
303       setError("cannot find " + s + " inside " + config->sysroot);
304     return;
305   }
306 
307   if (s.starts_with("/")) {
308     // Case 1: s is an absolute path. Just open it.
309     ctx.driver.addFile(s, /*withLOption=*/false);
310   } else if (s.starts_with("=")) {
311     // Case 2: relative to the sysroot.
312     if (config->sysroot.empty())
313       ctx.driver.addFile(s.substr(1), /*withLOption=*/false);
314     else
315       ctx.driver.addFile(saver().save(config->sysroot + "/" + s.substr(1)),
316                          /*withLOption=*/false);
317   } else if (s.starts_with("-l")) {
318     // Case 3: search in the list of library paths.
319     ctx.driver.addLibrary(s.substr(2));
320   } else {
321     // Case 4: s is a relative path. Search in the directory of the script file.
322     std::string filename = std::string(getCurrentMB().getBufferIdentifier());
323     StringRef directory = sys::path::parent_path(filename);
324     if (!directory.empty()) {
325       SmallString<0> path(directory);
326       sys::path::append(path, s);
327       if (sys::fs::exists(path)) {
328         ctx.driver.addFile(path, /*withLOption=*/false);
329         return;
330       }
331     }
332     // Then search in the current working directory.
333     if (sys::fs::exists(s)) {
334       ctx.driver.addFile(s, /*withLOption=*/false);
335     } else {
336       // Finally, search in the list of library paths.
337       if (std::optional<std::string> path = findFromSearchPaths(s))
338         ctx.driver.addFile(saver().save(*path), /*withLOption=*/true);
339       else
340         setError("unable to find " + s);
341     }
342   }
343 }
344 
readAsNeeded()345 void ScriptParser::readAsNeeded() {
346   expect("(");
347   bool orig = config->asNeeded;
348   config->asNeeded = true;
349   while (!errorCount() && !consume(")"))
350     addFile(unquote(next()));
351   config->asNeeded = orig;
352 }
353 
readEntry()354 void ScriptParser::readEntry() {
355   // -e <symbol> takes predecence over ENTRY(<symbol>).
356   expect("(");
357   StringRef tok = next();
358   if (config->entry.empty())
359     config->entry = unquote(tok);
360   expect(")");
361 }
362 
readExtern()363 void ScriptParser::readExtern() {
364   expect("(");
365   while (!errorCount() && !consume(")"))
366     config->undefined.push_back(unquote(next()));
367 }
368 
readGroup()369 void ScriptParser::readGroup() {
370   bool orig = InputFile::isInGroup;
371   InputFile::isInGroup = true;
372   readInput();
373   InputFile::isInGroup = orig;
374   if (!orig)
375     ++InputFile::nextGroupId;
376 }
377 
readInclude()378 void ScriptParser::readInclude() {
379   StringRef tok = unquote(next());
380 
381   if (!seen.insert(tok).second) {
382     setError("there is a cycle in linker script INCLUDEs");
383     return;
384   }
385 
386   if (std::optional<std::string> path = searchScript(tok)) {
387     if (std::optional<MemoryBufferRef> mb = readFile(*path))
388       tokenize(*mb);
389     return;
390   }
391   setError("cannot find linker script " + tok);
392 }
393 
readInput()394 void ScriptParser::readInput() {
395   expect("(");
396   while (!errorCount() && !consume(")")) {
397     if (consume("AS_NEEDED"))
398       readAsNeeded();
399     else
400       addFile(unquote(next()));
401   }
402 }
403 
readOutput()404 void ScriptParser::readOutput() {
405   // -o <file> takes predecence over OUTPUT(<file>).
406   expect("(");
407   StringRef tok = next();
408   if (config->outputFile.empty())
409     config->outputFile = unquote(tok);
410   expect(")");
411 }
412 
readOutputArch()413 void ScriptParser::readOutputArch() {
414   // OUTPUT_ARCH is ignored for now.
415   expect("(");
416   while (!errorCount() && !consume(")"))
417     skip();
418 }
419 
parseBfdName(StringRef s)420 static std::pair<ELFKind, uint16_t> parseBfdName(StringRef s) {
421   return StringSwitch<std::pair<ELFKind, uint16_t>>(s)
422       .Case("elf32-i386", {ELF32LEKind, EM_386})
423       .Case("elf32-avr", {ELF32LEKind, EM_AVR})
424       .Case("elf32-iamcu", {ELF32LEKind, EM_IAMCU})
425       .Case("elf32-littlearm", {ELF32LEKind, EM_ARM})
426       .Case("elf32-bigarm", {ELF32BEKind, EM_ARM})
427       .Case("elf32-x86-64", {ELF32LEKind, EM_X86_64})
428       .Case("elf64-aarch64", {ELF64LEKind, EM_AARCH64})
429       .Case("elf64-littleaarch64", {ELF64LEKind, EM_AARCH64})
430       .Case("elf64-bigaarch64", {ELF64BEKind, EM_AARCH64})
431       .Case("elf32-powerpc", {ELF32BEKind, EM_PPC})
432       .Case("elf32-powerpcle", {ELF32LEKind, EM_PPC})
433       .Case("elf64-powerpc", {ELF64BEKind, EM_PPC64})
434       .Case("elf64-powerpcle", {ELF64LEKind, EM_PPC64})
435       .Case("elf64-x86-64", {ELF64LEKind, EM_X86_64})
436       .Cases("elf32-tradbigmips", "elf32-bigmips", {ELF32BEKind, EM_MIPS})
437       .Case("elf32-ntradbigmips", {ELF32BEKind, EM_MIPS})
438       .Case("elf32-tradlittlemips", {ELF32LEKind, EM_MIPS})
439       .Case("elf32-ntradlittlemips", {ELF32LEKind, EM_MIPS})
440       .Case("elf64-tradbigmips", {ELF64BEKind, EM_MIPS})
441       .Case("elf64-tradlittlemips", {ELF64LEKind, EM_MIPS})
442       .Case("elf32-littleriscv", {ELF32LEKind, EM_RISCV})
443       .Case("elf64-littleriscv", {ELF64LEKind, EM_RISCV})
444       .Case("elf64-sparc", {ELF64BEKind, EM_SPARCV9})
445       .Case("elf32-msp430", {ELF32LEKind, EM_MSP430})
446       .Case("elf32-loongarch", {ELF32LEKind, EM_LOONGARCH})
447       .Case("elf64-loongarch", {ELF64LEKind, EM_LOONGARCH})
448       .Case("elf64-s390", {ELF64BEKind, EM_S390})
449       .Default({ELFNoneKind, EM_NONE});
450 }
451 
452 // Parse OUTPUT_FORMAT(bfdname) or OUTPUT_FORMAT(default, big, little). Choose
453 // big if -EB is specified, little if -EL is specified, or default if neither is
454 // specified.
readOutputFormat()455 void ScriptParser::readOutputFormat() {
456   expect("(");
457 
458   StringRef s;
459   config->bfdname = unquote(next());
460   if (!consume(")")) {
461     expect(",");
462     s = unquote(next());
463     if (config->optEB)
464       config->bfdname = s;
465     expect(",");
466     s = unquote(next());
467     if (config->optEL)
468       config->bfdname = s;
469     consume(")");
470   }
471   s = config->bfdname;
472   if (s.consume_back("-freebsd"))
473     config->osabi = ELFOSABI_FREEBSD;
474 
475   std::tie(config->ekind, config->emachine) = parseBfdName(s);
476   if (config->emachine == EM_NONE)
477     setError("unknown output format name: " + config->bfdname);
478   if (s == "elf32-ntradlittlemips" || s == "elf32-ntradbigmips")
479     config->mipsN32Abi = true;
480   if (config->emachine == EM_MSP430)
481     config->osabi = ELFOSABI_STANDALONE;
482 }
483 
readPhdrs()484 void ScriptParser::readPhdrs() {
485   expect("{");
486 
487   while (!errorCount() && !consume("}")) {
488     PhdrsCommand cmd;
489     cmd.name = next();
490     cmd.type = readPhdrType();
491 
492     while (!errorCount() && !consume(";")) {
493       if (consume("FILEHDR"))
494         cmd.hasFilehdr = true;
495       else if (consume("PHDRS"))
496         cmd.hasPhdrs = true;
497       else if (consume("AT"))
498         cmd.lmaExpr = readParenExpr();
499       else if (consume("FLAGS"))
500         cmd.flags = readParenExpr()().getValue();
501       else
502         setError("unexpected header attribute: " + next());
503     }
504 
505     script->phdrsCommands.push_back(cmd);
506   }
507 }
508 
readRegionAlias()509 void ScriptParser::readRegionAlias() {
510   expect("(");
511   StringRef alias = unquote(next());
512   expect(",");
513   StringRef name = next();
514   expect(")");
515 
516   if (script->memoryRegions.count(alias))
517     setError("redefinition of memory region '" + alias + "'");
518   if (!script->memoryRegions.count(name))
519     setError("memory region '" + name + "' is not defined");
520   script->memoryRegions.insert({alias, script->memoryRegions[name]});
521 }
522 
readSearchDir()523 void ScriptParser::readSearchDir() {
524   expect("(");
525   StringRef tok = next();
526   if (!config->nostdlib)
527     config->searchPaths.push_back(unquote(tok));
528   expect(")");
529 }
530 
531 // This reads an overlay description. Overlays are used to describe output
532 // sections that use the same virtual memory range and normally would trigger
533 // linker's sections sanity check failures.
534 // https://sourceware.org/binutils/docs/ld/Overlay-Description.html#Overlay-Description
readOverlay()535 SmallVector<SectionCommand *, 0> ScriptParser::readOverlay() {
536   Expr addrExpr;
537   if (consume(":")) {
538     addrExpr = [] { return script->getDot(); };
539   } else {
540     addrExpr = readExpr();
541     expect(":");
542   }
543   // When AT is omitted, LMA should equal VMA. script->getDot() when evaluating
544   // lmaExpr will ensure this, even if the start address is specified.
545   Expr lmaExpr =
546       consume("AT") ? readParenExpr() : [] { return script->getDot(); };
547   expect("{");
548 
549   SmallVector<SectionCommand *, 0> v;
550   OutputSection *prev = nullptr;
551   while (!errorCount() && !consume("}")) {
552     // VA is the same for all sections. The LMAs are consecutive in memory
553     // starting from the base load address specified.
554     OutputDesc *osd = readOverlaySectionDescription();
555     osd->osec.addrExpr = addrExpr;
556     if (prev) {
557       osd->osec.lmaExpr = [=] { return prev->getLMA() + prev->size; };
558     } else {
559       osd->osec.lmaExpr = lmaExpr;
560       // Use first section address for subsequent sections as initial addrExpr
561       // can be DOT. Ensure the first section, even if empty, is not discarded.
562       osd->osec.usedInExpression = true;
563       addrExpr = [=]() -> ExprValue { return {&osd->osec, false, 0, ""}; };
564     }
565     v.push_back(osd);
566     prev = &osd->osec;
567   }
568 
569   // According to the specification, at the end of the overlay, the location
570   // counter should be equal to the overlay base address plus size of the
571   // largest section seen in the overlay.
572   // Here we want to create the Dot assignment command to achieve that.
573   Expr moveDot = [=] {
574     uint64_t max = 0;
575     for (SectionCommand *cmd : v)
576       max = std::max(max, cast<OutputDesc>(cmd)->osec.size);
577     return addrExpr().getValue() + max;
578   };
579   v.push_back(make<SymbolAssignment>(".", moveDot, 0, getCurrentLocation()));
580   return v;
581 }
582 
readOverwriteSections()583 void ScriptParser::readOverwriteSections() {
584   expect("{");
585   while (!errorCount() && !consume("}"))
586     script->overwriteSections.push_back(readOutputSectionDescription(next()));
587 }
588 
readSections()589 void ScriptParser::readSections() {
590   expect("{");
591   SmallVector<SectionCommand *, 0> v;
592   while (!errorCount() && !consume("}")) {
593     StringRef tok = next();
594     if (tok == "OVERLAY") {
595       for (SectionCommand *cmd : readOverlay())
596         v.push_back(cmd);
597       continue;
598     } else if (tok == "INCLUDE") {
599       readInclude();
600       continue;
601     }
602 
603     if (SectionCommand *cmd = readAssignment(tok))
604       v.push_back(cmd);
605     else
606       v.push_back(readOutputSectionDescription(tok));
607   }
608 
609   // If DATA_SEGMENT_RELRO_END is absent, for sections after DATA_SEGMENT_ALIGN,
610   // the relro fields should be cleared.
611   if (!script->seenRelroEnd)
612     for (SectionCommand *cmd : v)
613       if (auto *osd = dyn_cast<OutputDesc>(cmd))
614         osd->osec.relro = false;
615 
616   script->sectionCommands.insert(script->sectionCommands.end(), v.begin(),
617                                  v.end());
618 
619   if (atEOF() || !consume("INSERT")) {
620     script->hasSectionsCommand = true;
621     return;
622   }
623 
624   bool isAfter = false;
625   if (consume("AFTER"))
626     isAfter = true;
627   else if (!consume("BEFORE"))
628     setError("expected AFTER/BEFORE, but got '" + next() + "'");
629   StringRef where = next();
630   SmallVector<StringRef, 0> names;
631   for (SectionCommand *cmd : v)
632     if (auto *os = dyn_cast<OutputDesc>(cmd))
633       names.push_back(os->osec.name);
634   if (!names.empty())
635     script->insertCommands.push_back({std::move(names), isAfter, where});
636 }
637 
readTarget()638 void ScriptParser::readTarget() {
639   // TARGET(foo) is an alias for "--format foo". Unlike GNU linkers,
640   // we accept only a limited set of BFD names (i.e. "elf" or "binary")
641   // for --format. We recognize only /^elf/ and "binary" in the linker
642   // script as well.
643   expect("(");
644   StringRef tok = unquote(next());
645   expect(")");
646 
647   if (tok.starts_with("elf"))
648     config->formatBinary = false;
649   else if (tok == "binary")
650     config->formatBinary = true;
651   else
652     setError("unknown target: " + tok);
653 }
654 
precedence(StringRef op)655 static int precedence(StringRef op) {
656   return StringSwitch<int>(op)
657       .Cases("*", "/", "%", 11)
658       .Cases("+", "-", 10)
659       .Cases("<<", ">>", 9)
660       .Cases("<", "<=", ">", ">=", 8)
661       .Cases("==", "!=", 7)
662       .Case("&", 6)
663       .Case("^", 5)
664       .Case("|", 4)
665       .Case("&&", 3)
666       .Case("||", 2)
667       .Case("?", 1)
668       .Default(-1);
669 }
670 
readFilePatterns()671 StringMatcher ScriptParser::readFilePatterns() {
672   StringMatcher Matcher;
673 
674   while (!errorCount() && !consume(")"))
675     Matcher.addPattern(SingleStringMatcher(next()));
676   return Matcher;
677 }
678 
peekSortKind()679 SortSectionPolicy ScriptParser::peekSortKind() {
680   return StringSwitch<SortSectionPolicy>(peek())
681       .Case("REVERSE", SortSectionPolicy::Reverse)
682       .Cases("SORT", "SORT_BY_NAME", SortSectionPolicy::Name)
683       .Case("SORT_BY_ALIGNMENT", SortSectionPolicy::Alignment)
684       .Case("SORT_BY_INIT_PRIORITY", SortSectionPolicy::Priority)
685       .Case("SORT_NONE", SortSectionPolicy::None)
686       .Default(SortSectionPolicy::Default);
687 }
688 
readSortKind()689 SortSectionPolicy ScriptParser::readSortKind() {
690   SortSectionPolicy ret = peekSortKind();
691   if (ret != SortSectionPolicy::Default)
692     skip();
693   return ret;
694 }
695 
696 // Reads SECTIONS command contents in the following form:
697 //
698 // <contents> ::= <elem>*
699 // <elem>     ::= <exclude>? <glob-pattern>
700 // <exclude>  ::= "EXCLUDE_FILE" "(" <glob-pattern>+ ")"
701 //
702 // For example,
703 //
704 // *(.foo EXCLUDE_FILE (a.o) .bar EXCLUDE_FILE (b.o) .baz)
705 //
706 // is parsed as ".foo", ".bar" with "a.o", and ".baz" with "b.o".
707 // The semantics of that is section .foo in any file, section .bar in
708 // any file but a.o, and section .baz in any file but b.o.
readInputSectionsList()709 SmallVector<SectionPattern, 0> ScriptParser::readInputSectionsList() {
710   SmallVector<SectionPattern, 0> ret;
711   while (!errorCount() && peek() != ")") {
712     StringMatcher excludeFilePat;
713     if (consume("EXCLUDE_FILE")) {
714       expect("(");
715       excludeFilePat = readFilePatterns();
716     }
717 
718     StringMatcher SectionMatcher;
719     // Break if the next token is ), EXCLUDE_FILE, or SORT*.
720     while (!errorCount() && peek() != ")" && peek() != "EXCLUDE_FILE" &&
721            peekSortKind() == SortSectionPolicy::Default)
722       SectionMatcher.addPattern(unquote(next()));
723 
724     if (!SectionMatcher.empty())
725       ret.push_back({std::move(excludeFilePat), std::move(SectionMatcher)});
726     else if (excludeFilePat.empty())
727       break;
728     else
729       setError("section pattern is expected");
730   }
731   return ret;
732 }
733 
734 // Reads contents of "SECTIONS" directive. That directive contains a
735 // list of glob patterns for input sections. The grammar is as follows.
736 //
737 // <patterns> ::= <section-list>
738 //              | <sort> "(" <section-list> ")"
739 //              | <sort> "(" <sort> "(" <section-list> ")" ")"
740 //
741 // <sort>     ::= "SORT" | "SORT_BY_NAME" | "SORT_BY_ALIGNMENT"
742 //              | "SORT_BY_INIT_PRIORITY" | "SORT_NONE"
743 //
744 // <section-list> is parsed by readInputSectionsList().
745 InputSectionDescription *
readInputSectionRules(StringRef filePattern,uint64_t withFlags,uint64_t withoutFlags)746 ScriptParser::readInputSectionRules(StringRef filePattern, uint64_t withFlags,
747                                     uint64_t withoutFlags) {
748   auto *cmd =
749       make<InputSectionDescription>(filePattern, withFlags, withoutFlags);
750   expect("(");
751 
752   while (!errorCount() && !consume(")")) {
753     SortSectionPolicy outer = readSortKind();
754     SortSectionPolicy inner = SortSectionPolicy::Default;
755     SmallVector<SectionPattern, 0> v;
756     if (outer != SortSectionPolicy::Default) {
757       expect("(");
758       inner = readSortKind();
759       if (inner != SortSectionPolicy::Default) {
760         expect("(");
761         v = readInputSectionsList();
762         expect(")");
763       } else {
764         v = readInputSectionsList();
765       }
766       expect(")");
767     } else {
768       v = readInputSectionsList();
769     }
770 
771     for (SectionPattern &pat : v) {
772       pat.sortInner = inner;
773       pat.sortOuter = outer;
774     }
775 
776     std::move(v.begin(), v.end(), std::back_inserter(cmd->sectionPatterns));
777   }
778   return cmd;
779 }
780 
781 InputSectionDescription *
readInputSectionDescription(StringRef tok)782 ScriptParser::readInputSectionDescription(StringRef tok) {
783   // Input section wildcard can be surrounded by KEEP.
784   // https://sourceware.org/binutils/docs/ld/Input-Section-Keep.html#Input-Section-Keep
785   uint64_t withFlags = 0;
786   uint64_t withoutFlags = 0;
787   if (tok == "KEEP") {
788     expect("(");
789     if (consume("INPUT_SECTION_FLAGS"))
790       std::tie(withFlags, withoutFlags) = readInputSectionFlags();
791     InputSectionDescription *cmd =
792         readInputSectionRules(next(), withFlags, withoutFlags);
793     expect(")");
794     script->keptSections.push_back(cmd);
795     return cmd;
796   }
797   if (tok == "INPUT_SECTION_FLAGS") {
798     std::tie(withFlags, withoutFlags) = readInputSectionFlags();
799     tok = next();
800   }
801   return readInputSectionRules(tok, withFlags, withoutFlags);
802 }
803 
readSort()804 void ScriptParser::readSort() {
805   expect("(");
806   expect("CONSTRUCTORS");
807   expect(")");
808 }
809 
readAssert()810 Expr ScriptParser::readAssert() {
811   expect("(");
812   Expr e = readExpr();
813   expect(",");
814   StringRef msg = unquote(next());
815   expect(")");
816 
817   return [=] {
818     if (!e().getValue())
819       errorOrWarn(msg);
820     return script->getDot();
821   };
822 }
823 
824 #define ECase(X)                                                               \
825   { #X, X }
826 constexpr std::pair<const char *, unsigned> typeMap[] = {
827     ECase(SHT_PROGBITS),   ECase(SHT_NOTE),       ECase(SHT_NOBITS),
828     ECase(SHT_INIT_ARRAY), ECase(SHT_FINI_ARRAY), ECase(SHT_PREINIT_ARRAY),
829 };
830 #undef ECase
831 
832 // Tries to read the special directive for an output section definition which
833 // can be one of following: "(NOLOAD)", "(COPY)", "(INFO)", "(OVERLAY)", and
834 // "(TYPE=<value>)".
835 // Tok1 and Tok2 are next 2 tokens peeked. See comment for
836 // readSectionAddressType below.
readSectionDirective(OutputSection * cmd,StringRef tok1,StringRef tok2)837 bool ScriptParser::readSectionDirective(OutputSection *cmd, StringRef tok1, StringRef tok2) {
838   if (tok1 != "(")
839     return false;
840   if (tok2 != "NOLOAD" && tok2 != "COPY" && tok2 != "INFO" &&
841       tok2 != "OVERLAY" && tok2 != "TYPE")
842     return false;
843 
844   expect("(");
845   if (consume("NOLOAD")) {
846     cmd->type = SHT_NOBITS;
847     cmd->typeIsSet = true;
848   } else if (consume("TYPE")) {
849     expect("=");
850     StringRef value = peek();
851     auto it = llvm::find_if(typeMap, [=](auto e) { return e.first == value; });
852     if (it != std::end(typeMap)) {
853       // The value is a recognized literal SHT_*.
854       cmd->type = it->second;
855       skip();
856     } else if (value.starts_with("SHT_")) {
857       setError("unknown section type " + value);
858     } else {
859       // Otherwise, read an expression.
860       cmd->type = readExpr()().getValue();
861     }
862     cmd->typeIsSet = true;
863   } else {
864     skip(); // This is "COPY", "INFO" or "OVERLAY".
865     cmd->nonAlloc = true;
866   }
867   expect(")");
868   return true;
869 }
870 
871 // Reads an expression and/or the special directive for an output
872 // section definition. Directive is one of following: "(NOLOAD)",
873 // "(COPY)", "(INFO)" or "(OVERLAY)".
874 //
875 // An output section name can be followed by an address expression
876 // and/or directive. This grammar is not LL(1) because "(" can be
877 // interpreted as either the beginning of some expression or beginning
878 // of directive.
879 //
880 // https://sourceware.org/binutils/docs/ld/Output-Section-Address.html
881 // https://sourceware.org/binutils/docs/ld/Output-Section-Type.html
readSectionAddressType(OutputSection * cmd)882 void ScriptParser::readSectionAddressType(OutputSection *cmd) {
883   // Temporarily set inExpr to support TYPE=<value> without spaces.
884   bool saved = std::exchange(inExpr, true);
885   bool isDirective = readSectionDirective(cmd, peek(), peek2());
886   inExpr = saved;
887   if (isDirective)
888     return;
889 
890   cmd->addrExpr = readExpr();
891   if (peek() == "(" && !readSectionDirective(cmd, "(", peek2()))
892     setError("unknown section directive: " + peek2());
893 }
894 
checkAlignment(Expr e,std::string & loc)895 static Expr checkAlignment(Expr e, std::string &loc) {
896   return [=] {
897     uint64_t alignment = std::max((uint64_t)1, e().getValue());
898     if (!isPowerOf2_64(alignment)) {
899       error(loc + ": alignment must be power of 2");
900       return (uint64_t)1; // Return a dummy value.
901     }
902     return alignment;
903   };
904 }
905 
readOverlaySectionDescription()906 OutputDesc *ScriptParser::readOverlaySectionDescription() {
907   OutputDesc *osd = script->createOutputSection(next(), getCurrentLocation());
908   osd->osec.inOverlay = true;
909   expect("{");
910   while (!errorCount() && !consume("}")) {
911     uint64_t withFlags = 0;
912     uint64_t withoutFlags = 0;
913     if (consume("INPUT_SECTION_FLAGS"))
914       std::tie(withFlags, withoutFlags) = readInputSectionFlags();
915     osd->osec.commands.push_back(
916         readInputSectionRules(next(), withFlags, withoutFlags));
917   }
918   osd->osec.phdrs = readOutputSectionPhdrs();
919   return osd;
920 }
921 
readOutputSectionDescription(StringRef outSec)922 OutputDesc *ScriptParser::readOutputSectionDescription(StringRef outSec) {
923   OutputDesc *cmd =
924       script->createOutputSection(unquote(outSec), getCurrentLocation());
925   OutputSection *osec = &cmd->osec;
926   // Maybe relro. Will reset to false if DATA_SEGMENT_RELRO_END is absent.
927   osec->relro = script->seenDataAlign && !script->seenRelroEnd;
928 
929   size_t symbolsReferenced = script->referencedSymbols.size();
930 
931   if (peek() != ":")
932     readSectionAddressType(osec);
933   expect(":");
934 
935   std::string location = getCurrentLocation();
936   if (consume("AT"))
937     osec->lmaExpr = readParenExpr();
938   if (consume("ALIGN"))
939     osec->alignExpr = checkAlignment(readParenExpr(), location);
940   if (consume("SUBALIGN"))
941     osec->subalignExpr = checkAlignment(readParenExpr(), location);
942 
943   // Parse constraints.
944   if (consume("ONLY_IF_RO"))
945     osec->constraint = ConstraintKind::ReadOnly;
946   if (consume("ONLY_IF_RW"))
947     osec->constraint = ConstraintKind::ReadWrite;
948   expect("{");
949 
950   while (!errorCount() && !consume("}")) {
951     StringRef tok = next();
952     if (tok == ";") {
953       // Empty commands are allowed. Do nothing here.
954     } else if (SymbolAssignment *assign = readAssignment(tok)) {
955       osec->commands.push_back(assign);
956     } else if (ByteCommand *data = readByteCommand(tok)) {
957       osec->commands.push_back(data);
958     } else if (tok == "CONSTRUCTORS") {
959       // CONSTRUCTORS is a keyword to make the linker recognize C++ ctors/dtors
960       // by name. This is for very old file formats such as ECOFF/XCOFF.
961       // For ELF, we should ignore.
962     } else if (tok == "FILL") {
963       // We handle the FILL command as an alias for =fillexp section attribute,
964       // which is different from what GNU linkers do.
965       // https://sourceware.org/binutils/docs/ld/Output-Section-Data.html
966       if (peek() != "(")
967         setError("( expected, but got " + peek());
968       osec->filler = readFill();
969     } else if (tok == "SORT") {
970       readSort();
971     } else if (tok == "INCLUDE") {
972       readInclude();
973     } else if (tok == "(" || tok == ")") {
974       setError("expected filename pattern");
975     } else if (peek() == "(") {
976       osec->commands.push_back(readInputSectionDescription(tok));
977     } else {
978       // We have a file name and no input sections description. It is not a
979       // commonly used syntax, but still acceptable. In that case, all sections
980       // from the file will be included.
981       // FIXME: GNU ld permits INPUT_SECTION_FLAGS to be used here. We do not
982       // handle this case here as it will already have been matched by the
983       // case above.
984       auto *isd = make<InputSectionDescription>(tok);
985       isd->sectionPatterns.push_back({{}, StringMatcher("*")});
986       osec->commands.push_back(isd);
987     }
988   }
989 
990   if (consume(">"))
991     osec->memoryRegionName = std::string(next());
992 
993   if (consume("AT")) {
994     expect(">");
995     osec->lmaRegionName = std::string(next());
996   }
997 
998   if (osec->lmaExpr && !osec->lmaRegionName.empty())
999     error("section can't have both LMA and a load region");
1000 
1001   osec->phdrs = readOutputSectionPhdrs();
1002 
1003   if (peek() == "=" || peek().starts_with("=")) {
1004     inExpr = true;
1005     consume("=");
1006     osec->filler = readFill();
1007     inExpr = false;
1008   }
1009 
1010   // Consume optional comma following output section command.
1011   consume(",");
1012 
1013   if (script->referencedSymbols.size() > symbolsReferenced)
1014     osec->expressionsUseSymbols = true;
1015   return cmd;
1016 }
1017 
1018 // Reads a `=<fillexp>` expression and returns its value as a big-endian number.
1019 // https://sourceware.org/binutils/docs/ld/Output-Section-Fill.html
1020 // We do not support using symbols in such expressions.
1021 //
1022 // When reading a hexstring, ld.bfd handles it as a blob of arbitrary
1023 // size, while ld.gold always handles it as a 32-bit big-endian number.
1024 // We are compatible with ld.gold because it's easier to implement.
1025 // Also, we require that expressions with operators must be wrapped into
1026 // round brackets. We did it to resolve the ambiguity when parsing scripts like:
1027 // SECTIONS { .foo : { ... } =120+3 /DISCARD/ : { ... } }
readFill()1028 std::array<uint8_t, 4> ScriptParser::readFill() {
1029   uint64_t value = readPrimary()().val;
1030   if (value > UINT32_MAX)
1031     setError("filler expression result does not fit 32-bit: 0x" +
1032              Twine::utohexstr(value));
1033 
1034   std::array<uint8_t, 4> buf;
1035   write32be(buf.data(), (uint32_t)value);
1036   return buf;
1037 }
1038 
readProvideHidden(bool provide,bool hidden)1039 SymbolAssignment *ScriptParser::readProvideHidden(bool provide, bool hidden) {
1040   expect("(");
1041   StringRef name = next(), eq = peek();
1042   if (eq != "=") {
1043     setError("= expected, but got " + next());
1044     while (!atEOF() && next() != ")")
1045       ;
1046     return nullptr;
1047   }
1048   SymbolAssignment *cmd = readSymbolAssignment(name);
1049   cmd->provide = provide;
1050   cmd->hidden = hidden;
1051   expect(")");
1052   return cmd;
1053 }
1054 
readAssignment(StringRef tok)1055 SymbolAssignment *ScriptParser::readAssignment(StringRef tok) {
1056   // Assert expression returns Dot, so this is equal to ".=."
1057   if (tok == "ASSERT")
1058     return make<SymbolAssignment>(".", readAssert(), 0, getCurrentLocation());
1059 
1060   size_t oldPos = pos;
1061   SymbolAssignment *cmd = nullptr;
1062   bool savedSeenRelroEnd = script->seenRelroEnd;
1063   const StringRef op = peek();
1064   if (op.starts_with("=")) {
1065     // Support = followed by an expression without whitespace.
1066     SaveAndRestore saved(inExpr, true);
1067     cmd = readSymbolAssignment(tok);
1068   } else if ((op.size() == 2 && op[1] == '=' && strchr("*/+-&^|", op[0])) ||
1069              op == "<<=" || op == ">>=") {
1070     cmd = readSymbolAssignment(tok);
1071   } else if (tok == "PROVIDE") {
1072     SaveAndRestore saved(inExpr, true);
1073     cmd = readProvideHidden(true, false);
1074   } else if (tok == "HIDDEN") {
1075     SaveAndRestore saved(inExpr, true);
1076     cmd = readProvideHidden(false, true);
1077   } else if (tok == "PROVIDE_HIDDEN") {
1078     SaveAndRestore saved(inExpr, true);
1079     cmd = readProvideHidden(true, true);
1080   }
1081 
1082   if (cmd) {
1083     cmd->dataSegmentRelroEnd = !savedSeenRelroEnd && script->seenRelroEnd;
1084     cmd->commandString =
1085         tok.str() + " " +
1086         llvm::join(tokens.begin() + oldPos, tokens.begin() + pos, " ");
1087     expect(";");
1088   }
1089   return cmd;
1090 }
1091 
readSymbolAssignment(StringRef name)1092 SymbolAssignment *ScriptParser::readSymbolAssignment(StringRef name) {
1093   name = unquote(name);
1094   StringRef op = next();
1095   assert(op == "=" || op == "*=" || op == "/=" || op == "+=" || op == "-=" ||
1096          op == "&=" || op == "^=" || op == "|=" || op == "<<=" || op == ">>=");
1097   // Note: GNU ld does not support %=.
1098   Expr e = readExpr();
1099   if (op != "=") {
1100     std::string loc = getCurrentLocation();
1101     e = [=, c = op[0]]() -> ExprValue {
1102       ExprValue lhs = script->getSymbolValue(name, loc);
1103       switch (c) {
1104       case '*':
1105         return lhs.getValue() * e().getValue();
1106       case '/':
1107         if (uint64_t rv = e().getValue())
1108           return lhs.getValue() / rv;
1109         error(loc + ": division by zero");
1110         return 0;
1111       case '+':
1112         return add(lhs, e());
1113       case '-':
1114         return sub(lhs, e());
1115       case '<':
1116         return lhs.getValue() << e().getValue() % 64;
1117       case '>':
1118         return lhs.getValue() >> e().getValue() % 64;
1119       case '&':
1120         return lhs.getValue() & e().getValue();
1121       case '^':
1122         return lhs.getValue() ^ e().getValue();
1123       case '|':
1124         return lhs.getValue() | e().getValue();
1125       default:
1126         llvm_unreachable("");
1127       }
1128     };
1129   }
1130   return make<SymbolAssignment>(name, e, ctx.scriptSymOrderCounter++,
1131                                 getCurrentLocation());
1132 }
1133 
1134 // This is an operator-precedence parser to parse a linker
1135 // script expression.
readExpr()1136 Expr ScriptParser::readExpr() {
1137   // Our lexer is context-aware. Set the in-expression bit so that
1138   // they apply different tokenization rules.
1139   bool orig = inExpr;
1140   inExpr = true;
1141   Expr e = readExpr1(readPrimary(), 0);
1142   inExpr = orig;
1143   return e;
1144 }
1145 
combine(StringRef op,Expr l,Expr r)1146 Expr ScriptParser::combine(StringRef op, Expr l, Expr r) {
1147   if (op == "+")
1148     return [=] { return add(l(), r()); };
1149   if (op == "-")
1150     return [=] { return sub(l(), r()); };
1151   if (op == "*")
1152     return [=] { return l().getValue() * r().getValue(); };
1153   if (op == "/") {
1154     std::string loc = getCurrentLocation();
1155     return [=]() -> uint64_t {
1156       if (uint64_t rv = r().getValue())
1157         return l().getValue() / rv;
1158       error(loc + ": division by zero");
1159       return 0;
1160     };
1161   }
1162   if (op == "%") {
1163     std::string loc = getCurrentLocation();
1164     return [=]() -> uint64_t {
1165       if (uint64_t rv = r().getValue())
1166         return l().getValue() % rv;
1167       error(loc + ": modulo by zero");
1168       return 0;
1169     };
1170   }
1171   if (op == "<<")
1172     return [=] { return l().getValue() << r().getValue() % 64; };
1173   if (op == ">>")
1174     return [=] { return l().getValue() >> r().getValue() % 64; };
1175   if (op == "<")
1176     return [=] { return l().getValue() < r().getValue(); };
1177   if (op == ">")
1178     return [=] { return l().getValue() > r().getValue(); };
1179   if (op == ">=")
1180     return [=] { return l().getValue() >= r().getValue(); };
1181   if (op == "<=")
1182     return [=] { return l().getValue() <= r().getValue(); };
1183   if (op == "==")
1184     return [=] { return l().getValue() == r().getValue(); };
1185   if (op == "!=")
1186     return [=] { return l().getValue() != r().getValue(); };
1187   if (op == "||")
1188     return [=] { return l().getValue() || r().getValue(); };
1189   if (op == "&&")
1190     return [=] { return l().getValue() && r().getValue(); };
1191   if (op == "&")
1192     return [=] { return bitAnd(l(), r()); };
1193   if (op == "^")
1194     return [=] { return bitXor(l(), r()); };
1195   if (op == "|")
1196     return [=] { return bitOr(l(), r()); };
1197   llvm_unreachable("invalid operator");
1198 }
1199 
1200 // This is a part of the operator-precedence parser. This function
1201 // assumes that the remaining token stream starts with an operator.
readExpr1(Expr lhs,int minPrec)1202 Expr ScriptParser::readExpr1(Expr lhs, int minPrec) {
1203   while (!atEOF() && !errorCount()) {
1204     // Read an operator and an expression.
1205     StringRef op1 = peek();
1206     if (precedence(op1) < minPrec)
1207       break;
1208     if (consume("?"))
1209       return readTernary(lhs);
1210     skip();
1211     Expr rhs = readPrimary();
1212 
1213     // Evaluate the remaining part of the expression first if the
1214     // next operator has greater precedence than the previous one.
1215     // For example, if we have read "+" and "3", and if the next
1216     // operator is "*", then we'll evaluate 3 * ... part first.
1217     while (!atEOF()) {
1218       StringRef op2 = peek();
1219       if (precedence(op2) <= precedence(op1))
1220         break;
1221       rhs = readExpr1(rhs, precedence(op2));
1222     }
1223 
1224     lhs = combine(op1, lhs, rhs);
1225   }
1226   return lhs;
1227 }
1228 
getPageSize()1229 Expr ScriptParser::getPageSize() {
1230   std::string location = getCurrentLocation();
1231   return [=]() -> uint64_t {
1232     if (target)
1233       return config->commonPageSize;
1234     error(location + ": unable to calculate page size");
1235     return 4096; // Return a dummy value.
1236   };
1237 }
1238 
readConstant()1239 Expr ScriptParser::readConstant() {
1240   StringRef s = readParenLiteral();
1241   if (s == "COMMONPAGESIZE")
1242     return getPageSize();
1243   if (s == "MAXPAGESIZE")
1244     return [] { return config->maxPageSize; };
1245   setError("unknown constant: " + s);
1246   return [] { return 0; };
1247 }
1248 
1249 // Parses Tok as an integer. It recognizes hexadecimal (prefixed with
1250 // "0x" or suffixed with "H") and decimal numbers. Decimal numbers may
1251 // have "K" (Ki) or "M" (Mi) suffixes.
parseInt(StringRef tok)1252 static std::optional<uint64_t> parseInt(StringRef tok) {
1253   // Hexadecimal
1254   uint64_t val;
1255   if (tok.starts_with_insensitive("0x")) {
1256     if (!to_integer(tok.substr(2), val, 16))
1257       return std::nullopt;
1258     return val;
1259   }
1260   if (tok.ends_with_insensitive("H")) {
1261     if (!to_integer(tok.drop_back(), val, 16))
1262       return std::nullopt;
1263     return val;
1264   }
1265 
1266   // Decimal
1267   if (tok.ends_with_insensitive("K")) {
1268     if (!to_integer(tok.drop_back(), val, 10))
1269       return std::nullopt;
1270     return val * 1024;
1271   }
1272   if (tok.ends_with_insensitive("M")) {
1273     if (!to_integer(tok.drop_back(), val, 10))
1274       return std::nullopt;
1275     return val * 1024 * 1024;
1276   }
1277   if (!to_integer(tok, val, 10))
1278     return std::nullopt;
1279   return val;
1280 }
1281 
readByteCommand(StringRef tok)1282 ByteCommand *ScriptParser::readByteCommand(StringRef tok) {
1283   int size = StringSwitch<int>(tok)
1284                  .Case("BYTE", 1)
1285                  .Case("SHORT", 2)
1286                  .Case("LONG", 4)
1287                  .Case("QUAD", 8)
1288                  .Default(-1);
1289   if (size == -1)
1290     return nullptr;
1291 
1292   size_t oldPos = pos;
1293   Expr e = readParenExpr();
1294   std::string commandString =
1295       tok.str() + " " +
1296       llvm::join(tokens.begin() + oldPos, tokens.begin() + pos, " ");
1297   return make<ByteCommand>(e, size, commandString);
1298 }
1299 
parseFlag(StringRef tok)1300 static std::optional<uint64_t> parseFlag(StringRef tok) {
1301   if (std::optional<uint64_t> asInt = parseInt(tok))
1302     return asInt;
1303 #define CASE_ENT(enum) #enum, ELF::enum
1304   return StringSwitch<std::optional<uint64_t>>(tok)
1305       .Case(CASE_ENT(SHF_WRITE))
1306       .Case(CASE_ENT(SHF_ALLOC))
1307       .Case(CASE_ENT(SHF_EXECINSTR))
1308       .Case(CASE_ENT(SHF_MERGE))
1309       .Case(CASE_ENT(SHF_STRINGS))
1310       .Case(CASE_ENT(SHF_INFO_LINK))
1311       .Case(CASE_ENT(SHF_LINK_ORDER))
1312       .Case(CASE_ENT(SHF_OS_NONCONFORMING))
1313       .Case(CASE_ENT(SHF_GROUP))
1314       .Case(CASE_ENT(SHF_TLS))
1315       .Case(CASE_ENT(SHF_COMPRESSED))
1316       .Case(CASE_ENT(SHF_EXCLUDE))
1317       .Case(CASE_ENT(SHF_ARM_PURECODE))
1318       .Default(std::nullopt);
1319 #undef CASE_ENT
1320 }
1321 
1322 // Reads the '(' <flags> ')' list of section flags in
1323 // INPUT_SECTION_FLAGS '(' <flags> ')' in the
1324 // following form:
1325 // <flags> ::= <flag>
1326 //           | <flags> & flag
1327 // <flag>  ::= Recognized Flag Name, or Integer value of flag.
1328 // If the first character of <flag> is a ! then this means without flag,
1329 // otherwise with flag.
1330 // Example: SHF_EXECINSTR & !SHF_WRITE means with flag SHF_EXECINSTR and
1331 // without flag SHF_WRITE.
readInputSectionFlags()1332 std::pair<uint64_t, uint64_t> ScriptParser::readInputSectionFlags() {
1333    uint64_t withFlags = 0;
1334    uint64_t withoutFlags = 0;
1335    expect("(");
1336    while (!errorCount()) {
1337     StringRef tok = unquote(next());
1338     bool without = tok.consume_front("!");
1339     if (std::optional<uint64_t> flag = parseFlag(tok)) {
1340       if (without)
1341         withoutFlags |= *flag;
1342       else
1343         withFlags |= *flag;
1344     } else {
1345       setError("unrecognised flag: " + tok);
1346     }
1347     if (consume(")"))
1348       break;
1349     if (!consume("&")) {
1350       next();
1351       setError("expected & or )");
1352     }
1353   }
1354   return std::make_pair(withFlags, withoutFlags);
1355 }
1356 
readParenLiteral()1357 StringRef ScriptParser::readParenLiteral() {
1358   expect("(");
1359   bool orig = inExpr;
1360   inExpr = false;
1361   StringRef tok = next();
1362   inExpr = orig;
1363   expect(")");
1364   return tok;
1365 }
1366 
checkIfExists(const OutputSection & osec,StringRef location)1367 static void checkIfExists(const OutputSection &osec, StringRef location) {
1368   if (osec.location.empty() && script->errorOnMissingSection)
1369     error(location + ": undefined section " + osec.name);
1370 }
1371 
isValidSymbolName(StringRef s)1372 static bool isValidSymbolName(StringRef s) {
1373   auto valid = [](char c) {
1374     return isAlnum(c) || c == '$' || c == '.' || c == '_';
1375   };
1376   return !s.empty() && !isDigit(s[0]) && llvm::all_of(s, valid);
1377 }
1378 
readPrimary()1379 Expr ScriptParser::readPrimary() {
1380   if (peek() == "(")
1381     return readParenExpr();
1382 
1383   if (consume("~")) {
1384     Expr e = readPrimary();
1385     return [=] { return ~e().getValue(); };
1386   }
1387   if (consume("!")) {
1388     Expr e = readPrimary();
1389     return [=] { return !e().getValue(); };
1390   }
1391   if (consume("-")) {
1392     Expr e = readPrimary();
1393     return [=] { return -e().getValue(); };
1394   }
1395 
1396   StringRef tok = next();
1397   std::string location = getCurrentLocation();
1398 
1399   // Built-in functions are parsed here.
1400   // https://sourceware.org/binutils/docs/ld/Builtin-Functions.html.
1401   if (tok == "ABSOLUTE") {
1402     Expr inner = readParenExpr();
1403     return [=] {
1404       ExprValue i = inner();
1405       i.forceAbsolute = true;
1406       return i;
1407     };
1408   }
1409   if (tok == "ADDR") {
1410     StringRef name = unquote(readParenLiteral());
1411     OutputSection *osec = &script->getOrCreateOutputSection(name)->osec;
1412     osec->usedInExpression = true;
1413     return [=]() -> ExprValue {
1414       checkIfExists(*osec, location);
1415       return {osec, false, 0, location};
1416     };
1417   }
1418   if (tok == "ALIGN") {
1419     expect("(");
1420     Expr e = readExpr();
1421     if (consume(")")) {
1422       e = checkAlignment(e, location);
1423       return [=] { return alignToPowerOf2(script->getDot(), e().getValue()); };
1424     }
1425     expect(",");
1426     Expr e2 = checkAlignment(readExpr(), location);
1427     expect(")");
1428     return [=] {
1429       ExprValue v = e();
1430       v.alignment = e2().getValue();
1431       return v;
1432     };
1433   }
1434   if (tok == "ALIGNOF") {
1435     StringRef name = unquote(readParenLiteral());
1436     OutputSection *osec = &script->getOrCreateOutputSection(name)->osec;
1437     return [=] {
1438       checkIfExists(*osec, location);
1439       return osec->addralign;
1440     };
1441   }
1442   if (tok == "ASSERT")
1443     return readAssert();
1444   if (tok == "CONSTANT")
1445     return readConstant();
1446   if (tok == "DATA_SEGMENT_ALIGN") {
1447     expect("(");
1448     Expr e = readExpr();
1449     expect(",");
1450     readExpr();
1451     expect(")");
1452     script->seenDataAlign = true;
1453     return [=] {
1454       uint64_t align = std::max(uint64_t(1), e().getValue());
1455       return (script->getDot() + align - 1) & -align;
1456     };
1457   }
1458   if (tok == "DATA_SEGMENT_END") {
1459     expect("(");
1460     expect(".");
1461     expect(")");
1462     return [] { return script->getDot(); };
1463   }
1464   if (tok == "DATA_SEGMENT_RELRO_END") {
1465     // GNU linkers implements more complicated logic to handle
1466     // DATA_SEGMENT_RELRO_END. We instead ignore the arguments and
1467     // just align to the next page boundary for simplicity.
1468     expect("(");
1469     readExpr();
1470     expect(",");
1471     readExpr();
1472     expect(")");
1473     script->seenRelroEnd = true;
1474     return [=] { return alignToPowerOf2(script->getDot(), config->maxPageSize); };
1475   }
1476   if (tok == "DEFINED") {
1477     StringRef name = unquote(readParenLiteral());
1478     // Return 1 if s is defined. If the definition is only found in a linker
1479     // script, it must happen before this DEFINED.
1480     auto order = ctx.scriptSymOrderCounter++;
1481     return [=] {
1482       Symbol *s = symtab.find(name);
1483       return s && s->isDefined() && ctx.scriptSymOrder.lookup(s) < order ? 1
1484                                                                          : 0;
1485     };
1486   }
1487   if (tok == "LENGTH") {
1488     StringRef name = readParenLiteral();
1489     if (script->memoryRegions.count(name) == 0) {
1490       setError("memory region not defined: " + name);
1491       return [] { return 0; };
1492     }
1493     return script->memoryRegions[name]->length;
1494   }
1495   if (tok == "LOADADDR") {
1496     StringRef name = unquote(readParenLiteral());
1497     OutputSection *osec = &script->getOrCreateOutputSection(name)->osec;
1498     osec->usedInExpression = true;
1499     return [=] {
1500       checkIfExists(*osec, location);
1501       return osec->getLMA();
1502     };
1503   }
1504   if (tok == "LOG2CEIL") {
1505     expect("(");
1506     Expr a = readExpr();
1507     expect(")");
1508     return [=] {
1509       // LOG2CEIL(0) is defined to be 0.
1510       return llvm::Log2_64_Ceil(std::max(a().getValue(), UINT64_C(1)));
1511     };
1512   }
1513   if (tok == "MAX" || tok == "MIN") {
1514     expect("(");
1515     Expr a = readExpr();
1516     expect(",");
1517     Expr b = readExpr();
1518     expect(")");
1519     if (tok == "MIN")
1520       return [=] { return std::min(a().getValue(), b().getValue()); };
1521     return [=] { return std::max(a().getValue(), b().getValue()); };
1522   }
1523   if (tok == "ORIGIN") {
1524     StringRef name = readParenLiteral();
1525     if (script->memoryRegions.count(name) == 0) {
1526       setError("memory region not defined: " + name);
1527       return [] { return 0; };
1528     }
1529     return script->memoryRegions[name]->origin;
1530   }
1531   if (tok == "SEGMENT_START") {
1532     expect("(");
1533     skip();
1534     expect(",");
1535     Expr e = readExpr();
1536     expect(")");
1537     return [=] { return e(); };
1538   }
1539   if (tok == "SIZEOF") {
1540     StringRef name = unquote(readParenLiteral());
1541     OutputSection *cmd = &script->getOrCreateOutputSection(name)->osec;
1542     // Linker script does not create an output section if its content is empty.
1543     // We want to allow SIZEOF(.foo) where .foo is a section which happened to
1544     // be empty.
1545     return [=] { return cmd->size; };
1546   }
1547   if (tok == "SIZEOF_HEADERS")
1548     return [=] { return elf::getHeaderSize(); };
1549 
1550   // Tok is the dot.
1551   if (tok == ".")
1552     return [=] { return script->getSymbolValue(tok, location); };
1553 
1554   // Tok is a literal number.
1555   if (std::optional<uint64_t> val = parseInt(tok))
1556     return [=] { return *val; };
1557 
1558   // Tok is a symbol name.
1559   if (tok.starts_with("\""))
1560     tok = unquote(tok);
1561   else if (!isValidSymbolName(tok))
1562     setError("malformed number: " + tok);
1563   script->referencedSymbols.push_back(tok);
1564   return [=] { return script->getSymbolValue(tok, location); };
1565 }
1566 
readTernary(Expr cond)1567 Expr ScriptParser::readTernary(Expr cond) {
1568   Expr l = readExpr();
1569   expect(":");
1570   Expr r = readExpr();
1571   return [=] { return cond().getValue() ? l() : r(); };
1572 }
1573 
readParenExpr()1574 Expr ScriptParser::readParenExpr() {
1575   expect("(");
1576   Expr e = readExpr();
1577   expect(")");
1578   return e;
1579 }
1580 
readOutputSectionPhdrs()1581 SmallVector<StringRef, 0> ScriptParser::readOutputSectionPhdrs() {
1582   SmallVector<StringRef, 0> phdrs;
1583   while (!errorCount() && peek().starts_with(":")) {
1584     StringRef tok = next();
1585     phdrs.push_back((tok.size() == 1) ? next() : tok.substr(1));
1586   }
1587   return phdrs;
1588 }
1589 
1590 // Read a program header type name. The next token must be a
1591 // name of a program header type or a constant (e.g. "0x3").
readPhdrType()1592 unsigned ScriptParser::readPhdrType() {
1593   StringRef tok = next();
1594   if (std::optional<uint64_t> val = parseInt(tok))
1595     return *val;
1596 
1597   unsigned ret = StringSwitch<unsigned>(tok)
1598                      .Case("PT_NULL", PT_NULL)
1599                      .Case("PT_LOAD", PT_LOAD)
1600                      .Case("PT_DYNAMIC", PT_DYNAMIC)
1601                      .Case("PT_INTERP", PT_INTERP)
1602                      .Case("PT_NOTE", PT_NOTE)
1603                      .Case("PT_SHLIB", PT_SHLIB)
1604                      .Case("PT_PHDR", PT_PHDR)
1605                      .Case("PT_TLS", PT_TLS)
1606                      .Case("PT_GNU_EH_FRAME", PT_GNU_EH_FRAME)
1607                      .Case("PT_GNU_STACK", PT_GNU_STACK)
1608                      .Case("PT_GNU_RELRO", PT_GNU_RELRO)
1609                      .Case("PT_OPENBSD_RANDOMIZE", PT_OPENBSD_RANDOMIZE)
1610                      .Case("PT_OPENBSD_WXNEEDED", PT_OPENBSD_WXNEEDED)
1611                      .Case("PT_OPENBSD_BOOTDATA", PT_OPENBSD_BOOTDATA)
1612                      .Default(-1);
1613 
1614   if (ret == (unsigned)-1) {
1615     setError("invalid program header type: " + tok);
1616     return PT_NULL;
1617   }
1618   return ret;
1619 }
1620 
1621 // Reads an anonymous version declaration.
readAnonymousDeclaration()1622 void ScriptParser::readAnonymousDeclaration() {
1623   SmallVector<SymbolVersion, 0> locals;
1624   SmallVector<SymbolVersion, 0> globals;
1625   std::tie(locals, globals) = readSymbols();
1626   for (const SymbolVersion &pat : locals)
1627     config->versionDefinitions[VER_NDX_LOCAL].localPatterns.push_back(pat);
1628   for (const SymbolVersion &pat : globals)
1629     config->versionDefinitions[VER_NDX_GLOBAL].nonLocalPatterns.push_back(pat);
1630 
1631   expect(";");
1632 }
1633 
1634 // Reads a non-anonymous version definition,
1635 // e.g. "VerStr { global: foo; bar; local: *; };".
readVersionDeclaration(StringRef verStr)1636 void ScriptParser::readVersionDeclaration(StringRef verStr) {
1637   // Read a symbol list.
1638   SmallVector<SymbolVersion, 0> locals;
1639   SmallVector<SymbolVersion, 0> globals;
1640   std::tie(locals, globals) = readSymbols();
1641 
1642   // Create a new version definition and add that to the global symbols.
1643   VersionDefinition ver;
1644   ver.name = verStr;
1645   ver.nonLocalPatterns = std::move(globals);
1646   ver.localPatterns = std::move(locals);
1647   ver.id = config->versionDefinitions.size();
1648   config->versionDefinitions.push_back(ver);
1649 
1650   // Each version may have a parent version. For example, "Ver2"
1651   // defined as "Ver2 { global: foo; local: *; } Ver1;" has "Ver1"
1652   // as a parent. This version hierarchy is, probably against your
1653   // instinct, purely for hint; the runtime doesn't care about it
1654   // at all. In LLD, we simply ignore it.
1655   if (next() != ";")
1656     expect(";");
1657 }
1658 
hasWildcard(StringRef s)1659 bool elf::hasWildcard(StringRef s) {
1660   return s.find_first_of("?*[") != StringRef::npos;
1661 }
1662 
1663 // Reads a list of symbols, e.g. "{ global: foo; bar; local: *; };".
1664 std::pair<SmallVector<SymbolVersion, 0>, SmallVector<SymbolVersion, 0>>
readSymbols()1665 ScriptParser::readSymbols() {
1666   SmallVector<SymbolVersion, 0> locals;
1667   SmallVector<SymbolVersion, 0> globals;
1668   SmallVector<SymbolVersion, 0> *v = &globals;
1669 
1670   while (!errorCount()) {
1671     if (consume("}"))
1672       break;
1673     if (consumeLabel("local")) {
1674       v = &locals;
1675       continue;
1676     }
1677     if (consumeLabel("global")) {
1678       v = &globals;
1679       continue;
1680     }
1681 
1682     if (consume("extern")) {
1683       SmallVector<SymbolVersion, 0> ext = readVersionExtern();
1684       v->insert(v->end(), ext.begin(), ext.end());
1685     } else {
1686       StringRef tok = next();
1687       v->push_back({unquote(tok), false, hasWildcard(tok)});
1688     }
1689     expect(";");
1690   }
1691   return {locals, globals};
1692 }
1693 
1694 // Reads an "extern C++" directive, e.g.,
1695 // "extern "C++" { ns::*; "f(int, double)"; };"
1696 //
1697 // The last semicolon is optional. E.g. this is OK:
1698 // "extern "C++" { ns::*; "f(int, double)" };"
readVersionExtern()1699 SmallVector<SymbolVersion, 0> ScriptParser::readVersionExtern() {
1700   StringRef tok = next();
1701   bool isCXX = tok == "\"C++\"";
1702   if (!isCXX && tok != "\"C\"")
1703     setError("Unknown language");
1704   expect("{");
1705 
1706   SmallVector<SymbolVersion, 0> ret;
1707   while (!errorCount() && peek() != "}") {
1708     StringRef tok = next();
1709     ret.push_back(
1710         {unquote(tok), isCXX, !tok.starts_with("\"") && hasWildcard(tok)});
1711     if (consume("}"))
1712       return ret;
1713     expect(";");
1714   }
1715 
1716   expect("}");
1717   return ret;
1718 }
1719 
readMemoryAssignment(StringRef s1,StringRef s2,StringRef s3)1720 Expr ScriptParser::readMemoryAssignment(StringRef s1, StringRef s2,
1721                                         StringRef s3) {
1722   if (!consume(s1) && !consume(s2) && !consume(s3)) {
1723     setError("expected one of: " + s1 + ", " + s2 + ", or " + s3);
1724     return [] { return 0; };
1725   }
1726   expect("=");
1727   return readExpr();
1728 }
1729 
1730 // Parse the MEMORY command as specified in:
1731 // https://sourceware.org/binutils/docs/ld/MEMORY.html
1732 //
1733 // MEMORY { name [(attr)] : ORIGIN = origin, LENGTH = len ... }
readMemory()1734 void ScriptParser::readMemory() {
1735   expect("{");
1736   while (!errorCount() && !consume("}")) {
1737     StringRef tok = next();
1738     if (tok == "INCLUDE") {
1739       readInclude();
1740       continue;
1741     }
1742 
1743     uint32_t flags = 0;
1744     uint32_t invFlags = 0;
1745     uint32_t negFlags = 0;
1746     uint32_t negInvFlags = 0;
1747     if (consume("(")) {
1748       readMemoryAttributes(flags, invFlags, negFlags, negInvFlags);
1749       expect(")");
1750     }
1751     expect(":");
1752 
1753     Expr origin = readMemoryAssignment("ORIGIN", "org", "o");
1754     expect(",");
1755     Expr length = readMemoryAssignment("LENGTH", "len", "l");
1756 
1757     // Add the memory region to the region map.
1758     MemoryRegion *mr = make<MemoryRegion>(tok, origin, length, flags, invFlags,
1759                                           negFlags, negInvFlags);
1760     if (!script->memoryRegions.insert({tok, mr}).second)
1761       setError("region '" + tok + "' already defined");
1762   }
1763 }
1764 
1765 // This function parses the attributes used to match against section
1766 // flags when placing output sections in a memory region. These flags
1767 // are only used when an explicit memory region name is not used.
readMemoryAttributes(uint32_t & flags,uint32_t & invFlags,uint32_t & negFlags,uint32_t & negInvFlags)1768 void ScriptParser::readMemoryAttributes(uint32_t &flags, uint32_t &invFlags,
1769                                         uint32_t &negFlags,
1770                                         uint32_t &negInvFlags) {
1771   bool invert = false;
1772 
1773   for (char c : next().lower()) {
1774     if (c == '!') {
1775       invert = !invert;
1776       std::swap(flags, negFlags);
1777       std::swap(invFlags, negInvFlags);
1778       continue;
1779     }
1780     if (c == 'w')
1781       flags |= SHF_WRITE;
1782     else if (c == 'x')
1783       flags |= SHF_EXECINSTR;
1784     else if (c == 'a')
1785       flags |= SHF_ALLOC;
1786     else if (c == 'r')
1787       invFlags |= SHF_WRITE;
1788     else
1789       setError("invalid memory region attribute");
1790   }
1791 
1792   if (invert) {
1793     std::swap(flags, negFlags);
1794     std::swap(invFlags, negInvFlags);
1795   }
1796 }
1797 
readLinkerScript(MemoryBufferRef mb)1798 void elf::readLinkerScript(MemoryBufferRef mb) {
1799   llvm::TimeTraceScope timeScope("Read linker script",
1800                                  mb.getBufferIdentifier());
1801   ScriptParser(mb).readLinkerScript();
1802 }
1803 
readVersionScript(MemoryBufferRef mb)1804 void elf::readVersionScript(MemoryBufferRef mb) {
1805   llvm::TimeTraceScope timeScope("Read version script",
1806                                  mb.getBufferIdentifier());
1807   ScriptParser(mb).readVersionScript();
1808 }
1809 
readDynamicList(MemoryBufferRef mb)1810 void elf::readDynamicList(MemoryBufferRef mb) {
1811   llvm::TimeTraceScope timeScope("Read dynamic list", mb.getBufferIdentifier());
1812   ScriptParser(mb).readDynamicList();
1813 }
1814 
readDefsym(StringRef name,MemoryBufferRef mb)1815 void elf::readDefsym(StringRef name, MemoryBufferRef mb) {
1816   llvm::TimeTraceScope timeScope("Read defsym input", name);
1817   ScriptParser(mb).readDefsym(name);
1818 }
1819