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,6 +10,7 @@ #ifndef LLD_ELF_LINKER_SCRIPT_H #define LLD_ELF_LINKER_SCRIPT_H +#include "ScriptParser.h" #include "Writer.h" #include "lld/Core/LLVM.h" #include "llvm/ADT/DenseMap.h" @@ -26,28 +27,51 @@ 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 { + AssignmentKind, + OutSectionKind, + OutSectionEndKind, + InputSectionKind, + FillerKind, + PhdrsKind, }; -// 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 { SectionKind, AssignmentKind }; - -struct SectionsCommand { - SectionsCommandKind Kind; +struct Command { + CommandKind Kind; std::vector Expr; StringRef Name; + StringRef Pattern; + bool Keep; + std::vector Filler; std::vector Phdrs; + + static Command createAssignmentCmd(std::vector &Expr) { + return Command{AssignmentKind, Expr, ".", "", false, {}, {}}; + } + static Command createSymbolAssignmentCmd(std::vector &Expr, + StringRef Name) { + return Command{AssignmentKind, Expr, Name, "", false, {}, {}}; + } + static Command createOutSecCmd(StringRef Name) { + return Command{OutSectionKind, {}, Name, "", false, {}, {}}; + } + static Command createOutSecEndCmd() { + return Command{OutSectionEndKind, {}, "", "", false, {}, {}}; + } + static Command createInputSectionCmd(StringRef Pattern, bool Keep) { + return Command{InputSectionKind, {}, "", Pattern, Keep, {}, {}}; + } + static Command createFillerCmd(const std::vector &Filler) { + return Command{FillerKind, {}, "", "", false, std::move(Filler), {}}; + } + static Command createPhdrsCmd(const std::vector &Phdrs) { + return Command{PhdrsKind, {}, "", "", false, {}, std::move(Phdrs)}; + } }; struct PhdrsCommand { @@ -59,25 +83,15 @@ // ScriptConfiguration holds linker script parse results. struct ScriptConfiguration { - // SECTIONS commands. - std::vector Sections; - - // Section fill attribute for each section. - llvm::StringMap> Filler; + bool DoLayout = false; - // Used to assign addresses to sections. - std::vector Commands; + // Used to handle SECTIONS commands for layout. + std::vector Commands; // Used to assign sections to headers. - std::vector PhdrsCommands; - - bool DoLayout = false; + std::vector PhdrsCommands; llvm::BumpPtrAllocator Alloc; - - // 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; }; extern ScriptConfiguration *ScriptConfig; @@ -85,16 +99,20 @@ // This is a runner of the linker script. template class LinkerScript { typedef typename ELFT::uint uintX_t; + typedef const std::unique_ptr> ObjectFile; public: typedef PhdrEntry Phdr; - 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); + + std::vector *> + createSections(OutputSectionFactory &Factory, + SymbolTable &SymTab); + + void sortSections(std::vector *> &S); + void addScriptedSymbols(); std::vector createPhdrs(ArrayRef *> S); bool hasPhdrsCommands(); @@ -104,6 +122,11 @@ ScriptConfiguration &Opt = *ScriptConfig; int getSectionIndex(StringRef Name); + void createOutputSection(OutputSectionFactory &Factory, + SymbolTable &Symtab, + std::vector *> &OutList, + size_t Ndx); + std::vector getPhdrIndicesForSection(StringRef Name); uintX_t Dot; Index: ELF/LinkerScript.cpp =================================================================== --- ELF/LinkerScript.cpp +++ ELF/LinkerScript.cpp @@ -46,7 +46,7 @@ namespace { class ExprParser : public ScriptParserBase { public: - ExprParser(std::vector &Tokens, uint64_t Dot) + ExprParser(ArrayRef Tokens, uint64_t Dot) : ScriptParserBase(Tokens), Dot(Dot) {} uint64_t run(); @@ -78,7 +78,7 @@ .Default(-1); } -static uint64_t evalExpr(std::vector &Tokens, uint64_t Dot) { +static uint64_t evalExpr(ArrayRef Tokens, uint64_t Dot) { return ExprParser(Tokens, Dot).run(); } @@ -187,46 +187,123 @@ 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 ""; +bool LinkerScript::shouldKeep(InputSectionBase *S) { + if (!Opt.DoLayout) + return false; + for (const Command &Cmd : Opt.Commands) { + if (Cmd.Kind != InputSectionKind) + continue; + if (!Cmd.Keep) + continue; + if (globMatch(Cmd.Pattern, S->getSectionName())) + return true; + } + return false; } template -bool LinkerScript::isDiscarded(InputSectionBase *S) { - return getOutputSection(S) == "/DISCARD/"; +static void addSection(OutputSectionFactory &Factory, + StringRef OutSecName, InputSectionBase *InSec, + std::vector *> &OutList) { + if (OutSecName == "/DISCARD/") { + InSec->Live = false; + return; + } + + OutputSectionBase *OutSection = nullptr; + bool IsNew; + std::tie(OutSection, IsNew) = Factory.create(InSec, OutSecName); + OutSection->addSection(InSec); + if (IsNew) + OutList.push_back(OutSection); } template -bool LinkerScript::shouldKeep(InputSectionBase *S) { - for (StringRef Pat : Opt.KeptSections) - if (globMatch(Pat, S->getSectionName())) - return true; - return false; +void LinkerScript::createOutputSection( + OutputSectionFactory &Factory, SymbolTable &Symtab, + std::vector *> &OutList, size_t Ndx) { + std::vector *Filler = nullptr; + + size_t SecNum = OutList.size(); + for (size_t I = Ndx, E = Opt.Commands.size(); I < E; ++I) { + Command &Cmd = Opt.Commands[I]; + if (Cmd.Kind == OutSectionEndKind) + break; + + if (Cmd.Kind == FillerKind) { + Filler = &Cmd.Filler; + continue; + } + + if (Cmd.Kind != InputSectionKind) + continue; + + for (ObjectFile &F : Symtab.getObjectFiles()) + for (InputSectionBase *C : F->getSections()) + if (!isDiscarded(C) && !C->OutSec) + if (globMatch(Cmd.Pattern, C->getSectionName())) + addSection(Factory, Opt.Commands[Ndx].Name, C, OutList); + } + + for (size_t I = SecNum; I < OutList.size(); ++I) + OutList[I]->Filler = Filler; } template -void LinkerScript::assignAddresses( - ArrayRef *> Sections) { +std::vector *> +LinkerScript::createSections(OutputSectionFactory &Factory, + SymbolTable &Symtab) { + std::vector *> Sections; + for (size_t I = 0, E = Opt.Commands.size(); I != E; ++I) + if (Opt.Commands[I].Kind == OutSectionKind) + createOutputSection(Factory, Symtab, Sections, I); + // 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 (ObjectFile &F : Symtab.getObjectFiles()) + for (InputSectionBase *C : F->getSections()) + if (!isDiscarded(C) && !C->OutSec) + addSection(Factory, getOutputSectionName(C), C, 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; + DenseSet *> Assigned; + + auto setVA = [&](OutputSectionBase *Sec) { + 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; + } - for (SectionsCommand &Cmd : Opt.Commands) { + if (Sec->getFlags() & SHF_ALLOC) { + Dot = alignTo(Dot, Sec->getAlignment()); + Sec->setVA(Dot); + MinVA = std::min(MinVA, Dot); + Dot += Sec->getSize(); + Assigned.insert(Sec); + return; + } + }; + + for (const Command &Cmd : Opt.Commands) { if (Cmd.Kind == AssignmentKind) { uint64_t Val = evalExpr(Cmd.Expr, Dot); @@ -239,32 +316,24 @@ continue; } + if (Cmd.Kind != OutSectionKind) + continue; + // Find all the sections with required name. There can be more than // one section with such name, if the alignment, flags or type // attribute differs. - assert(Cmd.Kind == SectionKind); 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; - } + setVA(Sec); } } + // Finally process all orphan sections. + for (OutputSectionBase *Sec : Sections) + if (!Assigned.count(Sec)) + setVA(Sec); + // ELF and Program headers need to be right before the first section in // memory. Set their addresses accordingly. MinVA = alignDown(MinVA - Out::ElfHeader->getSize() - @@ -359,44 +428,38 @@ return Phdrs; } -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) { +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; + auto I = std::find_if(Begin, End, [&](Command &N) { + return N.Kind == OutSectionKind && 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; +void LinkerScript::sortSections( + std::vector *> &S) { + std::stable_sort(S.begin(), S.end(), [this](OutputSectionBase *A, + OutputSectionBase *B) { + int I = getSectionIndex(A->getName()); + int J = getSectionIndex(B->getName()); + if (I == INT_MAX && J == INT_MAX) + return compareSections(A, B); + return I < J; + }); } -template -void LinkerScript::addScriptedSymbols() { - for (SectionsCommand &Cmd : Opt.Commands) +template void LinkerScript::addScriptedSymbols() { + if (!Opt.DoLayout) + return; + for (Command &Cmd : Opt.Commands) if (Cmd.Kind == AssignmentKind) - if (Cmd.Name != "." && Symtab::X->find(Cmd.Name) == nullptr) + if (Cmd.Name != ".") Symtab::X->addAbsolute(Cmd.Name, STV_DEFAULT); } @@ -410,13 +473,26 @@ template std::vector LinkerScript::getPhdrIndicesForSection(StringRef Name) { - std::vector Indices; - auto ItSect = std::find_if( - Opt.Commands.begin(), Opt.Commands.end(), - [Name](const SectionsCommand &Cmd) { return Cmd.Name == Name; }); - if (ItSect != Opt.Commands.end()) { - SectionsCommand &SecCmd = (*ItSect); - for (StringRef PhdrName : SecCmd.Phdrs) { + auto I = llvm::find_if(Opt.Commands, [&](Command &Cmd) { + return Cmd.Kind == OutSectionKind && Cmd.Name == Name; + }); + + if (I == Opt.Commands.end()) + return {}; + + ++I; + while (I != Opt.Commands.end()) { + Command &Cmd = *I; + if (Cmd.Kind == OutSectionEndKind) + return {}; + + if (Cmd.Kind != PhdrsKind) { + ++I; + continue; + } + + std::vector Indices; + for (StringRef PhdrName : Cmd.Phdrs) { auto ItPhdr = std::find_if( Opt.PhdrsCommands.rbegin(), Opt.PhdrsCommands.rend(), [PhdrName](PhdrsCommand &Cmd) { return Cmd.Name == PhdrName; }); @@ -425,8 +501,10 @@ else Indices.push_back(std::distance(ItPhdr, Opt.PhdrsCommands.rend()) - 1); } + return Indices; } - return Indices; + + return {}; } class elf::ScriptParser : public ScriptParserBase { @@ -664,12 +742,11 @@ if (Expr.empty()) error("error in location counter expression"); else - Opt.Commands.push_back({AssignmentKind, std::move(Expr), ".", {}}); + Opt.Commands.push_back(Command::createAssignmentCmd(Expr)); } void ScriptParser::readOutputSectionDescription(StringRef OutSec) { - Opt.Commands.push_back({SectionKind, {}, OutSec, {}}); - SectionsCommand &Cmd = Opt.Commands.back(); + Opt.Commands.push_back(Command::createOutSecCmd(OutSec)); expect(":"); expect("{"); @@ -678,22 +755,25 @@ if (Tok == "*") { expect("("); while (!Error && !skip(")")) - Opt.Sections.emplace_back(OutSec, next()); + Opt.Commands.push_back(Command::createInputSectionCmd(next(), false)); } else if (Tok == "KEEP") { expect("("); expect("*"); expect("("); - while (!Error && !skip(")")) { - StringRef Sec = next(); - Opt.Sections.emplace_back(OutSec, Sec); - Opt.KeptSections.push_back(Sec); - } + while (!Error && !skip(")")) + Opt.Commands.push_back(Command::createInputSectionCmd(next(), true)); expect(")"); } else { setError("unknown command " + Tok); } } - Cmd.Phdrs = readOutputSectionPhdrs(); + + std::vector Phdrs = readOutputSectionPhdrs(); + if (!Phdrs.empty()) + Opt.Commands.push_back(Command::createPhdrsCmd(Phdrs)); + + if (Error) + return; StringRef Tok = peek(); if (Tok.startswith("=")) { @@ -702,9 +782,11 @@ return; } Tok = Tok.substr(3); - Opt.Filler[OutSec] = parseHex(Tok); next(); + Opt.Commands.push_back(Command::createFillerCmd(parseHex(Tok))); } + + Opt.Commands.push_back(Command::createOutSecEndCmd()); } void ScriptParser::readSymbolAssignment(StringRef Name) { @@ -713,7 +795,7 @@ if (Expr.empty()) error("error in symbol assignment expression"); else - Opt.Commands.push_back({AssignmentKind, std::move(Expr), Name, {}}); + Opt.Commands.push_back(Command::createSymbolAssignmentCmd(Expr, Name)); } std::vector ScriptParser::readSectionsCommandExpr() { Index: ELF/OutputSections.h =================================================================== --- ELF/OutputSections.h +++ ELF/OutputSections.h @@ -84,6 +84,8 @@ virtual void writeTo(uint8_t *Buf) {} virtual ~OutputSectionBase() = default; + std::vector *Filler = nullptr; + protected: StringRef Name; Elf_Shdr Header; Index: ELF/OutputSections.cpp =================================================================== --- ELF/OutputSections.cpp +++ ELF/OutputSections.cpp @@ -947,9 +947,8 @@ } template void OutputSection::writeTo(uint8_t *Buf) { - ArrayRef Filler = Script::X->getFiller(this->Name); - if (!Filler.empty()) - fill(Buf, this->getSize(), Filler); + if (Filler) + fill(Buf, this->getSize(), *Filler); if (Config->Threads) { parallel_for_each(Sections.begin(), Sections.end(), [=](InputSection *C) { C->writeTo(Buf); }); Index: ELF/Writer.h =================================================================== --- ELF/Writer.h +++ ELF/Writer.h @@ -50,6 +50,9 @@ template void reportDiscarded(InputSectionBase *IS, const std::unique_ptr> &File); + +template +bool compareSections(OutputSectionBase *A, OutputSectionBase *B); } } Index: ELF/Writer.cpp =================================================================== --- ELF/Writer.cpp +++ ELF/Writer.cpp @@ -48,7 +48,11 @@ void copyLocalSymbols(); void addReservedSymbols(); + + std::vector *> + createRegularSections(OutputSectionFactory &Factory); void createSections(); + void addPredefinedSections(); bool needsGot(); @@ -86,10 +90,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.", @@ -385,14 +385,10 @@ // Output section ordering is determined by this function. template -static bool compareSections(OutputSectionBase *A, - OutputSectionBase *B) { +bool elf::compareSections(OutputSectionBase *A, + 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(); @@ -623,11 +619,14 @@ 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()) { @@ -638,14 +637,24 @@ 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 @@ -750,8 +759,11 @@ // This function adds linker-created Out::* sections. addPredefinedSections(); - std::stable_sort(OutputSections.begin(), OutputSections.end(), - compareSections); + if (ScriptConfig->DoLayout) + Script::X->sortSections(OutputSections); + else + std::stable_sort(OutputSections.begin(), OutputSections.end(), + compareSections); unsigned I = 1; for (OutputSectionBase *Sec : OutputSections) {