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 "lld/Core/LLVM.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/MapVector.h" @@ -25,47 +26,49 @@ 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, + 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 { SectionKind, AssignmentKind }; - -struct SectionsCommand { - SectionsCommandKind Kind; +struct Command { + CommandKind Kind; std::vector Expr; StringRef Name; + StringRef Pattern; + bool Keep; + std::vector Filler; + + 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 createInputSectionCmd(StringRef Pattern, bool Keep) { + return Command{InputSectionKind, {}, "", Pattern, Keep, {}}; + } + static Command createFillerCmd(const std::vector &Filler) { + return Command{FillerKind, {}, "", "", false, std::move(Filler)}; + } }; // ScriptConfiguration holds linker script parse results. struct ScriptConfiguration { - // SECTIONS commands. - std::vector Sections; - - // Section fill attribute for each section. - llvm::StringMap> Filler; - - // Used to assign addresses to sections. - std::vector Commands; - bool DoLayout = false; - + std::vector Commands; 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; @@ -75,12 +78,15 @@ 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); + + std::vector *> + createSections(OutputSectionFactory &Factory, + SymbolTable &SymTab); + + void sort(std::vector *>& S); + void addScriptedSymbols(); private: Index: ELF/LinkerScript.cpp =================================================================== --- ELF/LinkerScript.cpp +++ ELF/LinkerScript.cpp @@ -23,6 +23,7 @@ #include "Symbols.h" #include "SymbolTable.h" #include "Target.h" +#include "Writer.h" #include "llvm/ADT/StringSwitch.h" #include "llvm/Support/ELF.h" #include "llvm/Support/FileSystem.h" @@ -45,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(); @@ -77,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(); } @@ -186,49 +187,131 @@ 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 OutputSectionBase *addSection(OutputSectionFactory &Factory, + StringRef OutSecName, + InputSectionBase *InSec) { + if (OutSecName == "/DISCARD/") + return nullptr; + + OutputSectionBase *OutSection = nullptr; + bool IsNew; + std::tie(OutSection, IsNew) = Factory.create(InSec, OutSecName); + OutSection->addSection(InSec); + return IsNew ? OutSection : nullptr; } template -bool LinkerScript::shouldKeep(InputSectionBase *S) { - for (StringRef Pat : Opt.KeptSections) - if (globMatch(Pat, S->getSectionName())) - return true; - return false; -} +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.Commands) { + if (Cmd.Kind == OutSectionKind) { + OutSecName = Cmd.Name; + OutSection = nullptr; + continue; + } + if (OutSection && Cmd.Kind == FillerKind) { + OutSection->Filler = Cmd.Filler; + continue; + } + + if (Cmd.Kind != InputSectionKind) + continue; + + do { + auto I = llvm::find_if(Unassigned, [&](InputSectionBase *S) { + return globMatch(Cmd.Pattern, S->getSectionName()); + }); + if (I == Unassigned.end()) + break; + + InputSectionBase *InSec = *I; + Unassigned.erase(I); + if (OutputSectionBase *Sec = + addSection(Factory, OutSecName, InSec)) { + Sections.push_back(Sec); + OutSection = Sec; + } + + } while (true); + } -template -void LinkerScript::assignAddresses( - ArrayRef *> 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) + if (OutputSectionBase *Sec = + addSection(Factory, getOutputSectionName(U), U)) + Sections.push_back(Sec); + 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); - if (Cmd.Name == ".") { Dot = Val; } else { @@ -238,32 +321,24 @@ continue; } + if (Cmd.Kind != OutSectionKind) + continue; + // Find all the sections with required name. There can be more than - // ont section with such name, if the alignment, flags or type + // 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. @@ -274,44 +349,37 @@ 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) { +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::sort(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 false; + 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); } @@ -524,11 +592,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}); + Opt.Commands.push_back(Command::createOutSecCmd(OutSec)); expect(":"); expect("{"); @@ -537,22 +605,22 @@ 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); } } + if (Error) + return; + StringRef Tok = peek(); if (Tok.startswith("=")) { if (!Tok.startswith("=0x")) { @@ -560,8 +628,8 @@ return; } Tok = Tok.substr(3); - Opt.Filler[OutSec] = parseHex(Tok); next(); + Opt.Commands.push_back(Command::createFillerCmd(parseHex(Tok))); } } @@ -571,7 +639,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; + 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.", @@ -403,10 +403,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(); @@ -603,11 +599,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()) { @@ -618,14 +617,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 @@ -730,8 +739,11 @@ // This function adds linker-created Out::* sections. addPredefinedSections(); - std::stable_sort(OutputSections.begin(), OutputSections.end(), - compareSections); + if (ScriptConfig->DoLayout) + Script::X->sort(OutputSections); + else + std::stable_sort(OutputSections.begin(), OutputSections.end(), + compareSections); unsigned I = 1; for (OutputSectionBase *Sec : OutputSections) { Index: test/ELF/linkerscript-sections-keep.s =================================================================== --- test/ELF/linkerscript-sections-keep.s +++ test/ELF/linkerscript-sections-keep.s @@ -41,9 +41,9 @@ # MIXED1: Sections: # MIXED1-NEXT: Idx Name Size Address Type # MIXED1-NEXT: 0 00000000 0000000000000000 -# MIXED1-NEXT: 1 .keep 00000004 0000000000000120 DATA -# MIXED1-NEXT: 2 .temp 00000004 0000000000000124 DATA -# MIXED1-NEXT: 3 .text 00000007 0000000000000128 TEXT DATA +# MIXED1-NEXT: 1 .keep 00000004 0000000000000158 DATA +# MIXED1-NEXT: 2 .text 00000007 000000000000015c TEXT DATA +# MIXED1-NEXT: 3 .temp 00000004 0000000000000163 DATA # MIXED1-NEXT: 4 .symtab 00000060 0000000000000000 # MIXED1-NEXT: 5 .shstrtab 0000002d 0000000000000000 # MIXED1-NEXT: 6 .strtab 00000012 0000000000000000 @@ -60,9 +60,9 @@ # MIXED2: Sections: # MIXED2-NEXT: Idx Name Size Address Type # MIXED2-NEXT: 0 00000000 0000000000000000 -# MIXED2-NEXT: 1 .nokeep 00000004 0000000000000120 DATA -# MIXED2-NEXT: 2 .temp 00000004 0000000000000124 DATA -# MIXED2-NEXT: 3 .text 00000007 0000000000000128 TEXT DATA +# MIXED2-NEXT: 1 .nokeep 00000004 0000000000000158 DATA +# MIXED2-NEXT: 2 .text 00000007 000000000000015c TEXT DATA +# MIXED2-NEXT: 3 .temp 00000004 0000000000000163 DATA # MIXED2-NEXT: 4 .symtab 00000060 0000000000000000 # MIXED2-NEXT: 5 .shstrtab 0000002f 0000000000000000 # MIXED2-NEXT: 6 .strtab 00000012 0000000000000000 Index: test/ELF/linkerscript-sections.s =================================================================== --- test/ELF/linkerscript-sections.s +++ test/ELF/linkerscript-sections.s @@ -19,8 +19,8 @@ # SEC-DEFAULT: 1 .text 0000000e {{[0-9a-f]*}} TEXT DATA # SEC-DEFAULT: 2 .data 00000020 {{[0-9a-f]*}} DATA # SEC-DEFAULT: 3 other 00000003 {{[0-9a-f]*}} DATA -# SEC-DEFAULT: 4 .bss 00000002 {{[0-9a-f]*}} BSS -# SEC-DEFAULT: 5 .shstrtab 00000002 {{[0-9a-f]*}} +# SEC-DEFAULT: 4 .shstrtab 00000002 {{[0-9a-f]*}} +# SEC-DEFAULT: 5 .bss 00000002 {{[0-9a-f]*}} BSS # SEC-DEFAULT: 6 .symtab 00000030 {{[0-9a-f]*}} # SEC-DEFAULT: 7 .shstrtab 00000032 {{[0-9a-f]*}} # SEC-DEFAULT: 8 .strtab 00000008 {{[0-9a-f]*}} @@ -60,8 +60,8 @@ # SEC-SWAP-NAMES: 1 .data 0000000e {{[0-9a-f]*}} TEXT DATA # SEC-SWAP-NAMES: 2 .text 00000020 {{[0-9a-f]*}} DATA # SEC-SWAP-NAMES: 3 other 00000003 {{[0-9a-f]*}} DATA -# SEC-SWAP-NAMES: 4 .bss 00000002 {{[0-9a-f]*}} BSS -# SEC-SWAP-NAMES: 5 .shstrtab 00000002 {{[0-9a-f]*}} +# SEC-SWAP-NAMES: 4 .shstrtab 00000002 {{[0-9a-f]*}} +# SEC-SWAP-NAMES: 5 .bss 00000002 {{[0-9a-f]*}} BSS # SEC-SWAP-NAMES: 6 .symtab 00000030 {{[0-9a-f]*}} # SEC-SWAP-NAMES: 7 .shstrtab 00000032 {{[0-9a-f]*}} # SEC-SWAP-NAMES: 8 .strtab 00000008 {{[0-9a-f]*}} @@ -82,27 +82,6 @@ # SEC-DISCARD: 6 .shstrtab 00000032 {{[0-9a-f]*}} # SEC-DISCARD: 7 .strtab 00000008 {{[0-9a-f]*}} -# Multiple SECTIONS command specifying additional input section descriptions -# for the same output section description - input sections are merged into -# one output section. -# RUN: echo "SECTIONS { \ -# RUN: .text : { *(.text) } \ -# RUN: .data : { *(.data) } } \ -# RUN: SECTIONS { \ -# RUN: .data : { *(other) } }" > %t.script -# RUN: ld.lld -o %t6 --script %t.script %t -# RUN: llvm-objdump -section-headers %t6 | \ -# RUN: FileCheck -check-prefix=SEC-MULTI %s - -# Idx Name Size -# SEC-MULTI: 1 .text 0000000e {{[0-9a-f]*}} TEXT DATA -# SEC-MULTI: 2 .data 00000023 {{[0-9a-f]*}} DATA -# SEC-MULTI: 3 .bss 00000002 {{[0-9a-f]*}} BSS -# SEC-MULTI: 4 .shstrtab 00000002 {{[0-9a-f]*}} -# SEC-MULTI: 5 .symtab 00000030 {{[0-9a-f]*}} -# SEC-MULTI: 6 .shstrtab 0000002c {{[0-9a-f]*}} -# SEC-MULTI: 7 .strtab 00000008 {{[0-9a-f]*}} - .globl _start _start: mov $60, %rax Index: test/ELF/linkerscript-va.s =================================================================== --- test/ELF/linkerscript-va.s +++ test/ELF/linkerscript-va.s @@ -7,9 +7,9 @@ # CHECK: Sections: # CHECK-NEXT: Idx Name Size Address Type # CHECK-NEXT: 0 00000000 0000000000000000 -# CHECK-NEXT: 1 .foo 00000004 0000000000000120 DATA -# CHECK-NEXT: 2 .boo 00000004 0000000000000124 DATA -# CHECK-NEXT: 3 .text 00000001 0000000000000128 TEXT DATA +# CHECK-NEXT: 1 .text 00000001 0000000000000158 TEXT DATA +# CHECK-NEXT: 2 .foo 00000004 0000000000000159 DATA +# CHECK-NEXT: 3 .boo 00000004 000000000000015d DATA .global _start _start: