aboutsummaryrefslogtreecommitdiffstats
path: root/ELF/MarkLive.cpp
blob: 02ab6d18e53710dba4dacc7ff2263f1a1cbce297 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
//===- MarkLive.cpp -------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file implements --gc-sections, which is a feature to remove unused
// sections from output. Unused sections are sections that are not reachable
// from known GC-root symbols or sections. Naturally the feature is
// implemented as a mark-sweep garbage collector.
//
// Here's how it works. Each InputSectionBase has a "Live" bit. The bit is off
// by default. Starting with GC-root symbols or sections, markLive function
// defined in this file visits all reachable sections to set their Live
// bits. Writer will then ignore sections whose Live bits are off, so that
// such sections are not included into output.
//
//===----------------------------------------------------------------------===//

#include "MarkLive.h"
#include "InputSection.h"
#include "LinkerScript.h"
#include "OutputSections.h"
#include "SymbolTable.h"
#include "Symbols.h"
#include "SyntheticSections.h"
#include "Target.h"
#include "lld/Common/Memory.h"
#include "lld/Common/Strings.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Object/ELF.h"
#include <functional>
#include <vector>

using namespace llvm;
using namespace llvm::ELF;
using namespace llvm::object;

namespace endian = llvm::support::endian;

namespace lld {
namespace elf {
namespace {
template <class ELFT> class MarkLive {
public:
  MarkLive(unsigned partition) : partition(partition) {}

  void run();
  void moveToMain();

private:
  void enqueue(InputSectionBase *sec, uint64_t offset);
  void markSymbol(Symbol *sym);
  void mark();

  template <class RelTy>
  void resolveReloc(InputSectionBase &sec, RelTy &rel, bool isLSDA);

  template <class RelTy>
  void scanEhFrameSection(EhInputSection &eh, ArrayRef<RelTy> rels);

  // The index of the partition that we are currently processing.
  unsigned partition;

  // A list of sections to visit.
  SmallVector<InputSection *, 256> queue;

  // There are normally few input sections whose names are valid C
  // identifiers, so we just store a std::vector instead of a multimap.
  DenseMap<StringRef, std::vector<InputSectionBase *>> cNamedSections;
};
} // namespace

template <class ELFT>
static uint64_t getAddend(InputSectionBase &sec,
                          const typename ELFT::Rel &rel) {
  return target->getImplicitAddend(sec.data().begin() + rel.r_offset,
                                   rel.getType(config->isMips64EL));
}

template <class ELFT>
static uint64_t getAddend(InputSectionBase &sec,
                          const typename ELFT::Rela &rel) {
  return rel.r_addend;
}

template <class ELFT>
template <class RelTy>
void MarkLive<ELFT>::resolveReloc(InputSectionBase &sec, RelTy &rel,
                                  bool isLSDA) {
  Symbol &sym = sec.getFile<ELFT>()->getRelocTargetSym(rel);

  // If a symbol is referenced in a live section, it is used.
  sym.used = true;

  if (auto *d = dyn_cast<Defined>(&sym)) {
    auto *relSec = dyn_cast_or_null<InputSectionBase>(d->section);
    if (!relSec)
      return;

    uint64_t offset = d->value;
    if (d->isSection())
      offset += getAddend<ELFT>(sec, rel);

    if (!isLSDA || !(relSec->flags & SHF_EXECINSTR))
      enqueue(relSec, offset);
    return;
  }

  if (auto *ss = dyn_cast<SharedSymbol>(&sym))
    if (!ss->isWeak())
      ss->getFile().isNeeded = true;

  for (InputSectionBase *sec : cNamedSections.lookup(sym.getName()))
    enqueue(sec, 0);
}

// The .eh_frame section is an unfortunate special case.
// The section is divided in CIEs and FDEs and the relocations it can have are
// * CIEs can refer to a personality function.
// * FDEs can refer to a LSDA
// * FDEs refer to the function they contain information about
// The last kind of relocation cannot keep the referred section alive, or they
// would keep everything alive in a common object file. In fact, each FDE is
// alive if the section it refers to is alive.
// To keep things simple, in here we just ignore the last relocation kind. The
// other two keep the referred section alive.
//
// A possible improvement would be to fully process .eh_frame in the middle of
// the gc pass. With that we would be able to also gc some sections holding
// LSDAs and personality functions if we found that they were unused.
template <class ELFT>
template <class RelTy>
void MarkLive<ELFT>::scanEhFrameSection(EhInputSection &eh,
                                        ArrayRef<RelTy> rels) {
  for (size_t i = 0, end = eh.pieces.size(); i < end; ++i) {
    EhSectionPiece &piece = eh.pieces[i];
    size_t firstRelI = piece.firstRelocation;
    if (firstRelI == (unsigned)-1)
      continue;

    if (endian::read32<ELFT::TargetEndianness>(piece.data().data() + 4) == 0) {
      // This is a CIE, we only need to worry about the first relocation. It is
      // known to point to the personality function.
      resolveReloc(eh, rels[firstRelI], false);
      continue;
    }

    // This is a FDE. The relocations point to the described function or to
    // a LSDA. We only need to keep the LSDA alive, so ignore anything that
    // points to executable sections.
    uint64_t pieceEnd = piece.inputOff + piece.size;
    for (size_t j = firstRelI, end2 = rels.size(); j < end2; ++j)
      if (rels[j].r_offset < pieceEnd)
        resolveReloc(eh, rels[j], true);
  }
}

// Some sections are used directly by the loader, so they should never be
// garbage-collected. This function returns true if a given section is such
// section.
static bool isReserved(InputSectionBase *sec) {
  switch (sec->type) {
  case SHT_FINI_ARRAY:
  case SHT_INIT_ARRAY:
  case SHT_NOTE:
  case SHT_PREINIT_ARRAY:
    return true;
  default:
    StringRef s = sec->name;
    return s.startswith(".ctors") || s.startswith(".dtors") ||
           s.startswith(".init") || s.startswith(".fini") ||
           s.startswith(".jcr");
  }
}

template <class ELFT>
void MarkLive<ELFT>::enqueue(InputSectionBase *sec, uint64_t offset) {
  // Skip over discarded sections. This in theory shouldn't happen, because
  // the ELF spec doesn't allow a relocation to point to a deduplicated
  // COMDAT section directly. Unfortunately this happens in practice (e.g.
  // .eh_frame) so we need to add a check.
  if (sec == &InputSection::discarded)
    return;

  // Usually, a whole section is marked as live or dead, but in mergeable
  // (splittable) sections, each piece of data has independent liveness bit.
  // So we explicitly tell it which offset is in use.
  if (auto *ms = dyn_cast<MergeInputSection>(sec))
    ms->getSectionPiece(offset)->live = true;

  // Set Sec->Partition to the meet (i.e. the "minimum") of Partition and
  // Sec->Partition in the following lattice: 1 < other < 0. If Sec->Partition
  // doesn't change, we don't need to do anything.
  if (sec->partition == 1 || sec->partition == partition)
    return;
  sec->partition = sec->partition ? 1 : partition;

  // Add input section to the queue.
  if (InputSection *s = dyn_cast<InputSection>(sec))
    queue.push_back(s);
}

template <class ELFT> void MarkLive<ELFT>::markSymbol(Symbol *sym) {
  if (auto *d = dyn_cast_or_null<Defined>(sym))
    if (auto *isec = dyn_cast_or_null<InputSectionBase>(d->section))
      enqueue(isec, d->value);
}

// This is the main function of the garbage collector.
// Starting from GC-root sections, this function visits all reachable
// sections to set their "Live" bits.
template <class ELFT> void MarkLive<ELFT>::run() {
  // Add GC root symbols.

  // Preserve externally-visible symbols if the symbols defined by this
  // file can interrupt other ELF file's symbols at runtime.
  symtab->forEachSymbol([&](Symbol *sym) {
    if (sym->includeInDynsym() && sym->partition == partition)
      markSymbol(sym);
  });

  // If this isn't the main partition, that's all that we need to preserve.
  if (partition != 1) {
    mark();
    return;
  }

  markSymbol(symtab->find(config->entry));
  markSymbol(symtab->find(config->init));
  markSymbol(symtab->find(config->fini));
  for (StringRef s : config->undefined)
    markSymbol(symtab->find(s));
  for (StringRef s : script->referencedSymbols)
    markSymbol(symtab->find(s));

  // Preserve special sections and those which are specified in linker
  // script KEEP command.
  for (InputSectionBase *sec : inputSections) {
    // Mark .eh_frame sections as live because there are usually no relocations
    // that point to .eh_frames. Otherwise, the garbage collector would drop
    // all of them. We also want to preserve personality routines and LSDA
    // referenced by .eh_frame sections, so we scan them for that here.
    if (auto *eh = dyn_cast<EhInputSection>(sec)) {
      eh->markLive();
      if (!eh->numRelocations)
        continue;

      if (eh->areRelocsRela)
        scanEhFrameSection(*eh, eh->template relas<ELFT>());
      else
        scanEhFrameSection(*eh, eh->template rels<ELFT>());
    }

    if (sec->flags & SHF_LINK_ORDER)
      continue;

    if (isReserved(sec) || script->shouldKeep(sec)) {
      enqueue(sec, 0);
    } else if (isValidCIdentifier(sec->name)) {
      cNamedSections[saver.save("__start_" + sec->name)].push_back(sec);
      cNamedSections[saver.save("__stop_" + sec->name)].push_back(sec);
    }
  }

  mark();
}

template <class ELFT> void MarkLive<ELFT>::mark() {
  // Mark all reachable sections.
  while (!queue.empty()) {
    InputSectionBase &sec = *queue.pop_back_val();

    if (sec.areRelocsRela) {
      for (const typename ELFT::Rela &rel : sec.template relas<ELFT>())
        resolveReloc(sec, rel, false);
    } else {
      for (const typename ELFT::Rel &rel : sec.template rels<ELFT>())
        resolveReloc(sec, rel, false);
    }

    for (InputSectionBase *isec : sec.dependentSections)
      enqueue(isec, 0);
  }
}

// Move the sections for some symbols to the main partition, specifically ifuncs
// (because they can result in an IRELATIVE being added to the main partition's
// GOT, which means that the ifunc must be available when the main partition is
// loaded) and TLS symbols (because we only know how to correctly process TLS
// relocations for the main partition).
//
// We also need to move sections whose names are C identifiers that are referred
// to from __start_/__stop_ symbols because there will only be one set of
// symbols for the whole program.
template <class ELFT> void MarkLive<ELFT>::moveToMain() {
  for (InputFile *file : objectFiles)
    for (Symbol *s : file->getSymbols())
      if (auto *d = dyn_cast<Defined>(s))
        if ((d->type == STT_GNU_IFUNC || d->type == STT_TLS) && d->section &&
            d->section->isLive())
          markSymbol(s);

  for (InputSectionBase *sec : inputSections) {
    if (!sec->isLive() || !isValidCIdentifier(sec->name))
      continue;
    if (symtab->find(("__start_" + sec->name).str()) ||
        symtab->find(("__stop_" + sec->name).str()))
      enqueue(sec, 0);
  }

  mark();
}

// Before calling this function, Live bits are off for all
// input sections. This function make some or all of them on
// so that they are emitted to the output file.
template <class ELFT> void markLive() {
  // If -gc-sections is not given, no sections are removed.
  if (!config->gcSections) {
    for (InputSectionBase *sec : inputSections)
      sec->markLive();

    // If a DSO defines a symbol referenced in a regular object, it is needed.
    symtab->forEachSymbol([](Symbol *sym) {
      if (auto *s = dyn_cast<SharedSymbol>(sym))
        if (s->isUsedInRegularObj && !s->isWeak())
          s->getFile().isNeeded = true;
    });
    return;
  }

  // Otheriwse, do mark-sweep GC.
  //
  // The -gc-sections option works only for SHF_ALLOC sections
  // (sections that are memory-mapped at runtime). So we can
  // unconditionally make non-SHF_ALLOC sections alive except
  // SHF_LINK_ORDER and SHT_REL/SHT_RELA sections.
  //
  // Usually, non-SHF_ALLOC sections are not removed even if they are
  // unreachable through relocations because reachability is not
  // a good signal whether they are garbage or not (e.g. there is
  // usually no section referring to a .comment section, but we
  // want to keep it.).
  //
  // Note on SHF_LINK_ORDER: Such sections contain metadata and they
  // have a reverse dependency on the InputSection they are linked with.
  // We are able to garbage collect them.
  //
  // Note on SHF_REL{,A}: Such sections reach here only when -r
  // or -emit-reloc were given. And they are subject of garbage
  // collection because, if we remove a text section, we also
  // remove its relocation section.
  for (InputSectionBase *sec : inputSections) {
    bool isAlloc = (sec->flags & SHF_ALLOC);
    bool isLinkOrder = (sec->flags & SHF_LINK_ORDER);
    bool isRel = (sec->type == SHT_REL || sec->type == SHT_RELA);

    if (!isAlloc && !isLinkOrder && !isRel)
      sec->markLive();
  }

  // Follow the graph to mark all live sections.
  for (unsigned curPart = 1; curPart <= partitions.size(); ++curPart)
    MarkLive<ELFT>(curPart).run();

  // If we have multiple partitions, some sections need to live in the main
  // partition even if they were allocated to a loadable partition. Move them
  // there now.
  if (partitions.size() != 1)
    MarkLive<ELFT>(1).moveToMain();

  // Report garbage-collected sections.
  if (config->printGcSections)
    for (InputSectionBase *sec : inputSections)
      if (!sec->isLive())
        message("removing unused section " + toString(sec));
}

template void markLive<ELF32LE>();
template void markLive<ELF32BE>();
template void markLive<ELF64LE>();
template void markLive<ELF64BE>();

} // namespace elf
} // namespace lld