Index: ELF/InputSection.cpp =================================================================== --- ELF/InputSection.cpp +++ ELF/InputSection.cpp @@ -29,8 +29,7 @@ using namespace lld::elf; template bool elf::isDiscarded(InputSectionBase *S) { - return !S || S == &InputSection::Discarded || !S->Live || - Script::X->isDiscarded(S); + return !S || S == &InputSection::Discarded || !S->Live; } template Index: ELF/LinkerScript.h =================================================================== --- ELF/LinkerScript.h +++ ELF/LinkerScript.h @@ -10,11 +10,13 @@ #ifndef LLD_ELF_LINKER_SCRIPT_H #define LLD_ELF_LINKER_SCRIPT_H +#include "ScriptParser.h" #include "lld/Core/LLVM.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/MapVector.h" #include "llvm/Support/Allocator.h" #include "llvm/Support/MemoryBuffer.h" +#include namespace lld { namespace elf { @@ -25,47 +27,60 @@ class ScriptParser; template class InputSectionBase; +template class ObjectFile; template class OutputSectionBase; +template class OutputSectionFactory; +template class SymbolTable; -// This class represents each rule in SECTIONS command. -struct SectionRule { - SectionRule(StringRef D, StringRef S) - : Dest(D), SectionPattern(S) {} - - StringRef Dest; - - StringRef SectionPattern; +enum CommandKind { + ExprKind, + OutSectionKind, + InputSectionKind, + FillerKind, }; -// This enum represents what we can observe in SECTIONS tag of script: -// ExprKind is a location counter change, like ". = . + 0x1000" -// SectionKind is a description of output section, like ".data :..." -enum SectionsCommandKind { ExprKind, SectionKind, SymbolAssignmentKind }; - -struct SectionsCommand { - SectionsCommandKind Kind; +struct Command { + CommandKind Kind; std::vector Expr; StringRef Name; + StringRef Pattern; + bool Keep; + std::vector Filler; + + static Command createExprCmd(std::vector &Expr) { + return Command{ExprKind, Expr, "", "", false, {}}; + } + static Command createOutSecCmd(StringRef Name) { + return Command{OutSectionKind, {}, Name, "", false, {}}; + } + static Command createInputSectionCmd(StringRef Pattern, bool Keep) { + return Command{InputSectionKind, {}, "", Pattern, Keep, {}}; + } + static Command createFillerCmd(std::vector &Filler) { + return Command{FillerKind, {}, "", "", false, std::move(Filler)}; + } }; -// ScriptConfiguration holds linker script parse results. -struct ScriptConfiguration { - // SECTIONS commands. - std::vector Sections; +class LayoutParser : public ScriptParserBase { +public: + LayoutParser(StringRef Data) : ScriptParserBase(Data) {} - // Section fill attribute for each section. - llvm::StringMap> Filler; + size_t createLayout(); - // Used to assign addresses to sections. - std::vector Commands; + void parseLocationCounterValue(); + void parseOutputSectionDescription(); + + std::vector Commands; +}; +// ScriptConfiguration holds linker script parse results. +struct ScriptConfiguration { bool DoLayout = false; + StringRef SectionsData; - llvm::BumpPtrAllocator Alloc; + std::unique_ptr LayoutParser; - // List of section patterns specified with KEEP commands. They will - // be kept even if they are unused and --gc-sections is specified. - std::vector KeptSections; + llvm::BumpPtrAllocator Alloc; }; extern ScriptConfiguration *ScriptConfig; @@ -75,20 +90,18 @@ typedef typename ELFT::uint uintX_t; public: - StringRef getOutputSection(InputSectionBase *S); - ArrayRef getFiller(StringRef Name); - bool isDiscarded(InputSectionBase *S); - bool shouldKeep(InputSectionBase *S); void assignAddresses(ArrayRef *> S); - int compareSections(StringRef A, StringRef B); - void addScriptedSymbols(); + + std::vector *> + createSections(OutputSectionFactory &Factory, + SymbolTable &SymTab); + + bool shouldKeep(InputSectionBase *Sec); private: // "ScriptConfig" is a bit too long, so define a short name for it. ScriptConfiguration &Opt = *ScriptConfig; - int getSectionIndex(StringRef Name); - uintX_t Dot; }; Index: ELF/LinkerScript.cpp =================================================================== --- ELF/LinkerScript.cpp +++ ELF/LinkerScript.cpp @@ -22,6 +22,7 @@ #include "Strings.h" #include "Symbols.h" #include "SymbolTable.h" +#include "Writer.h" #include "Target.h" #include "llvm/ADT/StringSwitch.h" #include "llvm/Support/ELF.h" @@ -45,7 +46,7 @@ namespace { class ExprParser : public ScriptParserBase { public: - ExprParser(std::vector &Tokens, uint64_t Dot) + ExprParser(const std::vector &Tokens, uint64_t Dot) : ScriptParserBase(Tokens), Dot(Dot) {} uint64_t run(); @@ -77,7 +78,7 @@ .Default(-1); } -static uint64_t evalExpr(std::vector &Tokens, uint64_t Dot) { +static uint64_t evalExpr(const std::vector &Tokens, uint64_t Dot) { return ExprParser(Tokens, Dot).run(); } @@ -187,133 +188,219 @@ uint64_t ExprParser::parseExpr() { return parseExpr1(parsePrimary(), 0); } template -StringRef LinkerScript::getOutputSection(InputSectionBase *S) { - for (SectionRule &R : Opt.Sections) - if (globMatch(R.SectionPattern, S->getSectionName())) - return R.Dest; - return ""; +static OutputSectionBase * +findSection(ArrayRef *> V, StringRef Name) { + for (OutputSectionBase *Sec : V) + if (Sec->getName() == Name) + return Sec; + return nullptr; } -template -bool LinkerScript::isDiscarded(InputSectionBase *S) { - return getOutputSection(S) == "/DISCARD/"; +size_t LayoutParser::createLayout() { + if (!Tokens.size()) + return 0; + + expect("SECTIONS"); + expect("{"); + while (!Error && !skip("}")) { + StringRef Tok = peek(); + if (Tok == ".") + parseLocationCounterValue(); + else + parseOutputSectionDescription(); + } + + return Pos - 1; +} + +void LayoutParser::parseLocationCounterValue() { + expect("."); + expect("="); + + std::vector Expr; + while (!Error) { + StringRef Tok = next(); + if (Tok == ";") + break; + Expr.push_back(Tok); + } + if (Expr.empty()) + error("error in location counter expression"); + Commands.push_back(Command::createExprCmd(Expr)); +} + +void LayoutParser::parseOutputSectionDescription() { + StringRef OutSec = next(); + Commands.push_back(Command::createOutSecCmd(OutSec)); + expect(":"); + expect("{"); + + while (!Error && !skip("}")) { + StringRef Tok = next(); + if (Tok == "*") { + expect("("); + while (!Error && !skip(")")) + Commands.push_back(Command::createInputSectionCmd(next(), false)); + } else if (Tok == "KEEP") { + expect("("); + expect("*"); + expect("("); + while (!Error && !skip(")")) + Commands.push_back(Command::createInputSectionCmd(next(), true)); + expect(")"); + } else { + setError("unknown command " + Tok); + } + } + + if (Error) + return; + + StringRef Tok = peek(); + std::vector Filler; + if (Tok.startswith("=")) { + if (!Tok.startswith("=0x")) { + setError("filler should be a hexadecimal value"); + return; + } + Tok = Tok.substr(3); + Filler = parseHex(Tok); + next(); + Commands.push_back(Command::createFillerCmd(Filler)); + } } template -bool LinkerScript::shouldKeep(InputSectionBase *S) { - for (StringRef Pat : Opt.KeptSections) - if (globMatch(Pat, S->getSectionName())) - return true; - return false; +static void addSection(OutputSectionFactory &Factory, + StringRef OutSecName, InputSectionBase *InSec, + std::vector *> &List) { + if (OutSecName == "/DISCARD/" || !InSec->Live) + return; + + OutputSectionBase *OutSection = nullptr; + bool IsNew; + std::tie(OutSection, IsNew) = Factory.create(InSec, OutSecName); + OutSection->addSection(InSec); + if (IsNew) + List.push_back(OutSection); } template -void LinkerScript::assignAddresses( - ArrayRef *> Sections) { +std::vector *> +LinkerScript::createSections(OutputSectionFactory &Factory, + SymbolTable &Symtab) { + // Create a list of input sections that were not assigned to output yet. + std::vector *> Unassigned; + for (const std::unique_ptr> &F : + Symtab.getObjectFiles()) { + for (InputSectionBase *C : F->getSections()) + if (!isDiscarded(C)) + Unassigned.push_back(C); + } + + std::vector *> Sections; + StringRef OutSecName; + OutputSectionBase *OutSection = nullptr; + + for (const Command &Cmd : Opt.LayoutParser->Commands) { + if (Cmd.Kind == OutSectionKind) { + OutSecName = Cmd.Name; + continue; + } + if (OutSection && Cmd.Kind == FillerKind) { + OutSection->Filler = Cmd.Filler; + continue; + } + + if (Cmd.Kind != InputSectionKind) + continue; + + auto I = std::find_if(Unassigned.begin(), Unassigned.end(), + [&](InputSectionBase *S) { + return globMatch(Cmd.Pattern, S->getSectionName()); + }); + if (I == Unassigned.end()) + continue; + + InputSectionBase *InSec = *I; + Unassigned.erase(I); + addSection(Factory, OutSecName, InSec, Sections); + } + // Orphan sections are sections present in the input files which // are not explicitly placed into the output file by the linker script. // We place orphan sections at end of file. // Other linkers places them using some heuristics as described in // https://sourceware.org/binutils/docs/ld/Orphan-Sections.html#Orphan-Sections. - for (OutputSectionBase *Sec : Sections) { - StringRef Name = Sec->getName(); - if (getSectionIndex(Name) == INT_MAX) - Opt.Commands.push_back({SectionKind, {}, Name}); - } + for (InputSectionBase *U : Unassigned) + addSection(Factory, getOutputSectionName(U), U, Sections); + return Sections; +} + +template +void LinkerScript::assignAddresses( + ArrayRef *> Sections) { // Assign addresses as instructed by linker script SECTIONS sub-commands. Dot = Out::ElfHeader->getSize() + Out::ProgramHeaders->getSize(); - uintX_t MinVA = std::numeric_limits::max(); uintX_t ThreadBssOffset = 0; - for (SectionsCommand &Cmd : Opt.Commands) { - switch (Cmd.Kind) { - case ExprKind: - Dot = evalExpr(Cmd.Expr, Dot); - continue; - case SymbolAssignmentKind: { - auto *D = - cast>(Symtab::X->find(Cmd.Name)); - D->Value = evalExpr(Cmd.Expr, Dot); - continue; + DenseSet *> Assigned; + auto Assign = [&](StringRef Name) { + OutputSectionBase *Sec = findSection(Sections, Name); + + if (!Sec) + return; + + if ((Sec->getFlags() & SHF_TLS) && Sec->getType() == SHT_NOBITS) { + uintX_t TVA = Dot + ThreadBssOffset; + TVA = alignTo(TVA, Sec->getAlignment()); + Sec->setVA(TVA); + ThreadBssOffset = TVA - Dot + Sec->getSize(); + Assigned.insert(Sec); + return; } - default: - break; + + if (Sec->getFlags() & SHF_ALLOC) { + Dot = alignTo(Dot, Sec->getAlignment()); + Sec->setVA(Dot); + Dot += Sec->getSize(); + Assigned.insert(Sec); + return; } + }; - // Find all the sections with required name. There can be more than - // ont section with such name, if the alignment, flags or type - // attribute differs. - for (OutputSectionBase *Sec : Sections) { - if (Sec->getName() != Cmd.Name) - continue; - - if ((Sec->getFlags() & SHF_TLS) && Sec->getType() == SHT_NOBITS) { - uintX_t TVA = Dot + ThreadBssOffset; - TVA = alignTo(TVA, Sec->getAlignment()); - Sec->setVA(TVA); - ThreadBssOffset = TVA - Dot + Sec->getSize(); - continue; - } - - if (Sec->getFlags() & SHF_ALLOC) { - Dot = alignTo(Dot, Sec->getAlignment()); - Sec->setVA(Dot); - MinVA = std::min(MinVA, Dot); - Dot += Sec->getSize(); - continue; - } + for (const Command &Cmd : Opt.LayoutParser->Commands) { + if (Cmd.Kind == ExprKind) { + Dot = evalExpr(Cmd.Expr, Dot); + continue; } + if (Cmd.Kind != OutSectionKind) + continue; + Assign(Cmd.Name); } - // ELF and Program headers need to be right before the first section in - // memory. - // Set their addresses accordingly. - MinVA = alignDown(MinVA - Out::ElfHeader->getSize() - - Out::ProgramHeaders->getSize(), - Target->PageSize); - Out::ElfHeader->setVA(MinVA); - Out::ProgramHeaders->setVA(Out::ElfHeader->getSize() + MinVA); -} - -template -ArrayRef LinkerScript::getFiller(StringRef Name) { - auto I = Opt.Filler.find(Name); - if (I == Opt.Filler.end()) - return {}; - return I->second; -} - -// Returns the index of the given section name in linker script -// SECTIONS commands. Sections are laid out as the same order as they -// were in the script. If a given name did not appear in the script, -// it returns INT_MAX, so that it will be laid out at end of file. -template -int LinkerScript::getSectionIndex(StringRef Name) { - auto Begin = Opt.Commands.begin(); - auto End = Opt.Commands.end(); - auto I = std::find_if(Begin, End, [&](SectionsCommand &N) { - return N.Kind == SectionKind && N.Name == Name; - }); - return I == End ? INT_MAX : (I - Begin); -} - -// A compartor to sort output sections. Returns -1 or 1 if -// A or B are mentioned in linker script. Otherwise, returns 0. -template -int LinkerScript::compareSections(StringRef A, StringRef B) { - int I = getSectionIndex(A); - int J = getSectionIndex(B); - if (I == INT_MAX && J == INT_MAX) - return 0; - return I < J ? -1 : 1; + // Finally process all orphan sections. + for (OutputSectionBase *Sec : Sections) + if (!Assigned.count(Sec)) { + Assigned.insert(Sec); + Assign(Sec->getName()); + } } template -void LinkerScript::addScriptedSymbols() { - for (SectionsCommand &Cmd : Opt.Commands) - if (Cmd.Kind == SymbolAssignmentKind) - Symtab::X->addAbsolute(Cmd.Name, STV_DEFAULT); +bool LinkerScript::shouldKeep(InputSectionBase *Sec) { + if (!Opt.LayoutParser) + return false; + for (const Command &Cmd : Opt.LayoutParser->Commands) { + if (Cmd.Kind != InputSectionKind) + continue; + if (!Cmd.Keep) + continue; + if (globMatch(Cmd.Pattern, Sec->getSectionName())) + return true; + } + return false; } class elf::ScriptParser : public ScriptParserBase { @@ -339,9 +426,6 @@ void readSearchDir(); void readSections(); - void readLocationCounterValue(); - void readOutputSectionDescription(StringRef OutSec); - void readSymbolAssignment(StringRef Name); std::vector readSectionsCommandExpr(); const static StringMap Cmd; @@ -503,76 +587,10 @@ void ScriptParser::readSections() { Opt.DoLayout = true; - expect("{"); - while (!Error && !skip("}")) { - StringRef Tok = peek(); - if (Tok == ".") { - readLocationCounterValue(); - continue; - } - next(); - if (peek() == "=") - readSymbolAssignment(Tok); - else - readOutputSectionDescription(Tok); - } -} - -void ScriptParser::readLocationCounterValue() { - expect("."); - expect("="); - std::vector Expr = readSectionsCommandExpr(); - if (Expr.empty()) - error("error in location counter expression"); - else - Opt.Commands.push_back({ExprKind, std::move(Expr), ""}); -} - -void ScriptParser::readOutputSectionDescription(StringRef OutSec) { - Opt.Commands.push_back({SectionKind, {}, OutSec}); - expect(":"); - expect("{"); - - while (!Error && !skip("}")) { - StringRef Tok = next(); - if (Tok == "*") { - expect("("); - while (!Error && !skip(")")) - Opt.Sections.emplace_back(OutSec, next()); - } else if (Tok == "KEEP") { - expect("("); - expect("*"); - expect("("); - while (!Error && !skip(")")) { - StringRef Sec = next(); - Opt.Sections.emplace_back(OutSec, Sec); - Opt.KeptSections.push_back(Sec); - } - expect(")"); - } else { - setError("unknown command " + Tok); - } - } + StringRef SectionsData = Input.drop_front(Tokens[Pos - 1].begin() - Input.begin()); - StringRef Tok = peek(); - if (Tok.startswith("=")) { - if (!Tok.startswith("=0x")) { - setError("filler should be a hexadecimal value"); - return; - } - Tok = Tok.substr(3); - Opt.Filler[OutSec] = parseHex(Tok); - next(); - } -} - -void ScriptParser::readSymbolAssignment(StringRef Name) { - expect("="); - std::vector Expr = readSectionsCommandExpr(); - if (Expr.empty()) - error("error in symbol assignment expression"); - else - Opt.Commands.push_back({SymbolAssignmentKind, std::move(Expr), Name}); + Opt.LayoutParser = std::make_unique(SectionsData); + Pos += Opt.LayoutParser->createLayout(); } std::vector ScriptParser::readSectionsCommandExpr() { Index: ELF/OutputSections.h =================================================================== --- ELF/OutputSections.h +++ ELF/OutputSections.h @@ -88,6 +88,8 @@ virtual void writeTo(uint8_t *Buf) {} virtual ~OutputSectionBase() = default; + std::vector Filler; + protected: StringRef Name; Elf_Shdr Header; Index: ELF/OutputSections.cpp =================================================================== --- ELF/OutputSections.cpp +++ ELF/OutputSections.cpp @@ -947,7 +947,6 @@ } template void OutputSection::writeTo(uint8_t *Buf) { - ArrayRef Filler = Script::X->getFiller(this->Name); if (!Filler.empty()) fill(Buf, this->getSize(), Filler); if (Config->Threads) { Index: ELF/Writer.cpp =================================================================== --- ELF/Writer.cpp +++ ELF/Writer.cpp @@ -59,7 +59,11 @@ void copyLocalSymbols(); void addReservedSymbols(); + + std::vector *> + createRegularSections(OutputSectionFactory &Factory); void createSections(); + void addPredefinedSections(); bool needsGot(); @@ -103,10 +107,6 @@ template StringRef elf::getOutputSectionName(InputSectionBase *S) { - StringRef Dest = Script::X->getOutputSection(S); - if (!Dest.empty()) - return Dest; - StringRef Name = S->getSectionName(); for (StringRef V : {".text.", ".rodata.", ".data.rel.ro.", ".data.", ".bss.", ".init_array.", ".fini_array.", ".ctors.", ".dtors.", @@ -402,10 +402,6 @@ OutputSectionBase *B) { typedef typename ELFT::uint uintX_t; - int Comp = Script::X->compareSections(A->getName(), B->getName()); - if (Comp != 0) - return Comp < 0; - uintX_t AFlags = A->getFlags(); uintX_t BFlags = B->getFlags(); @@ -602,11 +598,15 @@ reinterpret_cast *>(S)->sortCtorsDtors(); } -// Create output section objects and add them to OutputSections. -template void Writer::createSections() { +template +std::vector *> +Writer::createRegularSections(OutputSectionFactory &Factory) { + if (ScriptConfig->DoLayout) + return Script::X->createSections(Factory, Symtab); + // Create output sections for input object file sections. std::vector *> RegularSections; - OutputSectionFactory Factory; + for (const std::unique_ptr> &F : Symtab.getObjectFiles()) { for (InputSectionBase *C : F->getSections()) { @@ -617,14 +617,23 @@ OutputSectionBase *Sec; bool IsNew; std::tie(Sec, IsNew) = Factory.create(C, getOutputSectionName(C)); - if (IsNew) { - OwningSections.emplace_back(Sec); - OutputSections.push_back(Sec); + if (IsNew) RegularSections.push_back(Sec); - } Sec->addSection(C); } } + return RegularSections; +} + +// Create output section objects and add them to OutputSections. +template void Writer::createSections() { + OutputSectionFactory Factory; + std::vector *> RegularSections = + createRegularSections(Factory); + for (OutputSectionBase *Sec : RegularSections) { + OwningSections.emplace_back(Sec); + OutputSections.push_back(Sec); + } // If we have a .opd section (used under PPC64 for function descriptors), // store a pointer to it here so that we can use it later when processing @@ -663,10 +672,6 @@ // Define __rel[a]_iplt_{start,end} symbols if needed. addRelIpltSymbols(); - // Add scripted symbols with zero values now. - // Real values will be assigned later - Script::X->addScriptedSymbols(); - if (!Out::EhFrame->empty()) { OutputSections.push_back(Out::EhFrame); Out::EhFrame->finalize();