contrib/llvm/tools/lld/ELF/MarkLive.cpp

   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 "InputSection.h"
  24 #include "LinkerScript.h"
  25 #include "OutputSections.h"
  26 #include "Strings.h"
  27 #include "SymbolTable.h"
  28 #include "Symbols.h"
  29 #include "Target.h"
  30 #include "Writer.h"
  31 #include "llvm/ADT/STLExtras.h"
  32 #include "llvm/Object/ELF.h"
  33 #include <functional>
  34 #include <vector>
  35
  36 using namespace llvm;
  37 using namespace llvm::ELF;
  38 using namespace llvm::object;
  39 using namespace llvm::support::endian;
  40
  41 using namespace lld;
  42 using namespace lld::elf;
  43
  44 namespace {
  45 // A resolved relocation. The Sec and Offset fields are set if the relocation
  46 // was resolved to an offset within a section.
  47 template <class ELFT> struct ResolvedReloc {
  48   InputSectionBase<ELFT> *Sec;
  49   typename ELFT::uint Offset;
  50 };
  51 } // end anonymous namespace
  52
  53 template <class ELFT>
  54 static typename ELFT::uint getAddend(InputSectionBase<ELFT> &Sec,
  55                                      const typename ELFT::Rel &Rel) {
  56   return Target->getImplicitAddend(Sec.Data.begin() + Rel.r_offset,
  57                                    Rel.getType(Config->Mips64EL));
  58 }
  59
  60 template <class ELFT>
  61 static typename ELFT::uint getAddend(InputSectionBase<ELFT> &Sec,
  62                                      const typename ELFT::Rela &Rel) {
  63   return Rel.r_addend;
  64 }
  65
  66 template <class ELFT, class RelT>
  67 static ResolvedReloc<ELFT> resolveReloc(InputSectionBase<ELFT> &Sec,
  68                                         RelT &Rel) {
  69   SymbolBody &B = Sec.getFile()->getRelocTargetSym(Rel);
  70   auto *D = dyn_cast<DefinedRegular<ELFT>>(&B);
  71   if (!D || !D->Section)
  72     return {nullptr, 0};
  73   typename ELFT::uint Offset = D->Value;
  74   if (D->isSection())
  75     Offset += getAddend(Sec, Rel);
  76   return {D->Section->Repl, Offset};
  77 }
  78
  79 // Calls Fn for each section that Sec refers to via relocations.
  80 template <class ELFT>
  81 static void forEachSuccessor(InputSection<ELFT> &Sec,
  82                              std::function<void(ResolvedReloc<ELFT>)> Fn) {
  83   if (Sec.AreRelocsRela) {
  84     for (const typename ELFT::Rela &Rel : Sec.relas())
  85       Fn(resolveReloc(Sec, Rel));
  86   } else {
  87     for (const typename ELFT::Rel &Rel : Sec.rels())
  88       Fn(resolveReloc(Sec, Rel));
  89   }
  90   if (Sec.DependentSection)
  91     Fn({Sec.DependentSection, 0});
  92 }
  93
  94 // The .eh_frame section is an unfortunate special case.
  95 // The section is divided in CIEs and FDEs and the relocations it can have are
  96 // * CIEs can refer to a personality function.
  97 // * FDEs can refer to a LSDA
  98 // * FDEs refer to the function they contain information about
  99 // The last kind of relocation cannot keep the referred section alive, or they
 100 // would keep everything alive in a common object file. In fact, each FDE is
 101 // alive if the section it refers to is alive.
 102 // To keep things simple, in here we just ignore the last relocation kind. The
 103 // other two keep the referred section alive.
 104 //
 105 // A possible improvement would be to fully process .eh_frame in the middle of
 106 // the gc pass. With that we would be able to also gc some sections holding
 107 // LSDAs and personality functions if we found that they were unused.
 108 template <class ELFT, class RelTy>
 109 static void
 110 scanEhFrameSection(EhInputSection<ELFT> &EH, ArrayRef<RelTy> Rels,
 111                    std::function<void(ResolvedReloc<ELFT>)> Enqueue) {
 112   const endianness E = ELFT::TargetEndianness;
 113   for (unsigned I = 0, N = EH.Pieces.size(); I < N; ++I) {
 114     EhSectionPiece &Piece = EH.Pieces[I];
 115     unsigned FirstRelI = Piece.FirstRelocation;
 116     if (FirstRelI == (unsigned)-1)
 117       continue;
 118     if (read32<E>(Piece.data().data() + 4) == 0) {
 119       // This is a CIE, we only need to worry about the first relocation. It is
 120       // known to point to the personality function.
 121       Enqueue(resolveReloc(EH, Rels[FirstRelI]));
 122       continue;
 123     }
 124     // This is a FDE. The relocations point to the described function or to
 125     // a LSDA. We only need to keep the LSDA alive, so ignore anything that
 126     // points to executable sections.
 127     typename ELFT::uint PieceEnd = Piece.InputOff + Piece.size();
 128     for (unsigned I2 = FirstRelI, N2 = Rels.size(); I2 < N2; ++I2) {
 129       const RelTy &Rel = Rels[I2];
 130       if (Rel.r_offset >= PieceEnd)
 131         break;
 132       ResolvedReloc<ELFT> R = resolveReloc(EH, Rels[I2]);
 133       if (!R.Sec || R.Sec == &InputSection<ELFT>::Discarded)
 134         continue;
 135       if (R.Sec->Flags & SHF_EXECINSTR)
 136         continue;
 137       Enqueue({R.Sec, 0});
 138     }
 139   }
 140 }
 141
 142 template <class ELFT>
 143 static void
 144 scanEhFrameSection(EhInputSection<ELFT> &EH,
 145                    std::function<void(ResolvedReloc<ELFT>)> Enqueue) {
 146   if (!EH.NumRelocations)
 147     return;
 148
 149   // Unfortunately we need to split .eh_frame early since some relocations in
 150   // .eh_frame keep other section alive and some don't.
 151   EH.split();
 152
 153   if (EH.AreRelocsRela)
 154     scanEhFrameSection(EH, EH.relas(), Enqueue);
 155   else
 156     scanEhFrameSection(EH, EH.rels(), Enqueue);
 157 }
 158
 159 // We do not garbage-collect two types of sections:
 160 // 1) Sections used by the loader (.init, .fini, .ctors, .dtors or .jcr)
 161 // 2) Non-allocatable sections which typically contain debugging information
 162 template <class ELFT> static bool isReserved(InputSectionBase<ELFT> *Sec) {
 163   switch (Sec->Type) {
 164   case SHT_FINI_ARRAY:
 165   case SHT_INIT_ARRAY:
 166   case SHT_NOTE:
 167   case SHT_PREINIT_ARRAY:
 168     return true;
 169   default:
 170     if (!(Sec->Flags & SHF_ALLOC))
 171       return true;
 172
 173     // We do not want to reclaim sections if they can be referred
 174     // by __start_* and __stop_* symbols.
 175     StringRef S = Sec->Name;
 176     if (isValidCIdentifier(S))
 177       return true;
 178
 179     return S.startswith(".ctors") || S.startswith(".dtors") ||
 180            S.startswith(".init") || S.startswith(".fini") ||
 181            S.startswith(".jcr");
 182   }
 183 }
 184
 185 // This is the main function of the garbage collector.
 186 // Starting from GC-root sections, this function visits all reachable
 187 // sections to set their "Live" bits.
 188 template <class ELFT> void elf::markLive() {
 189   SmallVector<InputSection<ELFT> *, 256> Q;
 190
 191   auto Enqueue = [&](ResolvedReloc<ELFT> R) {
 192     // Skip over discarded sections. This in theory shouldn't happen, because
 193     // the ELF spec doesn't allow a relocation to point to a deduplicated
 194     // COMDAT section directly. Unfortunately this happens in practice (e.g.
 195     // .eh_frame) so we need to add a check.
 196     if (!R.Sec || R.Sec == &InputSection<ELFT>::Discarded)
 197       return;
 198
 199     // We don't gc non alloc sections.
 200     if (!(R.Sec->Flags & SHF_ALLOC))
 201       return;
 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<ELFT>>(R.Sec))
 207       MS->markLiveAt(R.Offset);
 208
 209     if (R.Sec->Live)
 210       return;
 211     R.Sec->Live = true;
 212     // Add input section to the queue.
 213     if (InputSection<ELFT> *S = dyn_cast<InputSection<ELFT>>(R.Sec))
 214       Q.push_back(S);
 215   };
 216
 217   auto MarkSymbol = [&](const SymbolBody *Sym) {
 218     if (auto *D = dyn_cast_or_null<DefinedRegular<ELFT>>(Sym))
 219       Enqueue({D->Section, D->Value});
 220   };
 221
 222   // Add GC root symbols.
 223   MarkSymbol(Symtab<ELFT>::X->find(Config->Entry));
 224   MarkSymbol(Symtab<ELFT>::X->find(Config->Init));
 225   MarkSymbol(Symtab<ELFT>::X->find(Config->Fini));
 226   for (StringRef S : Config->Undefined)
 227     MarkSymbol(Symtab<ELFT>::X->find(S));
 228
 229   // Preserve externally-visible symbols if the symbols defined by this
 230   // file can interrupt other ELF file's symbols at runtime.
 231   for (const Symbol *S : Symtab<ELFT>::X->getSymbols())
 232     if (S->includeInDynsym())
 233       MarkSymbol(S->body());
 234
 235   // Preserve special sections and those which are specified in linker
 236   // script KEEP command.
 237   for (InputSectionBase<ELFT> *Sec : Symtab<ELFT>::X->Sections) {
 238     // .eh_frame is always marked as live now, but also it can reference to
 239     // sections that contain personality. We preserve all non-text sections
 240     // referred by .eh_frame here.
 241     if (auto *EH = dyn_cast_or_null<EhInputSection<ELFT>>(Sec))
 242       scanEhFrameSection<ELFT>(*EH, Enqueue);
 243     if (isReserved(Sec) || Script<ELFT>::X->shouldKeep(Sec))
 244       Enqueue({Sec, 0});
 245   }
 246
 247   // Mark all reachable sections.
 248   while (!Q.empty())
 249     forEachSuccessor<ELFT>(*Q.pop_back_val(), Enqueue);
 250 }
 251
 252 template void elf::markLive<ELF32LE>();
 253 template void elf::markLive<ELF32BE>();
 254 template void elf::markLive<ELF64LE>();
 255 template void elf::markLive<ELF64BE>();