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-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements --gc-sections, which is a feature to remove unused
10// sections from output. Unused sections are sections that are not reachable
11// from known GC-root symbols or sections. Naturally the feature is
12// implemented as a mark-sweep garbage collector.
13//
14// Here's how it works. Each InputSectionBase has a "Live" bit. The bit is off
15// by default. Starting with GC-root symbols or sections, markLive function
16// defined in this file visits all reachable sections to set their Live
17// bits. Writer will then ignore sections whose Live bits are off, so that
18// 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 C
83 // 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 between
87 // LiveItems. Acyclicality is maintained by only admitting the first
88 // discovered reason for each LiveItem; this captures the acyclic region of
89 // the liveness graph around the GC roots.
90 DenseMap<LiveItem, LiveReason> whyLive;
91};
92} // namespace
93
94template <class ELFT>
95static uint64_t getAddend(Ctx &ctx, InputSectionBase &sec,
96 const typename ELFT::Rel &rel) {
97 return ctx.target->getImplicitAddend(buf: sec.content().begin() + rel.r_offset,
98 type: 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 = {.item: SecOffset(&sec, rel.offset), .desc: "referenced by"};
133 else
134 reason = {.item: SecOffset(&sec, rel.r_offset), .desc: "referenced by"};
135 }
136
137 if (auto *d = dyn_cast<Defined>(Val: sym)) {
138 auto *relSec = dyn_cast_or_null<InputSectionBase>(Val: 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 else
147 offset += getAddend<ELFT>(ctx, sec, rel);
148 }
149
150 // fromFDE being true means this is referenced by a FDE in a .eh_frame
151 // piece. The relocation points to the described function or to a LSDA. We
152 // only need to keep the LSDA live, so ignore anything that points to
153 // executable sections. If the LSDA is in a section group or has the
154 // SHF_LINK_ORDER flag, we ignore the relocation as well because (a) if the
155 // associated text section is live, the LSDA will be retained due to section
156 // group/SHF_LINK_ORDER rules (b) if the associated text section should be
157 // 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 known
164 // whether this reference contributes to a printed whyLive chain, but
165 // that determination cannot be made without knowing the enclosing
166 // symbol.
167 if (Symbol *s = relSec->getEnclosingSymbol(offset))
168 canonicalSym = s;
169 else
170 canonicalSym = nullptr;
171 }
172 enqueue(sec: relSec, offset, sym: canonicalSym, reason);
173 }
174 return;
175 }
176
177 if (auto *ss = dyn_cast<SharedSymbol>(Val: sym)) {
178 if (!ss->isWeak()) {
179 cast<SharedFile>(Val: ss->file)->isNeeded = true;
180 if (TrackWhyLive)
181 whyLive.try_emplace(Key: sym, Args&: reason);
182 }
183 }
184
185 for (InputSectionBase *sec : cNamedSections.lookup(Val: 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 are
191// * CIEs can refer to a personality function.
192// * FDEs can refer to a LSDA
193// * FDEs refer to the function they contain information about
194// The last kind of relocation cannot keep the referred section alive, or they
195// would keep everything alive in a common object file. In fact, each FDE is
196// alive if the section it refers to is alive.
197// To keep things simple, in here we just ignore the last relocation kind. The
198// other two keep the referred section alive.
199//
200// A possible improvement would be to fully process .eh_frame in the middle of
201// the gc pass. With that we would be able to also gc some sections holding
202// LSDAs and personality functions if we found that they were unused.
203template <class ELFT, bool TrackWhyLive>
204void MarkLive<ELFT, TrackWhyLive>::scanEhFrameSection(EhInputSection &eh) {
205 if (TrackWhyLive)
206 whyLive.try_emplace(Key: &eh,
207 Args: LiveReason{.item: std::nullopt, .desc: "exception handling frame"});
208 ArrayRef<Relocation> rels = eh.rels;
209 for (const EhSectionPiece &cie : eh.cies)
210 if (cie.firstRelocation != unsigned(-1))
211 resolveReloc(eh, rels[cie.firstRelocation], false);
212 for (const EhSectionPiece &fde : eh.fdes) {
213 size_t firstRelI = fde.firstRelocation;
214 if (firstRelI == (unsigned)-1)
215 continue;
216 uint64_t pieceEnd = fde.inputOff + fde.size;
217 for (size_t j = firstRelI, end2 = rels.size();
218 j < end2 && rels[j].offset < pieceEnd; ++j)
219 resolveReloc(eh, rels[j], true);
220 }
221}
222
223// Some sections are used directly by the loader, so they should never be
224// garbage-collected. This function returns true if a given section is such
225// section.
226static bool isReserved(InputSectionBase *sec) {
227 switch (sec->type) {
228 case SHT_FINI_ARRAY:
229 case SHT_INIT_ARRAY:
230 case SHT_PREINIT_ARRAY:
231 return true;
232 case SHT_NOTE:
233 // SHT_NOTE sections in a group are subject to garbage collection.
234 return !sec->nextInSectionGroup;
235 default:
236 // Support SHT_PROGBITS .init_array (https://golang.org/issue/50295) and
237 // .init_array.N (https://github.com/rust-lang/rust/issues/92181) for a
238 // while.
239 StringRef s = sec->name;
240 return s == ".init" || s == ".fini" || s.starts_with(Prefix: ".init_array") ||
241 s == ".jcr" || s.starts_with(Prefix: ".ctors") || s.starts_with(Prefix: ".dtors");
242 }
243}
244
245template <class ELFT, bool TrackWhyLive>
246void MarkLive<ELFT, TrackWhyLive>::enqueue(InputSectionBase *sec,
247 uint64_t offset, Symbol *sym,
248 LiveReason reason) {
249 // Usually, a whole section is marked as live or dead, but in mergeable
250 // (splittable) sections, each piece of data has independent liveness bit.
251 // So we explicitly tell it which offset is in use.
252 if (auto *ms = dyn_cast<MergeInputSection>(Val: sec))
253 ms->getSectionPiece(offset).live = true;
254
255 // Set Sec->Partition to the meet (i.e. the "minimum") of Partition and
256 // Sec->Partition in the following lattice: 1 < other < 0. If Sec->Partition
257 // doesn't change, we don't need to do anything.
258 if (sec->partition == 1 || sec->partition == partition)
259 return;
260 sec->partition = sec->partition ? 1 : partition;
261
262 if (TrackWhyLive) {
263 if (sym) {
264 // If a specific symbol is referenced, that keeps it live. The symbol then
265 // keeps its section live.
266 whyLive.try_emplace(Key: sym, Args&: reason);
267 whyLive.try_emplace(Key: sec, Args: LiveReason{.item: sym, .desc: "contained live symbol"});
268 } else {
269 // Otherwise, the reference generically keeps the section live.
270 whyLive.try_emplace(Key: sec, Args&: reason);
271 }
272 }
273
274 // Add input section to the queue.
275 if (InputSection *s = dyn_cast<InputSection>(Val: sec))
276 queue.push_back(Elt: s);
277}
278
279// Print the stack of reasons that the given symbol is live.
280template <class ELFT, bool TrackWhyLive>
281void MarkLive<ELFT, TrackWhyLive>::printWhyLive(Symbol *s) const {
282 // Skip dead symbols. A symbol is dead if it belongs to a dead section.
283 if (auto *d = dyn_cast<Defined>(Val: s)) {
284 auto *sec = dyn_cast_or_null<InputSectionBase>(Val: d->section);
285 if (sec && !sec->isLive())
286 return;
287 }
288
289 auto msg = Msg(ctx);
290
291 const auto printSymbol = [&](Symbol *s) {
292 msg << s->file << ":(" << s << ')';
293 };
294
295 msg << "live symbol: ";
296 printSymbol(s);
297
298 LiveItem cur = s;
299 while (true) {
300 auto it = whyLive.find(Val: cur);
301 LiveReason reason;
302 // If there is a specific reason this item is live...
303 if (it != whyLive.end()) {
304 reason = it->second;
305 } else {
306 // This item is live, but it has no tracked reason. It must be an
307 // unreferenced symbol in a live section or a symbol with no section.
308 InputSectionBase *sec = nullptr;
309 if (auto *d = dyn_cast<Defined>(Val: std::get<Symbol *>(v&: cur)))
310 sec = dyn_cast_or_null<InputSectionBase>(Val: d->section);
311 reason = sec ? LiveReason{.item: sec, .desc: "in live section"}
312 : LiveReason{.item: std::nullopt, .desc: "no section"};
313 }
314
315 if (!reason.item) {
316 msg << " (" << reason.desc << ')';
317 break;
318 }
319
320 msg << "\n>>> " << reason.desc << ": ";
321 // The reason may not yet have been resolved to a symbol; do so now.
322 if (std::holds_alternative<SecOffset>(v: *reason.item)) {
323 const auto &so = std::get<SecOffset>(v&: *reason.item);
324 InputSectionBase *sec = so.first;
325 Defined *sym = sec->getEnclosingSymbol(offset: so.second);
326 cur = sym ? LiveItem(sym) : LiveItem(sec);
327 } else {
328 cur = *reason.item;
329 }
330
331 if (std::holds_alternative<Symbol *>(v: cur))
332 printSymbol(std::get<Symbol *>(v&: cur));
333 else
334 msg << std::get<InputSectionBase *>(v&: cur);
335 }
336}
337
338template <class ELFT, bool TrackWhyLive>
339void MarkLive<ELFT, TrackWhyLive>::markSymbol(Symbol *sym, StringRef reason) {
340 if (auto *d = dyn_cast_or_null<Defined>(Val: sym))
341 if (auto *isec = dyn_cast_or_null<InputSectionBase>(Val: d->section))
342 enqueue(sec: isec, offset: d->value, sym, reason: {std::nullopt, reason});
343}
344
345// This is the main function of the garbage collector.
346// Starting from GC-root sections, this function visits all reachable
347// sections to set their "Live" bits.
348template <class ELFT, bool TrackWhyLive>
349void MarkLive<ELFT, TrackWhyLive>::run() {
350 // Add GC root symbols.
351
352 // Preserve externally-visible symbols if the symbols defined by this
353 // file can interpose other ELF file's symbols at runtime.
354 for (Symbol *sym : ctx.symtab->getSymbols())
355 if (sym->isExported && sym->partition == partition)
356 markSymbol(sym, reason: "externally visible symbol; may interpose");
357
358 // If this isn't the main partition, that's all that we need to preserve.
359 if (partition != 1) {
360 mark();
361 return;
362 }
363
364 markSymbol(sym: ctx.symtab->find(name: ctx.arg.entry), reason: "entry point");
365 markSymbol(sym: ctx.symtab->find(name: ctx.arg.init), reason: "initializer function");
366 markSymbol(sym: ctx.symtab->find(name: ctx.arg.fini), reason: "finalizer function");
367 for (StringRef s : ctx.arg.undefined)
368 markSymbol(sym: ctx.symtab->find(name: s), reason: "undefined command line flag");
369 for (StringRef s : ctx.script->referencedSymbols)
370 markSymbol(sym: ctx.symtab->find(name: s), reason: "referenced by linker script");
371 for (auto [symName, _] : ctx.symtab->cmseSymMap) {
372 markSymbol(sym: ctx.symtab->cmseSymMap[symName].sym, reason: "ARM CMSE symbol");
373 markSymbol(sym: ctx.symtab->cmseSymMap[symName].acleSeSym, reason: "ARM CMSE symbol");
374 }
375
376 // Mark .eh_frame sections as live because there are usually no relocations
377 // that point to .eh_frames. Otherwise, the garbage collector would drop
378 // all of them. We also want to preserve personality routines and LSDA
379 // referenced by .eh_frame sections, so we scan them for that here.
380 for (EhInputSection *eh : ctx.ehInputSections)
381 scanEhFrameSection(eh&: *eh);
382 for (InputSectionBase *sec : ctx.inputSections) {
383 if (sec->flags & SHF_GNU_RETAIN) {
384 enqueue(sec, /*offset=*/0, /*sym=*/nullptr, reason: {std::nullopt, "retained"});
385 continue;
386 }
387 if (sec->flags & SHF_LINK_ORDER)
388 continue;
389
390 // Usually, non-SHF_ALLOC sections are not removed even if they are
391 // unreachable through relocations because reachability is not a good signal
392 // whether they are garbage or not (e.g. there is usually no section
393 // referring to a .comment section, but we want to keep it.) When a
394 // non-SHF_ALLOC section is retained, we also retain sections dependent on
395 // it.
396 //
397 // Note on SHF_LINK_ORDER: Such sections contain metadata and they
398 // have a reverse dependency on the InputSection they are linked with.
399 // We are able to garbage collect them.
400 //
401 // Note on SHF_REL{,A}: Such sections reach here only when -r
402 // or --emit-reloc were given. And they are subject of garbage
403 // collection because, if we remove a text section, we also
404 // remove its relocation section.
405 //
406 // Note on nextInSectionGroup: The ELF spec says that group sections are
407 // included or omitted as a unit. We take the interpretation that:
408 //
409 // - Group members (nextInSectionGroup != nullptr) are subject to garbage
410 // collection.
411 // - Groups members are retained or discarded as a unit.
412 if (!(sec->flags & SHF_ALLOC)) {
413 if (!isStaticRelSecType(type: sec->type) && !sec->nextInSectionGroup) {
414 sec->markLive();
415 for (InputSection *isec : sec->dependentSections)
416 isec->markLive();
417 }
418 }
419
420 // Preserve special sections and those which are specified in linker
421 // script KEEP command.
422 if (isReserved(sec)) {
423 enqueue(sec, /*offset=*/0, /*sym=*/nullptr, reason: {std::nullopt, "reserved"});
424 } else if (ctx.script->shouldKeep(s: sec)) {
425 enqueue(sec, /*offset=*/0, /*sym=*/nullptr,
426 reason: {std::nullopt, "KEEP in linker script"});
427 } else if ((!ctx.arg.zStartStopGC || sec->name.starts_with(Prefix: "__libc_")) &&
428 isValidCIdentifier(s: sec->name)) {
429 // As a workaround for glibc libc.a before 2.34
430 // (https://sourceware.org/PR27492), retain __libc_atexit and similar
431 // sections regardless of zStartStopGC.
432 cNamedSections[ctx.saver.save(S: "__start_" + sec->name)].push_back(Elt: sec);
433 cNamedSections[ctx.saver.save(S: "__stop_" + sec->name)].push_back(Elt: sec);
434 }
435 }
436
437 mark();
438
439 if (TrackWhyLive) {
440 const auto handleSym = [&](Symbol *sym) {
441 if (llvm::any_of(ctx.arg.whyLive, [sym](const llvm::GlobPattern &pat) {
442 return pat.match(S: sym->getName());
443 }))
444 printWhyLive(s: sym);
445 };
446
447 for (Symbol *sym : ctx.symtab->getSymbols())
448 handleSym(sym);
449 // Handle local symbols, skipping the symbol at index 0 and section
450 // symbols, which usually have empty names and technically not live. Note:
451 // a live section may lack an associated section symbol, making them
452 // unreliable liveness indicators.
453 for (ELFFileBase *file : ctx.objectFiles)
454 for (Symbol *sym : file->getSymbols())
455 if (sym->isLocal() && sym->isDefined() && !sym->isSection())
456 handleSym(sym);
457 }
458}
459
460template <class ELFT, bool TrackWhyLive>
461void MarkLive<ELFT, TrackWhyLive>::mark() {
462 // Mark all reachable sections.
463 while (!queue.empty()) {
464 InputSectionBase &sec = *queue.pop_back_val();
465
466 const RelsOrRelas<ELFT> rels = sec.template relsOrRelas<ELFT>();
467 for (const typename ELFT::Rel &rel : rels.rels)
468 resolveReloc(sec, rel, false);
469 for (const typename ELFT::Rela &rel : rels.relas)
470 resolveReloc(sec, rel, false);
471 for (const typename ELFT::Crel &rel : rels.crels)
472 resolveReloc(sec, rel, false);
473
474 for (InputSectionBase *isec : sec.dependentSections)
475 enqueue(sec: isec, /*offset=*/0, /*sym=*/nullptr,
476 reason: {&sec, "depended on by section"});
477
478 // Mark the next group member.
479 if (sec.nextInSectionGroup)
480 enqueue(sec: sec.nextInSectionGroup, /*offset=*/0, /*sym=*/nullptr,
481 reason: {&sec, "in section group with"});
482 }
483}
484
485// Move the sections for some symbols to the main partition, specifically ifuncs
486// (because they can result in an IRELATIVE being added to the main partition's
487// GOT, which means that the ifunc must be available when the main partition is
488// loaded) and TLS symbols (because we only know how to correctly process TLS
489// relocations for the main partition).
490//
491// We also need to move sections whose names are C identifiers that are referred
492// to from __start_/__stop_ symbols because there will only be one set of
493// symbols for the whole program.
494template <class ELFT, bool TrackWhyLive>
495void MarkLive<ELFT, TrackWhyLive>::moveToMain() {
496 for (ELFFileBase *file : ctx.objectFiles)
497 for (Symbol *s : file->getSymbols())
498 if (auto *d = dyn_cast<Defined>(Val: s))
499 if ((d->type == STT_GNU_IFUNC || d->type == STT_TLS) && d->section &&
500 d->section->isLive())
501 markSymbol(sym: s, /*reason=*/{});
502
503 for (InputSectionBase *sec : ctx.inputSections) {
504 if (!sec->isLive() || !isValidCIdentifier(s: sec->name))
505 continue;
506 if (ctx.symtab->find(name: ("__start_" + sec->name).str()) ||
507 ctx.symtab->find(name: ("__stop_" + sec->name).str()))
508 enqueue(sec, /*offset=*/0, /*sym=*/nullptr, /*reason=*/{});
509 }
510
511 mark();
512}
513
514// Before calling this function, Live bits are off for all
515// input sections. This function make some or all of them on
516// so that they are emitted to the output file.
517template <class ELFT> void elf::markLive(Ctx &ctx) {
518 llvm::TimeTraceScope timeScope("markLive");
519 // If --gc-sections is not given, retain all input sections.
520 if (!ctx.arg.gcSections) {
521 // If a DSO defines a symbol referenced in a regular object, it is needed.
522 for (Symbol *sym : ctx.symtab->getSymbols())
523 if (auto *s = dyn_cast<SharedSymbol>(Val: sym))
524 if (s->isUsedInRegularObj && !s->isWeak())
525 cast<SharedFile>(Val: s->file)->isNeeded = true;
526 return;
527 }
528
529 for (InputSectionBase *sec : ctx.inputSections)
530 sec->markDead();
531
532 // Follow the graph to mark all live sections.
533 for (unsigned i = 1, e = ctx.partitions.size(); i <= e; ++i)
534 if (ctx.arg.whyLive.empty())
535 MarkLive<ELFT, false>(ctx, i).run();
536 else
537 MarkLive<ELFT, true>(ctx, i).run();
538
539 // If we have multiple partitions, some sections need to live in the main
540 // partition even if they were allocated to a loadable partition. Move them
541 // there now.
542 if (ctx.partitions.size() != 1)
543 MarkLive<ELFT, false>(ctx, 1).moveToMain();
544
545 // Report garbage-collected sections.
546 if (ctx.arg.printGcSections.empty())
547 return;
548 std::error_code ec;
549 raw_fd_ostream os = ctx.openAuxiliaryFile(ctx.arg.printGcSections, ec);
550 if (ec) {
551 Err(ctx) << "cannot open --print-gc-sections= file "
552 << ctx.arg.printGcSections << ": " << ec.message();
553 return;
554 }
555 for (InputSectionBase *sec : ctx.inputSections)
556 if (!sec->isLive())
557 os << "removing unused section " << toStr(ctx, sec) << '\n';
558}
559
560template void elf::markLive<ELF32LE>(Ctx &);
561template void elf::markLive<ELF32BE>(Ctx &);
562template void elf::markLive<ELF64LE>(Ctx &);
563template void elf::markLive<ELF64BE>(Ctx &);
564