[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

222

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

[grimar]

ELF/LinkerScript.cpp

222

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

222

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

222

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

[evgeny777]

ELF/LinkerScript.cpp

222

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

222

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.

246–260

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.

747

Use auto.

762

Ditto

[grimar]

• Addressed review comments.

[evgeny777]

ELF/LinkerScript.h

45

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

222

Reverted to KeptSections.

246–260

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

747

Done.

762

Done.

ELF/LinkerScript.h

45

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

202

Do you still need this function?

247

OutSec as a name for a command is very confusing.

249

Flip if conditions and do continue to reduce indentation levels.

ELF/LinkerScript.h

45

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

76

Now you can remove this.

[grimar]

• Addressed review comments.

ELF/LinkerScript.cpp

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.

247

Changed to OutSec.

249

Done.

ELF/LinkerScript.h

45

Done.

76

Done.

[grimar]

ELF/LinkerScript.cpp

247

I mean to OutCmd, sorry.

[ruiu]

ELF/LinkerScript.cpp

252

Again, InSec is a confusing name.

261–265

Regular for-each loop is probably easier to read.

ELF/LinkerScript.h

100–101

Remove.

[grimar]

• Addressed review comments.

ELF/LinkerScript.cpp

252

Fixed.

261–265

Changed.

ELF/LinkerScript.h

100–101

Done.

[ruiu]

ELF/LinkerScript.cpp

246–260

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

271

break at end of a for-loop?

273–274

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

[grimar]

ELF/LinkerScript.cpp

271

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

271

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

271

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

271

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

261

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

261

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

261

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

[grimar]

ELF/LinkerScript.cpp

261

// 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 };
+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;
+  bool Keep = false;
+};
+
 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.
+  // It is the same information that can be found in Commands,
+  // but extracted for simplicity and possible speedup.
   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;

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)
uint64_t ExprParser::parseExpr1(uint64_t Lhs, int MinPrec) {
   }
   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;
+  for (const std::unique_ptr<BaseCommand> &Base : Opt.Commands)
+    if (auto *OutSec = dyn_cast<OutputSectionCommand>(Base.get()))
+      for (const std::unique_ptr<BaseCommand> &Cmd : OutSec->Commands)
+        if (auto *InSec = dyn_cast<InputSectionDescription>(Cmd.get()))
+          for (StringRef P : InSec->Patterns)
+            if (globMatch(P, S->getSectionName()))
+              return OutSec->Name;
   return "";
 }
 
 template <class ELFT>
 bool LinkerScript<ELFT>::isDiscarded(InputSectionBase<ELFT> *S) {
   return !S || !S->Live || getOutputSection(S) == "/DISCARD/";
 }
 
 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 (const std::unique_ptr<BaseCommand> &Base : Opt.Commands)
+    if (auto *OutSec = dyn_cast<OutputSectionCommand>(Base.get()))
+      for (const std::unique_ptr<BaseCommand> &Cmd : OutSec->Commands)
+        if (auto *InSec = dyn_cast<InputSectionDescription>(Cmd.get()))
+          for (ObjectFile &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);
+              if (!isDiscarded(S) && !S->OutSec) {
+                auto I = llvm::find_if(InSec->Patterns, [S](StringRef &P) {
+                  return globMatch(P, S->getSectionName());
+                });
+                if (I != InSec->Patterns.end()) {
+                  AddInputSec(S, OutSec->Name);
+                  continue;
+                }
+              }
 
   // 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;
 }
 
 template <class ELFT>
 void LinkerScript<ELFT>::assignAddresses(
     ArrayRef<OutputSectionBase<ELFT> *> 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<ELFT> *Sec : Sections) {
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 *IS = new InputSectionDescription();
+      Cmd->Commands.emplace_back(IS);
       expect("(");
       while (!Error && !skip(")"))
-        Opt.Sections.emplace_back(OutSec, next());
+        IS->Patterns.push_back(next());
     } else if (Tok == "KEEP") {
       expect("(");
       expect("*");
       expect("(");
+      auto *IS = new InputSectionDescription();
+      IS->Keep = true;
+      Cmd->Commands.emplace_back(IS);
       while (!Error && !skip(")")) {
-        StringRef Sec = next();
-        Opt.Sections.emplace_back(OutSec, Sec);
-        Opt.KeptSections.push_back(Sec);
+        Opt.KeptSections.push_back(peek());
+        IS->Patterns.push_back(next());
       }
       expect(")");
     } else {
       setError("unknown command " + Tok);
     }
   }
   Cmd->Phdrs = readOutputSectionPhdrs();
 
   StringRef Tok = peek();