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 "lld/Common/Utils.h"
32#include "llvm/ADT/DenseMapInfoVariant.h"
33#include "llvm/ADT/STLExtras.h"
34#include "llvm/Support/Parallel.h"
35#include "llvm/Support/TimeProfiler.h"
36#include <variant>
37#include <vector>
38
39using namespace llvm;
40using namespace llvm::ELF;
41using namespace llvm::object;
42using namespace llvm::support::endian;
43using namespace lld;
44using namespace lld::elf;
45
46namespace {
47using SecOffset = std::pair<InputSectionBase *, unsigned>;
48
49// Something that can have an independent reason for being live.
50using LiveItem = std::variant<InputSectionBase *, Symbol *, SecOffset>;
51
52// The most proximate reason that something is live.
53struct LiveReason {
54 std::optional<LiveItem> item;
55 StringRef desc;
56};
57
58template <class ELFT, bool TrackWhyLive> class MarkLive {
59public:
60 MarkLive(Ctx &ctx) : ctx(ctx) {}
61
62 void run();
63 void printWhyLive(Symbol *s) const;
64
65private:
66 void enqueue(InputSectionBase *sec, uint64_t offset, Symbol *sym,
67 LiveReason reason);
68 void markSymbol(Symbol *sym, StringRef reason);
69 void mark();
70 void visit(InputSection &sec, SmallVector<InputSection *, 0> &stack);
71 void markParallel();
72
73 template <class RelTy>
74 void resolveReloc(InputSectionBase &sec, const RelTy &rel, bool fromFDE);
75
76 void scanEhFrameSection(EhInputSection &eh);
77
78 Ctx &ctx;
79
80 // A list of sections to visit.
81 SmallVector<InputSection *, 0> queue;
82
83 // There are normally few input sections whose names are valid C
84 // identifiers, so we just store a SmallVector instead of a multimap.
85 DenseMap<StringRef, SmallVector<InputSectionBase *, 0>> cNamedSections;
86
87 // The most proximate reason that something is live. This forms a DAG between
88 // LiveItems. Acyclicality is maintained by only admitting the first
89 // discovered reason for each LiveItem; this captures the acyclic region of
90 // the liveness graph around the GC roots.
91 DenseMap<LiveItem, LiveReason> whyLive;
92};
93} // namespace
94
95template <class RelTy>
96static int64_t getAddend(Ctx &ctx, InputSectionBase &sec, const RelTy &rel) {
97 if constexpr (RelTy::HasAddend)
98 return rel.r_addend;
99 else
100 return ctx.target->getImplicitAddend(buf: sec.content().begin() + rel.r_offset,
101 type: rel.getType(ctx.arg.isMips64EL));
102}
103
104template <class ELFT, bool TrackWhyLive>
105template <class RelTy>
106void MarkLive<ELFT, TrackWhyLive>::resolveReloc(InputSectionBase &sec,
107 const RelTy &rel,
108 bool fromFDE) {
109 // If a symbol is referenced in a live section, it is used.
110 Symbol *sym;
111 if constexpr (std::is_same_v<RelTy, Relocation>) {
112 assert(isa<EhInputSection>(sec));
113 sym = rel.sym;
114 } else {
115 sym = &sec.file->getRelocTargetSym(rel);
116 }
117 sym->setFlags(USED);
118
119 LiveReason reason;
120 if (TrackWhyLive) {
121 if constexpr (std::is_same_v<RelTy, Relocation>)
122 reason = {.item: SecOffset(&sec, rel.offset), .desc: "referenced by"};
123 else
124 reason = {.item: SecOffset(&sec, rel.r_offset), .desc: "referenced by"};
125 }
126
127 if (auto *d = dyn_cast<Defined>(Val: sym)) {
128 auto *relSec = dyn_cast_or_null<InputSectionBase>(Val: d->section);
129 if (!relSec)
130 return;
131
132 uint64_t offset = d->value;
133 if (d->isSection()) {
134 if constexpr (std::is_same_v<RelTy, Relocation>)
135 offset += rel.addend;
136 else
137 offset += getAddend(ctx, sec, rel);
138 // Skip out-of-bounds offsets to avoid an assertion failure in
139 // getSectionPiece.
140 if (auto *ms = dyn_cast<MergeInputSection>(Val: relSec);
141 ms && offset >= ms->content().size())
142 return;
143 }
144
145 // fromFDE being true means this is referenced by a FDE in a .eh_frame
146 // piece. The relocation points to the described function or to a LSDA. We
147 // only need to keep the LSDA live, so ignore anything that points to
148 // executable sections. If the LSDA is in a section group or has the
149 // SHF_LINK_ORDER flag, we ignore the relocation as well because (a) if the
150 // associated text section is live, the LSDA will be retained due to section
151 // group/SHF_LINK_ORDER rules (b) if the associated text section should be
152 // discarded, marking the LSDA will unnecessarily retain the text section.
153 if (!(fromFDE && std::is_same_v<RelTy, Relocation> &&
154 ((relSec->flags & (SHF_EXECINSTR | SHF_LINK_ORDER)) ||
155 relSec->nextInSectionGroup))) {
156 Symbol *canonicalSym = d;
157 if (TrackWhyLive && d->isSection()) {
158 // This is expensive, so ideally this would be deferred until it's known
159 // whether this reference contributes to a printed whyLive chain, but
160 // that determination cannot be made without knowing the enclosing
161 // symbol.
162 if (Symbol *s = relSec->getEnclosingSymbol(offset))
163 canonicalSym = s;
164 else
165 canonicalSym = nullptr;
166 }
167 enqueue(sec: relSec, offset, sym: canonicalSym, reason);
168 }
169 return;
170 }
171
172 if (auto *ss = dyn_cast<SharedSymbol>(Val: sym))
173 if (!ss->isWeak() && TrackWhyLive)
174 whyLive.try_emplace(Key: sym, Args&: reason);
175
176 for (InputSectionBase *sec : cNamedSections.lookup(Val: sym->getName()))
177 enqueue(sec, /*offset=*/0, /*sym=*/nullptr, reason);
178}
179
180// The .eh_frame section is an unfortunate special case.
181// The section is divided in CIEs and FDEs and the relocations it can have are
182// * CIEs can refer to a personality function.
183// * FDEs can refer to a LSDA
184// * FDEs refer to the function they contain information about
185// The last kind of relocation cannot keep the referred section alive, or they
186// would keep everything alive in a common object file. In fact, each FDE is
187// alive if the section it refers to is alive.
188// To keep things simple, in here we just ignore the last relocation kind. The
189// other two keep the referred section alive.
190//
191// A possible improvement would be to fully process .eh_frame in the middle of
192// the gc pass. With that we would be able to also gc some sections holding
193// LSDAs and personality functions if we found that they were unused.
194template <class ELFT, bool TrackWhyLive>
195void MarkLive<ELFT, TrackWhyLive>::scanEhFrameSection(EhInputSection &eh) {
196 if (TrackWhyLive)
197 whyLive.try_emplace(Key: &eh,
198 Args: LiveReason{.item: std::nullopt, .desc: "exception handling frame"});
199 ArrayRef<Relocation> rels = eh.rels;
200 for (const EhSectionPiece &cie : eh.cies)
201 if (cie.firstRelocation != unsigned(-1))
202 resolveReloc(eh, rels[cie.firstRelocation], false);
203 for (const EhSectionPiece &fde : eh.fdes) {
204 size_t firstRelI = fde.firstRelocation;
205 if (firstRelI == (unsigned)-1)
206 continue;
207 uint64_t pieceEnd = fde.inputOff + fde.size;
208 for (size_t j = firstRelI, end2 = rels.size();
209 j < end2 && rels[j].offset < pieceEnd; ++j)
210 resolveReloc(eh, rels[j], true);
211 }
212}
213
214// Some sections are used directly by the loader, so they should never be
215// garbage-collected. This function returns true if a given section is such
216// section.
217static bool isReserved(InputSectionBase *sec) {
218 switch (sec->type) {
219 case SHT_FINI_ARRAY:
220 case SHT_INIT_ARRAY:
221 case SHT_PREINIT_ARRAY:
222 return true;
223 case SHT_NOTE:
224 // SHT_NOTE sections in a group are subject to garbage collection.
225 return !sec->nextInSectionGroup;
226 default:
227 // Support SHT_PROGBITS .init_array (https://golang.org/issue/50295) and
228 // .init_array.N (https://github.com/rust-lang/rust/issues/92181) for a
229 // while.
230 StringRef s = sec->name;
231 return s == ".init" || s == ".fini" || s.starts_with(Prefix: ".init_array") ||
232 s == ".jcr" || s.starts_with(Prefix: ".ctors") || s.starts_with(Prefix: ".dtors");
233 }
234}
235
236template <class ELFT, bool TrackWhyLive>
237void MarkLive<ELFT, TrackWhyLive>::enqueue(InputSectionBase *sec,
238 uint64_t offset, Symbol *sym,
239 LiveReason reason) {
240 // Usually, a whole section is marked as live or dead, but in mergeable
241 // (splittable) sections, each piece of data has independent liveness bit.
242 // So we explicitly tell it which offset is in use.
243 if (auto *ms = dyn_cast<MergeInputSection>(Val: sec))
244 ms->getSectionPiece(offset).live = true;
245
246 if (sec->partition)
247 return;
248 sec->partition = 1;
249
250 if (TrackWhyLive) {
251 if (sym) {
252 // If a specific symbol is referenced, that keeps it live. The symbol then
253 // keeps its section live.
254 whyLive.try_emplace(Key: sym, Args&: reason);
255 whyLive.try_emplace(Key: sec, Args: LiveReason{.item: sym, .desc: "contained live symbol"});
256 } else {
257 // Otherwise, the reference generically keeps the section live.
258 whyLive.try_emplace(Key: sec, Args&: reason);
259 }
260 }
261
262 // Add input section to the queue.
263 if (InputSection *s = dyn_cast<InputSection>(Val: sec))
264 queue.push_back(Elt: s);
265}
266
267// Print the stack of reasons that the given symbol is live.
268template <class ELFT, bool TrackWhyLive>
269void MarkLive<ELFT, TrackWhyLive>::printWhyLive(Symbol *s) const {
270 // Skip dead symbols. A symbol is dead if it belongs to a dead section or if
271 // it refers to a dead mergeable section piece.
272 if (auto *d = dyn_cast<Defined>(Val: s)) {
273 if (auto *sec = dyn_cast_or_null<InputSectionBase>(Val: d->section)) {
274 if (!sec->isLive())
275 return;
276
277 if (!d->isSection())
278 if (auto *ms = dyn_cast<MergeInputSection>(Val: sec);
279 ms && !ms->getSectionPiece(offset: d->value).live)
280 return;
281 }
282 }
283
284 auto msg = Msg(ctx);
285
286 const auto printSymbol = [&](Symbol *s) {
287 msg << s->file << ":(" << s << ')';
288 };
289
290 msg << "live symbol: ";
291 printSymbol(s);
292
293 LiveItem cur = s;
294 while (true) {
295 auto it = whyLive.find(Val: cur);
296 LiveReason reason;
297 // If there is a specific reason this item is live...
298 if (it != whyLive.end()) {
299 reason = it->second;
300 } else {
301 // This item is live, but it has no tracked reason. It must be an
302 // unreferenced symbol in a live section or a symbol with no section.
303 InputSectionBase *sec = nullptr;
304 if (auto *d = dyn_cast<Defined>(Val: std::get<Symbol *>(v&: cur)))
305 sec = dyn_cast_or_null<InputSectionBase>(Val: d->section);
306 reason = sec ? LiveReason{.item: sec, .desc: "in live section"}
307 : LiveReason{.item: std::nullopt, .desc: "no section"};
308 }
309
310 if (!reason.item) {
311 msg << " (" << reason.desc << ')';
312 break;
313 }
314
315 msg << "\n>>> " << reason.desc << ": ";
316 // The reason may not yet have been resolved to a symbol; do so now.
317 if (std::holds_alternative<SecOffset>(v: *reason.item)) {
318 const auto &so = std::get<SecOffset>(v&: *reason.item);
319 InputSectionBase *sec = so.first;
320 Defined *sym = sec->getEnclosingSymbol(offset: so.second);
321 cur = sym ? LiveItem(sym) : LiveItem(sec);
322 } else {
323 cur = *reason.item;
324 }
325
326 if (std::holds_alternative<Symbol *>(v: cur))
327 printSymbol(std::get<Symbol *>(v&: cur));
328 else
329 msg << std::get<InputSectionBase *>(v&: cur);
330 }
331}
332
333template <class ELFT, bool TrackWhyLive>
334void MarkLive<ELFT, TrackWhyLive>::markSymbol(Symbol *sym, StringRef reason) {
335 if (auto *d = dyn_cast_or_null<Defined>(Val: sym))
336 if (auto *isec = dyn_cast_or_null<InputSectionBase>(Val: d->section))
337 enqueue(sec: isec, offset: d->value, sym, reason: {std::nullopt, reason});
338}
339
340// If -r or --emit-relocs, mark symbols referenced by relocations as used so
341// .symtab retains them and the relocations keep valid symbol indices. Callers
342// invoke this only when .symtab filtering is active (--discard-* or
343// --retain-symbols-file); otherwise .symtab keeps every symbol anyway.
344template <class ELFT> static void markUsedSymbols(InputSectionBase &sec) {
345 auto mark = [&](const auto &rel) {
346 sec.file->getRelocTargetSym(rel).setFlags(USED);
347 };
348 const RelsOrRelas<ELFT> rels = sec.template relsOrRelas<ELFT>();
349 for (const typename ELFT::Rel &rel : rels.rels)
350 mark(rel);
351 for (const typename ELFT::Rela &rel : rels.relas)
352 mark(rel);
353 for (const typename ELFT::Crel &rel : rels.crels)
354 mark(rel);
355}
356
357// This is the main function of the garbage collector.
358// Starting from GC-root sections, this function visits all reachable
359// sections to set their "Live" bits.
360template <class ELFT, bool TrackWhyLive>
361void MarkLive<ELFT, TrackWhyLive>::run() {
362 // Add GC root symbols.
363
364 for (Symbol *sym : ctx.symtab->getSymbols()) {
365 // For now, preserve all symbols required by the embedded unoptimized part
366 // of dynamic debugging. TODO: better support for `--gc-sections`.
367 if (sym->isDynDbgRef) {
368 markSymbol(sym, reason: "dynamic debugging");
369 sym->setFlags(USED);
370 continue;
371 }
372
373 // Preserve externally-visible symbols if the symbols defined by this
374 // file can interpose other ELF file's symbols at runtime.
375 if (sym->isExported)
376 markSymbol(sym, reason: "externally visible symbol");
377 }
378
379 markSymbol(sym: ctx.symtab->find(name: ctx.arg.entry), reason: "entry point");
380 markSymbol(sym: ctx.symtab->find(name: ctx.arg.init), reason: "initializer function");
381 markSymbol(sym: ctx.symtab->find(name: ctx.arg.fini), reason: "finalizer function");
382 for (StringRef s : ctx.arg.undefined)
383 markSymbol(sym: ctx.symtab->find(name: s), reason: "undefined command line flag");
384 for (StringRef s : ctx.script->referencedSymbols)
385 markSymbol(sym: ctx.symtab->find(name: s), reason: "referenced by linker script");
386 for (auto &[_, entry] : ctx.symtab->cmseSymMap) {
387 markSymbol(sym: entry.sym, reason: "ARM CMSE symbol");
388 markSymbol(sym: entry.acleSeSym, reason: "ARM CMSE symbol");
389 }
390
391 // Mark .eh_frame sections as live because there are usually no relocations
392 // that point to .eh_frames. Otherwise, the garbage collector would drop
393 // all of them. We also want to preserve personality routines and LSDA
394 // referenced by .eh_frame sections, so we scan them for that here.
395 for (EhInputSection *eh : ctx.ehInputSections)
396 scanEhFrameSection(eh&: *eh);
397 // See markUsedSymbols.
398 bool markUsed =
399 ctx.arg.copyRelocs &&
400 (ctx.arg.discard != DiscardPolicy::None || ctx.arg.retainSymbols);
401 for (InputSectionBase *sec : ctx.inputSections) {
402 if (sec->flags & SHF_GNU_RETAIN) {
403 enqueue(sec, /*offset=*/0, /*sym=*/nullptr, reason: {std::nullopt, "retained"});
404 continue;
405 }
406 if (sec->flags & SHF_LINK_ORDER)
407 continue;
408
409 // Usually, non-SHF_ALLOC sections are not removed even if they are
410 // unreachable through relocations because reachability is not a good signal
411 // whether they are garbage or not (e.g. there is usually no section
412 // referring to a .comment section, but we want to keep it.) When a
413 // non-SHF_ALLOC section is retained, we also retain sections dependent on
414 // it.
415 //
416 // Note on SHF_LINK_ORDER: Such sections contain metadata and they
417 // have a reverse dependency on the InputSection they are linked with.
418 // We are able to garbage collect them.
419 //
420 // Note on SHF_REL{,A}: Such sections reach here only when -r
421 // or --emit-reloc were given. And they are subject of garbage
422 // collection because, if we remove a text section, we also
423 // remove its relocation section.
424 //
425 // Note on nextInSectionGroup: The ELF spec says that group sections are
426 // included or omitted as a unit. We take the interpretation that:
427 //
428 // - Group members (nextInSectionGroup != nullptr) are subject to garbage
429 // collection.
430 // - Groups members are retained or discarded as a unit.
431 if (!(sec->flags & SHF_ALLOC)) {
432 if (!isStaticRelSecType(type: sec->type) && !sec->nextInSectionGroup) {
433 sec->markLive();
434 for (InputSection *isec : sec->dependentSections)
435 isec->markLive();
436 if (markUsed)
437 markUsedSymbols<ELFT>(*sec);
438 }
439 }
440
441 // Preserve special sections and those which are specified in linker
442 // script KEEP command.
443 if (isReserved(sec)) {
444 enqueue(sec, /*offset=*/0, /*sym=*/nullptr, reason: {std::nullopt, "reserved"});
445 } else if (ctx.script->shouldKeep(s: sec)) {
446 enqueue(sec, /*offset=*/0, /*sym=*/nullptr,
447 reason: {std::nullopt, "KEEP in linker script"});
448 } else if ((!ctx.arg.zStartStopGC || sec->name.starts_with(Prefix: "__libc_")) &&
449 isValidCIdentifier(s: sec->name)) {
450 // As a workaround for glibc libc.a before 2.34
451 // (https://sourceware.org/PR27492), retain __libc_atexit and similar
452 // sections regardless of zStartStopGC.
453 cNamedSections[ctx.saver.save(S: "__start_" + sec->name)].push_back(Elt: sec);
454 cNamedSections[ctx.saver.save(S: "__stop_" + sec->name)].push_back(Elt: sec);
455 }
456 }
457
458 if constexpr (TrackWhyLive)
459 mark();
460 else
461 markParallel();
462
463 if (TrackWhyLive) {
464 const auto handleSym = [&](Symbol *sym) {
465 if (llvm::any_of(ctx.arg.whyLive, [sym](const llvm::GlobPattern &pat) {
466 return pat.match(S: sym->getName());
467 }))
468 printWhyLive(s: sym);
469 };
470
471 for (Symbol *sym : ctx.symtab->getSymbols())
472 handleSym(sym);
473 // Handle local symbols, skipping the symbol at index 0 and section
474 // symbols, which usually have empty names and technically not live. Note:
475 // a live section may lack an associated section symbol, making them
476 // unreliable liveness indicators.
477 for (ELFFileBase *file : ctx.objectFiles)
478 for (Symbol *sym : file->getSymbols())
479 if (sym->isLocal() && sym->isDefined() && !sym->isSection())
480 handleSym(sym);
481 }
482}
483
484template <class ELFT, bool TrackWhyLive>
485void MarkLive<ELFT, TrackWhyLive>::mark() {
486 while (!queue.empty()) {
487 InputSectionBase &sec = *queue.pop_back_val();
488
489 const RelsOrRelas<ELFT> rels = sec.template relsOrRelas<ELFT>();
490 for (const typename ELFT::Rel &rel : rels.rels)
491 resolveReloc(sec, rel, false);
492 for (const typename ELFT::Rela &rel : rels.relas)
493 resolveReloc(sec, rel, false);
494 for (const typename ELFT::Crel &rel : rels.crels)
495 resolveReloc(sec, rel, false);
496
497 for (InputSectionBase *isec : sec.dependentSections)
498 enqueue(sec: isec, /*offset=*/0, /*sym=*/nullptr,
499 reason: {&sec, "depended on by section"});
500
501 // Mark the next group member.
502 if (sec.nextInSectionGroup)
503 enqueue(sec: sec.nextInSectionGroup, /*offset=*/0, /*sym=*/nullptr,
504 reason: {&sec, "in section group with"});
505 }
506}
507
508// Mark the sections that sec references and push the newly marked ones onto
509// stack.
510template <class ELFT, bool TrackWhyLive>
511void MarkLive<ELFT, TrackWhyLive>::visit(
512 InputSection &sec, SmallVector<InputSection *, 0> &stack) {
513 auto mark = [&](InputSectionBase *target) {
514 auto &part = utils::atomicRef(x&: target->partition);
515 // Optimistic load-then-exchange avoids expensive atomic RMW on
516 // already-visited sections.
517 if (part.load(m: std::memory_order_relaxed) != 0 ||
518 part.exchange(i: 1, m: std::memory_order_relaxed) != 0)
519 return;
520 if (auto *s = dyn_cast<InputSection>(Val: target))
521 stack.push_back(Elt: s);
522 };
523 auto resolveEdge = [&](const auto &rel) {
524 Symbol &sym = sec.file->getRelocTargetSym(rel);
525 if (!sym.hasFlag(bit: USED))
526 sym.setFlags(USED);
527 if (auto *d = dyn_cast<Defined>(Val: &sym)) {
528 auto *relSec = dyn_cast_or_null<InputSectionBase>(Val: d->section);
529 if (!relSec)
530 return;
531 if (auto *ms = dyn_cast<MergeInputSection>(Val: relSec)) {
532 uint64_t offset = d->value;
533 if (d->isSection()) {
534 offset += getAddend(ctx, sec, rel);
535 if (offset >= ms->content().size())
536 return;
537 }
538 auto &piece = ms->getSectionPiece(offset);
539 auto &word = utils::atomicRef(x&: *(&piece.inputOff + 1));
540 constexpr uint32_t liveBit = sys::IsBigEndianHost ? (1U << 31) : 1U;
541 word.fetch_or(i: liveBit, m: std::memory_order_relaxed);
542 }
543 mark(relSec);
544 return;
545 }
546 for (InputSectionBase *csec : cNamedSections.lookup(Val: sym.getName()))
547 mark(csec);
548 };
549 const RelsOrRelas<ELFT> rels = sec.template relsOrRelas<ELFT>();
550 for (const typename ELFT::Rel &rel : rels.rels)
551 resolveEdge(rel);
552 for (const typename ELFT::Rela &rel : rels.relas)
553 resolveEdge(rel);
554 for (const typename ELFT::Crel &rel : rels.crels)
555 resolveEdge(rel);
556 for (InputSectionBase *isec : sec.dependentSections)
557 mark(isec);
558 if (sec.nextInSectionGroup)
559 mark(sec.nextInSectionGroup);
560}
561
562// Level-synchronous marking with depth-first workers. Each level is a
563// parallelFor round: workers claim chunks of the level and walk depth-first for
564// cache locality. Once one runs out of chunks, the others move their stacks to
565// the next level.
566template <class ELFT, bool TrackWhyLive>
567void MarkLive<ELFT, TrackWhyLive>::markParallel() {
568 const size_t numThreads = parallel::getThreadCount();
569 SmallVector<InputSection *, 0> level;
570 level.reserve(N: queue.size());
571 while (!queue.empty()) {
572 level.clear();
573 std::swap(LHS&: level, RHS&: queue);
574 std::mutex mu;
575 std::atomic<bool> anyIdle{false};
576 const size_t chunkSize =
577 std::clamp<size_t>(val: level.size() / (4 * numThreads), lo: 1, hi: 64);
578 // Shard i first takes chunk i, so `nextChunk` starts at chunk `numThreads`.
579 std::atomic<size_t> nextChunk{numThreads * chunkSize};
580 parallelFor(0, numThreads, [&](size_t shard) {
581 SmallVector<InputSection *, 0> stack;
582 size_t visited = 0;
583 for (size_t begin = shard * chunkSize, end = level.size(); begin < end;
584 begin = nextChunk.fetch_add(i: chunkSize, m: std::memory_order_relaxed)) {
585 stack.append(in_start: level.begin() + begin,
586 in_end: level.begin() + std::min(a: begin + chunkSize, b: end));
587 while (!stack.empty()) {
588 visit(sec&: *stack.pop_back_val(), stack);
589 // Move the stack only after 256 visits in this level: each level
590 // ends with a barrier, and moving it sooner would add many levels
591 // on deep, narrow graphs.
592 if (++visited >= 256 && !stack.empty() &&
593 anyIdle.load(m: std::memory_order_relaxed)) {
594 std::lock_guard<std::mutex> lock(mu);
595 queue.append(RHS: stack);
596 stack.clear();
597 }
598 }
599 }
600 anyIdle.store(i: true, m: std::memory_order_relaxed);
601 });
602 }
603}
604
605// Before calling this function, Live bits are off for all
606// input sections. This function make some or all of them on
607// so that they are emitted to the output file.
608template <class ELFT> void elf::markLive(Ctx &ctx) {
609 llvm::TimeTraceScope timeScope("markLive");
610 // If --gc-sections is not given, retain all input sections.
611 if (!ctx.arg.gcSections) {
612 // If a DSO defines a symbol referenced in a regular object, it is needed.
613 for (Symbol *sym : ctx.symtab->getSymbols())
614 if (auto *s = dyn_cast<SharedSymbol>(Val: sym))
615 if (s->isUsedInRegularObj && !s->isWeak())
616 cast<SharedFile>(Val: s->file)->isNeeded = true;
617 // See markUsedSymbols.
618 if (ctx.arg.copyRelocs &&
619 (ctx.arg.discard != DiscardPolicy::None || ctx.arg.retainSymbols))
620 parallelForEach(ctx.objectFiles, [](ELFFileBase *file) {
621 for (InputSectionBase *sec : file->getSections())
622 if (sec)
623 markUsedSymbols<ELFT>(*sec);
624 });
625 return;
626 }
627
628 parallelForEach(ctx.inputSections,
629 [](InputSectionBase *sec) { sec->markDead(); });
630
631 // Follow the graph to mark all live sections.
632 if (ctx.arg.whyLive.empty())
633 MarkLive<ELFT, false>(ctx).run();
634 else
635 MarkLive<ELFT, true>(ctx).run();
636
637 // Determine which DSOs are needed. A DSO is needed if a non-weak SharedSymbol
638 // is used from a live section.
639 parallelForEach(ctx.symtab->getSymbols(), [](Symbol *sym) {
640 if (auto *ss = dyn_cast<SharedSymbol>(Val: sym))
641 if (ss->hasFlag(bit: USED) && !ss->isWeak())
642 cast<SharedFile>(Val: ss->file)->isNeeded = true;
643 });
644
645 // Report garbage-collected sections.
646 if (ctx.arg.printGcSections.empty())
647 return;
648 std::error_code ec;
649 raw_fd_ostream os = ctx.openAuxiliaryFile(ctx.arg.printGcSections, ec);
650 if (ec) {
651 Err(ctx) << "cannot open --print-gc-sections= file "
652 << ctx.arg.printGcSections << ": " << ec.message();
653 return;
654 }
655 for (InputSectionBase *sec : ctx.inputSections)
656 if (!sec->isLive())
657 os << "removing unused section " << toStr(ctx, sec) << '\n';
658}
659
660template void elf::markLive<ELF32LE>(Ctx &);
661template void elf::markLive<ELF32BE>(Ctx &);
662template void elf::markLive<ELF64LE>(Ctx &);
663template void elf::markLive<ELF64BE>(Ctx &);
664