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 removed from output. 20 // 21 //===----------------------------------------------------------------------===// 22 23 #include "InputSection.h" 24 #include "OutputSections.h" 25 #include "SymbolTable.h" 26 #include "Symbols.h" 27 #include "Writer.h" 28 #include "llvm/ADT/STLExtras.h" 29 #include "llvm/Object/ELF.h" 30 #include <functional> 31 #include <vector> 32 33 using namespace llvm; 34 using namespace llvm::ELF; 35 using namespace llvm::object; 36 37 using namespace lld; 38 using namespace lld::elf2; 39 40 // Calls Fn for each section that Sec refers to. 41 template <class ELFT> 42 static void forEachSuccessor(InputSection<ELFT> *Sec, 43 std::function<void(InputSectionBase<ELFT> *)> Fn) { 44 typedef typename ELFFile<ELFT>::Elf_Rel Elf_Rel; 45 typedef typename ELFFile<ELFT>::Elf_Rela Elf_Rela; 46 typedef typename ELFFile<ELFT>::Elf_Shdr Elf_Shdr; 47 48 ELFFile<ELFT> &Obj = Sec->getFile()->getObj(); 49 for (const Elf_Shdr *RelSec : Sec->RelocSections) { 50 if (RelSec->sh_type == SHT_RELA) { 51 for (const Elf_Rela &RI : Obj.relas(RelSec)) 52 if (InputSectionBase<ELFT> *Succ = Sec->getRelocTarget(RI)) 53 Fn(Succ); 54 } else { 55 for (const Elf_Rel &RI : Obj.rels(RelSec)) 56 if (InputSectionBase<ELFT> *Succ = Sec->getRelocTarget(RI)) 57 Fn(Succ); 58 } 59 } 60 } 61 62 // Sections listed below are special because they are used by the loader 63 // just by being in an ELF file. They should not be garbage-collected. 64 template <class ELFT> static bool isReserved(InputSectionBase<ELFT> *Sec) { 65 switch (Sec->getSectionHdr()->sh_type) { 66 case SHT_FINI_ARRAY: 67 case SHT_INIT_ARRAY: 68 case SHT_NOTE: 69 case SHT_PREINIT_ARRAY: 70 return true; 71 default: 72 StringRef S = Sec->getSectionName(); 73 return S.startswith(".init") || S.startswith(".fini") || 74 S.startswith(".jcr") || S == ".eh_frame"; 75 } 76 } 77 78 template <class ELFT> void lld::elf2::markLive(SymbolTable<ELFT> *Symtab) { 79 SmallVector<InputSectionBase<ELFT> *, 256> Q; 80 81 auto Enqueue = [&](InputSectionBase<ELFT> *Sec) { 82 if (!Sec || Sec->Live) 83 return; 84 Sec->Live = true; 85 Q.push_back(Sec); 86 }; 87 88 auto MarkSymbol = [&](SymbolBody *Sym) { 89 if (Sym) 90 if (auto *D = dyn_cast<DefinedRegular<ELFT>>(Sym->repl())) 91 Enqueue(&D->Section); 92 }; 93 94 // Add GC root symbols. 95 MarkSymbol(Config->EntrySym); 96 MarkSymbol(Symtab->find(Config->Init)); 97 MarkSymbol(Symtab->find(Config->Fini)); 98 for (StringRef S : Config->Undefined) 99 MarkSymbol(Symtab->find(S)); 100 101 // Preserve externally-visible symbols if the symbols defined by this 102 // file could override other ELF file's symbols at runtime. 103 if (Config->Shared || Config->ExportDynamic) { 104 for (const std::pair<StringRef, Symbol *> &P : Symtab->getSymbols()) { 105 SymbolBody *B = P.second->Body; 106 if (B->getVisibility() == STV_DEFAULT) 107 MarkSymbol(B); 108 } 109 } 110 111 // Preserve special sections. 112 for (const std::unique_ptr<ObjectFile<ELFT>> &F : Symtab->getObjectFiles()) 113 for (InputSectionBase<ELFT> *Sec : F->getSections()) 114 if (Sec && Sec != &InputSection<ELFT>::Discarded) 115 if (isReserved(Sec)) 116 Enqueue(Sec); 117 118 // Mark all reachable sections. 119 while (!Q.empty()) 120 if (auto *Sec = dyn_cast<InputSection<ELFT>>(Q.pop_back_val())) 121 forEachSuccessor<ELFT>(Sec, Enqueue); 122 } 123 124 template void lld::elf2::markLive<ELF32LE>(SymbolTable<ELF32LE> *); 125 template void lld::elf2::markLive<ELF32BE>(SymbolTable<ELF32BE> *); 126 template void lld::elf2::markLive<ELF64LE>(SymbolTable<ELF64LE> *); 127 template void lld::elf2::markLive<ELF64BE>(SymbolTable<ELF64BE> *); 128