Index: ELF/EhFrame.h =================================================================== --- ELF/EhFrame.h +++ ELF/EhFrame.h @@ -19,6 +19,8 @@ template size_t readEhRecordSize(InputSectionBase *S, size_t Off); template uint8_t getFdeEncoding(EhSectionPiece *P); +template +bool isFdeLive(EhSectionPiece &P, ArrayRef Rels); } // namespace elf } // namespace lld Index: ELF/EhFrame.cpp =================================================================== --- ELF/EhFrame.cpp +++ ELF/EhFrame.cpp @@ -18,6 +18,7 @@ #include "EhFrame.h" #include "Error.h" +#include "InputFiles.h" #include "InputSection.h" #include "Relocations.h" #include "Strings.h" @@ -201,6 +202,31 @@ return DW_EH_PE_absptr; } +// There is one FDE per function. Returns true if a given FDE +// points to a live function. +template +bool elf::isFdeLive(EhSectionPiece &Piece, ArrayRef Rels) { + auto *Sec = cast(Piece.ID); + unsigned FirstRelI = Piece.FirstRelocation; + + // An FDE should point to some function because FDEs are to describe + // functions. That's however not always the case due to an issue of + // ld.gold with -r. ld.gold may discard only functions and leave their + // corresponding FDEs, which results in creating bad .eh_frame sections. + // To deal with that, we ignore such FDEs. + if (FirstRelI == (unsigned)-1) + return false; + + const RelTy &Rel = Rels[FirstRelI]; + SymbolBody &B = Sec->template getFile()->getRelocTargetSym(Rel); + auto *D = dyn_cast(&B); + if (!D || !D->Section) + return false; + auto *Target = + cast(cast(D->Section)->Repl); + return Target && Target->Live; +} + template size_t elf::readEhRecordSize(InputSectionBase *S, size_t Off); template size_t elf::readEhRecordSize(InputSectionBase *S, size_t Off); template size_t elf::readEhRecordSize(InputSectionBase *S, size_t Off); @@ -210,3 +236,20 @@ template uint8_t elf::getFdeEncoding(EhSectionPiece *P); template uint8_t elf::getFdeEncoding(EhSectionPiece *P); template uint8_t elf::getFdeEncoding(EhSectionPiece *P); + +template bool elf::isFdeLive(EhSectionPiece &Piece, + ArrayRef Rels); +template bool elf::isFdeLive(EhSectionPiece &Piece, + ArrayRef Rels); +template bool elf::isFdeLive(EhSectionPiece &Piece, + ArrayRef Rels); +template bool elf::isFdeLive(EhSectionPiece &Piece, + ArrayRef Rels); +template bool elf::isFdeLive(EhSectionPiece &Piece, + ArrayRef Rels); +template bool elf::isFdeLive(EhSectionPiece &Piece, + ArrayRef Rels); +template bool elf::isFdeLive(EhSectionPiece &Piece, + ArrayRef Rels); +template bool elf::isFdeLive(EhSectionPiece &Piece, + ArrayRef Rels); Index: ELF/MarkLive.cpp =================================================================== --- ELF/MarkLive.cpp +++ ELF/MarkLive.cpp @@ -20,6 +20,7 @@ // //===----------------------------------------------------------------------===// +#include "EhFrame.h" #include "InputSection.h" #include "LinkerScript.h" #include "Memory.h" @@ -42,6 +43,16 @@ using namespace lld; using namespace lld::elf; +namespace { +class EhFrameSectionCies { + std::vector Cies; + +public: + void add(EhSectionPiece *Cie); + EhSectionPiece *get(const EhSectionPiece &Fde, uint32_t ID) const; +}; +} + template static typename ELFT::uint getAddend(InputSectionBase &Sec, const typename ELFT::Rel &Rel) { @@ -101,52 +112,120 @@ Fn(IS, 0); } +void EhFrameSectionCies::add(EhSectionPiece *Cie) { + assert(Cies.empty() || Cies.back()->InputOff < Cie->InputOff); + Cies.push_back(Cie); +} + +EhSectionPiece *EhFrameSectionCies::get(const EhSectionPiece &Fde, + uint32_t ID) const { + if (Cies.empty()) + return nullptr; + + const uint32_t CieOffset = Fde.InputOff + 4 - ID; + + // In most cases, a FDE refers to the most recent CIE. + if (Cies.back()->InputOff == CieOffset) + return Cies.back(); + + auto Found = std::lower_bound(Cies.begin(), Cies.end(), CieOffset, + [](EhSectionPiece *Cie, uint32_t Offset) { + return Cie->InputOff < Offset; + }); + if (Found != Cies.end() && (*Found)->InputOff == CieOffset) + return *Found; + + return nullptr; +} + +template +static bool processFde(EhInputSection &EH, ArrayRef Rels, + std::function Fn, + EhSectionPiece &Fde) { + if (Fde.Live // This FDE is already fully processed. + || !elf::isFdeLive(Fde, Rels)) + return false; + + // This FDE should be kept. + Fde.Live = true; + + // In 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. + const typename ELFT::uint FdeEnd = Fde.InputOff + Fde.size(); + // The first relocation is known to point to the described function, + // so it is safe to skip it when looking for LSDAs. + for (unsigned I = Fde.FirstRelocation + 1, N = Rels.size(); I < N; ++I) { + const RelTy &Rel = Rels[I]; + if (Rel.r_offset >= FdeEnd) + break; + resolveReloc(EH, Rel, [&](InputSectionBase *Sec, uint64_t) { + if (Sec && Sec != &InputSection::Discarded && + !(Sec->Flags & SHF_EXECINSTR)) + Fn(Sec, 0); + }); + } + return true; +} + +template +static void processCie(EhInputSection &EH, ArrayRef Rels, + std::function Fn, + EhSectionPiece &Cie) { + if (Cie.Live) // Already processed. + return; + + Cie.Live = true; + + const unsigned CieFirstRelI = Cie.FirstRelocation; + if (CieFirstRelI == (unsigned)-1) + return; + + // In a CIE, we only need to worry about the first relocation. + // It is known to point to the personality function. + resolveReloc(EH, Rels[CieFirstRelI], 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 +// The section is divided in CIEs (Common Information Entries) and FDEs +// (Frame Description Entries). Each FDE references to a corresponding +// CIE via ID field, where a relative offset is stored. +// The relocations the section 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. +// * FDEs can refer to a LSDA. +// * FDEs refer to the function they contain information about. +// The last kind of relocation is used to keep a FDE alive if the section +// it refers to is alive. In that case, everything which is referenced from +// that FDE should be marked, including a LSDA, a CIE and a personality +// function. These sections might reference to other sections, so they +// are added to the GC queue. template static void scanEhFrameSection(EhInputSection &EH, ArrayRef Rels, std::function Fn) { 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(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. - resolveReloc(EH, Rels[FirstRelI], Fn); + EhFrameSectionCies Cies; + for (EhSectionPiece &Piece : EH.Pieces) { + // The empty record is the end marker. + if (Piece.size() == 4) + return; + + const uint32_t ID = read32(Piece.data().data() + 4); + if (ID == 0) { + Cies.add(&Piece); 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; - resolveReloc(EH, Rels[I2], - [&](InputSectionBase *Sec, uint64_t Offset) { - if (Sec && Sec != &InputSection::Discarded && - !(Sec->Flags & SHF_EXECINSTR)) - Fn(Sec, 0); - }); - } + + if (!processFde(EH, Rels, Fn, Piece)) + continue; + + // Find the corresponding CIE + EhSectionPiece *Cie = Cies.get(Piece, ID); + if (!Cie) + fatal(toString(&EH) + ": invalid CIE reference"); + + processCie(EH, Rels, Fn, *Cie); } } @@ -247,14 +326,15 @@ if (S->includeInDynsym()) MarkSymbol(S->body()); + std::vector EhInputSections; + // Preserve special sections and those which are specified in linker // script KEEP command. for (InputSectionBase *Sec : InputSections) { - // .eh_frame is always marked as live now, but also it can reference to - // sections that contain personality. We preserve all non-text sections - // referred by .eh_frame here. + // Postpone scanning .eh_frame until we find all the secions reachable + // from the roots. if (auto *EH = dyn_cast_or_null(Sec)) - scanEhFrameSection(*EH, Enqueue); + EhInputSections.push_back(EH); if (Sec->Flags & SHF_LINK_ORDER) continue; if (isReserved(Sec) || Script->shouldKeep(Sec)) @@ -266,8 +346,12 @@ } // Mark all reachable sections. - while (!Q.empty()) - forEachSuccessor(*Q.pop_back_val(), Enqueue); + while (!Q.empty()) { + while (!Q.empty()) + forEachSuccessor(*Q.pop_back_val(), Enqueue); + for (EhInputSection *EH : EhInputSections) + scanEhFrameSection(*EH, Enqueue); + } } template void elf::markLive(); Index: ELF/SyntheticSections.h =================================================================== --- ELF/SyntheticSections.h +++ ELF/SyntheticSections.h @@ -95,9 +95,6 @@ template CieRecord *addCie(EhSectionPiece &Piece, ArrayRef Rels); - template - bool isFdeLive(EhSectionPiece &Piece, ArrayRef Rels); - uint64_t getFdePc(uint8_t *Buf, size_t Off, uint8_t Enc); std::vector Cies; Index: ELF/SyntheticSections.cpp =================================================================== --- ELF/SyntheticSections.cpp +++ ELF/SyntheticSections.cpp @@ -16,6 +16,7 @@ #include "SyntheticSections.h" #include "Config.h" +#include "EhFrame.h" #include "Error.h" #include "InputFiles.h" #include "LinkerScript.h" @@ -427,33 +428,6 @@ return Cie; } -// There is one FDE per function. Returns true if a given FDE -// points to a live function. -template -template -bool EhFrameSection::isFdeLive(EhSectionPiece &Piece, - ArrayRef Rels) { - auto *Sec = cast(Piece.ID); - unsigned FirstRelI = Piece.FirstRelocation; - - // An FDE should point to some function because FDEs are to describe - // functions. That's however not always the case due to an issue of - // ld.gold with -r. ld.gold may discard only functions and leave their - // corresponding FDEs, which results in creating bad .eh_frame sections. - // To deal with that, we ignore such FDEs. - if (FirstRelI == (unsigned)-1) - return false; - - const RelTy &Rel = Rels[FirstRelI]; - SymbolBody &B = Sec->template getFile()->getRelocTargetSym(Rel); - auto *D = dyn_cast(&B); - if (!D || !D->Section) - return false; - auto *Target = - cast(cast(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 @@ -470,6 +444,9 @@ if (Piece.size() == 4) return; + if (!Piece.Live) + continue; + size_t Offset = Piece.InputOff; uint32_t ID = read32(Piece.data().data() + 4); if (ID == 0) { @@ -482,7 +459,7 @@ if (!Cie) fatal(toString(Sec) + ": invalid CIE reference"); - if (!isFdeLive(Piece, Rels)) + if (!Config->GcSections && !elf::isFdeLive(Piece, Rels)) continue; Cie->FdePieces.push_back(&Piece); NumFdes++; Index: test/ELF/eh-frame-gc3.s =================================================================== --- /dev/null +++ test/ELF/eh-frame-gc3.s @@ -0,0 +1,34 @@ +// REQUIRES: x86 +// RUN: llvm-mc -filetype=obj -triple=i686-pc-linux %s -o %t.o +// RUN: ld.lld %t.o --gc-sections -o %tout +// RUN: llvm-nm %tout | FileCheck %s + +// CHECK: _start +// CHECK-NOT: foo +// CHECK-NOT: lsda +// CHECK-NOT: personality + + .global _start, foo, lsda, personality + .text +_start: + .cfi_startproc + nop + .cfi_endproc + + .section ".text.foo","ax" +foo: + .cfi_startproc + .cfi_personality 0, personality + .cfi_lsda 0, .Lexception0 + nop + .cfi_endproc + + .section ".lsda","a" + .p2align 2 +.Lexception0: +lsda: + .byte 0 + + .section ".text.personality","ax" +personality: + nop Index: test/ELF/gc-sections-lsda.s =================================================================== --- test/ELF/gc-sections-lsda.s +++ test/ELF/gc-sections-lsda.s @@ -8,9 +8,14 @@ // we are consistent: if we keep .abc, we have to keep .foo // RUN: llvm-readobj -s %t | FileCheck %s -// CHECK: Name: .abc -// CHECK: Name: .foo +// CHECK: Name: .abc +// CHECK-NOT: Name: .abc2 +// CHECK: Name: .foo +// CHECK-NOT: Name: .foo2 + .section .text.func,"ax" + .global func +func: .cfi_startproc .cfi_lsda 0x1b,zed .cfi_endproc @@ -19,3 +24,16 @@ .long bar-. .section .foo,"ax" bar: + +// This section is similar to .text.func except that the symbol is local +// and should be eliminated as such with all dependent sections. + .section .text.func2,"ax" +func2: + .cfi_startproc + .cfi_lsda 0x1b,zed2 + .cfi_endproc + .section .abc2,"a" +zed2: + .long bar2-. + .section .foo2,"ax" +bar2: