[ELF] x86-64: place .lrodata, .lbss, and .ldata away from code sections

The x86-64 medium code model utilizes large data sections, namely .lrodata,
.lbss, and .ldata (along with some variants of .ldata). There is a proposal to
extend the use of large data sections to the large code model as well[1].

This patch aims to place large data sections away from code sections in order to
alleviate relocation overflow pressure caused by code sections referencing
regular data sections.

```
.lrodata
.rodata
.text     # if --ro-segment, MAXPAGESIZE alignment
RELRO     # MAXPAGESIZE alignment
.data     # MAXPAGESIZE alignment
.bss
.ldata    # MAXPAGESIZE alignment
.lbss
```

In comparison to GNU ld, which places .lbss, .lrodata, and .ldata after .bss, we
place .lrodata above .rodata to minimize the number of permission transitions in
the memory image.

While GNU ld places .lbss after .bss, the subsequent sections don't reuse the
file offset bytes of BSS.

Our approach is to place .ldata and .lbss after .bss and create a PT_LOAD
segment for .bss to large data section transition in the absence of SECTIONS
commands. assignFileOffsets ensures we insert an alignment instead of allocating
space for BSS, and therefore we don't waste more than MAXPAGESIZE bytes. We have
a missing optimization to prevent all waste, but implementing it would introduce
complexity and likely be error-prone.

GNU ld's layout introduces 2 more MAXPAGESIZE alignments while ours
introduces just one.

[1]: https://groups.google.com/g/x86-64-abi/c/jnQdJeabxiU "Large data sections for the large code model"

With help from Arthur Eubanks.

Co-authored-by: James Y Knight <jyknight@google.com>

Reviewed By: aeubanks, tkoeppe

Differential Revision: https://reviews.llvm.org/D150510

3 files changed, 141 insertions, 12 deletions

diff --git a/lld/ELF/LinkerScript.cpp b/lld/ELF/LinkerScript.cpp
index 2f183eb..8859371 100644
--- a/lld/ELF/LinkerScript.cpp
+++ b/lld/ELF/LinkerScript.cpp
@@ -101,9 +101,9 @@ static StringRef getOutputSectionName(const InputSectionBase *s) {
   }
 
   for (StringRef v :
-       {".data.rel.ro", ".data", ".rodata", ".bss.rel.ro", ".bss",
-        ".gcc_except_table", ".init_array", ".fini_array", ".tbss", ".tdata",
-        ".ARM.exidx", ".ARM.extab", ".ctors", ".dtors"})
+       {".data.rel.ro", ".data", ".rodata", ".bss.rel.ro", ".bss", ".ldata",
+        ".lrodata", ".lbss", ".gcc_except_table", ".init_array", ".fini_array",
+        ".tbss", ".tdata", ".ARM.exidx", ".ARM.extab", ".ctors", ".dtors"})
     if (isSectionPrefix(v, s->name))
       return v;
 
