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 &Fde, 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" @@ -200,6 +201,29 @@ 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 &Fde, ArrayRef Rels) { + auto *Sec = cast(Fde.Sec); + unsigned FirstRelI = Fde.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); + if (auto *D = dyn_cast(&B)) + if (D->Section) + return cast(D->Section)->Repl->Live; + return false; +} + 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); @@ -209,3 +233,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 &Fde, + ArrayRef Rels); +template bool elf::isFdeLive(EhSectionPiece &Fde, + ArrayRef Rels); +template bool elf::isFdeLive(EhSectionPiece &Fde, + ArrayRef Rels); +template bool elf::isFdeLive(EhSectionPiece &Fde, + ArrayRef Rels); +template bool elf::isFdeLive(EhSectionPiece &Fde, + ArrayRef Rels); +template bool elf::isFdeLive(EhSectionPiece &Fde, + ArrayRef Rels); +template bool elf::isFdeLive(EhSectionPiece &Fde, + ArrayRef Rels); +template bool elf::isFdeLive(EhSectionPiece &Fde, + ArrayRef Rels); Index: ELF/InputSection.h =================================================================== --- ELF/InputSection.h +++ ELF/InputSection.h @@ -264,14 +264,16 @@ struct EhSectionPiece { EhSectionPiece(size_t Off, InputSectionBase *Sec, uint32_t Size, unsigned FirstRelocation) - : InputOff(Off), Sec(Sec), Size(Size), FirstRelocation(FirstRelocation) {} + : InputOff(Off), Sec(Sec), Size(Size), Live(!Config->GcSections), + FirstRelocation(FirstRelocation) {} ArrayRef data() { return {Sec->Data.data() + this->InputOff, Size}; } size_t InputOff; ssize_t OutputOff = -1; InputSectionBase *Sec; - uint32_t Size; + uint32_t Size : 31; + uint32_t Live : 1; unsigned FirstRelocation; }; 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,109 @@ 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; + + 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 It = std::lower_bound(Cies.begin(), Cies.end(), CieOffset, + [](EhSectionPiece *Cie, uint32_t Offset) { + return Cie->InputOff < Offset; + }); + if (It != Cies.end() && (*It)->InputOff == CieOffset) + return *It; + + return nullptr; +} + +template +static void scanFde(EhInputSection &EH, ArrayRef Rels, + std::function Fn, + const EhSectionPiece &Fde) { + uint64_t 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 && Rels[I].r_offset < FdeEnd; ++I) + // In a FDE, the relocations point to the described function or to a LSDA. + // The described function is already marked and calling Fn for it is safe. + // Although the main intent here is to mark LSDAs, we do not need to + // recognize them especially and can process all references the same way. + resolveReloc(EH, Rels[I], Fn); +} + +template +static void scanCie(EhInputSection &EH, ArrayRef Rels, + std::function Fn, + const EhSectionPiece &Cie) { + if (Cie.FirstRelocation == (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[Cie.FirstRelocation], 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; + + 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 (Piece.Live // This FDE is already fully processed. + || !elf::isFdeLive(Piece, Rels)) + continue; + // This FDE should be kept. + Piece.Live = true; + + scanFde(EH, Rels, Fn, Piece); + + // Find the corresponding CIE + EhSectionPiece *Cie = Cies.get(Piece, ID); + if (!Cie) + fatal(toString(&EH) + ": invalid CIE reference"); + + if (Cie->Live) // Already processed. + continue; + Cie->Live = true; + + scanCie(EH, Rels, Fn, *Cie); } } @@ -195,6 +263,10 @@ SmallVector Q; CNamedSections.clear(); + // The flag is set if an executable section is added to the queue. + // We scan .eh_frame sections only if the flag is set. + bool ExecInQueue = false; + auto Enqueue = [&](InputSectionBase *Sec, uint64_t Offset) { // Skip over discarded sections. This in theory shouldn't happen, because // the ELF spec doesn't allow a relocation to point to a deduplicated @@ -218,8 +290,11 @@ Sec->Live = true; // Add input section to the queue. - if (InputSection *S = dyn_cast(Sec)) + if (InputSection *S = dyn_cast(Sec)) { Q.push_back(S); + if (S->Flags & SHF_EXECINSTR) + ExecInQueue = true; + } }; auto MarkSymbol = [&](SymbolBody *Sym) { @@ -247,14 +322,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 +342,23 @@ } // Mark all reachable sections. - while (!Q.empty()) - forEachSuccessor(*Q.pop_back_val(), Enqueue); + // It should take only one or two iterations to converge. + // If the output does not use exception handling, scanning .eh_frame sections + // will not add new sections to the queue and the loop will stop. + // Otherwise, sections for LSDAs and a personality function will be added. + // The personality function might be located in a DSO or in a library. + // In the latter case, it might require an additional iteration because + // it may introduce new dependencies, which, in turn, will require + // an additional scan of .eh_frame sections. + while (true) { + while (!Q.empty()) + forEachSuccessor(*Q.pop_back_val(), Enqueue); + if (!ExecInQueue) + break; + ExecInQueue = false; + for (EhInputSection *EH : EhInputSections) + scanEhFrameSection(*EH, Enqueue); + } } template void elf::markLive(); Index: ELF/SyntheticSections.h =================================================================== --- ELF/SyntheticSections.h +++ ELF/SyntheticSections.h @@ -93,9 +93,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 CieRecords; 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" @@ -428,31 +429,6 @@ return Rec; } -// There is one FDE per function. Returns true if a given FDE -// points to a live function. -template -template -bool EhFrameSection::isFdeLive(EhSectionPiece &Fde, - ArrayRef Rels) { - auto *Sec = cast(Fde.Sec); - unsigned FirstRelI = Fde.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); - if (auto *D = dyn_cast(&B)) - if (D->Section) - return cast(D->Section)->Repl->Live; - return false; -} - // .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 @@ -469,6 +445,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) { @@ -481,7 +460,7 @@ if (!Rec) fatal(toString(Sec) + ": invalid CIE reference"); - if (!isFdeLive(Piece, Rels)) + if (!Config->GcSections && !elf::isFdeLive(Piece, Rels)) continue; Rec->Fdes.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: