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