[ELF] - Linkerscript: support all kinds of sorting (including nested).

[grimar]

Summary

Previously we supported only sorting by name.
I found that SORT_BY_ALIGNMENT is also often used in combination with nested sorting:
https://searchcode.com/codesearch/view/85938978/
https://searchcode.com/codesearch/view/47611074/

When there are nested section sorting commands in linker script, there can be at most 1
level of nesting for section sorting commands.

1. SORT_BY_NAME (SORT_BY_ALIGNMENT (wildcard section pattern)). It will sort the input

sections by name first, then by alignment if 2 sections have the same name.

2. SORT_BY_ALIGNMENT (SORT_BY_NAME (wildcard section pattern)). It will sort the input

sections by alignment first, then by name if 2 sections have the same alignment.

3. SORT_BY_NAME (SORT_BY_NAME (wildcard section pattern)) is treated the same as SORT_

BY_NAME (wildcard section pattern).

4. SORT_BY_ALIGNMENT (SORT_BY_ALIGNMENT (wildcard section pattern)) is treated the

same as SORT_BY_ALIGNMENT (wildcard section pattern).

5. All other nested section sorting commands are invalid.

Patch implements that all above.

[ruiu]

ELF/LinkerScript.cpp

59

Because we have limited number of patterns, we probably should handle all pattern as a grammar rather than a computed result. I think more straightforward code is something like this.

