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