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 "UnwindInfoSection.h" |
15 | |
16 | #include "lld/Common/ErrorHandler.h" |
17 | #include "llvm/Support/TimeProfiler.h" |
18 | |
19 | namespace lld::macho { |
20 | |
21 | using namespace llvm; |
22 | using namespace llvm::MachO; |
23 | |
24 | struct WhyLiveEntry { |
25 | InputSection *isec; |
26 | // Keep track of the entry that caused us to mark `isec` as live. |
27 | const WhyLiveEntry *prev; |
28 | |
29 | WhyLiveEntry(InputSection *isec, const WhyLiveEntry *prev) |
30 | : isec(isec), prev(prev) {} |
31 | }; |
32 | |
33 | // Type-erased interface to MarkLiveImpl. Used for adding roots to the liveness |
34 | // graph. |
35 | class MarkLive { |
36 | public: |
37 | virtual void enqueue(InputSection *isec, uint64_t off) = 0; |
38 | virtual void addSym(Symbol *s) = 0; |
39 | virtual void markTransitively() = 0; |
40 | virtual ~MarkLive() = default; |
41 | }; |
42 | |
43 | template <bool RecordWhyLive> class MarkLiveImpl : public MarkLive { |
44 | public: |
45 | // -why_live is a rarely used option, so we don't want support for that flag |
46 | // to slow down the main -dead_strip code path. As such, we employ templates |
47 | // to avoid the usage of WhyLiveEntry in the main code path. This saves us |
48 | // from needless allocations and pointer indirections. |
49 | using WorklistEntry = |
50 | std::conditional_t<RecordWhyLive, WhyLiveEntry, InputSection>; |
51 | |
52 | void enqueue(InputSection *isec, uint64_t off) override { |
53 | enqueue(isec, off, nullptr); |
54 | } |
55 | void addSym(Symbol *s) override { addSym(s, nullptr); } |
56 | void markTransitively() override; |
57 | |
58 | private: |
59 | void enqueue(InputSection *isec, uint64_t off, const WorklistEntry *prev); |
60 | void addSym(Symbol *s, const WorklistEntry *prev); |
61 | const InputSection *getInputSection(const WorklistEntry *) const; |
62 | WorklistEntry *makeEntry(InputSection *, const WorklistEntry *prev) const; |
63 | |
64 | // We build up a worklist of sections which have been marked as live. We |
65 | // only push into the worklist when we discover an unmarked section, and we |
66 | // mark as we push, so sections never appear twice in the list. Literal |
67 | // sections cannot contain references to other sections, so we only store |
68 | // ConcatInputSections in our worklist. |
69 | SmallVector<WorklistEntry *, 256> worklist; |
70 | }; |
71 | |
72 | template <bool RecordWhyLive> |
73 | void MarkLiveImpl<RecordWhyLive>::enqueue( |
74 | InputSection *isec, uint64_t off, |
75 | const typename MarkLiveImpl<RecordWhyLive>::WorklistEntry *prev) { |
76 | if (isec->isLive(off)) |
77 | return; |
78 | isec->markLive(off); |
79 | if (auto s = dyn_cast<ConcatInputSection>(Val: isec)) { |
80 | assert(!s->isCoalescedWeak()); |
81 | worklist.push_back(makeEntry(s, prev)); |
82 | } |
83 | } |
84 | |
85 | static void printWhyLive(const Symbol *s, const WhyLiveEntry *prev) { |
86 | std::string out = toString(*s) + " from " + toString(file: s->getFile()); |
87 | int indent = 2; |
88 | for (const WhyLiveEntry *entry = prev; entry; |
89 | entry = entry->prev, indent += 2) { |
90 | const TinyPtrVector<Defined *> &symbols = entry->isec->symbols; |
91 | // With .subsections_with_symbols set, most isecs will have exactly one |
92 | // entry in their symbols vector, so we just print the first one. |
93 | if (!symbols.empty()) |
94 | out += "\n" + std::string(indent, ' ') + toString(*symbols.front()) + |
95 | " from " + toString(file: symbols.front()->getFile()); |
96 | } |
97 | message(msg: out); |
98 | } |
99 | |
100 | template <bool RecordWhyLive> |
101 | void MarkLiveImpl<RecordWhyLive>::addSym( |
102 | Symbol *s, |
103 | const typename MarkLiveImpl<RecordWhyLive>::WorklistEntry *prev) { |
104 | if (s->used) |
105 | return; |
106 | s->used = true; |
107 | if constexpr (RecordWhyLive) |
108 | if (!config->whyLive.empty() && config->whyLive.match(symbolName: s->getName())) |
109 | printWhyLive(s, prev); |
110 | if (auto *d = dyn_cast<Defined>(Val: s)) { |
111 | if (d->isec()) |
112 | enqueue(d->isec(), d->value, prev); |
113 | if (d->unwindEntry()) |
114 | enqueue(d->unwindEntry(), 0, prev); |
115 | } |
116 | } |
117 | |
118 | template <bool RecordWhyLive> |
119 | const InputSection *MarkLiveImpl<RecordWhyLive>::getInputSection( |
120 | const MarkLiveImpl<RecordWhyLive>::WorklistEntry *entry) const { |
121 | if constexpr (RecordWhyLive) |
122 | return entry->isec; |
123 | else |
124 | return entry; |
125 | } |
126 | |
127 | template <bool RecordWhyLive> |
128 | typename MarkLiveImpl<RecordWhyLive>::WorklistEntry * |
129 | MarkLiveImpl<RecordWhyLive>::makeEntry( |
130 | InputSection *isec, |
131 | const MarkLiveImpl<RecordWhyLive>::WorklistEntry *prev) const { |
132 | if constexpr (RecordWhyLive) { |
133 | if (!isec) { |
134 | assert(!prev); |
135 | return nullptr; |
136 | } |
137 | return make<WhyLiveEntry>(isec, prev); |
138 | } else { |
139 | return isec; |
140 | } |
141 | } |
142 | |
143 | template <bool RecordWhyLive> |
144 | void MarkLiveImpl<RecordWhyLive>::markTransitively() { |
145 | do { |
146 | // Mark things reachable from GC roots as live. |
147 | while (!worklist.empty()) { |
148 | WorklistEntry *entry = worklist.pop_back_val(); |
149 | // Entries that get placed onto the worklist always contain |
150 | // ConcatInputSections. `WhyLiveEntry::prev` may point to entries that |
151 | // contain other types of InputSections (due to S_ATTR_LIVE_SUPPORT), but |
152 | // those entries should never be pushed onto the worklist. |
153 | auto *isec = cast<ConcatInputSection>(getInputSection(entry)); |
154 | assert(isec->live && "We mark as live when pushing onto the worklist!" ); |
155 | |
156 | // Mark all symbols listed in the relocation table for this section. |
157 | for (const Reloc &r : isec->relocs) { |
158 | if (auto *s = r.referent.dyn_cast<Symbol *>()) |
159 | addSym(s, entry); |
160 | else |
161 | enqueue(cast<InputSection *>(Val: r.referent), r.addend, entry); |
162 | } |
163 | for (Defined *d : getInputSection(entry)->symbols) |
164 | addSym(d, entry); |
165 | } |
166 | |
167 | // S_ATTR_LIVE_SUPPORT sections are live if they point _to_ a live |
168 | // section. Process them in a second pass. |
169 | for (ConcatInputSection *isec : inputSections) { |
170 | // FIXME: Check if copying all S_ATTR_LIVE_SUPPORT sections into a |
171 | // separate vector and only walking that here is faster. |
172 | if (!(isec->getFlags() & S_ATTR_LIVE_SUPPORT) || isec->live) |
173 | continue; |
174 | |
175 | for (const Reloc &r : isec->relocs) { |
176 | if (auto *s = r.referent.dyn_cast<Symbol *>()) { |
177 | if (s->isLive()) { |
178 | InputSection *referentIsec = nullptr; |
179 | if (auto *d = dyn_cast<Defined>(Val: s)) |
180 | referentIsec = d->isec(); |
181 | enqueue(isec, 0, makeEntry(isec: referentIsec, prev: nullptr)); |
182 | } |
183 | } else { |
184 | auto *referentIsec = cast<InputSection *>(Val: r.referent); |
185 | if (referentIsec->isLive(off: r.addend)) |
186 | enqueue(isec, 0, makeEntry(isec: referentIsec, prev: nullptr)); |
187 | } |
188 | } |
189 | } |
190 | |
191 | // S_ATTR_LIVE_SUPPORT could have marked additional sections live, |
192 | // which in turn could mark additional S_ATTR_LIVE_SUPPORT sections live. |
193 | // Iterate. In practice, the second iteration won't mark additional |
194 | // S_ATTR_LIVE_SUPPORT sections live. |
195 | } while (!worklist.empty()); |
196 | } |
197 | |
198 | // Set live bit on for each reachable chunk. Unmarked (unreachable) |
199 | // InputSections will be ignored by Writer, so they will be excluded |
200 | // from the final output. |
201 | void markLive() { |
202 | TimeTraceScope timeScope("markLive" ); |
203 | MarkLive *marker; |
204 | if (config->whyLive.empty()) |
205 | marker = make<MarkLiveImpl<false>>(); |
206 | else |
207 | marker = make<MarkLiveImpl<true>>(); |
208 | // Add GC roots. |
209 | if (config->entry) |
210 | marker->addSym(s: config->entry); |
211 | for (Symbol *sym : symtab->getSymbols()) { |
212 | if (auto *defined = dyn_cast<Defined>(Val: sym)) { |
213 | // -exported_symbol(s_list) |
214 | if (!config->exportedSymbols.empty() && |
215 | config->exportedSymbols.match(symbolName: defined->getName())) { |
216 | // NOTE: Even though exporting private externs is an ill-defined |
217 | // operation, we are purposely not checking for privateExtern in |
218 | // order to follow ld64's behavior of treating all exported private |
219 | // extern symbols as live, irrespective of whether they are autohide. |
220 | marker->addSym(s: defined); |
221 | continue; |
222 | } |
223 | |
224 | // public symbols explicitly marked .no_dead_strip |
225 | if (defined->referencedDynamically || defined->noDeadStrip) { |
226 | marker->addSym(s: defined); |
227 | continue; |
228 | } |
229 | |
230 | // FIXME: When we implement these flags, make symbols from them GC |
231 | // roots: |
232 | // * -reexported_symbol(s_list) |
233 | // * -alias_list |
234 | // * -init |
235 | |
236 | // In dylibs and bundles and in executables with -export_dynamic, |
237 | // all external functions are GC roots. |
238 | bool externsAreRoots = |
239 | config->outputType != MH_EXECUTE || config->exportDynamic; |
240 | if (externsAreRoots && !defined->privateExtern) { |
241 | marker->addSym(s: defined); |
242 | continue; |
243 | } |
244 | } |
245 | } |
246 | // -u symbols |
247 | for (Symbol *sym : config->explicitUndefineds) |
248 | marker->addSym(s: sym); |
249 | // local symbols explicitly marked .no_dead_strip |
250 | for (const InputFile *file : inputFiles) |
251 | if (auto *objFile = dyn_cast<ObjFile>(Val: file)) |
252 | for (Symbol *sym : objFile->symbols) |
253 | if (auto *defined = dyn_cast_or_null<Defined>(Val: sym)) |
254 | if (!defined->isExternal() && defined->noDeadStrip) |
255 | marker->addSym(s: defined); |
256 | if (auto *stubBinder = |
257 | dyn_cast_or_null<DylibSymbol>(Val: symtab->find(name: "dyld_stub_binder" ))) |
258 | marker->addSym(s: stubBinder); |
259 | for (ConcatInputSection *isec : inputSections) { |
260 | // Sections marked no_dead_strip |
261 | if (isec->getFlags() & S_ATTR_NO_DEAD_STRIP) { |
262 | marker->enqueue(isec, off: 0); |
263 | continue; |
264 | } |
265 | |
266 | // mod_init_funcs, mod_term_funcs sections |
267 | if (sectionType(flags: isec->getFlags()) == S_MOD_INIT_FUNC_POINTERS || |
268 | sectionType(flags: isec->getFlags()) == S_MOD_TERM_FUNC_POINTERS) { |
269 | assert(!config->emitInitOffsets || |
270 | sectionType(isec->getFlags()) != S_MOD_INIT_FUNC_POINTERS); |
271 | marker->enqueue(isec, off: 0); |
272 | continue; |
273 | } |
274 | } |
275 | |
276 | for (ConcatInputSection *isec : in.initOffsets->inputs()) |
277 | marker->enqueue(isec, off: 0); |
278 | |
279 | marker->markTransitively(); |
280 | } |
281 | |
282 | } // namespace lld::macho |
283 | |