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 // This file implements --gc-sections, which is a feature to remove unused
10 // sections from output. Unused sections are sections that are not reachable
11 // from known GC-root symbols or sections. Naturally the feature is
12 // implemented as a mark-sweep garbage collector.
13 //
14 // Here's how it works. Each InputSectionBase has a "Live" bit. The bit is off
15 // by default. Starting with GC-root symbols or sections, markLive function
16 // defined in this file visits all reachable sections to set their Live
17 // bits. Writer will then ignore sections whose Live bits are off, so that
18 // such sections are not included into output.
19 //
20 //===----------------------------------------------------------------------===//
21
22 #include "MarkLive.h"
23 #include "InputSection.h"
24 #include "LinkerScript.h"
25 #include "OutputSections.h"
26 #include "SymbolTable.h"
27 #include "Symbols.h"
28 #include "SyntheticSections.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 "llvm/Support/TimeProfiler.h"
35 #include <functional>
36 #include <vector>
37
38 using namespace llvm;
39 using namespace llvm::ELF;
40 using namespace llvm::object;
41 using namespace llvm::support::endian;
42 using namespace lld;
43 using namespace lld::elf;
44
45 namespace {
46 template <class ELFT> class MarkLive {
47 public:
MarkLive(unsigned partition)48 MarkLive(unsigned partition) : partition(partition) {}
49
50 void run();
51 void moveToMain();
52
53 private:
54 void enqueue(InputSectionBase *sec, uint64_t offset);
55 void markSymbol(Symbol *sym);
56 void mark();
57
58 template <class RelTy>
59 void resolveReloc(InputSectionBase &sec, RelTy &rel, bool fromFDE);
60
61 template <class RelTy>
62 void scanEhFrameSection(EhInputSection &eh, ArrayRef<RelTy> rels);
63
64 // The index of the partition that we are currently processing.
65 unsigned partition;
66
67 // A list of sections to visit.
68 SmallVector<InputSection *, 0> queue;
69
70 // There are normally few input sections whose names are valid C
71 // identifiers, so we just store a std::vector instead of a multimap.
72 DenseMap<StringRef, std::vector<InputSectionBase *>> cNamedSections;
73 };
74 } // namespace
75
76 template <class ELFT>
getAddend(InputSectionBase & sec,const typename ELFT::Rel & rel)77 static uint64_t getAddend(InputSectionBase &sec,
78 const typename ELFT::Rel &rel) {
79 return target->getImplicitAddend(sec.data().begin() + rel.r_offset,
80 rel.getType(config->isMips64EL));
81 }
82
83 template <class ELFT>
getAddend(InputSectionBase & sec,const typename ELFT::Rela & rel)84 static uint64_t getAddend(InputSectionBase &sec,
85 const typename ELFT::Rela &rel) {
86 return rel.r_addend;
87 }
88
89 template <class ELFT>
90 template <class RelTy>
resolveReloc(InputSectionBase & sec,RelTy & rel,bool fromFDE)91 void MarkLive<ELFT>::resolveReloc(InputSectionBase &sec, RelTy &rel,
92 bool fromFDE) {
93 Symbol &sym = sec.getFile<ELFT>()->getRelocTargetSym(rel);
94
95 // If a symbol is referenced in a live section, it is used.
96 sym.used = true;
97
98 if (auto *d = dyn_cast<Defined>(&sym)) {
99 auto *relSec = dyn_cast_or_null<InputSectionBase>(d->section);
100 if (!relSec)
101 return;
102
103 uint64_t offset = d->value;
104 if (d->isSection())
105 offset += getAddend<ELFT>(sec, rel);
106
107 // fromFDE being true means this is referenced by a FDE in a .eh_frame
108 // piece. The relocation points to the described function or to a LSDA. We
109 // only need to keep the LSDA live, so ignore anything that points to
110 // executable sections. If the LSDA is in a section group, we ignore the
111 // relocation as well because (a) if the associated text section is live,
112 // the LSDA will be retained due to section group rules (b) if the
113 // associated text section should be discarded, marking the LSDA will
114 // unnecessarily retain the text section.
115 if (!(fromFDE &&
116 ((relSec->flags & SHF_EXECINSTR) || relSec->nextInSectionGroup)))
117 enqueue(relSec, offset);
118 return;
119 }
120
121 if (auto *ss = dyn_cast<SharedSymbol>(&sym))
122 if (!ss->isWeak())
123 ss->getFile().isNeeded = true;
124
125 for (InputSectionBase *sec : cNamedSections.lookup(sym.getName()))
126 enqueue(sec, 0);
127 }
128
129 // The .eh_frame section is an unfortunate special case.
130 // The section is divided in CIEs and FDEs and the relocations it can have are
131 // * CIEs can refer to a personality function.
132 // * FDEs can refer to a LSDA
133 // * FDEs refer to the function they contain information about
134 // The last kind of relocation cannot keep the referred section alive, or they
135 // would keep everything alive in a common object file. In fact, each FDE is
136 // alive if the section it refers to is alive.
137 // To keep things simple, in here we just ignore the last relocation kind. The
138 // other two keep the referred section alive.
139 //
140 // A possible improvement would be to fully process .eh_frame in the middle of
141 // the gc pass. With that we would be able to also gc some sections holding
142 // LSDAs and personality functions if we found that they were unused.
143 template <class ELFT>
144 template <class RelTy>
scanEhFrameSection(EhInputSection & eh,ArrayRef<RelTy> rels)145 void MarkLive<ELFT>::scanEhFrameSection(EhInputSection &eh,
146 ArrayRef<RelTy> rels) {
147 for (size_t i = 0, end = eh.pieces.size(); i < end; ++i) {
148 EhSectionPiece &piece = eh.pieces[i];
149 size_t firstRelI = piece.firstRelocation;
150 if (firstRelI == (unsigned)-1)
151 continue;
152
153 if (read32<ELFT::TargetEndianness>(piece.data().data() + 4) == 0) {
154 // This is a CIE, we only need to worry about the first relocation. It is
155 // known to point to the personality function.
156 resolveReloc(eh, rels[firstRelI], false);
157 continue;
158 }
159
160 uint64_t pieceEnd = piece.inputOff + piece.size;
161 for (size_t j = firstRelI, end2 = rels.size();
162 j < end2 && rels[j].r_offset < pieceEnd; ++j)
163 resolveReloc(eh, rels[j], true);
164 }
165 }
166
167 // Some sections are used directly by the loader, so they should never be
168 // garbage-collected. This function returns true if a given section is such
169 // section.
isReserved(InputSectionBase * sec)170 static bool isReserved(InputSectionBase *sec) {
171 switch (sec->type) {
172 case SHT_FINI_ARRAY:
173 case SHT_INIT_ARRAY:
174 case SHT_PREINIT_ARRAY:
175 return true;
176 case SHT_NOTE:
177 // SHT_NOTE sections in a group are subject to garbage collection.
178 return !sec->nextInSectionGroup;
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 template <class ELFT>
enqueue(InputSectionBase * sec,uint64_t offset)188 void MarkLive<ELFT>::enqueue(InputSectionBase *sec, uint64_t offset) {
189 // Skip over discarded sections. This in theory shouldn't happen, because
190 // the ELF spec doesn't allow a relocation to point to a deduplicated
191 // COMDAT section directly. Unfortunately this happens in practice (e.g.
192 // .eh_frame) so we need to add a check.
193 if (sec == &InputSection::discarded)
194 return;
195
196 // Usually, a whole section is marked as live or dead, but in mergeable
197 // (splittable) sections, each piece of data has independent liveness bit.
198 // So we explicitly tell it which offset is in use.
199 if (auto *ms = dyn_cast<MergeInputSection>(sec))
200 ms->getSectionPiece(offset)->live = true;
201
202 // Set Sec->Partition to the meet (i.e. the "minimum") of Partition and
203 // Sec->Partition in the following lattice: 1 < other < 0. If Sec->Partition
204 // doesn't change, we don't need to do anything.
205 if (sec->partition == 1 || sec->partition == partition)
206 return;
207 sec->partition = sec->partition ? 1 : partition;
208
209 // Add input section to the queue.
210 if (InputSection *s = dyn_cast<InputSection>(sec))
211 queue.push_back(s);
212 }
213
markSymbol(Symbol * sym)214 template <class ELFT> void MarkLive<ELFT>::markSymbol(Symbol *sym) {
215 if (auto *d = dyn_cast_or_null<Defined>(sym))
216 if (auto *isec = dyn_cast_or_null<InputSectionBase>(d->section))
217 enqueue(isec, d->value);
218 }
219
220 // This is the main function of the garbage collector.
221 // Starting from GC-root sections, this function visits all reachable
222 // sections to set their "Live" bits.
run()223 template <class ELFT> void MarkLive<ELFT>::run() {
224 // Add GC root symbols.
225
226 // Preserve externally-visible symbols if the symbols defined by this
227 // file can interrupt other ELF file's symbols at runtime.
228 for (Symbol *sym : symtab->symbols())
229 if (sym->includeInDynsym() && sym->partition == partition)
230 markSymbol(sym);
231
232 // If this isn't the main partition, that's all that we need to preserve.
233 if (partition != 1) {
234 mark();
235 return;
236 }
237
238 markSymbol(symtab->find(config->entry));
239 markSymbol(symtab->find(config->init));
240 markSymbol(symtab->find(config->fini));
241 for (StringRef s : config->undefined)
242 markSymbol(symtab->find(s));
243 for (StringRef s : script->referencedSymbols)
244 markSymbol(symtab->find(s));
245
246 // Preserve special sections and those which are specified in linker
247 // script KEEP command.
248 for (InputSectionBase *sec : inputSections) {
249 // Mark .eh_frame sections as live because there are usually no relocations
250 // that point to .eh_frames. Otherwise, the garbage collector would drop
251 // all of them. We also want to preserve personality routines and LSDA
252 // referenced by .eh_frame sections, so we scan them for that here.
253 if (auto *eh = dyn_cast<EhInputSection>(sec)) {
254 eh->markLive();
255 if (!eh->numRelocations)
256 continue;
257
258 if (eh->areRelocsRela)
259 scanEhFrameSection(*eh, eh->template relas<ELFT>());
260 else
261 scanEhFrameSection(*eh, eh->template rels<ELFT>());
262 }
263
264 if (sec->flags & SHF_LINK_ORDER)
265 continue;
266
267 if (isReserved(sec) || script->shouldKeep(sec)) {
268 enqueue(sec, 0);
269 } else if (isValidCIdentifier(sec->name)) {
270 cNamedSections[saver.save("__start_" + sec->name)].push_back(sec);
271 cNamedSections[saver.save("__stop_" + sec->name)].push_back(sec);
272 }
273 }
274
275 mark();
276 }
277
mark()278 template <class ELFT> void MarkLive<ELFT>::mark() {
279 // Mark all reachable sections.
280 while (!queue.empty()) {
281 InputSectionBase &sec = *queue.pop_back_val();
282
283 if (sec.areRelocsRela) {
284 for (const typename ELFT::Rela &rel : sec.template relas<ELFT>())
285 resolveReloc(sec, rel, false);
286 } else {
287 for (const typename ELFT::Rel &rel : sec.template rels<ELFT>())
288 resolveReloc(sec, rel, false);
289 }
290
291 for (InputSectionBase *isec : sec.dependentSections)
292 enqueue(isec, 0);
293
294 // Mark the next group member.
295 if (sec.nextInSectionGroup)
296 enqueue(sec.nextInSectionGroup, 0);
297 }
298 }
299
300 // Move the sections for some symbols to the main partition, specifically ifuncs
301 // (because they can result in an IRELATIVE being added to the main partition's
302 // GOT, which means that the ifunc must be available when the main partition is
303 // loaded) and TLS symbols (because we only know how to correctly process TLS
304 // relocations for the main partition).
305 //
306 // We also need to move sections whose names are C identifiers that are referred
307 // to from __start_/__stop_ symbols because there will only be one set of
308 // symbols for the whole program.
moveToMain()309 template <class ELFT> void MarkLive<ELFT>::moveToMain() {
310 for (InputFile *file : objectFiles)
311 for (Symbol *s : file->getSymbols())
312 if (auto *d = dyn_cast<Defined>(s))
313 if ((d->type == STT_GNU_IFUNC || d->type == STT_TLS) && d->section &&
314 d->section->isLive())
315 markSymbol(s);
316
317 for (InputSectionBase *sec : inputSections) {
318 if (!sec->isLive() || !isValidCIdentifier(sec->name))
319 continue;
320 if (symtab->find(("__start_" + sec->name).str()) ||
321 symtab->find(("__stop_" + sec->name).str()))
322 enqueue(sec, 0);
323 }
324
325 mark();
326 }
327
328 // Before calling this function, Live bits are off for all
329 // input sections. This function make some or all of them on
330 // so that they are emitted to the output file.
markLive()331 template <class ELFT> void elf::markLive() {
332 llvm::TimeTraceScope timeScope("markLive");
333 // If -gc-sections is not given, no sections are removed.
334 if (!config->gcSections) {
335 for (InputSectionBase *sec : inputSections)
336 sec->markLive();
337
338 // If a DSO defines a symbol referenced in a regular object, it is needed.
339 for (Symbol *sym : symtab->symbols())
340 if (auto *s = dyn_cast<SharedSymbol>(sym))
341 if (s->isUsedInRegularObj && !s->isWeak())
342 s->getFile().isNeeded = true;
343 return;
344 }
345
346 // Otherwise, do mark-sweep GC.
347 //
348 // The -gc-sections option works only for SHF_ALLOC sections (sections that
349 // are memory-mapped at runtime). So we can unconditionally make non-SHF_ALLOC
350 // sections alive except SHF_LINK_ORDER, SHT_REL/SHT_RELA sections, and
351 // sections in a group.
352 //
353 // Usually, non-SHF_ALLOC sections are not removed even if they are
354 // unreachable through relocations because reachability is not a good signal
355 // whether they are garbage or not (e.g. there is usually no section referring
356 // to a .comment section, but we want to keep it.) When a non-SHF_ALLOC
357 // section is retained, we also retain sections dependent on it.
358 //
359 // Note on SHF_LINK_ORDER: Such sections contain metadata and they
360 // have a reverse dependency on the InputSection they are linked with.
361 // We are able to garbage collect them.
362 //
363 // Note on SHF_REL{,A}: Such sections reach here only when -r
364 // or -emit-reloc were given. And they are subject of garbage
365 // collection because, if we remove a text section, we also
366 // remove its relocation section.
367 //
368 // Note on nextInSectionGroup: The ELF spec says that group sections are
369 // included or omitted as a unit. We take the interpretation that:
370 //
371 // - Group members (nextInSectionGroup != nullptr) are subject to garbage
372 // collection.
373 // - Groups members are retained or discarded as a unit.
374 for (InputSectionBase *sec : inputSections) {
375 bool isAlloc = (sec->flags & SHF_ALLOC);
376 bool isLinkOrder = (sec->flags & SHF_LINK_ORDER);
377 bool isRel = (sec->type == SHT_REL || sec->type == SHT_RELA);
378
379 if (!isAlloc && !isLinkOrder && !isRel && !sec->nextInSectionGroup) {
380 sec->markLive();
381 for (InputSection *isec : sec->dependentSections)
382 isec->markLive();
383 }
384 }
385
386 // Follow the graph to mark all live sections.
387 for (unsigned curPart = 1; curPart <= partitions.size(); ++curPart)
388 MarkLive<ELFT>(curPart).run();
389
390 // If we have multiple partitions, some sections need to live in the main
391 // partition even if they were allocated to a loadable partition. Move them
392 // there now.
393 if (partitions.size() != 1)
394 MarkLive<ELFT>(1).moveToMain();
395
396 // Report garbage-collected sections.
397 if (config->printGcSections)
398 for (InputSectionBase *sec : inputSections)
399 if (!sec->isLive())
400 message("removing unused section " + toString(sec));
401 }
402
403 template void elf::markLive<ELF32LE>();
404 template void elf::markLive<ELF32BE>();
405 template void elf::markLive<ELF64LE>();
406 template void elf::markLive<ELF64BE>();
407