[ELF] - Linkerscript: add InputSectionDescription command to LS parser.

[grimar]

Summary

This adds InputSectionDescription command to represent
the input section declaration.

This leads to next cleanup:
SectionRule removed.
ScriptConfiguration::Sections mamber removed.
LinkerScript<ELFT>::getOutputSection() removed.

[evgeny777]

ELF/LinkerScript.cpp

210

It looks like a slow-down compared with previous one, no?

[grimar]

ELF/LinkerScript.cpp

210

That fits in new design. I am sure we will spend time on optimization of LS later,
when will be able to run benchmarks. And probably many places will need tweaking,
for now I don't think it is critical to change until major slowdown is proven.

[evgeny777]

ELF/LinkerScript.cpp

210

As far as I understand if --gc-sections command line switch is set, then markLive() calls LinkerScript::shouldKeep() for every input section. There could easily be millions of input sections in large projects like WebKit or LLVM itself. It might not be a good idea to sacrifice performance that much in favor of design improvements.

[grimar]

ELF/LinkerScript.cpp

210

I think the most slow here is the call of globMatch. Amount of calls remained the same.

[evgeny777]

ELF/LinkerScript.cpp

210

Well, the time complexity in your new code is O(I*R), I - number of sections, R - number of rules
Imagine you don't have any kept sections and don't call globMatch. Let's say you have 1 million sections and 10 rules total in script
Your for statements are actually for_each, at average you need about 20 instructions (with -O2 and 100 without optimization) for a single iteration (this is just 'for' statement without body).
Let's say you'll need 50 instructions for each rule (just assumption - can't tell the exact number), so

1 000 000 * 10 * 50 = 500 000 000
On 2 Ghz processor and 1 clock cycle per instruction

t = (5 * 10^8) / (2*10^9) = 0.25 sec.
for doing nothing

Is it worth that?

[ruiu]

ELF/LinkerScript.cpp

210

Yeah, I have a feeling that we should keep KeptSections mostly for simplicity. The reason why we want to construct an AST in a way that that reflects the structure of a given linker script is because we want to construct output sections in the same order as they appear in a linker script. On the other hand, "KEEP" seems to have been just piggybacking the grammar which they already had. It doesn't belong to this much deep data structure.

234–263

I think you still want to iterate over SECTIONS subcommands. Eventually we want to create output sections and add input sections to them while we are visiting SECTIONS subcommands so that the results are naturally sorted by the same order as they appear in a linker script, so that we don't need to sort the results afterwards.

750

Use auto.

764

Ditto

[grimar]

• Addressed review comments.

[evgeny777]

ELF/LinkerScript.h

37

See comment above:

This enum represents what we can observe in SECTIONS tag of script.
(https://sourceware.org/binutils/docs/ld/SECTIONS.html#SECTIONS)

If you follow the link:

Each sections-command may of be one of the following:

- an ENTRY command (see Entry command)
- a symbol assignment (see Assignments)
- an output section description
- an overlay description

[grimar]

ELF/LinkerScript.cpp

210

Reverted to KeptSections.

234–263

I see. Done. Looks a little bit more complicated now though.

750

Done.

764

Done.

ELF/LinkerScript.h

37

Well, comment is depricated. I guess we do not want to treat SectionsCommandKind as written anymore, so it can be removed completely,
Rui, what do you think ?

[ruiu]

ELF/LinkerScript.cpp

201–202

Do you still need this function?

235

OutSec as a name for a command is very confusing.

237

Flip if conditions and do continue to reduce indentation levels.

ELF/LinkerScript.h

37

We should just remove this comment and leave the link to the documentation.

70

Now you can remove this.

[grimar]

• Addressed review comments.

ELF/LinkerScript.cpp

201–202

getOutputSection() was used in LinkerScript<ELFT>::isDiscarded().
I changed logic to avoid the using as "/DISCARD/" can just be processed as
special section kind.

235

Changed to OutSec.

237

Done.

ELF/LinkerScript.h

37

Done.

70

Done.

[grimar]

ELF/LinkerScript.cpp

235

I mean to OutCmd, sorry.

[ruiu]

ELF/LinkerScript.cpp

240

Again, InSec is a confusing name.

249–253

Regular for-each loop is probably easier to read.

ELF/LinkerScript.h

93–94

Remove.

[grimar]

• Addressed review comments.

ELF/LinkerScript.cpp

240

Fixed.

249–253

Changed.

ELF/LinkerScript.h

93–94

Done.

[ruiu]

ELF/LinkerScript.cpp

234

This change will make this function too long, but that's probably okay for now. I'll try to split it up.

259

break at end of a for-loop?

261–262

If you need {}, please put {} all inner loops.

[grimar]

ELF/LinkerScript.cpp

259

Yes, break. I need to exit this loop after first AddInputSec. As we do not want to add the section again if there are multiple pattern matches.
That was why I used std::find_if in previous iteration.
May be worth to revert to previous version ?

[ruiu]

ELF/LinkerScript.cpp

259

You can define a function taking two parameters, a stringref and an arrayref of stringref, which returns true if the former string glob-matches one of the latter strings.

[grimar]

ELF/LinkerScript.cpp

259

What about next ?

static bool hasGlobMatch(StringRef T, ArrayRef<StringRef> L) {
  for (StringRef S : L)
    if (globMatch(S, T))
      return true;
  return false;
}

[grimar]

• Addressed review comments.

[ruiu]

ELF/LinkerScript.cpp

259

That's what I meant. (a few nits are: I'd name the function match because "GlobMatch" is not an object or a thing, rename T Pattern, and swap T and L to match the parameter order of globMatch.)

[grimar]

ELF/LinkerScript.cpp

264

Afraid I am a bit lost in this puzzle :)
Is that what you mean ?

