Fix PR28575

[• rafael]

Summary

Not all relocations from a .eh_frame that point to an executable
section should be ignored. In particular, the relocation finding the
personality function should not.

This is a reduction from trying to bootstrap a static lld on linux.

[ruiu]

ELF/MarkLive.cpp

115

I'd rename Fn Enqueue.

ELF/OutputSections.cpp

1032

You don't need to pas FirstRelI as a separate parameter because you can use Piece->FirstRelocation instead.

1041

Ditto.

[• rafael]

Address review comments

[ruiu]

LGTM

[Eugene.Zelenko]

Committed in r276329.

ELF/InputSection.h

public:
   SectionPiece *getSectionPiece(uintX_t Offset);
   const SectionPiece *getSectionPiece(uintX_t Offset) const;
 
 private:
   llvm::DenseMap<uintX_t, uintX_t> OffsetMap;
   llvm::DenseSet<uintX_t> LiveOffsets;
 };
 
+struct EhSectionPiece : public SectionPiece {
+  EhSectionPiece(size_t Off, ArrayRef<uint8_t> Data, unsigned FirstRelocation)
+      : SectionPiece(Off, Data), FirstRelocation(FirstRelocation) {}
+  unsigned FirstRelocation;
+};
+
 // This corresponds to a .eh_frame section of an input file.
 template <class ELFT> class EhInputSection : public InputSectionBase<ELFT> {
 public:
   typedef typename ELFT::Shdr Elf_Shdr;
   typedef typename ELFT::uint uintX_t;
   EhInputSection(ObjectFile<ELFT> *F, const Elf_Shdr *Header);
   static bool classof(const InputSectionBase<ELFT> *S);
   void split();
+  template <class RelTy> void split(ArrayRef<RelTy> Rels);
 
   // Splittable sections are handled as a sequence of data
   // rather than a single large blob of data.
-  std::vector<SectionPiece> Pieces;
+  std::vector<EhSectionPiece> Pieces;
 
   // Relocation section that refer to this one.
   const Elf_Shdr *RelocSection = nullptr;
 };
 
 // This corresponds to a non SHF_MERGE section of an input file.
 template <class ELFT> class InputSection : public InputSectionBase<ELFT> {
   friend ICF<ELFT>;

ELF/InputSection.cpp

EhInputSection<ELFT>::EhInputSection(elf::ObjectFile<ELFT> *F,
   this->Live = true;
 }
 
 template <class ELFT>
 bool EhInputSection<ELFT>::classof(const InputSectionBase<ELFT> *S) {
   return S->SectionKind == InputSectionBase<ELFT>::EHFrame;
 }
 
+// Returns the index of the first relocation that points to a region between
+// Begin and Begin+Size.
+template <class IntTy, class RelTy>
+static unsigned getReloc(IntTy Begin, IntTy Size, const ArrayRef<RelTy> &Rels,
+                         unsigned &RelocI) {
+  // Start search from RelocI for fast access. That works because the
+  // relocations are sorted in .eh_frame.
+  for (unsigned N = Rels.size(); RelocI < N; ++RelocI) {
+    const RelTy &Rel = Rels[RelocI];
+    if (Rel.r_offset < Begin)
+      continue;
+
+    if (Rel.r_offset < Begin + Size)
+      return RelocI;
+    return -1;
+  }
+  return -1;
+}
+
 // .eh_frame is a sequence of CIE or FDE records.
 // This function splits an input section into records and returns them.
 template <class ELFT>
 void EhInputSection<ELFT>::split() {
+  // Early exit if already split.
+  if (!this->Pieces.empty())
+    return;
+
+  if (RelocSection) {
+    ELFFile<ELFT> &Obj = this->File->getObj();
+    if (RelocSection->sh_type == SHT_RELA)
+      split(Obj.relas(RelocSection));
+    else
+      split(Obj.rels(RelocSection));
+    return;
+  }
+  split(makeArrayRef<typename ELFT::Rela>(nullptr, nullptr));
+}
+
+template <class ELFT>
+template <class RelTy>
+void EhInputSection<ELFT>::split(ArrayRef<RelTy> Rels) {
   ArrayRef<uint8_t> Data = this->getSectionData();
+  unsigned RelI = 0;
   for (size_t Off = 0, End = Data.size(); Off != End;) {
     size_t Size = readEhRecordSize<ELFT>(Data.slice(Off));
-    this->Pieces.emplace_back(Off, Data.slice(Off, Size));
+    this->Pieces.emplace_back(Off, Data.slice(Off, Size),
+                              getReloc(Off, Size, Rels, RelI));
     // The empty record is the end marker.
     if (Size == 4)
       break;
     Off += Size;
   }
 }
 
 static size_t findNull(ArrayRef<uint8_t> A, size_t EntSize) {

ELF/MarkLive.cpp

 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Object/ELF.h"
 #include <functional>
 #include <vector>
 
 using namespace llvm;
 using namespace llvm::ELF;
 using namespace llvm::object;
+using namespace llvm::support::endian;
 
 using namespace lld;
 using namespace lld::elf;
 
 // A resolved relocation. The Sec and Offset fields are set if the relocation
 // was resolved to an offset within a section.
 template <class ELFT>
 struct ResolvedReloc {

 template <class ELFT>
 static void forEachSuccessor(InputSection<ELFT> &Sec,
                              std::function<void(ResolvedReloc<ELFT>)> Fn) {
   ELFFile<ELFT> &Obj = Sec.getFile()->getObj();
   for (const typename ELFT::Shdr *RelSec : Sec.RelocSections)
     run(Obj, Sec, RelSec, Fn);
 }
 
+// The .eh_frame section is an unfortunate special case.
+// The section is divided in CIEs and FDEs and the relocations it can have are
+// * CIEs can refer to a personality function.
+// * FDEs can refer to a LSDA
+// * FDEs refer to the function they contain information about
+// The last kind of relocation cannot keep the referred section alive, or they
+// would keep everything alive in a common object file. In fact, each FDE is
+// alive if the section it refers to is alive.
+// To keep things simple, in here we just ignore the last relocation kind. The
+// other two keep the referred section alive.
+//
+// A possible improvement would be to fully process .eh_frame in the middle of
+// the gc pass. With that we would be able to also gc some sections holding
+// LSDAs and personality functions if we found that they were unused.
+template <class ELFT, class RelTy>
+static void
+scanEhFrameSection(EhInputSection<ELFT> &EH, ArrayRef<RelTy> Rels,
+                   std::function<void(ResolvedReloc<ELFT>)> Enqueue) {
+  const endianness E = ELFT::TargetEndianness;
+  for (unsigned I = 0, N = EH.Pieces.size(); I < N; ++I) {
+    EhSectionPiece &Piece = EH.Pieces[I];
+    unsigned FirstRelI = Piece.FirstRelocation;
+    if (FirstRelI == (unsigned)-1)
+      continue;
+    if (read32<E>(Piece.data().data() + 4) == 0) {
+      // This is a CIE, we only need to worry about the first relocation. It is
+      // known to point to the personality function.
+      Enqueue(resolveReloc(EH, Rels[FirstRelI]));
+      continue;
+    }
+    // This is a FDE. The relocations point to the described function or to
+    // a LSDA. We only need to keep the LSDA alive, so ignore anything that
+    // points to executable sections.
+    typename ELFT::uint PieceEnd = Piece.InputOff + Piece.size();
+    for (unsigned I2 = FirstRelI, N2 = Rels.size(); I2 < N2; ++I2) {
+      const RelTy &Rel = Rels[I2];
+      if (Rel.r_offset >= PieceEnd)
+        break;
+      ResolvedReloc<ELFT> R = resolveReloc(EH, Rels[I2]);
+      if (!R.Sec || R.Sec == &InputSection<ELFT>::Discarded)
+        continue;
+      if (R.Sec->getSectionHdr()->sh_flags & SHF_EXECINSTR)
+        continue;
+      Enqueue({R.Sec, 0});
+    }
+  }
+}
+
 template <class ELFT>
-static void scanEhFrameSection(EhInputSection<ELFT> &EH,
-                               std::function<void(ResolvedReloc<ELFT>)> Fn) {
+static void
+scanEhFrameSection(EhInputSection<ELFT> &EH,
+                   std::function<void(ResolvedReloc<ELFT>)> Enqueue) {
   if (!EH.RelocSection)
     return;
+
+  // Unfortunately we need to split .eh_frame early since some relocations in
+  // .eh_frame keep other section alive and some don't.
+  EH.split();
+
   ELFFile<ELFT> &EObj = EH.getFile()->getObj();
-  run<ELFT>(EObj, EH, EH.RelocSection, [&](ResolvedReloc<ELFT> R) {
-    if (!R.Sec || R.Sec == &InputSection<ELFT>::Discarded)
-      return;
-    if (R.Sec->getSectionHdr()->sh_flags & SHF_EXECINSTR)
-      return;
-    Fn({R.Sec, 0});
-  });
+  if (EH.RelocSection->sh_type == SHT_RELA)
+    scanEhFrameSection(EH, EObj.relas(EH.RelocSection), Enqueue);
+  else
+    scanEhFrameSection(EH, EObj.rels(EH.RelocSection), Enqueue);
 }
 
 // Sections listed below are special because they are used by the loader
 // just by being in an ELF file. They should not be garbage-collected.
 template <class ELFT> static bool isReserved(InputSectionBase<ELFT> *Sec) {
   switch (Sec->getSectionHdr()->sh_type) {
   case SHT_FINI_ARRAY:
   case SHT_INIT_ARRAY:

ELF/OutputSections.h

 #include "llvm/Object/ELF.h"
 #include "llvm/Support/MD5.h"
 #include "llvm/Support/SHA1.h"
 
 namespace lld {
 namespace elf {
 
 class SymbolBody;
-struct SectionPiece;
+struct EhSectionPiece;
 template <class ELFT> class SymbolTable;
 template <class ELFT> class SymbolTableSection;
 template <class ELFT> class StringTableSection;
 template <class ELFT> class EhInputSection;
 template <class ELFT> class InputSection;
 template <class ELFT> class InputSectionBase;
 template <class ELFT> class MergeInputSection;
 template <class ELFT> class MipsReginfoInputSection;
public:
   bool shouldTailMerge() const;
 
 private:
   llvm::StringTableBuilder Builder;
   std::vector<MergeInputSection<ELFT> *> Sections;
 };
 
 struct CieRecord {
-  SectionPiece *Piece = nullptr;
-  std::vector<SectionPiece *> FdePieces;
+  EhSectionPiece *Piece = nullptr;
+  std::vector<EhSectionPiece *> FdePieces;
 };
 
 // Output section for .eh_frame.
 template <class ELFT>
 class EhOutputSection final : public OutputSectionBase<ELFT> {
   typedef typename ELFT::uint uintX_t;
   typedef typename ELFT::Shdr Elf_Shdr;
   typedef typename ELFT::Rel Elf_Rel;
public:
 
   size_t NumFdes = 0;
 
 private:
   template <class RelTy>
   void addSectionAux(EhInputSection<ELFT> *S, llvm::ArrayRef<RelTy> Rels);
 
   template <class RelTy>
-  CieRecord *addCie(SectionPiece &Piece, EhInputSection<ELFT> *Sec,
-                    ArrayRef<RelTy> &Rels);
+  CieRecord *addCie(EhSectionPiece &Piece, EhInputSection<ELFT> *Sec,
+                    ArrayRef<RelTy> Rels);
 
   template <class RelTy>
-  bool isFdeLive(SectionPiece &Piece, EhInputSection<ELFT> *Sec,
-                 ArrayRef<RelTy> &Rels);
+  bool isFdeLive(EhSectionPiece &Piece, EhInputSection<ELFT> *Sec,
+                 ArrayRef<RelTy> Rels);
 
   uintX_t getFdePc(uint8_t *Buf, size_t Off, uint8_t Enc);
 
   std::vector<EhInputSection<ELFT> *> Sections;
   std::vector<CieRecord *> Cies;
 
   // CIE records are uniquified by their contents and personality functions.
   llvm::DenseMap<std::pair<ArrayRef<uint8_t>, SymbolBody *>, CieRecord> CieMap;

ELF/OutputSections.cpp

for (InputSection<ELFT> *C : Sections)
       C->writeTo(Buf);
   }
 }
 
 template <class ELFT>
 EhOutputSection<ELFT>::EhOutputSection()
     : OutputSectionBase<ELFT>(".eh_frame", SHT_PROGBITS, SHF_ALLOC) {}
 
-// Returns the first relocation that points to a region
-// between Begin and Begin+Size.
-template <class IntTy, class RelTy>
-static const RelTy *getReloc(IntTy Begin, IntTy Size, ArrayRef<RelTy> &Rels) {
-  for (auto I = Rels.begin(), E = Rels.end(); I != E; ++I) {
-    if (I->r_offset < Begin)
-      continue;
-
-    // Truncate Rels for fast access. That means we expect that the
-    // relocations are sorted and we are looking up symbols in
-    // sequential order. It is naturally satisfied for .eh_frame.
-    Rels = Rels.slice(I - Rels.begin());
-    if (I->r_offset < Begin + Size)
-      return I;
-    return nullptr;
-  }
-  Rels = ArrayRef<RelTy>();
-  return nullptr;
-}
-
 // Search for an existing CIE record or create a new one.
 // CIE records from input object files are uniquified by their contents
 // and where their relocations point to.
 template <class ELFT>
 template <class RelTy>
-CieRecord *EhOutputSection<ELFT>::addCie(SectionPiece &Piece,
+CieRecord *EhOutputSection<ELFT>::addCie(EhSectionPiece &Piece,
                                          EhInputSection<ELFT> *Sec,
-                                         ArrayRef<RelTy> &Rels) {
+                                         ArrayRef<RelTy> Rels) {
   const endianness E = ELFT::TargetEndianness;
   if (read32<E>(Piece.data().data() + 4) != 0)
     fatal("CIE expected at beginning of .eh_frame: " + Sec->getSectionName());
 
   SymbolBody *Personality = nullptr;
-  if (const RelTy *Rel = getReloc(Piece.InputOff, Piece.size(), Rels))
-    Personality = &Sec->getFile()->getRelocTargetSym(*Rel);
+  unsigned FirstRelI = Piece.FirstRelocation;
+  if (FirstRelI != (unsigned)-1)
+    Personality = &Sec->getFile()->getRelocTargetSym(Rels[FirstRelI]);
 
   // Search for an existing CIE by CIE contents/relocation target pair.
   CieRecord *Cie = &CieMap[{Piece.data(), Personality}];
 
   // If not found, create a new one.
   if (Cie->Piece == nullptr) {
     Cie->Piece = &Piece;
     Cies.push_back(Cie);
   }
   return Cie;
 }
 
 // There is one FDE per function. Returns true if a given FDE
 // points to a live function.
 template <class ELFT>
 template <class RelTy>
-bool EhOutputSection<ELFT>::isFdeLive(SectionPiece &Piece,
+bool EhOutputSection<ELFT>::isFdeLive(EhSectionPiece &Piece,
                                       EhInputSection<ELFT> *Sec,
-                                      ArrayRef<RelTy> &Rels) {
-  const RelTy *Rel = getReloc(Piece.InputOff, Piece.size(), Rels);
-  if (!Rel)
+                                      ArrayRef<RelTy> Rels) {
+  unsigned FirstRelI = Piece.FirstRelocation;
+  if (FirstRelI == (unsigned)-1)
     fatal("FDE doesn't reference another section");
-  SymbolBody &B = Sec->getFile()->getRelocTargetSym(*Rel);
+  const RelTy &Rel = Rels[FirstRelI];
+  SymbolBody &B = Sec->getFile()->getRelocTargetSym(Rel);
   auto *D = dyn_cast<DefinedRegular<ELFT>>(&B);
   if (!D || !D->Section)
     return false;
   InputSectionBase<ELFT> *Target = D->Section->Repl;
   return Target && Target->Live;
 }
 
 // .eh_frame is a sequence of CIE or FDE records. In general, there
 // is one CIE record per input object file which is followed by
 // a list of FDEs. This function searches an existing CIE or create a new
 // one and associates FDEs to the CIE.
 template <class ELFT>
 template <class RelTy>
 void EhOutputSection<ELFT>::addSectionAux(EhInputSection<ELFT> *Sec,
                                           ArrayRef<RelTy> Rels) {
   const endianness E = ELFT::TargetEndianness;
 
   DenseMap<size_t, CieRecord *> OffsetToCie;
-  for (SectionPiece &Piece : Sec->Pieces) {
+  for (EhSectionPiece &Piece : Sec->Pieces) {
     // The empty record is the end marker.
     if (Piece.size() == 4)
       return;
 
     size_t Offset = Piece.InputOff;
     uint32_t ID = read32<E>(Piece.data().data() + 4);
     if (ID == 0) {
       OffsetToCie[Offset] = addCie(Piece, Sec, Rels);
       continue;
     }
 
     uint32_t CieOffset = Offset + 4 - ID;
     CieRecord *Cie = OffsetToCie[CieOffset];
     if (!Cie)
       fatal("invalid CIE reference");
 
     if (!isFdeLive(Piece, Sec, Rels))
       continue;
     Cie->FdePieces.push_back(&Piece);
     NumFdes++;
   }
 }
 
 template <class ELFT>
 void EhOutputSection<ELFT>::addSection(InputSectionBase<ELFT> *C) {

test/ELF/eh-frame-gc2.s

+// REQUIRES: x86
+// RUN: llvm-mc -filetype=obj -triple=i686-pc-linux %s -o %t.o
+// RUN: ld.lld --gc-sections %t.o -o %t
+// RUN: llvm-readobj -s %t | FileCheck %s
+
+// Test that the we don't gc the personality function.
+// CHECK: Name: .foobar
+
+  .globl  _start
+_start:
+  .cfi_startproc
+  .cfi_personality 3, foobar
+  .cfi_endproc
+        .section .foobar,"ax"
+foobar: