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