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
19namespace lld::macho {
20
21using namespace llvm;
22using namespace llvm::MachO;
23
24struct 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.
35class MarkLive {
36public:
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
43template <bool RecordWhyLive> class MarkLiveImpl : public MarkLive {
44public:
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
58private:
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
72template <bool RecordWhyLive>
73void 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
85static 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
100template <bool RecordWhyLive>
101void 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
118template <bool RecordWhyLive>
119const 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
127template <bool RecordWhyLive>
128typename MarkLiveImpl<RecordWhyLive>::WorklistEntry *
129MarkLiveImpl<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
143template <bool RecordWhyLive>
144void 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.
201void 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