if (skip("SORT") || skip("SORT_BY_NAME)) {
  expect("(");
  if (skip("SORT_by_alignment") {
    InCmd->Sort = NameAlign;
    expect("(");
    readInputFilePattern(InCmd, Keep);
    expect(")");
  } else {
    InCmd->Sort = Name;
    readInputFilePattern(InCmd, Keep);
  }
  expect(")");
  return;
}

if (skip("SORT_BY_ALIGNMENT")) {
  expect("(");
  if (skip("SORT") || skip("SORT_BY_NAME")) {
    InCmd->Sort = AlignName;
    expect("(");
    readInputFilePattern(InCmd, Keep);
    expect(")");
  } else {
    InCmd->Sort = Align;
    readInputFilePattern(InCmd, Keep);
  }
  expect(")");
  return;
}

readInputFilePattern(InCmd, Keep);

[grimar]

• Addressed review comments.

[grimar]

ELF/LinkerScript.cpp

59

Ok.

[ruiu]

LGTM. I think there's a way to simplify it, but it can be done in a follow-up patch.

ELF/LinkerScript.h

struct OutputSectionCommand : BaseCommand {
   Expr AddrExpr;
   Expr AlignExpr;
   std::vector<std::unique_ptr<BaseCommand>> Commands;
   std::vector<StringRef> Phdrs;
   std::vector<uint8_t> Filler;
   ConstraintKind Constraint = ConstraintKind::NoConstraint;
 };
 
+enum class SortKind { None, Name, Align, NameAlign, AlignName };
+
 struct InputSectionDescription : BaseCommand {
   InputSectionDescription() : BaseCommand(InputSectionKind) {}
   static bool classof(const BaseCommand *C);
   StringRef FilePattern;
-  bool Sort = false;
+  SortKind Sort = SortKind::None;
   std::vector<StringRef> ExcludedFiles;
   std::vector<StringRef> SectionPatterns;
 };
 
 struct PhdrsCommand {
   StringRef Name;
   unsigned Type;
   bool HasFilehdr;

ELF/LinkerScript.cpp

bool OutputSectionCommand::classof(const BaseCommand *C) {
   return C->Kind == OutputSectionKind;
 }
 
 bool InputSectionDescription::classof(const BaseCommand *C) {
   return C->Kind == InputSectionKind;
 }
 
 template <class ELFT> static bool isDiscarded(InputSectionBase<ELFT> *S) {
   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;
static void addSection(OutputSectionFactory<ELFT> &Factory,
   OutputSectionBase<ELFT> *Sec;
   bool IsNew;
   std::tie(Sec, IsNew) = Factory.create(C, Name);
   if (IsNew)
     Out.push_back(Sec);
   Sec->addSection(C);
 }
 
-template <class ELFT>
-static bool compareByName(InputSectionBase<ELFT> *A,
-                          InputSectionBase<ELFT> *B) {
-  return A->getSectionName() < B->getSectionName();
+template <class ELFT> struct SectionsSorter {
+  SectionsSorter(SortKind Kind) : Kind(Kind) {}
+  bool operator()(InputSectionBase<ELFT> *A, InputSectionBase<ELFT> *B) {
+    int AlignmentCmp = A->Alignment - B->Alignment;
+    if (Kind == SortKind::Align || (Kind == SortKind::AlignName && AlignmentCmp != 0))
+      return AlignmentCmp < 0;
+
+    int NameCmp = A->getSectionName().compare(B->getSectionName());
+    if (Kind == SortKind::Name || (Kind == SortKind::NameAlign && NameCmp != 0))
+      return NameCmp < 0;
+
+    if (Kind == SortKind::NameAlign)
+      return AlignmentCmp < 0;
+    if (Kind == SortKind::AlignName)
+      return NameCmp < 0;
+
+    llvm_unreachable("unknown section sort kind in predicate");
+    return false;
   }
+  SortKind Kind;
+};
 
 template <class ELFT>
 void LinkerScript<ELFT>::createSections(
     std::vector<OutputSectionBase<ELFT> *> *Out,
     OutputSectionFactory<ELFT> &Factory) {
   OutputSections = Out;
 
   for (auto &P : getSectionMap()) {
     std::vector<InputSectionBase<ELFT> *> Sections;
     StringRef OutputName = P.first;
     const InputSectionDescription *I = P.second;
     for (InputSectionBase<ELFT> *S : getInputSections(I)) {
       if (OutputName == "/DISCARD/") {
         S->Live = false;
         reportDiscarded(S);
         continue;
       }
       Sections.push_back(S);
     }
-    if (I->Sort)
-      std::stable_sort(Sections.begin(), Sections.end(), compareByName<ELFT>);
+    if (I->Sort != SortKind::None)
+      std::stable_sort(Sections.begin(), Sections.end(),
+                       SectionsSorter<ELFT>(I->Sort));
     for (InputSectionBase<ELFT> *S : Sections)
       addSection(Factory, *Out, S, OutputName);
   }
 
   // Add all other input sections, which are not listed in script.
   for (const std::unique_ptr<ObjectFile<ELFT>> &F :
        Symtab<ELFT>::X->getObjectFiles())
     for (InputSectionBase<ELFT> *S : F->getSections())
private:
 
   SymbolAssignment *readAssignment(StringRef Name);
   void readOutputSectionDescription(StringRef OutSec);
   std::vector<uint8_t> readOutputSectionFiller();
   std::vector<StringRef> readOutputSectionPhdrs();
   std::unique_ptr<InputSectionDescription> readInputSectionDescription();
   void readInputFilePattern(InputSectionDescription *InCmd, bool Keep);
   void readInputSectionRules(InputSectionDescription *InCmd, bool Keep);
+
   unsigned readPhdrType();
   void readProvide(bool Hidden);
   void readAlign(OutputSectionCommand *Cmd);
   void readSort();
 
   Expr readExpr();
   Expr readExpr1(Expr Lhs, int MinPrec);
   Expr readPrimary();
void ScriptParser::readInputSectionRules(InputSectionDescription *InCmd,
   expect("(");
 
   if (skip("EXCLUDE_FILE")) {
     expect("(");
     while (!Error && !skip(")"))
       InCmd->ExcludedFiles.push_back(next());
   }
 
-  if (skip("SORT")) {
+  if (skip("SORT") || skip("SORT_BY_NAME")) {
+    expect("(");
+    if (skip("SORT_BY_ALIGNMENT")) {
+      InCmd->Sort = SortKind::NameAlign;
       expect("(");
-    InCmd->Sort = true;
       readInputFilePattern(InCmd, Keep);
       expect(")");
+    } else {
+      InCmd->Sort = SortKind::Name;
+      readInputFilePattern(InCmd, Keep);
+    }
+    expect(")");
+    return;
+  }
+
+  if (skip("SORT_BY_ALIGNMENT")) {
+    expect("(");
+    if (skip("SORT") || skip("SORT_BY_NAME")) {
+      InCmd->Sort = SortKind::AlignName;
+      expect("(");
+      readInputFilePattern(InCmd, Keep);
+      expect(")");
+    } else {
+      InCmd->Sort = SortKind::Align;
+      readInputFilePattern(InCmd, Keep);
+    }
+    expect(")");
     return;
   }
 
   readInputFilePattern(InCmd, Keep);
 }
 
 std::unique_ptr<InputSectionDescription>
 ScriptParser::readInputSectionDescription() {

test/ELF/linkerscript/Inputs/linkerscript-sort-nested.s

+.section .aaa.1, "a"
+.align 16
+.quad 0x11
+
+.section .aaa.2, "a"
+.align 4
+.quad 0x22

test/ELF/linkerscript/Inputs/linkerscript-sort.s

 .section .aaa.5, "a"
+.align 2
 .quad 0x55
 
 .section .aaa.1, "a"
+.align 32
 .quad 0x11
 
 .section .aaa.3, "a"
+.align 8
 .quad 0x33
 
 .section .aaa.2, "a"
+.align 16
 .quad 0x22
 
 .section .aaa.4, "a"
+.align 4
 .quad 0x44

test/ELF/linkerscript/linkerscript-sort-nested.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t1.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux \
+# RUN:   %p/Inputs/linkerscript-sort-nested.s -o %t2.o
+
+## Check sorting first by alignment and then by name.
+# RUN: echo "SECTIONS { .aaa : { *(SORT_BY_ALIGNMENT(SORT_BY_NAME(.aaa.*))) } }" > %t1.script
+# RUN: ld.lld -o %t1 --script %t1.script %t1.o %t2.o
+# RUN: llvm-objdump -s %t1 | FileCheck -check-prefix=SORTED_AN %s
+# SORTED_AN:      Contents of section .aaa:
+# SORTED_AN-NEXT:  0120 02000000 00000000 22000000 00000000
+# SORTED_AN-NEXT:  0130 11000000 00000000 00000000 00000000
+# SORTED_AN-NEXT:  0140 55000000 00000000 00000000 00000000
+# SORTED_AN-NEXT:  0150 00000000 00000000 00000000 00000000
+# SORTED_AN-NEXT:  0160 01000000 00000000
+
+## Check sorting first by name and then by alignment.
+# RUN: echo "SECTIONS { .aaa : { *(SORT_BY_NAME(SORT_BY_ALIGNMENT(.aaa.*))) } }" > %t2.script
+# RUN: ld.lld -o %t2 --script %t2.script %t1.o %t2.o
+# RUN: llvm-objdump -s %t2 | FileCheck -check-prefix=SORTED_NA %s
+# SORTED_NA:      Contents of section .aaa:
+# SORTED_NA-NEXT:  0120 11000000 00000000 00000000 00000000
+# SORTED_NA-NEXT:  0130 00000000 00000000 00000000 00000000
+# SORTED_NA-NEXT:  0140 01000000 00000000 02000000 00000000
+# SORTED_NA-NEXT:  0150 22000000 00000000 00000000 00000000
+# SORTED_NA-NEXT:  0160 55000000 00000000
+
+.global _start
+_start:
+ nop
+
+.section .aaa.1, "a"
+.align 32
+.quad 1
+
+.section .aaa.2, "a"
+.align 2
+.quad 2
+
+.section .aaa.5, "a"
+.align 16
+.quad 0x55

test/ELF/linkerscript/linkerscript-sort.s

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t1.o
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux \
 # RUN:   %p/Inputs/linkerscript-sort.s -o %t2.o
 
 # RUN: echo "SECTIONS { .aaa : { *(.aaa.*) } }" > %t1.script
 # RUN: ld.lld -o %t1 --script %t1.script %t2.o %t1.o
 # RUN: llvm-objdump -s %t1 | FileCheck -check-prefix=UNSORTED %s
-# UNSORTED:      Contents of section .aaa:
-# UNSORTED-NEXT:   0120 55000000 00000000 11000000 00000000
-# UNSORTED-NEXT:   0130 33000000 00000000 22000000 00000000
-# UNSORTED-NEXT:   0140 44000000 00000000 05000000 00000000
-# UNSORTED-NEXT:   0150 01000000 00000000 03000000 00000000
-# UNSORTED-NEXT:   0160 02000000 00000000 04000000 00000000
+# UNSORTED:       Contents of section .aaa:
+# UNSORTED-NEXT:   0120 55000000 00000000 00000000 00000000
+# UNSORTED-NEXT:   0130 00000000 00000000 00000000 00000000
+# UNSORTED-NEXT:   0140 11000000 00000000 33000000 00000000
+# UNSORTED-NEXT:   0150 22000000 00000000 44000000 00000000
+# UNSORTED-NEXT:   0160 05000000 00000000 01000000 00000000
+# UNSORTED-NEXT:   0170 03000000 00000000 02000000 00000000
+# UNSORTED-NEXT:   0180 04000000 00000000
 
 ## Check that SORT works (sorted by name of section).
 # RUN: echo "SECTIONS { .aaa : { *(SORT(.aaa.*)) } }" > %t2.script
 # RUN: ld.lld -o %t2 --script %t2.script %t2.o %t1.o
 # RUN: llvm-objdump -s %t2 | FileCheck -check-prefix=SORTED_A %s
 # SORTED_A:      Contents of section .aaa:
 # SORTED_A-NEXT:  0120 11000000 00000000 01000000 00000000
 # SORTED_A-NEXT:  0130 22000000 00000000 02000000 00000000
 # SORTED_A-NEXT:  0140 33000000 00000000 03000000 00000000
-# SORTED_A-NEXT:  0150 44000000 00000000 04000000 00000000
-# SORTED_A-NEXT:  0160 55000000 00000000 05000000 00000000
+# SORTED_A-NEXT:  0150 44000000 00000000 00000000 00000000
+# SORTED_A-NEXT:  0160 04000000 00000000 55000000 00000000
+# SORTED_A-NEXT:  0170 00000000 00000000 00000000 00000000
+# SORTED_A-NEXT:  0180 05000000 00000000
 
 ## When we switch the order of files, check that sorting by
 ## section names is stable.
 # RUN: echo "SECTIONS { .aaa : { *(SORT(.aaa.*)) } }" > %t3.script
 # RUN: ld.lld -o %t3 --script %t3.script %t1.o %t2.o
 # RUN: llvm-objdump -s %t3 | FileCheck -check-prefix=SORTED_B %s
 # SORTED_B:      Contents of section .aaa:
-# SORTED_B-NEXT:  0120 01000000 00000000 11000000 00000000
-# SORTED_B-NEXT:  0130 02000000 00000000 22000000 00000000
-# SORTED_B-NEXT:  0140 03000000 00000000 33000000 00000000
-# SORTED_B-NEXT:  0150 04000000 00000000 44000000 00000000
-# SORTED_B-NEXT:  0160 05000000 00000000 55000000 00000000
+# SORTED_B-NEXT:  0120 01000000 00000000 00000000 00000000
+# SORTED_B-NEXT:  0130 00000000 00000000 00000000 00000000
+# SORTED_B-NEXT:  0140 11000000 00000000 02000000 00000000
+# SORTED_B-NEXT:  0150 22000000 00000000 03000000 00000000
+# SORTED_B-NEXT:  0160 33000000 00000000 00000000 00000000
+# SORTED_B-NEXT:  0170 04000000 00000000 44000000 00000000
+# SORTED_B-NEXT:  0180 05000000 00000000 55000000 00000000
 
 ## Check that SORT surrounded with KEEP also works.
 # RUN: echo "SECTIONS { .aaa : { KEEP (*(SORT(.aaa.*))) } }" > %t3.script
 # RUN: ld.lld -o %t3 --script %t3.script %t2.o %t1.o
 # RUN: llvm-objdump -s %t3 | FileCheck -check-prefix=SORTED_A %s
 
+## Check that SORT_BY_NAME works (SORT is alias).
+# RUN: echo "SECTIONS { .aaa : { *(SORT_BY_NAME(.aaa.*)) } }" > %t4.script
+# RUN: ld.lld -o %t4 --script %t4.script %t2.o %t1.o
+# RUN: llvm-objdump -s %t4 | FileCheck -check-prefix=SORTED_A %s
+
+## Check that sections ordered by alignment.
+# RUN: echo "SECTIONS { .aaa : { *(SORT_BY_ALIGNMENT(.aaa.*)) } }" > %t5.script
+# RUN: ld.lld -o %t5 --script %t5.script %t1.o %t2.o
+# RUN: llvm-objdump -s %t5 | FileCheck -check-prefix=SORTED_ALIGNMENT %s
+# SORTED_ALIGNMENT:      Contents of section .aaa:
+# SORTED_ALIGNMENT-NEXT:   0120 01000000 00000000 55000000 00000000
+# SORTED_ALIGNMENT-NEXT:   0130 02000000 00000000 44000000 00000000
+# SORTED_ALIGNMENT-NEXT:   0140 03000000 00000000 33000000 00000000
+# SORTED_ALIGNMENT-NEXT:   0150 04000000 00000000 00000000 00000000
+# SORTED_ALIGNMENT-NEXT:   0160 22000000 00000000 00000000 00000000
+# SORTED_ALIGNMENT-NEXT:   0170 00000000 00000000 00000000 00000000
+# SORTED_ALIGNMENT-NEXT:   0180 05000000 00000000 00000000 00000000
+# SORTED_ALIGNMENT-NEXT:   0190 00000000 00000000 00000000 00000000
+# SORTED_ALIGNMENT-NEXT:   01a0 11000000 00000000                  
+
 .global _start
 _start:
  nop
 
 .section .aaa.5, "a"
+.align 32
 .quad 5
 
 .section .aaa.1, "a"
+.align 2
 .quad 1
 
 .section .aaa.3, "a"
+.align 8
 .quad 3
 
 .section .aaa.2, "a"
+.align 4
 .quad 2
 
 .section .aaa.4, "a"
+.align 16
 .quad 4