[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

Why do you need this change ?

736

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

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

26

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

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

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

ELF/LinkerScript.cpp

void LinkerScript::allocateHeaders(std::vector<PhdrEntry *> &Phdrs) {
 
   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 (Opt.HasSections) {
+    uint64_t Base = alignDown(Min, Config->MaxPageSize);
+    if (HeaderSize <= Min - Base || Script->hasPhdrsCommands()) {
+      Out::ElfHeader->Addr = Base;
+      Out::ProgramHeaders->Addr = Base + Out::ElfHeader->Size;
+      return;
+    }
+  } else {
     if (HeaderSize <= Min || Script->hasPhdrsCommands()) {
       Min = 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;
+    } else if (Sec->FirstInPtLoad == Out::ProgramHeaders) {
+      ActualFirst = Sec;
+      break;
     }
   }
   if (ActualFirst) {
-    for (OutputSection *Sec : OutputSections)
+    for (OutputSection *Sec : OutputSections) {
       if (Sec->FirstInPtLoad == Out::ElfHeader)
         Sec->FirstInPtLoad = ActualFirst;
+      else if (Sec->FirstInPtLoad == Out::ProgramHeaders)
+        Sec->FirstInPtLoad = ActualFirst;
+    }
     FirstPTLoad->First = ActualFirst;
   } else {
     Phdrs.erase(It);
   }
 
   auto PhdrI = llvm::find_if(
       Phdrs, [](const PhdrEntry *E) { return E->p_type == PT_PHDR; });
   if (PhdrI != Phdrs.end())

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

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

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: ]

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

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 { \
+# RUN:   . = 0x2000; \
+# RUN:   .text : AT(0x100000) { \
+# RUN:     *(.text) \
+# RUN:   } \
+# RUN: }" > %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:   }
+# CHECK-NEXT:   ProgramHeader {
+# CHECK-NEXT:     Type: PT_GNU_STACK (0x6474E551)
+# CHECK-NEXT:     Offset: 0x0
+# CHECK-NEXT:     VirtualAddress: 0x0
+# CHECK-NEXT:     PhysicalAddress: 0x0
+# CHECK-NEXT:     FileSize: 0
+# CHECK-NEXT:     MemSize: 0
+# CHECK-NEXT:     Flags [ (0x6)
+# CHECK-NEXT:       PF_R (0x4)
+# CHECK-NEXT:       PF_W (0x2)
+# CHECK-NEXT:     ]
+# CHECK-NEXT:     Alignment: 0
+# CHECK-NEXT:   }
+# CHECK-NEXT: ]
+
+.section .text
+.global _start
+
+_start:
+  ret