static bool match(StringRef T, ArrayRef<StringRef> Pattern) {
  for (StringRef S : Pattern)
    if (globMatch(S, T))
      return true;
  return false;
}

[ruiu]

LGTM with the change.

ELF/LinkerScript.cpp

264

1. I want parameters of similar functions be ordered in a consistent way. However, your new function takes [Pattern Target] although globMatch takes [Target Pattern]
2. T is too short and doesn't convey it is a glob pattern rather.
3. Apparently Pattern is not a right name for ArrayRef<StringRef> that doesn't contain patterns
   
   static bool match(StringRef Pattern, ArrayRef<StringRef> Arr) { for (StringRef S : Arr) if (globMatch(Pattern, S)) return true; return false; }

[grimar]

ELF/LinkerScript.cpp

264

Ok, now I see what you meant. Sorry for my confusion and thanks a lot for all reviews !

[grimar]

ELF/LinkerScript.cpp

264

// Returns true if S matches T. S can contain glob meta-characters.
// The asterisk ('*') matches zero or more characters, and the question
// mark ('?') matches one character.
bool elf::globMatch(StringRef S, StringRef T) {
  for (;;) {
    if (S.empty())
      return T.empty();
    if (S[0] == '*') {
      S = S.substr(1);
      if (S.empty())
        // Fast path. If a pattern is '*', it matches anything.
        return true;
      for (size_t I = 0, E = T.size(); I < E; ++I)
        if (globMatch(S, T.substr(I)))
          return true;
      return false;
    }
    if (T.empty() || (S[0] != T[0] && S[0] != '?'))
      return false;
    S = S.substr(1);
    T = T.substr(1);
  }
}

1. According to comments S is pattern. So it takes [Pattern, Target].
2. My function searches Name in a list of wildcards, that mean second is a list of patterns, so ArrayRef<StringRef> *contains* patterns.

For function to work as I need, it needs to be:

if (globMatch(S, Pattern))

instead of

if (globMatch(Pattern, S))

And that is what inconsistent with globMatch,
which has Pattern as first argument.

