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