[ELF] Emit __ehdr_start when there is a segment containing program headers

[phosek]

Summary

The current logic for defining ehdr_start doesn't match the GNU linkers, whereas LLD does not define ehdr_start whenever a linker script is being used, while GNU linkers defined the symbol whenever there's a loadable segment which contains ELF headers. This change modifies LLD to use the same logic as GNU linkers.

This is complicated by the fact that LLD checks undefined symbols while scanning relocations, which happens before binary layout is finalized and program headers have been created. To handle this, we define the __ehdr_start symbol unconditionally, and only check whether it should have been defined after program headers have been created; if not and there are references to this symbol, we report an error.

Fixes https://bugs.llvm.org/show_bug.cgi?id=32367

[ruiu]

ELF/Writer.cpp

1200

What is this doing?

1205

Re-scanning all relocations is probably too slow.

[phosek]

ELF/Writer.cpp

1200

The idea is that ElfSym::EhdrStart is only defined if needed by addOptionalRegular, so if it's nullptr we can ignore it.

1205

I'm aware of that, do you have any ideas on how to do it faster? I don't know if there's any way to find relocations for a given symbol which is what's really needed here. Alternative would be to print an error without giving section and offset info, but that'll make it inconsistent with error reports for regular undefined symbols.

[ruiu]

Isn't there any way to determine if a ELF header is going to be included in some segment before scanning relocations?

Or, do you have any problem if you unconditionally define the symbol (and set it to zero if the condition is not satisfied)?

[phosek]

In D32887#747666, @ruiu wrote:

Isn't there any way to determine if a ELF header is going to be included in some segment before scanning relocations?

I can add a method to LinkerScript that checks if ELF header is going to included and define __ehdr_start conditionally based on that, would that be fine with you?

[ruiu]

It depends on complexity, but worth a try.

[phosek]

That solution isn't going to work because it wouldn't handle case where we only have SECTIONS with enough space for headers. I have added a test case for that. A solution to avoid rescaning all relocations I have implemented is to simply collect all references to __ehdr_start during the existing scan and then report the error if needed.

[ruiu]

I'm reluctant to introduce a new concept of SymbolReference just for ehdr_start symbol which is frankly speaking not that important. You needed these new concepts for defining ehdr_start only when an ELF header is memory-allocated, right? Is there any problem if you always define that symbol and leave it zero if an ELF header is not in an allocated segment?

[phosek]

In D32887#749970, @ruiu wrote:

I'm reluctant to introduce a new concept of SymbolReference just for ehdr_start symbol which is frankly speaking not that important. You needed these new concepts for defining ehdr_start only when an ELF header is memory-allocated, right? Is there any problem if you always define that symbol and leave it zero if an ELF header is not in an allocated segment?

I can use just tuple to avoid defining a new concept, that should be sufficient. The reason I don't like always defining __ehdr_start is because it changes its semantics and hence might break the existing code that relies on the existing semantics. In our case, it'll break the kernel build so we'll need a special case for LLD.

[ruiu]

Right, but we already violated the assumption for symbols such as __bss_start as it is always defined even if .bss does not exist.

How are you using __ehdr_start?

[phosek]

In our dynamic linker to find the image start. That use case is not a problem. We have some special binaries like vDSO which are using custom linker script and later post-processed and it's the post-processing stage I'm concerned about. I'd need to try and see if it's going to handle this.

Outside of our codebase, the main issue I can see (other than implementing semantics that differs from GNU linkers) is in code that uses __ehdr_start and uses a linker script. If the linker script is incorrect and the __ehdr_start cannot be defined, with GNU linkers they'll get a linker error. If LLD always defines __ehdr_start, the code will link but segfault at runtime when you try to access __ehdr_start.

[ruiu]

These possible compatibility issues could be real concerns, but I think we should go with a simple way which is to define ehdr_start unconditionally. When we need to strike a balance among simplicity, efficiency and compatibility, we sometimes chose simplicity or efficiency over the 100% precise compatibility, and it seems to be working surprisingly well. It feels __ehdr_start is in the same category. We can add more code later if it really needs more complexity.

[mcgrathr]

For the record, the intent of __ehdr_start is exactly that it be defined if and only if the ELF file header and program headers are indeed visible via some PT_LOAD segment (i.e. in the PAGE_TRUNCATE(p_vaddr)..PAGE_ROUND(p_vaddr + p_filesz) region) and not be defined otherwise.
I invented the feature in the GNU linkers, and this is the specification I gave it.
Code can use a weak reference to __ehdr_start and check for &__ehdr_start==0 to handle both cases. For that scenario, resolving it to absolute 0 even when there is a strong reference rather than diagnosing the undefined symbol is probably acceptable in practice.

