| 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 | |
| 23 | namespace lld::macho { |
| 24 | |
| 25 | using namespace llvm; |
| 26 | using namespace llvm::MachO; |
| 27 | |
| 28 | struct 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. |
| 39 | class MarkLive { |
| 40 | public: |
| 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. |
| 48 | static 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. |
| 58 | template <bool RecordWhyLive> class MarkLiveImpl : public MarkLive { |
| 59 | public: |
| 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 | |
| 74 | private: |
| 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. |
| 98 | template <bool RecordWhyLive> |
| 99 | void 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 | |
| 112 | static 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 | |
| 127 | template <bool RecordWhyLive> |
| 128 | void 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. |
| 137 | template <bool RecordWhyLive> |
| 138 | void 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 | |
| 154 | template <bool RecordWhyLive> |
| 155 | void 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. |
| 180 | template <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 | |
| 221 | template <bool RecordWhyLive> |
| 222 | const 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 | |
| 230 | template <bool RecordWhyLive> |
| 231 | typename MarkLiveImpl<RecordWhyLive>::WorklistEntry * |
| 232 | MarkLiveImpl<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 | |
| 246 | template <bool RecordWhyLive> |
| 247 | void 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. |
| 286 | void 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 | |