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