[ELF] Allow sections after a non-SHF_ALLOC section to be covered by PT_LOAD

[MaskRay]

Summary

GNU ld allows sections after a non-SHF_ALLOC section to be covered by PT_LOAD
(PR37607) and assigns addresses to non-SHF_ALLOC output sections (similar to
SHF_ALLOC NOBITS sections. The location counter is not advanced).

This patch tries to fix PR37607 (remove a special case in
Writer<ELFT>::createPhdrs). To make the created PT_LOAD meaningful, we cannot
reset dot to 0 for a middle non-SHF_ALLOC output section. This results in
removal of two special cases in LinkerScript::assignOffsets. Non-SHF_ALLOC
non-orphan sections can have non-zero addresses like in GNU ld.

The zero address rule for non-SHF_ALLOC sections is weakened to apply to orphan
only. This results in a special case in createSection and findOrphanPos, respectively.

[jhenderson]

I'm just trying to make sure I've got this straight. Current LLD behaviour is to ignore linker script positioning of non-allocatable sections and put them after all allocatable sections, and this changes to placing them in the output in their requested position. If a program header were to cover these sections as a result of covering the allocatable sections either side of them, the normally non-alloc sections are given addresses to maintain the address space. Makes sense to me.

Do we have/need a test case for non-alloc between two sections which are in different segments, e.g:

| PT_LOAD1 |           | PT_LOAD2 |
| alloc1   | non-alloc | alloc2   |

I'd expect non-alloc to not be covered by the segment, as it doesn't need to be (though I could be convinced it does need to be).

lld/ELF/Writer.cpp

1237

I think the term is "non-allocatable".

1238

lld/test/ELF/linkerscript/compress-debug-sections-custom.s

3

lld/test/ELF/linkerscript/symbols-non-alloc.test

2–3

[MaskRay]

Current LLD behaviour is to ignore linker script positioning of non-allocatable sections and put them after all allocatable sections, and this changes to placing them in the output in their requested position

For PT_LOAD creation, current LLD behaviors ignores every section after a non-allocable section.
This changes them to be allocated into some PT_LOAD. The non-allocable placement is arbitrary: their observed behaviors are not guaranteed property.

Do we have/need a test case for non-alloc between two sections which are in different segments, e.g:

Added a test that .data .bss .comment .other can be in one PT_LOAD.
This is not something we strive to satisfy, just a result of current implementation choice.

lld/ELF/Writer.cpp

1237

gABI uses "non-allocable" in one place (SHF_COMPRESSED, contributed by Solaris folks)

SHF_COMPRESSED

This flag identifies a section containing compressed data. SHF_COMPRESSED applies only to non-allocable sections, and cannot be used in conjunction with SHF_ALLOC. In addition, SHF_COMPRESSED cannot be applied to sections of type SHT_NOBITS.

I don't find a use of "non-allocatable".

[jhenderson]

Somebody else should probably verify that the logic makes sense to them.

lld/ELF/Writer.cpp

1237

Hmmm... that's an unforutnate word-usage there in the spec. Thinking about it further: SHF_ALLOC is presumably short for some variation of the verb "allocate", whose equivalent adjectives are "allocated" (is assigned memory) and "allocatable" (can be allocated). The opposite of these would actually be "unallocated" (is not assigned memory) and "unallocatable" (cannot be allocated to memory). However, "cannot" is probably too strong a meaning in this context. I don't think "non-alloc[at]able" is really a valid English word.

Maybe we can dodge the issue and just use "non-alloc"? That's what I colloquially use for referring to sections that don't have SHF_ALLOC.

lld/test/ELF/linkerscript/symbols-non-alloc.test

2–3

(Regardless of the non-allocable conversation, the "to" still needs deleting from this comment).

[MaskRay]

non-allocable -> non-SHF_ALLOC
equals to -> equals

[jhenderson]

Looks good from my point of view, but I'd appreciate another pair of eyes to confirm that the behaviour makes sense.

[psmith]

FWIW this looks good to me too.

lld/ELF/Writer.cpp

1237

I suggest rewording:

