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#include "MarkLive.h"
10#include "Config.h"
11#include "OutputSegment.h"
12#include "SymbolTable.h"
13#include "Symbols.h"
14#include "SyntheticSections.h"
15#include "UnwindInfoSection.h"
16
17#include "lld/Common/ErrorHandler.h"
18#include "llvm/Support/Parallel.h"
19#include "llvm/Support/TimeProfiler.h"
20
21#include <mutex>
22
23namespace lld::macho {
24
25using namespace llvm;
26using namespace llvm::MachO;
27
28struct WhyLiveEntry {
29 InputSection *isec;
30 // Keep track of the entry that caused us to mark `isec` as live.
31 const WhyLiveEntry *prev;
32
33 WhyLiveEntry(InputSection *isec, const WhyLiveEntry *prev)
34 : isec(isec), prev(prev) {}
35};
36
37// Type-erased interface to MarkLiveImpl. Used for adding roots to the liveness
38// graph.
39class MarkLive {
40public:
41 virtual void enqueue(InputSection *isec, uint64_t off) = 0;
42 virtual void addSym(Symbol *s) = 0;
43 virtual void markTransitively() = 0;
44 virtual ~MarkLive() = default;
45};
46
47// Sets `flag` and returns true if no other thread set it first.
48static bool tryClaim(bool &flag) {
49 std::atomic<bool> &atomicFlag = utils::atomicRef(x&: flag);
50 // Most claims find the flag already set, and the load lets those skip the
51 // more expensive atomic exchange.
52 return !atomicFlag.load(m: std::memory_order_relaxed) &&
53 !atomicFlag.exchange(i: true, m: std::memory_order_relaxed);
54}
55
56// Marks liveness on as many threads as are available. -why_live output is
57// deterministic only with --threads=1.
58template <bool RecordWhyLive> class MarkLiveImpl : public MarkLive {
59public:
60 // -why_live is a rarely used option, so we don't want support for that flag
61 // to slow down the main -dead_strip code path. As such, we employ templates
62 // to avoid the usage of WhyLiveEntry in the main code path. This saves us
63 // from needless allocations and pointer indirections.
64 using WorklistEntry =
65 std::conditional_t<RecordWhyLive, WhyLiveEntry, InputSection>;
66 using Worklist = SmallVector<WorklistEntry *, 0>;
67
68 void enqueue(InputSection *isec, uint64_t off) override {
69 enqueue(isec, off, nullptr, nextLevel);
70 }
71 void addSym(Symbol *s) override { addSym(s, nullptr, nextLevel); }
72 void markTransitively() override;
73
74private:
75 // Several threads call these at once, each passing its own worklist to
76 // receive the sections it claims.
77 void enqueue(InputSection *isec, uint64_t off, const WorklistEntry *prev,
78 Worklist &worklist) const;
79 // Most calls find `s` already claimed, so keep that check out from behind a
80 // call.
81 LLVM_ATTRIBUTE_ALWAYS_INLINE void addSym(Symbol *s, const WorklistEntry *prev,
82 Worklist &worklist) const;
83 void visitSymbol(Symbol *s, const WorklistEntry *prev,
84 Worklist &worklist) const;
85 void visit(WorklistEntry *entry, Worklist &worklist) const;
86 void drain();
87 const InputSection *getInputSection(const WorklistEntry *) const;
88 WorklistEntry *makeEntry(InputSection *, const WorklistEntry *prev) const;
89
90 // Sections that have been marked live and that the next level of drain() will
91 // visit. Literal sections cannot contain references to other sections, so we
92 // only store ConcatInputSections here.
93 Worklist nextLevel;
94};
95
96// Marks `isec` (at `off`) live. Only the thread whose claim succeeds queues a
97// section.
98template <bool RecordWhyLive>
99void MarkLiveImpl<RecordWhyLive>::enqueue(InputSection *isec, uint64_t off,
100 const WorklistEntry *prev,
101 Worklist &worklist) const {
102 if (auto *s = dyn_cast<ConcatInputSection>(Val: isec)) {
103 if (!tryClaim(flag&: s->live))
104 return;
105 assert(!s->isCoalescedWeak());
106 worklist.push_back(makeEntry(s, prev));
107 } else {
108 isec->markLive(off);
109 }
110}
111
112static void printWhyLive(const Symbol *s, const WhyLiveEntry *prev) {
113 std::string out = toString(*s) + " from " + toString(file: s->getFile());
114 int indent = 2;
115 for (const WhyLiveEntry *entry = prev; entry;
116 entry = entry->prev, indent += 2) {
117 const TinyPtrVector<Defined *> &symbols = entry->isec->symbols;
118 // With .subsections_with_symbols set, most isecs will have exactly one
119 // entry in their symbols vector, so we just print the first one.
120 if (!symbols.empty())
121 out += "\n" + std::string(indent, ' ') + toString(*symbols.front()) +
122 " from " + toString(file: symbols.front()->getFile());
123 }
124 message(msg: out);
125}
126
127template <bool RecordWhyLive>
128void MarkLiveImpl<RecordWhyLive>::addSym(Symbol *s, const WorklistEntry *prev,
129 Worklist &worklist) const {
130 if (tryClaim(flag&: s->used))
131 visitSymbol(s, prev, worklist);
132}
133
134// Marks what `s` keeps alive. Called by the thread that claimed `s`. This is
135// separate from addSym() because the class-stub edge makes it recursive, and
136// GCC won't always-inline a function that calls itself.
137template <bool RecordWhyLive>
138void MarkLiveImpl<RecordWhyLive>::visitSymbol(Symbol *s,
139 const WorklistEntry *prev,
140 Worklist &worklist) const {
141 if constexpr (RecordWhyLive)
142 if (!config->whyLive.empty() && config->whyLive.match(symbolName: s->getName()))
143 printWhyLive(s, prev);
144 if (auto *classSym = in.objcStubs->lookupClassSymbol(stubSym: s))
145 addSym(classSym, prev, worklist);
146 if (auto *d = dyn_cast<Defined>(Val: s)) {
147 if (d->isec())
148 enqueue(d->isec(), d->value, prev, worklist);
149 if (d->unwindEntry())
150 enqueue(d->unwindEntry(), 0, prev, worklist);
151 }
152}
153
154template <bool RecordWhyLive>
155void MarkLiveImpl<RecordWhyLive>::visit(WorklistEntry *entry,
156 Worklist &worklist) const {
157 // Entries that get placed onto the worklist always contain
158 // ConcatInputSections. `WhyLiveEntry::prev` may point to entries that
159 // contain other types of InputSections (due to S_ATTR_LIVE_SUPPORT), but
160 // those entries should never be pushed onto the worklist.
161 auto *isec = cast<ConcatInputSection>(getInputSection(entry));
162 assert(isec->isLive(0) && "We mark as live when pushing onto the worklist!");
163
164 // Mark all symbols listed in the relocation table for this section.
165 for (const Relocation &r : isec->relocs) {
166 if (auto *s = dyn_cast<Symbol *>(Val: r.referent))
167 addSym(s, entry, worklist);
168 else
169 enqueue(cast<InputSection *>(Val: r.referent), r.getAddend(), entry, worklist);
170 }
171 for (Defined *d : isec->symbols)
172 addSym(d, entry, worklist);
173}
174
175// Level-synchronous marking with depth-first workers and work sharing on idle.
176// Each level is a parallelFor round: workers claim chunks of the level and walk
177// depth-first for cache locality. Once one runs out of chunks, the others move
178// their stacks to the next level. The last join makes every live bit visible
179// to the live-support scan, which reads them with plain loads.
180template <bool RecordWhyLive> void MarkLiveImpl<RecordWhyLive>::drain() {
181 const size_t numThreads = parallel::getThreadCount();
182 // The minimum number of visits a worker makes in a level before it may hand
183 // back its stack. This keeps levels with fewer sections than workers from
184 // ending after a visit or two, which would result in a lot of fork-join
185 // overhead.
186 constexpr size_t minVisitsPerLevel = 256;
187 Worklist level;
188 level.reserve(nextLevel.size());
189 while (!nextLevel.empty()) {
190 level.clear();
191 std::swap(level, nextLevel);
192 std::mutex nextLevelMutex;
193 std::atomic<bool> anyWorkerIdle{false};
194 size_t chunkSize =
195 std::clamp<size_t>(level.size() / (4 * numThreads), 1, 64);
196 // Each worker starts with the chunk at its own index and then claims the
197 // chunks after the first numThreads.
198 std::atomic<size_t> next{numThreads * chunkSize};
199 parallelFor(0, numThreads, [&](size_t shard) {
200 Worklist stack;
201 size_t visited = 0;
202 for (size_t begin = shard * chunkSize, end = level.size(); begin < end;
203 begin = next.fetch_add(i: chunkSize, m: std::memory_order_relaxed)) {
204 size_t chunkEnd = std::min(a: begin + chunkSize, b: end);
205 stack.append(level.begin() + begin, level.begin() + chunkEnd);
206 while (!stack.empty()) {
207 visit(entry: stack.pop_back_val(), worklist&: stack);
208 if (++visited >= minVisitsPerLevel && !stack.empty() &&
209 anyWorkerIdle.load(m: std::memory_order_relaxed)) {
210 std::lock_guard<std::mutex> lock(nextLevelMutex);
211 nextLevel.append(stack);
212 stack.clear();
213 }
214 }
215 }
216 anyWorkerIdle.store(i: true, m: std::memory_order_relaxed);
217 });
218 }
219}
220
221template <bool RecordWhyLive>
222const InputSection *MarkLiveImpl<RecordWhyLive>::getInputSection(
223 const MarkLiveImpl<RecordWhyLive>::WorklistEntry *entry) const {
224 if constexpr (RecordWhyLive)
225 return entry->isec;
226 else
227 return entry;
228}
229
230template <bool RecordWhyLive>
231typename MarkLiveImpl<RecordWhyLive>::WorklistEntry *
232MarkLiveImpl<RecordWhyLive>::makeEntry(
233 InputSection *isec,
234 const MarkLiveImpl<RecordWhyLive>::WorklistEntry *prev) const {
235 if constexpr (RecordWhyLive) {
236 if (!isec) {
237 assert(!prev);
238 return nullptr;
239 }
240 return makeThreadLocal<WhyLiveEntry>(isec, prev);
241 } else {
242 return isec;
243 }
244}
245
246template <bool RecordWhyLive>
247void MarkLiveImpl<RecordWhyLive>::markTransitively() {
248 do {
249 // Mark things reachable from GC roots as live.
250 drain();
251
252 // S_ATTR_LIVE_SUPPORT sections are live if they point _to_ a live
253 // section. Process them in a second pass.
254 for (ConcatInputSection *isec : inputSections) {
255 // FIXME: Check if copying all S_ATTR_LIVE_SUPPORT sections into a
256 // separate vector and only walking that here is faster.
257 if (!(isec->getFlags() & S_ATTR_LIVE_SUPPORT) || isec->live)
258 continue;
259
260 for (const Relocation &r : isec->relocs) {
261 if (auto *s = dyn_cast<Symbol *>(Val: r.referent)) {
262 if (s->isLive()) {
263 InputSection *referentIsec = nullptr;
264 if (auto *d = dyn_cast<Defined>(Val: s))
265 referentIsec = d->isec();
266 enqueue(isec, 0, makeEntry(isec: referentIsec, prev: nullptr), nextLevel);
267 }
268 } else {
269 auto *referentIsec = cast<InputSection *>(Val: r.referent);
270 if (referentIsec->isLive(off: r.getAddend()))
271 enqueue(isec, 0, makeEntry(isec: referentIsec, prev: nullptr), nextLevel);
272 }
273 }
274 }
275
276 // S_ATTR_LIVE_SUPPORT could have marked additional sections live,
277 // which in turn could mark additional S_ATTR_LIVE_SUPPORT sections live.
278 // Iterate. In practice, the second iteration won't mark additional
279 // S_ATTR_LIVE_SUPPORT sections live.
280 } while (!nextLevel.empty());
281}
282
283// Set live bit on for each reachable chunk. Unmarked (unreachable)
284// InputSections will be ignored by Writer, so they will be excluded
285// from the final output.
286void markLive() {
287 TimeTraceScope timeScope("markLive");
288 MarkLive *marker;
289 if (config->whyLive.empty())
290 marker = make<MarkLiveImpl<false>>();
291 else
292 marker = make<MarkLiveImpl<true>>();
293 // Add GC roots.
294 if (config->entry)
295 marker->addSym(s: config->entry);
296 for (Symbol *sym : symtab->getSymbols()) {
297 if (auto *defined = dyn_cast<Defined>(Val: sym)) {
298 // -exported_symbol(s_list)
299 if (!config->exportedSymbols.empty() &&
300 config->exportedSymbols.match(symbolName: defined->getName())) {
301 // NOTE: Even though exporting private externs is an ill-defined
302 // operation, we are purposely not checking for privateExtern in
303 // order to follow ld64's behavior of treating all exported private
304 // extern symbols as live, irrespective of whether they are autohide.
305 marker->addSym(s: defined);
306 continue;
307 }
308
309 // public symbols explicitly marked .no_dead_strip
310 if (defined->referencedDynamically || defined->noDeadStrip) {
311 marker->addSym(s: defined);
312 continue;
313 }
314
315 // FIXME: When we implement these flags, make symbols from them GC
316 // roots:
317 // * -reexported_symbol(s_list)
318 // * -alias_list
319 // * -init
320
321 // In dylibs and bundles and in executables with -export_dynamic,
322 // all external functions are GC roots.
323 bool externsAreRoots =
324 config->outputType != MH_EXECUTE || config->exportDynamic;
325 if (externsAreRoots && !defined->privateExtern) {
326 marker->addSym(s: defined);
327 continue;
328 }
329 }
330 }
331 // -u symbols
332 for (Symbol *sym : config->explicitUndefineds)
333 marker->addSym(s: sym);
334 // local symbols explicitly marked .no_dead_strip
335 for (const InputFile *file : inputFiles)
336 if (auto *objFile = dyn_cast<ObjFile>(Val: file))
337 for (Symbol *sym : objFile->symbols)
338 if (auto *defined = dyn_cast_or_null<Defined>(Val: sym))
339 if (!defined->isExternal() && defined->noDeadStrip)
340 marker->addSym(s: defined);
341 if (auto *stubBinder =
342 dyn_cast_or_null<DylibSymbol>(Val: symtab->find(name: "dyld_stub_binder")))
343 marker->addSym(s: stubBinder);
344 for (ConcatInputSection *isec : inputSections) {
345 // Sections marked no_dead_strip
346 if (isec->getFlags() & S_ATTR_NO_DEAD_STRIP) {
347 marker->enqueue(isec, off: 0);
348 continue;
349 }
350
351 // mod_init_funcs, mod_term_funcs sections
352 if (sectionType(flags: isec->getFlags()) == S_MOD_INIT_FUNC_POINTERS ||
353 sectionType(flags: isec->getFlags()) == S_MOD_TERM_FUNC_POINTERS) {
354 assert(!config->emitInitOffsets ||
355 sectionType(isec->getFlags()) != S_MOD_INIT_FUNC_POINTERS);
356 marker->enqueue(isec, off: 0);
357 continue;
358 }
359 }
360
361 for (ConcatInputSection *isec : in.initOffsets->inputs())
362 marker->enqueue(isec, off: 0);
363
364 marker->markTransitively();
365}
366
367} // namespace lld::macho
368