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