[ELF] Sort by input order within an input section description

[MaskRay]

Summary

According to
https://sourceware.org/binutils/docs/ld/Input-Section-Basics.html#Input-Section-Basics
for *(.a .b), the order should match the input order:

• for ld 1.o 2.o, sections from 1.o precede sections from 2.o
• within a file, .a and .b appear in the section header table order

This patch implements the behavior. The interaction with SORT* and --sort-section is:

Matched sections are ordered by radix sort with the keys being (SORT*, --sort-section, input order),
where SORT* (if present) is most significant.

Note, multiple SORT* within an input section description has undocumented and
confusing behaviors in GNU ld:
https://sourceware.org/pipermail/binutils/2020-November/114083.html
Therefore multiple SORT* is not the focus for this patch but
this patch still strives to have an explainable behavior.

As an example, we partition SORT(a.*) b.* c.* SORT(d.*), into
SORT(a.*) | b.* c.* | SORT(d.*) and perform sorting within groups. Sections
matched by patterns between two SORT* are sorted by input order. If
--sort-alignment is given, they are sorted by --sort-alignment, breaking tie by
input order.

This patch also allows a section to be matched by multiple patterns, previously
duplicated sections could occupy more space in the output and had erroneous zero bytes.

The patch is in preparation for support for
*(SORT_BY_INIT_PRIORITY(.init_array.* .ctors.*)) *(.init_array .ctors),
which will allow LLD to mix .ctors*/.init_array* like GNU ld (gold's --ctors-in-init-array)
PR44698 and PR48096

[grimar]

This patch also fixes 2 bugs:
The second SORT in *(SORT(...) SORT(...)) is incorrectly parsed as a file pattern
A section may be added multiple times if it multiple patterns match it

Can these bug fixes be separated to their own reviews (at least the first one seems can be independent)?

lld/ELF/LinkerScript.cpp

436

I am not sure that doing 2 lookups in the DenseMap on each predicate call is a good idea.

445–449

So, with it it is also possible to do lookup in pos twice:
one here and one with pos[sec] |= 1;

It looks a bit dirty. I think usually double lookup situation is avoided.

472

Looks a bit hacky approach to me.

477

You don't need to call sortByPosition here? It is always sorted I believe.

497

I've experimented with the implementation and got the following
version that addresses all my concerns/comments. What do you think?

// Compute and remember which sections the InputSectionDescription matches.
std::vector<InputSectionBase *>
LinkerScript::computeInputSections(const InputSectionDescription *cmd,
                                   ArrayRef<InputSectionBase *> sections) {
  std::vector<InputSectionBase *> ret;
  SetVector<size_t> indices; // Parallel to ret.

  // Collects all sections that satisfy constraints of Cmd.
  size_t sizeLastSort = 0;
  for (const SectionPattern &pat : cmd->sectionPatterns) {
    size_t sizeBefore = ret.size();

    for (size_t I = 0, E = sections.size(); I != E; ++I) {
      InputSectionBase *sec = sections[I];
      if (!sec->isLive() || sec->parent || indices.contains(I))
        continue;

      // For -emit-relocs we have to ignore entries like
      //   .rela.dyn : { *(.rela.data) }
      // which are common because they are in the default bfd script.
      // We do not ignore SHT_REL[A] linker-synthesized sections here because
      // want to support scripts that do custom layout for them.
      if (isa<InputSection>(sec) &&
          cast<InputSection>(sec)->getRelocatedSection())
        continue;

      // Check the name early to improve performance in the common case.
      if (!pat.sectionPat.match(sec->name))
        continue;

      if (!cmd->matchesFile(sec->file) || pat.excludesFile(sec->file) ||
          (sec->flags & cmd->withFlags) != cmd->withFlags ||
          (sec->flags & cmd->withoutFlags) != 0)
        continue;

      indices.insert(I);
      ret.push_back(sec);
    }

    if (pat.sortOuter == SortSectionPolicy::Default)
      continue;

    sortInputSections(
        MutableArrayRef<InputSectionBase *>(ret).slice(sizeBefore),
        pat.sortOuter, pat.sortInner);
    sizeLastSort = ret.size();
  }

  std::vector<size_t> indicesV = indices.takeVector();
  llvm::sort(MutableArrayRef<size_t>(indicesV).slice(sizeLastSort),
             [&](size_t l, size_t r) { return l < r; });

  for (size_t I = sizeLastSort, E = ret.size(); I != E; ++I)
    ret[I] = sections[indicesV[I]];

  sortInputSections(
      MutableArrayRef<InputSectionBase *>(ret).slice(sizeLastSort),
      config->sortSection, SortSectionPolicy::None);
  return ret;
}

[MaskRay]

Comments

Move a bugfix to D91180

lld/ELF/LinkerScript.cpp

472

This could be another DenseSet, but that would have more overhead. So I reused the map.

477

This is the key. We need to sort patterns between two SORT by position.

Similarly, we need to sort the trailing patterns outside of the loop (if the last pattern is not SORT)

[MaskRay]

Fix a comment

[MaskRay]

Optimize

[MaskRay]

Take into account --sort-section and add a test.

[psmith]

It took a lot of staring at that bit of code to work out what was going on. If I have understood it correctly. In particular I got confused with the sizeBefore and sizeLastSort with sizeBefore being the larger value. It took me a while to spot the continue. If I've understood correctly:

• sizeBefore is really sizeOfRetBeforeNextSort
• sizeLastSort is really sizeOfRetAfterPreviousSort

If possible could we use Prev rather than Last as it is more specific. Last can mean the last one we went by, or the last one in the list. I strongly recommend adding something like Next to sizeBefore so that it is clear that sizeBefore >= sizeLastSort.

It would be good to write a comment explaining how the partitions work as there are a lot of sorts, some of the indices and some of the sections.

[MaskRay]

Improve comments
Change size* names

[psmith]

lld/ELF/LinkerScript.cpp

482

Thanks for the update, I think the new names are much better. One small nit, I think in sizeBeforePat should be sizeBeforeCurrPat in

ret[sizeBeforePat,ret.size())

[grimar]

lld/ELF/LinkerScript.cpp

430

The more common name in LLD for this would be seen

[MaskRay]

Improve comments

[MaskRay]

Thanks for the comments. I have improved comments and rewritten a significant portion of the description.
I added this paragraph:

Note, multiple SORT* within an input section description has undocumented and confusing behaviors in GNU ld: https://sourceware.org/pipermail/binutils/2020-November/114083.html
Therefore multiple SORT* is not the focus for this patch but this patch still strives to have an explainable behavior.

[grimar]

LGTM. Please wait for final word from Peter.

[psmith]

Thanks for the updates, LGTM too.

lld/ELF/LinkerScript.cpp

 // 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.
 static void sortInputSections(MutableArrayRef<InputSectionBase *> vec,
-                              const SectionPattern &pat) {
-  if (pat.sortOuter == SortSectionPolicy::None)
+                              SortSectionPolicy outer,
+                              SortSectionPolicy inner) {
+  if (outer == SortSectionPolicy::None)
     return;
 
-  if (pat.sortInner == SortSectionPolicy::Default)
+  if (inner == SortSectionPolicy::Default)
     sortSections(vec, config->sortSection);
   else
-    sortSections(vec, pat.sortInner);
-  sortSections(vec, pat.sortOuter);
+    sortSections(vec, inner);
+  sortSections(vec, outer);
 }
 
 // Compute and remember which sections the InputSectionDescription matches.
 std::vector<InputSectionBase *>
 LinkerScript::computeInputSections(const InputSectionDescription *cmd,
                                    ArrayRef<InputSectionBase *> sections) {
   std::vector<InputSectionBase *> ret;
+  std::vector<size_t> indexes;
+  DenseSet<size_t> seen;
+  auto sortByPositionThenCommandLine = [&](size_t begin, size_t end) {
+    llvm::sort(MutableArrayRef<size_t>(indexes).slice(begin, end - begin));
+    for (size_t i = begin; i != end; ++i)
+      ret[i] = sections[indexes[i]];
+    sortInputSections(
+        MutableArrayRef<InputSectionBase *>(ret).slice(begin, end - begin),
+        config->sortSection, SortSectionPolicy::None);
+  };
 
   // Collects all sections that satisfy constraints of Cmd.
+  size_t sizeAfterPrevSort = 0;
   for (const SectionPattern &pat : cmd->sectionPatterns) {
-    size_t sizeBefore = ret.size();
+    size_t sizeBeforeCurrPat = ret.size();
 
-    for (InputSectionBase *sec : sections) {
-      if (!sec->isLive() || sec->parent)
+    for (size_t i = 0, e = sections.size(); i != e; ++i) {
+      // Skip if the section is dead or has been matched by a previous input
+      // section description or a previous pattern.
+      InputSectionBase *sec = sections[i];
+      if (!sec->isLive() || sec->parent || seen.contains(i))
         continue;
 
       // For -emit-relocs we have to ignore entries like
       //   .rela.dyn : { *(.rela.data) }
       // which are common because they are in the default bfd script.
       // We do not ignore SHT_REL[A] linker-synthesized sections here because
       // want to support scripts that do custom layout for them.
       if (isa<InputSection>(sec) &&
           cast<InputSection>(sec)->getRelocatedSection())
         continue;
 
       // Check the name early to improve performance in the common case.
       if (!pat.sectionPat.match(sec->name))
         continue;
 
       if (!cmd->matchesFile(sec->file) || pat.excludesFile(sec->file) ||
           (sec->flags & cmd->withFlags) != cmd->withFlags ||
           (sec->flags & cmd->withoutFlags) != 0)
         continue;
 
       ret.push_back(sec);
+      indexes.push_back(i);
+      seen.insert(i);
     }
 
+    if (pat.sortOuter == SortSectionPolicy::Default)
+      continue;
+
+    // Matched sections are ordered by radix sort with the keys being (SORT*,
+    // --sort-section, input order), where SORT* (if present) is most
+    // significant.
+    //
+    // Matched sections between the previous SORT* and this SORT* are sorted by
+    // (--sort-alignment, input order).
+    sortByPositionThenCommandLine(sizeAfterPrevSort, sizeBeforeCurrPat);
+    // Matched sections by this SORT* pattern are sorted using all 3 keys.
+    // ret[sizeBeforeCurrPat,ret.size()) are already in the input order, so we
+    // just sort by sortOuter and sortInner.
     sortInputSections(
-        MutableArrayRef<InputSectionBase *>(ret).slice(sizeBefore), pat);
-  }
+        MutableArrayRef<InputSectionBase *>(ret).slice(sizeBeforeCurrPat),
+        pat.sortOuter, pat.sortInner);
+    sizeAfterPrevSort = ret.size();
+  }
+  // Matched sections after the last SORT* are sorted by (--sort-alignment,
+  // input order).
+  sortByPositionThenCommandLine(sizeAfterPrevSort, ret.size());
   return ret;
 }
 
 void LinkerScript::discard(InputSectionBase *s) {
   if (s == in.shStrTab || s == mainPart->relrDyn)
     error("discarding " + s->name + " section is not allowed");
 
   // You can discard .hash and .gnu.hash sections by linker scripts. Since
   // they are synthesized sections, we need to handle them differently than
   // other regular sections.

lld/test/ELF/linkerscript/exclude-multiple.s

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %tfile1.o
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %p/Inputs/exclude-multiple1.s -o %tfile2.o
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %p/Inputs/exclude-multiple2.s -o %tfile3.o
 # RUN: echo "SECTIONS { \
 # RUN:   .foo : { *(.foo.1 EXCLUDE_FILE (*file1.o) .foo.2 EXCLUDE_FILE (*file2.o) .foo.3) } \
 # RUN:  }" > %t1.script
 # RUN: ld.lld -script %t1.script %tfile1.o %tfile2.o %tfile3.o -o %t1.o
 # RUN: llvm-objdump -s %t1.o | FileCheck %s
 
+## Sections from %tfile1 precede sections from %tfile2 and %tfile3.
+## In each file, the sections are added in the original order.
 # CHECK:      Contents of section .foo:
-# CHECK-NEXT:  01000000 00000000 04000000 00000000
-# CHECK-NEXT:  07000000 00000000 05000000 00000000
-# CHECK-NEXT:  08000000 00000000 03000000 00000000
+# CHECK-NEXT:  03000000 00000000 01000000 00000000
+# CHECK-NEXT:  04000000 00000000 05000000 00000000
+# CHECK-NEXT:  07000000 00000000 08000000 00000000
 # CHECK-NEXT:  09000000 00000000
 # CHECK-NEXT: Contents of section .foo.2:
 # CHECK-NEXT:  02000000 00000000
 # CHECK-NEXT: Contents of section .foo.3:
 # CHECK-NEXT:  06000000 00000000
 
 # RUN: echo "SECTIONS { .foo : { *(EXCLUDE_FILE (*file1.o) EXCLUDE_FILE (*file2.o) .foo.3) } }" > %t2.script
 # RUN: not ld.lld -script %t2.script %tfile1.o %tfile2.o %tfile3.o -o /dev/null 2>&1 | \
 # RUN:   FileCheck %s --check-prefix=ERR
 # ERR: section pattern is expected
 
 # RUN: echo "SECTIONS { .foo : { *(EXCLUDE_FILE (*file1.o)) } }" > %t3.script
 # RUN: not ld.lld -script %t3.script %tfile1.o %tfile2.o %tfile3.o -o /dev/null 2>&1 | \
 # RUN:   FileCheck %s --check-prefix=ERR
 
-.section .foo.1,"a"
- .quad 1
-
 .section .foo.2,"a"
  .quad 2
 
+## %tfile1.o(.foo.3) precedes %tfile.o(.foo.1) in the output section.
 .section .foo.3,"a"
  .quad 3
+
+.section .foo.1,"a"
+ .quad 1

lld/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.*) .a* .a* SORT(.bar.*) .b*) } }" > %t1.script
 # RUN: ld.lld -o %t1 --script %t1.script %tfile1.o
 # RUN: llvm-readelf -x .abc %t1 | FileCheck %s
 
