557 lines · cpp
1//===- MarkLive.cpp -------------------------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements --gc-sections, which is a feature to remove unused10// sections from output. Unused sections are sections that are not reachable11// from known GC-root symbols or sections. Naturally the feature is12// implemented as a mark-sweep garbage collector.13//14// Here's how it works. Each InputSectionBase has a "Live" bit. The bit is off15// by default. Starting with GC-root symbols or sections, markLive function16// defined in this file visits all reachable sections to set their Live17// bits. Writer will then ignore sections whose Live bits are off, so that18// such sections are not included into output.19//20//===----------------------------------------------------------------------===//21 22#include "MarkLive.h"23#include "InputFiles.h"24#include "InputSection.h"25#include "LinkerScript.h"26#include "SymbolTable.h"27#include "Symbols.h"28#include "SyntheticSections.h"29#include "Target.h"30#include "lld/Common/Strings.h"31#include "llvm/ADT/DenseMapInfoVariant.h"32#include "llvm/ADT/STLExtras.h"33#include "llvm/Support/TimeProfiler.h"34#include <variant>35#include <vector>36 37using namespace llvm;38using namespace llvm::ELF;39using namespace llvm::object;40using namespace llvm::support::endian;41using namespace lld;42using namespace lld::elf;43 44namespace {45using SecOffset = std::pair<InputSectionBase *, unsigned>;46 47// Something that can have an independent reason for being live.48using LiveItem = std::variant<InputSectionBase *, Symbol *, SecOffset>;49 50// The most proximate reason that something is live.51struct LiveReason {52 std::optional<LiveItem> item;53 StringRef desc;54};55 56template <class ELFT, bool TrackWhyLive> class MarkLive {57public:58 MarkLive(Ctx &ctx, unsigned partition) : ctx(ctx), partition(partition) {}59 60 void run();61 void moveToMain();62 void printWhyLive(Symbol *s) const;63 64private:65 void enqueue(InputSectionBase *sec, uint64_t offset, Symbol *sym,66 LiveReason reason);67 void markSymbol(Symbol *sym, StringRef reason);68 void mark();69 70 template <class RelTy>71 void resolveReloc(InputSectionBase &sec, const RelTy &rel, bool fromFDE);72 73 void scanEhFrameSection(EhInputSection &eh);74 75 Ctx &ctx;76 // The index of the partition that we are currently processing.77 unsigned partition;78 79 // A list of sections to visit.80 SmallVector<InputSection *, 0> queue;81 82 // There are normally few input sections whose names are valid C83 // identifiers, so we just store a SmallVector instead of a multimap.84 DenseMap<StringRef, SmallVector<InputSectionBase *, 0>> cNamedSections;85 86 // The most proximate reason that something is live. This forms a DAG between87 // LiveItems. Acyclicality is maintained by only admitting the first88 // discovered reason for each LiveItem; this captures the acyclic region of89 // the liveness graph around the GC roots.90 DenseMap<LiveItem, LiveReason> whyLive;91};92} // namespace93 94template <class ELFT>95static uint64_t getAddend(Ctx &ctx, InputSectionBase &sec,96 const typename ELFT::Rel &rel) {97 return ctx.target->getImplicitAddend(sec.content().begin() + rel.r_offset,98 rel.getType(ctx.arg.isMips64EL));99}100 101template <class ELFT>102static uint64_t getAddend(Ctx &, InputSectionBase &sec,103 const typename ELFT::Rela &rel) {104 return rel.r_addend;105}106 107// Currently, we assume all input CREL relocations have an explicit addend.108template <class ELFT>109static uint64_t getAddend(Ctx &, InputSectionBase &sec,110 const typename ELFT::Crel &rel) {111 return rel.r_addend;112}113 114template <class ELFT, bool TrackWhyLive>115template <class RelTy>116void MarkLive<ELFT, TrackWhyLive>::resolveReloc(InputSectionBase &sec,117 const RelTy &rel,118 bool fromFDE) {119 // If a symbol is referenced in a live section, it is used.120 Symbol *sym;121 if constexpr (std::is_same_v<RelTy, Relocation>) {122 assert(isa<EhInputSection>(sec));123 sym = rel.sym;124 } else {125 sym = &sec.file->getRelocTargetSym(rel);126 }127 sym->used = true;128 129 LiveReason reason;130 if (TrackWhyLive) {131 if constexpr (std::is_same_v<RelTy, Relocation>)132 reason = {SecOffset(&sec, rel.offset), "referenced by"};133 else134 reason = {SecOffset(&sec, rel.r_offset), "referenced by"};135 }136 137 if (auto *d = dyn_cast<Defined>(sym)) {138 auto *relSec = dyn_cast_or_null<InputSectionBase>(d->section);139 if (!relSec)140 return;141 142 uint64_t offset = d->value;143 if (d->isSection()) {144 if constexpr (std::is_same_v<RelTy, Relocation>)145 offset += rel.addend;146 else147 offset += getAddend<ELFT>(ctx, sec, rel);148 }149 150 // fromFDE being true means this is referenced by a FDE in a .eh_frame151 // piece. The relocation points to the described function or to a LSDA. We152 // only need to keep the LSDA live, so ignore anything that points to153 // executable sections. If the LSDA is in a section group or has the154 // SHF_LINK_ORDER flag, we ignore the relocation as well because (a) if the155 // associated text section is live, the LSDA will be retained due to section156 // group/SHF_LINK_ORDER rules (b) if the associated text section should be157 // discarded, marking the LSDA will unnecessarily retain the text section.158 if (!(fromFDE && std::is_same_v<RelTy, Relocation> &&159 ((relSec->flags & (SHF_EXECINSTR | SHF_LINK_ORDER)) ||160 relSec->nextInSectionGroup))) {161 Symbol *canonicalSym = d;162 if (TrackWhyLive && d->isSection()) {163 // This is expensive, so ideally this would be deferred until it's known164 // whether this reference contributes to a printed whyLive chain, but165 // that determination cannot be made without knowing the enclosing166 // symbol.167 if (Symbol *s = relSec->getEnclosingSymbol(offset))168 canonicalSym = s;169 else170 canonicalSym = nullptr;171 }172 enqueue(relSec, offset, canonicalSym, reason);173 }174 return;175 }176 177 if (auto *ss = dyn_cast<SharedSymbol>(sym)) {178 if (!ss->isWeak()) {179 cast<SharedFile>(ss->file)->isNeeded = true;180 if (TrackWhyLive)181 whyLive.try_emplace(sym, reason);182 }183 }184 185 for (InputSectionBase *sec : cNamedSections.lookup(sym->getName()))186 enqueue(sec, /*offset=*/0, /*sym=*/nullptr, reason);187}188 189// The .eh_frame section is an unfortunate special case.190// The section is divided in CIEs and FDEs and the relocations it can have are191// * CIEs can refer to a personality function.192// * FDEs can refer to a LSDA193// * FDEs refer to the function they contain information about194// The last kind of relocation cannot keep the referred section alive, or they195// would keep everything alive in a common object file. In fact, each FDE is196// alive if the section it refers to is alive.197// To keep things simple, in here we just ignore the last relocation kind. The198// other two keep the referred section alive.199//200// A possible improvement would be to fully process .eh_frame in the middle of201// the gc pass. With that we would be able to also gc some sections holding202// LSDAs and personality functions if we found that they were unused.203template <class ELFT, bool TrackWhyLive>204void MarkLive<ELFT, TrackWhyLive>::scanEhFrameSection(EhInputSection &eh) {205 ArrayRef<Relocation> rels = eh.rels;206 for (const EhSectionPiece &cie : eh.cies)207 if (cie.firstRelocation != unsigned(-1))208 resolveReloc(eh, rels[cie.firstRelocation], false);209 for (const EhSectionPiece &fde : eh.fdes) {210 size_t firstRelI = fde.firstRelocation;211 if (firstRelI == (unsigned)-1)212 continue;213 uint64_t pieceEnd = fde.inputOff + fde.size;214 for (size_t j = firstRelI, end2 = rels.size();215 j < end2 && rels[j].offset < pieceEnd; ++j)216 resolveReloc(eh, rels[j], true);217 }218}219 220// Some sections are used directly by the loader, so they should never be221// garbage-collected. This function returns true if a given section is such222// section.223static bool isReserved(InputSectionBase *sec) {224 switch (sec->type) {225 case SHT_FINI_ARRAY:226 case SHT_INIT_ARRAY:227 case SHT_PREINIT_ARRAY:228 return true;229 case SHT_NOTE:230 // SHT_NOTE sections in a group are subject to garbage collection.231 return !sec->nextInSectionGroup;232 default:233 // Support SHT_PROGBITS .init_array (https://golang.org/issue/50295) and234 // .init_array.N (https://github.com/rust-lang/rust/issues/92181) for a235 // while.236 StringRef s = sec->name;237 return s == ".init" || s == ".fini" || s.starts_with(".init_array") ||238 s == ".jcr" || s.starts_with(".ctors") || s.starts_with(".dtors");239 }240}241 242template <class ELFT, bool TrackWhyLive>243void MarkLive<ELFT, TrackWhyLive>::enqueue(InputSectionBase *sec,244 uint64_t offset, Symbol *sym,245 LiveReason reason) {246 // Usually, a whole section is marked as live or dead, but in mergeable247 // (splittable) sections, each piece of data has independent liveness bit.248 // So we explicitly tell it which offset is in use.249 if (auto *ms = dyn_cast<MergeInputSection>(sec))250 ms->getSectionPiece(offset).live = true;251 252 // Set Sec->Partition to the meet (i.e. the "minimum") of Partition and253 // Sec->Partition in the following lattice: 1 < other < 0. If Sec->Partition254 // doesn't change, we don't need to do anything.255 if (sec->partition == 1 || sec->partition == partition)256 return;257 sec->partition = sec->partition ? 1 : partition;258 259 if (TrackWhyLive) {260 if (sym) {261 // If a specific symbol is referenced, that keeps it live. The symbol then262 // keeps its section live.263 whyLive.try_emplace(sym, reason);264 whyLive.try_emplace(sec, LiveReason{sym, "contained live symbol"});265 } else {266 // Otherwise, the reference generically keeps the section live.267 whyLive.try_emplace(sec, reason);268 }269 }270 271 // Add input section to the queue.272 if (InputSection *s = dyn_cast<InputSection>(sec))273 queue.push_back(s);274}275 276// Print the stack of reasons that the given symbol is live.277template <class ELFT, bool TrackWhyLive>278void MarkLive<ELFT, TrackWhyLive>::printWhyLive(Symbol *s) const {279 // Skip dead symbols. A symbol is dead if it belongs to a dead section.280 if (auto *d = dyn_cast<Defined>(s)) {281 auto *sec = dyn_cast_or_null<InputSectionBase>(d->section);282 if (sec && !sec->isLive())283 return;284 }285 286 auto msg = Msg(ctx);287 288 const auto printSymbol = [&](Symbol *s) {289 msg << s->file << ":(" << s << ')';290 };291 292 msg << "live symbol: ";293 printSymbol(s);294 295 LiveItem cur = s;296 while (true) {297 auto it = whyLive.find(cur);298 LiveReason reason;299 // If there is a specific reason this item is live...300 if (it != whyLive.end()) {301 reason = it->second;302 } else {303 // This item is live, but it has no tracked reason. It must be an304 // unreferenced symbol in a live section or a symbol with no section.305 InputSectionBase *sec = nullptr;306 if (auto *d = dyn_cast<Defined>(std::get<Symbol *>(cur)))307 sec = dyn_cast_or_null<InputSectionBase>(d->section);308 reason = sec ? LiveReason{sec, "in live section"}309 : LiveReason{std::nullopt, "no section"};310 }311 312 if (!reason.item) {313 msg << " (" << reason.desc << ')';314 break;315 }316 317 msg << "\n>>> " << reason.desc << ": ";318 // The reason may not yet have been resolved to a symbol; do so now.319 if (std::holds_alternative<SecOffset>(*reason.item)) {320 const auto &so = std::get<SecOffset>(*reason.item);321 InputSectionBase *sec = so.first;322 Defined *sym = sec->getEnclosingSymbol(so.second);323 cur = sym ? LiveItem(sym) : LiveItem(sec);324 } else {325 cur = *reason.item;326 }327 328 if (std::holds_alternative<Symbol *>(cur))329 printSymbol(std::get<Symbol *>(cur));330 else331 msg << std::get<InputSectionBase *>(cur);332 }333}334 335template <class ELFT, bool TrackWhyLive>336void MarkLive<ELFT, TrackWhyLive>::markSymbol(Symbol *sym, StringRef reason) {337 if (auto *d = dyn_cast_or_null<Defined>(sym))338 if (auto *isec = dyn_cast_or_null<InputSectionBase>(d->section))339 enqueue(isec, d->value, sym, {std::nullopt, reason});340}341 342// This is the main function of the garbage collector.343// Starting from GC-root sections, this function visits all reachable344// sections to set their "Live" bits.345template <class ELFT, bool TrackWhyLive>346void MarkLive<ELFT, TrackWhyLive>::run() {347 // Add GC root symbols.348 349 // Preserve externally-visible symbols if the symbols defined by this350 // file can interpose other ELF file's symbols at runtime.351 for (Symbol *sym : ctx.symtab->getSymbols())352 if (sym->isExported && sym->partition == partition)353 markSymbol(sym, "externally visible symbol; may interpose");354 355 // If this isn't the main partition, that's all that we need to preserve.356 if (partition != 1) {357 mark();358 return;359 }360 361 markSymbol(ctx.symtab->find(ctx.arg.entry), "entry point");362 markSymbol(ctx.symtab->find(ctx.arg.init), "initializer function");363 markSymbol(ctx.symtab->find(ctx.arg.fini), "finalizer function");364 for (StringRef s : ctx.arg.undefined)365 markSymbol(ctx.symtab->find(s), "undefined command line flag");366 for (StringRef s : ctx.script->referencedSymbols)367 markSymbol(ctx.symtab->find(s), "referenced by linker script");368 for (auto [symName, _] : ctx.symtab->cmseSymMap) {369 markSymbol(ctx.symtab->cmseSymMap[symName].sym, "ARM CMSE symbol");370 markSymbol(ctx.symtab->cmseSymMap[symName].acleSeSym, "ARM CMSE symbol");371 }372 373 // Mark .eh_frame sections as live because there are usually no relocations374 // that point to .eh_frames. Otherwise, the garbage collector would drop375 // all of them. We also want to preserve personality routines and LSDA376 // referenced by .eh_frame sections, so we scan them for that here.377 for (EhInputSection *eh : ctx.ehInputSections)378 scanEhFrameSection(*eh);379 for (InputSectionBase *sec : ctx.inputSections) {380 if (sec->flags & SHF_GNU_RETAIN) {381 enqueue(sec, /*offset=*/0, /*sym=*/nullptr, {std::nullopt, "retained"});382 continue;383 }384 if (sec->flags & SHF_LINK_ORDER)385 continue;386 387 // Usually, non-SHF_ALLOC sections are not removed even if they are388 // unreachable through relocations because reachability is not a good signal389 // whether they are garbage or not (e.g. there is usually no section390 // referring to a .comment section, but we want to keep it.) When a391 // non-SHF_ALLOC section is retained, we also retain sections dependent on392 // it.393 //394 // Note on SHF_LINK_ORDER: Such sections contain metadata and they395 // have a reverse dependency on the InputSection they are linked with.396 // We are able to garbage collect them.397 //398 // Note on SHF_REL{,A}: Such sections reach here only when -r399 // or --emit-reloc were given. And they are subject of garbage400 // collection because, if we remove a text section, we also401 // remove its relocation section.402 //403 // Note on nextInSectionGroup: The ELF spec says that group sections are404 // included or omitted as a unit. We take the interpretation that:405 //406 // - Group members (nextInSectionGroup != nullptr) are subject to garbage407 // collection.408 // - Groups members are retained or discarded as a unit.409 if (!(sec->flags & SHF_ALLOC)) {410 if (!isStaticRelSecType(sec->type) && !sec->nextInSectionGroup) {411 sec->markLive();412 for (InputSection *isec : sec->dependentSections)413 isec->markLive();414 }415 }416 417 // Preserve special sections and those which are specified in linker418 // script KEEP command.419 if (isReserved(sec)) {420 enqueue(sec, /*offset=*/0, /*sym=*/nullptr, {std::nullopt, "reserved"});421 } else if (ctx.script->shouldKeep(sec)) {422 enqueue(sec, /*offset=*/0, /*sym=*/nullptr,423 {std::nullopt, "KEEP in linker script"});424 } else if ((!ctx.arg.zStartStopGC || sec->name.starts_with("__libc_")) &&425 isValidCIdentifier(sec->name)) {426 // As a workaround for glibc libc.a before 2.34427 // (https://sourceware.org/PR27492), retain __libc_atexit and similar428 // sections regardless of zStartStopGC.429 cNamedSections[ctx.saver.save("__start_" + sec->name)].push_back(sec);430 cNamedSections[ctx.saver.save("__stop_" + sec->name)].push_back(sec);431 }432 }433 434 mark();435 436 if (TrackWhyLive) {437 const auto handleSym = [&](Symbol *sym) {438 if (llvm::any_of(ctx.arg.whyLive, [sym](const llvm::GlobPattern &pat) {439 return pat.match(sym->getName());440 }))441 printWhyLive(sym);442 };443 444 for (Symbol *sym : ctx.symtab->getSymbols())445 handleSym(sym);446 for (ELFFileBase *file : ctx.objectFiles)447 for (Symbol *sym : file->getSymbols())448 if (sym->isLocal())449 handleSym(sym);450 }451}452 453template <class ELFT, bool TrackWhyLive>454void MarkLive<ELFT, TrackWhyLive>::mark() {455 // Mark all reachable sections.456 while (!queue.empty()) {457 InputSectionBase &sec = *queue.pop_back_val();458 459 const RelsOrRelas<ELFT> rels = sec.template relsOrRelas<ELFT>();460 for (const typename ELFT::Rel &rel : rels.rels)461 resolveReloc(sec, rel, false);462 for (const typename ELFT::Rela &rel : rels.relas)463 resolveReloc(sec, rel, false);464 for (const typename ELFT::Crel &rel : rels.crels)465 resolveReloc(sec, rel, false);466 467 for (InputSectionBase *isec : sec.dependentSections)468 enqueue(isec, /*offset=*/0, /*sym=*/nullptr,469 {&sec, "depended on by section"});470 471 // Mark the next group member.472 if (sec.nextInSectionGroup)473 enqueue(sec.nextInSectionGroup, /*offset=*/0, /*sym=*/nullptr,474 {&sec, "in section group with"});475 }476}477 478// Move the sections for some symbols to the main partition, specifically ifuncs479// (because they can result in an IRELATIVE being added to the main partition's480// GOT, which means that the ifunc must be available when the main partition is481// loaded) and TLS symbols (because we only know how to correctly process TLS482// relocations for the main partition).483//484// We also need to move sections whose names are C identifiers that are referred485// to from __start_/__stop_ symbols because there will only be one set of486// symbols for the whole program.487template <class ELFT, bool TrackWhyLive>488void MarkLive<ELFT, TrackWhyLive>::moveToMain() {489 for (ELFFileBase *file : ctx.objectFiles)490 for (Symbol *s : file->getSymbols())491 if (auto *d = dyn_cast<Defined>(s))492 if ((d->type == STT_GNU_IFUNC || d->type == STT_TLS) && d->section &&493 d->section->isLive())494 markSymbol(s, /*reason=*/{});495 496 for (InputSectionBase *sec : ctx.inputSections) {497 if (!sec->isLive() || !isValidCIdentifier(sec->name))498 continue;499 if (ctx.symtab->find(("__start_" + sec->name).str()) ||500 ctx.symtab->find(("__stop_" + sec->name).str()))501 enqueue(sec, /*offset=*/0, /*sym=*/nullptr, /*reason=*/{});502 }503 504 mark();505}506 507// Before calling this function, Live bits are off for all508// input sections. This function make some or all of them on509// so that they are emitted to the output file.510template <class ELFT> void elf::markLive(Ctx &ctx) {511 llvm::TimeTraceScope timeScope("markLive");512 // If --gc-sections is not given, retain all input sections.513 if (!ctx.arg.gcSections) {514 // If a DSO defines a symbol referenced in a regular object, it is needed.515 for (Symbol *sym : ctx.symtab->getSymbols())516 if (auto *s = dyn_cast<SharedSymbol>(sym))517 if (s->isUsedInRegularObj && !s->isWeak())518 cast<SharedFile>(s->file)->isNeeded = true;519 return;520 }521 522 for (InputSectionBase *sec : ctx.inputSections)523 sec->markDead();524 525 // Follow the graph to mark all live sections.526 for (unsigned i = 1, e = ctx.partitions.size(); i <= e; ++i)527 if (ctx.arg.whyLive.empty())528 MarkLive<ELFT, false>(ctx, i).run();529 else530 MarkLive<ELFT, true>(ctx, i).run();531 532 // If we have multiple partitions, some sections need to live in the main533 // partition even if they were allocated to a loadable partition. Move them534 // there now.535 if (ctx.partitions.size() != 1)536 MarkLive<ELFT, false>(ctx, 1).moveToMain();537 538 // Report garbage-collected sections.539 if (ctx.arg.printGcSections.empty())540 return;541 std::error_code ec;542 raw_fd_ostream os = ctx.openAuxiliaryFile(ctx.arg.printGcSections, ec);543 if (ec) {544 Err(ctx) << "cannot open --print-gc-sections= file "545 << ctx.arg.printGcSections << ": " << ec.message();546 return;547 }548 for (InputSectionBase *sec : ctx.inputSections)549 if (!sec->isLive())550 os << "removing unused section " << toStr(ctx, sec) << '\n';551}552 553template void elf::markLive<ELF32LE>(Ctx &);554template void elf::markLive<ELF32BE>(Ctx &);555template void elf::markLive<ELF64LE>(Ctx &);556template void elf::markLive<ELF64BE>(Ctx &);557