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