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, all external functions are GC roots.
83       // FIXME: -export_dynamic should enable this for executables too.
84       if (config->outputType != MH_EXECUTE && !defined->privateExtern) {
85         addSym(defined);
86         continue;
87       }
88     }
89   }
90   // -u symbols
91   for (Symbol *sym : config->explicitUndefineds)
92     if (auto *defined = dyn_cast<Defined>(sym))
93       addSym(defined);
94   // local symbols explicitly marked .no_dead_strip
95   for (const InputFile *file : inputFiles)
96     if (auto *objFile = dyn_cast<ObjFile>(file))
97       for (Symbol *sym : objFile->symbols)
98         if (auto *defined = dyn_cast_or_null<Defined>(sym))
99           if (!defined->isExternal() && defined->noDeadStrip)
100             addSym(defined);
101   if (auto *stubBinder =
102           dyn_cast_or_null<DylibSymbol>(symtab->find("dyld_stub_binder")))
103     addSym(stubBinder);
104   for (InputSection *isec : inputSections) {
105     // Sections marked no_dead_strip
106     if (isec->flags & S_ATTR_NO_DEAD_STRIP) {
107       assert(isa<ConcatInputSection>(isec));
108       enqueue(isec, 0);
109       continue;
110     }
111 
112     // mod_init_funcs, mod_term_funcs sections
113     if (sectionType(isec->flags) == S_MOD_INIT_FUNC_POINTERS ||
114         sectionType(isec->flags) == S_MOD_TERM_FUNC_POINTERS) {
115       assert(isa<ConcatInputSection>(isec));
116       enqueue(isec, 0);
117       continue;
118     }
119 
120     // Dead strip runs before UnwindInfoSection handling so we need to keep
121     // __LD,__compact_unwind alive here.
122     // But that section contains absolute references to __TEXT,__text and
123     // keeps most code alive due to that. So we can't just enqueue() the
124     // section: We must skip the relocations for the functionAddress
125     // in each CompactUnwindEntry.
126     // See also scanEhFrameSection() in lld/ELF/MarkLive.cpp.
127     if (isec->segname == segment_names::ld &&
128         isec->name == section_names::compactUnwind) {
129       auto concatIsec = cast<ConcatInputSection>(isec);
130       concatIsec->live = true;
131       const int compactUnwindEntrySize =
132           target->wordSize == 8 ? sizeof(CompactUnwindEntry<uint64_t>)
133                                 : sizeof(CompactUnwindEntry<uint32_t>);
134       for (const Reloc &r : isec->relocs) {
135         // This is the relocation for the address of the function itself.
136         // Ignore it, else these would keep everything alive.
137         if (r.offset % compactUnwindEntrySize == 0)
138           continue;
139 
140         if (auto *s = r.referent.dyn_cast<Symbol *>())
141           addSym(s);
142         else
143           enqueue(r.referent.get<InputSection *>(), r.addend);
144       }
145       continue;
146     }
147   }
148 
149   do {
150     // Mark things reachable from GC roots as live.
151     while (!worklist.empty()) {
152       ConcatInputSection *s = worklist.pop_back_val();
153       assert(s->live && "We mark as live when pushing onto the worklist!");
154 
155       // Mark all symbols listed in the relocation table for this section.
156       for (const Reloc &r : s->relocs) {
157         if (auto *s = r.referent.dyn_cast<Symbol *>())
158           addSym(s);
159         else
160           enqueue(r.referent.get<InputSection *>(), r.addend);
161       }
162     }
163 
164     // S_ATTR_LIVE_SUPPORT sections are live if they point _to_ a live section.
165     // Process them in a second pass.
166     for (InputSection *isec : inputSections) {
167       if (!isa<ConcatInputSection>(isec))
168         continue;
169       auto concatIsec = cast<ConcatInputSection>(isec);
170       // FIXME: Check if copying all S_ATTR_LIVE_SUPPORT sections into a
171       // separate vector and only walking that here is faster.
172       if (!(concatIsec->flags & S_ATTR_LIVE_SUPPORT) || concatIsec->live)
173         continue;
174 
175       for (const Reloc &r : isec->relocs) {
176         bool referentLive;
177         if (auto *s = r.referent.dyn_cast<Symbol *>())
178           referentLive = s->isLive();
179         else
180           referentLive = r.referent.get<InputSection *>()->isLive(r.addend);
181         if (referentLive)
182           enqueue(isec, 0);
183       }
184     }
185 
186     // S_ATTR_LIVE_SUPPORT could have marked additional sections live,
187     // which in turn could mark additional S_ATTR_LIVE_SUPPORT sections live.
188     // Iterate. In practice, the second iteration won't mark additional
189     // S_ATTR_LIVE_SUPPORT sections live.
190   } while (!worklist.empty());
191 }
192 
193 } // namespace macho
194 } // namespace lld
195