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

[MaskRay]

Summary

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 <[e-mail]>

[peter.smith]

The approach and the code looks good to me. As an Arm person I would prefer for someone involved in x86_64 to comment on the proposed changes from GNU ld. If there are none forthcoming then give me a ping. From the GNU ld code-base there look to be a few other architectures that have .ldata sections but none of them look to be supported by upstream LLD.

lld/ELF/Writer.cpp

899

Do you mean .lrodata in the comment above?

[jyknight]

So, I also had a version I was going to send for review, but I'm too slow, and it's now conflicted with intermediary cleanups.

So I've pushed it here instead for now: https://github.com/llvm/llvm-project/compare/main...jyknight:llvm-project:lld-largefile-2 (starting with a revert of your cleanup, just in order to not need to deal with merge conflicts at this point...).

The main points I think are important are:

• Also supports code sections marked large (they are placed at the end, after RW data).
• Splits segments at NOBITS->BITS boundaries, so that a new segment is started between .bss and .ldata (assuming there is .bss).

[MaskRay]

In D150510#4342261, @jyknight wrote:

So, I also had a version I was going to send for review, but I'm too slow, and it's now conflicted with intermediary cleanups.

So I've pushed it here instead for now: https://github.com/llvm/llvm-project/compare/main...jyknight:llvm-project:lld-largefile-2 (starting with a revert of your cleanup, just in order to not need to deal with merge conflicts at this point...).

Thanks!

The main points I think are important are:

• Also supports code sections marked large (they are placed at the end, after RW data).
• Splits segments at NOBITS->BITS boundaries, so that a new segment is started between .bss and .ldata (assuming there is .bss).

I have thought about this, but after close look at GNU ld's layout, it shares the missing optimization with us... So I think not implementing this is fine.
Then, we can just not start a new RW PT_LOAD...

While GNU ld places .lbss after .bss, the subsequent sections don't reuse the file offset bytes of BSS. We have a similar missing optimization (implementing it would introduce complexity and likely be error-prone).