diff --git a/lld/ELF/Writer.cpp b/lld/ELF/Writer.cpp
index 9c22052..f68d4f4 100644
--- a/lld/ELF/Writer.cpp
+++ b/lld/ELF/Writer.cpp
@@ -834,10 +834,11 @@ enum RankFlags {
   RF_NOT_ALLOC = 1 << 26,
   RF_PARTITION = 1 << 18, // Partition number (8 bits)
   RF_NOT_SPECIAL = 1 << 17,
-  RF_WRITE = 1 << 13,
-  RF_EXEC_WRITE = 1 << 12,
-  RF_EXEC = 1 << 11,
-  RF_RODATA = 1 << 10,
+  RF_WRITE = 1 << 16,
+  RF_EXEC_WRITE = 1 << 15,
+  RF_EXEC = 1 << 14,
+  RF_RODATA = 1 << 13,
+  RF_LARGE = 1 << 12,
   RF_NOT_RELRO = 1 << 9,
   RF_NOT_TLS = 1 << 8,
   RF_BSS = 1 << 7,
@@ -895,6 +896,9 @@ static unsigned getSectionRank(const OutputSection &osec) {
     // .dynstr and .dynsym can be away from .text.
     if (osec.type == SHT_PROGBITS)
       rank |= RF_RODATA;
+    // Among PROGBITS sections, place .lrodata further from .text.
+    if (!(osec.flags & SHF_X86_64_LARGE && config->emachine == EM_X86_64))
+      rank |= RF_LARGE;
   } else if (isExec) {
     rank |= isWrite ? RF_EXEC_WRITE : RF_EXEC;
   } else {
@@ -905,6 +909,10 @@ static unsigned getSectionRank(const OutputSection &osec) {
       rank |= RF_NOT_TLS;
     if (!isRelroSection(&osec))
       rank |= RF_NOT_RELRO;
+    // Place .ldata and .lbss after .bss. Making .bss closer to .text alleviates
+    // relocation overflow pressure.
+    if (osec.flags & SHF_X86_64_LARGE && config->emachine == EM_X86_64)
+      rank |= RF_LARGE;
   }
 
   // Within TLS sections, or within other RelRo sections, or within non-RelRo
@@ -2321,16 +2329,27 @@ SmallVector<PhdrEntry *, 0> Writer<ELFT>::createPhdrs(Partition &part) {
     // Segments are contiguous memory regions that has the same attributes
     // (e.g. executable or writable). There is one phdr for each segment.
     // Therefore, we need to create a new phdr when the next section has
-    // different flags or is loaded at a discontiguous address or memory
-    // region using AT or AT> linker script command, respectively. At the same
-    // time, we don't want to create a separate load segment for the headers,
-    // even if the first output section has an AT or AT> attribute.
+    // different flags or is loaded at a discontiguous address or memory region
+    // using AT or AT> linker script command, respectively.
+    //
+    // As an exception, we don't create a separate load segment for the ELF
+    // headers, even if the first "real" output has an AT or AT> attribute.
+    //
+    // In addition, NOBITS sections should only be placed at the end of a LOAD
+    // segment (since it's represented as p_filesz < p_memsz). If we have a
+    // not-NOBITS section after a NOBITS, we create a new LOAD for the latter
+    // even if flags match, so as not to require actually writing the
+    // supposed-to-be-NOBITS section to the output file. (However, we cannot do
+    // so when hasSectionsCommand, since we cannot introduce the extra alignment
+    // needed to create a new LOAD)
     uint64_t newFlags = computeFlags(sec->getPhdrFlags());
     bool sameLMARegion =
         load && !sec->lmaExpr && sec->lmaRegion == load->firstSec->lmaRegion;
     if (!(load && newFlags == flags && sec != relroEnd &&
           sec->memRegion == load->firstSec->memRegion &&
-          (sameLMARegion || load->lastSec == Out::programHeaders))) {
+          (sameLMARegion || load->lastSec == Out::programHeaders) &&
+          (script->hasSectionsCommand || sec->type == SHT_NOBITS ||
+           load->lastSec->type != SHT_NOBITS))) {
       load = addHdr(PT_LOAD, newFlags);
       flags = newFlags;
     }
diff --git a/lld/test/ELF/x86-64-section-layout.s b/lld/test/ELF/x86-64-section-layout.s
new file mode 100644
index 0000000..e9ea69af
--- /dev/null
+++ b/lld/test/ELF/x86-64-section-layout.s
@@ -0,0 +1,110 @@
+# REQUIRES: x86
+## Test the placement of .lrodata, .lbss, .ldata, and their -fdata-sections variants.
+## See also section-layout.s.
+
+# RUN: rm -rf %t && split-file %s %t && cd %t
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64 --defsym=BSS=1 a.s -o a.o
+# RUN: ld.lld --section-start=.note=0x200300 a.o -o a
+# RUN: llvm-readelf -S -l a | FileCheck %s
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64 a.s -o a1.o
+# RUN: ld.lld --section-start=.note=0x200300 a1.o -o a1
+# RUN: llvm-readelf -S a1 | FileCheck %s --check-prefix=CHECK1
+
+# RUN: ld.lld -T b.lds -z norelro a.o -o b
+# RUN: llvm-readelf -S -l b | FileCheck %s --check-prefix=CHECK2
+
+# CHECK:       Name       Type            Address          Off    Size   ES Flg Lk Inf Al
+# CHECK-NEXT:             NULL            0000000000000000 000000 000000 00      0   0  0
+# CHECK-NEXT:  .note      NOTE            0000000000200300 000300 000001 00   A  0   0  1
+# CHECK-NEXT:  .lrodata   PROGBITS        0000000000200301 000301 000002 00  Al  0   0  1
+# CHECK-NEXT:  .rodata    PROGBITS        0000000000200303 000303 000001 00   A  0   0  1
+# CHECK-NEXT:  .text      PROGBITS        0000000000201304 000304 000001 00  AX  0   0  4
+# CHECK-NEXT:  .tdata     PROGBITS        0000000000202305 000305 000001 00 WAT  0   0  1
+# CHECK-NEXT:  .tbss      NOBITS          0000000000202306 000306 000002 00 WAT  0   0  1
+# CHECK-NEXT:  .data      PROGBITS        0000000000203306 000306 000001 00  WA  0   0  1
+# CHECK-NEXT:  .bss       NOBITS          0000000000203307 000307 001800 00  WA  0   0  1
+## We spend size(.bss) % MAXPAGESIZE bytes for .bss.
+# CHECK-NEXT:  .ldata     PROGBITS        0000000000205b07 000b07 000002 00 WAl  0   0  1
+# CHECK-NEXT:  .ldata2    PROGBITS        0000000000205b09 000b09 000001 00 WAl  0   0  1
+# CHECK-NEXT:  .lbss      NOBITS          0000000000205b0a 000b0a 000002 00 WAl  0   0  1
+# CHECK-NEXT:  .comment   PROGBITS        0000000000000000 000b0a {{.*}} 01  MS  0   0  1
+
+# CHECK:       Program Headers:
+# CHECK-NEXT:    Type  Offset   VirtAddr           PhysAddr           FileSiz  MemSiz   Flg Align
+# CHECK-NEXT:    PHDR  0x000040 0x0000000000200040 0x0000000000200040 {{.*}}   {{.*}}   R   0x8
+# CHECK-NEXT:    LOAD  0x000000 0x0000000000200000 0x0000000000200000 0x000304 0x000304 R   0x1000
+# CHECK-NEXT:    LOAD  0x000304 0x0000000000201304 0x0000000000201304 0x000001 0x000001 R E 0x1000
+# CHECK-NEXT:    LOAD  0x000305 0x0000000000202305 0x0000000000202305 0x000001 0x000001 RW  0x1000
+# CHECK-NEXT:    LOAD  0x000306 0x0000000000203306 0x0000000000203306 0x000001 0x001801 RW  0x1000
+# CHECK-NEXT:    LOAD  0x000b07 0x0000000000205b07 0x0000000000205b07 0x000003 0x000005 RW  0x1000
+
+# CHECK1:      .data      PROGBITS        0000000000203306 000306 000001 00  WA  0   0  1
+# CHECK1-NEXT: .ldata     PROGBITS        0000000000203307 000307 000002 00 WAl  0   0  1
+# CHECK1-NEXT: .ldata2    PROGBITS        0000000000203309 000309 000001 00 WAl  0   0  1
+# CHECK1-NEXT: .comment   PROGBITS        0000000000000000 00030a {{.*}} 01  MS  0   0  1
+
+# CHECK2:      .note      NOTE            0000000000200300 000300 000001 00   A  0   0  1
+# CHECK2-NEXT: .lrodata   PROGBITS        0000000000200301 000301 000001 00  Al  0   0  1
+## With a SECTIONS command, we suppress the default rule placing .lrodata.* into .lrodata.
+# CHECK2-NEXT: .lrodata.1 PROGBITS        0000000000200302 000302 000001 00  Al  0   0  1
+# CHECK2-NEXT: .rodata    PROGBITS        0000000000200303 000303 000001 00   A  0   0  1
+# CHECK2-NEXT: .text      PROGBITS        0000000000200304 000304 000001 00  AX  0   0  4
+# CHECK2-NEXT: .tdata     PROGBITS        0000000000200305 000305 000001 00 WAT  0   0  1
+# CHECK2-NEXT: .tbss      NOBITS          0000000000200306 000306 000001 00 WAT  0   0  1
+# CHECK2-NEXT: .tbss.1    NOBITS          0000000000200307 000306 000001 00 WAT  0   0  1
+# CHECK2-NEXT: .data      PROGBITS        0000000000200306 000306 000001 00  WA  0   0  1
+# CHECK2-NEXT: .bss       NOBITS          0000000000200307 000307 001800 00  WA  0   0  1
+# CHECK2-NEXT: .ldata     PROGBITS        0000000000201b07 001b07 000002 00 WAl  0   0  1
+# CHECK2-NEXT: .ldata2    PROGBITS        0000000000201b09 001b09 000001 00 WAl  0   0  1
+# CHECK2-NEXT: .lbss      NOBITS          0000000000201b0a 001b0a 000002 00 WAl  0   0  1
+# CHECK2-NEXT: .comment   PROGBITS        0000000000000000 001b0a {{.*}} 01  MS  0   0  1
+
+# CHECK2:      Program Headers:
+# CHECK2-NEXT:   Type  Offset   VirtAddr           PhysAddr           FileSiz  MemSiz   Flg Align
+# CHECK2-NEXT:   PHDR  0x000040 0x0000000000200040 0x0000000000200040 {{.*}}   {{.*}}   R   0x8
+# CHECK2-NEXT:   LOAD  0x000000 0x0000000000200000 0x0000000000200000 0x000304 0x000304 R   0x1000
+# CHECK2-NEXT:   LOAD  0x000304 0x0000000000200304 0x0000000000200304 0x000001 0x000001 R E 0x1000
+# CHECK2-NEXT:   LOAD  0x000305 0x0000000000200305 0x0000000000200305 0x001805 0x001807 RW  0x1000
+# CHECK2-NEXT:   TLS   0x000305 0x0000000000200305 0x0000000000200305 0x000001 0x000003 R   0x1
+
+#--- a.s
+.globl _start
+_start:
+  ret
+
+.section .note,"a",@note; .space 1
+.section .rodata,"a",@progbits; .space 1
+.section .data,"aw",@progbits; .space 1
+.ifdef BSS
+## .bss is large than one MAXPAGESIZE to test file offsets.
+.section .bss,"aw",@nobits; .space 0x1800
+.endif
+.section .tdata,"awT",@progbits; .space 1
+.section .tbss,"awT",@nobits; .space 1
+.section .tbss.1,"awT",@nobits; .space 1
+
+.section .lrodata,"al"; .space 1
+.section .lrodata.1,"al"; .space 1
+.section .ldata,"awl"; .space 1
+## Input .ldata.rel.ro sections are placed in the output .ldata section.
+.section .ldata.rel.ro,"awl"; .space 1
+.ifdef BSS
+.section .lbss,"awl",@nobits; .space 1
+## Input .lbss.rel.ro sections are placed in the output .lbss section.
+.section .lbss.rel.ro,"awl",@nobits; .space 1
+.endif
+.section .ldata2,"awl"; .space 1
+
+#--- b.lds
+SECTIONS {
+  . = 0x200300;
+  .rodata : {}
+  .text : {}
+  .data : {}
+  .bss : {}
+  .ldata : { *(.ldata .ldata.*) }
+  .ldata2 : {}
+  .lbss : { *(.lbss .lbss.*) }
+}