// To make the addresses of orphan sections not affected by orphan
// non-SHF_ALLOC sections in the middle, place orphan non-SHF_ALLOC sections
// at the end.

as

// OutputSections without the SHF_ALLOC flag are not part of the memory image and
// are given an address starting at 0. Place any orphan sections without the SHF_ALLOC
// flag at the end so that these do not affect the address assignment of OutputSections
// with the SHF_ALLOC flag.

[MaskRay]

reword a comment

[MaskRay]

lld/ELF/Writer.cpp

1237

Thanks. I reworded the part "are given an address starting at 0" as we actually assign addresses to OutputSections without the SHF_ALLOC flag created from non-orphan sections.

[jankratochvil]

It broke Linux buildbots:
http://lab.llvm.org:8011/builders/lldb-x86_64-debian/builds/15235/steps/test/logs/stdio
http://lab.llvm.org:8014/builders/lldb-x86_64-fedora/builds/10451/steps/test/logs/stdio

[omjavaid]

FYI I have reverted this change as it was breaking multiple buildbots.

Example:
http://lab.llvm.org:8011/builders/lldb-aarch64-ubuntu
http://lab.llvm.org:8011/builders/lldb-arm-ubuntu

lld/ELF/LinkerScript.cpp

if (auto *sec = dyn_cast<OutputSection>(base))
       if (sec->name == name)
         return sec;
   return nullptr;
 }
 
 static OutputSection *createSection(InputSectionBase *isec,
                                     StringRef outsecName) {
   OutputSection *sec = script->createOutputSection(outsecName, "<internal>");
+  if (!(isec->flags & SHF_ALLOC))
+    sec->addrExpr = [] { return 0; };
   sec->recordSection(isec);
   return sec;
 }
 
 static OutputSection *
 addInputSec(StringMap<TinyPtrVector<OutputSection *>> &map,
             InputSectionBase *isec, StringRef outsecName) {
   // Sections with SHT_GROUP or SHF_GROUP attributes reach here only when the -r
for (OutputSection *sec : outputSections)
     if (sec->ptLoad == load)
       return sec;
   return nullptr;
 }
 
 // This function assigns offsets to input sections and an output section
 // for a single sections command (e.g. ".text { *(.text); }").
 void LinkerScript::assignOffsets(OutputSection *sec) {
-  if (!(sec->flags & SHF_ALLOC))
-    dot = 0;
-
   const bool sameMemRegion = ctx->memRegion == sec->memRegion;
   const bool prevLMARegionIsDefault = ctx->lmaRegion == nullptr;
   ctx->memRegion = sec->memRegion;
   ctx->lmaRegion = sec->lmaRegion;
   if (ctx->memRegion)
     dot = ctx->memRegion->curPos;
 
-  if ((sec->flags & SHF_ALLOC) && sec->addrExpr)
+  if (sec->addrExpr)
     setDot(sec->addrExpr, sec->location, false);
 
   // If the address of the section has been moved forward by an explicit
   // expression so that it now starts past the current curPos of the enclosing
   // region, we need to expand the current region to account for the space
   // between the previous section, if any, and the start of this section.
   if (ctx->memRegion && ctx->memRegion->curPos < dot)
     expandMemoryRegion(ctx->memRegion, dot - ctx->memRegion->curPos,

lld/ELF/Writer.cpp

 }
 
 // We want to place orphan sections so that they share as much
 // characteristics with their neighbors as possible. For example, if
 // both are rw, or both are tls.
 static std::vector<BaseCommand *>::iterator
 findOrphanPos(std::vector<BaseCommand *>::iterator b,
               std::vector<BaseCommand *>::iterator e) {
+  // OutputSections without the SHF_ALLOC flag are not part of the memory image
+  // and their addresses usually don't matter. Place any orphan sections without
+  // the SHF_ALLOC flag at the end so that these do not affect the address
+  // assignment of OutputSections with the SHF_ALLOC flag.
   OutputSection *sec = cast<OutputSection>(*e);
+  if (!(sec->flags & SHF_ALLOC))
+    return e;
 
   // Find the first element that has as close a rank as possible.
   auto i = std::max_element(b, e, [=](BaseCommand *a, BaseCommand *b) {
     return getRankProximity(sec, a) < getRankProximity(sec, b);
   });
   if (i == e)
     return e;
 
if (isRelroSection(sec)) {
               " sections");
     } else if (inRelroPhdr) {
       inRelroPhdr = false;
       relroEnd = sec;
     }
   }
 
   for (OutputSection *sec : outputSections) {
-    if (!(sec->flags & SHF_ALLOC))
-      break;
     if (!needsPtLoad(sec))
       continue;
 
     // Normally, sections in partitions other than the current partition are
     // ignored. But partition number 255 is a special case: it contains the
     // partition end marker (.part.end). It needs to be added to the main
     // partition so that a segment is created for it in the main partition,
     // which will cause the dynamic loader to reserve space for the other

lld/test/ELF/linkerscript/compress-debug-sections-custom.s

 # REQUIRES: x86, zlib
 
+## NOTE GNU ld makes .debug_str and .debug_info SHF_ALLOC due to `. += 10`.
 # RUN: echo "SECTIONS { \
 # RUN:          .text : { . += 0x10; *(.text) } \
-# RUN:          .debug_str : { . += 0x10; *(.debug_str) } \
-# RUN:          .debug_info : { . += 0x10; *(.debug_info) } \
+# RUN:          .debug_str 0 : { . += 0x10; *(.debug_str) } \
+# RUN:          .debug_info 0 : { . += 0x10; *(.debug_info) } \
 # RUN:          }" > %t.script
 
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t.o
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %S/../Inputs/compress-debug.s -o %t2.o
 # RUN: ld.lld %t2.o %t.o -o %t1 --compress-debug-sections=zlib -T %t.script
 # RUN: llvm-dwarfdump %t1 -debug-str | FileCheck %s
 # These two checks correspond to the patched values of a_sym and a_debug_sym.
 # T = 0x54 - address of .text input section for this file (the start address of

lld/test/ELF/linkerscript/sections.s

 # SEC-DEFAULT: 2 .data         00000020 {{[0-9a-f]*}} DATA
 # SEC-DEFAULT: 3 other         00000003 {{[0-9a-f]*}} DATA
 # SEC-DEFAULT: 4 .bss          00000002 {{[0-9a-f]*}} BSS
 # SEC-DEFAULT: 5 .comment      00000008 {{[0-9a-f]*}}
 # SEC-DEFAULT: 6 .symtab       00000030 {{[0-9a-f]*}}
 # SEC-DEFAULT: 7 .shstrtab     0000003b {{[0-9a-f]*}}
 # SEC-DEFAULT: 8 .strtab       00000008 {{[0-9a-f]*}}
 
-# Sections are put in order specified in linker script, other than alloc
-# sections going first.
+## Sections are placed in the order specified by the linker script. .data has
+## a PT_LOAD segment, even if it is preceded by a non-alloc section. To
+## allow this, place non-alloc orphan sections at the end and advance
+## location counters for non-alloc non-orphan sections.
 # RUN: echo "SECTIONS { \
 # RUN:          .bss : { *(.bss) } \
 # RUN:          other : { *(other) } \
 # RUN:          .shstrtab : { *(.shstrtab) } \
 # RUN:          .symtab : { *(.symtab) } \
 # RUN:          .strtab : { *(.strtab) } \
 # RUN:          .data : { *(.data) } \
-# RUN:          .text : { *(.text) } }" > %t.script
-# RUN: ld.lld -o %t3 --script %t.script %t
-# RUN: llvm-objdump --section-headers %t3 | \
-# RUN:   FileCheck -check-prefix=SEC-ORDER %s
-
-#           Idx Name          Size
-# SEC-ORDER: 1 .bss          00000002 {{[0-9a-f]*}} BSS
-# SEC-ORDER: 2 other         00000003 {{[0-9a-f]*}} DATA
-# SEC-ORDER: 3 .shstrtab     0000003b {{[0-9a-f]*}}
-# SEC-ORDER: 4 .symtab       00000030 {{[0-9a-f]*}}
-# SEC-ORDER: 5 .strtab       00000008 {{[0-9a-f]*}}
-# SEC-ORDER: 6 .comment      00000008 {{[0-9a-f]*}}
-# SEC-ORDER: 7 .data         00000020 {{[0-9a-f]*}} DATA
-# SEC-ORDER: 8 .text         0000000e {{[0-9a-f]*}} TEXT
+# RUN:          .text : { *(.text) } }" > %t3.lds
+# RUN: ld.lld -o %t3a -T %t3.lds %t
+# RUN: llvm-readelf -S -l %t3a | FileCheck --check-prefix=SEC-ORDER %s
+# RUN: ld.lld -o %t3b -T %t3.lds --unique %t
+# RUN: llvm-readelf -S -l %t3b | FileCheck --check-prefix=SEC-ORDER %s
+
+# SEC-ORDER:       [Nr] Name      Type     Address          Off    Size   ES Flg
+# SEC-ORDER:       [ 0]           NULL     0000000000000000 000000 000000 00
+# SEC-ORDER-NEXT:  [ 1] .bss      NOBITS   0000000000000000 001000 000002 00  WA
+# SEC-ORDER-NEXT:  [ 2] other     PROGBITS 0000000000000002 001002 000003 00  WA
+# SEC-ORDER-NEXT:  [ 3] .shstrtab STRTAB   0000000000000005 001005 00003b 00
+# SEC-ORDER-NEXT:  [ 4] .symtab   SYMTAB   0000000000000040 001040 000030 18
+# SEC-ORDER-NEXT:  [ 5] .strtab   STRTAB   0000000000000070 001070 000008 00
+# SEC-ORDER-NEXT:  [ 6] .data     PROGBITS 0000000000000078 001078 000020 00  WA
+# SEC-ORDER-NEXT:  [ 7] .text     PROGBITS 0000000000000098 001098 00000e 00  AX
+# SEC-ORDER-NEXT:  [ 8] .comment  PROGBITS 0000000000000000 0010a6 000008 01  MS
+
+# SEC-ORDER:        Type      Offset   VirtAddr           PhysAddr           FileSiz  MemSiz   Flg Align
+# SEC-ORDER-NEXT:   LOAD      0x001000 0x0000000000000000 0x0000000000000000 0x000098 0x000098 RW  0x1000
+# SEC-ORDER-NEXT:   LOAD      0x001098 0x0000000000000098 0x0000000000000098 0x00000e 0x00000e R E 0x1000
+# SEC-ORDER-NEXT:   GNU_STACK 0x000000 0x0000000000000000 0x0000000000000000 0x000000 0x000000 RW  0
 
 # .text and .data have swapped names but proper sizes and types.
 # RUN: echo "SECTIONS { \
 # RUN:          .data : { *(.text) } \
 # RUN:          .text : { *(.data) } }" > %t.script
 # RUN: ld.lld -o %t4 --script %t.script %t
 # RUN: llvm-objdump --section-headers %t4 | \
 # RUN:   FileCheck -check-prefix=SEC-SWAP-NAMES %s

 # SEC-MULTI-NEXT:   .data         00000020 {{[0-9a-f]*}} DATA
 # SEC-MULTI-NEXT:   .data         00000003 {{[0-9a-f]*}} DATA
 # SEC-MULTI-NEXT:   .bss          00000002 {{[0-9a-f]*}} BSS
 # SEC-MULTI-NEXT:   .comment      00000008 {{[0-9a-f]*}}
 # SEC-MULTI-NEXT:   .symtab       00000030 {{[0-9a-f]*}}
 # SEC-MULTI-NEXT:   .shstrtab     00000035 {{[0-9a-f]*}}
 # SEC-MULTI-NEXT:   .strtab       00000008 {{[0-9a-f]*}}
 
+## other is placed in a PT_LOAD segment even if it is preceded by a non-alloc section.
+## The current implementation places .data, .bss, .comment and other in the same PT_LOAD.
+# RUN: echo 'SECTIONS { \
+# RUN:          .text : { *(.text) } \
+# RUN:          .data : { *(.data) } \
+# RUN:          .comment : { *(.comment) } \
+# RUN:          other : { *(other) } }' > %t5.lds
+# RUN: ld.lld -o %t5 -T %t5.lds %t
+# RUN: llvm-readelf -S -l %t5 | FileCheck --check-prefix=SEP-BY-NONALLOC %s
+
+# SEP-BY-NONALLOC:      [Nr] Name      Type     Address          Off    Size   ES Flg
+# SEP-BY-NONALLOC:      [ 1] .text     PROGBITS 0000000000000000 001000 00000e 00  AX
+# SEP-BY-NONALLOC-NEXT: [ 2] .data     PROGBITS 000000000000000e 00100e 000020 00  WA
+# SEP-BY-NONALLOC-NEXT: [ 3] .bss      NOBITS   000000000000002e 00102e 000002 00  WA
+# SEP-BY-NONALLOC-NEXT: [ 4] .comment  PROGBITS 0000000000000030 00102e 000008 01  MS
+# SEP-BY-NONALLOC-NEXT: [ 5] other     PROGBITS 0000000000000038 001038 000003 00  WA
+
+# SEP-BY-NONALLOC:      Type      Offset   VirtAddr           PhysAddr           FileSiz  MemSiz   Flg Align
+# SEP-BY-NONALLOC-NEXT: LOAD      0x001000 0x0000000000000000 0x0000000000000000 0x00000e 0x00000e R E 0x1000
+# SEP-BY-NONALLOC-NEXT: LOAD      0x00100e 0x000000000000000e 0x000000000000000e 0x00002d 0x00002d RW  0x1000
+# SEP-BY-NONALLOC-NEXT: GNU_STACK 0x000000 0x0000000000000000 0x0000000000000000 0x000000 0x000000 RW  0
+
 # Input section pattern contains additional semicolon.
 # Case found in linux kernel script. Check we are able to parse it.
 # RUN: echo "SECTIONS { .text : { ;;*(.text);;S = 0;; } }" > %t.script
 # RUN: ld.lld -o /dev/null --script %t.script %t
 
 .globl _start
 _start:
     mov $60, %rax

lld/test/ELF/linkerscript/symbols-non-alloc.test

 # REQUIRES: x86
+## The address of a symbol assignment after a non-SHF_ALLOC section equals the
+## end address of the section.
+
 # RUN: echo '.section .nonalloc,""; .quad 0' \
 # RUN:   | llvm-mc -filetype=obj -triple=x86_64-unknown-linux - -o %t
 # RUN: ld.lld -o %t2 --script %s %t
 # RUN: llvm-objdump --section-headers -t %t2 | FileCheck %s
 
 # CHECK: Sections:
-# CHECK:  .nonalloc     00000008 0000000000000000
+# CHECK:  .nonalloc     00000008 0000000000000120
 
 # CHECK: SYMBOL TABLE:
-# CHECK:  0000000000000008 g .nonalloc 0000000000000000 Sym
+# CHECK:  0000000000000128 g .nonalloc 0000000000000000 Sym
 
 SECTIONS {
   . = SIZEOF_HEADERS;
   .text : { *(.text) }
   .nonalloc : { *(.nonalloc) }
   Sym = .;
 }

lldb/test/Shell/SymbolFile/DWARF/Inputs/debug-line-basic.script

 PHDRS {
   text PT_LOAD;
 }
 SECTIONS {
-  .shstrtab     : { *(.shstrtab    ) }
-  .debug_info   : { *(.debug_info  ) }
-  .debug_line   : { *(.debug_line  ) }
-  .debug_str    : { *(.debug_str   ) }
-  .debug_abbrev : { *(.debug_abbrev) }
+  .shstrtab     0 : { *(.shstrtab    ) }
+  .debug_info   0 : { *(.debug_info  ) }
+  .debug_line   0 : { *(.debug_line  ) }
+  .debug_str    0 : { *(.debug_str   ) }
+  .debug_abbrev 0 : { *(.debug_abbrev) }
 
   . = 0x201000;
   .text : { *(.text .text.f) } :text
   /DISCARD/ : { *(*) }
 }