1 //===- MarkLive.cpp -------------------------------------------------------===//
2 //
3 // The LLVM Linker
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements --gc-sections, which is a feature to remove unused
11 // sections from output. Unused sections are sections that are not reachable
12 // from known GC-root symbols or sections. Naturally the feature is
13 // implemented as a mark-sweep garbage collector.
14 //
15 // Here's how it works. Each InputSectionBase has a "Live" bit. The bit is off
16 // by default. Starting with GC-root symbols or sections, markLive function
17 // defined in this file visits all reachable sections to set their Live
18 // bits. Writer will then ignore sections whose Live bits are off, so that
19 // such sections are not included into output.
20 //
21 //===----------------------------------------------------------------------===//
22
23 #include "MarkLive.h"
24 #include "InputSection.h"
25 #include "LinkerScript.h"
26 #include "OutputSections.h"
27 #include "SymbolTable.h"
28 #include "Symbols.h"
29 #include "Target.h"
30 #include "lld/Common/Memory.h"
31 #include "lld/Common/Strings.h"
32 #include "llvm/ADT/STLExtras.h"
33 #include "llvm/Object/ELF.h"
34 #include <functional>
35 #include <vector>
36
37 using namespace llvm;
38 using namespace llvm::ELF;
39 using namespace llvm::object;
40 using namespace llvm::support::endian;
41
42 using namespace lld;
43 using namespace lld::elf;
44
45 template <class ELFT>
getAddend(InputSectionBase & Sec,const typename ELFT::Rel & Rel)46 static typename ELFT::uint getAddend(InputSectionBase &Sec,
47 const typename ELFT::Rel &Rel) {
48 return Target->getImplicitAddend(Sec.data().begin() + Rel.r_offset,
49 Rel.getType(Config->IsMips64EL));
50 }
51
52 template <class ELFT>
getAddend(InputSectionBase & Sec,const typename ELFT::Rela & Rel)53 static typename ELFT::uint getAddend(InputSectionBase &Sec,
54 const typename ELFT::Rela &Rel) {
55 return Rel.r_addend;
56 }
57
58 // There are normally few input sections whose names are valid C
59 // identifiers, so we just store a std::vector instead of a multimap.
60 static DenseMap<StringRef, std::vector<InputSectionBase *>> CNamedSections;
61
62 template <class ELFT, class RelT>
63 static void
resolveReloc(InputSectionBase & Sec,RelT & Rel,llvm::function_ref<void (InputSectionBase *,uint64_t)> Fn)64 resolveReloc(InputSectionBase &Sec, RelT &Rel,
65 llvm::function_ref<void(InputSectionBase *, uint64_t)> Fn) {
66 Symbol &B = Sec.getFile<ELFT>()->getRelocTargetSym(Rel);
67
68 // If a symbol is referenced in a live section, it is used.
69 B.Used = true;
70 if (auto *SS = dyn_cast<SharedSymbol>(&B))
71 if (!SS->isWeak())
72 SS->getFile<ELFT>().IsNeeded = true;
73
74 if (auto *D = dyn_cast<Defined>(&B)) {
75 auto *RelSec = dyn_cast_or_null<InputSectionBase>(D->Section);
76 if (!RelSec)
77 return;
78 uint64_t Offset = D->Value;
79 if (D->isSection())
80 Offset += getAddend<ELFT>(Sec, Rel);
81 Fn(RelSec, Offset);
82 return;
83 }
84
85 if (!B.isDefined())
86 for (InputSectionBase *Sec : CNamedSections.lookup(B.getName()))
87 Fn(Sec, 0);
88 }
89
90 // Calls Fn for each section that Sec refers to via relocations.
91 template <class ELFT>
92 static void
forEachSuccessor(InputSection & Sec,llvm::function_ref<void (InputSectionBase *,uint64_t)> Fn)93 forEachSuccessor(InputSection &Sec,
94 llvm::function_ref<void(InputSectionBase *, uint64_t)> Fn) {
95 if (Sec.AreRelocsRela) {
96 for (const typename ELFT::Rela &Rel : Sec.template relas<ELFT>())
97 resolveReloc<ELFT>(Sec, Rel, Fn);
98 } else {
99 for (const typename ELFT::Rel &Rel : Sec.template rels<ELFT>())
100 resolveReloc<ELFT>(Sec, Rel, Fn);
101 }
102
103 for (InputSectionBase *IS : Sec.DependentSections)
104 Fn(IS, 0);
105 }
106
107 // The .eh_frame section is an unfortunate special case.
108 // The section is divided in CIEs and FDEs and the relocations it can have are
109 // * CIEs can refer to a personality function.
110 // * FDEs can refer to a LSDA
111 // * FDEs refer to the function they contain information about
112 // The last kind of relocation cannot keep the referred section alive, or they
113 // would keep everything alive in a common object file. In fact, each FDE is
114 // alive if the section it refers to is alive.
115 // To keep things simple, in here we just ignore the last relocation kind. The
116 // other two keep the referred section alive.
117 //
118 // A possible improvement would be to fully process .eh_frame in the middle of
119 // the gc pass. With that we would be able to also gc some sections holding
120 // LSDAs and personality functions if we found that they were unused.
121 template <class ELFT, class RelTy>
122 static void
scanEhFrameSection(EhInputSection & EH,ArrayRef<RelTy> Rels,llvm::function_ref<void (InputSectionBase *,uint64_t)> Fn)123 scanEhFrameSection(EhInputSection &EH, ArrayRef<RelTy> Rels,
124 llvm::function_ref<void(InputSectionBase *, uint64_t)> Fn) {
125 const endianness E = ELFT::TargetEndianness;
126
127 for (unsigned I = 0, N = EH.Pieces.size(); I < N; ++I) {
128 EhSectionPiece &Piece = EH.Pieces[I];
129 unsigned FirstRelI = Piece.FirstRelocation;
130 if (FirstRelI == (unsigned)-1)
131 continue;
132 if (read32<E>(Piece.data().data() + 4) == 0) {
133 // This is a CIE, we only need to worry about the first relocation. It is
134 // known to point to the personality function.
135 resolveReloc<ELFT>(EH, Rels[FirstRelI], Fn);
136 continue;
137 }
138 // This is a FDE. The relocations point to the described function or to
139 // a LSDA. We only need to keep the LSDA alive, so ignore anything that
140 // points to executable sections.
141 typename ELFT::uint PieceEnd = Piece.InputOff + Piece.Size;
142 for (unsigned I2 = FirstRelI, N2 = Rels.size(); I2 < N2; ++I2) {
143 const RelTy &Rel = Rels[I2];
144 if (Rel.r_offset >= PieceEnd)
145 break;
146 resolveReloc<ELFT>(EH, Rels[I2],
147 [&](InputSectionBase *Sec, uint64_t Offset) {
148 if (Sec && Sec != &InputSection::Discarded &&
149 !(Sec->Flags & SHF_EXECINSTR))
150 Fn(Sec, 0);
151 });
152 }
153 }
154 }
155
156 template <class ELFT>
157 static void
scanEhFrameSection(EhInputSection & EH,llvm::function_ref<void (InputSectionBase *,uint64_t)> Fn)158 scanEhFrameSection(EhInputSection &EH,
159 llvm::function_ref<void(InputSectionBase *, uint64_t)> Fn) {
160 if (!EH.NumRelocations)
161 return;
162
163 if (EH.AreRelocsRela)
164 scanEhFrameSection<ELFT>(EH, EH.template relas<ELFT>(), Fn);
165 else
166 scanEhFrameSection<ELFT>(EH, EH.template rels<ELFT>(), Fn);
167 }
168
169 // Some sections are used directly by the loader, so they should never be
170 // garbage-collected. This function returns true if a given section is such
171 // section.
isReserved(InputSectionBase * Sec)172 template <class ELFT> static bool isReserved(InputSectionBase *Sec) {
173 switch (Sec->Type) {
174 case SHT_FINI_ARRAY:
175 case SHT_INIT_ARRAY:
176 case SHT_NOTE:
177 case SHT_PREINIT_ARRAY:
178 return true;
179 default:
180 StringRef S = Sec->Name;
181 return S.startswith(".ctors") || S.startswith(".dtors") ||
182 S.startswith(".init") || S.startswith(".fini") ||
183 S.startswith(".jcr");
184 }
185 }
186
187 // This is the main function of the garbage collector.
188 // Starting from GC-root sections, this function visits all reachable
189 // sections to set their "Live" bits.
doGcSections()190 template <class ELFT> static void doGcSections() {
191 SmallVector<InputSection *, 256> Q;
192 CNamedSections.clear();
193
194 auto Enqueue = [&](InputSectionBase *Sec, uint64_t Offset) {
195 // Skip over discarded sections. This in theory shouldn't happen, because
196 // the ELF spec doesn't allow a relocation to point to a deduplicated
197 // COMDAT section directly. Unfortunately this happens in practice (e.g.
198 // .eh_frame) so we need to add a check.
199 if (Sec == &InputSection::Discarded)
200 return;
201
202
203 // Usually, a whole section is marked as live or dead, but in mergeable
204 // (splittable) sections, each piece of data has independent liveness bit.
205 // So we explicitly tell it which offset is in use.
206 if (auto *MS = dyn_cast<MergeInputSection>(Sec))
207 MS->getSectionPiece(Offset)->Live = true;
208
209 if (Sec->Live)
210 return;
211 Sec->Live = true;
212
213 // Add input section to the queue.
214 if (InputSection *S = dyn_cast<InputSection>(Sec))
215 Q.push_back(S);
216 };
217
218 auto MarkSymbol = [&](Symbol *Sym) {
219 if (auto *D = dyn_cast_or_null<Defined>(Sym))
220 if (auto *IS = dyn_cast_or_null<InputSectionBase>(D->Section))
221 Enqueue(IS, D->Value);
222 };
223
224 // Add GC root symbols.
225 MarkSymbol(Symtab->find(Config->Entry));
226 MarkSymbol(Symtab->find(Config->Init));
227 MarkSymbol(Symtab->find(Config->Fini));
228 for (StringRef S : Config->Undefined)
229 MarkSymbol(Symtab->find(S));
230 for (StringRef S : Script->ReferencedSymbols)
231 MarkSymbol(Symtab->find(S));
232
233 // Preserve externally-visible symbols if the symbols defined by this
234 // file can interrupt other ELF file's symbols at runtime.
235 for (Symbol *S : Symtab->getSymbols())
236 if (S->includeInDynsym())
237 MarkSymbol(S);
238
239 // Preserve special sections and those which are specified in linker
240 // script KEEP command.
241 for (InputSectionBase *Sec : InputSections) {
242 // Mark .eh_frame sections as live because there are usually no relocations
243 // that point to .eh_frames. Otherwise, the garbage collector would drop
244 // all of them. We also want to preserve personality routines and LSDA
245 // referenced by .eh_frame sections, so we scan them for that here.
246 if (auto *EH = dyn_cast<EhInputSection>(Sec)) {
247 EH->Live = true;
248 scanEhFrameSection<ELFT>(*EH, Enqueue);
249 }
250
251 if (Sec->Flags & SHF_LINK_ORDER)
252 continue;
253
254 if (isReserved<ELFT>(Sec) || Script->shouldKeep(Sec)) {
255 Enqueue(Sec, 0);
256 } else if (isValidCIdentifier(Sec->Name)) {
257 CNamedSections[Saver.save("__start_" + Sec->Name)].push_back(Sec);
258 CNamedSections[Saver.save("__stop_" + Sec->Name)].push_back(Sec);
259 }
260 }
261
262 // Mark all reachable sections.
263 while (!Q.empty())
264 forEachSuccessor<ELFT>(*Q.pop_back_val(), Enqueue);
265 }
266
267 // Before calling this function, Live bits are off for all
268 // input sections. This function make some or all of them on
269 // so that they are emitted to the output file.
markLive()270 template <class ELFT> void elf::markLive() {
271 if (!Config->GcSections) {
272 // If -gc-sections is missing, no sections are removed.
273 for (InputSectionBase *Sec : InputSections)
274 Sec->Live = true;
275
276 // If a DSO defines a symbol referenced in a regular object, it is needed.
277 for (Symbol *Sym : Symtab->getSymbols())
278 if (auto *S = dyn_cast<SharedSymbol>(Sym))
279 if (S->IsUsedInRegularObj && !S->isWeak())
280 S->getFile<ELFT>().IsNeeded = true;
281 return;
282 }
283
284 // The -gc-sections option works only for SHF_ALLOC sections
285 // (sections that are memory-mapped at runtime). So we can
286 // unconditionally make non-SHF_ALLOC sections alive except
287 // SHF_LINK_ORDER and SHT_REL/SHT_RELA sections.
288 //
289 // Usually, SHF_ALLOC sections are not removed even if they are
290 // unreachable through relocations because reachability is not
291 // a good signal whether they are garbage or not (e.g. there is
292 // usually no section referring to a .comment section, but we
293 // want to keep it.).
294 //
295 // Note on SHF_LINK_ORDER: Such sections contain metadata and they
296 // have a reverse dependency on the InputSection they are linked with.
297 // We are able to garbage collect them.
298 //
299 // Note on SHF_REL{,A}: Such sections reach here only when -r
300 // or -emit-reloc were given. And they are subject of garbage
301 // collection because, if we remove a text section, we also
302 // remove its relocation section.
303 for (InputSectionBase *Sec : InputSections) {
304 bool IsAlloc = (Sec->Flags & SHF_ALLOC);
305 bool IsLinkOrder = (Sec->Flags & SHF_LINK_ORDER);
306 bool IsRel = (Sec->Type == SHT_REL || Sec->Type == SHT_RELA);
307 if (!IsAlloc && !IsLinkOrder && !IsRel)
308 Sec->Live = true;
309 }
310
311 // Follow the graph to mark all live sections.
312 doGcSections<ELFT>();
313
314 // Report garbage-collected sections.
315 if (Config->PrintGcSections)
316 for (InputSectionBase *Sec : InputSections)
317 if (!Sec->Live)
318 message("removing unused section " + toString(Sec));
319 }
320
321 template void elf::markLive<ELF32LE>();
322 template void elf::markLive<ELF32BE>();
323 template void elf::markLive<ELF64LE>();
324 template void elf::markLive<ELF64BE>();
325