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/Parallel.h"
34#include "llvm/Support/TimeProfiler.h"
35#include <variant>
36#include <vector>
37
38using namespace llvm;
39using namespace llvm::ELF;
40using namespace llvm::object;
41using namespace llvm::support::endian;
42using namespace lld;
43using namespace lld::elf;
44
45namespace {
46using SecOffset = std::pair<InputSectionBase *, unsigned>;
47
48// Something that can have an independent reason for being live.
49using LiveItem = std::variant<InputSectionBase *, Symbol *, SecOffset>;
50
51// The most proximate reason that something is live.
52struct LiveReason {
53 std::optional<LiveItem> item;
54 StringRef desc;
55};
56
57template <class ELFT, bool TrackWhyLive> class MarkLive {
58public:
59 MarkLive(Ctx &ctx) : ctx(ctx) {}
60
61 void run();
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 void markParallel();
70
71 template <class RelTy>
72 void resolveReloc(InputSectionBase &sec, const RelTy &rel, bool fromFDE);
73
74 void scanEhFrameSection(EhInputSection &eh);
75
76 Ctx &ctx;
77
78 // A list of sections to visit.
79 SmallVector<InputSection *, 0> queue;
80
81 // There are normally few input sections whose names are valid C
82 // identifiers, so we just store a SmallVector instead of a multimap.
83 DenseMap<StringRef, SmallVector<InputSectionBase *, 0>> cNamedSections;
84
85 // The most proximate reason that something is live. This forms a DAG between
86 // LiveItems. Acyclicality is maintained by only admitting the first
87 // discovered reason for each LiveItem; this captures the acyclic region of
88 // the liveness graph around the GC roots.
89 DenseMap<LiveItem, LiveReason> whyLive;
90};
91} // namespace
92
93template <class ELFT>
94static uint64_t getAddend(Ctx &ctx, InputSectionBase &sec,
95 const typename ELFT::Rel &rel) {
96 return ctx.target->getImplicitAddend(buf: sec.content().begin() + rel.r_offset,
97 type: rel.getType(ctx.arg.isMips64EL));
98}
99
100template <class ELFT>
101static uint64_t getAddend(Ctx &, InputSectionBase &sec,
102 const typename ELFT::Rela &rel) {
103 return rel.r_addend;
104}
105
106// Currently, we assume all input CREL relocations have an explicit addend.
107template <class ELFT>
108static uint64_t getAddend(Ctx &, InputSectionBase &sec,
109 const typename ELFT::Crel &rel) {
110 return rel.r_addend;
111}
112
113template <class ELFT, bool TrackWhyLive>
114template <class RelTy>
115void MarkLive<ELFT, TrackWhyLive>::resolveReloc(InputSectionBase &sec,
116 const RelTy &rel,
117 bool fromFDE) {
118 // If a symbol is referenced in a live section, it is used.
119 Symbol *sym;
120 if constexpr (std::is_same_v<RelTy, Relocation>) {
121 assert(isa<EhInputSection>(sec));
122 sym = rel.sym;
123 } else {
124 sym = &sec.file->getRelocTargetSym(rel);
125 }
126 sym->setFlags(USED);
127
128 LiveReason reason;
129 if (TrackWhyLive) {
130 if constexpr (std::is_same_v<RelTy, Relocation>)
131 reason = {.item: SecOffset(&sec, rel.offset), .desc: "referenced by"};
132 else
133 reason = {.item: SecOffset(&sec, rel.r_offset), .desc: "referenced by"};
134 }
135
136 if (auto *d = dyn_cast<Defined>(Val: sym)) {
137 auto *relSec = dyn_cast_or_null<InputSectionBase>(Val: d->section);
138 if (!relSec)
139 return;
140
141 uint64_t offset = d->value;
142 if (d->isSection()) {
143 if constexpr (std::is_same_v<RelTy, Relocation>)
144 offset += rel.addend;
145 else
146 offset += getAddend<ELFT>(ctx, sec, rel);
147 // Skip out-of-bounds offsets to avoid an assertion failure in
148 // getSectionPiece.
149 if (auto *ms = dyn_cast<MergeInputSection>(Val: relSec);
150 ms && offset >= ms->content().size())
151 return;
152 }
153
154 // fromFDE being true means this is referenced by a FDE in a .eh_frame
155 // piece. The relocation points to the described function or to a LSDA. We
156 // only need to keep the LSDA live, so ignore anything that points to
157 // executable sections. If the LSDA is in a section group or has the
158 // SHF_LINK_ORDER flag, we ignore the relocation as well because (a) if the
159 // associated text section is live, the LSDA will be retained due to section
160 // group/SHF_LINK_ORDER rules (b) if the associated text section should be
161 // discarded, marking the LSDA will unnecessarily retain the text section.
162 if (!(fromFDE && std::is_same_v<RelTy, Relocation> &&
163 ((relSec->flags & (SHF_EXECINSTR | SHF_LINK_ORDER)) ||
164 relSec->nextInSectionGroup))) {
165 Symbol *canonicalSym = d;
166 if (TrackWhyLive && d->isSection()) {
167 // This is expensive, so ideally this would be deferred until it's known
168 // whether this reference contributes to a printed whyLive chain, but
169 // that determination cannot be made without knowing the enclosing
170 // symbol.
171 if (Symbol *s = relSec->getEnclosingSymbol(offset))
172 canonicalSym = s;
173 else
174 canonicalSym = nullptr;
175 }
176 enqueue(sec: relSec, offset, sym: canonicalSym, reason);
177 }
178 return;
179 }
180
181 if (auto *ss = dyn_cast<SharedSymbol>(Val: sym))
182 if (!ss->isWeak() && TrackWhyLive)
183 whyLive.try_emplace(Key: sym, Args&: reason);
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 if (sec->partition)
256 return;
257 sec->partition = 1;
258
259 if (TrackWhyLive) {
260 if (sym) {
261 // If a specific symbol is referenced, that keeps it live. The symbol then
262 // keeps its section live.
263 whyLive.try_emplace(Key: sym, Args&: reason);
264 whyLive.try_emplace(Key: sec, Args: LiveReason{.item: sym, .desc: "contained live symbol"});
265 } else {
266 // Otherwise, the reference generically keeps the section live.
267 whyLive.try_emplace(Key: sec, Args&: reason);
268 }
269 }
270
271 // Add input section to the queue.
272 if (InputSection *s = dyn_cast<InputSection>(Val: sec))
273 queue.push_back(Elt: 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 or if
280 // it refers to a dead mergeable section piece.
281 if (auto *d = dyn_cast<Defined>(Val: s)) {
282 if (auto *sec = dyn_cast_or_null<InputSectionBase>(Val: d->section)) {
283 if (!sec->isLive())
284 return;
285
286 if (!d->isSection())
287 if (auto *ms = dyn_cast<MergeInputSection>(Val: sec);
288 ms && !ms->getSectionPiece(offset: d->value).live)
289 return;
290 }
291 }
292
293 auto msg = Msg(ctx);
294
295 const auto printSymbol = [&](Symbol *s) {
296 msg << s->file << ":(" << s << ')';
297 };
298
299 msg << "live symbol: ";
300 printSymbol(s);
301
302 LiveItem cur = s;
303 while (true) {
304 auto it = whyLive.find(Val: cur);
305 LiveReason reason;
306 // If there is a specific reason this item is live...
307 if (it != whyLive.end()) {
308 reason = it->second;
309 } else {
310 // This item is live, but it has no tracked reason. It must be an
311 // unreferenced symbol in a live section or a symbol with no section.
312 InputSectionBase *sec = nullptr;
313 if (auto *d = dyn_cast<Defined>(Val: std::get<Symbol *>(v&: cur)))
314 sec = dyn_cast_or_null<InputSectionBase>(Val: d->section);
315 reason = sec ? LiveReason{.item: sec, .desc: "in live section"}
316 : LiveReason{.item: std::nullopt, .desc: "no section"};
317 }
318
319 if (!reason.item) {
320 msg << " (" << reason.desc << ')';
321 break;
322 }
323
324 msg << "\n>>> " << reason.desc << ": ";
325 // The reason may not yet have been resolved to a symbol; do so now.
326 if (std::holds_alternative<SecOffset>(v: *reason.item)) {
327 const auto &so = std::get<SecOffset>(v&: *reason.item);
328 InputSectionBase *sec = so.first;
329 Defined *sym = sec->getEnclosingSymbol(offset: so.second);
330 cur = sym ? LiveItem(sym) : LiveItem(sec);
331 } else {
332 cur = *reason.item;
333 }
334
335 if (std::holds_alternative<Symbol *>(v: cur))
336 printSymbol(std::get<Symbol *>(v&: cur));
337 else
338 msg << std::get<InputSectionBase *>(v&: cur);
339 }
340}
341
342template <class ELFT, bool TrackWhyLive>
343void MarkLive<ELFT, TrackWhyLive>::markSymbol(Symbol *sym, StringRef reason) {
344 if (auto *d = dyn_cast_or_null<Defined>(Val: sym))
345 if (auto *isec = dyn_cast_or_null<InputSectionBase>(Val: d->section))
346 enqueue(sec: isec, offset: d->value, sym, reason: {std::nullopt, reason});
347}
348
349// If -r or --emit-relocs, mark symbols referenced by relocations as used so
350// .symtab retains them and the relocations keep valid symbol indices. Callers
351// invoke this only when .symtab filtering is active (--discard-* or
352// --retain-symbols-file); otherwise .symtab keeps every symbol anyway.
353template <class ELFT> static void markUsedSymbols(InputSectionBase &sec) {
354 auto mark = [&](const auto &rel) {
355 sec.file->getRelocTargetSym(rel).setFlags(USED);
356 };
357 const RelsOrRelas<ELFT> rels = sec.template relsOrRelas<ELFT>();
358 for (const typename ELFT::Rel &rel : rels.rels)
359 mark(rel);
360 for (const typename ELFT::Rela &rel : rels.relas)
361 mark(rel);
362 for (const typename ELFT::Crel &rel : rels.crels)
363 mark(rel);
364}
365
366// This is the main function of the garbage collector.
367// Starting from GC-root sections, this function visits all reachable
368// sections to set their "Live" bits.
369template <class ELFT, bool TrackWhyLive>
370void MarkLive<ELFT, TrackWhyLive>::run() {
371 // Add GC root symbols.
372
373 for (Symbol *sym : ctx.symtab->getSymbols()) {
374 // For now, preserve all symbols required by the embedded unoptimized part
375 // of dynamic debugging. TODO: better support for `--gc-sections`.
376 if (sym->isDynDbgRef) {
377 markSymbol(sym, reason: "dynamic debugging");
378 sym->setFlags(USED);
379 continue;
380 }
381
382 // Preserve externally-visible symbols if the symbols defined by this
383 // file can interpose other ELF file's symbols at runtime.
384 if (sym->isExported)
385 markSymbol(sym, reason: "externally visible symbol");
386 }
387
388 markSymbol(sym: ctx.symtab->find(name: ctx.arg.entry), reason: "entry point");
389 markSymbol(sym: ctx.symtab->find(name: ctx.arg.init), reason: "initializer function");
390 markSymbol(sym: ctx.symtab->find(name: ctx.arg.fini), reason: "finalizer function");
391 for (StringRef s : ctx.arg.undefined)
392 markSymbol(sym: ctx.symtab->find(name: s), reason: "undefined command line flag");
393 for (StringRef s : ctx.script->referencedSymbols)
394 markSymbol(sym: ctx.symtab->find(name: s), reason: "referenced by linker script");
395 for (auto [symName, _] : ctx.symtab->cmseSymMap) {
396 markSymbol(sym: ctx.symtab->cmseSymMap[symName].sym, reason: "ARM CMSE symbol");
397 markSymbol(sym: ctx.symtab->cmseSymMap[symName].acleSeSym, reason: "ARM CMSE symbol");
398 }
399
400 // Mark .eh_frame sections as live because there are usually no relocations
401 // that point to .eh_frames. Otherwise, the garbage collector would drop
402 // all of them. We also want to preserve personality routines and LSDA
403 // referenced by .eh_frame sections, so we scan them for that here.
404 for (EhInputSection *eh : ctx.ehInputSections)
405 scanEhFrameSection(eh&: *eh);
406 // See markUsedSymbols.
407 bool markUsed =
408 ctx.arg.copyRelocs &&
409 (ctx.arg.discard != DiscardPolicy::None || ctx.arg.retainSymbols);
410 for (InputSectionBase *sec : ctx.inputSections) {
411 if (sec->flags & SHF_GNU_RETAIN) {
412 enqueue(sec, /*offset=*/0, /*sym=*/nullptr, reason: {std::nullopt, "retained"});
413 continue;
414 }
415 if (sec->flags & SHF_LINK_ORDER)
416 continue;
417
418 // Usually, non-SHF_ALLOC sections are not removed even if they are
419 // unreachable through relocations because reachability is not a good signal
420 // whether they are garbage or not (e.g. there is usually no section
421 // referring to a .comment section, but we want to keep it.) When a
422 // non-SHF_ALLOC section is retained, we also retain sections dependent on
423 // it.
424 //
425 // Note on SHF_LINK_ORDER: Such sections contain metadata and they
426 // have a reverse dependency on the InputSection they are linked with.
427 // We are able to garbage collect them.
428 //
429 // Note on SHF_REL{,A}: Such sections reach here only when -r
430 // or --emit-reloc were given. And they are subject of garbage
431 // collection because, if we remove a text section, we also
432 // remove its relocation section.
433 //
434 // Note on nextInSectionGroup: The ELF spec says that group sections are
435 // included or omitted as a unit. We take the interpretation that:
436 //
437 // - Group members (nextInSectionGroup != nullptr) are subject to garbage
438 // collection.
439 // - Groups members are retained or discarded as a unit.
440 if (!(sec->flags & SHF_ALLOC)) {
441 if (!isStaticRelSecType(type: sec->type) && !sec->nextInSectionGroup) {
442 sec->markLive();
443 for (InputSection *isec : sec->dependentSections)
444 isec->markLive();
445 if (markUsed)
446 markUsedSymbols<ELFT>(*sec);
447 }
448 }
449
450 // Preserve special sections and those which are specified in linker
451 // script KEEP command.
452 if (isReserved(sec)) {
453 enqueue(sec, /*offset=*/0, /*sym=*/nullptr, reason: {std::nullopt, "reserved"});
454 } else if (ctx.script->shouldKeep(s: sec)) {
455 enqueue(sec, /*offset=*/0, /*sym=*/nullptr,
456 reason: {std::nullopt, "KEEP in linker script"});
457 } else if ((!ctx.arg.zStartStopGC || sec->name.starts_with(Prefix: "__libc_")) &&
458 isValidCIdentifier(s: sec->name)) {
459 // As a workaround for glibc libc.a before 2.34
460 // (https://sourceware.org/PR27492), retain __libc_atexit and similar
461 // sections regardless of zStartStopGC.
462 cNamedSections[ctx.saver.save(S: "__start_" + sec->name)].push_back(Elt: sec);
463 cNamedSections[ctx.saver.save(S: "__stop_" + sec->name)].push_back(Elt: sec);
464 }
465 }
466
467 mark();
468
469 if (TrackWhyLive) {
470 const auto handleSym = [&](Symbol *sym) {
471 if (llvm::any_of(ctx.arg.whyLive, [sym](const llvm::GlobPattern &pat) {
472 return pat.match(S: sym->getName());
473 }))
474 printWhyLive(s: sym);
475 };
476
477 for (Symbol *sym : ctx.symtab->getSymbols())
478 handleSym(sym);
479 // Handle local symbols, skipping the symbol at index 0 and section
480 // symbols, which usually have empty names and technically not live. Note:
481 // a live section may lack an associated section symbol, making them
482 // unreliable liveness indicators.
483 for (ELFFileBase *file : ctx.objectFiles)
484 for (Symbol *sym : file->getSymbols())
485 if (sym->isLocal() && sym->isDefined() && !sym->isSection())
486 handleSym(sym);
487 }
488}
489
490template <class ELFT, bool TrackWhyLive>
491void MarkLive<ELFT, TrackWhyLive>::mark() {
492 if constexpr (!TrackWhyLive) {
493 markParallel();
494 return;
495 }
496 while (!queue.empty()) {
497 InputSectionBase &sec = *queue.pop_back_val();
498
499 const RelsOrRelas<ELFT> rels = sec.template relsOrRelas<ELFT>();
500 for (const typename ELFT::Rel &rel : rels.rels)
501 resolveReloc(sec, rel, false);
502 for (const typename ELFT::Rela &rel : rels.relas)
503 resolveReloc(sec, rel, false);
504 for (const typename ELFT::Crel &rel : rels.crels)
505 resolveReloc(sec, rel, false);
506
507 for (InputSectionBase *isec : sec.dependentSections)
508 enqueue(sec: isec, /*offset=*/0, /*sym=*/nullptr,
509 reason: {&sec, "depended on by section"});
510
511 // Mark the next group member.
512 if (sec.nextInSectionGroup)
513 enqueue(sec: sec.nextInSectionGroup, /*offset=*/0, /*sym=*/nullptr,
514 reason: {&sec, "in section group with"});
515 }
516}
517
518// Helper function for markParallel. Walk all GC edges from sec, marking
519// everything that needs to be live. Call fn(target section, offset) for each
520// edge, which will mark the section live and handle further processing of edges
521// from that section.
522template <class ELFT, class Fn>
523static void processSectionEdges(
524 Ctx &ctx, InputSectionBase &sec,
525 const DenseMap<StringRef, SmallVector<InputSectionBase *, 0>>
526 &cNamedSections,
527 Fn fn) {
528 auto resolveEdge = [&](const auto &rel) {
529 Symbol &sym = sec.file->getRelocTargetSym(rel);
530 if (!sym.hasFlag(bit: USED))
531 sym.setFlags(USED);
532 if (auto *d = dyn_cast<Defined>(Val: &sym)) {
533 if (auto *relSec = dyn_cast_or_null<InputSectionBase>(Val: d->section)) {
534 uint64_t offset = d->value;
535 if (d->isSection()) {
536 offset += getAddend<ELFT>(ctx, sec, rel);
537 if (auto *ms = dyn_cast<MergeInputSection>(Val: relSec);
538 ms && offset >= ms->content().size())
539 return;
540 }
541 if (auto *ms = dyn_cast<MergeInputSection>(Val: relSec)) {
542 auto &piece = ms->getSectionPiece(offset);
543 auto *word =
544 reinterpret_cast<std::atomic<uint32_t> *>(&piece.inputOff + 1);
545 constexpr uint32_t liveBit = sys::IsBigEndianHost ? (1U << 31) : 1U;
546 word->fetch_or(i: liveBit, m: std::memory_order_relaxed);
547 }
548 fn(relSec, offset);
549 }
550 return;
551 }
552 for (InputSectionBase *csec : cNamedSections.lookup(Val: sym.getName()))
553 fn(csec, 0);
554 };
555 const RelsOrRelas<ELFT> rels = sec.template relsOrRelas<ELFT>();
556 for (const typename ELFT::Rel &rel : rels.rels)
557 resolveEdge(rel);
558 for (const typename ELFT::Rela &rel : rels.relas)
559 resolveEdge(rel);
560 for (const typename ELFT::Crel &rel : rels.crels)
561 resolveEdge(rel);
562 for (InputSectionBase *isec : sec.dependentSections)
563 fn(isec, 0);
564 if (sec.nextInSectionGroup)
565 fn(sec.nextInSectionGroup, 0);
566}
567
568// Parallel mark using level-synchronized BFS with depth-limited inline
569// recursion. Each parallelFor iteration processes a subtree up to depth 3
570// (DFS for cache locality), then queues deeper discoveries for the next level.
571template <class ELFT, bool TrackWhyLive>
572void MarkLive<ELFT, TrackWhyLive>::markParallel() {
573 const size_t numThreads = parallel::getThreadCount();
574 auto visit = [&](InputSection &sec, int depth,
575 SmallVector<InputSection *, 0> &localQueue,
576 auto &self) -> void {
577 processSectionEdges<ELFT>(
578 ctx, sec, cNamedSections,
579 [&](InputSectionBase *target, uint64_t offset) {
580 auto &part =
581 reinterpret_cast<std::atomic<uint8_t> &>(target->partition);
582 // Optimistic load-then-exchange avoids expensive atomic
583 // RMW on already-visited sections.
584 if (part.load(m: std::memory_order_relaxed) != 0 ||
585 part.exchange(i: 1, m: std::memory_order_relaxed) != 0)
586 return;
587 if (auto *s = dyn_cast<InputSection>(Val: target)) {
588 if (depth < 3)
589 self(*s, depth + 1, localQueue, self);
590 else
591 localQueue.push_back(Elt: s);
592 }
593 });
594 };
595
596 while (!queue.empty()) {
597 auto queues =
598 std::make_unique<SmallVector<InputSection *, 0>[]>(num: numThreads);
599 // Workers claim items off a shared counter and accumulate deeper
600 // discoveries into their own local queue, merged into `queue` below.
601 std::atomic<ptrdiff_t> next{ptrdiff_t(queue.size())};
602 parallelFor(0, numThreads, [&](size_t shard) {
603 for (ptrdiff_t i; (i = next.fetch_sub(i: 1, m: std::memory_order_relaxed)) > 0;)
604 visit(*queue[i - 1], 0, queues[shard], visit);
605 });
606 queue.clear();
607 for (size_t t = 0; t < numThreads; ++t)
608 queue.append(RHS: std::move(queues[t]));
609 }
610}
611
612// Before calling this function, Live bits are off for all
613// input sections. This function make some or all of them on
614// so that they are emitted to the output file.
615template <class ELFT> void elf::markLive(Ctx &ctx) {
616 llvm::TimeTraceScope timeScope("markLive");
617 // If --gc-sections is not given, retain all input sections.
618 if (!ctx.arg.gcSections) {
619 // If a DSO defines a symbol referenced in a regular object, it is needed.
620 for (Symbol *sym : ctx.symtab->getSymbols())
621 if (auto *s = dyn_cast<SharedSymbol>(Val: sym))
622 if (s->isUsedInRegularObj && !s->isWeak())
623 cast<SharedFile>(Val: s->file)->isNeeded = true;
624 // See markUsedSymbols.
625 if (ctx.arg.copyRelocs &&
626 (ctx.arg.discard != DiscardPolicy::None || ctx.arg.retainSymbols))
627 parallelForEach(ctx.objectFiles, [](ELFFileBase *file) {
628 for (InputSectionBase *sec : file->getSections())
629 if (sec)
630 markUsedSymbols<ELFT>(*sec);
631 });
632 return;
633 }
634
635 parallelForEach(ctx.inputSections,
636 [](InputSectionBase *sec) { sec->markDead(); });
637
638 // Follow the graph to mark all live sections.
639 if (ctx.arg.whyLive.empty())
640 MarkLive<ELFT, false>(ctx).run();
641 else
642 MarkLive<ELFT, true>(ctx).run();
643
644 // Determine which DSOs are needed. A DSO is needed if a non-weak SharedSymbol
645 // is used from a live section.
646 parallelForEach(ctx.symtab->getSymbols(), [](Symbol *sym) {
647 if (auto *ss = dyn_cast<SharedSymbol>(Val: sym))
648 if (ss->hasFlag(bit: USED) && !ss->isWeak())
649 cast<SharedFile>(Val: ss->file)->isNeeded = true;
650 });
651
652 // Report garbage-collected sections.
653 if (ctx.arg.printGcSections.empty())
654 return;
655 std::error_code ec;
656 raw_fd_ostream os = ctx.openAuxiliaryFile(ctx.arg.printGcSections, ec);
657 if (ec) {
658 Err(ctx) << "cannot open --print-gc-sections= file "
659 << ctx.arg.printGcSections << ": " << ec.message();
660 return;
661 }
662 for (InputSectionBase *sec : ctx.inputSections)
663 if (!sec->isLive())
664 os << "removing unused section " << toStr(ctx, sec) << '\n';
665}
666
667template void elf::markLive<ELF32LE>(Ctx &);
668template void elf::markLive<ELF32BE>(Ctx &);
669template void elf::markLive<ELF64LE>(Ctx &);
670template void elf::markLive<ELF64BE>(Ctx &);
671