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 {
  19 namespace macho {
  20
  21 using namespace llvm;
  22 using namespace llvm::MachO;
  23
  24 // Set live bit on for each reachable chunk. Unmarked (unreachable)
  25 // InputSections will be ignored by Writer, so they will be excluded
  26 // from the final output.
  27 void markLive() {
  28   TimeTraceScope timeScope("markLive");
  29
  30   // We build up a worklist of sections which have been marked as live. We only
  31   // push into the worklist when we discover an unmarked section, and we mark
  32   // as we push, so sections never appear twice in the list.
  33   // Literal sections cannot contain references to other sections, so we only
  34   // store ConcatInputSections in our worklist.
  35   SmallVector<ConcatInputSection *, 256> worklist;
  36
  37   auto enqueue = [&](InputSection *isec, uint64_t off) {
  38     if (isec->isLive(off))
  39       return;
  40     isec->markLive(off);
  41     if (auto s = dyn_cast<ConcatInputSection>(isec)) {
  42       assert(!s->isCoalescedWeak());
  43       worklist.push_back(s);
  44     }
  45   };
  46
  47   auto addSym = [&](Symbol *s) {
  48     s->used = true;
  49     if (auto *d = dyn_cast<Defined>(s))
  50       if (d->isec)
  51         enqueue(d->isec, d->value);
  52   };
  53
  54   // Add GC roots.
  55   if (config->entry)
  56     addSym(config->entry);
  57   for (Symbol *sym : symtab->getSymbols()) {
  58     if (auto *defined = dyn_cast<Defined>(sym)) {
  59       // -exported_symbol(s_list)
  60       if (!config->exportedSymbols.empty() &&
  61           config->exportedSymbols.match(defined->getName())) {
  62         // FIXME: Instead of doing this here, maybe the Driver code doing
  63         // the matching should add them to explicitUndefineds? Then the
  64         // explicitUndefineds code below would handle this automatically.
  65         assert(!defined->privateExtern &&
  66                "should have been rejected by driver");
  67         addSym(defined);
  68         continue;
  69       }
  70
  71       // public symbols explicitly marked .no_dead_strip
  72       if (defined->referencedDynamically || defined->noDeadStrip) {
  73         addSym(defined);
  74         continue;
  75       }
  76
  77       // FIXME: When we implement these flags, make symbols from them GC roots:
  78       // * -reexported_symbol(s_list)
  79       // * -alias(-list)
  80       // * -init
  81
  82       // In dylibs and bundles and in executables with -export_dynamic,
  83       // all external functions are GC roots.
  84       bool externsAreRoots =
  85           config->outputType != MH_EXECUTE || config->exportDynamic;
  86       if (externsAreRoots && !defined->privateExtern) {
  87         addSym(defined);
  88         continue;
  89       }
  90     }
  91   }
  92   // -u symbols
  93   for (Symbol *sym : config->explicitUndefineds)
  94     if (auto *defined = dyn_cast<Defined>(sym))
  95       addSym(defined);
  96   // local symbols explicitly marked .no_dead_strip
  97   for (const InputFile *file : inputFiles)
  98     if (auto *objFile = dyn_cast<ObjFile>(file))
  99       for (Symbol *sym : objFile->symbols)
 100         if (auto *defined = dyn_cast_or_null<Defined>(sym))
 101           if (!defined->isExternal() && defined->noDeadStrip)
 102             addSym(defined);
 103   if (auto *stubBinder =
 104           dyn_cast_or_null<DylibSymbol>(symtab->find("dyld_stub_binder")))
 105     addSym(stubBinder);
 106   for (ConcatInputSection *isec : inputSections) {
 107     // Sections marked no_dead_strip
 108     if (isec->getFlags() & S_ATTR_NO_DEAD_STRIP) {
 109       enqueue(isec, 0);
 110       continue;
 111     }
 112
 113     // mod_init_funcs, mod_term_funcs sections
 114     if (sectionType(isec->getFlags()) == S_MOD_INIT_FUNC_POINTERS ||
 115         sectionType(isec->getFlags()) == S_MOD_TERM_FUNC_POINTERS) {
 116       enqueue(isec, 0);
 117       continue;
 118     }
 119   }
 120
 121   // Dead strip runs before UnwindInfoSection handling so we need to keep
 122   // __LD,__compact_unwind alive here.
 123   // But that section contains absolute references to __TEXT,__text and
 124   // keeps most code alive due to that. So we can't just enqueue() the
 125   // section: We must skip the relocations for the functionAddress
 126   // in each CompactUnwindEntry.
 127   // See also scanEhFrameSection() in lld/ELF/MarkLive.cpp.
 128   for (ConcatInputSection *isec : in.unwindInfo->getInputs()) {
 129     isec->live = true;
 130     const int compactUnwindEntrySize =
 131         target->wordSize == 8 ? sizeof(CompactUnwindEntry<uint64_t>)
 132                               : sizeof(CompactUnwindEntry<uint32_t>);
 133     for (const Reloc &r : isec->relocs) {
 134       // This is the relocation for the address of the function itself.
 135       // Ignore it, else these would keep everything alive.
 136       if (r.offset % compactUnwindEntrySize == 0)
 137         continue;
 138
 139       if (auto *s = r.referent.dyn_cast<Symbol *>())
 140         addSym(s);
 141       else
 142         enqueue(r.referent.get<InputSection *>(), r.addend);
 143     }
 144   }
 145
 146   do {
 147     // Mark things reachable from GC roots as live.
 148     while (!worklist.empty()) {
 149       ConcatInputSection *s = worklist.pop_back_val();
 150       assert(s->live && "We mark as live when pushing onto the worklist!");
 151
 152       // Mark all symbols listed in the relocation table for this section.
 153       for (const Reloc &r : s->relocs) {
 154         if (auto *s = r.referent.dyn_cast<Symbol *>())
 155           addSym(s);
 156         else
 157           enqueue(r.referent.get<InputSection *>(), r.addend);
 158       }
 159     }
 160
 161     // S_ATTR_LIVE_SUPPORT sections are live if they point _to_ a live section.
 162     // Process them in a second pass.
 163     for (ConcatInputSection *isec : inputSections) {
 164       // FIXME: Check if copying all S_ATTR_LIVE_SUPPORT sections into a
 165       // separate vector and only walking that here is faster.
 166       if (!(isec->getFlags() & S_ATTR_LIVE_SUPPORT) || isec->live)
 167         continue;
 168
 169       for (const Reloc &r : isec->relocs) {
 170         bool referentLive;
 171         if (auto *s = r.referent.dyn_cast<Symbol *>())
 172           referentLive = s->isLive();
 173         else
 174           referentLive = r.referent.get<InputSection *>()->isLive(r.addend);
 175         if (referentLive)
 176           enqueue(isec, 0);
 177       }
 178     }
 179
 180     // S_ATTR_LIVE_SUPPORT could have marked additional sections live,
 181     // which in turn could mark additional S_ATTR_LIVE_SUPPORT sections live.
 182     // Iterate. In practice, the second iteration won't mark additional
 183     // S_ATTR_LIVE_SUPPORT sections live.
 184   } while (!worklist.empty());
 185 }
 186
 187 } // namespace macho
 188 } // namespace lld