283 lines · cpp
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-exception6//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 liveness34// 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 flag46 // to slow down the main -dead_strip code path. As such, we employ templates47 // to avoid the usage of WhyLiveEntry in the main code path. This saves us48 // 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. We65 // only push into the worklist when we discover an unmarked section, and we66 // mark as we push, so sections never appear twice in the list. Literal67 // sections cannot contain references to other sections, so we only store68 // 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>(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(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 one92 // 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(symbols.front()->getFile());96 }97 message(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(s->getName()))109 printWhyLive(s, prev);110 if (auto *d = dyn_cast<Defined>(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 else124 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 contain150 // ConcatInputSections. `WhyLiveEntry::prev` may point to entries that151 // contain other types of InputSections (due to S_ATTR_LIVE_SUPPORT), but152 // 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 else161 enqueue(cast<InputSection *>(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 live168 // section. Process them in a second pass.169 for (ConcatInputSection *isec : inputSections) {170 // FIXME: Check if copying all S_ATTR_LIVE_SUPPORT sections into a171 // 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>(s))180 referentIsec = d->isec();181 enqueue(isec, 0, makeEntry(referentIsec, nullptr));182 }183 } else {184 auto *referentIsec = cast<InputSection *>(r.referent);185 if (referentIsec->isLive(r.addend))186 enqueue(isec, 0, makeEntry(referentIsec, 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 additional194 // 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 excluded200// from the final output.201void markLive() {202 TimeTraceScope timeScope("markLive");203 MarkLive *marker;204 if (config->whyLive.empty())205 marker = make<MarkLiveImpl<false>>();206 else207 marker = make<MarkLiveImpl<true>>();208 // Add GC roots.209 if (config->entry)210 marker->addSym(config->entry);211 for (Symbol *sym : symtab->getSymbols()) {212 if (auto *defined = dyn_cast<Defined>(sym)) {213 // -exported_symbol(s_list)214 if (!config->exportedSymbols.empty() &&215 config->exportedSymbols.match(defined->getName())) {216 // NOTE: Even though exporting private externs is an ill-defined217 // operation, we are purposely not checking for privateExtern in218 // order to follow ld64's behavior of treating all exported private219 // extern symbols as live, irrespective of whether they are autohide.220 marker->addSym(defined);221 continue;222 }223 224 // public symbols explicitly marked .no_dead_strip225 if (defined->referencedDynamically || defined->noDeadStrip) {226 marker->addSym(defined);227 continue;228 }229 230 // FIXME: When we implement these flags, make symbols from them GC231 // roots:232 // * -reexported_symbol(s_list)233 // * -alias_list234 // * -init235 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(defined);242 continue;243 }244 }245 }246 // -u symbols247 for (Symbol *sym : config->explicitUndefineds)248 marker->addSym(sym);249 // local symbols explicitly marked .no_dead_strip250 for (const InputFile *file : inputFiles)251 if (auto *objFile = dyn_cast<ObjFile>(file))252 for (Symbol *sym : objFile->symbols)253 if (auto *defined = dyn_cast_or_null<Defined>(sym))254 if (!defined->isExternal() && defined->noDeadStrip)255 marker->addSym(defined);256 if (auto *stubBinder =257 dyn_cast_or_null<DylibSymbol>(symtab->find("dyld_stub_binder")))258 marker->addSym(stubBinder);259 for (ConcatInputSection *isec : inputSections) {260 // Sections marked no_dead_strip261 if (isec->getFlags() & S_ATTR_NO_DEAD_STRIP) {262 marker->enqueue(isec, 0);263 continue;264 }265 266 // mod_init_funcs, mod_term_funcs sections267 if (sectionType(isec->getFlags()) == S_MOD_INIT_FUNC_POINTERS ||268 sectionType(isec->getFlags()) == S_MOD_TERM_FUNC_POINTERS) {269 assert(!config->emitInitOffsets ||270 sectionType(isec->getFlags()) != S_MOD_INIT_FUNC_POINTERS);271 marker->enqueue(isec, 0);272 continue;273 }274 }275 276 for (ConcatInputSection *isec : in.initOffsets->inputs())277 marker->enqueue(isec, 0);278 279 marker->markTransitively();280}281 282} // namespace lld::macho283