-## FIXME Some input sections are duplicated in .abc and their second occurrences are zeros.
+## Sections matched by patterns between two SORT are sorted separately by input order.
+## Note, GNU ld has a strange behavior with more than one SORT* https://sourceware.org/pipermail/binutils/2020-November/114083.html
+## In the absence of SORT, our multi-pattern behavior matches GNU ld.
 # CHECK:      Hex dump of section '.abc'
-# CHECK-NEXT: 0x00000000 01020306 05040000 00070908 0b0c0a
+# CHECK-NEXT: 0x00000000 01020306 05040708 090b0c0a
 
 # RUN: echo "SECTIONS { \
 # RUN:   .abc : { *(SORT(.foo.* EXCLUDE_FILE (*file1.o) .bar.*) .a* SORT(.bar.*) .b*) } \
 # RUN:  }" > %t2.script
 # RUN: ld.lld -o %t2 --script %t2.script %tfile1.o
 # RUN: llvm-readelf -x .abc %t2 | FileCheck %s
 
+## Non-SORT patterns are sorted by --sort-section, breaking tie by input order.
+# RUN: ld.lld -o %t4 --script %t1.script --sort-section=name %tfile1.o
+# RUN: llvm-readelf -x .abc %t4 | FileCheck %s --check-prefix=CHECK2
+
+# CHECK2:      Hex dump of section '.abc'
+# CHECK2-NEXT: 0x00000000 01020304 05060708 090a0b0c
+
 .text
 .globl _start
 _start:
 
 .section .foo.2,"a"; .byte 2
 .section .foo.3,"a"; .byte 3
 .section .foo.1,"a"; .byte 1