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 "lld/Common/Memory.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 template <class ELFT>
  46 static typename ELFT::uint getAddend(InputSectionBase &Sec,
  47                                      const typename ELFT::Rel &Rel) {
  48   return Target->getImplicitAddend(Sec.Data.begin() + Rel.r_offset,
  49                                    Rel.getType(Config->IsMips64EL));
  50 }
  51
  52 template <class ELFT>
  53 static typename ELFT::uint getAddend(InputSectionBase &Sec,
  54                                      const typename ELFT::Rela &Rel) {
  55   return Rel.r_addend;
  56 }
  57
  58 // There are normally few input sections whose names are valid C
  59 // identifiers, so we just store a std::vector instead of a multimap.
  60 static DenseMap<StringRef, std::vector<InputSectionBase *>> CNamedSections;
  61
  62 template <class ELFT, class RelT>
  63 static void resolveReloc(InputSectionBase &Sec, RelT &Rel,
  64                          std::function<void(InputSectionBase *, uint64_t)> Fn) {
  65   Symbol &B = Sec.getFile<ELFT>()->getRelocTargetSym(Rel);
  66
  67   // If a symbol is referenced in a live section, it is used.
  68   B.Used = true;
  69   if (auto *SS = dyn_cast<SharedSymbol>(&B))
  70     if (!SS->isWeak())
  71       SS->getFile<ELFT>()->IsNeeded = true;
  72
  73   if (auto *D = dyn_cast<Defined>(&B)) {
  74     auto *RelSec = dyn_cast_or_null<InputSectionBase>(D->Section);
  75     if (!RelSec)
  76       return;
  77     uint64_t Offset = D->Value;
  78     if (D->isSection())
  79       Offset += getAddend<ELFT>(Sec, Rel);
  80     Fn(RelSec, Offset);
  81     return;
  82   }
  83
  84   if (!B.isDefined())
  85     for (InputSectionBase *Sec : CNamedSections.lookup(B.getName()))
  86       Fn(Sec, 0);
  87 }
  88
  89 // Calls Fn for each section that Sec refers to via relocations.
  90 template <class ELFT>
  91 static void
  92 forEachSuccessor(InputSection &Sec,
  93                  std::function<void(InputSectionBase *, uint64_t)> Fn) {
  94   if (Sec.AreRelocsRela) {
  95     for (const typename ELFT::Rela &Rel : Sec.template relas<ELFT>())
  96       resolveReloc<ELFT>(Sec, Rel, Fn);
  97   } else {
  98     for (const typename ELFT::Rel &Rel : Sec.template rels<ELFT>())
  99       resolveReloc<ELFT>(Sec, Rel, Fn);
 100   }
 101
 102   for (InputSectionBase *IS : Sec.DependentSections)
 103     Fn(IS, 0);
 104 }
 105
 106 // The .eh_frame section is an unfortunate special case.
 107 // The section is divided in CIEs and FDEs and the relocations it can have are
 108 // * CIEs can refer to a personality function.
 109 // * FDEs can refer to a LSDA
 110 // * FDEs refer to the function they contain information about
 111 // The last kind of relocation cannot keep the referred section alive, or they
 112 // would keep everything alive in a common object file. In fact, each FDE is
 113 // alive if the section it refers to is alive.
 114 // To keep things simple, in here we just ignore the last relocation kind. The
 115 // other two keep the referred section alive.
 116 //
 117 // A possible improvement would be to fully process .eh_frame in the middle of
 118 // the gc pass. With that we would be able to also gc some sections holding
 119 // LSDAs and personality functions if we found that they were unused.
 120 template <class ELFT, class RelTy>
 121 static void
 122 scanEhFrameSection(EhInputSection &EH, ArrayRef<RelTy> Rels,
 123                    std::function<void(InputSectionBase *, uint64_t)> Fn) {
 124   const endianness E = ELFT::TargetEndianness;
 125
 126   for (unsigned I = 0, N = EH.Pieces.size(); I < N; ++I) {
 127     EhSectionPiece &Piece = EH.Pieces[I];
 128     unsigned FirstRelI = Piece.FirstRelocation;
 129     if (FirstRelI == (unsigned)-1)
 130       continue;
 131     if (read32<E>(Piece.data().data() + 4) == 0) {
 132       // This is a CIE, we only need to worry about the first relocation. It is
 133       // known to point to the personality function.
 134       resolveReloc<ELFT>(EH, Rels[FirstRelI], Fn);
 135       continue;
 136     }
 137     // This is a FDE. The relocations point to the described function or to
 138     // a LSDA. We only need to keep the LSDA alive, so ignore anything that
 139     // points to executable sections.
 140     typename ELFT::uint PieceEnd = Piece.InputOff + Piece.Size;
 141     for (unsigned I2 = FirstRelI, N2 = Rels.size(); I2 < N2; ++I2) {
 142       const RelTy &Rel = Rels[I2];
 143       if (Rel.r_offset >= PieceEnd)
 144         break;
 145       resolveReloc<ELFT>(EH, Rels[I2],
 146                          [&](InputSectionBase *Sec, uint64_t Offset) {
 147                            if (Sec && Sec != &InputSection::Discarded &&
 148                                !(Sec->Flags & SHF_EXECINSTR))
 149                              Fn(Sec, 0);
 150                          });
 151     }
 152   }
 153 }
 154
 155 template <class ELFT>
 156 static void
 157 scanEhFrameSection(EhInputSection &EH,
 158                    std::function<void(InputSectionBase *, uint64_t)> Fn) {
 159   if (!EH.NumRelocations)
 160     return;
 161
 162   // Unfortunately we need to split .eh_frame early since some relocations in
 163   // .eh_frame keep other section alive and some don't.
 164   EH.split<ELFT>();
 165
 166   if (EH.AreRelocsRela)
 167     scanEhFrameSection<ELFT>(EH, EH.template relas<ELFT>(), Fn);
 168   else
 169     scanEhFrameSection<ELFT>(EH, EH.template rels<ELFT>(), Fn);
 170 }
 171
 172 // Some sections are used directly by the loader, so they should never be
 173 // garbage-collected. This function returns true if a given section is such
 174 // section.
 175 template <class ELFT> static bool isReserved(InputSectionBase *Sec) {
 176   switch (Sec->Type) {
 177   case SHT_FINI_ARRAY:
 178   case SHT_INIT_ARRAY:
 179   case SHT_NOTE:
 180   case SHT_PREINIT_ARRAY:
 181     return true;
 182   default:
 183     StringRef S = Sec->Name;
 184     return S.startswith(".ctors") || S.startswith(".dtors") ||
 185            S.startswith(".init") || S.startswith(".fini") ||
 186            S.startswith(".jcr");
 187   }
 188 }
 189
 190 // This is the main function of the garbage collector.
 191 // Starting from GC-root sections, this function visits all reachable
 192 // sections to set their "Live" bits.
 193 template <class ELFT> static void doGcSections() {
 194   SmallVector<InputSection *, 256> Q;
 195   CNamedSections.clear();
 196
 197   auto Enqueue = [&](InputSectionBase *Sec, uint64_t Offset) {
 198     // Skip over discarded sections. This in theory shouldn't happen, because
 199     // the ELF spec doesn't allow a relocation to point to a deduplicated
 200     // COMDAT section directly. Unfortunately this happens in practice (e.g.
 201     // .eh_frame) so we need to add a check.
 202     if (Sec == &InputSection::Discarded)
 203       return;
 204
 205
 206     // Usually, a whole section is marked as live or dead, but in mergeable
 207     // (splittable) sections, each piece of data has independent liveness bit.
 208     // So we explicitly tell it which offset is in use.
 209     if (auto *MS = dyn_cast<MergeInputSection>(Sec))
 210       MS->markLiveAt(Offset);
 211
 212     if (Sec->Live)
 213       return;
 214     Sec->Live = true;
 215
 216     // Add input section to the queue.
 217     if (InputSection *S = dyn_cast<InputSection>(Sec))
 218       Q.push_back(S);
 219   };
 220
 221   auto MarkSymbol = [&](Symbol *Sym) {
 222     if (auto *D = dyn_cast_or_null<Defined>(Sym))
 223       if (auto *IS = dyn_cast_or_null<InputSectionBase>(D->Section))
 224         Enqueue(IS, D->Value);
 225   };
 226
 227   // Add GC root symbols.
 228   MarkSymbol(Symtab->find(Config->Entry));
 229   MarkSymbol(Symtab->find(Config->Init));
 230   MarkSymbol(Symtab->find(Config->Fini));
 231   for (StringRef S : Config->Undefined)
 232     MarkSymbol(Symtab->find(S));
 233   for (StringRef S : Script->ReferencedSymbols)
 234     MarkSymbol(Symtab->find(S));
 235
 236   // Preserve externally-visible symbols if the symbols defined by this
 237   // file can interrupt other ELF file's symbols at runtime.
 238   for (Symbol *S : Symtab->getSymbols())
 239     if (S->includeInDynsym())
 240       MarkSymbol(S);
 241
 242   // Preserve special sections and those which are specified in linker
 243   // script KEEP command.
 244   for (InputSectionBase *Sec : InputSections) {
 245     // Mark .eh_frame sections as live because there are usually no relocations
 246     // that point to .eh_frames. Otherwise, the garbage collector would drop
 247     // all of them. We also want to preserve personality routines and LSDA
 248     // referenced by .eh_frame sections, so we scan them for that here.
 249     if (auto *EH = dyn_cast_or_null<EhInputSection>(Sec)) {
 250       EH->Live = true;
 251       scanEhFrameSection<ELFT>(*EH, Enqueue);
 252     }
 253
 254     if (Sec->Flags & SHF_LINK_ORDER)
 255       continue;
 256     if (isReserved<ELFT>(Sec) || Script->shouldKeep(Sec))
 257       Enqueue(Sec, 0);
 258     else if (isValidCIdentifier(Sec->Name)) {
 259       CNamedSections[Saver.save("__start_" + Sec->Name)].push_back(Sec);
 260       CNamedSections[Saver.save("__stop_" + Sec->Name)].push_back(Sec);
 261     }
 262   }
 263
 264   // Mark all reachable sections.
 265   while (!Q.empty())
 266     forEachSuccessor<ELFT>(*Q.pop_back_val(), Enqueue);
 267 }
 268
 269 // Before calling this function, Live bits are off for all
 270 // input sections. This function make some or all of them on
 271 // so that they are emitted to the output file.
 272 template <class ELFT> void elf::markLive() {
 273   // If -gc-sections is missing, no sections are removed.
 274   if (!Config->GcSections) {
 275     for (InputSectionBase *Sec : InputSections)
 276       Sec->Live = true;
 277     return;
 278   }
 279
 280   // The -gc-sections option works only for SHF_ALLOC sections
 281   // (sections that are memory-mapped at runtime). So we can
 282   // unconditionally make non-SHF_ALLOC sections alive.
 283   //
 284   // Non SHF_ALLOC sections are not removed even if they are
 285   // unreachable through relocations because reachability is not
 286   // a good signal whether they are garbage or not (e.g. there is
 287   // usually no section referring to a .comment section, but we
 288   // want to keep it.)
 289   //
 290   // Note on SHF_REL{,A}: Such sections reach here only when -r
 291   // or -emit-reloc were given. And they are subject of garbage
 292   // collection because, if we remove a text section, we also
 293   // remove its relocation section.
 294   for (InputSectionBase *Sec : InputSections) {
 295     bool IsAlloc = (Sec->Flags & SHF_ALLOC);
 296     bool IsRel = (Sec->Type == SHT_REL || Sec->Type == SHT_RELA);
 297     if (!IsAlloc && !IsRel)
 298       Sec->Live = true;
 299   }
 300
 301   // Follow the graph to mark all live sections.
 302   doGcSections<ELFT>();
 303
 304   // Report garbage-collected sections.
 305   if (Config->PrintGcSections)
 306     for (InputSectionBase *Sec : InputSections)
 307       if (!Sec->Live)
 308         message("removing unused section from '" + Sec->Name + "' in file '" +
 309                 Sec->File->getName() + "'");
 310 }
 311
 312 template void elf::markLive<ELF32LE>();
 313 template void elf::markLive<ELF32BE>();
 314 template void elf::markLive<ELF64LE>();
 315 template void elf::markLive<ELF64BE>();