[ELF] - Linkerscript: support complex section pattern grammar.

[grimar]

Summary

Previously we were failed to parce complex expressions like:

foo : { *(SORT_BY_NAME(bar) zed) }

This is PR30442

Patch allows to handle them, for example the next grammar is parsed fine now:

.abc : { *(SORT(.foo.* EXCLUDE_FILE (*file1.o) .bar.*) .bar.*) }

Main idea of patch that globs and excludes can be wrapped in a SORT.
There is a difference in semanics of ld/gold:
ld likes:

*(SORT(EXCLUDE_FILE (*file1.o) .foo.1))

gold likes:

*(EXCLUDE_FILE (*file1.o) SORT(.foo.1))

Patch implements ld grammar.

[ruiu]

ELF/LinkerScript.cpp

159–160

Can you pass two pointers to InputSectionData instead of iterators?

S and E? Can you rename them Begin and End if they mean begin and end?

194–195

InputSectionData *Begin = I->Sections.data() + SizeBefore;
InputSectionData *End = I->Sections.data() + I->Sections.size();

774–778

Instead of mutating an argument, create a new vector and return it. It is the common practice in this file.

1120–1121

Returns a new vector instead of mutating the argument.

ELF/LinkerScript.h

104–106

So1 -> Sort1

RE is a common acronym for Regular Expression, but SO is not.

119–120

Remove = ... Default. You seem to always assign them.

[grimar]

• Addressed review comments.

[grimar]

ELF/LinkerScript.cpp

159–160

It was Start/End. And it is actually pointers to pointers here, I am not sure it looks better than iterators, but done.

194–195

Done.

774–778

Done.

1120–1121

Done.

ELF/LinkerScript.h

104–106

Done.

119–120

Done.

[ruiu]

ELF/LinkerScript.cpp

774–775

Out and In look like they are short for Output and Input, so these names are confusing. Since we know the type here, Inner and Outer should suffice.

1133–1137

This code seem too complicated compared to what it is doing. I think you could do like this.

SortSectionPolicy Inner = readSortKind();
SortSectionPolicy Outer = Default;
if (Inner != SortSectionPolicy::Default) {
  expect("(");
  Outer = readSortKind();
  if (Outer != SortSectionPolicy::Default) {
    expect("(");
    V = readInputSectionList();
    expect(")");
  } else {
    V = readInputSectionList();
  }
  expect(")");
}

for (SectionPattern &Pat : V) {
  Pat.SortInner = Inner;
  Pat.SortOuter = Outer;
}

[grimar]

• Addressed review comments.

ELF/LinkerScript.cpp

774–775

Done.

1133–1137

:) Something like this was my first idea when I strarted implementation. But then I thought you will not like the additional loop at the end..

[ruiu]

LGTM

ELF/LinkerScript.h

struct OutputSectionCommand : BaseCommand {
   std::vector<std::unique_ptr<BaseCommand>> Commands;
   std::vector<StringRef> Phdrs;
   std::vector<uint8_t> Filler;
   ConstraintKind Constraint = ConstraintKind::NoConstraint;
 };
 
 // This struct represents one section match pattern in SECTIONS() command.
 // It can optionally have negative match pattern for EXCLUDED_FILE command.
