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