[lld/ELF] Sort sections by SHF_X86_64_LARGE

[aeubanks]

Summary

So that binaries with both large and non-large sections will have the
non-large sections together, lowering the chance of relocation overflows
between the non-large sections.

[MaskRay]

The MC and lld/ELF parts belong to different patches.

The SHF_X86_64_LARGE MC change should test llvm-readelf -S or llvm-readobj -S output.

[aeubanks]

rebase

[jyknight]

I believe we should be able to rearrange the large sections to be "around" all of the other sections, rather than at the end, in order to reduce the overhead of additional LOAD segments. I was playing with this before my vacation last week, and will post a proposed patch soon.

[tkoeppe]

@jyknight Ah yes, we did discuss that, and that would indeed be a welcome improvement!

[aeubanks]

right now lld sorts sections by R, RX, RWX, RW. do you mean put large R right before normal R, and large RW right after normal RW, and whatever for large RX and RWX?

[aeubanks]

I guess that would also be better for having fewer text->data relocation overflows if we go down the -mlarge-data-threshold route

[MaskRay]

In D148356#4292950, @aeubanks wrote:

right now lld sorts sections by R, RX, RWX, RW. do you mean put large R right before normal R, and large RW right after normal RW, and whatever for large RX and RWX?

Yes. I would suggest this.

(I didn't notice that this patch had been made green. I'll change myself to a blocking reviewer :))

lld/ELF/Writer.cpp

 // We compute a rank for each section. The rank indicates where the
 // section should be placed in the file.  Instead of using simple
 // numbers (0,1,2...), we use a series of flags. One for each decision
 // point when placing the section.
 // Using flags has two key properties:
 // * It is easy to check if a give branch was taken.
 // * It is easy two see how similar two ranks are (see getRankProximity).
 enum RankFlags {
-  RF_NOT_ADDR_SET = 1 << 27,
-  RF_NOT_ALLOC = 1 << 26,
-  RF_PARTITION = 1 << 18, // Partition number (8 bits)
-  RF_NOT_PART_EHDR = 1 << 17,
-  RF_NOT_PART_PHDR = 1 << 16,
-  RF_NOT_INTERP = 1 << 15,
-  RF_NOT_NOTE = 1 << 14,
+  RF_NOT_ADDR_SET = 1 << 28,
+  RF_NOT_ALLOC = 1 << 27,
+  RF_PARTITION = 1 << 19, // Partition number (8 bits)
+  RF_NOT_PART_EHDR = 1 << 18,
+  RF_NOT_PART_PHDR = 1 << 17,
+  RF_NOT_INTERP = 1 << 16,
+  RF_NOT_NOTE = 1 << 15,
+  RF_LARGE = 1 << 14,
   RF_WRITE = 1 << 13,
   RF_EXEC_WRITE = 1 << 12,
   RF_EXEC = 1 << 11,
   RF_RODATA = 1 << 10,
   RF_NOT_RELRO = 1 << 9,
   RF_NOT_TLS = 1 << 8,
   RF_BSS = 1 << 7,
   RF_PPC_NOT_TOCBSS = 1 << 6,
static unsigned getSectionRank(const OutputSection &osec) {
 
   // Within TLS sections, or within other RelRo sections, or within non-RelRo
   // sections, place non-NOBITS sections first.
   if (osec.type == SHT_NOBITS)
     rank |= RF_BSS;
 
   // Some architectures have additional ordering restrictions for sections
   // within the same PT_LOAD.
+
+  if (config->emachine == EM_X86_64) {
+    // Large sections should always come after non-large sections so that
+    // smaller relocations between non-large sections are less likely to
+    // overflow.
+    if (osec.flags & SHF_X86_64_LARGE)
+      rank |= RF_LARGE;
+  }
+
   if (config->emachine == EM_PPC64) {
     // PPC64 has a number of special SHT_PROGBITS+SHF_ALLOC+SHF_WRITE sections
     // that we would like to make sure appear is a specific order to maximize
     // their coverage by a single signed 16-bit offset from the TOC base
     // pointer. Conversely, the special .tocbss section should be first among
     // all SHT_NOBITS sections. This will put it next to the loaded special
     // PPC64 sections (and, thus, within reach of the TOC base pointer).
     StringRef name = osec.name;

lld/test/ELF/section-layout.s

 .section s,"x"
 .section r,"w",@nobits
 .section q,"w"
 .section p,"wx",@nobits
 .section o,"wx"
 .section n,"",@nobits
 .section m,""
 
+.section u,"axl",@nobits
+.section v,"axl"
+.section w,"awl",@nobits
+.section x,"awl"
+.section y1,"awxl",@nobits
+.section y2,"awxl"
+.section z1,"al",@nobits
+.section z2,"al"
 .section l,"awx",@nobits
 .section k,"awx"
 .section j,"aw",@nobits
 .section i,"aw"
 .section g,"awT",@nobits
 .section e,"awT"
 .section d,"ax",@nobits
 .section c,"ax"

 // CHECK: Name: e
 // CHECK: Name: g
 
 // Writable sections appear after TLS and other relro sections.
 // CHECK: Name: i
 
 // CHECK: Name: j
 
+// Large sections come at the end
+// CHECK: Name: z1
+// CHECK: Name: z2
+// CHECK: Name: v
+// CHECK: Name: u
+// CHECK: Name: y2
+// CHECK: Name: y1
+// CHECK: Name: x
+// CHECK: Name: w
+
 // Non allocated sections are in input order.
 // CHECK: Name: t
 // CHECK: Name: s
 // CHECK: Name: r
 // CHECK: Name: q
 // CHECK: Name: p
 // CHECK: Name: o
 // CHECK: Name: n
 // CHECK: Name: m