+// Also it may be surrounded with SORT() command, so contains sorting rules.
 struct SectionPattern {
-  SectionPattern(llvm::Regex &&Re1, llvm::Regex &&Re2)
+  SectionPattern(llvm::Regex &&Re1, llvm::Regex &&Re2, SortSectionPolicy Sort1,
+                 SortSectionPolicy Sort2)
       : ExcludedFileRe(std::forward<llvm::Regex>(Re1)),
-        SectionRe(std::forward<llvm::Regex>(Re2)) {}
+        SectionRe(std::forward<llvm::Regex>(Re2)), SortOuter(Sort1),
+        SortInner(Sort2) {}
 
   SectionPattern(SectionPattern &&Other) {
     std::swap(ExcludedFileRe, Other.ExcludedFileRe);
     std::swap(SectionRe, Other.SectionRe);
+    std::swap(SortOuter, Other.SortOuter);
+    std::swap(SortInner, Other.SortInner);
   }
 
   llvm::Regex ExcludedFileRe;
   llvm::Regex SectionRe;
+  SortSectionPolicy SortOuter;
+  SortSectionPolicy SortInner;
 };
 
 struct InputSectionDescription : BaseCommand {
   InputSectionDescription(StringRef FilePattern)
       : BaseCommand(InputSectionKind),
         FileRe(compileGlobPatterns({FilePattern})) {}
   static bool classof(const BaseCommand *C);
   llvm::Regex FileRe;
-  SortSectionPolicy SortOuter = SortSectionPolicy::Default;
-  SortSectionPolicy SortInner = SortSectionPolicy::Default;
 
   // Input sections that matches at least one of SectionPatterns
   // will be associated with this InputSectionDescription.
   std::vector<SectionPattern> SectionPatterns;
 
   std::vector<InputSectionData *> Sections;
 };
 

ELF/LinkerScript.cpp

static bool matchConstraints(ArrayRef<InputSectionBase<ELFT> *> Sections,
   if (Kind == ConstraintKind::NoConstraint)
     return true;
   return llvm::all_of(Sections, [=](InputSectionData *Sec2) {
     auto *Sec = static_cast<InputSectionBase<ELFT> *>(Sec2);
     return checkConstraint(Sec->getSectionHdr()->sh_flags, Kind);
   });
 }
 
