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

   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
  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 template <class ELFT> class MarkLive {
  47 public:
  48   MarkLive(unsigned partition) : partition(partition) {}
  49
  50   void run();
  51   void moveToMain();
  52
  53 private:
  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
  76 template <class ELFT>
  77 static 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
  83 template <class ELFT>
  84 static uint64_t getAddend(InputSectionBase &sec,
  85                           const typename ELFT::Rela &rel) {
  86   return rel.r_addend;
  87 }
  88
  89 template <class ELFT>
  90 template <class RelTy>
  91 void 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.
 134 template <class ELFT>
 135 template <class RelTy>
 136 void 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.
 164 static 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
 179 template <class ELFT>
 180 void 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
 206 template <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.
 215 template <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
 271 template <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).
 294 template <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.
 308 template <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
 370 template void elf::markLive<ELF32LE>();
 371 template void elf::markLive<ELF32BE>();
 372 template void elf::markLive<ELF64LE>();
 373 template void elf::markLive<ELF64BE>();