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 189