[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 ↗

(On Diff #71917)

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?

197–198 ↗

(On Diff #71917)

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

764–765 ↗

(On Diff #71917)

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

1098–1099 ↗

(On Diff #71917)

Returns a new vector instead of mutating the argument.

ELF/LinkerScript.h

104–105 ↗

(On Diff #71917)

So1 -> Sort1

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

119–120 ↗

(On Diff #71917)

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

[grimar]

• Addressed review comments.

[grimar]

ELF/LinkerScript.cpp

159–160 ↗

(On Diff #71917)

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

197–198 ↗

(On Diff #71917)

Done.

764–765 ↗

(On Diff #71917)

Done.

1098–1099 ↗

(On Diff #71917)

Done.

ELF/LinkerScript.h

104–105 ↗

(On Diff #71917)

Done.

119–120 ↗

(On Diff #71917)

Done.

[ruiu]

ELF/LinkerScript.cpp

774–775 ↗

(On Diff #72023)

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 ↗

(On Diff #72023)

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 ↗

(On Diff #72023)

Done.

1133–1137 ↗

(On Diff #72023)

:) 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

lld/trunk/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)
       : ExcludedFileRe(std::forward<llvm::Regex>(Re1)),
         SectionRe(std::forward<llvm::Regex>(Re2)) {}
 
   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;
 };
 

lld/trunk/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();
   InputSectionDescription *readInputSectionRules(StringRef FilePattern);
   unsigned readPhdrType();
   SortSectionPolicy readSortKind();
   SymbolAssignment *readProvideHidden(bool Provide, bool Hidden);
   SymbolAssignment *readProvideOrAssignment(StringRef Tok, bool MakeAbsolute);
   void readSort();
   Expr readAssert();
 

 
 // 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() {
+  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)});
     else
       setError("section pattern is expected");
   }
-  expect(")");
+  return Ret;
 }
 
+// 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("(");
-
-  // Read SORT().
-  SortSectionPolicy K1 = readSortKind();
-  if (K1 != SortSectionPolicy::Default) {
-    Cmd->SortOuter = K1;
+  while (!HasError && !skip(")")) {
+    SortSectionPolicy Outer = readSortKind();
+    SortSectionPolicy Inner = SortSectionPolicy::Default;
+    std::vector<SectionPattern> V;
+    if (Outer != SortSectionPolicy::Default) {
       expect("(");
-    SortSectionPolicy K2 = readSortKind();
-    if (K2 != SortSectionPolicy::Default) {
-      Cmd->SortInner = K2;
+      Inner = readSortKind();
+      if (Inner != SortSectionPolicy::Default) {
         expect("(");
-      Cmd->SectionPatterns.push_back({Regex(), readFilePatterns()});
+        V = readInputSectionsList();
         expect(")");
       } else {
-      Cmd->SectionPatterns.push_back({Regex(), readFilePatterns()});
+        V = readInputSectionsList();
       }
       expect(")");
-    return Cmd;
+    } else {
+      V = readInputSectionsList();
     }
 
-  readSectionExcludes(Cmd);
+    for (SectionPattern &Pat : V) {
+      Pat.SortInner = Inner;
+      Pat.SortOuter = Outer;
+    }
+
+    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") {

lld/trunk/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