[ELF] - Initial support of tree-style linker script implemented.

[grimar]

Summary

Approach uses LLVM-style RTTI for representing the linker script
commands in a form of tree for future simplification of parsing.

Core idea and code sample belongs to Rui Ueyama.

[grimar]

• Update of comment.

[ruiu]

LGTM

[ruiu]

LGTM with this change.

ELF/LinkerScript.h

56 ↗

(On Diff #64797)

I think you need to define a virtual destructor because you are destructing derived classes instances through base class pointers.

[Eugene.Zelenko]

ELF/LinkerScript.cpp

44 ↗

(On Diff #64797)

Please fix -Wextra-semi.

48 ↗

(On Diff #64797)

Please fix -Wextra-semi.

[grimar]

ELF/LinkerScript.cpp

44 ↗

(On Diff #64797)

Will do, thanks.

ELF/LinkerScript.h

56 ↗

(On Diff #64797)

Right, thanks ! And thank you so much for reviewing and help with that !

lld/trunk/ELF/LinkerScript.h

struct SectionRule {
   SectionRule(StringRef D, StringRef S)
       : Dest(D), SectionPattern(S) {}
 
   StringRef Dest;
 
   StringRef SectionPattern;
 };
 
-// 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 };
+// This enum represents what we can observe in SECTIONS tag of script.
+// Each sections-command may of be one of the following:
+// (https://sourceware.org/binutils/docs/ld/SECTIONS.html#SECTIONS)
+// * An ENTRY command.
+// * A symbol assignment.
+// * An output section description.
+// * An overlay description.
+// We support only AssignmentKind and OutputSectionKind for now.
+enum SectionsCommandKind { AssignmentKind, OutputSectionKind };
+
+struct BaseCommand {
+  BaseCommand(int K) : Kind(K) {}
+  virtual ~BaseCommand() {}
+  int Kind;
+};
 
-struct SectionsCommand {
-  SectionsCommandKind Kind;
+struct SymbolAssignment : BaseCommand {
+  SymbolAssignment(StringRef Name, std::vector<StringRef> &Expr)
+      : BaseCommand(AssignmentKind), Name(Name), Expr(std::move(Expr)) {}
+  static bool classof(const BaseCommand *C);
+  StringRef Name;
   std::vector<StringRef> Expr;
+};
+
+struct OutputSectionCommand : BaseCommand {
+  OutputSectionCommand(StringRef Name)
+      : BaseCommand(OutputSectionKind), Name(Name) {}
+  static bool classof(const BaseCommand *C);
   StringRef Name;
   std::vector<StringRef> Phdrs;
+  std::vector<uint8_t> Filler;
 };
 
 struct PhdrsCommand {
   StringRef Name;
   unsigned Type;
   bool HasFilehdr;
   bool HasPhdrs;
 };
 
 // ScriptConfiguration holds linker script parse results.
 struct ScriptConfiguration {
   // SECTIONS commands.
   std::vector<SectionRule> Sections;
 
   // Section fill attribute for each section.
   llvm::StringMap<std::vector<uint8_t>> Filler;
 
   // Used to assign addresses to sections.
-  std::vector<SectionsCommand> Commands;
+  std::vector<std::unique_ptr<BaseCommand>> Commands;
 
   // Used to assign sections to headers.
   std::vector<PhdrsCommand> PhdrsCommands;
 
   bool DoLayout = false;
 
   llvm::BumpPtrAllocator Alloc;
 

lld/trunk/ELF/LinkerScript.cpp

 using namespace llvm;
 using namespace llvm::ELF;
 using namespace llvm::object;
 using namespace lld;
 using namespace lld::elf;
 
 ScriptConfiguration *elf::ScriptConfig;
 
+bool SymbolAssignment::classof(const BaseCommand *C) {
+  return C->Kind == AssignmentKind;
+}
+
+bool OutputSectionCommand::classof(const BaseCommand *C) {
+  return C->Kind == OutputSectionKind;
+}
+
 // This is an operator-precedence parser to parse and evaluate
 // a linker script expression. For each linker script arithmetic
 // expression (e.g. ". = . + 0x1000"), a new instance of ExprParser
 // is created and ran.
 namespace {
 class ExprParser : public ScriptParserBase {
 public:
   ExprParser(std::vector<StringRef> &Tokens, uint64_t Dot)
void LinkerScript<ELFT>::assignAddresses(
   // 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<ELFT> *Sec : Sections) {
     StringRef Name = Sec->getName();
     if (getSectionIndex(Name) == INT_MAX)
-      Opt.Commands.push_back({SectionKind, {}, Name, {}});
+      Opt.Commands.push_back(llvm::make_unique<OutputSectionCommand>(Name));
   }
 
   // Assign addresses as instructed by linker script SECTIONS sub-commands.
   Dot = Out<ELFT>::ElfHeader->getSize() + Out<ELFT>::ProgramHeaders->getSize();
   uintX_t MinVA = std::numeric_limits<uintX_t>::max();
   uintX_t ThreadBssOffset = 0;
 
-  for (SectionsCommand &Cmd : Opt.Commands) {
-    if (Cmd.Kind == AssignmentKind) {
-      uint64_t Val = evalExpr(Cmd.Expr, Dot);
+  for (const std::unique_ptr<BaseCommand> &Base : Opt.Commands) {
+    if (auto *Cmd = dyn_cast<SymbolAssignment>(Base.get())) {
+      uint64_t Val = evalExpr(Cmd->Expr, Dot);
+      if (Cmd->Name == ".") {
 
-      if (Cmd.Name == ".") {
         Dot = Val;
       } else {
-        auto *D = cast<DefinedRegular<ELFT>>(Symtab<ELFT>::X->find(Cmd.Name));
+        auto *D = cast<DefinedRegular<ELFT>>(Symtab<ELFT>::X->find(Cmd->Name));
         D->Value = Val;
       }
       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);
+    auto *Cmd = cast<OutputSectionCommand>(Base.get());
     for (OutputSectionBase<ELFT> *Sec : Sections) {
-      if (Sec->getName() != Cmd.Name)
+      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 (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 <class ELFT>
-int LinkerScript<ELFT>::getSectionIndex(StringRef Name) {
+template <class ELFT> int LinkerScript<ELFT>::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, [&](const std::unique_ptr<BaseCommand> &Base) {
+        if (auto *Cmd = dyn_cast<OutputSectionCommand>(Base.get()))
+          if (Cmd->Name == Name)
+            return true;
+        return false;
       });
   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 <class ELFT>
 int LinkerScript<ELFT>::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;
 }
 
-template <class ELFT>
-void LinkerScript<ELFT>::addScriptedSymbols() {
-  for (SectionsCommand &Cmd : Opt.Commands)
-    if (Cmd.Kind == AssignmentKind)
-      if (Cmd.Name != "." && Symtab<ELFT>::X->find(Cmd.Name) == nullptr)
-        Symtab<ELFT>::X->addAbsolute(Cmd.Name, STV_DEFAULT);
+template <class ELFT> void LinkerScript<ELFT>::addScriptedSymbols() {
+  for (const std::unique_ptr<BaseCommand> &Base : Opt.Commands)
+    if (auto *Cmd = dyn_cast<SymbolAssignment>(Base.get()))
+      if (Cmd->Name != "." && Symtab<ELFT>::X->find(Cmd->Name) == nullptr)
+        Symtab<ELFT>::X->addAbsolute(Cmd->Name, STV_DEFAULT);
 }
 
 template <class ELFT> bool LinkerScript<ELFT>::hasPhdrsCommands() {
   return !Opt.PhdrsCommands.empty();
 }
 
 // Returns indices of ELF headers containing specific section, identified
 // by Name. Each index is a zero based number of ELF header listed within
 // PHDRS {} script block.
 template <class ELFT>
 std::vector<size_t>
 LinkerScript<ELFT>::getPhdrIndicesForSection(StringRef Name) {
-  for (SectionsCommand &Cmd : Opt.Commands) {
-    if (Cmd.Kind != SectionKind || Cmd.Name != Name)
+  for (const std::unique_ptr<BaseCommand> &Base : Opt.Commands) {
+    auto *Cmd = dyn_cast<OutputSectionCommand>(Base.get());
+    if (!Cmd || Cmd->Name != Name)
       continue;
 
     std::vector<size_t> Indices;
-    for (StringRef PhdrName : Cmd.Phdrs) {
+    for (StringRef PhdrName : Cmd->Phdrs) {
       auto ItPhdr =
           std::find_if(Opt.PhdrsCommands.rbegin(), Opt.PhdrsCommands.rend(),
-                       [&](PhdrsCommand &Cmd) { return Cmd.Name == PhdrName; });
+                       [&](PhdrsCommand &P) { return P.Name == PhdrName; });
       if (ItPhdr == Opt.PhdrsCommands.rend())
         error("section header '" + PhdrName + "' is not listed in PHDRS");
       else
         Indices.push_back(std::distance(ItPhdr, Opt.PhdrsCommands.rend()) - 1);
     }
     return Indices;
   }
   return {};

 
 void ScriptParser::readLocationCounterValue() {
   expect(".");
   expect("=");
   std::vector<StringRef> Expr = readSectionsCommandExpr();
   if (Expr.empty())
     error("error in location counter expression");
   else
-    Opt.Commands.push_back({AssignmentKind, std::move(Expr), ".", {}});
+    Opt.Commands.push_back(llvm::make_unique<SymbolAssignment>(".", Expr));
 }
 
 void ScriptParser::readOutputSectionDescription(StringRef OutSec) {
-  Opt.Commands.push_back({SectionKind, {}, OutSec, {}});
-  SectionsCommand &Cmd = Opt.Commands.back();
+  OutputSectionCommand *Cmd = new OutputSectionCommand(OutSec);
+  Opt.Commands.emplace_back(Cmd);
   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);
     }
   }
-  Cmd.Phdrs = readOutputSectionPhdrs();
+  Cmd->Phdrs = readOutputSectionPhdrs();
 
   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<StringRef> Expr = readSectionsCommandExpr();
   if (Expr.empty())
     error("error in symbol assignment expression");
   else
-    Opt.Commands.push_back({AssignmentKind, std::move(Expr), Name, {}});
+    Opt.Commands.push_back(llvm::make_unique<SymbolAssignment>(Name, Expr));
 }
 
 std::vector<StringRef> ScriptParser::readSectionsCommandExpr() {
   std::vector<StringRef> Expr;
   while (!Error) {
     StringRef Tok = next();
     if (Tok == ";")
       break;