I am really not trying to argue here. I`ll commit it and just please adjust the naming as you want after that.

ELF/LinkerScript.h

 // Parses a linker script. Calling this function updates
 // Config and ScriptConfig.
 void readLinkerScript(MemoryBufferRef MB);
 
 class ScriptParser;
 template <class ELFT> class InputSectionBase;
 template <class ELFT> class OutputSectionBase;
 
-// This class represents each rule in SECTIONS command.
-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.
-// 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 };
+// This enum is used to implement linker script SECTIONS command.
+// https://sourceware.org/binutils/docs/ld/SECTIONS.html#SECTIONS
+enum SectionsCommandKind {
+  AssignmentKind,
+  OutputSectionKind,
+  InputSectionKind
+};
 
 struct BaseCommand {
   BaseCommand(int K) : Kind(K) {}
   virtual ~BaseCommand() {}
   int 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<std::unique_ptr<BaseCommand>> Commands;
   std::vector<StringRef> Phdrs;
   std::vector<uint8_t> Filler;
 };
 
+struct InputSectionDescription : BaseCommand {
+  InputSectionDescription() : BaseCommand(InputSectionKind) {}
+  static bool classof(const BaseCommand *C);
+  std::vector<StringRef> Patterns;
+};
+
 struct PhdrsCommand {
   StringRef Name;
   unsigned Type;
   bool HasFilehdr;
   bool HasPhdrs;
 };
 
 // ScriptConfiguration holds linker script parse results.
 struct ScriptConfiguration {
-  // SECTIONS commands.
-  std::vector<SectionRule> Sections;
-
   // Used to assign addresses to sections.
   std::vector<std::unique_ptr<BaseCommand>> Commands;
 
   // Used to assign sections to headers.
   std::vector<PhdrsCommand> PhdrsCommands;
 
   bool DoLayout = false;
 
   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<StringRef> KeptSections;
 };
 
 extern ScriptConfiguration *ScriptConfig;
 
 // This is a runner of the linker script.
 template <class ELFT> class LinkerScript {
   typedef typename ELFT::uint uintX_t;
 
 public:
   typedef PhdrEntry<ELFT> Phdr;
 
   std::vector<OutputSectionBase<ELFT> *>
   createSections(OutputSectionFactory<ELFT> &Factory);
 
-  StringRef getOutputSection(InputSectionBase<ELFT> *S);
   ArrayRef<uint8_t> getFiller(StringRef Name);
   bool isDiscarded(InputSectionBase<ELFT> *S);
   bool shouldKeep(InputSectionBase<ELFT> *S);
   void assignAddresses(ArrayRef<OutputSectionBase<ELFT> *> S);
   int compareSections(StringRef A, StringRef B);
   void addScriptedSymbols();
   std::vector<Phdr> createPhdrs(ArrayRef<OutputSectionBase<ELFT> *> S);
   bool hasPhdrsCommands();

ELF/LinkerScript.cpp

 bool SymbolAssignment::classof(const BaseCommand *C) {
   return C->Kind == AssignmentKind;
 }
 
 bool OutputSectionCommand::classof(const BaseCommand *C) {
   return C->Kind == OutputSectionKind;
 }
 
+bool InputSectionDescription::classof(const BaseCommand *C) {
+  return C->Kind == InputSectionKind;
+}
+
 // 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)
while (!atEOF()) {
     Lhs = apply(Op1, Lhs, Rhs);
   }
   return Lhs;
 }
 
 // Reads and evaluates an arithmetic expression.
 uint64_t ExprParser::parseExpr() { return parseExpr1(parsePrimary(), 0); }
 
 template <class ELFT>
-StringRef LinkerScript<ELFT>::getOutputSection(InputSectionBase<ELFT> *S) {
-  for (SectionRule &R : Opt.Sections)
-    if (globMatch(R.SectionPattern, S->getSectionName()))
-      return R.Dest;
-  return "";
-}
-
-template <class ELFT>
 bool LinkerScript<ELFT>::isDiscarded(InputSectionBase<ELFT> *S) {
-  return !S || !S->Live || getOutputSection(S) == "/DISCARD/";
+  return !S || !S->Live;
 }
 
 template <class ELFT>
 bool LinkerScript<ELFT>::shouldKeep(InputSectionBase<ELFT> *S) {
   for (StringRef Pat : Opt.KeptSections)
     if (globMatch(Pat, S->getSectionName()))
       return true;
   return false;
 }
 
 template <class ELFT>
 std::vector<OutputSectionBase<ELFT> *>
 LinkerScript<ELFT>::createSections(OutputSectionFactory<ELFT> &Factory) {
+  typedef const std::unique_ptr<ObjectFile<ELFT>> ObjectFile;
   std::vector<OutputSectionBase<ELFT> *> Result;
 
   // Add input section to output section. If there is no output section yet,
   // then create it and add to output section list.
   auto AddInputSec = [&](InputSectionBase<ELFT> *C, StringRef Name) {
     OutputSectionBase<ELFT> *Sec;
     bool IsNew;
     std::tie(Sec, IsNew) = Factory.create(C, Name);
     if (IsNew)
       Result.push_back(Sec);
     Sec->addSection(C);
   };
 
   // Select input sections matching rule and add them to corresponding
   // output section. Section rules are processed in order they're listed
   // in script, so correct input section order is maintained by design.
-  for (SectionRule &R : Opt.Sections)
-    for (const std::unique_ptr<ObjectFile<ELFT>> &F :
-         Symtab<ELFT>::X->getObjectFiles())
-      for (InputSectionBase<ELFT> *S : F->getSections())
-        if (!isDiscarded(S) && !S->OutSec &&
-            globMatch(R.SectionPattern, S->getSectionName()))
-          // Add single input section to output section.
-          AddInputSec(S, R.Dest);
+  for (const std::unique_ptr<BaseCommand> &Base : Opt.Commands) {
+    auto *OutCmd = dyn_cast<OutputSectionCommand>(Base.get());
+    if (!OutCmd)
+      continue;
+
+    for (const std::unique_ptr<BaseCommand> &Cmd : OutCmd->Commands) {
+      auto *InCmd = dyn_cast<InputSectionDescription>(Cmd.get());
+      if (!InCmd)
+        continue;
+
+      for (ObjectFile &F : Symtab<ELFT>::X->getObjectFiles())
+        for (InputSectionBase<ELFT> *S : F->getSections()) {
+          if (isDiscarded(S) || S->OutSec)
+            continue;
+
+          for (StringRef P : InCmd->Patterns) {
+            if (!globMatch(P, S->getSectionName()))
+              continue;
+
+            if (OutCmd->Name == "/DISCARD/") {
+              S->Live = false;
+              break;
+            }
+
+            AddInputSec(S, OutCmd->Name);
+            break;
+          }
+        }
+    }
+  }
 
   // Add all other input sections, which are not listed in script.
-  for (const std::unique_ptr<ObjectFile<ELFT>> &F :
-       Symtab<ELFT>::X->getObjectFiles())
+  for (ObjectFile &F : Symtab<ELFT>::X->getObjectFiles())
     for (InputSectionBase<ELFT> *S : F->getSections())
       if (!isDiscarded(S)) {
         if (!S->OutSec)
           AddInputSec(S, getOutputSectionName(S));
       } else
         reportDiscarded(S, F);
 
   return Result;
void ScriptParser::readOutputSectionDescription(StringRef OutSec) {
   OutputSectionCommand *Cmd = new OutputSectionCommand(OutSec);
   Opt.Commands.emplace_back(Cmd);
   expect(":");
   expect("{");
 
   while (!Error && !skip("}")) {
     StringRef Tok = next();
     if (Tok == "*") {
+      auto *InCmd = new InputSectionDescription();
+      Cmd->Commands.emplace_back(InCmd);
       expect("(");
       while (!Error && !skip(")"))
-        Opt.Sections.emplace_back(OutSec, next());
+        InCmd->Patterns.push_back(next());
     } else if (Tok == "KEEP") {
       expect("(");
       expect("*");
       expect("(");
+      auto *InCmd = new InputSectionDescription();
+      Cmd->Commands.emplace_back(InCmd);
       while (!Error && !skip(")")) {
-        StringRef Sec = next();
-        Opt.Sections.emplace_back(OutSec, Sec);
-        Opt.KeptSections.push_back(Sec);
+        Opt.KeptSections.push_back(peek());
+        InCmd->Patterns.push_back(next());
       }
       expect(")");
     } else {
       setError("unknown command " + Tok);
     }
   }
   Cmd->Phdrs = readOutputSectionPhdrs();
 
   StringRef Tok = peek();

ELF/Writer.cpp

private:
 
   uintX_t FileSize;
   uintX_t SectionHeaderOff;
 };
 } // anonymous namespace
 
 template <class ELFT>
 StringRef elf::getOutputSectionName(InputSectionBase<ELFT> *S) {
-  StringRef Dest = Script<ELFT>::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.",
                       ".tbss.", ".gcc_except_table.", ".tdata."})
     if (Name.startswith(V))
       return V.drop_back();
   return Name;
 }