[ELF] Don't output headers into a segment if there's no space for them

[phosek]

Summary

Currently, LLD checks whether there's enough space for headers by
checking if headers fit below the address of the first allocated
section. However, that's always thue if the binary doesn't start
at zero which means that LLD always emits a segment for headers,
even if no other sections belong to that segment.

This is a problem in cases when linker script is being used with a
non-zero start address when we don't want to make the headers visible
by not leaving enough space for them. This pattern is common in
embedded programming but doesn't work in LLD.

This patch changes the behavior of LLD in case when linker script
is being to match the behavior of BFD ld and gold, which is to only
place headers into a segment when they're covered by some output
section.

[mcgrathr]

The new test case exhibits the correct behavior.

[phosek]

Ping

[grimar]

ELF/LinkerScript.cpp

725 ↗

(On Diff #109468)

Why do you need this change ?

736 ↗

(On Diff #109468)

And this one ?

I removed both and had no no any test failtures:

OutputSection *ActualFirst = nullptr;
for (OutputSection *Sec : OutputSections) {
  if (Sec->FirstInPtLoad == Out::ElfHeader) {
    ActualFirst = Sec;
    break;
  }
}
if (ActualFirst) {
  for (OutputSection *Sec : OutputSections)
    if (Sec->FirstInPtLoad == Out::ElfHeader)
      Sec->FirstInPtLoad = ActualFirst;
  FirstPTLoad->First = ActualFirst;
} else {
  Phdrs.erase(It);
}

test/ELF/linkerscript/segment-headers.s

3 ↗

(On Diff #109468)

This can be single line probably.
echo "SECTIONS { . = 0x2000; .text : AT(0x100000) { *(.text) } }" > %t.script

26 ↗

(On Diff #109468)

Do you need to check anything except first load ?

[peter.smith]

I'd like to see something like this for embedded systems as the ELF file is often not directly run on the target (PT_LOAD regions are extracted into binary or hex and burned into flash), having the ELF headers mapped in the first PT_LOAD is often detrimental. I suggest you add Rafael as a reviewer as well as he has touched this area fairly recently.

ELF/LinkerScript.cpp

704 ↗

(On Diff #109468)

I found the combined if/else quite hard to follow, especially trying to work out what the differences between the two were as the logic is quite similar. Would it make sense to rewrite the combined if/else as:

uint64_t Base = (Opt.HasSections) ? alignDown(Min, Config->MaxPageSize) : 0;
  if (HeaderSize <= Min - Base || Script->hasPhdrsCommands()) {
    Min = (Opt.HasSections) ? Base : alignDown(Min - HeaderSize,
                                               Config->MaxPageSize);
    Out::ElfHeader->Addr = Min;
    Out::ProgramHeaders->Addr = Min + Out::ElfHeader->Size;
    return;
  }

A comment to explain what we are trying to do would help here as it isn't immediately obvious from the code why we are doing this.

[phosek]

ELF/LinkerScript.cpp

736 ↗

(On Diff #109468)

You're right, that was a leftover from a previous version of the patch but that's no longer needed.

[ruiu]

I'm sorry but I realized that I don't actually understand what LinkerScript::allocateHeaders exactly does, so I don't understand the new code as well. I believe you know better than me, so can you add a function comment to describe what that function is supposed to do?

[phosek]

In D36256#846163, @ruiu wrote:

I'm sorry but I realized that I don't actually understand what LinkerScript::allocateHeaders exactly does, so I don't understand the new code as well. I believe you know better than me, so can you add a function comment to describe what that function is supposed to do?

Done, let me know if the comment makes sense to you.

[ruiu]

Thank you for adding the comment! I now understand what this function is doing. LGTM

lld/trunk/ELF/LinkerScript.cpp

for (BaseCommand *Base : Opt.Commands) {
     } else {
       DefPhdrs = Sec->Phdrs;
     }
   }
 
   removeEmptyCommands();
 }
 
+// Try to find an address for the file and program headers output sections,
+// which were unconditionally added to the first PT_LOAD segment earlier.
+//
+// When using the default layout, we check if the headers fit below the first
+// allocated section. When using a linker script, we also check if the headers
+// are covered by the output section. This allows omitting the headers by not
+// leaving enough space for them in the linker script; this pattern is common
+// in embedded systems.
+//
+// If there isn't enough space for these sections, we'll remove them from the
+// PT_LOAD segment, and we'll also remove the PT_PHDR segment.
 void LinkerScript::allocateHeaders(std::vector<PhdrEntry *> &Phdrs) {
   uint64_t Min = std::numeric_limits<uint64_t>::max();
   for (OutputSection *Sec : OutputSections)
     if (Sec->Flags & SHF_ALLOC)
       Min = std::min<uint64_t>(Min, Sec->Addr);
 
   auto It = llvm::find_if(
       Phdrs, [](const PhdrEntry *E) { return E->p_type == PT_LOAD; });
   if (It == Phdrs.end())
     return;
   PhdrEntry *FirstPTLoad = *It;
 
   uint64_t HeaderSize = getHeaderSize();
-  if (HeaderSize <= Min || Script->hasPhdrsCommands()) {
-    Min = alignDown(Min - HeaderSize, Config->MaxPageSize);
+  // When linker script with SECTIONS is being used, don't output headers
+  // unless there's a space for them.
+  uint64_t Base = Opt.HasSections ? alignDown(Min, Config->MaxPageSize) : 0;
+  if (HeaderSize <= Min - Base || Script->hasPhdrsCommands()) {
+    Min = Opt.HasSections ? Base
+                          : alignDown(Min - HeaderSize, Config->MaxPageSize);
     Out::ElfHeader->Addr = Min;
     Out::ProgramHeaders->Addr = Min + Out::ElfHeader->Size;
     return;
   }
 
-  assert(FirstPTLoad->First == Out::ElfHeader);
   OutputSection *ActualFirst = nullptr;
   for (OutputSection *Sec : OutputSections) {
     if (Sec->FirstInPtLoad == Out::ElfHeader) {
       ActualFirst = Sec;
       break;
     }
   }
   if (ActualFirst) {

lld/trunk/test/ELF/linkerscript/at-addr.s

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
 # RUN: echo "SECTIONS { . = 0x1000; \
 # RUN:  .aaa : AT(ADDR(.aaa) - 0x500) { *(.aaa) } \
 # RUN:  .bbb : AT(ADDR(.bbb) - 0x500) { *(.bbb) } \
 # RUN:  .ccc : AT(ADDR(.ccc) - 0x500) { *(.ccc) } \
 # RUN: }" > %t.script
 # RUN: ld.lld %t --script %t.script -o %t2
 # RUN: llvm-readobj -program-headers %t2 | FileCheck %s
 
 # CHECK:      Type: PT_LOAD
-# CHECK-NEXT:   Offset: 0x0
-# CHECK-NEXT:   VirtualAddress: 0x0
-# CHECK-NEXT:   PhysicalAddress: 0x0
-# CHECK:      Type: PT_LOAD
 # CHECK-NEXT:   Offset: 0x1000
 # CHECK-NEXT:   VirtualAddress: 0x1000
 # CHECK-NEXT:   PhysicalAddress: 0xB00
 # CHECK:      Type: PT_LOAD
 # CHECK-NEXT:   Offset: 0x1008
 # CHECK-NEXT:   VirtualAddress: 0x1008
 # CHECK-NEXT:   PhysicalAddress: 0xB08
 # CHECK:      Type: PT_LOAD

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

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
 # RUN: echo "SECTIONS { \
 # RUN:  . = 0x1000; \
 # RUN:  .aaa : AT(0x2000) { *(.aaa) } \
 # RUN:  .bbb : { *(.bbb) } \
 # RUN:  .ccc : AT(0x3000) { *(.ccc) } \
 # RUN:  .ddd : AT(0x4000) { *(.ddd) } \
 # RUN:  .eee 0x5000 : AT(0x5000) { *(.eee) } \
 # RUN: }" > %t.script
 # RUN: ld.lld %t --script %t.script -o %t2
 # RUN: llvm-readobj -program-headers %t2 | FileCheck %s
 
 # CHECK:      ProgramHeaders [
 # CHECK-NEXT:   ProgramHeader {
-# CHECK-NEXT:     Type: PT_PHDR
-# CHECK-NEXT:     Offset: 0x40
-# CHECK-NEXT:     VirtualAddress: 0x40
-# CHECK-NEXT:     PhysicalAddress: 0x40
-# CHECK-NEXT:     FileSize:
-# CHECK-NEXT:     MemSize:
-# CHECK-NEXT:     Flags [
-# CHECK-NEXT:       PF_R
-# CHECK-NEXT:     ]
-# CHECK-NEXT:     Alignment: 8
-# CHECK-NEXT:   }
-# CHECK-NEXT:   ProgramHeader {
-# CHECK-NEXT:     Type: PT_LOAD
-# CHECK-NEXT:     Offset: 0x0
-# CHECK-NEXT:     VirtualAddress: 0x0
-# CHECK-NEXT:     PhysicalAddress: 0x0
-# CHECK-NEXT:     FileSize:
-# CHECK-NEXT:     MemSize:
-# CHECK-NEXT:     Flags [
-# CHECK-NEXT:       PF_R
-# CHECK-NEXT:       PF_X
-# CHECK-NEXT:     ]
-# CHECK-NEXT:     Alignment:
-# CHECK-NEXT:   }
-# CHECK-NEXT:   ProgramHeader {
 # CHECK-NEXT:     Type: PT_LOAD
 # CHECK-NEXT:     Offset: 0x1000
 # CHECK-NEXT:     VirtualAddress: 0x1000
 # CHECK-NEXT:     PhysicalAddress: 0x2000
 # CHECK-NEXT:     FileSize: 16
 # CHECK-NEXT:     MemSize: 16
 # CHECK-NEXT:     Flags [
 # CHECK-NEXT:       PF_R

lld/trunk/test/ELF/linkerscript/header-addr.s

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %s -o %t.o
 # RUN: echo "PHDRS {all PT_LOAD PHDRS;} \
 # RUN:       SECTIONS { \
-# RUN:       . = 0x2000; \
+# RUN:       . = 0x2000 + SIZEOF_HEADERS; \
 # RUN:       .text : {*(.text)} :all \
 # RUN:     }" > %t.script
 # RUN: ld.lld -o %t.so --script %t.script %t.o -shared
 # RUN: llvm-readobj -program-headers %t.so | FileCheck %s
 
 # CHECK:      ProgramHeaders [
 # CHECK-NEXT:   ProgramHeader {
 # CHECK-NEXT:     Type: PT_LOAD
 # CHECK-NEXT:     Offset: 0x40
-# CHECK-NEXT:     VirtualAddress: 0x1040
-# CHECK-NEXT:     PhysicalAddress: 0x1040
-# CHECK-NEXT:     FileSize: 4176
-# CHECK-NEXT:     MemSize: 4176
+# CHECK-NEXT:     VirtualAddress: 0x2040
+# CHECK-NEXT:     PhysicalAddress: 0x2040
+# CHECK-NEXT:     FileSize: 200
+# CHECK-NEXT:     MemSize: 200
 # CHECK-NEXT:     Flags [
 # CHECK-NEXT:       PF_R (0x4)
 # CHECK-NEXT:       PF_W (0x2)
 # CHECK-NEXT:       PF_X (0x1)
 # CHECK-NEXT:     ]
 # CHECK-NEXT:     Alignment: 4096
 # CHECK-NEXT:   }
 # CHECK-NEXT: ]
 
 # RUN: ld.lld -o %t2.so --script %t.script %t.o -shared -z max-page-size=0x2000
 # RUN: llvm-readobj -program-headers %t2.so \
 # RUN:   | FileCheck --check-prefix=MAXPAGE %s
 
 # MAXPAGE:      ProgramHeaders [
 # MAXPAGE-NEXT:   ProgramHeader {
 # MAXPAGE-NEXT:     Type: PT_LOAD
 # MAXPAGE-NEXT:     Offset: 0x40
-# MAXPAGE-NEXT:     VirtualAddress: 0x40
-# MAXPAGE-NEXT:     PhysicalAddress: 0x40
-# MAXPAGE-NEXT:     FileSize: 8272
-# MAXPAGE-NEXT:     MemSize: 8272
+# MAXPAGE-NEXT:     VirtualAddress: 0x2040
+# MAXPAGE-NEXT:     PhysicalAddress: 0x2040
+# MAXPAGE-NEXT:     FileSize: 200
+# MAXPAGE-NEXT:     MemSize: 200
 # MAXPAGE-NEXT:     Flags [
 # MAXPAGE-NEXT:       PF_R
 # MAXPAGE-NEXT:       PF_W
 # MAXPAGE-NEXT:       PF_X
 # MAXPAGE-NEXT:     ]
 # MAXPAGE-NEXT:     Alignment: 8192
 # MAXPAGE-NEXT:   }
 # MAXPAGE-NEXT: ]

lld/trunk/test/ELF/linkerscript/phdr-check.s

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
 
-# RUN: echo "SECTIONS { . = 0x10000000; .text : {*(.text.*)} }" > %t.script
+# RUN: echo "SECTIONS { . = 0x10000000 + SIZEOF_HEADERS; .text : {*(.text.*)} }" > %t.script
 # RUN: ld.lld -o %t1 --script %t.script %t
 # RUN: llvm-readobj -program-headers %t1 | FileCheck %s
 # CHECK:      ProgramHeaders [
 # CHECK-NEXT:  ProgramHeader {
 # CHECK-NEXT:    Type: PT_PHDR (0x6)
 # CHECK-NEXT:    Offset: 0x40
-# CHECK-NEXT:    VirtualAddress: 0xFFFF040
+# CHECK-NEXT:    VirtualAddress: 0x10000040
 
 .global _start
 _start:
  nop

lld/trunk/test/ELF/linkerscript/segment-headers.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t.o
+# RUN: echo "SECTIONS { . = 0x2000; .text : AT(0x100000) { *(.text) } }" > %t.script
+# RUN: ld.lld -o %t --script %t.script %t.o
+# RUN: llvm-readobj -l %t | FileCheck %s
+
+# CHECK: ProgramHeaders [
+# CHECK-NEXT:   ProgramHeader {
+# CHECK-NEXT:     Type: PT_LOAD (0x1)
+# CHECK-NEXT:     Offset: 0x1000
+# CHECK-NEXT:     VirtualAddress: 0x2000
+# CHECK-NEXT:     PhysicalAddress: 0x100000
+# CHECK-NEXT:     FileSize: 1
+# CHECK-NEXT:     MemSize: 1
+# CHECK-NEXT:     Flags [ (0x5)
+# CHECK-NEXT:       PF_R (0x4)
+# CHECK-NEXT:       PF_X (0x1)
+# CHECK-NEXT:     ]
+# CHECK-NEXT:     Alignment: 4096
+# CHECK-NEXT:   }
+
+.section .text
+.global _start
+
+_start:
+  ret