In LLD, the only time it could ever be omitted is when there is a custom linker script being used. So this is unlikely to come up.

ELF/Relocations.h

 //===- Relocations.h -------------------------------------------*- C++ -*-===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_ELF_RELOCATIONS_H
 #define LLD_ELF_RELOCATIONS_H
 
 #include "lld/Core/LLVM.h"
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallVector.h"
 #include <map>
 #include <vector>
 
 namespace lld {
 namespace elf {
 class SymbolBody;
 class InputSection;
 class InputSectionBase;

 struct Relocation {
   RelExpr Expr;
   uint32_t Type;
   uint64_t Offset;
   int64_t Addend;
   SymbolBody *Sym;
 };
 
+template <class ELFT> void reportUndefined(SymbolBody &Sym,
+                                           InputSectionBase &S,
+                                           uint64_t Offset);
+
 template <class ELFT> void scanRelocations(InputSectionBase &);
 
 class ThunkSection;
 class Thunk;
 
 template <class ELFT> class ThunkCreator {
 public:
   // Return true if Thunks have been added to OutputSections

 template <class ELFT>
 static inline int64_t getAddend(const typename ELFT::Rel &Rel) {
   return 0;
 }
 template <class ELFT>
 static inline int64_t getAddend(const typename ELFT::Rela &Rel) {
   return Rel.r_addend;
 }
+
+// Collect references to __ehdr_start in case we need to report an undefined
+// symbol error when the loadable segment containing headers is missing.
+struct EhdrStartReference {
+  InputSectionBase &Sec;
+  uint64_t Offset;
+};
+extern SmallVector<EhdrStartReference, 1> EhdrStartReferences;
 }
 }
 
 #endif

ELF/Relocations.cpp

 using namespace llvm;
 using namespace llvm::ELF;
 using namespace llvm::object;
 using namespace llvm::support::endian;
 
 using namespace lld;
 using namespace lld::elf;
 
+SmallVector<EhdrStartReference, 1> elf::EhdrStartReferences;
+
 // Construct a message in the following format.
 //
 // >>> defined in /home/alice/src/foo.o
 // >>> referenced by bar.c:12 (/home/alice/src/bar.c:12)
 // >>>               /home/alice/src/bar.o:(.text+0x1)
 template <class ELFT>
 static std::string getLocation(InputSectionBase &S, const SymbolBody &Sym,
                                uint64_t Off) {
static int64_t computeMipsAddend(const RelTy &Rel, InputSectionBase &Sec,
   }
 
   warn("can't find matching " + toString(PairTy) + " relocation for " +
        toString(Type));
   return 0;
 }
 
 template <class ELFT>
-static void reportUndefined(SymbolBody &Sym, InputSectionBase &S,
-                            uint64_t Offset) {
+void elf::reportUndefined(SymbolBody &Sym, InputSectionBase &S,
   if (Config->UnresolvedSymbols == UnresolvedPolicy::IgnoreAll)
     return;
 
   bool CanBeExternal = Sym.symbol()->computeBinding() != STB_LOCAL &&
                        Sym.getVisibility() == STV_DEFAULT;
   if (Config->UnresolvedSymbols == UnresolvedPolicy::Ignore && CanBeExternal)
     return;
 
for (auto I = Rels.begin(), End = Rels.end(); I != End; ++I) {
 
     // Report undefined symbols. The fact that we report undefined
     // symbols here means that we report undefined symbols only when
     // they have relocations pointing to them. We don't care about
     // undefined symbols that are in dead-stripped sections.
     if (!Body.isLocal() && Body.isUndefined() && !Body.symbol()->isWeak())
       reportUndefined<ELFT>(Body, Sec, Rel.r_offset);
 
+    if (&Body == ElfSym::EhdrStart)
+      EhdrStartReferences.push_back({Sec, Rel.r_offset});
+
     RelExpr Expr =
         Target->getRelExpr(Type, Body, Sec.Data.begin() + Rel.r_offset);
 
     // Ignore "hint" relocations because they are only markers for relaxation.
     if (isRelExprOneOf<R_HINT, R_NONE>(Expr))
       continue;
 
     bool Preemptible = isPreemptible(Body, Type);

ELF/Symbols.h

 };
 
 // Some linker-generated symbols need to be created as
 // DefinedRegular symbols.
 struct ElfSym {
   // __bss_start
   static DefinedRegular *Bss;
 
+  // __ehdr_start
+  static DefinedRegular *EhdrStart;
+
   // etext and _etext
   static DefinedRegular *Etext1;
   static DefinedRegular *Etext2;
 
   // edata and _edata
   static DefinedRegular *Edata1;
   static DefinedRegular *Edata2;
 

ELF/Symbols.cpp

 using namespace llvm;
 using namespace llvm::object;
 using namespace llvm::ELF;
 
 using namespace lld;
 using namespace lld::elf;
 
 DefinedRegular *ElfSym::Bss;
+DefinedRegular *ElfSym::EhdrStart;
 DefinedRegular *ElfSym::Etext1;
 DefinedRegular *ElfSym::Etext2;
 DefinedRegular *ElfSym::Edata1;
 DefinedRegular *ElfSym::Edata2;
 DefinedRegular *ElfSym::End1;
 DefinedRegular *ElfSym::End2;
 DefinedRegular *ElfSym::MipsGp;
 DefinedRegular *ElfSym::MipsGpDisp;

ELF/Writer.cpp

if (Config->Relocatable) {
     Script->synchronize();
     Script->assignAddresses(Phdrs);
 
     // Remove empty PT_LOAD to avoid causing the dynamic linker to try to mmap a
     // 0 sized region. This has to be done late since only after assignAddresses
     // we know the size of the sections.
     removeEmptyPTLoad();
 
+    if (ElfSym::EhdrStart) {
+      auto PhdrI =
+          std::find_if(Phdrs.begin(), Phdrs.end(), [](const PhdrEntry &E) {
+                       return E.p_type == PT_LOAD && E.First == Out::ElfHeader
+                           && (E.p_offset & -E.p_align) == 0; });
+      if (PhdrI == Phdrs.end()) {
+        for (auto &R : EhdrStartReferences) {
+          reportUndefined<ELFT>(*ElfSym::EhdrStart, R.Sec, R.Offset);
+        }
+      }
+    }
+
     if (!Config->OFormatBinary)
       assignFileOffsets();
     else
       assignFileOffsetsBinary();
 
     setPhdrs();
     fixPredefinedSymbols();
   }
template <class ELFT> void Writer<ELFT>::addReservedSymbols() {
 
   // __tls_get_addr is defined by the dynamic linker for dynamic ELFs. For
   // static linking the linker is required to optimize away any references to
   // __tls_get_addr, so it's not defined anywhere. Create a hidden definition
   // to avoid the undefined symbol error.
   if (!In<ELFT>::DynSymTab)
     Symtab<ELFT>::X->addIgnored("__tls_get_addr");
 
+  // __ehdr_start is the location of ELF file headers.
+  ElfSym::EhdrStart = addOptionalRegular<ELFT>("__ehdr_start", Out::ElfHeader, 0, STV_HIDDEN);
+
   // If linker script do layout we do not need to create any standart symbols.
   if (Script->Opt.HasSections)
     return;
 
-  // __ehdr_start is the location of ELF file headers.
-  addOptionalRegular<ELFT>("__ehdr_start", Out::ElfHeader, 0, STV_HIDDEN);
-
   auto Add = [](StringRef S) {
     return addOptionalRegular<ELFT>(S, Out::ElfHeader, 0, STV_DEFAULT);
   };
 
   ElfSym::Bss = Add("__bss_start");
   ElfSym::End1 = Add("end");
   ElfSym::End2 = Add("_end");
   ElfSym::Etext1 = Add("etext");
for (InputSectionBase *S : llvm::reverse(InputSections)) {
     SS->Live = false;
     // If there are no other sections in the output section, remove it from the
     // output.
     if (SS->OutSec->Sections.empty())
       V.erase(std::find(V.begin(), V.end(), SS->OutSec));
   }
 }
 
+template <class ELFT, class RelTy>
+static void checkUndefined(InputSectionBase &Sec, ArrayRef<RelTy> Rels,
+                           SymbolBody *S) {
+  for (auto &I : Rels)
+    if (&Sec.getFile<ELFT>()->getRelocTargetSym(I) == S)
+      reportUndefined<ELFT>(*S, Sec, I.r_offset);
+}
+
 // Create output section objects and add them to OutputSections.
 template <class ELFT> void Writer<ELFT>::finalizeSections() {
   Out::DebugInfo = findSection(".debug_info");
   Out::PreinitArray = findSection(".preinit_array");
   Out::InitArray = findSection(".init_array");
   Out::FiniArray = findSection(".fini_array");
 
   // The linker needs to define SECNAME_start, SECNAME_end and SECNAME_stop
template <class ELFT> void Writer<ELFT>::finalizeSections() {
   // The headers have to be created before finalize as that can influence the
   // image base and the dynamic section on mips includes the image base.
   if (!Config->Relocatable && !Config->OFormatBinary) {
     Phdrs = Script->hasPhdrsCommands() ? Script->createPhdrs() : createPhdrs();
     addPtArmExid(Phdrs);
     Out::ProgramHeaders->Size = sizeof(Elf_Phdr) * Phdrs.size();
   }
 
   // Dynamic section must be the last one in this list and dynamic
   // symbol table section (DynSymTab) must be the first one.
   applySynthetic({In<ELFT>::DynSymTab,  In<ELFT>::Bss,      In<ELFT>::BssRelRo,
                   In<ELFT>::GnuHashTab, In<ELFT>::HashTab,  In<ELFT>::SymTab,
                   In<ELFT>::ShStrTab,   In<ELFT>::StrTab,   In<ELFT>::VerDef,
                   In<ELFT>::DynStrTab,  In<ELFT>::GdbIndex, In<ELFT>::Got,
                   In<ELFT>::MipsGot,    In<ELFT>::IgotPlt,  In<ELFT>::GotPlt,
                   In<ELFT>::RelaDyn,    In<ELFT>::RelaIplt, In<ELFT>::RelaPlt,
                   In<ELFT>::Plt,        In<ELFT>::Iplt,     In<ELFT>::Plt,
                   In<ELFT>::EhFrameHdr, In<ELFT>::VerSym,   In<ELFT>::VerNeed,
                   In<ELFT>::Dynamic},
                  [](SyntheticSection *SS) { SS->finalizeContents(); });
 
   // Some architectures use small displacements for jump instructions.

test/ELF/linkerscript/ehdr_start.s

 # REQUIRES: x86
-
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t.o
-# RUN: echo "SECTIONS { }" > %t.script
-# RUN: not ld.lld %t.o -script %t.script -o %t 2>&1 | FileCheck %s
-# CHECK: error: undefined symbol: __ehdr_start
-# CHECK: >>> referenced by {{.*}}:(.text+0x0)
+
+# RUN: echo "SECTIONS { }" > %t1.script
+# RUN: not ld.lld %t.o -script %t1.script -o %t1 2>&1 | FileCheck %s --check-prefix=ERROR
+# ERROR: error: undefined symbol: __ehdr_start
+# ERROR: >>> referenced by {{.*}}:(.text+0x0)
+
+# RUN: echo "SECTIONS { \
+# RUN:   . = SIZEOF_HEADERS; \
+# RUN:   .text : { *(.text*) } \
+# RUN: }" > %t.script
+# RUN: ld.lld %t.o -script %t.script -o %t 2>&1
+# RUN: llvm-readobj -symbols %t | FileCheck %s --check-prefix=HEADERS
+
+# HEADERS:    Name: __ehdr_start (1)
+# HEADERS-NEXT:    Value: 0x0
+# HEADERS-NEXT:    Size: 0
+# HEADERS-NEXT:    Binding: Local (0x0)
+# HEADERS-NEXT:    Type: None (0x0)
+# HEADERS-NEXT:    Other [ (0x2)
+# HEADERS-NEXT:      STV_HIDDEN (0x2)
+# HEADERS-NEXT:    ]
+# HEADERS-NEXT:    Section: .text (0x1)
+
+# RUN: echo "SECTIONS { \
+# RUN:   . = SIZEOF_HEADERS; \
+# RUN:   .text : { *(.text*) } : text \
+# RUN: } \
+# RUN: PHDRS { \
+# RUN:   text PT_LOAD FILEHDR PHDRS; \
+# RUN: }" > %t.script
+# RUN: ld.lld %t.o -script %t.script -o %t 2>&1
+# RUN: llvm-readobj -symbols %t | FileCheck %s --check-prefix=PHDRS
+
+# PHDRS:    Name: __ehdr_start (1)
+# PHDRS-NEXT:    Value: 0x0
+# PHDRS-NEXT:    Size: 0
+# PHDRS-NEXT:    Binding: Local (0x0)
+# PHDRS-NEXT:    Type: None (0x0)
+# PHDRS-NEXT:    Other [ (0x2)
+# PHDRS-NEXT:      STV_HIDDEN (0x2)
+# PHDRS-NEXT:    ]
+# PHDRS-NEXT:    Section: .text (0x1)
 
 .text
 .global _start, __ehdr_start
 _start:
   .quad __ehdr_start