[ELF] Change way we place non-scripted (orphan) sections

[evgeny777]

Summary

Currently implemented algorithm doesn't work well for me, because my linker scripts put RW or RWX sections first. For example

SECTIONS {
   .rwx : { *(.rwx) } /* RWX sections go here */
   .ro : { *(.ro) } /* RO sections go after RWX */
}

If there is any RO orphan section in linked image it will be placed before RWX sections and produce extra PT_LOAD. This doesn't match nor gold nor ld behavior.
The approach I'm currently using (and one this patch implements) is to first find sections which can share same PT_LOAD with some orphan section. If such sections have been found they are compared with orphan section using compareSectionsNonScript<ELFT>() and best insertion position is chosen. If no section has equal access attributes then insertion position is found using current algorithm (insert before first section which is greater in sort order).

I don't know if this is right way to go, but this works much better for me (I don't have to edit scripts and results match ld/gold)

[davide]

@emaste might want to confirm this doesn't break linking the FreeBSD kernel.

[• rafael]

ELF/Writer.cpp

773

This needs to be updated.

812

This is a bit hard to read. Maybe you can write a lambda that given two candidates decides which one is better for placing the orphan. That way this would be

std:: max_element(I, NonScriptI, [&] (OutputSectionBase<ELFT> *A, OutputSectionBase<ELFT> *B) {
...
}

And if I understand correctly, the logic would be

• Prefer A/B if one can share a PT_LOAD.
• Prefer A/B if the element compares less than one.
• Otherwise prefer the last one.

[evgeny777]

ELF/Writer.cpp

812

I don't think max_element makes sense here, because this code is about finding best insertion position, not any kind of maximum.
This newer code implements two passes on OutputSections: first pass is done on subset of sections which can share PT_LOAD with NonScriptI and second pass is done on all sections. Hope it's easier to understand now.

[evgeny777]

Two-pass approach

[evgeny777]

Rebased + modified test case orphan.s

ELF/Writer.cpp

template <class ELFT> void Writer<ELFT>::createSections() {
   sortInitFini(findSection(".fini_array"));
   sortCtorsDtors(findSection(".ctors"));
   sortCtorsDtors(findSection(".dtors"));
 
   for (OutputSectionBase<ELFT> *Sec : OutputSections)
     Sec->assignOffsets();
 }
 
+template <class ELFT>
+static bool canSharePtLoad(OutputSectionBase<ELFT> *S1, OutputSectionBase<ELFT> *S2) {
+  if (!(S1->getFlags() & SHF_ALLOC) || !(S2->getFlags() & SHF_ALLOC))
+    return false;
+
+  return (S1->getFlags() & (SHF_WRITE | SHF_EXECINSTR)) ==
+         (S2->getFlags() & (SHF_WRITE | SHF_EXECINSTR));
+}
+
 template <class ELFT> void Writer<ELFT>::sortSections() {
   if (!ScriptConfig->HasSections) {
     std::stable_sort(OutputSections.begin(), OutputSections.end(),
                      compareSectionsNonScript<ELFT>);
     return;
   }
   Script<ELFT>::X->adjustSectionsBeforeSorting();
 
template <class ELFT> void Writer<ELFT>::sortSections() {
   //   .a (rx) # not in script
   //   .b (rx) # in script
   //   .c (ro) # in script
   //   .d (ro) # not in script
   //
   // The way we define an order then is:
   // *  First put script sections at the start and sort the script and
   //    non-script sections independently.
   // *  Move each non-script section to the first position where it
   //    compareSectionsNonScript less than the successor.
 
   std::stable_sort(OutputSections.begin(), OutputSections.end(),
                    compareSections<ELFT>);
 
-  auto I = OutputSections.begin();
   auto E = OutputSections.end();
-  auto NonScriptI = std::find_if(I, E, [](OutputSectionBase<ELFT> *S) {
+  auto NonScriptI =
+      std::find_if(OutputSections.begin(), E, [](OutputSectionBase<ELFT> *S) {
         return Script<ELFT>::X->getSectionIndex(S->getName()) == INT_MAX;
       });
+
+  // Find first greater element in a filtered range [I, NonScriptI].
+  auto findGreater =
+      [&](std::function<bool(OutputSectionBase<ELFT> *)> Filter) {
+        auto Ret = E;
+        for (auto I = OutputSections.begin(); I != NonScriptI; ++I)
+          if (Filter(*I)) {
+            // If filtered element is before *NonScriptI we'd
+            // prefer to insert *NonScriptI immediately before it.
+            if (compareSectionsNonScript<ELFT>(*NonScriptI, *I))
+              return I;
+            // If filtered element is less than *NonScriptI we'd
+            // prefer to insert *NonScriptI immediately after it.
+            Ret = I + 1;
+          }
+        return Ret;
+      };
+
   while (NonScriptI != E) {
-    auto FirstGreater =
-        std::find_if(I, NonScriptI, [&](OutputSectionBase<ELFT> *S) {
-          return compareSectionsNonScript<ELFT>(*NonScriptI, S);
-        });
+    // Try to find best place to put orphan (non-scripted) section N before
+    // some scripted section S in order to minimize number of PT_LOAD segments.
+    // We'll try to use following places, according to their priorities (1,2,3):
+    //   1) Before section S with same access attributes, 
+    //      if compareSectionsNonScript(N,S) is true.
+    //   2) After the last section with same access attributes, if any
+    //   3) Before any section for which compareSectionsNonScript(N, S) is true.
+    //      In such case there are no sections which can share segment with section N.
+
+    auto FirstGreater = findGreater([&](OutputSectionBase<ELFT> *S) {
+      return canSharePtLoad(S, *NonScriptI);
+    if (FirstGreater == E)
+      FirstGreater =
+          findGreater([&](OutputSectionBase<ELFT> *) { return true; });
+
+    if (FirstGreater != E)
       std::rotate(FirstGreater, NonScriptI, NonScriptI + 1);
     ++NonScriptI;
-    ++I;
   }
 }
 
 // Create output section objects and add them to OutputSections.
 template <class ELFT> void Writer<ELFT>::finalizeSections() {
   Out<ELFT>::DebugInfo = findSection(".debug_info");
   Out<ELFT>::PreinitArray = findSection(".preinit_array");
   Out<ELFT>::InitArray = findSection(".init_array");

test/ELF/linkerscript/merge-sections.s

 # CHECK-NEXT:   EntrySize: 2
 # CHECK-NEXT: }
 # CHECK-NEXT: Section {
 # CHECK-NEXT:   Index:
 # CHECK-NEXT:   Name:
 # CHECK-NEXT:   Type:
 # CHECK-NEXT:   Flags [
 # CHECK-NEXT:     SHF_ALLOC
-# CHECK-NEXT:     SHF_EXECINSTR
 # CHECK-NEXT:   ]
 # CHECK-NEXT:   Address: 0x[[ADDR2:.*]]
 # CHECK-NEXT:   Offset: 0x[[ADDR2]]
 
 
 # CHECK:      Name: begin
 # CHECK-NEXT: Value: 0x[[ADDR1]]
 

test/ELF/linkerscript/no-space.s

 # CHECK: Program Headers:
 # CHECK-NEXT: Type  Offset   VirtAddr           PhysAddr
 # CHECK-NEXT: PHDR
 # CHECK-NEXT: LOAD  0x001000 0x0000000000000000 0x0000000000000000
 
 # CHECK:      Section to Segment mapping:
 # CHECK-NEXT:  Segment Sections...
 # CHECK-NEXT:   00
-# CHECK-NEXT:   01     foo .text .dynsym .hash .dynstr
+# CHECK-NEXT:   01     foo .dynsym .hash .dynstr
 
 .section foo, "a"
 .quad 0

test/ELF/linkerscript/orphan.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+# RUN: echo "SECTIONS {       \
+# RUN:  .rw : { *(.rw) }      \
+# RUN:  .text : { *(.text) }  \
+# RUN:  .rx : { *(.ro) }      \
+# RUN: }" > %t.script
+# RUN: ld.lld -o %t1 --script %t.script %t
+# RUN: llvm-objdump -section-headers %t1 | FileCheck %s
+
+# CHECK:       0               00000000 0000000000000000 
+# CHECK-NEXT:  1 .rw           00000008 0000000000000000 DATA 
+# CHECK-NEXT:  2 .orphan.2     00000008 0000000000000008 DATA 
+# CHECK-NEXT:  3 .text         00000000 0000000000000010 TEXT DATA 
+# CHECK-NEXT:  4 .rx           00000001 0000000000000010 TEXT DATA 
+# CHECK-NEXT:  5 .orphan.1     00000008 0000000000000011 TEXT DATA 
+
+.section .rw, "aw"
+ .quad 0
+
+.section .rx, "ax"
+ nop
+
+.section .orphan.1, "ax"
+ .quad 0
+
+.section .orphan.2, "aw"
+ .quad 0

test/ELF/linkerscript/sections-constraint.s

 # RUN:  .readable : ONLY_IF_RO { *(.readable) }}" > %t2.script
 # RUN: ld.lld -o %t2 --script %t2.script %t
 # RUN: llvm-objdump -section-headers %t2 | \
 # RUN:   FileCheck -check-prefix=NO1 %s
 # NO1: Sections:
 # NO1-NEXT: Idx Name          Size
 # NO1-NEXT: 0               00000000
 # NO1:  .writable     00000004
+# NO1:  .foo.2        00000004
 # NO1:  .readable     00000004
 # NO1:  .foo.1        00000004
-# NO1:  .foo.2        00000004
 
 .global _start
 _start:
   nop
 
 .section .writable, "aw"
 writable:
  .long 1

test/ELF/linkerscript/sections-keep.s

 # RUN: echo "SECTIONS { \
 # RUN:  . = SIZEOF_HEADERS; \
 # RUN:  .keep : { KEEP(*(.keep)) } \
 # RUN:  .nokeep : { *(.keep) }}" > %t.script
 # RUN: ld.lld --gc-sections -o %t1 --script %t.script %t
 # RUN: llvm-objdump -section-headers %t1 | FileCheck -check-prefix=MIXED1 %s
 # MIXED1:      Sections:
 # MIXED1-NEXT: Idx Name          Size
-# MIXED1-NEXT:   0               00000000
-# MIXED1-NEXT:   1 .keep         00000004
-# MIXED1-NEXT:   2 .text         00000007 00000000000000ec TEXT DATA
-# MIXED1-NEXT:   3 .temp         00000004 00000000000000f3 DATA
-# MIXED1-NEXT:   4 .symtab       00000060 0000000000000000
-# MIXED1-NEXT:   5 .shstrtab     0000002d 0000000000000000
-# MIXED1-NEXT:   6 .strtab       00000012 0000000000000000
+# MIXED1-NEXT:  0               00000000 0000000000000000 
+# MIXED1-NEXT:  1 .keep         00000004 00000000000000e8 DATA 
+# MIXED1-NEXT:  2 .temp         00000004 00000000000000ec DATA 
+# MIXED1-NEXT:  3 .text         00000007 00000000000000f0 TEXT DATA 
+# MIXED1-NEXT:  4 .symtab       00000060 0000000000000000 
+# MIXED1-NEXT:  5 .shstrtab     0000002d 0000000000000000 
+# MIXED1-NEXT:  6 .strtab       00000012 0000000000000000 
 
 ## The same, but now section without KEEP is at first place.
 ## gold and bfd linkers disagree here. gold collects .keep while
 ## bfd keeps it. Our current behavior is compatible with bfd although
 ## we can choose either way.
 # RUN: echo "SECTIONS { \
 # RUN:  . = SIZEOF_HEADERS; \
 # RUN:  .nokeep : { *(.keep) } \
 # RUN:  .keep : { KEEP(*(.keep)) }}" > %t.script
 # RUN: ld.lld --gc-sections -o %t1 --script %t.script %t
 # RUN: llvm-objdump -section-headers %t1 | FileCheck -check-prefix=MIXED2 %s
 # MIXED2:      Sections:
 # MIXED2-NEXT: Idx Name          Size
-# MIXED2-NEXT:   0               00000000
-# MIXED2-NEXT:   1 .nokeep       00000004 00000000000000e8 DATA
-# MIXED2-NEXT:   2 .text         00000007 00000000000000ec TEXT DATA
-# MIXED2-NEXT:   3 .temp         00000004 00000000000000f3 DATA
-# MIXED2-NEXT:   4 .symtab       00000060 0000000000000000
-# MIXED2-NEXT:   5 .shstrtab     0000002f 0000000000000000
-# MIXED2-NEXT:   6 .strtab       00000012 0000000000000000
+# MIXED2-NEXT:  0               00000000 0000000000000000 
+# MIXED2-NEXT:  1 .nokeep       00000004 00000000000000e8 DATA 
+# MIXED2-NEXT:  2 .temp         00000004 00000000000000ec DATA 
+# MIXED2-NEXT:  3 .text         00000007 00000000000000f0 TEXT DATA 
+# MIXED2-NEXT:  4 .symtab       00000060 0000000000000000 
+# MIXED2-NEXT:  5 .shstrtab     0000002f 0000000000000000 
+# MIXED2-NEXT:  6 .strtab       00000012 0000000000000000 
 
-# Check file pattern for kept sections.
 # RUN: echo "SECTIONS { \
 # RUN:  . = SIZEOF_HEADERS; \
 # RUN:  .keep : { KEEP(*2.o(.keep)) } \
 # RUN:  }" > %t.script
 # RUN: ld.lld --gc-sections -o %t1 --script %t.script %t2.o %t
 # RUN: llvm-objdump -s %t1 | FileCheck -check-prefix=FILEMATCH %s
 # FILEMATCH:        Contents of section .keep:
 # FILEMATCH-NEXT:   00e8 41414141  AAAA