(I think objcopy/strip traditionally has some issues with bss including a bug which only happens with lld's layout.)

GCC/GNU ld don't create .ltext, so I omit it... Perhaps you may kindly send a patch to place .ltext, after Clang gets support for .ltext and .ltext.*...

lld/ELF/Writer.cpp

899

I mean .rodata is closer to .text. We have .dynsym ... .lrodata .rodata, but the comment can probably rewritten in a clearer way.

[aeubanks]

Splits segments at NOBITS->BITS boundaries, so that a new segment is started between .bss and .ldata (assuming there is .bss).

why is this necessary?

lld/ELF/Writer.cpp

899

Yeah I think this comment is confusing, something like Place large sections further from .text is clearer

lld/test/ELF/x86-64-section-layout.s

25

shouldn't this be merged with .ldata according to the change in LinkerScript.cpp?

[MaskRay]

improve a comment

lld/test/ELF/x86-64-section-layout.s

25

No. .ldata2 is picked to test that .ldata2 is not combined into .ldata .ldata.* sections.

[MaskRay]

In D150510#4362069, @aeubanks wrote:

Splits segments at NOBITS->BITS boundaries, so that a new segment is started between .bss and .ldata (assuming there is .bss).

why is this necessary?

As I noted in the description:

While GNU ld places .lbss after .bss, the subsequent sections don't reuse the file offset bytes of BSS. We have a similar missing optimization (implementing it would introduce complexity and likely be error-prone).

If we start a new PT_LOAD at NOBITS->BITS boundaries, we can in theory implement such a file size optimization.
fixSectionAlignments and assignFileOffsets would need some involved code.
I think this is error-prone and may not be a worthwhile change.

[jyknight]

Splits segments at NOBITS->BITS boundaries, so that a new segment is started between .bss and .ldata (assuming there is .bss).

why is this necessary?

As I noted in the description:

While GNU ld places .lbss after .bss, the subsequent sections don't reuse the file offset bytes of BSS. We have a similar missing optimization (implementing it would introduce complexity and likely be error-prone).

If we start a new PT_LOAD at NOBITS->BITS boundaries, we can in theory implement such a file size optimization.
fixSectionAlignments and assignFileOffsets would need some involved code.
I think this is error-prone and may not be a worthwhile change.

As a reminder, the section layout we're talking about is: .data (PROGBITS RW), .bss (NOBITS RW), .ldata (PROGBITS RW LARGE). The question is whether to cover all three sections with a single LOAD, or whether to use two LOADs, one for .data and .bss, and the second for .ldata.

In the former case, you cannot use the ability of an ELF LOAD to specify a smaller filesize than memory memory-size -- where the remainder of the memory-size gets zero-filled by the loader, because that can only be at the end of the LOAD. Thus, in that model, if you have 8MB of .bss, you will waste 8MB of zeros in the binary.

My patch does the latter, instead, and that saves space, already, without additional changes to other functions. Because of the way the alignment code works, you'll still waste some bytes in the file, but only up to max-page-size bytes (which defaults to 4K for x86-64; users can change it with -z,max-page-size= if they like).

[aeubanks]

In D150510#4364809, @jyknight wrote:

As a reminder, the section layout we're talking about is: .data (PROGBITS RW), .bss (NOBITS RW), .ldata (PROGBITS RW LARGE). The question is whether to cover all three sections with a single LOAD, or whether to use two LOADs, one for .data and .bss, and the second for .ldata.

In the former case, you cannot use the ability of an ELF LOAD to specify a smaller filesize than memory memory-size -- where the remainder of the memory-size gets zero-filled by the loader, because that can only be at the end of the LOAD. Thus, in that model, if you have 8MB of .bss, you will waste 8MB of zeros in the binary.

My patch does the latter, instead, and that saves space, already, without additional changes to other functions. Because of the way the alignment code works, you'll still waste some bytes in the file, but only up to max-page-size bytes (which defaults to 4K for x86-64; users can change it with -z,max-page-size= if they like).

The size of .bss is likely non-negligible if we're implementing -mlarge-data-threshold, so this does seem important.

In D150510#4362358, @MaskRay wrote:

If we start a new PT_LOAD at NOBITS->BITS boundaries, we can in theory implement such a file size optimization.
fixSectionAlignments and assignFileOffsets would need some involved code.
I think this is error-prone and may not be a worthwhile change.

James is saying that this already works?

anyway, this patch lgtm, I can take over James's https://github.com/llvm/llvm-project/commit/1ef68439208701146384d04f58286cdb94623452 for the new LOAD

lld/test/ELF/x86-64-section-layout.s

25

ah I missed that isSectionPrefix also checks for a . after the prefix

[MaskRay]

Add Co-authored-by and thanks to Arthur Eubanks

Add a SECTIONS test. Compared with https://github.com/llvm/llvm-project/commit/1ef68439208701146384d04f58286cdb94623452 , this version intentionally doesn't special case SECTIONS commands.

[MaskRay]

In D150510#4368945, @aeubanks wrote:

In D150510#4364809, @jyknight wrote:

As a reminder, the section layout we're talking about is: .data (PROGBITS RW), .bss (NOBITS RW), .ldata (PROGBITS RW LARGE). The question is whether to cover all three sections with a single LOAD, or whether to use two LOADs, one for .data and .bss, and the second for .ldata.

In the former case, you cannot use the ability of an ELF LOAD to specify a smaller filesize than memory memory-size -- where the remainder of the memory-size gets zero-filled by the loader, because that can only be at the end of the LOAD. Thus, in that model, if you have 8MB of .bss, you will waste 8MB of zeros in the binary.

My patch does the latter, instead, and that saves space, already, without additional changes to other functions. Because of the way the alignment code works, you'll still waste some bytes in the file, but only up to max-page-size bytes (which defaults to 4K for x86-64; users can change it with -z,max-page-size= if they like).

The size of .bss is likely non-negligible if we're implementing -mlarge-data-threshold, so this does seem important.

In D150510#4362358, @MaskRay wrote:

If we start a new PT_LOAD at NOBITS->BITS boundaries, we can in theory implement such a file size optimization.
fixSectionAlignments and assignFileOffsets would need some involved code.
I think this is error-prone and may not be a worthwhile change.

James is saying that this already works?

anyway, this patch lgtm, I can take over James's https://github.com/llvm/llvm-project/commit/1ef68439208701146384d04f58286cdb94623452 for the new LOAD

Yes, it already works. Seems good to incorporate the change in this patch. We waste up to MAXPAGESIZE bytes, but the current behavior should be good enough.

[MaskRay]

Use jyknight's comment

respect hasSectionsCommand

[aeubanks]

lgtm, but should we explicitly test the segments with with llvm-readelf --program-headers?

[MaskRay]

Test program headers

lld/ELF/LinkerScript.cpp

if (config->zKeepTextSectionPrefix)
       for (StringRef v : {".text.hot", ".text.unknown", ".text.unlikely",
                           ".text.startup", ".text.exit", ".text.split"})
         if (isSectionPrefix(v.substr(5), s->name.substr(5)))
           return v;
     return ".text";
   }
 
   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;
 
   return s->name;
 }
 
 uint64_t ExprValue::getValue() const {
   if (sec)

lld/ELF/Writer.cpp

 // 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_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,
 };
 
 static unsigned getSectionRank(const OutputSection &osec) {
   unsigned rank = osec.partition * RF_PARTITION;
 
static unsigned getSectionRank(const OutputSection &osec) {
   bool isWrite = osec.flags & SHF_WRITE;
 
   if (!isWrite && !isExec) {
     // Make PROGBITS sections (e.g .rodata .eh_frame) closer to .text to
     // alleviate relocation overflow pressure. Large special sections such as
     // .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 {
     rank |= RF_WRITE;
     // The TLS initialization block needs to be a single contiguous block. Place
     // TLS sections directly before the other RELRO sections.
     if (!(osec.flags & SHF_TLS))
       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
   // sections, place non-NOBITS sections first.
   if (osec.type == SHT_NOBITS)
     rank |= RF_BSS;
 
   // Some architectures have additional ordering restrictions for sections
if (sec->partition != partNo) {
       if (isMain && sec->partition == 255)
         addHdr(PT_LOAD, computeFlags(sec->getPhdrFlags()))->add(sec);
       continue;
     }
 
     // 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;
     }
 
     load->add(sec);
   }
 
   // Add a TLS segment if any.

lld/test/ELF/x86-64-section-layout.s

+# 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.*) }
+}