| //===- MarkLive.cpp -------------------------------------------------------===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // This file implements --gc-sections, which is a feature to remove unused |
| // sections from output. Unused sections are sections that are not reachable |
| // from known GC-root symbols or sections. Naturally the feature is |
| // implemented as a mark-sweep garbage collector. |
| // |
| // Here's how it works. Each InputSectionBase has a "Live" bit. The bit is off |
| // by default. Starting with GC-root symbols or sections, markLive function |
| // defined in this file visits all reachable sections to set their Live |
| // bits. Writer will then ignore sections whose Live bits are off, so that |
| // such sections are not included into output. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "MarkLive.h" |
| #include "InputSection.h" |
| #include "LinkerScript.h" |
| #include "OutputSections.h" |
| #include "SymbolTable.h" |
| #include "Symbols.h" |
| #include "Target.h" |
| #include "lld/Common/Memory.h" |
| #include "lld/Common/Strings.h" |
| #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; |
| |
| namespace { |
| template <class ELFT> class MarkLive { |
| public: |
| void run(); |
| |
| private: |
| void enqueue(InputSectionBase *Sec, uint64_t Offset); |
| void markSymbol(Symbol *Sym); |
| |
| template <class RelTy> |
| void resolveReloc(InputSectionBase &Sec, RelTy &Rel, bool IsLSDA); |
| |
| template <class RelTy> |
| void scanEhFrameSection(EhInputSection &EH, ArrayRef<RelTy> Rels); |
| |
| // A list of sections to visit. |
| SmallVector<InputSection *, 256> Queue; |
| |
| // There are normally few input sections whose names are valid C |
| // identifiers, so we just store a std::vector instead of a multimap. |
| DenseMap<StringRef, std::vector<InputSectionBase *>> CNamedSections; |
| }; |
| } // namespace |
| |
| template <class ELFT> |
| static uint64_t getAddend(InputSectionBase &Sec, |
| const typename ELFT::Rel &Rel) { |
| return Target->getImplicitAddend(Sec.data().begin() + Rel.r_offset, |
| Rel.getType(Config->IsMips64EL)); |
| } |
| |
| template <class ELFT> |
| static uint64_t getAddend(InputSectionBase &Sec, |
| const typename ELFT::Rela &Rel) { |
| return Rel.r_addend; |
| } |
| |
| template <class ELFT> |
| template <class RelTy> |
| void MarkLive<ELFT>::resolveReloc(InputSectionBase &Sec, RelTy &Rel, |
| bool IsLSDA) { |
| Symbol &Sym = Sec.getFile<ELFT>()->getRelocTargetSym(Rel); |
| |
| // If a symbol is referenced in a live section, it is used. |
| Sym.Used = true; |
| |
| if (auto *D = dyn_cast<Defined>(&Sym)) { |
| auto *RelSec = dyn_cast_or_null<InputSectionBase>(D->Section); |
| if (!RelSec) |
| return; |
| |
| uint64_t Offset = D->Value; |
| if (D->isSection()) |
| Offset += getAddend<ELFT>(Sec, Rel); |
| |
| if (!IsLSDA || !(RelSec->Flags & SHF_EXECINSTR)) |
| enqueue(RelSec, Offset); |
| return; |
| } |
| |
| if (auto *SS = dyn_cast<SharedSymbol>(&Sym)) |
| if (!SS->isWeak()) |
| SS->getFile().IsNeeded = true; |
| |
| for (InputSectionBase *Sec : CNamedSections.lookup(Sym.getName())) |
| enqueue(Sec, 0); |
| } |
| |
| // 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> |
| template <class RelTy> |
| void MarkLive<ELFT>::scanEhFrameSection(EhInputSection &EH, |
| ArrayRef<RelTy> Rels) { |
| for (size_t I = 0, End = EH.Pieces.size(); I < End; ++I) { |
| EhSectionPiece &Piece = EH.Pieces[I]; |
| size_t FirstRelI = Piece.FirstRelocation; |
| if (FirstRelI == (unsigned)-1) |
| continue; |
| |
| if (read32<ELFT::TargetEndianness>(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], false); |
| 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. |
| uint64_t PieceEnd = Piece.InputOff + Piece.Size; |
| for (size_t J = FirstRelI, End2 = Rels.size(); J < End2; ++J) |
| if (Rels[J].r_offset < PieceEnd) |
| resolveReloc(EH, Rels[J], true); |
| } |
| } |
| |
| // Some sections are used directly by the loader, so they should never be |
| // garbage-collected. This function returns true if a given section is such |
| // section. |
| static bool isReserved(InputSectionBase *Sec) { |
| switch (Sec->Type) { |
| case SHT_FINI_ARRAY: |
| case SHT_INIT_ARRAY: |
| case SHT_NOTE: |
| case SHT_PREINIT_ARRAY: |
| return true; |
| default: |
| StringRef S = Sec->Name; |
| return S.startswith(".ctors") || S.startswith(".dtors") || |
| S.startswith(".init") || S.startswith(".fini") || |
| S.startswith(".jcr"); |
| } |
| } |
| |
| template <class ELFT> |
| void MarkLive<ELFT>::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 |
| // COMDAT section directly. Unfortunately this happens in practice (e.g. |
| // .eh_frame) so we need to add a check. |
| if (Sec == &InputSection::Discarded) |
| return; |
| |
| // Usually, a whole section is marked as live or dead, but in mergeable |
| // (splittable) sections, each piece of data has independent liveness bit. |
| // So we explicitly tell it which offset is in use. |
| if (auto *MS = dyn_cast<MergeInputSection>(Sec)) |
| MS->getSectionPiece(Offset)->Live = true; |
| |
| if (Sec->Live) |
| return; |
| Sec->Live = true; |
| |
| // Add input section to the queue. |
| if (InputSection *S = dyn_cast<InputSection>(Sec)) |
| Queue.push_back(S); |
| } |
| |
| template <class ELFT> void MarkLive<ELFT>::markSymbol(Symbol *Sym) { |
| if (auto *D = dyn_cast_or_null<Defined>(Sym)) |
| if (auto *IS = dyn_cast_or_null<InputSectionBase>(D->Section)) |
| enqueue(IS, D->Value); |
| } |
| |
| // This is the main function of the garbage collector. |
| // Starting from GC-root sections, this function visits all reachable |
| // sections to set their "Live" bits. |
| template <class ELFT> void MarkLive<ELFT>::run() { |
| // Add GC root symbols. |
| markSymbol(Symtab->find(Config->Entry)); |
| markSymbol(Symtab->find(Config->Init)); |
| markSymbol(Symtab->find(Config->Fini)); |
| for (StringRef S : Config->Undefined) |
| markSymbol(Symtab->find(S)); |
| for (StringRef S : Script->ReferencedSymbols) |
| markSymbol(Symtab->find(S)); |
| |
| // Preserve externally-visible symbols if the symbols defined by this |
| // file can interrupt other ELF file's symbols at runtime. |
| for (Symbol *S : Symtab->getSymbols()) |
| if (S->includeInDynsym()) |
| markSymbol(S); |
| |
| // Preserve special sections and those which are specified in linker |
| // script KEEP command. |
| for (InputSectionBase *Sec : InputSections) { |
| // Mark .eh_frame sections as live because there are usually no relocations |
| // that point to .eh_frames. Otherwise, the garbage collector would drop |
| // all of them. We also want to preserve personality routines and LSDA |
| // referenced by .eh_frame sections, so we scan them for that here. |
| if (auto *EH = dyn_cast<EhInputSection>(Sec)) { |
| EH->Live = true; |
| if (!EH->NumRelocations) |
| continue; |
| |
| if (EH->AreRelocsRela) |
| scanEhFrameSection(*EH, EH->template relas<ELFT>()); |
| else |
| scanEhFrameSection(*EH, EH->template rels<ELFT>()); |
| } |
| |
| if (Sec->Flags & SHF_LINK_ORDER) |
| continue; |
| |
| if (isReserved(Sec) || Script->shouldKeep(Sec)) { |
| enqueue(Sec, 0); |
| } else if (isValidCIdentifier(Sec->Name)) { |
| CNamedSections[Saver.save("__start_" + Sec->Name)].push_back(Sec); |
| CNamedSections[Saver.save("__stop_" + Sec->Name)].push_back(Sec); |
| } |
| } |
| |
| // Mark all reachable sections. |
| while (!Queue.empty()) { |
| InputSectionBase &Sec = *Queue.pop_back_val(); |
| |
| if (Sec.AreRelocsRela) { |
| for (const typename ELFT::Rela &Rel : Sec.template relas<ELFT>()) |
| resolveReloc(Sec, Rel, false); |
| } else { |
| for (const typename ELFT::Rel &Rel : Sec.template rels<ELFT>()) |
| resolveReloc(Sec, Rel, false); |
| } |
| |
| for (InputSectionBase *IS : Sec.DependentSections) |
| enqueue(IS, 0); |
| } |
| } |
| |
| // Before calling this function, Live bits are off for all |
| // input sections. This function make some or all of them on |
| // so that they are emitted to the output file. |
| template <class ELFT> void elf::markLive() { |
| // If -gc-sections is not given, no sections are removed. |
| if (!Config->GcSections) { |
| for (InputSectionBase *Sec : InputSections) |
| Sec->Live = true; |
| |
| // If a DSO defines a symbol referenced in a regular object, it is needed. |
| for (Symbol *Sym : Symtab->getSymbols()) |
| if (auto *S = dyn_cast<SharedSymbol>(Sym)) |
| if (S->IsUsedInRegularObj && !S->isWeak()) |
| S->getFile().IsNeeded = true; |
| return; |
| } |
| |
| // Otheriwse, do mark-sweep GC. |
| // |
| // The -gc-sections option works only for SHF_ALLOC sections |
| // (sections that are memory-mapped at runtime). So we can |
| // unconditionally make non-SHF_ALLOC sections alive except |
| // SHF_LINK_ORDER and SHT_REL/SHT_RELA sections. |
| // |
| // Usually, non-SHF_ALLOC sections are not removed even if they are |
| // unreachable through relocations because reachability is not |
| // a good signal whether they are garbage or not (e.g. there is |
| // usually no section referring to a .comment section, but we |
| // want to keep it.). |
| // |
| // Note on SHF_LINK_ORDER: Such sections contain metadata and they |
| // have a reverse dependency on the InputSection they are linked with. |
| // We are able to garbage collect them. |
| // |
| // Note on SHF_REL{,A}: Such sections reach here only when -r |
| // or -emit-reloc were given. And they are subject of garbage |
| // collection because, if we remove a text section, we also |
| // remove its relocation section. |
| for (InputSectionBase *Sec : InputSections) { |
| bool IsAlloc = (Sec->Flags & SHF_ALLOC); |
| bool IsLinkOrder = (Sec->Flags & SHF_LINK_ORDER); |
| bool IsRel = (Sec->Type == SHT_REL || Sec->Type == SHT_RELA); |
| |
| if (!IsAlloc && !IsLinkOrder && !IsRel) |
| Sec->Live = true; |
| } |
| |
| // Follow the graph to mark all live sections. |
| MarkLive<ELFT>().run(); |
| |
| // Report garbage-collected sections. |
| if (Config->PrintGcSections) |
| for (InputSectionBase *Sec : InputSections) |
| if (!Sec->Live) |
| message("removing unused section " + toString(Sec)); |
| } |
| |
| template void elf::markLive<ELF32LE>(); |
| template void elf::markLive<ELF32BE>(); |
| template void elf::markLive<ELF64LE>(); |
| template void elf::markLive<ELF64BE>(); |