[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

750 ↗

(On Diff #73794)

This needs to be updated.

772 ↗

(On Diff #73794)

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

772 ↗

(On Diff #73794)

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

lld/trunk/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(const OutputSectionBase<ELFT> &S1,
+                           const OutputSectionBase<ELFT> &S2) {
+  if (!(S1.getFlags() & SHF_ALLOC) || !(S2.getFlags() & SHF_ALLOC))
+    return false;
+
+  bool S1IsWrite = S1.getFlags() & SHF_WRITE;
+  bool S2IsWrite = S2.getFlags() & SHF_WRITE;
+  if (S1IsWrite != S2IsWrite)
+    return false;
+
+  if (!S1IsWrite)
+    return true; // RO and RX share a PT_LOAD with linker scripts.
+  return (S1.getFlags() & SHF_EXECINSTR) == (S2.getFlags() & 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.
+  // *  Move each non-script section to its preferred position. We try
+  //    to put each section in the last position where it it can share
+  //    a PT_LOAD.
 
   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;
       });
   while (NonScriptI != E) {
-    auto FirstGreater =
-        std::find_if(I, NonScriptI, [&](OutputSectionBase<ELFT> *S) {
-          return compareSectionsNonScript<ELFT>(*NonScriptI, S);
+    auto BestPos =
+        std::max_element(I, NonScriptI, [&](OutputSectionBase<ELFT> *&A,
+                                            OutputSectionBase<ELFT> *&B) {
+          bool ACanSharePtLoad = canSharePtLoad(**NonScriptI, *A);
+          bool BCanSharePtLoad = canSharePtLoad(**NonScriptI, *B);
+          if (ACanSharePtLoad != BCanSharePtLoad)
+            return BCanSharePtLoad;
+
+          bool ACmp = compareSectionsNonScript<ELFT>(*NonScriptI, A);
+          bool BCmp = compareSectionsNonScript<ELFT>(*NonScriptI, B);
+          if (ACmp != BCmp)
+            return BCmp; // FIXME: missing test
+
+          size_t PosA = &A - &OutputSections[0];
+          size_t PosB = &B - &OutputSections[0];
+          return ACmp ? PosA > PosB : PosA < PosB;
         });
-    std::rotate(FirstGreater, NonScriptI, NonScriptI + 1);
+
+    // max_element only returns NonScriptI if the range is empty. If the range
+    // is not empty we should consider moving the the element forward one
+    // position.
+    if (BestPos != NonScriptI &&
+        !compareSectionsNonScript<ELFT>(*NonScriptI, *BestPos))
+      ++BestPos;
+    std::rotate(BestPos, 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");

lld/trunk/test/ELF/linkerscript/orphan.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+# RUN: echo "SECTIONS {       \
+# RUN:  .text : { *(.text) }  \
+# RUN:  .rw1 : { *(.rw1) }    \
+# RUN:  .rw2 : { *(.rw2) }    \
+# RUN:  .rw3 : { *(.rw3) }    \
+# 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 .text         00000000 0000000000000000 TEXT DATA 
+# CHECK-NEXT:  2 .jcr          00000008 0000000000000000 DATA 
+# CHECK-NEXT:  3 .rw1          00000008 0000000000000008 DATA 
+# CHECK-NEXT:  4 .rw2          00000008 0000000000000010 DATA 
+# CHECK-NEXT:  5 .rw3          00000008 0000000000000018 DATA 
+
+.section .rw1, "aw"
+ .quad 0
+
+.section .rw2, "aw"
+ .quad 0
+
+.section .rw3, "aw"
+ .quad 0
+
+.section .jcr, "aw"
+ .quad 0

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