-static void sortSections(std::vector<InputSectionData *> &Sections,
+static void sortSections(InputSectionData **Begin, InputSectionData **End,
                          SortSectionPolicy K) {
   if (K != SortSectionPolicy::Default && K != SortSectionPolicy::None)
-    std::stable_sort(Sections.begin(), Sections.end(), getComparator(K));
+    std::stable_sort(Begin, End, getComparator(K));
 }
 
 // Compute and remember which sections the InputSectionDescription matches.
 template <class ELFT>
 void LinkerScript<ELFT>::computeInputSections(InputSectionDescription *I) {
   // Collects all sections that satisfy constraints of I
   // and attach them to I.
   for (SectionPattern &Pat : I->SectionPatterns) {
+    size_t SizeBefore = I->Sections.size();
     for (ObjectFile<ELFT> *F : Symtab<ELFT>::X->getObjectFiles()) {
       StringRef Filename = sys::path::filename(F->getName());
       if (!I->FileRe.match(Filename) || Pat.ExcludedFileRe.match(Filename))
         continue;
 
       for (InputSectionBase<ELFT> *S : F->getSections())
         if (!isDiscarded(S) && !S->OutSec && Pat.SectionRe.match(S->Name))
           I->Sections.push_back(S);
       if (Pat.SectionRe.match("COMMON"))
         I->Sections.push_back(CommonInputSection<ELFT>::X);
     }
-  }
 
     // Sort sections as instructed by SORT-family commands and --sort-section
     // option. Because SORT-family commands can be nested at most two depth
     // (e.g. SORT_BY_NAME(SORT_BY_ALIGNMENT(.text.*))) and because the command
     // line option is respected even if a SORT command is given, the exact
     // behavior we have here is a bit complicated. Here are the rules.
     //
     // 1. If two SORT commands are given, --sort-section is ignored.
     // 2. If one SORT command is given, and if it is not SORT_NONE,
     //    --sort-section is handled as an inner SORT command.
     // 3. If one SORT command is given, and if it is SORT_NONE, don't sort.
     // 4. If no SORT command is given, sort according to --sort-section.
-  if (I->SortOuter != SortSectionPolicy::None) {
-    if (I->SortInner == SortSectionPolicy::Default)
-      sortSections(I->Sections, Config->SortSection);
+    InputSectionData **Begin = I->Sections.data() + SizeBefore;
+    InputSectionData **End = I->Sections.data() + I->Sections.size();
+    if (Pat.SortOuter != SortSectionPolicy::None) {
+      if (Pat.SortInner == SortSectionPolicy::Default)
+        sortSections(Begin, End, Config->SortSection);
       else
-      sortSections(I->Sections, I->SortInner);
-    sortSections(I->Sections, I->SortOuter);
+        sortSections(Begin, End, Pat.SortInner);
+      sortSections(Begin, End, Pat.SortOuter);
+    }
   }
 
   // We do not add duplicate input sections, so mark them with a dummy output
   // section for now.
   for (InputSectionData *S : I->Sections) {
     auto *S2 = static_cast<InputSectionBase<ELFT> *>(S);
     S2->OutSec = (OutputSectionBase<ELFT> *)-1;
   }
private:
 
   SymbolAssignment *readAssignment(StringRef Name);
   std::vector<uint8_t> readFill();
   OutputSectionCommand *readOutputSectionDescription(StringRef OutSec);
   std::vector<uint8_t> readOutputSectionFiller(StringRef Tok);
   std::vector<StringRef> readOutputSectionPhdrs();
   InputSectionDescription *readInputSectionDescription(StringRef Tok);
   Regex readFilePatterns();
-  void readSectionExcludes(InputSectionDescription *Cmd);
+  std::vector<SectionPattern> readInputSectionsList(SortSectionPolicy SortOut,
+                                                    SortSectionPolicy SortIn);
+  std::vector<SectionPattern>
+  readSortedInputSectionsList(SortSectionPolicy SortOut);
   InputSectionDescription *readInputSectionRules(StringRef FilePattern);
   unsigned readPhdrType();
   SortSectionPolicy readSortKind();
   SymbolAssignment *readProvideHidden(bool Provide, bool Hidden);
   SymbolAssignment *readProvideOrAssignment(StringRef Tok, bool MakeAbsolute);
   void readSort();
   Expr readAssert();
 
   Expr readExpr();

 
 // Method reads a list of sequence of excluded files and section globs given in
 // a following form: ((EXCLUDE_FILE(file_pattern+))? section_pattern+)+
 // Example: *(.foo.1 EXCLUDE_FILE (*a.o) .foo.2 EXCLUDE_FILE (*b.o) .foo.3)
 // The semantics of that is next:
 // * Include .foo.1 from every file.
 // * Include .foo.2 from every file but a.o
 // * Include .foo.3 from every file but b.o
-void ScriptParser::readSectionExcludes(InputSectionDescription *Cmd) {
+std::vector<SectionPattern>
+ScriptParser::readInputSectionsList(SortSectionPolicy SortOut,
+                                    SortSectionPolicy SortIn) {
+  std::vector<SectionPattern> Ret;
   while (!Error && peek() != ")") {
     Regex ExcludeFileRe;
     if (skip("EXCLUDE_FILE")) {
       expect("(");
       ExcludeFileRe = readFilePatterns();
     }
 
     std::vector<StringRef> V;
     while (!Error && peek() != ")" && peek() != "EXCLUDE_FILE")
       V.push_back(next());
 
     if (!V.empty())
-      Cmd->SectionPatterns.push_back(
-          {std::move(ExcludeFileRe), compileGlobPatterns(V)});
+      Ret.push_back(
+          {std::move(ExcludeFileRe), compileGlobPatterns(V), SortOut, SortIn});
     else
       setError("section pattern is expected");
   }
-  expect(")");
+  return Ret;
 }
 
-InputSectionDescription *
-ScriptParser::readInputSectionRules(StringRef FilePattern) {
-  auto *Cmd = new InputSectionDescription(FilePattern);
+std::vector<SectionPattern>
+ScriptParser::readSortedInputSectionsList(SortSectionPolicy SortOut) {
+  std::vector<SectionPattern> V;
   expect("(");
-
-  // Read SORT().
-  SortSectionPolicy K1 = readSortKind();
-  if (K1 != SortSectionPolicy::Default) {
-    Cmd->SortOuter = K1;
-    expect("(");
-    SortSectionPolicy K2 = readSortKind();
-    if (K2 != SortSectionPolicy::Default) {
-      Cmd->SortInner = K2;
-      expect("(");
-      Cmd->SectionPatterns.push_back({Regex(), readFilePatterns()});
-      expect(")");
-    } else {
-      Cmd->SectionPatterns.push_back({Regex(), readFilePatterns()});
-    }
-    expect(")");
-    return Cmd;
-  }
+  SortSectionPolicy SortIn = readSortKind();
+  if (SortIn != SortSectionPolicy::Default) {
+    V = readInputSectionsList(SortOut, SortIn);
+    V = readInputSectionsList(SortOut, SortIn);
+  return V;
 
-  readSectionExcludes(Cmd);
+// Section pattern grammar can have complex expressions, for example:
+// *(SORT(.foo.* EXCLUDE_FILE (*file1.o) .bar.*) .bar.* SORT(.zed.*))
+// Generally is a sequence of globs and excludes that may be wrapped in a SORT()
+// commands, like: SORT(glob0) glob1 glob2 SORT(glob4)
+// This methods handles wrapping sequences of excluded files and section globs
+// into SORT() if that needed and reads them all.
+InputSectionDescription *
+ScriptParser::readInputSectionRules(StringRef FilePattern) {
+  auto *Cmd = new InputSectionDescription(FilePattern);
+  expect("(");
+  while (!HasError && !skip(")")) {
+    std::vector<SectionPattern> V;
+    SortSectionPolicy SortOut = readSortKind();
+    if (SortOut != SortSectionPolicy::Default)
+      V = readSortedInputSectionsList(SortOut);
+    else
+      V = readInputSectionsList(SortSectionPolicy::Default,
+                                SortSectionPolicy::Default);
+
+    std::move(V.begin(), V.end(), std::back_inserter(Cmd->SectionPatterns));
+  }
   return Cmd;
 }
 
 InputSectionDescription *
 ScriptParser::readInputSectionDescription(StringRef Tok) {
   // Input section wildcard can be surrounded by KEEP.
   // https://sourceware.org/binutils/docs/ld/Input-Section-Keep.html#Input-Section-Keep
   if (Tok == "KEEP") {

test/ELF/linkerscript/sort2.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %tfile1.o
+
+# RUN: echo "SECTIONS { .abc : { *(SORT(.foo.*) .bar.*) } }" > %t1.script
+# RUN: ld.lld -o %t1 --script %t1.script %tfile1.o
+# RUN: llvm-objdump -s %t1 | FileCheck %s
+
+# CHECK:  Contents of section .abc:
+# CHECK:   00e8 01000000 00000000 02000000 00000000
+# CHECK:   00f8 03000000 00000000 04000000 00000000
+# CHECK:   0108 06000000 00000000 05000000 00000000
+
+# RUN: echo "SECTIONS { \
+# RUN:   .abc : { *(SORT(.foo.* EXCLUDE_FILE (*file1.o) .bar.*) .bar.*) } \
+# RUN:  }" > %t2.script
+# RUN: ld.lld -o %t2 --script %t2.script %tfile1.o
+# RUN: llvm-objdump -s %t2 | FileCheck %s
+
+.text
+.globl _start
+_start:
+
+.section .foo.2,"a"
+ .quad 2
+
+.section .foo.3,"a"
+ .quad 3
+
+.section .foo.1,"a"
+ .quad 1
+
+.section .bar.4,"a"
+ .quad 4
+
+.section .bar.6,"a"
+ .quad 6
+
+.section .bar.5,"a"
+ .quad 5