| //===- 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 "SyntheticSections.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: | |
| MarkLive(unsigned partition) : partition(partition) {} | |
| void run(); | |
| void moveToMain(); | |
| private: | |
| void enqueue(InputSectionBase *sec, uint64_t offset); | |
| void markSymbol(Symbol *sym); | |
| void mark(); | |
| template <class RelTy> | |
| void resolveReloc(InputSectionBase &sec, RelTy &rel, bool isLSDA); | |
| template <class RelTy> | |
| void scanEhFrameSection(EhInputSection &eh, ArrayRef<RelTy> rels); | |
| // The index of the partition that we are currently processing. | |
| unsigned partition; | |
| // 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; | |
| // Set Sec->Partition to the meet (i.e. the "minimum") of Partition and | |
| // Sec->Partition in the following lattice: 1 < other < 0. If Sec->Partition | |
| // doesn't change, we don't need to do anything. | |
| if (sec->partition == 1 || sec->partition == partition) | |
| return; | |
| sec->partition = sec->partition ? 1 : partition; | |
| // 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 *isec = dyn_cast_or_null<InputSectionBase>(d->section)) | |
| enqueue(isec, 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. | |
| // Preserve externally-visible symbols if the symbols defined by this | |
| // file can interrupt other ELF file's symbols at runtime. | |
| symtab->forEachSymbol([&](Symbol *sym) { | |
| if (sym->includeInDynsym() && sym->partition == partition) | |
| markSymbol(sym); | |
| }); | |
| // If this isn't the main partition, that's all that we need to preserve. | |
| if (partition != 1) { | |
| mark(); | |
| return; | |
| } | |
| 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 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->markLive(); | |
| 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(); | |
| } | |
| template <class ELFT> void MarkLive<ELFT>::mark() { | |
| // 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 *isec : sec.dependentSections) | |
| enqueue(isec, 0); | |
| } | |
| } | |
| // Move the sections for some symbols to the main partition, specifically ifuncs | |
| // (because they can result in an IRELATIVE being added to the main partition's | |
| // GOT, which means that the ifunc must be available when the main partition is | |
| // loaded) and TLS symbols (because we only know how to correctly process TLS | |
| // relocations for the main partition). | |
| template <class ELFT> void MarkLive<ELFT>::moveToMain() { | |
| for (InputFile *file : objectFiles) | |
| for (Symbol *s : file->getSymbols()) | |
| if (auto *d = dyn_cast<Defined>(s)) | |
| if ((d->type == STT_GNU_IFUNC || d->type == STT_TLS) && d->section && | |
| d->section->isLive()) | |
| markSymbol(s); | |
| mark(); | |
| } | |
| // 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->markLive(); | |
| // If a DSO defines a symbol referenced in a regular object, it is needed. | |
| symtab->forEachSymbol([](Symbol *sym) { | |
| 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->markLive(); | |
| } | |
| // Follow the graph to mark all live sections. | |
| for (unsigned curPart = 1; curPart <= partitions.size(); ++curPart) | |
| MarkLive<ELFT>(curPart).run(); | |
| // If we have multiple partitions, some sections need to live in the main | |
| // partition even if they were allocated to a loadable partition. Move them | |
| // there now. | |
| if (partitions.size() != 1) | |
| MarkLive<ELFT>(1).moveToMain(); | |
| // Report garbage-collected sections. | |
| if (config->printGcSections) | |
| for (InputSectionBase *sec : inputSections) | |
| if (!sec->isLive()) | |
| 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>(); |